数据仓库算法总结

1、数据仓库算法总结事务处理环境不适宜DSS应用的原因：(1) 事务处理和分析处理的性能特性不同(2) 数据集成问题历史数据问题(4)数据的综合问题数据仓库数据的四个基本特征：(1) 数据仓库的数据是面向主题的(2) 数据仓库的数据是集成的(3) 数据仓库的数据是不可更新的(4) 数据仓库的数据是随时间不断变化 数据仓库定义：数据仓库是在企业管理和决策中面向主题的、集成的、与时间相关的(时变的)、不可修改的(非易失的)数据集合，用于支持管理决策。支持度若D中的事务包含 A U包含A和和的元组二者)的百分比为s，则称关联规则 A B的支持度为 元组总数s。即：support (A 二 B)=P(A

2、U B)可信度/置信度若D中包含A的事务同时也包含 B的百分比为c ,则称关联规则 A= B的置信度/可信度为c。即： confidence(A二 B)=P(B|A) = support(A U B)/support(A)频繁项集项集的出现频率是包含项集的事物数，简称项集的频率。项集满足最小支持度阈值min sup :如果项集的出现频率大于或等于min sup与D中事物总数的乘积。满足最小支持阈值的项集就称为频繁项集(或大项集)。频繁k项集的集合记为Lk。定理(Apriori性质)频繁项集的所有非空子集都必须也是频繁的。任何非频繁项集的超级一定也是非频繁的Apriori 算法具体做法：对于所研

3、究的事务数据库D，首先找出频繁1-项集的集合，记为 L1 ;再用L1找频繁2-项集的集合L2 ;再用L2找L3如此下去，直到不能找到频繁 k-项集为止。找 每个Lk需要一次数据库扫描。如何实现用Lk-1找Lk.连接步：为找Lk，通过Lk-1与Lk-1连接产生候选k-项集的集合。该候选项集的集合记作Ck，执行Lk-1与Lk-1的连接：如果他们前（k-2）个项相同，则可连接。剪枝步：任何非频繁的（k-1）项集都不可能是频繁k-项集的子集。因此，进行剪枝。7TO项2的列表Tim11. 12. J5T20012, 14T30012. 13T40011, 12, 14T50011. 13T600J2.

4、13T70011T80011. 12. 13, 15T90011， 12, 13例1:该例基于某商店的事务 DB。DB中有9个事务, Apriori假定事务中的项按字典次序存放。（1）在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法简单地扫描所有的事务，对每个项的出现次数计 数。扫描D对每个候选计数（2）设最小支持计数为 2,可以确定频繁1-项集 的集合L1。它由具有最小支持度的候选1-项集组成。比较候选支持度计数与最小支持度计数（3）为发现频繁2-项集的集合L2，算法使用LL1（4）扫描D中事务，计算C2中每个候选项集的支持计 数。扫描D,对每 个候选计数项集支持度计数612

5、7何622项集玄持度计敎f/v6何7622产生候支持度汁数4阿134E 14111,阿2 02.踏42/52 13f 140 113r 15114, 150（5 ）确定频繁2-项集的集合C2中的候选2-项集组成。L2，它由具有最小支持度的比较候选支持度计数与最小支持度计数L _支持度计融mm4I1r 134I1r 152t2, 13492r 142I2r 152扫描D,对每 个候选计数项集支持度计数11 r 12, 132H, 12, 152（6）候选3-项集的集合C3的产生如下： 连接：C3 = L2 7 1-2=11,12，11,13 , 11,15 , 12,13 , 12,14 , 1

6、2,15X 11,12，11,13 , 11,15 , 12,13 , 12,14 , 12,15=11,213 ，11,12,15，11,13,15 , 12,13,14，12,13,15 , 12,14,15 利用Apriori性质剪枝：频繁项集的所有子集必须是频繁的。存在候选项集，判断其子集是否频繁。11,12,13的2-项子集是11,12 , 11,13和12,13,它们都是L2的元素。因此保留11,12,13。 11,12,15的2-项子集是11,12 , 11,15和12,15,它们都是L2的元素。因此保留11,12,15。11,13,15的2-项子集是11,13 , 11,15和

