面向高維特征缺失數(shù)據(jù)的K最近鄰插補(bǔ)子空間聚類算法

喬永堅(jiān)，劉曉琳，白亮*

面向高維特征缺失數(shù)據(jù)的K最近鄰插補(bǔ)子空間聚類算法

喬永堅(jiān)1，劉曉琳1，2，白亮1，2*

（1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006； 2.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室（山西大學(xué)），太原 030006）（?通信作者電子郵箱bailiang@sxu.edu.cn）

針對(duì)高維特征缺失數(shù)據(jù)在聚類過程中面臨的因數(shù)據(jù)高維引發(fā)的維度災(zāi)難問題和數(shù)據(jù)特征缺失導(dǎo)致的樣本間有效距離計(jì)算失效問題，提出一種面向高維特征缺失數(shù)據(jù)的K最近鄰（KNN）插補(bǔ)子空間聚類算法KISC。首先，利用高維特征缺失數(shù)據(jù)的子空間下的近鄰關(guān)系對(duì)原始空間下的特征缺失數(shù)據(jù)進(jìn)行KNN插補(bǔ)；然后，利用多次迭代矩陣分解和KNN插補(bǔ)獲得數(shù)據(jù)最終可靠的子空間結(jié)構(gòu)，并在該子空間結(jié)構(gòu)進(jìn)行聚類分析。在6個(gè)圖像數(shù)據(jù)集原始空間的聚類結(jié)果表明，相較于經(jīng)過插補(bǔ)后直接進(jìn)行聚類的對(duì)比算法，KISC算法聚類效果更好，說明子空間結(jié)構(gòu)能夠更加容易且有效地識(shí)別數(shù)據(jù)的潛在聚類結(jié)構(gòu)；在6個(gè)高維數(shù)據(jù)集子空間下的聚類結(jié)果顯示，KISC算法在各個(gè)數(shù)據(jù)集的聚類性能均優(yōu)于對(duì)比算法，且在大多數(shù)據(jù)集上取得了最優(yōu)的聚類精確度（ACC）和標(biāo)準(zhǔn)互信息（NMI）。KISC算法能夠更加有效地處理高維特征缺失數(shù)據(jù)，提高算法的聚類性能。

高維數(shù)據(jù)；特征缺失；插補(bǔ)算法；子空間結(jié)構(gòu)；聚類

0 引言

隨著科技的不斷進(jìn)步，數(shù)據(jù)采集設(shè)備性能逐漸增強(qiáng)，人們所獲取數(shù)據(jù)的維數(shù)越來越高。現(xiàn)實(shí)生活中存在很多高維數(shù)據(jù)，如圖像數(shù)據(jù)、用戶評(píng)分?jǐn)?shù)據(jù)、貿(mào)易交易數(shù)據(jù)、Web文檔數(shù)據(jù)、基因表達(dá)數(shù)據(jù)等。人們可以從這些高維數(shù)據(jù)中獲得更豐富的信息，使各個(gè)領(lǐng)域的生產(chǎn)生活更加便利，但是這些高維數(shù)據(jù)通常具有冗余信息量大、信息分布不均的特點(diǎn)［1］，且數(shù)據(jù)維度過高會(huì)造成維度災(zāi)難問題［2］。在高維空間下，數(shù)據(jù)點(diǎn)之間的距離基本相等，使樣本間相似性度量方法失效；同時(shí)，高維數(shù)據(jù)也容易受到噪聲和數(shù)據(jù)缺失問題的影響。因此，高維數(shù)據(jù)給數(shù)據(jù)挖掘任務(wù)帶來了巨大的挑戰(zhàn)。

數(shù)據(jù)在產(chǎn)生和收集過程中，由于某些原因，會(huì)出現(xiàn)數(shù)據(jù)特征缺失的情況，如樣本的個(gè)別屬性值缺失，而高維數(shù)據(jù)更容易受到數(shù)據(jù)缺失問題的影響形成高維特征缺失數(shù)據(jù)。高維特征缺失數(shù)據(jù)中同樣蘊(yùn)含著豐富的信息，需要人們進(jìn)行挖掘。聚類分析技術(shù)是數(shù)據(jù)挖掘中的一個(gè)重要分支［3］，目的是將一組給定的數(shù)據(jù)依據(jù)它們的相似性劃分為不同的簇，該劃分使得相同簇中的樣本盡量相似，不同簇中的樣本盡量不同。常見的高維數(shù)據(jù)聚類算法包括核K?Means聚類［4］、譜聚類［5］以及子空間聚類［6］等。這些聚類算法已被廣泛應(yīng)用到各大領(lǐng)域中，如生物信息分析［7］、醫(yī)學(xué)圖像分析［8］、社交網(wǎng)絡(luò)［9］、圖像分割［10］以及推薦系統(tǒng)［11］等。研究人員可以使用聚類分析技術(shù)來挖掘高維特征缺失數(shù)據(jù)中的隱藏信息，但是這個(gè)過程不僅需要解決數(shù)據(jù)高維引發(fā)的維度災(zāi)難問題，還要解決數(shù)據(jù)特征缺失導(dǎo)致的樣本間有效距離計(jì)算失效的問題，加大了聚類分析的難度。

