# Questions tagged [k-means]

k-means is a method to partition data into clusters by finding a specified number of means, k, s.t. when data are assigned to clusters w/ the nearest mean, the w/i cluster sum of squares is minimized

119 questions
Filter by
Sorted by
Tagged with
122k views

### How to understand the drawbacks of K-means

K-means is a widely used method in cluster analysis. In my understanding, this method does NOT require ANY assumptions, i.e., give me a dataset and a pre-specified number of clusters, k, and I just ...
94k views

### Why does k-means clustering algorithm use only Euclidean distance metric?

Is there a specific purpose in terms of efficiency or functionality why the k-means algorithm does not use for example cosine (dis)similarity as a distance metric, but can only use the Euclidean norm? ...
74k views

### How to decide on the correct number of clusters?

We find the cluster centers and assign points to k different cluster bins in k-means clustering which is a very well known algorithm and is found almost in every machine learning package on the net. ...
28k views

### k-means implementation with custom distance matrix in input

Can anyone point me out a k-means implementation (it would be better if in matlab) that can take the distance matrix in input? The standard matlab implementation needs the observation matrix in input ...
60k views

### How to tell if data is “clustered” enough for clustering algorithms to produce meaningful results?

How would you know if your (high dimensional) data exhibits enough clustering so that results from kmeans or other clustering algorithm is actually meaningful? For k-means algorithm in particular, ...
26k views

### How to use both binary and continuous variables together in clustering?

I need to use binary variables (values 0 & 1) in k-means. But k-means only works with continuous variables. I know some people still use these binary variables in k-means ignoring the fact that k-...
48k views

### Clustering on the output of t-SNE

I've got an application where it'd be handy to cluster a noisy dataset before looking for subgroup effects within the clusters. I first looked at PCA, but it takes ~30 components to get to 90% of the ...
7k views

### Are there any non-distance based clustering algorithms?

It seems that for K-means and other related algorithms, clustering is based off calculating distance between points. Is there one that works without it?
50k views

### Are mean normalization and feature scaling needed for k-means clustering?

What are the best (recommended) pre-processing steps before performing k-means?
15k views

### K-means: Why minimizing WCSS is maximizing Distance between clusters?

From a conceptual and algorithmic standpoint, I understand how K-means works. However, from a mathematical standpoint, I don't understand why minimizing the WCSS (within-cluster sums of squares) will ...
7k views

### Methods of initializing K-means clustering

I am interested in the current state of the art for selecting initial seeds (cluster centers) for K-means. Googling leads to two popular choices: random selection of initial seeds, and, using the ...
19k views

### Why does gap statistic for k-means suggest one cluster, even though there are obviously two of them?

I am using K-means to cluster my data and was looking for a way to suggest an "optimal" cluster number. Gap statistics seems to be a common way to find a good cluster number. For some reason it ...
14k views

### Compute BIC clustering criterion (to validate clusters after K-means)

I'm wondering if there is a good way to calculate the clustering criterion based on BIC formula, for a k-means output in R? I'm a bit confused as to how to calculate that BIC so that I can compare it ...
66k views

### What is the relation between k-means clustering and PCA?

It is a common practice to apply PCA (principal component analysis) before a clustering algorithm (such as k-means). It is believed that it improves the clustering results in practice (noise reduction)...
19k views

### Perform K-means (or its close kin) clustering with only a distance matrix, not points-by-features data

I want to perform K-means clustering on objects I have, but the objects aren't described as points in space, i.e. by objects x features dataset. However, I am able ...
48k views

### Determine different clusters of 1d data from database

I have a database table of data transfers between different nodes. This is a huge database (with nearly 40 million transfers). One of the attributes is the number of bytes (nbytes) transfers which ...
8k views

### How do I know my k-means clustering algorithm is suffering from the curse of dimensionality?

I believe that the title of this question says it all.
9k views

### Clustering of very skewed, count data: any suggestions to go about (transform etc)?

Basic problem Here is my basic problem: I am trying to cluster a dataset containing some very skewed variables with counts. The variables contain many zeros and are therefore not very informative for ...
40k views

### How would PCA help with a k-means clustering analysis?

Background: I want to classify the residential areas of a city into groups based on their social-economic characteristics, including housing unit density, population density, green space area, housing ...
15k views

### Elbow criteria to determine number of cluster

It is mentioned here that one of the methods to determine the optimal number of clusters in a data-set is the "elbow method". Here the percentage of variance is calculated as the ratio of the between-...
13k views

### Clustering procedure where each cluster has an equal number of points?

I have some points $X=\{x_1,...,x_n\}$ in $R^p$, and I want to cluster the points so that: Each cluster contains an equal number of elements of $X$. (Assume that the number of clusters divides $n$.) ...
164k views

### How to produce a pretty plot of the results of k-means cluster analysis?

I'm using R to do K-means clustering. I'm using 14 variables to run K-means What is a pretty way to plot the results of K-means? Are there any existing implementations? Does having 14 variables ...
19k views

### If k-means clustering is a form of Gaussian mixture modeling, can it be used when the data are not normal?

I'm reading Bishop on EM algorithm for GMM and the relationship between GMM and k-means. In this book it says that k-means is a hard assign version of GMM. I'm wondering does that imply that if the ...
6k views

### Is clustering (kmeans) appropriate for partitioning a one-dimensional array?

