基于模糊核聚类的svm多类分类方法.docx

基于模糊核聚类的svm多类分类方法 0 svm多类分类方法 支持向量机（svm）作为一种机器学习方法，可以更好地解决非线性、高维数和局部小距离问题，并具有其他机器学习方法的优势。但是,SVM是针对两类分类问题提出的,而实际中多类分类问题更为普遍,如何将SVM的优良性能推广到多类分类一直是SVM研究的一个重要问题,尤其对于大类别分类问题,目前还缺乏有效的SVM多类分类方法。 大类别分类问题类别数目多,训练样本规模大,在已提出的SVM多类分类方法中:一次性求解方法因计算复杂度过高、精度较低而不实用;one-against-one (1-a-1)方法、directed acyclic graph (DAG)方法因需要训练的SVM数目太多而训练速度较低;one-against-rest (1-a-r)方法因每个SVM都是在全部训练样本上学习的,而同样具有较低的训练速度;基于二叉分类树的decision-tree-based multiclass support vector machines(DT-SVM)方法和hierarchical support vector machines(H-SVM)方法因模糊类之间交叠严重以及分类树的错分积累而精度较低。 本文首先分析了已提出的各种SVM多类分类方法存在的问题,然后提出了一种基于模糊核聚类的SVM多类分类方法(support vector machines multi-class classification based on fuzzy kernel clustering, FKC-SVM multi-class classification),并给出了一种快速半模糊核聚类算法。新方法利用模糊核聚类生成模糊类,并采用树结构将多个两类分类器组合起来实现多类分类。模糊核聚类不但能够较好地分辨、提取并放大有用的特征,实现更为准确的聚类,而且能够挖掘有关模糊类的外围、不同模糊类之间的衔接和离散信息。利用这些信息能够使分类器在具有树型结构识别效率高的特点的同时,减少训练样本的规模、发现模糊类中的野值点,从而提高分类器的训练速度和精度。实验表明了新方法的有效性。 1 模糊类生成方法对识别精度的影响 SVM最初是针对两类分类问题提出的,用于多类分类问题必须将其推广。目前,已提出的SVM多类分类方法大致可分为两类:一次性求解法和分解重构法。一次性求解法是在所有训练样本上求解一个大型二次规划问题,同时将所有类别分开,该方法变量个数多,计算复杂度很高,尤其当类别数目较多时,它的训练速度很低,分类精度也不高。分解重构法是一种将多类分类问题转化为多个两类分类问题,并采用某种策略将多个两类分类器组合起来实现多类分类的方法。实验表明,分解重构法比一次性求解法更适合于实际应用。用分解重构法实现多类分类需要解决两个关键问题:模糊类的生成方法和多个两类分类器的组合策略。目前,已提出的SVM分解重构法主要包括: 1-a-r、1-a-1、DAG、DT-SVM和H-SVM等,表1对上述方法进行了对比。 模糊类生成方法决定了两类分类器的个数、各两类分类器的训练样本数目和模糊类间的交叠程度,进而对多类分类器的训练速度、分类速度和精度有较大影响。在上述方法中,1-a-r的模糊类方法是依次将所有类别中的一个类别与其余类别分开的“一对其余”方法, 1-a-1和DAG的模糊类就是原始类别。直接用原始类别作为模糊类时,模糊类的可分性相对较好,分类器的分类精度较高,但所付出的代价是需要训练的SVM数目较多,训练速度较慢。1-a-r需要训练的SVM数目相对较少,但是各SVM都是在全部训练集样本上进行学习的,因而,当样本数较多时,训练速度依然很慢,而且模糊类之间的交叠严重。文献给出的DT-SVM的模糊类生成方法实际上是一种在分类树的各个决策节点的“一对其余”方法,该方法生成的模糊类依然存在交叠严重、野值点数目多的问题。文献给出的H-SVM的模糊类生成方法则是在输入空间对分类树的各个决策节点所包含的训练样本进行聚类,然后根据聚类结果生成模糊类。多类分类问题类别数目多,训练集样本分布复杂,而输入空间聚类的有效性在很大程度上取决于样本的分布情况,因而,H-SVM的模糊类生成方法的效果通常也不好。 另外,分解重构方法的组合策略影响了多类分类器的识别效率。在已提出的分解重构法中,1-a-r采用最大输出法将多个分类器的输出组合起来实现多类分类,1-a-1采用投票法决定未知样本的类别,这两种方法分类时都需要遍历所有的SVM分类器,因而识别效率低。DAG与1-a-1的模糊类方法相同,但分类时DAG采用树结构将多个分类器组合起来实现多类分类,从而具有比1-a-1快得多的分类速度。DT-SVM和 H-SVM也是采用树结构的组合策略,具有较高的训练和分类速度,但是