农村中学并迁选址、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_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_kP’_，交横轴于（X_k+1,0），得到了X_k+1 ；注意， 进化序列X_n-1 、X_n ，X_n+1，… 沿X轴逼近鸡。

   如果 X_k 和 P_k 是自然界的原鸡与原鸡蛋，有下列命题：

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

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

       如果存在N， 当n>N,就有|P_n-P_n+1|<ε,就说蛋序列收敛了（蛋进化为鸡蛋了）；

       如果存在N， 当n>N,就有|X_n-X_n+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.  

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

    相关博文