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.

154 questions
Filter by
Sorted by
Tagged with
445 views

What are the drawbacks of Normalized Mutual Information clustering evaluation method?

What are the drawbacks of Normalized Mutual Information (NMI) clustering evaluation method? For evaluating what clustering algorithms, is the NMI evaluation method suitable?
50 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,...
19 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 ...
86 views

What is the name of this problem (the dual of the asymmetric k-center problem)

I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse. In this ...
10 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:...
16 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$ ...
20 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$ ...
28 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 ...
19 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 ...
13 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 ...
36 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 (...
32 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 ...
24 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) ...
16 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$, ...
31 views

RPI cluster performance related to network performance

I'm writing my thesis and i have built a RPI cluster, containing 10 nodes which consists of RPI model 3b. I've them connected to two gigabit switches. I don't know the CAT of the cables. They are not ...
49 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 ...
20 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 ...
39 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 ...
28 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 ...
240 views

Appropriate graph clustering algorithm

I'm looking for an appropriate technique to search for clusters. My underlying data is 70,000 respondents to about 2500 multiple choice questions. Most respondents have not answered most questions. I ...
32 views

647 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})$?
52 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 ...
190 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 ...
27 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 ...
70 views

k-means clustered data: how to label newly incoming data

I have a data set with labels that were produced by a $k$-means clustering algorithm. Now there is some data (with the same data structure) from another source and I wonder what is the most sensible ...
29 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: ...
47 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 ...
24 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 ...
1k views

Fast algorithm for clustering groups of elements given their size/time

I don't know if there is a canonical problem reducing my practical problem, so I will just try to describe it the best that I can. I would like to cluster files into the specified number of groups, ...
42 views

How to find clusters of a set of points in n-dimensional space that are furthest from unwanted points

I have a list of 25 points and their coordinates in a 512-dimensional space. I have 8 target points and 17 points I need to avoid (the 17 points to avoid also have differences in priority of how ...
20 views

Delivery Clustering based-on Pick-Drop & Driver locations

I'm reading some papers about Delivery Clustering to solve following generic problems: Given N orders (with its Pick-up and Drop location point) and M delivery-man (with his location). We are going ...
13 views

How can one algorithmically define the required amount of centroids in K-Means clustering?

Say I have a dataset of n vectors. These are, by nature, clustered so that there is a significant distance difference between any two points within a cluster and any two points in separate clusters. ...
25 views

How to cluster N sets into N subsets ,so that we can determine which set a point is from by checking its nearest neighbor in aforementioned subsets?

Question 1: Given N sets of points $S_1$ ... $S_n$ (no intersection between $S_i$ and $S_j$ when i != j), I want to find subsets of $S_1$ ... $S_n$ (call them $T_1$ ... $T_n$ respectively) So that ...