一種基于稀疏搜索的激活噪聲快速聚類(lèi)算法

郭林亮，韓旭明，張逸航

(1.長(zhǎng)春工業(yè)大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，吉林 長(zhǎng)春 130012；2.暨南大學(xué)信息科學(xué)與技術(shù)學(xué)院，廣東 廣州 510632；3.長(zhǎng)春工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林 長(zhǎng)春 130012)

0 引言

聚類(lèi)分析是無(wú)監(jiān)督學(xué)習(xí)中的重要方法.在樣本沒(méi)有給定類(lèi)別信息的情況下，聚類(lèi)分析根據(jù)計(jì)算樣本特征的相似性來(lái)確定樣本的分組，同一分組的樣本具有高度的相似性，而來(lái)自不同分組的樣本之間相異度高[1].聚類(lèi)算法可以以無(wú)監(jiān)督的方式找到數(shù)據(jù)的特征分布結(jié)構(gòu)，所以研究者們提出了很多不同類(lèi)型的聚類(lèi)算法，并被廣泛應(yīng)用于以空間信息處理為代表的眾多領(lǐng)域[2]，例如，圖像分割、模式識(shí)別等[3-6].

大多數(shù)現(xiàn)有的聚類(lèi)算法在處理局部和非線(xiàn)性數(shù)據(jù)模式方面都有很大的局限性[7].針對(duì)形狀復(fù)雜、噪聲比較多的數(shù)據(jù)集，這些聚類(lèi)算法沒(méi)有很好地解決參數(shù)多且不易調(diào)節(jié)的問(wèn)題，且對(duì)噪聲和緊鄰類(lèi)之間的連接點(diǎn)的分配也不合理.

實(shí)現(xiàn)聚類(lèi)的眾多方法中，基于密度的聚類(lèi)方法是比較流行且高效的.文獻(xiàn)[8]利用密度可達(dá)的方式去鏈接eps鄰域獲得子簇；在此基礎(chǔ)上，研究者們提出了許多變體算法來(lái)獲得更好的聚類(lèi)性能[9]；文獻(xiàn)[10]提出了一種快速的近似KNN的算法來(lái)判斷和確定核心塊、非核心塊和噪聲塊；文獻(xiàn)[11](DPC)選取乘積較大的幾個(gè)點(diǎn)作為聚類(lèi)中心，從而確定類(lèi)的個(gè)數(shù)；文獻(xiàn)[12](FSDPC)設(shè)計(jì)了一種新的稀疏搜索策略來(lái)衡量每個(gè)數(shù)據(jù)點(diǎn)的最近鄰居之間的相似性；文獻(xiàn)[13]設(shè)計(jì)了一種數(shù)據(jù)點(diǎn)關(guān)聯(lián)度轉(zhuǎn)移方法和分層方法來(lái)選擇聚類(lèi)中心；文獻(xiàn)[14](DPC-DBFN)使用基于k近鄰的模糊核密度對(duì)決策圖進(jìn)行分區(qū)來(lái)確定類(lèi)的個(gè)數(shù)，同時(shí)分配邊界區(qū)域和噪聲；文獻(xiàn)[15]提出在一定半徑鄰域?qū)ふ易畲竺芏赛c(diǎn)，并把它們作為聚類(lèi)中心，避免了選擇聚類(lèi)中心個(gè)數(shù)的問(wèn)題；文獻(xiàn)[16]采用覆蓋樹(shù)的方法快速計(jì)算數(shù)據(jù)點(diǎn)密度；文獻(xiàn)[17]采用了樹(shù)的結(jié)構(gòu)獲得初始的子類(lèi)，再計(jì)算這些子類(lèi)的相似度來(lái)進(jìn)行層次聚類(lèi)；文獻(xiàn)[18]先采用近鄰的方式獲得基本的簇，再通過(guò)圖的方式進(jìn)一步分割這些簇；文獻(xiàn)[19]以共享近鄰的方式確定數(shù)據(jù)點(diǎn)的密度，并選擇密度最大的幾個(gè)數(shù)據(jù)點(diǎn)作為代表點(diǎn)進(jìn)行層次聚類(lèi)得出最后的聚類(lèi)結(jié)果.

