聚類中心自動確定的譜聚類算法研究

陳晉音,吳洋洋,林 翔

(浙江工業大學 信息工程學院,杭州 310000) E-mail:chenjinyin@zjut.edu.cn

1 引 言

譜聚類算法[1]是建立在譜圖理論基礎上的一種聚類算法,能在任意形狀的樣本空間上進行聚類.經典的譜聚類算法有Ng、Bach和Jordan等人提出的多路譜聚類方法[3],Meila等人提出的多路歸一化割譜聚類算法[4]以及Elhamifar等人提出的稀疏子空間譜聚類算法[5].Fowlkeset等人提出了Nystr?m[6]算法,降低了譜聚類算法的時間復雜度和空間復雜度,其聚類效果依賴于初始點的選取.L Zelnik-Manor等人提出了自適應譜聚類算法[8](STSC),提出將局部尺度參數應用到數據點之間的相似度計算.Zhao F等人利用模糊C-means聚類得到的劃分矩陣提出了模糊相似度度量譜聚類算法[9](FSSC),能很好的處理現實中相似度不確定性的問題.Wang 等人提出一種能自動確定類別的譜聚類算法[10](ACNA),該算法能夠確定出聚類個數,但在進行特征分解的時候計算代價較大.H Ning等人提出了增量譜聚類[11](ISC)算法,該算法能夠使得動態數據所對應的相似度值也能夠動態更新,而且這個算法的時間復雜度相對較低,但其聚類準確率與初始聚類個數的設定有較大關系,如果人工設定的聚類個數不準確,則聚類誤差較大.Yan D等人提出了快速近似譜聚類算法[12](FASC),該算法在降低了時間復雜度的基礎上,增加了聚類準確率,但也需要預先設定聚類個數;X Chen等人提出了基于標志點的譜聚類算法[13](LSC),該算法選取標志點來近似的表示整個數據集,減少了算法的空間復雜度,但是該算法特別依賴于標志點的選擇.R Xia等人提出了穩定多視角譜聚類[14](RMSC)算法,能夠消除數據集中噪聲點的干擾,且對參數并不敏感.Li Y等人提出了密度譜聚類[15](SC-D)算法,該算法選擇高密度的點作為初始點,構造基于密度的相似度矩陣,能夠在聚類的時候顯示出來良好的穩定性和較好的聚類效果,但其空間復雜度過高,且需要人工設定聚類個數.

在實現自動確定聚類個數的算法中,近鄰傳播算法[16](AP)算法是其中較為經典的一種算法,該算法依據數據點之間的相似度進行自動聚類.Dong等人提出了可變相似性度量的近鄰傳播算法[17](AP-VSM),該算法在AP算法的基礎上改進了相似度矩陣,提高了聚類效果.R Jin等人提出了基于近鄰傳播的改進半監督聚類算法[18](SAP-LC),該算法不僅提高了算法的聚類效果,而且降低了算法的迭代次數.

綜上所述,目前的譜聚類算法主要存在以下三個問題:

1)難以選取合適的尺度參數來很好的反應復雜數據集的空間分布特點;

2)需要預先設定聚類個數,在實際應用中很難提前人工設定類標的準確個數;

3)譜聚類算法中參數依賴性較大,參數的選取直接影響聚類的結果.

針對這三個主要問題,本文提出基于臨近點法的聚類個數自動確定譜聚類算法(ADNC-SC),本文的主要工作如下:

1)針對難以選取合適的尺度參數來反應復雜數據集的空間分布特點,采用數據點與其臨近點的距離均值來定義數據點的局部尺度參數,通過數據點的局部特征反映整體的數據結構.

2)針對譜聚類方法需要預先設定聚類個數,而大多數應用存在無法預先獲得數據對象的準確聚類別個數的問題,ADNC-SC可實現聚類個數自動確定,通過分析數據對象的密度和距離分布規律,采用正態擬合確定奇異點,理論證明奇異點即為聚類中心.

