3.1.4　基于聚類的填補(bǔ)方法

基于聚類的填補(bǔ)方法是指采用聚類算法處理數(shù)據(jù)缺失問題的填補(bǔ)方法。聚類算法基于樣本間的相似度將數(shù)據(jù)集劃分為若干子集，其中，每個子集通常稱為一個簇，簇中樣本分布的中心稱為聚類中心，也稱原型。

基于聚類的填補(bǔ)方法采用聚類算法將不完整數(shù)據(jù)集劃分為不同的簇，并參照聚類中心及簇內(nèi)完整樣本對不完整樣本的缺失值進(jìn)行填補(bǔ)。下面主要從三個方面對該方法進(jìn)行介紹，即缺失值填補(bǔ)中常見的聚類算法，聚類過程中不完整數(shù)據(jù)的處理，基于不完整數(shù)據(jù)聚類的缺失值填補(bǔ)方法。

1.缺失值填補(bǔ)中常見的聚類算法

K均值聚類和FCM是常用于缺失值填補(bǔ)的聚類算法，下面分別介紹兩種聚類算法。

（1）K均值聚類算法

K均值聚類算法是一種迭代式聚類算法，該算法將每個樣本劃到距該樣本最近的聚類中心所在的簇中，接著通過簇內(nèi)樣本的均值更新聚類中心，并由此反復(fù)迭代直至聚類結(jié)束。假設(shè)X={x_i|x_i∈^s,i=1,2,…,n}表示樣本數(shù)量為n，屬性數(shù)量為s的數(shù)據(jù)集，其第i個樣本為x_i=[x_i1,x_i2,…,x_is]^T(i=1,2,…,n)，基于此數(shù)據(jù)集的聚類流程如圖3-3所示。

圖3-3　K均值聚類算法流程圖

如圖3-3所示，K均值聚類算法首先在數(shù)據(jù)集X中隨機(jī)選擇K個樣本分別作為各簇的聚類中心。隨后，采用迭代的方式進(jìn)行樣本聚類，每輪迭代分兩步進(jìn)行。第一步，對于數(shù)據(jù)集中的n個樣本，分別計算其與K個聚類中心的歐式距離，將各樣本劃入其最近聚類中心所在的簇中；第二步，根據(jù)劃分結(jié)果更新聚類中心，計算劃分結(jié)束后簇內(nèi)樣本各屬性值的均值并以此更新聚類中心。若更新前后聚類中心的變化小于設(shè)定的閾值，則結(jié)束迭代，并將最后一輪迭代中劃分的樣本簇作為聚類結(jié)果，各簇記為X⁽¹⁾,X⁽²⁾,…,X^(k)。在K均值聚類算法中，樣本x_i(i=1,2,…,n)相對于簇X^(k)(k=1,2,…,K)的隸屬關(guān)系可由式（3-17）所示的隸屬函數(shù)表示：

式（3-17）中，隸屬函數(shù)u_ik需滿足式（3-18）、式（3-19）中的兩個條件：

式（3-18）表明每個樣本只能屬于一個簇，式（3-19）限定了每個簇均為非空。若樣本劃分的結(jié)果符合上述隸屬函數(shù)，則稱這樣的劃分為硬劃分。

（2）FCM算法

FCM算法可視為K均值聚類算法基于模糊劃分的改進(jìn)算法。模糊劃分的概念由Ruspini于1969年首先提出，該劃分是相對于硬劃分而言的，即所有樣本并非完全屬于某一個簇，而是以不同程度隸屬于各個簇。模糊劃分中隸屬度u_ik的取值范圍由{0，1}擴(kuò)展到[0,1]區(qū)間，從而刻畫出樣本分屬于各簇的程度。對于數(shù)據(jù)集X中的樣本，采用FCM算法對其進(jìn)行聚類，相應(yīng)的聚類模型如式（3-20）所示：

