# 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.

52 questions
Filter by
Sorted by
Tagged with
111 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-...
71 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 ...
43 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 ...
21 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-...
75 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 ...
80 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)$$
181 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 ...
104 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 ...
239 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 ...
746 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-...
54 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 ...
37 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 ...
161 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 ...
372 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 ...
99 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 ...
211 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 ...
514 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, ...
157 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 ...
243 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 ...
511 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 ...
124 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 (...
1k 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 ...
350 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 ...
508 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 ...
222 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 ...
1k 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 ...
420 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?
206 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)$ ...
141 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 ...
183 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....
898 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-...
179 views

### Clustering without specifying the number of clusters apriori

Does anyone know of an algorithm that can perform the following tasks: Unsupervised clustering without specifying the number of clusters apriori. For example if all the buildings in wide geographical ...
120 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 ...
128 views

### Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D [closed]

I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...
110 views

### Techniques to get nodes in the best Markov Cluster?

I was using Markov Clustering to cluster nodes in my bidirectional graph, and overall the results were great. However, there were a couple instances where a weakly connected node would attract a node ...
868 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 ...
329 views

### Divide-and-conquer approach for hierarchical clustering

I have a huge data set (33K), each represented as a bit-vector of 275-dimensions. Basically my data set can be represented as a $33000 \times 275$ matrix. I want to cluster these bit-vectors. I have ...
287 views

### Fuzzy K-modes clustering how to find the cluster centers

I'm trying to understand [fuzzy k-modes] algorithm (look mainly at page 3) in order to implement it. I'm stuck at the calculation of cluster centers they said as shown in the link https://...
259 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 ...
210 views

### K-means with centres outside the data?

Say we want to split a cube in $\mathbb{R}^{64}$ into 10 pieces. NN, nearest-neighbor or Voronoi splits, take 10 cluster centres $c_0, \ldots, c_9$ in the cube, e.g. from K-means, then classify a new ...
255 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 ...
114 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 ...
417 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 ...
149 views

### A better way to cluster items

I am working on a text processer which gives out similarities between a set of strings. After weighted LCS, Levenshtein distance and double metaphone matching, I get buckets of strings such as ...
193 views

### clustering (lat,lng) pairs, with clusters having the same number of elements

Imagine you have a list of (lat,lng) pairs. You have k employees. And you want each employee to visit roughly the same number of places, making the least distance possible. I've tried to solve this ...
465 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 ...
4k 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 ...
377 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 ...