摘 要：傳統(tǒng)的基于歐氏距離和K-means聚類算法的空值估計(jì)算法容易因?yàn)闅W氏距離對量綱的敏感性和初始聚類中心對K-means聚類效果的影響產(chǎn)生估值誤差。將層次聚類算法和K-means聚類算法有機(jī)結(jié)合起來的H-K聚類算法克服了K-means算法對初始聚類中心的敏感性，從而改善了聚類效果。與歐氏距離不同，馬氏距離可以避免量綱的影響。為此提出一種改進(jìn)的空值估計(jì)算法，將H-K聚類應(yīng)用到空值估計(jì)算法中進(jìn)行聚類，在聚類時(shí)采用馬氏距離代替歐氏距離，在聚類后使用多元線性回歸法計(jì)算樣本中的空值。實(shí)驗(yàn)結(jié)果表明改進(jìn)后的空值估計(jì)算法使得估計(jì)值的絕對誤差率（MAER）得到降低。

關(guān)鍵詞：K-means算法；層次聚類；H-K聚類算法；馬氏距離；空值估計(jì)

中圖分類號：TP391.41

隨著大數(shù)據(jù)時(shí)代的到來，發(fā)展日新月異的數(shù)據(jù)庫技術(shù)和各類信息系統(tǒng)應(yīng)用使得生活中數(shù)據(jù)的采集和存儲日益便利，這為數(shù)據(jù)的海量化和復(fù)雜化奠定了基礎(chǔ)。然而，爆炸式增長的數(shù)據(jù)中存在不完全數(shù)據(jù)的現(xiàn)象非常普遍，這使得一個(gè)具有表示和處理不完全數(shù)據(jù)能力的數(shù)據(jù)庫系統(tǒng)不僅具有現(xiàn)實(shí)意義，更具有應(yīng)用價(jià)值。

國外對不完全數(shù)據(jù)的研究起步較早，最早出現(xiàn)在全美的社會保險(xiǎn)錯(cuò)誤糾正[ ]，此后又出現(xiàn)了許多重要研究成果。1975年，ANSI（American National Standards Institute）在內(nèi)部報(bào)告中提出用一種特殊的空值[ ]（1 value）來表示這些不完全信息，奠定了處理不完全信息的基礎(chǔ)。國內(nèi)的相關(guān)研究起步較晚，盡管在部分學(xué)術(shù)期刊上也能見到這方面的文章，但直接針對缺失數(shù)據(jù)的原創(chuàng)性研究較少。臺灣學(xué)者Chen、Huang等人提出了各種基于神經(jīng)網(wǎng)絡(luò)、統(tǒng)計(jì)學(xué)習(xí)和遺傳算法等估計(jì)空值的方法[ ]，但是其計(jì)算過程比較復(fù)雜，得到的結(jié)論也不太容易讓人理解，并且這些方法在確定相關(guān)聯(lián)屬性時(shí)，主觀性色彩都太濃。早期具有代表性的成果有：金勇進(jìn)在1998年探討處理缺失數(shù)據(jù)時(shí)對輔助信息的利用問題[ ]和龐新生在2004年對多重填補(bǔ)算法的深入探討和對多重插補(bǔ)法處理的基本思想[ ]。2006年喬珠峰使用樸素貝葉斯分類模型進(jìn)行缺失值處理[ ]，2009年梁怡詳細(xì)描述了均值填補(bǔ)法，并引入時(shí)間序列插補(bǔ)法進(jìn)行了改進(jìn)[ ]。

數(shù)據(jù)分類是空值估計(jì)算法中最重要的步驟，它直接影響含空值樣本的分類和空值的估計(jì)。數(shù)據(jù)分類的算法有很多，其中比較經(jīng)典的有K-means（K-均值）聚類算法和層次聚類算法。其中，K-means聚類算法有著廣泛的應(yīng)用，但是傳統(tǒng)的K-means聚類算法只能保證收斂到局部最優(yōu)，故而聚類結(jié)果對初始聚類中心的選擇非常敏感；凝聚層次聚類雖無需選擇初始的聚類中心，但是其計(jì)算復(fù)雜度較高并且凝聚過程不可逆。Chen Tung-Shou等人提出的結(jié)合了兩種算法各自特點(diǎn)的H-K聚類算法[ ]（Hierarchical K-means），即通過層次聚類算法獲得初始聚類中心而用K-means完善聚類過程，收到了更好的聚類效果。

