论文部分内容阅读
随着科学技术的发展,人类收集数据的能力大幅度提高,各个行业都已经或正在积累大量的数据,人们需要对这些数据进行分析推理获取有意义的信息,而聚类分析研究上取得好的成果,对于数据分析推理具有重要的意义。谱聚类方法是众多聚类分析方法中的一支独秀,是聚类分析相关领域的一个研究热点。谱聚类方法能在任意形状的样本空间上聚类,且收敛于全局最优解。谱聚类方法能够揭示数据的低维的非线性特性,可以用于各种对象的降维,在降维的同时也将这些对象嵌入到欧式空间,所以谱聚类方法可以执行各种数据的聚类。但是,谱聚类方法的计算复杂度过高,故谱聚类方法的诸多优点只适合小数据集,面向大规模数据集的谱聚类方法研究并不多。当今,很多行业积累的数据量都非常庞大,为了获取大规模数据集更好的聚类分析成果,使得数据分析推理更精确、更有效,研究面向大规模数据集的谱聚类方法是必要的。首先,针对大规模数值型数据集的谱聚类,其Laplacian矩阵特征分解的时间复杂度及空间复杂度过高,受增量协方差无关方法计算主成分思想的启发,提出一种快速计算Laplacian矩阵的前k个最小特征向量的方法。该方法构建两个对称半正定矩阵,使其前k个最大特征向量与Laplacian矩阵的前k个最小特征向量相同,通过循环输入构建矩阵的列向量,增量方法计算出Laplacian矩阵的前k个最小特征向量。该方法所用空间为n量级,特征分解时间复杂度为线性时间,有效解决了谱聚类中Laplacian矩阵特征分解的问题。实验证明该方法能够快速特征分解Laplacian矩阵。其次,针对这样一类大规模混合型数据集,随着时间的推移,样本数量呈爆炸式增长,而样本的属性空间变化则逐渐趋于固定范围,提出一种基于准超图像映射的谱聚类方法,有效解决了这类混合型数据集的划分问题。量化数据集的每个属性,由每个属性的量化份数确定准超图像的每个维的尺寸,根据量化公式将大规模数据集映射到准超图像,并确定像素相似度函数。使用谱聚类方法划分准超图像,则能够获得数据集的全局分布情况。数据集到准超图像的映射计算是线性的,准超图像的像素规模已经很小,采用谱聚类所用时间也会很少,而通过映射极大地减小了数据的存储空间,故该方法满足时间和存储的要求。实验结果表明,该方法能够迅速处理此类大规模混合型数据集的划分问题,同时获得数据的全局分布情况。再次,针对大规模异构信息网络的结构特点,利用异构信息网络的稀疏性,提出一种基于嵌入技术的异构信息网络的快速谱聚类方法。从相容的角度将异构信息网络转化为若干个相容的二部图,使用随机映射和一种线性时间求解程序快速计算出每个二部图的近似commute time嵌入,每个嵌入都存在一个子集指示目标数据集,也就是目标数据集同时被多个指示子集所指示。使用这些指示子集构建一个通用的聚类模型,将所有指示子集的类设置标号,通过计算指示同一目标对象的指示数据与标号相同类的中心点的加权距离总和,同时划分所有的指示子集,从而快速获得通用模型的极小值。实验结果表明,该方法聚类准确率高,聚类速度快,能够有效处理异构信息网络的划分问题。最后,针对动态异构信息网络划分问题,利用异构信息网络的稀疏性,提出一种解决星型模式的动态异构信息网络的演化谱聚类方法。从相容的角度将异构信息网络转化为若干个相容的二部图。时间平滑每个二部图结点间的关系,使得时间平滑二部图能够充分表达某时刻及先前时间结点间的关系。稀疏化时间平滑二部图,由随机映射和一种线性时间的求解程序快速计算出每个时间平滑二部图的近似commute time嵌入,获得指示目标数据集的多个指示子集。计算指示同一个目标对象的所有指示数据与标号相同类的中心点的加权距离总和,由加权距离总和确定目标对象所属的类。实验表明该方法划分动态异构信息网络的准确率高于以往的动态异构信息网络聚类方法,计算速度也比较快。