3)針對譜聚類算法中參數依賴性較大的問題,設計Fitness函數,依據Fitness函數評價不同臨近點個數所對應的聚類結果,選取最優臨近點個數,并依據空間復雜度閾值以及算法的時間復雜度和空間復雜度的關系確定劃分區間個數.

2 聚類中心自動確定的譜聚類算法(ADNC-SC)

ADNC-SC算法的主要工作是依據數據點的局部特征確定局部尺度參數,通過分析數據對象分布規律確定聚類中心,設計Fitness函數確定最優臨近點個數以及依據時間復雜度和空間復雜度的關系確定劃分區間個數,分別在本小節做詳細的闡述.

2.1 局部尺度參數

譜聚類算法的相似度度量是采用高斯核函數,然而這個度量的明顯缺陷是高斯核函數中尺度參數的取值非常敏感.因此,選擇合適的尺度參數進行度量成為譜聚類算法中十分關鍵的問題.

我們通過臨近點法將數據點所對應的局部尺度參數σi的取值定義為該數據點與其t個臨近點之間的距離均值,如公式(1)所示:

(1)

其中d(i,j)表示數據點i與其第j個臨近點的距離.

由當前局部尺度參數的定義可得,當前相似度函數計算公式為:

Sij=exp(-‖d(i,j)‖2/(2max(σi,σj)))

(2)

利用所定義的每個數據點的局部尺度參數代替高斯核函數的單個尺度參數,能準確分離出稀疏背景數據簇內所包含的緊密簇.

本文選擇使用基于臨近點法的稀疏相似度矩陣[19]代替完整的相似度矩陣進行存儲,能有效的降低算法的空間復雜度,而且依據臨近點法所定義的局部尺度參數能夠通過數據點的局部特征優化稀疏相似度矩陣,有效的反映數據結構,優化聚類效果.

2.2 自動確定聚類中心算法(ADNC)

2.2.1 算法主要思想

本文在Alex等人的基于密度的快速聚類算法[20]的基礎上,通過分析數據對象的密度-距離的分布特征,構建正態分布函數擬合確定聚類個數.

為了降低算法的空間復雜度,在計算密度和距離這兩個變量的時候都是使用局部距離矩陣進行計算,而且對這兩個變量的定義進行適當的修改:

定義1.(局部密度)對于任意數據對象i,其局部密度計算方法為:

(3)

(4)

其中,m矩陣是由距離矩陣中最小的npercent個距離值組成,percent表示鄰居點個數占總數據點距離個數的比例,d(i,j)表示點i和點j之間的距離.在每個計算區間距離矩陣的同時,利用該區間距離矩陣逐個與m矩陣中仍保留的距離值比較,每次比較只將其中npercent個最小距離值保留在m矩陣中,直到處理完所有區間距離矩陣為止.

定義2.(最小距離)對于任何對象,利用其臨近點的局部密度與該點密度進行比較,若臨近點中沒有點的局部密度大于該點密度,則將該點判斷為候選點,其中只有候選點有可能成為聚類中心點,候選點的最小距離為該點到密度更高點的最小距離的計算如公式(5)所示;否則將該點判斷為非候選點,該點的最小距離為密度比它大的臨近點中距離最近的臨近點距離.

(5)

其中DNi表示數據點i與所有數據點中局部密度比它高的點距離值集合,ρi表示點i的密度,ρmax表示數據點最大局部密度,max(δ)表示最大距離值.

存在樣本數據集DataSet1,其二維空間內數據分布如圖1所示.計算樣本數據集中每個數據點的局部密度ρ和到密度更高點的最小距離δ,繪制出ρ-δ分布圖.數據分布與數據對象ρ-δ分布存在映射關系,如圖1所示.

圖1 樣本數據分布圖與ρ-δ分布圖的映射關系Fig.1 Mapping relationships between the data distribution of the dataset and ρ-δ distribution

其中,A1、A2、A3是上圖中的三個聚類中心,他們在ρ-δ分布圖中表現出了較大的ρ值和δ值;對于其他點,稱其為邊界點,他們在ρ-δ分布圖中表現出較小的ρ和δ值.

基于以上對ρ-δ圖的分析,本文引入變量γ,對于任意一個數據點i,其γi定義為:

