The Study Of Maximal-margin Classification Approaches Based On Scaled Convex Hulls

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.