高維特征缺失數(shù)據(jù)由于信息不完整，無法使用常見的高維數(shù)據(jù)聚類算法進(jìn)行分析?，F(xiàn)有的解決方案需要先將高維特征缺失數(shù)據(jù)插補(bǔ)完整，再對(duì)完整的數(shù)據(jù)進(jìn)行聚類分析。插補(bǔ)高維特征缺失數(shù)據(jù)時(shí)，受到維度災(zāi)難和數(shù)據(jù)特征缺失導(dǎo)致的樣本間有效距離計(jì)算失效問題的影響，得到的插補(bǔ)值會(huì)扭曲原始數(shù)據(jù)的潛在結(jié)構(gòu)，使得到的完整數(shù)據(jù)用于聚類分析時(shí)，表現(xiàn)不佳。將高維特征缺失數(shù)據(jù)補(bǔ)全后，對(duì)補(bǔ)全后的完整數(shù)據(jù)進(jìn)行聚類分析。如果使用一般的聚類算法，由于沒有解決維度災(zāi)難問題，在計(jì)算樣本間相似性時(shí)，基于距離的相似性度量方法受到維度災(zāi)難的影響變得不可靠，必然會(huì)影響最終的聚類結(jié)果，所以需要對(duì)插補(bǔ)后的完整高維數(shù)據(jù)進(jìn)行降維處理。采用矩陣分解法［12］學(xué)習(xí)高維數(shù)據(jù)的子空間結(jié)構(gòu)可以解決維度災(zāi)難問題，但是得到的子空間結(jié)構(gòu)會(huì)受插補(bǔ)算法的影響，因此選擇一種合適的插補(bǔ)算法尤為重要。

因此，本文提出一種面向高維特征缺失數(shù)據(jù)的K最近鄰（K?Nearest Neighbor， KNN）插補(bǔ)子空間聚類（KNN Imputation Subspace Clustering， KISC）算法。該算法主要是將矩陣分解和KNN插補(bǔ)進(jìn)行有機(jī)融合，利用數(shù)據(jù)的子空間下的近鄰關(guān)系去插補(bǔ)原數(shù)據(jù)的缺失特征，通過迭代優(yōu)化數(shù)據(jù)的子空間表示和原數(shù)據(jù)插補(bǔ)值，使子空間結(jié)構(gòu)更加穩(wěn)定可靠，最終利用穩(wěn)定的子空間結(jié)構(gòu)去識(shí)別數(shù)據(jù)的潛在聚類結(jié)構(gòu)。最后，在6個(gè)高維數(shù)據(jù)集上對(duì)該算法和已有算法進(jìn)行了實(shí)驗(yàn)分析，結(jié)果表明本文提出的KNN插補(bǔ)子空間聚類算法非常適合高維特征缺失數(shù)據(jù)的聚類分析。

1 相關(guān)工作

現(xiàn)實(shí)生活中的大量數(shù)據(jù)都存在一定程度的缺失，如何對(duì)缺失數(shù)據(jù)進(jìn)行聚類引起學(xué)者們的廣泛討論。目前對(duì)高維特征缺失數(shù)據(jù)聚類需要先進(jìn)行插補(bǔ)，然后在完整的高維數(shù)據(jù)集上進(jìn)行聚類。

已有插補(bǔ)算法可以分為兩大類：基于統(tǒng)計(jì)學(xué)的插補(bǔ)算法和基于機(jī)器學(xué)習(xí)的插補(bǔ)算法。

