# 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
22 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 ...
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 ...
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 ...
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 (...
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 ...
1 vote
94 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 ...
1 vote
40 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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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
46 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 ...
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 \...
1 vote
37 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 ...
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 ...
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 ...
112 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 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 ...
46 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$ ...
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$ ...
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
210 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 (...
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
61 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 ...
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 vote 1 answer 81 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 67 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 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 42 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 ... 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 ... 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 ... 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)$... 0 votes 1 answer 116 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})$?