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.
82
questions with no upvoted or accepted answers
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 ...
- 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 \...
- 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 ...
- 530
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 ...
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 ...
- 221
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 ...
- 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 ...
- 31
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 ...
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 ...
- 131
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 ...
- 1,554
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 ...
- 12.5k
2
votes
0
answers
109
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 ...
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 ...
- 955
2
votes
0
answers
80
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 $ ...
- 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 ...
- 155
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 ...
- 121
2
votes
0
answers
67
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.♦
- 152k
2
votes
0
answers
180
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 ...
- 121
1
vote
0
answers
28
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 ...
- 11
1
vote
0
answers
47
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 ...
- 111
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. ...
- 111
1
vote
0
answers
28
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 ...
- 111
1
vote
0
answers
40
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 ...
- 11
1
vote
0
answers
34
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 ...
- 193
1
vote
1
answer
70
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 ...
- 111
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 ...
- 136
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 ...
- 364
1
vote
0
answers
27
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 ...
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.
...
- 111
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 ...
- 61
1
vote
0
answers
25
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 ...
- 11
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 ...
- 531
1
vote
0
answers
12
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 ...
1
vote
0
answers
30
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 ...
- 375
1
vote
0
answers
31
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 ...
- 11
1
vote
0
answers
17
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 ...
- 531
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.
...
- 235
1
vote
0
answers
70
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 ...
- 11
1
vote
0
answers
115
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 ...
- 111
1
vote
0
answers
436
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 ...
1
vote
0
answers
71
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 ...
- 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 ...
- 11
1
vote
0
answers
279
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 ...
- 235
1
vote
1
answer
297
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 ...
- 11
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 ...
- 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 ...
Dr_Watcher
1
vote
0
answers
99
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 ...
- 111
1
vote
0
answers
40
views
Clustering as an approach to regression
Suppose $\varphi: X \rightarrow Y$ is a function between feature spaces that I want to model. I want to produce two easily computable functions $\phi_X: X \rightarrow \mathbb{R}^m$ and $\phi_Y: Y \...
- 111