35
$\begingroup$

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 range from 0 bytes to 2 tera bytes. I would like to cluster the nbytes such that given k clusters some x1 transfers belongs to k1 cluster, x2 transfters to k2 etc.

From the terminology that I used you might have guessed what I was going with: K-means. This is 1d data since nbytes is the only feature I care about. When I was searching for different methods to this I saw the EM was mentioned a couple times along with a non-clustering approach. I would like to know about your views on how to approach this problem (specifically whether to cluster or not to cluster).

Thanks!

Improve this question
$\endgroup$
7
  • $\begingroup$ What are "x1 transfers", "x2 transfers" etc.? Is "transfer type" a second variable? $\endgroup$ – Peter Flom Oct 15 '12 at 15:02
  • $\begingroup$ x1 transfers is just a way for me to say that these 500 transfers had transfer size around the some value (this would be the mean for that cluster in k-means). $\endgroup$ – Shaun Oct 15 '12 at 15:05
  • 6
    $\begingroup$ I'm not an expert on clustering, but w/ so much data & just 1 dimension, I wonder if you could just make some kernel density plots using different bandwidths and see how many modes / peaks you find, & whether the result seems like it would be useful for you. $\endgroup$ – gung - Reinstate Monica Oct 15 '12 at 15:05
  • 1
    $\begingroup$ You asked whether to cluster or not. What would be your goal from clustering? Would you use the clusters for some other purpose, or is this of theoretical interest? $\endgroup$ – Peter Flom Oct 15 '12 at 15:11
  • $\begingroup$ Some of the other attributes from the table are username, start and end dates. My hope is by clustering the transfers based on transfer size, I can then refer to other attributes of a particular transfer to see who is transferring how much at what month of the year. What we will do with this observation, I don't know yet. But that's kind of where I am going. $\endgroup$ – Shaun Oct 15 '12 at 15:16
58
$\begingroup$

In one dimensional data, don't use cluster analysis.

Cluster analysis is usually a multivariate technique. Or let me better put it the other way around: for one-dimensional data -- which is completely ordered -- there are much better techniques. Using k-means and similar techniques here is a total waste, unless you put in enough effort to actually optimize them for the 1-d case.

Just to give you an example: for k-means it is common to use k random objects as initial seeds. For one dimensional data, it's fairly easy to do better by just using the appropriate quantiles (1/2k, 3/2k, 5/2k etc.), after sorting the data once, and then optimize from this starting point. However, 2D data cannot be sorted completely. And in a grid, there likely will be empty cells.

I also wouldn't call it cluster. I would call it interval. What you really want to do is to optimize the interval borders. If you do k-means, it will test for each object if it should be moved to another cluster. That does not make sense in 1D: only the objects at the interval borders need to be checked. That obviously is much faster, as there are only ~2k objects there. If they do not already prefer other intervals, more central objects will not either.

You may want to look into techniques such as Jenks Natural Breaks optimization, for example.

Or you can do a kernel density estimation and look for local minima of the density to split there. The nice thing is that you do not need to specify k for this!

See this answer for an example how to do this in Python (green markers are the cluster modes; red markers a points where the data is cut; the y axis is a log-likelihood of the density):

KDE with Python

P.S. please use the search function. Here are some questions on 1-d data clustering that you missed:

Improve this answer
$\endgroup$
8
  • $\begingroup$ Quantiles don't necessarily agree with clusters. A 1d distribution can have 3 natural clusters where two hold 10% of the data each and the last one contains 80% of the data. So I think it is possible to cluster here, although I agree it makes sense to optimize the run by picking seeds smartly etc. or using other ideas. $\endgroup$ – Bitwise Oct 16 '12 at 0:32
  • $\begingroup$ The quantiles are probably good seed points for optimizing, that was what I was referring to. And just to give an example of what you can do in 1D that doesn't work that well in 2+ dimensions. $\endgroup$ – Has QUIT--Anony-Mousse Oct 16 '12 at 0:50
  • 1
    $\begingroup$ Oh, and k-means does unnecessary checks on 1d data, since it does not exploit convexity. I've updated my answer with how to do a much faster 1d-kmeans by looking only at elements close to the interval borders. But that will then likely boil down to Jenks or a similar method. After all, there are millions of algorithms for 1d data. $\endgroup$ – Has QUIT--Anony-Mousse Oct 16 '12 at 16:11
  • 5
    $\begingroup$ Jenks is k-means in 1D. $\endgroup$ – whuber♦ Feb 2 '13 at 22:46
  • 2
    $\begingroup$ @whuber even if it mathematically is, I hope he was smart enough to exploit that the data can be ordered. If you use the Lloyd approach for doing k-means on 1-d data, you are stupid, because you are doing a lot of computations that you could skip. And to most people, k-means is Lloyd. And some people do care about avoiding unnecessary recomputations. $\endgroup$ – Has QUIT--Anony-Mousse Feb 2 '13 at 22:49
5
$\begingroup$

One-dimensional clustering can be done optimally and efficiently, which may be able to give you insight on the structure of your data.

In the one-dimensional case, there are methods that are optimal and efficient (O(kn)), and as a bonus there are even regularized clustering algorithms that will let you automatically select the number of clusters! I recommend this survey: https://cs.au.dk/~larsen/papers/1dkmeans.pdf R implementations can be found on the Ckmeans.1d.dp package: https://cran.r-project.org/web/packages/Ckmeans.1d.dp/index.html

As a side note, 1-dimensional clustering can be used for quantization, where you represent your input data using a smaller set of values; this can help with compression, or to speed up searching for example.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This space is intended for answering this question 7 not discussing another. $\endgroup$ – Michael R. Chernick Dec 18 '19 at 23:07
1
$\begingroup$

Is your question whether you should cluster or what method you should use to cluster?

Regarding whether you should cluster, it depends if you want to automatically partition your data (for example if you want to repeat this partitioning several times). If you are doing this only once, you can just look at the histogram of the distribution of your values, and partition it by eye, as proposed in the comments. I would recommend looking at the data by eye anyway, since it could help you determine how many clusters you want and also whether the clustering "worked".

Regarding the type of clustering, k-means should be fine if there are "real" clusters in the data. If you don't see any clusters in the histogram, it doesn't make much sense clustering it anyway, since any partitioning of your data range will give valid clusters (or in the case of random initiation of kmeans, you will get different clusters each run).

Improve this answer
$\endgroup$
1
$\begingroup$

You can try:

  1. KMeans, GMM or other methods by specifying n_clusters= no. of peaks in kernel density plot.

  2. KMeans, GMM or other methods by determining the optimum no. of clusters based on some metrics. More info: [here] https://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set

Improve this answer
$\endgroup$

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.