高维数据的若干聚类问题及算法研究

发布时间：2017-12-23 14:20

本文关键词：高维数据的若干聚类问题及算法研究　出处：《哈尔滨工业大学》2015年博士论文　论文类型：学位论文

【摘要】：随着社会化媒体和移动互联网技术的快速发展,各种新应用如微博、微信和Digg等不断涌现。这些新应用改变了在传统上用户只能被动的接收数据的信息传播方式,使得用户可以主动参与信息的创造和传播。在用户使用这些应用的过程中,产生了大量高价值的数据和信息。如何有效地从这些数据中挖掘出有价值的知识是目前国际上的研究热点之一。高维数据聚类是数据挖掘中一种重要的无监督学习技术,众多国内外研究者利用高维数据聚类技术来挖掘社会化媒体数据中的知识,已取得了一定的研究成果。然而,同传统的高维数据相比,这些新应用产生的数据呈现出新的特点。首先,由于用户群体的复杂性和用户在使用过程中的随意性,产生的数据往往是多噪音、高维稀疏的。其次,随着应用的复杂化,产生的数据通常包含异构多视图特征,并且随着大量用户的参与,数据的规模也越来越大。这导致传统的方法不适用于新形势下产生的高维数据集。近年来,研究人员提出了一些针对于这类大规模高维复杂数据的聚类算法,如高维子空间聚类、利用外部知识库扩展稀疏数据聚类、矩阵分解等方法。但是这些研究中存在信息利用不充分、需要外部辅助知识、不能解决异构特征融合等缺点。本文针对高维数据中的多噪音、稀疏性、特征融合和高计算复杂度问题,结合现有的子空间聚类和非负矩阵分解等方法,提出了一系列新的高维数据聚类方法。本文主要研究工作和创新包括以下四个方面：首先,本文提出了一种能够同时利用簇内散度和簇间散度的子空间聚类框架。基于该框架,提出了三种扩展kmeans聚类算法：无特征加权的扩展简单kmeans聚类算法,向量特征加权的扩展自动变量加权kmeans聚类算法和矩阵特征加权的扩展属性加权聚类算法。同时,通过理论分析,证明了三种扩展kmeans聚类算法的收敛性。相比于传统的kmeans聚类算法,扩展加权kmeans算法能够利用簇间散度进行更加有效地特征选择,降低噪音维度在聚类中所起的作用,从而提高算法的聚类性能。最后在人工数据集和真实数据集上的实验结果表明扩展kmeans聚类算法优于传统的kmeans聚类算法。其次,本文提出了STCEK (Short Text Clustering with Extending Keywords)算法以解决高维稀疏短文本数据聚类问题。该算法主要思想是根据词在文档中的共现性提取概念,利用概念之间的语义联系构建出概念图,通过划分概念图得到概念簇。最后,利用概念簇来丰富每个短文的语义,改善短文本的特征空间稀疏性问题,从而提高短文本聚类效果。由于STCEK算法只是利用数据集内部信息来扩展短文本,不需要引入外部辅助知识库,因此,一般不会引入外部噪音。通过与传统无扩展关键词聚类算法和基于Wikipedia扩展关键词算法的实验对比,STCEK算法能够获得更好的聚类性能。然后,本文提出了MNMF (Multiple Nonnegative Matrices Factorization)算法以解决多视图(多类型特征)数据聚类问题。该算法把数据中包含的多种类型特征表示成多个非负矩阵,然后通过联合多非负矩阵分解方法来聚类。同时,为了得到簇在时间维度上的演化趋势,算法在矩阵分解过程中采用时间平滑约束以缓解噪音数据造成演化趋势上的震荡。同时,通过理论分析,证明了该算法能够收敛到局部最优解。最后,在TDT5数据集和NIPS数据集上的实验结果表明MNMF算法优于现有的多视图聚类算法。最后,本文提出了PMNMF (Parallel Multiple Nonnegative Matrices Factoriza-tion)算法以解决大规模多视图数据聚类的高计算代价问题。该算法也是基于多非负矩阵分解方法,其基本思想是把多非负矩阵分解转化为矩阵乘法、矩阵加法、矩阵按元素乘除等操作,然后利用图形处理单元(GPU)在这些操作上的速度优势,提高多非负矩阵分解的速度。最后,在人工数据集和真实数据集上的实验结果表明PMNMF算法比串行的MNMF算法具有明显的速度优势。总体而言,本文针对高维数据中多噪音、特征稀疏性、异构多视图特性和高计算复杂性,分别提出了四种算法：扩展kmeans算法、STCEK算法、MNMF算法和PMNMF算法。其中,MNMF算法是PMNMF算法的前置工作。本文的研究将为高维数据聚类带来新的思路,同时这些算法也给舆情分析、精准营销、社会化搜索等应用系统带来更多的选择。
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP311.13

【共引文献】