7、13,15,13,15不是L2的元素，因而不是频繁的， 由 C3 中删除11,13,15。12,13,14的2-项子集是12,13 , 12,14和13,14,其中13,14不是L2的元素，因而不是频繁 的，由C3中删除12,13,14。12,13,15的2-项子集是12,13 , 12,15和13,15,其中13,15不是L2的元素，因而不是频繁 的，由C3中删除12,13,15。12,14,15的2-项子集是12,14 , 12,15和14,15,其中14,15不是L2的元素，因而不是频繁 的，由C3中删除12,14,15。 这样，剪枝后 C3 = 11,12,13，11,12,15。（7

8、） 扫描D中事务，以确定L3，它由具有最小支持度的C3中的候选3-项集组成。 由L2产生候选C38）算法使用L: L3产生候选4-项集的集合C4。尽管连接产生结果11,12,13,15,这个项集被剪去，因为它的子集 12,13,15不是频繁的。则 C4 =空集,因此算法终止，找出了所有的频繁项集。关联规则的生成：根据上面介绍的关联规则挖掘的两个步骤，在得到了所有频繁项目集后，可以按照下面的步骤生成关联规则：对于每一个频繁项目集I，生成其所有的非空子集；对于 I 的每一个非空子集 X，计算 Co nferen ce(X)，若 Con fide nce(X) mincon fide nee , 则

9、“ x= (I - X) ” 成立。由于规则由频繁项集产生，每个规则都自动满足最小支持度。例2:基于例1的结果，假定数据包含频繁项集I =11 ,12 ,15。可以由I产生哪些关联规则?T1DID列表T10011,12.15T200123T30012,13T40011,123T50011,13TBOO12,13T70011,13T800I1.I2AIST90011,1233如果最小置信度阈值为 70% , 这些是产生的强规则。L (L)的非空子集有11 , 12、11 , 15、I2 , 15、11、12 和15关联规则如下：1112二 15,confidence = 2 4 = 50%111

10、5二 12,confidence 二 2 2 = 100%I2 15二 11,con fide nee = 2 2 二 100%11 = 12I5,confidence = 2 6 = 33%12二 11I5,con fide nee = 2 7 = 29%15二 11I2,confidence 二 2 2 = 100%2、3、6个规则可以作为最终的输出，因为只有那么只有第序列关联规则收集到的数据中常常存在某种顺序关系，通常是基于时间的先后顺序。对于识别动态系统的重要特征，或预测特定事件的未来发生，序列信息将是很有价 值的。对象时间戳事件A11 , 2 , 4A22 , 3A35B11 , 2

11、B22, 3 , 41C11 , 2 1C22, 3 , 4C32, 4 , 5D12D23 , 4D34 , 5每一行记录与一个特定的对象相关联的一些事件在 给定时刻的出现。时间戳不是一个具体的时间，而是一个象征性的时 间，表示时间上的先后次序。将与对象A有关的所有事件按时间戳增序排列就得 到对象 A的一个序列(sequenee)。数据序列(data sequenee)是指与单个数据对象相关 联的事件的有序列表。如表中显示的数据集包含四个数 据序列，对象 A , B, C , D各一个。设D是包含一个或多个数据序列的数据集序列s的支持度是包含s的所有数据序列所占的比例。如果序列s的支持度大于

12、或等于用户给定的最小支持度阈值(minsup)，则称s是一个频繁序列。以前面给定的包含 4个数据序列的数据集为例，序列的支持度等于75%。假定minsup=50%，则至少出现在2个数据序列中的任何序列都是序列模式：minsup=50%序列模式的例子：s=75%，除 D 外s=75%，除 D 外序列合并规则序列S1和序列S2合并，仅当从S1中去掉第一个事件后得到的子序列与从S2中去掉最后一个事件后得到的子序列相同，结果候选是序列S1和序列S2的最后一个事件连接，S2的最后一个事件可以作为最后一个事件合并到S1的最后一个元素中，也可以作为一个不同的元素，这取决于如下条件：如果S2的最后两个事件属于

