[發(fā)明專利]一種K近鄰相似度優(yōu)化的密度峰聚類方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710607140.9
• 申請(qǐng)日: 2017-07-24
• 公開（公告）號(hào): CN107392249A
• 公開（公告）日: 2017-11-24
• 發(fā)明（設(shè)計(jì)）人: 葛洪偉;朱慶峰;江明;李莉
• 申請(qǐng)（專利權(quán)）人: 江南大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)挖掘和智能信息處理領(lǐng)域，涉及流形數(shù)據(jù)聚類處理；具體地說就是一種K近鄰相似度優(yōu)化的密度峰聚類方法，可用于數(shù)據(jù)挖掘、模式識(shí)別和機(jī)器學(xué)習(xí)等領(lǐng)域。

背景技術(shù)

聚類是指將物理或抽象對(duì)象的集合分組為由類似的對(duì)象組成的多個(gè)類的分析過程。它是一種重要的人類行為。聚類的目的簡(jiǎn)單來說就是對(duì)相似的數(shù)據(jù)進(jìn)行分類。聚類源于很多領(lǐng)域，包括數(shù)學(xué)，計(jì)算機(jī)科學(xué)，統(tǒng)計(jì)學(xué)，生物學(xué)和經(jīng)濟(jì)學(xué)。聚類在數(shù)據(jù)挖掘、模式識(shí)別、機(jī)器學(xué)習(xí)、信息檢索等領(lǐng)域已經(jīng)得到了廣泛研究和應(yīng)用。聚類是一種探索性的分析，在分類的過程中，人們不必事先給出一個(gè)分類的標(biāo)準(zhǔn)，聚類分析能夠從樣本數(shù)據(jù)出發(fā)，自動(dòng)進(jìn)行分類。從統(tǒng)計(jì)學(xué)的角度看，聚類是通過數(shù)據(jù)建模簡(jiǎn)化數(shù)據(jù)的一種方法。傳統(tǒng)的統(tǒng)計(jì)聚類分析方法包括系統(tǒng)聚類法、分解法、動(dòng)態(tài)聚類法、有序樣品聚類及模糊聚類等。從機(jī)器學(xué)習(xí)的角度看，簇相當(dāng)于隱藏模式。聚類是搜索簇的無監(jiān)督學(xué)習(xí)過程。聚類與分類不同，無監(jiān)督學(xué)習(xí)不依賴預(yù)先定義的類或帶類標(biāo)記的訓(xùn)練實(shí)例，需要由聚類學(xué)習(xí)算法自動(dòng)確定標(biāo)記，而分類學(xué)習(xí)的實(shí)例或數(shù)據(jù)對(duì)象有類別標(biāo)記。聚類是觀察式學(xué)習(xí)，而不是示例式的學(xué)習(xí)；從實(shí)際應(yīng)用的角度看，聚類分析是數(shù)據(jù)挖掘的主要任務(wù)之一。聚類能夠作為一個(gè)獨(dú)立的工具獲得數(shù)據(jù)的分布狀況，觀察每一簇?cái)?shù)據(jù)的特征，集中對(duì)特定的聚簇集合作進(jìn)一步地分析。聚類分析還可以作為其他算法(如分類、定性歸納算法等)及應(yīng)用(如圖像檢索、數(shù)據(jù)挖掘等)的預(yù)處理步驟，具有重要的意義。

2014，Alex Rodriguez等人在《Science》上提出了基于密度的密度峰聚類(Density Peaks Clustering，DPC)算法。DPC算法不需要事先指定族類數(shù)目，而是通過決策圖，找出聚類中心，再將其他的點(diǎn)進(jìn)行分配，得到聚類結(jié)果。密度峰聚類算法雖然簡(jiǎn)單高效，但是容易發(fā)生點(diǎn)錯(cuò)誤分配，造成誤差傳播，最后得到錯(cuò)誤的結(jié)果。尤其對(duì)于一些復(fù)雜的流形聚類，這種缺陷尤為突出。

發(fā)明內(nèi)容

針對(duì)上述的問題，本發(fā)明提出了K近鄰相似度優(yōu)化的密度峰聚類(Density Peaks clustering Optimized by K Nearest Neighbor’s Similarity，DPCKS)方法，可以解決原密度峰聚類算法無法正確處理流形數(shù)據(jù)聚類的問題，提高了算法的適用范圍，可以滿足實(shí)際工程應(yīng)用的需求。

實(shí)現(xiàn)本發(fā)明的關(guān)鍵技術(shù)是：對(duì)于每一個(gè)樣本點(diǎn)，首先通過函數(shù)計(jì)算它與其他點(diǎn)的相似度，找出其K近鄰。然后通過它的K近鄰判斷其指向點(diǎn)是否正確，對(duì)于指向錯(cuò)誤的樣本點(diǎn)，重新尋找它的指向點(diǎn)。最后，將剩余的點(diǎn)分配給密度比它大的最近點(diǎn)所在族類。

為實(shí)現(xiàn)上述目標(biāo)，具體實(shí)現(xiàn)步驟如下：

(1)計(jì)算所有點(diǎn)間距離，算出截?cái)嗑嚯xd_c值，利用高斯函數(shù)：計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的密度，然后利用函數(shù)：計(jì)算每個(gè)點(diǎn)到密度比它大的最近點(diǎn)的距離。其中，d_ij表示點(diǎn)i和點(diǎn)j的距離。對(duì)于全局密度最大的點(diǎn)，令δ_i＝max_jd_ij。

(2)根據(jù)每個(gè)點(diǎn)的ρ和δ值畫出決策圖，找出聚類中心。

(3)根據(jù)函數(shù)：計(jì)算點(diǎn)間相似度，找到每個(gè)點(diǎn)的K近鄰點(diǎn)。其中X＝(x₁,…,x_d)和Y＝(y₁,…,y_d)是d維空間中的兩個(gè)向量，m_i表示第i維上X和Y的平均值的絕對(duì)值。

(4)所有的點(diǎn)按照密度從大到小排序，新建空數(shù)組Aq，Bq，并把聚類中心依次放入數(shù)組Aq。

(5)按照密度從大到小的順序，依次取點(diǎn)i，判斷點(diǎn)i是否已經(jīng)分配。如果已經(jīng)分配，取下一個(gè)；如果未分配，則進(jìn)行下一步。

(6)判斷點(diǎn)i是否是密度峰值點(diǎn)。如果不是，取下一個(gè)；如果是，判斷點(diǎn)i與指向點(diǎn)j是否連通。如果連通，把點(diǎn)i放入數(shù)組Aq末尾；如果不連通，則把點(diǎn)i放入數(shù)組Bq末尾。

(7)判斷數(shù)組Bq是否為空，如果為空，則將剩余的點(diǎn)分配，結(jié)束；如果不為空，則分別從數(shù)組Aq中找出一個(gè)點(diǎn)j，從數(shù)組Bq中找出一個(gè)點(diǎn)h，滿足點(diǎn)j與點(diǎn)h距離最近。

(8)判斷點(diǎn)h與點(diǎn)j是否連通，如果連通，則點(diǎn)h的指向點(diǎn)為點(diǎn)j，把點(diǎn)h歸入點(diǎn)j所在族類，并將點(diǎn)h加入數(shù)組Aq末尾，并從數(shù)組Bq中刪除點(diǎn)h；如果不連通，尋找下一對(duì)最近點(diǎn)，判斷。重復(fù)，直到數(shù)組Bq為空或者數(shù)組Bq中剩余點(diǎn)都不與數(shù)組Aq中的點(diǎn)連通。