Pattern Recognition, 4th Edition

The Chameleon Algorithm

The algorithms CURE and ROCK, described previously, are based on “static” modeling of the clusters. Specifically, CURE models each cluster by the same number, k, of representatives, whereas ROCK poses constraints on the clusters through f(ϑ). Clearly, these algorithms may fail to unravel the clustering structure of the data set in cases where the individual clusters do not obey the adopted model, or when noise is present. In the sequel, another hierarchical clustering algorithm, known as Chameleon, is presented. The algorithm is capable of recovering clusters of various shapes and sizes.

To quantify the similarity between two clusters, we define the concepts of relative interconnectivity and relative closeness. Both ...