13、相同的元素，则 是S1的最后一个元素的一部分如果S2的最后两个事件属于不同的元素，则 成为连接到S1的尾部的单独元素序列关联算法的连接和剪枝步骤的例子(其中，每个 事件)S2的最后一个事件在合并后的序列中S2的最后一个事件在合并后的序列中是指一个元素，1，2， 3， 4， 5是指频繁3序列产生候选4序列,候选4序列剪枝对于给定的序列s,t，形如s= t的表达式就是序列关联规则。 序列关联规则s= t的置信度是支持序列s和t的数据序列数与仅支持s的数据序列数之比。例如，= 的置信度为：s()/s()=1样本数据序号属性1属性2111221312422543653744854例3计算簇平均值点，得

14、到新的平均值点为（1.5, 1.5)和(4.5, 3.5) o只凭支持度和可信度阈值未必总能找到符合实际的或有意义的规则，应该在关联规则X=Y的置信度超过某个特定的度量标准时，定义它为有意义。在此引入Lift值（增益）Lift （X 二 Y）=P（Y|X）/P（Y）=P（X U Y）/P（X）*P（Y）Lift=1 ,前项和后项经验独立X与Y实际同时发生的概率大于X与Lift 1,表明前项和后项是正相关的，说明Y独立时同时发生的随机概率Lift1 ,表明前项和后项是负相关的基于划分的聚类方法1、k-means算法（k-平均或k-均值） 首先将所有对象随机分配到k个非空的簇中。 计算每个簇的平均

15、值，并用该平均值代表相应的簇。 根据每个对象与各个簇中心的距离，分配给最近的簇。 然后转第二步，重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函 数才停止。根据所给的数据通过对其实施k-means （设n=8, k=2），其主要执行步骤：第一次迭代：假定随机选择的两个对象，如序号 1和序号3 当作初始点，分别找到离两点最近的对象，并产生两个簇 1 , 2和3 , 4, 5, 6, 7, 8。对于产生的簇分别计算平均值，得到平均值点。对于1 , 2，平均值点为（1.5, 1）;对于3 , 4, 5, 6, 7, 8，平均值点为（3.5, 3）。第二次迭代：通过平均值调整对象的所在的簇，

16、重新聚类，即将所有点按离平均值点（1.5, 1 ）、（ 3.5, 3）最近的原则重新 分配。得到两个新的簇：1 , 2, 3, 4和5 , 6, 7, 8。重新第三次迭代：将所有点按离平均值点（1.5, 1.5）和（4.5, 3.5）最近的原则重新分配，调整对象，簇仍然为1 , 2, 3, 4和5 , 6, 7 8，发现没有出现重新分配，而且准则函数收敛，程序结束。迭代次数平均值平均值产生的新簇新平均值新平均值(簇1)(簇2)(簇1)(簇2)1(1, 1)(1 , 2)1 , 2 , 3 , 4, 5 , 6 , 7 , 8(1.5 , 1)(3.5 , 3)2(1.5, 1)(3.5, 3)

17、1 , 2 , 3 , 4, 5, 6 , 7 , 8(1.5 , 1.5)(4.5 , 3.5)3(1.5, 1.5)(4.5, 3.5)1 , 2 , 3 , 4, 5, 6 , 7 , 8(1.5 , 1.5)(4.5 , 3.5)请思考：4和7,结果与前面会一样吗？有何对于相同的样本数据，若随机选择的两个初始点为序号 结论？2、K-中心点算法1为每个簇随机选择一个代表对象 (中心点)；2剩余的对象根据其与代表对象的距离分配给与其最近的一个簇；3反复地用非代表对象来替换代表对象，以提高聚类的质量，直至找到最合适的中心点。例4假如空间中的五个点 A、E、C、D、E如图1所示，各点之间的距离

