您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
一种基于最大最小距离和SSE的自适应聚类算法.pdf 7页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：80 &&
一种基于最大最小距离和SSE的自适应聚类算法.pdf
你可能关注的文档：
··········
··········
第35卷第2期南京邮电大学学报(自然科学版)V01．35No．2of0fP∞tsandscienceJournal1Heco蚴unications(NaturalEdition)2015年4月NanjingUIliversityApr．2015doi：10．14132／j．cnki．．6一种基于最大最小距离和SSE的自适应聚类算法成卫青，卢艳红(南京邮电大学计算机学院，江苏南京210023)摘要：K均值聚类是一种常用的聚类算法，需要指定初始中心和簇数，但随意指定初始中心可能导致聚类陷入局部最优解，且实际应用中簇数未必是已知的。针对K均值聚类的不足，文中提出了一个自适应聚类算法，该算法基于数据实例之间的最大最小距离选取初始聚类中心，基于误差平方和(SSE)选择相对最稀疏的簇分裂，并根据SSE变化趋势停止簇分裂从而自动确定簇数。实验结果表明，该算法可以在不增加迭代次数的情况下得到更准确的聚类结果，验证了所提聚类算法是有效的。关键词：K均值聚类算法；最大最小距离；初始中心；误差平方和中图分类号：哪91文献标志码：A文章编号：15)02旬102旬6cl哪teringb邪edonma】|【imumandAdaptiVealgorithmSSEmiIlim哪distances，andCHENGYanhongWeiqing，LUandUniversity《P0stsTelecommunications，Nanjing2l0023，China)(school《Compulerscie珏ce&khnolo影，NanjingK-meansofthemostcommontoAk瞳ract：Theclusteringalgori出m，oneeluste订ngalgorithms，requiresoftheinitialcenterscanmndom—theinitialcentersandthenumberspecifyclusters．HoweVer，specifyingincurthe10calofthethenumberofclustersisnotknowninsolvelyoptimumclustering，andpractice．Totheseancanselectinitialcen—problems，thispaperproposesadaptiVeclusteringalgorithm．Thealgorithmtersbasedonmaximumandminimumdistancesbetweendatathemostclusterb船edinstaIlces，andsparseonthesumofdetenninethenuIIlberofclusterswhentoen．0r(SSE)tostopsplittingsquaredsplit，andofb鹅edonthetrendoftllenumberclusterschan百ngSSE，thusidentifyingautomaticaUy．ExperimentalresultsshowthatthecanmoreaccurateresuItswithoutalgorithmgenerateclusteringincre鹊ingproposedt11enumberofitverifiesthee珏色ctivenessoftheiterations，thuspmposedclusteringaLlgorit}lm．initialsumma)【imumandminimumofwords：天r．meansalgorithm；distances；centers；1【eyclustedngsⅡuareden．ors聚类分析是给一组对象分组的工作，它使同一组(也称簇)内的对象相互之间比它们与其他组内进行了系统的论述。Han等人【31归纳了5种聚类算对象之间更为相似。组内对象之间的相似性(同质法：基于划分、基于层次、基于密度、基于网格和基于性)越高，组间对象之间差别越大，聚类就越好。无模型的聚类算法。K均值是基于几何中心基于划分论是旨在理解还是实用，聚类分析在统计学、模式识的聚类技术，以其简单的算法思想、较快的聚类速度别、信息检索、机器学习和数据挖掘等领域都扮演着得到了广泛应用。最早的K均值聚类算法由Mac一收稿日期：2014聊m1；修回日期：2014一12舶本刊月址：httP：∥nyzr．njupt．edu．cn基金项目：国家自然科学基金(17lll7，)资助项目通讯作者：成卫青电话：025—E—mail：chen舭iq@njupt．edu．c玎万方数据第2期成卫青，
正在加载中，请稍后...您的访问出错了(404错误)
很抱歉，您要访问的页面不存在。
1、请检查您输入的地址是否正确。
进行查找。
3、感谢您使用本站，1秒后自动跳转聚类分类理论研究及其在文本挖掘中的应用-共享资料网
聚类分类理论研究及其在文本挖掘中的应用
分类号 UDC密级 编号中 国 科 学 院 博士学位研究生学位论文聚类/分类理论研究及其在文本挖掘中的应用卜东波指导教师李国杰 院士 研究员 白 硕 研究员 中国科学院计算技术研究所申请学位级别 论文提交日期 学位授予单位博士学科专业名称 计算机组织与体系结构2000 年 10 月 论文答辩日期 中国科学院计算技术研究所答辩委员会主席I中国科学院计算技术研究所学位论文致谢我来到计算所求学已经六年了，如果说在这六年的时间里，学业上还有尺 寸之进的话，我想这是和众多良师益友的帮助分不开的。 李国杰院士是我的博士导师， “求真” “务实” ， 是李老师的科学理念， 也是 他向我们强调的最多的话。李老师不仅注重向学生传授知识，而且更加注重激 发学生的创造力和想象力。在每两周一次的讨论班上，李老师都要听取学生的 工作进展和心得体会，向我们讲解如何做学问、如何养成良好的科学素养。因 此我们的讨论班始终洋溢着一种良好的科研气氛，大家致力于真理的探讨，兼 收并蓄，无门户之见，师生“燃烧着学习的热望” 。 我这六年里，都是在白硕老师的具体指导下工作和学习的。老师渊博的知 识和富有魅力的大师风范，给我以很深的影响，也是我今后努力追求的目标和 方向。总记得迸发新思路时老师眼睛中闪亮的光芒，总记得老师作讲演时迷人 的风采，总记得和老师讨论问题时的那种心领神会、灵犀一点......这些都是我 脑海永存的图象。前人说过，师生之间的默契恰似“如鱼在水” ，其中的喜悦 是外人所不能体会的。我遇良师，内心的喜悦也是如此啊！ 自动化所的王珏老师也给我以很大的帮助和教诲。在当今的社会里，王珏 老师是为数不多的能够潜心做学问的学者之一， 不为名利所惑， 不为金钱所动， 醉心于学术之中，始终追求那种“今夕明其道”的喜悦，这也是我们敬佩王珏 老师的原因之一。王珏老师不仅学识渊博，而且对待我们这些后学晚辈也非常 热情，经常给我们以鼓舞和激励。而对于常生高山仰止情绪的青年来说，又有 什么能比热情的鼓励更催人奋进的呢？ 古人云：明师不可期，意思是说一个人遇到明师是可遇而不可求的事情。 而我同时得到三位明师的教诲，实在是一件值得庆幸的事啊！ NCIC-Motorola联合实验室的贺思敏博士是我的学长，也是我科研道路上 的好友。对于学术上的很多问题，我们都有着相同或相近的看法。很多奇思妙 想， 都是从和他的谈话聊天中得到启发的， 而这种自由自在、 身心放松的闲聊，iii中国科学院计算技术研究所学位论文也许就是思维迸发灵感火花的最佳时刻吧！ 感谢我的同学毛永捷和陈明宇，我们共同在计算所度过了六年的时光，心 意相通， 志趣相投， 我为有这样的高手同学而感到自豪， 他们是我最好的朋友。 感谢教育处的诸位老师，他们在这六年里给了我很多的帮助和照顾。 感谢软件室的程学旗博士、郭莉、余志华、梁英、赵洁、邓晶博士以及已 远赴加拿大的赵刚、李晔，想起他们就会想起我们共同构建“天罗信息检索平 台”和“天联代理服务器系统”的时光，以及我们携手奋进、带动软件室从小 到大逐步发展的艰辛历程。 感谢易靖、许洪波、吴赣以及谢华刚、沙瀛、庞剑峰、杨志峰、张泽峰、 朱茂盛等诸位师弟，还有黄园园、熊锦华、向泓等，感谢他们给我的帮助，以 及他们带来的青春朝气。 特别感谢我的父母，是他们哺育我成长，引导我树立远大的志向；感谢我 的姐姐和小妹，是她们多年来辛勤工作支持我求学、勉励我进取，在我身上也 寄托了她们的期望。以她们的聪明和勤奋，如果能有象我一样的好运气，相信 一定会做的比我好，我希望这篇论文没有辜负她们多年来对我的关怀和期望。 深情感谢我的妻子刘萍女士。是她陪伴我度过了最艰难的日子，是她给本 来单调的0/1世界带来那么多欢乐，在我灰心沮丧时是她鼓励我充满勇气，我 要衷心地对她说声：谢谢！iv中国科学院计算技术研究所学位论文摘要如何让 Internet 更好地为人类服务， 是未来几年的一个真正挑战。 一方面 是人们对快速、准确而全面获取信息的渴望，而另一方面却是 Internet 上信息 的纷繁芜杂，在这两者之间架设一座桥梁的确是一个巨大的挑战。基于人工智 能的信息内容的自动聚类、分类和文摘，以及深层次的“知识检索”为迎接这 个挑战提供了新的支撑技术。 本文的目标就是在信息检索的背景下，从理论、 算法和应用三个层次来讨论聚类和分类技术。 本文首先全面分析了聚类和分类算法的关键技术，总结了在统计、机器学 习和模式识别等领域的聚类/分类算法。 本文随后从理论的层面来剖析聚类/分类算法。 我们发现聚类过程实际上是 在样本集上定义一种特定的等价关系，一个逐渐加细的等价关系序列和聚类谱 系图是相对应的，不同的等价标准就导致了不同粒度的聚类结果。从信息粒度 的角度看待聚类和分类，就能更清楚地看出它们之间的相通之处---聚类是在一 个统一、均匀的粒度下进行计算，而分类是在非均匀粒度下进行计算。由此出 发，还可以定义一种衡量特征空间与分类先验知识之间协调程度的定量度量， 并发展了一种崭新的、基于粒度的分类算法，实验结果表明这种分类算法有很 好的泛化能力。 从拟物的角度出发，我们提出了一种针对实数变量样本的聚类算法。选定 了特征空间之后，实际上就是把和领域相关的样本集转化成特征空间中的一群 点。把这些点想象成物理世界中一群质点，它们除了坐标不同之外，其他方面 没有任何的不同。这样，在由各质点形成的引力场中，从等势面的包含关系导 出存在一种奇妙的拓扑结构，现今关于化学键的研究表明正是这种拓扑结构构 成了化学键。从粒度的角度看，这种逐级包含的拓扑结构恰好又相应于一个逐 渐加细的等价关系序列，使用这种拓扑结构进行聚类得到很好的效果。 对于名义尺度变量的样本，我们则使用“规则+例外”和最小描述复杂度 的原理，提出了一种利用优化技术的聚类算法。名义尺度变量，比如：颜色取v中国科学院计算技术研究所学位论文值为“红” 、 “绿” 、 “兰”等，无法象实数变量那样定义加、减、乘、除等运算， 因此有必要发展新的算法。受 Rough Sets 中“规则+例外”策略的启发，我们 从描述复杂性的角度，把聚类问题转化成求样本集的最小描述长度的优化问 题，使用优化技术最终得到一个较好的聚类方案。 本文最后介绍了在文本处理中如何实际应用聚类算法。相对于关系数据库 中的样本来讲，文本实际上是一个无结构的字符流。要想进行聚类/分类操作， 首要任务就是选取特征，定义文本在各个特征上的权重，从而在特征空间中表 示文本。我们观察到文本和特征项的重要性之间存在着这样的一种对偶关系： ● 一个重要的文本就是包含许多重要词的文本； ● 一个重要的词就是经常出现在重要文本中的词； 这种对偶关系实际上是对重要性的一个循环定义，无法各自独立地定义文本和 词的重要性。我们使用迭代的策略来打破这种循环，并证明了这种迭代过程是 收敛的。实际上，如此定义的特征项恰好反映了文本集中最重要的概念，在 Dumais 的隐性语义检索中称为隐含概念。使用隐含概念空间以替代原始的词 空间，得到了良好的实验结果。 [关键词] 聚类/分类 杂性 信息粒度 势场 拓扑结构 聚类谱系图 描述复最小描述长度 规则+例外主特征向量 隐含概念vi中国科学院计算技术研究所学位论文ABSTRACTIt’s a real challenge for us to make Internet easier to use. The information in Internet is in short of organization, and full of a mass of pages, and on the other side, people want to obtain the information quickly and accurately. The technique of clustering, classification and abstracting based on AI, and so- called “Knowledge Indexing” technique, seemed as good approaches to solve such problems. This thesis aims to discuss the clustering/classification techniques with the background of information retrieval. At first, we summarize the key techniques used to do clustering/classification in different fields such as statistics, machine learning, pattern recognition, etc. We proposed a new classification algorithm based on theorem of “information granularity”. We found that clustering corresponds with a special equivalent relation on the sample set, and a series of equivalent relation with different information granularity correspond with a clustering diagram. From the view of granularity, thing is more clear that clustering is a procedure in a uniform granularity, while classification in different granularities. After selecting terms to represent the sample, we can treat the samples as points in the term space, which has the same weight and different coordinate. Let’s consider the energy field constructed by the universal gravity, we can obtain a topology structure from the relation among equilibrium curve with different energy. And the topology structure is corresponding with a special clustering diagram. We proposed a new clustering algorithm based on the topology structure, which shows good performance in the experiment. For the sample with nominal variables, it is difficult to define the fitful operation such as add, minus, multiply and division. From the view of minimum description length and theorem of “Rules + Exception”, we proposed a clusteringvii中国科学院计算技术研究所学位论文algorithm which treat the clustering problem as an optimizing one which aims to get the minimum description of the sample set. The experiment result shows the algorithm is very fast and always finds the shortest description of the sample set. We proposed a new algorithm to compute out a new concept space instead of the original term space in text clustering. There is a basic cycle in defining the importance of files and words. An important file is one containing more important words, and an important is such one that occurs more frequently in important files. We use an iteration procedure to obtain the weight of files and words, and project the files in the concept space instead of term space. The experiment shows that we could get better clustering result in such a concept space.[Keywords] Clustering/Classification,InformationGranularity,MinimumDescription Length, Rules + Exception, Energy field, Topology structure, Latent Conceptviii中国科学院计算技术研究所学位论文目录第一章 引言 ………………………………………………………………………………… 1 1.1 我们所期待的信息服务………………..…………………………………………. 1 1.2 聚类/分类的帮助………………..…………………………………………………. 4 1.3 本文的组织………………..………………………………………………………...6第二章 聚类/分类算法概述………………..……………………………………………….9 2.1 样本类型和相似性测度………………..……………………………………………9 2.1.1 2.1.2 样本类型………..………………………………………………………….9 相似性测度………………..………………………………………………102.2 聚类算法介绍………………..………………………………………………………13 2.2.1 2.2.2 2.2.3 2.2.4 2.2.5 2.2.6 聚类三步曲………………..………………………………………………13 几种常用的聚类策略………………..……………………………………15 类的定义………………..…………………………………………………16 聚类谱系图………………..………………………………………………17 系统聚类法………………..………………………………………………18 动态聚类法………………..………………………………………………222.3 分类算法介绍………………..………………………………………………………23 2.3.1 2.3.2 2.3.3 判别分析………………..…………………………………………………24 机器学习的思路………………..…………………………………………26 神经网络………………..…………………………………………………27第三章 聚类/分类中的粒度原理………………..………………………………………….29 3.1 聚类中的粒度原理………………..…………………………………………………29 3.1.1 3.1.2 3.1.3 信息粒度………………..…………………………………………………31 信息粒度的形式化描述………………..…………………………………31 不同粒度世界的关系………………..……………………………………32ix中国科学院计算技术研究所学位论文 3.2 分类中的粒度原理………………..…………………………………………………33 3.2.1 3.2.2 聚类结果和先验知识的不协调………………..…………………………34 从粒度的角度理解不协调性………………..……………………………353.3 统一在粒度框架下的聚类和分类………………..…………………………………37 3.4 基于信息粒度原理的分类算法………………..……………………………………39 3.5 实验结果………………..…………………………………………..………………..39 3.6 数据分析和小结………………..……………………………………………………41第四章 基于拓扑结构的聚类算法………………..………………………………………..43 4.1 拓扑结构和化学键………………..…………………………………………………43 4.2 拟物的思路………………..…………………………………………………………46 4.2.1 4.2.2 引力场模型………………..………………………………………………47 等势线圈的拓扑结构和聚类谱系图………………..……………………484.3 拓扑结构的计算………………..……………………………………………………50 4.4 实验结果和不足之处………………..………………………………………………52第五章基于描述复杂性的聚类算法………………..…………………….………………555.1 最小描述长度原理………………..…………………………………………………56 5.2 “规则+例外”的描述方法………………..……………………………………….58 5.2.1 认知心理学的启示………………..………………………………………585.2.1.1 概念结构………………..……………………………………………58 5.2.1.2 概念形成………………..……………………………………………60 5.2.2 5.2.3 机器学习的启示………………..…………………………………………63 描述方法的形式化表述………………..…………………………………645.3 优化技术介绍………………..………………………………………………………65 5.4 邻域的定义和启发式策略………………..…………………………………………68 5.5 实验结果………………..……………………………………………………………69第六章文本聚类中权重计算的对偶性策略………………..…………………….………716.1 文本的表示………………..…………………………………………………………71x中国科学院计算技术研究所学位论文 6.1.1 6.1.2 务实的统计路线………………..…………………………………………71 文本的形式化表示………………..………………………………………736.2 特征项的选择………………..………………………………………………………75 6.3 权重计算的对偶性策略………………..……………………………………………76 6.4 概念空间………………..……………………………………………………………82 6.5 概念空间在文本聚类中的应用………………..……………………………………84 6.6 概念空间在文本摘要中的应用………………..……………………………………85 6.7 小结………………..…………………………………………………………………85第七章总结和对未来工作的展望………………..…………………….…………………897.1 本文的贡献………………..…………………………………………………………90 7.2 进一步研究的方向………………..…………………………………………………90xi中国科学院计算技术研究所学位论文第一章引 言十八世纪的法国，在启蒙运动精神的鼓舞下，一些人士提出了一项雄心勃 勃、近乎幻想的规划：将全世界所有的知识汇集在一起，做成一本反映人类全 部文明的百科全书。然而两个世纪之后，当 Internet 看来就要将这个乌托邦式 的梦想付诸实现的时候，人们又发现了一个更加严峻的问题，那就是：我们如 何来使用这个知识宝库呢？我们如何来翻阅这本厚厚的百科全书呢？1．1 我们所期望的信息服务让 Internet 为人类服务，是未来几年的真正挑战。电子邮件甚至是电话会 议都已普及，然而这些应用并没有触及 Internet 的核心问题：Internet 的空间 是原始信息和分析结果的巨大储存库，Internet 是一个庞大而又充满着混沌的 网络。一方面，它为信息发布者提供了极大的言论自由：你可以非常容易地向 整个世界发布你的思想、高论抑或呓语，以你最钟爱的方式---文本、声音或者 图象；然而另一方面，这种快速、无序的增长对于信息的使用者来说却意味着 混乱---很多信息变得稀奇古怪、突然消失或者杂乱无章。那么，我们希望这本 没有主编的，因而有些杂乱无章的百科全书能够提供哪些服务呢？也许我们可 以从以下几个方面来概括：● 准确而全面的“人找信息”人们一直梦想有这么一种手段： 只要你说出想查询什么， 马上就能得到 所有符合要求的信息， 并且不被那些不相干的信息所打扰。 这实际上隐含 了对信息检索的两个要求：查全率和查准率。 查准率是检出文档之中真正符合检索意图的文档所占的比率，即：xii中国科学院计算技术研究所学位论文 正确文档数查准率 =检出文档数查全率是所有符合检索意图的文档之中被检出的文档所占的比率，即：正确文档数查全率 =应有文档数查全率和查准率反映了检索质量的两个不同方面， 二者必须综合考虑， 不可偏废。如果只考虑查准率，那么可以只检出 1 篇最有把握的文档，赌 正了查全率就是 100%，但是这样的话，符合要求的文档被检出的数目太 少，不能满足全面了解相关信息内容的要求；同样地，如果只追求查全率， 那么把所有的信息都端出来，查全率固然可以达到 100%，但是真正有用 的信息就都淹没在大量的无用信息之中了，无法满足快速地、有针对性地 了解信息内容的需求。因此，任何信息检索系统都要在查全率和查准率之 间进行权衡。 在网络时代说起信息检索，大家都会想到搜索引擎。现在的确有很多声名 显赫的搜索引擎，比如 Yahoo!、Excite 等，但是如果你因此而以为问题 已经解决的话， 那就大错特错了。实际使用过搜索引擎的人想必都有这种 体会：想查的东西查不着，不相关的东西倒是很多。构造更好的信息检索 系统仍然是人们努力的目标。● 主动的“信息找人”人们还有一个梦想， 希望能够象订阅报纸一样订阅 Internet 上的信息。 只需事前在某个地方登记对哪些信息感兴趣，或者干脆连这一步都省略 掉， 由某种机制从用户的浏览历史行为中学习出用户的兴趣， 然后只要有 人在网络上发布了相关信息，就能立刻推送到用户手中，也就是个性化、 主动化的“信息找人、按需服务” 。 既然是“信息找人” ，那么什么信息找什么人就是关键。每个用户都 有自己特定的信息需求， 设法获得这些信息需求， 进而使用这些信息需求xiii中国科学院计算技术研究所学位论文组成过滤条件， 对信息资源进行过滤， 就能把符合条件的信息抽取出来进 行服务。 个性化的实质是针对性，即对不同的用户采取不同的服务策略，提供 不同的服务内容；主动服务的实质是主动性，即不需用户做什么，系统自 动按照用户的需求来提供相应的服务。 个性化主动服务将使用户付出尽可 能小的努力，获得尽可能好的服务。● 信息的加工、过滤和整理Internet 上的信息浩若烟海而又纷繁芜杂， 怎样才能掌握尽可能多的 信息，同时避免那些令人讨厌的信息，始终是一个有意思的话题。 信息的加工和整理能够使得人们更好地掌握信息。在搜索引擎上，随 便输入一个查询，就能得到成千上万个页面，如果你想作全局了解的话， 除了逐篇阅读别无他途。 一种可行的解决办法就是把获得的大量信息进行 条理化，自动地将页面分检成不同的类别。初步的实验表明，把信息分组 并且每组都抽取出一个主题的做法有助于使用者找到他感兴趣的文件。 Internet 并不是一个和平的地球村，在网络空间中，人们不仅与熟人 或朋友进行商业和社交来往， 同时还要和形形色色的陌生人打交道。 换句 话说，Internet 上不仅存在数不清的机遇，同时也潜伏着许多危险。如何 避开那些令人讨厌的， 甚至是危险的信息， 就是信息过滤专家关注的课题。 这些只是人们对信息服务的各式各样需求的冰山之一角。总之，一方面是 人们对快速、准确全面获取信息的渴望，而另一方面却是 Internet 上信息的纷 繁芜杂，在这两者之间架设一座桥梁的确是一个巨大的挑战。1．2 聚类/分类的帮助对信息内容的自动聚类、分类和文摘，以及深层次的“知识检索”为迎接xiv中国科学院计算技术研究所学位论文这个挑战提供了新的技术。 聚类/分类是人们认识自然的一种重要手段， 在计算 机出现之后，人们就开始借助这一利器研究数据的自动分类问题。从计算的观 点看，如果分类原则是事先通过示例告诉计算机的，那么计算机在示例基础上 形成分类机制的过程就成为有监督的分类；如果事先没有任何示例，全凭数据 自身在某种角度上的相似性来分类，这时自然就谈不上遵守既定分类体系的问 题，那么这种分类过程就称为无监督的分类，也称为自动聚类问题[方开泰等， 1982]。聚类和分类都是机器学习、统计等领域关注的课题，随着相关研究的 开展，它们又被纳入所谓“数据挖掘”的框架之下。 用过检索系统的人都知道，很多文本在检索中是成团出现的。一“团”文 本要么都不出现， 要么同时出现。 无论是在网上信息的检索还是封闭文本检索， 都可以观察到这种现象。因此，这一“团”文本，在信息检索的意义上是等价 的，在这个等价意义下，一“团”文本可以看作一篇文本。在文本自动分类中， 也有这种文本成团入类的现象。求这种“团”的过程，就是文本聚类。 文本聚类/分类技术将大量的文本分门别类， 依据文本的语义将它们划归不 同的类别，从而可以更好地把握整个文本集。对于信息检索，文本聚类/分类技 术可以在如下几个方面有所助益：● 对于检索结果的组织：起初 WWW 仅仅是一些主页的无组织的杂乱集合，用户没有一个访问 这个庞大资源的有效入口，为了满足这方面的需求，人们又建造了 Alta Vista、InfoSeek、Excite 等大量的搜索引擎。 然而这些搜索引擎的检索结果却并不尽如人意―使用者输入一些关键 词， 一般都会得到成千上万的检索结果， 而且其中大部分页面都是不需要 的无关资料。 虽然有一些技巧试图给那些有较多关键词或者罕见关键词的 页面赋予更大的权重， 却仍然不能保证和用户意图最相关的页面一定被排 在最前面。 因此用户别无选择， 只能把检索到的页面一个一个再筛选一遍。 [Marti A. Hearst, 1997]等开发了一种称为“Scatter/Gather”的技术， 试图更合理的组织检索结果。这种技术对检索到的结果页面进行聚类/分 类操作， 按照页面彼此之间的相似程度分为若干组， 每组都有一个比较明xv中国科学院计算技术研究所学位论文确的主题，用户可以迅速地扫描每一组并选择那些和他的目标最相关的 组。● 加速检索过程：自然语言中词形和词义并不是一一对应的， 有很多一词多义和多词一义 的现象，这种现象使得仅仅依靠关键词的比较不足以获得满意的检索结 果。针对这种现象， [Dumais, etc 1990] 提出了一种称为隐性语义检索 （LSI：Latent Semantic Indexing）的算法，在大规模文本集合中提取出 隐含的概念， 进而使用在概念空间中的投影表示文本。 检索过程把用户输 入的检索项视为一个虚拟文本， 按照同样的方式计算其在概念空间中的投 影， 将这个虚拟文本和文本库中的所有文本逐个比较， 然后返回那些距离 比较小的文本。如果文本库中文本数目过多，这个过程将是非常耗时的。 一种可行的加速方案就是事前对原始文本进行聚类， 把那些近似程度较高 的文本分在同一个组内， 每个组都形成一个中心， 检索时只需和这些类中 心比较就可以了，这会大大加速整个检索过程。● 个性化信息推送：传统的获取信息的技术中用户是主动方， 因此可以称之为 “拉” （Pull） ， 与之相反的另一种方式则称为“推” （Push） ，由信息发布方主动地将信 息推送给感兴趣的用户。 要想快速完成信息分发步骤， 就要对用户进行分 类，类中诸用户拥有共同的兴趣。用户的兴趣可以使用用户自己提交的 Profile，或者用户访问过的文本集合来描述。文本聚类/分类技术可以把 用户分为对不同事物感兴趣的各个小团体。1．3 本文的组织本文的目标就是在信息检索的背景下，从理论、算法和应用三个层次来讨 论聚类和分类技术。xvi中国科学院计算技术研究所学位论文第二章是关于聚类和分类算法一个综述，总结了在统计、机器学习和模式 识别等领域的聚类/分类算法。 第三章主要从理论的层面来剖析聚类/分类算法。 我们发现聚类过程实际上 是在样本集上定义一种特定的等价关系，一个逐渐加细的等价关系序列和聚类 谱系图是相对应的，不同的等价标准就导致了不同粒度的聚类结果。从信息粒 度的角度看待聚类和分类，就能更清楚地看出它们之间的相通之处---聚类是在 一个统一、均匀的粒度下进行计算，而分类是在非均匀粒度下进行计算。由此 出发，还可以定义一种衡量特征空间与分类先验知识之间协调程度的定量度 量，并发展了一种崭新的、基于粒度的分类算法，实验结果表明这种分类算法 有很好的泛化能力。 第四章介绍一个针对实数尺度的变量的聚类算法。选定了特征空间之后， 实际上就是把和领域相关的样本集转化成特征空间中的一群点。把这些点想象 成物理世界中一群质点，它们除了坐标不同之外，其他方面没有任何的不同。 这样，在由各质点形成的引力场中，从等势面的包含关系导出存在一种奇妙的 拓扑结构，现今关于化学键的研究表明正是这种拓扑结构构成了化学键。从粒 度的角度看，这种逐级包含的拓扑结构恰好又相应于一个逐渐加细的等价关系 序列，使用这种拓扑结构进行聚类得到很好的效果。 第五章介绍一个针对名义尺度的变量的聚类算法。名义尺度变量，比如： 颜色取值为 “红” 、 “绿” 、 “兰” 等， 无法象实数变量那样定义加减乘除等运算， 因此有必要发展新的算法。受 Rough Sets 中“规则+例外”策略的启发，我们 从描述复杂性的角度，把聚类问题转化成求样本集的最小描述长度的优化问 题，使用优化技术最终得到一个较好的聚类方案。 第六章介绍在文本处理中如何实际应用聚类算法。相对于关系数据库中的 样本来讲，文本实际上是一个无结构的字符流。要想进行聚类/分类操作，首要 任务就是选取特征，定义文本在各个特征上的权重，从而在特征空间中表示文 本。我们观察到文本和特征项的重要性之间存在着这样的一种对偶关系：● 一个重要的文本就是包含许多重要词的文本； ● 一个重要的词就是经常出现在重要文本中的词。这种对偶关系实际上是对重要性的一个循环定义，无法各自独立地定义文本和xvii中国科学院计算技术研究所学位论文词的重要性。我们使用迭代的策略来打破这种循环，并证明了这种迭代过程是 收敛的。实际上，如此定义的特征项恰好反映了文本集中最重要的概念，在 Dumais 的隐性语义检索中称为隐含概念。 第七章对全文作出总结。 我们一直有一个想法，就是象做物理实验一样来研究信息科学，着重对实 验数据的分析和研究，并且尽可能地降低算法设计中的不确定性和随意性，本 文可以看作是沿着这个方向的一个尝试。xviii中国科学院计算技术研究所学位论文第二章 聚类/分类算法概述聚类/分类是人类认识未知世界的一种重要的认知手段。在生产和生活中， 人们往往面对非常复杂的事和物，如果能够把相似的东西归为一类，有明显区 别的事物分属在不同的类别中，处理起来就大为简便。所谓“物以类聚，人以 群分” ，说的就是这个道理。譬如人们将生物分为动物和植物，又根据不同的 生理特点将生物分为不同的门、纲、目、科、属、种；在化学理论中，人们根 据不同的化学性质将各种元素划分为不同的类别，比如卤族元素、惰性气体等 等，进而总结出元素周期率；在社会学中，人们还根据不同的信仰划分出不同 的党派、宗教等。 在原始的分类学中，人们的分类依据是经验和专业知识来进行定性分析， 很少使用数学工具。随着人类对自然和社会的认识不断深入，要处理的数据量 规模越来越大，相互关系也越来越复杂，分类越来越细，对分类的要求也越来 越高， 这时仅仅依靠定性分析就不能满足要求， 于是数学这个得力工具被引入， 形成了数值分类学 （Numerical Taxonomy） [Jardine N. etc. 1975][Sokal, R. etc. 1973]，对分析对象进行定量的研究。由于数值分类学中的方法不仅能够用于 分类，还能用于其他领域，于是人们觉得使用“聚类分析”这个名称更为恰当。 聚类分析的目的是揭示样本点之间最本质的“抱团”性质。要想定量地处 理一批样本点，首先必须对这些样本点的性质进行定量的表示。领域专家确定 采用哪些指标特征变量来精确刻画样本的性质，以及如何定义样本之间的相似 性测度。2．1 样本类型及相似性测度2．1．1 样本类型一般地，我们常常使用多个指标特征变量来描述一个样本点。指标特征变 量可以分为以下 3 种，不同类型的指标特征变量有不同的处理策略。xix中国科学院计算技术研究所学位论文间隔尺度：使用实数来表示的数量信息，比如温度、浓度、长度等。 有序尺度：特征变量取离散值，没有数量信息，但是具有次序关系，比如 成绩分为优、良、中、及格等。 名义尺度：特征变量取离散值，不仅没有数量信息，而且也没有次序关系， 它仅仅是个名称而已。比如肤色分为黄、白、棕、黑等。 对于间隔尺度的指标特征变量， 一个样本点实际上就是 Rn 空间中的一点， 可以很方便地定义加、减、乘、除以及各种复杂运算，它和我们的直观是很一 致的。而对于名义尺度特征变量就没有这么便利了，因为对于这种特征变量无 法定义合适的运算。所以，现在聚类分析的大部分研究都集中在间隔尺度特征 变量上，涉及一些名义尺度特征变量，对有序尺度特征变量就更少了。 假如我们选择了 n 个指标特征变量，那么 m 个样本点就可以表示成一个 mxn 的样本矩阵：Am *n? a 11 ?a = ? 21 ? ... ? ? a m1a 12 a 22 ... am2... ... ... ...a1n ? a2n ? ? ... ? ? a mn ?2．1．2相似性测度聚类分析按照样本在性质上的亲疏远近的程度进行分类。为了使类分得合 理，必须描述样本之间的亲疏远近的程度。刻画样本点之间的相似性主要有以 下两类函数：● 相似系数：两个样本点愈相似，则相似系数值愈接近 1；样本点愈不相似， 则相似系数值愈接近 0。 这样就可以使用相似系数值来刻画样本点性质 的相似性。● 距离函数：设使用 n 个指标特征变量来描述样本，那么我们就可以把每个样本点看作 n 维空间中的一个点，进而使用某种距离来表示样本点之间 的相似性，距离较近的样本点性质较相似，距离较远的样本点则差异较大。 那么，什么样的函数才能称为距离函数呢？xx中国科学院计算技术研究所学位论文设Ω是样本点集合，如果函数 D: Ω ×Ω→R 满足以下条件，我们都称之为 距离函数。 （1） 正定性 D(x,y)≥0 （2） D(x,x)=0 （3） 对称性 D(x,y)=D(y,x) （4） 三角不等式 D(x,y)+D(y,z)≥D(x,z) 有时我们定义的距离函数不满足三角不等式，从广义的角度我们也称之为 距离。而在另外一些场合，条件（4）被减弱为 （4’）D(x,y)≤max( D(x,z), D(z,y) ) 对于一切 z 使用条件 4’替代条件 4 得到的距离，我们称之为极端距离，它在系统聚类 法的分析中有很重要的应用。[任若恩，王惠文 1997] 聚类分析中常常采用以下 3 种距离函数：[方开泰 1986][张尧庭等 1982] 1． 明氏(Minkowski)距离? D q ( X ,Y ) = ? ? ?∑i| Xi? ? Yi | ? ? ?q1/q当 q 取 1,2,无穷大时，则分别得 （1） 绝对值距离 （2） 欧式(Euclid)距离 （3） 切比雪夫(Chebyshev)距离 因为明氏距离直观，计算简便，是实际应用中采用最多的一类距离函 数。值得强调的是欧式距离的一个优点：当坐标轴进行正交旋转时，欧式 距离保持不变。 因而如果对原坐标系进行平移和旋转处理后， 样本集合仍 然能够保持原来的相似结构。然而明氏距离也有不足之处： 首先，明氏距离受指标特征变量的量纲影响甚大。例如，一些特征变 量采用厘米为量纲表示身高， 另一些特征变量采用米为量纲； 还有一些特 征变量之间从根本上缺乏度量的可比性和一致性。 使用明氏距离时，特征 变量量纲一定要一致， 否则一些特征变量的作用将被淹没。 对于量纲相差 悬殊或没有一致语义的情况，可以首先对数据进行标准化处理以统一量xxi中国科学院计算技术研究所学位论文纲，然后再计算距离。 其次，明氏距离没有考虑指标特征变量的多重相关性。我们在选择描 述样本的指标特征变量时， 为了达到没有遗漏的目的， 常常对一种性质用 不同的名目多次描述， 这样就会造成信息重叠， 片面地强调了某一些性质， 其他的一些性质的作用就会被削弱。 克服多重相关性的方法一是慎重选择 描述指标特征变量， 根据领域知识或者采用特征变量聚类的方法， 选择合 适的特征变量集合；或者采用下述的马氏距离。 2．马氏（Mahalanois）距离D ( X , Y ) = ( X ? Y ) T ? ∑ ?1 ?( X ? Y )其中，∑是样本矩阵 A 的协差阵，是总体分布的协差估计量。 马氏距离是明氏距离的改进，它对于一切线性变换是不变的，克服了明 氏距离受量纲影响的缺点；马氏距离也部分克服了多重相关性。 马氏距离具有这么多优点， 是不是应该在聚类分析中尽量采用呢？然而以 下考虑使得它无法象想象中应用的那么广泛。在尚未形成类之前，直接采 用整体样本矩阵的均值和协差阵来求马氏距离，效果不是很好。比较好的 办法是使用各个类的协差阵来计算马氏距离，同类样本点之间距离应当采 用这一类的协差阵进行计算。可是这里面隐含了一个循环：类的形成依赖 于定义样本点之间的距离，而合理的马氏距离又依赖于类的形成，而且马 氏距离的计算量比较大，对于大规模的数据不太适用。马氏距离在分类算 法比较常用。 3． 兰氏(Lance)距离D ( X ,Y ) =∑i| X | Xi i? Yi | + Yi |兰氏距离克服了明氏距离受量纲影响的缺点，但是没有考虑多重相关性。 聚类分析中不仅要将样本点聚类，在有些场合还需要对特征变量进行聚 类。特征变量之间的相似性测度除了可以使用上述的距离函数之外，更常xxii中国科学院计算技术研究所学位论文用的是相似系数函数。如果一个函数 C:V ×V→[-1,1]满足以下条件，我们就 称之为相似系数函数。 (1) |C(X,Y)|≤1 (2) C(X,X) = 1 (3) C(X,Y) = C(Y,X) |C(X,Y)|越接近 1，两个特征变量间的关系越密切。经常采用的相似系数 有以下两种： a. 夹角余弦C ( X ,Y ) =∑iX i ? Yi2 i(∑ Xi) ? (∑ Yi )2 i这是受相似形的启发而来的，夹角余弦函数忽律各个向量的绝对长度， 着重从形状方面考虑它们之间的关系。 当两个向量的方向相近时， 夹角余 弦值较大，反之则较小。特殊地，当两个向量平行时，夹角余弦值为 1； 而正交时余弦值为 0。 b. 相关系数C ( X ,Y ) =∑i(Xii? X ) ? (Y i ? Y )i(∑ ( Xi? X ) 2 ) ? ( ∑ (Y i ? Y ) 2 )相关系数是对向量做标准差标准化后的夹角余弦。 它表示两个向量的线性 相关的程度。2．22．2．1聚类算法介绍聚类三步曲在实际应用聚类分析中，我们根据有无领域知识参与将整个过程分解为三 个环节，每个步骤都有其明确的任务，这样对于整个聚类分析的过程就会有更 清晰的认识。详见下图：xxiii中国科学院计算技术研究所学位论文原始样本 特征抽取 样本矩阵 聚类算法 聚类谱系图 选取阈值 聚类方案 领域知识 无领域知识参与 领域知识第一步是特征抽取。它的输入是原始样本，由领域专家决定使用哪些特征 来深刻地刻画样本的本质性质和结构。特征抽取的结果是输出一个矩阵，每一 行是一个样本，每一列是一个特征指标变量。 选取特征的优劣将直接影响以后的分析和决策。如果第一步就选择了和聚 类意图根本无关的特征变量，企图得到良好的聚类结果则无异于缘木求鱼。因 为无论后续步骤采用多么优良的聚类算法和阈值选择方案，都不可能计算出执 行者的意图。合理的特征选取方案应当使得同类样本在特征空间中相距较近， 异类样本则相距较远。 在有些应用场合还需要将得到的样本矩阵进行一些后处理工作。比如为了 统一量纲就对变量进行标准化处理，这样采用不同量纲的变量才具有可比性； 在有些场合可能选择的特征变量太多，不利于以后的分析和决策，这时可以先 进行一下降维处理；仅凭经验和领域知识选择的特征变量有可能是相关的，进 行主成分分析就可以消除变量间的相关性，从而得到一些相互独立的特征变 量。 第二步是执行聚类算法，获得聚类谱系图。聚类的输入是一个样本矩阵， 它把一个样本想象成特征变量空间中的一个点。xxiv中国科学院计算技术研究所学位论文聚类算法的目的就是获得能够反映 N 维空间中这些样本点之间的最本质的 “抱团”性质。这一步没有领域专家的参与，它除了几何知识外不考虑任何的 领域知识，不考虑特征变量在其领域中的特定含义，仅仅认为它是特征空间中 一维而已。 聚类算法的输出一般是一个聚类谱系图，由粗到细地反映了所有的分类情 况；或者直接给出具体的分类方案，包括总共分成几类，每类具体包含那些样 本点等等。 第三步是选取合适的分类阈值。在得到了聚类谱系图之后，领域专家凭借 经验和领域知识，根据具体的应用场合，决定阈值的选取。选定阈值之后，就 能够从聚类谱系图上直接看出分类方案。没有领域专家的参与，不考虑具体的 应用背景，而仅仅依赖于从聚类谱系图出发寻找聚类指数突变点，或者求最小 生成树的长边等等，往往不会得到满意的结果。 领域专家还可以对聚类结果结合领域知识进行进一步的分析，从而加深样 本点和特征变量的认识。 总之，实际应用聚类分析是一个需要多方参与的过程，它无法脱离开领域 专家的参与，聚类算法仅仅是整个聚类流程中的一环而已，光依靠聚类算法专 家一般不会得到满意的效果。 2．2．2 几种常用的聚类策略从上节的分析可知，聚类算法的输入是样本矩阵，它把样本视为 N 维空间 中的一点，目标是找出样本点之间最本质的“抱团”关系。有以下几种聚类策 略：[A.D. Gordan 1981][Brian Everitt, 1980][J. Van Ryzin, 1977] 1． 排序法（Sorting）这种策略适用于采用离散型特征变量的样本。 将特征变量按照重要性排序，首先选择最重要的特征变量，按照在这 个特征变量取值的不同将样本划归不同的子集。对于每个子集，接着 选择次重要特征变量进行分类，重复这种操作直到最后一个特征变量。 排序法得到的结果是一棵分类树，它的运行速度很快，但是对于特征 变量很多的情况则很不适用。xxv中国科学院计算技术研究所学位论文2．调整法（Switching）首先粗糙地分一下类，然后根据使分类函数最小 的原则对分类进行调整， 这种策略中以动态聚类法为典型。 分解法和合 并法的特点是一旦确定某个样本点属于哪一类之后就不再变化， 这就对 分解或并类操作提出了很高的要求， 初始操作失误会严重影响整体的聚 类效果。 调整法在这一点上表现得比较灵活， 它可以允许对前面的聚类 结果进行调整。调整法非常类似数值计算中的迭代法。 3．合并法（Joining）开始时每个样本自成一类，然后将最相似的两类合 并成一个新类， 使类的数目减少， 重复这种操作直到最后所有样本合并 成一类。 这种策略中以系统聚类法为代表， 聚类过程可以使用聚类谱系 图来表示。 4．分裂法（Splitting）和合并法恰好相反，分裂法开始时将整个样本集合 视为一类， 然后遵照某种最优准则将它分为两类， 一直分裂为每个样本 点各成一类。是否需要分裂操作，同时使用一个分类函数的值来控制。 当一类分得比较合理时，分类函数值较小；反之则较大。分裂法试图寻 求一种分类方案，使得分类函数值达到极小。 5．加入法（Adding）设已经存在一个分类方案（使用聚类谱系图或分类 树表示） ，每次加入一个新样本，按照某种规则确定其在分类系统的合 适位置，当样本全部加入之后，分类即告结束。 除了以上提到的策略之外，还有其他一些方法，比如应用模糊数学理论的 模糊聚类法、应用最小支撑树的图论法等等。 2.2.3 类的定义 由于客观事物纷繁芜杂的特性，以及我们在特征提取过程中用来表示样本 点性质的特征变量的不同选择，使得样本点的表示很不相同，在不同的问题中 类的定义也是不同的。 要想给类下一个通用， 严格的定义看来是不可能的， [Rao, C.R. 1977]提出以下几种不同的类的定义， 不同的定义适用于不同的应用场合。 设 G 表示一个有 k 个样本的集合，Si 表示其中的样本，T 和 V 为预设阈值 定义 1：如果对于任意 Si,Sj ∈G, 都有 D(Si,Sj)≤T, 则 G 称为一个类xxvi中国科学院计算技术研究所学位论文定义 2：如果对于每个 Si ∈G，都有 G 称为一类1 ∑ D ( Si , Sj ) ≤ T ，那么 k ?1 j定义 3：如果对于每个 Si,Sj ∈G，都有1 k * ( k ? 1)∑ ∑ D ( Si , Sj ) ≤ T 且 D ( Si , Sj ) ≤ Vi j那么 G 称为一类 定义 4：对于任意样本 Si，都存在 G 中一个样本 Sj，满足 D(Si,Sj) ≤T， 则称 G 为一个类。 以上几种定义中，定义 1 是要求最高的，凡是满足定义 1 要求的类，肯定 满足其他几种定义；凡是满足定义 2 的集合，也必定满足定义 3。 设有类 G， 类中共有 k 个样本， 我们常常从以下几个角度来刻画类的特征： 1．均值或重心S =1 k∑iSi2．样本协差阵 C，表示样本点的散布程度C = 1 k ? 1∑i(Si? S )( Si? S )T3．类的直径 R，类的直径有以下几种定义方法R = 1 k ? 1∑i(Si? S )T (Si? S )或者 R 采用 G 的最小支撑树的最大边长 2.2.4 聚类谱系图 大部分聚类算法的输出结果是一个聚类谱系图，它可以详细展现从总体归 为一类到所有样本点自成一类之间所有的中间情况，如果聚类谱系图的每个类 均标有其平台高度，则称之为标度聚类谱系图。[任若恩等，1997]xxvii中国科学院计算技术研究所学位论文标度谱系图可以用以下的二元组〈H，f〉来形式化地定义，其中 H 是类集 合，函数 f：H→R+表示 H 中每个类的平台高度。H 满足以下条件： (1) Ω∈H，其中Ω表示样本集，即：样本全集Ω一定是 H 的一个元素 (2) 对于任意的 S∈Ω，都有 { S } ∈Ω (3) 对于任意的 h1，h2 ∈H，若 h1∩h2=Ф，则必有 h1 包含于 h2 或 h2 包含于 h1。也就是说，H 中的任意两个元素要么不相交，要么就是包 含关系。 映射 f：H→R+满足以下条件： (1) (2) f(h) = 0 当且仅当 h 中只包含一个元素 若 h1 包含于 h2, 则 f(h1)&f(h2)。换句话说，f 具有单调性。比如对于右图所示的聚类谱系图，相应的形式化定义是：H = {{1}, {2}, {3}, {1, 2}, {1, 2,3}} f ({1}) = f ({2}) = f ({3}) = 0 f ({1, 2}) = 0.6 f ({1, 2,3}) = 0.81 23 0T30.6T20.8T1如果选取的分类阈值 T 取 T1（T1&0.8）时，那么所有样本点归入一类，相 应的分类方案是{1,2,3}；如果 T 取 T2（0.6&T2&0.8）时，则样本点被分为两 类，即{1,2}和{3}；如果 T 取 T3（T3&0.6）时，共分为三类，即{1},{2}和{3}。 一个聚类谱系图和一个距离矩阵是一一对应的。 即样本 Si,Sj 的距离等于同 时包含 Si 与 Sj 的，平台高度最小的那一类的 f(h)值。 2.2.5 系统聚类法 系统聚类法和 k-means 算法是目前聚类分析中应用最多的两种方法， 许多 著名的统计软件， 比如 SAS、 SPSS 等都包含相应模块。 本节介绍系统聚类法， k-means 算法在下节中介绍。xxviii中国科学院计算技术研究所学位论文2.2.5.1系统聚类法的工作步骤设样本集合Ω={S1,S2….Sn} STEP 1：计算 n 个样本两两之间的距离 D(Si,Sj)，记为初始距离矩阵 STEP 2： 初始构造 n 个类， 每个样本自成一类， 每一类的平台高度都是 0。 STEP 3： 寻找距离矩阵中的最小元素， 合并距离最近的两类形成一个新类， 并且以这两类间的距离作为新类的平台高度。 STEP 4：计算新类与当前各类的距离，更新距离矩阵。若类数等于 1，则 跳至步骤 5，否则跳至步骤 3。 STEP 5：依据结合情况和聚合指数画出聚类谱系图 STEP 6：选定分类阈值，决定类的个数和类。 除了需要定义样本点之间距离之外，还需要定义类间距离。设有样本点集 合 G1,G2 ，我们需要一种测度来衡量两类之间的相似性，即需要定义函数 f(G1,G2)， 不同的类间距离函数应用到上述程序中， 就会得到一种系统聚类法。 常用的类间测度函数有以下 5 种： 1． 最小距离 使用两类间的最近两点的距离来描述两类间的相似程度。D ( G 1 , G 2 ) = min{ D ( X , Y ) | X ∈ G 1 , Y ∈ G 2 }2． 最大距离 使用两类间的最远两点的距离来描述两类间的相似程度。D ( G 1 , G 2 ) = max{ D ( X , Y ) | X ∈ G 1 , Y ∈ G 2 }3． 重心法D ( G 1 , G 2 ) = D ( X , Y ), 其中， X 是 G 1的重心， Y 是 G 2的重心重心法是从物理意义出发，以类的重心代表此类，使用两类重心之 间的距离来描述类间相似性。 4． 类平均法D (G 1 , G 2 ) = 1 n1 * n 2∑ ∑i jD ( X i,Y j )类平均法使用 G1,G2 中两两样本点距离的平均值来表示类间距离。xxix中国科学院计算技术研究所学位论文5． 离差平方和法 Ward 从方差分析的观点出发，认为正确的分类应当使得类内方差 尽量小，而类间方差尽量地大。 样本集 G 的类内方差为S (G ) =∑i(Xi? X )T ( Xi? X )定义类间距离为D (G , G ) = S (G ∪ G ) ? S (G ) ? S (G ) 1 2 1 2 1 2每次选择类间距离最小的两类合并，使得 S(G)增加最小，最终得 到一个 S(G)的局部极小值。 值得指出的是，离差平方和法和重心法只适用于欧氏距离，不适用于采用 相似函数作为样本点间相似性测度的情形。 上述几种聚类方法初始矩阵都是相同的， （Ward 法中初始距离都乘以 2， 就得到和其他方法相同的距离矩阵，而乘以一个常数因子对于聚类结果是没有 影响的。 ） ，基本步骤也是相同的，它们的不同仅仅体现在计算距离的递推公式 上，因而如果能够总结出一个统一的递推公式模型，将大大有利于编制计算机 程序。[Lance, G.N and Willams, W.T. 1969]提出了一个计算公式，将以上几种 距离函数统一起来。 2.2.5.2 聚类方法比较和类数的确定显然，聚类结果和我们采用的样本点间距离函数以及类间距离函数都有极 大的关系，采用不同的距离函数，有时会得到截然不同的聚类结果。人们从多 个方面对系统聚类法的性质进行研究，得到一些初步的结论： 最短距离法使用于长条状或 S 形的类， 最长距离法， 重心法， ● 一般来讲， 类平均法，离差平方和法适用于椭球型的类。采用最小生成树的方法，可 以更加直观看到最短距离法的一种链现象的性质。Si,Sj 两个样本点在 N 维 空间中原来相距很远，但是由于存在最小生成树中一条通路连接 si,sj,可能 使得他们变得很近，由于链的存在使得点之间存在一种传递作用，这种作xxx中国科学院计算技术研究所学位论文用使得距离缩短了。因此，一般认为最短距离法适用于链状的类。● 我们用 Dk 表示第 k 次并类操作时的距离，如果一个系统聚类法能够保证{Di}是单调上升的， 那么我们称之为具有单调性。 可以证明， 最短距离法， 最长距离法，类平均法，离差平方和法具有单调性，重心法和中间距离法 不具有单调性。从聚类谱系图中可以看出，不具有单调性表现为出现一个 凹陷，并且不容易划分类。● 有人从极端距离矩阵的观点出发，认为相比于其他方法，类平均法既不太浓缩，也不太扩张，比较适中；因而从空间的浓缩和扩张的角度，他们 推荐类平均法。● 有人证明与初始距离距离矩阵 A 最接近的极端距离矩阵， 恰好是使用最短距离法得到的极端距离矩阵，而其他的浓缩类系统聚类法都不具有这 个最优性质。从这个角度出发，最短距离法比较受到推崇。 总之，从不同的角度评价各种聚类算法，会得到不同的结论，对各种聚类 算法的比较现在仍然是一个值得研究的课题。 当绘出聚类谱系图之后，一个重要的工作就是如何决定类数。一种常用的 方法是在聚合指数发生突变的地方砍一刀，按照谱系图将样本点划分至不同的 类。 实际应用还可以结合图论的方法， 比如求最小生成树的长边， 把长边砍断， 则最小生成树分解成互不连通的几部分，每部分自成一类；按样本点周围的密 度分类等等。问题领域专家的参与也是一种非常重要的方法。 系统聚类法能够得到完整的聚类谱系图，可以详细地说明从 1 类直到 n 类 的所有聚类方案， 是实践中应用最广的一种算法。 但是系统聚类法的计算量大， 而且共有 8 种选择聚合指数的方案， 对于一些题往往得到截然不同的聚类结果， 很难说能够达到聚类分析试图反映样本点之间最本质的“抱团”性质的目标， 并且让使用者也很难取舍。 2.2.6 动态聚类法xxxi中国科学院计算技术研究所学位论文使用系统聚类法时，一旦某个样本点被划为某一类之后就不再变化，这要 求划分时要非常准确；而且系统聚类法要计算距离矩阵，处理大样本时存储开 销较大。 类比于数值计算中的迭代法， [MacQueen, J. 1967]等提出了动态聚类 法，首先给出一个粗糙的初步分类，然后按照某种原则动态修改聚类结果，直 到得到合理的分类结果。 动态聚类法一般需要人为给定类数 k， 或者一些阈值。 动态分类法执行步骤如下： STEP 1：选择 k 个初始凝聚点，作为类中心的估计 STEP 2：对每一个样本，按照某种原则划归某个类中 STEP 3：重新计算各类的重心 STEP 4：跳转到 STEP 2 直到各类重心稳定。 初始凝聚点是一批有代表性的点，是希望形成类的中心，可以采用以下几 种方法来选择： 1． 前 k 元法：直接取前 k 个样本作为初始凝聚点。 2． 经验法： 凭经验确定样本点集合分为几类， 对每一类指定一个代表 点。 3． 随机法： 首先确定将样本集合分为几类， 然后将每个样本点随机地 分配给每一类，计算每一类的均值作为初始凝聚点；或者直接随机 指定几个样本点作为初始凝聚点。 4． 密度法：先人为给定两个数 d1,d2(d2&d1)，对每一个样本点统计 和它相距不超过 d1 的样本点数目，并称为它的密度。将样本点按 照密度由大到小排列，首先将密度最大的样本点加入到凝聚点集 中，然后考虑密度次大的样本点，如果该点到现有的任一凝聚点的 距离都大于 d2,则将该样本点加入到凝聚点集中，否则放弃该点。 如此按照密度序进行下去，就会得到一个凝聚点集合。 得到初始类中心之后，一般采用最近邻法将其他样本划归不同的类。对于 每个样本点，计算它和每个凝聚点之间的距离，并且将它归入和它最近的凝聚 点所有的类。 动态聚类法还有一个成员，就是美国标准局经过多年研究之后，提出的自 组织 ISODATA 算法[Ball, etc. 1965]。ISODATA 是一个很繁琐的算法，它有 6xxxii中国科学院计算技术研究所学位论文个参数，可以控制算法当某个类中元素过多并且过于分散时，就会将此类分解 为两类；而当某个类中元素过少时，就会执行和另外一类的合并操作。这样的 自组织过程会比较灵活地控制类的数目。然而从算法设计的观点来看， ISODATA 并不是一个很好的算法，由于它拥有过多的参数，使得整个算法难 以调优，在实际应用中调参数是一项令人非常头疼的工作。 动态聚类法的目标是将样本集合分为 k 类，每一类都聚集在离凝聚点周围 的一个小区域， 而且类与类间是可以比较明显地区分。K-means 算法运算速度 快，内存开销小，比较适合于大样本量的情况，但是聚类结果受初始凝聚点的 影响很大，不同的初始点选择会导致截然不同的结果；并且当按最近邻归类时 如果遇到到两个凝聚点距离相等的情况，不同的选择也会造成不同的结果。因 此动态聚类法具有很大的不确定性，并且初始类数的确定需要领域专家参与。 动态聚类法是一种迭代算法，而迭代算法的一个重要性质就是是否收敛。 [MacQueen, J. 1967]使用随机过程理论证明了 k-means 算法是收敛的，后来 Diday 给出了一个初等的证明。2.3分类算法介绍分类实际上是有教师的学习过程。它的特点是根据已经掌握的每类若干样本的数据信息，总结出分类的规律性，建立判别公式和判别规则。然后，当遇 到新的样本点时，只需根据总结出的判别公式和判别规则，就能判别该样本点 所属的类别。 分类技术是很多领域，比如统计领域、模式识别、人工智能、神经网络等 的研究课题。本节将简要介绍各种主要的分类算法。[边肇琪，1988][蔡云龙， ．1 判别分析 [任若恩等，1997]分类技术在统计分析领域中被称为判别分析，比较有名的算法有 Bayes 判 别法、Fisher 判别函数法、距离函数法和 k-近邻法等。xxxiii中国科学院计算技术研究所学位论文●Bayes 判别法：从概率统计理论我们知道 Bayes 公式可以如下表述：设 B1,B2…Bn 是全 样本空间 S 的划分， 且概率 P(Bi)≥0。 对于某个事件 A， P(A) ≥0， 则有 Bayes 公式：P ( Bi | A ) =P ( A | Bi ) P ( Bi ) ∑ P ( A | Bi ) P ( Bi )i设有两个总体 G1 和 G2，从使得误判概率最小的角度，我们可以使用如下 的判别规则：? X ∈ G 1，若 P ( G 1 | X ) & P ( G 2 | X ) ? ? X ∈ G 2，若 P ( G 2 | X ) & P ( G 1 | X ) ? 待判，若 P ( G | X ) = P ( G | X ) 1 2 ?Bayes 公式的特点是利用以往对研究对象的认识―先验概率来辅助判断， 以期得到更精确的分析结论。它在使误判概率或风险最小的意义上是最佳的， 但是 Bayes 分类器需要已知条件概率， 而且其决策面往往是超曲面， 形状复杂， 难以计算和构造。● 线性判别函数法实际问题往往遇到决策面是线性的（直线或者超平面） ，计算和构造都很简 单，因此即使遇到决策面不是线性时，我们也宁可牺牲错误率最小这个最优原 则，努力构成线性函数。 对于图 2.3.1 所示的两类分类问题，线性分类法的目标就是寻找一条直线：g(X ) = WT? X + w 0 ，这条直线能够能够尽可能地将两类样本分开。Fisher 线性判别函数是一个经典的判别方法。它的核心思想是进行坐标变 换， 寻找能将样本尽可能分开的方向。 考虑把 n 维空间的样本投影到一条直线 上，形成一维空间，为了避免投影后不同样本混杂在一起，不易区分，可以将 直线转动，寻找一个方向使样本的投影尽量分开，也就是说，使得类间差异尽 可能大，类内差异尽可能小。 在有些情况下，比如多峰分布，每类是由几个相距较远的团组成，直接采xxxiv中国科学院计算技术研究所学位论文用线性分类函数来进行分类，错判率就会很大，可以考虑采用分段线性分类法 降低错判率。形象地看，在多峰分布下，分类决策面是一个超曲面，可以采用 类似折线的分段线性函数来逼近超曲面。 Chang 法就是实现分段线性分类的一 种手段，但是它需要事先根据先验知识确定线性判别函数的数目，这一点常常 不容易满足。[容观澳，1994]●● ●●●●○○●○ ○ ○ ○○○ ○ ○ ○图 2.3.1● 距离函数法和最近邻判别法模式分类中最简单直观的方法就是基于距离函数的分类法。 它的核心思想 是使用一类的重心来代表这个类，计算待分类样本到各类重心的距离，归入距 离最近的类。 在判别分析中常采用马氏距离， 因为马氏距离既考虑了类的均值， 又包含了类内方差的信息，对训练样本中蕴涵的信息利用得比较充分。采用马 氏距离的基本假设是各类均为正态总体。 如果允许类中全部样本点都可有资格作为类的代表的话， 这就是最近邻法。 最近邻法不是仅仅比较与各类均值的距离，而是计算和所有样本点之间的距 离，只要有距离最近者就归入所属类。 为了克服最近邻法错判率较高的缺陷，k-近邻法不是仅选取一个最近邻进 行分类，而是选取 k 个近邻，然后检查它们的类别，归入比重最大的那一类。● 支持向量机传统统计学理论是在样本数目趋于无穷大时的渐进理论，在训练样本数有 限的情况下效果不是很好。1995 年，V.Vapnik 对小样本统计学习理论进行系 统化，并在此基础上发展了一种通用的学习方法―支持向量机(SVM：Support Vector Machine)。[V.N. Vapnik, 2000][张学工，2000]xxxv中国科学院计算技术研究所学位论文SVM 的基本思想是使用简单的线性分类器划分样本空间。 对于在当前特征 空间中线性不可分的模式，则使用一个事先选择的非线性映射把样本映射到一 个高维空间中，在这个空间中构造最优分类超平面。● 势函数法势函数法采用“拟物”的思路，将特征空间中的点视为物理空间中的点。 每个样本点都看作一个能量源，在该点上电位达到峰值，而随着与该点距离的 增大，电位分布迅速减小，换句话说，把样本空间中的电位分布看作一个势函 数 P(x)。构造合适的势函数，使得在一类样本点周围形成“高地” ，在另一类 样本点周围形成“低谷” ，在两类电位分布中间选择合适的等位线，作为分类 的判别函数。势函数法在一些实验样例中取得很好的结果。 2．3．2 机器学习的思路人工智能领域中的机器学习方向就是研究怎样学出分类规律的，认为知识 就是分类。机器学习比较适用于具有离散型变量的样本，对于连续型的变量， 常常采用一些离散化的手段把它们转化成离散值。传统的机器学习算法有两大 代表， 一是基于覆盖的 AQ 家族算法， 一是以信息熵为基础的 ID3 决策树算法， 最近又出现了基于 Rough Sets 理论的学习算法。● ID3 决策树算法[Quinlan, 93]ID3 是 Quinlan 于 1986 年提出的一种重要的归纳学习算法。 它有以下三个 特点：使用一棵分类决策树表示学习结果；决策树的每个节点都是样本的某个 属性，采用信息熵作为节点的选择依据；采用了有效的增量学习策略。● AQ11 算法[Michalski, R.S. etc. 1980]AQ11 使用逻辑语言来描述学习结果。整个学习过程就是一个逻辑演算过 程：E P ∧ ? E N = ( e1 ∨ e 2 ... e k ) ∧ ? ( e1 ∨ e 2 ... e m )xxxvi+++???中国科学院计算技术研究所学位论文= (e1 ∧ ?e1 ∧ ?e2 ... ∧ ?em ) ∨ ....(ek ∧ ?e1 ∧ ?e2 ... ∧ ?em )其中，eI+∈EP 表示正例样本集合中的一个正例样本，其中，eI-∈EN 表示反 例样本集合中的一个反例样本。然后使用分配率和吸收率对上式进行简化。 ● 基于 Rough Sets 理论的机器学习算法[王珏等 98]+???+???Rough Set 是波兰数学家 Pawlak 提出的一种对不确定性知识的表示方法， 现在则常被用来做数据约简。数据约简去除那些对于分类不起作用的元素，可 以分为只删除一个属性值的值约简，以及删除整个属性的属性约简。数据约简 可以在保持分类一致的约束下大大简化样本数据，最终使用很少的几条逻辑规 则就能描述分类规则。 2．3．3 神经网络神经网络领域采用感知算法进行分类。[Rosenblatt.F. 1962]采用感知机模 型来解决机器人的感知问题，[Rumelhart, D.E. etc. 1986]采用 sigmoid 型作用 函数，并提出了 BP 算法。在这种模型中，分类知识被隐式地储存在连接的权 值上，使用迭代算法来确定权值向量。当网络输出判别正确时，权值向量保持 不变，否则进行增加或降低的调整，因此也称为奖惩法。 可以证明，对于线性可分的情况，感知判别算法是收敛的。对于线性不可 分的情况，一般都是不收敛的，可以采用最小均方误差准则。神经网络分类器 的一个首要问题就是确定神经网络的结构，不良结构会使得训练过程很慢或根 本不收敛。现在有些学者致力于神经网络结构的演化研究。[朱大铭, 1999]xxxvii中国科学院计算技术研究所学位论文第三章 聚类/分类中的粒度原理聚类和分类之间有着紧密的关系。从表象上看，聚类是指无导师的学习， 而分类是有导师的学习，然而，这只是非常表面的看法。实际上，聚类的目的 是发现样本点之间最本质的“抱团”性质，选定了样本的特征之后，样本点就 表示为特征空间中一些点集，如果再选定样本点之间的相似性测度函数，那么 聚类的结果就应该是确定的，总之，聚类是样本点“抱团”性质的一种客观反 映。而分类在这一点上却大不相同，分类需要一个训练样本集，由领域专家指 明哪些样本属于一类，哪些样本属于另一类，但是分类的这种先验知识却常常 是纯粹主观的---有些领域专家认为某些样本点应该属于同一类，而另外一些专 家从另外的角度出发，可能认为这些样本点应该分属不同的类别---总之，你无 法预先限定别人的奇思异想。从特征空间的角度来看，聚类是把那些相似性测 度函数值较大（比如距离最小）的样本点归为一类，而先验知识可能规定距离 非常遥远的两个样本点属于同一类别。换句话说，先验知识极有可能是和特征 以及相似性测度函数是不协调的。 本章主要从信息粒度的角度来看待聚类和分类技术，试图使用信息粒度原 理的框架来统一聚类和分类，并且根据粒度原理设计了一种崭新的分类算法， 在大规模中文文本分类的应用实践表明这种分类算法有很强的泛化能力。3．1 聚类中的粒度原理聚类算法的结果一般都使用聚类谱系图来表示。比如对于图 3.1.1 中的 4 个样本点，相应的聚类谱系图见图 3.1.2。 从聚类谱系图中可以看出，如果我们选取的分类阈值 t 足够大的话，那么 所有的样本点都被归为一类；如果 t2&t&t3，那么所有的样本点被分为两类， 样本点{3，4}归为一类，剩余的样本点归为另一类……随着 t 的减小，类数越 来越多，直到所有的样本点自成一类。xxxviii中国科学院计算技术研究所学位论文●1●2●3●4t1 图 3.1.1t2t3图 3.1.2打个形象的比方，这个过程和使用显微镜来观察切片非常类似（见图 3.1.3） ―这里的阈值和镜头的放大倍数起着相似的作用。如果放大倍数小的话，在我 们的视野中，4 个样本点表现成一个团，看不出各个独立的点；如果我们换个 放大倍数高一些的镜头，就会在视野中看到两个团，这时能够区别出两个团， 但是团内各个样本点却区别不开……当放大倍数足够高时，就可以区别出各个 独立的样本点来。图 3.1.3聚类操作实质上是在样本点之间定义一种等价关系。属于同一类的任意两 个样本点被看作是等价的，可以认为它们具有相近的性质，在当前的阈值尺度 下是没有区别的。一个等价关系就定义了样本点集合的一个划分，它把样本点 划分成一些子集，一个子集就对应着聚类形成的一个类。 和由大到小的一系列阈值相对应，会形成由粗到细的一族等价关系。采用 较大的阈值时，展现在我们面前的是样本点集比较“粗”的轮廓，一些细枝末 节被忽略掉了；而采用较小的阈值时，就能够比较精细地刻画样本点之间一些 细微差别。进一步说，这一族粗细不等的等价关系之间又存在一种奇妙的关系 ----“细”等价关系继承了“粗”等价关系的部分性质，用数学语言来说，这xxxix中国科学院计算技术研究所学位论文一族等价关系形成一个偏序格结构。 3．1．1 信息粒度上面提到的所谓“粗”和“细” ，只是一种很不严格、感性的提法，它隐约 指示了人们在认知和处理现实世界的问题时，常常采用从不同层次观察问题的 策略， 这种策略可以使用信息粒度原理更加准确、 严格地来表述。 [张钹， 张铃， 1990] 提出了信息粒度的概念，并且作出了非常精辟和彻底的论述。粒度 （Granularity）本来是一个物理学概念，意指“微粒大小的平均度量” ，在这 里则被借用做“信息粗细的平均度量” 。物理粒度涉及对物理对象的细化划分， 而信息粒度则是对信息和知识细化的不同层次的度量。[邵健, 2000] 之所以提出信息粒度的概念，是因为人工智能和认知科学研究者们观察到 人类智能的一个公认特点，那就是人们能从极不相同的粒度上观察和分析同一 问题。 “人们不仅能在不同粒度的世界上进行问题求解，而且能够很快地从一 个粒度世界跳到另一个粒度的世界，往返自如，毫无困难。这种处理不同粒度 世界的能力，正是人类问题求解的强有力的表现。 ” [张钹，张铃，1990]以工厂组织为例说明信息粒度的概念。设想一位策划 全厂生产规划的计划人员，当他考虑全厂的总的生产规划时，他会忽略掉工厂 的许多具体细节：机床是什么样子，安装在什么地方等等。这时，工厂在他看 来只不过是由若干车间组成的方块图，即他以很粗的粒度来描述工厂。随着计 划的深入，当不能不考虑车间内部的细节时，他又进入一个较细粒度的世界观 察和分析问题。一旦需要重新考虑某个全局性问题时，他又返回到工厂的粗粒 度世界。总之，他可以在不同粒度的世界中来去自由。 但是，无论是状态空间法，还是问题归约法，都难以把上述现象描述清楚。 而信息粒度的概念则有助于把人类的这种能力形式化。 3．1．2 信息粒度的形式化描述我们使用一个三元组( X, F,г)来描述一个问题，其中：xl中国科学院计算技术研究所学位论文X 表示问题的论域，也就是我们要考虑的基本元素的集合。比如对于上述 的工厂例子中，X 就表示组成工厂的车间、机器等全体。 并设 F 是属性函数，定义为 F: X→Y，Y 表述基本元素的属性集合，比如 车间的员工数、机器台数等。 Г表示论域的结构，定义为论域中各个基本元素之间的关系。 从一个较“粗”的角度看问题，实际上是对 X 进行简化，把性质相近的元 素看成是等价的，把它们归入一类，整体作为一个新元素，这样就形成一个粒 度较大的论域 [X] ，从而把原问题 ( X, F, г ) 转化成新层次上的问题 ( [X], [F], [г])。 粒度和等价关系有着非常密切的联系。实际上，上面所说的简化过程和商 集的概念完全相同。因此，可以使用如下的粒度世界的数学模型： 设在论域 X 上定义一个等价关系 R， 并由 R 得到与之相应的商集[X]=X/R， 然后将[X]当作新的论域，对它进行讨论，并称之为对 X 进行 R 划分，相应地 得到一个较粗粒度的世界[X]。这样，就将粒度世界和数学上的商集完全统一起 来，以商集作为粒度世界的数学模型。问题的不同粒度表示对应着不同的等价 关系 R，也就对应着对论域不同的划分。 至于如何选择 R 以对论域 X 进行划分， 就要针对具体的应用目标作具体分 析了。在实际问题求解中，粒度的选择可能是动态的，即先进行一次比较粗的 划分，在这个粒度上进行推理和分析，得到论域的一些初步性质，再进一步精 细划分，直至问题的解决。 3．1．3 不同粒度世界的关系对一个问题，有时需要同时在粗细不同的粒度世界中进行问题求解，因此 有必要研究不同粒度世界之间的关系。 设 R 表示由 X 上一切等价关系 R 所组成的集合， 可以如下定义粒度的 “粗” 和“细” 。 定义：设 R1,R2 ∈R, 如果对于任意的 x, y ∈X, 都有 x R1 y → x R2 y，那么就称 R1 比 R2 细，记为 R1≤R2xli中国科学院计算技术研究所学位论文[张钹，张铃，1990]证明了如下的定理： 定理：R 在如上定义的“≤”关系下形成一个完备半序格。 这是一个非常深刻的定理。它揭示了有关粒度的核心性质，其他性质都以 此为基础。有关它的详细证明请参阅[张钹，张铃，1990]的第 10-11 页。 还是以上述的工厂为例，如果把工厂的全体职工看作一个类，即定义 R0： 一切属于 X 的 x 都等价，那么 R0 就是最粗的一个粒度；如果以车间为单位划 分 X，定义关系 R1：属于同一车间的 x 是同一类，就得到一个比较细的关系； 继续进行划分直到把每个职工独自看成一类，即定义 Rn：x Rn y 当且仅当 x=y，就不能再继续划分了。这样就得到如下的序列：Rn≤ Rn ?1..... ≤ R 1 ≤ R0直观地看，如上操作得到的序列和一棵 n 层的树是相对应的。设 T 是一棵 n 层的树，所有叶节点构成集合 X。对于任意一个节点 p，我们使用 Tree(p) 表示以 p 为根的子树的叶节点的集合， 那么每一层节点都对应着 X 的一个划分。 而聚类操作得到的聚类谱系图恰好也是一棵 n 层树， 因此必定存在一个等价关 系序列与之对应，这也就是聚类和粒度之所以相通的原因。 选定一个等价关系之后，就会从较细的粒度世界( X, F,г)到达一个相对较 粗的粒度世界( [X], [F], [г])，粒度变粗实际上是对问题的简化，值得探讨的是 在粗粒度世界里，哪些基本性质仍然继续保持。[张钹，张铃，1990]对于两种 特殊情况，(X,г)是拓扑空间及(X,г)是半序空间作了一些研究，研究表明经过 简化的粗粒度世界仍然能够保持细粒度世界的部分性质。 总之，利用适当的划分在粗粒度世界中讨论问题，若问题在粗粒度世界中 就无解的话，那么在细粒度的原问题上也无解。因为粗粒度世界比原来的问题 要简单，所以一般就能够缩小问题求解的范围，加快求解速度。自然，经过简 化的粗粒度世界必然会造成信息的损失，这时可以把粒度适当地减小，使得论 域个体之间的可区别性增大，以对我们感兴趣的性质做比较精细的研究。3．2分类中的粒度原理和聚类试图尽可能忠实地反映样本点之间“抱团”性质的目标不同，分类xlii中国科学院计算技术研究所学位论文实际上是一个学习过程。 对于给定的一堆样本点， 先由领域专家确定分成几类， 每一类都包含哪些样本点，分类算法的目标就是探索每一类样本点的规律。不 妨从着色的角度来更加直观形象地理解分类的本质：选定特征之后，样本集就 被表示成特征空间中一群点，我们可以按照先验知识来给样本点着色，使得同 一类样本点有同样的颜色，而不同类的样本点的颜色也不同，研究目标就是摸 清楚：红色点有什么规律？绿色点又有什么规则可循？再来一个新的样本点， 当投射到同一个特征空间之后，我们判断它应该染成红色、绿色还是其他某种 颜色呢？ 3．2．1 聚类结果和先验知识的不协调最理想的先验知识自然是以下的情形：在特征空间中，异类样本点之间有 明显的界限， 相似性测度较小； 而同类样本点则聚集成一团， 相似性测度较大。 或者从聚类的角度说，先验知识中规定的某一类中的样本点，依照选定的特征 空间和相似性测度，也应当聚成一类。然而不幸的是，在绝大多数情况下，都 不会达到这种理想境界，常常遇到情况的却是领域专家认为应该归为一类的 点，往往在特征空间中距离特别远，或者说相似性测度特别小；而那些被认为 分属不同类的样本点，却距离非常近，相似性测度特别大。换言之，聚类结果 和先验知识之间往往存在某种不协调性。XOR 问题可以作为这种不协调性的 一个典型代表。Y A● ●DB●●C X图 3.2.1.1假设有如图 3.2.1.1 所示的 4 个样本点 A,B,C,D，选定的特征 X,Y，采用欧 氏距离作为相似性测度，这 4 个样本点在特征空间中的位置如图所示。领域专 家从某个角度出发认为分两类比较合适， 其中 A,C 构成一类， B,D 构成另一类， 或者从着色的角度说，A,C 被染成黑色，B,D 被染成白色。然而在选定的特征xliii中国科学院计算技术研究所学位论文空间中，A 和 B 离得比较近，A 和 C 离得反而较远，B 的情况和 A 类似，如果 要求对这 4 个样本点聚成两类的话，应该是 A,B 一类，C,D 一类。 这种不协调性增加了分类的难度。因为如果同一类的样本点在特征空间中 分布地很开，甚至和其他类的样本点混杂在一块的话，我们就很难找到隐藏在 表象之后的，之所以将这些样本点如此分类的原因。再比如对于最近邻算法， 它使用同一类样本点的重心作为此类的代表，新样本点只需和各类的重心比 较，归入距离较近的那一类。然而对于上面的例子来说，事情就变得复杂了： A,C 的重心是 O1 和 B,D 的重心 O2 是重合的，任何一个新样本点到两个类中 心的距离都是相同的，新样本点将无所适从。 造成这种不协调性有两个方面的原因：首先，聚类是一个试图客观忠实反 映样本点之间的抱团性质的过程，当选定了特征空间和相似性度量函数之后， 那么聚类结果就确定了；其次，分类的先验知识却是由人来主观决定的，对于 同一个样本集合，不同人会有不同的、甚至是迥异的分类方案。这种主观和客 观的差异是不可避免的，反映在分类过程中，就是聚类结果和先验知识之间的 不协调性。 3．2．2 从粒度的角度理解不协调性Rough Sets 理论是 1991 年由波兰数学家 Z. Pawlak 提出的，对不确定知 识进行表示的理论。它的贡献表现在以下两个方面：一是提出了一套新的对不 确定性信息进行表达的理论；二是从这种表示方法出发，提出了一种数据约简 理论， 描述了什么是数据库中的冗余数据， 以及如何删除这些冗余数据。 Rough Sets 对于知识表示是一种非常有效的理论，它和粒度是密不可分的， 在这里我 们借用 Rough Sets 的体系和术语来描述聚类结果和先验知识的不协调性。首 先简要介绍以下 Rough Sets 理论： Rough Sets 理论认为知识就体现在分类上。设 U 是非空有限集合，称为 论域。U 中每个元素称为对象，并设有定义在 U 上的等价关系 R，商集 U/R 表示根据 R 对 U 中对象的划分：U/R={X1,X2….Xn}，每一个等价类 Xi 称为一 个范畴。将二元组（U,R）称为一个知识库。从这种知识表示体系出发，Roughxliv中国科学院计算技术研究所学位论文Sets 理论定义了一个重要的不确定性度量：粗糙度。 设 R 是论域 U 上的等价关系，U 的任意一个子集 X 都可以由以下两个集 合来近似描述，或者说使用现有的知识体系来近似描述：R ( X ) = ∪ { Xi | Xi ? X , Xi ∈ U / R } R ( X ) = ∪ { Xi | Xi ∩ X ≠ φ , Xi ∈ U / R } Boundary (X ,R) = R(X ) ? R(X )这两个集合分别称为 X 的 R 下近似（R-lower Approximation）和 R 上近 似(R-upper Approximation)，下近似表示 X 中可以完全使用现有知识表示的对 象，上近似则表示所有和 X 有关的的范畴。如果上近似和下近似不同，就说明 待表达的集合 X 不能由现有的知识体系精确的反映，就说 X 是粗糙的。而上 近似和下近似的差异，也就是边界 Boundary(X,R)的大小就能够定性地说明 X 在现有的知识体系 R 之下的粗糙程度。 采用 Rough Sets 框架可以很容易地表示聚类和先验知识之间不协调性。 从上一节可以看出，聚类谱系图实际上是定义了一个粒度逐渐变细的等价关系 序列，选择一个阈值实际上就是选定一个等价关系 R，进而可以得到商集，也 就是知识体系 U/R。 如果由先验知识规定的类 X 能够使用现有的知识体系精确 表达，就表示聚类结果和先验知识是协调的；而如果上近似和下近似不相同的 话，就说明聚类结果和先验知识是不协调的，这种不协调性的程度可以使用 X 的 R 边界 Boundary(X,R)的大小来定性表示。详见图 3.2.2。论域 U 边界 X 下近似图 3.2.2xlv中国科学院计算技术研究所学位论文3．3统一在粒度框架下的聚类和分类有两种策略来消除这种不协调性。一种方法是变换特征空间，在当前的特 征空间中不容易区别各类，但是变换一下特征空间就有可能使得各类之间的区 别暴露出来。比如， Vladimir N. Vapnik 提出了支持向量机理论（ SVM ： Supported Vector Machine） ， 其核心思想就是用简单的线性分类器划分样本空 间，对于那些非线性可分的模式，则采用一个核函数将样本空间映射到适当的 高维空间，在这个高维空间下是线性可分的；张铃和张钹教授提出的球面投影 算法和 SVM 有异曲同工之妙，其基本思想是将 n 维的样本点投影至 n+1 维的 球面上，使用超平面对其进行划分。然而，在有些应用场合下，不希望引入新 的特征，只能继续使用原有的特征空间。我们以下的讨论即是沿着这条思路。 其实，如果都从粒度的角度看的话，就会发现聚类和分类之间存在某些相 通之处。仍然就上节中的例子继续讨论，对于由先验知识规定的类 X，如果在 一个粒度比较粗的 R 决定的知识体系下，只能得到比较粗糙的表示， Boundary(X,R)也比较大；而在一个粒度比较细的 R 决定的知识体系下，就能 得到比较精细的表示，Boundary(X,R)也比较小。 考虑一种极端的情况，假如我们选择粒度最细的等价关系 R，也就是每个 对象自成一个等价类，那么在这种 R 决定的知识体系之下，类 X 能够得到最 精细的表达，此时的边界 Boundary(X,R)等于 0，换句话说，粗糙度等于 0。 然而粗糙度的降低是有代价的， 因为采用如此细的粒度来表达 X 实际上只是对 X 中元素的简单枚举，我们并没有挖掘出构成类 X 元素的任何规律。 上面所说的极端情况给我们以很大的启发：我们的目标是寻找一个知识体 系，这种知识体系一方面能够精确地表达先验知识规定的类 X，同时又能表示 构成类 X 诸元素的规律。因此我们放弃统一或者均匀粒度的设想，而采用一种 非均匀粒度的知识体系。具体的方案描述如下： 对于类 X，我们首先选择一个比较粗的粒度 R1，计算 X 的 R1 下近似和 R1 边界，因为在当前的知识体系之下，X 的 R1 下近似已经能够精细表达，无需 进一步的操作，我们只需考虑尚不能精确表达的 X 的 R1 边界。对于边界中诸xlvi中国科学院计算技术研究所学位论文元素，我们可以适当进入细节，采用更细的粒度 R2，再计算 X 的 R2 下近似和 R2 边界， 扣除掉能够由 R2 精细表达的 R2 下近似， 继续进行这种操作直到边界 为 0。采用非均匀粒度表示 X 的详细情况见图 3.3.1。论域 U 边界 X 下近似图 3.3.1 采用非均匀粒度方案的结果，就是把类 X 分解成一些小类的并集 X=X1∪ X2∪…∪Xn，每一个小类都采用不同的粒度，是在相应粒度之下能够精细表达 的最大子集。而连接符号“∪”的数目，恰恰能够定量地反映出当前选择的特 征空间和相似性测度函数与先验知识之间的协调程度， 如果 “∪” 的数目很少， 就表示当前选择的特征空间和相似性测度函数比较支持这种先验知识，否则就 表示其中存在着较大的不协调性。 概括地说，我们首先尽可能地使用粗的粒度来表示，因为如果能用粗粒度 的、简单的区别手续体现出类内元素的构成规律，使聚类结果与先验知识协调 起来，就没有必要把问题复杂化；而对于那些边边角角中的元素，由于在大粒 度世界里不容易看出它们之间的区别，易于造成和其他类元素的混淆，只有适 当地“换一下镜头” ，采用较小一些的粒度，才能够更准确地对它们加以区分。图 3.3.2 至此，我们可以用一句话来总结聚类和分类：聚类是在一个均匀的、统一xlvii中国科学院计算技术研究所学位论文的粒度下来描述样本集， 而分类是在非均匀粒度