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
0
votes
0answers
10 views

Separate overlapping clusters

Suppose I have multiple data points in 2d (x,y) that are either labeled as A, B, C, or D. I find a minimum bounding area for points that are labeled as A and refer to it as cluster A. I can do the ...
0
votes
0answers
21 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 ...
0
votes
0answers
25 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 ...
0
votes
1answer
25 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 ...
0
votes
0answers
12 views

Clustering - Complete Linkage draw example

I'm studying unsupervised learning methods (clustering) and i've seen the Complete Linkage Method. I've also seen the following statement: Unlike single linkage, the complete linkage method can be ...
0
votes
0answers
7 views

Find shared properties of a cluster samples

I have a dataset which contains ~15 features. With the elbow method, I found out that the optimal number of clusters is probably four. Therefore, I applied the K-means algorithm with four clusters. ...
1
vote
0answers
22 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 ...
0
votes
0answers
10 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 ...
1
vote
0answers
44 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 ...
1
vote
0answers
14 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 ...
0
votes
0answers
23 views

What is difference between parallel virtual machine (PVM) and (mpi) Message passing Interface? [duplicate]

I am using beowulf cluster. And want to know the difference between parallel virtual machine(pvm) and message passing interface(mpi). Thank you.
0
votes
1answer
162 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
0
votes
0answers
14 views

What is the difference between parallel virtual machine and message passing interface. And how both works [duplicate]

I m learning beowulf system architecture and I encounter these terms many time. I know these are the library file and we use these to write parallel programing. But I do not know how these work and ...
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 ...
0
votes
1answer
15 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 ...
0
votes
0answers
51 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 ...
0
votes
0answers
16 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/~...
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 ...
0
votes
0answers
23 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 ...
1
vote
0answers
19 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. ...
0
votes
1answer
455 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
1answer
77 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 ...
1
vote
1answer
34 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) ...
0
votes
0answers
85 views

What is the relationship between pairwise loss and centroid loss?

What is the relationship between pairwise loss and centroid loss? Under what conditions you would expect them to give similar behavior? Under what conditions would they give different behavior?
3
votes
1answer
228 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
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 ...
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 ...
3
votes
1answer
51 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 ...
1
vote
0answers
56 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 ...
4
votes
2answers
58 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 ...
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
0answers
71 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 ...
0
votes
0answers
67 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 ...
1
vote
0answers
92 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
1answer
2k 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 ...
2
votes
0answers
39 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 $ ...
0
votes
1answer
32 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 ...
1
vote
0answers
45 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 ...
0
votes
0answers
34 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: ...
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
347 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: ...
0
votes
1answer
40 views

k-means clustering with efficient point lookup?

What's an algorithm for $k$-means clustering, in particular an online algorithm (you can stream new points to it), such that once the size of the set of clusters $k$ becomes large, we can still ...
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 ...
0
votes
2answers
268 views

What are the drawbacks of Normalized Mutual Information clustering evaluation method?

What are the drawbacks of Normalized Mutual Information (NMI) clustering evaluation method? For evaluating what clustering algorithms, is the NMI evaluation method suitable?
0
votes
0answers
245 views

Clustering based on weights of edges

I have a weighted graph representing traffic network. Nodes represent the locations and vertices represent available paths between locations. Weight values represent number of the passages on the path....
1
vote
0answers
123 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 ...
2
votes
1answer
147 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 ...
0
votes
0answers
41 views

Spectral clustering algorithm doesn't use all available clusters

We have implemented a spectral clustering algorithm according to the article Multiclass Spectral Clustering (Yu and Shi, Proc. IEEE ICCV '03, vol. 2, pp. 313–319, 2003; PDF). We used ...
1
vote
0answers
60 views

Strength-based player cards sampling [closed]

Let's say we have a card game, like poker. Inputs are board cards and an array of cards strength(that is calculated based on the board cards and game rules). For example for 3 ranks(A, K, Q) /2 ...
2
votes
1answer
111 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 ...