中国科学技术大学：《信息检索与数据挖掘》课程教学资源（课件讲稿）数据挖掘经典算法概述

信息检索与数据挖掘 2019/5/51 5月21日12：00前，提交文献阅读相关素材 6月3日12：00前，提交实验报告及相关素材 信息检索与数据挖掘 补充：数据挖掘经典算法概述 4月29日，补充：概率图及主题模型 5月6日，补充：数据挖掘经典算法概述(1) 5月8日，补充： 数据挖掘经典算法概述(2) 5月13日，第12章Web搜索 5月15日，第13章多媒体信息检索 5月20日，复习 5月22日，同学们文献阅读报告 5月27日，同学们文献阅读报告 6月3日，期末考试【暂定】

信息检索与数据挖掘 2019/5/5 1 信息检索与数据挖掘 补充：数据挖掘经典算法概述 4月29日，补充：概率图及主题模型 5月6日，补充：数据挖掘经典算法概述(1) 5月8日，补充：数据挖掘经典算法概述(2) 5月13日，第12章 Web搜索 5月15日，第13章 多媒体信息检索 5月20日，复习 5月22日，同学们文献阅读报告 5月27日，同学们文献阅读报告 6月3日，期末考试【暂定】 5月21日12:00前，提交文献阅读相关素材 6月3日12:00前，提交实验报告及相关素材

信息检索与数据挖掘 2019/5/52 名词演化 ,数据挖掘(data mining) ·数据库的知识发现(KDD,Knowledge Discovery in Database) ·模式识别(pattern recognition) 。人工智能（Artificial intelligence.) .机器学习(machine learning) ·统计机器学习(statistical learning)

信息检索与数据挖掘 2019/5/5 2 名词演化 • 数据挖掘（data mining） • 数据库的知识发现（KDD, Knowledge Discovery in Database） • 模式识别（pattern recognition） • 人工智能（Artificial intelligence） • 机器学习（machine learning） • 统计机器学习（statistical learning）

信息检索与数据挖掘 2019/5/53 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,2008.Published online:4 December 2007

信息检索与数据挖掘 2019/5/5 3 Top 10 algorithms in data mining, 2007 Xindong Wu, Vipin Kumar, J. Ross Quinlan, et al. Top 10 algorithms in data mining. Knowledge and Information Systems, 14(1):1–37, 2008. Published online: 4 December 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

信息检索与数据挖掘 2019/5/54 数据挖掘十大经典算法 C4.5 CART AdaBoost Naive Bayes Apriori kNN K-Means SVM k-Means SVM C4.5 Apriori EM The Top Ten Algorithms in CART Data Mining EM Naive Bayes PageRank KNN AdaBoost Pagerank c第l2章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

信息检索与数据挖掘 2019/5/5 4 数据挖掘十大经典算法 [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. Pagerank ⊂ 第12章Web搜索 Naive Bayes kNN k-Means SVM EM C4.5 CART AdaBoost Apriori

信息检索与数据挖掘 2019/5/55 今日内容：数据挖掘经典算法概述 。教材中有的 ·Naive Bayes、EM、K-neans、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) ·近似重复检测

信息检索与数据挖掘 2019/5/5 5 今日内容：数据挖掘经典算法概述 • 教材中有的 • 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) • 近似重复检测

信息检索与数据挖掘 2019/5/56 今日内容：数据挖掘经典算法概述 ·教材中有的 ·Naive Bayes、EM、K-means、SVM、kNN ·决策树 ·ID3 。C4.5 ·CART ·把若干个分类器整合为一个分类器 ·Bagging ·Boosting ·AdaBoost,1995 ·流数据挖掘：频繁项集 。Web中的数据挖掘

信息检索与数据挖掘 2019/5/5 6 今日内容：数据挖掘经典算法概述 • 教材中有的 • Naive Bayes、 EM、 K-means、SVM、kNN • 决策树 • ID3 • C4.5 • CART • 把若干个分类器整合为一个分类器 • Bagging • Boosting • AdaBoost，1995 • 流数据挖掘：频繁项集 • Web中的数据挖掘

