【趣味】数据挖掘(6)——借水浒传故事，释决策树思路

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

天罡地煞之精彩出笼

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

“….忠义堂上做醮至第七日，…三更，….只听得天上一声响，如裂帛相似，…卷出一块火来，…. 竟钻入正南地下去了。宋江随即叫人将铁锹锄头掘开泥土，…只见一个石碣，正面两侧面各有天书文字….”

于是请出了一位何道士（作为第三方的公证人），口译蝌蚪文，竟是座次排行榜，三十六天罡和七十二地煞赫然在上！

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

疑点重重的蝌蚪文天书

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

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

宋江的训练集

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

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

吴用的决策树

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

（1）建立功勋G（这有利于公平和稳定）；

(2)江湖义气Y（即江湖名气，英雄们就认这条）；

(3）上山前的地位P（后面有揭秘；

（4）文治武功W；

（5）入伙时间T，…,等等。

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

粗精度分类-按功劳分如图1左，分水岭属性取“功劳”，阈值记为g1 。吴用很纠结：不论怎样调节 g1 ，错分率都不为0；换言之，在测试数据上测试，集合地煞1中总有混有少数天罡，而集合天罡1中总混有少数地煞。

于是，退而求其次，吴用找了一个阈值g1，使得平均的错分率比较小。

如果摸着石头过河，可用华罗庚的优选法（穿越时空了），多试几次就成了；

比较规范的是IBM的准则：能使基尼指数（Gini Index）最小的划分是正确的划分。基尼指数公式如下:

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

中精度分类—如图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 等）。