基于統(tǒng)計(jì)學(xué)的插補(bǔ)算法運(yùn)用統(tǒng)計(jì)學(xué)領(lǐng)域的算法對(duì)缺失數(shù)據(jù)進(jìn)行處理，如均值插補(bǔ)、冷平臺(tái)插補(bǔ)、熱平臺(tái)插補(bǔ)、回歸插補(bǔ)和模型插補(bǔ)等。Kalton等［13］在熱平臺(tái)插補(bǔ)法的基礎(chǔ)上提出樹枝分類的距離函數(shù)匹配法，使回歸插補(bǔ)和熱平臺(tái)插補(bǔ)存在的相關(guān)性和回歸系數(shù)偏差大的問題得到解決。Dempster等［14］提出的期望值最大化（Expectation Maximization， EM）算法在求解缺失值時(shí)可以加入求解目標(biāo)的額外約束。EM算法的不足在于：如果數(shù)據(jù)集中缺失值的比率過高，EM算法會(huì)因?yàn)榫徛氖諗亢头爆嵉挠?jì)算過程導(dǎo)致估計(jì)值與真實(shí)值的偏差過大。Little等［15］總結(jié)并克服了EM算法的不足，提出了多重插補(bǔ)（Multiple Imputation，MI）法。金勇進(jìn)［16］介紹了演繹估計(jì)、均值插補(bǔ)、隨機(jī)插補(bǔ)、回歸插補(bǔ)和多重插補(bǔ)算法的理論知識(shí)。熊巍等［17］結(jié)合修正的EM算法，提出了基于R型聚類的Lasso?分位回歸插補(bǔ)法，解決了高維成分?jǐn)?shù)據(jù)的近似零值問題。Lux等［18］為任意維度的線性插值提供了一種創(chuàng)新的誤差界定，將某些插值技術(shù)的性能與常用的回歸技術(shù)進(jìn)行了對(duì)比，并通過實(shí)驗(yàn)結(jié)果驗(yàn)證了插值對(duì)于中等高維稀疏問題的可行性。

基于機(jī)器學(xué)習(xí)的插補(bǔ)算法借鑒機(jī)器學(xué)習(xí)的各種算法對(duì)缺失數(shù)據(jù)進(jìn)行處理。武森等［19］針對(duì)分類變量不完備數(shù)據(jù)集定義約束容差集合差異度，直接計(jì)算不完備數(shù)據(jù)對(duì)象集合內(nèi)所有對(duì)象的總體相異程度，以不完備數(shù)據(jù)聚類的結(jié)果為基礎(chǔ)進(jìn)行缺失數(shù)據(jù)的填補(bǔ)，優(yōu)化了缺失數(shù)據(jù)的填補(bǔ)效果。陳靜杰等［20］通過計(jì)算QAR（Quick Access Recorder）數(shù)據(jù)樣本之間的標(biāo)準(zhǔn)歐氏距離選擇最近鄰樣本，利用熵值賦權(quán)法計(jì)算最近鄰的加權(quán)系數(shù)，基于最近鄰樣本中燃油流量的加權(quán)平均即可得到缺失燃油流量的估計(jì)值，有效插補(bǔ)了飛機(jī)油耗的缺失數(shù)據(jù)。Daberdaku等［21］使用特征之間的最大信息系數(shù)（Maximal Information Coefficient，MIC）作為距離計(jì)算的權(quán)重，整合患者自身和患者之間的信息。獨(dú)立測(cè)試線性插值和加權(quán)KNN插補(bǔ)算法為每個(gè)特性選擇最佳的插補(bǔ)方案，通過組合它們進(jìn)行最終插補(bǔ)，使重癥監(jiān)護(hù)室患者多次就診的縱向臨床實(shí)驗(yàn)室檢測(cè)結(jié)果的插補(bǔ)效果更顯著。陳帥等［22］通過發(fā)掘插補(bǔ)過程中非缺失數(shù)據(jù)的低秩特性，借助奇異值分解理論建立了魯棒性更強(qiáng)的SVD?KDR（Singular Value Decomposition? Known Data Regression）算法模型，有效減弱了缺失數(shù)據(jù)對(duì)參數(shù)估計(jì)精度的不利影響，所提算法在高缺失率下仍具有較高插補(bǔ)精度和穩(wěn)健性。

上述插補(bǔ)算法可以對(duì)不同情況的缺失數(shù)據(jù)進(jìn)行估計(jì)，得到較為準(zhǔn)確的插補(bǔ)。但是，由于沒有解決維度災(zāi)難問題，即使是經(jīng)過插補(bǔ)的高維特征缺失數(shù)據(jù)，聚類效果也表現(xiàn)不佳。

