結合可信度的km-means 算法①

熊君竹, 何振峰

(福州大學 計算機與大數(shù)據(jù)學院, 福州 350108)

聚類是一種無監(jiān)督學習方法, 它基于給定的相似性評價措施將數(shù)據(jù)集劃分成若干簇, 使得在同一個簇中的對象彼此具有高相似性, 處于不同簇中的對象具有低相似性[1]. 聚類被廣泛應用在許多領域, 如機器學習、模式識別等[2]. 對于傳統(tǒng)的聚類算法, 屬性值的缺失導致部分實例之間的距離無法有效的度量, 所以不能直接應用到不完整的數(shù)據(jù)集上. 因此, 在不完整數(shù)據(jù)集上的聚類研究是非常有意義的.

目前針對不完整數(shù)據(jù)的處理, 主要采用以下方法:(1) 在聚類之前直接刪除包含缺失值的實例, 盡管它很簡單, 但是當缺失比例較小時, 刪除是非常有效的方法[3].(2) 對缺失的數(shù)據(jù)集進行填充, 通過填充的方式獲取完整的數(shù)據(jù)集, 然后使用傳統(tǒng)聚類算法進行聚類分析, 算法的性能往往受限于預估填充值的準確性[4]. (3) 在聚類過程中采用非填充的方式, 在聚類之前沒有對缺失部分進行填充處理, 而是在不完整狀態(tài)下減少缺失值對聚類過程的影響. 如利用數(shù)據(jù)包含的背景知識, 通過在實例之間添加少量“軟約束”[5]引導包含缺失值的實例進行簇的劃分, 減少數(shù)據(jù)填充過程中不可靠的填充值對聚類的影響.

針對不同的問題, 研究人員提出了多種結合不完整數(shù)據(jù)的聚類算法. 文獻[6]提出一種刪除策略, 當數(shù)據(jù)集缺失比例較小時, 一般小于10%, 直接將包含缺失值的實例刪除, 數(shù)據(jù)缺失比例較小時, 對于最終的聚類分析結果不會產(chǎn)生較大的影響. 文獻[7] 提出K-Pod 算法, 采用迭代填充的方式處理不完整數(shù)據(jù), 填充的過程中使用期望最大化算法(expectation maximization)預估缺失屬性值, 每一次迭代過程中使用K-means 對填充后的實例進行標記, 直到算法收斂, 但是迭代過程中重復使用K-means 方法進行更新, 消耗了大量時間. 文獻[5]提出SLIM 算法, 在聚類過程中添加基于距離的成對約束, 引導包含缺失值的實例進行簇的劃分. 文獻[8]提出km-means 算法, 該算法將缺失值的處理結合到聚類過程中, 通過調整局部距離計算方式, 減少實例中缺失值對目標函數(shù)的影響.

km-means 是對K-means 的擴展, 仍然受到K-means算法固有缺陷的限制[9]. 該算法采用K-means++[10]的初始化方式獲取k個聚類中心, 使得中心之間距離盡可能的大. 由于缺失值的存在, 導致聚類中心的可靠性存在較大的不確定性. 主要表現(xiàn)在兩方面: 直接不確定性和間接不確定性. 初始化過程中選擇的聚類中心, 在標記階段引導簇的劃分起到十分關鍵的作用, 所以增大初始化階段選取聚類中心的可靠性研究具有重要意義.

可信度來源于He 在EKM 算法[11]中, 描述成對約束在簇劃分過程中的滿足度, 即某個簇中, 實例的劃分結果滿足成對約束的個數(shù)占成對約束總個數(shù)的比例.EKM 算法中認為滿足度高, 則該簇可信度高; 滿足度低, 則該簇的可信度低. 因此, 受He 工作的啟發(fā), 為了描述不完整數(shù)據(jù)集中實例之間距離的可信度, 結合實例的完整性, 本文將實例中屬性值的完整性稱為實例可信度, 實例中缺失值的比例越小, 則計算出的局部距離可信度的越高; 反之, 實例中缺失值比例越高, 則計算出的局部距離可信度的越低.

