数据挖掘原理与SPSS Clementine应用宝典 元昌安 主编　 邓　松　李文敬　刘海涛　编著 电子工业出版社

本章包括： 数据预处理基本功能 数据预处理的方法 第5章 数据预处理 本章包括： 数据预处理基本功能 数据预处理的方法

数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但有潜在的有用信息和知识的过程。 数据挖掘：为企业决策者提供重要的、有价值的信息或知识，从而为企业带来不可估量的经济效益。

数据挖掘过程一般包括数据采集、数据预处理、数据挖掘以及知识评价和呈现。 在一个完整的数据挖掘过程中，数据预处理要花费60% 左右的时间，而后的挖掘工作仅占总工作量的10% 左右。 目前对数据挖掘的研究主要集中于挖掘技术、挖掘算法、挖掘语言等。

数据挖掘的必要性： 在海量的原始数据中，存在着大量杂乱的、重复的、不完整的数据，严重影响到数据挖掘算法的执行效率，甚至可能导致挖掘结果的偏差。

数据预处理分类： 从对不同的源数据进行预处理的功能来分，数据预处理主要包括数据清理、数据集成、数据变换、数据归约等4个基本功能。 在实际的数据预处理过程中， 这4种功能不一定都用到，而且，它们的使用也没有先后顺序， 某一种预处理可能先后要多次进行。

从数据预处理所采用的技术和方法来分： 基本粗集理论的简约方法； 复共线性数据预处理方法； 基于Hash函数取样的数据预处理方法； 基于遗传算法数据预处理方法； 基于神经网络的数据预处理方法； Web挖掘的数据预处理方法等等。

5.1数据预处理基本功能 在数据挖掘整体过程中,海量的原始数据中存在着大量杂乱的、重复的、不完整的数据，严重影响到数据挖掘算法的执行效率，甚至可能导致挖掘结果的偏差。为此，在数据挖掘算法执行之前，必须对收集到的原始数据进行预处理，以改进数据的质量，提高数据挖掘过程的效率、精度和性能。数据预处理主要包括数据清理、数据集成、数据变换与数据归约等技术。

5.1.1　数据清理 数据清理要去除源数据集中的噪声数据和无关数据，处理遗漏数据和清洗脏数据、空缺值， 识别删除孤立点等。

5.1.1.1噪声数据处理 噪声是一个测量变量中的随机错误或偏差，包括错误的值或偏离期望的孤立点值。对于噪声数据有如下几种处理方法： 分箱法 聚类法识别孤立点 回归

5.1.1.2空缺值的处理 目前最常用的方法是使用最可能的值填充空缺值， 如用一个全局常量替换空缺值、使用属性的平均值填充空缺值或将所有元组按某些属性分类， 然后用同一类中属性的平均值填充空缺值。 例5.2：一个公司职员平均工资收入为3000元，则使用该值替换工资中“基本工资”属性中的空缺值。

5.1.1.3清洗脏数据 异构数据源数据库中的数据并不都是正确的，常常不可避免地存在着不完整、不一致、不精确和重复的数据，这些数据统称为“脏数据”。脏数据能使挖掘过程陷入混乱，导致不可靠的输出。

清洗脏数据可采用下面的方式： 手工实现方式 用专门编写的应用程序 采用概率统计学原理查找数值异常的记录 对重复记录的检测与删除

5.1.2.1 实体识别问题 在数据集成时，来自多个数据源的现实世界的实体有时并不一定是匹配的，例如：数据分析者如何才能确信一个数据库中的student_id和另一个数据库中的stu_id 值是同一个实体。通常，可根据数据库或数据仓库的元数据来区分模式集成中的错误。

5.1.2.2冗余问题 数据集成往往导致数据冗余，如同一属性多次出现、同一属性命名不一致等，对于属性间冗余可以用相关分析检测到，然后删除。

5.1.2.3 数据值冲突检测与处理 对于现实世界的同一实体，来自不同数据源的属性值可能不同。这可能是因为表示、比例或编码、数据类型、单位不统一、字段长度不同。

5.1.3　数据变换 数据变换主要是找到数据的特征表示，用维变换或转换方法减少有效变量的数目或找到数据的不变式，包括规格化、归约、切换、旋转和投影等操作。 规格化是指将元组集按规格化条件进行合并，也就是属性值量纲的归一化处理。