為了解決維度災(zāi)難問題，需要對(duì)高維數(shù)據(jù)進(jìn)行降維處理。對(duì)數(shù)據(jù)的降維過程需要滿足兩個(gè)基本條件：一是數(shù)據(jù)的維度應(yīng)該減少；二是需要有效地辨別數(shù)據(jù)中突出或隱藏的特性。將目標(biāo)數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)按行排列得到由原始數(shù)據(jù)集構(gòu)成的數(shù)據(jù)矩陣，從代數(shù)的角度分析，降維可看作是將原始數(shù)據(jù)點(diǎn)集構(gòu)成的數(shù)據(jù)矩陣分解為兩個(gè)因子矩陣相乘的過程。矩陣分解法［12］即可以對(duì)原始數(shù)據(jù)矩陣進(jìn)行分解，得到對(duì)應(yīng)的兩個(gè)低維的數(shù)據(jù)矩陣，從而實(shí)現(xiàn)對(duì)原始數(shù)據(jù)的降維。矩陣分解的過程中，目標(biāo)數(shù)據(jù)點(diǎn)集丟失的信息較少，可以較好地保留目標(biāo)數(shù)據(jù)中所包含的特征信息，因此可以利用矩陣分解法來學(xué)習(xí)高維數(shù)據(jù)集的子空間結(jié)構(gòu)。利用子空間進(jìn)行聚類可以解決高維數(shù)據(jù)的維度災(zāi)難問題，但是在學(xué)習(xí)數(shù)據(jù)子空間結(jié)構(gòu)時(shí)，會(huì)受到插補(bǔ)信息的影響，當(dāng)插補(bǔ)信息不適合時(shí)，得到的子空間結(jié)構(gòu)用于聚類表現(xiàn)不佳。因此，本文針對(duì)高維特征缺失數(shù)據(jù)提出一種新的插補(bǔ)聚類算法，該算法相較于其他插補(bǔ)聚類算法更加適合聚類分析。

2 面向高維特征缺失數(shù)據(jù)的KISC算法

2.1　高維特征缺失數(shù)據(jù)的插補(bǔ)聚類問題

2.2　KNN插補(bǔ)子空間聚類框架

KNN插補(bǔ)算法［23］是一種面向機(jī)器學(xué)習(xí)任務(wù)的被廣泛使用的數(shù)據(jù)插補(bǔ)算法。將KNN插補(bǔ)算法用于處理高維特征缺失數(shù)據(jù)時(shí)，由于維度災(zāi)難問題和數(shù)據(jù)缺失導(dǎo)致的樣本間距離度量方法失效問題，無法進(jìn)行有效插補(bǔ)，從而導(dǎo)致聚類效果不佳。為了解決上述問題，本文結(jié)合KNN插補(bǔ)算法和子空間聚類算法的優(yōu)點(diǎn)，提出一種面向高維特征缺失數(shù)據(jù)的KNN插補(bǔ)子空間聚類算法KISC。該算法的基本思想是：在潛在子空間下，同類數(shù)據(jù)距離相近，異類數(shù)據(jù)距離較遠(yuǎn)，求出高維特征缺失數(shù)據(jù)的子空間結(jié)構(gòu)可以解決樣本間的距離度量失效的問題；同時(shí)，低維結(jié)構(gòu)也能解決維度災(zāi)難問題，改善高維特征缺失數(shù)據(jù)的聚類效果。算法的框架如圖1所示。

表1　符號(hào)與定義

圖1　KISC算法框架

算法的核心步驟如下：

2.3　矩陣分解過程

首先使用矩陣分解算法學(xué)習(xí)高維特征缺失數(shù)據(jù)的子空間結(jié)構(gòu)，分解公式如下：

2.4　插補(bǔ)過程

利用式（7）求出子空間下所有數(shù)據(jù)之間的距離，從而可以得到缺失數(shù)據(jù)的近鄰樣本構(gòu)成的近鄰集。為了不被插補(bǔ)的數(shù)據(jù)誤導(dǎo)，本文在插補(bǔ)過程中加入一個(gè)約束條件，即：只使用原始數(shù)據(jù)集中的數(shù)據(jù)信息進(jìn)行插補(bǔ)。

2.5　KNN插補(bǔ)子空間聚類算法

學(xué)習(xí)高維特征缺失數(shù)據(jù)的子空間結(jié)構(gòu)，可以在子空間下挖掘出數(shù)據(jù)間的近鄰關(guān)系，從而解決KNN算法在高維和特征缺失情況下不能計(jì)算數(shù)據(jù)間有效距離的問題。同時(shí)，本文固定子空間的基矩陣，充分利用插補(bǔ)信息對(duì)子空間的影響，多次迭代KNN插補(bǔ)和矩陣分解過程，逐漸調(diào)整數(shù)據(jù)子空間的系數(shù)矩陣，使高維特征缺失數(shù)據(jù)的子空間結(jié)構(gòu)更加穩(wěn)定可靠，得到更好的聚類結(jié)果。KISC算法的具體流程如下：

根據(jù)式（7）計(jì)算所有數(shù)據(jù)間的有效距離；

end

3 實(shí)驗(yàn)與結(jié)果分析

