论文部分内容阅读
基于相似性度量图的半监督学习算法是机器学习领域一个很重要的研究方向。其中，图的顶点集合为数据样本集合，边表示样本之间的相似性，因此基于图的方法具有直观、可解释性。且基于图的方法通常在实际场合中较其他半监督学习方法有更强的分类能力。然而基于图的方法通常涉及矩阵求逆，整体时间复杂度较高:基于完全图的算法的时间复杂度为O(n3)（n为数据样本集合大小）;稀疏矩阵的求逆有很多快速算法，但是稀疏矩阵的逆矩阵一般不为稀疏矩阵，从而基于稀疏图（k-近邻图）的算法的整体时间复杂度一般不低于O(n2)，同时存储大规模稠密矩阵也十分困难。由于基于图的方法其固有的较高的时间复杂度，使得基于图的方法很难应用到较大的数据集中去，这使得降低计算开销成了研究这类算法的重要目标。本文对基于相似性度量图的半监督学习方法进行深入的分析、研究。在前人研究的基础上，针对该类方法的两个重要性能瓶颈:k-近邻图构建(O(n2))和图优化(最坏O(n3))，提出了快速的k-近邻图构建算法FastKnn算法及其并行实现，和并行的基于类标号传播的图优化算法。具体来说: 通过对现有k-近邻图构建算法—RLB和NNDes—进行分析、改进，本文提出了时间复杂度为O(nlogn)的高效的k-近邻图构建算法FastKnn，该算法适用于任意的相似性度量方式，应用范围广泛。FastKnn算法包括两个重要的部分:“递归的空间划分”和“近邻传播”，该算法通过迭代这两步操作来不断提升所构建的近邻图的精度。从理论上分析了迭代方式的合理性。然后，为了进一步提升FastKnn算法的性能，针对空间划分和近邻传播算法，本文给出了相应的并行化实现。实验验证了FastKnn算法在多个数据集上的良好表现，同时并行的FastKnn算法能进一步大幅的提升算法的性能。 “基于高斯场和调和函数的图方法”和“局部和全局一致性约束方法”是两类主流的图优化方法，然而，这两类算法有较高的时间复杂度，使其难以应用于大规模数据集。本文对这两类图优化方法进行了深入的研究，在前人理论基础上实现了线性时间复杂度O(nm)（m为迭代次数）的基于类标号传播的并行图优化算法。同时，本文实现了数据访问顺序优化算法来提高缓存命中率，从而进一步提升了并行图优化算法的性能。实验表明，在多个数据集上只需要标注极少量样本，类标号传播算法可以取得比一些优秀的无监督算法更好的分类精度。同时，并行算法具有良好的加速性能，在采用数据访问顺序优化策略后，并行加速性能可以得到进一步提升。