CHAMELEON clustering

Construct a weighted undirected k-nearest-neighbor graph by retaining an edge when either endpoint lists the other among its k most similar points. Obtain small initial subclusters by repeated balanced graph bisection, selecting the largest current subcluster; the report uses hMETIS with each child holding at least 25 percent of its parent and stops when the largest subcluster is below MINSIZE. For clusters A,B, relative interconnectivity RI is the total cross-edge weight divided by the mean of the two internal bisection-cut weights. Relative closeness RC is the mean cross-edge weight divided by the size-weighted mean of the two mean internal bisection-edge weights. One merge scheme maximizes RI(A,B)*RC(A,B)^alpha over pairs; this is the scheme used for the report’s dendrogram experiments. An alternative visits clusters and selects their most strongly connected eligible neighbor subject to separate RI and RC thresholds, permitting multiple merges per iteration and either stopping or relaxing thresholds when no pair qualifies.