3.1　實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文所提算法的有效性，本文選取了6個(gè)不同規(guī)模的高維數(shù)據(jù)集。數(shù)據(jù)集的詳細(xì)描述如表2所示。

表2　數(shù)據(jù)集描述

3.2　實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)都是在3.6 GHz CPU，8 GB內(nèi)存，Windows 10操作系統(tǒng)下完成的，本文算法采用Matlab2018b實(shí)現(xiàn)。

將實(shí)驗(yàn)對(duì)比過程分為兩部分：

1）為了證明子空間聚類的有效性，使用0值插補(bǔ)法、最大值插補(bǔ)法、最小值插補(bǔ)法、均值插補(bǔ)法、KNN插補(bǔ)法、EM插補(bǔ)法、矩陣分解（Matrix Factorization， MF）一次插補(bǔ)法共7種插補(bǔ)算法將高維特征缺失數(shù)據(jù)補(bǔ)全后，直接在數(shù)據(jù)的原始空間進(jìn)行聚類分析，并與KISC算法進(jìn)行比較。

2）為了驗(yàn)證本文算法KISC學(xué)到的子空間更適合高維特征缺失數(shù)據(jù)的聚類分析，使用以下算法與KISC進(jìn)行比較：①基于統(tǒng)計(jì)學(xué)的對(duì)比算法，包括0值插補(bǔ)法、最大值插補(bǔ)法、最小值插補(bǔ)法、均值插補(bǔ)法、EM插補(bǔ)法。利用這些插補(bǔ)算法將高維特征缺失數(shù)據(jù)補(bǔ)全后，對(duì)完整數(shù)據(jù)進(jìn)行矩陣分解得到高維數(shù)據(jù)的子空間結(jié)構(gòu)，并在該子空間結(jié)構(gòu)進(jìn)行聚類。②基于機(jī)器學(xué)習(xí)的對(duì)比算法，包括KNN插補(bǔ)法、MF法和MF一次插補(bǔ)法。MF法直接使用矩陣分解算法學(xué)習(xí)高維特征缺失數(shù)據(jù)的子空間結(jié)構(gòu)，并使用學(xué)習(xí)到的子空間結(jié)構(gòu)進(jìn)行聚類。MF一次插補(bǔ)法是在MF法的基礎(chǔ)上利用子空間下的近鄰關(guān)系補(bǔ)全高維特征缺失數(shù)據(jù)，再次使用矩陣分解學(xué)習(xí)完整數(shù)據(jù)的子空間結(jié)構(gòu)，不對(duì)子空間進(jìn)行調(diào)整，直接利用子空間進(jìn)行聚類。MF一次插補(bǔ)法與本文算法KISC的區(qū)別在于：直接使用完整數(shù)據(jù)首次矩陣分解得到的子空間進(jìn)行聚類，不對(duì)子空間結(jié)構(gòu)進(jìn)行調(diào)整。

3.3　評(píng)價(jià)指標(biāo)

本文使用的評(píng)價(jià)指標(biāo)為標(biāo)準(zhǔn)互信息（Normalized Mutual Information， NMI）和聚類精確度（ACCuracy， ACC）［26］。

3.4　實(shí)驗(yàn)結(jié)果分析

表3和表4列出了對(duì)比算法在6個(gè)圖像數(shù)據(jù)集原始空間的聚類性能。結(jié)果表明：相較于經(jīng)過插補(bǔ)后直接進(jìn)行聚類的對(duì)比算法，本文的KISC算法聚類效果更好，這說明子空間結(jié)構(gòu)能夠更加容易且有效地識(shí)別數(shù)據(jù)的潛在聚類結(jié)構(gòu)。

表3　在原始空間聚類結(jié)果的ACC值比較

表5和表6列出了對(duì)比算法在6個(gè)高維數(shù)據(jù)集子空間下的聚類性能。根據(jù)聚類效果，可以得出如下結(jié)論：

1）在缺失率相同的條件下，0值插補(bǔ)、最大值插補(bǔ)、最小值插補(bǔ)的聚類效果并不穩(wěn)定，而其他對(duì)比算法的聚類效果相對(duì)穩(wěn)定。缺失率為10%時(shí)，0值插補(bǔ)和最小值插補(bǔ)在Scene和3Sources數(shù)據(jù)集上的聚類效果與其他對(duì)比算法相近，在其余數(shù)據(jù)集上的聚類效果相對(duì)較差，這與高維特征缺失數(shù)據(jù)的結(jié)構(gòu)存在聯(lián)系。當(dāng)缺失率增加時(shí)，0值插補(bǔ)、最大值插補(bǔ)、最小值插補(bǔ)受到很大影響，聚類效果變化較大，而其他對(duì)比算法的聚類效果變化小。這說明不同插補(bǔ)信息會(huì)對(duì)高維特征缺失數(shù)據(jù)的潛在聚類結(jié)構(gòu)造成不同程度的影響，使用數(shù)據(jù)的整體信息進(jìn)行插補(bǔ)聚類，不僅可以改善聚類效果，而且加強(qiáng)了算法的魯棒性。