18、关系如表 1所示, 根据所给的数据对其运行 PAM算法实现划分聚类(设 k=2 )。样本点间距离如下表所示：第一步 建立阶段：假如从5个对象中随机抽取的 2个中心点为A , B,则样本被划分为A、 C、D和B、E。第二步交换阶段：假定中心点 A、B分别被非中心点C、D、E替换，根据PAM算法需要计算下列代价 TCAC、TCAD、 TCAE、TCBC、TCBD、TCBE。以TCAC为例说明计算过程：a) 当A被C替换以后，A不再是一个中心点，因为 A离B比A离C近，A被分配到B中 心点代表的簇，CAAC=d(A,B)-d(A,A)=1 。b) B是一个中心点，当 A被C替换以后，B不受影响，CB

19、AC=0。c) C原先属于A中心点所在的簇，当A被C替换以后，C是新中心点，符合PAM算法代价 函数的第二种情况 CCAC=d(C,C)-d(C,A)=0-2=-2 。d) D原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是 C,根据PAM算法代价函数的第二种情况CDAC=d(D,C)-d(D,A)=1-2=-1 。e) E原先属于B中心点所在的簇，当A被C替换以后，离E最近的中心仍然是B,根据PAM算法代价函数的第三种情况CEAC=0。因此，TCAC=CAAC+ CBAC+ CBAC+ CDAC+ CEAC=1+0-2-1+0=-2。请计算代价 TCAD、 TCAE、TCBC、

20、TCBD、TCBE。在上述代价计算完毕后，选取一个最小的代价，显然有多种替换可以选择，选择第一个最小代价的替换(也就是 C替换A),根据图(a)所示，样本点被划分为 B、A、E和C、D 两个簇。图(b)和图(c)分别表示了 D替换A , E替换A的情况和相应的代价(b) D 替换 A, TCAD= -2 图替换中心点A图(a)、(b)、(c)分别表示了用 C、D、E替换B的情况和相应的代价。(a) C 替换 B, TCBC=-2(b) D 替换 B, TCBD= -2(c) E 替换 B, TCBE= -2图替换中心点B通过上述计算，已经完成了A、D、E替换中心点B、 不再减小为止。PAM算法

21、的第一次迭代。在下一迭代中，将用其他的非中心点 C，找出具有最小代价的替换。一直重复上述过程，直到代价层次聚类方法1、AGNES 算法例5将下列数据聚为两个簇第1步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为1，合并后1，2点合并为一个簇。第2步：对上一次合并后的簇计算簇间距离，找出距离最近的两个簇进行合并，合并后3，4点成为一簇。第3步：重复第2步的工作，5，6点成为一簇。第4步：重复第2步的工作，7，8点成为一簇。第5步：合并1，2，3，4成为一个包含四个点的簇。第6步：合并5，6 ,7,8，由于合并后簇的数目达到了用户输入的终止条件，程序结束。序号属性

22、1属性2111步骤最近的簇距离最近的两个簇合并后的新簇212111 ， 21，2，3，4，5，6，7，8321213，41，2，3，4，5，6，7，8422315，61，2，3，4，5，6，7，8534417 ， 81，2，3，4，5，6，7，8635511，2，3，41，2, 3，4，5，6，7，8744615，6，7，81，2, 3，4，5，6，7，8结束8452、DIANA算法（典型的分裂聚类方法） 两种测度方法：簇的直径：在一个簇中的任意两个数据点的距离中的最大值。 平均相异度（平均距离）：davg(G,Cj)二例6yCjx y序号属性1属性2111212321422534635744

