面向高维数据的聚类算法设计和张量低秩表示研究

摘要

聚类算法在探索数据可视化和发掘数据底层结构等领域得到了广泛的应用和发展。工业生产活动中产生了大量无标签的数据，对这些数据进行聚类具有重要意义。当前聚类算法在检测识别形状不规则的簇时，通常会面临着算法参数增加或聚类精度下降的问题。基于密度峰值的聚类算法利用决策图寻找密度峰值，从而可以发现数据底层结构。该类算法在高效识别不规则簇的同时，能够实现算法参数和聚类精度好的折衷。然而，当数据集中簇存在内部不均匀分布现象时，基于密度峰值的聚类算法可能无法确定正确的中心点，导致簇划分错误。在实际互联网数据中，数据通常还具有特征维度高、样本稀疏的特性，导致真实簇结构通常存在于样本对应的低秩子空间中。另外，先验概率分布的多样化，张量数据的增量式更新，会导致张量低秩表达的分析过程变得复杂。针对上述问题，本文通过分析基于密度峰值的聚类算法，研究高效准确获取数据真实簇分布的聚类算法，并将其用于高维数据聚类；在分析张量分解理论的基础上，提出了可适应不同数据分布和可在线学习的张量分解方法，并扩展到GPU和多GPU上。论文的主要研究工作如下：　　针对数据集中簇内分布不均匀的问题，本研究提出了一种基于层次化策略的密度峰值算法(HCFS)。本研究主要包括形成子簇和合并子簇两个方面：第一，在形成子簇的过程中，选择多个密度和距离都较大数据点作为备选中点。这一方面能规避掉选择“符合条件”的中心点带来的困难，另一方面避免了因选择错误的中心点而出现的误分类。第二，在合并子簇的过程中，提出一种能同时度量相邻子簇间联通性与相似性的方法，降低了参数设置的难度。在多个常用UCI数据集上进行了相关的对比实验，结果证明本文算法较好地解决了数据集中簇内不均匀分布的问题。　　针对高维数据集中簇内分布不均匀的问题，本文提出了一种改进的基于多视图和张量低秩表达的子空间聚类算法。首先，本文采用求解误差矩阵‘2,1范数最小化的方法解决了高维数据集多视图特征数据中噪声、数据损坏的问题；其次，本文把多视图的相关数据堆叠成张量，并把求解多视图子空间表达的优化问题转化成为求解张量的低秩表达问题，以充分考虑视图间的互补性。本文基于以上两个方面从高维数据集中得到了更加准确的子空间表达，进一步整合并确定了最终的相似度矩阵。最后，本文通过结合合理的相似度矩阵与HCFS算法，解决了高维数据集中簇内不均匀分布的问题。在多个多视图人脸数据集上，进行了与其它几种典型的子空间聚类算法之间的对比实验，结果表明了本文算法的有效性。　　数据分布多样性普遍存在，需要独立推导基于不同数据分布的因子矩阵更新规则，这给稀疏非负张量分解分析带来了困扰。针对这种情况，本文提出了一种通用的因子矩阵更新规则。首先，本文基于单通道的模型设计了逐元素更新的策略，遵从稀疏张量的稀疏性，从而避免产生大规模的中间矩阵；其次，本文通过设置自适应的训练步长，保证了因子矩阵损失函数的单调性和因子矩阵元素的非负性；最后，本文分析和推导了不同数据分布下因子矩阵的更新规则，并提出了一种通用的因子矩阵的更新规则，以适应多种不同的数据分布。此外，本文算法通过把整个因子矩阵元素的求解问题分解为多个独立行元素的求解问题，一定程度上实现了并行化设计。在多个真实的稀疏张量数据集上，进行了与其它稀疏非负张量分解模型之间的对比实验，结果表明了本文算法高效的收敛性、准确性，以及对不同数据分布的适用性。　　随着数据量的不断增加，单个GPU不能加载和处理整个数据集。另外，随着互联网的迅速发展，数据更新的速度也随之加快；忽略实时数据将可能会导致信息的大量损失，重新处理整个数据集又将会造成大量的资源浪费。针对第一个问题，本文通过研究多个GPU之间的通讯原理，提出了一种基于多GPU的因子矩阵更新规则。同时，本文结合逐元素更新的策略，解决了现有并行化和优化求解算法中临时矩阵带来的大量计算和存储开销问题。针对第二个问题，本文结合在线学习的策略，提出了针对实时数据的因子矩阵更新规则。此外，本文还改进了CSF(Compressed Sparse Fiber)树的存储结构，提出了一种合并旧数据与新数据的方法。在多个高阶数据集上，进行了1、4、8个GPU上稀疏非负张量分解的实验，结果表明了本文基于多GPU算法的有效性和可扩展性；在动态更新数据集上的实验，证明了不损失实时数据信息的情况下，本文在线学习的算法能达到降低计算资源和存储空间消耗的目的。

目录

声明

第1章 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.2.1 参数削减聚类算法

1.2.2 基于子空间的多视图聚类算法

1.2.3 非负张量分解算法

1.2.4 非负张量分解并行化及优化方法

1.3 本文研究内容

1.4 本文章节组织和安排

第2章 基于层次化策略的密度峰值聚类算法

2.1 参数削减的聚类算法

2.1.1 基于密度划分策略的聚类算法

2.1.2 基于密度峰值的算法

2.2 基于层次化策略的密度峰值算法

2.2.1 问题描述

2.2.2 建立子簇

2.2.3 合并子簇

2.2.4 算法过程

2.3 实验结果及分析

2.3.1 实验设置

2.3.2 实验结果

2.3.3 参数分析

2.4 本章小结

第3章 基于多视图和张量低秩表达的MVTLR-HCFS算法

3.1 子空间与多视图聚类相关技术原理及应用现状

3.1.1 相关概念及技术原理

3.1.2 应用现状

3.2 基于多视图和张量低秩表达的MVTLR-HCFS算法

3.2.1 相关定义

3.2.2 张量低秩优化问题

3.2.3 优化问题求解

3.2.4 高维数据的簇内不均匀分布现象

3.2.5 算法过程

3.3 实验结果

3.3.1 实验设置

3.3.2 实验结果

3.3.3 收敛性分析

3.4 本章小结

第4章 基于单通道模型的通用因子矩阵更新算法

4.1 相关符号和定义

4.1.1 相关符号和名称

4.1.2 相关定义

4.1.3 NTF与NMF的差异

4.1.4 NTF相关问题

4.1.5 SNTF相关问题

4.1.6 GPU计算模型

4.2 通用的因子矩阵更新算法

4.2.1 通用的单通道模型GS S NT F

4.2.2 算法的并行化设计

4.2.3 算法复杂度分析

4.3 实验结果及分析

4.3.1 实验设置

4.3.2 关于秩R的扩展性实验结果

4.3.3 算法的收敛性实验结果

4.4 本章小结

第5章 GSSNTF在多GPU与在线学习模型上的扩展算法

5.1 相关研究

5.1.1 相关定义

5.1.2 相关应用情况

5.2 基于多GPU的MCUGSSNTF算法

5.2.1 多GPU通信原理

5.2.2 MCUGSSNTF算法

5.3 在线的GSSNTF算法

5.3.1 在线学习的算法

5.3.2 更新临时因子矩阵A(N),t2

5.3.4 新旧数据在线归并结构OnCSF

5.4 实验结果

5.4.1 实验设置及数据

5.4.2 并行化算法实验结果对比

5.4.3 OnGSSNTF算法实验结果

5.5 本章小结

参考文献

致谢

附录A 攻读学位期间所发表的学术论文