第二篇 数据挖掘与空间数据挖掘,第五章 数据挖掘概念与数据预处理,2,第五章 目录,5.1 数据挖掘概述 5.2 数据挖掘分类 5.3 数据挖掘系统 5.4 数据预处理 5.5 数据挖掘与数据仓库 5.6 数据挖掘的应用和发展 5.7 本章小结,3,引例,美国加州某个超级连锁店通过数据挖掘，从记录着每天销售和顾客基本情况的数据库中发现，在下班后前来购买婴儿尿布的顾客多数是男性，他们往往也同时购买啤酒。于是这个连锁店的经理当机立断重新布置了货架，把啤酒类商品布置在婴儿尿布货架附近，并在两者之间放上土豆片之类的佐酒小食品，同时把男士们需要的日常生活用品也就近布置。这样一来，上述几种商品的销量几乎马上成倍增长。,4,5.1 数据挖掘概述（1）,数据库中的知识发现（Knowledge Discovery in Database，简称KDD）是一个从数据库中挖掘有效的、新颖的、潜在有用的和最终可理解的模式的复杂过程。 1）数据是一组事实的集合，它可以来自不同的数据源，可以是规则数据，也可以是非规则数据。 2）模式是关于数据子集的某种语言描述的表达式或某种可应用的模型，又称为知识。 3）模式必须是有效的、新颖的、潜在有用的和最终可理解的，分别用可信度、新颖度、可用度和简单度对其进行评价。 4）KDD过程是一个复杂过程，其步骤如图5.1所示。,5,5.1 数据挖掘概述（2）,图5.1 KDD步骤 KDD步骤 研究问题域。包括掌握应预先了解的有关知识和确定数据挖掘任务； 选择目标数据集。根据上一步骤的要求选择要进行挖掘的数据； 数据预处理。将上一步骤的数据进行集成、清理、变换等，使数据转换为可以直接应用数据挖掘工具进行挖掘的高质量数据； 数据挖掘。根据数据挖掘任务和数据性质选择合适的数据挖掘工具挖掘模式； 模式解释与评价。去除无用的或冗余的模式，将有趣的模式以用户能理解的方式表示，并储存或提交给用户； 应用。用上述步骤得到的有趣模式（或知识）指导人的行为。 数据挖掘（Data Mining，简称DM）是KDD过程中对数据真正应用算法抽取知识的那一步骤，是KDD过程中的重要环节。人们往往不加区分地使用KDD和DM，本书也不明确区分两者。,6,5.2 数据挖掘分类,5.2.1概述 1. 根据挖掘的数据源类型分类 2. 根据采用的挖掘技术分类 3. 根据发现的知识类型分类 5.2.2描述性挖掘 1. 特征与比较描述 2. 关联分析 3. 聚类分析 4. 异常检测 5.2.3预测性挖掘 1. 数据分类 2. 数值预测,7,5.3 数据挖掘系统 5.3.1 数据挖掘系统的结构,图5.2 数据挖掘系统的典型结构,8,5.3.2 数据挖掘系统的设计,在数据挖掘系统的设计中，需要考虑如下问题。 1. 数据挖掘系统怎样与数据源集成 2. 数据挖掘系统怎样指定目标数据集 3. 数据挖掘系统怎样指定数据挖掘任务 4. 数据挖掘系统怎样解释与评价模式 5. 数据挖掘系统怎样利用领域知识 6. 数据挖掘系统怎样提交知识,9,5.4 数据预处理 5.4.1 数据清理（1）,1. 消除不完整 1）使用一个全局常量填充：例如，某顾客表中的年龄属性，使用“unknown”填充。 2）使用属性平均值填充：例如，某顾客表中的薪水属性，使用薪水属性平均值填充。 3）使用相同类的属性平均值填充：例如，在分类规则挖掘中，可以使用与给定样本属于相同类的其他样本的属性平均值填充。 4）使用最可能的值填充：例如，将某顾客表中的薪水属性作为预测属性，采用预测算法，预测给定样本的薪水属性最可能的值并填充。,10,5.4.1 数据清理（2）,2. 消除噪声 1）通过平滑数据消除噪声：例如，分箱技术，它将数据排序，根据分布规则将数据分布到不同箱中，根据平滑规则将同一箱中的数据用相应数据替换。分布规则可以是等深、等宽。等深是指每个箱中的数据个数相等；等宽是指每个箱的取值区间大小相等。平滑规则可以是平均值平滑、中值平滑、边界平滑。平均值平滑是指将同一箱中的数据全部用该箱中数据的平均值替换；中值平滑是指将同一箱中的数据全部用该箱中数据的中值替换；边界平滑是指将同一箱中的数据分别用该箱中最近的边界值替换。 2）通过识别孤立点消除噪声：例如，采用聚类算法得到类（或簇），在类之外的数据可以视为孤立点（或噪声）并消除。 3. 消除不一致,11,5.4.1 数据清理（3）,例5.1 假设某属性的值为18，12，3，9，7，6，15，21，16，采用分箱技术平滑数据消除噪声。分布规则为等深、深度为3，平滑规则为平均值平滑。 首先，将属性的值排序为3, 6, 7, 9, 12, 15, 16, 18, 21 然后，根据分布规则（等深、深度为3）将数据分布到 箱1：3, 6, 7 箱2：9, 12, 15 箱3：16, 18, 21 最后，根据平滑规则（平均值平滑）将数据替换为 箱1：5.3, 5.3, 5.3 箱2：12, 12, 12 箱3：18.3, 18.3, 18.3,12,5.4.2 数据集成,冗余是一个重要问题。一个属性是冗余的，如果它能由另外的属性“导出” 。有些冗余可以被相关分析检测到。 对给定的两个数值属性A、B，它们之间的相关性可以根据下式计算 式中，n是元组个数， 、 分别是A、B的平均值 （即 ）， 、 分别是A、B的标准差 （即 ）。 如果rA,B0，则A与B正相关，A的值随着B的值的增加而增加； 如果rA,B0，则A与B负相关，A的值随着B的值的增加而减少； 如果rA,B=0，则A与B独立。因此，|rA,B|很大时，A与B可以去除一个。,13,5.4.3 数据变换（1）,1. 最小-最大规格化 对给定的数值属性A， minA，maxA为A规格化前的取值区间，new_ minA，new_ maxA 为A规格化后的取值区间，最小-最大规格化根据下式将A的值v规格化为值v,14,5.4.3 数据变换（2）,例5.2 假设某属性规格化前的取值区间为100，100，规格化后的取值区间为0，1，采用最小-最大规格化66，得,15,5.4.3 数据变换（3）,2. 零-均值规格化 对给定的数值属性A， 、 分别为A的平均值、标准差，零-均值规格化根据下式将A的值v规格化为值v,16,5.4.3 数据变换（4）,例5.3 假设某属性的平均值、标准差分别为80、25，采用零-均值规格化66,17,5.4.3 数据变换（5）,3. 小数定标规格化 对给定的数值属性A，max|A|为A的最大绝对值，j为满足下式的最小整数 小数定标规格化根据下式将A的值v规格化为值v,18,5.4.3 数据变换（6）,例5.4 假设属性A规格化前的取值区间为120，110，采用小数定标规格化66，A的最大绝对值为120，j为3，66规格化后为,19,5.4.4 数据归约（1）,属性归约：又称为维归约、属性子集选择、特征子集选择，它通过删除不相关的或冗余的属性减小数据集，它的目标是找出最小属性集， 使得数据在其上的概率分布尽可能地接近在原属性集上的概率分布。 粗糙集方法 决策树分类 记录归约 ：通过用少量记录代表或替换原有记录来减小数据集。 抽样 数据概化（面向属性归纳）,20,5.4.4 数据归约（2）,面向属性归纳：根据属性的概念分层，通过阈值控制，将属性的低层属性值用相应高层概念替换，并合并由此得到的相同记录，达到记录归约。 给定关系表、各个属性的概念层次树及属性阈值，面向属性归纳对各个属性进行如下处理： 首先根据属性A的概念层次树，将关系表中A的属性值转换为最低层的相应概念，也称为叶概念，统计关系表中A的不同叶概念个数，如果A的不同叶概念个数大于A的属性阈值，再根据A的概念层次树，将关系表中A的叶概念转换为上一层的相应概念，如此重复，直至关系表中A的不同概念个数小于等于A的属性阈值；最后合并相同记录，并统计重复记录数目。,21,5.4.4 数据归约（3）,例5.5 假设气温如表5.2所示，“地名”、“气温”属性的概念层次树分别如图5.3、图5.4所示，属性阈值均为4，采用面向属性归纳进行记录归纳，气温如表5.3所示，记录由6个归约为3个，count的值表示重复记录数目。 图5.3 “地名”属性的概念层次树,22,5.4.4 数据归约（4）,图5.4 “气温”属性的概念层次树,23,5.4.5 属性概念分层的自动生成（1）,离散属性概念分层的自动生成：这种方法基于这样一个事实：概念层次树中高层的概念个数一般少于低层的概念个数。 连续属性概念分层的自动生成：基于熵的离散化技术。,24,5.4.5 属性概念分层的自动生成（2）,例5.6 “地址”属性的值由国家、省、市组成，如表5.4所示。首先统计国家、省、市的不同值个数，不同值个数最少的在最高层，依次类推，可以得到“地址”属性的概念层次树结构，也称为模式定义的概念分层。如图5.5所示，国家在最高层、省在中间层、市在最低层。然后根据结构的从属关系，确定各层的概念及从属关系，最终得到“地址”属性的概念层次树。如图5.6所示，因为市从属于省，而昆明市、大理市、玉溪市、曲靖市的省都是云南省，所以它们从属于云南省，同理，成都市从属于四川省，贵阳市从属于贵州省。,25,5.4.5 属性概念分层的自动生成（3）,表5.4 “地址”属性,26,5.4.5 属性概念分层的自动生成（4）,27,5.4.5 属性概念分层的自动生成（5）,基于熵的离散化技术 1）给定关系表r及其连续属性A，计算在A的取值区间V上的记录集合S的熵。 S的熵定义为： 式中，|c|为在S中属于目标类c的记录数，当目标属性是A时，为A取属性值v（=c）的记录数，|S|为S中的记录数。,28,5.4.5 属性概念分层的自动生成（6）,2）对A在V上取的每个v，用v划分V为v1（v）、v2（v），划分S为S1，S2，计算在此划分下S的熵。 在此划分下S的熵定义为： 式中，|S1|、|S2|、|S|分别为S1、S2、S中的记录数，E(S1)、E(S2)分别为S1、S2的熵。,29,5.4.5 属性概念分层的自动生成（7）,3）对在V上的每个划分v1（v）、v2（v），计算在此划分下S的信息增益。 在此划分下S的信息增益定义为： 式中，E(S)为S的熵，E(S,v)为在此划分下S的熵。 4）选择使S的信息增益最大的划分作为最佳划分，记为V1（T）、V2（T）（假设T是使S的信息增益最大的v）。 5）递归地应用步骤1）4）于V1、V2及S1、S2上，直至满足一定的结束条件，例如，最大信息增益小于某个阈值。,30,5.4.5 属性概念分层的自动生成（8）,例5.7 假设“气温”属性就是目标属性，它的取值区间为100,100，在此区间上的属性值及记录数如表5.5所示，采用基于熵的离散化技术生成“气温”属性的概念层次树。 表5.5 “气温”属性,31,5.4.5 属性概念分层的自动生成（9）,首先，划分区间100,100,32,5.4.5 属性概念分层的自动生成（10）,G(100, 100, 3)=2.03782.0378=0 G(100, 100, 6)= 2.03781.7465=0.2913 G(100, 100, 18)= 2.03781.464=0.5738 G(100, 100, 22)= 2.03781.0741=0.9637 G(100, 100, 26)= 2.03781.3323=0.7055 最佳划分为 V1=100, 22) (T=22) V=22, 100(T=22) 并且产生“气温”属性的概念层次树的相应最高层与次高层，如图5.7所示。,33,5.4.5 属性概念分层的自动生成（11）,图5.7 “气温”属性的概念层次树的部分结构 其次，应用相同方法分别划分区间100,22