Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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/...