信息检索与数据挖掘

Save this PDF as:
 WORD  PNG  TXT  JPG

Size: px
Start display at page:

Download "信息检索与数据挖掘"

Transcription

1 2018/5/4 1 信息检索与数据挖掘 补充 : 数据挖掘经典算法概述 4 月 28 日, 补充 : 概率图及主题模型 5 月 4 日, 补充 : 数据挖掘经典算法概述 (1) 5 月 7 日, 补充 : 数据挖掘经典算法概述 (2) 5 月 11 日, 第 12 章 Web 搜索 5 月 14 日, 第 13 章多媒体信息检索 5 月 18 日, 复习 5 月 21 日, 同学们文献阅读报告 5 月 25 日, 同学们文献阅读报告 5 月 28 日, 期末考试 暂定

2 2018/5/4 2 小结 : 什么是 Graphical Model Graphical Model( 概率图模型 ) Probabilistic Graphical Models (PGMs) 展开的概率图 盘式记法 概率图理论共分为三个部分 Representation Inference Learning 概率图模型的常见类型 贝叶斯网络采用有向无环图 (Directed Acyclic Graph) 马尔可夫随机场则采用无向图 (Undirected Graph)

3 2018/5/4 3 小结 :plsa topic model:(1) 文档是若干主题的混合分布 ;(2) 每个主题又是一个关于单词的概率分布 d z w N plsa M

4 2018/5/4 4 小结 :LDA latent Dirichlet allocation (LDA) A generative probabilistic LDA is a three-level hierarchical Bayesian model. θ~p(θ), Dirichlet(α) topic z n ~p(z θ), Multinomial(θ) word w n ~p(w z), from p(w n z n,β), multinomial

5 2018/5/4 5 信息检索与数据挖掘 补充 : 数据挖掘经典算法概述 4 月 28 日, 补充 : 概率图及主题模型 5 月 4 日, 补充 : 数据挖掘经典算法概述 (1) 5 月 7 日, 补充 : 数据挖掘经典算法概述 (2) 5 月 11 日, 第 12 章 Web 搜索 5 月 14 日, 第 13 章多媒体信息检索 5 月 18 日, 复习 5 月 21 日, 同学们文献阅读报告 5 月 25 日, 同学们文献阅读报告 5 月 28 日, 期末考试 暂定

6 2018/5/4 7 名词演化 数据挖掘 (data mining) 数据库的知识发现 (KDD, Knowledge Discovery in Database) 模式识别 (pattern recognition) 人工智能 (Artificial intelligence) 机器学习 (machine learning) 统计机器学习 (statistical learning)

7 2018/5/4 8 Top 10 algorithms in data mining, 2007 This paper presents the top 10 data mining algorithms identified by the IEEE International Conference on Data Mining (ICDM) in December 2006: C4.5, k-means, SVM, Apriori, EM, PageRank, AdaBoost, knn, Naive Bayes, and CART. These top 10 algorithms are among the most influential data mining algorithms in the research community These 10 algorithms cover classification, clustering, statistical learning, association analysis, and link mining, which are all among the most important topics in data mining research and development. Xindong Wu, Vipin Kumar, J. Ross Quinlan, et al. Top 10 algorithms in data mining. Knowledge and Information Systems, 14(1):1 37, Published online: 4 December 2007.

8 2018/5/4 9 数据挖掘十大经典算法 Naive Bayes knn k-means SVM EM C4.5 CART AdaBoost Apriori Pagerank 第 12 章 Web 搜索 [1] Xindong Wu, Vipin Kumar, J. Ross Quinlan, et al. Top 10 algorithms in data mining. Knowledge and Information Systems, 14(1):1 37, 4 December 2007.

9 2018/5/4 10 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost,1995 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 A-Priori [1994] Eclat [1997] FP-growth (Frequent Pattern growth) [2000] 不确定数据的频繁项集的挖掘 Web 中的数据挖掘 哈希 (hash) 与哈希表 (Hash Table) 布隆过滤器 (Bloom Filter) 近似重复检测

10 2018/5/4 11 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost,1995 流数据挖掘 : 频繁项集 Web 中的数据挖掘

11 2018/5/4 12 示例 : 训练集 测试集 训练集 outlook temperature humidity windy play sunny hot high FALSE no sunny hot high TRUE no overcast hot high FALSE yes rainy mild high FALSE yes rainy cool normal FALSE yes rainy cool normal TRUE no overcast cool normal TRUE yes sunny mild high FALSE no sunny cool normal FALSE yes rainy mild normal FALSE yes sunny mild normal TRUE yes overcast mild high TRUE yes overcast hot normal FALSE yes rainy mild high TRUE no Machine Learning, Tom M.Mitchell, 1997, 第 3 章例子 统计了 14 天的气象数据 ( 指标包括 outlook,temperature, humidity,windy), 并已知这些天气是否打球 (play) 如果给出新一天的气象指标数据 :sunny,cool,high,true, 判断一下会不会去打球 这是个二分类问题 测试集 outlook temperature humidity windy sunny cool high FALSE

12 2018/5/4 13 朴素贝叶斯分类求解回顾 :Naive Bayes text classification 在文本分类中, 我们的目标是找出文档最可能属于的类别 对于 NB 分类来说, 最可能的类是具有 MAP 估计值的结果 c map : 如何估计参数 Pˆ(c) 及 Pˆ(t k c )? 零概率问题 平滑

