第6期 何清，等：基于超曲面的分类算法研究进展 。3 进行判别（设T为样本点分类所得类别）：选择适当 点，但与连通分支的形状无关，在现实中的数据分 的由待定点X出发的射线fx,设fx与SHS的相 布大都满足条件之一25] 交点数为C,分别计算fx与/SHSl a=1,,n}和 H$C算法发展至今，已相继解决了二维2类分 {SHSb=1,,n}(n+n=)的相交点数之和， 类23引、二维多类分类24)、二维一般连通区域分 1 类2)、三维多类21、高维换维分类问题2)、高维多 记为c.和c,则有 6- 类集成分类问题28.451」 C为奇数r=1 关于HSC算法的最新进展包括：利用HSC算 法构造了极小样本集，提出了基于覆盖的极小样本 集的概念使之不仅可以代表整个模型，而且可以反 或 C为奇数7=2 映出整个训练集的拓扑结构6，并研究了BAG 实际上，求C的过程，就是求∫x与HP相交数量 GNG和ADABOOST算法使用不同的训练样本集 的过程 时对HSC分类器性能的影响，试验结果表明，他们 6)若不能判别X的类别，就对X所在的小区域 对分类精度的提高是受极小样本集制约的).另外 边界进行标定，不妨设x'(m+1)∈Dm+1,则Dm+1的 从视觉认知角度研究了超曲面在和数据理解中的作 边界可表示为 用41.采用Aget(智能主体)技术用于多个HSC Hm+1=f1m+1,Hg1|p=1,2,…km+1 分类器的合成，使得HSC算法适合在分布式环境 之后转入4)，继续合并相邻同类区域： 中进行数据挖掘.这种合成的特点是不把样本集划 以上给出了基于分类超曲面的分类判别方法的 分为若干小样本集的横向划分，而是对分布在不同 基本算法，即通过区域合并计算获得多个超平面组 地点的不同属性的样本集就地作属性集纵向划分后 成的双侧闭曲面作为分类超曲面对空间进行划分， 的合成4 也就是在样本点周围形成一个封闭区域，该区域由 3基于超曲面的覆盖分类学习算法的 多个分类超平面片围成，并使得该区域覆盖某一类 研究方向 尽可能多的样本点，同时不覆盖异类样本点】 基于超曲面的分类学习算法HSC作为一种新 2算法特点与已有研究成果 的算法，有很多问题亟待研究，这既包括算法优化 H$C算法有2个关键步骤，一是局部化策略， 又包括理论分析，还包括应用中遇到的现实问题 另一个是用围绕数判断类别.该算法中，判别样本所 首先是优化高维数据分类算法问题.从理论上 属类别，不需与所有分类边界链表作相交操作后再 讲，这种方法可以推广到高维，因为Jordan定理在 判断，而只需满足：由样本点所引射线与一完整分类 任意有限维空间都是成立的.但是高维空间中的实 边界链表相交点数为奇数即可，这样可提高判别速 现存在以下挑战性问题：一是高维空间的单位方体 度.这种方法得到的分类超曲面是由若干个封闭闭 的合并计算复杂度随着维数增加而提高，另一方面 曲面构成，而曲面的局部是由低维平面片构成.每个 高维超曲面的存储开销大.但是这并不意味HSC 闭曲面内部是一类样本，这样对闭曲面可以进行类 不能处理高维数据，借助数据预处理和集成学习技 别标记.样本类别可以是多个，所以这种方法对于多 术，对于高维数据处理提出并实现了2种解决办法. 类问题的解决是很方便的，因为多个分类器可以在 这2种高维处理方法与HSC算法特点紧密结合，这 一次训练过程中产生，避免了2类分类器转化为多 就是基于样本数据重排的换维分类学习算法和基于 类分类器的技术处理.对二维和三维双螺旋及UCI 集成学习思想的分维分类学习算法.有关集成学 中的数据的分类实验结果说明，分类超曲面可以有 习周志华教授做了出色的工作1，).HSC的集成 效地解决在有限区域分布很复杂的海量(10')的非 特点是通过分维获得子分类器，不是通过划分样本 线性数据多类分类问题，计算速度较高，同时对计 集获得子分类器21.基于样本数据重排的换维分类 算机资源要求很低，而传统的SVM不具备这种优 学习]，将涉及到维排序和维组合问题，这些策略 点.另外小样本训练大样本测试结果表明，基于分类 具有多样性，他们如何影响分类器性能，如何找到最 超曲面的分类法的泛化能力较好.该方法是对直接 优的策略是待研究的问题.由于分类器集成方法是 解决非线性分类问题的一种尝试，此方法的一个前 基于分维的，那么维的排序策略、划分策略及权重策 提是同类样本点应具有在有限个连通分支分布的特 略就值得研究 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net进行判别(设 T 为样本点分类所得类别) :选择适当 的由待定点 X 出发的射线 f X ,设 f X 与 SHS t i 的相 交点数为 C t i ,分别计算 f X 与{SHS 1 a | a = 1 , …, r1 }和 {SHS 2 b | b = 1 , …, r2 } ( r1 + r2 = r) 的相交点数之和 , 记为 ∑ r 1 a = 1 C 1 a 和 ∑ r 2 b= 1 C 2 b ,则有 ∑ r 1 a= 1 C 1 a 为奇数 Ζ T = 1 或 ∑ r 2 b= 1 C 2 b 为奇数 Ζ T = 2. 实际上 ,求 C t i 的过程 ,就是求 f X 与 HP i l 相交数量 的过程. 6) 若不能判别 X 的类别 ,就对 X 所在的小区域 边界进行标定 ,不妨设 x t ( m + 1) ∈Dm + 1 ,则 Dm + 1的 边界可表示为 Hm+1 = { tm+1 , H m+1 p | p = 1 ,2 , …, km+1 } , 之后转入 4) ,继续合并相邻同类区域. 以上给出了基于分类超曲面的分类判别方法的 基本算法 ,即通过区域合并计算获得多个超平面组 成的双侧闭曲面作为分类超曲面对空间进行划分 , 也就是在样本点周围形成一个封闭区域 ,该区域由 多个分类超平面片围成 ,并使得该区域覆盖某一类 尽可能多的样本点 ,同时不覆盖异类样本点. 2 算法特点与已有研究成果 HSC 算法有 2 个关键步骤 ,一是局部化策略 , 另一个是用围绕数判断类别. 该算法中 ,判别样本所 属类别 ,不需与所有分类边界链表作相交操作后再 判断 ,而只需满足 :由样本点所引射线与一完整分类 边界链表相交点数为奇数即可 ,这样可提高判别速 度. 这种方法得到的分类超曲面是由若干个封闭闭 曲面构成 ,而曲面的局部是由低维平面片构成. 每个 闭曲面内部是一类样本 ,这样对闭曲面可以进行类 别标记. 样本类别可以是多个 ,所以这种方法对于多 类问题的解决是很方便的 ,因为多个分类器可以在 一次训练过程中产生 ,避免了 2 类分类器转化为多 类分类器的技术处理. 对二维和三维双螺旋及 UCI 中的数据的分类实验结果说明 ,分类超曲面可以有 效地解决在有限区域分布很复杂的海量 (10 7 ) 的非 线性数据多类分类问题 ,计算速度较高 , 同时对计 算机资源要求很低 , 而传统的 SVM 不具备这种优 点. 另外小样本训练大样本测试结果表明 ,基于分类 超曲面的分类法的泛化能力较好. 该方法是对直接 解决非线性分类问题的一种尝试 , 此方法的一个前 提是同类样本点应具有在有限个连通分支分布的特 点 , 但与连通分支的形状无关 ,在现实中的数据分 布大都满足条件之一[25 ] . HSC 算法发展至今 ,已相继解决了二维 2 类分 类[23 ] 、二维多 类 分 类[24 ] 、二 维 一 般 连 通 区 域 分 类[25 ] 、三维多类[26 ] 、高维换维分类问题[ 27 ] 、高维多 类集成分类问题[28 - 45 ] . 关于 HSC 算法的最新进展包括 :利用 HSC 算 法构造了极小样本集 ,提出了基于覆盖的极小样本 集的概念使之不仅可以代表整个模型 ,而且可以反 映出整个训练集的拓扑结构[46 ] ,并研究了 BA G2 GIN G和 ADABOOST 算法使用不同的训练样本集 时对 HSC 分类器性能的影响 ,试验结果表明 ,他们 对分类精度的提高是受极小样本集制约的[47 ] . 另外 从视觉认知角度研究了超曲面在和数据理解中的作 用[48 ] . 采用 Agent (智能主体) 技术用于多个 HSC 分类器的合成 ,使得 HSC 算法适合在分布式环境 中进行数据挖掘. 这种合成的特点是不把样本集划 分为若干小样本集的横向划分 , 而是对分布在不同 地点的不同属性的样本集就地作属性集纵向划分后 的合成[ 49 ] . 3 基于超曲面的覆盖分类学习算法的 研究方向 基于超曲面的分类学习算法 HSC 作为一种新 的算法 ,有很多问题亟待研究 ,这既包括算法优化 , 又包括理论分析 ,还包括应用中遇到的现实问题. 首先是优化高维数据分类算法问题. 从理论上 讲 ,这种方法可以推广到高维 ,因为 Jordan 定理在 任意有限维空间都是成立的. 但是高维空间中的实 现存在以下挑战性问题 :一是高维空间的单位方体 的合并计算复杂度随着维数增加而提高 ,另一方面 高维超曲面的存储开销大. 但是这并不意味 HSC 不能处理高维数据 ,借助数据预处理和集成学习技 术 ,对于高维数据处理提出并实现了 2 种解决办法. 这 2 种高维处理方法与 HSC 算法特点紧密结合 ,这 就是基于样本数据重排的换维分类学习算法和基于 集成学习思想[30 ]的分维分类学习算法. 有关集成学 习周志华教授做了出色的工作[31 - 32 ] . HSC 的集成 特点是通过分维获得子分类器 ,不是通过划分样本 集获得子分类器[28 ] . 基于样本数据重排的换维分类 学习[27 ] ,将涉及到维排序和维组合问题 ,这些策略 具有多样性 ,他们如何影响分类器性能 ,如何找到最 优的策略是待研究的问题. 由于分类器集成方法是 基于分维的 ,那么维的排序策略、划分策略及权重策 略就值得研究. 第 6 期 何 清 ,等 :基于超曲面的分类算法研究进展 ·3 ·