学到老Never too old to learn分享 http://blog.sciencenet.cn/u/tangchangjie

博文

团拜会与鸡尾酒会上的聚类—趣味数据挖掘之七 精选

已有 16130 次阅读 2011-12-28 09:54 |个人分类:科普札记|系统分类:科普集锦|关键词:趣味,数据挖掘,聚类,团拜会,鸡尾酒,核函数| 趣味, 数据挖掘, 团拜会, 聚类, 鸡尾酒

   团拜会与鸡尾酒会上的聚类—趣味数据挖掘之七 (唐常杰)

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

    团拜会上一道风景线 岁末年初,参加了几个团拜会。朋友们都知道我对酒特过敏,宽容地让我以茶代酒,因而能在酒席上清醒地倾听、观察和记忆,并在这里调侃敬酒的艺术。

    社会是由各种纽带联络而成的人的集合,敬酒是众多纽带中的一种。老百姓敬酒传达亲情友情;伟人(如罗斯福、斯大林)的敬酒也是政治;文人敬酒吟诗作赋,企业家敬酒不忘投资。作为数据挖掘阵地上的戒酒一兵,笔者在敬酒中观察到了聚类技术的应用。

    敬酒与聚类技术  善敬酒者都是聚类专家,试看下例:

         “赵总,你我同学多年, 这一杯酒你要喝了,

         “老张,你我同扛过枪,这一杯酒你要干了 ,…

         “老李,你我 同乡同学感情深,这杯一口闷,……

    善劝酒者总是抓住自己与被敬酒者的相同点,说对方和自己聚在同一个“簇” ,令对方推迟不得,用的是对称聚类技术;“簇”--cluster,有时也译为“类”。

    当对方非常德高望重,不好意思把对方和自己聚成一簇,敬酒人会找几个同簇人士壮胆,说“我们几位同YYY,一起来敬..."; 有时,还分“簇”发起集团冲锋,让对方喝得尽兴;仔细思量,用的是非对称(或单侧)聚类技术。

    常用敬酒词汇与短语还有:同学、同乡、同事、一同下过乡、一起扛过枪,...,等等。如果一时找不到具体的共同点,对炎黄子孙,总可用“同胞”。上述的 “同学”、“同乡”等名词,相当于英文中的 Homo-Something,在数据库技术中称为属性,对应英文单词Attribute,所以,这种敬酒技巧可泛称为同A技巧,

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

    簇内相似度大,簇间相似度小 如果只往大处找共性(如同胞同星系),不足为荣,因为概念太大,而无特色。把一个大集合只聚成一类,最蹩脚的聚类家也会。

    能干的聚类家于细微处见功夫,要找某些子集的特色,把大集合中的对象凝聚成若干个特色小簇,使得簇内相似度大,簇间相似度小,那才是万紫千红、信息量丰富的春天。

    A聚类 -- 投影到属性A上的小小区间  顾名思义,A即在属性A上的值相同或相近;前者投影到属性A上一个点,是严格的A聚类,后者投影到不太大的区间 [a-ε, a+ε],是宽松的同A聚类

    巧得很,中华文明早为聚类作了准备。中文中有很多形如“同某”的词汇,如同学,同乡,同志,同事,同袍,还有数学上的同态,同构,拓扑学中的同坯,等等。

    图1中,横轴是籍贯,纵轴是班级。图中的点代表学生。在横轴投影相近的那些点称为同乡,在纵轴上投影相近的那些称为同学,红圈中的点在双轴上投影都较近,所以是“同学+同乡”。多维的情形稍微复杂,但是思路是同样的。

                          图1  同学与同乡             

    鸡尾酒会上人以群分。国际学术会议常有鸡尾酒会方式的招待会(reception),人们端着酒杯,不断流动,笑声中交流学术,干杯时结识朋友。

    聚类之主动 vs 分类之被动 鸡尾酒会上,常看到一群学子围住一个学术带头人;也常看到几位研究者坐在角落,一边品酒,一边在草稿上写写画画,讨论问题;偶尔也有不善交际的离群点(outlier),远离人群,在边沿灯下,“独酌无相亲,...对影成三人”。这里,影响聚群的不是万有引力或电磁力,也不是强、弱相互作用,而是学术思想的凝聚力,是人格魅力。

    鸡尾酒会上没有人指挥谁谁应该到哪里。所遵循的是“物以类聚,人以群分”,聚类对象是主动的。

    而在在分类中,对象是被动的,网络上时髦的“被”句型,是分类技术在社会生活中的体现,如菜园子张青“”分类到地煞,豹子头林冲“”分类到天罡。某人“被捐款”, 某人“被集资”,等等。主动与被动之差别,是聚类和分类的最大区别。分类有训练集和测试集,它代表了人们主观意志对分类过程的监督,在机器学习中,分类又称为有监督的机器学习,而聚类称为无监督的学习。

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

          图2 (1)坐标旋转                        (2)极坐标               

      令θ=-45o 它顺时针旋转,就转回XOY 平面,中学数学中有坐标变换公式:

            x'=xcos(-45 o)-ysin(-45 o)

            y'=xsin(-45 o)+ycos(-45 o)

