(本科）第7章数据挖掘基本算法教学ppt课件.ppt

(本科）第7章 数据挖掘基本算法教学ppt课件LOGO第七章第七章 数据挖掘基本算法数据挖掘基本算法 东北财经大学电子商务学院东北财经大学电子商务学院第七章第七章 数据挖掘基本算法数据挖掘基本算法 7.17.1 数据挖掘基本分析方法数据挖掘基本分析方法 17.2 7.2 关联分析关联分析 27.37.3 序列模式分析序列模式分析37.47.4 分类分析分类分析 4东北财经大学电子商务学院东北财经大学电子商务学院7.57.5 聚类分析聚类分析57.1 7.1 数据挖掘基本分析方法数据挖掘基本分析方法根据不同的标准，数据挖掘系统可以分类如下： 根据挖掘的数据库类型分类 根据数据模型分类 ：有关系的、事务的、对象-关系的或数据仓库的数据挖掘系统；根据所处理的数据的特定类型： 空间的、时间序列的、文本的、流数据的、多媒体的 根据挖掘的知识类型分类 （数据挖掘的功能分类 ） 特征化、区分、关联和相关分析、分类、预测、聚类、孤立点分析 根据所用的技术分类 根据用户交互程度 ：自动系统、交互探查系统、查询驱动系统； 根据数据分析方法 ：面向数据库或数据仓库的技术、机器学习、统计学、可视化、模式识别、神经网络 根据应用分类 有些数据挖掘系统特别适合金融、电信、DNA、股票市场、E-mail等等 7.1 7.1 数据挖掘基本分析方法数据挖掘基本分析方法 无论采用哪几种技术来完成任务，从功能上可以将数据挖掘的分析方法划分为以下四种(根据IBM的划分方法)： 关联分析：挖掘隐藏在数据间的相互关系 1序列模式分析 ：分析数据间的前后序列关系 2分类分析：为一个事件或对象归类 3聚类分析：把没有分类的记录合理地划分成若干类47.2 7.2 关联分析关联分析 交易数据库又称事务数据库，一个事务数据库中关联规则挖掘的基本概念描述如下： 定义定义4定义定义3定义定义2定义定义1设I=i1,i2,im是m个不同项的集合。D是事务数据库的集合，每个事务T是一些项的集合，T包含在I中，即T I ，并且每个事务可以用唯一的标识符TID来标识。 设A为I中某些项的集合，简称为项集。如果A T，则称事务T包含A。 关联规则表示为A B的蕴涵式，其中A I，B I，并且AB= 。支持度表示规则出现的频度，等于事务集中同时包括A和B的百分比；置信度表示规则的强度，指D中包含了A的事务，同时也包含B的百分比。在进行关联规则挖掘时，要求用户预先设定支持度和置信度阈值，即在挖掘过程中只产生满足这两个阈值要求的关联规则，对于这样的支持度和置信度通常分别称为最小支持度和最小置信度。 7.2.1 7.2.1 基本概念基本概念 7.2 7.2 关联分析关联分析定义定义8定义定义7定义定义6定义定义5D中包含的事务数表示为|D|，A中包含的项数表示为|A|。 项集A在D中出现的频率，称为A在D中的支持数（support count），简记为count，count=s|D|。把支持数阈值定义为最小支持数（minimum support count），简记为min_count 对于项集A，如果A中包含有k个项，则A称为k-项集。若项集A的支持度不小于最小支持度，则称A为频繁项集。若某一项m满足最小支持度要求，则称m为频繁项，所有频繁项的集合称为频繁1-项集，记为L1；满足最小支持度要求的k-项集称为频繁k-项集，所有频繁k-项集的集合记为Lk。 Lk通过Lk-l与自己连接产生的集合称为候选k-项集，记作Ck。 7.2.1 7.2.1 基本概念基本概念 7.2 7.2 关联分析关联分析TID购买的项2000 A,B,C1000A,C4000A,D5000B,E,F表7-1任务相关数据D【例7.1】 表7-1所示的任务相关数据D是数据库事务的集合，假设最小支持度为50%，最小置信度为50%， 则有如下关联规则：A C(50%，66.6%)，因为P（AC）=50%，P（AC）/P（A）=50%/75%=66.6% C A(50%，100%)，因为P（CA）=50%，P（CA）/P（C）=50%/50%=100%7.2.1 7.2.1 基本概念基本概念 7.2 7.2 关联分析关联分析7.2.2 7.2.2 关联规则分类关联规则分类 可以根据以下标准对这些关联规则进行分类：1) 根据关联规则所处理的变量值来进行分类 （1）如果规则考虑的关联是项的存在或者不存在，那么这种关联规则就是一个布尔关联规则。 （2）如果描述的是量化的项或属性之间的关联，则该规则是量化型的关联规则。2) 根据规则中涉及到的数据的维数来分类 （1）在单维的关联规则中，只涉及到数据的一个维，那么它就是一个单维关联规则。 （2）在多维的关联规则中，要处理的数据将会涉及多个维，那么它就是一个多维关联规则。7.2 7.2 关联分析关联分析7.2.2 7.2.2 关联规则分类关联规则分类 3) 根据规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 （1）单层的关联规则：所有的变量仅涉及单一层次的项或属性。 （2）多层的关联规则：变量涉及不同抽象层次的项或属性。4)根据所挖掘的模式类型分类 （1）频繁项集挖掘：从事务或关系数据集挖掘频繁项集（项的集合）。 （2）序列模式挖掘：从序列数据集中搜索频繁子序列，其中序列记录了事件的次序。7.2 7.2 关联分析关联分析7.2.3 7.2.3 关联规则的挖掘步骤关联规则的挖掘步骤 整个挖掘过程可分解为以下两步：第一步：发现所有的事务支持度大于最小支持度的项集。一个项集的支持度是指包含该项集的事务数目。具有最小支持度的项集称为频繁项集，其他均为非频繁项集。即找出所有那些支持度大于事先给定的支持度阈值的项集。第二步：在找出频繁项集的基础上产生强关联规则。即产生那些支持度和置信度分别大于或等于事先给定的支持度阈值和置信度阈值的关联规则。7.2 7.2 关联分析关联分析7.2.4 Apriori7.2.4 Apriori算法算法 1 1）AprioriApriori算法算法 Apriori算法的原理： 首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1-项集的集合，该集合记作L1。然后，L1用于找频繁2-项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k-项集。 Apriori算法利用了以下两个重要的性质用来压缩搜索空间： Apriori性质1：若X为频繁项集，则X的所有子集都是频繁项集。 Apriori性质2：若X为非频繁项集，则X的所有超集均为非频繁项集。 7.2 7.2 关联分析关联分析7.2.4 Apriori7.2.4 Apriori算法算法 2 2）AprioriApriori算法的步骤算法的步骤 在Apriori算法中有两个关键的步骤：一是候选项集的生成，采用拼接和剪枝的方法，即由频繁k-项集连接生成候选(k+1)-项集，然后再根据候选k-项集中非频繁的项集来剪枝候选(k+1)-项集。二是候选项集的计数，采用hash树结构，把每个事务中所包含的k维项集存储到hash树中，然后对于每个候选项集查找该树结构，如果某个候选项集包含在树中，则对其进行计数。7.2 7.2 关联分析关联分析7.2.4 Apriori7.2.4 Apriori算法算法 【例7.2】 设事务数据库D如表7-2所示，D中包含9个事务，即|D|=9，最小支持数min_count=2，即最小支持度min_sup=2/9=22%。挖掘频繁项集的具体过程如下所述：表7-2 事务数据ID购买商品T1A,B,ET2B,DT3B,CT4A,B,DT5A,CT6B,CT7A,CT8A,B,C,ET9A,B,C7.2 7.2 关联关联分析分析C1L1L2L3C2C2C3C3项集 支持数 A,B,C 2A,B,E 2项集 支持数A,B,C 2A,B,E 2项集A,B,CA,B,C项集A,BA,CA,DA,EB,CB,DB,EC,DC,ED,E项集 支持数A,B 4A,C 4A,D 1A,E 2B,C 4B,D 2B,E 2C,D 0C,E 1D,E 0项集 支持数A,B 4A,C 4A,E 2B,C 4B,D 2B,E 2项集 支持数 A 6 B 7 C 6 D 2 E 2 项集 支持数 A 6 B 7 C 6 D 2 E 2扫描D，对每个项进行计数取 出 计 数大 于 最 小支 持 数 的项由L1产生C2扫描D，对C2中的项集进行计数取出C2中计数大于最小支持数的项集扫描D，对C3中的项集进行计数取出C3中计数大于最小支持数的项集由L2产生C37.2.4 Apriori算法算法 图7-1 Apriori算法的挖掘过程7.2 7.2 关联分析关联分析（1）发现所有的事务支持度大于最小支持度的项集。（2）产生强关联规则 在找到了事务数据库中的所有频繁项集后，利用这些频繁项集可以产生关联规则，产生关联规则的步骤如下： 对于每个频繁项集L，产生L的所有非空子集。 对于L的每个非空子集m，如果support(L)/support(m)min_conf，则输出规则“m (L-m)”。 例如，在上例中产生的频繁项集LA,B,E，L的非空子集有A,B、A,E、B,E、A、B和E，则运用上述产生关联规则的方法可以得到以下关联规则： A B E confidence=(2/9)/(4/9)=0.5 A E B confidence=(2/9)/(2/9)=1 B E A confidence=(2/9)/(2/9)=1 A B E confidence=(2/9)/(6/9)=0.33 B A E confidence=(2/9)/(7/9)=0.29 E A B confidence=(2/9)/(2/9)=17.2.4 Apriori算法算法 7.2 7.2 关联分析关联分析3 3）AprioriApriori算法中存在的两个问题算法中存在的两个问题 由以上的分析可以看出，在许多情况下，Apriori算法大幅度地压缩了侯选项集的大小，并且导致很好的性能。但该算法中存在的两个问题，在有些情况下不能忽视： （1）该算法在计算的过程中需要产生大量的候选项集。 （2）该算法需要对数据库进行多次扫描，并通过模式匹配检查候选项集。7.2.4 Apriori算法算法 7.2 7.2 关联分析关联分析7.2.5 Apriori算法的几种优化方法算法的几种优化方法 为了减小Apriori算法中存在的问题所带来的影响，提高Apriori算法的执行性能，许多学者提出了一些优化的算法。通常把这些在Apriori基础上优化的算法称为类Apriori算法。1 1）AprioriApriori算法几种典型的改进方法算法几种典型的改进方法 （1）基于散列的优化方法（散列项集到对应的桶中） （2）基于事务压缩的优化方法（压缩未来迭代扫描的事务数） （3）基于划分的优化方法（为寻找候选项集划分数据） （4）基于抽样的优化方法（对给定数据的子集挖掘） （5）基于动态项集计数的优化方法（在扫描的不同点添加候选项集）2 2）频繁模式增长）频繁模式增长7.2 7.2 关联分析关联分析3 3）关联分析的应用）关联分析的应用 关联分析的研究近年来发展迅速，市场前景十分广阔。近年来随着数据库和网络技术的广泛应用，加上使用先进的自动数据生成和采集工具，人们所拥有的数据量急剧增加，使关联分析在市场营销、零售等行业已得到了比较广泛的应用。7.2.5 Apriori算法的几种优化方法算法的几种优化方法 7.2 7.2 关联分析关联分析4 4）关联分析的发展趋势）关联分析的发展趋势 7.2.5 Apriori算法的几种优化方法算法的几种优化方法 2.关联规则挖掘算法 的交互性4.关联规则挖掘技术与其它技术的融合1. 关联规则的兴趣度关联规则的兴趣度3.关联规则算法挖掘效率的提高7.3 7.3 序列模式分析序列模式分析给定一个序列集，每一个序列由项集构成，然后给定由用户确定的最小支持度阈值，序列模式挖掘就是发现所有出现频率不小于给定的最小支持度的频繁子序列。定义定义4定义定义3定义定义2定义定义1项集：项集：各个项(item)组成的集合。集合I=il，i2，.，im，其中每个ik（1km）是一个项。 序列：不同项集的有序排列。序列S可以表示为S=s1，s2， sn。其中，sk(1kn)为项集，也称为序列S的元素。 序列长度：序列长度：一个序列包含的所有项目的个数，长度为1的序列记为1-序列。 序列的包含：序列的包含：设存在两个序列A，B。其中：A=a1，a2，am，B=b1， b2，bn。如果存在整数1i1i2imn，使得a1 bi1，a2 bi2，am bim，则称序列A是B的子序列，又称B序列包含A序列，记为A B。 7.3.1 7.3.1 基本概念基本概念 1 1）序列模式相关概念）序列模式相关概念7.3 7.3 序列模式分析序列模式分析定义定义8定义定义7定义定义6定义定义5序列数据库：序列数据库：把所有的数据按时间进行排列，将得到一个序列，记作itemset（Tl）， itemset（T2），.，itemset（Tn），这里Ti（1i_n）是第i次交易时间，itemset（Ti）为该次交易的项集。由全部序列组成的数据库称为序列数据库，记作SDB。 支持数：支持数：序列A在序列数据库SDB的支持数为序列数据库中包含序列A的序列个数。序列的支持度：序列的支持度：指序列数据库中支持序列A的序列数(也称A的支持数)与SDB中总序列数之比。序列的支持度是一个预先设定的阈值。频繁序列：频繁序列：给定最小支持度阈值，如果序列A在序列数据库中的支持数不低于该阈值，则称序列A为频繁序列。 7.3.1 7.3.1 基本概念基本概念 定义定义10定义定义9最大的序列模式：最大的序列模式：在一个序列集中如果序列S不包含于任何其他序列中，则称序列S为最大的。 序列模式挖掘：序列模式挖掘：给定一个序列的集合，其中每个序列都由事件（或元素）的列表组成，而每个事件都由一个项集组成，给定用户指定的最小支持度阈值，序列模式挖掘找出所有的频繁子序列。定义定义107.3 7.3 序列模式分析序列模式分析 其中，序列a(bc)df是序列1的子序列，因为前者的事件都是序列1的每个事件的子集，而且保持了事件的顺序。 对于A=(ab)c，子序列A被序列1和序列3包含，因此A的支持度为2，这满足最小的支持度。因此，A是频繁的，所以把它叫做序列模式。它是一个3模式，因为它是一个长度为3的序列模式。还有其他的序列模式如B=(bc)a等等，子序列B被序列1和序列2包含，因此B的支持度为2，满足最小的支持度。7.3.1 7.3.1 基本概念基本概念 2 2）序列模式应用举例）序列模式应用举例【例7.3】 设序列数据库如表7-4所示，并设用户指定的最小支持度min_support=2。表7-4 序列数据库 序列ID序列1a(abc)(ac)d(cf)2(ad)c(bc)(ae)3(ef)(ab)(df)cb4eg(af)cbc7.3 7.3 序列模式分析序列模式分析序列模式的挖掘算法从整体上可以被分为两大类：一是基于Apriori特性的、逐层的发现方法，如AprioriAll、GSP和SPADE算法等；二是基于投影的模式增长方法，如FreeSpan和PrefixSpan等。这些方法的共同之处是利用用户给定的最小支持度阈值，基于Apriori启发式搜索机制，即，非频繁模式的超模式一定是非频繁的；频繁模式的子模式一定是频繁的，以确保产生正确、完全的序列模式集合。7.3.2 7.3.2 经典的序列模式挖掘算法分类经典的序列模式挖掘算法分类 频繁项集阶段 变换阶段 1排序阶段 此阶段将挖掘所有的频繁项集，将挖掘到的所有频繁项集映射至一个连续整数的集合变换方法为在一个变换后的顾客序列中，每个交易被它所包含的全部频繁项集的集合所代替最大序列阶段 序列阶段 若最终目的是要挖掘所有的最大频繁序列，算法将包含最大序列阶段。一旦挖掘了全部频繁序列的集合乙，再挖掘最大序列 将交易数据库以Cid为主键，Tid为次键排序，得到顾客序列数据库 7.3 7.3 序列模式分析序列模式分析 AprioriAll算法将序列的长度定义为序列中包含的项集的数量，将序列模式挖掘的过程分为以下五个阶段：给定数据序列d和候选序列集C，需要找到C中被d包含的全部候选序列 7.3.3 AprioriAll7.3.3 AprioriAll算法算法 【例7.4】给出一个客户序列组成的数据库如图72所示，假如最小支持度为40%，那么在频繁项集阶段可以得到频繁1-序列，之后应用AprioriAll算法可以逐步演变成最终的频繁序列集。图72给出了整个过程：7.3.3 AprioriAll7.3.3 AprioriAll算法算法 7.3 7.3 序列模式分析序列模式分析图图7-2第一次扫描数据库时，找到所有的频繁项，也就是具有最小支持度的项。每项产生由其本身组成的1事件频繁序列。 从序列模式的种子集前次扫描得到的序列模式开始扫描，每个候选序列比产生它的种子序列模式多包含一个项。扫描一遍数据库，得到每个候选k序列的支持度。Ck中支持度至少是min_sup的候选集形成所有频繁k序列的集合Lk。然后这个集合成为下一遍扫描的种子集。 7.3 7.3 序列模式分析序列模式分析 1 1）GSPGSP算法步骤算法步骤7.3.4 GSP7.3.4 GSP算法算法4当一遍扫描不能产生新的序列模式或新的候选序列时，算法终止。 2 2）实例解释）实例解释7.3.4 GSP7.3.4 GSP算法算法7.3 7.3 序列模式分析序列模式分析【例7.5】假设给定表75的序列数据库S，min_sup=2。表75 序列数据序列ID序列1a(abc)(ac)d(cf)2(ad)c(bc)(ae)3(ef)(ab)(df)cb4eg(af)cbc（1）第一次扫描时(k=1)，GSP收集每项的支持度。候选1序列的集合是：a：4，b：4，c：4，d：3，e：3，f：3，g：1。（2）序列g的支持度为1，是唯一不满足最小支持度的序列。过滤掉它，得到第一个种子集L1=a,b,c,d,e,f。该集合中的每个元素代表一个1事件序列模式。（3）从上一遍扫描发现的种子集开始，进行扫描，并使用它产生新的候选序列，它们都是潜在频繁的。用L1作种子集，这6个长度为1的序列模式产生66+（65）/2=51个长度为2的候选序列的集合C2=aa,ab,af,ba,bb, , ff,（ab）（ac）, , （ef）。 1 1）SPADESPADE算法算法7.3.5 SPADE7.3.5 SPADE算法算法7.3 7.3 序列模式分析序列模式分析 SPADE算法 （Sequential Pattern Discovery using Equivalence Classes）利用组合属性和基于格的搜索技术进行序列挖掘，并且允许在挖掘过程中加上一定的限制。 SPADE的主要特征包括：数据库的布局是垂直ID列表格式的数据库，搜索空间被分解为小的片断（子格），每个片断在内存中都能够独立处理，使得数据库只需被扫描三次或者对数据预处理之后只需扫描一次。2 2）搜索序列模式的策略：）搜索序列模式的策略： 宽度优先搜索：每个等价类的格都使用自底向上的方式进行处理，在处理每一层的所有子类之前该层必需处理完毕。 深度优先搜索：每条路径的所有等价类都处理完之后才能处理下一条路径。第二步计算频繁2-序列。可以通过两种方式进行，一个是对数据进行预处理并收集所有大于用户定义的最低边界2-序列，另一个是将数据进行一次从垂直到水平的转换。 第三步将2-序列分解成基于前缀的父等价类，在等价类中进行宽度优先搜索或者深度优先搜索。7.3 7.3 序列模式分析序列模式分析第四步列举出其它的所有频繁序列 。7.3.5 SPADE7.3.5 SPADE算法算法第一步扫描数据库计算出所有的频繁1-序列。 第一第一步步7.3.5 SPADE7.3.5 SPADE算法算法7.3 7.3 序列模式分析序列模式分析【例7.6】如图73所示的垂直格式数据布局：表(a) Input-sequences database注：SID：Sequence ID TID ：Time IDSequence IdTimeItems110CD115ABC120ABF125ACDF215ABF220E310ABF410 DGH 420BF 425AGH表(b) ID-lists for the itemsABDFSIDTIDSIDTIDSIDTIDSIDTID115115110120120120125125125215410215215310310310420420425注：SID：Sequence ID TID ：Time ID图73垂直格式数据布局D ADBDFSIDTIDSIDTIDSIDTID115115120120120125125420420215510425DBADBFSIDTIDSIDTID120120125420425(a)Intersect D and A.D and B.D and F(b)Intersect DB and DA, DB and DF(c)Intersect DBAand DBFDBFASIDTID125425图74 利用ID-LIST表连接进行支持度计算 7.3 7.3 序列模式分析序列模式分析7.3.5 SPADE7.3.5 SPADE算法算法7.3.6 PrefixSpan7.3.6 PrefixSpan算法算法 7.3 7.3 序列模式分析序列模式分析 1)1)相关定义相关定义7.3.6 PrefixSpan7.3.6 PrefixSpan算法算法 7.3 7.3 序列模式分析序列模式分析 【例7.7】表76为序列数据库，设最小支持数为2。 表76 序列数据库顾客号顾客序列1(C)(H)2(AB)(CH)(DFG)(H)3(CEG)4(C)(DGH)(H)5(H)7.3.6 PrefixSpan7.3.6 PrefixSpan算法算法 7.3 7.3 序列模式分析序列模式分析PrefixSpan算法过程如下： 步骤1：扫描交易数据库得到全部频繁项目，即频繁1-序列。它们分别是：4，：2，：3，：4。 步骤2：序列模式的完整的集合可被分为四个具有不同前缀的序列模式的子集：以为前缀的；以为前缀的。 步骤3：发现序列模式的子集。通过构造相应的投影库并在其中递归地挖掘可得到序列模式的子集，具体过程如下： 首先发现以为前缀的序列模式，将包含项C的数据序列收集起来，且在这些序列中，只考虑其中以第一次出现的C为前缀的子序列。S中包含的投影构成了-投影库，它包含4个后缀序列。通过对该投影库扫描一次，可发现所有以为前缀的2-序列模式。它们是：2， ：2， ：3。 【例7.7】表76为序列数据库，设最小支持数为2。(续续) 7.3.6 PrefixSpan7.3.6 PrefixSpan算法算法 7.3 7.3 序列模式分析序列模式分析PrefixSpan算法过程如下（续）： 递归地，所有以为前缀的序列模式可分为3个子集：以为前缀的，以为前缀的，以为前缀的。通过构造各自的投影库并在其中递归挖掘可得到各个子集。 相似地，通过构造-、-、-投影库来构造相应的序列模式的子集。 投影数据库和序列模式的完整集合见表77。7.3.6 PrefixSpan7.3.6 PrefixSpan算法算法 7.3 7.3 序列模式分析序列模式分析表77 投影数据库和序列模式前缀投影(后缀数据库)序列模式 ,7.3 7.3 序列模式分析序列模式分析序列模式挖掘的应用：商店销售帮助商家分析顾客行为，更高地使用货架空间从而方便顾客。股票金融找出合理的经济行为联动杠杆模式。软件工程主要用于分析设计模式和编码模式，也可用于软件可用性测试技术中。生物领域从DNA序列中推断出蛋白质和其它生物重大结构的不同特征。同时，也应用于分子序列分析、蛋白质结构预测、基因映射、生化建模及药物研制等方面。Web挖掘对用户访问模式进行有效预测，帮助网站了解用户习惯，从而构建更加友好方便的网站结构。 序列模式挖掘的发展趋势： 研究的方向主要集中在：如何进一步提高算法效率；如何拓展序列模式挖掘，多维模式挖掘、增式挖掘都是其中的热点。 多维序列模式挖掘是在挖掘序列模式时，除了考虑事件发生的时间属性，也加入了其他与之相关联的维度属性。 所有数据库都是随时间更新的，挖掘的序列数据也在随时间改变，所以增式挖掘在序列模式挖掘上更为重要，它涉及了所有数据挖掘技术。7.3 7.3 序列模式分析序列模式分析 1 1）相关概念）相关概念 7.4 7.4 分类分析分类分析 7.4.1 7.4.1 分类过程分类过程 分类分析的分类分析的相关概念相关概念分类：分类：给定一个数据库给定一个数据库D=t1，t2， ，tn和一和一组类组类C=C1，C2， ，Cm，分类问题是去确定，分类问题是去确定一个映射一个映射f：DC，每个，每个元组元组ti被分配到一个类中。被分配到一个类中。一个类一个类Cj包含映射到该类包含映射到该类中的所有元组，即中的所有元组，即Cj=ti f(ti)=Cj，1in，且且tiD。 训练数据集：训练数据集：对于分类，对于分类，数据元组也称为样本、实数据元组也称为样本、实例或对象。为建立模型而例或对象。为建立模型而被分析的数据元组形成训被分析的数据元组形成训练数据集。训练数据集中练数据集。训练数据集中的单个元组称为训练样本，的单个元组称为训练样本，并随机的由样本集中选取。并随机的由样本集中选取。每个训练样本还有一个特每个训练样本还有一个特定的类标签与之对应。定的类标签与之对应。 7.4 7.4 分类分析分类分析 7.4.1 7.4.1 分类过程分类过程 2 2）数据分类的过程）数据分类的过程建立一个描述已知数据集类别或概念的模型建立一个描述已知数据集类别或概念的模型 利用所获得的模型进行分类操作利用所获得的模型进行分类操作 7.4 7.4 分类分析分类分析 7.4.1 7.4.1 分类过程分类过程 【例7.8】给定一个顾客信用信息的数据库，可以根据他们的信誉度（优良或相当好）来识别顾客。首先需要学习分类规则，之后通过分析现有顾客数据学习得到的分类规则可以用来预测新的或未来顾客的信誉度。图75给给出了数据分类过程。 7.4 7.4 分类分析分类分析 7.4.1 7.4.1 分类过程分类过程 图75显示了分类的两个基本过程：（a）训练。用分类算法分析训练数据，这里，类标号属性是credit_rating，学习模型或分类法以分类规则形式提供。（b）使用。利用测试来评估分类规则的准确率，如果准确率是可以接受的，则规则可用于新的数据元组分类，或者对未分类的数据进行标识。图75数据分类过程 1 1）分类数据预处理）分类数据预处理7.4 7.4 分类分析分类分析 7.4.2 7.4.2 分类的相关问题分类的相关问题 法律地位的确立法律地位的确立 （1）数据清理）数据清理可采用平滑技术消除或减少噪声数据；对于空缺值，可用该属性最常出现的值，或根据统计，用最可能的值代替。 （3）数据变换）数据变换数据可以概化到较高层的概念。数据也可以按某种规则进行规范化处理等。分类数据预处理 （2）相关性分析）相关性分析 数据中的许多属性可能与分类任务不相关。可以进行相关分析，删除学习过程中不相关的或冗余的属性。 2 2）分类方法的比较和评估标准）分类方法的比较和评估标准7.4 7.4 分类分析分类分析 7.4.2 7.4.2 分类的相关问题分类的相关问题 预测准确度预测准确度计算复杂度计算复杂度强壮性强壮性 可伸缩性可伸缩性模型简洁度模型简洁度和可理解性和可理解性 分类方法的比较和评估标准分类方法的比较和评估标准 1 1）从采用的技术来看，可以分为以下几大类：）从采用的技术来看，可以分为以下几大类：7.4 7.4 分类分析分类分析 7.4.3 7.4.3 几种典型的分类算法几种典型的分类算法 基于信息论：主要包括决策树系列算法。基于概率统计：主要包括贝叶斯/贝叶斯网络，回归算法。基于要求：主要包括k-最临近分类、基于案例的推理。基于人工智能：主要包括向后传播、遗传算法。 2 2）从算法的执行特点来分，可以归为两大类：）从算法的执行特点来分，可以归为两大类：7.4 7.4 分类分析分类分析 7.4.3 7.4.3 几种典型的分类算法几种典型的分类算法 急切分类：包括决策树、贝叶斯、神经网络等算法。懒散分类：包括最邻近基于案例的推理等算法。 7.4 7.4 分类分析分类分析 7.4.4 7.4.4 决策树系列算法决策树系列算法1 1）D3D3算法算法miiimppsssI1221)(log),(vimjjmjjssIsssAE111,)( AEsssIAGainm),()(2, 1 检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。 通过计算每个属性的信息增益，并比较它们的大小，获得具有最大信息增益的属性。某属性的信息增益按下列方法计算。 设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci (i=1,m)。设Si是类Ci中的样本数。对一个给定的样本分类所需的期望信息由下式给出： 其中pi=Si/s是任意样本属于Ci的概率。注意，对数函数以2为底，其原因是信息用二进制编码。 设属性A具有v个不同值a1, a2, av。可以用属性A将S划分为v个子集S1, S2, , Sv，其中Sj中的样本在属性A上具有相同的值aj（j=1,2,v）。设Sij是子集Sj中类Ci的样本数。由A划分成子集的熵或信息期望由下式给出： 其中Pij=Sij/Sj是Sj中样本属于Ci的概率。在属性A上分枝将获得的信息增益是ID性别年龄收入（万/年）付款方式购买1男40-49L现金否2男40-49L信用卡否3男40-49M现金是4男30-39H现金是5女20-29H现金是6女20-29H信用卡否 1 1）D3D3算法算法7.4 7.4 分类分析分类分析 7.4.4 7.4.4 决策树系列算法决策树系列算法【例7.9】表78为某店的部分交易数据。其中ID为用户的编号，收入为用户的年收入，购买与否是指用户是否在某店购买电器。 表78某店销售数据7女20-29M信用卡是8男30-39L现金否9女20-29L现金是10女30-39H现金是11女30-39L信用卡是12男30-39M信用卡是13女40-49M现金是14男30-39H信用卡否 类标号属性“购买”有两个不同的值“是，否”，即m=2。设C1对应“是”，C2对应“否”，则“是”有9个样本，“否”有5个样本。 首先使用公式计算对给定样本分类所需的期望信息：940. 0145log145149log149)5 , 9(),(2221 IssI接下来，根据公式计算每个属性的信息增益，过程如下：7.4 7.4 分类分析分类分析 7.4.4 7.4.4 决策树系列算法决策树系列算法 7.4 7.4 分类分析分类分析 7.4.4 7.4.4 决策树系列算法决策树系列算法 通过结果发现，属性“收入”具有最高的信息增益。因此，用“收入”标记，创建一个节点，并由每个“收入”属性值引出一个分枝。得到决策树的一部分。对分枝后的数据循环上述工作，得到最终的决策树如图76所示。LMH收入性别付款方式是男女否是信用卡用现金否是图76 决策树 2 2）C4.5C4.5算法算法 7.4 7.4 分类分析分类分析 7.4.4 7.4.4 决策树系列算法决策树系列算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足。 在树构造过程中进行剪枝，可以通过不同剪枝技术以避免树的不平衡。 能够完成对连续属性的离散化处理 能够对不完整数据进行处理 C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 3 3）SLIQSLIQ算法算法 7.4 7.4 分类分析分类分析 7.4.4 7.4.4 决策树系列算法决策树系列算法SLIQ算法对C4.5决策树分类算法的实现方法进行了改进，在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。预排序预排序 针对每个属性的取值，把所有的记录按照从小到大的顺序进行排序，以消除在决策树的每个结点对数据集进行的排序。 广度优先广度优先策略策略 在决策树的每一层只需对每个属性列表扫描一次，就可以为当前决策树中每个叶子结点找到最优分裂标准。 4 4）SPRINTSPRINT算法算法 7.4 7.4 分类分析分类分析 7.4.4 7.4.4 决策树系列算法决策树系列算法SPRINT算法进一步改进了决策树算法的数据结构，去掉了在SLIQ中需要驻留于内存的类别列表，将它的类别列合并到每个属性列表中。 SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进行分裂变得很困难。 1 1）k-k-最邻近分类最邻近分类7.4 7.4 分类分析分类分析 7.4.5 k-7.4.5 k-最邻近分类最邻近分类 当给定一个未知样本时，k-最近邻分类算法搜索模式空间，找出最接近该未知样本的k个训练样本。 两个点X=(x1，x，xn)和Y=(y1，y2，yn)之间的欧几里德距离是：d（X，Y）=n1i2yixi）（未知样本被分配到k个最近邻者中最公共的类，当k=1时，未知样本被指定到模式空间中与之最近邻的训练样本的类。对于有n个记录，m个属性的数据集，此算法的时间复杂度是O(nm)，空间复杂度是O(km)。 1 1）k-k-最邻近分类最邻近分类7.4 7.4 分类分析分类分析 7.4.5 k-7.4.5 k-最邻近分类最邻近分类 假定用于描述苹果的数据元组有三个属性，分别是：大小，颜色，品种，待预测的苹果的大小和颜色已知。算法首先确定预测的样本数据与数据库中的记录的相似性，对于数值型属性的数据元组，通常采用两个样本向量的欧几里德距离来计算，从而得到6个最类似的样本数据，如图77所示。由图77观察：6个相似的样本数据中有4个样本属于“国光”这一类的，因此可得出待预测的这种苹果的品种是“国光”。 2 2）分类挖掘算法的应用）分类挖掘算法的应用 7.4 7.4 分类分析分类分析 7.4.5 k-7.4.5 k-最邻近分类最邻近分类 （1）在入侵检测中的应用（2）在学生资源管理中的应用（3）在银行不良贷款信用风险评估中的应用3 3）分类挖掘算法的发展趋势）分类挖掘算法的发展趋势 （1）降低分类挖掘算法计算复杂度。（2）提高分类挖掘算法的强壮性。 （3）增强分类挖掘算法的可伸缩性。7.5 7.5 聚类分析聚类分析聚类分析聚类分析 聚类是把一组个体按照相似性划分成若干个类别，跟平常说的“物以类聚”相似。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。分类问题和聚类问题根本的不同是：分类问题中，我们知道训练例的分类属性值，而在聚类问题中，就需要我们在训练例中找到这个分类属性值。 本节先介绍了聚类的概念、距离和相似性度量，然后探讨了聚类分析的方法，最后研究了实现这些方法的几种典型算法。 7.5.1 7.5.1 聚类概念聚类概念1 1）聚类的相关概念）聚类的相关概念 一个聚类分析系统的输入是一组样本和一个度量两个样本相似度的标准，输出是数据集的几个类，描述如下： 聚类分析的输入可以用一组有序对（X，s）或（X，d）表示，这里X表示一组样本，s和d分别是度量样本相似度或相异度的标准。聚类系统的输出是一个分区，若C=C1,C2, Ck，其中Ci(i=1,2, ,k)是X的子集，如下表示： C1C2Ck=X CiCj= ，ij C中的成员C1，C2，Ck叫做类，每一个类都是通过一些特征描述的，通常有如下几种表示方式： 通过类的中心或类的边界点表示一个类。 使用聚类树中的结点图形化地表示一个类。 使用样本属性的逻