论文部分内容阅读
支持向量机(SVM)是一种有效的数据挖掘算法，被广泛用于分类和预测问题。但是训练样本规模较大时，支持向量机求解凸二次规划问题的计算复杂度比较高，甚至难以求解。最小二乘支持向量机(LSSVM)将凸二次规划问题转化为线性方程组求解问题，大大提高了计算效率。但是它的解缺乏稀疏性，难以有效解决大规模训练问题。尤其在数据量较大时，大规模训练数据形成的核矩阵在训练过程中往往难以存储，甚至无法参与计算。由于提高稀疏性成为最小二乘支持向量机的迫切需求，因此稀疏最小二乘支持向量机应运而生。而稀疏最小二乘支持向量机算法的关键是寻找尽可能最优的小规模低秩近似核矩阵代替核矩阵进行求解，从而提高解的稀疏性并降低计算复杂度。本文从两个方面讨论稀疏求解算法。 一方面，传统稀疏最小二乘支持向量机算法一般通过随机选择部分样本来得到核矩阵的小规模低秩近似矩阵。为了使小规模低秩近似矩阵来尽可能很好地近似原来的核矩阵，利用QR分解的数值稳定性保证所选样本之间保持较大的差异。本文利用QR分解的这一优势，迭代地选择核矩阵的部分列，来得到核矩阵的Nystrom近似，并据此得到P-LSSVM的稀疏解，从而提出基于QR分解的QRP-LSSVM稀疏算法。本文通过理论分析和实验表明，QRP-LSSVM算法可以得到更加稀疏的解，甚至在稀疏水平不超过0.05％的情况下也能达到较高的准确率。本文提出的QRP-LSSVM算法稳定性好，可以有效解决大规模训练问题。 另一方面，本文将基于QR分解选择差异性较大样本的优势运用到约减支持向量机(RSVM)中。我们采用基于QR分解选择样本子集的方法尽可能地筛选有代表性的样本来得到约减支持向量集，来弥补了RSVM随机选择约减集所导致的一系列不足。本文在基于QR分解选取约减集的基础上，分别讨论了采用不同损失函数的情况下，约减支持向量机的求解算法。并且分别得到基于Square Hinge损失函数、最小二乘损失函数和Huber损失函数的QRP+SHRSVM、QRP+LSRSVM和QRP+HRSVM算法。本文通过理论分析和实验表明，基于Square Hinge损失函数的QRP+SHRSVM算法过程中牛顿迭代简单，且可以得到比较高的测试准确率。另外，通过与随机选择约减集的RR+SHRSVM算法对比，突出了QRP+SHRSVM算法筛选出有代表性的样本来得到支持向量集的优点，提高了算法稀疏性和结果的稳定性。