13 2018/5/4 14 朴素贝叶斯分类器 概率图 E1(outlook): sunny, overcast, rainy E2(temperature): hot, mild, cool E3(humidity): high, normal E4(windy): FALSE, TRUE C(play): no, yes 独立性的假设 P(C,E1,E2,E3,E4)=P(C)P(E1 C)P(E2 C)P(E3 C)P(E4 C) Graphical Model C E4 E1 E2 E3

14 朴素贝叶斯分类求解 2018/5/4 15 E1:outlook E2: emperature E3:humidity E4:windy C:play yes no yes no yes no yes no yes no sunny 2 3 hot 2 2 high 3 4 false overcast 4 0 mild 4 2 normal 6 1 true 3 3 rainy 3 2 cool 3 1 Bayes 公式 :P(c e) P(c)P(e c) e = {e1=sunny, e2=cool, e3=high, e4=false} 测试集 outlook temperature humidity windy sunny cool high FALSE P(c=yes e) P(c=yes)P(E1 c=yes)p(e2 c=yes) P(E3 c=yes) P(E4 c=yes) P(c=no e) P(c=no)P(E1 c=no)p(e2 c=no) P(E3 c=no) P(E4 c=no) P(c=yes e)*p(e)=9/14 2/9 3/9 3/9 3/9= P(c=no e)*p(e)=5/14 3/5 1/5 4/5 3/5= c=no

15 2018/5/4 16 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost,1995 流数据挖掘 : 频繁项集 Web 中的数据挖掘

16 2018/5/4 17 EM 算法示例 : 求两个硬币随机抛出后正反面的概率完全信息下的 MLE 估计 x = (x1, x2,, x5), x i {0,1,,10} 第 i 次抛硬币试验中正面 (head) 朝上的次数 z = (z 1, z 2,, z 5 ), z i {A,B} 第 i 次抛硬币试验中被抛掷的硬币是 A 还是 B x=(5,9,8,4,7) z=(b,a,a,b,a) MLE:Find parameters θθ = ( θθ AA, θθ BB ) that maximize logp(x,z;θ). 找到使得 logp(x,z;θ) 最大的参数 θ,logp(x,z ; θ) 分号左边是随机变量, 右边是模型参数 硬币 AA 正面朝上的次数 θθ AA =, θθ 硬币 AA 抛的总次数 AA = 硬币 B 正面朝上的次数硬币 B 抛的总次数 C. B. Do and S. Batzoglou, "What is the expectation maximization algorithm?," Nature Biotechnology, vol. 26, p. 897, 08/01/online 2008.

17 2018/5/4 18 EM 算法示例 : 求两个硬币随机抛出后正反面的概率不完全信息 : 不知道每次抛的是 A 还是 B 如果是 A 硬币, 抛出 HHHHTHHHHH 的概率是 θθ AA 9 (1- θθ AA ) 1 = = 如果是 B 硬币, 抛出 HHHHTHHHHH 的概率是 θθ BB 9 (1- θθ BB ) 1 = H1T 0.80*9H1T *9H1T 7.2H,0.8T + 1.8H,0.2T θθ AA = , θθ BB = 故这次试验是硬币 A 的期望为 0.004/( )=0.80, 是硬币 B 的期望为 0.004/( )= EM starts with an initial guess of the parameters. 2. In the E-step, a probability distribution over possible completions is computed using the current parameters. The counts shown in the table are the expected numbers of heads and tails according to this distribution. 3. In the M-step, new parameters are determined using the current completions. 4. After several repetitions of the E-step and M-step, the algorithm converges. C. B. Do and S. Batzoglou, "What is the expectation maximization algorithm?," Nature Biotechnology, vol. 26, p. 897, 08/01/online 2008.

18 2018/5/4 19 EM 算法示例 : 求两个硬币随机抛出后正反面的概率迭代过程分析 x = (x1, x2,, x5), x i {0,1,,10} 第 i 次抛硬币试验中正面 (head) 朝上的次数 z = (z 1, z 2,, z 5 ), z i {A,B} 第 i 次抛硬币试验中被抛掷的硬币是 A 还是 B x=(x 1 =5,x 2 =9,x 3 =8,x 4 =4,x 5 =7) Z 是隐变量 2 求隐变量 Z 的后验概率 PP(zz ii = AA xx ii ; θθ AA (00) ) PP(zz ii = BB xx ii ; θθ BB (00) ) X 和 Z 的联合概率 PP(xx ii, zz ii = AA xx ii ; θθ AA (00) ) PP(xx ii, zz ii = BB xx ii ; θθ BB (00) ) 3 从联合概率求边缘概率 θθ AA (11) = PP(zzii = AA xx ii ; θθ AA (00) ) θθ B (11) = PP(zzii = BB xx ii ; θθ BB (00) ) C. B. Do and S. Batzoglou, "What is the expectation maximization algorithm?," Nature Biotechnology, vol. 26, p. 897, 08/01/online 2008.