23、845将下列数据聚为两个簇第i步，找到具有最大直径的簇，对簇中的每个点计算平均相异 度（假定采用是欧式距离）。1 的平均距离：（1 + 1 + 1.414+3.6+4.24+4.47+5）/7=2.96类似地：2的平均距离为 2.526 ；3 的平均距离为2.68 ；4的平均距离为 2.18 ；5的平均距离为 2.18 ；6的平均距离为2.68 ；7 的平均距离为2.526 ； 8的平均距离为2.96。挑出平均相异度最大的点1放到splinter group中，剩余点在 oldparty 中。第2步，在old party里找出到最近的splinter group中的点的距离不大于到old pa

24、rty中最近的点的距离的点，将该点放入splinter group中，该点是2。第3步，重复第2步，splinter group中放入点3。第4步，重复第2步，splinter group中放入点4。第5步，没有在old party中的点放入了 splinter group中且达到终止条件（k=2），程序终止。如果没有到终止条件，应该从分裂好的簇中选一个直径最大的簇继续分裂。步骤具有最大直;径的簇splintergroupOldparty11，2,3,4,5,6,7,812 ,3,4,5,6, 7, 821，2,3,4,5,6,7,81 , 23 ,4,5,6,7, 831，2,3,4,5,6

25、,7,81 , 2,34 ,5,6,7,841，2,3,4,5,6,7,81 , 2,3,45 ,6,7,851，2,3,4,5,6,7,81 , 2,3,45 ,6,7,8终止3、BIRCH (1996)4、CURE算法密度聚类1、DBSCAN对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目 定义1对象的 -临域（EpS近邻）：给定对象在半径内的区域。定义2核心对象：如果一个对象的-临域至少包含最小数目 MinPts个对象，则称该对象为核心对象。例如，在图中， =1cm, MinPts=5 , q是一个核心对象。定义3直接密度可达：给定一个对象集合D，如果p是

26、在q的 -邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。例如，在图中, =1cm, MinPts=5 , q是一个核心对象，对象p从对象q出发是直接密度可达的。图直接密度可达图密度可达定义4密度可达的：如果存在一个对象链图密度相连图噪声p1,p2,，pn, p1=q , pn=p,对 pi D,( 1=i=n ),pi+1是从pi关于和MitPts直接密度可达的，则对象p是从对象q关于和MinPts密度可 达的。例如，在图中， =1cm , MinPts=5 , q是一个核心对象，pl是从q关于和MitPts直接 密度可达，p是从pl关于和MitPts直接密度可达，则对

27、象p从对象q关于和Min Pts密 度可达的 （间接密度可达）。定义5密度相连的：如果对象集合D中存在一个对象0,使得对象p和q是从o关于和MinPts密度可达的，那么对象p和q是关于和MinPts密度相连的。定义6噪声：一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含 在任何簇中的对象被认为是“噪声”。F面给出一个样本事务数据库（见左表），对它实施DBSCAN算法。根据所给的数据通过对其进行MinPts=4 )DBSCAN算法，以下为算法的步骤（设n=12,用户输入 =1 ,样本事务数据库DBSCAN算法执行过程示意歩骤选择的点在屮点的个数通过计算可达点而找到的新簇112无

