数据挖掘噪声数据处理综述

噪声数据处理综述摘要：噪声数据是指数据中存在着错误或异常(偏离期望值)的数据,不完整数据是指感兴趣的属性没有值.不一致数据则是数据内涵出现不一致的情况。为了更好的论述什么是噪声数据处理，给出了两种噪声数据处理的算法：在属性级别上处理噪声数据的数据清洗算法和一种改进的应用于噪声数据中的KNN算法。关键词：噪声数据噪声数据处理数据清洗KNN算法1.概述噪声数据（noisydata）就是无意义的数据（meaninglessdata）。这个词通常作为损坏数据（corruptdata）的同义词使用。但是，现在它的意义已经扩展到包含所有难以被机器正确理解和翻译的数据，如非结构化文本。任何不可被创造它的源程序读取和运用的数据，不管是已经接收的、存储的还是改变的，都被称为噪声。噪声数据未必增加了需要的存储空间容量，相反地，它可能会影响所有数据挖掘（datamining）分析的结果。统计分析可以运用历史数据中收集的信息来清除噪声数据从而促进数据挖掘。引起噪声数据（noisydata）的原因可能是硬件故障、编程错误或者语音或光学字符识别程序（OCR）中的乱码。拼写错误、行业简称和俚语也会阻碍机器读取。噪声数据处理是数据处理的一个重要环节，在对含有噪声数据进行处理的过程中，现有的方法通常是找到这些孤立于其他数据的记录并删除掉，其缺点是事实上通常只有一个属性上的数据需要删除或修正，将整条记录删除将丢失大量有用的、干净的信息。在数据仓库技术中，通常数据处理过程应用在数据仓库之前，其目的是提高数据的质量，使后继的联机处理分析(OLAP)和数据挖掘应用得到尽可能正确的结果。然而，这个过程也可以反过来，即利用数据挖掘的一些技术来进行数据处理，提高数据质量。2.噪声数据处理2.1在属性级别上噪声数据处理的数据清洗算法2.1.1数据清洗和聚类分析介绍数据清洗包括许多的内容，文献【l】给出了详尽的介绍，其中噪声数据(包含错误或存在偏离期望的孤立点值)的处理是其中重要的一部分。数据含噪声(包含错误或存在偏离期望的孤立点值)可能有多种原因：收集数据本身难以得到精确的数据，收集数据的设备可能出现故障，数据输入时可能出现错误，数据传输过程中可能出现错误，存储介质有可能出现损坏等。根据决策系统中“garbagein，garbageout“(如果输入的分析数据是垃圾，那么输入的分析结果也将是垃圾)这条原理，必须处理这些噪声数据。去掉噪声、平滑数据的技术主要有：分箱(binning)，聚类(clustering)，同归(regression)等。聚类(clustering)就是将数据对象分组成为多个类或簇(cluster)，在同一个簇中的对象之间具有较高的相似度，而不同的簇间的对象差别较大。聚类分析可以用来进行孤立点挖掘。孤立点挖掘可以发现噪声数据，因为噪声本身就是孤立点、聚类分析发现孤立点的方法有：基于统计的孤立点检测，基于距离的孤立点检测和基于偏离的孤立点检测。2.1.2算法介绍下面是一个利用聚类算法来发现关系数据库中孤立点数据的例子：输入：数据集S，包括N条记录，属性集D：{年龄、收入}；本文称一条记录为一个数据点(DataPoint)，一条记录上的每个属性上的值为一个数据单元格(DataCel1)。S有N×D个数据单元格，其中某些数据单元格是噪声数据。输出：孤立数据点如图1所示。图1通过聚类发现噪声数据的例子孤立点A是一个孤立点数据，我们认为它是噪声数据，很明显它的噪声属性足收入，剩下的干净信息即年龄属性上的数据仍然可以用于预测或其他应用，同时可以利用年龄属性上的干净数据来矫正A在收入上的值。进一步，数据点B也是一个噪声数据，但是很难判定它在哪个属性上的数据出现错误。本方法试图确定噪声点B的噪声属性(即产生噪声的具体属性)，并对其进行矫正。算法思想：首先通过聚类识别噪声数据，并考察它们在各个属性上的值与其期望之间的距离以判定引起噪声的属性；然后，对于能够判定噪声属性的记录，寻找它所属的分类，并利用它所属分类中噪声属性上的值进行矫正；对于不能判定噪声属性的记录，因为噪声记录去除非噪声属性后的仍然是噪声记录，同样可以通过聚类判定其噪声属性并进行矫正；整个过程记录噪声记录在属性上的分布情况。。几个定义如下：噪声数据矩阵(NoiseMatrix，NM)：通过聚类算法得到的孤立数据点集合矩阵，NM(i,j)的值对应孤立点集合P中第i条记录在属性j上的值，即NM(i,j)=P污染矩阵(CorruptionMatrix，CM)：NM对应的一个0—1布尔矩阵，NM(i,j)为噪声=CM（ij)=1；否则，CM(i,j)=0。基本算法描述：输入：含噪声数据的数据集S，S有N个数据对象，S的属性集合D={D1，D2，⋯，Dk}。输出：噪声数据矫正后的数据集合S，污染矩阵CM方法：(1)P=GetNo1seByClustering(S、D);/*属性集合D上对S进行聚类，得到孤立点数据集台P*/(2)If(P!=Nul1)Then{Fori=Otolength(P){Forj=0tok{NM(i，j)=P(i，j);/*NM(i,j)为P中第i条，记录在属性D1上的值*/If(Distance(NM(i,j)、E(S,D1))阈值A)ThenCM(i，j)=1：/*替NM(i，j)与S中D1上的期望之间的距离大于某个阈值，则判定D1上产生了噪声*/ElseCM(i，j)=0}}}(3)ForEachD1(1=i=k){P’=GetNoiseByClustering(S．D-{D}});/*在D＝D{D}上对S聚类；*/Form=1tolength(P){if(CM(m，i)=1)ThenNM(m，i)用行m所对应的记录rm所在的聚集D1上的(平均)值替换；/*对于能够划定噪声属性的记录，用干净数据中D1上的(期望)值矫正*/Else1f(CM(m，j)=0)(1=j=k)ThenIf行m所对应的记录rm所在新的聚类P中不是孤立点then{NM(m，i)用行m所对应的纪录rm所在的聚集中D1上的(期望)值替换；/*对于不能判定噪声属性,并矫正*/CM(m,i)=l：}}}}(4)Form=1tolength(P){/*矫正原始数据S;*/Forj=0tok{If(CM=1)Then{用NM(m，j)替换S中对应的记录属性D1上的值．}}}(5)返回S和NM：其中，过程GetNoiseByCIustering(S,D)是对数据求S在属性集D上进行聚类返回的噪声数据集合。它可以通过聚类算法如k-means(k-平均值)，k-medoids(k-中心点)实现，这里不作具体介绍。这个算法在判定噪声属性的时候采用与其期望值进行比较的方法。这个算法能在属性的级别上发现噪声数据，并且根据剩余的干净数据来矫正噪声而无需事先了解数据的结构。它还能为噪声的产生过程建模，即得到了噪声在属性上的分布规律统计。它的时间复杂度为O(kf)，其中k为数据集合的属性数，f所选的聚类算法的时间复杂度.2.2改进的用于噪声数据中的KNN算法2.2.1相关知识1.相关处理方法K－近邻算法是一种非常简单直观且有效的分类方法，广泛应用于模式识别的各个领域。顾名思义，该方法就是找出未知样本x的k个近邻，根据k个近邻中多数实例所属类别，把x归为该类。具体地说，假设有L个类c1，c2，⋯，cL，第i个类的训练样本集L为wi，整个训练样本集为U，样本总数Ω，yi(i=1,2,…Ω)表示第i个训练样本。给定未知样本x和距离测试，首先从Q个训练样本中找出X的k个近邻，ki(1=i=L)表示这k个近邻中属于第i类的样本数，那么把X归为类cL，其中I=argmaxk，这就是所谓的K－近邻规则(分类方法)。我们用向量表示样本或者样本的特征向量，分类中采用Euclidean距离。2．KNN算法中的噪声处理。噪声数据是永远存在于机器学习领域的研究之中。现在很多工作成果是关于如何处理噪声数据以及噪声数据对分类学习算法的影响。在前人的工作中，大多没有使用噪声数据模型来有效地增强学习算法的分类效果。然而很少有工作研究如何充分利用噪声模型来建立更优的分类算法。K－近邻算法是基于距离的局部最优的算法。不可否认的是，当数据中存在噪声时，局部最优的基于距离的算法会受到明显的影响。虽然合适的参数k能够减弱突发性的噪声数据对分类效果的影响。但当数据服从稳定的噪声模型时，其很难能够从实质上解决此问题。在前人的工作中，一种普遍被接受的观点是，如果训练数据集与测试数据集中存在相同的噪声模型，则噪声数据将会在训练数据和测试数据中起到相同的作用，因而可以忽略输入数据中的不确定性。然而，文献明确指出考虑输入数据的不确定性，可以提高分类器的预测准确性。如果对于类标签来说，所有条件属性是同等重要的，那么将条件属性值规范化于[0，1]区间后，欧基里德距离在计算对象之间的距离时是相当成功的。然而这种假设也不尽然，数据集中的条件属性与类标签之问不一定都是相关，且即使是与类标签之问是相关的，相关程度也不尽相同。朴素的K－近邻算法中，每一个数据所起到的作用是等价的明显存在漏洞。因而很多专家提出了用权重的方法来强调相关性强的属性或减弱不相关的属性在计算距离时的作用。权重的获得有很多种方法，如信息熵、互信息或各属性在相同类标签或不同类标签的实例之间所起的作用来决定等等。2.2.2改进算法1．K－近邻算法。尽管有很多种计算实例之间距离的方法，但大多算法仍旧使用欧基里德距离引。一个实例(a1(1)，a2(1)，⋯，ak(1))和另一个实例((a1(2)，a2(2)，⋯，ak(2))之间距离为：(1)其中，k为条件属性个数。2．噪声模型。真实数据中的噪声数据永远都是存在的。但噪声数据产生的原因有很多种，如手工的误操作、机器本身存在的误差、传输过程中发生的错误等等。(1)系统误差。实验系统的组成包括：实验仪器、环境、实验的理论和方法以及实验人员。由这四种组成所引起的有规律的误差称之为系统误差。①仪器误差：又以其本身的固有缺陷、较正不完善或使用不当引起的。②环境误差：仪器所处的外界环境如：温度、湿度、电磁场等环境的变化引发的误差。③方法误差：由于计算公式的近似，没有完全满足理论公式所给定的条件。例如，单摆测重力加速度的实验中，采用了sin0~0的近似条。④人员误差：由测量者的个人因素造成的误差。例如：按秒表时总是超前或滞后，读数时头总是向一边偏等。(2)随机误差。由某些偶然的、不确定的因素所造成的误差称之为随机误差。若从一次测量来看，随机误差是随机的，没有确定的规律，也不能预测。但当测量次数足够多时，随机误差遵从一定的统计分布。因此，增加测量的次数，可以明显地减少随机误差。其中一部分误差是随机的，没有规律可循，如手工误操作、传输错误等；而另外一类，是有一定规律可循的，也就是说这类噪声往往有一点的范围，服从一定的分布，如机器本身存在的误差，一般在出厂时都有一定的说明，明确指出其精确度。这些有效信息对数据本身的可靠性是最有力的证明。正态分布在概率论与数理统计的理论研究和实际应用中都占有十分重要的地位。在自然界和社会现象中，大量的随机变量都服从或近似地服从正态分布。诸如各种测量误差、计算误差、产品的各类质量指标等。因此，对于连续属性值，本文讨论假设误差服从正态分布情况下的处理方法。对于属性集中的某一个属性a1，假设其噪声服从N(μ，σ2)，μ为噪声的均值，σ为噪声的方差，即表示噪声的分散程度。为了计算两个实例之间的距离，必需先计算公式(1)中各属性之间的距离。以第一个属性为例，讨论正态分布中的两个参数μ和σ对计算距离的影响。现计算实例e1和e2的属性a1之间的距离。定理l对于某一属性，其误差服从正态分布，则其误差均值不会对两个实例的该属性之间的距离产生影响，此距离只受方差的影响。但在数据集中，由于不同的属性的度量单位不同，不同属性的取值范围也就不同。如对于属性a1，的取值va2范围为[10，80]，其方差σ为3；而属性a2的取值va2范围为[1，8]，其方差σ也为3，很明显同样的方差3