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

Filter by
Sorted by
Tagged with
375
votes
5answers
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 ...
65
votes
6answers
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? ...
55
votes
11answers
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. ...
14
votes
4answers
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 ...
82
votes
6answers
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, ...
30
votes
2answers
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-...
87
votes
7answers
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 ...
14
votes
4answers
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?
45
votes
2answers
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?
7
votes
2answers
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 ...
10
votes
3answers
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 ...
19
votes
3answers
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 ...
8
votes
2answers
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 ...
65
votes
5answers
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)...
23
votes
8answers
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 ...
25
votes
4answers
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 ...
11
votes
2answers
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.
10
votes
2answers
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 ...
32
votes
1answer
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 ...
9
votes
1answer
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-...
27
votes
5answers
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$.) ...
80
votes
3answers
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 ...
21
votes
2answers
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 ...
4
votes
2answers
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" ...
1
vote
3answers
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 ...
6
votes
1answer
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 ...
51
votes
3answers
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 ...
32
votes
3answers
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 (...
13
votes
2answers
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 ...
19
votes
3answers
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?
20
votes
2answers
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....
13
votes
4answers
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 ...
6
votes
1answer
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 ...
3
votes
2answers
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 ...
3
votes
2answers
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 ...
8
votes
2answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
92
votes
5answers
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?
34
votes
5answers
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 ...
48
votes
6answers
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 ...
17
votes
5answers
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 ...
15
votes
1answer
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 ...
7
votes
1answer
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.
14
votes
2answers
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?
10
votes
3answers
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.
9
votes
1answer
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 ...
8
votes
3answers
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 ...
8
votes
1answer
3k views

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}$. ...
2
votes
2answers
4k views

Use of bootstrap in clustering algorithms

Are there clustering algorithms that take advantage of bootstrap? For example can one combine bootstrap with a standard K-Means algorithm to scale K-Means. I was thinking if the following at a high-...