28、222无333445敷1： 1,蓟4, 5f久他12553已在一个簇q中663无775簇q 2r 6( 7f11S2已在-个簇q中993已在一个簇q中101D4已在个議q中，11112已在一个簇C!中12122已崔个簇匸中聚出的类为1 , 3, 4, 5, 9, 10, 12 , 2 , 6,乙 8 , 11可达步骤选择的点一 一一 - 在中点的个数222无33无n.75打3pfO.11*3中-IX C 个一在 已m63无_T87,A- IT 1 p2E2丄So14叵2中 个一在 已EH中1C 簇 个一在 已点。算法执行过程：第1步，在数据库中选择一点 1,由于在以它为圆心的，以 1 为半径的

29、圆内包含 2个点（小于4）,因此它不是核心点，选 择下一个点。第2步，在数据库中选择一点 2,由于在以它为圆心的，以 1 为半径的圆内包含 2个点，因此它不是核心点，选择下一个 点。第3步，在数据库中选择一点 3,由于在以它为圆心的，以 1 为半径的圆内包含 3个点，因此它不是核心点，选择下一个 点。第4步，在数据库中选择一点 4,由于在以它为圆心的，以 1 为半径的圆内包含 5个点，因此它是核心点，寻找从它出发 可达的点（直接可达 4个，间接可达2个），聚出的新类1， 3，4，5，9，10，12，选择下一个点。第5步，在数据库中选择一点 5,已经在簇1中，选择下一 个点。第6步，在数据库中选

30、择一点 6,由于在以它为圆心的，以 1 为半径的圆内包含 3个点，因此它不是核心点，选择下一个第7步，在数据库中选择一点7,由于在以它为圆心的，以 1为半径的圆内包含 5个点，因2 , 6, 7, 8, 11，选择下一个点。 中，选择下一个点。中，选择下一个点。1中，选择下一个点。2中，选择下一个点。8, 已经在簇29, 已经在簇110, 已经在簇11, 已经在簇第12步，选择12点，已经在簇1此它是核心点，寻找从它出发可达的点，聚出的新类 第8步，在数据库中选择一点 第9步，在数据库中选择一点 第10步，在数据库中选择一点 第11步，在数据库中选择一点 中，由于这已经是最后一点所有点都已处理

31、，程序终止。网格聚类1、STING 算法是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。 高层单元的统计参数可以很容易的从底层单元的计算得到。这些参数包括属性无关的参数 count、属性相关的参数 m （平均值）、s（标准偏差）、min（最小值卜max（最 大值）以及该单元中属性值遵循的分布类型。模型聚类K最近邻居算法（KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类

32、别。“身高”用于计算距离，K=5，对Pat,女,1.6分类。姓名性别身高（米）类别Kristina女1.6矮Jim男2高Maggie女1.9中等Martha女1.88中等Stephanie女1.7矮Bob男1.85中等Kathy女1.6矮Dave男1.7矮Worth男2.2高Steven男2.1高Debbie女1.8中等Todd男1.95中等Kim女1.9中等Amy女1.8中等Wynette女1.75中等女,1.6、 Debbie,女,1.8 、 对第12到14个记录，没变化。1取前K=5个记录：N=Kristina,女,1.6、 Jim,男,2、 Maggie,女,1.9、 Martha,女

33、,1.88和 Stephanie,女,1.7。2对第 6 个记录 d=Bob,男,1.85，得到 N=Kristina,女,1.6、 Bob,男,1.85、 Maggie,女，1.9、 Martha, 女,1.88和 Stephanie,女,1.7。3. 对第 7 个记录 d=Kathy,女,1.6，得到 N=Kristina, 女,1.6、 Bob,男,1.85、 Kathy,女，1.6、 Martha, 女,1.88和 Stephanie,女,1.7。4. 对第 8个记录 d=Dave,男,1.7，得到 N=Kristina,女,1.6、 Bob,男,1.85 、 Kathy,女,1.6、

34、 Dave, 男,1.7和 Stephanie，女,1.7。对第9和10个记录，没变化。5，对第 11 个记录 d=Debbie,女,1.8，得到 N=Kristiina, Kathy,女,1.6、 Dave,男,1.7和 Stephanie,女,1.7。6. 对第 15 个记录 d=Wynette,女,1.75，得到 N=Kristina,女,1.6、Wynette,女,1.75、 Kathy,女,1.6、 Dave,男,1.7 和 Stephanie,女,1.7。7. 最后输出元组是：Kristina,女,1.6、Kathy,女,1.6、Stephanie,女,1.7、Dave,男,1.7

35、和 Wynette,女,1.75。 其中，四个属于矮个、一个属于中等。最终KNN方法认为Pat为矮个。请问：若K=5，Pety，男,1.96的身高应该属于那种类型?ID3算法生成决策树信息增益信息增益是指划分前后进行正确预测所需的信息量之差。即原始分割的熵与划分以后各分割的熵累加得到的总熵之间的差。选择属性的方法：选择具有最大信息增益（熵减少的程度最大）的属性作为当前节点的测试 属性信息增益的计算设S是有s个训练样本数据的集合，类标号属性具有m个不同值，定义 m个不同类Ci（i=1,2，,m）, si是类Ci中的样本数，则对一个给定的训练样本分类所需要的期望信息为：mI S1,S2,Sm -

36、八 pi log 2 Pi其中pi是任意样本属于 Ci的概率，可用si/s来估计设属性A具有v个不同值a1,a2,av，则可用属性 A将S划分为v个子集S1,S2,Sv, Sj中包含的样本在属性 A上具有值aj。如果选择A作为测试属性，则这些子集对应于由包 含集合S的结点生长出来的分枝。设sij是子集Sj中类Ci的样本数，则按照 A划分成子集的熵为：v s 亠亠s .E(A) Y Igj,，Smj)j丄s其中 S!j Smjs为第j个子集的权，等于子集(A值为aj)中的样本数除以 S中的样本数。对于给定的子集Sj，它的信息I(s1j,s2j,smj)可用下式计算mI (sij , S2j ,

37、Smj )為 Pij log 2 ( P ij )i丄亠Pij =|S|是Sj中的样本属于类 Ci的概率由A划分的信息增益为：Gain(A)=l(s1,s2,sm)-E(A)例8一个商场顾客数据库(训练样本集合)ridifceincum.esludentcrwiilratingbuiv-cumpulcr30HighNuFairNo240MediumNoFairYes540Law?sFair畑640LowYes臼cd lentNo7LowYesExcdlettYes&30MediumNdFairNd940MediumYesFairYes1140MediumNoExcd kitNd样本集合的类别属

