Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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.

83 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4 votes
0 answers
156 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
50 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
  • 345
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
319 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
130 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
0 answers
36 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
121 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
0 answers
72 views

Fit of two lines to an arbitrary set of points - NP-Hardness

My problem is: Given $n$ points in $\mathbb{R}^d$, I want to find a partition of these $n$ points into $k=2$ clusters. For each cluster, instead of computing the centroid as in the usual k-means ...
T. Pmp's user avatar
  • 43
2 votes
0 answers
118 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 ...
ErroR's user avatar
  • 1,942
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
  • 13.6k
2 votes
0 answers
128 views

How to calculate delta Q (modularity increase matrix) in graphs?

I've been trying to implement the Three-stage Algorithm to compare its results with our new proposed algorithm with different datasets than those mentioned in the article. I've succeeded in ...
Imen Z Imanou's user avatar
2 votes
0 answers
44 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 ...
einpoklum's user avatar
  • 975
2 votes
0 answers
81 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 $ ...
c11o's user avatar
  • 21
2 votes
0 answers
82 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 ...
besabestin's user avatar
2 votes
0 answers
26 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 ...
Thagor's user avatar
  • 121
2 votes
0 answers
74 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$). ...
D.W.'s user avatar
  • 161k
2 votes
0 answers
182 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 ...
gtwebb's user avatar
  • 121
1 vote
0 answers
24 views

Clustering 2D points with flavour

Problem Description I have two sets of 2D points with flavours: Noisy points $$p_i = (x_i, y_i, f_i) : p_i \in N : |N|\approx 10^8 $$ and true points $$p_{t_i} = (x_{t_i}, y_{t_i}, f_{t_i}) : p_{t_i} \...
Emil Jansson's user avatar
1 vote
0 answers
41 views

What might be a suitable clustering algorithm to split different parts in dense optical flow?

I want to split the main part(like people) in optical flow from the background, but I don't konw how to start. I think one way is to use some kind of clustering algorithm, first split the optical flow ...
zjnyly's user avatar
  • 111
1 vote
0 answers
146 views

grouping/clustering of lines using Hough transform

I am new to Hough transform, though I have some basic idea about it. I am currently trying to fit the best line to a cluster of points $\left(x_i, y_i\right), i = 1,2,\cdots , N$, where there are ...
user146290's user avatar
1 vote
0 answers
30 views

Grouping only overlapping points into stacks