规格化条件定义了属性的多个取值到给定虚拟值的对应关系。对于不同的数值属性特点，一般可以分为取值连续和取值分散的数值属性规格化问题。

归约指将元组按语义层次结构合并。语义层次结构定义了元组属性值之间的语义关系。规格化和归约能大量减少元组个数，提高计算效率。同时，规格化和归约过程提高了知识发现的起点，使得一个算法能够发现多层次的知识，适应不同应用的需要。

5.1.4　数据归约 数据归约是将数据库中的海量数据进行归约，归约之后的数据仍接近于保持原数据的完整性，但数据量相对小得多，这样进行数据挖掘的性能和效率会得到很大提高。 数据归约的策略主要有数据立方体聚集、维归约、数据压缩、数值压缩、离散化和概念分层。

5.1.4.1 维归约　 通过删除不相关的属性(或维) 减少数据量，不仅压缩了数据集，还减少了出现在发现模式上的属性数目，通常采用属性子集选择方法找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性的原分布。

5.1.4.2数据压缩 数据压缩分为无损压缩和有损压缩，比较流行和有效的有损数据压缩方法是小波变换和主要成分分析。 小波变换对于稀疏或倾斜数据以及具有有序属性的数据有很好的压缩结果。

5.1.4.3数值归约 数值归约通过选择替代的、较小的数据表示形式来减少数据量。 5.1.4.3数值归约　 数值归约通过选择替代的、较小的数据表示形式来减少数据量。 数值归约技术可以是有参的，也可以是无参的。有参方法是使用一个模型来评估数据，只需存放参数，而不需要存放实际数据。 有参的数值归约技术有以下两种，回归：线性回归和多元回归；对数线性模型：近似离散属性集中的多维概率分布。

无参的数值归约技术有3种： 直方图 聚类 选样

5.1.4.4 概念分层 概念分层通过收集并用较高层的概念替换较低层的概念来定义数值属性的一个离散化。 5.1.4.4 概念分层　 概念分层通过收集并用较高层的概念替换较低层的概念来定义数值属性的一个离散化。 概念分层可以用来归约数据，通过这种概化尽管细节丢失了，但概化后的数据更有意义、更容易理解，并且所需的空间比原数据少。 对于数值属性，由于数据的可能取值范围的多样性和数据值的更新频繁，说明概念分层是困难的。

数值属性的概念分层可以根据数据的分布分析自动地构造，如用分箱、直方图分析、聚类分析、基于熵的离散化和自然划分分段等技术生成数值概念分层。 由用户专家在模式级显示地说明属性的部分序或全序，从而获得概念的分层； 只说明属性集，但不说明它们的偏序，由系统根据每个属性不同值的个数产生属性序，自动构造有意义的概念分层。

5.2数据预处理的方法 数据预处理方法就是根据不同的挖掘问题采用相应的理论和技术，实现数据清理、数据集成、数据变换、数据归约等基本功能。 预处理方法很多，在此介绍常用的几种方法。

5.2.1基于粗集理论的简约方法 　　粗糙集理论是一种研究不精确、不确定性知识的数学工具，可以对数据属性进行十分有效的精简，求出最小约简集，是数据预处理一种有效的方法。

数据一般存在信息的含糊性问题。 粗糙集理论的最大特点是无需提供问题所需处理的数据集合之外的任何先验信息。

粗糙集理论的基本思路是利用定义在数据集合U上的等价关系对U进行划分，对于数据表来说，这种等价关系可以是某个属性，或者是几个属性的集合。因此按照不同属性的组合就把数据表划分成不同的基本类，在这些基本类的基础上进一步求得最小约简集。

例如：表5.1　优秀人才决策表给出了某部门的员工数据记录集，通过对员工的政治表现、工作能力、科研能力等确定优秀人才人选。 论域 U 条件属性（C） 决策属性 政治表现（C1） 工作能力（C2） 科研能力（C3） 优秀人才（D） e1 优秀 强 是 e2 良好 一般 否 e3 差 e4 e5 e6 其中：条件属性集为C＝{政治表现，工作能力，科研能力}，决策属性集为D＝{优秀人才}。

