基于馬氏距離和H—K聚類的空值估計研究

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

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

中圖分類號：TP391.41

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

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

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

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

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

1 基本算法

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

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

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

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

輸入：包含n個對象的數(shù)據(jù)集，算法終止時的簇數(shù)K。

輸出：K個簇。

步驟1。將每個對象當成一個初始簇。

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

步驟3。合并最近的兩個簇生成新的簇。

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

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

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

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

輸入：包含n個對象的數(shù)據(jù)集，算法終止時的簇數(shù)K。

輸出：K個簇。

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

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

1.4 多元線性回歸算法。

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

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

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

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

2 改進的空值估計算法

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

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

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

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

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

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

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

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

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

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

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

3 實驗與分析

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

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

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

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

4 結(jié)束語

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

參考文獻：

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

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

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

[7]梁怡.缺失數(shù)據(jù)的插補調(diào)整方法[J].西安文理學院學報，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.

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

作者單位：南京航空航天大學 計算機科學與技術(shù)學院，南京 211106；計算機軟件新技術(shù)國家重點實驗室（南京大學），南京 210093