面向数据特性的聚类算法研究

来源 :中国科学院研究生院 中国科学院大学 | 被引量 : 0次 | 上传用户:fishwatcher
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在信息时代,人们在享受信息带来的便利的同时,也承受着信息过剩所引发的困扰。人们被海量信息淹没,却越来越难找到自己真正想要的信息。对海量信息进行有效组织成为一个亟待解决的难题。在这样的背景下,聚类作为一种重要的文本分析与管理方法,被应用到了信息时代的方方面面,如加速信息检索的过程,提高检索的准确性,更合理地组织检索结果等。信息时代的信息具有来源的多样性、结构的多样性等特点,从而决定了其分布上的多样性。然而,聚类算法通常基于自身固有的模型假设,很难为数据的分布调整自身策略,这就导致了算法模型假设与数据真实分布之间的模型不匹配问题。本文的工作即围绕模型不匹配问题展开。   经典的聚类算法可分为如密度聚类、网格聚类等基于局部的聚类算法,以及除此之外的面向全局的聚类算法,在这两个方面,我们分别展开了对应的工作以缓解算法模型与数据分布之间的差异,进而提高聚类性能。   在局部聚类方面,我们的工作针对代表性的密度聚类算法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-Rk-means算法的时间复杂度保持在与k-means算法同一时间量级,聚类性能却得到了明显提高。而M-R谱聚类算法则通过M-R框架的帮助,缓解了原谱聚类算法在局部信息上进行全局聚类的根本缺陷。M-R框架通过分析数据的全局分布特性,并将这些分布特性引入聚类过程,从而为谱聚类算法引入了全局信息,聚类结果也更为准确。通过参数设置与收敛性的分析,我们将M-R谱聚类的时间开销压缩到了与原谱聚类算法一个量级,使得M-R谱聚类在有效的时间开销内尽量提升聚类性能。M-R框架通过与多个聚类算法的结合,证实了自身的有效性和通用性,也表明了其具有与更多聚类算法进行结合的潜力。
其他文献
伴随着互联网技术的迅猛发展,人们对网络的依赖程度越来越高,网络的商业价值也越来越大。然而,网络测量技术相对滞后的研究现状,使得电信运营商无法对互联网实施有效的管理。
分布式业务网络(Distributed Service Network,简称DSN)是中国移动针对电信业务和移动互联网业务所提出的新一代可运营、可管理的分布式核心网体系和功能架构。即通过一个接
网格是一种解决复杂科学问题的新兴计算平台,网格中包含大量异构、分布式、跨管理域的资源,这给网格资源管理带来了极大的挑战。传统的以系统为中心的资源管理策略只考虑系统
航天型号研制集中了国家高新技术发展的前沿成果,投入了大量的资金,组织了庞大的研制队伍,是典型的高技术项目,如何缩短研制周期、降低研制成本、提高系统可靠性及增强作战能力一
好的数控编程系统不仅能减少用户的学习和使用负担,还能在很大程度上提高数控机床的加工精度,提高产品的市场竞争力。   数控图形轨迹编程是在数控语言编程上发展起来的,克服
3G网络为用户提供了高带宽的移动网络接入,这为运营商满足用户个性化的多媒体通信服务需求提供了可能。为了能实现各种增值业务的快速部署,3GPP在Release5版本中引入了IP多媒体
从上世纪70年代第一个单片机的诞生到现在,经过40多年的发展,嵌入式系统已经无处不在,小到移动电话、家用电器、电子娱乐设备等,大到工业制造、航空航天、环境工程等,都离不开嵌入
随着移动通信技术的发展,各种接入技术层出不穷,从GSM,Wi-Fi到WCDMA,TD-SCDMA,甚至LTE,为用户提供了丰富多彩的接入方式和服务。为了充分利用各种网络资源,移动终端需要在传统意义上
疵点是影响织物成品质量的重要因素之一,如何高效、快速的判定疵点织物以及如何准确的标记出疵点位置是一项具有实际意义的课题。本文从实际应用角度出发,首先讨论了与织物疵
多核处理器因其高性能、低功耗的显著特点在嵌入式实时系统中的得到越来越广泛的应用。多核处理器虽然能够提供更好的平均性能,但是多核系统中大量存在共享资源,位于不同核心