信息检索与数据挖掘 2019/5/57 《Machine Learning.》,TomM.Mitchell,1997,第3章例子 示例：训练集、测试集 训练集 outlook temperature humidity windy play 统计了14天的气象数据（指标 sunny hot high FALSE no 包括outlook,temperature, sunny hot high TRUE no humidity,windy),并已知这 overcast hot high FALSE yes 些天气是否打球(play)。如果 rainy mild high FALSE yes 给出新一天的气象指标数据 rainy cool normal FALSE ves :sunny,cool,high,TRUE,判断 rainy cool normal TRUE no 一下会不会去打球。 overcast cool normal TRUE ves sunny mild high FALSE 这是个二分类问题 no sunny cool normal FALSE yes rainy mild normal FALSE 测试集 yes sunny mild normal TRUE outlook yes sunny mild high TRUE temperature cool overcast ves overcast hot normal FALSE humidity yes high rainy mild high TRUE no windy FALSE

信息检索与数据挖掘 2019/5/5 7 示例：训练集、测试集 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 统计了14天的气象数据(指标 包括outlook，temperature， humidity，windy)，并已知这 些天气是否打球(play)。如果 给出新一天的气象指标数据 :sunny,cool,high,TRUE，判断 一下会不会去打球。 outlook sunny temperature cool humidity high windy FALSE 测试集 训练集 这是个二分类问题 《Machine Learning》, Tom M.Mitchell, 1997, 第3章例子

信息检索与数据挖掘 2019/5/58 朴素贝叶斯分类求解 ▣顾：Naive Bayes text classification ·在文本分类中，我们的目标是找出文档最可能属于 的类别。对于NB分类来说，最可能的类是具有 MAP估计值的结果cmap: Cmap arg max P(cld)=arg max P(c)P(tklc) cEC ceC 1≤k≤nd 如何估计参数P(c)及P(tklc)? P(c)=N. P(tc)= T ∑remI ·零概率问题→平滑 Tct +1 Tct +1 p(tc)=∑rev(Tr+ ）(∑tev Tct)+B

信息检索与数据挖掘 2019/5/5 8 朴素贝叶斯分类求解 回顾：Naive Bayestext classification • 在文本分类中，我们的目标是找出文档最可能属于 的类别。对于NB 分类来说，最可能的类是具有 MAP估计值的结果cmap： • 如何估计参数Pˆ(c)及Pˆ(tk |c ) ？ • 零概率问题平滑

信息检索与数据挖掘 2019/5/59 朴素贝叶斯分类器→概率图 El(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(EI C)P(E2 CP(E3 CP(E4 C) Graphical Cmap=arg max P(cld)=arg max P(c)P(tklc) cEC cEC Model 1<k≤nd C E4 E1 E2 E3

信息检索与数据挖掘 2019/5/5 9 朴素贝叶斯分类器概率图 独立性的假设 Graphical Model C E2 E3 E4 E1 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)

信息检索与数据挖掘 2019/5/510 朴素贝叶斯分类求解 El: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 6 2 9 5 overcast 4 0 mild 4 2 normal 6 1 true 3 3 rainy 3 2 cool 3 1 测试集 outlook sunny Bayes公式：P(cle)→P(c)P(elc) temperature cool e ={el=sunny,e2=cool,e3-high,e4-false) humidity high windy FALSE P(c=yesle)P(c=yes)P(E1lc-yes)P(E2|c-yes)P(E3c-yes)P(E4c-yes) P(c=nole)P(c=no)P(E1c=no)P(E2c=no)P(E3c=no)P(E4c=no) P(c-yesle)*P(E)=9/14×2/9×3/9×3/9×3/9=0.0053 c=no P(c=nole)*P(E)=5/14×3/5×1/5×4/5×3/5=0.0206

信息检索与数据挖掘 2019/5/5 10 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 6 2 9 5 overcast 4 0 mild 4 2 normal 6 1 true 3 3 rainy 3 2 cool 3 1 P(c=yes|e)*P(E)=9/14×2/9×3/9×3/9×3/9=0.0053 P(c=no|e)*P(E)=5/14×3/5×1/5×4/5×3/5=0.0206 outlook sunny temperature cool humidity high windy FALSE 测试集 Bayes公式：P(c|e)  P(c)P(e|c) e = {e1=sunny, e2=cool, e3=high, e4=false} c=no 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) 朴素贝叶斯分类求解