【趣味】数据挖掘(7)——团拜会与鸡尾酒会上的聚类

在硕博士生的数据挖掘课程中，聚类是难点，一文难尽。此文用宴会上的见闻，用异于传统的方式，从讲课PPT上取些素材（这样比较快），来说明聚类的一些概念，为下篇做些铺垫，下篇将通过通俗的例子说明一个著名的方法。

团拜会上一道风景线

岁末年初，参加了几个团拜会。朋友们都知道我对酒特过敏，宽容地让我以茶代酒，因而能在酒席上清醒地倾听、观察和记忆，并在这里调侃敬酒的艺术。 社会是由各种纽带联络而成的人的集合，敬酒是众多纽带中的一种。老百姓敬酒传达亲情友情；伟人（如罗斯福、斯大林）的敬酒也是政治；文人敬酒吟诗作赋，企业家敬酒不忘投资。作为数据挖掘阵地上的戒酒一兵，笔者在敬酒中观察到了聚类技术的应用。

敬酒与聚类技术

善敬酒者都是聚类专家，试看下例： “赵总，你我同学多年，这一杯酒你要喝了，… “老张，你我一同扛过枪，这一杯酒你要干了 ,… “老李，你我同乡兼同学，感情深，这杯一口闷，…… 善劝酒者总是抓住自己与被敬酒者的相同点，说对方和自己聚在同一个“簇”，令对方推迟不得，用的是对称聚类技术；“簇”--cluster，有时也译为“类”。 当对方非常德高望重，不好意思把对方和自己聚成一簇，敬酒人会找几个同簇人士壮胆，说“我们几位同YYY，一起来敬..."; 有时，还分“簇”发起集团冲锋，让对方喝得尽兴；仔细思量，用的是非对称（或单侧）聚类技术。 常用敬酒词汇与短语还有：同学、同乡、同事、一同下过乡、一起扛过枪,...,等等。如果一时找不到具体的共同点，对炎黄子孙，总可用“同胞”。上述的“同学”、“同乡”等名词,相当于英文中的 Homo-Something,在数据库技术中称为属性,对应英文单词Attribute，所以，这种敬酒技巧可泛称为同A技巧。

同A技巧的推广

同A技巧还可推广。例如，假如那一天来临，科幻迷有机会到银河系中心开联合星系（联合国的推广）团拜会，来的都是广义人（外星智慧生命），见“人”都可称同系(同一个银河系)；如果见到了我们这个太阳系的火星人，那简直是老乡见老乡，两眼泪汪汪(假定火星人也是两只眼睛），同在他乡为异客：“这一杯一定要干”，不干不解乡愁。

簇内相似度大，簇间相似度小

如果只往大处找共性（如同胞、同星系），不足为荣，因为概念太大，而无特色。把一个大集合只聚成一类，最蹩脚的聚类家也会。 能干的聚类家于细微处见功夫，要找某些子集的特色，把大集合中的对象凝聚成若干个特色小簇，使得簇内相似度大，簇间相似度小，那才是万紫千红、信息量丰富的春天。

同A聚类 -- 投影到属性A上的小小区间

顾名思义，同A即在属性A上的值相同或相近；前者投影到属性A上一个点，是严格的同A聚类，后者投影到不太大的区间 [a-ε, a+ε]，是宽松的同A聚类。 巧得很，中华文明早为聚类作了准备。中文中有很多形如“同某”的词汇，如同学，同乡，同志，同事，同袍，还有数学上的同态，同构，拓扑学中的同坯，等等。 图1中，横轴是籍贯，纵轴是班级。图中的点代表学生。在横轴投影相近的那些点称为同乡，在纵轴上投影相近的那些称为同学，红圈中的点在双轴上投影都较近，所以是“同学+同乡”。多维的情形稍微复杂，但是思路是同样的。

鸡尾酒会上人以群分

国际学术会议常有鸡尾酒会方式的招待会（reception），人们端着酒杯，不断流动，笑声中交流学术，干杯时结识朋友。 聚类之主动 vs 分类之被动鸡尾酒会上，常看到一群学子围住一个学术带头人；也常看到几位研究者坐在角落，一边品酒，一边在草稿上写写画画，讨论问题;偶尔也有不善交际的离群点（outlier),远离人群，在边沿灯下，“独酌无相亲，...对影成三人”。这里，影响聚群的不是万有引力或电磁力，也不是强、弱相互作用，而是学术思想的凝聚力，是人格魅力。 鸡尾酒会上没有人指挥谁谁应该到哪里。所遵循的是“物以类聚，人以群分”，聚类对象是主动的。 而在在分类中，对象是被动的，网络上时髦的“被”句型，是分类技术在社会生活中的体现，如菜园子张青“被”分类到地煞，豹子头林冲“被”分类到天罡。某人“被捐款”，某人“被集资”，等等。主动与被动之差别，是聚类和分类的最大区别。分类有训练集和测试集，它代表了人们主观意志对分类过程的监督，在机器学习中，分类又称为有监督的机器学习，而聚类称为无监督的学习。