無論是聚類還是估值，其精確度受到計(jì)算出的元組和聚類簇之間的距離的影響。傳統(tǒng)的估值算法采用的是歐氏距離。歐氏距離對數(shù)據(jù)的量綱敏感，而馬氏距離則可以克服量綱影響。

根據(jù)上述介紹，本文在已有的基于K-means聚類的空值估計(jì)算法的基礎(chǔ)上，在聚類方面改用結(jié)合了層次聚類和K-means聚類的H-K聚類算法，并且在聚類和估值中采用馬氏距離代替歐氏距離；在估值方面則采用多元線性回歸法估計(jì)空值。本文提出的算法通過改善聚類效果降低估值誤差率，達(dá)到優(yōu)化目標(biāo)。

1 基本算法

1.1 K-means聚類算法。K-means聚類算法是基于劃分的聚類算法，在目前的聚類分析中應(yīng)用最為廣泛。K-means聚類的基本思想是首先從n個(gè)對象元素中任意選取K個(gè)作為初始聚類中心并計(jì)算剩余對象與這K個(gè)聚類中心的相似度（距離），將他們分配給與其最為相似（距離最短）的聚類，然后重新計(jì)算對應(yīng)聚類的聚類中心。如此重復(fù)進(jìn)行，直到標(biāo)準(zhǔn)測度函數(shù)（一般選取均方差作為標(biāo)準(zhǔn)測度函數(shù)）收斂為止。

K-means聚類算法的流程如下：

1.2 層次聚類。本論文提出的算法中采用了層次聚類方法中的AGNES（Agglomerative Nesting）算法。在聚類開始時(shí)先將每個(gè)對象作為一個(gè)簇，然后采用單連接（single-linkage）的方法計(jì)算簇間距離，即簇間距離等于兩簇對象之間的最小距離，最后將距離最近的兩個(gè)簇合并。聚類的合并過程反復(fù)進(jìn)行直到所有的對象最終合并得到指定的簇?cái)?shù)目。

層次聚類算法的流程如下：

輸入：包含n個(gè)對象的數(shù)據(jù)集，算法終止時(shí)的簇?cái)?shù)K。

輸出：K個(gè)簇。

步驟1。將每個(gè)對象當(dāng)成一個(gè)初始簇。

步驟2。根據(jù)兩個(gè)簇中最近的對象找到最近的兩個(gè)簇。

步驟3。合并最近的兩個(gè)簇生成新的簇。

步驟4。若達(dá)到條件終止的簇?cái)?shù)目則聚類完成；否則轉(zhuǎn)到步驟2繼續(xù)執(zhí)行。

層次聚類算法的聚類質(zhì)量較好，但是運(yùn)算的時(shí)間復(fù)雜度和空間復(fù)雜度均較高。

1.3 H-K聚類算法。H-K聚類算法結(jié)合K-means聚類和層次聚類的優(yōu)點(diǎn)，對K-means算法進(jìn)行部分改進(jìn)，得到了更高的運(yùn)算效率和更好的聚類效果。H-K聚類算法首先采用層次聚類算法計(jì)算出初始聚類中心，再使用K-means聚類算法完善聚類結(jié)果，得到指定數(shù)目的簇。

H-K聚類算法的流程如下：

輸入：包含n個(gè)對象的數(shù)據(jù)集，算法終止時(shí)的簇?cái)?shù)K。

輸出：K個(gè)簇。

步驟1。用1.2中所述的層次聚類算法求出初始聚類中心。

步驟2。用步驟1求出的聚類中心代替隨機(jī)生成的聚類中心作為1.1中所述的K-means聚類算法的初始聚類中心，通過K-means的進(jìn)一步聚類，求出K個(gè)簇。

1.4 多元線性回歸算法。

步驟1。用一個(gè)解釋變量表示所有可能的回歸，檢查其中一個(gè)擁有最大t值的變量，如果此時(shí)它對獨(dú)立數(shù)據(jù)集合Y的貢獻(xiàn)值低于實(shí)驗(yàn)設(shè)定值，則結(jié)束這個(gè)算法。

步驟2。如果存在一個(gè)t值高于實(shí)驗(yàn)指定t值的變量，并且它對當(dāng)前的獨(dú)立數(shù)據(jù)集Y的貢獻(xiàn)最大，則將它作為下一個(gè)輸入變量。

步驟3。如果存在一個(gè)t值低于實(shí)驗(yàn)指定t值的變量，并且它對當(dāng)前的獨(dú)立數(shù)據(jù)集Y的貢獻(xiàn)最小，則將它作為下一個(gè)輸出變量。

