数据挖掘——数据预处理.ppt

《数据挖掘——数据预处理.ppt》由会员分享，可在线阅读，更多相关《数据挖掘——数据预处理.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据挖掘与知识发现数据挖掘与知识发现（复杂数据对象的数据挖掘与知识发现）（复杂数据对象的数据挖掘与知识发现）4数数据据挖掘的预处理挖掘的预处理数据挖掘的困难所在数据挖掘的困难所在nNoisenSkewed distributionnMissing values(incomplete info)nScalabilitynHigh dimensionalitynBias in datan.预处理在知识发现中所占份量预处理在知识发现中所占份量预处理预处理n各种不同的数据源和数据对象各种不同的数据源和数据对象数据的选择、集成与整合，对问题进行限定数据的选择、集成与整合，对问题进行限定n数据库中的数据具

2、有噪声、缺值、不易至数据库中的数据具有噪声、缺值、不易至数据的去噪和规范化问题，提高挖掘精度数据的去噪和规范化问题，提高挖掘精度n数据的变换数据的变换规范化、映射到不同的空间，提高挖掘效率规范化、映射到不同的空间，提高挖掘效率n数据的规约数据的规约取出冗余、属性聚类来压缩数据取出冗余、属性聚类来压缩数据数据的预处理是数据的预处理是KDD&DM的重要步骤的重要步骤预处理的基本功能预处理的基本功能n预处理主要是接受并理解预处理主要是接受并理解KDD要求，确定发现要求，确定发现任务任务n抽取与发现任务相关的数据源，根据背景知识抽取与发现任务相关的数据源，根据背景知识中的约束性规则对数据进行合法性检查

3、中的约束性规则对数据进行合法性检查n通过清理和归约等操作，生成供挖掘核心使用通过清理和归约等操作，生成供挖掘核心使用的目标数据。的目标数据。它汇集了原始数据库中与发现有关的所有数据它汇集了原始数据库中与发现有关的所有数据的总体特征，是知识发现状态空间的基底。的总体特征，是知识发现状态空间的基底。4数据挖掘的预处理数据挖掘的预处理4.1数据选择与集成4.2数据清理4.4数据归约4.4数据变换4.5数据离散4.1数据选择数据选择n分析需求和应用，了解业务背景分析需求和应用，了解业务背景n确定分析主题确定分析主题n数据库或数据仓库中选择索要分析的数据数据库或数据仓库中选择索要分析的数据n利用数据转换

4、工具进行分析处理利用数据转换工具进行分析处理4.1数据集成数据集成将将多多文文件件或或多多数数据据库库运运行行环环境境中中的的异异构构数数据据进进行行合合并并处处理理，解解决决语语义义的的模模糊糊性性。解解决决数数据的冲突问题以及不一致数据的处理问题。据的冲突问题以及不一致数据的处理问题。n数数据据来来自自多多个个系系统统，存存在在着着异异构构数数据据的的转转换换问问。多多个个数数据据源源的的之之间间还还存存在在许许多多不不一一致致的的地地方方，如如命命名名、结结构构、单单位位、含含义义等等。因因此此，数数据据集集成成并并非非是是简简单单的的数数据据合合并并，而而是是把把数数据据进进行行统统一

5、一化化和和规规范范化化处处理理的复杂过程。的复杂过程。n需需要要统统一一原原始始数数据据中中的的所所有有矛矛盾盾之之处处，如如字字段段的的同同名名异异义义、异异名名同同义义、单单位位不不统统一一、字字长长不不一一致致等等，把原始数据在最低层次上加以转换、提炼和聚集。把原始数据在最低层次上加以转换、提炼和聚集。n数据集成中还应考虑数据类型的选择问题数据集成中还应考虑数据类型的选择问题，尽量选，尽量选择占物理空间较小的数据类型。择占物理空间较小的数据类型。4.1数据集成数据集成冗余冗余n冗余的原因：数据库设计，不同来源的数冗余的原因：数据库设计，不同来源的数据引起的数据的相关性据引起的数据的相关性

6、n冗余检验：属性的相关性冗余检验：属性的相关性属性属性A,B其其相关性度量相关性度量4.2数据清理4.1数据选择与集成4.2数据清理4.4数据归约4.4数据变换4.5数据离散4.2数据清理数据清理n数据清理要去除源数据集中的数据清理要去除源数据集中的噪声噪声和和无关数据无关数据n处理遗漏数据和清洗脏数据处理遗漏数据和清洗脏数据n去除空白数据域和知识背景上的白噪声去除空白数据域和知识背景上的白噪声n考考虑虑时时间间顺顺序序和和数数据据变变化化等等，主主要要包包括括重重复复数数据处理和缺值数据处理据处理和缺值数据处理n完成一些数据类型的转换。完成一些数据类型的转换。4.2数据清理数据清理n数据清理

