基于最小二乘法的无监督支持向量机

孔 波， 王红蔚

(河南教育学院 数学与统计学院，河南 郑州 450046)

基于最小二乘法的无监督支持向量机

孔 波， 王红蔚

(河南教育学院 数学与统计学院，河南 郑州 450046)

将最小二乘支持向量机的思想引入无监督学习，提出一个最小二乘无监督支持向量机.首先假设超平面过样本中心点，再给出线性可分的条件构造目标函数和约束条件，从而得到一个线性规划问题去求解聚类问题.

无监督学习；最小二乘支持向量机；线性规划；聚类

0 引言

支持向量机[1](support vector machine, SVM)是一种非常有效的处理分类问题的机器学习方法. 最小二乘支持向量机(least square SVM,LS-SVM)[2-3]是SVM的一种变形，大大简化了问题的计算复杂性. 这两种方法都是对有类别标签样本进行分类，这是有监督学习，而直接对无类别标签的分类称为无监督学习(unsupervised learning).文献[4]最早将SVM用于聚类，将训练样本通过高斯核映射到高维特征空间，并在其中寻找最小封闭球体进行聚类，称为支持向量聚类(support vector clustering).目前的支持向量聚类大多是此类算法，无法求出最优分划超平面.还有一类是先对无类别样本进行类别标示，再根据所有样本求解决策函数的方法[5]，但标注过程本身就非常复杂，而且准确率难以保证. 文献[6]提出了一种新的思路:直接对无类别标签样本进行分类，使得聚类分类一次完成，并得到了一个无监督支持向量机. 目前还没有使用最小二乘法构造无监督支持向量机进行聚类的算法.

本文首先利用最小二乘法中回归曲线过样本中心点的原则进行聚类假设，再给出线性可分的条件，将LS-SVM的思想运用到无监督学习中进行聚类，从而构造一个线性规划问题去求解聚类分类超平面.最后利用核函数将线性问题推广至非线性问题，得到一般情形下的最小二乘无监督支持向量机.

1 最小二乘支持向量分类机(LS-SVM)

给定训练样本{(xi,yi),xi∈Rn,yi∈{-1,+1},i=1,2,…,l}，为求解分类函数，需构造如下优化问题，

(1)

则由Lagrange 数乘法可得与原始问题(1)式对偶的线性方程组

(2)

2 最小二乘无监督支持向量分类机

这样只需求解如下优化问题

(3)

令

(4)

则有

(5)

可得如下线性规划问题，

最小二乘无监督支持向量机的算法如下.

3 实验分析

图1 实验1的聚类效果图Fig.1 Clustering Result of Experiment 1

图2 实验2的聚类效果图Fig.2 Clustering Result of Experiment 2

4 结论

为了有效利用LS-SVM对无类别标签样本进行聚类，通过构造新的目标函数和约束条件，提出了一个最小二乘无监督支持向量机.该算法同传统的最小二乘支持向量机一样将优化问题最终化为线性规划问题来求解，具有解的优良性，并能借助于核函数处理非线性问题，从而解决了训练样本的非线性问题和“维数灾难”问题.实验结果印证了该算法的有效性.下一步将此算法结合多类分类支持向量机[9]推广至多类的聚类算法.

[1] VAPNIK V. The nature of statistical learning theory [M]. New York: Springer-Verlag，1995.

[2] SUYKENS J A K, VANDEWALLE J.Least squares support vector machines classifiers [J]. Neural Process Letter, 1999,9(3)：293-300.

[3] 刘小茂，孔波，高俊斌，等. 一种稀疏最小二乘支持向量分类机[J].模式识别与人工智能，2007，20(5)：681-687.

[4] BEN-HUR A, HORN D, SIEGELMANN H T. Support vector clustering [J]. Journal of Machine Learning Research，2001, 2: 125-137.

[5] FUNG G, MANGASARIAN O L. Semi-supervised support vector machines for unlabeled data classification [J]. Optimization Methods and Software,2001, 15(1): 29-44.

[6] WU TAO, ZHAO HANQING. Classifying unlabeled data with SVMs [J]. Advances in Intelligent and Soft Computing,2006, 34: 695-702.

[7] 王红蔚，席红旗，孔波. 一种新的半监督支持向量机[J]. 郑州大学学报：理学版， 2012，44(3)：66-68.

[8] BLAKE C L, MERZ C J. UCI repository of machine learning databases [DB/OL]. [2014-01-11] .http://www.ics.uci.edu/～mlearn/databases.

[9] 孔波，郑喜英. 支持向量机多类分类方法研究[J].河南教育学院学报：自然科学版，2010，19(2)：9-12.

Unsupervised Support Vector Machine Based on the Least Square Method

KONG Bo， WANG Hong-wei

(SchoolofMathematicsandStatistics,HenanInstituteofEducation,Zhengzhou450046,China)

Least square unsupervised support vector machines are presented by introducing the ideas of the least squares support vector machine(SVM). It assumes that hyperplane over the center of the sample points and gives the conditions of linearly separable, so a linear program model to solve clustering problem by constructing a new objective function and constraints, so that SVMs can be used to cluster the unlabeled data.

unsupervised learning; least squares support vector machines； linear programming; clustering

2014-06-21

河南省基础与前沿项目(122300410229)；河南省教育厅科学技术重点研究项目(12B110005)

孔 波(1980—)，男，河南周口人，河南教育学院数学与统计学院讲师．

10.3969/j.issn.1007-0834.2014.04.004

O235

A

1007-0834(2014)04-0017-03