22Oct
2016
Eugene / Learning, MIT Data Science: Data To Insights / 0 comment
Clusters
Cluster: points that are well-connected with each other (lots of edges)
Number of edges = volume
Volume per node = density
Cut value: separation of clusters
Cut(C) = 1 (number of edges between clusters)
1st criteria: density must be large
2nd criteria: there should not be too many edges between different clusters
Normalised Cut
$\text{Ncut(C)}=\frac{\text{Cut(C)}}{\text{Volume(C)}\times \text{Volume(V\C)}}$
Conductance
$\text{conductance(C)}=\frac{\text{Cut(C)}}{\text{Min\{Volume(C),Volume(V\C)\}}}$
Good clusters are not too small, internally well-connected and separated from the rest of the nodes