数极客首页

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

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

天罡地煞之精彩出笼

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

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

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

疑点重重的蝌蚪文天书

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

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

宋江的训练集

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

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

姓名上山前地位P入伙时间T江湖义气Y建立功勋G文治武功W类别
训练集卢俊义10.50.90.9天罡
柴进0.80.60.80.6…...天罡
….….
朱?武0.40.70.50.6..地煞
燕?顺0.50.60.50.4..地煞
测试集林冲10.9111天罡
李逵0.20.60.90.90.6天罡
….….….
安道全0.50.50.80.6地煞
张?青6454地煞

吴用的决策树

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

  • 建立功勋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

发表评论

评论已关闭。

相关文章