根据粗糙集理论对表5.1进行离散化后再进行数据预处理。 处理过程分两个步骤进行，一是对决策表条件属性集进行约简求核；二是对条件属性值进行约简。具体求解步骤可见第11章相关内容。

基于粗糙集理论的数据预处理具有优点： 第一，数据挖掘的对象一般都是通过观测、试验、调查得到的数据，通过观测、试验、调查等得到的数据存在着冗余、杂乱、不完整等因素，采用粗糙集理论进行数据预处理，不需要预先知道额外的信息，有利于集中精力解决问题；

第二，算法简单。对于给定的决策表，预处理过程所使用的算法可以是分辨矩阵或逐个属性、逐条规则进行检验，算法简单，易于计算机的实现，方便挖掘系统的自动操作； 第三，可以有效地去除冗余的属性或属性的值。

5.2.2复共线性数据的预处理方法 常规方法进行函数发现时一般要作出一个假设：数据满足统计不相关。而传统的函数发现算法中，常常忽略对数据是否满足该假设的检验。若数据不满足统计不相关的假设（也称数据变量之间存在复共线性），在这种情况下，函数发现算法挖掘出来的函数关系表达式可能会存在系统误差，该表达式将不是我们要发现的理想函数。

为解决该问题，本节给出ε－复共线性的概念，然后给出不满足不相关假设的情况下进行数据预处理的算法ε－MDPA（ε－Multicollinearity Data Preprocessing Algorithm复共线性数据预处理算法）。

5.2.2.1.相关概念 假定给定的样本数据为Y、X，其中因变量样本数据矩阵Y=(y1,y2,…,yn)是p×n样本矩阵，即p个因变量，n个样本；自变量样本数据矩阵X是q×n矩阵，即q个自变量，n个样本。在实际计算时，X一般是将原始数据中心化后得到的样本矩阵，即：X×1n＝0。

在一般的函数发现算法中，自变量样本数据矩阵X需要数据满足统计不相关假设，也即X各行之间不能存在线性关系。而实际上，只要矩阵X的行向量之间存在近似线性关系时，函数发现算法就有可能达不到实用的效果。为此，下面我们给出ε－复共线性的定义，并对满足这一定义的数据给出数据预处理的算法(ε－MDPA)。

定义5.1（ε－复共线性）给定矩阵X，设X′为X的转置矩阵，设矩阵（XX′）n×n的特征根为λ1, λ2, …,λn, 若对预设的正数ε，0＜ε＜0.1，有max(λi,i=1,…,n)/ min(λi,i=1,…,n)>1/ε，则称矩阵X满足ε－复共线性。

ε－复共线性描述了最大特征根和最小特征根之间的差距，当ε足够小时，XX′至少有一个特征根接近于0，这时，X的行向量之间存在着近似的线性关系，从而描述了数据之间的相关程度。

5.2.2.2.ε－复共线性数据预处理算法 本小节主要讨论存在着ε－复共线性的数据矩阵X数据预处理的方法。

算法思路：为消除数据的复共线性使数据满足统计不相关假设，需对矩阵X作主成分分析，计算出主向量矩阵Z，矩阵Z的各行向量之间是满足统计不相关假设的。于是，在后继的函数发现算法中，将挖掘Y与Z的关系，然后再利用X与Z的关系，得到Y与X之间的关系表达式。

下面的ε－复共线性数据预处理算法描述了存在ε－复共线性数据的转换方法。

算法5-1　ε－MDPA(ε－Multicollinearity Data Preprocessing Algorithm) 输入：q×n矩阵 X，控制值ε 输出：Z (转换后消除复共线性的数据矩阵) 步骤： Begin Step1计算XX′的特征值λ1,λ2, …, λq，并按从大到小顺序排序； Step2 判断数据矩阵X具有ε－复共线性。 End. 　　算法的伪代码如下： EC（X） //计算XX′的特征值λ1,λ2, …, λq，并按从大到小顺序排序； IF　λ1/λq>1/ε //数据矩阵X具有ε－复共线性 PCMC(Xq×n，λ1, λ2, …,λq，t ) //主分量矩阵计算 ELSE Z=X； ENDIF

算法3-1的计算代价主要在第1行计算特征值过程和第3行主分量矩阵计算过程，分别由下面的算法5-2和算法5-3实现。