19 EM 算法 : 迭代过程不断构造更好的下界 2018/5/4 20 先固定当前参数, 计算得到当前隐变量分布的一个下界 (Lower Bound) 函数, 然后优化这个函数, 得到新的参数, 然后循环继续 pp XX ; θθ = ZZ pp XX, ZZ ; θθ 从联合概率计算边缘概率 pp XX, ZZ ; θθ pp(xx ; θθ) = qq ZZ, qq ZZ = pp(zz XX ; θθ tt ), 构造的先验分布 qq(zz) log pp(xx ; θθ) = log qq ZZ ZZ ZZ pp XX, ZZ ; θθ qq(zz) pp XX, ZZ ; θθ gg tt θθ qq ZZ log qq ZZ ZZ qq ZZ log ZZ = pp ZZ XX ; θθ tt ZZ pp XX, ZZ ; θθ qq ZZ pp XX, ZZ ; θθ log pp ZZ XX ; θθ tt θθ (tt+1) = argmax gg tt (θθ) gg tt (θθ) 是 log pp(xx ; θθ) 的 lower bound θθ JJJJJJJJJJnn ss iiiiiiiiiiiiiiiiiiii C. B. Do and S. Batzoglou, "What is the expectation maximization algorithm?," Nature Biotechnology, vol. 26, p. 897, 08/01/online 关于 EM 算法的九层境界的浅薄介绍

20 2018/5/4 21 pp XX ; θθ = ZZ pp XX, ZZ ; θθ 从联合概率计算边缘概率 pp XX, ZZ ; θθ pp(xx ; θθ) = qq ZZ, qq ZZ = pp(zz XX ; θθ tt ), 构造的先验分布 qq(zz) ZZ log pp(xx ; θθ) = log qq ZZ ZZ pp XX, ZZ ; θθ qq(zz) log pp(xx ; θθ) qq ZZ ; θθ tt log pp(xx ; θθ) pp ZZ XX ; θθ tt log pp(xx ; θθ) pp ZZ XX ; θθ tt log pp(xx ; θθ) pp ZZ XX ; θθ tt EM 算法 : 迭代逼近最优解过程分析 ZZ ZZ ZZ ZZ qq ZZ log ZZ log pp XX, ZZ ; θθ tt qq ZZ; θθ tt log pp XX, ZZ ; θθ tt pp ZZ XX ; θθ tt log pp XX, ZZ ; θθ tt pp ZZ XX ; θθ log pp XX, ZZ ; θθ tt pp ZZ XX ; θθ pp XX, ZZ ; θθ qq ZZ llllll pp XX θθ LL qq, θθ + KKKK(qq pp) pp ZZ XX ; θθ pp ZZ XX ; θθ tt JJJJJJJJJJnn ss iiiiiiiiiiiiiiiiiiii + pp ZZ XX ; θθ tt ZZ log pp ZZ XX ; θθ pp ZZ XX ; θθ tt

21 2018/5/4 22 EM 算法 : 迭代逼近最优解过程示意 log pp XX θθ L qq, θθ + KKKK qq pp Expectation: 参数 θθ = θθ tt 固定, 使 KKKK qq pp 最小化, 即更新后验概率 pp ZZ XX ; θθ tt Maximization: 使 L qq, θθ 最大化, 即更新参数 θθ tt+1 = θθ tt 关于 EM 算法的九层境界的浅薄介绍

22 2018/5/4 24 K-means 算法是一种 Hard EM 算法 拟聚类文档随机选择两个种子 (K=2) 分配 ( 第 1 次 ) 分配结果重新计算质心向量再重新分配 ( 第 2 次 )

23 2018/5/4 25 K-means 算法是一种 Hard EM 算法 xx = xx 1, xx 2,, xx NN, x 为第 i i 个文档 zz = zz 1, zz 2,, zz NN, zz ii {ωω 1, ωω 2,, ωω KK } z i 为隐变量, 代表文档 x i 所属的类 参数 θθ = (θθ 1, θθ 2,, θθ KK ) {μμ(ωω 1 ), μμ(ωω 2 ),, μμ(ωω KK )}, 代表类的质心 L(XX ; θθ) = qq ZZ ; θθ tt ZZ log pp XX, ZZ ; θθ tt qq ZZ; θθ tt Expectation:qq ZZ ; θθ tt = pp(zz XX ; θθ tt ) pp XX, ZZ ; θθ tt argmin jj xx ii θθ jj tt argmin jj PP XX = xx ii, ZZ = zz jj ; θθ tt Maximization: θθ jj tt+1 = 1 ωω jj zz ii ωω jj xx ii xx ii θθ jj tt PP(ZZ = zz jj XX = xx ii ; θθ tt ) 上述形式化描述受如下文献的启发导出, 与该文并不相同, 仅供参考关于 EM 算法的九层境界的浅薄介绍

24 2018/5/4 26 小结 :EM (Expectation Maximization) 参数估计的两种情形 完全信息下的 MLE 估计 不完全信息下的参数估计 EM 算法是一种解决存在隐含变量优化问题的方法 E-Step: 根据已经估计的参数计算隐藏变量的后验概率 ( 即根据参数计算似然函数的期望 ) M-Step: 根据已经计算的后验概率更新参数 ( 选择参数使似然最大化 ) 特点 通过不断构造下界逐步向最优逼近 K-means 算法是一种 Hard EM 算法 估计参数的初值影响到是否落入局部最优点 C. B. Do and S. Batzoglou, "What is the expectation maximization algorithm?," Nature Biotechnology, vol. 26, p. 897, 08/01/online 关于 EM 算法的九层境界的浅薄介绍

