基于图的半监督维数约减方法的研究

摘要

维数约减已经成为当前机器学习领域的受人关注的研究热点。维数约减是将数据由高维约减到低维的过程而用来揭示数据的本质低维结构。它作为克服“维数灾难”的途径在这些相关领域中扮演着重要的角色。在众多维数约减方法中，由于基于图的维数约减方法简单、容易理解和高性能等特点使其得到了广泛的学习和研究。基于图的方法把每个样本数据作为在图中的一个节点，强调样本数据结构的嵌入即高维空间中的结构在低维空间中得到保持。如何在高维样本上构造图是基于图的维数约减算法的关键。一个好的图再结合适当的降维算法就会有着良好的性能表现。其中，与传统降维算法不同，半监督降维在有限的有价值标记信息或者成对约束下经常可以得到好的低维嵌入比那些无监督降维方法。在过去的几十年里，有着大量的降维算法被提出如：传统的无监督降维方法主成分分析、有监督降维方法线性判别分析（LDA）、流行学习算法、基于图的降维算法等等。但大多数方法都多少存在着一些问题，如小样本问题、分类问题、样本的非线性分布问题等等。在本文中针对在高维数据上构造的近邻图难以较好的刻画样本间的相似性，在其上的优化过程并不有助于后续的降维学习，同时也为了进一步提高维数约减算法的效率和降维后的分类精度，我们对半监督维数约减的方法进行了系统的研究。
　　本研究主要内容包括：⑴提出了一种基于组合图的半监督维数约减算法----SSDRCG。SSDRCG利用随机子空间的思想，把每一个子空间通过聚类的方式构造子图。然后把各个子图融合在一起构成组合图。最后把我们构造的新图与基于成对约束的半监督维数约减算法相结合形成新的降维算法。为了验证该算法的性能，我们将SSDRCG分别与多种维数约减方法进行对比，通过在不同的人脸数据集上的实验证明，该算法降维后的分类精度高于其它方法，时间复杂度也低于增强型保举投影算法。⑵提出一种改进的基于混合图的半监督维数约减算法----SSDRHG。SSDRHG在混合图的构造策略上进一步改进，打造新的图，然后应用到基于成对约束的半监督维数约减中，既利用了同类约束和异类约束，同时也利用了未标记数据进行维数约减。同样的通过在2种不同的人脸数据集上进行实验，得到的结果与多种方法在相同参数下取得的结果进行对比，结果表明这种方法更加优越，不仅降维后的分类精确度高于其它相关方法，而且对近邻参数的选取和噪声数据更加的鲁棒。同时这样方法的思想也可以应用到其它基于图的学习中。