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.
75 questions
1
vote
1
answer
75
views
Approximation of a variant of facility location problem
I'm thinking about a variant of the facility location problem. Given a set of cities $C$ and facilities $F$, we want to open a subset $S \subseteq F$ of facilities such that the following is minimized:...
- 121
1
vote
1
answer
91
views
Approximations of graph clustering
Consider the task of clustering a graph, modelled as the balanced cut problem:
Input: $G = (V, E)$ simple graph
Output: $S^* \subseteq V$ such that $S^* = \arg\min_{S \subseteq V} h(S)$.
Here, $h(S)$ ...
- 113
3
votes
2
answers
175
views
Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes
Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes.
Does this have a constant approximation?
($p,k$ and the graph are all part of the ...
- 228
1
vote
1
answer
61
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 ...
- 210
1
vote
0
answers
303
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
2
votes
0
answers
115
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,551
4
votes
1
answer
121
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
0
votes
0
answers
75
views
k-Median Problem With Restricted Centers
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,551
2
votes
1
answer
210
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
3
votes
0
answers
93
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,551
1
vote
1
answer
166
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 ...
- 10.9k
1
vote
0
answers
53
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
0
votes
0
answers
115
views
How general cost function for $p = \log n$ is the $k$-center cost function?
The $k$-clustering 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,551
1
vote
0
answers
50
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
0
votes
1
answer
59
views
How to build the tree with the "most different" solutions of a clustering?
Illustrate the question with an example : we have a similarity matrix for 1000 people, and the similarity represents how much their hobbies are the same (it does not really matter how it's built).
Let'...
- 109
3
votes
2
answers
519
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,551
3
votes
0
answers
176
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,551
6
votes
0
answers
248
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,551
1
vote
0
answers
43
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
5
votes
0
answers
162
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 $...
- 319
-1
votes
1
answer
84
views
Al-Mubaid's Similarity Measure for Ontological Concepts
Al-Mubaid et al. proposed a semantic similarity measure in their research paper [1]. They see ontologies as connected graphs but refer to clusters within ontology graphs without ever defining what ...
- 11
6
votes
1
answer
319
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,551
5
votes
2
answers
252
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,551
4
votes
1
answer
423
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,163
0
votes
0
answers
52
views
What is the meaning of an Oracle in data clustering?
I am not sure whether this is the best place to ask this question. I am in the process of researching the area in data clustering as well as the algorithms that are associated with it and the term ...
- 11
0
votes
0
answers
35
views
Does optimal fitting flat must pass through the mean of the point set?
I am confused about a statement made in the paper Linear Time Algorithm for Projective Clustering, section 5.1, second paragraph, second line.
Project clustering is a natural generalization of k-...
- 265
1
vote
0
answers
90
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 ...
- 649
3
votes
1
answer
96
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)
$$
- 791
4
votes
1
answer
195
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.6k
1
vote
0
answers
114
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
0
votes
1
answer
271
views
Cluster Edge Deletion on 2-trees
Definitions:
Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced ...
- 9
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
1
vote
0
answers
57
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
16
votes
0
answers
506
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 ...
- 10.9k
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
1
answer
237
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
9
votes
1
answer
386
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
2
votes
1
answer
104
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
0
votes
0
answers
216
views
Clustering in sublinear time/query
Given a set of $n$ points in $R^d$, the goal is to cover them with (finitely many) unit balls such that following conditions satisfy:
1) Minimizing the number of balls that are required to cover all ...
- 639
0
votes
1
answer
668
views
What is a minimum vertex separator as in this definition?
In a research paper the following definition appears that I'm not able to understand completely.
Let $G=(V,E)$ be an undirected unweighted graph with vertex set $V$ and edge set $E$, no self-loops, ...
- 221
2
votes
1
answer
217
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
9
votes
1
answer
301
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
1
vote
0
answers
785
views
Splitting a graph into size constrained clusters
I ran across a problem while working on an algorithm for a game I'm making on the side. It's basically a clustering problem where we have a graph G and want to split it into clusters of equal size ...
- 11
2
votes
0
answers
157
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
-1
votes
1
answer
2k
views
Time complexity analysis of random forest and k-means?
I am working with random forest for a supervised classification problem, and I am using the k-means clustering algorithm to split the data at each node, where
$n$ is the number of points,
$K$ is ...
2
votes
1
answer
710
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
1
vote
0
answers
538
views
Time complexity of clustering based on random walk
What is the time complexity of the following algorithm (from this paper suggested by Zhou) to partition directed graph?
Can I use the complexity of eigen vector computation for this purpose?
The ...
- 11
2
votes
0
answers
249
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
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
votes
1
answer
450
views
Canopy clustering: what should we do with samples in overlapping canopies?
In canopy clustering http://www.kamalnigam.com/papers/canopy-kdd00.pdf, if a sample falls in an overlap of 2 canopies, how do we choose its cluster?
- 197