趣味数据挖掘系列6：借水浒传故事，释决策树思路

决策树 (又称判定树，Decision Tree)是硕、博士生数据挖掘课程要点和难点，教学实践表明，这一章需要数学基础知识多，难得有趣。明知是难点，偏向难点行，再难也要“趣味”一番，从课程PPT中取了一些素材，把漫谈的焦点选在了水泊梁山。

天罡地煞之精彩出笼

水浒传第71回“忠义堂石碣受天文，梁山泊英雄排座次”中，施耐庵有段精彩的描述：

….忠义堂上做醮至第七日，…三更，….只听得天上一声响，如裂帛相似，…卷出一块火来，…. 竟钻入正南地下去了。宋江随即叫人将铁锹锄头掘开泥土，…只见一个石碣，正面两侧面各有天书文字….于是请出了一位何道士(作为第三方的公证人)，口译蝌蚪文，竟是座次排行榜，三十六天罡和七十二地煞赫然在上!

对这段故事。老百姓已耳熟能详。

疑点重重的蝌蚪文天书

该天书疑点重重，可能是宋江授意，吴用作数据挖掘，串通了公证人何道士，密藏于适当地点，在适当的时候，借神明的力量来展示，类似于陈胜吴广之鱼腹藏书，要旨是天予神授。

为揭穿天书的秘密，也为说明 “判定树”要点，下面要作一点故事新编，仅属娱乐性质，不至于引起施耐庵的抗议。

宋江的训练集

在小说中描述的那段时间，李逵武松等沉浸在大碗喝酒的庆祝心态中，颇有政治智慧的宋江一心思考着一个大问题：“梁山泊向何处去”，也思考着山寨的稳定。他找到一个绝妙的抓手(handle)：排座次。排得好，则既稳定山寨，又为招安作组织准备。

宋江给出了训练集和测试集，各含几位典型好汉，要求吴用秘造天书，那时的吴用，简直就是宋江的电脑，他把领导意图表达为下列训练集和测试集，其中，还采取了模糊数据的离散化技术,把属性值规范到[0,1]中，因故事细节年久失传，这里仅能给出示意性数据，用于介绍思路，够了。

吴用的决策树

智多星吴用分析了训练集，计算了列属性的信息增益(其公式参见上篇博文)，按信息增益从大到小的排序,列出了属性序列：

• 建立功勋G(这有利于公平和稳定)
• 江湖义气Y(即江湖名气，英雄们就认这条)，
• 上山前的地位P(后面有揭秘)
• 文治武功W
• 入伙时间T
• …,等等

根据信息增益的次序，取前三个属性，分粗-中-精三个步骤,作了如图1的决策树：

　　粗精度分类-按功劳分

如图1左，分水岭属性取“功劳”，阈值记为g1 。吴用很纠结：不论怎样调节 g1 ，错分率都不为0;换言之，在测试数据上测试，集合 地煞1中总有混有少数天罡，而集合天罡1中总混有少数地煞。于是，退而求其次，吴用找了一个阈值g1，使得平均的错分率比较小。

如果摸着石头过河，可用华罗庚的优选法(穿越时空了)，多试几次就成了;比较规范的是IBM的准则：能使基尼指数(Gini Index)最小的划分是正确的划分。基尼指数公式如下:

相关概念与信息熵有关，稍有点难，阅读时可跳过 。

图1 从左到右，粗、中、高精度的决策树(图可以放大)

中精度分类

如图1中间，把粗分类的叶节点改为 “名气” 节点，即把第一步的结果，按名气再分分成两类(复杂对象可分多类)，用上面说的基尼指数方法，找到合适的分水岭阈值y1和y2 , 这一步完成后，错分率减小了，还是有一点错分，不完美。

高精度分类

如图1右边，把中精度的叶节点改为 “上梁山前的社会地位” 节点，找适当的分水岭阈值p1, p2 ,p3 ,p4 ，把中精度的结果再一分为二。奇迹出现了，不但在训练数据上完全匹配，在测试数据上也完全正确。

此时，吴用才恍然大悟，原来，宋江的训练数据和测试数据暗藏玄机，“上梁山前的社会地位”在提高分类精度时至关重要，宋江提出这样的训练数据，其良苦用心是借这些江湖名流和朝廷叛将，在招安时拉关系，或在谈判时讨价还价。

应用

上述决策树高度为3，有23=8条路径，可改写成8条规则：最右路径R1和最左路径R8如下：

