# Agglomerative Clustering Stopping Criteria

I am trying to implement section 3.4 of paper Predicting Important Objects for Egocentric Video Summarization where they have created a distance matrix of frame histograms.

In short, let say Ω is mean of distances between all frames,DVis distance matrix.

I didn't understand what is meant by this:

We next perform complete-link agglomerative clustering with DV , grouping frames until the smallest maximum interframe distance is larger than two standard deviations beyond Ω

Can this be achieved by setting the cutoff value to 2Ω in Matlab's clusterdata function ?

## 1 Answer

Clearly, 2 standard deviations beyond Omega is not the same as twice the mean.

Apparently, their process is this:

1. compute the distance matrix
2. compute the mean
3. compute the standard deviation
4. compute hierarchical clustering with maximum linkage
5. cut the tree at mu+2*sigma

Because complete linkage is in O(n^3), this approach will not scale to longer videos or higher frame rates.

• What did you mean by saying "Because complete linkage is in O(n^3), this approach will not scale to longer videos or higher frame rates." Does that mean I should not use complete linkage in long videos just for "performance" issues ? – Muhammet Ali Asan Oct 22 '15 at 20:31
• Yes, this approach will not scale to large data because it has cubic complexity. – Has QUIT--Anony-Mousse Oct 22 '15 at 21:00
• If you look at their paper, they decreased the framerate, and used only 680 frames on average (assuming they only used the annotated frames for clustering). At 24 fps, this would be less than 30 seconds of video. O(n^3) means that 10x as many frames will take 1000x as long. – Has QUIT--Anony-Mousse Oct 22 '15 at 21:30
• I think they took every 15th frame.I also did same thing and took every 15th frame this decreased the run time of my code. – Muhammet Ali Asan Oct 22 '15 at 21:35