信息检索与数据挖掘 2019/5/522 今日内容：数据挖掘经典算法概述 ·教材中有的 ·Naive Bayes、EM、K-means、SVM、kNN ·决策树 ·ID3 。C4.5 ·CART ·把若干个分类器整合为一个分类器 ·Bagging ·Boosting ·AdaBoost,1995 ·流数据挖掘：频繁项集 。Web中的数据挖掘
信息检索与数据挖掘 2019/5/5 22 今日内容：数据挖掘经典算法概述 • 教材中有的 • Naive Bayes、EM、K-means、SVM、kNN • 决策树 • ID3 • C4.5 • CART • 把若干个分类器整合为一个分类器 • Bagging • Boosting • AdaBoost，1995 • 流数据挖掘：频繁项集 • Web中的数据挖掘
信息检索与数据挖掘 2019/5/523 决策树(Decision Tree) 女儿： 多大年纪了？ 年龄 母亲：26。 <=30 >30 女儿： 长的帅不帅？ 母亲： 挺帅的。 女儿： 收入高不？ 长相 不见 母亲：不算很高，中等情况。 帅或中等 丑 女儿： 是公务员不？ 母亲：是，在税务局上班呢。 收入 不见 女儿：那好，我去见见。 高 中等 低 见 公务 员 不见 如果将所有条件 是 不是 量化，就变成真 正的决策树了 见 不见 存在问题：如何构造决策树（根节点、各级节点如何选）？
信息检索与数据挖掘 2019/5/5 23 决策树（Decision Tree） 女儿：多大年纪了？ 母亲：26。 女儿：长的帅不帅？ 母亲：挺帅的。 女儿：收入高不？ 母亲：不算很高，中等情况。 女儿：是公务员不？ 母亲：是，在税务局上班呢。 女儿：那好，我去见见。 如果将所有条件 量化，就变成真 正的决策树了 存在问题：如何构造决策树（根节点、各级节点如何选）？
信息检索与数据挖掘 2019/5/525 《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 25 示例：训练集、测试集 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/526 两种不同的决策树 Outlook sunny overcast rain 用什么样的规则构造决策树？ Humidity yes Windy normal high true false yes no no yes Temperature hot mild cool Outlook Outlook Outlook sunny rain overcast sunny rain overcast sunny rain overcast no yes Humidity Humidity yes yes Humidity yes high normal high normal high normal no yes Windy yes Windy true false true false no yes no yes
信息检索与数据挖掘 2019/5/5 26 两种不同的决策树 用什么样的规则构造决策树？
信息检索与数据挖掘 2019/5/527 构建决策树的思路 •构建决策树时通常采用自上而下的方法，在每一步 选择一个最好的属性来分裂。 ·“最好”的定义是使得子节点中的训练集尽量的纯。 ·“最好”也可以定义为“不纯度”尽量小。 ·在数据挖掘中，决策树主要有两种类型： ·分类树：输出是样本的类别标签(label) ·回归树：输出是一个实数 回归，为什么称之为回归？ Galton:y=33.73+0.516×
信息检索与数据挖掘 2019/5/5 27 构建决策树的思路 • 构建决策树时通常采用自上而下的方法，在每一步 选择一个最好的属性来分裂。 • “最好” 的定义是使得子节点中的训练集尽量的纯。 • “最好”也可以定义为 “不纯度”尽量小。 • 在数据挖掘中，决策树主要有两种类型: • 分类树：输出是样本的类别标签(label) • 回归树：输出是一个实数 回归，为什么称之为回归？ Galton: y＝33.73＋0.516 x