As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [clustering]

Clustering is the problem of finding groups of data points (often modelled as nodes in a graph) that are closer to each other than to other points.

Filter by
Sorted by
Tagged with
30 votes
4 answers
70k views

What exactly is the difference between supervised and unsupervised learning?

I am trying to understand clustering methods. What I I think I understood: In supervised learning, the categories/labels data is assigned to are known before computation. So, the labels, classes or ...
Prot's user avatar
  • 403
8 votes
1 answer
622 views

Under what conditions is K-means clustering transformation-invariant?

Given a set of data points $X = \{x_1, x_2, \ldots, x_m\}$ where $x_i \in \mathbb{R}^d$ we run K-means on $X$ and obtain the clusters $c_1, c_2, \ldots, c_k$. Now, if we create a new dataset $Y = \{...
Ana Echavarria's user avatar
6 votes
1 answer
975 views

How to compare/cluster millions of strings?

I have around 1,000,000 of strings of variable length (from 200 to 50000) that can contain 5 characters (A, B, C, D, E). What I actually want is to cluster them together if they are similar enough. ...
Ivan's user avatar
  • 273
5 votes
2 answers
692 views

Efficiently partition tree into clusters of similar diameter

I am looking for a way to split a tree into $k$ clusters so that the cluster with largest diameter is as small as possible. All edges have the same length. I'm hoping for an algorithm that can handle ...
Bartosz's user avatar
  • 51
5 votes
1 answer
82 views

k-means clustered data: how to label newly incoming data

I have a data set with labels that were produced by a $k$-means clustering algorithm. Now there is some data (with the same data structure) from another source and I wonder what is the most sensible ...
Uli Niklas's user avatar
5 votes
1 answer
2k views

How is the (local) clustering coefficient defined for vertices with degree 1

We want to compute the clustering coefficient $C$ for an undirected graph $G = (V, E)$. The clustering coefficient $C$ for a graph $G$ is the average over all local clustering coefficients $C_i$, ...
confusedstudent's user avatar
4 votes
1 answer
135 views

What is the global function we are trying to Optimise with Clustering Algorithms?

I am doing some reading (and implementation) of some Clustering Algorithms. First I started with the well known K-Mean algorithm and implemented it directly from a paper. Got a kind of decent ...
Frames Catherine White's user avatar
4 votes
1 answer
714 views

How to calculate the minimum number of groups, by grouping groups with capacity together?

I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem. If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the ...
Ricardo Jesus's user avatar
4 votes
2 answers
195 views

Creating Best Clusters of Objects Based on Distance Between Them

I have an array of images. And, there is a function that calculates the distance between two images. I wish to cluster the images based on this distance. So the clusters contain images that are all ...
meaning-matters's user avatar
4 votes
1 answer
1k views

Finding similar high dimensional real vectors

I have a collection of vectors $v_1,v_2\in [0,1]^n$ and I want to find similar pairs quickly. For similarity, I want to use the Euclidean distance metric $L: [0,1]^n \times [0,1]^n \longrightarrow R$. ...
AdrianGW's user avatar
4 votes
2 answers
1k views

Fast algorithm for clustering groups of elements given their size/time

I don't know if there is a canonical problem reducing my practical problem, so I will just try to describe it the best that I can. I would like to cluster files into the specified number of groups, ...
gaborous's user avatar
  • 346
4 votes
1 answer
324 views

How to group intervals which overlap by some amount?

I have an algorithm that generates a list of intervals. The algorithm is run m times. Lets mark the intervals as tuples (s1, e1), (s2, e2), .., (sn, en). It is ...
mibm's user avatar
  • 149
4 votes
0 answers
155 views

Find a dynamic programming solution that minimize the sum of the diameters of two clusters?

I asked a question at this link, where I suggested a greedy algorithm for this problem: Suppose given $2n$ points in the plane and we want partition points into two clusters $C_1$ , $C_2$ such that ...
All's user avatar
  • 83
4 votes
0 answers
44 views

K-means, but normalized and with max

Given points $x_1, \ldots, x_n$ in the Euclidean space and $K \in \mathbb N$, I'm interested in the following objective. Partition the points into $K$ clusters $C_1, \ldots, C_K$ so that: $$\max_{i \...
Dmitry's user avatar
  • 304
4 votes
0 answers
38 views

Finding the "most modular" subset of graph vertices, i.e. that minimize disagreement inside and outside

Let $G = (V, E)$ be a graph. I want to find the subset of vertices of $G$ that minimizes a certain modularity cost. In our setting, the modularity cost of a subset $X$ is defined as the number of ...
Manuel Lafond's user avatar
4 votes
0 answers
313 views

Persistent Homology vs Clustering Methods

How do persistent homology and clustering methods for data point clouds differ? I'm specifically interested in the application to gene expression data of cancer patients, but any example works. I ...
Emil_Longshore's user avatar
4 votes
1 answer
124 views

How to cluster similar objects into fixed size groups?

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day. eg - Suppose there ...
ask's user avatar
  • 221
3 votes
1 answer
748 views

Implement K-means clustering with Map-Reduce

Recently in an interview I was asked to implement k-means clustering using the Map Reduce architecture. I know how to implement a simple k-means clustering algorithm but couldn't wrap my head around ...
user2966197's user avatar
3 votes
1 answer
689 views

What are the (efficient) algorithms to cluster squares into groups using a threshold such that the closest squares form groups?

I have a set of rectangles that needed to be grouped based on their locations. (All the rectangles follow the same orientation.) Two rectangles would be in the same group if the distance between them ...
Wickramaranga's user avatar
3 votes
1 answer
260 views

Optimal way for grouping events

I am creating an event notification system. Each event has a user and a subject, such that, 'user did event to the subject'. Now while presenting these the events need to be grouped. All the events ...
Optimus's user avatar
  • 133
3 votes
1 answer
312 views

Densely connected non overlapping subgraph

I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster. I'm currently trying to detect community using Louvain algorithm, but it ...
adp7's user avatar
  • 33
3 votes
1 answer
145 views

Is an $\mathcal{O}(n\times \text{Number of clusters})$ clustering algorithm useful?

I am a physicist, with little formal training in computer science - please don't assume I know even obvious things about computer science! Within the context of data analysis, I was interested in ...
innisfree's user avatar
  • 145
3 votes
1 answer
805 views

CURE algorithm: what does moving the representative points towards the centroid do?

The CURE algorithm is a method of clustering data. An outline of it can be found here on slide 5: https://www.slideshare.net/ellepiu/cure-clustering-algorithm. I personally learnt it from this video: ...
quanty's user avatar
  • 205
3 votes
1 answer
360 views

Least squares fit of a 1D lattice of points to a 2D dataset

Given a set of data points (shown in red), it is possible to fit a line $y = mx + c$ through the points using linear least squares regression. I would like to modify this to fit a 1D lattice (grid) ...
Rehno Lindeque's user avatar
3 votes
2 answers
220 views

The nearest points in a set

I have $N$ points and I have a distance between every pair of points stored in a 2D matrix. The goal is to find the nearest $K$ points among these $N$ points. "Nearest" means the sum of all distances ...
jackykuo's user avatar
3 votes
1 answer
116 views

Analysis and classification based on data points

I'm not sure if this is the correct stack exchange or correct tags, but my question is as follows: I am working on a sort-of ratings system for players in a particular game. After allowing the ...
ctlaltdefeat's user avatar
3 votes
1 answer
60 views

A heuristic for finding the vector that is maximally distant from a set of vectors

I have two sets of vectors: A and B. I want to find the vector Bi in set ...
magnetlion's user avatar
3 votes
1 answer
155 views

(DROP) Data Reduction Algorithm - How it works?

I am studing a PHD framework which the propose is to reduce the dataset with the most representative samples for training a classifier. Maybe I am loosing something, but I could not undestand a ...
rej's user avatar
  • 31
3 votes
1 answer
61 views

Graph families with high $k$-community

Just a quick question here, is there a known description of a graph family where for every graph $G=(V,E)$ it holds that for every $(u,v) \in E$ you have $|N(u) \cap N(v)| \geq k$? There was a ...
Eugene's user avatar
  • 1,086
3 votes
1 answer
1k views

How can k-means be reduced to Integer Programming

The k-means algorithm reduces to computing the objective function: $ \underset{\textbf{S}}{\operatorname{argmax}} \sum_{i=1}^k \sum_{\textbf{x}_j\in\textbf{S}_i} \lVert \textbf{x}_j - \mathbf{\mu}_i ...
user13675's user avatar
  • 1,594
3 votes
0 answers
34 views

Is there an algorithm polynomial in dimension of space and number of points for the Minimum Enclosing Ball?

Let $C_1, ..., C_m \in \mathbb{R}^n$ Is there a polynomial algorithm in $n,m$ which finds the Minimum Enclosing Ball (MEB) for these points? My research I see mentions of algorithms like Megido, Waltz ...
C Marius's user avatar
  • 185
3 votes
0 answers
26 views

Algorithm to separate single contour of glyph into several strokes?

A glyph contour contains points set {p}, a point contains tuple (x,y,on_curve). Now, think about this need, converting contour of glyph X, for example, into to two contour parts or two strokes, point ...
oner ptkh's user avatar
3 votes
0 answers
117 views

How to map points in high-dimensional space into dense grid in lower-dimensional space?

A formal description of the problem: Given a set $P$ of $n^k$ points in $d$ dimensional space, what algorithm can I use to find a mapping between them and points on a $n \times n \times n...$ grid in ...
Alecto Irene Perez's user avatar
3 votes
0 answers
87 views

Document clustering for summarization

I am curious as to what steps one would reasonably need to take to perform an extraction-based text summarizer. I've taken a look at some papers I've found on Google such as this one, which explains ...
DaniG2k's user avatar
  • 131
2 votes
3 answers
285 views

How to calculate IV, EV and optimal k for K-means?

Could someone explain how to calculate the following 3 evaluative properties: Intercluster Variability (IV) - How different are the data points within the same cluster Extracluster Variability (EV) - ...
Tesla's user avatar
  • 43
2 votes
1 answer
148 views

Group time series events into minimal amount of buckets

I'm trying to efficiently compute events in a time series by grouping them into buckets. My goal is to have as few buckets as possible. The constraint is that events within one bucket are all within a ...
Daniel's user avatar
  • 123
2 votes
2 answers
162 views

What happens when you don't use a metric in k-means?

K-means is a clustering algorithm which works like this: ...
Martin Thoma's user avatar
  • 2,340
2 votes
2 answers
1k views

Visualize Graph Clusters

I am working on my thesis which involves using ant based techniques for graph clustering. I am testing the algorithm currently and I was wondering if there is a way that I can visualize the clusters ...
muddy's user avatar
  • 314
2 votes
1 answer
39 views

Understanding contradiction in proof of Algorithm for Testing of Clustering of points in metric space in sub-linear time

I am trying to understand this paper, in which (k, b)-clusterability is defined like so: A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...
Gulzar's user avatar
  • 193
2 votes
1 answer
1k views

What is parallel virtual machine (pvm) and how it's different from mpi (message passing interface)

I am learning beowulf cluster. And I want to know what is pvm and how it's work and there is any difference between mpi and pvm
user7761585's user avatar
2 votes
1 answer
599 views

sum of squared distances from mean equals all-pairs sum of square distances?

In this variance based k-clustering paper they claim that for a cluster with S points: $$|S|\sum_{i \in S}{\|x_i-\bar{x}\|^2} = \sum_{a,b \in S,\ a<b}{\|x_a-x_b\|^2}\,.$$ Why is that? can you ...
ihadanny's user avatar
  • 359
2 votes
2 answers
1k views

Community detection in weighted directed graphs for fixed number of communities

I have a weighted directed graph $G=(V,E)$ with positive weights. Say these vertices represent cities and the weight $w : V_1 \rightarrow V_2$ represents number of students moving into other cities ...
Sandipan Bhattacharyya's user avatar
2 votes
1 answer
61 views

Is there a well-known algorithm for arranging inputs according to their category?

Background: (I’m a complete beginner in computer science in general, so I do apologise if my question is not formulated in a sensible way. E.g. I have avoided technicalities in formulating my ...
Nikelmouse Dylar's user avatar
2 votes
1 answer
104 views

What is the name of this problem (the dual of the asymmetric k-center problem)

I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse. In this ...
samie's user avatar
  • 21
2 votes
1 answer
45 views

Subspace clustering with random transformation

One approach for clustering a high dimensional dataset is to use linear transformation, and the most common approaches are PCA and random projection (where random projection arises from the Johnson-...
user1468089's user avatar
2 votes
0 answers
109 views

Minimize the sum of diameters of 2-clustering graph

Is there an algorithm with runtime $\mathcal{O}(n^2)$ that for given weighted graph $G$, partition it into 2 cluster $C_1,C_2$ such that sum of diameters of two clusters minimized? I find a paper with ...
Mohammad.Rostami's user avatar
2 votes
0 answers
22 views

Separating labelled points with a plane, minimizing label variance

Suppose we have observations with associated labels $\{({\bf x}_1, y_1), ({\bf x}_2, y_2), \dots, ({\bf x}_n, y_n)\}$ where ${\bf x}_i \in \mathbb{R}^d$ and $y_i \in \mathbb{R}$. Can we efficiently ...
orlp's user avatar
  • 12.5k