0引言
随着大数据时代的到来，发展日新月异的数据库技术和各类信息系统应用使得生活中数据的采集和存储日益便利，这为数据的海量化和复杂化奠定了基础。然而，爆炸式增长的数据中存在不完全数据的现象非常普遍，这使得一个具有表示和处理不完全数据能力的数据库系统不仅具有现实意义，更具有应用价值。
1 基本算法
1.1 K-means聚类算法
K-means聚类算法是基于划分的聚类算法，在目前的聚类分析中应用最为广泛。K-means聚类的基本思想是首先从n个对象元素中任意选取K个作为初始聚类中心并计算剩余对象与这K个聚类中心的相似度（距离），将他们分配给与其最为相似（距离最短）的聚类，然后重新计算对应聚类的聚类中心。如此重复进行，直到标准测度函数（一般选取均方差作为标准测度函数）收敛为止。
1.2 层次聚类
本论文提出的算法中采用了层次聚类方法中的AGNES（Agglomerative Nesting）算法。在聚类开始时先将每个对象作为一个簇，然后采用单连接（single-linkage）的方法计算簇间距离，即簇间距离等于两簇对象之间的最小距离，最后将距离最近的两个簇合并。聚类的合并过程反复进行直到所有的对象最终合并得到指定的簇数目。
层次聚类算法的流程如下：
输出：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 多元线性回归算法
多元线性回归法一般用来研究3个以上独立变量间存在的数学关系，它是对传统单因子线性回归法的扩展，其数学模型如公式（1）所示
（1）
其中 表示独立数据集合Y中的一系列数值； 表示数据集合Y同数据集合 的部分相关系数； 表示独立变量 中的已知数值（非NULL）。此外，引入一个服从 分布的随机变量 模拟现实数据的随机性。
（1）式中相关系数 的计算，通常采用逐步回归的方法。逐步回归法由一系列迭代组成，而每一次的迭代又可分为往回归模型移入变量和移出变量两部分组成。其算法大致步骤如下：
步骤 1 用一个解释变量表示所有可能的回归，检查其中一个拥有最大t值的变量，如果此时它对独立数据集合Y的贡献值低于实验设定值，则结束这个算法；
步骤 2 如果存在一个t值高于实验指定t值的变量，并且它对当前的独立数据集Y的贡献最大，则将它作为下一个输入变量；
步骤 3 如果存在一个t值低于实验指定t值的变量，并且它对当前的独立数据集Y的贡献最小，则将它作为下一个输出变量；
步骤 4 重复上述步骤2、3，直到所有的对独立数据集合Y的贡献符合实验要求，二代变量被计算执行。
2 改进的空值估计算法
传统的空值估计算法是基于K-means聚类算法和欧氏距离的，本文给出一种基于引入马氏距离的H-K聚类算法的改进算法。
2.1 马氏距离替代欧式距离
马氏距离是由印度统计学家马哈拉诺比斯于1936年引入的，故称为马氏距离。这一距离在多元统计分析中起着十分重要的作用，下面给出定义。
设 表示协方差矩阵，即
如果 存在，则两个样品之间的马氏距离为
其中 , 分别代表样本 , 的p个指标组成的向量。
样品X到总体G的马氏距离定义为
其中 为总体的均值向量， 为协方差阵。
欧氏距离受量纲影响较大，数量级大的数值会影响小数量级数值的体现。马氏距离不受量纲的影响，它不但排除了样本之间相关性的干扰，而且不受线性变换的影响。相对于欧氏距离而言，马氏距离运用在聚类算法中会提高计算和聚类的准确度。本文提出的改进的空值估计算法就是将传统H-K算法聚类时采用的欧氏距离改为马氏距离，通过改善聚类效果来改善空值估计的误差率。
2.2 基于马氏距离和H-K聚类算法的空值估计算法
由于欧氏距离对量纲的敏感性和传统K-means聚类对初始聚类中心的依赖性，本文将马氏距离引入H-K（Hierarchical K-means）聚类算法进行聚类，并采用多元线性回归法估计样本中的空值。具体的空值估计算法流程表示如下：
输入：数据集D，聚类簇个数K；
输出：样本中出现的空值的估值结果；
步骤 1 对数据集进行预处理，使其便于在聚类时进行计算；
步骤 2 用层次聚类算法进行聚类（采用马氏距离），求出所有的聚类中心 ， ；
步骤3将得到的这些聚类中心作为K-means聚类的初始聚类中心进行K-means聚类（采用马氏距离），得到K个聚类簇；
步骤 4 计算含空值样本与各簇之间的马氏距离，求出距离最近的簇 ；
步骤 5 计算回归系数（即关联属性与待估计属性之间的影响力系数）和待估计样本与簇 之间的偏移量；
步骤 7 根据回归系数和偏移量计算出待估计样本中空值的估计值。
3.1 实验说明
（1）数据预处理过程中将对象“性别”，“身高”，“体重”，“肺活量”作为独立变量（Independent Variables，IV），将“耐力项目测试”作为相关变量（Dependent Variables，DV）。其中对象“耐力项目测试”中含有部分空值 。将“性别”转换为数值型数据以便于分析，其中“男”用1表示，“女”用“2”表示。将“耐力项目测试”的字符串型数据也转换为相应的数值型数据。
（2）使用2所述的H-K聚类算法根据属性建立聚类簇，计算出空值元组所在聚类 和相应的回归系数（IV各属性和聚类 所对应的DV值之间的影响度 ）。
（3）假设聚类 中第j个元组的贡献向量是 （1 j m，m是 中的元组数），其中G，H，W，V，E分别代表“性别”，“身高”，“体重”，“肺活量”，“耐力项目测试”。 代表DV每发生一个单位的改变时，聚类 中各项的改变量。由此可得计算估计值 的公式：
其中center-i是聚类 的聚类中心；
传统的基于欧氏距离和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, 11(4):495-506.
[[4]] 金勇进.处理缺失数据中辅助信息的利用[J].统计研究，1998，（01）：43-45.
[[5]] 庞新生.缺失数据处理中相关问题的探讨[J].统计与信息论坛,2004,19(05):30-33.
[[6]] 乔珠峰，田凤占，黄厚宽，陈景年.缺失数据处理方法的比较研究[J].计算机研究与发展，2006,43(增刊）：171-175.
[[7]] 梁怡.缺失数据的插补调整方法[J].西安文理学院学报,2009,12(01):74-76.
[[8]] CHEN TUNG-SHOU, TSAR TZU-HSIN, CHEN YI-TZU. A combined K-means and hierarchical clustering efficiency of microarray[C]. Proceedings of 2005 International Symposium on Intelligent Signal Processing and Communication System, 2005.
[9] ANUPAMA CHADHA, SURESH KUMAR. An improved K-means clustering algorithm: a step forward for removal of dependency on K[J]. 2014 International Conference on Reliability, Optimization and Information Technology(ICROIT 2014), 2014.
[10] PRITHA MAHATA. Exploratory consensus of hierarchical clusterings for melanoma and breast cancer[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2010, 7(1):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, 2(1).
[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(1):142-147.
[14] M.EMRE CELEBI, HASSAN A.KINGRAVI, PATRICIO A.VELA. A comparative study of efficient initialization methods for the K-means clustering algorithm[J]. Expert Systems with Applications, 2013, 40(1):200-210.
[17] Ton J.CLEOPHAS, AEILKO H.ZWINDERMAN. Hierarchical clustering and K-means clustering to identify subgroups in surveys(50 p
atients)[J]. Machine Learning in Medicine-Cookbook, 2014.
,
