数据挖掘导论-第2章 基本数据挖掘技术

1、第二章基本数据挖掘技术，2.1决策树2.2关联规则2.3聚类分析技术2.4数据挖掘技术的选择，本章的目标，决策树理解决策树的概念C4.5决策树的创建过程，理解重要技术和决策树规则的其他决策树算法。 掌握理解关联规则关联规则的Apriori相关分析流程。 聚类分析掌握k平均算法。 理解数据挖掘技术的选择。 2.1决策树、决策树(Decision Tree ) :从数据生成决策树的机器学习技术。 决策树是数据挖掘中最常用的分类和预测技术，可以建立分类和预测模型。 决策树模型是树结构，树中的每个节点表示要分析的属性，每个节点表示该属性的可能值，并且每个叶节点表示从根节点到叶节点的路径上对象的值。 模

2、型用树的各枝对对象进行分类，叶节点表示的对象值表示决策树分类的结果。 C4.5算法、决策树是常用的指导式学习模式，其中C4.5算法是常用的算法之一。 C4.5提出的基本思想是用“属性-值”形式表示的多个实例组成的数据集，数据集的多个输入属性和输出属性输入属性表示数据集的各个实例的某一面的特征和行为输出属性属于各个实例的唯一类昆兰1965年获得悉尼大学物理硕士学位，1968年获得惠灵顿大学计算机科学博士学位。 1979年，澳大利亚的计算机科学家奎兰提出了ID3的决策树算法，ID3的扩展版C4.5。 C4.5在工业数据挖掘实践中应用非常广泛，被称为机器学习和数据挖掘研究中的标准算法。 分类模型，算

3、法是将数据集的部分或全部实例建模为训练实例的分类模型。 分类模型可以用于对新的未知分类实例进行分类或预测。 在应用模型之前，经常需要进行必要的剪枝和检查。 剪枝用于限制树的规模，提高模型的分类正解率。 检查是评价决策树模型质量的重要环节，也可以检查模型对未知事例进行分类的能力。 给出了数据集t，形式为2.1.1决策树算法的通用过程，C4.5算法的步骤(1)属性-值。 (2)选择最能区分t的实例的输入属性，C4.5使用增益因子来选择该属性。 (3)使用该属性创建树节点，并创建该节点的分支。 各分支是该节点的所有可能值。 (4)使用这些分支，将数据集的实例分类，作为细分的子类。 此外，重复步骤(2

4、)和(3)以上C4.5算法的步骤(接着)、(5)聚合当前子类实例，并且针对数据集的剩馀属性重复(2)、(3)步骤，直到满足下述两个条件中的任一个为止，并且结束该过程并创建叶节点算法的结束条件：此子类的实例满足预定义的标准。 例如，假设所有实例都被划分为输出类，并且被划分为一个输出类的实例达到了某个百分比，则没有剩馀属性。 【例2.1】假定数据集t打篮球，创建了一个决策树，用于预测某个学生是否打篮球。 打篮球决策树，用15例进行训练，输入属性是Weather、Temperature、Courses和Partner的输出属性Play，2.1.2决策树算法的关键技术，三个关键技术(1)数据集的实例(

5、3)检查方法：评价决策树分类准确度的方法。 选择最能区分分支节点的创建、剪枝、检查、1、数据集的实例属性的方法，C4.5的目的是用信息论，即增益率的概念来选择属性的树的层次和节点数最小化，使数据的概况度最大化C4.5选择的基本思想：选择具有最大增益率的属性作为分支节点对事例数据进行分类。 一)信息熵，1948年，克劳德香农提出了“信息熵”的概念。 在信息论中，信息熵是信息不确定度的尺度。 熵越大，信息越难理解，所需信息量越大，能够传输的信息越多。 香农(1916年4月30日2001年2月24日)是美国数学家、信息论的创始人。 香农提出了信息熵的概念，为信息论和数字通信奠定了基础。 信息熵的计算

6、公式，其中H(x )表示随机事件x，熵p表示xi出现的概率xi的随机事件x的所有可能结果n被分类到实例集合可能的类的个数信息熵的计算单位为比特比特，例子1 :一次线圈示例2 :随机事件x有x1、x2和x3三种可能性，其中出现概率分别为1/4、1/2和1/4，并计算x的熵值。 2 )信息增益(Information Gain )和信息增益表示当x取属性xi的值时对降低x的熵作出贡献的大小。 信息增益值越大，越适合于对x进行分类。 使用C4.5信息量和信息增益的概念计算所有属性的增益，计算所有属性的增益率，选择值最大的属性来分割数据实例。 其中，计算属性a的增益率的公式计算在当前数据集合的所有实例

