3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Try the Simplified Silhouette Index, which only needs O(nk) instead of O(n²) time, by using only the distances from the mean / median each. $\endgroup$
    – Has QUIT--Anony-Mousse
    Oct 23, 2017 at 6:27
  • $\begingroup$ Cluster analysis is by definition an exploratory, even heuristic, to an extent, technique. In this stance, nobody will want to "find" many clusters, say, 30 or 50. We do clustering to find a structure easy to apprehend and interpret, typically in the range of 2-15 or so clusters. So, the window of solutions, to plot the validity index and appreciate the line, is typically k 2 through 20 in practice. Note that local peaks and elbows are more important about those indices than their general max (or min). $\endgroup$
    – ttnphns
    Oct 24, 2017 at 5:23
  • $\begingroup$ Given that your goal is to relate the clusters to the diagnoses, is there any point in having the number of clusters be much larger (or much smaller) than the number of diagnoses? I am no cardiologist, but it does not seem intuitive to me that there should be really distinct groups that get the same diagnosis. Therefore, the number of diagnoses should give the order of magnitude of the number of clusters. $\endgroup$
    – G5W
    Nov 17, 2017 at 17:19

2 Answers 2

Reset to default
1
$\begingroup$

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.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the answer John. We are trying a new direction by reducing the numbers of leads for each ECG by applying PCA (Principal component analysis) / KLT (Karhunen-Loeve transform) to concentrate the information into fewer leads. Thereby trying to avoid reducing the dimension of the leads by PAA and still get a result within reasonable time. It sound really interesting! I will get in touch by mail. $\endgroup$
    – Morten Brodersen Jensen
    Oct 24, 2017 at 8:58
1
$\begingroup$

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.

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.