7、可以分为有监督和无监督数据清理可以分为有监督和无监督n有有监监督督过过程程是是在在领领域域专专家家的的指指导导下下，分分析析收收集集的的数数据据，去去除除明明显显错错误误的的噪噪音音数数据据和和重重复复记记录录，填补缺值数据；填补缺值数据；n无无监监督督过过程程是是用用样样本本数数据据训训练练算算法法，使使其其获获得得一一定定的的经经验验，并并在在以以后后的的处处理理过过程程中中自自动动采采用用这些经验完成数据清理工作。这些经验完成数据清理工作。4.2数据清理数据清理n另一个重要内容是数据类型的转换，通常是指另一个重要内容是数据类型的转换，通常是指连续属性的离散化连续属性的离散化n离散化方法有

8、等距区间法、等频区间法和最大离散化方法有等距区间法、等频区间法和最大熵法。熵法。n通过离散化，可以有效地减少数据表的大小，通过离散化，可以有效地减少数据表的大小，提高分类准确性。提高分类准确性。4数据挖掘的预处理数据挖掘的预处理4.1数据库与数据仓库4.2数据选择与集成4.3数据清理4.4数据归约4.5数据变换4.6数据离散4.4数据规约数据规约n有有些些数数据据属属性性对对发发现现任任务务是是没没有有影影响响的的，这这些些属属性性的的加加入入会会大大大大影影响响挖挖掘掘效效率率，甚甚至至还还可可能能导致挖掘结果的偏差。导致挖掘结果的偏差。简简化化是是在在对对发发现现任任务务和和数数据据本本身

9、身内内容容理理解解的的基基础础上上，寻寻找找依依赖赖于于发发现现目目标标的的表表达达数数据据的的有有用用特特征征，以以缩缩减减数数据据规规模模，从从而而在在尽尽可可能能保保持持数数据原貌的前提下最大限度地精简数据量。据原貌的前提下最大限度地精简数据量。4.4数据规约数据规约n主主要要有有两两个个途途径径：属属性性选选择择和和数数据据抽抽样样，分分别别针对数据库中的针对数据库中的属性和记录属性和记录。n属属性性选选择择包包括括针针对对属属性性进进行行剪剪枝枝、并并枝枝、找找相相关等操作。关等操作。n数据抽样是进行数据记录之间的相关性分析，数据抽样是进行数据记录之间的相关性分析，用少量的记录基底的

10、线性组合来表示大量的记用少量的记录基底的线性组合来表示大量的记录。它主要得用统计学中的抽样方法如简单随录。它主要得用统计学中的抽样方法如简单随机抽样、等距抽样、分层抽样等。机抽样、等距抽样、分层抽样等。4.4数据规约数据规约基于粗糙集理论的约简法基于粗糙集理论的约简法粗糙集（粗糙集（RoughSet,RS）一一种种研研究究不不精精确确、不不确确定定性性知知识识的的数数据据学学工工具具，目目前前受受到到了了KDD研研究究者者的的广广泛泛重重视视，用用RS理理论论对对数数据据时时行行处处理理是是一一种种十十分分有有效效的的精精简简数数据据维维数数的的方方法法。我我们们所所处处理理的的数数据据一一般

11、般存存在在信信息息的的含含糊糊性性问问题题，含含糊糊性性有有三三种种，术术语语的的模模糊糊性性，知识自身的不确定性；数据的不确定性。知识自身的不确定性；数据的不确定性。4.4数据规约数据规约基于粗糙集理论的约简法基于粗糙集理论的约简法粗糙集（粗糙集（RoughSet,RS）RS理理论论的的最最大大特特点点是是无无需需提提供供问问题题所所需需处处理理的的数数据据集集合合之之外外的的任任何何先先验验信信息息，其其基基本本思思路路是是利利用用定定义义在在数数据据集集合合U上上等等价价关关系系对对U进进行行划划分分。对对于于数数据据表表来来说说，这这种种等等价价关关系系可可以以是是某某个个属属性性，或