算法5-2　EC(Eigenvalue Compute特征值计算子程序) 输入：q×n矩阵 X 输出：特征值λ1，λ2，…，λq，并按从大到小顺序排序和特征向量矩阵Eigenvalue(q,q) 步骤： Begin Step1　计算相关系数矩阵CorMatrix（q,q）； Step2 利用雅可比法计算矩阵CorMatrix（q,q）的特征值； Step3 判断上三角元素是否全部满足设定值； Step4 将特征值、特征向量按照特征值的大小进行排序得到特征值向量lpt[q]和特征向量矩阵EigenVector[q,q]。 End.

算法的伪代码如下： Begin 计算相关系数矩阵CorMatrix（q,q）； 利用雅可比法计算矩阵CorMatrix（q,q）的特征值； Eigenvalue[i,j]=CorMatrix[i,j], (i,j=1,2,…,q)； l=0; //定义计数变量 while(l<(q*(q-1))/2) //判断上三角元素是否全部满足设定值,满足跳出循环，否则继续循环 { l=0; 求在Eigenvalue[q,q]矩阵上三角元素中的最大值及其位置pos1,pos2 根据pos1,pos2进行一轮特征值、特征向量的计算 if((abs(Eigenvalue [i,j])<),(i=0,1,…,q,j=i+1,…,q) //判断上三角元素是否满足条件 l++; //满足计数器l加1 } Lpt[i]= Eigenvalue[i,i]; (i=1,2,…,q);//将特征值放入一维数组中 将特征值、特征向量按照特征值的大小进行排序得到特征值向量lpt[q]和特征向量矩阵EigenVector[q,q] End.

说明： 算法中把特征值存放在Lpt数组，特征向量存放在Eigenvalue数组中。 一般q<<n，所以算法的主要计算代价在第一步计算相关系数矩阵中，计算量为q*n=O(n) 下面的算法描述了主分量矩阵的计算过程。

算法5-3　PCMC(Principle Component Matrix Compute主分量矩阵计算子程序) 输入：矩阵Xq×n，λ1, λ2, …,λq，特征向量矩阵EigenVector[q,q]，t (t<=1为确定主分量个数时所需特征值之和对总和贡献率的临界值) 输出：所需主分量矩阵Zk×n 步骤： Begin Step1计算所需主分量个数k； Step2根据特征向量矩阵Eigenvalue(q,q)计算出所需特征向量矩阵Pk×q； Step3计算主分量矩阵Zk×n(=P×X)。 End.

算法的伪代码如下： Begin 计算所需主分量个数k(<=q) 即满足（λ1＋λ2＋…＋λk）/（λ1＋λ2＋…＋λq）>=t 根据特征向量矩阵Eigenvalue(q,q)计算出所需特征向量矩阵Pk×q 计算主分量矩阵Zk×n(=P×X) End. 显然，算法3-3的计算代价主要在第2行，第3行，它们的计算复杂度在下面的命题中将进行分析。 下面的命题描述了算法ε－MDPA的复杂度。

因此，ε－MDPA的总计算量为O(n)。 证明： 注意，算法中的p,q的值一般较小，相对于n的值可计为O(1)，算法计算代价主要有： （1）计算特征值：计算量为O(n) （2）计算主分量个数：计算量为O(1) （3）计算特征向量矩阵：计算量为O(1) （4）计算主分量矩阵：计算量为O(1) 因此，ε－MDPA的总计算量为O(n)。

在目前常规的数据挖掘系统中，其数据分析功能模块中，一般有主成分分析模块，因此，ε－复共线性数据预处理算法在海量数据计算中，可使用这些模块计算的中间结果，或者使用抽样方法估算主成分分析模块的一些参数，以减少运算量。 因此，ε－MDPA在没有明显增加计算量的情况下，将一些函数发现算法的应用推广到数据不满足统计不相关假设的情况，大大地拓宽了统计学及数据挖掘中的一些方法应用

