符号聚类新方法的研究及应用

论文摘要

聚类是一门非常重要的技术。所谓聚类就是按照某种度量（相似性度量、不相似性度量或距离）,根据一定的准则将个体集合分成若干类,使得同类个体之间的相似程度大于不同类个体之间的相似程度即做到”物以类聚”,其目的是要挖掘出个体集合的信息。目前的常用聚类方法大致可以分为层次聚类、划分聚类、基于模型的聚类、基于密度的聚类、基于网格的聚类等。聚类技术已经被广泛得应用于分类学、生物信息学、商业、医学、图像处理等领域。传统的聚类技术处理的对象都是连续的数值型数据（我们称之为传统数据,其中包括模糊数据）。但是,现在我们发现,在很多场合中我们无法用传统的数据来很好得表达信息,例如物体的颜色（或许你会认为,可以用不同的数值来代表不同的颜色,但是那样的数值也仅仅是不同颜色的代码,已不再是传统意义上的数值,自然不能用传统的数值方法来处理）、用户的反馈、某个地区某段时间内的气温范围等等,这些数据不像传统的数据那样有序、单值、连续,而且有时候同一个体的不同特征的取值之间存在着一定的关系,我们把这类数据统称为符号数据。随着符号数据越来越多得出现,产生了专门分析处理符号数据的领域——符号数据分析（SDA,Symbolic Data Analysis）,而聚类是其中重要且不可替代的分支。符号聚类分析就是研究如何将传统聚类中的技术引入符号数据分析中,并且在需要的情况下创造出符合符号数据特性的新聚类理论和方法。本着这个原则,本论文主要针对三种常见的符号数据——名词性数据、区间数据、混合数据（即一部分特征是符号特征,一部分特征是传统特征）,在前人工作的基础上,做了一些研究改进。对于名词性数据,过去常用Hamming Distance来简单度量,但是Hamming Distance太粗糙,不能充分挖掘隐藏在数据中的信息。本论文中采用了智能优化算法中粒群优化算法（PSO,Particle Swarm Optimization）,通过训练得到适合于对应数据集的距离公式。层次聚类的实验结果表明了,在度量名词性数据上,通过PSO学习得到距离要优于简单的Hamming Distance。对于区间数据,我们采用了相互距离（MD,Mutual Distance）的概念,给出了一个适用于区间数据的相互距离公式,并在此度量的基础了,引进了最新的聚类方法——相似性传播聚类（APC,Affinity Propagation Clustering）,避免了符号聚类中心如何表示的问题。最后的实验证明了我们的算法要优于基于Euclidean Distance的C均值算法（CM,C-means）。对于混合数据,由于之前的混合数据聚类中没有考虑到不同的特征对于聚类的贡献不一样。因此本文在对混合数据进行模糊C均值聚类（FCM,Fuzzy C-means）时,考虑特征权重问题,推导出适用于混合数据的带特征权重的模糊C均值算法。最后的实验也表明了考虑特征权重的合理性和必要性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 研究意义与目标
• 1.4 论文结构
• 第二章 符号聚类概述
• 2.1 符号数据
• 2.2 符号度量
• 2.3 符号聚类中心的表示
• 2.4 聚类方法
• 2.4.1 C 均值
• 2.4.2 模糊C 均值
• 2.4.3 层次聚类
• 2.5 评价准则
• 2.5.1 CR 准则
• 2.5.2 Davies-Bouldin 准则
• 2.5.3 规范化Hubert’s Statistic
• 2.5.4 Dunn’s 准则
• 第三章 名词性数据聚类
• 3.1 研究意义、现状及目标
• 3.2 距离学习
• 3.2.1 距离学习的重要性
• 3.2.2 基于粒群优化的距离学习
• 3.3 实验及分析
• 3.3.1 实验一
• 3.3.2 实验二
• 3.3.3 实验三
• 3.4 小结
• 第四章 区间数据聚类
• 4.1 研究的意义、现状及目标
• 4.2 相互距离
• 4.3 相似性传播聚类算法
• 4.3.1 相似性传播聚类算法
• 4.3.2 基于相互距离的相似性传播聚类算法
• 4.4 实验及分析
• 4.4.1 实验一
• 4.4.2 实验二
• 4.5 小结
• 第五章 混合数据聚类
• 5.1 研究的意义、现状及目标
• 5.2 混合数据的不相似性度量
• 5.2.1 符号特征分量的不相似性度量
• 5.2.2 模糊特征分量的不相似性度量
• 5.3 混合数据的中心表示
• 5.4 带特征权重的混合数据的模糊C 均值算法
• 5.4.1 模糊隶属度
• 5.4.2 事件隶属度
• 5.4.3 模糊特征中心
• 5.4.4 符号特征权重
• 5.4.5 模糊特征权重
• 5.5 实验及分析
• 5.5.1 实验一
• 5.5.2 实验二
• 5.5.3 实验三
• 5.6 小结
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 致谢
• 参考文献
• 附录：作者在攻读硕士学位期间发表的论文