李 萍,龔曉峰,雒瑞森

(四川大學(xué) 電氣信息學(xué)院,成都 610065)

0 概述

聚類(lèi)分析是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要分支,其可在無(wú)任何先驗(yàn)知識(shí)的條件下,用于探索數(shù)據(jù)之間的內(nèi)部結(jié)構(gòu)和內(nèi)在聯(lián)系從而獲取有價(jià)值的信息。聚類(lèi)的過(guò)程是通過(guò)迭代將數(shù)據(jù)集劃分為多個(gè)類(lèi)簇,并且使類(lèi)間聯(lián)系盡可能小、類(lèi)內(nèi)聯(lián)系盡可能大[1]。如今,聚類(lèi)分析已廣泛應(yīng)用于人工智能、圖像處理、模式識(shí)別等任務(wù)中。

聚類(lèi)算法一般可分為基于劃分的聚類(lèi)、基于網(wǎng)格的聚類(lèi)、基于密度的聚類(lèi)等算法[2-3]。K均值聚類(lèi)(K-means)算法[4-5]是基于劃分聚類(lèi)的經(jīng)典算法,通過(guò)多次迭代找到最佳數(shù)據(jù)均值點(diǎn)作為聚類(lèi)中心,因此異常點(diǎn)和噪聲點(diǎn)對(duì)聚類(lèi)中心的影響很大。基于此,文獻(xiàn)[6-7]相繼提出K-medoids聚類(lèi)和K-modes聚類(lèi)算法來(lái)尋找最佳聚類(lèi)中心,改善異常點(diǎn)和噪聲點(diǎn)對(duì)聚類(lèi)中心的影響,但其都需要設(shè)定初始聚類(lèi)個(gè)數(shù)。STING算法[8]是基于網(wǎng)格聚類(lèi)的代表算法,將數(shù)據(jù)每個(gè)屬性的可能值劃分成多個(gè)相鄰區(qū)間,從而創(chuàng)建網(wǎng)格單元集合進(jìn)行聚類(lèi),但其也需提前設(shè)定聚類(lèi)個(gè)數(shù)?；诿芏鹊目臻g聚類(lèi)(Density-Based Spatial Clustering of Applications with Noise,DBSCAN)算法[9]是基于密度聚類(lèi)的經(jīng)典算法,該算法能夠識(shí)別異常點(diǎn)和噪聲點(diǎn),然而需要人工設(shè)定兩個(gè)鄰域信息參數(shù)(Eps和Minpts),并且對(duì)于數(shù)據(jù)集的密度比較敏感。為解決以上問(wèn)題,文獻(xiàn)[10]提出改進(jìn)的DBSCAN算法對(duì)不同密度層次的數(shù)據(jù)進(jìn)行分層聚類(lèi),但需要確定近鄰數(shù)K。文獻(xiàn)[11]提出一種新的密度峰值聚類(lèi)(Density Peaks Clustering,DPC)算法,該算法只需要指定一個(gè)截?cái)嗑嚯x來(lái)計(jì)算數(shù)據(jù)集的局部密度,但是聚類(lèi)中心的選取需要利用決策圖進(jìn)行判斷,缺乏可靠性。近些年來(lái),基于圖論的譜聚類(lèi)算法[12]廣泛應(yīng)用于聚類(lèi)任務(wù)中。譜聚類(lèi)主要通過(guò)求解圖的最優(yōu)劃分得到最優(yōu)結(jié)果,但是該算法的準(zhǔn)確性依賴(lài)于其鄰接矩陣,基于此,文獻(xiàn)[13-14]相繼提出改進(jìn)的譜聚類(lèi)算法,雖然通過(guò)改進(jìn)鄰接矩陣能有效改善聚類(lèi)效果,但是需要指定聚類(lèi)數(shù)并且無(wú)法識(shí)別出異常點(diǎn)和噪聲點(diǎn)。

