论文部分内容阅读
聚类分析是一种重要的无监督学习方法,作为数据分析的工具,其重要性在模式识别、图像处理等各个领域都得到了广泛的认可。聚类分析的目的是寻找隐藏在数据中的结构,并按照某种相似性度量,尽可能地使具有相同性质的数据归于同一类。近年来,各类数据及其信息量以指数形式增长,面对大规模数据,由于受到时间、内存、CPU等资源的限制,传统的聚类算法处理能力不再“高效”,而普遍存在着单位时间内处理量小、面对大规模数据时处理时间较长、难以达到预期效果等缺陷。如何对大规模数据进行有效聚类,得到了广大学者的关注,也已成为国际数据挖掘领域的重点。针对现有聚类算法不能有效处理大规模数据的问题,本文分成二大部分开展了研究:第一部分,面向大规模复杂数据,结合并行计算及云计算技术,针对划分聚类算法和谱聚类算法,设计了两种并行聚类算法,分别是基于MapReduce的抽样划分聚类算法和云环境下高效并行谱聚类算法;第二部分,面向复杂网络、生物基因、图像分割等特定领域中的大规模数据,分别设计了聚类集成发现复杂社区算法F-DC、加权半监督聚类图像分割算法WSSC和基因差异共表达双聚类算法DCECluster。本文的主要研究成果如下:(1)提出了一个基于抽样划分聚类算法的通用框架,并为其设计了MapReduce实现。具体而言,我们先采用改进的抽样技术去处理大规模数据集的表示;而后提出了一种抽样划分聚类算法的通用框架,并通过实现k-means和k-medoids算法来验证框架的有效性;此外,在此基础上,我们使用MapReduce编程模型实现了提出的框架。实验显示,针对大规模数据集,本文提出的方法是有效的。(2)提出了高效的并行谱聚类算法。并行化谱聚类算法的策略是:改进了距离矩阵和相似度矩阵,引入kd树技术,用于对相似度矩阵进行稀疏化处理;在计算特征向量时,把拉普拉斯矩阵存储于Hadoop文件系统上,通过分布式Lanczos运算获得特征向量;最后使用高效的并行k-means聚类对特征向量的转置矩阵进行处理获得聚类结果。通过对算法的每一步采用不同的并行策略,使得整个算法在速度上获得线性增长。实验表明,随着处理数据规模的扩大,聚类速度达到差不多线性的增长,提出的并行谱聚类算法适合海量数据挖掘。(3)提出了高效的社区发现聚类集成算法F-DC。算法的具体做法是:先提出了时间演变网络模型,并对每个聚类进行了统一描述;针对真实网络随时间进化演变特征,提出了基于聚类分割的网络快照产生聚类成员的方法;考虑到每个聚类成员的聚类中心分布和实际分布的差异,提出了基于最大似然法集成聚类结果的方法。通过大量实验的评估,验证了面向时间演变网络社区发现的聚类集成算法有效性。(4)提出了一种面向彩色图像分割的加权半监督聚类算法WSSC。算法首先提出了在传统半监督聚类算法中权重的概念并给出了计算公式。在此基础上,通过优化可能性矩阵获得了类标签。对于每一副图像,都可以表示成一个d维随机向量,每个像素点可由混合密度独立获取。利用WSSC算法,图像分割结果可以通过混合组件类标签获得。通过在二组图像数据上的一系列实验结果证明,提出的算法WSSC效率较高,特别是针对大规模彩色图像优势明显。(5)提出了一种新的基于粗糙集的多值样本属性离散化方法,进而提出了一种基于基因差异共表达样本权值图和搜索剪枝策略的最大双聚类挖掘算法DCECluster。算法首先把离散化的数据集构建成基因差异样本关系权值图,有效去除了无关的基因,通过基因差异共表达关系,定义了新的差异支持度概念,最后使用有效的搜索策略和剪枝策略对产生的候选双聚类进行剪枝。通过对4种不同差异共表达双聚类算法在有效性和效率方面的实验验证,显示出所提出的算法具有运行速度快、挖掘的有效双聚类数目多、节省内存等优点。大规模数据,作为信息化社会无形的生产资料,在智慧城市建设中呈现爆发式增长态势,它就像血液一样遍布智慧交通、智慧医疗、智慧生活等智慧城市建设的各个方面,对大规模数据进行复杂的分析、挖掘,可得出一系列规律以供决策与服务。本文取得的研究成果可以为智慧城市建设提供很好的支持。