步驟4。重復(fù)上述步驟2、3，直到所有的對獨(dú)立數(shù)據(jù)集合Y的貢獻(xiàn)符合實(shí)驗(yàn)要求，二代變量被計(jì)算執(zhí)行。

2 改進(jìn)的空值估計(jì)算法

傳統(tǒng)的空值估計(jì)算法是基于K-means聚類算法和歐氏距離的，本文給出一種基于引入馬氏距離的H-K聚類算法的改進(jìn)算法。

2.1 馬氏距離替代歐式距離。馬氏距離是由印度統(tǒng)計(jì)學(xué)家馬哈拉諾比斯于1936年引入的，故稱為馬氏距離。這一距離在多元統(tǒng)計(jì)分析中起著十分重要的作用，下面給出定義。

2.2 基于馬氏距離和H-K聚類算法的空值估計(jì)算法。由于歐氏距離對量綱的敏感性和傳統(tǒng)K-means聚類對初始聚類中心的依賴性，本文將馬氏距離引入H-K（Hierarchical K-means）聚類算法進(jìn)行聚類，并采用多元線性回歸法估計(jì)樣本中的空值。具體的空值估計(jì)算法流程表示如下：

輸入：數(shù)據(jù)集D，聚類簇個(gè)數(shù)K。

輸出：樣本中出現(xiàn)的空值的估值結(jié)果。

步驟1。對數(shù)據(jù)集進(jìn)行預(yù)處理，使其便于在聚類時(shí)進(jìn)行計(jì)算。

步驟2。用層次聚類算法進(jìn)行聚類（采用馬氏距離），求出所有的聚類中心Ci，i=1，…，N。

步驟3。將得到的這些聚類中心作為K-means聚類的初始聚類中心進(jìn)行K-means聚類（采用馬氏距離），得到K個(gè)聚類簇。

步驟4。計(jì)算含空值樣本與各簇之間的馬氏距離，求出距離最近的簇Ci。

步驟5。計(jì)算回歸系數(shù)（即關(guān)聯(lián)屬性與待估計(jì)屬性之間的影響力系數(shù)）和待估計(jì)樣本與簇Ci之間的偏移量。

步驟6。根據(jù)回歸系數(shù)和偏移量計(jì)算出待估計(jì)樣本中空值的估計(jì)值。

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

實(shí)驗(yàn)環(huán)境：Windows 7操作系統(tǒng)，內(nèi)存：2G；編程語言：Visual C++。

實(shí)驗(yàn)選用的數(shù)據(jù)集描述如下：

3.1 實(shí)驗(yàn)說明。（1）數(shù)據(jù)預(yù)處理過程中將對象“性別”，“身高”，“體重”，“肺活量”作為獨(dú)立變量（Independent Variables，IV），將“耐力項(xiàng)目測試”作為相關(guān)變量（Dependent Variables，DV）。其中對象“耐力項(xiàng)目測試”中含有部分空值 。將“性別”轉(zhuǎn)換為數(shù)值型數(shù)據(jù)以便于分析，其中“男”用1表示，“女”用“2”表示。將“耐力項(xiàng)目測試”的字符串型數(shù)據(jù)也轉(zhuǎn)換為相應(yīng)的數(shù)值型數(shù)據(jù)；（2）使用2所述的H-K聚類算法根據(jù)屬性建立聚類簇，計(jì)算出空值元組所在聚類Ci和相應(yīng)的回歸系數(shù)（IV各屬性和聚類Ci所對應(yīng)的DV值之間的影響度βCi，IV）；（3）假設(shè)聚類Ci中第j個(gè)元組的貢獻(xiàn)向量是（Gij，Hij，Wij，Vij，Eij）（1 j m，m是Ci中的元組數(shù)），其中G，H，W，V，E分別代表“性別”，“身高”，“體重”，“肺活量”，“耐力項(xiàng)目測試”。ΔIVDVi代表DV每發(fā)生一個(gè)單位的改變時(shí)，聚類 中各項(xiàng)的改變量。由此可得計(jì)算估計(jì)值Eestimated的公式：Eestimated=Ecenter-i+∑ΔIVDVi×（IVi-IVcenter-i），1≤i≤K；其中center-i是聚類Ci的聚類中心；（4）計(jì)算MAER值衡量空值估計(jì)數(shù)值Eestimated的準(zhǔn)確性，以下是MAER的計(jì)算公式： 其中Eoriginal表示該空值對應(yīng)的真實(shí)值，n表示測試數(shù)據(jù)的元組個(gè)數(shù)。