γi=ρi×δi

(6)

根據γ的概率分布情況,對于該γ的分布進行曲線的擬合[21],發現其圖形的擬合曲線形狀類似于一條正態分布曲線.現利用選取置信區間的方式在與擬合曲線相應的正態分布曲線中尋找出奇異點的信息,此處奇異點表示落在置信區間以外的點.

考慮到奇異點中可能存在ρ和δ的相對指標相差較大的點,也就是所謂的噪聲點或者密度值較大而最小距離較小的點,故在此還需對奇異點進行一次篩選以確定最終的聚類中心.篩選方法為:

2.2.2 正態分布分析確定奇異點

正態曲線的數學期望為μ、方差為σ2.實際工作中,總體方差已知時,樣本平均數的分布為正態分布或漸近正態分布.查表可知,樣本落在一個抽樣標準差范圍內的概率為68.268949%;落在兩個抽樣標準差范圍內的概率為95.449974%;落在五個抽樣標準差范圍內概率為99.99999999≈1.當樣本容量不是特別大的時候,可認為隨機變量的X的所有取值包含在在五個抽樣標準差范圍內,即當置信區間為(μ-5σ,μ+5σ)時,未落在該區間內的點即為不服從該正態分布的奇異點.

2.2.3 正態擬合曲線的均值與標準差的確定

(7)

2.3 參數自適應

2.3.1 最優臨近點個數的自動確定

臨近點個數的選擇和稀疏相似度矩陣的結構息息相關,也就是說臨近點個數的選取會對聚類結果產生影響.本文設計了一個Fitness函數作為比較不同臨近點個數所對應的聚類結果的評價指標.

Fitness函數由兩部分組成:

(8)

(9)

其中n表示數據集數據量,K表示簇的個數,Ci和Cj表示第i個簇和第j個簇的聚類中心.

從公式(8)和公式(9)可以看出,Fitness1表示數據集的簇內距離均值,Fitness2表示數據集的簇間距離均值.根據聚類效果好壞的最本質定義:簇內距離越小越好,簇間距離越大越好.因此Fitness函數的定義為:

Fitness=Fitness1/ Fitness2

(10)

對于一個給定的臨近點個數,Fitness函數值越小,表示聚類效果越好.

2.3.2 劃分區間個數的確定

ADNC-SC算法將數據集劃分成多個區間,再計算區間距離矩陣,這樣能夠降低了計算稀疏相似度矩陣的空間復雜度.其中與劃分區間個數相關的步驟主要是稀疏相似度矩陣的計算,該部分的時間復雜度為O(nmb+nblog(t)),而ADNC-SC算法的空間復雜度為O(n2/b),其中n表示數據集的數據量,m表示數據維數,b表示劃分區間個數,t表示臨近點個數.由于處理數據時,計算機的存儲空間有限,所以算法的空間復雜度應該小于空間復雜度的閾值O(Smax).

本文定義了一個選取劃分區間個數的方法:

(11)

證明:將時間復雜度和空間復雜度分別定量化,得到算法時間復雜度值為Space=nmb+nblog(t),空間復雜度值為T=n2/bTime=n2/b.

在這里我們定義復雜度和函數L:

L=Space+Time=nmb+nblog(t)+n2/b

(12)

以區間個數b為自變量對復雜度和函數L求兩次導數:

(13)

但是為了保證算法的空間復雜度S滿足S≤O(Smax)的條件,即滿足b≥n2/Smax,那么選取區間劃分個數需要考慮以下兩種情況:

1)如果bbest≥n2/Smax,即(n3(m+log(t)))1/2>Smax時,那么可以選取劃分區間個數b=bbest,使得當前算法的空間復雜度在沒有超過空間復雜度閾值Smax的情況下,保證了當前的時間復雜度和空間復雜度的總代價和最小;

2)當bbest

2.4 ADNC-SC算法詳述描述

根據Science上Alex[20]算法,鄰居點個數占總數據點距離個數的比例percent的取值為1%-2%時,聚類個數的確定較為準確.

