数据的背后 闵帆 博士·副教授 漳州师范学院粒计算重点实验室 砺志楼414 作业：fjzsroughsets@163.com 答疑：周四全天（包括晚上） http://grc.fjzs.edu.cn/~fmin/ 1

数据库表Weather No. Outlook Temperature Humidity Windy Play 1 sunny hot high false N 2 true 3 overcast P 4 rain mild 5 cool normal 6 7 8 9 10 11 12 13 14

问题 有多少种可能的组合？ 试比较记录No. 1与No. 2，可得到什么结论？ 试比较记录No. 5与No. 6，可得到什么结论？

第一章 决策树 令Play为决策属性，以 Outlook -> Temperature -> Humidity -> Windy 的顺序构造一棵决策树

决策树 Outlook Sunny Overcast Rain Temperature Hot Cool Mild N P Humidity Normal High Windy False True

课堂练习 以Temperature -> Outlook -> Windy -> Humidity 与 Humidity -> Windy -> Temperature -> Outlook 的顺序各构造一棵决策树

问题 不同的顺序导致决策树的大小是否相同？ 不同的决策树进行分类的效果是否相同？ 试构造一个新实例，它导致分类结果不同。

讨论 决策树越大越好还是越小越好？ Occam’s razor（上网搜索） 复杂的模型导致过度拟合，简单模型则有更好的归纳能力

课堂练习 构造一棵最小的决策树，不同的分支可用不同属性

最小决策树 Outlook Sunny Overcast Rain Humidity High Normal N P Windy False True

ID3算法 Step 1. 选择合适的属性，使其信息增益最大； Step 2. 根据该属性将数据分成几个子集；

信息增益计算方法 选择属性时不需要计算I(p, n)，因为对于不同属性该值相同

Congratulations! 你已经掌握了数据挖掘最重要的算法！

作业2 Weka的安装与使用 下载JDK, Weka 安装 运行Weka，测试数据集Weather.nomimal

运行选项 Classifier: trees -> Id3 Test option: Using training set

结果 outlook = sunny | humidity = high: no | humidity = normal: yes outlook = overcast: yes outlook = rainy | windy = TRUE: no | windy = FALSE: yes

Woooo! 你已经能用决策树来分析自己的数据！ 问题：分析的效果如何？

训练与测试 用一部分数据来训练分类器（决策树） 另外的数据来测试该分类器的效果

iris.nominal.arff运行结果 Test option: Percentage split 60% === Confusion Matrix === a b c <-- classified as 12 0 0 | a = Iris-setosa 0 11 2 | b = Iris-versicolor 0 0 10 | c = Iris-virginica

连续属性值 用C4.5（J48） 选择合适的断点（离散化）

iris.arff运行结果（树） 66%训练，其余测试 petalwidth <= 0.6: Iris-setosa (50.0) petalwidth > 0.6 | petalwidth <= 1.7 | | petallength <= 4.9: Iris-versicolor (48.0/1.0) | | petallength > 4.9 | | | petalwidth <= 1.5: Iris-virginica (3.0) | | | petalwidth > 1.5: Iris-versicolor (3.0/1.0) | petalwidth > 1.7: Iris-virginica (46.0/1.0)

iris.arff运行结果（准确率） === Confusion Matrix === a b c <-- classified as 15 0 0 | a = Iris-setosa 0 19 0 | b = Iris-versicolor 0 2 15 | c = Iris-virginica

作业3 专业数据分析 构造你所学专业数据 用ID3或C4.5分析 上传源数据与运行结果

参考文献 [1] J.R. Quinlan, Induction of Decision Trees, Machine learning 1: 81-106, 1986 (被引用次数9054)

第二章 属性约简与属性值约简 属性约简是粗糙集的一个重要问题 动机 删除冗余属性以加快学习速度，提高分类器精度（多数属性约简工作的目标） 减少数据获取的代价，即测试代价（闵帆的最新研究重点）

决策表的属性约简 在Weather决策表中，哪些属性去掉后，不影响分类器（如决策树）的生成？

数据库表Weather No. Outlook Temperature Humidity Windy Play 1 sunny hot high false N 2 true 3 overcast P 4 rain mild 5 cool normal 6 7 8 9 10 11 12 13 14

删除Windy No. Outlook Temperature Humidity Play 1 sunny hot high N 2 8 mild 11 normal P 9 cool 4 rain 14 10 5 6 7 overcast 12 13 3

删除Humidity No. Outlook Temperature Windy Play 1 sunny hot false N 2 true 8 mild 11 P 9 cool 4 rain 10 14 5 6 7 overcast 12 13 3

删除Temperature ?

删除Outlook ?

讨论 哪些属性可以被约简？ 有哪些约简？ {Outlook, Humidity, Windy} {Outlook, Temperature, Windy} 可否有多个属性被同时约简？

最小约简 属性数量最少的约简被称为最小约简 Zoo有33个约简，最小的有5个属性，最多的有7个 { a2, a3, a5, a7, a12 } { a0, a2, a5, a7, a10, a12 } { a0, a2, a5, a6, a9, a11, a12 } { a0, a2, a5, a7, a11, a12 } ......

最小测试代价约简 假设各属性的测试代价如下： 哪个约简为最小代价约简？ Outlook Temperature Humidity Windy ￥1 ￥2 ￥3 ￥4 哪个约简为最小代价约简？

问题 为什么要找最小约简？ 为什么要找最小测试代价约简？ 两个问题有什么关系？

核属性 包含在所有约简中的属性 本例中为{Outlook, Windy}

属性值约简 把某属性值设为“不关心”，用*表示

获得的特殊决策表 把某属性值设为“不关心”，用*表示 No. Outlook Temperature Windy Play 1 sunny hot false N 2 true 8 mild 11 P 9 cool 4 rain 10 14 5 6 7 overcast 12 13 3 把某属性值设为“不关心”，用*表示

生成规则集合（课堂演示） 把某属性值设为“不关心”，用*表示 No. Outlook Temperature Windy Play 1 sunny hot false N 2 true 8 mild 11 P 9 cool 4 rain 10 14 5 6 7 overcast 12 13 3 把某属性值设为“不关心”，用*表示

Yes! 你已经掌握了基于属性值约简的规则生成算法！

最新进展 带测试代价约束条件的属性约简 由于代价原因，无法获得一个真正的约简

LEM2 算法 在Rses中使用LEM2算法生成规则集合。

参考文献 [1] Z. Pawlak, “Rough sets”, International Journal of Computer and Information Sciences, 11: 341-356, 1982. (被引用次数6887) [2] A. Skowron and C. Rauszer, “The discernibility matrics and functions in information systems”, Intelligent Decision Support: 331-362, 1992. [3]F. Min, H, He, Y. Qian, and W. Zhu, “Test-cost-sensitive attribute reduction”, Information Sciences, vol. 181, Issue 22, pp. 4928-4942, November 2011. (Most read)