基于间隔聚类合并的支持向量机反问题求解算法  

Inverse problem of SVM via margin merging clustering algorithm

作　　者：朱杰[1] 李宁[2] 高相辉[2] 

机构地区：[1]中央司法警官学院信息管理系,河北保定071000 [2]河北大学数学与计算机学院,河北保定071002

出　　处：《计算机应用》2009年第9期2481-2482,2486,共3页journal of Computer Applications

摘　　要：支持向量机(SVM)反问题研究的是如何把无类标签的数据集合分成两类才能得到最大的间隔。但是,求解反问题惊人的时间复杂度使得这种算法很难应用到具有一定规模的数据集上。先聚类后枚举所有划分的方法,聚类个数的确定会很大程度影响计算结果和运行效率。根据间隔和类间最近点的关系,提出了一种基于间隔聚类合并的反问题求解算法,通过不断合并类间距小于2倍间隔的子类,减少了子类个数和枚举次数。实验比较证明此算法比单纯的利用传统聚类解决此问题的算法有更好的性能。The inverse problem of Support Vector Machine （SVM） is how to split the dataset into two clusters so that the margin between the two clusters reaches maximum. But the surprising time complexity makes it difficult to be applied to a dataset with certain scale. The result and efficiency of method, in which first clustering and then enumerating ＇all the possible cases, were greatly affected by the number of clusters. Based on the relationship between margin and the minimum distance between the points in different clusters, a new algorithm ealIed margin merging clustering algorithm was proposed to solve this problem. Combining the subelusters that the distance between them was smaller than 2 ＊ margin, the number of subclusters and the number of enumeration were reduced. The comparative experiments demonstrate that the proposed algorithm performs better than the traditional algorithm only based on clustering algorithm.

关 键 词：支持向量机 反问题 间隔 类间最短距离 聚类合并 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]