Beyond Hartigan Consistency: Merge Distortion Metric for Hierarchical Clustering

Published on 2015-08-201675 Views

Hierarchical clustering is a popular method for analyzing data, which associates a tree to a dataset. Hartigan consistency has been used extensively as a framework to analyze such clustering algorithm

COLT 2015 - Paris

Presentation

Beyond Hartigan Consistency00:00

The goal of clustering02:01:08

In this talk ...08:22:00

What structure do we wish to recover?54:27:09

High-density clusters - 161:34:24

High-density clusters - 271:03:52

High-density clusters - 372:14:30

High-density clusters - 473:37:06

A hierarchy of clusters 77:20:48

The density cluster tree80:54:13

What structure do we wish to recover?89:14:48

Recovering the density cluster tree from data - 192:31:45

Recovering the density cluster tree from data - 2100:14:48

Recovering the density cluster tree from data - 3103:30:29

Recovering the density cluster tree from data - 4107:45:43

Recovering the density cluster tree from data - 5113:34:00

Recovering the density cluster tree from data - 6118:31:23

Recovering the density cluster tree from data - 7126:17:33

Recovering the density cluster tree from data - 8129:07:14

Recovering the density cluster tree from data - 9133:35:50

Recovering the density cluster tree from data - 10134:19:55

What properties ensure that an algorithm captures the density cluster tree?135:33:15

Hartigan Consistency -1146:06:25

Hartigan Consistency - 2149:53:36

Hartigan Consistency - 3155:57:21

Hartigan Consistency - 4156:51:56

Hartigan Consistency - 5157:56:43

Hartigan Consistency - 6159:00:24

Hartigan Consistency - 7162:10:23

Hartigan Consistency - 8163:30:20

Hartigan Consistency - 9163:59:21

Hartigan Consistency - 10164:18:41

Hartigan Consistency - 11164:40:23

Hartigan Consistency - 12167:05:40

Hartigan Consistency - 13167:59:17

Hartigan Consistency - 14169:41:38

Hartigan Consistency - 15170:53:37

What properties ensure that an algorithm captures the density cluster tree? - 1172:42:11

Hartigan Consistency is insufficient - 1193:16:41

Hartigan Consistency is insufficient - 2199:54:33

Hartigan Consistency is insufficient - 3200:45:01

Hartigan Consistency is insufficient - 4201:01:40

Hartigan Consistency is insufficient - 5203:40:24

Hartigan Consistency is insufficient - 6204:05:23

Hartigan Consistency is insufficient - 7208:44:59

Hartigan Consistency is insufficient - 8209:37:23

Hartigan Consistency is insufficient - 9211:31:58

Hartigan Consistency is insufficient - 10213:04:38

Hartigan Consistency is insufficient - 11215:50:06

Beyond Hartigan consistency218:50:37

Minimality - 1229:38:55

Minimality - 2235:05:54

Minimality - 3243:51:48

Minimality - 4244:18:30

Minimality - 5244:54:52

Separation - 1248:33:54

Separation - 2254:20:33

Separation - 3254:54:14

Separation - 4255:26:55

Separation - 5255:54:35

What properties ensure that an algorithm captures the density cluster tree? - 2262:26:39

Ideal and empirical merge height - 1270:32:55

Ideal and empirical merge height - 2275:11:57

Ideal and empirical merge height - 3276:48:43

Ideal and empirical merge height - 4277:04:35

Ideal and empirical merge height - 5277:23:20

Ideal and empirical merge height - 6279:35:32

Ideal and empirical merge height - 7279:56:29

Ideal and empirical merge height - 8280:29:56

Ideal and empirical merge height - 9281:19:17

Ideal and empirical merge height - 10282:56:37

Theorem289:35:13

Minimality, separation and the merge distortion metric292:32:14

Convergence of robust single linkage298:51:23

Future work307:27:21

Summary - 1309:20:20

Summary - 2309:54:05

Thank you315:19:05