圖2 ADNC-SC算法流程圖Fig.2 Flow chart of ADCN-SC

通過上文的分析,ADNC-SC算法流程圖如圖2所示,其具體步驟為:

Step1.對輸入數據預處理,并確定劃分區間個數;

Step2.依據臨近點法計算出區間稀疏距離矩陣和局部尺度參數,通過所有區間稀疏距離矩陣和相似度函數計算公式得到整體稀疏相似度矩陣;

Step3.調用ADNC算法,自動確定出聚類個數K;

Step4.選出K個最大的特征值所對應的特征向量;

Step5.對所選的特征向量進行K-means聚類,得到當前的聚類結果;

Step6.計算當前臨近點個數的Fitness函數值;

Step7.對臨近點個數進行不斷迭代,計算出區間內每個臨近點個數對應的Fitness函數值,通過比較選擇出最優臨近點個數;

Step8.輸出最優臨近點個數所對應的聚類結果.

3 實驗結果與分析

實驗中的操作系統為Windows 7,集成開發環境為MATLAB R2012b.硬件條件為:CPU為Intel Core I5 2.5GHz,內存為4GB.在當前實驗條件下,最大存儲元素個數為1.6797×109,ADNC-SC算法空間復雜度的閾值O(Smax)設置為O(109).

本文算法測試了十個來自UCI及其學習庫的數據集,數據集的具體信息如表1所示:

表1 十個真實數據集信息Table 1 Information of the ten real data sets

3.1 聚類結果評價指標

本文使用兩個評價指標衡量算法性能:聚類準確率和聚類純度.

1)聚類準確率的定義為:

(14)

其中ai表示被正確分類的樣本個數,K表示聚類個數,n表示數據集的樣本個數.

2)聚類純度的定義為:

(15)

3.2 ADNC-SC算法的聚類結果分析

在二維坐標圖將ADNC-SC算法處理Aggregation數據集、Jain數據集、Spiral數據集、Flame數據集和等二維數值型數據集得到的聚類結果展示出來,聚類結果如圖3所示.

3.2.1 自動確定聚類中心的實驗分析

自動確定聚類個數的實驗分析中,首先獲得數據集內所有數據點的ρ-δ分布圖,如圖4所示;然后通過數據點的ρ-δ分布圖找出數據點的γ值概率分布圖,如圖5所示;接著通過對γ值概率分布圖進行擬合曲線,得到相應的正態擬合圖,找出置信區間,如圖6所示,其中虛線為找到的置信區間;通過得到的置信區間在γ值概率分布圖上確定在置信區間外的奇異點,圖5中的虛線為已確定的置信區間;最后在ρ-δ分布圖中,做出斜率分別為η和1/η的兩條直線,選取得到落在兩條直線之間的奇異點.通過實驗數據集分析,一般η=3時能有效排除奇異點中的干擾信息,較為準確地選出真正的聚類中心.

3.2.2 最優臨近點個數選取分析

從論文和多組數據集的測試表明,對于一個數據量為n的數據集,當臨近點個數的取值在范圍[3,6+‖log(n)‖]內時,算法的聚類結果相對較好,其中‖log(n)‖表示log(n)取整數.

從圖7可以看出來,Fitness函數值越小,且ADNC-SC算法所對應的聚類準確率則越高,當Fitness函數值最小的時候,對應的聚類準確率最高.

(a) Aggregation數據集 (b) Jain數據集 (c)Spiral數據集 (d) Flame數據集

3.3 ADNC-SC算法與各種算法的比較

3.3.1 各種算法的聚類效果的對比

表2對比ADNC-SC算法與SC算法、SC-D算法、NJWN算法和STSC算法在表1中的十個真實數據集上的聚類準確率.

圖4 4個數據集的ρ-δ分布圖Fig.4 ρ-δ distribution of four datasets

