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
377
votes
5answers
124k 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 ...
94
votes
5answers
98k 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?
90
votes
7answers
51k 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 ...
83
votes
6answers
61k 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, ...
80
votes
3answers
167k 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 ...
68
votes
5answers
70k 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)...
67
votes
6answers
97k 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
75k 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. ...
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 ...
48
votes
5answers
72k 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 ...
46
votes
2answers
52k views

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

What are the best (recommended) pre-processing steps before performing k-means?
34
votes
3answers
59k 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 (...
34
votes
5answers
43k 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 ...
33
votes
1answer
41k 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 ...
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-...
28
votes
1answer
22k views

Difference between standard and spherical k-means algorithms

I would like to understand, what is the major implementation difference between standard and spherical k-means clustering algorithms. In each step, k-means computes distances between element vectors ...
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$.) ...
25
votes
4answers
49k 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 ...
24
votes
2answers
20k 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 ...
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 ...
22
votes
4answers
22k views

Clustering a correlation matrix

I have a correlation matrix which states how every item is correlated to the other item. Hence for a N items, I already have a N*N correlation matrix. Using this correlation matrix how do I cluster ...
21
votes
3answers
26k 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
3answers
20k 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 ...
20
votes
2answers
28k 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....
20
votes
3answers
24k views

Visually plotting multi dimensional cluster data

I have a data set with 16 variables, and after clustering by kmeans, I wish to plot the two groups. What plots do you suggest to visually represent the two clusters?
19
votes
4answers
20k views

How to understand the drawbacks of Hierarchical Clustering?

Can someone explain the pros and cons of Hierarchical Clustering? Does Hierarchical Clustering have the same drawbacks as K means? What are the advantages of Hierarchical Clustering over K means? ...
17
votes
5answers
25k 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
6k 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 ...
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?
14
votes
4answers
29k 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 ...
14
votes
3answers
14k views

Appropriateness of ANOVA after k-means cluster analysis

The notification after the ANOVA table after K-means analysis indicates that significance levels should not be looked at as the test of equal means, as the cluster solution has been derived based on ...
14
votes
2answers
20k 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?
14
votes
3answers
34k views

Why do we use k-means instead of other algorithms?

I researched about k-means and these are what I got: k-means is one of the simplest algorithm which uses unsupervised learning method to solve known clustering issues. It works really well with large ...
14
votes
3answers
13k views

Do I need to drop variables that are correlated/collinear before running kmeans?

I am running kmeans to identify clusters of customers. I have approximately 100 variables to identify clusters. Each of these variables represent the % of spend by a customer on a category. So, if I ...
14
votes
2answers
16k views

Is there a function in R that takes the centers of clusters that were found and assigns clusters to a new data set

I have two parts of a multidimensional data set, let's call them train and test. And I want to built a model based on the train ...
14
votes
2answers
4k views

Why isn't k-means optimized using gradient descent?

I know k-means is usually optimized using Expectation Maximization. However we could optimize its loss function the same way we optimize any other! I found some papers that actually use stochastic ...
13
votes
5answers
12k views

How I can convert distance (Euclidean) to similarity score

I am using $k$ means clustering to cluster speaker voices. When I compare an utterance with clustered speaker data I get (Euclidean distance-based) average distortion. This distance can be in range of ...
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 ...
13
votes
2answers
24k 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 ...
13
votes
4answers
9k views

What do you do when there's no elbow point for kmeans clustering

I've learned that when choosing a number of clusters, you should look for an elbow point for different values of K. I've plotted the values of withinss for values of k from 1 to 10, but I'm not seeing ...
13
votes
3answers
9k views

Clustering probability distributions - methods & metrics?

I have some data points, each containing 5 vectors of agglomerated discrete results, each vector's results generated by a different distribution, (the specific kind of which I am not sure, my best ...
12
votes
2answers
45k views

Interpreting result of k-means clustering in R

I was using the kmeans instruction of R for performing the k-means algorithm on Anderson's iris dataset. I have a question about some parameters that I got. The ...
12
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.
12
votes
1answer
5k views

k-means|| a.k.a. Scalable K-Means++

Bahman Bahmani et al. introduced k-means||, which is a faster version of k-means++. This algorithm is taken from page 4 of their paper, Bahmani, B., Moseley, B., Vattani, A., Kumar, R., & ...
11
votes
1answer
17k views

Cosine Distance as Similarity Measure in KMeans [duplicate]

I am currently solving a problem where I have to use Cosine distance as the similarity measure for k-means clustering. However, the standard k-means clustering package (from Sklearn package) uses ...
11
votes
4answers
1k views

Are there cases where there is no optimal k in k-means?

This has been inside my mind for at least a few hours. I was trying to find an optimal k for the output from the k-means algorithm (with a cosine similarity metric) so I ended up plotting the ...
11
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 ...
11
votes
3answers
9k views

What algorithm should I use to cluster a huge binary dataset into few categories?

I have a large (650K rows * 62 columns) matrix of binary data (0-1 entries only). The matrix is mostly sparse: about 8% is filled. I would like to cluster it into 5 groups - say named from 1 to 5. I ...
10
votes
3answers
43k 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.
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 ...

1
2 3 4 5
18