基于成對約束的SubKMeans聚類數確定算法①

高 波,何振峰

(福州大學 數學與計算機科學學院,福州 350108)

聚類是一種無監督學習方法,它根據樣本間相似度把樣本劃分到若干簇[1].K-Means 算法是聚類算法的一種典型代表,它因其簡單而又有效的特性備受歡迎,并且在十大經典數據挖掘算法中排名第二[2].該算法根據用戶指定的K值,基于某種距離度量方式,把樣本劃分為K個不同的簇,使得簇內樣本相似性高,簇間樣本相似性低[1].高維數據空間中數據分布稀疏且存在著大量無關屬性,數據的重要結構信息會隱藏在海量的噪聲數據中,因此使用K-Means 算法在高維數據上進行聚類很難發現數據的內在結構,使得聚類效果差[3,4].然而在現實的聚類分析應用場景中,數據維度通常很高,比如圖片視頻或文本數據,其維度一般為千萬級,甚至更高.針對這一問題,Mautz 等人于2017年提出了SubKMeans 算法[5],該算法能夠將數據映射到子空間中進行聚類,降低維度影響,提升K-Means 類算法聚類性能.

SubKMeans 算法將數據空間劃分為一個包含有大部分重要信息的子空間和一個基本不包含重要信息的子空間,通過映射矩陣能夠把數據投影到包含有大部分重要信息的子空間中進行聚類,從一定程度上減輕“維度災難”對K-Means 類算法的影響.但是SubKMeans算法只是對經典K-Means 類算法的一種擴展,它依然會受到K-Means 類算法固有缺陷的限制[6].SubKMeans算法是無監督聚類算法,需要用戶事先指定K值,而在現實中部分數據集的種類數是未知的,這給使用者帶來巨大的困擾,因此SubKMeans 算法的聚類數確定研究具有重要的現實意義.

現有的子空間聚類算法可以劃分為硬子空間聚類和軟子空間聚類[7,8].硬子空間聚類把所有屬性都看成同等重要,按照搜索子空間方式的不同,可以進一步劃分為自底向上的子空間聚類算法和自頂向下的子空間聚類算法.軟子空間聚類算法認為每個屬性對于每個簇的貢獻程度不一樣,因此給每個屬性賦予不同的權重.文獻[9]和文獻[10]中提出基于懲罰機制的競爭學習來逐步合并聚類簇,消除冗余聚類,最后為子空間聚類確定聚類數目.文獻[11]基于類內緊湊性和類間分離性提出了一種新的聚類有效性指標,通過在K的取值范圍內得出最佳指標值來為子空間聚類確定K值.文獻[12]把現有的K值確定方法分為3 類,分別為傳統方法、基于合并分裂方法和基于進化的方法.傳統方法把最佳聚類有效性指標對應的K值作為最佳K值.基于合并分裂的方法根據聚類有效性指標的值是否更優來決定是否合并或分裂,達到穩定時的K值即為最佳K值.基于進化的方法使用特定的編碼方式將可能的劃分方式編碼到個體或染色體中,通過遺傳變異的方式得到適應性最好的個體,把該個體對應的K值作為最終K值.

為解決SubKMeans 聚類數確定問題,考慮到現實中有時能獲取到類似成對約束之類的監督信息,參考文獻[13]中成對約束與輪廓系數的結合方法,用成對約束改變輪廓系數計算方式,并用成對約束的滿足度給輪廓系數加權.將改進后的輪廓系數作為聚類有效性評價指標,通過嘗試不同的K值來找到一個最佳指標值,把該最佳指標值對應的K值作為最佳K值.第1 節介紹SubKMeans 算法,第2 節介紹改進的SubKMeans算法,第3 節對改進算法進行實驗并分析實驗結果,第4 節對所做工作進行總結.

1 SubKMeans 算法簡介

SubKMeans 算法又稱子空間K均值算法,它通過尋找數據的最佳子空間來發現數據的隱藏結構,降低維度影響,使得K-Means 類算法在高維數據上也能夠有不錯的表現[5].它的主要思想是：假設在一個數據集中大部分重要的信息會隱藏在某一個維度更低的子空間中,而其它的子空間能夠提供的有用信息很少.根據這一假設把數據空間劃分為兩個子空間,包含大部分重要信息的子空間稱為聚類子空間,基本不包含重要信息的子空間稱為噪聲子空間[5].為了提高聚類性能,挖掘出數據的內在結構,需要把數據映射到聚類子空間上進行聚類.