為了解決km-means 初始化階段選取聚類中心的可靠性問題, 本文在初始化過程中引入可信度, 通過可信度調整距離的計算, 減小選取聚類中心的直接不確定性, 增大初始化完成后選取聚類中心的可靠性, 使得聚類中心能夠更好地引導標記階段的簇劃分. 本文第1 節(jié)介紹不完整數(shù)據(jù)的缺失機制和符號定義, 第2 節(jié)介紹km-means 算法, 第3 節(jié)介紹改進的km-means 算法,第4 節(jié)先對初始化階段選取聚類中心的可靠性問題進行實驗與分析說明, 然后對改進后的km-means 進行實驗并分析結果, 第5 節(jié)對所做的工作進行總結.

1 不完整數(shù)據(jù)集

1.1 不完整數(shù)據(jù)的缺失機制

不完整數(shù)據(jù)的缺失機制[12]有3 種不同的類型. 完全隨機缺失, 是指缺失部分獨立于本身, 與數(shù)據(jù)集的其他屬性無關; 隨機缺失, 是指缺失部分獨立于本身, 與數(shù)據(jù)集中其他屬性有關; 非隨機不可忽略缺失, 是指缺失部分與本身有關, 與數(shù)據(jù)集中的其他屬性也有關. 完全隨機缺失和隨機缺失被稱作可忽略缺失, 目前處理不完整數(shù)據(jù)集主要針對可忽略缺失.

1.2 符號定義

現(xiàn)有文獻中有許多關于缺失度(missing rate)[12,13]的定義. 本文采用屬性值缺失度和實例缺失度, 從不同維度描述缺失程度. 屬性值缺失度衡量數(shù)據(jù)集中缺失的屬性值比例, 實例缺失度衡量含有缺失屬性值的實例比例.

設數(shù)據(jù)集D={X1,X2,···,Xn}∈Rn×p,n是數(shù)據(jù)集D的規(guī)模,p是屬性個數(shù).Xi的部分屬性值可能會出現(xiàn)缺失, 用?表示缺失值. 假設Y={Y1,Y2,···,Yn}是一個p維的缺省信息矩陣,Yi的第j個屬性Yij=I(Xijis recorded),Xij是Xi的第j個屬性,I(·)是一個指示函數(shù), 當自變量為真時為1, 否則為0.

定義2. 實例缺失度(instance missing rate,IMR).設D中含有缺失屬性值的實例個數(shù)為ni, 則數(shù)據(jù)集D的實例缺失度為IMR=ni/n.

在不完整數(shù)據(jù)集中, 屬性值缺失度和實例缺失度描述數(shù)據(jù)集的整體缺失程度.

2 km-means 算法簡介

km-means 算法又被稱為結合不完整數(shù)據(jù)集處理的K-means 類型算法, 在Hartigan 等人[14]提出的K-means算法框架基礎上改進, 使其能夠高效的結合缺失值的處理. 該算法的主要思想是: 通過修正實例與聚類中心之間的相似性度量方式, 將缺失值的處理結合到算法中, 減少實例中的缺失值對目標函數(shù)的影響, 使得算法準確度有不錯的提升.

給定數(shù)據(jù)集D={X1,X2,···,Xn}∈Rn×p. 假設K是已知的, 算法的目標尋找劃分集C={C1,C2,···,CK}和聚類中心μ={μ1,μ2, ···,μK}, 優(yōu)化目標是使得每個實例到它所在聚類中心的距離總和最小, 優(yōu)化目標函數(shù)如式(1):

對于每一個劃分集合C, 聚類中心的更新如式(2):

算法1. km-means 算法輸入: 數(shù)據(jù)集D, 聚類數(shù)K C={C1,C2,···,CK}μ={μ1,μ2,···,μK}輸出: 聚類簇的劃分, 聚類中心1)采用算法2 初始化得到K 個簇中心, {?μ(0)k ;k=1,2,···,K}1 ,ξ(0)2 ,···,ξ(0)n }2)采用式(6)初始化每一個實例的所屬簇, ξ(0)={ξ(0)3)初始化活動集和迭代次數(shù)L≠?L={1,2,···,K}t=0 4) while do Xi∈D 5) for each Xik=ξ(t)Δ?k,i 6) 獲取距離 最近的簇, 采用式(4)計算 . // t 表示迭代i次數(shù)7) if k∈L l=argminb≠kΔ+b,i 8) 計算9) else l=argminb∈LΔ+b,i 10) 計算Δ+l,i＜Δ?k,i 11) if 12) 將 從 移入 , 更新XiCkClξ(t+1)i=l k?μ(t+1)lk lL 13) 采用式(2)更新聚類中心和, 并將和放入 中?μ(t+1)14) else XiCkξ(t+1)i=ξ(t)i 15) 仍屬于 , 設置16) end for L 17) 從 中移除本輪迭代過程中沒有更新的簇索引, 更新迭代次數(shù)t=t+1 18) end while