I have n number of files on a ScrollView. Every time a file is added, x/y coordinates are stored in an array. The user is able to drag and drop the files anywhere they like. Overlapping files (e.g. ...
mmackh's user avatar
  • 111
1 vote
0 answers
48 views

Find clustering/partitioning based on edge weight

So I have a complete digraph with non-zero positive edge weights. The nodes represent locations and edge weights are the travel times between the two corresponding nodes. I have 2 or more agents ...
Anteino's user avatar
  • 111
1 vote
0 answers
57 views

Finding highly-connected regions of graphs

I have a large network of 10,000 nodes and I am trying to identify subgraphs which are clique-like, in that they share many connections. I don't a priori know how many subgraphs fit this criteria. To ...
Gabriel's user avatar
  • 11
1 vote
0 answers
41 views

Cluster 3d points with constraints

I have some 3d point cloud I wish to cluster into some number of clusters. I have the probability of two points being in the same cluster given as some function of their relative locations, with the ...
Gulzar's user avatar
  • 193
1 vote
1 answer
86 views

How to group thousand of data points for each user

I have thousands of data points associated with users. So a single user can have 2000-10000 data points. These data points are identified by contiguous numbers (e.g. all numbers from 0 to 2000). Each ...
Artur Carvalho's user avatar
1 vote
0 answers
51 views

Is n-dimentional assignment problem for points NP-hard?

We have $n$ sets of $k$ points in $\mathbb R^d$ and we are trying to partition them to $k$ clusters of $n$ points such that from each set every point is mapped to a different cluster and the sum of ...
Tomer Wolberg's user avatar
1 vote
0 answers
52 views

Clustering sets by set difference

Suppose you have $n$ nonequal sets $S_1, \ldots, S_n$ and some constant $0 \le k < n$. The goal of set clustering is to find a partition of the set $\mathbf{S} = \{S_1, \ldots, S_n\}$ such that the ...
taktoa's user avatar
  • 364
1 vote
0 answers
29 views

Delivery Clustering based-on Pick-Drop & Driver locations

I'm reading some papers about Delivery Clustering to solve following generic problems: Given N orders (with its Pick-up and Drop location point) and M delivery-man (with his location). We are going ...
Le Duong Tuan Anh's user avatar
1 vote
0 answers
14 views

How can one algorithmically define the required amount of centroids in K-Means clustering?

Say I have a dataset of n vectors. These are, by nature, clustered so that there is a significant distance difference between any two points within a cluster and any two points in separate clusters. ...
A. McMount's user avatar
1 vote
0 answers
27 views

How to cluster N sets into N subsets ,so that we can determine which set a point is from by checking its nearest neighbor in aforementioned subsets?

Question 1: Given N sets of points $S_1$ ... $S_n$ (no intersection between $S_i$ and $S_j$ when i != j), I want to find subsets of $S_1$ ... $S_n$ (call them $T_1$ ... $T_n$ respectively) So that ...
iouvxz's user avatar
  • 61
1 vote
0 answers
29 views

Clustering customer with string data

I'm looking for a customer clustering solution. I have done a lot of research on the machine learning level to find algorithms that could fit my needs but I can't find much information when the data ...
LookingFor's user avatar
1 vote
0 answers
18 views

Finding fewest strings that cover $\Sigma^n$ up to $R$ edit operations

Let $\Sigma$ be the alphabet, $0<R<n$ be an integer and let $\Sigma^n$ denote the set of all strings of length $n$ over the alphabet. The task is to find the minimum $m$ such that there exist ...
Ameer Jewdaki's user avatar
1 vote
0 answers
13 views

2 stage clustering

The problem I am facing is clustering problem, needed for a Vehicle routing problem (VRP) I'm tackling. It is a heterogeneous VRP with Time Windows and a capacity utilization constraint, i.e. a truck ...
Dimitris Boukosis's user avatar
1 vote
0 answers
33 views

How can I express the similarity between a Bing and a Google search result?

I'm working on a "semantic" browser engine where all search engines should look the same. One way to do this is to hard-code parsing rules for each site; another is to use machine-learning. Of course ...
Olle Härstedt's user avatar
1 vote
0 answers
32 views

Point cloud clustering based on similarity in less than $O(n^2)$

not sure if this is the right place to ask this but here it goes. Let's assume I have some 2D points dataset consisting of facial landmarks, and I want to cluster these based on similarity so that I ...
Zach's user avatar
  • 11
1 vote
0 answers
20 views

Balanced $\epsilon$-separated partitioning by a hyperplane

Suppose we have $m$ points in $R^n$ and $\epsilon>0$ is a given constant. How can we find a hyperplane that the number of points that are $\epsilon$-close to it is minimum, with the constraint that ...
Ameer Jewdaki's user avatar
1 vote
0 answers
22 views

Concrete/theoritical center of a cluster in a general metric space

What i call center is the point which minimize the distance to every points of a specific cluster. From what i know we can look for a concrete point in the cluster get an approximation of the center. ...
KyBe's user avatar
  • 235
1 vote
0 answers
71 views

$k$ -center with outliers - but the points are on a line

The classic $k$-center with outliers problem is NP-hard and there exist approximation algorithms to solve it. However, what if we assume that the input point are on a line, rather than in an ...
Mik's user avatar
  • 11
1 vote
0 answers
116 views

Strict partitioning clustering of points in 2D space into variable (but fixed) length cluster in order to minimize distance from center

Given $\\N$ points in 2D space, one is required to cluster them into $\\M$ clusters, with each cluster of a given size $\\S_m$ such that $\sum S_m = N$, in order to minimize the sum of the distance of ...
travis bickle's user avatar
1 vote
0 answers
491 views

Clustering via Max-Cut

I wonder if there are papers that uses max cut algorithm(s) to cluster data. For example, if an edge between two nodes $u$ and $v$ indicate that $u$ and $v$ are different, then the max-cut in some ...
polar_bear_cheese's user avatar
1 vote
0 answers
75 views

Spanning tree with equally separated edge weights

I have a fully-connected graph $G=(V,E)$ with edge weights $w(v)\in\mathbb{R};v\in V$ and I need to find a spanning tree $T=(V_t\subseteq V,E_t\subseteq E)$ where the set of edge weights in the tree ...
thayne's user avatar
  • 141
1 vote
0 answers
150 views

Is this version of clustering still NP-Hard?

Let the set $A = \{a_1,...,a_n\}$ of objects and $d(a_i,aj) \quad \forall i,j\in[n] \quad i\neq j$. Let $\;C=\{C_1,...,C_k\}$ the set of clusters, split the elements of $A$ into $C$ such as there is ...
tonibofarull's user avatar
1 vote
0 answers
299 views

Determine border points of a cluster

My question is as follow. Imagine a random shape cluster of high dimension in an euclidian space, how can i get points which are at the edge of the cluster where edge are defined as segments ...
KyBe's user avatar
  • 235
1 vote
1 answer
312 views

Appropriate graph clustering algorithm

I'm looking for an appropriate technique to search for clusters. My underlying data is 70,000 respondents to about 2500 multiple choice questions. Most respondents have not answered most questions. I ...
Raggamuffin's user avatar
1 vote
0 answers
23 views

What are internal clustering index for binary data ? And if possible applicable to massive cluster ?

I was wondering what are the current existing internal clustering index for binary data. I know already the silhouette and Davis Bouldin for euclidian space, i suppose they work as well in binary ...
KyBe's user avatar
  • 235
1 vote
0 answers
49 views

Update existing clusters to satisfy distance and volume constraints

I have a massive distance matrix of clusters. The distance matrix is the distance between each cluster. I now need to recluster each entity based on two constraints. Each cluster has an associated ...
user avatar
1 vote
0 answers
101 views

Clustering images based on timestamp

I want to make folders of images of users in a meaningful way. The images have only the timestamp of creation associated with them. Each folder can have a maximum of k images. I can use median or ...
tanvi's user avatar
  • 111