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.

57 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
1answer
42 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 ...
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
1k 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
274 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
93 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
0answers
15 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 ...
3
votes
0answers
89 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
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
46 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
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
50 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
148 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
0answers
10 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
0answers
24 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 ...
1
vote
0answers
87 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 ...
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. ...
1
vote
0answers
58 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 ...
1
vote
0answers
73 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 ...
1
vote
0answers
109 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
0answers
52 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 ...
1
vote
0answers
126 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 ...
1
vote
0answers
189 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 ...
1
vote
1answer
188 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 ...
1
vote
0answers
18 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 ...
1
vote
0answers
48 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 ...
1
vote
0answers
86 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 ...
1
vote
0answers
34 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 \...
1
vote
0answers
189 views

Enumerate subtrees of a given size in a graph

Given a graph $G$ with $n$ nodes, is there an algorithm to find $m$ subtrees, each with $\lfloor n/m\rfloor$ or $\lceil n/m\rceil$ nodes, such that every node of $G$ is in exactly one tree? Other ...
1
vote
0answers
58 views

How to cluster nodes based on the number of dependencies

I have a problem where, there are a set of nodes and dependencies between them. I want to cluster them based on the maximum number of dependencies. Dependencies can be thought of as number of edges ...
0
votes
0answers
38 views

Is it possible to represent a citation network as a Tensor for clustering purposes?

My goal is to find a clustering (or an embedding in a vector space) algorithm for a citation network with nodes containing rdf (resource description framework) data (description logic). Dyadic ...
0
votes
0answers
19 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
28 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
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
9 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. ...
0
votes
0answers
13 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 ...
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
55 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
18 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/~...
0
votes
0answers
26 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 ...
0
votes
0answers
86 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?
0
votes
0answers
68 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 ...
0
votes
0answers
35 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: ...
0
votes
2answers
302 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
273 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....