2）在算法相同的條件下，不同缺失率的數(shù)據(jù)對(duì)算法的影響不同。MF算法在處理低缺失率數(shù)據(jù)時(shí)，聚類性能與其他對(duì)比算法相近，但是當(dāng)缺失率高于30%時(shí)，MF算法的聚類效果急劇下降。說明數(shù)據(jù)缺失率較高時(shí)，只使用已知數(shù)據(jù)信息不易學(xué)到缺失數(shù)據(jù)的潛在聚類結(jié)構(gòu)。0值插補(bǔ)、最大值插補(bǔ)、最小值插補(bǔ)的聚類性能隨著缺失率的增加逐漸下降，這三種方法沒有利用樣本之間的全面信息，導(dǎo)致插補(bǔ)數(shù)據(jù)極大程度地扭曲了高維特征缺失數(shù)據(jù)的潛在聚類結(jié)構(gòu)，缺失率越高，對(duì)聚類結(jié)構(gòu)的破壞越大。KNN插補(bǔ)算法的聚類效果相對(duì)較好，但是，當(dāng)數(shù)據(jù)缺失率過高時(shí)，每條數(shù)據(jù)都會(huì)存在不同程度的缺失，無法滿足KNN插補(bǔ)算法所需條件，所以該算法部分聚類結(jié)果用nan（空值）表示。均值插補(bǔ)、EM插補(bǔ)、MF一次插補(bǔ)和KISC算法使用樣本之間的全面信息進(jìn)行插補(bǔ)聚類，聚類效果較好，并且受缺失率改變的影響較小。

3）KISC算法在各個(gè)數(shù)據(jù)集的聚類性能均優(yōu)于均值插補(bǔ)、KNN插補(bǔ)和EM插補(bǔ)算法，說明KISC可以更有效地利用數(shù)據(jù)之間的聯(lián)系，找到高維特征缺失數(shù)據(jù)適合聚類的潛在子空間結(jié)構(gòu)。同時(shí)，KISC也優(yōu)于矩陣分解法和矩陣分解一次插補(bǔ)算法的聚類性能，表明迭代插補(bǔ)過程可以優(yōu)化高維特征缺失數(shù)據(jù)的潛在聚類結(jié)構(gòu)。本文的KISC算法在大多數(shù)據(jù)集上的NMI和ACC值都是最優(yōu)的，表明它可以提升高維特征缺失數(shù)據(jù)的聚類性能。綜上所述，KISC算法更適合高維特征缺失數(shù)據(jù)的聚類分析。

表4　在原始空間聚類結(jié)果的NMI值比較

表5　不同插補(bǔ)算法+子空間聚類算法在子空間聚類結(jié)果的ACC值比較

表6　不同插補(bǔ)算法+子空間聚類算法在子空間聚類結(jié)果的NMI值比較

3.5　模型分析

3.5.1系數(shù)矩陣的收斂性分析

圖2　ORL數(shù)據(jù)集上缺失率為40%時(shí)，系數(shù)矩陣的變化情況

3.5.2參數(shù)分析

圖3　ORL數(shù)據(jù)集上缺失率為40%時(shí)，k和對(duì)聚類性能的影響

4 結(jié)語

本文針對(duì)高維特征缺失數(shù)據(jù)無法進(jìn)行有效插補(bǔ)聚類的問題，提出一種面向高維特征缺失數(shù)據(jù)的KNN插補(bǔ)子空間聚類算法KISC。該算法通過學(xué)習(xí)高維特征缺失數(shù)據(jù)的子空間結(jié)構(gòu)，運(yùn)用子空間下的近鄰關(guān)系對(duì)缺失數(shù)據(jù)進(jìn)行有效的迭代插補(bǔ)，并利用插補(bǔ)信息逐漸調(diào)整子空間結(jié)構(gòu)，使子空間結(jié)構(gòu)更加穩(wěn)定可靠，最后使用穩(wěn)定的子空間進(jìn)行聚類。在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示，該算法在NMI、ACC評(píng)價(jià)指標(biāo)上的效果都有所提高，驗(yàn)證了算法的有效性。然而，當(dāng)缺失數(shù)據(jù)存在大量噪聲時(shí)，將缺失數(shù)據(jù)作為KNN插補(bǔ)子空間聚類算法的輸入可能會(huì)使聚類精度大幅降低，因此，如何識(shí)別出噪聲數(shù)據(jù)，并對(duì)缺失數(shù)據(jù)進(jìn)行插補(bǔ)和聚類，需要被進(jìn)一步研究。

