【作者】 刘振丙；

【导师】 刘建国；

【作者基本信息】 华中科技大学 ， 控制科学与工程， 2010， 博士

【摘要】 以SVM为代表的最大间隔机器学习方法,因为具有简洁的数学形式、直观的几何解释和良好的泛化能力,在模式分类、数据挖掘等领域受到越来越多的关注。本文受压缩凸壳思想的启发,提出了一种新的用最大间隔思想构造线性不可分问题分类器的方法——尺度化凸壳(Scaled Convex Hull,简记为SCH)方法。该方法可以把求解线性不可分问题转化为求解两类样本分别生成的SCH间的最近点对的问题。通过使用核技巧,该方法还可以用于解决非线性分类问题。首先,给出了SCH的定义,证明了与其相关的一些性质,这些性质从理论上保证了在采用SCH构造分类器时的推广能力。SCH的大小是由尺度因子控制的,因此,通过不断地减小尺度因子,两个SCH不断缩小直至可分。然后,就可以通过计算几何中已有的成熟的最近点对算法,求解SCH间的最近点对,把垂直平分连接最近点对线段的超平面作为线性不可分问题的分类超平面,其对应的分类器称为基于SCH的最大间隔分类器。这种构造分类器的思想和用压缩凸壳构造SVM最大间隔分类器的思想是一致的,因此,该方法也可以看成是一种变形的SVM方法。SCH方法改进了压缩凸壳方法的不足之处,这是因为SCH与原凸壳有相同数量的顶点,这就给求解最近点对提供简单的方法,并且求解最近点对的复杂度与尺度因子无关。此外,SCH的形状不随尺度因子的变化而变化,这也是称之为尺度化凸壳的原因。其次,介绍了求解最近点对的三种计算几何算法,即Gilbert算法、SK算法和MDM算法,把这三种算法应用到SCH最近点对的求解中去。并与压缩凸壳的情形下的三种算法进行了计算复杂度的对比分析,说明了SCH方法的优点。再次,SCH方法还可用于解决类不平衡问题。一般地,对于类不平衡问题,正类样本数较少,生成的凸壳相对也较小,而负类点生成的凸壳较大,在这种情况下,得到的分类面会倾向于误分正类样本。而利用本文提出的SCH方法,通过不同程度的缩小两个凸壳,则可以解决这个问题。即对于负类点的凸壳,赋予小的尺度因子,而正类点的凸壳,则赋予大的尺度因子,这样得到的正类SCH和负类SCH大小基本一致,然后把垂直平分两个SCH的超平面作为分类面。用类似的方法,通过赋予不同的SCH以不同的尺度因子,本文提出的方法还可以解决代价敏感问题。最后,通过建立SCH和最小闭球问题之间的关系,本文把求解SCH分类器的问题转化为求解最小闭球问题。然后,利用现有的求解最小闭球的快速算法,可以求解大规模的SCH分类问题。更多还原

【Abstract】 Maximal-margin classification approaches, noted as support vector machines, have attracted more and more attentions in the fileds of pattern recognition and data mining, due to the clear mathematical formulation, intuitive geometric description and good generalization performance. In this thesis, inspired by the notion of Reduced convex hull (RCH), a notion of scaled convex hull (SCH) is introduced to construct the maximal-margin classifiers for nonseparable classificaiton problems, through which the nonseparable problems can be transformed to the problems of finding the nearest point pair between two SCHs generated by the two class training points respectively.First, the notion of "scaled convex hulls" (SCH) is employed and a set of theoretical results are exploited to support it, and those results guartee theoretically the generalization performance of the SCH based classifiers. By a suitable selection of the scale factor (reduction factor), the initially overlapping SCHs can be reduced to become separable. Once they are separable, we can find the nearest point pair between them using the existing algorithms, and the separating hyperplane a) bisects, and b) is normal to the line segment joining these two nearest points. This separating hyperplane obtains the maximal margin between SCHs, resulting in a maximal-margin classifier. This viewpoint is the same as the reduced convex hull (RCH) framework for SVM classifiers, so it can be seen as a variant of SVMs. Being different to the RCH, the SCH has the number of extreme points as the original convex hull. It simplifies the computation of nearest point pair between the SCHs, which is independent to the reduction factor. Besides, the SCH has the same shape as the original concex hull when the sacle factor changes, so we call it scaled convex hull.Second, three algorithms are introduced to compute the nearest point pair between SCHs, i.e.,the Gilbert algorithm,the SK algorithm and the MDM algorithm. The comparison with the RCH methods shows the advantages of the proposed method.Third, the SCH can be used to solve imbalance problems. In this situation, the number of the positive points is much less than that of the negative points, so the convex hull generated by the positive points is smaller than that generated by the negative points, and the resulting classifier will tend to misclassify more positive points. By providing different SCH with a different scale factor, the imbalance can be addressed, i.e., providing the positive SCH with bigger scale factor and the two SCH will have the same area, and the resulting classifier will misclassify less positive points.In the same way, by providing different SCH with a different scale factor, the proposed SCH method can solve the cost-sensitive problems.In the last, by building the relationship between the SCH and the minimum enclosing ball (MEB) problems, the solution of SCH based classifiers can be transformed to the solution of MEB. By the existing methods to solve MEB problems,the large-scale classification problems can be resolved.更多还原