【趣味】数据挖掘(8)——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-平均法的轮廓,是在韩家炜教授等著名专家撰写的书(参见文献[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步的迭代过程,(假定相关条件都满足,如函数连续可微,二阶导数为正等等)。

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

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

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

如果 Xk 和 Pk 是自然界的原鸡与原鸡蛋,有下列命题: Xk 成功进化为鸡的必要条件:所产生的海量生殖细胞中,一半以上(这也是海量)充分接近鸡的生殖细胞;

Pk 成功进化为鸡蛋的充要条件:只要这一个蛋孵出的是鸡。(数量上要求少)。 6 先有鸡还是先有蛋,阈值说了算

图2右中有个紫色的阈值园,不管是鸡序列,还是蛋序列。谁先进入阈值园,谁就先进化成功。但是阈值园的圆心正是欲求的目标,所以有纠结,知道它存在,但画不出来。 数学分析中的柯西收敛原理能解决这个问题。给定一个收敛阈值ε: 如果存在N,当n>N,就有|Pn-Pn+1|<ε,就说蛋序列收敛了(蛋进化为鸡蛋了);

如果存在N,当n>N,就有|Xn-Xn+1|<ε,就说鸡序列收敛了(鸟进化为鸡了)。我们得到一条启发性知识:若逢蛋鸡纠结,请用迭代之法。

7 自然界中,先有蛋的可能性,比先有鸡的可能性大

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

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

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

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

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

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

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2014-07-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

小二,来一份机器学习书单!

编者注:澳大利亚机器学习专家、畅销书作者 Jason Brownlee,对机器学习领域的各类优质书籍进行了盘点,汇总成这份阅读指南。在 AI 研习社所筛选的学...

3935
来自专栏专知

自动驾驶的“大脑”——决策规划篇

自动驾驶的“大脑”——决策规划篇 中国人工智能系列白皮书-智能驾驶2017 ▌决策规划技术概述 ---- 智能汽车 ( Intelligent Vehic...

4178
来自专栏机器之心

学界 | 学术盛宴:微软亚洲研究院CVPR 2017论文分享会全情回顾

机器之心原创 作者:Smith 今年 7 月,世界顶级计算机视觉会议 CVPR(计算机视觉与模式识别会议)将在美国夏威夷举行。在此之前,「微软亚洲研究院创研论坛...

4496
来自专栏目标检测和深度学习

CVPR 2018视频行为识别挑战赛结果出炉:前三名均由国内团队包揽

Moment 是由 MIT-IBM Watson AI Lab 开发的研究项目。该项目致力于构建超大规模数据集来帮助 AI 系统识别和理解视频中的动作和事件。

672
来自专栏大数据挖掘DT机器学习

【趣味】数据挖掘(5)—分房与分类

中老年回顾歌曲集中有这样一首歌:月亮在白莲花般的云朵里穿行,晚风吹来一阵阵欢乐的歌声,我们坐在高高的谷堆旁边,听妈妈讲那过去的事情……   歌词美,旋律也美...

2603
来自专栏CreateAMind

吴文俊先生的思想对我学术研究的影响

今天(2017年5月7日)惊闻吴文俊先生仙逝,宛若晴天霹雳,令人无限感伤。我虽然从未有幸和吴先生见面,但却多次通过电子邮件得到他亲自教诲。我的学术生涯受到了吴文...

863
来自专栏思影科技

《大话脑成像》系列之九 —— 由 ALFF 说开去

看到这个标题有些朋友表示很不解,为什么是之九,不是第十二吗? 我告诉您,没有为什么,因为我任性(其实是因为漏掉了一期,显得不工整,现在补上) ...

3357
来自专栏周景超的专栏

腾讯 AI Lab 计算机视觉中心人脸 & OCR 团队近期成果介绍 ( 2 )

近期,我们团队在人脸识别的关键任务上也取得突破,在人脸识别的国际权威评测平台(Megaface Challenge)中取得了国际领先的成果。同时,在人脸检测中,...

1.1K3
来自专栏数说工作室

这是一份开光的课程 |《神经网络》中文字幕版(2.1 RNN & 2.2 感知机)

《Neutral Network for Machine Learning》(机器学习中的神经网络)系列课程,是深度学习大神 Geoffrey Hinton 毕...

32412
来自专栏思影科技

EEG和fNIRS同步研究揭示年龄和神经反馈对运动想象信号的影响

注释:这篇文章相当长,请耐心看完。 来自德国奥尔登堡大学心理学部的Catharina Zich等人在Neurobiology of Aging杂志上发表了一项基...

3336

扫描关注云+社区