组合凸线性感知器的极大切割构造方法

摘要

组合凸线性感知器(Multiconlitron)是用来构造分片线性分类器的一个通用理论框架,对于凸可分和叠可分情况,分别使用支持凸线性感知器算法(Support conlitron algorithm, SCA)和支持组合凸线性感知器算法(Support multiconlitron algorithm, SMA)将两类样本分开。本文在此基础上,提出了一种基于极大切割(Maximal cutting)的组合凸线性感知器构造方法。该方法由两阶段训练构成,第一阶段称为极大切割过程(Maximal cutting process, MCP),通过迭代不断寻求能够切开最多样本的线性边界,并因此来构造尽可能小的决策函数集,最大程度减少决策函数集中线性函数的数量,最终简化分类模型。第二阶段称为边界调整过程(Boundary adjusting process, BAP),对MCP 得到的初始分类边界进行一个二次训练,调整边界到适当位置,以提高感知器的泛化能力。数值实验说明,此方法能够产生更为合理的分类模型,提高了感知器的性能。同其他典型分片线性分类器的性能对比,也说明了这种方法的有效性和竞争力。%Multiconlitron is a general framework for constructing piecewise linear classifiers. For convexly separable and commonly separable data sets, it can separate them correctly by using support conlitron algorithm (SCA) and support multiconlitron algorithm (SMA), respectively. On this basis, the paper proposes a maximal cutting construction method for multiconlitron design. The method consists of two training processes. In the first step, the maximal cutting process (MCP) is utilized iteratively to find a linear boundary such that it can obtain the maximum number of samples. Thus, the MCP can reduce the number of linear boundaries and construct a minimal set of decision functions, and ultimately simplify the classification model. To improve the generalization ability further, in the second step we employ a boundary adjusting process (BAP) to make the classification boundaries more fittable. Experiments on both synthetic and real data sets show that the presented method can produce more reasonable multiconlitron with better performance. Comparison with some other piecewise linear classifiers verifies its effectiveness and competitiveness.