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
0 answers
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 ...
Max Muller's user avatar
2 votes
0 answers
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 ...
T. Pmp's user avatar
  • 43
1 vote
1 answer
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 ...
TheCollegeStudent's user avatar
0 votes
0 answers
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 ...
lefouflou's user avatar
3 votes
0 answers
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 ...
C Marius's user avatar
  • 185
0 votes
1 answer
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 (...
Ramon's user avatar
  • 15
0 votes
0 answers
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?
Tarun Gupta's user avatar
1 vote
0 answers
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 ...
zjnyly's user avatar
  • 111
1 vote
0 answers
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 ...
user146290's user avatar
1 vote
1 answer
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 ...
gmr's user avatar
  • 113
1 vote
1 answer
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 ...
Mew's user avatar
  • 141
1 vote
1 answer
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 ...
Praxder's user avatar
  • 113
1 vote
0 answers
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. ...
mmackh's user avatar
  • 111
1 vote
0 answers
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 ...
Anteino's user avatar
  • 111
4 votes
0 answers
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 ...
All's user avatar
  • 83
1 vote
1 answer
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 ...
Thomas Baruchel's user avatar
0 votes
0 answers
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 ...
user023049's user avatar
1 vote
0 answers
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 ...
Gabriel's user avatar
  • 11
4 votes
0 answers
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 \...
Dmitry's user avatar
  • 315
1 vote
0 answers
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 ...
Gulzar's user avatar
  • 193
1 vote
1 answer
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 ...
sligocki's user avatar
  • 215
1 vote
1 answer
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 ...
Nicholas_'s user avatar
3 votes
1 answer
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 ...
magnetlion's user avatar
2 votes
0 answers
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 ...
MR_'s user avatar
  • 1,564
1 vote
1 answer
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 ...
MR_'s user avatar
  • 1,564
0 votes
1 answer
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 ...
FlubberBeer's user avatar
2 votes
1 answer
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$ ...
Gulzar's user avatar
  • 193
1 vote
1 answer
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$ ...
Gulzar's user avatar
  • 193
0 votes
1 answer
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 ...
Yves Boutellier's user avatar
0 votes
0 answers
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 ...
FlubberBeer's user avatar
1 vote
1 answer
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 (...
sn3jd3r's user avatar
  • 190
1 vote
1 answer
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 ...
FlubberBeer's user avatar
1 vote
1 answer
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 ...
FlubberBeer's user avatar
0 votes
1 answer
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 ...
sten's user avatar
  • 139
1 vote
2 answers
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 ...
dipak narayanan's user avatar
0 votes
0 answers
35 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), \...
Xzy's user avatar
  • 1
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 ...
Artur Carvalho's user avatar
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 ...
Tomer Wolberg's user avatar
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", ...
Raffi's user avatar
  • 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,...
imagineerThat's user avatar
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 ...
Paek Se's user avatar
  • 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 ...
Daniel's user avatar
  • 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) ...
Meowth8743's user avatar
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 ...
orlp's user avatar
  • 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)$...
WilliamW's user avatar
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 ...
Xx_22's user avatar
  • 1
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 ...
Ameet Rahane's user avatar
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 $...
Good to learn everything's user avatar
2 votes
0 answers
119 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 ...
Imen Z Imanou's user avatar
1 vote
1 answer
3k views

what would be the time complexity of DBSCAN algorithm?

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})$?
user13476360's user avatar