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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
11 views

Spectral Clustering: Finding the normalized minimum cut using the laplacian

I am trying to prove that finding the min $Ncut(A,B)$ for a edge weight graph $W$ with the diagonal matrix of edge degrees $D$ is equivalent to solving for $f \in \{a,b\}^n$ with the constraint that $...
bluesquare's user avatar
1 vote
0 answers
14 views

Maximum number of local minima in k-means

Suppose $\mathcal{Z} = \{z_1, \dots, z_n\}$ is the set of points in $d$-dimensional Euclidean space. The aim is to partition the dataset into $(K\leq n)$ distinct clusters $R_1,\dots, R_K$ where $R_i\...
entropy's user avatar
  • 147
0 votes
0 answers
13 views

Metrics for document clustering with measure of synonyms

I asked this question on Data Science stack exchange, but didn't get any responses there. I have a (finite) vocabulary which is a metric space, where the metric measures how antonymous the words are. ...
user avatar
3 votes
1 answer
210 views

Why do randomly drawn numbers tend to repeat themselves?

I track the behavior of random numbers and I have discovered that once a number appears, it tends to reappear again shortly thereafter. For example, I've been tracking the Red Powerball in the ...
steveK's user avatar
  • 119
1 vote
0 answers
29 views

References for a statistics question relating to clustering

I am interested in references for the following research topic. It was mentioned to me that this may be a classically studied question, but I'm unsure what line of work of references to begin looking ...
spectrum's user avatar
0 votes
0 answers
17 views

notation for clusters of 2D data points

Is there any convention about the notation to use for clusters of $2-$D data points? I have a set of clusters of $2-$D data point. I can denote each cluster with $c_i$, where $i = 1, 2, ..., n$, and $...
Ommo's user avatar
  • 329
1 vote
1 answer
37 views

Derivation of a function - GBM

why does the sum disapear in this derivation: derivation of loss Mean Squared Error. It comes from the following wikipedia page: https://en.wikipedia.org/wiki/Gradient_boosting. It is the last ...
F.I.'s user avatar
  • 15
0 votes
0 answers
10 views

Eigenvectors corresponding to eigenvalue 1 in the Normalized Laplacian - Why does it represent clusters?

Consider the Normalized Laplacian associated to a similarty graph $$ L = D^{-1/2}SD^{-1/2} $$ I have two sources stating that, in the "ideal case of zero noise", the eigenvectors ...
ygh's user avatar
  • 121
0 votes
0 answers
15 views

minimizing Earth Mover Distance

