不完备数据处理及应用

不完备数据处理及应用摘要：缺失数据的处理是数据挖掘领域进行数据预处理的一个重要问题。本文从数据缺失原因入手，阐述了各种导致数据缺失的原因，然后详细介绍了不完备数据处理的三类基本方法，删除法，填补法，以及不处理的方法，针对每一类方法剖析了各种相应的处理方法。最后以一个不完备数据聚类的实例进行相应的说明。关键字：缺失数据；删除法；填补法；聚类IncompleteDataProcessingandApplicationAbstract:Missingdataprocessingisanimportantproblemofdatapre-processingindataminingfield.Inthispaper,thereasonsofthemissingdataarediscussed,andexplainthevariouscausesofdataloss,thenthreebasicmethodsofincompletedataprocessingareintroducedindetail,deletionmethod,fillingmethod,andnotreatmentmethod.Accordingtoeachkindofmethod,variousprocessingmethodsareanalyzed.Atlast,anexampleofincompletedataclusteringisdescribed.Keywords:Missingdata;deletingmethod;fillingmethod;clustering1.引言随着信息化的普及，互联网的发展以及传感器等各种先进信息采集技术的成熟，收集和存储指数级增长的数据资源成为可能，人类面临越来越多的数据信息[1]。为了提高工作效率或更好的做出决策，人们必须获得蕴含在大量数据中的有价值的数据，为此，数据挖掘技术产生并快速发展。数据挖掘算法越来越受到人们的重视，许多算法和模型都是建立在数据集上的，而现实中的数据集通常存在不完整、数据沉余等情况。这些数据将严重影响数据挖掘的资料，成为数据挖掘的障碍。因此，为了提高数据挖掘的指令，在对数据库中数据进行分析之前，一定要对数据进行预处理。数据清洗是数据预处理的一部分，而对缺失值的处理是数据清洗的重要环节[2]。现实生活中，很多原因造成采集的数据集存在缺失的现象。例如，人口普查的时候由于某种原因造成缺失；在进行实验的过程中由于意外中断造成部分实验数据无法获取；在问卷调查中的收入栏，被调查人为了保护隐私拒绝填写；在后期数据维护中，认为删除不和逻辑的数据等。无论是那种形式的缺失值都会造成数据挖掘结果的偏差。在各个领域中普遍存在缺失值，而在调查和研究中数据存在缺失的情况还在不断呈现上升的趋势。如果对缺失值的处理只是删除带有缺失值的记录，仅对数据集中的完整记录进行数据挖掘，很有可能出现错误的决策。对缺失值的处理主要的方法是基于填充技术的插值法，插补缺失值对数据挖掘有着重要意义。首先，插补缺失值使得数据集中一些重要信息得以保留，避免了删除含有少量带有缺失值的聚类。其次，插补缺失值使数据集变成完整数据集，从在数据挖掘能在完整数据集上进行分析，而不是在数据集的子集上进行分析，避免了分析结果的偏差。因此，在数据挖掘过程中，对缺失值进行插补是非常有必要的，并且插补值的准确性将严重影响数据挖掘的质量，因此对缺失值插补方法的研究也是非常重要的。本文简要的介绍了不完备数据处理产生的原因和基本的插补方法，最后以一个实例进行说明。本文后续部分的组织如下：第二章介绍不完备数据；第三章是缺失数据插补方法的详细介绍；第四部分以一个不完备数据相关的实例进行说明；第五章是结束语。2.不完备数据简介2.1数据缺失原因在各种实用的数据库中，属性值缺失的情况经常发全甚至是不可避免的。因此，在大多数情况下，信息系统是不完备的，或者说存在某种程度的不完备。造成数据缺失的原因是多方面的，主要可能有以下几种[3]：有些信息暂时无法获取。例如在医疗数据库中，并非所有病人的所有临床检验结果都能在给定的时间内得到，就致使一部分属性值空缺出来。又如在申请表数据中，对某些问题的反映依赖于对其他问题的回答。有些信息是被遗漏的。可能是因为输入时认为不重要、忘记填写了或对数据理解错误而遗漏，也可能是由于数据采集设备的故障、存储介质的故障、传输媒体的故障、一些人为因素等原因而丢失了。有些对象的某个或某些属性是不可用的。也就是说，对于这个对象来说，该属性值是不存在的，如一个未婚者的配偶姓名一个儿童的固定收入状况等。有些信息（被认为）是不重要的。如一个属性的取值与给定语境是无关的，或训练数据库的设计者并不在乎某个属性的取值获取这些信息的代价太大，系统实时性能要求较高，即要求得到这些信息前迅速做出判断或决策。2.2数据缺失机制在对缺失数据进行处理前，了解数据缺失的机制和形式是十分必要的。将数据集中不含缺失值的变量（属性）称为完全变量，数据集中含有缺失值的变量称为不完全变量，Little和Rubin[4]定义了以下三种不同的数据缺失机制：完全随机缺失（MissingCompletelyatRandom，MCAR）。如果所缺失的数据发送的概率既与以观察的数据无关也与未观察到的数据无关，则该缺失模式数据类型为MCAR。随机缺失（MissingatRandom，MAR）。如果缺失数据的发生概率与所观察到的变量是有关的，与未观察到的数据特征无关，则该缺失数据类型为MAR。非随机、不可忽略缺失（NotMissingatRandom,NMAR）。如果缺失数据的发生概率与所观察到的变量是有关的，与未观察到的数据特征有关，则该缺失数据类型为NMAR。这种缺失是不可忽略的。如果按照缺失模式可分为单调缺失模式和任意缺失模式两类。当对一个数据集进行适当的调整，得到的缺失数据呈现出层次缺失模式，这种缺失模式称为单调缺失模式。如果数据缺失是随意的，没有任何规律可循，即使通过行列变换后也无法得到任何规律，则这种缺失称为任意缺失模式。3.不完备数据处理方法3.1删除法将存在遗漏信息属性值的对象删除，从而得到一个完备的信息表。这种方法简单易行，在对象有多个属性缺失值、被删除的含缺失值的对象与信息表中的数据量相比非常小的情况下是非常有效的。然而，这种方法却有很大的局限性。它是以减少历史数据来换取信息的完备，会造成资源的大量浪费，丢弃了大量隐藏在这些对象中的信息。在信息表中本来包含的对象很少的情况下，删除少量对象就足以严重影响到信息表信息的客观性和结果的正确性；当每个属性空值的百分比变化很大时，它的性能非常差。因此，当遗漏数据所占比例较大，特别当遗漏数据非随机分布时，这种方法可能导致数据发生偏离，从而引出错误的结论。3.2基于填补方法3.2.1单一填补法只构造一个合理的替代值，并将其插补到原缺失的位置上，替代后构成一个完整数据集。人工填写：由于最了解数据的还是用户自己，因此这个方法产生数据偏离最小，可能是填充效果最好的一种。然而一般来说，该方法很费时，当数据规模很大、空值很多的时候，该方法是不可行的。平均值填充：将信息表中的属性分为数值属性和非数值属性来分别进行处理。如果空值是数值型的，就根据该属性在其他所有对象的取值的平均值来填充该缺失的属性值；如果空值是非数值型的，就根据统计学中的众数原理，用该属性在其他所有对象的取值次数最多的值(即出现频率最高的值)来补齐该缺失的属性值。回归填补法：基于完整的数据集，建立回归方程，将已知属性值带入方程估计未知属性，以此来进行填充，当变量不是线性相关可能会导致有偏差的估计。热平台填充法：在完整数据中找到一个与它最相似的对象，然后用这个相似对象的值来进行填充。不同的问题可能会选用不同的标准来对进行相似进行判定。该方法在概念上很简单，且利用了数据间的关系来进行空值估计。这个方法的缺点在于难以定义相似标准，主观因素较多。冷平台插补法：和热平台插补法类似，插补数据由其他资料提供。期望最大化法[5]：通过计算极大似然估计或者后验分布的迭代算法，每次迭代过程交替执行两步：E步（期望步）：在给定完全数据和前一次迭代所得到的参数估计的情况下计算完全数据对应的对数似然函数的条件期望；M步（极大化步）：用极大化对数似然函数以确定参数的值，并用于下步的迭代。在E步和M步之间不断迭代直至收敛，即两次迭代之间的参数变化小于一个预先给定的阈值时结束。该方法可能会陷入局部极值，收敛速度也不是很快，并且计算很复杂。K近邻法：先根据局部欧式距离来确定缺失数据样本最近的K个样本，然后将这K个样本对应属性的平均值来估计该样本的缺失数据。3.2.2多重填补法多重插补[6]是由Rubin在1987年首先提出的，该方法从单一插补的基础上衍生而来的，对每个缺失值构造m个合理的替代值，从而产生了m个完全数据集，然后对每个完全数据集采用相同的数据分析反复进行处理，得到m个处理结果，然后综合这些处理结果，基于某些原则，得到最终的目标变量的估计。多重填补法是基于EM算法来你对缺失数据进行处理，对EM算法进行了扩充和改进。多重插补分为三个阶段：（1）对目标变量进行估值；（2）创建完全数据集；（3）目标变量的确定。多重插补优点：（1）数据分布，随机抽取进行插补，增加了估计的有效性；（2）多重插补通过模拟缺失数据的分布，较好地保持变量之间的关系；（3）多重插补能给出衡量估计结果不确定性的大量信息。多重填补缺点缺点：（1）多重插补比单一插补需要更多的工作；（2）储存多重插补数据集需要更多的存储空间；（3）分析多重插补数据集比单一插补需要花费更多精力。3.2.3不处理法不处理方法是直接在包含空值的数据上进行数据挖掘。这类方法包括贝叶斯网络、粗糙集模型和人工神经网络等。贝叶斯网络是用来表示变量间连接概率的图形模式，它提供了一种自然的表示因果信息的方法，用来发现数据间的潜在关系。在这个网络中，用节点表示变量，有向边表示变量间的依赖关系。贝叶斯网络仅适合于对领域知识具有一定了解的情况，至少对变量间的依赖关系较清楚的情况。否则直接从数据中学习贝叶斯网的结构不但复杂性较高（随着变量的增加，指数级增加），网络维护代价昂贵，而且它的估计参数较多，为系统带来了高方差，影响了它的预测精度。当在任何一个对象中的缺失值数量很大时，存在指数爆炸的危险。粗糙集模型是将严格的等价关系放宽到要求更为宽松的容差关系、非对称相似关系、限制容差关系，应用最为广泛的是容差关系，它对不完备信息系统中的样本对象间的相似性给出定义。BP神经网络方法把同一系统的除估计参数以外的其他参数的数据作为神经网络的输入，待估计参数的数据作为输出，利用该系统中的已知数据训练网络，在网络满足要求后，把与待估计的数据同一时间的其他参数的数据输入网络，网络的输出即为缺失数据的估计值。4.实例说明4.1基于q近邻的不完备数据三支决策聚类[7]算法思路：利用局部欧式距离找到不完备数据对象的q个近邻，使用q个近邻的平均值填充缺失数据；然后在“完备的”的数据集上使用基于密度峰值的聚类方法[8]得到簇划分，对每个簇中含有不确定数据的数据对象，使用三支决策的思想将其划分到边界域中。算法流程如下：输入：不完备数据集12{,,,}NUxxx，近邻数个为q，阈值为ed，类簇个数为K输出：三支决策聚类结果。Step1:找到每个不完备数据对象的q个近邻Step2:使用近邻中不缺失属性值的平均值填补不完备数据Step3:根据密度峰值方法，得到每个数据的局部密度和距离，并找到K个簇中心Step4:非簇中心的数据对象，按局部密度从高到低依次划分它们到距离最近的类中Step5:将每个簇中局部密度小于簇平均密度并且近邻中包含其他簇对象的数据划分到相应簇的边界，最终得到三只决策聚类结果。4.2实验仿真本次的实验环境为：windows7操作系统、Matlab2011b。采用的是2维人工数据集来展示实验效果，数据集的缺失率为5%，近邻个数选为10，原始数据和填补后的数据如下图所示：利用基于密度峰值的聚类方法，选择阈值为5，得到决策图