表5.2 某地区森林植被与引起洪涝灾害的降雨量的关系 5.2.2.3.实验 本实验的目的在于让读者理解ε－MDPA算法的运算过程，所以，实验数据样本数较小。实验针对以下数据进行，见表5.2。 表5.2　某地区森林植被与引起洪涝灾害的降雨量的关系 序号 变量 1 2 3 4 5 6 7 8 9 10 X1 82.9 88.0 99.9 105.3 117.7 131.0 168.2 161.8 174.2 184.7 X2 92.0 93.0 96.0 94.0 110.0 101.0 105.0 112.0 X3 17.1 21.3 25.1 29.0 34.0 40.0 44.0 49.0 51.0 53.0 X4 97.0 100.0 104.0 109.0 111.0 y 8.4 9.6 10.4 11.4 12.2 14.2 15.8 17.9 19.6 20.8

该例中：p=1，q=4，n=10 运行ε－MDPA应用程序，并选择ε＝0.001,t=0.90 计算得：   CorMatrix（q,q）= λ1＝3.827, λ2=0.138, λ3=0.032, λ4=0.003 λ1/λ4=1276>1/ε=1000,

数据矩阵X存在复共线性，执行PCMC子程序，计算主分量矩阵。 由λ1/∑λi＝0.957>t，k=1,即主分量只需取一个，即λ1＝3.827对应的评分量。 计算得P1＊4=(0.259,0.257,0.258,0.258) 计算消除复共线性后的数据矩阵Z： Z1＊10＝P×X＝(73.8,76.9,82.0,83.9,93.3,96.3,103.6,111.5,115.7,118.9) 然后，就可以使用新的数据矩阵挖掘其与因变量Y之间的函数关系，最终将结果再代回到自变量X即可。

5.2.3基于Hash函数取样的抽样技术数据预处理 在函数发现算法处理海量数据时，由于实时的需要（例如针对数据流的处理），常需要先进行抽样。要使抽样取得好的效果，最重要的是要使样本的代表性能真正反映总体的统计特性。传统的抽样方法一般采取简单随机抽样，但这种方法反映的是数据编号的统计特性，没有真正反映出其数据分布的统计特性；特别是当数据倾斜时，样本不具有对总体数据统计分布的代表性。

传统的分层抽样需要有关层次概念的知识，然后根据层的知识来进行分层，因而传统方法在没有层知识的情况下就显得无能为力。

新的基于Hash函数取样技术SHF (Sampling Based on Hash Function )模型，新方法注意到传统分层抽样需要预先知道关于层的知识，因此引入Hash函数技术，在对总体数据没有层知识的情形下，利用Hash桶进行分层，即将m维超立方体按等概率空间进行分桶，使得每层（Hash桶）的数据个数相近，以较小的计算代价获得分层的效果，然后进行分层抽样，使所抽样本能充分反映数据的统计特性。

算法保证了样本具有对总体数据的充分的统计代表性并从理论上可证明新算法复杂度为O（n）。

5.2.3.1 SHF模型中的概念 总体的分布函数构造Hash函数，由于以下原因： 完全地计算总体数据去得到精确分布的计算量太大； 即使处理完整个总体的数据，由于数据噪声，得到总体的分布也只是近似的。 所以，SHF利用随机抽样的一些性质，使用总体的估计 分布函数来代替其精确分布。

l 连续型，如重量和高度等。其距离计算方法一般用欧氏距离或曼哈坦距离。 设总体数据为：X＝（Xij）n×m，即共有m个变量，n行数据。为了简化问题且不失一般性，本节作下列两项假定： (1) 假定m个变量中有下列几种类型： l 连续型，如重量和高度等。其距离计算方法一般用欧氏距离或曼哈坦距离。 l 二元型，即变量取值只有2个状态，如性别。 l 标称型，二元型的推广，其状态多于2个，如颜色。 其它类型均可以看作上述三种类型的特例。

(2) 假定m个变量中，x1，…，xm1为连续型变量，xm1+1，…，x m1+m2为二元变量， x m1+m2+1，…，x m1+m2+m3为标称变量。 m1+m2+m3＝m，即m1个连续变量，m2个二元变量，m3个标称变量。 关于二元变量，两个对象i，j之间的距离常用它们的匹配系数来表示：d(i,j)=f/m2，其中f为m2个二元变量中，两个对象取不同状态的个数。 关于标称变量，两个对象i，j之间的距离也常用它们的匹配系数来表示：d(i,j)=m3－g/m3，其中g为m3个标称变量中，两个对象取相同状态的个数。