[1] CHEN L F， JIANG Q S. An extended EM algorithm for subspace clustering［J］. Frontiers of Computer Science in China， 2008， 2（1）： 81-86.

[2] ERT?Z L， STEINBACH M， KUMAR V. Finding clusters of different sizes， shapes， and densities in noisy， high dimensional data［C］// Proceedings of the 3rd SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2003： 47-58.

[3] WU X D， KUMAR V， QUINLAN J R， et al. Top 10 algorithms in data mining［J］. Knowledge and Information Systems， 2008， 14（1）： 1-37.

[4] MULLER K R， MIKA S， RATSCH G， et al. An introduction to kernel?based learning algorithms［J］. IEEE Transactions on Neural Networks， 2001， 12（2）： 181-201.

[5] LUXBURG U von. A tutorial on spectral clustering［J］. Statistics and Computing， 2007， 17（4）： 395-416.

[6] VIDAL R. Subspace clustering［J］. IEEE Signal Processing Magazine， 2011， 28（2）： 52-68.

[7] LUSCOMBE N M， GREENBAUM D， GERSTEIN M. What is bioinformatics？ a proposed definition and overview of the field［J］. Methods of Information in Medicine， 2001， 40（4）： 346-358.

[8] RAJENDRAN P， MADHESWARAN M. Hybrid medical image classification using association rule mining with decision tree algorithm［J］. Journal of Computing， 2010， 2（1）：127-136.

[9] BEEFERMAN D， BERGER A. Agglomerative clustering of a search engine query log［C］// Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2000： 407-416.

[10] SHI J B， MALIK J. Normalized cuts and image segmentation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（8）： 888-905.

[11] SHEPITSEN A， GEMMELL J， MOBASHER B， et al. Personalized recommendation in social tagging systems using hierarchical clustering［C］// Proceedings of the 2008 ACM Conference on Recommender Systems. New York： ACM， 2008： 259-266.

[12] LEE D D， SEUNG H S. Learning the parts of objects by non? negative matrix factorization［J］. Nature， 1999， 401（6755）： 788-791.

[13] KALTON G， KISH L. Some efficient random imputation methods［J］. Communications in Statistics ― Theory and Methods， 1984， 13（16）： 1919-1939.

[14] DEMPSTER A P， LAIRD N M， RUBIN D B. Maximum likelihood from incomplete data via the EM algorithm［J］. Journal of the Royal Statistical Society： Series B （Methodological）， 1977， 39（1）： 1-22.

[15] LITTLE R J A， RUBIN D B. Statistical Analysis with Missing Data［M］. 2nd ed. Hoboken， NJ： John Wiley & Sons， Inc.， 2002：200-220

[16] 金勇進(jìn). 缺失數(shù)據(jù)的插補(bǔ)調(diào)整［J］. 數(shù)理統(tǒng)計(jì)與管理， 2001， 20（6）： 47-53.（JIN Y J. Imputation adjustment for missing data［J］. Journal of Applied Statistics and Management， 2001， 20（6）： 47-53.）

[17] 熊巍，潘晗，劉立新. 穩(wěn)健高效的高維成分?jǐn)?shù)據(jù)近似零值插補(bǔ)方法及應(yīng)用［J］. 統(tǒng)計(jì)研究， 2020， 37（5）： 104-116.（XIONG W， PAN H， LIU L X. Robust efficient imputation of rounded zeros in high?dimensional compositional data and its applications［J］. Statistical Research， 2020， 37（5）： 104-116.）

[18] LUX T C H， WATSON L T， CHANG T H， et al. Interpolation of sparse high?dimensional data［J］. Numerical Algorithms， 2021， 88（1）： 281-313.

[19] 武森，馮小東，單志廣. 基于不完備數(shù)據(jù)聚類的缺失數(shù)據(jù)填補(bǔ)方法［J］. 計(jì)算機(jī)學(xué)報(bào)， 2012， 35（8）： 1726-1738.（WU S， FENG X D， SHAN Z G. Missing data imputation approach based on incomplete data clustering［J］. Chinese Journal of Computers， 2012， 35（8）： 1726-1738.）

[20] 陳靜杰，車潔. 基于標(biāo)準(zhǔn)歐氏距離的燃油流量缺失數(shù)據(jù)填補(bǔ)算法［J］. 計(jì)算機(jī)科學(xué)， 2017， 44（6A）： 109-111， 125.（CHEN J J， CHE J. Fuel flow missing?value imputation method based on standardized Euclidean distance［J］. Computer Science， 2017， 44（6A）： 109-111， 125.）