由于多數(shù)聚類(lèi)算法需要指定聚類(lèi)參數(shù),導(dǎo)致聚類(lèi)結(jié)果的準(zhǔn)確性受到影響,而自然近鄰[15-16]是一種無(wú)尺度的最近鄰概念,其利用數(shù)據(jù)集自身的特性進(jìn)行自然鄰居的搜索,通過(guò)每個(gè)數(shù)據(jù)點(diǎn)的自然鄰居個(gè)數(shù)來(lái)判斷其周?chē)臄?shù)據(jù)分布情況,因此無(wú)需人為指定聚類(lèi)參數(shù)。本文利用自然近鄰的特性篩選出密度較高的數(shù)據(jù)作為代表核點(diǎn)進(jìn)行聚類(lèi),從而排除邊界點(diǎn)和噪聲點(diǎn)對(duì)聚類(lèi)的影響,通過(guò)建立簇間的關(guān)聯(lián)度矩陣來(lái)尋找具有關(guān)聯(lián)度的簇,并根據(jù)簇間融合的有效性評(píng)估自適應(yīng)合并關(guān)聯(lián)度較高的簇,最終得到理想的聚類(lèi)結(jié)果。

1 相關(guān)工作

1.1 自然近鄰

自然近鄰是一種新型的最近鄰概念,其屬于無(wú)尺度最近鄰方法的范疇,自然鄰居的搜索過(guò)程中不需要進(jìn)行人工的參數(shù)設(shè)置,而是通過(guò)不斷擴(kuò)大自然鄰居的搜索范圍,使得數(shù)據(jù)集比較密集的地方自然鄰居較多,數(shù)據(jù)集比較稀疏的地方自然鄰居較少。對(duì)于一些離群點(diǎn)和噪聲點(diǎn)而言,其自然鄰居個(gè)數(shù)相對(duì)較少甚至幾乎為0。假設(shè)存在數(shù)據(jù)集X,p∈X,q∈X且p≠q,則存在如下定義[17]:

定義1(逆K近鄰) 若q在p的K近鄰內(nèi),則稱(chēng)p屬于q的逆K近鄰,記為p∈RNNk(q)。

定義2(自然穩(wěn)定狀態(tài)) 在自然鄰居的搜索過(guò)程中,若每個(gè)數(shù)據(jù)點(diǎn)都有逆近鄰或者當(dāng)所有逆鄰個(gè)數(shù)為0的數(shù)據(jù)不變時(shí),自然鄰居搜索達(dá)到自然穩(wěn)定狀態(tài)。

定義3(自然特征值) 當(dāng)自然鄰居的搜索達(dá)到自然穩(wěn)定狀態(tài)時(shí),自然鄰居的搜索次數(shù)稱(chēng)為自然特征值,記作supk。

定義4(自然近鄰) 當(dāng)自然鄰居的搜索達(dá)到自然穩(wěn)定狀態(tài)時(shí),若?p是q的supk逆近鄰,則稱(chēng)p是q的自然鄰居,同理,若q是p的supk逆近鄰,則稱(chēng)q是p的自然鄰居。

自然近鄰搜索算法的具體步驟如下:

步驟1初始化搜索次數(shù)r=1,自然近鄰數(shù)nb=?,逆近鄰數(shù)RNN=?。

步驟2計(jì)算每個(gè)樣本p的r近鄰、nb(p)及RNN(p)。

步驟3r=r+1。

步驟4當(dāng)?q使得RNN(q)≠?或所有RNN=?的q值不再變化時(shí),supk=r-1,輸出supk、nb和RNN,否則跳轉(zhuǎn)至步驟2。

1.2 自適應(yīng)關(guān)聯(lián)融合聚類(lèi)算法

本文通過(guò)自然近鄰思想尋找數(shù)據(jù)集中的相對(duì)稀疏點(diǎn)和密集點(diǎn)。為去除稀疏的邊界點(diǎn)和噪聲點(diǎn)信息,本文提出代表核點(diǎn)的概念,即代表核點(diǎn)周?chē)淖匀秽従訑?shù)較多并且其周?chē)植嫉淖匀秽従右捕鄶?shù)為代表核點(diǎn)。因此,由代表核點(diǎn)組成的代表核點(diǎn)集能反映數(shù)據(jù)的集中分布情況,從而體現(xiàn)原數(shù)據(jù)集的主要數(shù)據(jù)結(jié)構(gòu)信息。以R15人工數(shù)據(jù)集為例,通過(guò)計(jì)算代表核點(diǎn)并去除干擾點(diǎn),得到如圖1所示的主要簇信息,最后將代表核點(diǎn)進(jìn)行聚類(lèi)得到初始聚類(lèi)信息和聚類(lèi)數(shù)。

