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
29
votes
4answers
69k 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 ...
8
votes
1answer
503 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 = \{...
5
votes
2answers
620 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 ...
5
votes
1answer
747 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. ...
5
votes
1answer
65 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 ...
5
votes
1answer
1k 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$, ...
4
votes
1answer
115 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 ...
4
votes
2answers
71 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 ...
4
votes
1answer
873 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$. ...
4
votes
2answers
722 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, ...
4
votes
0answers
31 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 ...
4
votes
0answers
283 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 ...
4
votes
1answer
94 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 ...
3
votes
1answer
683 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 ...
3
votes
1answer
258 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 ...
3
votes
1answer
197 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 ...
3
votes
1answer
234 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 ...
3
votes
1answer
128 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 ...
3
votes
1answer
474 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: ...
3
votes
1answer
258 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) ...
3
votes
2answers
200 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 ...
3
votes
1answer
84 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 ...
3
votes
1answer
31 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 ...
3
votes
1answer
328 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 ...
3
votes
1answer
64 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 ...
3
votes
1answer
58 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 ...
3
votes
1answer
883 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 ...
3
votes
0answers
21 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 ...
3
votes
0answers
93 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 ...
3
votes
0answers
78 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 ...
2
votes
3answers
234 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) - ...
2
votes
2answers
152 views

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

K-means is a clustering algorithm which works like this: ...
2
votes
2answers
912 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 ...
2
votes
1answer
309 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 ...
2
votes
1answer
52 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 ...
2
votes
1answer
42 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-...
2
votes
0answers
38 views

Algorithms / heuristics for a distributed sorting problem

The setting: There's a cluster of $k$ computers (= nodes). For simplicity, assume their hardware is identical. The network topology can be complicated, but let's simplify and assume it's a clique ...
2
votes
0answers
64 views

What is the definition of a “Clustering Feature” in BIRCH algorithm?

The paper for BIRCH (a clustering algorithm) contains definitions of a Clustering Feature (CF) where the notation is unclear (cf. PDF page 3 / section 4). A cluster contains N d-dimensional entries $ ...
2
votes
0answers
78 views

Selecting higher values from arrays that are not far from each other

I have arrays $a_1...a_n$ each containing $m$ values inside. I want to select one value from each array. Let us say the selected values from each array are represented with $x_1...x_n$ and the ...
2
votes
1answer
116 views

Specific Examples with Explanation of Similarities and Differences of how Distance Functions are used Across Different Fields [closed]

I took a tangent from a student project I had done a number of years ago and spent some time studying distance functions. (please note that the above link contains the full question with links as I ...
2
votes
0answers
22 views

Where to cut a category tree

Since I don't have CS background I will most probably ask this question the wrong way. I need to choose a node from a tree, where I include all beneath this node leafs in a validation. I have a data ...
2
votes
0answers
52 views

Clustering with probabilities / vector quantization with arbitrary distance measures

Suppose I'm given $n$ points $x_1,\dots,x_n$ in some space $\mathcal{S}$ (think: $\mathbb{R}^d$), and probabilities $p_1,\dots,p_n$ that form a probability distribution (so $p_1 + \dots + p_n=1$). ...
2
votes
0answers
163 views

Footprint finding algorithm

I'm trying to come up with an algorithm to optimize the shape of a polygon (or multiple polygons) to maximize the value contained within that shape. I have data with 3 columns: X: the location of ...
1
vote
2answers
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 ...
1
vote
1answer
19 views

Finding the middle point of the “most populated” area in a set of points?

I'm working on a game-related application, and I'm trying to find the middle point of the most populated area in my map. Example: ...
1
vote
1answer
46 views

How to cluster images based on meta-information in tags

Context and Motivation I have researched online for an algorithm (independent of a programming language AND in the context of Machine Learning) that accepts images as inputs with the expectation that ...