算法2. KMIWMD 算法輸入: 數(shù)據(jù)集D, 聚類數(shù)量K輸出: K 個聚類中心1) 隨機選取作為第1 個聚類中心|μ|＜Kμ←?μ1 =Xi 2) while do // |·|表示集合的個數(shù)proi=d2i/∑ny=1 d2y,i∈{1,2,···,n}3) 計算概率4) 通過概率選取第k 個(k=2, 3, …, K)聚類中心μ←μ∪?μk proi?μk 5) 6) end while

在KMIWMD 算法初始化完成后, 選取的聚類中心存在不可靠性, 這種不可靠性具體表現(xiàn)在兩方面:(1) 直接不確定性, 被選為簇中心的實例存在缺失值時,它所處的空間位置并不確定, 在缺省值被填充為某些值時, 它不適合作為簇中心. (2) 間接不確定性, 在度量實例之間的距離時, 由于缺失值的存在, 可能出現(xiàn)原本距離較近的實例, 得出的距離較大, 導致相距較遠的實例不會被選作下一個聚類中心, 如圖1 所示. 我們將其他包含缺失值的實例, 導致聚類中心的不確定性稱作間接不確定性. 上述兩種不確定性會導致聚類中心在標記階段對簇的劃分產(chǎn)生錯誤的引導, 容易陷入局部最優(yōu)解.

圖1 不可靠的聚類中心影響示意圖

如圖1 所示, 存在兩個大小不同的簇C1和C2, 假設使用KMIWMD 初始化選擇的第一個聚類中心 μ1. 當μ1=(?1.5,?)存在缺失值時, 由于缺失值的存在, 導致原本二維平面上的點與點之間的距離變成了點與直線之間的距離, 即其他實例到 μ1的距離變成了到直線x=–1.5 的距離. 此時 μ2與直線x=–1.5 距離最遠, 由算法2 中的步驟(3) 計算得, 概率pro2最大, 所以選擇μ2為下一個聚類中心. 由圖1 可知此時選擇的兩個聚類中心均在簇C2中, 這會導致在接下來的實例標記過程中, 初始中心無法有效的引導簇的劃分. 當μ1=(?1.5,2.1)不存在缺失值時, 距離 μ1最遠的實例為 μ1′,通過計算可知pro1′最大, μ1′作為下一個聚類中心. 因為 μ1′和 μ1分布在不同的簇中, 所以和 μ2相比 μ1′是一個更好的聚類中心. 上述過程中, 我們將 μ1是否包含缺失值稱作直接不確定性; 將 μ1存在缺失值時, 導致選取下一個聚類中心的發(fā)生變化稱作間接不確定性. 針對上述存在的問題, 我們將在第3 節(jié)討論解決方案.

3 結合可信度的km-means 聚類算法

針對km-means 算法初始化(KMIWMD 算法)過程中, 選取聚類中心的不可靠性問題, 受He 等人的工作啟發(fā)[11,15], 本文在式(7)的計算過程中引入可信度, 如定義3 和定義4, 通過可信度優(yōu)化不完整數(shù)據(jù)集的初始化過程, 減少初始化完成后, 多個聚類中心位于同一個簇中, 使得聚類中心能夠更好地引導簇的劃分. 結合式(7)和可信度, 推出新的結合缺失值處理的初始化方式,式(8)為結合實例可信度的距離計算, 當實例Xi中存在缺失值, 即ICi＜1, 在計算實例與聚類中心之間的距離時, 實例可信度通過減少該實例被選做下一個聚類中心的概率proi, 盡量保證選取較完整的實例作為下一個聚類中心, 從而增大選取聚類中心可靠性. 式(9)為結合公共屬性可信度的距離計算, 式(9)與公共屬性可信度的結合方式和式(8)類似.