圖1 R15人工數(shù)據(jù)集原始分布及其代表核點(diǎn)

定義5(代表核點(diǎn)) 當(dāng)自然鄰居的搜索達(dá)到自然穩(wěn)定狀態(tài)時(shí),?p滿足其自然鄰居個(gè)數(shù)nb(p)大于等于自然特征值supk,并且在p的supk范圍內(nèi)滿足此條件的數(shù)據(jù)個(gè)數(shù)大于不滿足該條件的數(shù)據(jù)個(gè)數(shù),則稱(chēng)該點(diǎn)為代表核點(diǎn)。

代表核點(diǎn)的選取雖然能有效移除邊界點(diǎn)和噪聲點(diǎn),從而使得邊界點(diǎn)和噪聲點(diǎn)不會(huì)影響數(shù)據(jù)的聚類(lèi),但是由于同簇?cái)?shù)據(jù)間會(huì)存在一些相對(duì)稀疏的非邊界點(diǎn)數(shù)據(jù),該算法可能會(huì)將這些相對(duì)稀疏的非邊界點(diǎn)移除,使得同簇的數(shù)據(jù)最終聚為兩個(gè)不同的簇。因此,本文提出關(guān)聯(lián)度矩陣(ccomatrix)的概念。關(guān)聯(lián)度矩陣表示簇間的關(guān)聯(lián)程度,簇間關(guān)聯(lián)度越大,則關(guān)聯(lián)程度越高,當(dāng)簇間關(guān)聯(lián)度為0時(shí),即不存在關(guān)聯(lián)關(guān)系,其數(shù)學(xué)表達(dá)式如下:

(1)

其中,cco_num為簇間數(shù)據(jù)點(diǎn)的關(guān)聯(lián)個(gè)數(shù)矩陣,co_dist為簇間代表核點(diǎn)的最短距離,ds為簇間最短距離之和,ns為簇間關(guān)聯(lián)個(gè)數(shù)之和。

為尋找最佳的關(guān)聯(lián)簇進(jìn)行融合,本文引入一種幾何方法[18]計(jì)算簇間的融合信息。簇間的融合度量體現(xiàn)了簇間融合的有效性,本文通過(guò)聚類(lèi)簇的數(shù)據(jù)特征軸和聚類(lèi)簇間的距離來(lái)評(píng)估聚類(lèi)結(jié)果對(duì)于簇間分離或融合的有效性。當(dāng)聚類(lèi)數(shù)據(jù)簇間的融合度量(GI)達(dá)到最優(yōu)值時(shí)(GI達(dá)到最小),此時(shí)的聚類(lèi)數(shù)為最佳聚類(lèi)數(shù)。簇間的融合度量可表示為:

(2)

其中,λ表示聚類(lèi)簇的協(xié)方差矩陣的特征根,d表示聚類(lèi)數(shù)據(jù)維度,c表示聚類(lèi)個(gè)數(shù),k表示第k類(lèi)簇,q表示第q類(lèi)簇,mk表示第k類(lèi)簇的中心點(diǎn),mq表示第q類(lèi)簇的中心點(diǎn)。

圖2 樣本分布示意圖

本文算法步驟具體如下:

步驟1將數(shù)據(jù)進(jìn)行歸一化處理,利用自然近鄰搜索算法計(jì)算自然特征值supk,逆近鄰數(shù)RNN,自然近鄰數(shù)nb。

步驟2通過(guò)定義5選擇代表核點(diǎn),將互為最大逆鄰范圍內(nèi)的代表核點(diǎn)歸為一類(lèi)。

步驟3將最大逆鄰范圍內(nèi)包含代表核點(diǎn)的未歸類(lèi)點(diǎn)歸為離其最近的代表核點(diǎn)類(lèi)。

