基于自然鄰的層次聚類(lèi)算法研究.pdf

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

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

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

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

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

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

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