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
26
votes
4answers
68k 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
450 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
526 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 ...
4
votes
1answer
112 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
55 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
745 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
1answer
560 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
30 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
1answer
926 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
0answers
260 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
92 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
550 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
185 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
190 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
124 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
323 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
584 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. ...
3
votes
1answer
180 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
177 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
78 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
179 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
50 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
741 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
73 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
76 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
228 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
144 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
831 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
124 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 ...
2
votes
1answer
195 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
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
1answer
37 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 ...
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
31 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
77 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
110 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
49 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
136 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
901 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
24 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 ...
1
vote
1answer
28 views

How fast can we optimally cluster 1-D data?

K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) ...
1
vote
1answer
28 views

Identify objects (bus) on the map based on coordinates (lat, lon)

Let's say I have an android app that frequently sends current GPS location of the user. If person is driving with bus, I can easily get GPS location of the bus and display it on the map and update it ...
1
vote
1answer
1k views

Python: Clustering based on pairwise distance matrix [closed]

I have a matrix which represents the distances between every two relevant items. For example, M[i][j] holds the distance between items i and j. My next aim is to cluster items by these distances. I ...
1
vote
2answers
348 views

Keywords for classification of 2D time series data?

Trying to find the right search terms for literature on classifying 2D time series data. I am looking at data from positional tracking of a swarm of insects over time. I have example datasets for ...