給定數據集D={x1,x2,···,xn}∈Rd×n,其中n是數據集D的規模,d是樣本的維度.假設要把數據聚為K個簇在經典K-Means 算法中,最優化目標是使得每個樣本到其聚類中心點的距離總和最小[1,5],即優化下式：

其中,ui為第i個簇的簇中心,‖·‖表示歐幾里得范數.SubKMeans 算法需要將樣本映射到聚類子空間中進行聚類,兩個樣本在聚類子空間中的距離可以通過式(2)計算.

其中,PC∈Rm×d,m為聚類子空間維度且m＜d,V∈Rd×d是一個維度為d的正交矩陣.通過能夠將樣本x映射到聚類子空間中,PC定義為：

其中,Im是維度為m的單位矩陣,Od?m,m∈Rm×(d?m)為零矩陣.重新定義樣本間距離計算公式后,SubKMeans優化目標可以表示為：

其中,PN∈R(d?m)×d,(d?m)為噪聲子空間維度,uD∈Rd×1為數據集D的列均值.將式(4)展開,利用矩陣跡的特性,可以表示為：

其中,Tr表示矩陣的跡,V是一個正交矩陣,根據正交矩陣的特性,可知VTSDV相乘后,只改變矩陣SD特征向量的方向,不改變其特征值本身.因此對于任意的正交矩陣V,VTSDV的特征值是常量.矩陣的跡是其所有特征值之和,所以是一個常量,在式(5)中可以忽略.令矩陣V為SiD特征分解后的特征向量,并且這些特征向量按照特征值的大小進行升序排序,最小的m個特征值對應的特征向量將數據映射到聚類子空間中,其它(d?m)個特征值對應的特征向量將數據映射到噪聲子空間中,令m為SiD特征分解后特征值中小于0 的個數,可解決(4)的最優化問題.使用式(2)計算樣本距離,不斷迭代更新簇中心,更新矩陣V和子空間維度m,算法最終趨于穩定得到固定維度的聚類子空間和聚類簇.SubKMeans 算法框架如算法1 所示.

算法1.SubKMeans 算法輸入：數據集D,聚類數量K{C1,C2,···,CK}輸出：聚類簇,正交變換矩V,聚類子空間維度m m=■d/2」■」1)初始化聚類子空間維度 // 表示向下取整2)計算數據集列平均uD 3)采用式(8)計算數據集的散列矩陣ui,i=1,2,···,K S D 4)隨機產生初始聚類中心5)隨機矩陣執行QR 分解產生正交矩陣V 6)While(簇中心改變)x∈D 7)for each 8)采用式(2)計算樣本到簇中心的距離9)將樣本劃分到距離最近的簇10)end for ui 11)更新簇中心12)采用式(7)計算簇的散列矩陣V,ε=eig(S iD)ε S i 13)更新矩陣 // eig 表示特征分解,V 為特征分解后的特征向量,為特征值m=|{e|e∈ε,e＜0}| ||14)更新維度 // 表示取集合中元素個數15)end while

雖然SubKMeans 算法能夠自動確定聚類子空間維度,但需要用戶指定聚類數量K.聚類數的確定是實際應用中的一個重大問題,因為在實際的應用場景中,需要聚類的數據往往是未知數據,我們不知道哪些數據應該分配到同一類中,對于給出的K值,我們也無法驗證其是否是當前數據的準確K值.

2 基于成對約束的SubKMeans 聚類數確定算法

輪廓系數是一種常用的聚類有效性指標,可用于確定K值.在輪廓系數的計算方式中,聚類的輪廓系數為數據集中所有樣本的輪廓系數的平均值,其把每個樣本看成同等重要,把該指標作為聚類有效性指標用于確定聚類數量時,往往效果不好.而在實際的聚類過程中,存在部分樣本對簇的貢獻程度不一樣的情況.為了體現這種差異,基于文獻[13],本文引入成對約束,用輪廓系數的滿足度給單個樣本和整個聚類進行加權,并將違反的成對約束作為懲罰項,改進輪廓系數的計算方式,為SubKMeans 算法提出一種成對約束與輪廓系數結合的K值確定方法,稱為Constrained Weighted SubKMeans,簡稱CSWKM.CSWKM 算法把改進后的輪廓系數作為一種新的聚類有效性指標,在K的取值范圍內,計算出各個K值時的指標值,把最佳指標值對應的K值作為最佳K值.CSWKM 算法框架如下算法2所示.

算法2.CSWKM 算法輸入：數據集D,成對約束Cst,最大迭代次數Count{C1,C2,···,CK}輸出：聚類簇,正交變換矩V,聚類子空間維度m,聚類數量K 1)for to 2)SubKMeans 算法 //迭代時需判斷迭代次數是否超過限制3)if (簇迭代次數小于Count)4)采用式(13)計算出此次劃分的輪廓系數5)if(計算得出的輪廓系數小于0)6)令輪廓系數為0 7)else 8)令此次劃分的輪廓系數為0 9)end for K=Kmin Kmax