38、性为：“ buy_computer ”，该属性有两个不 同取值，即yes, no，因此就有两 个不同的类别(m=2)。设C1对应 类 别yes, C2对应类别no。类别C1 包含9个样本，类别 C2包含5个 样本。为了计算每个属性的信息增益，首先利用公式计算出所有(对一个给定样本进行分类所需要) 的信息，具体计算过程如下：-logjlog2 = 0.94接着需要计算每个属性的(信息)熵。假设先从属性“age”开始，根据属性“ age”每个取值在yes类别和no类别中的分布，就可以计算出每个分布所对应的信息。对于 agesi -2-3耳珀罔J = 0*971对于聘?孝0-4；jn=4甩=0HSn

39、） = O虻于 age40u;知二 3s5J =2口石阳）二 Q971然后利用公式计算出若根据属性“ age对样本集合进行划分，所获得对一个数据对象进行分类而需要的信息熵为：545E他e）二心屁）+亍（龄）+（知知）=0金4由此获得利用属性 “ age对样本集合进行划分所获得的信息增益为：6加他0二I（5|尚卜（嘟）二0245类似可得Gain（income）=0.029，Gai n（stude nt）=0.151 ，Gain（credit_rating）=0.048。显然选择属性“ age所获得的信息 增益最大，因此被作为测试属性用 于产生当前分支结点。这个新产生 的结点被标记为“ age；同

40、时根据 属性“age的三个不同取值，产生 三个不同的分支，当前的样本集合 被划分为三个子集，如图所示。in oo mestudentfnsdil_nilingtLklC1Itcreilic nilingdasBiniediumnofairyeslowyesfairyeslowye号no-mediumyesfairyesnwdiumnoexcellentnoC4.5算法信息增益比例：是在信息增益概念基础上发展起来的，一个属性的信息增益比例用下面的公式给出:GainRatio (A)二Gai n(A)SplitI (A)v其中 SplitI (A)八 Pjlog2(Pj)OutlookTemper