以上的聚類(lèi)算法取得了一定的成就，但還存在以下不足：算法雖然減少了運(yùn)行時(shí)間成本，但卻降低了邊界點(diǎn)和噪聲分配的效率；在處理彼此靠近類(lèi)的連接處的點(diǎn)時(shí)，由于預(yù)設(shè)的參數(shù)較多，引起連鎖反應(yīng)導(dǎo)致噪聲點(diǎn)沒(méi)有有效分配，使聚類(lèi)結(jié)果出現(xiàn)偏差.

為了解決這些問(wèn)題，本文提出了一種基于稀疏搜索的激活噪聲快速聚類(lèi)算法(ANSC).本文算法利用數(shù)據(jù)總體離散度與個(gè)體近鄰屬性的關(guān)系重構(gòu)密度函數(shù)，把分布結(jié)構(gòu)復(fù)雜的數(shù)據(jù)點(diǎn)映射到簡(jiǎn)單的自定義密度函數(shù)上，通過(guò)觀察密度函數(shù)的性質(zhì)來(lái)激活潛在的噪聲.按照有規(guī)律的步長(zhǎng)規(guī)則快速尋找稀疏互連點(diǎn)，并以粗化和細(xì)化分割數(shù)據(jù)點(diǎn)的方式共建這些互連點(diǎn)形成子類(lèi)，利用子類(lèi)間距離的分布特性來(lái)合并.在獲得初步的聚類(lèi)結(jié)果后，根據(jù)噪聲的分布特點(diǎn)判斷是否形成新的目標(biāo)類(lèi).因此，對(duì)于不同形狀的數(shù)據(jù)集，針對(duì)如何處理噪聲、減少參數(shù)的數(shù)量和降低時(shí)間成本的問(wèn)題，本文提出了ANSC.

1 ANSC

1.1 激活噪聲

提出的算法使用近鄰的方式確定數(shù)據(jù)點(diǎn)的密度，這種方式可以反映數(shù)據(jù)的總體離散度和個(gè)體近鄰之間的關(guān)系.當(dāng)一個(gè)數(shù)據(jù)點(diǎn)與周?chē)c(diǎn)的距離和標(biāo)準(zhǔn)差較大時(shí)，它的密度會(huì)很小，甚至小于0.這種方式可以把分布結(jié)構(gòu)復(fù)雜的數(shù)據(jù)點(diǎn)映射到密度函數(shù)上，通過(guò)觀察函數(shù)的性質(zhì)挖掘潛在的噪聲.與神經(jīng)網(wǎng)絡(luò)中設(shè)置的激活函數(shù)的意義類(lèi)似，認(rèn)為在密度小于0的數(shù)據(jù)點(diǎn)是不需要被關(guān)注的點(diǎn)，并把這些點(diǎn)定義為噪聲，實(shí)現(xiàn)激活的作用.

為了減少重復(fù)的距離計(jì)算，算法采用快速k近鄰的方法(如kd-tree[20])，僅通過(guò)搜索近鄰以減少數(shù)據(jù)點(diǎn)間距離的計(jì)算次數(shù).此過(guò)程只設(shè)計(jì)一個(gè)易于調(diào)節(jié)的近鄰參數(shù)k.這種設(shè)置方式減少了聚類(lèi)過(guò)程中參數(shù)的數(shù)量.

假設(shè)數(shù)據(jù)集為X={x1，x2，…，xn}，其中n是數(shù)據(jù)點(diǎn)的個(gè)數(shù).數(shù)據(jù)點(diǎn)xi與所有近鄰距離的和Dis(xi)=sum(knn_dist(xi，：))，其中knn_dist(xi，：)代表數(shù)據(jù)點(diǎn)xi的近鄰距離的集合.定義Dis={Dis(x1)，Dis(x2)，…，Dis(xn)}.

借助數(shù)據(jù)近鄰和標(biāo)準(zhǔn)差與離散度的關(guān)系，定義了總體離散度Gdis的概念，定義為

(1)

其中：d是數(shù)據(jù)的維度，mean表示求數(shù)據(jù)的均值，max表示求數(shù)據(jù)的最大值，st是所有st(xi)的集合，st(xi)代表數(shù)據(jù)點(diǎn)xi與所有近鄰點(diǎn)的標(biāo)準(zhǔn)差.

