運用微群集策略於階層式分群法

A Novel Hierarchical Clustering Algorithm Using the Micro-Cluster Strategy

李維平(Wei-Ping Lee) ； 賴錦慧(Chin-Hui Lai) ； 蘇俊杰(Chun-Chieh Su)

《先進工程學刊》 10卷3期 (2015/07) Pp. 117-124

摘要

本研究提出一個以微群集為基礎的階層式分群法（HCMC）。將密度法的概念應用在資料分割上，並過濾雜訊資料，降低雜訊對分群的品質。HCMC演算法屬於二階段演算法，第一階段為分割階段，利用密度法的概念將資料分割出許多微群集，並將雜訊資料過濾，保留群聚主幹的資料；第二階段為合併階段，採用階層法中的，單一連接聚合法進行聚合，達到探索任意形狀的能力，經過分割階段的處理，使聚合的過程更有效率。實驗結果證明HCMC能降低雜訊資料影響分群結果，同時也有不錯的分群品質，時間複雜度計算上，也稍優於同類型的分群演算法。

關鍵字

分群演算法 ； 二階段分群法 ； 微群集 ； 單一連結

並列摘要

This paper proposes a novel Hierarchical Clustering algorithm based on the Micro-Cluster strategy, called HCMC algorithm. In order to alleviate the influence caused by the noise data on the quality of clustering, the concept of density-based is applied to data partition and filtration of noise data. The HCMC algorithm consists of two phases. The first phase aims to partition several micro-clusters and then filter out noise data by using the density-based method for keeping the main data of clusters. The second phase uses single-linkage agglomerative algorithm to explore of arbitrary shapes. With the partitioning phase, the process of agglomeration is efficient. The experiment demonstrates that HCMC algorithm is capable of reducing the impact on clustering caused by noise data and keeping a fair quality of clustering as well. In the meantime, HCMC algorithm also proves to be superior to other clustering algorithms among the same categories as far as the complicated time calculation is concerned.

並列關鍵字

clustering algorithm ； two phases clustering ； micro-cluster ； single linkage