科学网 › 标签 › 蛋鸡悖论

标签: 蛋鸡悖论

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

没有相关内容

相关日志

农村中学并迁选址、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 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二其它系列博文的入口唐常杰博客主页科学博客主页; 个人分类: 科普札记|18297 次阅读|78 个评论

更多...

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

关闭 安全验证

标签: 蛋鸡悖论

相关帖子

相关日志

关闭安全验证