步驟4對(duì)于最大逆鄰范圍內(nèi)未包含代表核點(diǎn)的未歸類(lèi)點(diǎn),若在其逆鄰范圍內(nèi)包含具有類(lèi)簇信息的數(shù)據(jù)點(diǎn),則將該點(diǎn)歸為該類(lèi)簇,否則判斷其為異常點(diǎn)。

步驟5通過(guò)式(1)計(jì)算簇間的關(guān)聯(lián)度矩陣ccomatrix,選擇關(guān)聯(lián)度大于0的值從高到低排序作為數(shù)據(jù)融合閾值。

步驟6通過(guò)式(2)計(jì)算從高到低閾值下數(shù)據(jù)融合的最小GI值,選擇最小GI值所對(duì)應(yīng)的聚類(lèi)數(shù)作為最佳聚類(lèi)數(shù),得到最終的聚類(lèi)結(jié)果。

1.3 算法分析

本文算法主要分為初步聚類(lèi)和聚類(lèi)有效性評(píng)估兩個(gè)部分:

第一部分主要是對(duì)數(shù)據(jù)集進(jìn)行初步聚類(lèi),首先利用自然近鄰篩選代表核點(diǎn),再對(duì)代表核點(diǎn)集進(jìn)行初步聚類(lèi),最后將一些邊界點(diǎn)進(jìn)行歸類(lèi),其主要優(yōu)點(diǎn)如下:

1)在代表核點(diǎn)的篩選過(guò)程中,由于自然近鄰能尋找每個(gè)數(shù)據(jù)點(diǎn)的自然鄰居,其自然鄰居數(shù)越多,該數(shù)據(jù)點(diǎn)的位置就越集中,因此可以將自然鄰居數(shù)少的邊界點(diǎn)和噪聲點(diǎn)排除,避免代表核點(diǎn)集聚類(lèi)時(shí)將噪聲點(diǎn)和具有邊界相連的數(shù)據(jù)簇融合。

2)由于自然近鄰算法的自然鄰居尋找是通過(guò)數(shù)據(jù)點(diǎn)附近的數(shù)據(jù)分布特點(diǎn)進(jìn)行搜索,因此對(duì)于不同密度簇的數(shù)據(jù)集而言,代表核點(diǎn)的篩選不會(huì)將整體密度較小的數(shù)據(jù)簇作為噪聲點(diǎn)或邊界點(diǎn)排除,只要密度較小的數(shù)據(jù)簇分布集中,也能篩選出該簇的主要簇信息。

3)對(duì)于代表核點(diǎn)的聚類(lèi),考慮數(shù)據(jù)點(diǎn)間的密度分布情況,本文通過(guò)對(duì)代表核點(diǎn)間的互逆近鄰關(guān)系進(jìn)行聚類(lèi)從而達(dá)到一個(gè)理想效果,對(duì)于非代表核點(diǎn)的分類(lèi),主要分為兩種情況,即其逆鄰范圍內(nèi)存在代表核點(diǎn)和不存在代表核點(diǎn),將存在代表核點(diǎn)的數(shù)據(jù)歸為最近核點(diǎn)類(lèi),而不存在代表核點(diǎn)類(lèi)的數(shù)據(jù),若逆鄰范圍內(nèi)無(wú)類(lèi)簇信息,則可證明其遠(yuǎn)離信息簇,其可能為異常點(diǎn)或噪聲點(diǎn)。

第二部分主要是對(duì)第一部分的初步聚類(lèi)效果進(jìn)行有效性評(píng)估。由于初步聚類(lèi)過(guò)程中可能存在同簇間數(shù)據(jù)連接較稀疏,使得代表核點(diǎn)的篩選過(guò)程中將同簇分離,因此本文需要對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)估。該部分首先求出類(lèi)簇間的關(guān)聯(lián)度,其中關(guān)聯(lián)度越小,類(lèi)簇間融合的可能性越小,當(dāng)簇間關(guān)聯(lián)度為0時(shí),說(shuō)明該簇組無(wú)關(guān)聯(lián),無(wú)需考慮融合。為尋找最佳的關(guān)聯(lián)簇進(jìn)行融合,本文結(jié)合關(guān)聯(lián)度信息與簇間融合度量的方法,將關(guān)聯(lián)度以從高到低的類(lèi)簇進(jìn)行依次融合并計(jì)算其對(duì)應(yīng)的GI值,當(dāng)GI值達(dá)到最小時(shí)停止融合。此時(shí)的聚類(lèi)結(jié)果可作為最佳聚類(lèi)結(jié)果,可見(jiàn)本文算法在無(wú)需設(shè)定聚類(lèi)數(shù)的情況下仍能尋找出合適的類(lèi)簇個(gè)數(shù)。

