20
$\begingroup$

I have a dataset, I want to create clusters on that data based on only one variable (there are no missing values). I want to create 3 clusters based on that one variable.

Which clustering algorithm to use, k-means, EM, DBSCAN etc.?

My main question is, in what circumstances should I use k-means over EM or EM over k-means?

$\endgroup$
7
  • 1
    $\begingroup$ The EM algorithm is a general purpose tool for doing maximum likelihood estimation with missing data - can you be more specific about how it is a "clustering algorithm"? $\endgroup$ – Macro Aug 3 '11 at 2:42
  • $\begingroup$ I am using weka as a tool, and under clustering algorithm, EM is listed as an algorithm. I am sorry for lame question, I am new to data-mining. $\endgroup$ – Ali Aug 3 '11 at 2:44
  • $\begingroup$ I know the EM algorithm is used to do maximum likelihood estimation for latent variable models (which can be thought of as "missing data") and latent variables are often used to model clustering. Perhaps this is what is meant. $\endgroup$ – Macro Aug 3 '11 at 2:49
  • $\begingroup$ @macro: you may wanna have a look here: stat.washington.edu/mclust for a start. $\endgroup$ – user603 Aug 3 '11 at 7:16
  • 3
    $\begingroup$ What is the purpose of the clustering? As with most statistical questions, there are multiple answers and knowing the purpose is an essential guide to selecting appropriate or good ones. $\endgroup$ – whuber Aug 3 '11 at 14:22
12
$\begingroup$

The K-means algorithm and the EM algorithm are going to be pretty similar for 1D clustering.

In K-means you start with a guess where the means are and assign each point to the cluster with the closest mean, then you recompute the means (and variances) based on current assignments of points, then update the assigment of points, then update the means ...

In EM you would also start with a guess where the means are, then you compute the expected value of the assignments (essentially the probability of each point being in each cluster), then you update the estimated means (and variances) using the expected values as weights, then compute new expected values, then compute new means, ...

The primary difference is that the assignment of points to clusters in K-means is an all or nothing, where EM gives proportions/probability of group membership (one point may be seen as having 80% probability of being in group A, 18% probability of being in group B, and 2% probability of being in group C). If there is a lot of seperation between the groups then the 2 methods are going to give pretty similar results. But if there is a fair amount of overlap then the EM will probably give more meaningful results (even more if the variance/standard deviation is of interest). But if all you care about is assigning group membership without caring about the parameters, then K-means is probably simpler.

Why not do both and see how different the answers are? if they are similar then go with the simpler one, if they are different then decide on comparing the grouping to the data and outside knowledge.

$\endgroup$
2
  • $\begingroup$ Thanks greg your post helped, I applied both and it appears that EM generated better clusters than k-mean. (I think its mainly because the data I have is continuous and there are no gaps). I am little confused, since I only have 1D data, then I should probably do binning to categorize the data. What do you think? What exactly do you mean by parameters? Does it refer to attributes of an instance? Thanks Ali $\endgroup$ – Ali Aug 3 '11 at 23:00
  • $\begingroup$ Hm EM alone seems to be insufficient. You need an assumption on the distribution of the underlying distributions of the mixture. $\endgroup$ – tomka Oct 4 '17 at 12:35
3
$\begingroup$

EM is better than k-means in terms of results.

K-means, however, has a faster run-time.

They will produce similar results if the standard deviation/covariance matrices are approximately equal. If you suspect this is true, use k-means.

DBSCAN is used when the data is non-gaussian. If you are using 1-dimensional data, this is generally not applicable, as a gaussian approximation is typically valid in 1 dimension.

$\endgroup$
0
$\begingroup$

Another simple way is to basically use sorting of the 1D array: i.e. iterate over each point and get the values which are at a minimum distance from it in both the positive and the negative directions. For example:

data = [1,2,3,4,5,6,7,8,9,10,12]
k = 5
for a in data:
   print {'group': sorted(k, key=lambda n: abs(n-a))[0:k], 'point': a}

will give out:

{'group': [1, 2, 3, 4, 5], 'point': 1}
{'group': [2, 1, 3, 4, 5], 'point': 2}
{'group': [3, 2, 4, 1, 5], 'point': 3}
{'group': [4, 3, 5, 2, 6], 'point': 4}
{'group': [5, 4, 6, 3, 7], 'point': 5}
{'group': [6, 5, 7, 4, 8], 'point': 6}
{'group': [7, 6, 8, 5, 9], 'point': 7}
{'group': [8, 7, 9, 6, 10], 'point': 8}
{'group': [9, 8, 10, 7, 6], 'point': 9}
{'group': [10, 9, 8, 12, 7], 'point': 10}
{'group': [12, 10, 9, 8, 7], 'point': 12}

Which points, that the items close to a particular point are basically under its group. The only thing to ponder upon in this technique is the variable k, which is the fixed size of the cluster :-).

$\endgroup$
-2
$\begingroup$

If there is only one variable, no need for clustering. You can easily group your observations based on the variable's distribution.

Or am I missing some points here?

$\endgroup$
4
  • 5
    $\begingroup$ Can you give a specific example of how to group observations based on the variable's distribution? $\endgroup$ – Ali Aug 3 '11 at 13:07
  • $\begingroup$ @composer314: with an histogram? $\endgroup$ – nico Aug 3 '11 at 16:07
  • 1
    $\begingroup$ I'm sorry, but I'm still not following. How can I use a histogram to group related observations? (I guess the question I may be asking is really how does one find clumps within a histogram? Would this be similar to spectral peak picking?) $\endgroup$ – Ali Aug 3 '11 at 16:58
  • 7
    $\begingroup$ @composer Using the histogram or even a kernel smooth of the data is usually not an "easy" way to cluster. If you want to go this way, you need to fit a finite mixture model. If you just want what a casual view of a histogram might suggest, use K-means (also known as Jenks' method, popular among cartographers). $\endgroup$ – whuber Aug 3 '11 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.