25 2018/5/4 27 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost,1995 流数据挖掘 : 频繁项集 Web 中的数据挖掘

26 2018/5/4 28 决策树 (Decision Tree) 女儿 : 多大年纪了? 母亲 :26 女儿 : 长的帅不帅? 母亲 : 挺帅的 女儿 : 收入高不? 母亲 : 不算很高, 中等情况 女儿 : 是公务员不? 母亲 : 是, 在税务局上班呢 女儿 : 那好, 我去见见 如果将所有条件量化, 就变成真正的决策树了 存在问题 : 如何构造决策树 ( 根节点 各级节点如何选 )?

27 2018/5/4 30 示例 : 训练集 测试集 训练集 outlook temperature humidity windy play sunny hot high FALSE no sunny hot high TRUE no overcast hot high FALSE yes rainy mild high FALSE yes rainy cool normal FALSE yes rainy cool normal TRUE no overcast cool normal TRUE yes sunny mild high FALSE no sunny cool normal FALSE yes rainy mild normal FALSE yes sunny mild normal TRUE yes overcast mild high TRUE yes overcast hot normal FALSE yes rainy mild high TRUE no Machine Learning, Tom M.Mitchell, 1997, 第 3 章例子 统计了 14 天的气象数据 ( 指标包括 outlook,temperature, humidity,windy), 并已知这些天气是否打球 (play) 如果给出新一天的气象指标数据 :sunny,cool,high,true, 判断一下会不会去打球 这是个二分类问题 测试集 outlook temperature humidity windy sunny cool high FALSE

28 2018/5/4 31 两种不同的决策树 用什么样的规则构造决策树?

29 2018/5/4 32 构建决策树的思路 构建决策树时通常采用自上而下的方法, 在每一步选择一个最好的属性来分裂 最好 的定义是使得子节点中的训练集尽量的纯 最好 也可以定义为 不纯度 尽量小 在数据挖掘中, 决策树主要有两种类型 : 分类树 : 输出是样本的类别标签 (label) 回归树 : 输出是一个实数 回归, 为什么称之为回归? Galton: y= x

30 2018/5/4 33 一种可能的构造方法 E1:outlook E2: temperature E3:humidity E4:windy C:play yes no yes no yes no yes no yes no sunny 2 3 hot 2 2 high 3 4 false overcast 4 0 mild 4 2 normal 6 1 true 3 3 rainy 3 2 cool 3 1 H(C) = - p(c=yes)log 2 p(c=yes) - p(c=no)log 2 p(c=no) 事件 C 的不确定度 = - 9/14log(9/14)-5/14log2(5/14) = H(C E1)= - p(e1=sunny) [p(c=yes e1=sunny) + p(c=no e1=sunny)] - p(e1=overcast) [p(c=yes e1=overcast) + p(c=no e1=overcast)] - p(e1=rainy) [p(c=yes e1=rainy) + p(c=no e1=rainy)] H(C E1) = -5/14 *[2/5log 2 (2/5) + 3/5log 2 (3/5)] = 5/14 * /14 * 0-5/14 * [3/5log 2 (3/5) + 2/5log 2 (2/5)] = 获知 outlook 后的不确定度 H(C E2) = H(C E3) = H(C E4) = 获知 temperature 后的不确定度 获知 humidity 后的不确定度 获知 windy 后的不确定度 获知 outlook 后不确定度最小, 选为根节点

31 2018/5/4 34 ID3 (Iterative Dichotomiser 3) 算法 (1979): 树的构造之根节点选取 信息增益 (information gain) 最大 上述构造树的基本想法是随着树深度的增加, 节点的熵迅速地降低 熵降低的速度越快越好, 这样我们有望得到一棵高度最矮的决策树 ID3 算法基于信息增益最大的原则来选择节点 ( 其实就是互信息量 ) 例如, 计算根节点信息增益 ( 属性 E1 与类别 C 的互信息量 ) Gain(E1) = H(C) H(C E1) = 最大, 根节点 Gain(E2) = H(C) H(C E2) = Gain(E3) = H(C) H(C E3) = Gain(E4) = H(C) H(C E4) = E1 属性被选作根节点后, 下一步, 确定 e1=sunny, e1=overcast, e1=rainy 三个分支的下一级 互信息量 I(X,Y) = H(X) H(X Y), 获知 Y 后对减少 X 不确定度的贡献

32 2018/5/4 35 ID3 算法 (1979) : 树的构造之子节点选取 互信息量 I(X,Y) = H(X) H(X Y), 获知 Y 后对减少 X 不确定度的贡献 ID3 算法中的信息增益其实就是互信息量例如, 属性 E1 与类别 C 的互信息量 Gain(E1) = H(C) H(C E1) = 最大, 根节点 Gain(E2) = H(C) H(C E2) = Gain(E3) = H(C) H(C E3) = E1 rainy Gain(E4) = H(C) H(C E4) = overcast? E1 属性被选作根节点后, 下一步, 确定 e1=sunny, e1=overcast, e1=rainy 三个分支的下一级 通过计算这三种条件下的信息增益来选择 Gain(E2, e1=sunny) Gain(E3, e1=sunny) Gain(E4, e1=sunny) Gain(E2, e1=overcast) Gain(E3, e1=overcast) Gain(E4, e1=overcast) Gain(E2, e1=rainy) Gain(E4, e1=rainy) Gain(E4, e1=rainy)? sunny?

