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.
269
questions
1
vote
0answers
6 views
I'm doing clustering using k-maps but in the end all the vales come in the same cluster
This is the data im working with
Using cases 6,9,15 as the initial cluster centers
Second
Using the mean values of the clusters insted of the initial values.
There some change in the clustering.
...
0
votes
0answers
37 views
Plot data points according to the pairwise distance matrix
Consider eight data points. The following matrix (i.e., a symmetric matrix with the lower triangle elements) shows the pairwise distances between any two points.
0
11 0
5 13 0
12 2 14 0
7 17 1 18 0
...
0
votes
0answers
14 views
How to determine if a positive integer is comparatively small
Given a set of positive integers, what is a basic statistical method that cuts off the smallest numbers in the set if the method (fed some parameter) determines they are "negligible" or &...
1
vote
0answers
15 views
Hierarchical Clustering with Ward Distance
I know how hierarchical clustering (with a certain definition of inter-cluster distance) works. And I know that Ward's procedure is based on the goal of minimizing the sum of the squared errors ...
0
votes
0answers
23 views
Compute Gower's distance manually
Given
a=(1,0,13,apple)
b=(1, 1, NA, pear)
c=(0,1,12,apple)
The first two elements for each ...
1
vote
1answer
33 views
Any common methods to integrate $\frac {\int dx P(x) x r(x)}{\int dx P(x) r(x)}$ when $P(x)$ is a guassian distribution?
I am currently studying David MacKay's Information Theory, Inference, and Learning Algorithms.
In chapter 20, where he talks about modify kmean algorithm into a soft kmean algorithm (Gaussian Mixture ...
0
votes
0answers
19 views
Optimal k-means clustering solution for 2x2 and 3x3 blocks of quadratic grids (proof or proof idea sought)
Condider a set $\mathcal{X}$ of $n \times n$ data points arranged on a quadratic grid which should be quantized by a single centroid (i.e., $k$-means clustering with $k=1$). The optimal position for ...
0
votes
0answers
5 views
Reducing features from k-means and hierarchical clusters
I have a dataset with 170 features. I use K-means and hierarchical clustering to determine the "optimal" number of clusters (between 10-12). I calculate clustered permutation feature ...
0
votes
0answers
14 views
LOF - local reachability density - Why is it considered an average?
In the context of Local Outlier Factor (described in the following paper https://dl.acm.org/doi/10.1145/335191.335388 ), the local reachability density of a point p is defined as follow :
$$ lrd_K (p) ...
0
votes
0answers
15 views
Gaussian normalized by local density
programmer coming over to the light side. You guys are smarter, and your stack exchange is cleaner, so please bear with me.
To summarize what I'm trying to do in general:
I have a very high ...
0
votes
1answer
32 views
Why is the silhouette coefficient of a clustering between $[-1,+1]$?
I have been recently reading about clustering validation and came upon the silhouette coefficient, represented by the following formula.
Everywhere I read about this coefficient, it says that it is ...
1
vote
1answer
22 views
Division by $0$ Extreme Case in Fuzzy C-Means Clustering
I have a question about calculating the partition matrix for the Fuzzy C-Means (FCM) Clustering Algorithm. For any point $x_i$ and cluster centroid $c_j$, the membership value $w_{i,j}$ is computed by ...
0
votes
0answers
31 views
Generative Model for random graphs with community structure based on Random Walks (similar to Stochastic Block Model)
There are many algorithms in which the community structure of a graph is recovered using Random Walk based methods such as Walktrap, Markov Clustering Algorithm etc. One of the most popular random ...
0
votes
0answers
12 views
Formalizing the description of a Neural Network that takes some input and maps it to a Euclidean embedding which is optimized for class separation
I have a neural network which we can just think as some function $f$ with learned parameters $\theta$ that takes as an input an image which we can think of as a matrix $M_i \in \mathbb{R}^{3 \times ...
0
votes
0answers
16 views
Recovering a graph that consists entirely of disjoint cliques given edge probabilities
We have $n$ nodes and an $n \times n$ probabilistic adjacency matrix $A$ such that $A_{ij}$ is the probability that an edge exists between nodes $i$ and $j$.
Our objective is to find the maximum ...
0
votes
0answers
7 views
Responsibility Matrix (r) and Availability Matrix (a) of Affinity Propagation Clustering Algorithm
Could anyone explain about the physical interpretation/meaning of setting up the Responsibility Matrix and Availability Matrix inside Affinity Propagation Clustering Algorithm ?
In other words, what ...
0
votes
0answers
11 views
Proving linear seperation in balanced 2-Clustering
Let's say we want to cluster $2n$ point into two equal sized clusters $S_1$ and $S_2$. I now want to find the optimal clustering. So the clusters need to minimize the within cluster sum of squared ...
1
vote
1answer
26 views
Partitioning points into 2 sets of euqal size by a line
How can u find every possible division of $2n$ points into 2 sets each containing $n$ points, with the condition, that these two sets need to be divisible by a line (for a 2 dimensional space).
My ...
1
vote
0answers
27 views
the centroid-based clustering is NP-hard
I am trying to understand why the centroid-based clustering is NP-hard.
Assume we have one-dimensional sorted data set $x_{1}, \dots, x_{n}$ and we want to find, say $k$, optimal clusters (intervals) $...
1
vote
1answer
28 views
k-mean clustering minimize L1 distance
k-mean clustering minimize L1 norm
In k-mean clustering, if I want to minimize the L1 distance from any point to cluster center, the error function and derivative is shown above.
However, according to ...
1
vote
0answers
23 views
Unsure about Linearized Cluster Assignments via Spectral Ordering paper
I've been attempting to implement the method of linearized cluster assignments to cluster data just as shown in Linearized Cluster Assignment via Spectral Ordering by Chris Ding and Xiaofeng He. I've ...
0
votes
0answers
21 views
Measuring the difference between two sets of n dimensional points.
I am working on a machine learning algorithm where names of females and males are represented as an n-dimensional vector. For example, in a two dimensional space, those names get plotted as:
How do I ...
0
votes
0answers
5 views
Creating linear spaces between two intervals
I have to create linear spacing between [min, max] of multi-dimensional values. Say "W" is a (100, 2) matrix (it can also be 500, 5) and the min = -9.1 and max = 12. Then how can I create ...
0
votes
0answers
26 views
What algorithm or statistic technique can help me to recognize the most “relevant” groups based in the number of their populations?
Let's assume I have a number of groups, for example 0 to 999. Each of the groups have a population that range randomly from 1 to 1 million members. I want to recognize the most statistically "relevant"...
0
votes
1answer
20 views
what (arithmetically simple) algorithm can help me to recognize clusters in a data?
Suppose I have a data of 1000 random values ranging from 0 to 100, I want to detect clusters in the data with numbers near to each other. I decide how near, for example not more than 2.5 of difference ...
1
vote
0answers
23 views
Bipartite Graph Community detection
The main idea is I want to cluster a bipartite network based on total number of shared nodes. Here is an example
A bipartite network
A bipartite network clustered on the criteria that the rectangle ...
0
votes
1answer
19 views
Solutions to generalized eigensystem
Is there a method to solve for $(\lambda, \vec{v})$ eigenpair in the following system?
$$L\vec{v} = \lambda M \vec{v}$$
Here $\lambda \in R$, $\vec{v} \in R^n$, $L \in R^{n \times n}$, and $M \in R^{...
0
votes
0answers
12 views
Min-cut vesus Normalized min-cut
I am studying graph clustering. I have arrived at the optimization approaches min-cut and normalized min-cut. I completely get the min-cut, since it leads us to find the maximum flow in a directed ...
0
votes
1answer
27 views
Linear Program for Hyperplane Sparation
GOAL: I want create a simple linear programming model that can be used to classify new data based off of a found hyperplane. In this particular case I have two classes and I'm given a data set in ...
0
votes
0answers
36 views
Clustering number on ring lattice
I have seen in several places a useful formula that let us calculates the clustering number of regular ring lattice graphs with even degree but I have not found a convincing proof of it. Concretely, ...
3
votes
2answers
71 views
A counter-example to disprove that not every adjacency matrix can be made block-diagonal?
I have a bunch of clusters of proteins (a disconnected graph) and wanted to present this data as an adjacency matrix for various reasons and have been looking for a way to make these adjacency ...
0
votes
0answers
10 views
Which clustering model would best fit this data, or how could I reformat it to be usable with k means or sliding means?
I have data from numerous cities about particulate concentration in the air. For the most part, it does not change drastically from day to day, but certain events, and cycles do occur, such as rain, ...
1
vote
0answers
308 views
Probability of a non-random sample to represent initial Poisson distribution
I'm looking for a way to correctly approach the following noise-signal problem. What I'm doing is a looking for arbitrary structures in a seemingly random input data, akin to a night vision with noisy ...
0
votes
0answers
22 views
Fitting a Second Gaussian Mixture Model
I have a Gaussian mixture, $\sum_{i=1}^{K_1} v_{i} \mathcal{N}(x; a_{i}, A_{i})$. I am given another set of $K_2$ Gaussian centers, $z_{j}$, and I want to find the optimal parameters $\Sigma_{j}$ to ...
0
votes
0answers
14 views
What is the difference between biclustering and clustering?
After reading the wiki page for biclustering (https://en.m.wikipedia.org/wiki/Biclustering), I am really confused on what is the difference between biclustering and clustering?
Any explanation/...
0
votes
0answers
24 views
Is the Hamming distance sensitive to sequence of bits?
Two binary strings ($110$) and ($100$) have a hamming distance of $1$, similarly ($110$) and ($111$) also have hamming distance $1$. Hamming distance is not sensitive to the sequence of bits. Is there ...
0
votes
0answers
16 views
How to measure a semi-supervised clustering problem in topic modeling?
I have a set of documents ($M$). Each document is an article ($m_i$) with a set of tags ($T_{mi}=\{A,B,C, ..., X,Y,Z\}$) where the length of tags is not a fixed number.
I am analyzing documents' ...
1
vote
0answers
35 views
Explanation of Equation for K-means Initialization
I'm currently working on a college project and was having trouble deciphering a formula I ran across. The problem involves the initialization of cluster centers for the K-means algorithm, and here is ...
0
votes
1answer
73 views
prove that sum of quadric form less than the frobenius norm
I was reading this famous paper (Clustering Large Graphs via the Singular Value DecompositionClustering Large Graphs via the Singular Value Decomposition) and find difficulty in understanding a step ...
1
vote
0answers
34 views
Classification of 32 bit integers into 2 classes with uneven probability
I've been given a set of integer data $x_t$ that are all 32-bit unsigned integers. These data have been previously divided into two classes using a function unknown to me as the following:
$$f(x)=\...
1
vote
0answers
50 views
Standard deviation of a cluster
I have a set of measurement points obtained from a sensor and each data point has a standard deviation (which is assumed to be the same for all the points). Clustering is applied and the center of the ...
0
votes
0answers
17 views
Show that the solution of optimization problem for K-means is not unique
Show that the solution of optimization problem for K-means is not unique:
$$\text{arg min} \sum_{l=1}^k \sum_{i \in S_l} \vert \vert x_i - \mu_l \vert \vert ^2$$
s.t. $\mu_1,...,\mu_k \in R^p$ and $\...
0
votes
0answers
19 views
What metrics can be used to describe the clustering of a group of points?
Consider a set of points $\Omega \subset \mathbb{R}^n$ (to make it simple, consider $n=2$). So you basically have a bunch of points on a plane.
I need to find good metrics that can describe the ...
0
votes
0answers
88 views
Custom hash-function that preserves behavior from previous hash-function
Let's define a Hash-function in the following way:
$$ H_n(x) = a_n $$ where $L$ could be any Language with $x \in L$ and $a \in
\{1, 2, \dots, n\}$. So this means the Hash-function $H_n$ should ...
1
vote
0answers
165 views
What sort of clustering/optimization problem is this and is there a specific algorithm/method to solve it?
I have a population which consist of n customers, each of them has an associated rate r and an annual purchase volume apv. Rate and volume are negative correlated to some extent:
The average weighted ...
0
votes
0answers
19 views
Elbow Method for Document Clustering
I am working with BBC-News dataset.
This has 2225 news articles classified between 5 labels.
I am using the text to perform different clustering algorithms and see which one better fits the ground-...
0
votes
0answers
19 views
Interpolating probabilities using similarity information
Is it possible to interpolate the probability values for sampling individual points in a cluster given the probability of selecting a cluster of points event and similarity informations ?
I think the ...
0
votes
1answer
79 views
Time complexity to compute Rand Index
Suppose we have a set $S$ with $n$ elements, and let $\{X_1,\ldots,X_r\}$ and $\{Y_1,\ldots,Y_s\}$ be two partitions (clusterings) of $S$. I would like to know what is the time complexity for the ...
0
votes
0answers
18 views
EM-algorithm (a mixture of uniform and Gaussian)
I am having a hard time with the EM-algorithm. Here's the problem that I am trying to solve.
Dealing with noisy annotations is a common problem in computer vision, especially when using ...
2
votes
1answer
128 views
Why do we use the Laplacian matrix in Spectral Clustering?
When we perform spectral clustering, given a similarity matrix $S$, we define the Laplacian matrix $L$ (normalized or unnormalized). Then, we do eigenvalue decomposition on $L$ and get its eigenvector ...
