4

We have a list of prices and need to find both the number of clusters (or intervals) and the mean price of each cluster (or interval). The only constraint is that we want cluster means to be at least X distance from each another.

K-means doesn't seem to work because it requires specifying the number of clusters as input.

The reason for finding these is that prices become a "significant" cluster with more data points serve as support and resistance levels for trading. Currently this process is done by simple human observation of clusters of prices on a chart. But the purpose here is to quantify this in an algorithm to make it more objective and measurable.

Nick Cox
  • 48,377
  • 8
  • 110
  • 156
Wayne
  • 141
  • 1
  • 1
  • 2
  • See http://stats.stackexchange.com/questions/67571/how-can-i-group-numerical-data-into-naturally-forming-brackets-e-g-income/ for a similar-sounding problem. The constraint that means differ by at least a certain amount should be satisfied by any classification of interest; trying to impose it via code is likely to be awkward at best and make your code much more difficult to write. It is not clear whether your problem is really one of looking for multiple modes in a distribution. – Nick Cox Dec 11 '13 at 11:39
  • @Nick Thanks for help with terminology. This is a problem of multiple modes in a distribution. The proposed constraint on minimum distance is an arbitrary idea to narrow the problem that can be dropped. What matters is finding the "modes" which we were calling clusters. – Wayne Dec 11 '13 at 15:30
  • @Nick, your reference only leads to a Stata coding example which is cryptic. I can read C, C++, C#, BASIC, Fortran, Java and other languages but never picked up Stata. I googled and can't find any other examples of this. – Wayne Dec 11 '13 at 15:31
  • Not so. What I said included this: "Hartigan (1975) showed how a dynamic programming approach makes such computation straightforward and presented Fortran code." Also, the Stata code is mostly Mata, which is very like C. With your skills, it should be fairly transparent. Hartigan's book should be in any decent library. – Nick Cox Dec 11 '13 at 15:50
  • If it's really multiple modes, consider in general kernel density estimation and finding peaks and in particular "mode trees". – Nick Cox Dec 11 '13 at 15:51

3 Answers3

3

Don't run clustering (such as k-means) on 1-dimensional data.

Why: 1-dimensional data can be sorted. Algorithms that exploit sorting are much more efficient than algorithms that do not exploit this.

Look at classic statistics

And forget about buzzwords such as "data mining" and "clustering"!

For your task, I recommend you use kernel density estimation. This is a well-proven technique from statistics, and very flexible. To cluster your data, look for maxima and minima in the density estimation to split your data. It's fast, and has a much stronger theoretical background than cluster analysis.

When to use cluster analysis

Essentially, use cluster analysis, when your data is so large and complex you cannot use classic statistical modeling anymore. When you have too many variables and too complex processes to model them. When density estimation no longer works. When you can no longer visualize the data.

Even in 2d data, don't do cluster analysis. Visualize your data, and manually mark your clusters. Methods such as k-means will produce a k-cluster result no matter what; even when there are no clusters in your data set! Because they blindly optimize some mathematical equation, without reality-checking it. If you manually cluster your data, your results will be much more meaningful.

Has QUIT--Anony-Mousse
  • 39,639
  • 7
  • 61
  • 96
  • 2
    I couldn't agree more with the general advice to visualize and for this problem the specific advice to consider density estimation. But saying that you shouldn't do cluster analysis in 1D or 2D is more than a trifle dogmatic. People often need or want clusters for scientific or practical reasons, even with 1D or 2D data. For example, if the science says there are clusters, then wanting to test that is a natural thing to do. Considering that there might be a continuum instead is also a natural thing to do. Comparing "automatic" with manual clusters is also a natural thing to do. – Nick Cox Dec 13 '13 at 09:23
2

The XMeans algorithm can be used to estimate the total number of clusters directly from the data, without human guidance. The Weka package has a Java implementation. An expectation maximization algorithm can also be used to automatically estimate the total number of clusters as well. There is a Weka implementation of that also. In addition, there is at least one individual contributor version (i.e., not sanctioned by mathworks.com) for performing Gaussian Mixture Model clustering in MATLAB also, if you prefer to do your analysis that way instead of in Java.

stachyra
  • 2,792
  • 11
  • 14
  • We're using C# but Java is a comfortable language for example code! Awesome. Will study it now. – Wayne Dec 11 '13 at 15:36
  • Well after reading alot about XMeans--it's exactly what we need. Amazingly, the XMeans isn't in subversion for Weka project. I requested the C source version from the university. We'll see if that comes. Still can't find a working example just PDF and tutorials. Any ideas? – Wayne Dec 11 '13 at 16:22
  • Yes it is in the repository. It's just that it's not in the "trunk" branch yet; it's off on a separate release branch; not sure why they did it that way. You can find the source code (Java, not C unfortunately) here: https://svn.cms.waikato.ac.nz/svn/weka/branches/stable-3-6/weka/src/main/java/weka/clusterers/XMeans.java . If you want a working demo example with it implemented in situ, check out my GitHub repository: https://github.com/stachyra/WekaSwingDemo . Also, if you found my answer "definitive", please remember to award it "best answer" status. – stachyra Dec 11 '13 at 17:58
2

You can just estimate the probability density function of price. If they are a mixture of normal distributions, hopefully you will observe several peaks in your mixture of Gaussian kernels. It can be implemented easily with Python, and I believe there are packages for other languages as well.

from scipy.stats import kde
import matplotlib.pyplot as plt     
density = kde.gaussian_kde(x) # x: list of price
xgrid = np.linspace(x.min(), x.max(), Num_Price)   
plt.plot(xgrid, density(xgrid))
plt.show()
lennon310
  • 2,582
  • 2
  • 21
  • 30