So I have a discretized magnitude spectrum $S \in \mathbb{R}^n$ ($n$ number of bins), and a set of frequencies $f_1, f_2, ..., f_m$ (not necessarily corresponding to any of the discretized bin ...
SmoothKen's user avatar
  • 419
1 vote
0 answers
309 views

What is the correct formula for Within Cluster Sum of Squares

I am studying clustering with K-Means algorithm and I got stumbled in the "inertia", or "within cluster sum of squares" part. First I would appreciate if anyone could explain me ...
Artur Juan Dantas's user avatar
1 vote
0 answers
94 views

Modeling a similarity measure between numbers based on predictive probability

Suppose I'm trying to predict a number $v_p \in \mathbb{R}$ and, thanks to sampling, I know that the prediction $v_p=a$ is true in $P(v_p)=P(a)$ percent of cases. In other words, $P(a)$ percent of the ...
Ben W's user avatar
  • 31
0 votes
0 answers
17 views

Standard metric for the distance between two clusters

Let $A=\{A_1,A_2,\cdots,A_m\}$ and $B=\{B_1,B_2,\cdots,B_n\}$ be two sets of points in $k$-dimensional Euclidean space. Each points $A_i$ or $B_i$ can be thought of as a feature vector of a data ...
govindah's user avatar
  • 107
0 votes
0 answers
20 views

Using goodness of fit statistics to cluster data

We are working on a wrapper that clusters observations, wrapping around a multivariate linear regression model within each cluster of observations. The idea is to use some goodness of fit statistic ...
Werner Lucifer's user avatar
3 votes
1 answer
59 views

Managing warehouse based on how likely it is that products are ordered together

I am trying to solve a rather difficult issue at my job right now. We are interested in installing a set of automatic trays in our warehouse, each of which can hold $N \in \{5, 6, \dots, 20 \}$ unique ...
Owen S's user avatar
  • 31
0 votes
1 answer
17 views

Comparing statistical features extracted from time series using correct distance metrics

I would like to cluster 400 car rental demand time series (small positive valued) based on the following 7 statistical features: entropy, number of mean crossings, 95th percentile, root mean squared, ...
Jose_Peeterson's user avatar
0 votes
0 answers
23 views

Integrating over euclidean spaces: A formula from a seminal paper on $k$-means clustering

I am studying the seminal paper Some methods for classification and analysis of multivariate observations (MacQueen). It is the first presentation of the $k$-mean clustering model. I am a computer ...
lafinur's user avatar
  • 3,332
1 vote
1 answer
73 views

The distance formula used in Kernel K-means in tslearn

I am reading the document of the class tslearn.clustering.KernelKMeans and find its source code. I have questions on the function _compute_dist from the source code which I quote as follows ...
Lin2568's user avatar
  • 325
0 votes
0 answers
13 views

K-means algorithm: the behavior of the cluster vector around the global optimum.

I am studying the k-means clustering algorithm. Suppose, I have 2 clusters and the partition vector $I$ is a binary vector indicating whether an observation belongs to $k^{th}$ cluster. Further, ...
entropy's user avatar
  • 147
1 vote
0 answers
16 views

Theoretical guarantee of binary-relation-preserving embeddings

Suppose we have two sets $A = \{a_1, a_2, \ldots, a_n\}$ and $B = \{b_1, b_2, \ldots, b_m\}$, together with some binary relations between them $R \subseteq A \times B$. We want to have two embedding ...
Vezen BU's user avatar
  • 2,016
3 votes
0 answers
62 views

K-Medoid Clustering

The question I am trying to answer is: (k-medoids clustering) What are the resulting clusters when the k-medoids algorithm is used with $k = 2$ and initial random medoids $\{(1, 2), (2, 1)\}$ on the ...
ClareB's user avatar
  • 31
0 votes
0 answers
21 views

Separation of points by polytopes

I have a set of roughly $N\sim50'000$ points in $\mathbb{R}^d$ where $d<50.$ Most of those points are colored black but some (roughly 1% to 5%) are colored red. My goal is to "understand" ...
g g's user avatar
  • 2,727
0 votes
0 answers
169 views

Normalized graph cut

Is finding the normalized cut of an undirected weighted graph the same as normalizing the weights and finding the cut? Consider finding the minimum cut (min-cut) of a connected, undirected weighted ...
Sup's user avatar
  • 101
0 votes
0 answers
31 views

Graph Decomposition by Clustering

Suppose $G$ is a d-regular graph with $n$ vertices, such that $\log n$ is much smaller than $d$. Suppose we create a set $S$ of vertices such that $|S| = \frac{n \log n}{d}$. For every vertex in the ...
Sandra's user avatar
  • 1
1 vote
0 answers
32 views

How is spectral clustering related to bayesian clustering methods?

What is the advantage of spectral clustering over bayesian cluster estimation techniques like stochastic block models, mixed-membership stochastic block models?
tonygrey's user avatar
0 votes
0 answers
28 views

Statistical test for comparing number of clusters in data

I am performing $K$-means clustering on a dataset consisting of $n$ observations and $d$ variables, and I'm trying to determine the optimal number of clusters. Is there a test that can determine the ...
RyRy the Fly Guy's user avatar
1 vote
1 answer
85 views

probability of seeing a set of combinations

Say I have 3 combinations of letters picked at random from the alphabet, with duplications forbidden within a combination, but allowed between combinations (i.e. ...
Tim Kirkwood's user avatar
0 votes
1 answer
60 views

How do you find the mean proximity of two clusters using Manhattan Distance way or the Euclidean Distance way?

Question Solution I don't understand how the mean proximity is calculated here like it says take the average of the $x$ components then add it with the average of the $y$ components of these $16$ ...
Loren Beer's user avatar
0 votes
1 answer
153 views

Why can a similarity matrix be used instead of a Laplace matrix when using spectral clustering methods?

When we are using spectral clustering methods, we often construct similarity matrices $S$ between data, and use the similarity matrix to derive the Laplacian matrix $L$ for further clustering. But in ...
Haoyi Lei's user avatar
1 vote
0 answers
13 views

How is this R squared calculated in context to clusteiring?

I was reading the paper "Consistent Individualized Feature Attribution for Tree Ensembles" by Scott Lundberg et al and cannot understand how the calculation for the $R^2$ works here - see ...
Penguines's user avatar
1 vote
1 answer
34 views

On the choice of indicator function in graph clustering problem

In section 5.1 from A tutorial on spectral clustering by von Luxburg (p. 10), the author reformulates RatioCut using the graph Laplacian. To do so, he defines a partitioning vector f, such that $$ f_i=...
Blade's user avatar
  • 461
1 vote
0 answers
24 views

k-means errors for a block Gaussian vector

Consider a standard centered Gaussian vector $(X_1,...,X_n)$ with an approximate block structure, i.e. there is $q$ and a partition of $\{1,...,n\}$ in $q$ classes such that if $i,j$ are in the same ...
kaleidoscop's user avatar
1 vote
0 answers
95 views

Partitioning antidirected trees such that the induced graph by the partition is also an antidirected tree of constant size

Statement: Define for an oriented graph $G$ and a partition $\mathcal{P}$ of $V(G)$, the contracted graph $G[\mathcal{P}]$, with vertex set $V(G[\mathcal{P}]) = \mathcal{P}$ and edge set $$E(G[\...
alosc's user avatar
  • 75
3 votes
1 answer
31 views

Common issues with graph partitioning algorithms

In the Graph Representation Learning book by Hamilton (P. 24), it is mentioned that : [...] one option to define an optimal clustering of the nodes into K clusters would be to select a partition that ...
Blade's user avatar
  • 461
0 votes
0 answers
61 views

How should I interpret the double summation sign?

I am reading this paper on the Hierarchical Clustering. The author introduces cluster intra-compactness indicator and it is formulated as follows $$RR_{intra}(S) = \sum_{i \in D \\ C_{k} \in S | i \in ...
Karina's user avatar
  • 141
0 votes
0 answers
63 views

How should I read this dividing notation in the sigma index, aka "$|$"?

I am reading this paper on the Hierarchical Clustering. The author introduces cluster intra-compactness indicator and it is formulated as follows $$RR_{intra}(S) = \sum_{i \in D \\ C_{k} \in S | i \in ...
Karina's user avatar
  • 141
1 vote
0 answers
151 views

Normalized Laplacian Proof

I'm reading a lecture on clustering (https://www.math.ucdavis.edu/~strohmer/courses/180BigData/180lecture_clustering.pdf) And I was wondering about the proofs for Theorem 3.3 and 3.4. That is, For two ...
Jayden Rice's user avatar
1 vote
0 answers
47 views

Trajectories, Paths Clustering Using Expectation Maximization

[tl;dr]: Go to the question and the part below the question directly. The question should be easy. I'm a newbie on probability. Trajectories are a series of paths, each of them consisting of multiple ...
Chuan Sun's user avatar
0 votes
1 answer
56 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 ...
Gsag21's user avatar
  • 3
3 votes
1 answer
339 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 understand, I stumbled upon this great post, that ...
snatchysquid's user avatar
2 votes
0 answers
28 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 ...
chesslad's user avatar
  • 2,533
2 votes
1 answer
114 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, ...
Turing's user avatar
  • 456
0 votes
1 answer
434 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{...
Turing's user avatar
  • 456
1 vote
1 answer
228 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 ...
ASH's user avatar
  • 147
0 votes
0 answers
37 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). ...
scurpuleux's user avatar
2 votes
0 answers
177 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,...
Hans's user avatar
  • 29
1 vote
0 answers
22 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 ...
Alejandro's user avatar
  • 177
1 vote
1 answer
20 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 ...
Vikram Murthy's user avatar
0 votes
1 answer
215 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 "...
Peiffap's user avatar
  • 355
2 votes
1 answer
123 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 ...
Daniel's user avatar
  • 2,630
0 votes
1 answer
233 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 ...
Marion's user avatar
  • 2,219

1
2 3 4 5
7