12、或者者是是几几个个属属性性的的集集合合。因因此此按按照照不不同同属属性性的的组组合合就就把把数数据据表表划划分分成成不不同同的的基基本本类类。在在这这些些基基本本类类的的基基础础上上进进一一步步求求得得最最小小约约简集。简集。4.4数据规约数据规约基于粗糙集理论的约简法基于粗糙集理论的约简法粗糙集（粗糙集（RoughSet,RS）采采用用RS理理论论作作为为数数据据预预处处理理方方法法具具有有许许多多的的优优点点：不不需需要要预预先先知知道道额额外外信信息息；算算法法简简单单、易易于于操操作作。应应用用RS的的属属性性约约简简可可以以有有效效地地去去除除冗冗余余现现象象，同同样样可可以以应应用

13、用RS方方法法中中的的约约简简技技术术删删除除某某些些属属性性的的多多余余值值，从从而而使使条条件件属属性性的的个个数和取值得到约简。数和取值得到约简。但但是是，RS理理论论只只能能处处理理离离散散型型属属性性。对对于于连连续续的的属属性性必必须须先先进进行行离离散散化化才才能能再再运运用用RS理理论论进进行处理。行处理。4.4数据规约数据规约基于粗糙集理论的约简法基于粗糙集理论的约简法概念概念树树的的基本思路基本思路在在数数据据库库中中，许许多多属属性性都都是是可可以以进进行行归归类类，各各属属性性值值和和概概念念依依据据抽抽象象程程度度不不同同可可以以进进行行数数据据归归类类并并构构成成一

14、一个个层层次次结结构构，概概念念的的这这种种层层次次结结构通常称为概念树。构通常称为概念树。概概念念树树一一般般由由领领域域专专家家提提供供，它它将将各各个个层层次次的的概念按一般到特殊的顺序排列。概念按一般到特殊的顺序排列。n基于概念树的数据预处理方法是一种归纳方法，基于概念树的数据预处理方法是一种归纳方法，其实是数据库中元组合并的处理过程，其基本其实是数据库中元组合并的处理过程，其基本思路如下思路如下：n首先，一个属性的具体的值被该属性的概念树首先，一个属性的具体的值被该属性的概念树中的父概念所代替，然后对相同元组进行合并，中的父概念所代替，然后对相同元组进行合并，构成更宏观的元组，并计算

15、宏元组所覆盖的元构成更宏观的元组，并计算宏元组所覆盖的元组数目仍然很大，那么用该属性的概念树中父组数目仍然很大，那么用该属性的概念树中父概念去替代或者根据另一个属性进行概念树的概念去替代或者根据另一个属性进行概念树的提升操作，最后行成覆盖面更广、量更少的宏提升操作，最后行成覆盖面更广、量更少的宏元组。元组。4.4数据规约数据规约基于概念树的数据浓缩基于概念树的数据浓缩n可可以以采采用用统统计计分分析析中中的的一一些些算算法法来来进进行行特特征征属属性性的的选选取取，比比如如主主成成分分分分析析、逐逐步步回回归归分分析析。这这些些方方法法的的共共同同特特征征是是用用少量的特征元组去描述的原始数据

16、。少量的特征元组去描述的原始数据。4.4数据规约数据规约基于统计分析的属性选择基于统计分析的属性选择n主成分分析的思想是：对于给定的输入数据矩主成分分析的思想是：对于给定的输入数据矩阵阵X，计算其相关系数矩阵计算其相关系数矩阵R=XX，取与取与R中中最大的几个特征值相应的特征向量作为主成分。最大的几个特征值相应的特征向量作为主成分。其中数据准则是希望每次取得一个综合变量的其中数据准则是希望每次取得一个综合变量的方差，在原变量的全部方差（或剩下的全部方方差，在原变量的全部方差（或剩下的全部方差）中所占的比例最大。差）中所占的比例最大。4.4数据规约数据规约基于统计分析的属性选择基于统计分析的属性

17、选择n主成分方法的特点是将描述某一事物的主成分方法的特点是将描述某一事物的多个变量压缩成描述该事物的少数几个多个变量压缩成描述该事物的少数几个合变量或称主成分（通常用原变量的线合变量或称主成分（通常用原变量的线性组合表示），旨在用新的少数几个综性组合表示），旨在用新的少数几个综合变量代替原始变量，并使这合变量代替原始变量，并使这种替代所种替代所蒙受的损失最少。主成分分析法具有变蒙受的损失最少。主成分分析法具有变差最优性。信息损失最小性。相关最优差最优性。信息损失最小性。相关最优性和回归最优性，使它得以成为多元降性和回归最优性，使它得以成为多元降维的重要工具之一。维的重要工具之一。4.4数据规约

