An algorithm that aims to combine the benefits of both hierarchical clustering and scripts clustering.

A clustering algorithm of this category is CHAMELEON. It is an agglomerative hierarchical algorithm that measures the similarity of two clusters based on a dynamic model. CHAMELEON finds the clusters of the data set using a two-phase algorithm:

• During the first phase, CHAMELEON uses a graph-based clustering algorithm to segment the data into a large number of relatively small sub-clusters.
• During the second phase, it uses a cumulative hierarchical algorithm to find the clusters of iterative combinations of sub-clusters derived from the first phase. The similarity between clusters is determined by controlling the relative inter-connectivity and relative closeness thereof. The representation of the data is based on the commonly used k-nearest neighbor graph approach. The vertices of the k-nearest neighboring graph represent the objects of the dataset and there is an edge between two nodes, if the object corresponding to x is among the k closest neighbors of the y. The algorithm then finds the initial sub-clusters using a graph segmentation algorithm to divide the k-nearest neighboring graph of the dataset into a large number of segments.

During the next phase, CHAMELEON uses a clustering algorithm that combines these sub-clusters of the graph. For merging the sub-clusters it takes into account the relative interconnectivity and closeness of sub-clusters. Consequently, those pairs of clusters whose relative interconnectivity and proximity are above the user-defined threshold are merged.