以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分类问题。