18、数据规约基于统计分析的属性选择基于统计分析的属性选择4 数据挖掘的预处理 4.1数据库与数据仓库4.2数据选择与集成4.4数据清理4.4数据归约4.5数据变换4.6数据离散数据变换数据变换n数据变换主要是找到数据的特征表示，用维变数据变换主要是找到数据的特征表示，用维变换或转换方法减少有效变量的数目或找到数据换或转换方法减少有效变量的数目或找到数据的不变式，包括规格化、归约切换、旋转和投的不变式，包括规格化、归约切换、旋转和投影等操作。影等操作。简单变换简单变换n平滑：去噪平滑：去噪,方法：回归、聚类方法：回归、聚类n聚集：不同估量单位的聚集，如日聚集：不同估量单位的聚集，如日-月月-年年n数

19、据概化：抽象和提升数据概化：抽象和提升n规范化：将数据转化到一定区间，规范化：将数据转化到一定区间，0，1最小最小-最大规范化：最大规范化：零均值规范化：零均值规范化：空间变换空间变换n线性变换线性变换n小波变换小波变换（高维空间变化，正交基，可保持多种属性不（高维空间变化，正交基，可保持多种属性不变，在此后面我们将进行深入介绍）。变，在此后面我们将进行深入介绍）。4 数据挖掘的预处理 4.1数据库与数据仓库4.2数据选择与集成4.4数据清理4.4数据归约4.5数据变换4.6数据离散连续属性离散化连续属性离散化n离散属性也称符号的（离散属性也称符号的（symbolic）、）、或名称或名称的（的

20、（nominal）、）、或类别的（或类别的（categorical）n连续属性也称实数的（连续属性也称实数的（real）、）、或有序的或有序的（ordered）、）、或数值的（或数值的（numerical）n连续属性离散化在连续属性离散化在KDD中是一个很重要的问题。很多中是一个很重要的问题。很多数据挖掘和知识发现算法要求连续属性数据必须预先数据挖掘和知识发现算法要求连续属性数据必须预先离散化之后才行。离散化之后才行。n离散化的任务是把连续属性的取值范围或取值区间划离散化的任务是把连续属性的取值范围或取值区间划分为若干个数目不太多的小区间，其中每个区间对应分为若干个数目不太多的小区间，其中每个

21、区间对应着一个离散的符号。着一个离散的符号。n例如，设当前考察的属性是年龄，则一种可能的离散例如，设当前考察的属性是年龄，则一种可能的离散化是化是0.11小孩，小孩，12.17少年，少年，18.44青壮年，青壮年，45-69中年，中年，79.老老年。年。连续属性离散化连续属性离散化n连续属性离散化的方法有很多种：连续属性离散化的方法有很多种：n是否自动离散化：完全由人手工离散化，完是否自动离散化：完全由人手工离散化，完全由机器自动离散化，机器辅助人离散化。一全由机器自动离散化，机器辅助人离散化。一般地，离散化是指机器自动离散化。般地，离散化是指机器自动离散化。n是否与分类或决策类别有关：一是考

22、虑分类是否与分类或决策类别有关：一是考虑分类类别；另一是不考虑分类类别，这种方法可用类别；另一是不考虑分类类别，这种方法可用于非监督学习或概念聚类学习，不过当用于带于非监督学习或概念聚类学习，不过当用于带有类别标记的分类学习时效果肯定不会好于上有类别标记的分类学习时效果肯定不会好于上面的方法。面的方法。连续属性离散化连续属性离散化n一般有这样几种：一般有这样几种：n等宽区间法（等宽区间法（equal-width-intervals）n等频区间法（等频区间法（equal-frequency-intervals）n最大熵法（最大熵法（maximumentropy）4.2.1语言场及语言值结构语言场

23、及语言值结构n给定数据库给定数据库D上的所有属性集合上的所有属性集合A=a1,a2,amn其中，其中，ai也称为语言变量，每个属性又可以由不同的也称为语言变量，每个属性又可以由不同的程度词来描述属性的状态程度词来描述属性的状态,如对第一个属性如对第一个属性ai可以表可以表示为示为ai=ai1,ai2,aikn其中，其中，aij也称为语言值，也称为语言值，aij的的i表示第表示第i个属性，个属性，j表示表示该属性的第该属性的第j个程度词，如对温度而言，个程度词，如对温度而言，“很高很高”、“高高”等都是程度词，也即语言值。等都是程度词，也即语言值。n属性程度词是把某一属性和它的一个程度词放在一起

