基于自然鄰的自適應(yīng)譜聚類算法研究.pdf

1、聚類分析是當(dāng)下研究的熱點(diǎn)之一，它主要是將整個(gè)數(shù)據(jù)集劃分成一個(gè)個(gè)簇，簇內(nèi)的成員之間相似度較高，而簇間成員相似度較低。通過(guò)相似或相異性進(jìn)行分析，挖掘其中潛在的有用的商業(yè)信息?，F(xiàn)如今它的運(yùn)用領(lǐng)域非常廣泛，如統(tǒng)計(jì)學(xué)、生物工程、社會(huì)科學(xué)、醫(yī)療信息處理等。聚類分析方法多種多樣，按照思想進(jìn)行分類，基本可以分為以下幾類：基于密度聚類、層次聚類、基于網(wǎng)格聚類、劃分聚類以及基于模型聚類等。大部分經(jīng)典的聚類分析算法都在凸形的樣本空間上表現(xiàn)理想，但在非凸形數(shù)據(jù)

2、集上效果欠佳，而譜聚類算法卻能避免這一問(wèn)題，它在任何形狀的樣本空間中無(wú)限接近最佳值。另外，它還可以處理高維數(shù)據(jù)集，故而受到很多學(xué)者的廣泛關(guān)注。
　　譜聚類算法是以圖論為理論基礎(chǔ)的，按照不同的劃分目的，提出了很多劃分準(zhǔn)則，其中包括最小割集準(zhǔn)則、比例割集準(zhǔn)則、規(guī)范割集準(zhǔn)則、最大最小割集準(zhǔn)則等。求解準(zhǔn)則函數(shù)的最優(yōu)解，是一個(gè)NP難問(wèn)題，故而將它松弛到求解拉普拉斯矩陣的譜分解上，譜分解結(jié)果對(duì)應(yīng)的就是最優(yōu)解。根據(jù)拉普拉斯矩陣的不同，它的聚類步

3、驟也略有差別，但根據(jù)實(shí)驗(yàn)證明，在基于矩陣Lsym上的聚類效果最為理想，代表性算法是NJW算法，故而后面大量研究都是基于此基礎(chǔ)上進(jìn)行改進(jìn)的。Self-Tuning算法是一個(gè)比較經(jīng)典的改進(jìn)，該算法主要思想是將高斯函數(shù)里面的核參數(shù)替換為第K近鄰距離，為每一個(gè)點(diǎn)都指定一個(gè)核參數(shù)，這樣可以弱化核參數(shù)對(duì)聚類效果的影響，在一定程度上取得了不錯(cuò)的效果。但是該算法針對(duì)多重尺度數(shù)據(jù)集效果不是很理想，而且也需要出入?yún)?shù)值 K和聚類數(shù)目。針對(duì)這些問(wèn)題，又提出了

4、很多基于密度改進(jìn)的算法，此處給出一個(gè)代表IASCDBA算法，它的主要思想是將密度信息引入相似矩陣構(gòu)造中，從而達(dá)到更加完善的相似性度量效果，但該算法仍然需要輸入K值和聚類數(shù)目。
　　自然鄰是近期提出的一個(gè)鄰居概念，與傳統(tǒng)的鄰居概念大不相同，且具有明顯的優(yōu)勢(shì)。典型并且運(yùn)用廣泛的傳統(tǒng)鄰居算法有兩種，分別是K-最近鄰和-最近鄰，這兩個(gè)算法都需要人為輸入?yún)?shù)，其中一個(gè)是正整數(shù)K，另外一個(gè)是距離數(shù)值，不同數(shù)據(jù)集參數(shù)選擇差異較大。而在自然鄰中，

5、無(wú)需輸入任何參數(shù)，自動(dòng)尋找各個(gè)數(shù)據(jù)點(diǎn)的分布特征和自然鄰居個(gè)數(shù)，并且獲得了類似于K值的自然特征是supk，從而可以將自然鄰運(yùn)用到很多算法中去，解決他們的參數(shù)問(wèn)題。
　　提出了一種基于自然鄰自適應(yīng)譜聚類算法。針對(duì)當(dāng)前譜聚類改進(jìn)算法的缺陷，該算法將自然鄰運(yùn)用到譜聚類算法中。首先通過(guò)自然鄰算法獲取自然鄰居數(shù)nb、自然特征值supk、supk近鄰集NN，自然鄰居集RNN。然后利用這些信息改進(jìn)相似矩陣的構(gòu)造，使得相似矩陣更加貼切地描述數(shù)據(jù)點(diǎn)之

6、間的相似性；并且使用近鄰傳播信息在全鄰居上面進(jìn)行擴(kuò)展，得到更加穩(wěn)定的聚類數(shù)目。將以上的結(jié)果作為聚類算法的輸入，最后輸出數(shù)據(jù)集對(duì)應(yīng)的聚類結(jié)果。實(shí)驗(yàn)部分，在8個(gè)人工數(shù)據(jù)集上，將本文的算法與NJW、Self-Tuning、IASCDBA算法三種算法進(jìn)行比較，在以上三種算法人為輸入合適參數(shù)的情況下，本文改進(jìn)的NN-ASC算法聚類效果最為理想。
　　提出了一種基于自然鄰的去噪算法（NN-NR）。針對(duì)當(dāng)前自適應(yīng)譜聚類算法在含有噪聲點(diǎn)的樣本空間