面向数据特性的聚类算法研究
文献类型：学位论文
| 作者 | 曾依灵 |
| 答辩日期 | 2011-03-22 |
| 文献子类 | 博士 |
| 授予单位 | 中国科学院研究生院 |
| 授予地点 | 北京 |
| 导师 | 白硕 |
| 关键词 | 文本聚类, 模型不匹配, 空间映射, 尺度变换 |
| 学位专业 | 其它专业 |
| 英文摘要 | 在信息时代，人们在享受信息带来的便利的同时，也承受着信息过剩所引发的困扰。人们被海量信息淹没，却越来越难找到自己真正想要的信息。对海量信息进行有效组织成为一个亟待解决的难题。在这样的背景下，聚类作为一种重要的文本分析与管理方法，被应用到了信息时代的方方面面，如加速信息检索的过程，提高检索的准确性，更合理地组织检索结果等。信息时代的信息具有来源的多样性、结构的多样性等特点，从而决定了其分布上的多样性。然而，聚类算法通常基于自身固有的模型假设，很难为数据的分布调整自身策略，这就导致了算法模型假设与数据真实分布之间的模型不匹配问题。本文的工作即围绕模型不匹配问题展开。 经典的聚类算法可分为如密度聚类、网格聚类等基于局部的聚类算法，以及除此之外的面向全局的聚类算法，在这两个方面，我们分别展开了对应的工作以缓解算法模型与数据分布之间的差异，进而提高聚类性能。 在局部聚类方面，我们的工作针对代表性的密度聚类算法OPTICS展开。OPTICS算法以数据的局部密度作为聚类判断的依据，当一个点的邻域密度大于指定阈值时，认为其在某个簇内，否则认为其在簇与簇的边界。算法总是朝着数据点尽可能密集的方向扩张，以期搜索出一个个类簇。然而，这种贪心式的搜索策略使得那些处在略微稀疏的区域的数据点总被放在最后处理，从而割裂了数据点与其邻域的局部关系，降低了聚类性能。针对OPTICS算法的这个缺陷，本文提出了针对性的解决策略，为每个数据点增加一个referrer域，以记录数据之间的局部关联，并通过这种局部关联对聚类结果进行重新整理，使数据点能够被放入到更为合理的类簇中。改进后的OPTICS算法被称为OPTICS-Plus算法，它充分考虑数据的局部特性，从而也获得了更好的聚类性能。 在全局聚类方面，我们提出了一种面向全局数据特性的聚类框架。该框架基于空间映射（Mapping）和尺度变换（Rescaling），因此也被称为M-R聚类框架。M-R框架的基本思想是对数据中各个类簇的全局分布特性进行分析，并针对这些分布特性进行空间变换，从而使得变换后的空间更为契合理想的模型假设。M-R框架首先将数据映射到一个特别构造的坐标系中，以分析各个类簇的分布特性，接着以这些分布特性为基础进行尺度变换，以归一化各个类簇的尺度。在归一化的尺度下，数据分布更为理想，距离度量更为合理，聚类决策也更为准确。在迭代策略下，M-R框架通过与聚类算法相互修正的方式提升聚类性能。 我们分别将M-R框架应用到了k-means算法及谱聚类算法上，形成了M-R k-means算法及M-R谱聚类算法。M-R k-means算法在M-R框架的帮助下，将数据面向k-means算法的理想模型假设进行映射，从而使得数据分布更为满足算法的模型假设。M-R k-means算法的时间复杂度保持在与k-means算法同一时间量级，聚类性能却得到了明显提高。而M-R谱聚类算法则通过M-R框架的帮助，缓解了原谱聚类算法在局部信息上进行全局聚类的根本缺陷。M-R框架通过分析数据的全局分布特性，并将这些分布特性引入聚类过程，从而为谱聚类算法引入了全局信息，聚类结果也更为准确。通过参数设置与收敛性的分析，我们将M-R谱聚类的时间开销压缩到了与原谱聚类算法一个量级，使得M-R谱聚类在有效的时间开销内尽量提升聚类性能。M-R框架通过与多个聚类算法的结合，证实了自身的有效性和通用性，也表明了其具有与更多聚类算法进行结合的潜力。 |
| 学科主题 | 自然语言处理 |
| 语种 | 中文 |
| 公开日期 | 2011-03-28 |
| 分类号 | TP3 |
| 源URL | [http://ictir.ict.ac.cn/handle/311040/1006]  |
| 专题 | 中国科学院计算技术研究所学位论文_2011博士 |
| 推荐引用方式 GB/T 7714 | 曾依灵. 面向数据特性的聚类算法研究[D]. 北京. 中国科学院研究生院. 2011. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。