5.2.3.2 各类型变量分布函数的估计 对于分布函数的估计采用简单随机取样，设简单随机样本数据为ssimp。为了针对各类型变量给出各分布函数的估计，根据文献[13]，有下列三条性质： 性质5.1（无偏估计性） （1）样本均值xmean是总体均值Xmean的无偏估计量。 （2）xtotal＝nxmean是总体总值Xtotal的无偏估计量。 （3）样本方差 ＝ (xi-xmean)2/(ssimp-1)是 总体方差：S ＝ (Xi-Xmean)2/(n-1)的无偏估计量。

性质5.2（关于各类型变量的近似分布性） (1) 对于连续随机变量x，其估计分布函数为近似正态分布N(xmena,sx2)。分布函数为： F（x）＝

(2) 对于二元变量x，设其状态为0,1。所抽ssimp个样本中，0状态的个数为ssimp0，1状态的个数为ssimp1。令p= ssimp0/ssimp,则其估计分布函数为： F（x）=

(3) 对于标称变量x，设状态为sta1,sta2,…,stat，分别被标记为1,2，…,t。所抽样本中各状态出现的个数分别为ksta1,ksta2,…kstat，令pi=kstai /ssimp(i=1,2,…,t)。则其估计分布函数为： F(x)＝

性质5.3　(抽样数的确定)　估计分布函数的简单随机抽样样本个数ssimp由以下方法确定： 其中 为标准正态分布的双侧 分位数，r为相对误差。

5.2.3.3 Hash函数的构造 SHF模型按如下步骤构造Hash函数： 对总体进行简单随机抽样，抽样针对每维变量进行。 H(x1,x2,…,xm)＝F(x1)F(x2)…F(xm)　　　　 （5.4）

以上方法实际上假定了各变量之间相互独立。对于总体数据，若各变量之间存在复共线性情形，可采取因子分析法先将数据进行转化，消除其复共线性。其计算量为O（n）。 命题5.2　 x1,x2,…,xm 相互独立时，H(x1,x2,…,xm)为变量X=(x1,x2,…,xm)的联合分布函数。 证明：由独立随机变量的联合分布函数的性质即知。

5.2.3.4 分层取样 SHF模型利用Hash函数对总体数据进行分桶，亦即将数据进行分层，然后针对各桶进行简单随机抽样，从而实现分层抽样。 设按函数发现技术要求所需抽取的样本数为slayer，将[0,1]slayer等分，slayer个等分点如下： 0=i0, i1, i2, …, islayer-1, islayer=1，则iq-iq-1=1/slayer(q=1, 2, …, slayer) 将n个数据分到slayer个桶，分法如下： 若第j行数据满足： iq-1<=H(xj1, xj2, …, xjm)<iq(q=1,2,…slayer-1) iq-1<=H(xj1,xj2,…,xjm)<=iq(q=slayer) 　（5.5） 则第j 行属于第q个桶。

命题5.3 （各桶中数据分布的特点）按上述分桶方法，各桶中数据的个数以概率1相同。 证明：由命题5.2知， H(x1, x2, …, xm)为变量X=(x1,x2,…,xm)的联合分布函数，将n个点看作是分布在维数为m的超几何体中。由于桶的划分是按分布函数等概率来划分的（注意，不是按超几何体等体积划分），即超几何体被划分为slayer个等概率空间，即slayer个等概率Hash桶，由概率函数的频率意义知，各桶落入点的频率应该均为，因此，各桶中数据的个数以概率1相同。

命题5.3保证了后面的基于Hash函数取样技术在分层时，各层中数据个数接近，为保证抽样质量提供了理论依据。 性质5.4　分层抽样的精度优于简单随机抽样，即分层抽样的估计量方差小于简单随机抽样。

5.2.3.5 基于Hash函数取样的数据预处理算法 SHF模型中的HSDPA(Hash Sampling Based Data Preprocessing Algorithm)算法首先进行简单随机抽样，估计分布函数，构造出Hash函数，然后进行基于Hash函数的分层抽样，得到具有充分统计代表性的样本。下面的算法5-4给出了计算过程的细节：

