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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
44 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
132 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
89 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) = \...
4 votes
1 answer
114 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) =...
0 votes
0 answers
68 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 ...
2 votes
1 answer
180 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 ...
3 votes
0 answers
84 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 vote
1 answer
93 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,380
1 vote
0 answers
51 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. ...
0 votes
0 answers
105 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 vote
0 answers
46 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)...
0 votes
1 answer
57 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
411 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 ...
3 votes
0 answers
141 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 (...
6 votes
0 answers
229 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 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 ...
5 votes
0 answers
156 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 $...
  • 181
-1 votes
1 answer
82 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 ...
6 votes
1 answer
275 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-...
5 votes
2 answers
234 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 ...
4 votes
1 answer
275 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 ...
0 votes
0 answers
45 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
33 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-...
1 vote
0 answers
83 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 ...
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) $$
4 votes
1 answer
189 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
1 vote
0 answers
111 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 ...
0 votes
1 answer
250 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 ...
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
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
16 votes
0 answers
469 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,380
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 ...
2 votes
1 answer
225 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 ...
  • 629
9 votes
1 answer
380 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 ...
  • 629
2 votes
1 answer
102 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 ...
  • 629
0 votes
0 answers
215 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 ...
  • 629
0 votes
1 answer
643 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
210 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 ...
9 votes
1 answer
282 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 ...
1 vote
0 answers
677 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
153 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
609 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 ...
1 vote
0 answers
536 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
238 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
436 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
2 votes
1 answer
208 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
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 ...
1 vote
2 answers
185 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