2 實(shí)驗(yàn)設(shè)置與結(jié)果分析

2.1 實(shí)驗(yàn)參數(shù)設(shè)置

為驗(yàn)證本文聚類(lèi)算法的有效性,將其與DBSCAN密度聚類(lèi)、K-means聚類(lèi)算法分別在D31、Aggregation、Five_Clusters人工數(shù)據(jù)集上進(jìn)行對(duì)比驗(yàn)證,其中,K-means聚類(lèi)算法的聚類(lèi)個(gè)數(shù)K選取原始數(shù)據(jù)集的類(lèi)簇個(gè)數(shù),DBSCAN算法的參數(shù)Eps和Minpits選取接近于原始類(lèi)簇聚類(lèi)效果的最佳值。

2.2 結(jié)果分析

實(shí)驗(yàn)最終聚類(lèi)結(jié)果如圖3～圖5所示,其中的實(shí)心圓點(diǎn)為噪聲點(diǎn)或異常點(diǎn)。通過(guò)原始數(shù)據(jù)特征可以看出,3種類(lèi)型的數(shù)據(jù)集都存在邊界值相連的情況并且部分?jǐn)?shù)據(jù)簇存在密度分布不均的問(wèn)題。對(duì)于K-means聚類(lèi)結(jié)果而言,由于K-means算法聚類(lèi)中心選取不當(dāng),導(dǎo)致數(shù)據(jù)集中同簇?cái)?shù)據(jù)分離成為異簇,異簇?cái)?shù)據(jù)合并成為同簇。對(duì)于DBSCAN聚類(lèi)結(jié)果而言,由于DBSCAN算法參數(shù)選取容易將邊界相連的兩類(lèi)數(shù)據(jù)合并為同一簇,大部分邊界點(diǎn)和密度較稀疏的點(diǎn)判斷為噪聲點(diǎn)。本文算法考慮到較稀疏的邊界值和噪聲點(diǎn)對(duì)數(shù)據(jù)聚類(lèi)結(jié)果的影響,首先使用自然近鄰搜索算法在保證密度層次較低的數(shù)據(jù)簇不被當(dāng)作邊界點(diǎn)或噪聲點(diǎn)排除的情況下選取代表核點(diǎn)進(jìn)行初步聚類(lèi),再將一些與類(lèi)簇有關(guān)聯(lián)的邊界點(diǎn)進(jìn)行歸類(lèi),而無(wú)關(guān)聯(lián)的數(shù)據(jù)點(diǎn)判定為異常點(diǎn)或孤立點(diǎn),最后對(duì)已聚類(lèi)的類(lèi)簇間進(jìn)行關(guān)聯(lián)度計(jì)算排序,按照關(guān)聯(lián)度大小依次計(jì)算融合后數(shù)據(jù)集的GI值,通過(guò)尋找最小的GI值使得數(shù)據(jù)集中本為同簇的類(lèi)簇合并為一簇,從而找到合適的聚類(lèi)數(shù)。因此,對(duì)比K-means算法和DBSCAN算法的聚類(lèi)結(jié)果,本文算法在無(wú)需指定聚類(lèi)個(gè)數(shù)的條件下,對(duì)邊界互連和密度層次不同的類(lèi)簇仍具有比較理想的聚類(lèi)效果,并且能識(shí)別出偏離類(lèi)簇較遠(yuǎn)的異常點(diǎn)或噪聲點(diǎn)。

圖3 D31人工數(shù)據(jù)集原始分布及聚類(lèi)算法效果對(duì)比