R1：IF (功劳>g1) and (名气>y2) and (上山前地位>p4 ) Then 属于天罡类中的前25%

…..

R8 ：IF (功劳≤g1) and (名气≤y1) and (上山前地位≤p1 ) Then 属于地煞类中的后25%

有了这8条规则，莫说108将，就是108万条好汉，电脑几分钟就可搞定(当然，先要穿越时空);接下来就是收买那位不属于梁山的何道士，未来的第三方公证人，写蝌蚪文和暗埋天书了。

分类程序自动且允许后悔。数据挖掘研究者研究了决策树算法并开发成为有一定通用性的程序，其特色是数据与程序分离，即训练数据和测试数据是可更换的，程序至少有三个模块，：

训练模块

输入一组训练数据和精度要求，决策树程序能自动训练并输出一颗决策树，小问题在几秒钟到几分钟内可完成。如果宋江后悔了，觉得昨天给出的训练集中，某两位英雄的星座应互换，吴用重新录入修改后的训练集，程序在不太长的时间内重新训练出新决策树。这便于决策者试点、摸底和调整政策，例如要做一个XX地区学校排行榜，可以先给一个训练集和测试集试试，不理想，再更换训练集，直到训练出的规则测试合格。

测试模块

给定一组测试数据和一颗决策树，决策树程序能自动测试，计算出测试精度。

应用模块

给定一个含几万甚至上百万个对象的集合和一个测试合格的决策树，程序能在合理的时间内，把对象分类，当对象数上千万或上亿时，时间可能会比较长，人们常用分块，抽样，近似的方法来加速。

决策树的优劣

训练集是老师，决策树是学生，测试集是考官。分类精度的评价与学生的百分制成绩类似：90后为优，80后为良，70后为中，60后及格，很难有百分。要求过分，则导致训练时间太长，决策树高度h(层次数)太多，决策树导出的规则变复杂，且规则数以2h 的趋势增长。

怎样用分类结果作预测

设若后来梁山队伍继续扩大，来了一位新好汉X，按照决策树， 设X被分入天罡类中的前25%。于是，读者也能大致预测X的未来，其行为、功劳、武功，等等，大致应该与同类的林冲，卢俊义相似。

电视观众看谍战片时，常预测剧情的结果，例如，猜测谁是大坏蛋，谁是真英雄，以彰显自己的智力，预测的方法本质上是有意无意地利用常识，对人物进行分类，再预测。

超市在新会员注册收集信息，并分类。用同类老会员的已有消费行为，可预测新会员的消费行为，从而实现对广告或短信息的精准投放，近年，Yahoo提出了一门新学科—计算广告学，其中也常用分类预测技术，当然，新学科还有其它新的亮点。

高考中，经过德智体多方面考察，考生被打上分类标签，如重点，一本，二本，三本;这对于考生的人生有一定预测作用，这种 “一考定终身”的现象不好，有负面效应，但却客观存在。如何缩小其负面效应，是社会学家研究的课题。

毛主席的《中国社会各阶层分析》，是社会科学中进行分类的经典，解决了民主革命时期的敌友我问题，在中国革命中取得了辉煌的成功。

与其他真理一样，决策树有其适合的时空区间，所以要与时俱进，这就引出了动态决策树，是目前受关注的研究课题。

分类技术多种多样。由于分类的重要性，人们研究了各种方法，如 贝叶斯分类，神经网络， 基于关联规则的概念的分类, ….

十大算法的第一名

1978年，Ross J. Quinlan 在斯坦福大学做访问学者时,提出了判定树方法ID3，后来改进成为 C4.5 算法，他的著名专著[1] 被被引用18200+次。

在本系列博文之二中曾经提到，R.Agrowal的关于关联规则的论文被引用了11480+次，是大牛论文;那么，这本专著就应该称为超牛著作了。在2006年，国际数据挖掘界推选十大数据挖掘算法，经过严密的程序，判定树 C4.5 算法名列十大算法之首, 此后，他获得了一系列的殊荣，如2011年 SIGKDD Innovation Award [2](值得一提的是，在这个链接页面还可以下载一些开源软件，如 RapidMiner 等)。

这篇博文内容稍难，可能会使人疲倦。数据挖掘中还有许多领域，如聚类，如公式发现，等等。希望下篇更精彩。

参考文献

[1] . C4.5: Quinlan, J. R. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc.

[2] http://www.kdnuggets.com/2011/08/sigkdd-2011-innovation-award-ross-quinlan.html