学到老Never too old to learn分享 http://blog.sciencenet.cn/u/tangchangjie

博文

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

已有 16208 次阅读 2012-1-5 08:35 |个人分类:科普札记|系统分类:科普集锦|关键词:趣味数据挖掘,中学并迁,,蛋鸡悖论,K平均、聚类、| 趣味数据挖掘, 中学并迁, 蛋鸡悖论, K平均、聚类、

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

    本文从农村中学并迁选址问题出发,介绍了数据挖掘十大算法中位居第二的K-平均聚类,后又借用牛顿迭代原理,议论蛋鸡悖论。从过去的数据挖掘课程PPT取些素材,改成这篇博文(比较省事),也许对此课程的新教师有用。 虽涉嫌双重班门弄斧(生物、数学),有趣就行,不当之处,请专家指正。   

    1 一道应用题:用聚类技术为农村中学并迁选址 为提高教学质量,一些边远农村中学并校迁址。考察图1,在(x,y)的村庄有m名学生,表达为在(x,y)处部署一个质量为m的质点。如果把全部质点聚成若干簇,学校新址选在这些簇的质心,则校址向学生多的居住点倾斜,照顾了大多数人,学生上学的交通里程从总体上得到优化,也有助于减少校车事故。(中学物理指出,一组质点的质心坐标是它们坐标的加权平均,其公式不再赘述)。

     2 似乎是妙想,却涉嫌蛋鸡悖论  1使人联想到宇宙大爆炸后星云逐渐凝聚成为星系的过程。人眼能看出图1中大致有7-9个簇,每个簇中选出质心,标为红色,如果远处飘来一颗流星,可能会向最近的簇心靠拢。求质心位置用(加权)平均,故由此引出的算法称为K-平均算法,由J.MacQueen于1967年提出[1]

    初听起来不错,却似有悖论之纠结 还没有开始聚簇,怎样知道哪些质点是一簇而在一起选举质心?到底是先有簇再选质心,(先有鸡),还是先有质心再聚簇(先有蛋)? 上篇博文讲过,聚类对象是主动的,那么,主动的质心会问:“我是属于这一簇吗?,我该这里参加选举吗?,而没有质心,一个普通质点又怎样知道自己聚向何方?  若干教科书在这一内容前没有分析这个纠结,使初学者不易理解K-平均算法之微妙,反而错误地以为该算法笨笨的,慢慢的。

    破解悖论纠结的迭代法 生活中常有这样的纠结:例如职称与科研项目(无高级职称,不易申请项目,无项目,不易晋升职称)、居民新区的服务点与人气、申请博士点与成果,等等。

    300多年前的牛顿(1643-1727)为我们准备了破解类似纠结的迭代原理:先干起来再改进,宽容地从近似值开始,逐步求精。为不干扰主题,我们先用此方法,后回头再看牛顿迭代原理,给一点演绎,并试图说明:在自然界中,先有蛋的可能性比先有鸡的可能性大。

 

    3 用聚类为农村中学迁移选址:K-平均聚类   2给出了k-平均法的轮廓,是在韩家炜教授等著名专家撰写的书(参见文献[2])中的一个图添加了一簇而成,赋以了本应用题环境的语义,含5个子图分别标记为ABCDE,下面一一道来,(如觉得较难,可跳到第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,引来若干批评和改进,殊不知,这正是“算法如此多娇,引无数英雄竟改进”,增加了其影响力,也增加了文献[1]的它引率。而在实践中,这一瑕疵不是大问题,Why? 请问,实践中有过不经人的调查研究,而只靠机器决策的事吗?在中学并迁选址问题中,有调查、有经费约束,这自然就确定了簇数。此算法实用且高效,因而高居十大算法之二。

    此外,不要以为K平均算法就如这个科普故事这么简单,K平均的收敛性证明是相当复杂而艰难的,读读文献[1],可以体会这个艰苦的历程和作者高超的技巧。

    4星计划和杨强教授的课堂游戏  2007年,香港科技大学杨强教授在川大的主讲一周龙星计划课程《数据挖掘和机器学习》在讲解K-平均算法时,杨强教授导演了一场课堂游戏:图2中的点对应于课堂上的学生,簇数K=3,关键步骤是:(a)迭代过程中,得到新簇后,每簇同学重新选举新质心,新质心站起来; (b)基于新的质心,同学们重新就近入簇(不移动座位,只是心里认定自己聚在那一簇),如果预先准备了簇号牌,就举起相应的簇号牌。 如此经过3-5次迭代,就收敛了,收敛的标志是质心点成为不动点。同学们在游戏中,领悟了聚类的深刻道理,也看到迭代过程宽容地从随意的近似值开始,竟然能很快收敛。

  (注:龙星计划课程是国家自然科学基金委资助的学术活动,邀请国际知名的华人计算机科学家回国举办专题讲座。2006年,文献[2]的作者韩家炜教授来川大讲学,考察了我们的课程、环境、条件、研究基础等,鼓励我们竞争申请龙星计划,次年竞争成功)。

   5 破解蛋鸡悖论的利器--迭代原理  前面说过,蛋鸡纠结常见于科研生活中,如职称与科研项目、如居民新区的服务点与人气,如申请博士点与成果,等等。300多年前的牛顿1643—1727为我们准备了破解蛋鸡悖论纠结的原理。

    图3左展示了用牛顿弦线法迭代地求f(x)=0的近似根时,从第n-1步到第n+1的迭代过程,(假定相关条件都满足,如函数连续可微,二阶导数为正等等)

    把曲线上的点Pn-1 Pn Pn+1 比喻为蛋,把横轴上Xn-1 Xn Xn+1 标示的点比喻为鸡。

    鸡生蛋XkPk: Pk=(Xk,f(xk)); 注意,进化序列Pn-1 Pn Pn+1,沿函数曲线逼近鸡(欲求的根);

    蛋生鸡Pk产生XK+1如下 作弦线 PkP’交横轴于(Xk+1,0),得到了Xk+1 注意, 进化序列Xn-1 Xn Xn+1… 沿X轴逼近鸡。

   如果 XkPk 是自然界的原鸡与原鸡蛋,有下列命题:

   Xk 成功进化为鸡的必要条件:所产生的海量生殖细胞中,一半以上(这也是海量)充分接近鸡的生殖细胞;

   Pk 成功进化为鸡蛋的充要条件只要这一个蛋孵出的是鸡。(数量上要求少)。 

 

    6 先有鸡还是先有蛋,阈值说了算2 中有个紫色的阈值园,不管是鸡序列,还是蛋序列。谁先进入阈值园,谁就先进化成功。但是阈值园的圆心正是欲求的目标,所以有纠结,知道它存在,但画不出来。  数学分析中的柯西收敛原理能解决这个问题。给定一个收敛阈值 ε:

       如果存在N n>N,就有|Pn-Pn+1|<ε,就说蛋序列收敛了(蛋进化为鸡蛋了);

       如果存在N n>N,就有|Xn-Xn+1|<ε,就说鸡序列收敛了(鸟进化为鸡了)。

    我们得到一条启发性知识:若逢蛋鸡纠结,请用迭代之法。

   7 自然界中,先有蛋的可能性,比先有鸡的可能性大。我们的课题组在做基于基因表达式编程的数据挖掘时,学过一些遗传和变异的常识,做过一些模拟,感觉到自然界中,从原鸡(鸡的祖先)进化到鸡的过程中,先有鸡蛋的可能性,比先有鸡的可能性大。有下列三个原因:

     (a) 获得性不能遗传,例如原鸡之妈和原鸡之爸割了双眼皮,不会遗传到下一代上。原鸡全身的可能变异中,很小一部分发生在生殖细胞,而发生了这种变异的生殖细胞,还只是是半个生命。

     (b)在数量上,生殖细胞的数量比原鸡数大若干个数量级,生殖细胞发生变异的机会比原鸡多,公原鸡和母原鸡受到辐射、化学刺激、或卫星或火箭搭载时(外星人的火箭 atlong ago),可能引起生殖细胞变异;当几个生殖细胞发生变异后,山还是那座山,水还是那湾水,原鸡还是那个原鸡,而不是鸡;来自原鸡爸妈生殖细胞的变异都可汇集在能孵出下一代的蛋(已是一个生命,而不是半个);

     (c)鸡蛋被生出来后,孵化之前,还可能受到辐射、化学处理、或卫星搭载等等,都可以发生变异;

    如果图3中阈值园能画出,蛋的序列一旦进入这个阈值园,则称为鸡蛋;原鸡序列一旦进入这个阈值园,则称为鸡。与原鸡相比,鸡蛋发生变异的机会多,原鸡蛋序列收敛速度更高,在用收敛原理作阈值检查时,满足阈值条件的时间可能会更早。

    结论: 自然界中,先有鸡蛋的可能性 大于 先有鸡的可能性。

    这是双重的班门弄斧(生物、数学),有趣就行,请专家指正。

   参考文献

    [1]J.MacQueen, "Some methods for classification and analysis of multivariate observations," in <i>Proc. 5th Berkeley Symp. Mathematical Statistics and Probability, vol.1. Berkeley, CA: University of California Press, 1967, pp. 281-297.  

    K-平均原文.pdf

    [2 Data Mining: Concepts and Techniques, 2nd ed.,  Jiawei Han and Micheline Kamber, Morgan Kaufmann, 2006. P P383-464.  有中译本,《数据挖掘,概念和技术》第二版,范明,孟小峰 等译,机械工业出版社出版。(目前还是世界各国采用最多的教科书)。

 

    相关博文



http://blog.sciencenet.cn/blog-287179-525905.html

上一篇:团拜会与鸡尾酒会上的聚类—趣味数据挖掘之七
下一篇:灯谜、外星殖民、愚公移山和进化计算---趣味数据挖掘之九

49 李伟钢 李学宽 王娜娜 杨正瓴 刘洋 封力军 曹元兰 陈玉红 王利国 钟炳 王迪 董文娜 曹广福 刘波 卢利强 王铮 李泳 许培扬 朱志敏 柳海涛 孙学军 赵家平 张骥 刘用生 王恪铭 陈安 金小伟 张震 曹聪 白红友 魏玉保 边一 吴吉良 高建国 闫钟峰 谢鑫 章成志 刘剑 井然哲 曾新林 化柏林 曹建军 马小池 liyigong liuwenwenb chengmin8504 zhangbenhua82 lftkf xchen

发表评论 评论 (78 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-4-6 21:21

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部