CSWKM 需要分別計算出各個K值時的輪廓系數值,把最大輪廓系數對應的K值作為最終K值.在計算單個K值的輪廓系數時,需要迭代更新簇中心點、更新矩陣V和子空間維度m,同時在進行迭代時需要先判斷當前迭代次數是否超過最大迭代次數,若超過,則停止迭代.Kmin一般取2,Kmax根據經驗為樣本數量的平方根取整,算法輸出部分中,簇 {C1,C2,···,CK}、V和m對應于最佳K值的簇、V和m.與SubKMeans算法相比,CSWKM 算法對簇的迭代次數進行了限制,計算了每次簇劃分后對應的輪廓系數值.

2.1 簇迭代次數限制

CSWKM 算法不同于SubKMeans 算法,CSWKM算法需要嘗試K值范圍內的每個K值.由于CSWKM算法中對簇的個數進行了限制,強制每個簇里面的樣本個數必須大于5,在實驗中發現當給出的K值與實際的K值相差較大時,會出現劃分簇的迭代次數過多或者不收斂的現象.為了解決這一問題,給簇的迭代加上次數限制,使得超過迭代次數的K值劃分認為是不合適的劃分,直接令此次K值劃分的簇輪廓系數為0,一般情況下令迭代次數為50.

2.2 輪廓系數

輪廓系數是目前使用最為頻繁的聚類有效性評價指標之一,其要求同一個簇內樣本間距離小,相似性高,不同簇間距離大,相似性低[13,14].聚類的輪廓系數為數據集中所有樣本的輪廓系數平均值,單個樣本x的輪廓系數計算公式如式(9)所示：

其中,a(x)表示樣本x與其所屬簇的其他樣本之間的平均距離,為類內距離,b(x)表示樣本x到其他簇的平均距離中的最小值,為類間距離.

單獨使用輪廓系數作為聚類有效性評價指標效果并不理想,基于樣本對簇的貢獻程度不同,本文引入監督信息對輪廓系數進行改進.監督信息可以分為兩類,一類是數據樣本類別標簽,另一類是數據樣本之間的成對約束信息.成對約束一般是指must-link與cannotlink兩種關聯約束關系,正關聯約束關系must-link(x,y)表示樣本x和樣本y屬于同一類,負關聯約束關系cannotlink(x,y)表示樣本x和樣本y屬于不同類.由于成對約束信息獲取成本低,容易得到,因此本文使用的監督信息為成對約束.為了體現出各個樣本對簇的貢獻大小,我們認為成對約束滿足程度高的樣本對簇的貢獻程度更大,應該賦予更高的權重.但是當兩個樣本成對約束滿足程度一致時,其對簇的貢獻程度也可能不一樣.文獻[15]認為不同的成對約束的包含的信息不一樣,應該區分對待.因此我們把未得到滿足的成對約束之間的平均距離作為一個懲罰項,用來體現當成對約束滿足程度一致時,樣本對簇的貢獻程度.

在must-link約束關系中,距離更大的約束包含的信息更多,違反后應該受到更大懲罰,應使得其輪廓系數更小.根據輪廓系數計算方式,通常類內距離越大輪廓系數越小.在不考慮權重的情況下,對同一個樣本來說,違反約束后,其輪廓系數值應該更小,因此改進后的類內距離不應該比原先的類內距離小.所以令改進后的類內距離為a(x)與懲罰項兩者中的最大值[13],如式(10)所示,a(x)表示為改進時的類內距離.

其中,xML表示與樣本x具有正關聯約束關系但在實際劃分簇的過程中沒有劃分到同一個簇的樣本集合,avg(x,xML) 表示樣本x到集合xML的平均距離.

在cannot-link約束關系中,距離更小的約束包含的信息更多,違反后應該受到更大懲罰.根據輪廓系數計算方式,一般類間距離越小輪廓系數越小,同理,應該使得改進后的類間距離為b(x)與懲罰項兩者中的最小值[13],如式(11)所示,b(x)表示未改進前的類間距離.

其中,xCL表示與樣本x具有負關聯約束關系但在實際劃分簇的過程中劃分到同一個簇的樣本集合,avg(x,xCL)表示樣本x到集合xCL的平均距離.

改進后的單個樣本輪廓系數如式(12)所示.此時可能會出現輪廓系數為負數的情況,而輪廓系數不為負數,因此令小于0 的輪廓系數為0.