24、属性程度词是把某一属性和它的一个程度词放在一起（即语言变量（即语言变量+语言值），表示该属性的某种状态，语言值），表示该属性的某种状态，例如，例如，“温度很高温度很高”是一个属性程度词。是一个属性程度词。数值：数值：3535 37 t 37 tm m(D)(D)基础变量基础变量（N N）语言值语言值 低烧低烧1 1 正常正常n n2 2 n nm m数数值值区区间间：aa0 0，a a1 1 aa1 1，a a2 2 aam-1m-1，a am m（L L）语言变量）语言变量 体温、疼痛体温、疼痛n定定义义4.1：在在语语言言变变量量相相应应的的基基础础变变量量论论域域中中，各各个个被被划划分

25、分的的交交叉叉区区间间的的中中点点连连同同-邻邻域域（通通常常为为允允许许误误差差值值）内内的的点点，称称为为标标准准样样本本（点点），其其取取值值邻邻域域称称为为标标准准值值；其其余余诸诸点点均均称称为为非非标标准准样样本本（点点），其其取取值值称称为为非非标标准准值值。它它们们分分别别构构成成标标准准样样本本空空间间与与非非标标准准样样本本空空间间，并并统称为一般样本空间。统称为一般样本空间。n属性的划分如下图所示，对于类别属性和取值范围不宽的离散型数值属性，可以将每个属性值映射到相应语言变量的语言值，但是对于连续型属性、或取值范围很宽的离散型属性，必须将其分为若干区间，然后将每个区间映射

26、为一个相应的语言值。n有有了了以以上上的的算算法法就就可可以以得得到到语语言言值值所所映映射射的的区区间间，其其关关键键是是求求临临界界点点，然然后后再再对对真真实实数数据据库库进进行行处处理理，转转换换为为挖挖掘掘数数据据库库。令令真真实实数数据据库库为为D，属属性性集集为为(e1,e2,em)，属属性性ei所所对对应应的的数数据据精精度度为为Pi，划划分分语语言言值值的的个个数数为为Numi，划划分分语语言言值值的的标标准准样样本本点点为为aj,对对应应的的-邻邻域域的的半半径径为为rj，其其中中j=1,2,Numi，对对应应的的临临界界点点数数值值为为Vk，其中其中k=1,2,Numi-

27、1，则则其算法描述如下：其算法描述如下：n(1)fori:=1tomdon(2)forj:=1toNumi-1don(4)u:=ajn(4)IsLarge:=Truen(5)whileIsLargedon(6)u:=u+Pin(7)if u(aj+rj)and u(aj+1-rj+1)thenn(8)n(9)求求，/根根据据公公式式（4-2）n(10)ifthenn(11)Vj=un(12)IsLarge:=Falsen(14)end;n从以上讨论可以看出，利用语言场理论对连续从以上讨论可以看出，利用语言场理论对连续属性进行离散化，该方法简单，计算时间短，属性进行离散化，该方法简单，计算时间短

28、，可以根据专家（用户）的意愿来划分连续属性，可以根据专家（用户）的意愿来划分连续属性，从而用自然语言来描述最后得到的规则，使之从而用自然语言来描述最后得到的规则，使之更为用户所理解，因此比较实用，其不足之处更为用户所理解，因此比较实用，其不足之处是受人为因素的影响。是受人为因素的影响。离散化的问题离散化的问题n离离散散化化方方法法的的一一个个先先天天不不足足是是可可能能降降低低发发现现的的知知识识的的精精确确度度，因因此此离离散散化化过过程程如如同同其其他他的的汇汇总总小小结结过过程程一一样样，可可能能会会导导致致某某些些相相关关的的详详细细信信息息的的丢丢失失。另另外外，离离散散化化方方法法对对挖挖掘掘出出的的知知识识的的质质量量的的影影响响如如何何，仍仍是是一一个个有有待待研研究究的的课课题。题。n离离散散化化方方法法即即改改变变连连续续属属性性为为离离散散值值。属属性性进进行行离离散散化化的的思思想想是是输输入入一一个个（整整数数的的或或连连续续值值的的）属属性性值值输输出出一一个个有有序序区区间间，因因此此整整个个输输入入域域相相应应与与一一个个有有序序区区间间列列表表。离离散散化化方方法法常常常常跟分类问题相联系。跟分类问题相联系。