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

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

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

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

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

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

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