式（3-20）中，u_ik為隸屬度，表示樣本x_i隸屬于第k個簇的程度，記U=[u_ik]∈^n×K，稱為劃分矩陣。v_k為第k個簇的聚類中心，即該簇的原型，v_k∈^s，記V=[v_kj]=[v₁,v₂,…,v_K]^T∈^K×s，稱為原型矩陣。z∈(1,∞)是一個模糊化參數(shù)，其控制著樣本在各簇間的分享程度。當(dāng)z=1時，F(xiàn)CM算法退化為K均值算法；當(dāng)z趨近于無窮時，F(xiàn)CM算法將失去劃分能力。在實際應(yīng)用中，可結(jié)合數(shù)據(jù)集自身特征確定z的取值，一個常用的取值是z=2^[7]。為了簡便描述，將u_ik∈[0,1]和作為隸屬度必須滿足的默認(rèn)條件，后續(xù)不再列寫。

考慮式（3-20）中關(guān)于隸屬度u_ik的等式約束條件，采用拉格朗日乘子法，設(shè)增廣拉格朗日函數(shù)如式（3-21）所示：

式（3-21）中，λ=[λ₁,λ₂,…,λ_n]^T為拉格朗日乘子，使FCM聚類過程中的目標(biāo)函數(shù)J達(dá)到極小的必要條件如式（3-22）、式（3-23）所示：

對式（3-22）和式（3-23）進(jìn)行交替迭代式求解，當(dāng)先后兩次迭代中原型矩陣或劃分矩陣的改變量小于某一預(yù)先設(shè)定的閾值時，則迭代停止。以下為算法的具體步驟。

步驟1：設(shè)定模糊化參數(shù)z，聚類數(shù)K和閾值ε，(ε>0)，隨機(jī)初始化劃分矩陣U⁽⁰⁾；

步驟2：當(dāng)?shù)螖?shù)為l,l=1,2,…時，基于U^(l-1)使用式（3-22）更新原型矩陣V^(l)；

步驟3：基于V^(l)，使用式（3-23）更新劃分矩陣U^(l)；

步驟4：若滿足條件?k,，算法停止，輸出劃分矩陣U和原型矩陣V；否則l←l+1，返回步驟2。

最終，所得劃分矩陣U即聚類結(jié)果，原型矩陣V記錄了劃分結(jié)束后各簇的原型。

2.聚類過程中不完整數(shù)據(jù)的處理

在聚類過程中，針對數(shù)據(jù)集中的數(shù)據(jù)缺失問題，目前有4種常用的應(yīng)對策略^[8]，即完整數(shù)據(jù)策略（Whole Data Stra_tegy，WDS）、局部距離策略（Partial Distance Stra_tegy，PDS）、優(yōu)化完整策略（Optimal Completion Stra_tegy，OCS）和最近原型策略（Nearest Prototype Stra_tegy，NPS），以下依次對這4種策略進(jìn)行詳細(xì)說明。

（1）完整數(shù)據(jù)策略

完整數(shù)據(jù)策略是指將數(shù)據(jù)集中存在缺失值的樣本直接剔除，僅采用完整樣本參與聚類。假設(shè)數(shù)據(jù)集X中存在不完整樣本，首先將數(shù)據(jù)集X劃分為完整樣本集X_co和不完整樣本集x_in；然后直接采用標(biāo)準(zhǔn)的聚類算法對X_co進(jìn)行劃分，從而獲得由完整樣本構(gòu)成的多個聚類簇；最后對x_in中的樣本，分別計算其中樣本與各聚類中心的局部距離（見式（3-8）），進(jìn)而將不完整樣本劃分到與之最近聚類中心所對應(yīng)的簇中。此方法雖然易于實施，但聚類過程中忽視了不完整樣本中的大量現(xiàn)有信息，往往很難獲得理想的聚類精度。

（2）局部距離策略