33 2018/5/4 36 E1:outlook E2: temperature E3:humidity E4:windy C:play sunny yes no yes no yes no yes no hot 0 2 high 0 3 false mild 1 1 normal 1 0 true 1 1 cool 0 0 Gain(E2, e1=sunny) = H(C) - H(C E2, e1=sunny) = H(C) Gain(E3, e1=sunny) = H(C) - H(C E3, e1=sunny) = H(C) 0 最大! Gain(E4, e1=sunny) = H(C) - H(C E4, e1=sunny) = H(C) H(C E2, e1=sunny) = - p(e2=hot,e1=sunny) [p(c=yes e2=hot,e1=sunny) + p(c=no e2=hot,e1=sunny)] - p(e2=mild,e1=sunny) [p(c=yes e2=mild,e1=sunny) + p(c=no e2=mild,e1=sunny)] - p(e2=cool,e1=sunny) [p(c=yes e2=cool,e1=sunny) + p(c=no e2=cool,e1=sunny)] = 2/4 * 0 2/4 * 1 0 = 0.5 Max{ Gain(E2, e1=sunny), Gain(E3, e1=sunny), Gain(E4, e1=sunny) } = Gain(E3, e1=sunny)? sunny E1? overcast rainy?

34 2018/5/4 37 E1:outlook E2: temperature E3:humidity E4:windy C:play sunny overcast rainy yes no yes no yes no yes no hot 0 2 high 0 3 false mild 1 1 normal 1 0 true 1 1 cool yes no yes no yes no yes no hot 2 0 high 2 0 false mild 1 0 normal 2 0 true 2 0 cool 1 0 yes no yes no yes no yes no hot high 1 1 false mild 2 1 normal 2 1 true 0 2 cool 1 1 P(c=yes e1=overcast) = 1 P(c=yes e4=windy, e1=rainy) = 1

35 2018/5/4 38 ID3 算法 (1979) 测试集 outlook sunny temperature cool humidity high windy FALSE 思考 : (1) 属性 temperature 并未出现在所生成的决策树中 (2) 对于给定的测试集而言属性 windy 也未被利用 E1: outlook E3: humidity normal high sunny overcast YES rainy false E4: windy true NO YES YES NO

36 2018/5/4 39 ID3 算法 (1979) 缺点 ID3 信息增益的计算依赖于特征数目较多的特征, 而属性取值最多的属性并不一定最优 ID3 是单变量决策树 ( 在分枝节点上只考虑单个属性 ), 许多复杂概念的表达困难, 属性相互关系强调不够, 容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次 抗噪性能差, 训练例子中正例和反例的比例较难控制

37 2018/5/4 40 其他待解决的问题 1 如果某属性的取值为连续值? 分段划分 temperature: -10 ~ 45 temperature: hot, mild, cool temperature play NO NO YES YES YES YES 2 如果某属性的取值特别多 ( 熵值高 )? 归一化 -1/2log 2 (1/2) -1/2log 2 (1/2) = 1-1/4log 2 (1/4) -1/4log 2 (1/4) -1/4log 2 (1/4) -1/4log 2 (1/4)=2-1/8log 2 (1/8)- -1/8log 2 (1/8)=3 需要找到合适的归一化方式, 使得取值多和取值少的属性贡献度一致

38 其他待解决的问题过拟合与剪枝 2018/5/ 决策树的过拟合 (Overfitting) 对于训练样本而言, 树表现完好, 误差率极低且能够正确得对训练样本集中的样本进行分类 训练样本中的错误数据也会被决策树学习, 成为决策树的部分, 但是对于测试数据的表现就没有想象的那么好, 或者极差, 这就是所谓的过拟合问题 树的剪枝 (Pruning) 研究表明, 过拟合的决策树的错误率比经过简化的决策树的错误率要高 剪枝可以分为两种 : 预剪枝 (Pre-Pruning) 和后剪枝 (Post-Pruning) : 预剪枝, 及早的停止树增长 后剪枝, 在已生成决策树上进行剪枝, 得到简化的决策树

39 2018/5/4 42 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost,1995 流数据挖掘 : 频繁项集 Web 中的数据挖掘

40 2018/5/4 43 C4.5(1992): 对 ID3 的改进 ID3 算法中的信息增益 ( 其实就是互信息量 ) Gain(E1) = H(C) H(C E1) Gain(E3, e1=sunny) = H(C) - H(C E3, e1=sunny) C4.5 算法的信息增益率 IGR(E1) = Gain(E1) / H(E1) IGR(E1) = [H(C) H[C E1]] / H(E1)

41 2018/5/4 44 C4.5(1992): 对 ID3 的扩展 C4.5 算法在以下几方面对 ID3 算法进行了改进 : 1) 用信息增益率来选择属性, 克服了用信息增益选择属性时偏向选择取值多的属性的不足 ; 2) 在树构造过程中进行剪枝 ; 一些分枝反映的是训练数据中的异常 ( 数据中的噪声和离群点 ) 剪枝方法是用来处理这种过分拟合数据的问题 3) 能够完成对连续属性的离散化处理 ; 4) 能够对不完整数据进行处理 C4.5 算法优点 产生的分类规则易于理解, 准确率较高 C4.5 算法缺点 在构造树的过程中, 需要对数据集进行多次的顺序扫描和排序, 因而导致算法的低效 此外,C4.5 只适合于能够驻留于内存的数据集, 当训练集大得无法在内存容纳时程序无法运行

