Chameleon变色龙层次聚类算法

最经典的层次聚类算法,

Chameleon:HierarchicalClustering UsingDynamic Modeling

Many advanced algorithms have dif culty dealing with highly variable

clusters that do not follow a preconceived model. By basing its selectionson both interconnectivity and closeness, the Chameleon algorithm yieldsaccurate results for these highly variable clusters.

Cover Featur

e

GeorgeKarypisEui-Hong(Sam) HanVipin Kumar

University ofMinnesota

C

lustering is a discovery process in data min-ing.1It groups a set of data in a way thatmaximizes the similarity within clusters andminimizes the similarity between two dif-ferent clusters.1,2These discovered clusters

can help explain the characteristics of the underlyingdata distribution and serve as the foundation for otherdata mining and analysis techniques. Clustering is use-ful in characterizing customer groups based on pur-chasing patterns, categorizing Web documents,3grouping genes and proteins that have similar func-tionality,4grouping spatial locations prone to earth-quakes based on seismological data, and so on.

Most existing clustering algorithms find clustersthat t some static model. Although effective in somecases, these algorithms can break down—that is, clus-ter the data incorrectly—if the user doesn’t selectappropriate static-model parameters. Or sometimesthe model cannot adequately capture the clusters’characteristics. Most of these algorithms break downwhen the data contains clusters of diverse shapes, den-sities, and sizes.

Existing algorithms use a static model of the clustersand do not use information about the nature of indi-vidual clusters as they are merged. Furthermore, oneset of schemes (the CURE algorithm and relatedschemes) ignores the information about the aggregateinterconnectivityof items in two clusters. The otherset of schemes (the Rock algorithm, group averagingmethod, and related schemes) ignores informationabout the closeness of two clusters as de ned by thesimilarity of the closest items across two clusters. (Formore information, see the “Limitations of TraditionalClustering Algorithms” sidebar.)

By only considering either interconnectivity or close-ness, these algorithms can easily select and merge the

wrong pair of clusters. For instance, an algorithm thatfocuses only on the closeness of two clusters will incor-rectly merge the clusters in Figure 1a over those inFigure 1b. Similarly, an algorithm that focuses only oninterconnectivity will, in Figure 2, incorrectly mergethe dark-blue with the red cluster rather than the greenone. Here, we assume that the aggregate interconnec-tivity between the items in the dark-blue and red clus-ters is greater than that of the dark-blue and greenclusters. However, the border points of the dark-bluecluster are much closer to those of the green clusterthan those of the red cluster.

CHAMELEON: CLUSTERING USING DYNAMIC MODELING

Chameleon is a new agglomerative hierarchical clus-tering algorithm that overcomes the limitations ofexisting clustering algorithms. Figure 3 (on page 70)provides an overview of the overall approach used byChameleon to nd the clusters in a data set.

The Chameleon algorithm’s key feature is that itaccounts for both interconnectivity and closeness inidentifying the most similar pair of clusters. It thusavoids the limitations discussed earlier. Furthermore,Chameleon uses a novel approach to model the degreeof interconnectivity and closeness between each pair ofclusters. This approach considers the internal charac-teristics of the clusters themselves. Thus, it does notdepend on a static, user-supplied model and can auto-matically adapt to the internal characteristics of themerged clusters.

Chameleon operates on a sparse graph in whichnodes represent data items, and weighted edges rep-resent similarities among the data items. This sparse-graph representation allows Chameleon to scale to

large data sets and to successfully use data sets that

0018-9162/99/$10.00 © 1999 IEEE

68Computer

第1页下一页