從表2可以看出,SC算法、SC-D算法、NJWN算法和STSC算法的聚類準確率都明顯低于ADNC-SC算法,而且NJWN算法特別依賴于初始點的選擇,使得算法的聚類穩定性較差,所以在處理其中一部分數據集時聚類結果較差.ADNC-SC算法處理十個真實數據集所得的聚類純度分別為:99.26%,99.72%,100%,94.73%,100%,99.07%,98.73%,94.16%,95.92%和96.78%.也就是說,ADNC-SC算法的聚類效果較為優秀.

實驗證明:ADNC-SC算法與這些對比算法比較起來,均能得到相對更好的聚類效果,其原因在于:

圖5 4個數據集的γ值概率分布圖Fig.5 Density distribution of γ of four datasets

1) 所定義的局部尺度參數代替整體尺度參數,能夠更好的反應數據集的空間分布特點,從而得到更好的聚類效果;

2)依據臨近點法得到的稀疏相似度矩陣能夠增大類內數據點的相似度,減小類間數據點相似度,使聚類效果更優秀.

圖6 四個數據集的正態擬合圖Fig.6 Normal distribution curve of four datasets

3.3.2 各種算法的算法平均執行時間和時間復雜度的對比和分析

圖8給出了ADNC-SC算法和SC算法、SC-D算法和STSC算法的算法平均執行時間.

ADNC-SC算法的時間復雜度主要是由相似度矩陣計算、自動確定聚類個數、K-means聚類以及最優臨近點個數的確定等四部分構成.在計算稀疏相似度矩陣的時候,將m維的n個數據分成b個區間分別進行計算,得到臨近點個數為t的稀疏相似度矩陣,其時間復雜度為O(nmb+nblog(t));自動確定聚類中心的時間復雜度為O(nt);K-means聚類部分的時間復雜度為O(nK2),其中K表示聚類個數;最后,計算Fitness函數的時間復雜度為O(nK),而確定最優臨近點個數所需迭代次數為tn.總的來說,ADNC-SC算法的時間復雜度為O(tn(nmb+nblog(t)+nt+nK2+nK)).

圖7 六個數據集中的Fitness函數值與聚類準確率之間的變化關系Fig.7 Relationship between the values of the Fitness function and the accuracy of clustering in the six data sets

表2 各種算法在十個真實數據集上的聚類準確率對比(%)Table 2 Comparison of clustering accuracy of various algorithms on ten real data sets(%)

在表3中,n表示數據個數,m表示數據維數,b表示區間個數,t表示臨近點個數,K表示聚類個數,p表示迭代次數,l表示在NJWN算法中的抽樣個數,tn表示臨近點迭代次數.

圖8 各種算法的算法平均執行時間對比Fig.8 Comparison of the average execution time of the algorithms of various algorithms

本文利用迭代的方式尋找最優臨近點個數,使得ADNC-SC算法的時間復雜度會偏高.但與這些對比算法相比,ADNC-SC算法聚類準確率相對較高,且能夠準確的自動確定聚類個數,從而在一定程度上彌補了時間復雜度偏高的缺點.

3.3.3 各種算法空間復雜度的對比和分析

在表4中,數據量為n,聚類個數為K,樣本點個數為l,區間個數為b.ADNC-SC算法的空間復雜度主要是計算區間距離矩陣的空間復雜度O(n2/b).SC算法、SC-D算法和STSC算法都需要計算整個相似度矩陣,則這些算法的空間復雜度都為O(n2).NJWN算法將計算相似度矩陣所需的空間復雜度降低為O(l2).總的來說,相對于SC算法、SC-D算法和STSC算法的空間復雜度,ADNC-SC算法的空間復雜度明顯較低.而相對于NJWN算法,當抽樣個數較小時,NJWN算法空間復雜度會低于ADNC-SC算法的空間復雜度.

表3 多種算法的時間復雜度Table 3 Time complexity of multiple algorithms

表4 多種算法空間復雜度Table 4 Space complexity of multiple algorithms

4 基于ADNC-SC的人臉識別應用

在人臉識別領域,大多人臉識別方法需要已知不同類別的人臉圖像分類情況,并提取足夠的樣本數據進行訓練,利用訓練得到的模型對其他人臉圖像進行分類和識別.ADNC-SC算法能夠在分類情況未知的時候,對人臉數據集進行分類和識別.