42 2018/5/4 45 罗斯. 昆兰 (Ross Quinlan) Software available for download: FOIL Release 6: (shell archive) FFOIL Release 2: (shell archive) C4.5 Release 8: (gzipped tar file) C4.5 has been superseded by C5.0. Source code for C5.0 is available 2011 年获得了数据挖掘领域最高荣誉奖 KDD 创新奖, 昆兰发明了著名的决策树学习算法 ID3 C4.5, 其个人主页公布了 C4.5 的 C 代码 John Ross Quinlan is a computer science researcher in data mining and decision theory. He has contributed extensively to the development of decision tree algorithms, including inventing the canonical C4.5 and ID3 algorithms. He also contributed to early ILP literature with First Order Inductive Learner (FOIL). He is currently running the company RuleQuest Research which he founded in Inductive Logic Programming, ILP

43 2018/5/4 46 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost,1995 流数据挖掘 : 频繁项集 Web 中的数据挖掘

44 2018/5/4 47 CART (Classification And Regression Tree, 1984) CART 算法是一种二分递归分割技术, 把当前样本划分为两个子样本, 使得生成的每个非叶子结点都有两个分支, 因此 CART 生成的决策树是结构简洁的二叉树 设 x 1,x 2,,x n 代表单个样本的 n 个属性,y 表示所属类别 CART 算法通过递归的方式将 n 维的空间划分为不重叠的矩形 划分步骤大致如下 : (1) 选一个自变量 x i, 再选取 x i 的一个值 v i, v i 把 n 维空间划分为两部分, 一部分的所有点都满足 x i vv ii, 另一部分的所有点都满足 x i > vv ii, 对非连续变量来说属性值的取值只有两个, 即等于该值或不等于该值 (2) 递归处理, 将上面得到的两部分按步骤 (1) 重新选取一个属性继续划分, 直到把整个维空间都划分完 在划分时有一个问题, 它是按什么标准来划分的? 对于一个变量属性来说, 它的划分点是一对连续变量属性值的中点 假设 m 个样本的集合一个属性有 m 个连续的值, 那么则会有 (m-1) 个分裂点, 每个分裂点为相邻两个连续值的均值 每个属性的划分按照能减少的杂质的量来进行排序, 而杂质的减少量定义为划分前的杂质减去划分后的每个节点的杂质量划分所占比率之和

45 2018/5/4 48 CART (Classification And Regression Tree, 1984) 基尼指数用于指示分裂方式 GINI 指数的概念 : 给定一个数据集 D, 其中包含的分类类别总数为 K, 类别 k 在数据集中的个数为 C k, 其 GINI 指数表示为 : KK GGIIIIII DD = pp kk (11 pp kk ) = 11 pp 22 kk = 11 kk=11 KK kk=11 KK kk=11 CC kk 若样本集合 D 根据特征 A 是否取某一可能值 a 被分割成 D 1 和 D 2 两部分, 即 : DD 11 = xx, yy DD AA(xx) = aa, DD 22 = DD DD 11 在特征 A 给定的条件下, 集合 D 的基尼指数 D(D,A) 定义为 : GGIIIIII DD, AA = DD 11 DD GGGGGGGG DD 11, AA + DD 22 DD GGGGGGGG DD 22, AA 数据集内包含的类别越杂,GINI 指数就越大 DD 22

46 2018/5/4 49 CART (Classification And Regression Tree, 1984) CART 决策树生成算法 输入 : 训练数据集 D, 停止计算条件根据训练数据集, 从根节点开始, 递归地对每个节点进行以下操作, 构建二叉决策树 : 1 计算现有特征对数据集 D 的基尼指数 此时, 对每一个特征 A, 对其可能取的每一个值 a, 根据样本点对 A=a 的测试为 是 或 否 将 D 分割为 D1 和 D2 两部分, 计算 A=a 时的基尼指数 2 在所有可能的特征 A 以及它们可能的切分点 a 中, 选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点, 依最优特征与最优切分点, 从现节点生成两个子节点, 将训练数据依特征分配到两个子节点中去 3 对两个子节点递归地调用 12, 直至满足停止条件 算法的停止条件 : 节点中的样本个数小于预定阈值, 或样本集的基尼指数小于预定阈值 ( 样本基本属于同一类 ), 或者没有更多特征

47 2018/5/4 58 CART (Classification And Regression Tree, 1984) 示例 有房者 婚姻状况 年收入 拖欠贷款者 是 单身 125K 否 否 已婚 100K 否 否 单身 70K 否 是 已婚 120K 否 否 离异 95K 是 否 已婚 60K 否 是 离异 220K 否 否 单身 85K 是 否 已婚 75K 否 否 单身 90K 是 图中, 属性有 3 个, 分别是有房情况, 婚姻状况和年收入, 其中有房情况和婚姻状况是离散的取值, 而年收入是连续的取值 拖欠贷款者属于分类的结果 决策树之 CART 算法 Retrieved:

48 2018/5/4 59 决策树之 CART 算法 Retrieved:

49 2018/5/4 60

