# K means clustering inadequate in determining extreme regions in R

I want to identify the regions that are considerably higher than the highest cluster. (The obvious regions which should be identified as their own clusters, notably at the x coordinate ~10 e+07. How would I be able to identify that using a clustering algorithm?

I am using R algorithm kmeans in the picture above. with 6 centers:

kmeans(numbers_vector, centers=6, nstart=10)

What can I do to alleviate the inadequacy of this algorithm? Use a different clustering algorithm? Have more centers? But If I have more centers, it identifies many more regions in the center (namely clusters 3,5, and 6). Any ideas?

Here is histogram and density. It is important to note that the histogram and density plot DO NOT show the spike ~x=10e+07, because the number of points involved in the spike ~20, perhaps are completely overshadowed by the ~107,350 points plotted.

Data: x (88289 obs.); Bandwidth 'bw' = 0.7574

   x                 y


Min. : -1.272 Min. :0.000e+00
1st Qu.: 40.114 1st Qu.:4.110e-06
Median : 81.500 Median :3.167e-05
Mean : 81.500 Mean :6.035e-03
3rd Qu.:122.886 3rd Qu.:2.886e-03
Max. :164.272 Max. :4.827e-02

• Are these questions ever answered on stats.stackexchange.com, or will they just die if no one answers within an allotted period? Feel like SO provides a much faster response. – user41912 Jul 28 '14 at 20:43
• Isn't fifteen minutes a little soon to declare the question dead? – David Robinson Jul 28 '14 at 21:11
• In any case: this is not a good case for k-means clustering. K-means clustering is generally designed for when you have multiple clusters that are each approximately normally distributed (or multivariate normal) around a different center. Your y-axis points don't look like they fall into several clusters: rather, I would guess that they follow a very roughly normal distribution around about 60, with some outliers. This will be the key to looking for values that are outliers. Could you show a histogram of your numbers_vector? – David Robinson Jul 28 '14 at 21:14
• @David Robinson Yep, uploading it in 2 minutes after I generate in R. If you want the dataset, look at the comments I left to the answer provided to the question by Eric. – user41912 Jul 28 '14 at 21:24
• First, rather than looking and quantiles I would suggest considering the problem parametrically. The data looks rather close to normal with the exception of a group of outliers at 0. First remove those 0s, then find the mean and standard deviation. For choosing the number of sd's away from the mean that are "significant": you could use that distribution to compute a p-value for each point (probability you would see that extreme or more if it were actually normal). Then it would become a problem of multiple hypothesis testing to find which points are actually extreme given how many you have – David Robinson Jul 29 '14 at 3:28

K-means will partition to minimize variance.

The minimum variance parition does produce these slices.

Instead of using clustering, use density estimation. You have already plotted densities for your data. It's fairly obvious how to identify low density regions in the histogram (if you don't want to use bins, you can use kernel density estimation). The low values will also be separated from the majority of the data by a low density region.

The spike you are interested in is an area with really low density.

I.e. split your data set at a density minimum, and select data in areas with low density.

How would I be able to identify that using a clustering algorithm?

Assuming you want to identity outliers or where the groups break at (your question isn't exactly clear to me), I recommend plotting your data and then plotting your centers. This will plot your data points color coded by cluster and then plot the cluster centers over it.

c1<-kmeans(numbers_vector, centers=6, nstart=10)
plot(numbers_vector, col = cl1$cluster) points(cl1$centers, col = 11, pch = 8, cex = 2,lwd=5)


Without actual data, I can't be much more help.

I am using R algorithm kmeans in the picture above. with 6 centers:

The picture above appears not to have shown through. Can you provide your dataset?

What can I do to alleviate the inadequacy of this algorithm? Use a different clustering algorithm? Have more centers? But If I have more centers, it identifies many more regions in the center (namely clusters 3,5, and 6). Any ideas?

• The dataset I plan to upload to dropbox shortly as an .RData file. Simply download the file from dropbox and when you open R, use the command load(file_location), and then use head(df.add) to confirm the loading of the dataset. The x values are the start column and the y values are the Number_of_AID_OH column. Ignore all other columns. – user41912 Jul 28 '14 at 21:21