文档介绍：决策树ID3算法的实例解析
讲座主要内容
嘉兴简介
数据挖掘10大算法
ID3算法
嘉兴——中国共产党的诞生地
上海港
长三角的中心 发达便捷的交通
高速公路网：
“三横三纵三桥”
三个国际空港：
虹桥、浦E '01.
集成挖掘(Integrated Mining)
CBA: Liu, B., Hsu, W. and Ma, Y. M. Integrating classification and association rule mining. KDD-98.
粗糙集(Rough Sets)
Finding reduct: Zdzislaw Pawlak, Rough Sets: Theoretical Aspects of Reasoning about Data, KluwerAcademic Publishers, Norwell, MA, 1992
图挖掘(Graph Mining)
gSpan: Yan, X. and Han, J. 2019. gSpan: Graph-Based Substructure Pattern Mining. In ICDM '02.
18种通过审核的候选算法
数据挖掘10大算法产生过程
三步鉴定流程
18种通过审核的候选算法
算法陈述
数据挖掘10大算法：一览
1
2
3
4
开放式讨论
5
算法陈述
每种算法的陈述包括以下内容:
- a) 算法的概要描述
- b) 算法的应用
- c) 该算法目前和未来的研究方向
数据挖掘10大算法产生过程
三步鉴定流程
18种通过审核的候选算法
算法陈述
数据挖掘10大算法：一览
1
2
3
4
开放式讨论
5
排名
挖掘主题
算法
得票数
发表时间
作者
陈述人
1
分类
61
1993
Quinlan,
Hiroshi Motoda
2
聚类
k-Means
60
1967
MacQueen,
Joydeep Ghosh
3
统计学****br/>SVM
58
2019
Vapnik,
QiangYang
4
关联分析
Apriori
52
1994
Rakesh Agrawal
Christos Faloutsos
5
统计学****br/>EM
48
2000
McLachlan, G
Joydeep Ghosh
6
链接挖掘
PageRank
46
2019
Brin, S.
Christos Faloutsos
7
集装与推进
AdaBoost
45
2019
Freund, Y.
Zhi-Hua Zhou
8
分类
kNN
45
2019
Hastie, T
Vipin Kumar
9
分类
Naïve Bayes
45
2019
Hand,
Qiang Yang
10
分类
CART
34
1984
Dan Steinberg
共有145人参加了ICDM 2019 Panel (会议的专题讨论),并对18种候选算法进行投票，选出了数据挖掘10大算法
ICDM 2019会议的算法投票结果
数据挖掘10大算法
数据挖掘10大算法产生过程
三步鉴定流程
18种通过审核的候选算法
算法陈述
数据挖掘10大算法：一览
1
2
3
4
开放式讨论
5
由算法的原作者和陈述人编写调查表
如何更好地使用这10大算法？
是否需要为这10大算法专门编写一本书？
- 注：该书已出版，参见右图封面。书名为
«The Top Ten Algorithms in Data Mining», 编著者为吴信东和Vipin Kumar
针对这10大算法的任何问题展开讨论
开放式讨论
讲座主要内容
嘉兴简介
数据挖掘10大算法
ID3算法
信息的定量描述
衡量信息多少的物理量称为信息量。
若概率很大，受信者事先已有所估计，则该消息信息量就很小；
若概率很小，受信者感觉很突然，该消息所含信息量就很大。
信息量的定义
根据客观事实和人们的****惯概念，函数f(p)应满足以下条件：
f(p)应是概率p的严格单调递减函数，即当p1>p2， f(p1)<f(p2)；
当p=1时，f(p)=0；
当p=0时，f(p)=∞；
两个独立事件的联合信息量应等于它们分别的信息量之和。
对信息量的 认识理解
信息量的定义
若一个消息x出现的概率为p，则这一消息所含的信息量为
其中，