局部距離策略是一種簡單且有效的不完整數(shù)據(jù)聚類方法，其在聚類迭代過程中僅忽略了不完整樣本的缺失屬性值。PDS方法采用式（3-8）所示的局部距離代替標(biāo)準(zhǔn)聚類算法中的歐式距離，從而將不完整數(shù)據(jù)集X劃分為K個簇。以FCM算法為例，其相應(yīng)的聚類模型如式（3-24）所示：

采用拉格朗日乘子法，設(shè)增廣函數(shù)如式（3-25）所示：

式（3-25）中，λ=[λ₁,λ₂,…,λ_n]^T為拉格朗日乘子，則在關(guān)于隸屬度u_ik的等式約束條件下，基于式（3-1）所定義的數(shù)據(jù)缺失情況，聚類目標(biāo)函數(shù)j₂達(dá)到極小的必要條件如式（3-26）、式（3-27）所示：

PDS方法通過執(zhí)行式（3-26）和式（3-27）的交替迭代，即可獲得各簇原型以及完整樣本和不完整樣本相對于各簇的隸屬度。相比于WDS方法忽略了全部不完整樣本，PDS更充分地使用了不完整數(shù)據(jù)集中所有已知信息，是一種更有效的不完整數(shù)據(jù)聚類方法。

（3）優(yōu)化完整策略

優(yōu)化完整策略是一種關(guān)注度較高的不完整數(shù)據(jù)聚類方法，該方法將缺失值視作變量，在聚類的同時進(jìn)行缺失值填補(bǔ)。以FCM算法為例，設(shè)X_m為數(shù)據(jù)集X中缺失值構(gòu)成的集合，其聚類模型如式（3-28）所示：

由式（3-28）可見，缺失值在目標(biāo)函數(shù)J₃中作為變量出現(xiàn)。

采用拉格朗日乘子法，設(shè)增廣拉格朗日函數(shù)如式（3-29）所示：

使聚類目標(biāo)函數(shù)J3達(dá)到極小的必要條件如式（3-30）、式（3-31）和式（3-32）所示：

式（3-32）表明，優(yōu)化完整策略利用樣本在各簇的隸屬度計算權(quán)重，并將各簇原型屬性值的加權(quán)平均作為填補(bǔ)值，上述加權(quán)平均值稱為模糊均值。OCS方法執(zhí)行式（3-30）、式（3-31）和式（3-32）三者的交替迭代，收斂后可同時獲得各簇原型、樣本隸屬度和缺失值的填補(bǔ)結(jié)果。

（4）最近原型策略

最近原型策略是對優(yōu)化完整策略的一種簡單修改，其將OCS方法中的式（3-32）修改為如式（3-33）所示的形式：

在迭代過程中，NPS策略采用最近原型的相應(yīng)屬性值來填補(bǔ)缺失值。NPS方法需要執(zhí)行式（3-30）、式（3-31）和式（3-33）三者的交替迭代，從而在聚類的同時進(jìn)行缺失值填補(bǔ)。對于K均值聚類算法而言，由于其采用硬劃分的方式，每個樣本僅被劃入一個確定的簇，因此該算法的優(yōu)化完整策略和最近原型策略實際上是等價的。然而到目前為止，尚無法從理論上對NPS算法的收斂性加以證明，該算法在聚類不完整數(shù)據(jù)時可能出現(xiàn)不收斂的情況^[9]。

通過上述4種策略能夠?qū)崿F(xiàn)不完整數(shù)據(jù)的聚類，其中WDS和PDS僅能獲得聚類結(jié)果，需根據(jù)聚類結(jié)果進(jìn)行缺失值填補(bǔ)；OCS和NPS在聚類的同時進(jìn)行缺失值填補(bǔ)，能夠同時得到聚類結(jié)果與填補(bǔ)值，但其本質(zhì)仍是以聚類為目標(biāo)的不完整數(shù)據(jù)處理策略，獲得的填補(bǔ)結(jié)果可能并不精確，因此需對基于聚類結(jié)果的缺失值填補(bǔ)方法進(jìn)一步探討。