為了體現(xiàn)數(shù)據(jù)個(gè)體與總體的離散關(guān)系，有效地確定噪聲，定義了數(shù)據(jù)點(diǎn)的密度函數(shù)為

(2)

從公式(2)可知，隨著總體離散度的增加，數(shù)據(jù)個(gè)體的密度在逐漸減小，當(dāng)密度小于0的時(shí)候，則認(rèn)定數(shù)據(jù)點(diǎn)為噪聲.如果一個(gè)數(shù)據(jù)集中密度小于0的點(diǎn)比較多，則數(shù)據(jù)集中的噪聲也很多，能夠反應(yīng)這個(gè)數(shù)據(jù)集的數(shù)據(jù)分布比較松散，為后續(xù)的識(shí)別和判斷噪聲的類(lèi)別提供了基本的保障.在實(shí)驗(yàn)中可以改變近鄰的個(gè)數(shù)來(lái)實(shí)現(xiàn)數(shù)據(jù)點(diǎn)密度的變化，從而確定不同的噪聲點(diǎn)和類(lèi)連接處的點(diǎn).

1.2 近鄰互連共建子類(lèi)

與現(xiàn)有的構(gòu)建子類(lèi)的方法不同，本文以步長(zhǎng)的方式稀疏搜索數(shù)據(jù)確定互連點(diǎn)，再以先粗化后細(xì)化的分割方法共建這些點(diǎn)形成子類(lèi).按照類(lèi)與類(lèi)的性質(zhì)，相似性大且距離比較近的點(diǎn)屬于一個(gè)類(lèi)的幾率更大.

基于以上想法，本文提出在一個(gè)隨機(jī)數(shù)據(jù)點(diǎn)的最大近鄰索引的基礎(chǔ)上，設(shè)置一個(gè)步長(zhǎng)去尋找下一個(gè)數(shù)據(jù)點(diǎn)的方法.同時(shí)，定義以這種方式尋找到的數(shù)據(jù)點(diǎn)為互連點(diǎn).如果互連點(diǎn)間滿(mǎn)足一定的閾值條件，就鏈接這些互連點(diǎn)形成子類(lèi)，這個(gè)過(guò)程叫作粗化共建.在此基礎(chǔ)上，為了進(jìn)一步分裂彼此靠近的類(lèi)，需要細(xì)化共建這些互連點(diǎn).選擇每個(gè)子類(lèi)中密度最大的點(diǎn)為代表點(diǎn)，代表子類(lèi)，并把這些代表點(diǎn)稱(chēng)為共建點(diǎn).

假定搜索到的互連點(diǎn)個(gè)數(shù)為n1，所有的數(shù)據(jù)點(diǎn)都是未訪(fǎng)問(wèn)點(diǎn).

粗化共建：找到第一個(gè)未訪(fǎng)問(wèn)的互連點(diǎn)xi及它的近鄰，在此基礎(chǔ)上，不斷尋找其他互連點(diǎn).若兩個(gè)數(shù)據(jù)點(diǎn)索引之間滿(mǎn)足以下條件，則停止粗化共建，并標(biāo)記這些互連點(diǎn)為已訪(fǎng)問(wèn)：

Index(xi)-Index(xc)

(3)

此時(shí)xc是當(dāng)前需要判斷類(lèi)別的數(shù)據(jù)點(diǎn)，Index(xi)代表數(shù)據(jù)點(diǎn)xi的索引.

細(xì)化共建：在粗化共建的基礎(chǔ)上，尋找未訪(fǎng)問(wèn)的第一個(gè)互連點(diǎn).若數(shù)據(jù)點(diǎn)索引之間滿(mǎn)足以下條件，則進(jìn)行細(xì)化共建，并標(biāo)記這些互連點(diǎn)為已訪(fǎng)問(wèn)：

(4)

其中：knnj(xi)表示離xi最近的第j個(gè)點(diǎn)，Round表示向上取整函數(shù).

1.3 識(shí)別和檢測(cè)噪聲

