sneighborhood Graph 。e-neighborhood Compute pairwise distance between any two objects Connect each point to all other points which have distance smaller than a threshold s Weighted or unweighted Unweighted-There is an edge if one point belongs to the &-neighborhood of another point Weighted-Transform distance to similarity and use similarity as edge weights 6
ε-neighborhood Graph • ε-neighborhood – Compute pairwise distance between any two objects – Connect each point to all other points which have distance smaller than a threshold ε • Weighted or unweighted – Unweighted—There is an edge if one point belongs to the ε–neighborhood of another point – Weighted—Transform distance to similarity and use similarity as edge weights 6
KNN Graph ·Directed graph Connect each point to its k nearest neighbors ·kNN graph Undirected graph An edge between x;and x;:There's an edge from x;to X;OR from x;to x;in the directed graph 。Mutual kNN graph Undirected graph Edge set is a subset of that in the kNN graph An edge between x;and x;:There's an edge from x;to X;AND from x;to x;in the directed graph 7
kNN Graph • Directed graph – Connect each point to its k nearest neighbors • kNN graph – Undirected graph – An edge between xi and xj : There’s an edge from xi to xj OR from xj to xi in the directed graph • Mutual kNN graph – Undirected graph – Edge set is a subset of that in the kNN graph – An edge between xi and xj : There’s an edge from xi to xj AND from xj to xi in the directed graph 7
Data points epsilon-graph,epsilon=0.3 -1 -1 米 米 米 米 米 -2 -2 米 米 -3 米 米 米 -3 0 1 2 0 1 2 kNN graph,k =5 Mutual kNN graph,k =5 米 2 -3 -3 2 1 2 3
8
Clustering Objective Traditional definition of a "good"clustering Points assigned to same cluster should be highly similar Points assigned to different clusters should be highly dissimilar Apply this objective to our graph representation 0.1 0.8 0.8 0.8 0.6 6 0.7 0.8 0.2 Minimize weight of between-group connections 9
Clustering Objective Traditional definition of a “good” clustering • Points assigned to same cluster should be highly similar • Points assigned to different clusters should be highly dissimilar Minimize weight of between-group connections 0.1 0.2 0.8 0.7 0.6 0.8 0.8 0.8 1 2 3 4 5 6 Apply this objective to our graph representation 9
Graph Cuts Express clustering objective as a function of the edge cut of the partition Cut:Sum of weights of edges with only one vertex in each group We wants to find the minimal cut between groups C2 cut(C1,C2）=∑w C ieCl,jEC2 0.1 0.8 0.8 0.8 0.6 6 cut(C1,C2)=0.3 2 0.7 0.8 0.2 10
Graph Cuts • Express clustering objective as a function of the edge cut of the partition • Cut: Sum of weights of edges with only one vertex in each group • We wants to find the minimal cut between groups 1 2 , 1 2 ( , ) i C j C C C wij cut 0.1 0.2 0.8 0.7 0.6 0.8 0.8 1 2 3 4 5 6 0.8 cut(C1 , C2 ) = 0.3 10 C1 C2