加權的方式分為劃分權重與樣本權重.劃分權重是從整個聚類劃分的角度出發,為在此次K值劃分中滿足的約束關系個數占總約束關系個數的比例.樣本權重是從單個樣本的角度出發,若樣本x具有約束關系,則其樣本權重為樣本x滿足的約束關系個數占樣本x總約束關系個數的比例.若樣本x沒有約束關系但其所在的簇里面其它樣本具有約束關系,那么其樣本權重為簇中滿足的約束關系個數占簇中總約束關系個數的比例.若樣本x本身沒有約束關系并且其所在的簇中其它樣本也沒有約束關系,那么其樣本權重為1.

把劃分權重與樣本權重結合起來,聚類的輪廓系數計算公式如式(13)所示,其中SI(D)表示聚類輪廓系數,S i(x)′為單個樣本x的輪廓系數,w(x)為樣本權重,|D|為數據集D中的樣本個數,weight為劃分權重.

3 實驗與分析

實驗階段使用6 個UCI 數據集和1 個UCR 數據集,如表1所示.Wdbc、Seeds、Iris、Wine、Vertebral column、Glass Identification、Breast Tissue 來自于UCI 數據集,Plane 來自于UCR 數據集,Wdbc 表示的是Breast Cancer Wisconsin (Diagnostic)數據集.每組數據都采用了標準化(將一組數的每個數都減去這組數的平均值后再除以這組數的均方差)的預處理方式,采用結合成對約束的輪廓系數作為聚類有效性評價指標,聚類準確性使用標準互信息(NMI).

表2是CSWKM 算法對比實驗的結果,在CSWKM算法對比實驗中,迭代次數Count取50,聚類數量K的最大取值范圍為向下取整,n表示數據集的規模,Pre_K 表示實驗重復100 次時,算法選出的最佳聚類數與原數據集中種類數一致的次數,“無”表示算法迭代10 000 次后未收斂,括號中的數字為成對約束的對數,NMI 的值為10 次十折交叉驗證的平均值.把僅僅使用輪廓系數而不加成對約束作為聚類有效性評價指標,用來為SubKMeans 確定K值的算法稱為SIKM.

表1 數據集相關信息

表2 CSWKM、SIKM 和SubKMeans 算法對比

從表2中CSWKM 與SIKM 算法的對比實驗數據中可以明顯看到CSWKM 算法的K值確定準確率不論在成對約束對數為10 或100 時,均要高于SIKM 算法,預測K值更加精準,使得NMI 系數也要高于SIKM算法.這一結果表明結合成對約束后的輪廓系數更能夠表示聚類性能,驗證了CSWKM 算法在確定K值上的有效性.在Glass 數據集上,由于有一類只有9 個樣本,在進行十折交叉驗證的時候會出現有的簇中無法滿足樣本數大于5 的要求,導致不收斂,而CSWKM 算法對簇的迭代次數進行了限制,因此不會出現不收斂的現象.從10 對成對約束與100 對成對約束的實驗結果中可以看到,CSWKM 算法的NMI 系數隨著預測K值準確率的提高而提升,由于在大多數的數據集中預測的K值準確率不能達到百分百,因而NMI 系數普遍要比SubKMeans 算法低.當K值預測準確率達到百分百時,CSWKM 算法的NMI 系數不低于SubKMeans算法,可以從Wdbc 和Seeds 數據集的實驗結果中看出.在部分數據集上,可能聚為其它簇的效果要更好,因而預測K值準確率雖然沒有達到百分百,但是CSWKM算法的NMI 系數還是要高于SubKMeans 算法.

4 總結與展望

針對SubKMeans 算法需要用戶指定K值的問題,提出了一種基于成對約束的SubKMeans 聚類數確定算法.將成對約束運用到輪廓系數中,首先用成對約束改進輪廓系數的計算方式,其次用成對約束的滿足程度給輪廓系數加權,將改進后的輪廓系數作為聚類有效性評價指標,在K的取值范圍內根據最佳指標值挑選出對應的最佳K值,有效的解決了SubKMeans 算法在確定聚類數量方面的難題.最后,通過在UCI 和UCR數據集上進行實驗,對比沒有使用成對約束改進輪廓系數的SIKM 算法和SubKMeans 算法.實驗結果表明,CSWKM 算法的K值確定準確率和聚類效果優于SIKM算法,驗證了CSWKM 算法的有效性.并且CSWKM算法在給出100 對成對約束時,聚類效果優于SubKMeans算法.未來的工作將致力于如何把子空間信息作為確定K值的一個考慮因素.