Find the number of clusters in huge unlabeled ECG time series data set We are a project group working with ECG and we could use theoretical approval of our approach to deal with the problem.
Our present approach is to cluster the ECG's, validate the formed clusters by cluster validity indexes and then compare each cluster with the features of the diagnosis attached to the ECG's to try to find correlation.
We have 50.000 ECG's each with 8 median leads (representative median complex with noise reduction where each lead are time aligned) with 600 samples for each lead.
Our approach is to use state-of-the-art shape-based clustering algorithms and evaluate them in relation to CVI and correlation with diagnosis features.
For algorithms to evaluate we will use:


*

*k-Shape     

*Fuzzy c-Shape

*Baseline: Hierarchical clustering with Euclidean distance as metric
and computed for both average linkage and ward.


For Internal CVI (Since we do not have any unlabeled ECG's):


*

*Silhouette index

*Calinski-Harabasz index

*Davies-Bouldin index

*(S_Dbw validity index)


Our current problem and where we especially would like some feedback is to find a window of k to run the two algorithms within. The time complexity of silhouette index do not allow us to try k with 1-50.000. 
We have talked about a window of running k with 5-200 but we do not have theory to back this window up. An approach to find a window could be to reduce the dimension of each ECG leads using PAA, run k-Shape from 1-50.000 on this reduced data set, find a window of interesting k's and the run the two algorithms on the full ECG samples.
We would really appreciate feedback on our current approach and a point in the right direction if you think there are cleverer ways to achieve our goal.
 A: PAA might not be a good choice to perform dimensionality reduction for k-Shape as PAA cannot capture the necessary "shape-based" properties (i.e., scale- and shift-invariances). 
I have developed a method to estimate k, the number of clusters, and, subsequently, to pick appropriate k samples as seeding for k-Shape, without the need to run the algorithm for k=1 to 50k or compute full dissimilarity matrixes. The approach is currently under double-blind reviewing so I cannot share details in public, but if you need it urgently, get in touch. (As an example, it can estimate k and pick k samples from 1M time series in less than 3 hours.)
A: Hmm "PAA might not be a good choice to perform dimensionality reduction for k-Shape as PAA cannot capture the necessary "shape-based" properties (i.e., scale- and shift-invariances)." I am not sure that is true, scale-invariance you can get from simply z-normalizing the data.   You can get shift-invariance doing cross correlation on the PAA.

In any case, this is a bit of a red herring. You can cluster such data without ANY dimensionality reduction.
ECGs typically have "warping", you will find DTW works well, especially endpoint invariant DTW.
