# Metric and Clustering Method

I need some suggestions regarding what kind of metric and clustering analysis I should use. I read a lot of posts but didn't get any hints about this type of data.

I have a 3000*5000 matrix, where 3000 is signals from various different sources and 5000 is time point from 0 to 5000 seconds. for example: a signal intensity from a source looks like:

0 0 0 0 0 0 0 0 0 2.3 3.2 4.5 6.5 4.2 3.5 2.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... and so on

indicating "0" for no signal and a positive rational number for a signal intensity at a particular second. I am interested in capturing similar patterns rather intensity values i.e. having spikes/intensity > 0 at a similar time point.

I tried using sq. Euclidean metric and then performed MDS (multi-dimensional scaling) on the distance matrix. When I plotted the graph, I don't discern any similar patterns. I did K-means (k = 3-12 clusters) with the Euclidean metric and tried comparing the signals between the two sources but I didn't get similar patterns between them.

What type of metric and clustering algorithm should I use? Would you recommend to me 1-cor metric?

• Are your patterns global or local in time, i.e. if you have a flat signal with triangular spike at 10s, you would call it similar to a flat signal with rectangular spike at 10s or to a signal with exactly the same triangular spike at 500s? – user88 Oct 4 '12 at 9:25

It looks like you are analyzing time series.

Try to use a distance function designed for time series, that e.g. allows slight differences in the exact beginning (i.e. at spikes at slightly different time points). And that scales better with dimensionality...

Euclidean distance is not a very good choice for high-dimensional data, and this probably also kills k-means for you (it also expects you to use Euclidean distance!). Similarly, dimension-reduction techniques will often not work well, because you have too many dimensions for too few objects. PCA for example has d^2 degrees of freedom - with fewer objects than say 3*d*d you cannot expect good results, but it will overfit the dimensionality reduction.

Just an example why Euclidean (or actually any LP norm) will not work for you. Consider the vectors:

0 0 0 1 1 0 0 0 0 0 ... 0 0 0 1 1 0 0
0 1 1 0 0 0 0 0 0 0 ... 0 1 1 0 0 0 0


These two vectors are about as different as they get for euclidean distance. A time-warping distance function however should recognize that with a shift of 2 it can align them perfectly.

Once you have found a distance measure that work for your dataset (note, this depends heavily on the dataset. Measures that work with one may fail badly on the others. Sometimes you need to go into the frequency domain and use completely different measures, too!), you can try MDS and/or Clustering. There are various clustering algorithms available that are "density" based (where density is defined via distance, usually!)

Check out this survey paper [1]. This survey is somewhat older but hopefully will get you an idea of basic approaches tried prior to 2005. You possibly might want to explore some of the recent papers like this one [2].

[1] Clustering of time series data : a survey
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.6594
[2] Time Series Clustering: Complex is Simpler!
http://mldiscuss.appspot.com/venue/ICML/2011/article/159/

For the problem you describe, I'd use a cross-correlation instead a cluster analysis.
I used to do something similar in the past in matlab, using the xcorr function.
Of course, the details for this approach will depend on the length of the patterns you want to find in your vectors.
Another approach I tried was Gibbs sampling, however it is also time consuming and I wasn't very happy with the results obtained... but you can give it a try anyway.

Edit:
I kept thinking a little bit about the problem... it seemed to me plausible to use the cross-correlation results for further cluster analysis so I googled the two terms and found there are some papers on the topic, like this one.
Basically, you can use the cross-correlation as a metric for being used in fuzzy clustering.
Very interesting and promising, at least from my point of view.

• Thanks a lot.. the paper/work looks promising.. I appreciate your help !! – snape Oct 5 '12 at 4:30
• Hi Diego, I went through the paper but I didn't understand the calculation of cross correlation distance metric ? Could you please explain it. Thanks. – snape Oct 9 '12 at 1:52
• I don't really understand your question. The calculation of that "metric" is just the Pearson's correlation coefficient. – Diego Oct 9 '12 at 3:23
• I went through the paper that you have attached to the post. When I am calculating the cross-correlation for two different signals then it produces a vector of 2*N-1 coefficients(which is same as Pearson's correlation for every point -- equation 9, lets call it as Cross-Correlation Vector). Now, when I am calculating the distance then Cross-Correlation Distance = 1-max(Cross-Correlation Vector)[equation 10]. I don't understand this step. Technically, the distance should be between 0 and 2 (as in the case of Pearson distance). But my values don't lie between 0 and 2. I used xcorr function. – snape Oct 9 '12 at 10:42
• r = -1 to 1 NOT 0 to 2. xcorr does not normalize the values as Pearson does so they are expected to produce different results. The paper uses Pearson. I prefer xcorr. – Diego Oct 9 '12 at 18:19