• 1. 第七章:分类和预测7.1 什么是分类?什么是预测 7.2 关于分类和预测的一些问题 7.3 使用决策树进行分类 7.4 贝叶斯分类 7.5 (向后传播分类)带回馈的分类 7.6 基于关联规则的分类 7.7 其他分类方法 7.8 预测 7.9 分类法的准确性 7.10 总结2018/10/231Data Mining: Concepts and Techniques
  • 2. 分类: 预测种类字段 基于训练集形成一个模型,训练集中的类标签是已知的。使用该模型对新的数据进行分类 预测: 对连续性字段进行建模和预测。 典型应用 信用评分 Direct Marketing 医疗诊断 …………分类和预测2018/10/232Data Mining: Concepts and Techniques
  • 3. 分类的两个步骤模型创建: 对一个类别已经确定的数据创建模型 每一条记录都属于一个确定的类别,我们使用类标签属性记录类别。 用于创建模型的数据集叫:训练集 模型可以用分类规则,决策树,或者数学方程的形式来表达。 模型使用: 用创建的模型预测未来或者类别未知的记录 估计模型的准确率 使用创建的模型在一个测试集上进行预测,并将结果和实际值进行比较。 准确率:正确被模型分类的测试样本的百分比。 测试集和训练集是独立的。2018/10/233Data Mining: Concepts and Techniques
  • 4. 分类过程:模型创建训练集分类算法IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’ 模型2018/10/234Data Mining: Concepts and Techniques
  • 5. 分类过程 (2): 使用模型模型测试集未知数据(Jeff, Professor, 4)Tenured?2018/10/235Data Mining: Concepts and Techniques
  • 6. 有监督和无监督学习有监督学习 (分类) 训练集是带有类标签的 新的数据是基于训练集进行分类的。 无监督学习 (聚集) 训练集是没有类标签的。 提供一组属性,然后寻找出训练集中存在类别或者聚集。2018/10/236Data Mining: Concepts and Techniques
  • 7. 7.2关于分类和预测的一些问题 数据清洗 对数据进行预处理,消除噪音和丢失值。 相关性分析 (属性选择) 去掉不相关或者冗余的属性 数据转换 泛化或者对数据进行标准化(1): 数据准备2018/10/237Data Mining: Concepts and Techniques
  • 8. 关于分类和预测的问题 (2): 评估、比较分类方法预测的准确率 速度 创建速度 使用速度 强壮性 处理噪声数据和缺失值数据的能力 伸缩性 对大量数据,对磁盘驻留数据的处理能力 可解释性: 对模型的可理解和解释的程度。 规则好坏的评价 决策树的大小 分类规则的简明性2018/10/238Data Mining: Concepts and Techniques
  • 9. 7.3使用决策树进行分类(188页)决策树 一个类似流程图的树状结构 内部节点上选用一个属性进行分割 每个分叉都是分割的一个部分 叶子节点表示一个分布 决策树生成算法分成两个步骤 树的生成 开始,数据都在根节点 递归的进行数据分片 树的修剪 去掉一些可能是噪音或者异常的数据 决策树使用: 对未知数据进行分割 按照决策树上采用的分割属性逐层往下,直到一个叶子节点2018/10/239Data Mining: Concepts and Techniques
  • 10. 训练集ID3算法2018/10/2310Data Mining: Concepts and Techniques
  • 11. Output: A Decision Tree for “buys_computer”age?overcaststudent?credit rating?noyesfairexcellent<=30>40nonoyesyesyes30..402018/10/2311Data Mining: Concepts and Techniques
  • 12. 决策树算法基本算法(贪心算法) 自上而下分而治之的方法 开始时,所有的数据都在根节点 属性都是离散值字段 (如果是连续的,将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量 (如, information gain) 停止分割的条件 一个节点上的数据都是属于同一个类别 没有属性可以再用于对数据进行分割 2018/10/2312Data Mining: Concepts and Techniques
  • 13. 属性选择的统计度量Information gain (ID3/C4.5) 所有属性假设都是离散值字段 经过修改之后可以适用于连续值字段 Gini index (IBM Intelligent Miner) 能够适用于离散值和连续值字段2018/10/2313Data Mining: Concepts and Techniques
  • 14. Information Gain (ID3/C4.5) 190页选择属性的标准:具有最高Information Gain 假设有两个类, P 和 N 假设集合S中含有p个类别P的记录,n个类别N的记录 决定任意一个记录属于类别P或者N所需要的information. 2018/10/2314Data Mining: Concepts and Techniques
  • 15. Information Gain 在决策树中的使用假设使用属性A将把集合S分成 V份 {S1, S2 , …, Sv} 如果 Si 中包含 pi 个类别为 P的记录, ni 个类别为 N,的记录。那么熵就是 (entropy), 从而这个信息增益就是 2018/10/2315Data Mining: Concepts and Techniques
  • 16. 使用信息增益进行属性选择 (例7.2)Class P: buys_computer = “yes” Class N: buys_computer = “no” I(p, n) = I(9, 5) =0.940 Compute the entropy for age: Hence Similarly2018/10/2316Data Mining: Concepts and Techniques
  • 17. Gini Index (IBM IntelligentMiner)集合T包含N个类别的记录,那么其Gini指标就是 pj 类别j出现的频率 如果集合T分成两部分 N1 and N2 。那么这个分割的Gini就是 提供最小Ginisplit 就被选择作为分割的标准(对于每个属性都要遍历所有可以的分割方法).2018/10/2317Data Mining: Concepts and Techniques
  • 18. 几种经典算法介绍CART         min(P(c1),P(c2))          2P(c1)P(c2) [P(c1)logP(c1)]+[P(c2)logP(c2)] C4.5(ID3) C4.5(ID3) 对种类字段处理时,缺省是对每个值作为一个分割 Gain和Gain Ratio CHAID 在Overfitting前停止树的生成 必须都是种类字段 选择分割。X2检验 2018/10/2318Data Mining: Concepts and Techniques
  • 19. 从树中生成分类规则用 IF-THEN 这种形式来表现规则 每个叶子节点都创建一条规则 每个分割都成为一个规则中的一个条件 叶子节点中的类别就是Then的内容 规则对于人来说更容易理解 例子7.3 IF age = “<=30” AND student = “no” THEN buys_computer = “no” IF age = “<=30” AND student = “yes” THEN buys_computer = “yes” IF age = “31…40” THEN buys_computer = “yes” IF age = “>40” AND credit_rating = “excellent” THEN buys_computer = “yes” IF age = “<=30” AND credit_rating = “fair” THEN buys_computer = “no”2018/10/2319Data Mining: Concepts and Techniques
  • 20. 在分类中避免过度适应(Overfit)在训练集中生成的会可能会 Overfit 太多的分支, 有些可能是对异常例外的反映 在进行预测的时候准确率比较差 两种 预修剪: 难点:选择一个域值比较困难 后修建: 先生成完整的树,然后进行修剪 使用另外一个的一个测试集来决定哪个树最好2018/10/2320Data Mining: Concepts and Techniques
  • 21. 决定最终树大小的方法使用部分数据: 使用全部数据: 使用一个统计测试 (e.g., chi-square) 来估计保留或者修剪掉一个分支的影响 使用最小描述长度 (MDL) 原则: 当树的Coding最小的时候最佳。2018/10/2321Data Mining: Concepts and Techniques
  • 22. 对基本决策树的提高加入对连续字段的支持 采用 A<=V的形式 处理空值 用最常见的值代替 每个可能的值都给一个概率 属性构造 在现有属性上创建新的属性,主要是针对一些稀疏属性 从而降低 fragmentation, repetition, and replication2018/10/2322Data Mining: Concepts and Techniques
  • 23. 在大型数据库中进行分类分类—在统计和机器学习中有广泛的研究 伸缩性: 对几百万记录和几百个属性进行训练的时候,能够达到一定的速度。 在数据挖掘中为什么使用决策树? 相对比较快的学习速度 (和其它学习方法比较来说) 能够转换成容易理解的分类规则 能够使用SQL语句查询数据库 分类的准确率也不差2018/10/2323Data Mining: Concepts and Techniques
  • 24. Scalable Decision Tree Induction 数据挖掘中提出的方法SLIQ (EDBT’96 — Mehta et al.) SPRINT (VLDB’96 — J. Shafer et al.) PUBLIC (VLDB’98 — Rastogi & Shim) RainForest (VLDB’98 — Gehrke, Ramakrishnan & Ganti) builds an AVC-list (attribute, value, class label)2018/10/2324Data Mining: Concepts and Techniques
  • 25. SLIQ算法介绍总揽:预排序、广度优先、种类字段快速分割、 MDL修剪方法 预排序:减少对数值字段进行排序消耗的时间 属性列表(attribute list): 属性值 索引 类列表(class list): 类标签 指向树中的节点2018/10/2325Data Mining: Concepts and Techniques
  • 26. Sliq分类算法2018/10/2326Data Mining: Concepts and Techniques
  • 27. Sliq分类算法进行节点的分割:广度优先 对当前树中所有叶子节点分割的计算都是在同一遍中完成的。 引进的数据结构:类分布表 数值字段:类标签、频率 种类字段:属性值、类标签、频率 对数值字段进行分割计算:2018/10/2327Data Mining: Concepts and Techniques
  • 28. Sliq分类算法2018/10/2328Data Mining: Concepts and Techniques
  • 29. Sliq分类算法对种类字段进行分割: 通过对数据的扫描生成类分布表 寻找分割集合 如果不同字段的值少于预定值,进行完全搜索 如果不同字段的值大于预定值,使用贪心算法 2018/10/2329Data Mining: Concepts and Techniques
  • 30. Sliq分类算法树的修剪:采用了MDL策略 Cost(M,D)=cost(D|M)+cost(M) 整个算法包括两个部分: 编码方法 不同子树的比较方法 2018/10/2330Data Mining: Concepts and Techniques
  • 31. 基于数据立方体的决策树Integration of generalization with decision-tree induction (Kamber et al’97). 在最低概念层上进行分类 例如, precise temperature, humidity, outlook, etc. 低的层次,分散的类别,过多的叶子节点 模型解释的问题. 基于Cube的多层分类 在多个层次上进行相关性分析. 在多个层次上进行Information Gain的计算.2018/10/2331Data Mining: Concepts and Techniques
  • 32. 结果显示(一)2018/10/2332Data Mining: Concepts and Techniques
  • 33. 结 果 显 示(二)2018/10/2333Data Mining: Concepts and Techniques
  • 34. 7.4贝叶斯分类后验概率(posteriori probabilities):P(H|X)表示条件X下H的概率. 贝叶斯定理: P(H|X)=P(X|H)P(H)/P(X)2018/10/2334Data Mining: Concepts and Techniques
  • 35. 朴素贝叶斯分类假定有m个类C1,…Cm,对于数据样本X,分类法将预测X属于类Ci,当且仅当 P(Ci|X)> P(Cj|X),1<=j<=m,j!=i 根据贝叶斯定理, P(Ci|X)=P(X|Ci)P(Ci)/P(X) 由于P(X)对于所有类都是常数,只需最大化P(X|Ci) P(Ci) 2018/10/2335Data Mining: Concepts and Techniques
  • 36. 计算P(X|Ci),朴素贝叶斯分类假设类条件独立.即给定样本属性值相互条件独立. P(x1,…,xk|C) = P(x1|C)·…·P(xk|C) 2018/10/2336Data Mining: Concepts and Techniques
  • 37. 2018/10/2337Data Mining: Concepts and Techniques
  • 38. 样本 X = P(X|p)·P(p) = P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p) = 3/9·2/9·3/9·6/9·9/14 = 0.010582 P(X|n)·P(n) = P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n) = 2/5·2/5·4/5·2/5·5/14 = 0.018286 样本 X 分配给 类 n (don’t play) 2018/10/2338Data Mining: Concepts and Techniques
  • 39. 贝叶斯网络朴素贝叶斯算法假定类条件独立,当假定成立时,该算法是最精确的.然而实践中,变量之间的依赖可能存在. 贝叶斯网络解决了这个问题,它包括两部分,有向无环图和条件概率表(CPT).2018/10/2339Data Mining: Concepts and Techniques
  • 40. 贝叶斯信念网络Family HistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLC~LC(FH, S)(FH, ~S)(~FH, S)(~FH, ~S)0.80.20.50.50.70.30.10.9有向无环图The conditional probability table for the variable LungCancer2018/10/2340Data Mining: Concepts and Techniques
  • 41. 一旦FamilyHistory和Smoker确定,LungCancer就确定和其他的无关. P(LungCancer=“yes”| FamilyHistory=“yes” Smoker=“yes”)=0.8 P(LungCancer=“no”| FamilyHistory=“no” Smoker=“no”)=0.9 2018/10/2341Data Mining: Concepts and Techniques
  • 42. 训练贝叶斯网络梯度 其中s个训练样本X1,…Xs,Wijk表示具有双亲Ui=uik的变量Yi=yij的CPT项.比如Yi是LungCancer,yij是其值“yes”,Ui列出Yi的双亲(FH,S),uik是其值(“yes”,”yes”)2018/10/2342Data Mining: Concepts and Techniques
  • 43. 梯度方向前进, Wijk=Wijk+(l)*梯度 其中l是学习率,l太小学习将进行得很慢,l太大可能出现在不适当的值之间摆动.通常令l=1/t,t是循环的次数 将Wijk归一化. 每次迭代中,修改Wijk,并最终收敛到一个最优解.2018/10/2343Data Mining: Concepts and Techniques
  • 44. 神经网络7.5 (向后传播分类)带回馈的分类2018/10/2344Data Mining: Concepts and Techniques
  • 45. 计算方法2018/10/2345Data Mining: Concepts and Techniques
  • 46. 由前一层的输出作为输入i,与对应的权w相乘形成加权和,再加上偏置 对上面结果用一个非线性函数f作用形成本层的输出.将较大的值映射到0-1之间2018/10/2346Data Mining: Concepts and Techniques
  • 47. 算法步骤Output nodesInput nodesHidden nodesOutput vectorInput vector: xiwij2018/10/2347Data Mining: Concepts and Techniques
  • 48. 计算实例2018/10/2348Data Mining: Concepts and Techniques
  • 49. 一个训练样本X={1,0,1},输出为1 X1=1,x2=0,x3=1,w14=0.2,w15=-0.3,w24=0.4,w25=0.1,w34=-0.5,w35=0.2,w46=-0.3,w56=-0.2, 偏置值:节点4:-0.4,节点5:0.2,节点6:0.1 学习率设为0.92018/10/2349Data Mining: Concepts and Techniques
  • 50. 节点4: 输入值:w14*x1+w24*x2+w34*x3+节点4的偏置=1*0.2+0.4*0-0.5*1-0.4=-0.7 输出值:用公式 可得0.332 同理:节点5输入值0.1,输出值0.525 节点6: 输入值:w46*o4+w56*o5+节点6的偏置=-0.3*0.332-0.2*0.525+0.1=-0.105 输出值:0.4742018/10/2350Data Mining: Concepts and Techniques
  • 51. 误差计算节点6: 0.474*(1-0.474)*(1-0.474)=0.1311 节点5: 0.525*(1-0.525)*0.1311*(-0.2)= -0.0065 同理节点4误差为:-0.00872018/10/2351Data Mining: Concepts and Techniques
  • 52. 更新权值和偏置值W46: -0.3+(0.9)(0.1311)(0.332)=-0.261 其他Wij同理 节点6的偏置: 0.1+(0.9)*(0.1311)=0.218 其他偏置同理2018/10/2352Data Mining: Concepts and Techniques
  • 53. 终止条件对所有样本作一次扫描称为一个周期 终止条件:对前一周期所有Wij的修改值都小于某个指定的阈值;或超过预先指定的周期数. 防止训练过度2018/10/2353Data Mining: Concepts and Techniques
  • 54. 神经网络的解释2018/10/2354Data Mining: Concepts and Techniques
  • 55. 2018/10/2355Data Mining: Concepts and Techniques
  • 56. 解释过程对隐藏节点进行聚类,对于所有给定的输入,输出值分成几个类. 导出与输出节点O的一系列规则 导出与输入节点I的一系列规则 得到关于输入和输出的规则 2018/10/2356Data Mining: Concepts and Techniques
  • 57. 灵敏度分析用于评估一个给定的变量对网络输出的影响.改变该变量的输入,其他变量固定,监测网络的输出. 得到的规则形如:IF X 减少5%, THEN Y 增加 8%的规则.2018/10/2357Data Mining: Concepts and Techniques
  • 58. 7.6 基于关联规则的分类 7.7 其他分类方法 K-最临近分类 基于案例的推理 遗传算法 粗糙集算法 模糊集算法 7.8 预测 线性回归和多元回归 非线性回归 其他回归模型2018/10/2358Data Mining: Concepts and Techniques
  • 59. 7.9 分类法的准确性 评估分类法的准确率 提高分类法的准确率 准确率足够判定分类法? 7.10 总结2018/10/2359Data Mining: Concepts and Techniques
  • 60. 第七章:分类和预测7.1 什么是分类?什么是预测 7.2 关于分类和预测的一些问题 7.3 使用决策树进行分类 7.4 贝叶斯分类 7.5 (向后传播分类)带回馈的分类 7.6 基于关联规则的分类 7.7 其他分类方法 7.8 预测 7.9 分类法的准确性 7.10 总结2018/10/2360Data Mining: Concepts and Techniques