·2 智能系统学报 第2卷 相继提出了一些很有价值的分类学习方法.张铃、张 围绕数)为奇数，x∈X的外部自x引出的射线与 钹教授给出了MP神经元的几何意义，通过球面投 X的相交数为偶数.如图1所示.现在问题的关键在 影变换将神经网络的最优设计问题转化为某种最优 于如何获得分类超曲面 覆盖问题！.张铃、张钱教授给出了邻域覆盖算法 和交叉覆盖算法，以及改进的函数覆盖算法和核覆 盖算法.王守觉院士提出了仿生模式识别（拓扑模式 识别))，它是基于“认识”事物而不是基于“区 分”事物为目的，与传统以“最佳划分”为目标的统计 模式识别相比，它更接近于人类“认识”事物的特 性，故称为“仿生模式识别”徐宗本教授最近提出了 图1分类判别图示 一种基于视觉的分类方法(visual classification al- Fig.I Classification theorem illustration gorithm,VCA)),这种方法是针对目前很多分类 下面的算法给出了构造和使用分类超曲面的 方法主要是通过发现数据内在的结构来分类，很少 基本过程 或没有注意到从模拟人的感觉和感知来进行分类而 假定M个训练样本：Kan={x'(i)川t=1,2;i= 提出的.何清等提出了基于超曲面的分类学习算法 1,2M,不失一般性，假设样本点己预先标记好 (hyper surface classification,HSC)2),这t也是一种 的类别∈{1,2：训练空间D为一封闭区域，且其 覆盖分类算法.本文综述了基于超曲面的分类算法， 边界满足Jordan曲线定理的基本条件 对算法进行了详细分析和阐述，并指出了基于超曲 )设前m个训练样本落在区域D内，m∈ 面的分类算法进一步发展的方向 1,2,…,M. 1基于超曲面的分类学习算法 2)将区域D划分成n个小区域，设D=D1U D2U…UDm,n≥m.且满足以下条件： 基于超曲面的分类学习算法基本思想是从几何 ①D,(j=1,2,,的边界H满足Jordan曲 学和拓扑学出发的，该算法基于Jordan曲线定理， 线定理的基本条件： 根据围绕数的奇偶进行分类判断，该算法不需要考 ②x()∈D,i=1,2,…m,j=1,2,n,不妨 虑使用何种核函数，而直接地解决非线性分类问题. 设i=j,即每个小区域至多含一个样本点， 下面给出Jordan曲线定理和分类判别定理 3)设D(j=1,2,…,m的边界H分别由k Jorn曲线定理设XCR是闭子集，X同胚 个超平面片组成，可以将每片超平面表示为用，i= 于球面S2,那么它的余集R/S有2个连通分支，一 1,2,,k:则可将H表示为含类别分量和超平面 个是有界的，另一个是无界的，X中任何一点的任 片的集合， 何邻域与这2个连通分支均相交 H={5,|p=1,2,k;4=1,2} 上述定理可推广到高维空间 式中：t为D,所含样本点x'(的类别 定理1高维空间的Jordan曲线定理 4)若D,与D,(i)相邻，且=i,则合并边 若XCS”同胚于球面Sm,那么m≤n否则X= 界H,和H,不妨设H与H重合，即H=), S.若m<n,余集的同调群为 将重合超平面片消去，则获得封闭区域A虹，其边界 Z⊙Z,m=n-1且k=0, 为 Z,m<n-1且k=0, BL H,U Hj= 0,其他 ft,Ha,|a=1,…k,且a≠p 当m=n-1时SX由2个连通分支组成，当m<n b=1,k,且b≠q;红=. -1时，只有1个连通分支 继续合并相邻同类区域，最终获得一组由若干超平 Jordan曲线定理表明任何由n-1维球面经连 面片组成的封闭超曲面一分类超曲面，记为 续变形得到的双侧闭曲面都把n维空间分成2个区 SHS={ti,HPi|i∈f1,2,…; 域—一个外部和一个内部，这种曲面可用于分类， 1=1,2,…k;1=1,2},r≤m. 称之为分类超曲面.给定一个点x,判断它在分类超 以链的形式存储SHS的各超平面片HP,1=1,2, 曲面X的内部，还是在外部的方法是：x∈X的内部 “,k 自x引出的射线与X的相交数（即X关于x的 5)输入新样本点X=x'(m+1),按照以下方法 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net相继提出了一些很有价值的分类学习方法. 张铃、张 钹教授给出了 M2P 神经元的几何意义 ,通过球面投 影变换将神经网络的最优设计问题转化为某种最优 覆盖问题[12 ] . 张铃、张钹教授给出了邻域覆盖算法 和交叉覆盖算法 ,以及改进的函数覆盖算法和核覆 盖算法. 王守觉院士提出了仿生模式识别(拓扑模式 识别) [17 - 18 ] ,它是基于“认识”事物而不是基于“区 分”事物为目的 ,与传统以“最佳划分”为目标的统计 模式识别相比 , 它更接近于人类“认识”事物的特 性 ,故称为“仿生模式识别”. 徐宗本教授最近提出了 一种基于视觉的分类方法 ( visual classification al2 gorithm ,VCA) [21 ] ,这种方法是针对目前很多分类 方法主要是通过发现数据内在的结构来分类 ,很少 或没有注意到从模拟人的感觉和感知来进行分类而 提出的. 何清等提出了基于超曲面的分类学习算法 (hyper surface classification , HSC) [23 ] ,这也是一种 覆盖分类算法. 本文综述了基于超曲面的分类算法 , 对算法进行了详细分析和阐述 ,并指出了基于超曲 面的分类算法进一步发展的方向. 1 基于超曲面的分类学习算法 基于超曲面的分类学习算法基本思想是从几何 学和拓扑学出发的 ,该算法基于 Jordan 曲线定理 , 根据围绕数的奇偶进行分类判断 ,该算法不需要考 虑使用何种核函数 ,而直接地解决非线性分类问题. 下面给出 Jordan 曲线定理和分类判别定理. Jordan 曲线定理 设 X < R 3 是闭子集 , X 同胚 于球面 S 2 ,那么它的余集 R 3 / S 有 2 个连通分支 ,一 个是有界的 ,另一个是无界的 , X 中任何一点的任 何邻域与这 2 个连通分支均相交. 上述定理可推广到高维空间. 定理 1 高维空间的 Jordan 曲线定理. 若 X < S n 同胚于球面 S m ,那么 m ≤n 否则 X = S n . 若 m < n ,余集的同调群为 Hk (s n \ X) µ Z Ý Z , m = n - 1 且 k = 0 , Z , m < n - 1 且 k = 0 , 0 ,其他. 当 m = n - 1 时 S n \ X 由 2 个连通分支组成 ,当 m < n - 1 时 ,只有 1 个连通分支. Jordan 曲线定理表明任何由 n - 1 维球面经连 续变形得到的双侧闭曲面都把 n 维空间分成 2 个区 域 ———一个外部和一个内部 ,这种曲面可用于分类 , 称之为分类超曲面. 给定一个点 x ,判断它在分类超 曲面 X 的内部 ,还是在外部的方法是 : x ∈X 的内部 Ζ自 x 引出的射线与 X 的相交数 (即 X 关于 x 的 围绕数) 为奇数 , x ∈X 的外部 Ζ自 x 引出的射线与 X 的相交数为偶数. 如图 1 所示. 现在问题的关键在 于如何获得分类超曲面. 图 1 分类判别图示 Fig. 1 Classification theorem illustration 下面的算法给出了构造和使用分类超曲面的 基本过程. 假定 M 个训练样本 : Ktrain = { x′( i) | t = 1 ,2 ; i = 1 ,2 …, M} ,不失一般性 ,假设样本点已预先标记好 的类别 ti ∈{ 1 ,2} ;训练空间 D 为一封闭区域 ,且其 边界满足 Jordan 曲线定理的基本条件. 1) 设前 m 个训练样本落在区域 D 内 , m ∈ { 1 ,2 , …, M} . 2) 将区域 D 划分成 n 个小区域 ,设 D = D1 ∪ D2 ∪…∪Dn , n ≥m. 且满足以下条件 : ①Dj ( j = 1 , 2 , …, n) 的边界 Hj 满足 Jordan 曲 线定理的基本条件; ②x′( i) ∈Dj , i = 1 ,2 , …, m , j = 1 ,2 , …, n ,不妨 设 i = j ,即每个小区域至多含一个样本点. 3) 设 Dj ( j = 1 , 2 , …, m) 的边界 Hj 分别由 k j 个超平面片组成 ,可以将每片超平面表示为 H j i , i = 1 ,2 , …, kj ;则可将 Hj 表示为含类别分量和超平面 片的集合 , Hj = { tj , H j p | p = 1 ,2 , …, kj ; tj = 1 ,2} . 式中 :tj 为 D j 所含样本点 x′( j) 的类别. 4) 若 Di 与 D j ( i ≠j) 相邻 ,且 ti = tj ,则合并边 界 Hi 和 H j (不妨设 H i p 与 H j p 重合 ,即 H i p = H j q ) , 将重合超平面片消去 ,则获得封闭区域 AL ,其边界 为 BL = Hi ∪ Hj = { tL , H i a , H j b | a = 1 , …, ki ,且 a ≠p ; b = 1 , …, kj ,且 b ≠q; tL = ti} . 继续合并相邻同类区域 ,最终获得一组由若干超平 面片组成的封闭超曲面 ———分类超曲面 ,记为 SHS t i = { ti , HP i l | i ∈{ 1 ,2 , …, r} ; l = 1 ,2 , …, ki ; ti = 1 ,2} , r ≤m. 以链的形式存储 SHS t i 的各超平面片 HP i l , l = 1 , 2 , …, ki . 5) 输入新样本点 X = x t ( m + 1) ,按照以下方法 ·2 · 智 能 系 统 学 报 第 2 卷