熊君竹, 何振峰

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

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

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

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

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

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

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

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

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

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

1.2 符號定義

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

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

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

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

2 km-means 算法簡介

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

給定數(shù)據(jù)集D={X1,X2,···,Xn}∈Rn×p. 假設(shè)K是已知的, 算法的目標(biāo)尋找劃分集C={C1,C2,···,CK}和聚類中心μ={μ1,μ2, ···,μK}, 優(yōu)化目標(biāo)是使得每個實(shí)例到它所在聚類中心的距離總和最小, 優(yōu)化目標(biāo)函數(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)初始化每一個實(shí)例的所屬簇, ξ(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)計(jì)算 . // t 表示迭代i次數(shù)7) if k∈L l=argminb≠kΔ+b,i 8) 計(jì)算9) else l=argminb∈LΔ+b,i 10) 計(jì)算Δ+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) 仍屬于 , 設(shè)置16) end for L 17) 從 中移除本輪迭代過程中沒有更新的簇索引, 更新迭代次數(shù)t=t+1 18) end while

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

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

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

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

3 結(jié)合可信度的km-means 聚類算法

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

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

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

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

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

4 實(shí)驗(yàn)與分析

如表1 所示, 實(shí)驗(yàn)階段使用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 標(biāo)準(zhǔn)化.

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

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

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

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

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

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

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

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

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

5 總結(jié)與展望

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