在不完整數(shù)據(jù)集中, 實例可信度描述單個實例的缺失程度, 實例可信度越小, 表示該實例包含缺失屬性值越多, 實例越不可信. 公共屬性可信度描述任意兩個實例之間, 同一個屬性均未缺失的屬性值比例, 公共屬性可信度越小, 表示兩個實例之間公共缺失的屬性值越多, 實例越不可信.

式(8) 中的ICi表示Xi的實例可信度, 式(9) 中的PACi,k表示Xi與Ck的公共屬性可信度. 結合上文對算法2 的分析與改進, 本文提出優(yōu)化后的KMIWMD 算法, 即結合可信度的不完整數(shù)據(jù)集聚類中心初始化算法, 記作KMIWMD++, 具體的流程如算法3 所示.

算法3. KMIWMD++算法輸入: 數(shù)據(jù)集D, 聚類數(shù)K, 可信度閾值輸出: K 個聚類中心θ′1) 采用定義3 計算各個實例μ←?μ1 =XiICi>θ′2) 隨機選取作為第一個聚類中心, 其中, IC={IC1,IC2,···,ICn}3) while do // ||表示集合的個數(shù)d2i=minl=1,2,···,k?1 ?d2i,Cl 4) 使用式(8)計算|μ|＜K/∑ny=1 d2y,i∈{1,2,···,n}5) 計算概率proi?μk proi=d2i 6) 通過概率選取第k 個(k=2, 3, …, K)聚類中心μ←μ∪?μk 7) 8) end while

步驟(4)中我們可以使用式(8)或式(9)結合不同的可信度, 調整初始化過程中的距離計算. KMIWND++算法確定下一個聚類中心的時, 在局部距離計算的過程中引入可信度(實例可信度或公共屬性可信度), 步驟(2)中通過實例可信度選擇包含較完整信息的實例作為第一個聚類中心, 減小簇中心包含缺失值對第k(k=2, 3, …,K)個中心選取的影響. 步驟(4)、步驟(5)通過實例可信度(或者公共屬性可信度)調整距離計算, 減少包含缺失值的實例被選作下一個中心的概率,盡可能地減少直接不確定性對中心選取的影響, 使得初始化完成后多個中心分布在不同的簇中. 最后, 本文將使用算法3 初始化的算法1 稱作KMMC (km-means with credibility), 接下來在第4 節(jié)通過實驗分析對比km-means 和KMMC 在結合不完整數(shù)據(jù)集的處理效果.

4 實驗與分析

如表1 所示, 實驗階段使用7 個UCI 數(shù)據(jù)集和3 個UCR 數(shù)據(jù)集. Seeds, Ceramic, Wine, Wdbc, CCBR,Iris 和Column 來自于UCI 數(shù)據(jù)集. Plane, CBF 和Trace來自于UCR 數(shù)據(jù)集. Wdbc 表示的是Breast Cancer Wisconsin (Diagnostic)數(shù)據(jù)集, CCBR 表示Cervical Cancer Behavior Risk 數(shù)據(jù)集, Ceramic 表示Chemical Composition of Ceramic Samples 數(shù)據(jù)集, Column 表示的是Vertebral Column 數(shù)據(jù)集. 每組數(shù)據(jù)都采用了ZScore 標準化.

表1 數(shù)據(jù)集信息

本文對實驗需要的缺失數(shù)據(jù)集進行如下處理, 構建隨機缺失機制下的不完整數(shù)據(jù)集. 在完整數(shù)據(jù)集基礎上, 分別構建不同實例缺失度(IMR)的不完整數(shù)據(jù)集, 構建過程中分別取IMR為0、10%和20%. 首先通過隨機數(shù)發(fā)生器在n個實例中隨機選取miss=IMR×n個實例作為缺失部分, 然后通過隨機數(shù)發(fā)生器依次在miss個實例中隨機選取m個屬性, 將該屬性對應的值設置為空值, 每個實例的隨機種子為該實例在數(shù)據(jù)集中的序號, 最后將miss個包含缺失值的部分和n–miss個完整部分組合成實驗所需的不完整數(shù)據(jù)集. 公共屬性可信度存在為0 的情況, 如X1=(?,?,6),X2=(1,5,?),此時PAC1,2=0, 為了避免這種情況, 構建過程中保證每個實例中屬性值缺失的個數(shù)m