算法5-4 HSDPA算法 输入：n行m列混合类型数据，样本个体数为slayer 输出：slayer行m列混合类型数据 步骤： Begin Step1 针对各列进行简单随机抽样； Step2 根据（5.1）（5.2）（5.3）式估计各列分布函数； Step3 根据（5.4）式构造Hash函数H； Step4 根据（5.5）式将n个个体分成slayer个桶； Stpe5 随机地从各桶抽取一个个体，组成一个样本数为slayer的样本； Step6 End.

命题5.4 HSDPA算法的复杂度为O（n），即为关于n的线性时间。 证明：显然，HSDPA算法中m, k, ssimp, slayer<<n 第1步代价为O(1) 第2步代价为O(1) 第3步代价为O(1) 第4步代价为n 第5代价为O(1) 所以整个算法的代价为：O(n) 即整个算法的复杂度是关于n的线性时间。 HSDPA算法已被成功应用于聚类分析方法中，参见文献[15]。该文实验表明，HSPDA算法在聚类质量下降很小的情况下，在数据集个数接近10000时，聚类效率比传统算法提高2个数量级。

5.2.3基于遗传算法的预处理方法 遗传算法是从某一随机产生的或是特定的初始群体出发(父本)，进行选择、复制、交叉、变异等，不断地进行迭代计算，并根据每一个个体的适应度值，优胜劣汰，引导搜索过程向解逼近。 遗传算法的优点：它直接对结构对象进行操作，无需函数可导或连续，具有内在的隐并行性和较好的全局寻优能力，它以一定的概率进行交叉和变异，采用了概率化的寻优方法，能自动获取搜索过程中的有关知识并用于指导优化，自适应地调整搜索方向，不需要确定的规则。

遗传算法的高效搜索能力可以用来进行数据的聚类预处理，即把一条具有n个属性的记录看作是n维空间中的一个点，数据库中的数据记录就成为n维空间中的一组点群，这样对样本的聚类问题就转化为对点群的划分或归类问题。

在用遗传算法求解之前，有必要先对问题的解空间进行编码。以交易数据库为例，经过预处理的目标子集，由0，1形成了相应的属性值，所以可采用通常的二进制编码方法，编码长度取决于向量的维数，这是一个长度固定的染色体编码。遗传算法中，自然选择过程的模拟通常是采用评估函数和适应度函数来实现的。

评估函数主要通过染色体优劣的绝对值来评估，而适应度则用来评估一个染色体相对于整个群体优劣的相对值的大小。

通常的遗传算子主要有选择、交叉和变异。 其中，选择算子指按照一定的策略从父代中选出个体进入中间群体；交叉算子指随机地从群体中抽取两个个体，并按照某种交叉策略使两个个体互相交换部分染色体码串，形成两个新的个体，可采用两点交叉或多点交叉策略；变异算子指按一定的概率，改变染色体中的某些位的值。

标准遗传算法的形式化描述为 ，SGA是一个八元组SGA =(C, E, P0,M,Φ,Γ,Ψ, T) ，其中，C为个体的编码方法，E为个体适应度评价函数，P0为初始群体，M 为群体规模，Φ 为选择算子，Γ为交叉算子，Ψ 为变异算子，T为遗传算法的终止条件。遗传算法一般分为两个阶段，首先从初始群体开始，通过选择生成中间群体，然后在中间群体上进行交叉与变异，以形成下一代的群体。

算法5-5 基于遗传算法的特征子集选取算法 输入：置迭代次数为0,随机生成初始群体； 输出：优化的特征子集，优化的子群体。 步骤： 算法5-5　基于遗传算法的特征子集选取算法 输入：置迭代次数为0,随机生成初始群体； 输出：优化的特征子集，优化的子群体。 步骤： Begin Step1 置迭代次数为0,随机生成初始群体； Step2 IF T终止条件满足 Then End； Step3 计算当前群体中各个体的适应度； Step4 由各个体适应度选择生成中间群体； Step5 以概率Pc选择个体进行交叉，产生的新个体替换老个体，加入到中间群体中； Step6 以概率Pm 选择个体对其某一位进行变异，产生新个体替换老个体，并加入到中间群体中； Step7 转Step2。 End.

5.2.4基于神经网络数据预处理方法 人工神经网络（artificialneuralnetwork，简称ANN）是在对大脑的生理研究的基础上，用模拟生物神经元的某些基本功能元件（即人工神经元），按各种不同的联结方式组成的一个网络。神经网络(Neural Network)的学习结果为目标函数，根据这个目标函数的输出作为分类的依据。输入即为文本在各个特征上的各分量值。

