半监督支持向量机的截断凝聚同伦算法及复杂性分析

Semi-supervised support vector machine is a hot topic in data mining. The problem can be modeled as a piecewise convex quadratic optimization problems. Though the model is simple, there is few mature software because of huge data in the model and the nonsmoothness and nonconvexity. In this project, some more efficient implementations will be given based on existing aggregate homotopy method. Firstly, a twice truncated aggregate technique will be introduced to make data reduction at each iteration. In conjunction existing aggregate homotopy method with the technique, one more efficient path-following algorithm will be given. Secondly, more detailed discussions will be given to the implementation of the new algorithm. By analyzing the special structure of coefficient matrix of linear equations at each inner iteration, it can be found that generalized Shermann-Morrison-Woodbury formula for inverting matrix can be used to reduce compuational cost. And then software design of the algorithm can be established based on the discussions. Moreover, the established software will be used to make gene functional analysis in bioinformation to verify the efficiency of the algorithm. Finally, complexity analysis of aggregate homotoy method solving the model is tried to be given such that efficiency of the algorithm can be proven theoretically.

半监督支持向量机是目前数据挖掘领域里的一个研究热点，该问题建模或适当变形后实质上是一类分片凸二次的非光滑优化问题。尽管模型形式并不复杂，但由于问题中的海量数据以及模型本质的非光滑非凸性，使得目前仍然缺少成熟的算法软件。本项目拟在已有的凝聚同伦路径跟踪算法的基础上，考虑模型的更有效的求解。首先，基于已有的凝聚同伦方法，给出二次截断凝聚技巧以减少每步迭代调用的数据量，建立效率更高的路径跟踪算法。其次，结合截断凝聚技巧，研究内迭代线性方程组系数矩阵的特殊结构，利用矩阵求逆的广义Shermann-Morrison-Woodbury公式进一步简化计算，从而给出算法的高效数值实现并完成软件设计。进一步的，我们拟将算法软件用于生物信息学中的基因功能分析检验算法效率。最后，尝试给出凝聚同伦算法解这类特殊问题的复杂性分析，从理论上证明算法的效率。

本项目考虑半监督支持向量机模型的高效数值解法及相应的计算复杂性。项目组成员认真履行申请书的承诺，取得了一定研究成果，主要研究成果包括以下几个方面：一是给出二次截断凝聚技巧，建立新的预估校正路径跟踪算法及相关收敛性分析；二是对算法进行了软件设计，并用标准测试数据和齿轮箱故障诊断问题检验效率。在标准测试数据上计算，新方法平均每步迭代所用到的数据量不到给定总数据的1/3。在齿轮箱故障诊断数据上测试，得到了比支持向量机方法更为理想的结果。最后，对算法的计算复杂性加以研究，得到新算法的计算复杂度的一个上界。