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.
170
questions
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
0
votes
0
answers
30
views
Bounding 0-1 matrix with k unique rows
Problem Statement:
Suppose that I have a $0-1$ matrix $A$ (all of the entries are $0$ or $1$). I wish to find the tightest upper bound with $k$ many unique rows. To be more precise, let S denote the ...
- 128
0
votes
1
answer
49
views
RPI cluster performance related to network performance
I'm writing my thesis and i have built a RPI cluster, containing 10 nodes which consists of RPI model 3b. I've them connected to two gigabit switches. I don't know the CAT of the cables. They are not ...
- 1
0
votes
0
answers
66
views
How to find clusters of a set of points in n-dimensional space that are furthest from unwanted points
I have a list of 25 points and their coordinates in a 512-dimensional space. I have 8 target points and 17 points I need to avoid (the 17 points to avoid also have differences in priority of how ...
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
0
votes
1
answer
48
views
Clustering algorithm with specific cluster grouping areas
I'm looking for a way to cluster points in a given space, where clusters form around specific closed, allowed zones of that initial space. Each allowed zone should be surrounded by points of its ...
- 13
0
votes
0
answers
27
views
Spliting strings into groups of similar strings
I would like to group a list of strings into groups of strings differing by max 1 character:
For instance, given:
[John, Alibaba, Johny, Alidaba, Mary]
I would ...
- 175
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
votes
1
answer
231
views
Proof for clustering in a network of friendship
Consider an undirected graph $G = (V, E)$ representing the social network of friendship/trust between
students. We would like to form teams of three students that know each other. The question
is to ...
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
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 ...
-1
votes
1
answer
25
views
Determine the optimal value of K - K-means clustering
I am trying to determine the optimal value of k. I have used a graph to plot the SSE against the values of k.
Using the elbow method, what would be the optimal value of k? I am unsure as to whether 7 ...
- 1
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 ...
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 ...
- 21
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
0
votes
0
answers
122
views
Divide directed weighted graph into two parts
I have a directed, weighted graph $G = (E,V)$. For example, one might be $|E| = 74000, |G| = 725$.
I want to divide this graph into two parts/clusters/communities, taking the edge weights into ...
- 269
1
vote
1
answer
342
views
Weighted graph clustering with maximum size constraint
I'm currently trying to solve a clustering problem. I need to cluster/partition an undirected weighted graph into groups that are restricted to size n.
I have ...
- 13
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
0
votes
0
answers
23
views
Evaluating clustering/partitioning quality
I'm wondering what are the most common/recognized methods to assess the quality of a clustering.
That is because I have developed a tool that can cluster/partition a network (in this case, a public ...
- 319
1
vote
1
answer
755
views
Why does the BFR (Bradley, Fayyad and Reina) algorithm assume clusters to be normally distributed around its centroid?
I'm following a course on data mining based on the lectures from Stanford University and the book Mining of massive datasets.
On the topic of clustering, the BFR algorithm is explained with this ...
- 145
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
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
- 21
1
vote
1
answer
163
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 ...
- 11
1
vote
1
answer
25
views
Grouping/Clustering results based on shared values
I have a data set that is similar to this:
10,000 jobs with 200,000 applicants which are linked to a job.
I'm looking to cluster the shared jobs based on applicants that they share, am I reinventing ...
- 111
0
votes
0
answers
112
views
How to perform particle swarm optimization clustering of results obtained from tf-idf vectorizer?
I have a collection of news articles. I have performed tf-idf operations on them. I am using python as programming language so it was just the use of TF-IDF vectorizer function. I now have the ...
- 101
0
votes
0
answers
71
views
Cluster with categorical / ordinal
i have a dataset with movies review. I wish cluster my element but inside i have a
categorical / ordinal values.
i seen that exist:
MCA (Multiple Correspondence Analysis)
https://www.utdallas.edu/~...
- 252
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 ...
- 51
0
votes
0
answers
159
views
Algorithm to group entities into variable sized groups based on attribute
I have the following problem:
There are n entities (persons) having a common attribute (weight) and I need to build weight categories (this is for a sports event) grouping people based on their ...
- 101
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
0
votes
1
answer
2k
views
Large-scale string clustering
I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at ...
0
votes
1
answer
265
views
Variant of the "Stable Roommates Problem" when room has not 2 but "n" mates
I'm looking at the name of a variant of the Stable Roommates Problem, when the rooms have more than 2 mates, ie for example 6 to 8. Does this problem has a specific name? A well-known algorithm?
To ...
- 143
1
vote
1
answer
142
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) ...
- 955
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 ...
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
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
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 ...
- 31
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
4
votes
2
answers
197
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 ...
- 141
1
vote
1
answer
58
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 ...
- 111
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
0
votes
0
answers
167
views
Clustering non-overlapping time series
I have thousands of times series of different length and different time. I want to group them together so that I know the optimal ones to pick as input for a ML algorithm and to document how they are ...
- 101
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
1
answer
3k
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 ...
- 11
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
0
votes
1
answer
41
views
clustering with uncertain number of clusters
I detect a unmanned aerial vehicle(UAV) in a picture using template matching. The template library only contains targets with different scales, rotations and other differences.I want to simplify the ...
- 3
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
0
votes
0
answers
39
views
how to add bound to clustering algorithm?
I've got a numeric matrix with 72 rows and 2 columns where the first column is the index value and the other column has sequence from 0 to 5 repeated 12 times. The dataset is like above:
...
- 101