科学网—标签 - 趣味数据挖掘

相关帖子	版块	作者	回复/查看	最后发表

热度 31 tangchangjie 2012-4-10 08:53

数据挖掘中的趣味哲学---趣味数据挖掘之十二 (唐常杰）想用趣味的方式给《趣味数据挖掘系列》做一个哲学的总结，哲学常较深奥，深则难得有趣。因为选题含原生态冲突，写起来就费思量。拟借用一个交通肇事频率分析的例子，又百语千言，颇难开头。硬着头皮 Try ，还是从故事讲起，很久很久以前， It was long long ago… 1 文本数据挖掘的老祖宗，实事求是的践行者汉代的班固在描述汉武帝之二哥刘德时写到： “ 修学好古，实事求是。 … 留其真 ” ，还称赞这位皇二兄（兼河间献王）“求真是”，“留其正本”。（《汉书 • 河间献王传）。用今天数据挖掘课堂上的语言来描述：汉初学者在研究汉以前的文化时，遇到了困难，包括文献不完整，数据冲突，数据有偏颇（与始皇焚书、战乱等诸多原因有关），等等。刘德在研究中，收集了尽可能多的先秦诸子文献做挖掘对象，再去粗存精、去伪存真，对不完整的文本数据进行了人工挖掘。这是“实事求是”见诸于文字的最早记载。可见，“实事求是”不论是作为原则、方法，还是作为成语，从它诞生起，就与数据挖掘有深刻的联系。很多学者追崇实事求是，如清代学者钱大昕提出“实事求是，护惜古人之苦心，可与海内共白”，戴震倡导“实事求是，不偏主一家”，等等，但应用领域都限于历史文献研究。在《改造我们的学习》中，毛泽东的一段话普及且推广了这一思想：“ ‘实事’就是客观存在着的一切事物，‘是’就是客观事物的内部联系，即规律性，‘求’就是我们去研究”，把实事求是(即数据挖掘）的应用领域从历史性文本的挖掘推广到了广谱对象的分析与挖掘。 2 交通肇事频率分析中的“实事求是” 数据挖掘系统认定：真理蕴含在真实完整的数据中。表 1给出了示意了一组交通肇事记录，是为说明方法的示意性数据，共 10000 行。数据挖掘系统和传统专家系统在处理这一组数据的观点和方法有何不同呢？编号安全状况车速 0000 安全常速 0001 肇事快 0002 肇事常速．．．．．．．．． 9999 安全快表 1 一组关于交通肇事的示意性数据表 1 示意了数据的格式（结构），没有写全 10000 行（枯燥的）数据，需对数据的宏观性质的做些补充说明（或假定）： (1) 数据已经做了核实和清理，是可信的数据，是较丰富的数据； ( 2) 10000 次行车记录中，快车有 2000 次，常速 8000 次，共肇事 140 次，肇事记录中有70次是快车。比较老旧的的专家系统的处理方法 : 设先已把若干交通管理专家的（历史）经验表达到知识库。专家系统在知识库中查到了一条权值很高的、很著名的历史经验 :“ 十次肇事九次快 ” ，专家系统得出下列规则： R1 ： If 肇事 Then 开了快车，置信度 90% 遗憾的是，相对于这一组数据，这个比较老旧的专家系统犯了经验主义错误 , 有点类似于刻舟求剑，舟已行矣，而剑不行，求剑若此，不亦惑乎？。（一些新的专家系统明白了这一点，向数据挖掘学习，已有改进）。数据挖掘系统的处理步骤 1 ：实事求是地挖掘车速和安全之间的关联： (1) 10000 个记录中快车出现 2000 次。所以，该数据库对 “ 快车 ” 事件的支持度 = 2000/10000 =20% ，其中只有 70 次是“快车且肇事”，所以数据库对 “肇事且快车”事件的支持度 =70/10000 = 0.7% ， (2) 共肇事 140 次，肇事记录中有70次是快车，所以： “ 肇事 è 快车 ” 的置信度为70/140=5 0% 。综合（ 1 ）（ 2 ），得到下列关联规则： R2：肇事 -- 快车，支持度 0.7% ，置信度5 0 于是，尊重数据的数据挖掘得到的初步结果（后面还要改进）与传统专家系统的结果不同。数据挖掘系统的处理步骤2：-- 实践是检验真理的标准。数据挖掘的工作还没有完成，还要用另一组测试数据来测试和修正。设测试数据格式与训练数据类似，也是 10000 行。记录号从 10000 号── 19999 号。其中： 10000 次行车记录中，快车有 2000 次，常速 8000 次，共肇事 100 次，肇事记录中有60次是快车上面挖掘得到的初步结论，即规则 R2 ，与这组数据不吻合。解决方法之一是，用增量挖掘技术，把新的 10000 个记录追加到表 1 的数据上，组成新的含 20000 个记录的训练数据（需另找测试数据），演算之：原来的: 10000 次行车记录中，快车有 2000 次，常速 8000 次，共肇事 140 次，肇事记录中有70次是快车追加的： 10000 次行车记录中，快车有 2000 次，常速 8000 次，共肇事 100 次，肇事记录中有60次是快车 ---------------------------------------------------------------------------------------------- 追加后： 20000 次行车记录中，快车有4 000 次，常速16000次，共肇事24 0 次，肇事记录中有130次是快车其中，快车出现 4000 次，快车且肇事共计70+60=130次，所以快车且肇事支持度为130/20000= 0.65% ， 240 次肇事记录中共 130 次是快车的，于是得出下列规则： R3：肇事-- 快车，支持度为 0.65% ，置信度为 130/240=54.1 % 粗看R3，这条修正后的规则比较中庸，细与R1，R2相比，发现 R3 在较大范围，较准确地符合了数据。为什么与老旧专家系统的“十次肇事九次快 ”结论不同呢？，可能是与多年前相比，酒驾和疲劳驾驶的肇事有所增加；挖掘的结论为制定惩戒酒驾和疲驾的法规提供了决策依据。 3 数据挖掘系统坚持真理在数据中上面的交通肇事频率分析中，数据挖掘相信规律就（隐藏）在事实中，数据挖掘的思想和挖掘过程都贯彻了“实事求是”。音乐会上，不同的歌手对同一首歌曲作出不同的理解和演唱技术处理；人们对 “ 实事 ” 的词性和语义也有两种理解和处理。其一，理解为名词， “ 实事 ” 即事实、即数据，毛泽东的那段通俗的解释采用了这一种处理，优点是利于普及和推广。其二，理解“实”为动词，把“实事”视为动宾结构。理由：后面的“求是”是动宾结构，四个字，两个动宾结构，可能更符合古人讲究对仗的文风。 “实”作为动词，即“实证化”，相当于数据挖掘中的数据核实与清理步骤，旨在建立可靠的数据库；而“是”则是潜藏于数据中的规律，即知识， “ 求 ” ，就是发挥主观能动性，挖掘、求证、思考和解释。合起来，用六个字更清楚，“实其事”而“求其是”，就是先做数据收集和数据清理，再作数据挖掘和知识解释。数据挖掘人当然更喜欢第二种解释， “实事求是”，囊括了数据挖掘的全过程，忍不住叹服，汉语成语的语义密度真大！ 4 数据挖掘坚持实践是检验真理的标准，善于改正错误、与时俱进。数据挖掘还要用测试数据来测试初步的结果。测试数据是经过清理核实、“实”化了的数据。当测试数据与系统自己挖掘出的规则冲突时，数据挖掘系统先天性地“ 宁信数据，不信自己 ”，会重新挖掘或增量挖掘、改正错误、与时俱进。数据挖掘软件在事实面前，竟能如此客观和谦虚，殊为难能可贵。如果我们的国家公务员（如统计部门、信访部门、执法部门，...的公务员）都像数据挖掘系统对事实这样地尊重，国家的事情就好办得多，老百姓心情就舒畅得多。 5 数据挖掘 PK 专家系统早期的专家系统假定真理在专家脑中（近来有所改进）。专家系统从人类专家获取知识，传统的三大步骤是：知识获取、知识表达、知识解释，由于在知识获取和知识表达方面的困难，用拟人化的语言描述，近年来专家系统混得似乎不如数据挖掘那样风生水起。专家系统有一点“唯专家” ，如果“唯”过了头，易涉嫌唯心；数据挖掘有一点“唯数据”，如果“唯” 过了头，容易走向“机械”或呆板；二者各有长短，最近似乎有取长补短，走向融合的意向。从哲学角度看 , 数据挖掘作为软件系统，先天性地“实事求是”，坚持实践是检验真理的标准，尊重事实，善于修正错误和与时俱进，具有很好的先天哲学素养。可能这也是近年来数据挖掘比较成功，而专家系统不太成功的哲学原因吧。（《趣味数据挖掘系列》暂时在此告一段落。）相关博文 1“ 被打 ” 和 “ 北大 ” 的关联 --- 趣味数据挖掘系列之一 2 烤鸭、面饼和甜面酱之朴素关联 --- 趣味数据挖掘系列之二 3 一篇它引上万的大牛论文与数据血统论 -- 趣味数据挖掘之三 4 巧挖科学博客之均击量公式，兼谈干预规则 ---- 趣味数据挖掘之四 5 听妈妈讲过去的故事，分房与分类 ----- 趣味数据挖掘之五 6 借水浒传故事，释决策树思路 --- 趣味数据挖掘之六 7 团拜会和鸡尾酒会上的聚类 — 趣味数据挖掘之七 8 农村中学并迁选址、 K- 平均聚类及蛋鸡悖论 -- 趣味数据挖掘之八 9 灯谜、外星殖民、愚公移山和进化计算--- 趣味数据挖掘之九 10 达尔文、孟德尔与老愚公会盟：基因表达式编程-- 趣味数据挖之十 11 十大算法展现辉煌，十大问题引领锦绣--- 趣味数据挖掘之十一 12 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二假日聚会，戏说云物人海 -- 漫谈大数据其它系列博文的入口唐常杰博客主页科学博客主页

个人分类: 科普札记|19589 次阅读|66 个评论

农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八

热度 33 tangchangjie 2012-1-5 08:35

农村中学并迁选址、K- 平均聚类及蛋鸡悖论 -- 趣味数据挖掘之八（唐常杰）本文从农村中学并迁选址问题出发，介绍了数据挖掘十大算法中位居第二的 K- 平均聚类，后又借用牛顿迭代原理，议论蛋鸡悖论。从过去的数据挖掘课程PPT取些素材，改成这篇博文（比较省事），也许对此课程的新教师有用。虽涉嫌双重班门弄斧（生物、数学），有趣就行，不当之处，请专家指正。 1 一道应用题：用聚类技术为农村中学并迁选址为提高教学质量，一些边远农村中学并校迁址。考察图 1，在 (x,y) 的村庄有m 名学生，表达为在(x,y)处部署一个质量为m的质点。如果把全部质点聚成若干簇，学校新址选在这些簇的质心，则校址向学生多的居住点倾斜，照顾了大多数人，学生上学的交通里程从总体上得到优化，也有助于减少校车事故。（中学物理指出，一组质点的质心坐标是它们坐标的加权平均，其公式不再赘述）。 2 似乎是妙想，却涉嫌蛋鸡悖论图 1使人联想到宇宙大爆炸后星云逐渐凝聚成为星系的过程。人眼能看出图1中大致有7- 9个簇，每个簇中选出质心，标为红色，如果远处飘来一颗流星，可能会向最近的簇心靠拢。求质心位置用（加权）平均，故由此引出的算法称为 K-平均算法,由 J.MacQueen于1967年提出。初听起来不错，却似有悖论之纠结。还没有开始聚簇，怎样知道哪些质点是一簇而在一起选举质心？到底是先有簇再选质心，（先有鸡），还是先有质心再聚簇（先有蛋）？上篇博文讲过，聚类对象是主动的，那么，主动的质心会问：“我是属于这一簇吗？，我该这里参加选举吗？，而没有质心，一个普通质点又怎样知道自己聚向何方？若干教科书在这一内容前没有分析这个纠结，使初学者不易理解 K-平均算法之微妙，反而错误地以为该算法笨笨的，慢慢的。破解悖论纠结的迭代法生活中常有这样的纠结：例如职称与科研项目（无高级职称，不易申请项目，无项目，不易晋升职称）、居民新区的服务点与人气、申请博士点与成果，等等。 300多年前的牛顿（ 1643-1727）为我们准备了破解类似纠结的迭代原理：先干起来再改进，宽容地从近似值开始，逐步求精。为不干扰主题，我们先用此方法，后回头再看牛顿迭代原理，给一点演绎，并试图说明：在自然界中，先有蛋的可能性比先有鸡的可能性大。 3 用聚类为农村中学迁移选址： K-平均聚类图 2 给出了 k- 平均法的轮廓，是在韩家炜教授等著名专家撰写的书（参见文献）中的一个图添加了一簇而成，赋以了本应用题环境的语义，含 5 个子图分别标记为 A 、 B 、 C 、 D 、 E ，下面一一道来，（如觉得较难，可跳到第4节看课堂游戏、看牛顿迭代原理与蛋鸡悖论）。为不使读者晕头，质点加上了颜色：浅蓝、深蓝和黄色。注意，问题本身并不给颜色（否则可以根据颜色聚类了），这正如侦探小说，为不使读者晕头，先告诉了谜底，然后再演绎侦破过程，精彩在过程中，而不在于结果。 A图：播种质心（插红旗），据观察或先验知识，确定聚簇数 K=3 。（此法之缺点，需先验知识 K=3 ），随意播种三质心（尽量分散），作质心初始位置。黄色和深蓝阵营的质心在现有居民点，是实体质心，用红色标志，浅蓝阵营是虚拟质心，不在实体居民点，插上红旗，虚实质心无本质区别，都是近似的校址参考点。 B图：就近入学（就近入簇） A 给出了三个近似校址，学生按就近入学原则聚簇，去掉虚拟质心，得到了 B图，一簇内的学生可能会到同一校学习，（还待迭代调整）。 C 图：在 B的基础上，重新选举质心选举即计算，虚拟质心标上红色，实体质心的插上红旗，得到 C图。其中，黄色阵营中是实体质心；深蓝和浅蓝阵营的质心为虚拟（红点）。注意，如标注框中提示，有两个点将转学到它校，夸张一点，“叛离”原簇。 D图：舍远求近，就近入学在 C的基础上，就近入学，去掉虚拟质心，得到了 D 图。如标注框中提示，为了响应“就近入学（簇）”的号召，有一个点已从深蓝“转学”到浅蓝，有一个点已从“浅蓝”转学到深蓝。 E 图：重新选举质心在 D的基础上，重新选举（计算）质心，标红色或红旗，得到 E图。黄色阵营的质心与中间居民点重合，是实体质心，另两阵营的质心是虚拟的，表示在实际居民点之外的新址建校。此问题较简单，到此，选出的质心作为新校址，中间发生了两个质点的对簇的“背叛”，E图已较合理，停止并输出结果。循环控制：如果聚类精度达不到要求，就要从 E图转到 B图，开始新一轮的迭代。迭代终止条件：三者之一：达预设迭代次数，例如 100次；或质心点都成为不动点；或预设聚类精度。竖起招兵旗，就有吃粮人。回顾A图：随意竖起种子旗，就有质点加入。三国时期，曹操，刘备集团，买粮买兵器竖旗，白手起家，颇像A图中的虚拟质心；而原来就有军队的孙坚孙策，就像实体质心。后来几十集团竞争，兼并加招降纳叛，最后聚成了三大集团。因瑕得福。 K-平均算法有一瑕疵：需要先验的簇数 K，引来若干批评和改进，殊不知，这正是“算法如此多娇，引无数英雄竟改进”，增加了其影响力，也增加了文献的它引率。而在实践中，这一瑕疵不是大问题，Why? 请问，实践中有过不经人的调查研究，而只靠机器决策的事吗？在中学并迁选址问题中，有调查、有经费约束，这自然就确定了簇数。此算法实用且高效，因而高居十大算法之二。此外，不要以为K平均算法就如这个科普故事这么简单，K平均的收敛性证明是相当复杂而艰难的，读读文献，可以体会这个艰苦的历程和作者高超的技巧。 4 龙星计划和杨强教授的课堂游戏 2007年，香港科技大学杨强教授在川大的主讲一周龙星计划课程《数据挖掘和机器学习》。在讲解 K-平均算法时，杨强教授导演了一场课堂游戏：图 2中的点对应于课堂上的学生，簇数 K=3，关键步骤是：（a)迭代过程中，得到新簇后，每簇同学重新选举新质心，新质心站起来； (b)基于新的质心，同学们重新就近入簇(不移动座位，只是心里认定自己聚在那一簇），如果预先准备了簇号牌，就举起相应的簇号牌。如此经过3-5次迭代，就收敛了，收敛的标志是质心点成为不动点。同学们在游戏中，领悟了聚类的深刻道理，也看到迭代过程宽容地从随意的近似值开始，竟然能很快收敛。（注：龙星计划课程是国家自然科学基金委资助的学术活动，邀请国际知名的华人计算机科学家回国举办专题讲座。2006年，文献的作者韩家炜教授来川大讲学，考察了我们的课程、环境、条件、研究基础等，鼓励我们竞争申请龙星计划，次年竞争成功）。 5 破解蛋鸡悖论的利器 --迭代原理前面说过，蛋鸡纠结常见于科研生活中，如职称与科研项目、如居民新区的服务点与人气，如申请博士点与成果，等等。300多年前的牛顿（ 1643—1727 ）为我们准备了破解蛋鸡悖论纠结的原理。图 3 左展示了用牛顿弦线法迭代地求 f(x)=0 的近似根时，从第 n-1 步到第 n+1 步的迭代过程，（假定相关条件都满足，如函数连续可微，二阶导数为正等等）。把曲线上的点 P n-1 、 P n ， P n+1 比喻为蛋，把横轴上 X n-1 、 X n ， X n+1 标示的点比喻为鸡。鸡生蛋：从 X k 找 P k： P k =(X k ,f(x k )); 注意，进化序列 P n-1 、 P n ， P n+1，沿函数曲线逼近鸡（欲求的根）；蛋生鸡： P k 产生 X K+1 如下：作弦线 P k P’ ，交横轴于（ X k+1 ,0 ），得到了 X k+1 ；注意，进化序列 X n-1 、 X n ， X n+1 ， … 沿X轴逼近鸡。如果 X k 和 P k 是自然界的原鸡与原鸡蛋，有下列命题： X k 成功进化为鸡的必要条件：所产生的海量生殖细胞中，一半以上（这也是海量) 充分接近鸡的生殖细胞; P k 成功进化为鸡蛋的充要条件：只要这一个蛋孵出的是鸡。（数量上要求少）。 6 先有鸡还是先有蛋，阈值说了算，图 2 右中有个紫色的阈值园，不管是鸡序列，还是蛋序列。谁先进入阈值园，谁就先进化成功。但是阈值园的圆心正是欲求的目标，所以有纠结，知道它存在，但画不出来。数学分析中的柯西收敛原理能解决这个问题。给定一个收敛阈值 ε：如果存在 N ，当 nN, 就有 |P n -P n+1 | ε , 就说蛋序列收敛了（蛋进化为鸡蛋了）；如果存在 N ，当 nN, 就有 |X n -X n+1 | ε , 就说鸡序列收敛了（鸟进化为鸡了）。我们得到一条启发性知识：若逢蛋鸡纠结，请用迭代之法。 7 自然界中，先有蛋的可能性，比先有鸡的可能性大。我们的课题组在做基于基因表达式编程的数据挖掘时，学过一些遗传和变异的常识，做过一些模拟，感觉到自然界中，从原鸡（鸡的祖先）进化到鸡的过程中，先有鸡蛋的可能性，比先有鸡的可能性大。有下列三个原因： (a) 获得性不能遗传，例如原鸡之妈和原鸡之爸割了双眼皮，不会遗传到下一代上。原鸡全身的可能变异中，很小一部分发生在生殖细胞，而发生了这种变异的生殖细胞，还只是是半个生命。 (b)在数量上，生殖细胞的数量比原鸡数大若干个数量级，生殖细胞发生变异的机会比原鸡多，公原鸡和母原鸡受到辐射、化学刺激、或卫星或火箭搭载时（外星人的火箭 atlong ago），可能引起生殖细胞变异；当几个生殖细胞发生变异后，山还是那座山，水还是那湾水，原鸡还是那个原鸡，而不是鸡；来自原鸡爸妈生殖细胞的变异都可汇集在能孵出下一代的蛋（已是一个生命,而不是半个）； (c) 原鸡蛋被生出来后，孵化之前，还可能受到辐射、化学处理、或卫星搭载等等，都可以发生变异；如果图3中阈值园能画出，蛋的序列一旦进入这个阈值园，则称为鸡蛋；原鸡序列一旦进入这个阈值园，则称为鸡。与原鸡相比，原鸡蛋发生变异的机会多,原鸡蛋序列收敛速度更高，在用收敛原理作阈值检查时，满足阈值条件的时间可能会更早。结论：自然界中，先有鸡蛋的可能性大于先有鸡的可能性。这是双重的班门弄斧（生物、数学），有趣就行，请专家指正。参考文献 J.MacQueen, "Some methods for classification and analysis of multivariate observations," in iProc. 5th Berkeley Symp. Mathematical Statistics and Probability, vol.1. Berkeley, CA: University of California Press, 1967, pp. 281-297. K-平均原文.pdf Data Mining: Concepts and Techniques, 2nd ed., Jiawei Han and Micheline Kamber, Morgan Kaufmann, 2006. P P383-464. 有中译本，《数据挖掘，概念和技术》第二版，范明，孟小峰等译，机械工业出版社出版。（目前还是世界各国采用最多的教科书）。相关博文 1 “被打”和“北大” 的关联 --- 趣味数据挖掘系列之一 2 烤鸭、面饼和甜面酱之朴素关联 --- 趣味数据挖掘系列之二 3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之三 4 巧挖科学博客之均击量公式，兼谈干预规则 ---- 趣味数据挖掘之四 5 听妈妈讲过去的故事，分房与分类 ----- 趣味数据挖掘之五 6 借水浒传故事，释决策树思路--- 趣味数据挖掘之六 7 团拜会和鸡尾酒会上的聚类 — 趣味数据挖掘之七 8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八 9 灯谜、外星殖民、愚公移山和进化计算 --- 趣味数据挖掘之九 10 达尔文、孟德尔与老愚公会盟：基因表达式编程--趣味数据挖之十 11 十大算法展辉煌，十大问题现锦绣---趣味数据挖掘之十一 12 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二其它系列博文的入口唐常杰博客主页科学博客主页

个人分类: 科普札记|18332 次阅读|78 个评论

借水浒传故事，释决策树思路---趣味数据挖掘之六

热度 28 tangchangjie 2011-12-22 08:55

借水浒传故事，释决策树思路---趣味数据挖掘之六 (唐常杰）决策树 ( 又称判定树， Decision Tree) 是硕、博士生数据挖掘课程要点和难点，教学实践表明，这一章需要数学基础知识多，难得有趣。明知是难点，偏向难点行，再难也要“趣味”一番，从课程 PPT 中取了一些素材，把漫谈的焦点选在了水泊梁山。天罡地煞之精彩出笼水浒传第 71 回“忠义堂石碣受天文，梁山泊英雄排座次”中，施耐庵有段精彩的描述： “ …. 忠义堂上做醮至第七日， … 三更， …. 只听得天上一声响，如裂帛相似， … 卷出一块火来， …. 竟钻入正南地下去了。宋江随即叫人将铁锹锄头掘开泥土， … 只见一个石碣，正面两侧面各有天书文字 …. ” 于是请出了一位何道士（作为第三方的公证人），口译蝌蚪文，竟是座次排行榜，三十六天罡和七十二地煞赫然在上！对这段故事。老百姓已耳熟能详。疑点重重的蝌蚪文天书该天书疑点重重，可能是宋江授意，吴用作数据挖掘，串通了公证人何道士，密藏于适当地点，在适当的时候，借神明的力量来展示，类似于陈胜吴广之鱼腹藏书，要旨是天予神授。为揭穿天书的秘密，也为说明 “判定树”要点，下面要作一点故事新编，仅属娱乐性质，不至于引起施耐庵的抗议。宋江的训练集在小说中描述的那段时间，李逵武松等沉浸在大碗喝酒的庆祝心态中，颇有政治智慧的宋江一心思考着一个大问题：“梁山泊向何处去？”，也思考着山寨的稳定。他找到一个绝妙的抓手 (handle) ：排座次。排得好，则既稳定山寨，又为招安作组织准备。宋江给出了训练集和测试集，各含几位典型好汉，要求吴用秘造天书，那时的吴用，简直就是宋江的电脑，他把领导意图表达为下列训练集和测试集，其中，还采取了模糊数据的离散化技术 , 把属性值规范到中，因故事细节年久失传，这里仅能给出示意性数据，用于介绍思路，够了。姓名上山前地位 P 入伙时间 T 江湖义气 Y 建立功勋 G 文治武功 W … 类别训练集卢俊义 1 0.5 0.9 0.9 … … 天罡柴进 0.8 0.6 0.8 0.6 …. .. 天罡 …. … …. … … … … 朱武 0.4 0.7 0.5 0.6 … .. 地煞燕顺 0.5 0.6 0.5 0.4 … .. 地煞测试集林冲 1 0.9 1 1 1 天罡李逵 0.2 0.6 0.9 0.9 0.6 天罡 … …. …. …. … … … 安道全 0.5 0.5 0.8 0.6 地煞张青 6 4 5 4 … 地煞吴用的决策树智多星吴用分析了训练集，计算了列属性的信息增益（其公式参见上篇博文），按信息增益从大到小的排序 , 列出了属性序列：（ 1 ）建立功勋 G （这有利于公平和稳定） , (2) 江湖义气 Y （即江湖名气，英雄们就认这条）， (3 ）上山前的地位 P （后面有揭秘），（ 4 ）文治武功 W ，（ 5 ）入伙时间 T ， …, 等等。根据信息增益的次序，取前三个属性，分粗 - 中 - 精三个步骤 , 作了如图 1 的决策树：粗精度分类 - 按功劳分如图 1 左，分水岭属性取“功劳”，阈值记为 g 1 。吴用很纠结：不论怎样调节 g 1 ，错分率都不为 0 ；换言之，在测试数据上测试，集合地煞 1 中总有混有少数天罡，而集合天罡 1 中总混有少数地煞。于是，退而求其次，吴用找了一个阈值 g 1 ，使得平均的错分率比较小。如果摸着石头过河，可用华罗庚的优选法（穿越时空了），多试几次就成了；比较规范的是 IBM 的准则：能使基尼指数（ Gini Index ）最小的划分是正确的划分。基尼指数公式如下: 相关概念与信息熵有关，稍有点难，阅读时可跳过。图 1 从左到右，粗、中、高精度的决策树（图可以放大）中精度分类 — 如图 1 中间，把粗分类的叶节点改为 “名气” 节点，即把第一步的结果，按名气再分分成两类（复杂对象可分多类），用上面说的基尼指数方法，找到合适的分水岭阈值 y 1 和 y 2 , 这一步完成后，错分率减小了，还是有一点错分，不完美。高精度分类如图 1 右边，把中精度的叶节点改为 “上梁山前的社会地位” 节点，找适当的分水岭阈值 p 1 , p 2 ,p 3 ,p 4 ，把中精度的结果再一分为二。奇迹出现了，不但在训练数据上完全匹配，在测试数据上也完全正确。此时，吴用才恍然大悟，原来，宋江的训练数据和测试数据暗藏玄机，“上梁山前的社会地位”在提高分类精度时至关重要，宋江提出这样的训练数据，其良苦用心是借这些江湖名流和朝廷叛将，在招安时拉关系，或在谈判时讨价还价。应用上述决策树高度为3，有2 3 = 8 条路径，可改写成 8 条规则：最右路径 R1 和最左路径R8如下： R1 ： IF （功劳 g 1 ） and （名气 y 2 ） and ( 上山前地位 p 4 ) Then 属于天罡类中的前 25% ….. R8 ： IF （功劳 ≤ g 1 ） and （名气 ≤ y 1 ） and ( 上山前地位 ≤ p 1 ) Then 属于地煞类中的后 25% 有了这 8 条规则，莫说 108 将，就是 108 万条好汉，电脑几分钟就可搞定 ( 当然，先要穿越时空 ) ；接下来就是收买那位不属于梁山的何道士，未来的第三方公证人，写蝌蚪文和暗埋天书了。分类程序自动且允许后悔。数据挖掘研究者研究了决策树算法并开发成为有一定通用性的程序，其特色是数据与程序分离，即训练数据和测试数据是可更换的，程序至少有三个模块，：训练模块输入一组训练数据和精度要求，决策树程序能自动训练并输出一颗决策树，小问题在几秒钟到几分钟内可完成。如果宋江后悔了，觉得昨天给出的训练集中，某两位英雄的星座应互换，吴用重新录入修改后的训练集，程序在不太长的时间内重新训练出新决策树。这便于决策者试点、摸底和调整政策，例如要做一个 XX地区学校排行榜，可以先给一个训练集和测试集试试，不理想，再更换训练集，直到训练出的规则测试合格。测试模块给定一组测试数据和一颗决策树，决策树程序能自动测试，计算出测试精度。应用模块给定一个含几万甚至上百万个对象的集合和一个测试合格的决策树，程序能在合理的时间内，把对象分类，当对象数上千万或上亿时，时间可能会比较长，人们常用分块，抽样，近似的方法来加速。决策树的优劣训练集是老师，决策树是学生，测试集是考官。分类精度的评价与学生的百分制成绩类似： 90后为优， 80后为良， 70后为中， 60后及格，很难有百分。要求过分，则导致训练时间太长，决策树高度h（层次数）太多，决策树导出的规则变复杂，且规则数以2 h 的趋势增长。怎样用分类结果作预测设若后来梁山队伍继续扩大，来了一位新好汉 X ，按照决策树，设 X 被分入天罡类中的前 25% 。于是，读者也能大致预测 X 的未来，其行为、功劳、武功，等等，大致应该与同类的林冲，卢俊义相似。电视观众看谍战片时，常预测剧情的结果，例如，猜测谁是大坏蛋，谁是真英雄，以彰显自己的智力，预测的方法本质上是有意无意地利用常识，对人物进行分类，再预测。超市在新会员注册收集信息，并分类。用同类老会员的已有消费行为，可预测新会员的消费行为，从而实现对广告或短信息的精准投放，近年， Yahoo 提出了一门新学科 --- 计算广告学，其中也常用分类预测技术，当然，新学科还有其它新的亮点。高考中，经过德智体多方面考察，考生被打上分类标签，如重点，一本，二本，三本；这对于考生的人生有一定预测作用，这种 “一考定终身”的现象不好，有负面效应，但却客观存在。如何缩小其负面效应，是社会学家研究的课题。毛主席的《中国社会各阶层分析》，是社会科学中进行分类的经典，解决了民主革命时期的敌友我问题，在中国革命中取得了辉煌的成功。与其他真理一样，决策树有其适合的时空区间，所以要与时俱进，这就引出了动态决策树，是目前受关注的研究课题。分类技术多种多样。由于分类的重要性，人们研究了各种方法，如贝叶斯分类，神经网络，基于关联规则的概念的分类 , …. 十大算法的第一名 1978 年， Ross J. Quinlan 在斯坦福大学做访问学者时 , 提出了判定树方法 ID3 ，后来改进成为 C4. 5 算法，他的著名专著被被引用 18200 + 次。在本系列博文之二中曾经提到， R.Agrowal 的关于关联规则的论文被引用了 11480 + 次，是大牛论文；那么，这本专著就应该称为超牛著作了。在 2006 年，国际数据挖掘界推选十大数据挖掘算法，经过严密的程序，判定树 C4. 5 算法名列十大算法之首 , 此后，他获得了一系列的殊荣，如 2011 年 SIGKDD Innovation Award （值得一提的是，在这个链接页面还可以下载一些开源软件，如 RapidMiner 等）。这篇博文内容稍难，可能会使人疲倦。数据挖掘中还有许多领域，如聚类，如公式发现，等等。希望下篇更精彩。参考文献 . C4.5: Quinlan, J. R. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc. http://www.kdnuggets.com/2011/08/sigkdd-2011-innovation-award-ross-quinlan.html ; 相关博文 1 “被打”和“北大” 的关联 --- 趣味数据挖掘系列之一 2 烤鸭、面饼和甜面酱之朴素关联 --- 趣味数据挖掘系列之二 3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之三 4 巧挖科学博客之均击量公式，兼谈干预规则 ---- 趣味数据挖掘之四 5 听妈妈讲过去的故事，分房与分类 ----- 趣味数据挖掘之五 6 借水浒传故事，释决策树思路--- 趣味数据挖掘之六 7 团拜会和鸡尾酒会上的聚类 — 趣味数据挖掘之七 8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八 9 灯谜、外星殖民、愚公移山和进化计算 --- 趣味数据挖掘之九 10 达尔文、孟德尔与老愚公会盟：基因表达式编程--趣味数据挖之十 11 十大算法展辉煌，十大问题现锦绣---趣味数据挖掘之十一 12 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二其它系列博文的入口唐常杰博客主页科学博客主页

个人分类: 科普札记|21275 次阅读|61 个评论

听妈妈讲过去的故事，分房与分类-----趣味数据挖掘之五

热度 23 tangchangjie 2011-12-15 09:10

听妈妈讲过去的故事，分房与分类-----趣味数据挖掘之五(唐常杰）　中老年回顾歌曲集中有这样一首歌：月亮在白莲花般的云朵里穿行，晚风吹来一阵阵欢乐的歌声，我们坐在高高的谷堆旁边，听妈妈讲那过去的事情…… 　　歌词美，旋律也美，每当听到它，就仿佛回到了那如歌的岁月。　　此故事的主人公小梅，在上周末也听她母亲讲了的故事。故事中没有月亮、云朵和晚风，却有关于数据挖掘中的分类技术的启示；虽然，现在不再分福利房了，但此故事既回顾历史，也解释了分类技术若干要点，有参考价值。　　　　 1 乔迁之喜引出的故事：上周末，去贺朋友女儿小梅乔迁之喜，漂亮的新房引起小梅之母一阵阵感叹唏嘘，说，当年小梅都两岁了，还带着她住集体宿舍，每逢有人探亲，同室姐妹们自动到仓库暂住几天…. 　　梁山英雄排座次后来，厂里修了一栋两层的砖楼，共18个一套三，厂里搬家动静可大了，搬动了18X6=108家，好像梁山泊英雄排座次：厂级干部搬新房，处长搬厂干之旧房，科长搬处长之旧房，副科长搬科长之旧房，老师傅搬副科长旧房，小梅家以优秀技术员的资格，比水浒传中扈三娘座次略低，从集体宿舍搬到老师傅腾出的旧房。仍令未搬家的群众眼馋，好事者按《水浒传》取外号，编排了36天罡，72地煞,有些天罡年年岁岁搬新房，难怪有些地煞月月天天想升版本。半导体PN结之填空运动雅一点的牢骚来自技术员，有人说，好像半导体三极管的“发射极-基极”PN结上电荷空穴的填充运动，其放大后输出的舆论暗流，在口耳相传中，涌动了半年。　　后来，有了分房委员会，实行公开民主评议分房，才有所改观。　　小梅问母亲，分房委员会是怎样分房的呢？　　小梅母亲的故事细且长；细致中见舆情，罗嗦中有感叹，既忆苦思甜，又鞭笞时弊。故事触动了我的灵感，正好用来解释分类概念与技术，现将故事与术语混合，夹叙夹议，演绎于下。　　　　 2 分房样板：训练集与测试集　　当年有句话：榜样的力量是无穷的。厂长秘书起草了一个分房样板，交给工会分房委员会，征求意见，旨在修改成一个群众满意，领导认可的样板；用数据挖掘的行话描述，要构造一个正确的、用于分类的训练数据集和测试数据集，格式如表1。　　据小梅母亲回忆，当年的样板较大，列数较多，每个车间，科室，不同层次都有，还考虑了贡献、民族、党派、工种，单身，离异，…。下面是示意性格式和数据。其中有些属性（列）与分房关系不大，似有其它意图，为突出问题，这里做了一点夸张，用“身高”和“体重”来代表这类属性。　　　　表1 职工分房计分样板（训练数据和测试数据）格式编号姓名职务工龄贡献计分家庭人口身高体重应住面积（类标签） 1 张三处长 28 6 5 1.7 80 75 (1类 ) 2 李四技术员 20 4 4 1.7 85 45 (4类 ) 3 王五三级技工 10 1 4 1.8 65 33 (5类 ) 4 张 C 工程师 23 3 2 1.7 80 45 (4类 ) 5 李 D 高工 26 6 3 1.7 85 60 (2类 ) 6 王 E 六级技工 20 5 5 1.8 65 50 (3类 ) … …. …. 150 上述表中的每一行是一个申请住房的记录，简单地用住房面积为类标签，当然，标签也可用序号，如1、2、3…等，来等价地代替。　　其中，一部分作为训练集（例如 1—50号），另一部分作测试集（例如51--150号）。　　　　2 训练集相当于教练，训练出的分类公式相当于学生样板比较直观，但不便于推广使用，要从训练数据中挖掘出一个分房（分类）公式，数据挖掘假定真理就在训练集之中，尽管到现在还不知道它将表达陈什么摸样。　　在分类过程中，训练集相当于教练，训练出的公式相当于学生, 如果教师不公正，训练出的公式就不公正。　　　　 3 教考分离，测试集必须独立，如今学校都实行教考分离，同理，由训练数据训练出来的公式，要在另外一批、独立的测试数据上测试。　　有时候，一个不公正的训练集和训练集会复杂得让人看不懂而暗藏玄机，委员会会举手通过，直到最后分房揭晓时，才知道某列某加权因子是为了照顾某某人。　　经过认真核实讨论，能在很大程度上简明化、公正化，使训练数据和测试集基本符合群众利益，自然也会符合好领导的意图。 4 第一个训练结果，删除无用的列--属性选择。 4．1 分房委员会看出了冗余属性问题分房委员会对这个样板初稿，提出了意见。　　(a)“身高”和“体重”，以及类似的若干列，和分房没有大的关系，应该删去。　　(b)“姓名”和分房没有关系，制定分房标准对事不对人，没有姓名，才好讨论。　　人看出了问题，计算机能吗？能。　　 4．2 计算机程序向训练数据学习，也能看出冗余属性问题　　删去这些无关列，行话称为属性选择，旨在选留那些“区分度大”、对分类贡献大的属性。事实上，包含真理的训练数据中就暗含了“哪些列应该删去”的信息. 　　例如，属性精简程序会比较张三与张C ，李四与李D ，王五与王E，发现身高、体重与住房无关；　　计算过程是：计算身高（或体重）的分布，发现相同的身高（或体重）比较均匀地分布在不同类，说明身高（或体重）的熵比较大，或者，对住房分类的贡献不大，用行话，身高（或体重）的信息增益低。根据信息熵原理，写一道到几十行的程序，以训练数据为输入，训练数据训练机器（对称地，机器向数据学习），使之可把信息增益低于指定阈值的属性删去。　　数据挖掘中，属性选择所依据的“信息增益”(Info Gain)公式如下（较难，阅读时可跳过）。　　它与列属性A的信息熵相关，依赖于训练集中的记录的分布状态。　　精简属性能减少无关属性干扰，既节省时间，又保证分类精度。　　 5第二个训练结果，训练一个分房（分类）公式。　　分房委员会反复讨论，旨在生成一个加权公式：　　　　　　　Total =∑P i F i 　　其中，P i 为加权值，总分Total为应住面积。而F i 为各条件之量化值，例如，曾经有一个学校的真实的分数：工龄一年算一分，副教授算3分，教授算5分，等等；　　注意，复杂的分类规则不一定能用简单的公式表达，但总可用一组形如“If….then….”的规则来表示。　　经委员会反复讨论，（在计算机中，则表现为反复迭代），当把训练集中每一行代入分房公式，得到的分房总分Total都与训练数据中对应房型基本匹配。训练过程就完成了。　　计算机能模拟这一手工的、交互的过程，自动地生成加权公式，或形如“If….Then…”的规则，例如用决策树、回归、用遗传算法、用基因表达式编程，等等，对分房这种小规模问题，现在的数据挖掘系统几秒钟就出结果。　　 6 测试数据与测试 6.1 讨论与迭代中的校正交互过程中，分房委员会的委员们会暗自把自己的数据代入公式，看自己能分到哪一类。如果发现吃亏了，会大呼上当，提出反对意见。　　如果分房委员会有足够的代表性，每一个委员都维护自己所代表的那一类人的利益，在讨论或计算机的迭代过程中，缩小误差，最后推出的分房（分类）公式是基本正确的。　　 6.2 测试用独立的测试数据（本文中，第51-150号记录），代入公式，得到的结果应该与测试数据中所分类型基本一致，否则，要重新修订公式、各项分值和加权等，在计算机中表现为继续迭代计算。 7 应用于大规模的分类公示通过了测试的分房公式，用其计算全厂申请住房者的分类标号（等价于住房面积数），公示。 8 商品房时代的购房与分类有关吗？　　福利分房用了表1 那样的多属性表，如今的商品房的法则，也可视为是上述方法的特例，即用一个属性取代表1中所有属性，这个属性就叫金钱，出第n等的钱，就住第n等的房。　　设有一个映射： f: 对社会的贡献--收入如果这个映射f很完整、很公平，则金钱法则相当于多劳多得，按劳分配。但是，社会太复杂，这个映射f 不太完整，还有漏洞（如贷款炒房），也不太公平，情况就复杂了。此外，如今一些在本单位土地上建设的商品房，对本单位职工比较优惠，因僧多粥少，还需排队，排队时，还是用类似于如表1描述的传统方式计算分类，分出排队次序。　需要说明，真正的分类技术并不像这篇科普文章这么简单。事实上，在数据挖掘中，分类是比关联规则更复杂的技术，计算机专业的硕士生、博士生也要花好几周，甚至更长时间才学得扎实。分类还有那些重要情节？它与预测又怎样联系？且看下篇分解。相关博文 1 “被打”和“北大” 的关联 --- 趣味数据挖掘系列之一 2 烤鸭、面饼和甜面酱之朴素关联 --- 趣味数据挖掘系列之二 3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之三 4 巧挖科学博客之均击量公式，兼谈干预规则 ---- 趣味数据挖掘之四 5 听妈妈讲过去的故事，分房与分类 ----- 趣味数据挖掘之五 6 借水浒传故事，释决策树思路--- 趣味数据挖掘之六 7 宴会上的聚类 — 趣味数据挖掘之七 8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八 9 灯谜、外星殖民、愚公移山和进化计算 --- 趣味数据挖掘之九 10 达尔文、孟德尔与老愚公会盟：基因表达式编程--趣味数据挖之十 11 十大算法展辉煌，十大问题现锦绣---趣味数据挖掘之十一 12 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二其它系列博文的入口唐常杰博客主页科学博客主页

个人分类: 科普札记|14614 次阅读|48 个评论

帐号		自动登录	找回密码
密码			注册

关闭安全验证

标签: 趣味数据挖掘

相关帖子

相关日志

关闭 安全验证

标签: 趣味数据挖掘

相关帖子

相关日志

关闭安全验证