支持向量机与K-均值聚类融合算法的研究

田飞，于威威（上海海事大学，上海　201306）

支持向量机与K-均值聚类融合算法的研究

田飞，于威威
（上海海事大学，上海201306）

传统的支持向量机分类算法随着样本规模增大、支持向量数量增多时，其分类过程所消耗的时间也会随之增加。为此，提出一种改进算法，将K-均值聚类算法与支持向量机融合。将标准支持向量机训练后得到的支持向量集进行特定比例的K均值聚类操作，把聚类的中心作为新的支持向量，再用二次规划方法求解得到新的分类决策函数。实验结果表明，该分类算法有效地减少计算时间，提高分类速度，尤其在训练集规模庞大、支持向量数量较多的情况下，效果会更加明显。

支持向量机；支持向量；K均值聚类；二次规划

0　引言

支持向量机（Support Vector Machine，SVM）算法是在统计学习理论［1］的基础上提出的，在处理小样本分类问题是具有其他分类算法不具备的优势。它最初于20世纪90年代由Vapnik提出，是近几年来机器学习的一项重大研究成果，SVM在很大程度上解决了过学习、高维数和局部极小点等传统困难。此外，由于其优秀的性能以及其优良的范化能力，使其在很多领域中得到长足的发展，并被广泛应用于网络入侵检测、文本识别、人脸表情图像识别等领域。人们对于支持向量机算法的研究已经相当成熟，在加速训练过程方面近年来已经取得了一定的研究成果：如Platt提出的 SMO （Sequential Minimal Optimization）方法［2］、以及Suykens等人提出的最小二乘支持向量机［3］（Least Squares Support Vector Machines，LS-SVM）和Osuna等的Chunking方法［4］以及文献［5］使用KNN预选取样本的方法等，这些方法对分类速度的提高没有任何影响。……