Questions tagged [clustering]
Clustering is grouping (partitioning) a set of objects so that items in the same group are more similar to each other than to items in different groups, where the notion of similarity may be variously defined.
314
questions
0
votes
0
answers
9
views
Clustering of directed graphs satisfying priority constraints
I recently ran into a problem related to directed graph clustering, but don't know how to solve it.
There is a directed acyclic graph $G = (V,E)$, where $V$ is the set of vertices, and $E$ is the set ...
- 431
0
votes
0
answers
20
views
Understanding academic paper methodology (clustering trajectories with Bezier curves)
I'm currently doing my Master's dissertation project using football (soccer) tracking data, and am looking to cluster player run paths of various lengths in Python. I have found a relevant paper ...
- 1
0
votes
1
answer
36
views
Get Maximum value of a cluster as a constraint in a MILP
I am facing the following problem:
I have same kind of a clustering Problem
\begin{alignat}{4}
\text{min }\quad& \sum_{c \in C} \sum_{s \in S} - y_{c,s}\\[2ex]
\text{s.t. }\quad& \sum_{c \in ...
- 3
3
votes
1
answer
52
views
Why does spectral clustering work?
Relevant Background
I've recently learnt about the spectral clustering algorithm and had a hard time understanding why we do what we do. Trying to undetstand, I stumbled upon this great post, that ...
- 223
0
votes
0
answers
39
views
Find in which face lie a point on a hyper polytope, inscribed in an hyper unit-sphere (and how to generate this hyper polytope)
I am working on clustering normalized point in a k dimension space.
At first i used Spherical LSH strategy where i used random planes to cut the hyper-sphere but it induces a lot of random (because i ...
0
votes
0
answers
16
views
Clustering when data is represented by multiple functional forms, all at once.
I wish to cluster similar data where I have a collection of many $y$ vs $x$ data. A third variable $z$ also exists, but z doesn't always affect $y$ whereas $x$ always affects $z$.
In terms of $x$ and $...
0
votes
0
answers
3
views
High dimensional behavior of Dirichlet Process-based clustering?
I have a problem stemming from Dirichlet Process Gaussian Mixture Models (DP-GMMs) in high dimension. I'll write this question so that no knowledge of DP-GMMs is needed.
Let $D$ be the dimensionality ...
- 389
2
votes
0
answers
24
views
How to learn data points by minimizing a loss function given their pairwise distance matrix?
Suppose $x_i \in\mathbb{R}^2$ for $i=1,2,...9$ are unknown. I'm given the pair-wise distance matrix between these points $D$ which is a $9*9$ symmetric matrix. I want to learn these data points by ...
- 2,265
0
votes
0
answers
9
views
How can I select K value of K-means from eigengap?
I have studied perturbation theory and spectral graph theory to calculate the optimal number of clusters .Eigengap heuristic suggests the number of clusters k is usually given by the value of k that ...
- 333
0
votes
0
answers
31
views
Maximum distance based clustering in metric spaces
I want to cluster a set of points $S$ in a general metric space with metric $d$, so that all points in a cluster can be connected by a path where the distance between two points is at most $D$.
This ...
- 153
2
votes
1
answer
78
views
what are the benefits of using Spectral K-means over Simple K-means ? and how Spectral K-means overcomes the local minimum problem of K-means?
I have understood why K-means get stuck in local minima
Now I am curious to know how spectral k-means helps to avoid this local minima problem?
According to this paper A tutorial on Spectral,
...
- 333
0
votes
1
answer
122
views
How to prove that the residual sum of squares is a non-convex Function?
The $K$-means algorithm uses a residual sum of squares (RSS) where $$ \mbox{RSS}_{K} = \sum_{d \in s}|{d-c(s)}|^2 $$
$\mbox{RSS} = \sum_{k= 1}^K \mbox{RSS}_{K}$ is the convergence criterion. $\mbox{...
- 333
0
votes
0
answers
5
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 ...
- 1
1
vote
1
answer
42
views
Calculating Mahalanobis distance
I am slightly confused as to how you calculate Mahalanobis distance given a set of data. I have tried asking my tutor for help but he does not seem interested in helping what so ever and I am ...
- 147
0
votes
0
answers
16
views
Selecting N evenly spaced nodes in the plane
Given a set of nodes $P$, making up a completely disconnected graph, I am looking for a method of selecting $N$ of them such that the graph can be partitioned into approximately equally sized clusters ...
0
votes
0
answers
26
views
Sampling vertices from a graph to maximize the spread
Given a graph with N vertices, I want to sample K of them such that I have the maximum possible spread. A possible application of this is to build shelters in a road network so that they cover the ...
0
votes
0
answers
15
views
How RatioCut leads to unnormalized spectral clustering?
I have understood the underlying concepts of spectral clustering and how inter cluster distance equation is mapped to a matrix form and how it is optimized using lagrange multiplier. But unable to ...
- 333
0
votes
0
answers
35
views
Best order to allocate services in graph using custom comparator
Good day!
I have a lot of graphs with different properties: structure, number of nodes & edges, etc. All of them are undirected, "weighted" (edges have width, in other words capacity). ...
- 117
0
votes
0
answers
47
views
Colorblind test -- finding and classifying lines in 3-D space
I am creating a color blind test that uses RGB colors. RGB ranges [0-255] in all three colors to determine the final color. I would like to test the user to find which colors they struggle with. For ...
- 1
0
votes
0
answers
8
views
Clustering Similarity Measurement Based on Mutual Information
I have a question when learning the measures based on mutual information to the similarity between two clusterings. See this paper.
Say the labels can be permuted. For example, "both a and b ...
- 1,526
0
votes
0
answers
18
views
Approximate maximization of a function
I am trying to find $s$ and $\eta=(\eta_0,\eta_1)$, that maximizes the following function.
$$\max_{s,\eta} <x, \eta(s)>-n_0(s)log(1+e^{\eta_0})-n_1(s)log(1+e^{\eta_1})$$
where
$x$ is a vector ...
0
votes
0
answers
37
views
How to mathematically formulate this clustering optimization problem?
I need to perform clustering of two different entities (as seen in the attached image, red square and blue balls are two different entities) under the following constraints
Lets say, red square: ...
- 155
2
votes
0
answers
72
views
How to prove that trangle inequality is satisfied in Hausdorff distance
I'm working on a problem my teacher asked me to check if I was interested, which is 'how to prove that Hausdorff Distance is strictly a distance function'. More specifically, how to prove that
$$D_H(A,...
- 29
0
votes
0
answers
17
views
Relation between two cost functions
I'm having a problem with an issue.
Is the following statement true? If it is true, why?
Be $X$ a set in $\mathbb{R}^m$. Given two clusterizations of it, ie, $C=\{C_1,...,C_k\}$ which each subset ...
- 58
1
vote
0
answers
14
views
Cover all 2D points given a 2D template with minimum distance between them
I am looking for an algorithm that gets a binary image similar to the below image
and given a circle(as a template) with radius R, returns the location of instances of this circle needed to cover all ...
- 177
1
vote
1
answer
14
views
intra cluster sampling
Apologize for the longish context setting but we are working on a recommender system which needs to let users know which erroneous files need attention. These erroneous files have been generated via ...
0
votes
1
answer
35
views
Generalization of Marchenko-Pastur law to nonzero mean random matrices with unknown variance
I have an application where rectangular, $m \times n$ matrices appear, where every row represents a data point with noise in all of its components, except for some components which are part of a "...
- 325
0
votes
0
answers
18
views
How to design a clustering metric or cluster algorithm to seperate tow intersected circles?
In some classical books about pattern recognition, the clustering algorithm reveals the similarity among samples, while not considering the "global pattern" of grouped samples.
So, I think ...
- 271
2
votes
1
answer
17
views
Sampling from a particular region of a Voronoi diagram
We are given a finite set of points $\{p_1, ..., p_n\}$ in $\mathbb{R}^d$ which induce a
Voronoi partitioning of the space into $n$ regions under, say, Euclidean metric.
What is an efficient way of ...
- 2,390
0
votes
1
answer
53
views
Clustering data using mixed integer linear programming
I am trying to understand if it is possible to use mixed integer linear programming (MILP) in order to perform a basic clustering operation to a dataset $D$. I know there exists standard algorithms ...
- 2,119
1
vote
0
answers
46
views
Spectral partitioning and Fiedler Vector
As we know, the Fiedler vector is the eigenvector corresponding to the second smallest eigenvalue and this vector can be used for graph partitioning. We also know that this vector comes from a relaxed ...
- 43
2
votes
0
answers
44
views
Can clustering be implemented as Linear Programming?
When considering Gaussian mixture models (GMM) one efficient algorithm is the Expectation-Minimization (EM) algorithm. The E-step famously determines the degree of membership.
For example, given a GMM ...
- 2,119
0
votes
0
answers
13
views
K-Means-Algorithm: After 4 consecutive Iterations a Cluster has assumed three different sets
I am currently reading an analysis for the $k$-means algorithm. It states as a side note following lemma without a proof:
Assume we are given four consecutive Iterations of the $k$-means algorithm. ...
- 155
0
votes
0
answers
24
views
Partition With Ranking to Solve A Clustering Problem
I have r restaurants and f friend where no of f >> no of r. Basically this is a clustering problem. I want to find the nature of clusters(i.e which restaurant consists how much no of friends)
...
- 333
2
votes
0
answers
92
views
Is this implementation use HBOS mathematic?
I'm experimenting with an unsupervised statistical-based outlier detection so-called XBOS on top of the KMeans clustering algorithm. It is claimed that XBOS generates outlier scores as HBOS does. I'm ...
- 73
0
votes
0
answers
53
views
Matching the labels of a clustering with ground truth labels for performance analysis
I'm working on clustering a dataset for which I have ground-truth labels. I want to evaluate the confusion matrix between the predicted and ground truth labels, but the labels assigned by my ...
- 61
0
votes
0
answers
21
views
Clustering with Matrix norm
Hello I am trying to learn some numerical linear algebra and I need some help.
my problem:
we have $225$ freshmen students in $15$ groups of $15$ students in each. for each student $3$-vector is ...
- 383
1
vote
0
answers
36
views
Error rate in comparing clusterings or partitions
Given $n,k \in \mathbb{N}, \ k < n$, we assume that there is an optimal partition $P$ of $n$ elements into $k$ bins.
Given a random partition $Q$, what is the expectation value $E(r)$ of $r$, the ...
- 61
0
votes
0
answers
20
views
How to solve the following clustering problem with special constraints and imperfect information?
Given a set of nodes $[v_1, v_2, ... v_n]$ in order, I want to do a clustering task that assign all the nodes into a variable number of groups. I tried to do this by finding the parent node for each ...
- 1
0
votes
0
answers
52
views
Measuring cluster-ness in graph by operation on the adhjacency matrix
We have a weighted graph G=(V,E). Each vertex represents a d dimensional node embedding. the feature matrix $H\in \mathbb{R}^{|V|...
- 153
0
votes
0
answers
16
views
One-sided clustering in 3D space
Suppose we have some 3D observations of the form $a_i = {x_i, y_i, z_i}$ where all coordinates are non-negative. Is there then a way to cluster them according to the "outermost" point of a ...
- 1
0
votes
0
answers
20
views
how to calculate the variance between some observations when each observation is an n*m matrix
I have a cluster of 250 observations. each observation is a 4 by 9 matrix.
4 is number of variable parameters observed and 9 is number of days, observations were collected.
I want to know the ...
- 15
1
vote
0
answers
18
views
Expectation Maximization : Show that the E step is the folowing
Given that $X_1,X_2 \dots X_n$ random variables distributed $exp(\theta)$.
let $T>0$ constant , and we define instead of $X_i$ , $(Z_i,\delta_i)$ such as : $$Z_i = min\{Z_i,T\}$$ $$\delta_i = \...
- 119
0
votes
0
answers
31
views
Maximize colors within a circle
I have a set of $m$ points $P$ over a large bidimensional space, each point having a color. Every color belongs to one of $n$ disjunct sets $S_i$ of colors. Given a circle $c$ we define $C_c$ as the ...
- 101
0
votes
0
answers
20
views
Indexing The Nodes of a Dendrogram
Suppose I have a dataset $\{x_i\}_{i=1}^n$ that I have implemented some hierarchical clustering algorithm (e.g., Single-Linkage Clustering) on. This gives me a dendrogram, which we can use to ...
- 61
0
votes
0
answers
18
views
Is vector quantization belonging to the extention of K-means clustering
In unsupervised learning, vector quantization belongs to the extension of K-means clustering? since K-means tries to develop clusters with corresponding chose optimized centers to represent and find ...
- 71
1
vote
0
answers
41
views
Normalize an adjacency matrix twice
I am working on a graph clustering problem and i've seen that applying two consecutive normalizations on the adjacency matrix gives much better performance than when applying a single one.
I first ...
- 55
0
votes
0
answers
35
views
A "straightfoward" statement about eigenvalues
I'm reading a paper about clustering techniques and I found the following easy construction
Let $S = \{s_1,\dots , s_n\}$ be a ser of $n$ points where each $s_i \in \mathbb{R}^2$. Suppose that $S = ...
- 501
1
vote
0
answers
17
views
label a set of data points
I have a set of data points in a 3-dimensional space. Points are approximately in two rows, like this (with 3 in secondary row and 7 in primary row):
I need to label both rows separately. For example,...
- 153
0
votes
0
answers
41
views
Am I interpreting this notation correctly?
I'm trying to parse a paper about a new (to me) clustering algorithm into code, and I want to make sure I understand the math correctly... but the notation is holding me up. From page 3 , equation 2:
$...
- 925