50 2018/5/4 61 小结 : 决策树算法 ID3, 信息增益,1979 Gain(E1) = H(C) H(C E1) Gain(E3, e1=sunny) = H(C) - H(C E3, e1=sunny) C4.5, 信息增益率,1992 IGR(E1) = Gain(E1) / H(E1) IGR(E1) = [H(C) H[C E1]] / H(E1) CART, 基尼指数,1985 KK GGIIIIII DD = pp kk (11 pp kk ) = 11 pp 22 kk = 11 kk=11 一些问题 分枝有限个, 如何处理连续值属性? 误入歧途, 如何处理过拟合问题? 信息不完整, 如何处理部分样本属性缺失的问题? KK kk=11 KK kk=11 CC kk DD 22

51 2018/5/4 62 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost,1995 流数据挖掘 : 频繁项集 Web 中的数据挖掘

52 2018/5/4 63 分类器的组合 Combining Models It is often found that improved performance can be obtained by combining multiple models together in some way, instead of just using a single model in isolation. 多个分类器组合效果优于单个分类器 For instance, we might train L different models and then make predictions using the average of the predictions made by each model. Such combinations of models are sometimes called committees. 多个分类器组合的权重通过投票机制 ( 委员会 ) 实现 Pattern Recognition and Machine Learning,Christopher M. Bishop Chapter 14. COMBINING MODELS

53 2018/5/4 64 组合多个分类器的一般性问题 弱分类器 : 组合前的每一个分类器 强分类器 : 组合后最后的分类器 每个弱分类器的训练样本集? 相同还是不同, 如果不同如何选取? 每个弱分类器的学习方法? 相同还是不同, 如果不同选取的原则? 各个弱分类器是否相关? 训练样本是相关的? 学习方法是相关的? 如何将训练得到的各弱分类器组合成强分类器?

54 2018/5/4 65 Bagging(Bootstrap aggregating) 思路 bagging 技术的过程 : 假设有一个大小为 n 的训练集 D,bagging 会从 D 中有放回的均匀抽样, 假设用 bagging 生成了 m 个新的训练集 Di, 每个 Di 的大小为 j 由于有放回的进行抽样, 那么在 Di 中的样本有可能是重复的 如果 j=n, 这种取样称为 bootstrap 取样 现在, 可以用上面的 m 个训练集来拟合 m 个模型, 然后结合这些模型进行预测 对于回归问题来说, 我们平均这些模型的输出 ; 对于分类问题来说, 我们进行投票 (voting) bagging 能提升机器学习算法的稳定性和准确性, 它可以减少模型的方差从而避免 overfitting

55 Bagging(Bootstrap aggregating) 思路示意图 2018/5/4 66 首先创建随机训练数据集样本 ( 训练数据集的子集 ) 然后为每个样本建立分类器 最后, 这些多分类器的结果将结合起来, 使用平均或多数投票

56 2018/5/4 67 Bagging(Bootstrap aggregating) 有放回的随机抽样示例 假设有一个训练集 D 的大小为 7, 用 bagging 生成 3 个新的训练集 Di, 每个 Di 的大小为 7, 结果如下表 : 样本索引 Bagging(D1) Bagging(D2) Bagging(D3)

57 2018/5/4 68 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost,1995 流数据挖掘 : 频繁项集 Web 中的数据挖掘

58 2018/5/4 69 Boosting, 思路 Boosting 是一个迭代的过程, 用来自适应的改变训练样本的分布, 使分类器聚焦在那些很难分的样本上 在 Bagging 的过程中, 抽取自主样本集的时候是简单随机抽样, 每个样本被抽到的概率是一样的, 但是 Boosting 算法中给每一个样本赋予一个权值, 每一轮在抽取自助样本集 训练完基分类器之后会对原始样本集做一个分类, 然后跟效果比对, 然后对分错的训练样本, 自动的调节该样本的权值 权值可以用在以下方面 : (1) 可以用作抽样分布, 从原始数据集中选出自助样本集 ( 注意,Bagging 抽样时样本是均匀分布的 ) (2) 基分类器训练时更倾向于用高权值的样本进行训练 分类器组合方法 Bootstrap, Boosting, Bagging, 随机森林 ( 一 ) Retieved:

59 2018/5/4 70 Boosting, 示例 例, 有 10 个样本, 开始时简单随机抽样, 每个样本被抽到的概率是一样的, 都是 1/10, 然后第一轮结束后用得到的模型对该轮数据集中的样本分类, 发现样本 4 被分错了, 就增加它的权值, 这样, 第二轮抽取的时候 4 被抽到的概率增加了, 第三轮也是一样 这样做, 就可以让基分类器聚焦于难被分类的样本 4, 增加 4 被正确分类的几率 分类器组合方法 Bootstrap, Boosting, Bagging, 随机森林 ( 一 ) Retieved:

60 2018/5/4 71 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost,1995 流数据挖掘 : 频繁项集 确定性数据中频繁项集挖掘的相关算法 不确定数据的频繁项集的挖掘

61 2018/5/4 72 AdaBoost (Adaptive boosting), 1995 Adaboost 结构 : 最后的分类器 Y M 是由数个弱分类器 (weak classifier) 组合而成的, 相当于最后 m 个弱分类器来投票决定分类, 而且每个弱分类器的 话语权 α 不一样 Pattern Recognition and Machine Learning,Christopher M. Bishop Chapter 14. COMBINING MODELS