7、上表示的信息量，Gain(A )、Info(I )是在基于属性a的k个可能值对I的实例进行分类之后表示的信息量(k是属性a有k个输出结果)=Info(I)-Info(I，a )、SplitsInfo(A )、和SplitsInfo(A )计算属性a的增益值的标准化，以消除属性选择的偏差。SplitsInfo(A)=-，例如，下表是一个由银行客户概况和部分信用资料数据组成的培训样本集，使用C4.5算法生成决策树。 根据、属性“年龄”对样本集进行分类时，增益速率(age )=0.246/1.577=0.156增益速率(income )=0.029/1.557=0.018增益速率(marriage

8、)=0.15 选择1=0.151 gain ratio (credit _ rate )=0.048/0.985=0.049，age，40，30，30-40，age40的分支节点， 馀数输入属性： income credit _ rategrainratio (income )=(0.971-0.95 )/0.971=0.022 grani ratio (credit _ rate )=(0.971-0 )/0.971=1信息增益最大的属性三个都是Yes类Excellent的例子中的两个都是No类被分配给输出类，因此算法结束。 使用信息增益分裂特性图，计算例2.1的增益率，GainRatio(

9、Weather )，(1) info (I )=(7/15 log2 (7/15 )-8/15 log2 (8/15 ) )=0.9968 (2) info (I weather )=0. 计算=0.9968 (4)增益=信息(I )信息=0. 99680.9118=-0.085 (5)增益速率=-0.085/0.9968=-0.085=0.9968 (2)信息=0.6406 (3)分离信息=2.1493 (4)增益=0.3561 (5)增益速率计算增益率(参数) (1)信息(I )=0.9968 (2)信息(I，参数)=0.9453 (3)分割信息(参数)=0.8366 (4)增益(参数)=

10、0 GainRatio(Courses )，1 .计算数值型数据并排序2 .把两个特征之间的中点作为可能的分裂点，把数据集分成两个部分，计算每个可能的分裂点的信息增益3 .把最大的分裂点作为这个特征的最佳分裂点， 选择Courses 4和4的分裂点的信息增益(1)Info(I)=0.9968 (2)Info(I， courses=0. 9118 (3) splits info (courses )=0.9968 (4) gain (courses )=0.085 (5) gain ratio (courses )=0.085， Courses5和5分割点的信息增益为： (1)Info(I)=0

11、.9968 (2)Info(I，courses )=0. 5875 (3) splits info (courses )=0. 918 (4) gain (courses )=0. 4093Courses属性5的分支继续分裂，子类继续选择10个记录，其馀3个属性weather、Temperature、Partner中信息增益率最大的节点作为分支节点，完全决策树，图2.4 Courses表示根节点的完全决定【例2.2】使用表2.1所示的数据集t，使用Weka软件，应用C4.5算法创建决策树，并预测一个学生是否打篮球。使用Weka软件，C4.5算法(称为J48 )、2、决策树的剪枝、剪枝：为了控制

12、决策树的规模，优化决策树的剪枝的方法。 剪枝是事先制定停止基准，某枝满足停止基准时，停止该枝的生长进行剪枝。 决策树完全成长后，根据一定的规则减去决策树中不典型的叶节点和枝，【例2.3】使用来自UCI的creditscreendatabase数据集，应用Weka的J48(C4.5 )算法，生成2个决策树方法和结果，图2.11提供了“未被剪枝”，图2.12提供了被剪枝的决策树，2.13未被剪枝的决策树，3，决策树检查，Weka提供了4种检查方法(1)使用训练集的实例检查。 (2)supplied test Set :使用另外提供的检查组实例进行检查时，必须单击set按钮选择检查中使用的数据集文件

13、。 (3)cross-validation :使用交叉验证验证分类器，将使用的折射率输入Folds文本框中。 (4)百分比检查。 以一定比例从数据集检索数据的一部分，用作检查组的实例，并且根据这些实例中分类器的预测效果来检查分类器的质量。 取出的数据量由“%”栏的值决定。 2.1.3决策树规则、决策树的各路径使用生成式规则来解释，决策树整体映射到规则的集合。 courses5|weather=sunny : yes (5.0 )|weather=rain : no (5.0/2.0 ) courses 5: no (5.0 )以上Weka生成的规则是三个生成公式规则(1) if courses

14、5 and weather=sunnythenplay=是正确率：5/5=100%垄断率：5/7=71.4 % (2) if courses5 and weather=rainthenplay=否正确率：3/5=ifcourses5thenplay=no正解率：5/5=100%霸权率：5/8=62.5%、2.1.4其他决策树算法、ID3算法： C4.5的前身，j .罗斯伊朗在1986年提交。 cart (classificationandregressedtree，分类回归树)，1984年莱奥布莱特曼等人提出。 CHAID决策树算法，戈登v.kass在1980年提出的。 2.1.5决策树的总结

15、，优点(1)容易理解和解释，可以映射到更有魅力的一组生成式规则中。 (2)没有必要事先假定数据的性质。 (3)可以使用数值型数据和分类型数据的数据集构筑模型。 限制(1)输出属性必须是分类类型，输出属性必须是一个。 (2)决策树算法不稳定。 (3)用数值型数据集制作的树很复杂。 上课练习，根据下表的信息，利用C4.5算法生成决策树，参考答案，2.2关联规则，相关分析是发现事物间相关关系的分析过程。 典型的应用程序-购物车分析会确定客户可以在一次购物中一起购买的商品，发现购物车中不同商品之间的联系，分析客户的购买习惯，并发现购买行为之间的关联。 关联规则：表示关联关系的一系列特别规则，2.2.1关联规则的概要，关联规则的一般表示是包含性的规则形式： XY。 x是被称为关联规则的前提条件或引导条件y是关联规则的结果或后续关联规则与分类模型的生成式规则不同(1)在某一关联规则中以前提条件出现的属性出现在下一个关联规则的结果中。 (2)传统分类的生成规则的结果中只有一个属性，但关联规则的结果中可以包含一个或多个属性。【例2.4】根据顾客的实际购买行为数据，分析顾客在网上购买书、运动鞋、耳机、DVD和果汁五种商品时，是否与购买行为有关。 【例2.4】相关分析的结果，(1)顾客买了运动鞋的话，他们也买了Earphone (耳机)。