[21] DABERDAKU S， TAVAZZI E， DI CAMILLO B. A combined interpolation and weighted?nearest neighbours approach for the imputation of longitudinal ICU laboratory data［J］. Journal of Healthcare Informatics Research， 2020， 4（2）： 174-188.

[22] 陳帥，趙明，郭棟，等. 基于SVD?KDR算法的工業(yè)監(jiān)測(cè)數(shù)據(jù)插補(bǔ)技術(shù)［J］. 機(jī)械工程學(xué)報(bào)， 2021， 57（2）： 30-38.（CHEN S， ZHAO M， GUO D， et al. Missing data imputation using SVD? KDR algorithm in industrial monitoring data［J］. Journal of Mechanical Engineering， 2021， 57（2）： 30-38.）

[23] GARCíA?LAENCINA P J， SANCHO?GóMEZ J L， FIGUEIRAS? VIDAL A R， et al.nearest neighbours with mutual information for simultaneous classification and missing data imputation［J］. Neurocomputing， 2009， 72（7/8/9）： 1483-1493.

[24] 項(xiàng)亮. 推薦系統(tǒng)實(shí)踐［M］. 北京：人民郵電出版社， 2012： 64-72.（XIANG L. Recommender System Practice［M］. Beijing： Posts and Telecommunications Press， 2012： 64-72.）

[25] DEZA M M， DEZA E. Distances and similarities in data analysis［M］// Encyclopedia of Distances. 2nd ed. Berlin： Springer， 2013： 291-305.

[26] XU W， LIU X， GONG Y H. Document clustering based on non? negative matrix factorization［C］// Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2003： 267-273.

K?nearest neighbor imputation subspace clustering algorithm for high?dimensional data with feature missing

QIAO Yongjian1， LIU Xiaolin1，2， BAI Liang1，2*

（1，，030006，；2（），030006，）

During the clustering process of high?dimensional data with feature missing， there are problems of the curse of dimensionality caused by data high dimension and the invalidity of effective distance calculation between samples caused by data feature missing. To resolve above issues， a K?Nearest Neighbor （KNN） imputation subspace clustering algorithm for high?dimensional data with feature missing was proposed， namely KISC. Firstly， the nearest neighbor relationship in the subspace of the high?dimensional data with feature missing was used to perform KNN imputation on the feature missing data in the original space. Then， multiple iterations of matrix decomposition and KNN imputation were used to obtain the final reliable subspace structure of the data， and the clustering analysis was performed in that obtained subspace structure. The clustering results in the original space of six image datasets show that the KISC algorithm has better performance than the comparison algorithm which clusters directly after interpolation， indicating that the subspace structure can identify the potential clustering structure of the data more easily and effectively； the clustering results in the subspace of six high?dimensional datasets shows that the KISC algorithm outperforms the comparison algorithm in all datasets， and has the optimal clustering Accuracy and Normalized Mutual Information （NMI） on most of the datasets. The KISC algorithm can deal with high?dimensional data with feature missing more effectively and improve the clustering performance of these data.

high?dimensional data; feature missing; imputation algorithm; subspace structure; clustering

This work is partially supported by National Natural Science Foundation of China （62022052）， Shanxi Basic Research Program （201901D211192）， “1331 Project” Quality and Efficiency Improvement Construction Program of Shanxi Province.

QIAO Yongjian， born in 1995， M. S. candidate. His research interests include missing data clustering.

LIU Xiaolin， born in 1990， Ph. D. candidate. Her research interests include machine learning， clustering analysis.

BAI Liang， born in 1982， Ph. D.， professor. His research interests include clustering analysis.

1001-9081（2022）11-3322-08

10.11772/j.issn.1001-9081.2021111964

2021?11?19；

2021?11?29；

2021?12?06。

國(guó)家自然科學(xué)基金資助項(xiàng)目（62022052）；山西省基礎(chǔ)研究計(jì)劃項(xiàng)目（201901D211192）；山西省“1331工程”提質(zhì)增效建設(shè)計(jì)劃項(xiàng)目。

TP391

A

喬永堅(jiān)（1995—），男，山西臨汾人，碩士研究生，主要研究方向：缺失數(shù)據(jù)聚類；劉曉琳（1990—），女，山西太原人，博士研究生，CCF會(huì)員，主要研究方向：機(jī)器學(xué)習(xí)、聚類分析；白亮（1982—），男，山西太原人，教授，博士，CCF會(huì)員，主要研究方向：聚類分析。