数极客首页

趣味数据挖掘系列8:农村中学并迁选址、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个子图分别标记为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,引来若干批评和改进,殊不知,这正是“算法如此多娇,引无数英雄竟改进”,增加了其影响力,也增加了文献[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步的迭代过程,(假定相关条件都满足,如函数连续可微,二阶导数为正等等)。

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

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

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

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

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

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

6 先有鸡还是先有蛋,阈值说了算

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

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

如果存在N, 当n>N,就有|X-X+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.? 有中译本,《数据挖掘,概念和技术》第二版,范明,孟小峰 等译,机械工业出版社出版。(目前还是世界各国采用最多的教科书)。

发表评论

评论已关闭。

相关文章