神经网络实际上是一组连接的输入/输出单元，其中每一个连接都具有一定的权值。通过训练集来训练的过程就是调整这些权值的过程，使得神经网络可以正确的预测类别。神经网络的训练是针对训练例逐个进行的，所以神经网络的训练集可以随时添加，不需要重新进行训练就可完成网络的调整。

同时有实验结果表明，在训练例过少的情况下，神经网络的分类准确率较低。因为可通过训练来针对特征取一定的合适的权值，神经网络可以较好地抵御噪音的干扰。 因此有必要建立“白化”机制，用规则解释网络的权值矩阵，为决策支持和数据挖掘提供说明。

通常有两种解决方法： 方法一，建立一个基于规则的系统辅助。神经网络运行的同时，将其输入和输出模式给基于规则的系统，然后用反向关联完成网络的推理过程，这种方法把网络的运行过程和解释过程用两套系统实现，开销大，不够灵活； 方法二，直接从训练好的网络中提取(分类)规则。这是当前数据挖掘使用得比较多的方法。

网络中的采掘规则，主要有两种： 网络结构分解的规则提取和由神经网络的非线性映射关系提取规则。其中，网络结构分解的规则提取以神经网络的隐层结点和输出层结点为研究对象，把整个网络分解为许多单层子网的组合。研究较简单的子网，便于从中挖掘知识。

对于大规模网络，在提取规则前，需要对网络结构进行剪枝和删除冗余结点等预处理工作。而由神经网络的非线性映射关系提取规则直接从网络输入和输出层数据入手，不考虑网络的隐层结构，避免基于结构分解的规则提取算法的不足。

组织特征映射神经网络(SOFM) 　　自组织特征映射神经网络(SOFM) 是一种典型的自适应聚类分析技术。SOFM是一个动态系统，它利用低维空间的表示学习拓扑结构并提取高维输入向量中的结构。这种表示代替了输入向量的全局的概率密度。 　　设有n 个样本，SOFM网络训练算法如下：

算法5-6　SOFM算法 输入：初始化输入结点到输出结点的连接权值,并置时间t = 0 , i = 0；输入模式向量。 输出：输出结点 所连接的权向量及 几何邻域 内结点所连接的权值 : 　　

步骤： Begin Step1 初始化输入结点到输出结点的连接权值,并置时间t = 0 , i = 0。 Step2 输入模式向量 ； Step3计算输入与全部输出结点所连接权向量 的距离: Step4具有最小距离的结点为竞争获胜结点 Step5 调整输出结点 所连接的权向量及 几何邻域 内结点所连接的权值: Step 6 i = i + 1 ， t = t + 1 ,IF　i ≤n Then Step2　 End

算法中， 表示学习速度是可变的，随时间而衰减，即随着训练次数的增加，权值调整 幅度逐渐减小，以使获胜结点所连接的权向量能代表模式的本质属性。 借助SOFM网络，可将归纳数据库中的样本数据(一般仍为高维数据) 按数据分布聚类到低维空间，这也体现了一种数据降维操作，可以形成相应的目标数据子集。

5.2.5Web挖掘数据预处理方法 Web使用挖掘由3个阶段构成: 数据预处理 模式发现 模式分析

算法5-7　WLP会话识别算法 输入：给出θ的会话溢出时间和会话总数； 输出：会话集si。 步骤： 　　Begin (1)θ表示会话的溢出时间。

(2) for i = 1 to n do A、 ； // 确定使用者活动列表Li的会话总数； B、 ； C、 for m = 1 to do // m表示第m个会话； i. ； //找出最接近阈值的请求时间函数； ii.将tm加入到ti； iii.tstart =tm； D、 依据 将 Li转存为会话列表si ； End

函数 中的 代表已知列表的起始点， 为已知列表的终点， 表示要查找的记录参考时间，即等于它或小于它的最近的记录。其结果是返回一条记录的位置，标示出会话的终点，或下一会话的起点。

例如：从某实验室的Web服务器3天的日志作为会话的数据，数据大小是145MB。其中，θ的会话溢出时间为30min，会话总数47631,原始Web日志中项数为572614，数据清洗后项数为85892

谢谢