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.
2
votes
0answers
11 views
Measure overlap of cluster in higher dimensions
I would like to describe how good an algorithm is clustering my data. For that I would like to create a measure on how much two point-clusters overlap or are away from each other.
Take for example a ...
0
votes
0answers
28 views
Why is normalisation of a Laplacian matrix defined as $L - I$?
I have a piece of code that computes the Laplacian matrix using $I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$, that is, it computes the symmetric normalised Laplacian. This Laplacian is not defined when $...
0
votes
0answers
26 views
Some technicalities about Modularity Clustering Criterion proposed by Newman.
I am studying the well-known paper of Prof. Newman title "Finding community structure in networks using the eigenvectors of matrices" which can be found in this address:
https://arxiv.org/pdf/...
3
votes
1answer
32 views
Compute component probabilities in EM-algorithm with log densities?
I coded up an implementation of the EM-algorithm for Gaussian mixtures. In the E-step I compute, for each row in the data matrix, the probability $p_i$ that it has been drawn from the component $i \in ...
0
votes
0answers
15 views
looking for a simple example in machine learning with step-by-step procedure
I am looking for a simple example in the area of machine learning as well as a step-by-step procedure.
For example, if I have 3 measurement devices and each one reports 5 data hourly how can I ...
2
votes
0answers
27 views
Is it appropriate to use clustering to partition the dependent variable into separate datasets for a home price prediction model?
I'm struggling to decide how to deal with a heteroskedasticity problem in a home price prediction model I'm developing. The training set residuals are normally distributed around zero, but they have ...
0
votes
0answers
25 views
Ambiguity with Kronecker Delta function
Given $Q = \sum_{i j s r} [(a_{i j s} − \frac{k_{i s} k_{j s}}{2m_{s}}) \delta(s,r) + c_{jsr} \delta(i,j)] \delta(\gamma_{i,s},\gamma_{j, j})$
Where $\delta$ is Kronecker function. I am having ...
2
votes
1answer
26 views
Verifying the correctness simplifying an equation?
Give a $N \times N$ matrix $ P=(p_{i j})$; I defined a clustering criterion as follows.
$ Q = \rho_{g} \sum_{i, j}(\lambda^2 m_{i}^2 m_{j}^2 - 2 \lambda p_{i j} m_{i} m_{j} )$ where $\lambda = \...
0
votes
1answer
15 views
Dimensional properties derived from PCA eigenvectors
Background
Let's assume I'm using principal component analysis to carry out clustering of a 2-d data set, using a non-normalized covariance matrix to carry out the operation. I then solve for the ...
0
votes
1answer
24 views
Selecting a cluster based on minimum average distance
I have a symmetric matrix of non-Euclidean distances of size $N$ (say, 500) and I would like to select one cluster of a fixed size $K$ (say, 25), so that it has the smallest average distance within ...
0
votes
1answer
22 views
K-Means Clustering Proof
I'm attempting to prove the following equality (K-Means Algorithm):
$$
\frac{1}{\lvert C_k \rvert}\sum_{i,i' \in C_k}\sum_{j=1}^P \left( x_{i,j} - x_{i',j} \right)^2 = 2\sum_{i \in C_k}\sum_{j=1}^P \...
0
votes
3answers
64 views
What does the slash mean in this set notation?
In Section 2.2, Definition 1 of this paper, it has the following:
Here, $x,y \subseteq X $ and $X$ is a set of $d$-dimensional vectors. $dist(x,y)$ stands for the Eucledian distance between $x$ and $...
1
vote
1answer
18 views
Can FFT be used to cluster sound waves based on their similarity?
I am new to this so apologies if the question appears trivial.
Say we have n sound files and we want to cluster them to identify which ones are more similar. I ...
0
votes
0answers
21 views
Number of Clusters - SSE
Hello and thanks in advance for your time,
as i am practicing clustering,I came across an assignment (http://axon.cs.byu.edu/Dan/478/assignments.php?id=clustering).
This one requires to calculate SSE(...
0
votes
0answers
14 views
k-means cost functions comparison
$J_{avg^2} = \sum_{j=1}^{k}\sum_{x\in C_j}d(x,m_j)^2$ and $J_{IC} = \sum_{j=1}^{k}\frac{1}{|C_j|}\sum_{x\in C_j}\sum_{y \in c_j}d(x,y)^2$, where $m_j = \frac{1}{C_j}\sum_{x\in C_j}x$. Now I want to ...
2
votes
1answer
32 views
Find $k$-clique with max min weight.
I have a problem with the following equivalent formulation in graph theory:
Take $G(V, E, W)$ a complete weighted graph, where $w_{ij} > 0$ is the weight of edge $e_{ij}$. For a given $k$, find ...
1
vote
0answers
118 views
How can I prove that clust-p is NP-complete?
CLUST-P:
Instance: A a non-empty set, α : A × A → N, p, s ∈ N
Question: Does A have a partition, A1, A2, . . . , Ap, such that max α(u,v) <=s, u,v∈Ai ∀1 <= i <= p?
It is obvious that A ...
0
votes
0answers
10 views
Adjusted Rand Index Standard Deviation
I'm doing some clustering analysis and am aware of the Rand and Adjusted Rand Index (ARI) that can be used to compare similarity between groupings.
Is there a theoretical result for the standard ...
0
votes
0answers
10 views
Calinski - Harabasz criterion for choosing optimal number of clusters
I've been using the CH criterion to determine the optimal number of clusters for some data I'm working with. I know that in general you would evaluate the criterion for a number of different choices ...
0
votes
1answer
44 views
How to find the best fit point inside a cluster?
I have a cluster with many points.
Like this:
Where I can visually identify a cluster of points and a ...
0
votes
1answer
36 views
What is the appropriate weight ($W_k$) (for two arbitrary partitions)?
I already asked a similar question, And from the answer I received, another question came to my mind.
A positive integer can be partitioned, for example, the number 7 can be partitioned into the ...
3
votes
1answer
48 views
Is this true for every partitioning?
I have two categories (category1 and category2 ) and The size of both categories is equal to each other. if we partition each categories arbibtrary .Is this proposition proven? or rejected?
$n_T \...
0
votes
1answer
69 views
Clustering coefficient in a random graph model with transitivity
Reading the book Networks, by Mark Newman I found this exercise and I have some question about it:
"We can make a simple random graph model of a network with clustering or transitivity as follows. We ...
0
votes
1answer
69 views
Uniform Effect of K-means Clustering
In the following link is discussed the uniform Effect of K-means Clustering:
https://www.springer.com/cda/content/document/cda_downloaddocument/9783642298066-c2.pdf?SGWID=0-0-45-1338325-...
0
votes
0answers
11 views
Explanation of the Adjusted Rand Index formula
Could anyone give an explanation of the adjusted Rand Index formula?
I know it can be used in cluster analysis to compare two clusterings, and it is preferable over the standard rand index because it ...
0
votes
0answers
11 views
How to model and formulate this optimization problem on clustering?
I have a system with 72 nodes.
I have a binary adjacency matrix $S$ of size $72\times 72$. If $S_{i,j}=1$, then node $I$ is adjacent to node $j$. So, we also have $S_{i,j}=S{j,i}$. So, $S$ is a ...
0
votes
1answer
25 views
How to calculate the updated centroids of clustering?
I have 100 points on a two dimentional space. Any point $i$ is defined by the coordinates $(x_i,y_i)$.
Lets say we perform Kmeans clustering over these points and generate clusters. Now, each ...
0
votes
0answers
21 views
can we perform SVD in spectral clustering to get top-$k$ eigenvector?
In spectral clustering, we need to compute top-k eigenvector for k-means clustering
I have been told that SVD and eigendecomposition is equal for symmetric matrix here page 9.
I try in matlab
<...
1
vote
1answer
69 views
what`s the name of this clustering algorithm?
I have been learning the fuzzy clstering algorithm recently,and I got an object function as following:
\begin{array}{l}
\min \;\;J = \sum\limits_{i = 1}^N {\sum\limits_{k = 1}^K {\sum\limits_{j = 1}^...
1
vote
1answer
37 views
Algorithm to express distribution of 1s and 0s
I'm a software dev, not a math wiz so bear with me. I'm trying to find an algorithm to express a sequence of ones and zeroes as a single decimal number between 0 and 1 based on how they are ...
2
votes
0answers
21 views
Convert a vector of distances to a normalized vector of similarities
I'm struggling to find a way to solve this problem.
I have derived a $m \times n$ matrix containing in each row the Mahalanobis distance from a certain centroid. So at the end I have $m$ rows each ...
1
vote
1answer
36 views
Clustering computation in pair approximation model
Let's consider a square lattice of cells. Each cell can be either occupied by a species (1 or 2) or be empty (0).
Each cell can be either in state 1, 2 or 0.
In the pair approximation model, I ...
1
vote
0answers
14 views
Calculating clusters based on position ellipses
I'm looking for pointers to existing algorithms that take a number of position ellipses (centre, axis orientation, majr/minor axes) and cluster them together based on proximity to each other. The ...
0
votes
0answers
70 views
Object segmentation in PCL
Sorry because I am not sure if this question fits here.
I am new working in object recognition and localisation. I am using PCL to capture a model of an object and localise it. It works well.
I ...
1
vote
1answer
58 views
Permuting with Sinkhorn normalization: find $\sigma$ s.t. $\bf{min}\frac{dS}{dp}\rightarrow \bf{\sigma} \times \bf{X'}= \bf{X}$
I have a matrix of samples vs. features and would like to organize or permute the features such that the sum of the first derivative along these features is minimized for all of the samples within the ...
0
votes
1answer
52 views
“Reverse Clustering” Algorithm?
The clustering algorithm splits points into disjoint sets in a way that minimizes the intra-set distance.
Is there an efficient algorithm which does the opposite (maximize the intra-set distance)? I....
1
vote
1answer
49 views
K-Means equality proof
Is there any geometrical and or short proof for the equality
${\displaystyle {\underset { }{ }}\sum _{i=1}^{k}\sum _{\mathbf {x}
\in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu}}_{i}\right\|^{2}}={\...
0
votes
1answer
98 views
Kmeans Clustering Input after Dimensionality Reduction?
I would like to know what do i have to do for the input of Kmeans Clustering if I use Dimensionality Reduction (SVD in this case) after TF-IDF? Does these three matrices become my input (A = USVt)? or ...
1
vote
1answer
25 views
Clustering algorithm to group linear equation into groups to achieve certain conditions
Given linear equations of many lines. There exists groups of these lines that intersect near a single point. How do I cluster these groups of lines. See illustration below for better understanding.
...
1
vote
1answer
11 views
How exactly is the prototype clustering solved using gradient descent?
How exactly is the prototype clustering solved using gradient descent?
I don't see any derivatives.
-1
votes
1answer
22 views
Find the optimal number of number of clusters to best represent the data?
Given distance metric and N vectors, what would be algorithm or procedure to decide how many clusters to form ? My question is not how to cluster, but how to decide how many clusters is the most ...
2
votes
1answer
64 views
What's the algorithm for agglomerative hierarchical clustering?
I have read some descriptions about agglomerative hierarchical clustering, however, I cannot seem to find an accurate description of the algorithm.
My notes give:
Assign each observation to own ...
0
votes
1answer
13 views
What's the common way to utilize distance functions for clustering?
What's the common way to utilize distance functions for clustering?
Like does one set some thresholds for the distances and do grouping based on that?
1
vote
1answer
32 views
Best vector distance measure for contrasting clustering?
Let say i have V-vectors, everyone with size N, which measure of distance should I use if i want to cluster them by the following criteria : the more elements vector has in common with other vectors ...
2
votes
1answer
77 views
F - measure in Clustering
We can define the F - measure as follows:
$$F_\alpha=\frac{1}{\alpha \frac{1}{P}+(1-\alpha)\frac{1}{R}} $$
Now we might be interested in choosing a good $\alpha$. In the article The truth of the F-...
0
votes
0answers
14 views
Divergence Distance Measure
I am implementing different distance measures for k-means, during which I found a distance measure, Divergence as it is named in the ref given below. It says
Click here for the formula
where xi and ...
0
votes
1answer
15 views
clusterization with minimization of the SSE
I have found the following document in which it explains the minimization of sum of squared errors applied to clusterization. An extract of the book is the following:
Actually I am having some ...
0
votes
0answers
9 views
Analysing Model Prediction Error Using Clustering
I have a linear model that makes predictions based on 5 predictor variables.
I now want to analyse where my model is getting things wrong, in the space of predictor variables, and I'd like to do ...
0
votes
0answers
15 views
measuring intra cluster variance for different distance metrics
I am currently exploring different distance metrics with kmeans, I want to ask that suppose I have a dataset having mixed structure like this, I have come to know that different distance metrics are ...
1
vote
0answers
31 views
What defines a convex Cluster and how it differentiates from other types?
I keep encountering the term "convex cluster" which I cannot understand what it means. I am exploring different types of clustering methods and in the description sections some mention advantages/...