坐标变换与聚类

观察图2，左图是图1内容旋转45o的结果。在XOY坐标系中，不容易简单表达聚类准则。旋转45o后，在新坐标系X’OY’中，能直接看出同乡即同X'，同学即同Y’。

图2 （1）坐标旋转 （2）极坐标 令θ=-45o，它顺时针旋转，就转回XOY平面，中学数学中有坐标变换公式： x'=xcos(-45 o)-ysin(-45o)， y'=xsin(-45 o)+ycos(-45o)； 下面讲核函数概念还要用到它，现在暂且按下不表。

坐标变换与核函数

聚类可以表现为在簇周围画一条紧边界。考察图2右边的紫色扇面簇，在直角坐标系中的描述稍复杂一些，但在极坐标中却很简单。坐标变换公式是： f(x,y)=r=x2+y2 ， g(x, y)=θ=ArcSin(y/(x2+y2)(1/2)) 坐标变换后，扇面变成<r, θ>平面上的矩形，例如，{ { （r, θ）|1≤r≤2 , 45 o ≤θ<90 o }是一个扇面。在XOY平面，扇面边界是非线性的，在<r, θ>平面上，边界却是直线段！ 又例如， { （r, θ）|0≤r≤1 , 0≤θ< 360 o } 描述了图2（2）中的那个白色的园核。 于是，我们有理由称 f(x,y)，g(x, y)为核函数或类核函数，可以这样来理解名称中的“核”字： （1）如果把图2右边看成是染色的青核桃， f(x,y) ≤1所描述的正好是中间哪个白色的核。 （2）图2左边的坐标变换中类核函数是f(x,y)=x’=xcos(-45 o)-ysin(-45 o) , g(x,y)= y’=xsin(-45o)+ycos(-45 o) 。设a,b为常数， X’=a, 是一条直线，也是一个同乡簇的中心线； Y’=b, 是一条直线, 是一个同学簇的中心线；点(X', Y')=(a,b) 是一个点，是同乡兼同学簇的中心点；中心线与中心点都与“核”概念相关，这也提示了选择和设计核函数的思路，设法引入曲线坐标系，综合考虑坐标曲线簇与对象簇中心线、以及簇的边界的联系，设法联系原点与重要簇的中心，则核函数选择就有线索了。 核函数(Kernal function) 是个较难懂的概念，在分类的支持向量机SVM技术中也要用到。这里斗胆对核函数做了一个直观解释，有点反传统，未提及在对应的高维空间中的线性可分性，仅供辅助理解，科普不能代替严格的数学定义和证明，如有不妥，请专家指正。

多样化的距离,海内存知己，天涯若比邻

设描述人的维度有（x,y,z,t,籍贯，感情，信仰，…..）。设人与人的距离为d， （1）把d定义为在籍贯维上投影的差别，得到的簇是同乡; （2）把d定义为在信仰维上投影的差别，得到的簇是同志。 （3）把d定义为在感情维上投影的差别，得到的簇是朋友。 如果两个人在信仰和感情上的投影一致，哪怕x,y,z,t有巨大的时空差别，也心心相印，这就是“海内存知己，天涯若比邻”的数学描述或解释，天涯和比邻描述的是在不同维度上的距离。 正邪两方都会用科学规律，二战时，德日意三国的欧式空间距离不小，却聚成了一个反人类集团，是在政治和利益两个维度上的投影相近。

Minkovski-距离 p维空间中两点的Minkovski -距离

当q=1，结果为各维度上差别之和 ,又称为曼哈顿距离.说的是，城市曼哈顿以方格子路为特色，（似乎济南老城区经纬路那一块也类似），从（x1，y1)到 (x2, y2)，有若干条最短路径，虽然转弯的次数不同，但长度都是|x1-x2|+|y1-y2}。

当q=2；是最普通的欧式空间距离。实践中，有时为夸大距离，采用q=3；有时为了缩小差别，可用q=3/2,等等。 但是，一旦人们在聚类之初选择了距离类型，或多或少地加入了主观干预，极大地干预了最后结果，例如，如上面所述，选择不同的距离定义，似乎开始的差别不大，但可导致结果分别是同乡和同志，这两个概念差之千里，同乡不一定是同志，蒋介石的奉化同乡中也有坚定的共产党员。 笔者以为，如果距离的类型也是挖掘出来的，而不是主观指定的，那才真的是“无监督”，或者，从分布熵的角度，避开距离来解决聚类，这方面也许还有许多工作，可供处于选题饥饿的博士生做。

为深入研究准备的准备

聚类是数据挖掘中难度较大的内容，本文只是为哪个准备而做的准备的准备，从远处看看轮廓，讲讲思想, 尝尝味道，有了这些铺垫，下篇将通过通俗的例子说明一个著名的方法。