论文部分内容阅读
随着计算机硬件及采样技术的发展，海量高维数据的获取也变得越来越容易，例如图像与视频数据、文本与网页数据等。那些高维数据不但会显著地增加计算和存储代价，也使得推理、学习和识别等任务无法完成，并对传统的机器学习与统计分析理论提出了严峻的挑战，如维数灾难和小样本问题等。如何获取高维数据的低维表示并探索其内在规律及本质结构，已成为机器学习、数据挖掘、模式识别、计算机视觉及统计分析等领域研究的热点问题。维数约简可在很大程度上避免维数灾难，使得学习任务（如分类或聚类等）更加稳定和高效。然而很多经典的维数约简技术存在着一定的局限性，比如传统谱聚类算法、低秩矩阵恢复与填充算法与非参数核学习算法的计算复杂度非常高，通常是样本数n的立方或者O (n6.5)；传统的非负矩阵分解没有充分考虑数据与特征的几何结构，以及半监督数据表示学习没有利用核矩阵固有的低秩结构信息等。因此，本论文以学习数据的有效表示为主题，通过挖掘数据本身固有的结构如几何结构、稀疏与低秩结构等信息来更有效地学习数据的表示。另外，再加以利用可获得的少量监督信息如少量标签数据或成对约束等来学习数据更有效的表示。从利用的信息由少到多，所取得的主要研究成果为：1.提出了一种局部与全局一致性的两阶段谱聚类框架，可充分挖掘利用数据分布空间的拓扑几何与低秩结构来学习数据的有效表示。该框架主要包括两个阶段：第一阶段是利用快速采样算法获得少量样本代表点（简称代表点）；第二阶段是由正交化的密度加权Nystrom低秩近似方法来得到全部数据的低维数据表示。在此框架下，首先定义了局部和全局两种距离测度方法，可准确地反映数据的几何结构；然后又提出了一种快速两阶段近邻传播采样算法，可得到少量富含信息的代表点，该采样算法是一种非均匀采样的方式；最后给出了一种快速密度加权低秩近似谱聚类算法。该算法不但在聚类质量、效率及内存需求方面都超过了传统的谱聚类与近邻传播方法，而且可处理较大规模数据的问题，学习获得的数据表示可应用于后面的章节。2.提出了一种双图正则的非负矩阵分解框架，可充分利用数据的流形与低秩结构来学习非负数据的有效表示。该框架同时考虑了数据流形和特征流形的几何结构，并分别在数据空间和特征空间创建两个近邻图来反映它们各自的几何流形结构。在此框架下，首先给出了一种双图正则非负矩阵分解模型，并推导了一种交替迭代更新规则；作为上述模型的拓展，然后又提出了一种双图正则非负矩阵三分解模型，并提供了一种交替迭代更新算法；最后分别提供了两种算法的收敛性证明。大量的实验结果表明提出的两种算法比相关算法的聚类性能更好，并能学习得到更有效的基于部分的数据表示。3.提出了一种鲁棒低秩矩阵分解框架，可充分利用数据的稀疏与低秩结构恢复被幅值较大的噪声或奇异点损坏的数据，而且还能填充丢失的数据。传统的核范数最小化算法每次迭代都需要对较大规模的矩阵进行奇异值分解，故此它们具有很高的时间复杂度。为了克服上述算法的局限性，把矩阵分解的思想引入到传统的核范数最小化模型中。再根据给定数据分布于单线性子空间或多子空间，分别给出了两种不同的鲁棒低秩矩阵分解模型。提出的两种优化问题分别为核范数与l1或l2,1范数最小化的混合问题，又提供了一种基于交替方向法的迭代求解算法。最后再推广到低秩矩阵填充问题，并给出了一种相应的交替迭代求解算法。4.提出了一种基于核矩阵元素分类的数据表示学习框架，可充分利用数据的几何与低秩结构及给定的少量成对约束信息。该框架以图Laplacian的谱嵌入作为辅助，再利用成对约束信息去提升它得到新的数据表示。为了更准确地刻画数据的几何结构，首先创建了一种对称偏好近邻图。然后基于平方损失函数，把学习数据表示的问题转化为一个半正定二次线性规划问题，可由常用的半正定规划软件包如SDPT3进行有效地求解。最后再把学习得到数据表示应用于半监督聚类及直推式分类问题。5.提出了一种基于理想核矩阵填充学习数据表示的框架，可充分利用数据的几何和低秩结构及给定的少量成对约束信息。由于一般给定的成对约束的数目比精确重构低秩核矩阵需要的采样数目少很多，因此也考虑把图Laplacian的谱嵌入作为辅助，进而把整个较大规模核矩阵的求解转化为一个较小规模的对称半正定矩阵求解问题。上述的模型还是一个核范数正则最小二乘问题。然后又提出了一种特征值迭代阈值算法去有效地求解给出的优化问题。最后还提供了该算法收敛于其最优解的严格理论证明。6.提出了一种基于复合信息的半监督学习框架，可充分利用数据的几何和低秩结构及给定的少量数据标签与成对约束信息。该框架不但能利用少量的样本标签与给定的成对约束信息，还能利用了大量的无标签数据。基于上述的框架，给出了一种核范数正则的半监督学习模型。然后又发展了一种两阶段优化策略，并提出了一种改进的不动点连续迭代算法去有效地学习低秩谱核。文中理论分析了上述算法的全局收敛性，并给出一种BB步长技术来进一步加速该算法的收敛速度。最后又给出了一种基于低秩谱核的半监督分类算法，并推导了一种有效的归纳分类方法。