数据挖掘原理与算法教案.doc

数据挖掘原理与算法教案讲授：王志明湖南农业大学理学院信息科学系第一章 绪论教学目的：掌握数据挖掘的概念，背景，基本理论，基本应用，发展趋势教学重点难点：数据挖掘的概念，粗糙集方法教学课时：2教学过程：一、概念数据挖掘(Data mining)属一交叉学科，融合了数据库技术(Database)，人工智能(Artificial Intelligence)，机器学习(Machine Learning)，统计学(Statistics)，知识工程(Knowledge Engineering),面向对象方法(Object-Oriented Method)，信息检索(Information Retrieval)，高性能计算(High-Performance Computing)以及数据可视化（Data Visualization）等技术。联机事物处理（On Line Transaction Processing，OLTP）是在网络环境下的事务处理工作，以快速的响应和频繁的数据修改为特征，使用户利用数据库能够快速地处理具体的业务。知识：广义讲就是数据、信息的表现形式。人们常把概念、规则、模式、规律和约束等看成知识。数据挖掘：又称数据库中的知识发现(Knowledge Discovery in Database, KDD),就是从大量数据中获取有效地、新颖的、潜在有用的、最终可理解的模式的非平凡过程。简单的说就是从大量数据中提取或挖掘知识。数据仓库是面向主题的、集成的、稳定的，不同时间的数据集合，用于支持经营管理中决策制定过程。二、数据挖掘产生与发展1）查询、统计、报表等简单传统的数据处理无法获取知识。这样促使数据挖掘技术的发展。利用数据仓库存储数据。2）数据挖掘技术产生的技术背景：（1）数据库、数据仓库、Internet等信息技术的发展；(2)计算机性能的提升；(3)统计学和人工智能等数据分析方法的应用。3）数据挖掘技术发展应用以及重点需要的研究的方面：（1）商业中的应用（2）与特定数据存储类型的适应问题（3）大型数据的选择与规格化问题（4）数据挖掘系统的构架与交互式挖掘技术（5）数据挖掘语言与系统的可视化问题（6）数据挖掘理论与算法研究三、数据挖掘的分类 见书P11四、广义知识挖掘 1、概念描述，包括特征性描述和区别性描述 2、多维数据分析，如求和，计数，平均，最大值等 3、多层次概念描述 （1）模式分层；（2）集合分组分层；（3）操作导出层；（4）基于规则分层五、类知识挖掘1、分类：决策树、贝叶斯分类、神经网络、遗传算法与进化理论、类比学习、粗糙集、模糊集等2、聚类：基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法六、预测型知识挖掘1、趋势预测分析2、周期分析模式3、序列模式4、神经网络七、粗糙集方法粗糙集（Rough Set）是波兰数学家Z.Pawlak于1982年提出的。粗糙集以等价关系（不可分辨关系）为基础，用于分类问题。它用上、下近似（upper approximation, lower approximation）两个集合来逼近任意一个集合，该集合的边界线区域被定义为上近似集和下近似集之差集。1、等价粗糙集把客观世界抽象为一个信息系统，一个信息系统是一四元组S=(U，A，V，f )的定义为:U:是一个非空有限对象(元组)集合, U=x1 x2 xn,其中xi为对象(元组)。A:是对象的属性集合,A=A1,A2,An,A常分为两个不相交的子集,即条件属性C和决策属性D, V:是属性值的集合， V=V1,V2,Vn,Vi是Ai的值域。 f ：是信息函数，f:对于A中任意一个属性a,若两记录和它们的属性值相同，称和是对属性a的等价关系。属于同一等价关系的归位一个等价类。2、上近似和下近似 1、设U是对象（事例）的集合U=x1 x2 xn；B是属性集A的子集，R(B)是U上的二元等价关系，若对任意集合O，B是属性集A的子集，则O的下近似定义为： 这里表示x在R(B)上的等价类。 上近似定义为： 3、约简 设有两属性集,是的真子集，如果，则称可归约为，若属性集B不可归约，则称B为U的一个约简或归约子。 4、依赖度 设有两属性集P和Q，则P对Q的属性依赖度定义为：，其中，表示集合X在属性集上的下近似。 设，C是条件属性和D是决策属性,则属性重要度定义为：全集U可以划分为三个不相交的区域，即正域（Pos），负域（NEG）和边界（BND）：从上面可见：用图说明正域、负域和边界，每一个小长方形表示一个等价类。 正域、负域和边界NEG（X）Pos（X）=BND（X）X 正域负域边界5、粗糙集若，即，即边界为空，称X为A的可定义集；否则X为A不可定义的，即，称X为A的Rough集（粗糙集）。6、规则的提取通过分析U中的两个划分和之间的关系，把C视为分类条件，D视为分类结论，我们可以得到下面的分类规则：1）当，则有： 和分别是等价集和等价集中的特征描述。2）当时（完全被包含）即下近似，建立的规则是确定的，规则的可信度cf=1.0。3）当时（部分被包含）即上近似，建立的规则是不确定的，规则的可信度为： cf=4)当时（不被包含），和不能建立规则。7、举例(汽车数据)IDPowerTurboWeightIDPowerTurboWeight1highyesmed6mediumyeslight2lownolight7lownoheavy3mediumyeslight8highnoheavy4highnolight9highyesmed5highyesmed10lownoheavyU=1,2,3,4,5,6,7,8,9,10A=power, turbo, weightV=low, high, medium, yes, no, light, heavy, medC= power, turbo, D=weight按照C，则U分为：E1=1，5，9，E2=2，7，10，E3=3，6，E4=4，8按照D，则U可分为Y1=1,5,9, Y2=7,8,10, Y3=2,3,4,6P28八、数据挖掘的应用1、CRM（客户关系管理）的应用2、体育竞技中的应用3、商业银行的应用4、电信中的应用5、科学探索中的应用6、信息安全中的应用第二章教学目的：掌握知识发现过程以及数据处理有关概念的概念，基本应用 教学重点难点：知识发现技术要点、过程模型处理教学课时：3教学过程：一、知识发现过程1、大概过程（1）问题定义阶段（2）数据抽取阶段 目标数据（Target Data），是根据用户的需要从原始数据库中选取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录等。数据转换的主要目的是完成数据类型转换。尽量消减数据维数或降维，以减少数据挖掘时要考虑的属性个数。（3）数据挖掘 首先要确定挖掘的任务或目的，如数据分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。实施数据挖掘算法，获取有用的模式（4）知识评估阶段获取的模式经过评估，可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求。把结果转换为用户易懂的另一种表示，如把分类决策树转换为“if .then”规则。2、数据清洗与预处理目标数据（Target Data），是根据用户的需要从原始数据库中选取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录等。数据转换的主要目的是完成数据类型转换。尽量消减数据维数或降维，以减少数据挖掘时要考虑的属性个数。二、数据库中的知识发现处理过程模型1、阶梯处理过程模型数据源数据数据集成目标数据预处理后数据转换数据模式知识数据选择预处理数据挖掘数据转换结果表达和解释数据准备数据挖掘结果评价KDD过程2、螺旋处理过程模型 G. H. John提出定义问题抽取数据清洗数据数据工程算法工程运行挖掘算法分析结果3、以用户为中心的处理模型Brachman 和 Anand从用户角度对KDD处理过程进行了分析。任务发现数据发现数据清洗模型开发数据分析输出结果生成4、联机KDD模型 传统数据挖掘的缺陷：（1）过分强调自动化，忽视交互性，导致用户对数据挖掘过程参与过程困难；（2）数据挖掘算法对用户是一个“黑盒”，只有在算法挖掘结束后，用户才能评价发现的模式，若对模式不满意，则 重复挖掘过程，消耗资源；（3）传统数据挖掘过程只能一次对一个数据集进行挖掘。OLAM（On Line Analytical Mining）联机分析挖掘由OLAP发展而来。被分为几个层次：（1） L0层：数据集，包含了相关的数据库和数据仓库。（2） L1层：形成支持OLAP和OLDM的多维数据集，主要由元数据集和数据立方体。（3） L2层：是OLAP和OLDM的应用层，包含相互关联并协同工作的OLAM引擎和OLAP引擎。L2接受数据挖掘请求，通过访问多维数据和元数据，完成数据挖掘和分析工作。（4） L3层：是一个用户接口层，它主要承担用户请求的理解与挖掘结果的解释和表达等。三、知识发现软件和工具的发展1、独立的知识发现软件2、横向的知识发现工具集(P52) DBMiner, Quest, IBM Intelligent Miner, Darwin, ReMind3、纵向的知识发现解决方案 如证券系统的趋势预测；银行和电信行业的欺诈行为检测；基因分析系统中的DNA识别等4、KDD系统介绍 Quest：QUEST是IBM公司Almaden研究中心开发的一个多任务数据挖掘系统，目的是为新一代决策支持系统的应用开发提供高效的数据开采基本构件。系统具有如下特点：提供了专门在大型数据库上进行各种开采的功能：关联规则发现、序列模式发现、时间序列聚类、决策树分类、递增式主动开采等。各种开采算法具有近似线性（O(n)）计算复杂度，可适用于任意大小的数据库。算法具有找全性，即能将所有满足指定类型的模式全部寻找出来。为各种发现功能设计了相应的并行算法。DBMiner： DBMiner是加拿大SimonFraser（加拿大名校- 西蒙菲沙大学）大学开发的一个多任务数据挖掘系统，它的前身是DBLearn。该系统设计的目的是把关系数据库和数据开采集成在一起，以面向属性的多级概念为基础发现各种知识。DBMiner系统具有如下特色：能完成多种知识的发现：泛化规则、特性规则、关联规则、分类规则、演化知识、偏离知识等。综合了多种数据开采技术：面向属性的归纳、统计分析、逐级深化发现多级规则、元规则引导发现等方法。提出了一种交互式的类SQL语言数据开采查询语言DMQL。能与关系数据库平滑集成。实现了基于客户/服务器体系结构的Unix和PC（Windows/NT）版本的系统。四、知识发现项目的过程化管理（略）五、数据挖掘语言介绍第三章 关联规则挖掘理论和算法教学目的：掌握关联规则挖掘的概念，背景知识，了解常见关联规则挖掘的数据挖掘算法教学重点难点：关联规则挖掘常见算法教学课时：6教学过程：关联规则挖掘最早由Agrawal于1993年提出，目的是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式 。一、概念：事务数据库：设是项（Item）的集合。记为事务（Transaction）的集合（事务数据库），每个事务都对应I上的一个子集。支持度：设，项目集在数据集D上的支持度(support)是包含的事务在D中所占的百分比，即：support()=频繁项目集：对项目集I和事务数据库D，T中所有满足用户指定的最小支持度(minsupport)的项目集，即大于或等于minsupport的I的非空子集，称为频繁项目集(Frequent Itemsets)或者大项目集(Large Itemsets)。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集(Maximum Frequent Itemsets)或最大项目集(Maximum Large Itemsets)。规则的可信度：一个定义在I和D上的形如的关联规则通过满足一定的可信度、信任度或置信度(Confidence)来给出，所谓可信度是指包含和的事务数与包含的事务数之比，即，其中强关联规则：D在I上满足最小支持度和最小信任度的关联规则成为强关联规则（Strong Association Rule）我们一般所说的关联规则指强关联规则。一般地，给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小支持度和最小可信度来寻找强关联规则的过程。其划分为两个小问题：（1） 发现频繁项目集：找出支持度大于最小支持度的项集，即频繁项集。（2） 生成关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。例子：例子：讨论不购买商品与购买商品的关系。设交易集D，经过对D的分析，得到表格:买咖啡不买咖啡合计买牛奶20525不买牛奶70575合计9010100设定minsupp=0.2, minconf=0.6, 得到如下的关联规则： 买牛奶 买咖啡 s=0.2 c=0.8即80的人买了牛奶就会买咖啡。同时得到结论：90的人肯定会买咖啡。规则 买咖啡 不买牛奶 s=0.7 c=0.78支持度和可信度分别为0.7和0.78，更具有商业销售的指导意义。二、经典的频繁项目集的生成算法1、项目集空间理论定理1 频繁项集的所有非空子集都必须也是频繁的。定理2 非频繁项目集的超集是非频繁项目集。2、Apriori算法 1、Apriori 使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3，如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。 2、“K-项集”产生“K+1-项集”设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK+1。有公式：CK+1=LKLK=XY，其中X，YLK， |XY|=K+1其中C1是1-项集的集合，取自所有事务中的单项元素。 如：如 L1=A，BC2=AB=A，B，且|AB|=2L2=A，B，A，CC3=A，BA，C=A，B，C，且 |ABC|=3例1见P72例2生成频繁项目集过程:事务ID事务的项目集T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C解:1) 在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法扫描所有的事务，对每个项的出现次数计数。见图中第1列。2) 假定最小事务支持计数为2（即min-sup=2/9=22%），可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。见图中第2列。3) 为发现频繁2-项集的集合L2，算法使用L1*L1来产生候选集C2。见图中第3列。4) 扫描D中事务，计算C2中每个候选项集的支持度计数，如图中的第4列。5) 确定频繁2-项集的集合L2，它由具有最小支持度的C2中的候选2-项集组成。见图第5列6) 候选3-项集的集合C3的产生，得到候选集：C3=A，B，C，A，B，E，A，C，E，B，C，D，B，C，E，B，D，E按Apriori 性质，频繁项集的所有子集必须是频繁的。由于A，D，C，D，C，E，D，E不是频繁项集，故C3中后4个候选不可能是频繁的，在C3中删除它们。见图第6列。扫描D中事务，对C3中的候选项集计算支持度计数，见图第7列。7) 确定L3，它由具有最小支持度的C3中候选3项集组成，见图第8列。8）按公式产生候选4项集的集合C4，产生结果A,B,C,E,这个项集被剪去，因为它的子集B,C,E不是频繁的。这样L4=。此算法终止。L3是最大的频繁项集，即：A,B,C和A,B,E。3、定理:设项目集X，X1是X的一个子集，如果规则X-（l-X）不是强规则，那么X1-(l-X1)一定不是强规则。4、定理：设项目集X，X1是X的一个子集，如果规则Y-X是强规则，那么规则Y-X1一定是强规则。三、Apriori算法的性能瓶颈问题1）多次扫描事务数据库，需要很大的I/O负载2）可能产生庞大的候选集四、Apriori算法改进1、基于数据分割的方法1）合理利用主存空间2）支持并行挖掘算法2、基于散列(Hash)的方法Hash，一般翻译做“散列”，也有直接音译为”哈希“的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。1995年，Park等提出一个基于散列技术的产生频繁项目集的算法。他们通过试验发现寻找频繁项目集的主要计算是在生成2-频繁项目集L2上。例P753、基于采用（Sampling）的方法1996年，Toivonen提出一个基于采用技术产生频繁项目集的算法。其思想是：先使用数据库的抽样数据得到一些可能成立的规则，然后利用数据库的剩余部分验证这些关联规则是否正确。有点是简单且显著降低因为挖掘所付出的I/O的代价。缺点是抽样数据的选取以及由此而产生的结果的偏差过大。五、对项目集空间理论的发展随着数据库容量的增大，重复访问数据库将导致性能的低下，因此，探索新的理论和算法减少数据库的扫描次数和候选集空间的占用，采用并行挖掘等方式提高数据挖掘效率已经成为研究的热点之一。1、探索新的管理规则挖掘理论2、提高裁减项目集格空间的效率3、分布和并行环境下的关联规则挖掘问题1）Close算法在close算法中，也使用了迭代的方法：利用频繁闭合i-项目集记为FCi，生成频繁闭合(i+1)-项目集，记为FCi+1（i=1）。首先找出候选1-项目集，记为FCC1，通过扫描数据库找到它的闭合以及支持度，得到候选闭合项目集，然后对其中的每个候选闭合项进行修剪，如果支持度不小于最小支持度，则加入到频繁闭合项目集FC1.再将它与自身链接，以得到候选项频繁闭合2-项目集FCC2，再经过修剪得到FC2，再利用FC2推出FC3，如此下去，直到有某个值r使得候选频繁频繁闭合r-项目集FCCr为空，这时算法结束。例P80其余算法略。八、改善关联规则挖掘质量问题衡量关联规则挖掘结果的有效性应该多方面考虑：1） 准确性：挖掘出的规则必须反映数据的实际情况。2） 实用性：挖掘出的规则必须是间接可用的，而且是针对挖掘目标的。3） 新颖性：挖掘出的关联规则可以为用户提供新的有价值信息。可以在用户主观和系统主观两个层面上考虑关联规则挖掘的质量问题。1、用户主观层面 约束数据挖掘可以为用户参与知识发现工作提供一种有效的机制。1） 知识类型的约束2） 数据的约束3） 维/层次约束4） 知识内容的约束5） 针对具体知识类型的约束2、系统客观层面九、约束数据挖掘问题1、约束在数据挖掘中的作用1）聚焦挖掘任务，提高挖掘效率2）保证挖掘的精确性3）控制系统的使用和规模2、约束的类型第四章 分类方法教学目的：掌握分类的概念，背景，基本理论，基本应用，发展趋势和常见分类算法教学重点难点：分类算法教学课时：4教学过程：分类是数据挖掘中一项非常重要的任务，分类的目的是学会一个分类函数或者分类模型（常称为分类器），该模型能把数据库中的数据项映射到给定类别中的某一类中。分类器的构造方法常见有：统计方法、机器学习、神经网络等。统计方法：贝叶斯法、非参数法机器学习方法：决策树法、规则归纳法神经网络方法：BP算法另外还有粗糙集、支持向量机等。一、分类的基本概念定义：给定一个数据库和一组类，分类问题就是确定一个映射，每个元组被分配到一个类中，一个类包含映射到该类中的所有元组，即。例如：见P115一般，数据分类(Data Classification)分为两个步骤：（1）建立模型，描述预订的数据类集或概念集训练数据集中的每个元组称为训练样本，是从样本中抽取的，训练又分有指导学习和无指导学习。（3） 使用模型进行分类二、基于距离的分类算法1、定义：给定一个数据库和一组类，对于任意的元组如果存在一个，使得则被分配到类中，其中称为相似性。实际中常用距离来表征，距离越近，相似性越大，距离越远，相似性越小。例子P1172、KK最近邻(k-Nearest Neighbor，KNN)分类算法K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。例子P119三、决策树分类决策树是另外一种有效的生成分类器的方法。决策树方法采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同的属性值判断从该节点向下的分支，在决策树的叶节点得到结论。故从决策树的根到叶节点的一条路径对应着一条合取规则。基于决策树的分类算法的一个最大优点就是它在学习过程中不需要使用者了解很多背景知识（同时这也是其最大缺点），只要训练集能够用属性-结论表示出来就能用该算法学习。例如：则可以的决策树如下（算法以后再说）：1、信息论概念 信息论是C.E.Shannon为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。（1）信道模型 一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。信源UU1,U2,Un信宿VV1,V2,Vn信道P(V/U)(2) 在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性。而且这种不确定性是存在于通信之前的。因而又叫做先验不确定性，表示成 信息熵 H（U）在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。如果干扰很小，不会对传递的信息产生任何可察觉的影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。 先验不确定性不能全部被消除，只能部分地消除。在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。通信结束之后，信宿仍然具有一定程度的不确定性。这就是后验不确定性，用条件熵表示H（U/V）。后验不确定性总要小于先验不确定性:H（U/V）H（X） 故信源Y比信源X的平均不确定性要大。(E)平均互信息 定义为：I(U,V)= H（U）-H(U|V) I（U,V）称为U和V之间的平均互信息.它代表接收到符号集V后获得的关于U的信息量。 可见，熵（H（U）、H（U|V）只是平均不确定性的描述。熵差（H（U）-H（U|V）是不确定性的消除，即互信息才是接收端所获得的信息量。对输入端U只有U1，U2两类，互信息的计算公式为: I(U,V)= H（U）-H(U|V)决策树算法步骤：决策树生成和决策树修剪。2、决策树生成算法构造决策树的方法是采用自上而下的递归构造。（1） 以代表训练样本的某个节点开始建树；（2） 如果样本的哦偶在同一类中，则该节点成为树叶，并用该类标记；（3） 否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性。该属性成为该节点的“测试”或“判定”属性。3、ID3算法（1）主算法 从训练集中随机选择一个既含正例又含反例的子集（称为窗口）； 用“建树算法”对当前窗口形成一棵决策树； 对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子； 若存在错判的例子，把它们插入窗口，转2，否则结束。主算法流程用下图表示。其中PE、NE分别表示正例集和反例集，它们共同组成训练集。PE，PE和NE，NE分别表示正例集和反例集的子集。主算法中每迭代循环一次，生成的决策树将会不相同。训练集PE、NE取子集建窗口窗口PE、NE生成决策树测试PE、NE扩展窗口PE=PE+PENE=NE+NE此决策树为最后结果存在错判的PE，NE吗是否(2) 建树算法 对当前例子集合，计算各特征的互信息； 选择互信息最大的特征Ak； 把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集； 对既含正例又含反例的子集，递归调用建树算法； 若子集仅含正例或反例，对应分枝标上P或N，返回调用处。例：NO.属性类别天气气温湿度风1晴热高无风N2晴热高有风N3多云热高无风P4雨适中高无风P5雨冷正常无风P6雨冷正常有风N7多云冷正常有风P8晴适中高无风N9晴冷正常无风P10雨适中正常无风P11晴适中正常有风P12多云适中高有风P13多云热正常无风P14雨适中高有风N解： 信息熵的计算信息熵：类别出现概率：，对9个正例和5个反例有：P（u1）=9/14 P（u2）=5/14H（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit 条件熵计算条件熵：属性A1取值时，类别的条件概率：。A1=天气 取值 v1=晴，v2=多云，v3=雨在A1处取值晴的例子5个，取值多云的例子4 个，取值雨的例子5 个，故： P（v1）=5/14 P（v2）=4/14 P（v3）=5/14取值为晴的5 个例子中有2 个正例、3个反例，故： P（u1/v1）=2/5， P（u2/v1）=3/5同理有：P（u1/v2）=4/4， P（u2/v2）=0 P（u1/v3）=2/5， P（u2/v3）=3/5H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)(4/4)log(4/4) +0)+(5/14)(2/5)log(5/2)+(3/5)log(5/3) = 0.694bit 互信息计算 对 A1=天气 处有： I（天气）=H（U）- H（U|V）= 0.94 - 0.694 = 0.246 bit 类似可得： I（气温）=0.029 bit I（湿度）=0.151 bit I（风）=0.048 bit 建决策树的树根和分枝 ID3算法将选择互信息最大的特征天气作为树根，在14个例子中对天气的3个取值进行分枝，3 个分枝对应3 个子集，分别是: F1=1，2，8，9，11，F2=3，7，12，13，F3=4，5，6，10，14 其中F2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。 递归建树 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征）求互信息. （1）F1中的天气全取晴值，则H（U）=H（U|V），有I（U|V）=0，在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。 （2）在F3中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。这样就得到下图的决策树。4、对ID3的讨论 ID3在选择重要特征时利用了互信息的概念，算法的基础理论清晰，使得算法较简单，是一个很有实用价值的示例学习算法。该算法的计算时间是例子个数、特征个数、结点个数之积的线性函数。有人曾用4761个关于苯的质谱例子作了试验。其中正例2361个，反例2400个，每个例子由500个特征描述，每个特征取值数目为6，得到一棵1514个结点的决策树。对正、反例各100个测试例作了测试，正例判对82个，反例判对80个，总预测正确率81%，效果是令人满意的。缺点：（1）互信息的计算依赖于特征取值的数目较多的特征，这样不太合理。一种简单的办法是对特征进行分解，如上例中，特征取值数目不一样，可以把它们统统化为二值特征，如天气取值晴，多云，雨，可以分解为三个特征；天气晴，天气多云，天气雨。取值都为“是”或“否”，对气温也可做类似的工作。这样就不存在偏向问题了。（2）用互信息作为特征选择量存在一个假设，即训练例子集中的正，反例的比例应与实际问题领域里正、反例比例相同。一般情况不能保证相同，这样计算训练集的互信息就有偏差。（3）ID3在建树时，每个节点仅含一个特征，是一种单变元的算法，特征间的相关性强调不够。虽然它将多个特征用一棵树连在一起，但联系还是松散的。（4）ID3对噪声较为敏感。关于什么是噪声，Quinlan的定义是训练例子中的错误就是噪声。它包含两方面，一是特征值取错，二是类别给错。（5）当训练集增加时，ID3的决策树会随之变化。在建树过程中，各特征的互信息会随例子的增加而改变，从而使决策树也变化。这对渐近学习（即训练例子不断增加）是不方便的。天 气湿 度风晴雨多云高正常有风无风PNNPPID3决策树5、C4.5算法ID3算法在数据挖掘中占有非常重要的地位。但是，在应用中，ID3算法不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。C4.5是在ID3基础上发展起来的决策树生成算法，由J.R.Quinlan在1993年提出。C4.5克服了ID3在应用中存在的不足，主要体现在以下几个方面：(1)用信息增益率来选择属性，它克服了用信息增益选择属性时偏向选择取值多的属性的不足； (2)在树构造过程中或者构造完成之后，进行剪枝；(3)能够完成对连续属性的离散化处理；(4)能够对于不完整数据的处理，例如未知的属性值；(5)C4.5采用的知识表示形式为决策树，并最终可以形成产生式规则。1. 算法设T为数据集，类别集合为C1,C2,Ck，选择一个属性V把T分为多个子集。设V有互不重合的n个取值v1,v2,vn ，则T被分为n个子集T1,T2,Tn ，这里Ti中的所有实例的取值均为vi。 令：|T|为数据集T的例子数，|Ti|为v=vi的例子数，|Cj|= freq(Cj,T)，为Cj类的例子数，|Cjv|是V=vi例子中，具有Cj类别例子数。 则有： （1）类别Cj的发生概率：p(Cj)=|Cj|/|T|= freq(Cj,T)/|T| （2）属性V=vi的发生概率：p(vi) = |Ti|/|T| （3）属性V=vi的例子中，具有类别Cj的条件概率：p(Cj|vi) = |Cjv|/|Ti| Quinlan在ID3中使用信息论中的信息增益（gain）来选择属性，而C4.5采用属性的信息增益率（gain ratio）来选择属性。 (1)类别的信息熵：(2)类别条件熵按照属性V把集合T分割，分割后的类别条件熵为：(3)信息增益（gain），即互信息(4)属性V的信息熵(5)信息增益率C4.5对ID3改进是用信息增益率来选择属性。理论和实验表明，采用“信息增益率”（C4.5方法）比采用“信息增益”（ID3方法）更好，主要是克服了ID3方法选择偏向取值多的属性。六、贝叶斯分类一般来说分类是将未知样本分到预先已知类别的过程。常见的分类模型有神经网络模型、决策树模型、朴素贝叶斯分类模型等。在众多的分类模型中，基于贝叶斯定理的朴素贝叶斯模型应用极其广泛。贝叶斯定理是英国著名数学家托马斯贝叶斯于1763年提出来的。该定理使用统计学理论研究概率推导，即根据已经发生的事件来预测将来可能发生的事件，因此如果过去试验中事件的出现率已知，那么可以计算出未来试验中事件出现的概率。根据未来出现各种事件的概率的大小就可以判断各个事件发生的可能性，故贝叶斯定理可以用来进行分类。与其他模型相比，由于朴素贝叶斯模型基于贝叶斯理论，具有坚实的数学基础和稳定的分类效果，所需估计的参数很少，对缺失数据不太敏感，算法也比较简单，因此用途甚广，如垃圾邮件过滤、人脸识别、图像去噪、入侵检测等。、贝叶斯定理定义：设是两个事件，且，称 (1)为在事件发生的条件下事件发生的概率。由(1)式得的联合概率公式。定义：设S为试验E的样本空间，为E的一组事件，若满足(1) ；(2) ，则称为样本空间S的一个划分。定理：设试验E的样本空间为S，A为E的事件，为样本空间S的一个划分且，则 (2)称为全概率公式。贝叶斯定理：设试验E的样本空间为S，A为E的事件，为样本空间S的一个划分且，则称为贝叶斯公式。、朴素贝叶斯分类器为了详细论述朴素贝叶斯分类过程，我们先了解一些概念。设每个样本数据具有m+1个属性，为条件属性，C为决策属性；表示第个属性的第k个取值；是C的一个取值，表示第j类。另外，用表示集合A中元素的个数。所有样本数据的集合为，则每个数据样本也就是中的元素表示为一个m维特征向量，这里表示属性的取值。是训练集样本的集合。表示样本属于类，那么分类问题就是决定。若有多个类，给定一个未知的数据样本，若有，那么称为的最佳分类。我们称为先验概率，为后验概率，因此求的最佳分类即为求取最大的后验概率。根据贝叶斯定理，有，由于对于所有的类而言是常数，因此只需要最大即可。若类的先验概率未知，则通常假定这些类是等概率的，即，或者用属于类的样本数在总样本数中的比例来近似，即，这种情况下只需对最大化，否则要对最大化。 当训练数据集的属性较多时，的计算量可能比较大，因此朴素贝叶斯分类器基于一个简单的假设：在给定目标值时属性值之间相互条件独立。这样就有。这样，对于给定的训练集D，决策属性包含类，则最佳分类为： (3)或者为： (4)、举例说明 表1为一气候训练集。训练集大小为14个样本，共5个属性，其中4个条件属性，1个决策属性，决策属性的取值只有2种N和P，表示每个样本要么属于P类，要么属于N类。表 1 气候训练集条件属性决策属性outlooktemperaturehumiditywindkind1sunnyhothighweakN2sunnyhothighstrongN3overcasthothighweakP4rainmildhighweakP5raincoolnormalweakP6raincoolnormalstrongN7overcastcoolnormalstrongP8sunnymildhighweakN9sunnycoolnormalweakP10rainmildnormalweakP11sunnymildnormalstrongP12overcastmildhighstrongP13overcasthotnormalweakP14rainmildhighstrongN根据表1，对于测试样本：天气为sunny，气温为hot，湿度为high，风为weak时属于哪一类呢？设测试样本为X=sunny，hot，high，weak，要比较属于两类N和P的概率大小。根据公式(4)，由于对于这两类均一样，因此只要求公式(4)的分子即可。先求类别为N的概率： / 再求类别为P的概率：/显然有。根据后验概率最大原则，X属于N类。此外，可以用Weka软件进行朴素贝叶斯分类。步骤如下：(1)把训练集和测试样本均转换成Weka软