DataMining分类、聚类概述.pptx

第五章 分类分析;2015/11/6;2015/11/6;分类分析;2015/11/6;2015/11/6;2015/11/6;2015/11/6;分类分析;是否会买计算机？;是否保险欺诈?;分类的应用;分类的定义;是否会买计算机？;简单例子;监督学习与非监督学习;简单例子;分类与预测;Decision trees 决策树 Rough Set 粗糙集 Bayes Classifier 贝叶斯分类 Associative Classification 关联分类 ……;分类的三个阶段;一个完整的分类过程;分类任务;数据划分;模型构造;模型测试/应用;分类分析;基于距离的分类算法; 基于距离分类算法的一般性描述;基于距离的分类方法的直观解释;k-近邻分类算法思想;K-近邻算法描述：;kNN的例子;kNN的例子;K-近邻算法的几个问题;分类分析;;决策树;内部节点：数据集的一个属性 分枝：对应属性的一个分割 叶子节点：表示一个类;决策树;决策树的构造;反 例;决策树算法思想;决策树生成算法;决策树生成过程; 为什么要选择最有分类能力的属性作为决策树当前节点？; 如何选择最有分类能力的属性作为决策树当前节点？ 信息增益、增益指标、GINI指标、…;⑵ 根据当前决策属性取值不同，将训练样本数据集划分为若干子集。; ⑶ 针对上一步得到每一个子集，重复上述过程，直到子集中所有元组都属于同一类，不能再进一步划分为止。;体形;体形;最终生成的决策树;示例1：训练集;天气;决策树建立的关键;决策树分类算法－ID3分类算法;ID3学习算法;类别; 信息增益（Information Gain）衡量属性区分训练样例的能力: 一个属性的信息增益就是由于使用这个属性而导致的熵的降低 属性X相对样例集合S的信息增益定义： ;决策树建立的关键;ID3学习算法;实例序号;实例序号; ;对当前的数据表，建立一个节点N。 如果数据表中的数据都属于同一类，N就是树叶，在树叶上标上所属的那一类。 如果数据表中没有其他属性可以考虑，N也是树叶，按照少数服从多数的原则在树叶上标上所属类别。 否则，根据Information Gain值选出一个最佳属性作为节点N的测试属性A。 节点属性选定以后，对于该属性的每一个值ai： 从N生成一个A=ai的分支， 并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏。 如果分支数据表非空，则运用以上算法从该节点建立子树。 递归上述过程 ;ID3算法举例;ID3算法举例;Outlook;属性”Outlook“的信息增益： 同理通过计算，得Humidity，Temperature，Wind属性的信息增益： 通过比较，选择信息增益最大的属性”Outlook”作为根节点。 ;初步生成的决策树：;Outlook;以outlook=“sunny”对应的节点为例继续划分。 对样本划分的信息熵：;以属性”temperature”为例计算信息增益，有3个属性值hot，mild，cool。;属性“temperature”的信息增益;Outlook;以“outlook=‘Rain’”对应的节点为例继续划分。 对样本划分的信息熵：;以属性“temperature”为例计算信息增益，有2个属性值mild，cool。;属性“temperature”的信息增益 ;最终生成的决策树;属性选择方法;信息增益与增益比率;基尼系数;基尼系数示例;按照“温度”分裂，得到三个子集{T1, T2 , T3} ;基尼系数示例（续）;决策树的“过度拟合”问题;避免过度的两种方法 ;前剪枝(prepruning);前剪枝(prepruning);后剪枝(postpruning);后剪枝法举例 ;A;A;第1步 将决策树规则化 ;规则1 IF A=Y AND B=Y THEN + 规则2 IF A=Y AND B=N AND C=Y THEN + 规则3 IF A=Y AND B=N AND C=N THEN – 规则4 IF A=N THEN - ;规则2与???则4精度为100%，保留;第3步 对规则进行修剪;第4步 根据精度和泛化能力对对规则进行排序;决策树的规则生成;天气=‘晴’ and 湿度＝‘高’ ? 运动=‘不适合’ 天气=‘晴’ and湿度＝‘适中’? 运动=‘适合’ 天气=‘多云’ ? 运动=‘适合’ 天气=‘雨’ and 风况=‘弱’ ? 运动=‘适合’ 天气=‘雨’ and 风况=‘强’ ? 运动=‘不适合’