圖5 Five_Clusters人工數(shù)據(jù)集原始分布及聚類(lèi)算法效果對(duì)比

為驗(yàn)證算法的有效性,本文采用準(zhǔn)確率[19]和輪廓系數(shù)[20]兩組指標(biāo)對(duì)這3種聚類(lèi)算法的聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)。準(zhǔn)確率是聚類(lèi)結(jié)果的外部評(píng)價(jià)指標(biāo),其原理是將聚類(lèi)得到的類(lèi)標(biāo)簽與原數(shù)據(jù)的類(lèi)標(biāo)簽進(jìn)行對(duì)比,并計(jì)算出正確分類(lèi)的樣本個(gè)數(shù)占總樣本的比值,準(zhǔn)確率的比值越大,則表示聚類(lèi)的質(zhì)量越高,準(zhǔn)確率的數(shù)學(xué)表達(dá)式如式(3)所示:

(3)

其中,xi表示第i個(gè)樣本的正確類(lèi)標(biāo)號(hào),yi表示聚類(lèi)計(jì)算后得到的第i個(gè)樣本的類(lèi)標(biāo)號(hào),當(dāng)xi=yi時(shí),δ(xi,yi)=1,否則δ(xi,yi)=0。

輪廓系數(shù)是聚類(lèi)結(jié)果的內(nèi)部評(píng)價(jià)指標(biāo),其衡量了每個(gè)樣本與其同簇樣本間的緊密程度和異簇樣本間的分離程度,取值范圍為[-1,1],輪廓系數(shù)的數(shù)學(xué)表達(dá)式如式(4)所示:

(4)

其中:a(i)表示第i個(gè)樣本與同簇樣本間的平均歐式距離;b(i)表示第i個(gè)樣本與所有異簇樣本間的最小平均歐式距離;S(i)越接近于1,表示第i個(gè)樣本聚類(lèi)越具合理性,本文取所有樣本的平均輪廓系數(shù)作為評(píng)價(jià)指標(biāo)。

如表1和表2所示,本文實(shí)驗(yàn)分別記錄了K-means算法、DBSCAN算法和本文算法在D31、Aggregation、Five_Clusters人工數(shù)據(jù)集下的聚類(lèi)準(zhǔn)確率和輪廓系數(shù)值。對(duì)于K-means算法,本文對(duì)每個(gè)數(shù)據(jù)集進(jìn)行100次獨(dú)立的K-means算法實(shí)驗(yàn),實(shí)驗(yàn)的準(zhǔn)確率和輪廓系數(shù)值取100次重復(fù)實(shí)驗(yàn)的平均結(jié)果。通過(guò)對(duì)比可知,本文算法的聚類(lèi)準(zhǔn)確率和輪廓系數(shù)值在不同數(shù)據(jù)集上均明顯高于K-means算法和DBSCAN算法,驗(yàn)證了本文算法的可靠性。

表1 聚類(lèi)算法準(zhǔn)確率比較

表2 聚類(lèi)算法輪廓系數(shù)比較

3 結(jié)束語(yǔ)

本文提出基于自然近鄰的自適應(yīng)關(guān)聯(lián)融合聚類(lèi)算法,在自然近鄰的基礎(chǔ)上尋找代表簇結(jié)構(gòu)的核點(diǎn)進(jìn)行初步聚類(lèi),并通過(guò)簇間融合度量尋找關(guān)聯(lián)度矩陣中的最優(yōu)關(guān)聯(lián)度類(lèi)簇進(jìn)行融合。實(shí)驗(yàn)結(jié)果表明,本文算法無(wú)需人工設(shè)定聚類(lèi)參數(shù),可以有效處理密度層次不同和簇間相互靠近的類(lèi)簇,同時(shí)能排除異常點(diǎn)和噪聲點(diǎn)的干擾。但由于本文算法在多維數(shù)據(jù)集中的聚類(lèi)效果不明顯,因此后續(xù)將對(duì)多維數(shù)據(jù)集的最佳聚類(lèi)個(gè)數(shù)確定問(wèn)題進(jìn)行研究,進(jìn)一步提升算法聚類(lèi)準(zhǔn)確率。