下面讲核函数概念还要用到它,现在暂且按下不表

    坐标变换与核函数  聚类可以表现为在簇周围画一条紧边界。考察图2右边的紫色扇面簇,在直角坐标系中的描述稍复杂一些,但在极坐标中却很简单。 坐标变换公式是:

           f(x,y)=r=x2+y2 

              g(x, y)=θ=ArcSin(y/(x2+y2)(1/2) )

    坐标变换后,扇面变成<r, θ>平面上的矩形,例如,{ { r, θ)|1r2 , 45 o ≤θ< 90 o }是一个扇面XOY平面,扇面边界是非线性的,在<r, θ>平面上,边界却是直线段!

    又例如, { r, θ)|0r1 , 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(-45 o)+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,等等。

    但是,一旦人们在聚类之初选择了距离类型,或多或少地加入了主观干预,极大地干预了最后结果,例如,如上面所述,选择不同的距离定义,似乎开始的差别不大,但可导致结果分别是同乡同志,这两个概念差之千里,同乡不一定是同志,蒋介石的奉化同乡中也有坚定的共产党员。

    笔者以为,如果距离的类型也是挖掘出来的,而不是主观指定的,那才真的是“无监督”,或者,从分布熵的角度,避开距离来解决聚类,这方面也许还有许多工作,可供处于选题饥饿的博士生做。

    为深入研究的准备的准备的准备   聚类是数据挖掘中难度较大的内容,文献[1]中,用70多页的篇幅,扫描和检阅了相关的成果和方法,也只是一个为深入研究而做的准备;本文只是为哪个准备而做的准备的准备,从远处看看轮廓,讲讲思想, 尝尝味道,有了这些铺垫,下篇将通过通俗的例子说明一个著名的方法

    参考文献

     [1 Data Mining: Concepts and Techniques, 2nd ed.,  Jiawei Han and Micheline Kamber, Morgan Kaufmann, 2006. P P383-464.  有中译本,《数据挖掘,概念和技术》第二版,范明,孟小峰 等译,机械工业出版社出版。
 
  


http://blog.sciencenet.cn/blog-287179-522842.html

上一篇:双模校车:至少我们还有梦
下一篇:农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八

49 李学宽 单博炜 袁文常 曹建军 齐伟 陈斌 金小伟 许培扬 武夷山 平文丽 黄秀清 王亚宁 黄富强 高建国 刘剑 杨冠灿 吴明火 杨正瓴 边一 李冰 李泳 马剑 苏德辰 曹广福 骆小红 李伟钢 刘用生 马萧萧 闫钟峰 张玉秀 陈绥阳 贾伟 段庆伟 李征 魏玉保 王福涛 任胜利 曾新林 曹聪 洪鹏 李斌 黄锦芳 陈智文 化柏林 shsm zhangbenhua82 liuwenwenb crossludo yangwencao

发表评论 评论 (65 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-4-6 13:52

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部