第一組實驗, 如表2 和表3 所示, 通過實驗分析KMIWMD (算法2)和KMIWMD++ (算法3)初始化完成后聚類中心包含缺失值的情況和初始完成后聚類中心出現(xiàn)在同一個簇中的情況, 其中算法2 為km-means算法中的初始化聚類中心部分.

表2 算法2 與算法3 初始化完成后聚類中心包含缺失值的情況

表3 算法2 與算法3 初始化聚類中心完成后聚類中心在同一個簇中的情況

第2 組實驗, 如表4 所示, 通過實驗對比km-means算法結合不同的聚類中心初始化算法(算法2 和算法3)對聚類準確度的影響.

表4 KMMC 和km-means 算法ARI 系數(shù)對比

表2 和表3 分別表示對Iris 數(shù)據(jù)集, 采用KMIWMD和KMIWMD++算法進行1 000 次實驗, 初始化完成后選取的聚類中心包含缺失值的次數(shù)和聚類中心在同一個簇中的次數(shù)(表2 和表3 中的數(shù)據(jù)統(tǒng)計在同一組實驗中完成). 表2 中的mi(i=1,2,···,k)表示選擇k個聚類中心包含缺失值的次數(shù), 如m1=239表示1 000 次實驗中, 選取的k聚類中心里有1 個聚類中心包含缺失值出現(xiàn)239 次, 表3 中si(i=2,3,···,k)表示選擇的k個聚類中心在同一個簇中的次數(shù), 如s3=8表示1 000 次試驗中, 選取的k聚類中心有3 個聚類中心在同一個簇中出現(xiàn)了8 次.

表4 是KMMC 與km-means 對比實驗結果, KMMC算法中每一行兩個值分別表示采用實例可信度和公共屬性可信度優(yōu)化的實驗結果. 從實驗數(shù)據(jù)分析可知, 當數(shù)據(jù)集不存在缺失值時, 通過定義3 和定義4 可知, 實例可信度ICi≡1,?i∈(1,n), 公共屬性可信度PACi,k≡1,?i,k∈(1,n),i≠k, 文中引入的可信度對于KMMC 算法與km-means 算法初始化聚類中心不存在影響, 所以表4中KMMC 算法與km-means 算法在完整數(shù)據(jù)集的情況下ARI 值均相等. 在相同的缺失機制和實例缺失度的情況下, KMMC 的ARI 值普遍要比km-means 的值要高, 說明了減少初始化中心的直接不確定性, 即減少包含缺失屬性值的實例作為初始樣本中心, 可以提高結合缺失值處理的聚類算法性能. 但是在高維數(shù)據(jù)集(CBF), 傳統(tǒng)的距離度量方式難以準確找出實例之間的差異性, 導致聚類效果不佳; 同樣, 在Trace 數(shù)據(jù)集上,當實例缺失度為20%時, 優(yōu)化初始中對聚類結果幾乎沒有提升. 在高維數(shù)據(jù)集中隨著實例缺失度增大, 通過優(yōu)化初始化聚類中心, 無法有效的改善聚類準確度.

5 總結與展望

針對不完整數(shù)據(jù)集初始化聚類中心問題, 提出了結合可信度的不完整數(shù)據(jù)集聚類算法KMMC, 將實例可信度和公共屬性可信度運用到聚類中心初始化過程中, 減少實例中屬性值的缺失對實例之間距離度量的影響, 增大初始化階段選取聚類中心的可靠性. 通過可信度調整距離計算, 有效減少了簇劃分過程中, 不可靠的聚類中心對實例標記階段產(chǎn)生的錯誤引導. 最后, 通過UCI 和UCR 數(shù)據(jù)集對比KMMC 與km-means 算法的聚類準確度, 實驗結果表明, 改進初始化聚類中心的KMMC 算法的準確度優(yōu)于km-means 算法, 驗證了KMMC 算法的有效性. 未來工作將致力于如何在不完整數(shù)據(jù)集上引入成對約束, 引導聚類過程中的簇劃分,減少不完整數(shù)據(jù)對實例標記階段的影響.