I want to group the outcome of a function into 2 (or 3) categories. I have a function efficiency=f(weight,speed,#refueling_stops) that takes 3 input parameters and the output tells me how "efficient" ...
2k views

### Standardizing some features in K-Means

I have 21 features in my dataset, some features are more important than others. As a fact I know, if I don't standardize (mean=0, SD=1) any features, then features with low variance will have slightly ...
3k views

### X-mean algorithm BIC calculation question

I'm having trouble understanding some of the formulas in this paper related to BIC calculation (Dan Pelleg and Andrew Moore, X-means: Extending K-means with Efficient Estimation of the Number of ...
48k views

### Clustering with K-Means and EM: how are they related?

I have studied algorithms for clustering data (unsupervised learning): EM, and k-means. I keep reading the following : k-means is a variant of EM, with the assumptions that clusters are ...
57k views

### Clustering a long list of strings (words) into similarity groups

I have the following problem at hand: I have a very long list of words, possibly names, surnames, etc. I need to cluster this word list, such that similar words, for example words with similar edit (...
23k views

### Using BIC to estimate the number of k in KMEANS

I am currently trying to compute the BIC for my toy data set (ofc iris (: ). I want to reproduce the results as shown here (Fig. 5). That paper is also my source for the BIC formulas. I have 2 ...
25k views

### Estimating the most important features in a k-means cluster partition

Is there a way to determine which features / variables of the dataset are the most important / dominant within a k-means cluster solution?
26k views

### Proof of convergence of k-means

For an assignment I've been asked to provide a proof that k-means converges in a finite number of steps. This is what I've written: In the following, $C$ is a collection of all the cluster centres....
23k views

### Initializing K-means centers by the means of random subsamples of the dataset?

If I have a certain dataset, how smart would it be to initialize cluster centers using means of random samples of that dataset? For example, suppose I want ...
2k views

### What are the use cases related to cluster analysis of different distance metrics?

I'm trying to use different distance metrics like Euclidean, Manhattan, cosine, chebyshev among other distance metrics in my k-means algorithm to calculate distances between the data points and the ...
5k views

### How to determine which method is the most valid, reasonable clustering results?

Method 1: Cluster by K-means with initial centroid {27, 67.5} Method 2: Cluster by K-means with initial centroid {22.5, 60} Method 3: Agglomerative Clustering How can I know which method gives a ...
2k views

### K-medians, formula to compute the median

If you are running K-medians, and your distance metric is the L1 norm, how do you derive that the center of each centroid is the median of the data points assigned to it? Second, how do you compute ...
7k views

### Assumption of equal size of clusters in clustering

I am wondering: when clustering data using some general algorithm is there is an assumption on approximately equal sizes of the clusters? For example, in k-means as I know all clusters should have ...
2k views

### In cluster analysis should I scale (standardize) my data if variables are in the same units?

I am performing cluster analysis (k-means and hierarchical) based on multiple variables. Each variable is in percentage 0-100% and the sum of all variables is at most 100%. I see that in many of the ...
2k views

### Correlated variables in kmeans clustering

I have a dataset with 3 variables: A, B and C. Now, A and B are ordinal variables (i.e.; the result of two questions measured using a 5-point Likert), whereas B is continuous. A and B are also ...
97k views

### What are the main differences between K-means and K-nearest neighbours?

I know that k-means is unsupervised and is used for clustering etc and that k-NN is supervised. But I wanted to know concrete differences between the two?
42k views

### Clustering a dataset with both discrete and continuous variables

I have a dataset X which has 10 dimensions, 4 of which are discrete values. In fact, those 4 discrete variables are ordinal, i.e. a higher value implies a higher/better semantic. 2 of these discrete ...
69k views

### Is it important to scale data before clustering?

I found this tutorial, which suggests that you should run the scale function on features before clustering (I believe that it converts data to z-scores). I'm wondering whether that is necessary. I'm ...
24k views

### Why doesn't k-means give the global minimum?

I read that the k-means algorithm only converges to a local minimum and not to a global minimum. Why is this? I can logically think of how initialization could affect the final clustering and there is ...
5k views

### Does Dimensionality curse effect some models more than others?

The places I have been reading about dimensionality curse explain it in conjunction to kNN primarily, and linear models in general. I regularly see top rankers in Kaggle using thousands of features on ...
22k views

### usefulness of k-means clustering on high dimensional data [duplicate]

I wonder what is the usefulness of k-means clustering in high dimensional spaces, and why it can be better (or not) than other clustering methods when dealing with high dimensional spaces.
19k views

### k-means vs k-median?

I know there is k-means clustering algorithm and k-median. One that uses the mean as the center of the cluster and the other uses the median. My question is: when/where to use which?
42k views

### An example where the output of the k-medoid algorithm is different than the output of the k-means algorithm

I understand the difference between k medoid and k means. But can you give me an example with a small data set where the k medoid output is different from k means output.
60k views

### Calculate P value for the correlation coefficient

I would like to understand how people add the P value on a figure for means (Y axis) by age, volume or any other variable (x axis). How did they calculate the P value here? Please check the following ...
4k views

### Using k-means with other metrics

So I realize this has been asked before: e.g. What are the use cases related to cluster analysis of different distance metrics? but I've found the answers somewhat contradictory to what is suggested ...
### K-means as a limit case of EM algorithm for Gaussian mixtures with covariances $\epsilon^2 I$ going to $0$
My goal is to see that K-means algorithm is in fact Expectation-Maximization algorithm for Gaussian mixtures in which all components have covariance $\sigma^2 I$ in the limit as $\lim_{\sigma \to 0}$. ...