基于拓扑学中的Jordan曲线定理,何清老师于2002年提出了一种通用的覆盖型分类方法--分类超曲面算法(HypelSurface Classification Method:HSC).该方法直接在原空间解决非线性分类问题,通过区域细化与区域合并获得由多个超平面组成的双侧闭曲面作为分类超曲面对空间进行划分,通过计算样本点关于分类超曲面的围绕数的奇偶性即可简单方便地判定其类别.实验表明,在二维和三维空间中,分类超曲面算法分类正确率高、速度快;而存储量和计算量都很小,从而能够处理海量数据. 虽然具备诸多优点,但作为一种新颖的分类方法,分类超曲面算法中还存在一些亟待解决的问题.本文的研究工作是从如下三个问题出发的: ●由于分类超曲面算法在高维空间实现起来比较困难,那么它如何对高维数据进行训练和分类? ●作为一种典型的覆盖型分类方法,对分类超曲面算法来说,是否存在一个具有代表性的子集可以"覆盖"整个数据集? ●为了进一步提高分类超曲面模型的可理解性,如何从中抽取出易于理解的规则并用于指导分类? 本文从分类超曲面算法的研究现状出发,相继解决了上述问题,从而使得分类超曲面算法对各类数据都具有更好的适应性、推广性以及良好的可理解性.研究内容主要包括以下四个部分: (1)作为分类超曲面算法处理高维数据的第一种解决方案,实现了一种通用的维度约简方法,并取得了和其他方法相当甚至更好的效果.这种方法通过重新排列高维数据中的所有数位来得到三维数据,在降维的过程中并没有丢失任何数位信息,因此是一种无损降维方法.而且,由于事先对高维向量的各分量运用主成份分析方法进行了重新排序,该方法在形式上属于基于等级的维度约简(Dimension Reduction Based on Rankina)方法,但在本质上是一种基于等级的维度换位(Dimension Transposition Based on Ranking)方法. (2)作为分类超曲面算法处理高维数据的第二种解决方案,基于集成学习(Ensemble Leaming)的思想,提出了高维数据划分集成方法.首先把原始高维训练集按照属性划分为若干子集,消除其中的矛盾数据,然后对每个子集启动一个HSC训练过程,得到多个分类模型;在测试阶段,对测试集作同样的划分,然后对每个测试子集调用与之相对应的分类器进行分类;最终的分类结果由多个分类器通过投票的方式决定.与传统的集成学习方法相比,高维划分集成方法最大的特点在于它是对属性集的划分而不是对样本集的划分,是纵向划分集成而非横向划分集成;它试图从高维数据的每个纵向切片来对数据进行分析,即从各个角度观察数据.实验证明,这种方法运用到分类超曲面算法对高维数据的处理问题中取得了很好的效果,在各个纵向切片中没有矛盾数据的情况下尤为适用. (3)为了从样本集中选出最具有代表性的子集,提出了极小覆盖子集(Minimal CoverSubset)的概念与计算方法,找到了影响分类效果的决定因素,这是在分类超曲面的泛化能力方面所做的基础理论性工作.分类超曲面算法中的极小覆盖子集除了具备覆盖性、极小性和存在性三个普遍性质之外,还具有两方面的特殊性质:尺度依赖性和极小一致性.极小覆盖子集提出的意义主要在于它具有以下四方面的重要特征: ·对给定样本集,极小覆盖子集能够完全、充分地反映其分类能力; ·针对分类超曲面算法,极小覆盖子集是对给定数据集的最佳采样方式; ·对给定数据集,通过其训练集与极小覆盖子集的关系,可以准确、定量地预测出由该训练集得到的分类超曲面模型对测试集的分类精度,因此极小覆盖子集是分类超曲面泛化能力的幕后操纵者; ·极小覆盖子集是PAC学习理论在分类超曲面算法中的推广,它在满足PAC学习理论提出的成功学到目标概念所需训练样本数目的边界的前提下,具体给出了训练样本集的这样一个子集. (4)作为一种几何方法,分类超曲面在很大程度上已经具备了较好的直观性与可解释性.为了进一步改善其可理解性,提出了分类超曲面算法的规则抽取与规则分类方法,使得分类知识得以显化,有利于分类知识的学习和传播.规则抽取过程是对处于不同层次不同位置的每一个单元格形成一条规则,并用于指导分类,因此规则的总数等于单元格的个数,也即极小覆盖子集中的样本数.与Ripper算法相比,分类超曲面的规则抽取与规则分类方法的优点在于其简单直接,在分类超曲面模型存储的数据结构之上实现起来非常方便,分类精度也稍高于Ripper算法;而缺点在于规则的规模(即规则条数与规则前件数)比Ripper算法要大. 文章最后对上述研究内容进行了总结,并指出了未来的研究方向.