由共建點(diǎn)的定義可知，共建點(diǎn)是子類(lèi)中密度最大的點(diǎn).如果兩個(gè)共建點(diǎn)之間的距離小于共建點(diǎn)間的最小距離均值時(shí)，就認(rèn)為它們代表的子類(lèi)應(yīng)該屬于一個(gè)類(lèi)，所以需要合并一些相似度大的子類(lèi).這種合并的方式與層次聚類(lèi)相似，但是實(shí)現(xiàn)途徑是不同的.本文算法中類(lèi)的個(gè)數(shù)可以根據(jù)共建點(diǎn)的分布特點(diǎn)自動(dòng)地確定，無(wú)須的人為的干預(yù).對(duì)于所有的剩余點(diǎn)，未訪(fǎng)問(wèn)的點(diǎn)歸類(lèi)于最近的類(lèi).

為了減少噪聲對(duì)聚類(lèi)結(jié)果的影響，提出兩種分配噪聲的方法：一是連續(xù)出現(xiàn)噪聲的個(gè)數(shù)n3；二是噪聲與它的近鄰之間的關(guān)系.如果連續(xù)出現(xiàn)很多噪聲，則認(rèn)為這些噪聲可以構(gòu)成一個(gè)新的類(lèi)，并把它們定義為近類(lèi)噪聲.如果當(dāng)前噪聲與近鄰所屬的類(lèi)距離比較遠(yuǎn)，把這些點(diǎn)形成一個(gè)新的類(lèi)，并定義它們?yōu)檫h(yuǎn)類(lèi)噪聲.

假定當(dāng)前的聚類(lèi)結(jié)果中有n2個(gè)子類(lèi)，每個(gè)子類(lèi)中數(shù)據(jù)點(diǎn)的個(gè)數(shù)分別是{num1，num2，…，numn2}.

近類(lèi)噪聲：存在連續(xù)的噪聲，且它們的個(gè)數(shù)和為n3，如果滿(mǎn)足以下條件：

n3>(num1+num2+…+numn2)/n2.

(5)

遠(yuǎn)類(lèi)噪聲：假定噪聲為點(diǎn)noi，它與最近鄰點(diǎn)knn1(noi)的距離為Ndis，它的第k個(gè)近鄰為knnk(noi)，Kdis是knnk(noi)所有近鄰距離的平均值，滿(mǎn)足以下條件：

Ndis>n2*Kdis.

(6)

本文提出的算法由以上3個(gè)模塊組成，描述如下：

第1步：按照公式(2)獲取每個(gè)數(shù)據(jù)點(diǎn)的密度，根據(jù)密度的大小來(lái)確定噪聲點(diǎn)；

第2步：隨機(jī)選擇一個(gè)初始點(diǎn)，如果初始點(diǎn)的最大近鄰不是噪聲點(diǎn)，則把最大近鄰點(diǎn)認(rèn)為是第一個(gè)互連點(diǎn)，在此互連點(diǎn)的基礎(chǔ)上以4*k的步長(zhǎng)尋找下一個(gè)初始點(diǎn)；否則以2*k的步長(zhǎng)尋找下一個(gè)初始點(diǎn)，直到所有的數(shù)據(jù)點(diǎn)都被搜索結(jié)束；

第3步：通過(guò)第2步可以獲得很多個(gè)互連點(diǎn)，把所有的互連點(diǎn)組成一個(gè)新的數(shù)據(jù)集，在此基礎(chǔ)上獲得共建點(diǎn)，再按照公式(3)和(4)定義的方式獲得粗化共建和細(xì)化共建的子類(lèi)；

第4步：就近分配未訪(fǎng)問(wèn)點(diǎn)，按照公式(5)和(6)的原則去分配近類(lèi)噪聲或者遠(yuǎn)類(lèi)噪聲；

第5步：得到最后的聚類(lèi)結(jié)果.

1.4 時(shí)間復(fù)雜度分析

本文計(jì)算數(shù)據(jù)點(diǎn)密度的時(shí)間復(fù)雜度是O(nlogn).在近鄰互連共建子簇、合并子簇和分配剩余數(shù)據(jù)點(diǎn)的過(guò)程中，只計(jì)算互連點(diǎn)之間的距離，而互連點(diǎn)的個(gè)數(shù)遠(yuǎn)小于數(shù)據(jù)個(gè)數(shù)，所以這部分的時(shí)間復(fù)雜度不高于O(n).綜上所述，ANSC的算法的時(shí)間復(fù)雜度為O(nlogn)，小于對(duì)比算法的時(shí)間復(fù)雜度O(n2).

2 實(shí)驗(yàn)結(jié)果

