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
0answers
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:...
0
votes
1answer
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 ...
2
votes
1answer
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$ ...
1
vote
1answer
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$ ...
0
votes
1answer
27 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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
34 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 (...
0
votes
0answers
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$, ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
38 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 ...
0
votes
0answers
31 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
vote
1answer
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 ...
1
vote
0answers
41 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
0answers
31 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
1answer
46 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
1answer
17 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
1answer
52 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
1answer
23 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
0answers
20 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 ...
0
votes
0answers
203 views

How does secondary clustering occur in hashing?

One of my friends said me that secondary clustering is the phenomenon occurring when the probe sequence has the same initial value. This definition shows that secondary clustering occurs in linear ...
1
vote
1answer
35 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
0answers
11 views

building a unsupervised learning model to detect suspicious transactions using DBSCAN

I am working for the first time on building a unsupervised learning model to detect suspicious transactions using DBSCAN, Do I train the model on all data columns(Columns like account number, ...
0
votes
1answer
35 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
1answer
38 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
0answers
27 views

What does the decision boundary of XOR problem look like?

My textbook walks through an example of solving the XOR problem in machine learning using a two-dimensional RBF network. It does this by setting the centers for the two basis functions at [0,0] and [1,...
0
votes
0answers
14 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
0answers
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 ...
0
votes
1answer
621 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})$?
4
votes
1answer
185 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 ...
0
votes
1answer
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 ...
1
vote
1answer
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: ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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. ...
1
vote
0answers
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 ...
1
vote
0answers
18 views

Clustering customer with string data

I'm looking for a customer clustering solution. I have done a lot of research on the machine learning level to find algorithms that could fit my needs but I can't find much information when the data ...
0
votes
1answer
39 views

Clustering algorithm with specific cluster grouping areas

I'm looking for a way to cluster points in a given space, where clusters form around specific closed, allowed zones of that initial space. Each allowed zone should be surrounded by points of its ...
0
votes
0answers
27 views

Spliting strings into groups of similar strings

I would like to group a list of strings into groups of strings differing by max 1 character: For instance, given: [John, Alibaba, Johny, Alidaba, Mary] I would ...
1
vote
0answers
15 views

Finding fewest strings that cover $\Sigma^n$ up to $R$ edit operations

Let $\Sigma$ be the alphabet, $0<R<n$ be an integer and let $\Sigma^n$ denote the set of all strings of length $n$ over the alphabet. The task is to find the minimum $m$ such that there exist ...
-1
votes
1answer
228 views

Proof for clustering in a network of friendship

Consider an undirected graph $G = (V, E)$ representing the social network of friendship/trust between students. We would like to form teams of three students that know each other. The question is to ...
3
votes
0answers
23 views

Algorithm to separate single contour of glyph into several strokes?

A glyph contour contains points set {p}, a point contains tuple (x,y,on_curve). Now, think about this need, converting contour of glyph X, for example, into to two contour parts or two strokes, point ...
2
votes
1answer
55 views

Is there a well-known algorithm for arranging inputs according to their category?

Background: (I’m a complete beginner in computer science in general, so I do apologise if my question is not formulated in a sensible way. E.g. I have avoided technicalities in formulating my ...
-1
votes
1answer
18 views

Determine the optimal value of K - K-means clustering

I am trying to determine the optimal value of k. I have used a graph to plot the SSE against the values of k. Using the elbow method, what would be the optimal value of k? I am unsure as to whether 7 ...
1
vote
0answers
11 views

2 stage clustering

The problem I am facing is clustering problem, needed for a Vehicle routing problem (VRP) I'm tackling. It is a heterogeneous VRP with Time Windows and a capacity utilization constraint, i.e. a truck ...