# 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.

141 questions
Filter by
Sorted by
Tagged with
23 views

### Reference and code for community discovery algorithms in multigraphs

In order to group unstructured or sem-structured texts for a timeline construction approach, I consider several types of correlations among such texts. These different correlations induce a weighted ...
• 101
72 views

### Fit of two lines to an arbitrary set of points - NP-Hardness

My problem is: Given $n$ points in $\mathbb{R}^d$, I want to find a partition of these $n$ points into $k=2$ clusters. For each cluster, instead of computing the centroid as in the usual k-means ...
• 43
1 vote
50 views

### Hardness of the k-center problem with relaxed triangle inequality

Consider the $k$-center problem where we are given an undirected, complete graph $G=(V, E)$, with a distance $d(u, v) \geq 0$ for each pair $u, v \in V$. Furthermore, we assume that the triangle ...
10 views

### Clustering data to recover individual functions of a lower-hemicontinuous correspondence/bifurcation diagram

I have a data (from simulations) that is coming from something similar to a bifurcation diagram: it is a lower hemicontinuous correspondence (actually limit points of each branch is included), or in ...
36 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
45 views

### fault-tolerant K-median problem on an undirected graph

We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $G=(V, E)$: We are given a set of facilities $F\subseteq V$ and a set of demands (...
• 15
31 views

### Difference between Distributed File System, Cluster File System and Parallel File System

On the internet, I am unable to find concrete definitions of these three types of file-systems. Can someone clearly explain the difference between these?
1 vote
36 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 ...
• 111
1 vote
95 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
41 views

### Efficiently find the distance from a point to the decision boundary for assigning points to a particular $k$-means cluster

I have run $k$-means on a large set of high-dimensional data, and now I want to find the distance from a point $x$ to the Voronoi cell associated with one of the $k$ centroids. (In a previous version ...
• 113
1 vote
113 views

### Is $k$-means clustering strictly NP-hard?

I've had lectures and read other threads claiming that $k$-means clustering is NP-hard. The fact that they never mention NP-completeness makes me suspect that strict NP-hardness is what's meant. This ...
• 141
1 vote
49 views

### K-Modes Clustering with Partially-Overlapping, Variable-Length Data?

I'm working on a project that's attempting to cluster books using machine learning. I'm using the K-Prototypes algorithm for clustering data that has both numerical and class-based data. Under the ...
• 113
1 vote
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
35 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
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
1 vote
67 views

### Proof of NP-hardness of the k-means clustering problem for $k\geqslant 3$

coming from the computing science side rather than from the data analysis one, I studied the k-means clustering problem for a short time and noticed that the NP-hardness of the problem for $k=2$ seems ...
27 views

### Is there an algorithm to efficiently generate all partitions of a set such that no cell contains fewer than k elements of the set?

I am trying to generate partitions of networks to evaluate clustering algorithms. I know that generating all partitions is infeasible (since they grow with Stirling number of the second kind which get ...
1 vote
47 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
48 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 \...
• 315
1 vote
38 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
85 views

### Efficient Network Clustering Algorithm for Million Node Networks

I am looking for a clustering algorithm that is scalable up to large sparse undirected, unweighted networks (10-40M nodes, 10-80M edges). The most important aspects I care about are scaling efficiency ...
• 215
1 vote
107 views

### How should i face the cluster editing problem?

The mentioned problem: Cluster Editing Problem. I need to code this problem but i can't understand the algorithm behind it, even when i try to search for resources about graphs into the web; can ...
62 views

### A heuristic for finding the vector that is maximally distant from a set of vectors

I have two sets of vectors: A and B. I want to find the vector Bi in set ...
• 113
113 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,564
1 vote
93 views

### Formulate a 2-clustering problem in LP

The problem: Suppose there are $n$ points in plane, and we want to partition points into two clusters such that sum of diameter of clusters is minimized. The diameter of cluster is maximum distance ...
• 1,564
47 views

### Children of internal node in a quadtree with high dimensionality

Let's say for example we have 1000 points and 50 dimensions. And we build a quadtree where each node represents a 50-dimensional box and is divided by splitting the box into smaller boxes that are ...
46 views

### Understanding contradiction in proof of Algorithm for Testing of Clustering of points in metric space in sub-linear time

I am trying to understand this paper, in which (k, b)-clusterability is defined like so: A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...
• 193
1 vote
54 views

### Testing of Clustering of points in metric space in sub-linear time

I am trying to understand this paper, in which (k, b)-clusterability is defined like so: A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...
• 193
53 views

### Clustering Formulas for Networks

Consider an undirected, unweighted graph 𝐺=(𝑉,𝐸). I want to compute the clustering coefficient of each node. In the publicly available lecture from stanford, the following formula for computing the ...
69 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 ...
1 vote
211 views

### Proof of approximation ratio for approximate triangle inequality version of k-center

Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (...
• 190
1 vote
330 views

### Initializations methods for lloyds algorithm (Kmeans++ vs Gonzalez)

I'm learning the initialization methods for Lloyd's algorithm. And I have a hard thing finding examples where Kmeans++ works better than Gonzalez and where the reverse is true so Gonzalez works better ...
1 vote
62 views

### Possible partitions, for k-means problem(k=2)

I have this brute-force algorithm to solve the problem: Generate all possible partitions of P into two subsets of P1 and P2 For each partition P1, P2 generated in Step 1, compute the cost of the ...
51 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 ...
• 139
1 vote
174 views

### Optimal clustering with optimal number of clusters as well as max and min cluster size constraints

I need to cluster $N$ data points. I don't know the number of clusters to be formed. It needs to be found optimally. Also, there is maximum and minimum cluster size constraints, where $C_{\max}$ is ...
35 views

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), \... • 1 1 vote 1 answer 84 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 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 ... 0 votes 0 answers 68 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", ... • 101 0 votes 1 answer 80 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,... 1 vote 1 answer 43 views ### Tips on speeding up hierarchical linkage clustering algorithm I implemented a hierarchical linkage algorithm for a set of 5,000 points. Each point is defined with a longitude and a latitude. I read about this algorithm here. These are the steps: Compute ... • 113 2 votes 1 answer 195 views ### Group time series events into minimal amount of buckets I'm trying to efficiently compute events in a time series by grouping them into buckets. My goal is to have as few buckets as possible. The constraint is that events within one bucket are all within a ... • 123 0 votes 1 answer 2k views ### Is there an online/offline tool that can perform K-means/median, given an initial centroid from the user? The types of problems I am trying to solve are as follows: Given a set of co-ordinates such as: (1,2), (3,3), (6,2), (7,1), a value of k such as k=3 and an initial set of centroids such as c1=(2,2) ... 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.7k 1 vote 1 answer 52 views ### Question in coreset construction fro K-median clustering I was reading Ke chen's paper about coreset construction for K-median clustering. In this paper, he assumed that$A$is an$[α, β]$-bicriteria approximation for K-median clustering for some$α, β=O(1)$... • 51 0 votes 1 answer 117 views ### How to detect outliers using DBSCAN? I am working on a Fraudulent Cash Transaction Detection System using DBSCAN and I want to know what is the proper way to identify outliers? Thank you ##Edite## I had a problem how to represent the ... 0 votes 1 answer 65 views ### How can I examine the subnetworks of a nearly fully connected graph? I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a ... 0 votes 0 answers 24 views ### How to cluster a dataset in which each data point is composed of a set of 2-dimensional coordinates I have a dataset with totally$1000$scenarios, each of which is composed of$5$users' coordinates$(x_i,y_i), \forall i \in \{1,\dots,5\}$. Now, based on users' coordinates, I want to cluster these$...
what would be the time complexity of DBSCAN algorithm if we use it for graph(sparse) clustering $O(n^2)$ or $O(n \log{n})$?