4.1 人臉數據集介紹

在本次實驗中,測試了兩個人臉數據集:Olivertti人臉數據集與Yale人臉數據集.

Olivertti人臉數據集包含40個人,每個人有10張64×64的人臉灰度圖像.選取Olivetti人臉數據集中10個人的人臉圖像,每個人選10張,組成100張人臉圖像的Olivertti圖像測試數據集.

Yale人臉數據集,由耶魯大學計算視覺與控制中心創建,包含15位志愿者的165張人臉圖片.圖10為Yale人臉庫上某人的11張人臉圖像.

圖9 Olivertti數據集上某人的10張人臉圖像示例Fig.9 10 face images of someone on the Olivetti dataset

4.2 ADNC-SC算法處理人臉數據集的算法流程

ADNC-SC算法處理人臉數據集的步驟:首先對人臉圖像進行劃分區間,利用SSIM算法[7]計算出圖像之間的相對距離,并利用臨近點算法計算出圖像的所有區間稀疏距離矩陣和局部尺度參數;根據所有區間稀疏距離矩陣和相似度函數計算公式計算得到稀疏相似度矩陣;調用ADNC算法確定聚類個數,并將拉普拉斯矩陣進行特征分解,選取合適的特征向量;對所選特征向量進行K-means聚類,得到聚類結果;最后利用Fitness函數值確定最優臨近點個數,并輸出所對應的聚類結果.

圖10 Yale上某人的11張人臉圖像示例
Fig.10 11 face images of someone on the Yale dataset

圖11 Olivetti人臉測試數據集的實驗過程和結果Fig.11 Olivetti face test data set of the experimental process and result

圖12 Yale人臉數據集的實驗過程和結果Fig.12 Yale face test data set of the experimental process and result

4.3 ADNC-SC算法處理人臉數據集的實驗結果分析

圖11和圖12分別為ADNC-SC算法處理Olivetti人臉測試數據集和Yale人臉數據集的實驗過程和結果.ADNC-SC算法首先依據所得到的Olivetti數據集的ρ-δ分布圖確定出γ值概率分布圖,如圖11(a)和圖11(b)所示;接著依據圖11(b)的γ值概率分布圖擬合正態曲線,如圖11(c)所示;在圖11(b)的γ值概率分布圖中,根據正態分布曲線的5σ原則選取出來在置信區間外的所有奇異點;再對奇異點進行篩選確定的聚類中心點,如圖11(a)為最后確定的Olivetti數據集的10個聚類中心點.ADNC-SC算法處理Olivetti人臉數據集的識別準確率能夠達到94.67%左右.

同理,從圖12(a)、圖12(b)和圖12(c)的自動確定聚類個數的分析過程可以看出來,ADNC-SC算法能夠識別出Yale人臉數據集中的14個人臉對象.從實驗結果圖12(d)可以看出來,由于第二類人臉數據和第十三類人臉數據存在較多的相似特點,所以ADNC-SC算法無法準確的將這兩類人臉圖像區分開來.總的來說,ADNC-SC算法處理Yale人臉數據集的識別準確率能達到87.27%左右.

實驗結果表明,ADNC-SC算法對人臉圖像具有較好的識別能力,也基本上能夠識別出人臉圖像聚類個數,但仍然有一部分的識別錯誤.總的來說,在沒有任何訓練的情況下,ADNC-SC算法具有較好的識別能力.

5 結 語

本文針對譜聚類算法難以選取合適的尺度參數,需要人工輸入聚類個數和參數依賴性較大等問題提出了一種基于臨近點法的聚類個數自動確定譜聚類算法.無論是從真實數據集的實驗還是從人臉數集的實驗中,我們都可以看出來,該算法不僅提高了聚類的質量,使得聚類的結果更加準確,而且能夠準確的識別出數據集的聚類個數.但是ADNC-SC算法的算法時間復雜度相對較高,對處理數據量較大的數據集時,仍然存在一定的局限性,所以下一步的研究重點是進一步的降低算法的復雜度,特別是時間復雜度方面.