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
1 vote
1 answer
20 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 ...
user avatar
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. ...
user avatar
  • 111
0 votes
0 answers
6 views

Grouping/Clustering surface mesh triangles by function values

I have the following problem. I have triangular surface meshs of three dimensional bodies. For each triangle exists an associated function value. This value varies over the whole mesh, but there are ...
user avatar
1 vote
0 answers
14 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 ...
user avatar
  • 111
0 votes
0 answers
18 views

What makes Spectral kmeans clustering better than only Kmeans clustering?

I know that Kmeans clustering is the final step of Spectral clustering. But why is it that the previous steps involved in Spectral clustering make it a more convenient clustering approach? moreover ...
user avatar
  • 157
4 votes
0 answers
141 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 ...
user avatar
  • 1
1 vote
1 answer
45 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 ...
user avatar
0 votes
0 answers
20 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 ...
user avatar
1 vote
0 answers
20 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 ...
user avatar
  • 11
4 votes
0 answers
39 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 \...
user avatar
  • 197
1 vote
0 answers
30 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 ...
user avatar
  • 193
1 vote
1 answer
40 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 ...
user avatar
  • 215
1 vote
1 answer
84 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 ...
user avatar
3 votes
1 answer
55 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 ...
user avatar
2 votes
0 answers
95 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 ...
user avatar
  • 1
1 vote
1 answer
83 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 ...
user avatar
  • 1
0 votes
0 answers
14 views

Does it make sense to use Bayesian Network to understand feature correlation of clusters created with K-means?

My project idea is to create clusters of typical rooms for hotel customers, indicate which rooms are similar to the one they are looking for and let them understand why they are conceptually similar. ...
user avatar
  • 13
0 votes
0 answers
11 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:...
user avatar
0 votes
1 answer
29 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 ...
user avatar
2 votes
1 answer
28 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$ ...
user avatar
  • 193
1 vote
1 answer
32 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$ ...
user avatar
  • 193
0 votes
1 answer
34 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 ...
user avatar
0 votes
0 answers
25 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 ...
user avatar
0 votes
0 answers
24 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 ...
user avatar
1 vote
1 answer
86 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 (...
user avatar
  • 69
0 votes
0 answers
17 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$, ...
user avatar
1 vote
1 answer
144 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 ...
user avatar
1 vote
1 answer
42 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 ...
user avatar
0 votes
1 answer
36 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 ...
user avatar
  • 139
1 vote
2 answers
67 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 ...
user avatar
0 votes
0 answers
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), \...
user avatar
  • 1
1 vote
1 answer
43 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 ...
user avatar
1 vote
0 answers
49 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 ...
user avatar
0 votes
0 answers
43 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", ...
user avatar
  • 101
0 votes
1 answer
58 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,...
user avatar
1 vote
1 answer
24 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 ...
user avatar
  • 113
2 votes
1 answer
75 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 ...
user avatar
  • 123
0 votes
1 answer
419 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) ...
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 ...
user avatar
  • 12.3k
1 vote
1 answer
47 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)$...
user avatar
0 votes
1 answer
51 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 ...
user avatar
0 votes
1 answer
50 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 ...
user avatar
0 votes
0 answers
18 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 $...
user avatar
  • 31
2 votes
0 answers
71 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 ...
user avatar
1 vote
1 answer
1k 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})$?
user avatar
4 votes
1 answer
242 views

How to group intervals which overlap by some amount?

I have an algorithm that generates a list of intervals. The algorithm is run m times. Lets mark the intervals as tuples (s1, e1), (s2, e2), .., (sn, en). It is ...
user avatar
  • 151
0 votes
1 answer
30 views

Clustering Application with a Huge Number of Clusters

I am wondering if there are any clustering applications in practice where the number of clusters, i.e., the $k$ in the $k$-means problem is very high ($k>50$, optimally $k>200$), if possible ...
user avatar
1 vote
1 answer
51 views

Finding the middle point of the "most populated" area in a set of points?

I'm working on a game-related application, and I'm trying to find the middle point of the most populated area in my map. Example: ...
user avatar
  • 13
1 vote
0 answers
52 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 ...
user avatar
  • 364
0 votes
0 answers
29 views

Bounding 0-1 matrix with k unique rows

Problem Statement: Suppose that I have a $0-1$ matrix $A$ (all of the entries are $0$ or $1$). I wish to find the tightest upper bound with $k$ many unique rows. To be more precise, let S denote the ...
user avatar
  • 128