基于自然鄰的層次聚類算法研究.pdf

1、數(shù)據(jù)挖掘是從大量數(shù)據(jù)中發(fā)現(xiàn)潛在的有價值的知識，其主要任務包括回歸分析（Regression）、關聯(lián)分析（Association rule learning）、分類分析（Classification）、聚類分析（Clustering）以及異常分析（Outliers detection）等。聚類分析是其中的一個重要分支。所謂聚類就是將需要處理的整個數(shù)據(jù)集劃分成多個不同的類簇，使得簇內對象彼此相似，而簇間對象彼此相異。聚類分析不僅可以作為獨立

2、的數(shù)據(jù)挖掘工具對數(shù)據(jù)集進行分析，聚類后通過對相似或相異的對象進行分析（集中對某些對象進行分析），可以幫助人們有效地提取共同的特征和發(fā)現(xiàn)有價值的信息，還可以在使用其他算法（如特征提取、離群檢測、和分類）之前，先利用聚類算法將數(shù)據(jù)集中相似的對象劃分到一起，不同的對象分開。聚類分析作為一種無監(jiān)督的學習方法，在計算機領域（如圖像處理、計算機視覺、模式識別、機器學習等），統(tǒng)計分析，社會學等鄰域都有較為廣泛的應用。
　　針對不同的目的、方法，

3、很多聚類算法已經被提出。其中層次聚類算法由于其思想比較簡單，且能有效幫助分析具有層次結構的實際問題，因此成為應用較為廣泛的一類算法。Chameleon算法是層次聚類算法中具有代表性的一個算法。它通過構造 K-最近鄰圖，劃分和利用基于互連度和接近度的簇與簇之間的相似性度量方法對劃分得到的初始子簇進行合并等操作，使得 Chameleon算法在發(fā)現(xiàn)任意形狀的簇方面更具有優(yōu)勢。但是 Chameleon算法需要進行參數(shù)設定，如設定構造K-最近鄰圖

4、時的K值，對K-最近圖進行劃分時的子簇大小的閾值和進行子簇合并時的相似度閾值或期望的聚類數(shù)目。針對此問題，本文將自然鄰居的概念引入到層次聚類算法中。
　　自然鄰居（Natural Neighbor:NaN）是我們提出的一種新的鄰居概念，與以前的K-最近鄰居和ε-最近鄰居不同的是它是一種無尺度的鄰居概念。K-最近鄰居和ε-最近鄰居，由于其方法比較簡單，而且能夠較好地反映數(shù)據(jù)集的分布特征，一經提出就被廣泛應用于很多的分類算法如KNN分

5、類算法、聚類算法如Chameleon算法和DBSCAN算法、離群檢測算法如LOF和INFLO中。但是K-最近鄰居和ε-最近鄰居在使用中都需要設定參數(shù)，特別是對于一個分布結構未知的數(shù)據(jù)集，K-最近鄰居中的 K值或者ε-最近鄰居中的ε應設為多少才能夠反映這個數(shù)據(jù)集的結構特性，越來越成為人們需要關注的問題。自然鄰居在使用過程中不需設定任何參數(shù)，而是通過在給定的數(shù)據(jù)集上不斷地擴大鄰域搜索范圍進行自適應學習，從而得到數(shù)據(jù)集的分布特征。在自然鄰居的

6、概念下，分布在密集區(qū)域的數(shù)據(jù)對象的自然鄰居數(shù)較多，而分布在稀疏區(qū)域的數(shù)據(jù)對象的自然鄰居數(shù)則較少。
　　本文將自然鄰居的概念與 Chameleon算法相結合，提出了一種新的聚類算法——基于自然鄰居的層次聚類算法Hi-CLUBS。首先利用自然鄰搜索算法構造飽和自然鄰域圖，并提出了一種基于模塊度的圖劃分算法將飽和自然鄰域圖劃分成初始子簇，然后利用一種新的基于子簇互連度和子簇接近度的相似性度量方法對劃分得到的初始子簇進行合并，直到得到期望

7、的聚類數(shù)目。通過與其他算法的對比實驗證明了 Hi-CLUBS算法減少了對參數(shù)的依賴，而且在發(fā)現(xiàn)任意形狀的簇方面更具優(yōu)勢。
　　針對數(shù)據(jù)集中可能存在噪聲點的問題，我們考慮先去除數(shù)據(jù)集中的噪聲點，然后再對其進行聚類。由此本文提出了基于噪聲去除的層次聚類算法HCBNR。首先利用自然鄰居計算法每個數(shù)據(jù)對象的密度，根據(jù)密度遞增曲線確定密度閾值，去掉數(shù)據(jù)集中的噪聲點，然后利用我們在本文提出的 Hi-CLUBS算法對剩余的數(shù)據(jù)集進行聚類。通過與