基于马氏距离和H―K聚类的空值估计研究

　　摘 要：传统的基于欧氏距离和K-means聚类算法的空值估计算法容易因为欧氏距离对量纲的敏感性和初始聚类中心对K-means聚类效果的影响产生估值误差。将层次聚类算法和K-means聚类算法有机结合起来的H-K聚类算法克服了K-means算法对初始聚类中心的敏感性，从而改善了聚类效果。与欧氏距离不同，马氏距离可以避免量纲的影响。为此提出一种改进的空值估计算法，将H-K聚类应用到空值估计算法中进行聚类，在聚类时采用马氏距离代替欧氏距离，在聚类后使用多元线性回归法计算样本中的空值。实验结果表明改进后的空值估计算法使得估计值的绝对误差率（MAER）得到降低。 　　关键词：K-means算法；层次聚类；H-K聚类算法；马氏距离；空值估计 　　中图分类号：TP391.41 　　随着大数据时代的到来，发展日新月异的数据库技术和各类信息系统应用使得生活中数据的采集和存储日益便利，这为数据的海量化和复杂化奠定了基础。然而，爆炸式增长的数据中存在不完全数据的现象非常普遍，这使得一个具有表示和处理不完全数据能力的数据库系统不仅具有现实意义，更具有应用价值。 　　国外对不完全数据的研究起步较早，最早出现在全美的社会保险错误纠正[ ]，此后又出现了许多重要研究成果。1975年，ANSI（American National Standards Institute）在内部报告中提出用一种特殊的空值[ ]（null value）来表示这些不完全信息，奠定了处理不完全信息的基础。国内的相关研究起步较晚，尽管在部分学术期刊上也能见到这方面的文章，但直接针对缺失数据的原创性研究较少。台湾学者Chen、Huang等人提出了各种基于神经网络、统计学习和遗传算法等估计空值的方法[ ]，但是其计算过程比较复杂，得到的结论也不太容易让人理解，并且这些方法在确定相关联属性时，主观性色彩都太浓。早期具有代表性的成果有：金勇进在1998年探讨处理缺失数据时对辅助信息的利用问题[ ]和庞新生在2004年对多重填补算法的深入探讨和对多重插补法处理的基本思想[ ]。2006年乔珠峰使用朴素贝叶斯分类模型进行缺失值处理[ ]，2009年梁怡详细描述了均值填补法，并引入时间序列插补法进行了改进[ ]。 　　数据分类是空值估计算法中最重要的步骤，它直接影响含空值样本的分类和空值的估计。数据分类的算法有很多，其中比较经典的有K-means（K-均值）聚类算法和层次聚类算法。其中，K-means聚类算法有着广泛的应用，但是传统的K-means聚类算法只能保证收敛到局部最优，故而聚类结果对初始聚类中心的选择非常敏感；凝聚层次聚类虽无需选择初始的聚类中心，但是其计算复杂度较高并且凝聚过程不可逆。Chen Tung-Shou等人提出的结合了两种算法各自特点的H-K聚类算法[ ]（Hierarchical K-means），即通过层次聚类算法获得初始聚类中心而用K-means完善聚类过程，收到了更好的聚类效果。 　　无论是聚类还是估值，其精确度受到计算出的元组和聚类簇之间的距离的影响。传统的估值算法采用的是欧氏距离。欧氏距离对数据的量纲敏感，而马氏距离则可以克服量纲影响。 　　根据上述介绍，本文在已有的基于K-means聚类的空值估计算法的基础上，在聚类方面改用结合了层次聚类和K-means聚类的H-K聚类算法，并且在聚类和估值中采用马氏距离代替欧氏距离；在估值方面则采用多元线性回归法估计空值。本文提出的算法通过改善聚类效果降低估值误差率，达到优化目标。 　　1 基本算法 　　1.1 K-means聚类算法。K-means聚类算法是基于划分的聚类算法，在目前的聚类分析中应用最为广泛。K-means聚类的基本思想是首先从n个对象元素中任意选取K个作为初始聚类中心并计算剩余对象与这K个聚类中心的相似度（距离），将他们分配给与其最为相似（距离最短）的聚类，然后重新计算对应聚类的聚类中心。如此重复进行，直到标准测度函数（一般选取均方差作为标准测度函数）收敛为止。 　　K-means聚类算法的流程如下： 　　1.2 层次聚类。本论文提出的算法中采用了层次聚类方法中的AGNES（Agglomerative Nesting）算法。在聚类开始时先将每个对象作为一个簇，然后采用单连接（single-linkage）的方法计算簇间距离，即簇间距离等于两簇对象之间的最小距离，最后将距离最近的两个簇合并。聚类的合并过程反复进行直到所有的对象最终合并得到指定的簇数目。 　　层次聚类算法的流程如下： 　　输入：包含n个对象的数据集，算法终止时的簇数K。 　　输出：K个簇。 　　步骤1。将每个对象当成一个初始簇。 　　步骤2。根据两个簇中最近的对象找到最近的两个簇。 　　步骤3。合并最近的两个簇生成新的簇。 　　步骤4。若达到条件终止的簇数目则聚类完成；否则转到步骤2继续执行。 　　层次聚类算法的聚类质量较好，但是运算的时间复杂度和空间复杂度均较高。 　　1.3 H-K聚类算法。H-K聚类算法结合K-means聚类和层次聚类的优点，对K-means算法进行部分改进，得到了更高的运算效率和更好的聚类效果。H-K聚类算法首先采用层次聚类算法计算出初始聚类中心，再使用K-means聚类算法完善聚类结果，得到指定数目的簇。 　　H-K聚类算法的流程如下： 　　输入：包含n个对象的数据集，算法终止时的簇数K。 　　输出：K个簇。 　　步骤1。用1.2中所述的层次聚类算法求出初始聚类中心。 　　步骤2。用步骤1求出的聚类中心代替随机生成的聚类中心作为1.1中所述的K-means聚类算法的初始聚类中心，通过K-means的进一步聚类，求出K个簇。 　　1.4 多元线性回归算法。 　　步骤1。用一个解释变量表示所有可能的回归，检查其中一个拥有最大t值的变量，如果此时它对独立数据集合Y的贡献值低于实验设定值，则结束这个算法。 　　步骤2。如果存在一个t值高于实验指定t值的变量，并且它对当前的独立数据集Y的贡献最大，则将它作为下一个输入变量。 　　步骤3。如果存在一个t值低于实验指定t值的变量，并且它对当前的独立数据集Y的贡献最小，则将它作为下一个输出变量。 　　步骤4。重复上述步骤2、3，直到所有的对独立数据集合Y的贡献符合实验要求，二代变量被计算执行。 　　2 改进的空值估计算法 　　传统的空值估计算法是基于K-means聚类算法和欧氏距离的，本文给出一种基于引入马氏距离的H-K聚类算法的改进算法。 　　2.1 马氏距离替代欧式距离。马氏距离是由印度统计学家马哈拉诺比斯于1936年引入的，故称为马氏距离。这一距离在多元统计分析中起着十分重要的作用，下面给出定义。 　　2.2 基于马氏距离和H-K聚类算法的空值估计算法。由于欧氏距离对量纲的敏感性和传统K-means聚类对初始聚类中心的依赖性，本文将马氏距离引入H-K（Hierarchical K-means）聚类算法进行聚类，并采用多元线性回归法估计样本中的空值。具体的空值估计算法流程表示如下： 　　输入：数据集D，聚类簇个数K。 　　输出：样本中出现的空值的估值结果。 　　步骤1。对数据集进行预处理，使其便于在聚类时进行计算。 　　步骤2。用层次聚类算法进行聚类（采用马氏距离），求出所有的聚类中心Ci，i=1，…，N。 　　步骤3。将得到的这些聚类中心作为K-means聚类的初始聚类中心进行K-means聚类（采用马氏距离），得到K个聚类簇。 　　步骤4。计算含空值样本与各簇之间的马氏距离，求出距离最近的簇Ci。 　　步骤5。计算回归系数（即关联属性与待估计属性之间的影响力系数）和待估计样本与簇Ci之间的偏移量。 　　步骤6。根据回归系数和偏移量计算出待估计样本中空值的估计值。 　　3 实验与分析 　　实验环境：Windows 7操作系统，内存：2G；编程语言：Visual C++。 　　实验选用的数据集描述如下： 　　3.1 实验说明。（1）数据预处理过程中将对象“性别”，“身高”，“体重”，“肺活量”作为独立变量（Independent Variables，IV），将“耐力项目测试”作为相关变量（Dependent Variables，DV）。其中对象“耐力项目测试”中含有部分空值 。将“性别”转换为数值型数据以便于分析，其中“男”用1表示，“女”用“2”表示。将“耐力项目测试”的字符串型数据也转换为相应的数值型数据；（2）使用2所述的H-K聚类算法根据属性建立聚类簇，计算出空值元组所在聚类Ci和相应的回归系数（IV各属性和聚类Ci所对应的DV值之间的影响度βCi，IV）；（3）假设聚类Ci中第j个元组的贡献向量是（Gij，Hij，Wij，Vij，Eij）（1 j m，m是Ci中的元组数），其中G，H，W，V，E分别代表“性别”，“身高”，“体重”，“肺活量”，“耐力项目测试”。ΔIVDVi代表DV每发生一个单位的改变时，聚类 中各项的改变量。由此可得计算估计值Eestimated的公式：Eestimated=Ecenter-i+∑ΔIVDVi×（IVi-IVcenter-i），1≤i≤K；其中center-i是聚类Ci的聚类中心；（4）计算MAER值衡量空值估计数值Eestimated的准确性，以下是MAER的计算公式： 其中Eoriginal表示该空值对应的真实值，n表示测试数据的元组个数。 　　3.2 实验结果与分析。由表2可得结合马氏距离和H-K聚类的空值估计算法的MAER值为1.41%，略小于结合欧氏距离和H-K聚类的空值估计算法的MAER值1.63%，同样小于采用欧氏距离和传统K-means聚类的空值估计算法的MAER值1.97%，所以结合马氏距离和H-K聚类的空值估计算法在本例中估值效果最好。 　　4 结束语 　　传统的基于欧氏距离和K-means聚类的空值估计算法在聚类时容易受到数据的量纲和随机的初始聚类中心影响。本文提出的改进的空值估计算法采用马氏距离代替了欧氏距离，并使用结合了层次聚类的H-K聚类算法代替了传统的K-means聚类算法，在实验中得到了更好的聚类效果和误差率MAER值更低的空值估计值。除了以上优点，H-K聚类算法在计算复杂性上存在不足，其计算复杂性高于传统K-means算法，需要在今后做进一步的优化。 　　参考文献： 　　[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 null 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 null values using genetic algorithms[J].IEEE Transactions on Fuzzy Systems，2003（04）：495-506. 　　[4]金勇进.处理缺失数据中辅助信息的利用[J].统计研究，1998（01）：43-45. 　　[5]庞新生.缺失数据处理中相关问题的探讨[J].统计与信息论坛，2004（19）：30-33. 　　[6]乔珠峰，田凤占，黄厚宽.缺失数据处理方法的比较研究[J].计算机研究与发展，2006（43）：171-175. 　　[7]梁怡.缺失数据的插补调整方法[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，FU 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-），女，安徽合肥人，本科，研究方向：数据挖掘。 　　作者单位：南京航空航天大学 计算机科学与技术学院，南京 211106；计算机软件新技术国家重点实验室（南京大学），南京 210093