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.

75 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
32 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
0answers
293 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
102 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
23 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
99 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
80 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
20 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 ...
2
votes
0answers
52 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
0answers
40 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
69 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
80 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
23 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
52 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
172 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
1answer
28 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 ...
1
vote
0answers
41 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 ...
1
vote
0answers
47 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 ...
1
vote
0answers
20 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
0answers
13 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. ...
1
vote
0answers
25 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 ...
1
vote
0answers
18 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 ...
1
vote
0answers
15 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 ...
1
vote
0answers
11 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
27 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 ...
1
vote
0answers
25 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
16 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
20 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
67 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
101 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
278 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
65 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
137 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
241 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
239 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
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 ...
1
vote
0answers
94 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
35 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
199 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
62 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
10 views

Dimensional reduction of quadtree influence on clustering with dbscan

Let's say we take a quadtree of 50 dimension and apply dimension reduction(Assume the dimension reduction works well). Why does the dimension reduction not influence the clustering with DBSCAN(Mintpts:...
0
votes
0answers
19 views

Euclidean space vs metric space in density clustering algorithms

I'm trying to find out if these algorithm still work if i replace the Euclidean space with metric space defined on the input point set. But i'm having some trouble figuring it out for some of them. I ...
0
votes
0answers
13 views

Using Restricted Boltzmann Machines for clustering data

I want to use RBMs as a clustering model and the idea is to use an RBM for clustering a 16 class clustering problem with 4 nodes in the hidden layer. The clustering is done by updating the hidden ...
0
votes
0answers
16 views

How to solve this grouping problem heuristically?

There are $S$ servers in the system. There are also $M$ computers in the system. Each computer shows different efficiencies when they are connected to different servers. Lets say, for computer $m$, ...
0
votes
1answer
32 views

Hierarchial clustering cannonnical representation?

I have to handle large binary dataset. That is one of the reasons I have to build my own Hierarchical Clustering. As I digged into the algorithms I was surprised and not ;) to find that it is possible ...
0
votes
0answers
32 views

Find Smooth Functions from Discrete Datas

I'm trying to write a algorithm to solve the following problem, which I did not find any related papers: Given a set of discrete data points generated by n unknown smooth functions $f_1(x), f_2(x), \...
0
votes
0answers
33 views

Is there an approximation algorithm for the three-person stable roommates problem?

While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the "threesome roommates problem", ...
0
votes
1answer
50 views

How do I assign homes to hospitals based on locality? (clustering, kmeans?)

I have a large set of $(X)$ hospitals and $(Y)$ homes, where $(Y)$ is much larger than $(X)$, and their respective coordinates. Each hospital can handle any home within a 50 mile radius, and up to 10,...