Questions tagged [clustering]
Clustering is an unsupervised learning problem. It deals with finding "clusters" or groups in a collection of unlabeled data. A cluster is therefore a collection of objects which are “similar” and are “dissimilar” to the objects belonging to other clusters.
72
questions
16
votes
0
answers
481
views
a geometric variant of k-medians. NP-hard or in P?
The following problem is a special case of k-medians. Is it NP-hard? Is it in P?
Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$.
Output: a set ...
- 9,595
12
votes
5
answers
575
views
clustering algorithm for non-dimensional data
i have a dataset of thousands of points and a means of measuring the distance between any two points, but the data points have no dimensionality. i want an algorithm to find cluster centers in this ...
- 223
12
votes
2
answers
514
views
Euclidean-squared max-cut in low dimensions
Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that ...
- 121
11
votes
2
answers
355
views
Clustering formalizations other than K-means for separable data
Real world data sometimes has a natural number of clusters (trying to cluster it into a number of cluster lesser than some magic k will cause a dramatic increase the clustering cost). Today I attended ...
9
votes
4
answers
456
views
Continuous Clustering
So I have an issue I'm facing in regards to clustering with live, continuously streaming data. Since I have an ever-growing data set I'm not sure what is the best way to run efficient and effective ...
brian
9
votes
2
answers
5k
views
Computational complexity of clustering algorithms
My wish is to describe the time complexity of several clustering approaches. For example, suppose we have $n$ data points in $m$ dimensional space.
Suppose further that the pairwise dissimilarity ...
- 251
9
votes
1
answer
291
views
Bisecting a set of points into two optimal subsets
I want to divide a set of points into two equally-sized subsets such that the within-cluster sum of squares is minimized. We can assume that the points are in two-dimensional Euclidian space. I'm ...
- 121
9
votes
1
answer
382
views
Finding similar vectors in subquadratic time
Let $d:\{0,1\}^k\times \{0,1\}^k \to \mathbb{R}$ be a function which we refer to as the similarity function.
Examples of similarity function are
cosine distance, $l_2$ norm, Hamming distance, Jaccard ...
- 639
7
votes
1
answer
993
views
K-Clustering of a Graph maximizing intra-cluster weights?
I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.
Input: A complete graph G with non-...
- 261
6
votes
1
answer
291
views
Good Survey paper for k-means/k-median/k-center/facility-location
I have stated 4 problems in the Question title.
All these problems are closely related and are studied in various variations. For example:
Space: Euclidean/metric/discrete/continuous/non-metric/2-...
- 1,471
6
votes
0
answers
235
views
Does k-Median problem become any easier when L = C?
In the $k$-median problem, $L$ defines as set of feasible facility locations and $C$ defines a set of client locations in a metric space.
The current best approximation guarantee for the problem is $2....
- 1,471
5
votes
2
answers
239
views
kmeans++ for arbitrary metric spaces and general potential function
I was reading this popular paper "k-means++: The Advantages of Careful Seeding". It appeared in SODA 2007. Since this technique is the most popular clustering technique, I am hoping that my question ...
- 1,471
5
votes
1
answer
339
views
k-clustering problems
I'm interested in open questions from the book Approximation Algorithms for NP-Hard Problemss dedicated to k-clustering. They are:
Is Euclidean max cut solvable in polynomial time? If not, how well ...
5
votes
1
answer
159
views
PTAS Algorithm for K-Clustering when Distance Computation is Costly
Can anyone throw any light on any PTAS algorithm that I can apply for K-Clustering algorithm when the distance computation between the clustering points is costly.
In details, I have a set of N ...
- 101
5
votes
0
answers
158
views
Exact algorithms for $k$-means
Lets recall the definition of $k$-means clustering for euclidean spaces.
Let $X$ be a set of $n$ points in $R^d$ and $k$ a given natural number. Let $C$ any $k$ clustering of $X$. Define the cost of $...
- 189
4
votes
1
answer
346
views
Approximation Ratio of Local search for $k-$center problem
In the $k-$center problem, you're given $V$ points in Eucledian space, and you're asked to get a subset $C\subset V, |C|=k$ such that $\max _{v\in V}d(v, Closest-Center(C,v))$ is minimized.
Now I am ...
- 1,058
4
votes
1
answer
264
views
Higher-order and black-box clustering
As far as I understand a large number of clustering problems can be formulated as:
$\underset{\textbf{P}}{ \text{argmin}} \; \sum_{i,j} f \left(x_i, x_j\right)$
where $\textbf{P}$ is a partitioning ...
4
votes
1
answer
115
views
A counter example for the set mean objective
Let $\mathcal{P} = \{P_1, \cdots,P_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function
\begin{align}
cost(\mathcal{P},c) =...
- 265
4
votes
1
answer
190
views
Kleinberg-consistency of spectral clustering
Spectral clustering refers to a family of graph-based algorithms, which usually rely on a similarity function rather than a metric, though a metric $\rho(x,y)$ can always be converted to a similarity ...
- 10.2k
3
votes
2
answers
442
views
Is there any Bi-criteria PTAS for Metric $k$-Median?
The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the ...
- 1,471
3
votes
1
answer
95
views
Centroid in $\ell_2$ distance
Given points $x_1, x_2, \cdots, x_n \in \mathbb{R}^d$. What is the complexity of computing
$$
argmin_{x}\left(\sum_{i=1}^n ||x_i-x||_2\right)
$$
- 771
3
votes
0
answers
86
views
Exact FPT Algorithm for Continuous Euclidean $k$-Means
The continuous Euclidean $k$-means problem is defined as follows:
Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ ...
- 1,471
3
votes
0
answers
153
views
Incorrect Lower Bound of k-Means++ Algorithm
The $k$-means++ algorithm is composed of two parts:
Initialization part: the initial $k$ centers are chosen based on $D^2$ sampling.
Expectation maximization part: the standard $k$-means algorithm (...
- 1,471
3
votes
0
answers
122
views
Finding most informative feature subsets given dataset, clustering algorithm and gold standard partition
I have an $n \times m$ matrix of data $\mathbf{D}$ as well as a $k$-partition $P$ of $n$ indices each representing a row in a dataset. Assuming an arbitrary clustering algorithm $A$, I would like to ...
- 61
2
votes
1
answer
209
views
Clustering massive data sets in practice
If you have a very large data set of $n$ vectors and you want to cluster them according to some metric measure, what is the current state of the art when you can not afford to do more than $\Theta(n)$ ...
- 333
2
votes
1
answer
227
views
Determining the number of clusters using property testing algorithm
We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of paper) which consider a promise version of ...
- 639
2
votes
1
answer
1k
views
Max-sum graph-partition for maximizing intra-edge weights?
I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.
Input: A graph G with negative or non-...
- 21
2
votes
1
answer
103
views
Approximating the value of k in $k$-mean clustering problem
Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by ...
- 639
2
votes
1
answer
211
views
an axiomatic framework for clustering by jon kleinberg may have a problem?
In the paper An Impossibility Theorem for Clustering, Jon Kleinberg introduced an axiomatic framework for clustering and showed that his set of axioms are inconsistent. One of the axioms is the ...
- 61
2
votes
1
answer
188
views
Divide and Conquer Algorithm for 1-Median Problem
Let $P_1$ and $P_2$ be two disjoint point sets in $\mathbb{R}^d$ and $n = \vert P_1\vert = \vert P_2\vert$ and $P = P_1\cup P_2$. Let $c^\star$ be the optimal 1-median for $P$ and $opt^\star$ is the ...
- 265
2
votes
1
answer
534
views
K-NN or matrix factorization for discovering correlated features?
I am looking to cluster users together in a database, with each user represented by a number of features that are both discrete and continuous in nature. "Similar" users should be clustered together ...
DanB
2
votes
1
answer
628
views
The non-metric k-median problem
It is well-known that the non-metric $k$-median problem cannot be approximated better than $O(\log(n))$ (by a gap preserving reduction from the set cover problem). Is there any logarithmic ...
- 741
2
votes
0
answers
92
views
NP-hardness of Euclidean k-Median for k = 2
In the Euclidean $k$-median problem, we are given a set $C$ of clients in $\mathbb{R}^d$. The task is to open a set $F \subset \mathbb{R}^d$ of $k$ facilities such that the cost function $\Phi(F) = \...
- 1,471
2
votes
0
answers
40
views
Concept of 'shape' in clustering
Is there any abstract definition for 'shapes' of a cluster?
I am currently working on providing for a set of axioms to study clustering. In my work, I have found a need for an abstract definition for ...
- 61
2
votes
0
answers
154
views
Quality measure for clusters of a metric space embedding of a graph?
When evaluating clustering algorithms for networks, we have well-established metrics like Modularity and Surprise for evaluating the quality of the resulting partition.
If we then embed our graph (...
- 161
2
votes
0
answers
242
views
Grouping a set of rectangles in larger rectangular regions
I have a set of rectangles, which I want to cluster (group) as shown here(I can not post images yet, so please bear with me).
The approach I took was to consider central points of each rectangle as a ...
- 131
1
vote
2
answers
187
views
Classic parallel clustering algorithms
I'm starting a research about parallel clustering. I see a ton of articles on this topic, so that I don't know where to start. I'd like to get familiar with classic methods of parallelizing clustering....
- 111
1
vote
1
answer
55
views
$k-$median problem and filtering technique Lin and Vitter
I read a paper from Tardos et al. about $k-$medians in metric space problem:
Given $N$ as set of points in metric space with distance function $c_{ij}$ for each $i,j\in N$, demand $d_i$ for each point ...
- 113
1
vote
1
answer
120
views
Scoring set of points based on clustering
I have a sparse set of points with unpredictable locations. I need a way of "scoring" each set of points such that clustering is rewarded. My working case is actually one dimensional, but a two ...
- 119
1
vote
1
answer
109
views
partitioning points in the plane into two clusters to minimize maximum cluster diameter
What is a fast algorithm for the following problem?
input: a set of $n$ pairs of points in the Euclidean plane
output: a partition of the points into two clusters so that, for each given pair, the ...
- 9,595
1
vote
2
answers
2k
views
Hyperspherical nature of K-means and similar clustering methods
Jain, Murty, and Flynn
state in their article Data Clustering: A Review
all squared error based clustering methods like K-means
tend to generate hyperspherical clusters.
However, they do not give a ...
- 131
1
vote
1
answer
894
views
Simple k-nearest-neighbor algorithm for euclidean data with highly variable density?
An elaboration on this question, but with more constraints.
The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions. The bucketing grid seems to work ...
- 161
1
vote
1
answer
633
views
Clustering of letters - what approach would give the best results?
I am working on letter recognition program. I have a text and divide it into letters, every single letter is written to separate file.
Now I want to apply a clustering algorithm to these images to ...
- 111
1
vote
1
answer
198
views
Graph partitioning to minimize sum of intra-partition edge weights
I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
- 11
1
vote
0
answers
52
views
Failing to understand a lemma regarding Robust Low Rank Approximation
I am reading Low Rank Approximation in the Presence of
Outliers by Bhaskara and Kumar and kind of stuck at the proof of Lemma 9. The paper studies robust (to outliers) low rank approximation problem. ...
- 265
1
vote
0
answers
47
views
A variant of k-median clustering
Suppose $\mathcal{P} =\{P_1,\cdots,P_n\}$ is a family of $n$ finite sets in $\mathbb{R}^d$. Given set $C=\{c_1,\cdots,c_k\}$ of $k$ points, consider the follwoing objective funtion
$cost(\mathcal{P},C)...
- 265
1
vote
0
answers
37
views
A continuum version of the 1D k-means clustering problem: constant factor approximations
Modify the k-means clustering problem in 1D by assuming that, instead of a finite number of observations, we must classify into $K$ clusters a continuum of observations, distributed on the unit ...
- 33
1
vote
0
answers
85
views
k-center 2.0: A stronger k-center condition
Given an unweighted, undirected graph, we can use the classical 2-appx for $k$-center to select a set $S$ of centers such that every vertex is within a distance of 2 of some center in $S$.
Note that ...
- 607
1
vote
0
answers
112
views
algorithms for a large submatrix / general factor / quasi-biclique problem?
Given a sparse 0/1 matrix $X$, too large to fit in memory, with $m$ rows and $n$ columns, I'm looking for an algorithm for finding a submatrix (when one exists) with maximum number of rows such that ...
- 145
1
vote
0
answers
55
views
Clustering algorithm for image metric
Im working on image clustering (finding duplicates). I have a metric for images, it uses histogram features (mean, dispersion, skewnewss) for each color channel. So there are 9 dimensions. It is quite ...
- 111