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
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 ...
- 101
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 ...
- 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 ...
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 ...
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 ...
- 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 (...
- 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?
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 ...
- 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 ...
- 111
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 ...
- 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 ...
- 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 ...
- 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. ...
- 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 ...
- 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 ...
- 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 ...
- 131
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 ...
- 11
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 ...
- 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 \...
- 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 ...
- 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 ...
- 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 ...
- 11
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 ...
- 113
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 ...
- 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 ...
- 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 ...
- 27
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$ ...
- 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$ ...
- 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 ...
- 103
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 ...
- 27
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 (...
- 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 ...
- 27
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 ...
- 27
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 ...
- 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 ...
- 111
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), \...
- 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 ...
- 111
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 ...
- 136
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", ...
- 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,...
- 123
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 ...
- 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) ...
- 23
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
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 ...
- 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 ...
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 $...
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 ...
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})$?
- 25