2.1 實(shí)驗(yàn)對(duì)比

為了驗(yàn)證ANSC算法的有效性，使用最新聚類(lèi)研究中經(jīng)常使用的10個(gè)人工和真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).ANSC與最新的聚類(lèi)算法進(jìn)行了比較，包括算法FSDPC[12]、DPC-DBFN[14].為了排除對(duì)比算法在改變參數(shù)時(shí)對(duì)聚類(lèi)結(jié)果的影響，在實(shí)驗(yàn)過(guò)程中采取多次微調(diào)參數(shù)的方式，并選用最好的評(píng)價(jià)指標(biāo)作為聚類(lèi)結(jié)果.所有算法的實(shí)驗(yàn)都是在MATLAB 2018 a環(huán)境上實(shí)現(xiàn)的.所有數(shù)據(jù)集的信息如表1所示，它們都來(lái)自UCI 數(shù)據(jù)庫(kù).

表1 全部數(shù)據(jù)集

2.2 性能評(píng)估

為了進(jìn)一步比較3種聚類(lèi)算法在10種數(shù)據(jù)集上的聚類(lèi)方法可靠性和性能，本文使用3種常見(jiàn)的外部聚類(lèi)評(píng)價(jià)指標(biāo)，包括準(zhǔn)確度(ACC)、歸一化互信息(NMI)[21]、調(diào)整蘭德系數(shù)(ARI)[22].若這些指標(biāo)的值越大越好，越接近1，則表示聚類(lèi)算法的實(shí)際效果越好.在人工和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表2所示.

表2 3種算法在3個(gè)評(píng)價(jià)指標(biāo)上的結(jié)果

在實(shí)驗(yàn)中，算法采用的聚類(lèi)準(zhǔn)確度評(píng)價(jià)指標(biāo)ACC定義為

2.3 結(jié)果與分析

根據(jù)表2的實(shí)驗(yàn)結(jié)果可知，在解決不同形狀的人工和真實(shí)數(shù)據(jù)集時(shí)，所提出的算法都是可行的，提高了聚類(lèi)算法的性能指標(biāo)，并且3個(gè)性能評(píng)價(jià)指標(biāo)都是最高的.對(duì)于對(duì)比算法，算法DPC-DBFN的聚類(lèi)效果在解決非凸數(shù)據(jù)集時(shí)，效果是最差的；算法 FSDPC比DPC-DBFN展示了更好的聚類(lèi)結(jié)果，但是在解決密度不均勻的數(shù)據(jù)集時(shí)，兩個(gè)算法的聚類(lèi)結(jié)果表現(xiàn)都一般.

通過(guò)以上實(shí)驗(yàn)結(jié)果的分析，所提出的ANSC對(duì)非凸數(shù)據(jù)的邊界和類(lèi)連接處點(diǎn)的處理方式是有效的；從3個(gè)聚類(lèi)的評(píng)價(jià)指標(biāo)可知，相對(duì)于2個(gè)較新的對(duì)比算法，本文算法對(duì)非凸數(shù)據(jù)集是有效且高效率的聚類(lèi).

3 結(jié)論

本文針對(duì)聚類(lèi)算法中對(duì)噪聲和邊界分配不合理的問(wèn)題，提出了一種基于近鄰互連共建的ANSC.此算法包括3個(gè)核心部分：激活潛在的噪聲；以步長(zhǎng)的方式快速搜索互連點(diǎn)來(lái)達(dá)到共建子簇；判斷噪聲類(lèi)型.本文算法利用數(shù)據(jù)總體離散度與個(gè)體近鄰屬性的離散關(guān)系重構(gòu)具有代表性的密度函數(shù)來(lái)獲得噪聲；通過(guò)快速確定近鄰互連點(diǎn)來(lái)獲得新的共建數(shù)據(jù)點(diǎn)；通過(guò)噪聲的分布特點(diǎn)來(lái)優(yōu)化其類(lèi)別.

與較新的聚類(lèi)算法相比，在10個(gè)人工和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文提出的方法在噪聲和類(lèi)連接處點(diǎn)的合理分配問(wèn)題上是有效的和可靠的.在預(yù)設(shè)參數(shù)少和運(yùn)算時(shí)間成本低的情況下，提高了聚類(lèi)算法的效率和性能.