3.2 實(shí)驗(yàn)結(jié)果與分析。由表2可得結(jié)合馬氏距離和H-K聚類的空值估計(jì)算法的MAER值為1.41%，略小于結(jié)合歐氏距離和H-K聚類的空值估計(jì)算法的MAER值1.63%，同樣小于采用歐氏距離和傳統(tǒng)K-means聚類的空值估計(jì)算法的MAER值1.97%，所以結(jié)合馬氏距離和H-K聚類的空值估計(jì)算法在本例中估值效果最好。

4 結(jié)束語

傳統(tǒng)的基于歐氏距離和K-means聚類的空值估計(jì)算法在聚類時(shí)容易受到數(shù)據(jù)的量綱和隨機(jī)的初始聚類中心影響。本文提出的改進(jìn)的空值估計(jì)算法采用馬氏距離代替了歐氏距離，并使用結(jié)合了層次聚類的H-K聚類算法代替了傳統(tǒng)的K-means聚類算法，在實(shí)驗(yàn)中得到了更好的聚類效果和誤差率MAER值更低的空值估計(jì)值。除了以上優(yōu)點(diǎn)，H-K聚類算法在計(jì)算復(fù)雜性上存在不足，其計(jì)算復(fù)雜性高于傳統(tǒng)K-means算法，需要在今后做進(jìn)一步的優(yōu)化。

參考文獻(xiàn)：

[1]BATISTA G E，MENARDS M C.A study of K-nearest neighbor as a model-based method to treat missing data[J].Proceedings of the Argentine Symposium on Artificial Intelligence，2003（30）：1-9.

[2]C.ZANIOLO.Database relations with 1 values[J].Proceedings of the 1st ACM SIGACT-SIGMOD Symposium on Principles of Database Systems，Los Angeles，California，U.S.A.，ACM Press，1982：27-33.

[3]S.M.CHEN，C.M.HUANG.Generating weighted fuzzy rules from relational database systems for estimating 1 values using genetic algorithms[J].IEEE Transactions on Fuzzy Systems，2003（04）：495-506.

[4]金勇進(jìn).處理缺失數(shù)據(jù)中輔助信息的利用[J].統(tǒng)計(jì)研究，1998（01）：43-45.

[5]龐新生.缺失數(shù)據(jù)處理中相關(guān)問題的探討[J].統(tǒng)計(jì)與信息論壇，2004（19）：30-33.

[6]喬珠峰，田鳳占，黃厚寬.缺失數(shù)據(jù)處理方法的比較研究[J].計(jì)算機(jī)研究與發(fā)展，2006（43）：171-175.

[7]梁怡.缺失數(shù)據(jù)的插補(bǔ)調(diào)整方法[J].西安文理學(xué)院學(xué)報(bào)，2009（12）：74-76.

[8]CHEN TUNG-SHOU，TSAR TZU-HSIN，CHEN YI-TZU.A combined K-means and hierarchical clustering efficiency of microarray[A].Proceedings of 2005 International Symposium on Intelligent Signal Processing and Communication System[C]，2005.

[9]ANUPAMA CHADHA，SURESH KUMAR.An improved K-means clustering algorithm：a step forward for removal of dependency on K[A].2014 International Conference on Reliability，Optimization and Information Technology[C]，2014.

[10]PRITHA MAHATA.Exploratory consensus of hierarchical clusterings for melanoma and breast cancer[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics，2010（07）：138-152.

[11]JASVINDER KAUR，GAURAV GUPTA.Optimized clustering algorithm with hybrid K-Means and hierarchical algorithms[J].International Journal for Multi-Disciplinary Engineering and Business Management，2014（02）.

[12]WANG LING，F(xiàn)U DONGMEI，LI QING，MU ZHICHUN.Modeling method with missing values based on clustering and support vector regression[J].Journal of Systems Engineering and Electronics，2010（21）：142-147.

[13]M.EMRE CELEBI，HASSAN A.KINGRAVI，PATRICIO A.VELA.Acomparative study of efficient initialization methods for the K-means clustering algorithm[J].Expert Systems with Applications，2013（40）：200-210.

[14]Ton J.CLEOPHAS，AEILKO H.ZWINDERMAN.Hierarchical clustering and K-means clustering to identify subgroups in surveys（50 patients）[J].Machine Learning in Medicine-Cookbook，2014.

作者簡介：陳睿進(jìn)（1994-），女，安徽合肥人，本科，研究方向：數(shù)據(jù)挖掘。

作者單位：南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106；計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室（南京大學(xué)），南京 210093