基于聚类的svm反问题求解.doc

基于聚类求解SVM反问题 摘 要 SVM反问题针对一个没有类别信息的数据集，通过指定类别标签和利用SVM理论来寻找最大间隔（Margin），将数据集划分为间隔最大的两部分。针对小规模的数据集可利用遗传算法来求解SVM反问题，但SVM反问题的计算时间随着问题规模的增加呈指数级增长，导致在较大规模的数据集上无法求解。为了减少计算时间，本文提出了基于聚类求解SVM反问题的方法，通过聚类减少类别指定的次数和正问题的求解次数，从而使SVM反问题在较大规模的数据集上的求解成为可能。 实验结果表明基于聚类求解SVM反问题的方法是可行的和有效的。 关键词 SVM反问题；聚类；最大Margin The Inverse Problem of SVM Based on Clustering Abstract The inverse problem of SVM is to assign a class label {+ or -} to every point of a dataset (therefore two clusters are formed) such that the margin between the two clusters attains maximum. It can be solved by using the genetic algorithm if the scale of the dataset is small. When the scale of the dataset grows, the computational time of the inverse SVM increases exponentially, which may cause impossibility when solve the problem even on a moderate-scale dataset. This paper proposed a technique to solve the inverse SVM based on clustering in order to decrease the computational complexity. This technique reduces the possible assignments of labels and the number of training SVMs by clustering, and makes possibility to solve the inverse SVM on larger datasets. The results of experiment indicate that the method to solve the inverse SVM based on clustering is feasible and effective. Key words The Inverse Problem of SVM; Clustering; Maximum Margin 1 引 言 SVM分类问题是Vapnik等人在1995年提出的[1]，它以统计学习理论为基础，经过不断的发展，在解决一系列实际问题中得到了广泛应用[2]，表现出了良好的学习能力、泛化能力，从而引起人们对这一领域的极大关注。 SVM的基本问题是在拥有正负类别信息的训练样本集上，通过寻找不同类别样本之间的最大Margin训练出分类器[3]，从而使不同类别的样本被分类器分开。SVM反问题是针对正问题提出的一种无监督分类问题，它在不含有任何类别信息的样本集上寻找样本之间的最大Margin。对于这个不含类别信息的样本集，反问题任意地将它指定为两类，假设一个为正类，另一个为负类，我们利用SVM理论求出最优超平面，并记录相应的间隔（Margin）。若划分为两类的样本点线性不可分，则Margin记为零。显然，对数据集的不同划分，会得到不同的间隔。最后得到各种划分所对应的Margin序列，对这个序列求最大值，这个最大的Margin就是反问题要求的样本之间的最大间隔。问题的关键就在于，如何对数据集进行划分才能使得利用SVM理论求出的间隔达到最大。 从上面的反问题求解过程可以看出，类别指定完成后，样本点类别就确定了，相应的划分也就确定了，对每一种划分，需要求解一次SVM基本问题以得到相应的Margin。给定一个具有n个样本点的训练样本集，如果采用枚举的方法，则有种类别指定，除去对称的划分和全标记为+1和-1的情况，则有种划分，这意味着需要求解次SVM基本问题。如果样本集规模很小，可以利用遗传算法解决SVM反问题[4]。遗传算法虽然不用枚举方法进行类别指定，但实验表明它的运算时间也是随着