41、atureHumidityWindPlayTennisSunnyHot85falseNoSunnyHot90trueNoOvercastHot78falseYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercastCool65trueYesSunnyMild95falseNoSunnyCool70falseYesRainMild80falseYesSunnyMild70trueYesOvercastMild90trueYesOvercastHot75falseYes样本数据d 1(9,5)二 0.9403)计算每个属性的 Ga

42、inRatio :假如以属性A的值为基准对样本进行分割的化，Splitl(A) 就是前面熵的概念。C4.5处理连续值的属性：根据属性的值，对数据集排序；用不同的阈值将数据集动态的进行划分；当输出改变时确定一个阈值；取两个实际值中的中点作为一个阈值；取两个划分，所有样本都在这两个划分中；得到所有可能的阈值、增益及增益比；在每一个属性会变为取两个取值，即小于阈值或大于等于阈值。简单地说，针对属性有连续数值的情况，则在训练集中可以按升序方式排列。如果属性A共有n种取值，则对每个取值vj (j=1 , 2, n),将所有的记录进行划分：一部分小于vj ;另一部分则大于或等于 vj。针对每个vj计算划分

43、对应的增益比率，选择增益率最大的 划分来对属性A进行离散化。1) 首先对Humidity进行属性离散化，针对上面的训练集合，通过检测每个划分而确定最好的 划分在75处，则这个属性的范 围就变为(75)。2) 计算目标属性PlayTennis分 类的期望信息：GainRatio (Outlook) = 0246 =0.156;1.577GainRatio (windy) =0.049;GainRatio (Temperature) =0.0248;GainRatio (Humidity) =0.04834) 选取最大的 Gain Ratio，根据Outlook的取值，得到三个分支。5) 再扩展各

44、分枝节点，得到最终的决策树。 贝叶斯定理设X是类标号未知的数据样本。设H为某种假定，如数据样本X属于某特定的类 C。对于分类问题，我们希望确定P(H|X)，即给定观测数据样本 X，假定H成立的概率。贝叶斯定理给出了如下计算P(H|X)的简单有效的方法P(H |X)二P(X | H )P(H )P(H):是先验概率，或称 H的先验概率。P(X):样本数据被观察的概率。P(X|H)代表假设H成立的情况下，观察到X的概率。P(H|X)是后验概率，或称条件 X下H的后验概率。后验概率P(H|X)比先验概率 P(H)基于更多的信息。P(H)是独立于X的。朴素贝叶斯分类朴素贝叶斯分类就是假定一个属性值对给

45、定类的影响独立于其他属性的值。这一假定称作类条件独立。做此假定是为了简化所需计算，并在此意义下称为“朴素的” 朴素贝叶斯分类的工作过程如下:(1) 每个数据样本用一个n维特征向量X=x1,x2, ,xn表示，分别描述对 n个属性A1 ,A2 ,An样本的n个度量。(2) 假定有m个类C1, C2,，Cm，给定一个未知的数据样本X (即没有类标号)，分类器将预测X属于具有最高后验概率(条件 X下)的类。也就是说，朴素贝叶斯分类将未知则通常假定这些类是等概率的，即 的最大化(P(X|Ci)常被称为给定 大似然假设)。否则，需要最大化的样本分配给类 Ci ( K i wm)当且仅当P(Ci|X) P(Cj|X)，对任意的j=1 , 2,，m, j丰i。 这样，最大化P(Ci|X)。其P(Ci|X)最大的类Ci称为最大后验假定。(3)根据贝叶斯定理：CiP(X|Ci)P(Ci)P(X)由于P(X)对于所有类为常数，只需要 P(X|Ci)*P(Ci)最大即可。如果 Ci类的先验概率未知,P(C1)=P(C2)=- =P(Cm)，因此问题就转换为对 P(X|Ci)Ci时数据X的似然度，而使 P(X|Ci)最大的假设Ci称为最P(X|Ci)*P(Ci)。注意，类的先验概率可以用 P(Ci)=si/s计算，其中si是类Ci中的训练样本数，而s是训练