3.基于不完整數(shù)據(jù)聚類的缺失值填補(bǔ)方法

K均值聚類算法和FCM算法分別采用硬劃分和模糊劃分進(jìn)行樣本聚類。因此，二者聚類結(jié)果的形式存在差異，K均值聚類算法將每個樣本劃分到唯一確定的簇，而FCM算法則采用劃分矩陣記錄樣本對各簇的隸屬度，從而將每個樣本以不同的程度劃分到各個簇。上述兩種形式的聚類結(jié)果在缺失值填補(bǔ)中的應(yīng)用方式也不盡相同，下面對其依次展開討論。

（1）基于K均值聚類的填補(bǔ)方法

在利用K均值聚類結(jié)果進(jìn)行缺失值填補(bǔ)時，一種簡捷且常見的方法是采用不完整樣本所在簇的聚類中心對應(yīng)屬性值填補(bǔ)缺失值。若不完整樣本中的缺失值較多，則基于該樣本現(xiàn)有值所計算的局部距離可靠性較低，可能使得該樣本的聚類劃分不準(zhǔn)確，從而對填補(bǔ)結(jié)果的精度產(chǎn)生影響。為此，可采用離群樣本檢測算法對填補(bǔ)結(jié)果進(jìn)行檢驗。離群樣本是指集群中與其他大部分樣本不同的樣本，離群點檢測算法又稱局部異常因子（Local Outlier Factor，LOF）算法，用于檢測樣本集中的離群樣本。假設(shè)K均值聚類算法將數(shù)據(jù)集X中的樣本劃分為K個簇，記其中的第k個簇為X^(k)，可通過如式（3-34）所示的殘差平方和檢驗該簇中的離群樣本：

式中，v_k表示簇X^(k)的聚類中心。當(dāng)加入某個樣本后S^(k)_res顯著增大，則說明該樣本為離群樣本。通常而言，離群樣本的屬性值明顯偏離期望的或常見的屬性值^[10]。因此，如果填補(bǔ)后的樣本檢測為離群樣本，則很可能該樣本的填補(bǔ)值與真實值偏差較大。

加入離群樣本檢測的缺失值填補(bǔ)方法是基于K均值聚類算法填補(bǔ)缺失值，并采用式（3-34）檢測填補(bǔ)后的樣本是否為離群樣本，去除離群樣本的填補(bǔ)值并對其重新填補(bǔ)。該方法不斷迭代直到填補(bǔ)后的樣本不再被檢測出離群樣本。以下為加入離群樣本檢測的缺失值填補(bǔ)方法流程。

步驟1：設(shè)定聚類數(shù)K和殘差平方和閾值ε(ε>0)，設(shè)數(shù)據(jù)集X中的不完整樣本組成的集合為x_in。

步驟2：隨機(jī)選擇K個樣本作為初始聚類中心，采用K均值聚類算法將數(shù)據(jù)集X中的樣本劃分為K個簇，對于x_i∈x_in，基于所在簇的聚類中心填補(bǔ)缺失值，隨后清空x_in。

步驟3：對于簇X^(k)(k=1,2,…,K)，計算其殘差平方和S_res^(k)，隨后依次刪除其中的不完整樣本，計算刪除后簇內(nèi)樣本的殘差平方和S_res^(k)'，若S_res^(k)-S_res^(k)'≥ε，將該樣本加入數(shù)據(jù)集x_in。

步驟4：若x_in不為空，返回步驟2，重新進(jìn)行聚類填補(bǔ)；否則，填補(bǔ)結(jié)束。

此方法在缺失值填補(bǔ)的同時檢測填補(bǔ)精度，及時處理精度不高的填補(bǔ)值，從而獲得更有效、精度更高的填補(bǔ)結(jié)果。

