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

《基于马氏距离和h―k聚类的空值估计研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于马氏距离和H―K聚类的空值估计研究摘要：传统的基于欧氏距离和K-means聚类算法的空值估计算法容易因为欧氏距离对量纲的敏感性和初始聚类中心对K-means聚类效果的影响产生估值误差。将层次聚类算法和K-means聚类算法有机结合起来的H-K聚类算法克服了K-means算法对初始聚类中心的敏感性，从而改善了聚类效果。与欧氏距离不同，马氏距离可以避免量纲的影响。为此提出一种改进的空值估计算法，将H-K聚类应用到空值估计算法中进行聚类，在聚类时采用马氏距离代替欧氏距离，在聚类后使用多元线性回归法计算样本中的

2、空值。实验结果表明改进后的空值估计算法使得估计值的绝对误差率（MAER）得到降低。关键词：K-means算法；层次聚类；H-K聚类算法；马氏距离；空值估计中图分类号：TP391.41随着大数据时代的到来，发展日新月异的数据库技术和各类信息系统应用使得生活中数据的采集和存储日益便利，这为数据的海量化和复杂化奠定了基础。然而，爆炸式增长的数据中存在不完全数据的现象非常普遍，这使得一个具有表示和处理不完全数据能力的数据库系统不仅具有现实意义，更具有应用价值。11国外对不完全数据的研究起步较早，最早出现在全美的社会

3、保险错误纠正[]，此后又出现了许多重要研究成果。1975年，ANSI（AmericanNationalStandardsInstitute）在内部报告中提出用一种特殊的空值[]（nullvalue）来表示这些不完全信息，奠定了处理不完全信息的基础。国内的相关研究起步较晚，尽管在部分学术期刊上也能见到这方面的文章，但直接针对缺失数据的原创性研究较少。台湾学者Chen、Huang等人提出了各种基于神经网络、统计学习和遗传算法等估计空值的方法[]，但是其计算过程比较复杂，得到的结论也不太容易让人理解，并且这些方法

4、在确定相关联属性时，主观性色彩都太浓。早期具有代表性的成果有：金勇进在1998年探讨处理缺失数据时对辅助信息的利用问题[]和庞新生在2004年对多重填补算法的深入探讨和对多重插补法处理的基本思想[]。2006年乔珠峰使用朴素贝叶斯分类模型进行缺失值处理[]，2009年梁怡详细描述了均值填补法，并引入时间序列插补法进行了改进[]。11数据分类是空值估计算法中最重要的步骤，它直接影响含空值样本的分类和空值的估计。数据分类的算法有很多，其中比较经典的有K-means（K-均值）聚类算法和层次聚类算法。其中，K-m

5、eans聚类算法有着广泛的应用，但是传统的K-means聚类算法只能保证收敛到局部最优，故而聚类结果对初始聚类中心的选择非常敏感；凝聚层次聚类虽无需选择初始的聚类中心，但是其计算复杂度较高并且凝聚过程不可逆。ChenTung-Shou等人提出的结合了两种算法各自特点的H-K聚类算法[]（HierarchicalK-means），即通过层次聚类算法获得初始聚类中心而用K-means完善聚类过程，收到了更好的聚类效果。无论是聚类还是估值，其精确度受到计算出的元组和聚类簇之间的距离的影响。传统的估值算法采用的是欧

6、氏距离。欧氏距离对数据的量纲敏感，而马氏距离则可以克服量纲影响。根据上述介绍，本文在已有的基于K-means聚类的空值估计算法的基础上，在聚类方面改用结合了层次聚类和K-means聚类的H-K聚类算法，并且在聚类和估值中采用马氏距离代替欧氏距离；在估值方面则采用多元线性回归法估计空值。本文提出的算法通过改善聚类效果降低估值误差率，达到优化目标。1基本算法1.111K-means聚类算法。K-means聚类算法是基于划分的聚类算法，在目前的聚类分析中应用最为广泛。K-means聚类的基本思想是首先从n个对象元

7、素中任意选取K个作为初始聚类中心并计算剩余对象与这K个聚类中心的相似度（距离），将他们分配给与其最为相似（距离最短）的聚类，然后重新计算对应聚类的聚类中心。如此重复进行，直到标准测度函数（一般选取均方差作为标准测度函数）收敛为止。K-means聚类算法的流程如下：1.2层次聚类。本论文提出的算法中采用了层次聚类方法中的AGNES（AgglomerativeNesting）算法。在聚类开始时先将每个对象作为一个簇，然后采用单连接（single-linkage）的方法计算簇间距离，即簇间距离等于两簇对象之间的最

8、小距离，最后将距离最近的两个簇合并。聚类的合并过程反复进行直到所有的对象最终合并得到指定的簇数目。层次聚类算法的流程如下：输入：包含n个对象的数据集，算法终止时的簇数K。输出：K个簇。步骤1。将每个对象当成一个初始簇。步骤2。根据两个簇中最近的对象找到最近的两个簇。步骤3。合并最近的两个簇生成新的簇。步骤4。若达到条件终止的簇数目则聚类完成；否则转到步骤2继续执行。层次聚类算法的聚类质量较好，但是运算的时间复杂度