62 2018/5/4 73 初始化样本权重系数 w (1) n AdaBoost 训练数据 :x 1,, x N 对应类别 :t 1,, t N t n { 1, 1} 分类器 :y 1,, y M 第 m 个分类器的误差 J m 第 n 个样本在第 m 个分类器 y m 中的权重 :w (m) n 示性函数 I() 第 m 个分类器的归一化误差 ε m 分类器 y m 归一化误差 ε m 分类器 y m 权重 α m 第 m 个分类器的权重 α m 样本权重系数 w n (1) 更新 Pattern Recognition and Machine Learning,Christopher M. Bishop Chapter 14. COMBINING MODELS

63 2018/5/4 74 AdaBoost 弱分类器示例 Pattern Recognition and Machine Learning,Christopher M. Bishop Chapter 14. COMBINING MODELS

64 2018/5/4 75 随机森林 (Random Forest,1995) 随机森林利用随机的方式将许多决策树组合成一个森林, 每个决策树在分类的时候投票决定测试样本的最终类别 随机森林主要包括下 4 个部分 : 1. 随机选择样本 给定一个训练样本集, 数量为 N, 我们使用有放回采样到 N 个样本, 构成一个新的训练集 2. 随机选择特征 在随机森林中, 不计算所有特征的增益, 而是从总量为 M 的特征向量中, 随机选择 m 个特征,m 可以等于 sqrt(m), 然后计算 m 个特征的增益, 选择最优特征 3. 构建决策树 在随机产生的样本集上使用一般决策树的构建方法, 得到一棵决策树 4. 随机森林投票分类 通过上面的三步走, 得到一棵决策树, 我们可以重复这样的过程 H 次, 就得到了 H 棵决策树 然后来了一个测试样本, 我们就可以用每一棵决策树都对它分类一遍, 得到了 H 个分类结果 这时, 我们可以使用简单的投票机制, 或者该测试样本的最终分类结果

65 2018/5/4 76 小结 : 分类器的组合 多分类器进行组合的目的是为了将单个分类器 ( 也叫基分类器 base classifier) 进行组合, 提升对未知样本的分类准确率,( 依赖于基分类器的分类性能和基分类器之间的独立性 ) 提到组合方法 (classifier combination), 有很多的名字涌现, 如 bootstraping, boosting, adaboost, bagging, random forest 等等 那么它们之间的关系如图 : 注意 :Boosting 中组合在一起的多个分类器是有关联的 : 后一个分类器依赖于前一个分类器 分类器组合方法 Bootstrap, Boosting, Bagging, 随机森林 ( 一 ) Retieved:

66 2018/5/4 77 Do we Need Hundreds of classifiers to Solve Real World Classification Problems? We evaluate 179 classifiers arising from 17 families (discriminant analysis, Bayesian, neural networks, SVM, decision trees, rule-based classifiers, boosting, bagging, stacking, random forests and other ensembles, generalized linear models, nearest neighbors, partial least squares and principal component regression, logistic and multinomial regression, multiple adaptive regression splines and other methods), implemented in Weka, R, C and Matlab, including all the relevant classifiers available today. We use 121 data sets. The classifiers most likely to be the bests are the random forest (RF) versions, the best of which (implemented in R and accessed via caret) achieves 94.1% of the maximum accuracy overcoming 90% in the 84.3% of the data sets. However, the difference is not statistically significant with the second best, the SVM with Gaussian kernel implemented in C using LibSVM, which achieves 92.3% of the maximum accuracy.. Manuel Fern andez-delgado et.al. Do we Need Hundreds of classifiers to Solve Real World Classication Problems?, Journal of Machine Learning Research 15 (2014)

67 2018/5/4 78 The Top 10 Topics in Machine Learning Revisited: A Quantitative Meta-Study, 2017 https://arxiv.org/abs/ The Top 10 Topics in Machine Learning Revisited: A Quantitative Meta-Study, 2017 In our study, we use machine learning in order to find the top 10 topics in machine learning from about 54K abstracts of papers published between 2007 and 2016 in leading machine learning journals and conferences.

68 C4.5 k-means SVM Apriori EM PageRank AdaBoost knn Naive Bayes CART 2007 算法原理 2017 算法实现 Weka, R, C, Matlab 2018/5/4 79 Support vector machine Neural network Data set Objective function Markov random field Feature space Generative model Linear matrix inequality Gaussian mixture model Principal component analysis Hidden Markov model Conditional random field Graphical model Maximum likelihood estimation Clustering algorithm Nearest neighbors Genetic algorithm Latent Dirichlet allocation Gaussian process Markov chain Monte Carlo Top 10 algorithms in data mining Do we Need Hundreds of classifiers to Solve Real World Classication Problems? 2014 The Top 10 Topics in Machine Learning Revisited: A Quantitative Meta-Study. 2017

69 2018/5/4 80 今日内容 : 数据挖掘经典算法概述 教材中有的 Naive Bayes EM K-means SVM knn 决策树 ID3 C4.5 CART 把若干个分类器整合为一个分类器 Bagging Boosting AdaBoost [1995] 流数据挖掘 : 频繁项集 Web 中的数据挖掘

70 2018/5/4 81 谢谢大家!