（2）基于模糊C均值聚類的填補(bǔ)方法

在使用FCM算法對不完整數(shù)據(jù)集X聚類的過程中，采用劃分矩陣U記錄樣本對各簇的隸屬度，并采用原型矩陣V記錄劃分結(jié)束后各簇的原型。目前，基于上述兩種矩陣填補(bǔ)缺失值的方法主要有3種，包括模糊均值填補(bǔ)法、最近原型填補(bǔ)法和屬性投票填補(bǔ)法。其中，模糊均值填補(bǔ)法在簇原型的基礎(chǔ)上，根據(jù)樣本對各簇的隸屬度計算原型中現(xiàn)有值的加權(quán)平均并將其作為填補(bǔ)結(jié)果。優(yōu)化完整策略采用此方法填補(bǔ)缺失值，計算方式見式（3-32）。最近原型填補(bǔ)法是指使用不完整樣本最近原型的相應(yīng)屬性值進(jìn)行缺失值填補(bǔ)。最近原型策略采用此方法填補(bǔ)缺失值，計算方式見式（3-33）。屬性投票填補(bǔ)法是指采用各屬性投票的方式確定樣本所屬的聚類簇，從而根據(jù)簇原型的屬性值進(jìn)行缺失值填補(bǔ)^[11]。以下為對不完整數(shù)據(jù)集X采用屬性投票填補(bǔ)法進(jìn)行缺失值填補(bǔ)的流程。

步驟1：設(shè)定模糊化參數(shù)z、聚類數(shù)K和閾值ε，ε>0。

步驟2：采用FCM算法對數(shù)據(jù)集X中的樣本進(jìn)行模糊劃分，得到劃分矩陣U=[u_ik]∈^n×K和原型矩陣V=[v_kj]∈^K×s，n為數(shù)據(jù)集X中的樣本數(shù)量，s為數(shù)據(jù)集X中的屬性數(shù)量。

步驟3：對于數(shù)據(jù)集X中的各樣本，分別計算其中完整屬性值與各簇原型屬性值的距離，該距離實際上是基于單個屬性所得的局部距離，如式（3-35）所示：

步驟4：對于樣本x_i(i=1,2,…,n)的第j(j=1,2,…,s)個屬性，基于式（3-35）分別計算該屬性值與各簇原型相應(yīng)屬性值的距離，選擇距離最近的簇作為該屬性的投票意向。

步驟5：統(tǒng)計樣本中各屬性的投票意向，其中得票最高的簇即該樣本基于屬性投票的劃分結(jié)果。

步驟6：根據(jù)上述劃分結(jié)果，采用原型中的現(xiàn)有屬性值填補(bǔ)簇內(nèi)樣本的缺失值。

大部分情況下，上述3種基于FCM聚類結(jié)果進(jìn)行缺失值填補(bǔ)的方法所得結(jié)果相差并不明顯，可結(jié)合具體數(shù)據(jù)集進(jìn)行選擇。

相比于均值填補(bǔ)法、熱平臺填補(bǔ)法和K最近鄰填補(bǔ)法，基于聚類的填補(bǔ)方法更加擅長處理大規(guī)模數(shù)據(jù)集，已廣泛應(yīng)用于工業(yè)、生物、醫(yī)療等眾多領(lǐng)域。其中，基于K均值聚類的填補(bǔ)方法易于實現(xiàn)，時間復(fù)雜較低。但實際應(yīng)用中，很多樣本或?qū)傩圆淮嬖诿鞔_的邊界，不適合采用硬劃分的方式進(jìn)行聚類，故此類填補(bǔ)方法的應(yīng)用范圍受到一定制約。基于FCM聚類的填補(bǔ)方法雖然計算量較大，但FCM算法提供了樣本對于各聚類簇的隸屬度，使得此類方法能夠應(yīng)用于更多實踐和研究領(lǐng)域。