【趣味】数据挖掘(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,等等。 但是,一旦人们在聚类之初选择了距离类型,或多或少地加入了主观干预,极大地干预了最后结果,例如,如上面所述,选择不同的距离定义,似乎开始的差别不大,但可导致结果分别是同乡和同志,这两个概念差之千里,同乡不一定是同志,蒋介石的奉化同乡中也有坚定的共产党员。 笔者以为,如果距离的类型也是挖掘出来的,而不是主观指定的,那才真的是“无监督”,或者,从分布熵的角度,避开距离来解决聚类,这方面也许还有许多工作,可供处于选题饥饿的博士生做。

为深入研究准备的准备

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

资源 | 2017深度学习优秀论文盘点(建议收藏)

本文是伦敦帝国学院博士生Pierre Richemond所写的年度深度学习论文盘点,他属于该大学的BICV计算机视觉团队。这些论文在他们每周的Imperial ...

35911
来自专栏新智元

【机器学习经典案例】从白富美相亲看特征选择与预处理( 上篇 )

1.引言 再过一个月就是春节,相信有很多码农就要准备欢天喜地地回家过(xiang)年(qin)了。我们今天也打算讲一个相亲的故事。 讲机器学习为什么要讲相亲?被...

25610
来自专栏量子位

AI学会了视觉推理,“脑补”看不清的物体 | 李佳李飞飞等的CVPR论文

这张照片在人类眼中,左下角的一小片棕黄黑灰就是一匹活生生的马——这个姿势和场景,当然是骑马啦!

1064
来自专栏大数据文摘

概率的意义:随机世界与大数法则

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

用AlphaGo来做股票交易会怎样?机器学习预测股票靠谱么?

今天李世石已连续输掉了第二局,粗看下来,后面几盘似乎已没啥悬念了。无疑,这是一个伟大的时刻,也是个伟大的开始,超级智能机器在未来将会在人类生活中扮演更多更重要的...

2676
来自专栏量子位

照片有灵异鬼影?伯克利 x 陈启峰培育高能FCN“除灵师” | CVPR论文

图像(I),可以被建模成,透射层(T)与反光层 (R) 之和,即I = T + R。

1053
来自专栏AI科技评论

CNCC | 丘成桐演讲全文:工程上取得很大发展,但理论基础仍非常薄弱,人工智能需要一个可被证明的理论作为基础

AI科技评论消息,2017年10月26日上午,中国计算机学会(CCF)主办的第十四届中国计算机大会(CNCC 2017)正式在福州海峡国际会展中心开幕,雷锋网作...

3448
来自专栏企鹅号快讯

2017深度学习优秀论文盘点

本文是伦敦帝国学院博士生Pierre Richemond所写的年度深度学习论文盘点,他属于该大学的BICV计算机视觉团队。这些论文在他们每周的Imperial ...

2067
来自专栏灯塔大数据

平均数的称霸之路

? 一 1906年,伟大的科学家兼恶心的人种改良倡导者高尔顿(Francis Galton)参加了年度西英格兰家畜展,即兴做了个数学实验。 在集会上闲逛的他碰...

3106
来自专栏计算机视觉战队

视频大数据处理的挑战和机遇

背景: 视频在许多应用中是非常重要的问题,如内容搜索、智能内容识别广告等。现在正处在一个数据爆炸性增长的"大数据"时代,大数据对社会经济、政治、文化,人们生活等...

3569

扫描关注云+社区