第9卷第3期 智能系统学报 Vol.9 No.3 2014年6月 CAAI Transactions on Intelligent Systems Jun.2014 D0:10.3969/j.issn.1673-4785.201403063 网络出版地址：http://www.enki..net/kcms/doi/10.3969/j.issn.16734785.201403063.html 邻域同调学习算法 赵梦梦，李凡长 (苏州大学计算机科学与技术学院，江苏苏州215006) 摘要：日前已有的边缘学习算法对边缘可变的数据划分问题存在一些不足，这些算法在分类过程中不能有效地保 证数据的结构特征不变。因而文章首先通过引进同调代数中的单形划分理论，从机器学习的角度对分类问题中的 边缘划分进行研究，提出了一种邻域同调学习算法。算法给出了图形的邻域复形的构造方法和判断2个给定图形 相似性的判定标准。最后通过在USPS_ALL手写数字集数据库和MPEG7CE图像库上与SVM、TVQ算法的对比实 验验证了本算法的有效性。 关键词：同调学习：同调代数：机器学习：边缘划分：边缘同调学习：邻域同调学习算法：邻域复形图：相似性 中图分类号：TP181文献标志码：A文章编号：1673-4785(2014)03-0336-07 中文引用格式：赵梦梦，李凡长.邻城同调学习算法[J].智能系统学报，2014,9(3)：336-343. 英文引用格式：ZHAO Mengmeng,LI Fanzhang..Neighborhood homology learning algorithm[J].CAAI Transactions on Intelligent Systems,2014,9(3):336-343. Neighborhood homology learning algorithm ZHAO Mengmeng,LI Fanzhang (School of Computer Science and Technology,Soochow University,Suzhou 215006,China) Abstract:At present,the existing margin learning algorithms still have some affects when attempting to solve the data partitioning problem of variable margins.These algorithms can not effectively maintain the structure feature of datas in classification..At present,the existing margin learning algorithms still have defects when attempting to solve the data partitioning problem of variable margins.As a consequence,this paper initially proposes a neighbor- hood homology learning algorithm through using the monomorphic division theory in homology algebra.The neigh- borhood homology learning algorithm reasearchs the margin partitioning problem from the perspective of machine learning.The neighborhood homology learning algorithm includes the method of structuring the neighborhood com- plex,and the criterion for judging the similarity between two given graphs.Finally,this algorithm is justified through the experimental results contrasted with SVM and TVQ on an image dataset named MPEG7 CE and a data- base of handwritten digits named USPSALL. Keywords:homology learning;homology algebra;machine learning;margin partitioning;margin homology learn- ing;neighborhood homology learning algorithm;neighborhood complex graphs;similarity 边缘学习s1是机器学习的核心问题之一。目 Sperduti提出的TVQ算法[9]和同调边缘胞腔学习 前比较成功的边缘学习算法主要有V.Vapnik提出 算法等10-) 的SVM最大边缘算法[6-8]，Fabio Ailli、Alessandro 支持向量机(support vector machine,SVM)是一 种努力最小化结构风险213]的算法，主要有线性可 收稿日期：2014-03-22.网络出版日期：2014-06-14. 基金项目：国家自然科学基金资助项目(61033013,60775045). 分支持向量机12】、近似线性可分支持向量机12]和 通信作者：李凡长.E-mail:lfh@suda.eu.cn. 线性不可分支持向量机。线性可分支持向量机又叫
第 ９ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．３ ２０１４ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０３０６３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｏｉ ／ １０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３４７８５．２０１４０３０６３．ｈｔｍｌ 邻域同调学习算法 赵梦梦，李凡长 （苏州大学 计算机科学与技术学院，江苏 苏州 ２１５００６） 摘 要：目前已有的边缘学习算法对边缘可变的数据划分问题存在一些不足，这些算法在分类过程中不能有效地保 证数据的结构特征不变。 因而文章首先通过引进同调代数中的单形划分理论，从机器学习的角度对分类问题中的 边缘划分进行研究，提出了一种邻域同调学习算法。 算法给出了图形的邻域复形的构造方法和判断 ２ 个给定图形 相似性的判定标准。 最后通过在 ＵＳＰＳ＿ＡＬＬ 手写数字集数据库和 ＭＰＥＧ７ ＣＥ 图像库上与 ＳＶＭ、ＴＶＱ 算法的对比实 验验证了本算法的有效性。 关键词：同调学习；同调代数；机器学习；边缘划分；边缘同调学习；邻域同调学习算法；邻域复形图；相似性 中图分类号： ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０３⁃０３３６⁃０７ 中文引用格式：赵梦梦，李凡长． 邻域同调学习算法［Ｊ］． 智能系统学报， ２０１４， ９（３）： ３３６⁃３４３． 英文引用格式：ＺＨＡＯ Ｍｅｎｇｍｅｎｇ，ＬＩ Ｆａｎｚｈａｎｇ． Ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（３）： ３３６⁃３４３． Ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ＺＨＡＯ Ｍｅｎｇｍｅｎｇ，ＬＩ Ｆａｎｚｈａｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｓｏｏｃｈｏｗ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｕｚｈｏｕ ２１５００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｔ ｐｒｅｓｅｎｔ ，ｔｈｅ ｅｘｉｓｔｉｎｇ ｍａｒｇｉｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｓｔｉｌｌ ｈａｖｅ ｓｏｍｅ ａｆｆｅｃｔｓ ｗｈｅｎ ａｔｔｅｍｐｔｉｎｇ ｔｏ ｓｏｌｖｅ ｔｈｅ ｄａｔａ ｐａｒｔｉｔｉｏｎｉｎｇ ｐｒｏｂｌｅｍ ｏｆ ｖａｒｉａｂｌｅ ｍａｒｇｉｎｓ．Ｔｈｅｓｅ ａｌｇｏｒｉｔｈｍｓ ｃａｎ ｎｏｔ ｅｆｆｅｃｔｉｖｅｌｙ ｍａｉｎｔａｉｎ ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｆｅａｔｕｒｅ ｏｆ ｄａｔａｓ ｉｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ．． Ａｔ ｐｒｅｓｅｎｔ， ｔｈｅ ｅｘｉｓｔｉｎｇ ｍａｒｇｉｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｓｔｉｌｌ ｈａｖｅ ｄｅｆｅｃｔｓ ｗｈｅｎ ａｔｔｅｍｐｔｉｎｇ ｔｏ ｓｏｌｖｅ ｔｈｅ ｄａｔａ ｐａｒｔｉｔｉｏｎｉｎｇ ｐｒｏｂｌｅｍ ｏｆ ｖａｒｉａｂｌｅ ｍａｒｇｉｎｓ． Ａｓ ａ ｃｏｎｓｅｑｕｅｎｃｅ， ｔｈｉｓ ｐａｐｅｒ ｉｎｉｔｉａｌｌｙ ｐｒｏｐｏｓｅｓ ａ ｎｅｉｇｈｂｏｒ⁃ ｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｈｒｏｕｇｈ ｕｓｉｎｇ ｔｈｅ ｍｏｎｏｍｏｒｐｈｉｃ ｄｉｖｉｓｉｏｎ ｔｈｅｏｒｙ ｉｎ ｈｏｍｏｌｏｇｙ ａｌｇｅｂｒａ． Ｔｈｅ ｎｅｉｇｈ⁃ ｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｒｅａｓｅａｒｃｈｓ ｔｈｅ ｍａｒｇｉｎ ｐａｒｔｉｔｉｏｎｉｎｇ ｐｒｏｂｌｅｍ ｆｒｏｍ ｔｈｅ ｐｅｒｓｐｅｃｔｉｖｅ ｏｆ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ． Ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｎｃｌｕｄｅｓ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｓｔｒｕｃｔｕｒｉｎｇ ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｃｏｍ⁃ ｐｌｅｘ， ａｎｄ ｔｈｅ ｃｒｉｔｅｒｉｏｎ ｆｏｒ ｊｕｄｇｉｎｇ ｔｈｅ ｓｉｍｉｌａｒｉｔｙ ｂｅｔｗｅｅｎ ｔｗｏ ｇｉｖｅｎ ｇｒａｐｈｓ． Ｆｉｎａｌｌｙ， ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｉｓ ｊｕｓｔｉｆｉｅｄ ｔｈｒｏｕｇｈ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｃｏｎｔｒａｓｔｅｄ ｗｉｔｈ ＳＶＭ ａｎｄ ＴＶＱ ｏｎ ａｎ ｉｍａｇｅ ｄａｔａｓｅｔ ｎａｍｅｄ ＭＰＥＧ７ ＣＥ ａｎｄ ａ ｄａｔａ⁃ ｂａｓｅ ｏｆ ｈａｎｄｗｒｉｔｔｅｎ ｄｉｇｉｔｓ ｎａｍｅｄ ＵＳＰＳ＿ＡＬＬ． Ｋｅｙｗｏｒｄｓ：ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ； ｈｏｍｏｌｏｇｙ ａｌｇｅｂｒａ； ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ； ｍａｒｇｉｎ ｐａｒｔｉｔｉｏｎｉｎｇ； ｍａｒｇｉｎ ｈｏｍｏｌｏｇｙ ｌｅａｒｎ⁃ ｉｎｇ； ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ； ｎｅｉｇｈｂｏｒｈｏｏｄ ｃｏｍｐｌｅｘ ｇｒａｐｈｓ； ｓｉｍｉｌａｒｉｔｙ 收稿日期：２０１４⁃０３⁃２２． 网络出版日期：２０１４⁃０６⁃１４． 基金项目：国家自然科学基金资助项目（６１０３３０１３，６０７７５０４５）． 通信作者：李凡长． Ｅ⁃ｍａｉｌ：ｌｆｚｈ＠ ｓｕｄａ．ｅｄｕ．ｃｎ． 边缘学习［１⁃５ ］是机器学习的核心问题之一。 目 前比较成功的边缘学习算法主要有 Ｖ．Ｖａｐｎｉｋ 提出 的 ＳＶＭ 最大边缘算法［ ６⁃８ ］ ， Ｆａｂｉｏ Ａｉｌｌｉ、 Ａｌｅｓｓａｎｄｒｏ Ｓｐｅｒｄｕｔｉ 提出的 ＴＶＱ 算法［ ９ ］ 和同调边缘胞腔学习 算法等［１０⁃１１］ 。 支持向量机（ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ，ＳＶＭ）是一 种努力最小化结构风险［１ ２ ⁃１ ３ ］的算法，主要有线性可 分支持向量机［１ ２ ］ 、近似线性可分支持向量机［１ ２ ］ 和 线性不可分支持向量机。 线性可分支持向量机又叫
第3期 赵梦梦，等：邻域同调学习算法 ·337· 硬间隔支持向量机2]，它是在正确划分训练集的 算群、环、代数的同调群是同调的重要研究课题。 超平面中，采用极大间隔分类超平面的方 为了方便讨论，先介绍一些基本概念。 法2,1415]，根据最大间隔原则，找出最优的决策超 定义1设点集{ao,a1,…,a,}CR”,R”表示 平面。近似线性可分支持向量机即软间隔支持向量 线性的n维欧氏空间，若矢量组a1-ao,a2-ao,…, 机(soft margin SVM)[1s],是在线性可分的情况下建 a,-a线性无关，则称点集{ao,a1,…,a,}CR"在 立起来的，即在线性可分支持向量机的最优化问题 R中是几何独立的。 上添加松弛因子专：和惩罚因子C,允许有错分样本 设点集{ao,a1,…,a,}在R中几何独立，令 存在。线性不可分25]是通过引入一个核函 数12)来实现的，该方法是将原始数据通过非线性 A={xER=2Aa,A,≥0,2，= =0 i=0 映射投影到高维空间，使得数据在高维空间变得线 称A?为g维几何单形，简称q维单形，记作〈ao,a1, 性可分。 …,a,〉，ao,a1,…,a,称为q维单形A9的顶点，实数 在TVQ算法中，提出了一个对提升边缘问题的 入：称为点x在g维单形A?中的重心坐标。 很好的方案，该方案是建立在边缘理论原则上，是基 定义2设K=A9,9=0,1,…,n,i=1,2,…,a。 于样本加权策略。其算法实例包含了基于1-NN分 是R中有限个单形的集合，若满足下列2个条件， 类器的切线距离16]，其中1-NN分类器加入了一种 则称K为单纯复形。 量子化的切距离原型。该算法中，引入的切距离原 1)K中任意2个单形都是规则相处的： 型在关于标准切线模式的泛化误差中得到了明显的 2)K中任意单形的任意一个面仍是K中的单形。 改进。该方法与SVM方法进行比较，可以观察到， 单纯复形K中的0维单形称为K中的顶点。K 当此方法和SVM方法具有从经验风险到理想风险 的维数是K中单形维数的最大值，即dimK:= 中一致收敛的统计学习理论概念时，该方法将输入 max{q;A9∈K}。对于一个q维单形的全体顶点 分布直接工作在非线性模型上而不是采取预定义核 ao,a1,…,a,,它们的全部排列可以分成2组：同一 的方式。该方法和Boosting算法[17.18]很相似，但是 组（如：同是顺时针方向）中的排列彼此差一个偶置 在Boosting算法中，采取的是多种组合假设；而在 换，不同组之间的排列，彼此差一个奇置换。这两组 TVQ算法中，更加关注的是独立假设。 叫做A?的2个定向。选定定向的单形叫做有向单 SVM和TVQ在一定程度上都提高了边缘划分 形，那么可以将该有向单形中的一组记作+σ？（简 效果和准确度。但是这些方法对边缘可变的划分问 记作σ”)，另一组相反指向的记作-σ”。 题就显得不足了，因此本文提出了一种邻域同调学 现有一n维单纯复形K, 习算法。邻域同调学习算法是通过引进同调论思 {499=0,1,…,n,i=1,2,…,a,}是它的全部单 想，从机器学习的角度出发研究的一种边缘学习新 形。对每个A:取定一个指向，这个有向单形记作σ 方法。该方法针对图集的分类问题，在分类过程中 (另一个指向决定的有向单形就是一σ)。则称 能够有效地保证图形的结构特征不变。该方法主要 {c9=0,1,…,n,i=1,2,…,an}为K的有向单 是通过判断给定图形的邻域复形的各阶同调群是否 形的一个基本组。 同构，对图形进行邻域同调分类。 (1) 1 邻域同调的基本概念 2AaA∈Z,g=0l,,n 同调[92]是源于代数拓扑学211的一个分支。 叫做K的一个g维链。链(1)与同维链y= μo 20世纪40年代，代数拓扑学的一些概念和方法被 的和定义为链： 引进春代数领域，形成了系统的理论，它的兴起对 群、李代数22]与结合环的研究都起了非常重要的 x9+y9= 乏(：+4，) (2) 作用。同调的研究对象基本上是模范畴2324]所派 显然，在式(2)的加法运算下，g维链的全体构成一 生一些Abel范畴，其核心是同调以及同调函子。代 个自由交换群，记作C,(K),即 数拓扑学中的复形、同调群等概念也由此引入。其 中起重要作用的一类模234]是投射模、内射模和平 c,闲=(2，五9=01.3 i 坦模，利用它们定义了扩张函子和n级张量函子以 C,(K)叫作K的q维（整数）链群。且对于任意K 及同调维数24]等概念。在环论研究中，利用同调 性质来刻画环自身结构取得了一系列重要成果。计 的g维链c= 立x,meC,W,令
硬间隔支持向量机［１ ２ ］ ，它是在正确划分训练集的 超 平 面 中， 采 用 极 大 间 隔 分 类 超 平 面 的 方 法［１ ２ ，１ ４ ⁃ １ ５ ］ ，根据最大间隔原则，找出最优的决策超 平面。 近似线性可分支持向量机即软间隔支持向量 机（ｓｏｆｔ ｍａｒｇｉｎ ＳＶＭ） ［１ ５ ］ ，是在线性可分的情况下建 立起来的，即在线性可分支持向量机的最优化问题 上添加松弛因子 ξｉ 和惩罚因子 Ｃ ，允许有错分样本 存在。 线 性 不 可 分［１ ２ ，１ ５ ］ 是 通 过 引 入 一 个 核 函 数［１ ２ ］来实现的，该方法是将原始数据通过非线性 映射投影到高维空间，使得数据在高维空间变得线 性可分。 在 ＴＶＱ 算法中，提出了一个对提升边缘问题的 很好的方案，该方案是建立在边缘理论原则上，是基 于样本加权策略。 其算法实例包含了基于 １⁃ＮＮ 分 类器的切线距离［１ ６ ］ ，其中 １⁃ＮＮ 分类器加入了一种 量子化的切距离原型。 该算法中，引入的切距离原 型在关于标准切线模式的泛化误差中得到了明显的 改进。 该方法与 ＳＶＭ 方法进行比较，可以观察到， 当此方法和 ＳＶＭ 方法具有从经验风险到理想风险 中一致收敛的统计学习理论概念时，该方法将输入 分布直接工作在非线性模型上而不是采取预定义核 的方式。 该方法和 Ｂｏｏｓｔｉｎｇ 算法［１ ７ ⁃ １８ ］很相似，但是 在 Ｂｏｏｓｔｉｎｇ 算法中，采取的是多种组合假设；而在 ＴＶＱ 算法中，更加关注的是独立假设。 ＳＶＭ 和 ＴＶＱ 在一定程度上都提高了边缘划分 效果和准确度。 但是这些方法对边缘可变的划分问 题就显得不足了，因此本文提出了一种邻域同调学 习算法。 邻域同调学习算法是通过引进同调论思 想，从机器学习的角度出发研究的一种边缘学习新 方法。 该方法针对图集的分类问题，在分类过程中 能够有效地保证图形的结构特征不变。 该方法主要 是通过判断给定图形的邻域复形的各阶同调群是否 同构，对图形进行邻域同调分类。 １ 邻域同调的基本概念 同调［ １９ ⁃２ ０ ］是源于代数拓扑学［２ １ ］ 的一个分支。 ２０ 世纪 ４０ 年代，代数拓扑学的一些概念和方法被 引进春代数领域，形成了系统的理论，它的兴起对 群、李代数［２ ２ ］ 与结合环的研究都起了非常重要的 作用。 同调的研究对象基本上是模范畴［２ ３⁃２４ ］ 所派 生一些 Ａｂｅｌ 范畴，其核心是同调以及同调函子。 代 数拓扑学中的复形、同调群等概念也由此引入。 其 中起重要作用的一类模［２ ３⁃２４ ］是投射模、内射模和平 坦模，利用它们定义了扩张函子和 ｎ 级张量函子以 及同调维数［２ ４ ］ 等概念。 在环论研究中，利用同调 性质来刻画环自身结构取得了一系列重要成果。 计 算群、环、代数的同调群是同调的重要研究课题。 为了方便讨论，先介绍一些基本概念。 定义 １ 设点集 ａ０ ，ａ１ ，…，ａｑ { } ⊂ Ｒ ｎ ， Ｒ ｎ 表示 线性的 ｎ 维欧氏空间，若矢量组 ａ１ － ａ０ ，ａ２ － ａ０ ，…， ａｑ － ａ０ 线性无关，则称点集 ａ０ ，ａ１ ，…，ａｑ { } ⊂ Ｒ ｎ 在 Ｒ ｎ 中是几何独立的。 设点集 ａ０ ，ａ１ ，…，ａｑ { } 在 Ｒ ｎ 中几何独立，令 Ａ ｑ ＝ ｘ ∈ Ｒ ｎ ；ｘ ＝ ∑ ｑ ｉ ＝ ０ λｉａｉ，λｉ ≥ ０，∑ ｑ ｉ ＝ ０ λｉ { ＝ １} 称 Ａ ｑ 为 ｑ 维几何单形，简称 ｑ 维单形，记作 〈ａ０ ，ａ１ ， …，ａｑ〉 ， ａ０ ，ａ１ ，…，ａｑ 称为 ｑ 维单形 Ａ ｑ 的顶点，实数 λｉ 称为点 ｘ 在 ｑ 维单形 Ａ ｑ 中的重心坐标。 定义 ２ 设 Ｋ ＝ Ａ ｑ ｉ ，ｑ ＝ ０，１，…，ｎ，ｉ ＝ １，２，…，αｑ 是 Ｒ ｍ 中有限个单形的集合，若满足下列 ２ 个条件， 则称 Ｋ 为单纯复形。 １） Ｋ 中任意 ２ 个单形都是规则相处的； ２） Ｋ 中任意单形的任意一个面仍是 Ｋ 中的单形。 单纯复形 Ｋ 中的 ０ 维单形称为 Ｋ 中的顶点。 Ｋ 的维 数 是 Ｋ 中 单 形 维 数 的 最 大 值， 即 ｄｉｍＫ： ＝ ｍａｘ ｑ；Ａ { ｑ ∈ Ｋ} 。 对于一个 ｑ 维单形的全体顶点 ａ０ ，ａ１ ，…，ａｑ ，它们的全部排列可以分成 ２ 组：同一 组（如：同是顺时针方向）中的排列彼此差一个偶置 换，不同组之间的排列，彼此差一个奇置换。 这两组 叫做 Ａ ｑ 的 ２ 个定向。 选定定向的单形叫做有向单 形，那么可以将该有向单形中的一组记作 ＋ σ ｑ （简 记作 σ ｑ ），另一组相反指向的记作 － σ ｑ 。 现 有 一 ｎ 维 单 纯 复 形 Ｋ ， Ａ ｑ ｉ ；ｑ ＝ ０，１，…，ｎ，ｉ ＝ １，２，…，αｑ { } 是 它 的 全 部 单 形。 对每个 Ａ ｑ ｉ 取定一个指向，这个有向单形记作 σ ｑ ｉ （另一个指向决定的有向单形就是 － σ ｑ ｉ ）。 则称 σ ｑ ｉ ；ｑ ＝ ０，１，…，ｎ，ｉ ＝ １，２，…，αｑ { } 为 Ｋ 的有向单 形的一个基本组。 ｘ ｑ ＝ ∑ αｑ ｉ ＝ １ λｉσ ｑ ｉ ，λｉ ∈ Ｚ，ｑ ＝ ０，１，…，ｎ （１） 叫做 Ｋ 的一个 ｑ 维链。 链（１）与同维链 ｙ ｑ ＝∑ αｑ ｉ ＝ １ μｉσ ｑ ｉ 的和定义为链： ｘ ｑ ＋ ｙ ｑ ＝ ∑ αｑ ｉ ＝ １ （λｉ ＋ μｉ）σ ｑ ｉ （２） 显然，在式（２）的加法运算下， ｑ 维链的全体构成一 个自由交换群，记作 Ｃｑ (Ｋ) ，即 Ｃｑ (Ｋ) ＝ ∑ αｑ ｉ ＝ １ λｉσ ｑ { ｉ ；λｉ ∈ Ｚ， ｑ ＝ ０，１，…，ｎ} （３） Ｃｑ (Ｋ) 叫作 Ｋ 的 ｑ 维（整数） 链群。 且对于任意 Ｋ 的 ｑ 维链 ｃ ｑ ＝ ∑ αｑ ｉ ＝ １ λｉσ ｑ ｉ ∈ Ｃｑ (Ｋ) ，令 第 ３ 期 赵梦梦，等：邻域同调学习算法 ·３３７·
·338· 智能系统学报 第9卷 a,e=,(2）=2A,a e Cok(4 为元素所得的集K,叫做以co,C1,…,c。为顶点的抽 i=1 象复形，如果满足以下2个条件： 则a,:C,(K)→Cg-1(K)是群同态。这里的a,即为 1)由单个元素c,所组成的子集属于K,这里i= q维边缘算子或边缘同态。其实，边缘同态是几何 0,1,…,9； 上概念的代数化，是用来反映图形的边界关系的。 2)若A是K的元，则A的子集也是K的元。 在此基础上，定义出一个单纯链复形C,(K)= 抽象复形K中的元A叫做抽象单形，它的维数 {C,(K),a,}。C.(K)即是一串g维（整数）链群 是其顶点数减1。A的子集叫做A的面。K的维数 C,(K)和一串边缘同态a,:C,(K→C,-1(K),排成 是K中诸单形的最大维数。显然，每个单纯复形K 一个序列： 都自然地决定一个抽象复形K。实际上，K的每个 →0→C,C-1()）- 单形(aa…a,)规定K的一个抽象单形 (5)》 (cc,)。这样规定的K,显然是一个抽象复形， →C,(K)C,(K60 且称K为K的一个几何实现。 满足条件对每个维数q都有0,0，+1=0，也就是说“2 2邻域同调学习算法 次边缘为零”。 定义3单纯复形K的g维闭链群和边缘链群 设G=(V(G),E(G))是一个简单连通图。显 依次为 然，一个简单连通图就是一个单纯复形，根据上述定 Z,(K)=Keri。={z9∈C,(K);a,z=0}(6) 义即可以看成是有限个单形的集合，V(G)= B,(K)=Im0,+1= {ao,a1,…,a-1}表示图G的a。个顶点的集合也 {beC,(K);3c*1∈C,+1(K),使ac*1=b'} 就是图G中所有0维单形的集合，E(G)表示顶点 之间的所有连接边的集合。令X和F分别是G的 (7) 一个顶点子集和边子集，就以G一X表示G去掉X Z,(K)的元”叫做q维闭链，B,(K)的元b9叫做q 中的点及其关联边而得的图，G-F表示G去掉F 维边缘链。 中的边而得到的图。设a是G的任意一个顶点，以 这里B,(K)CZ(K),而且作为自由群 N(a)表示a的邻域，那么N(X)表示X中所有点 C,(K)的子群，它们也都是自由的。Z,(K)是描述有 邻域的并，即N(X)=U,N(a)。 可能成为边的图形，B,(K)是描述真的是边的图形。 基于此，可以构造出一幅给定图形G的领域复 那么“有可能成为边，又不真是边”这一事实，用群论 形N(G),N(G)是以G的顶点为顶点，以G中具有 的语言来表达，就应该是：在有可能成为边的 公共邻接点的子集为单形的一个抽象复形。根据抽 Z(K)中，模真是边的部分B(K)。这样就有商群： 象复形的概念，可以看出任意的抽象复形都可以在 H (K)=Z (K)/B (K)Kerd/Imd+ 欧氏空间实现25]。因此邻域复形在欧氏空间中是 H,(K)叫做单纯复形K的g维（单纯）同调群。 有其相对应的单纯复形的，这里仍以N(G)记邻域 同调群H(K)中的元素为Z,(K)中元素的模 复形所对应的单纯复形。除非特殊说明，二者不加 B(K)的等价类，因此，由单纯复形K上q维闭链” 以区别，统称为G的邻域复形。下文中的N(G)即 所决定的模B(K)的等价类是z+B,(K),记作 指邻域复形在欧氏空间中所对应的单纯复形。 [z],称其为z”的q维同调类，并且Hn(K)= 由于构造出的任意图形的邻域复形N(G)可以 {[z];z”∈Z,(K)}。同一同调类中的元号和号 看成是单纯复形，那么可以将N(G)剖分成有限个 称为同调的，记作月~号或-号~0。 单形，根据定义2可表示为N(G)= 由定义2可以看出单纯复形是由简单的图 {A;9=0,1,…,dim(N(G)),i=1,2,…,a};对 形一单形构成的。那么有了一个单纯复形之后， 每个单形取定一个指向并记为σ！，根据定义1，每 由此出发也可构成相应的新复形。其实仔细观察单 个单形σ？都可以根据顶点坐标线性表示出来：再由 纯复形的定义就会发现，单纯复形实际上完全由其 式(1)将q维单形线性组合就能得出N(G)的q维 顶点和顶点构成的子集组（单形）所决定，当然这时 链，这些g维链组成的自由交换群即为N(G)的q 顶点的子集组要适合某种条件。据此，定义4给出 维链群C,(W(G))。再通过计算同调群，就可以得 了抽象复形的定义，该定义则为本文算法中提到的 出2个图形之间的一种同调关系。设有2个图G、 构造邻域复形提供了理论基础。 H,如果N(G)和N(H)的各阶同调群分别同构，就 定义4以有限个元素c0,c1,…,c,的子集做 称G和H是邻域同调的，记为G≥H
∂ｑ ｃ ｑ ＝ ∂ｑ ∑ αｑ ｉ ＝ １ λｉσ ｑ ( ｉ ) ＝ ∑ αｑ ｉ ＝ １ λｉ∂σ ｑ ｉ ∈ Ｃｑ－１Ｋ （４） 则 ∂ｑ：Ｃｑ (Ｋ) → Ｃｑ－１ (Ｋ) 是群同态。 这里的 ∂ｑ 即为 ｑ 维边缘算子或边缘同态。 其实，边缘同态是几何 上概念的代数化，是用来反映图形的边界关系的。 在此基础上，定义出一个单纯链复形 Ｃ∗ (Ｋ) ＝ Ｃｑ (Ｋ) ，∂ｑ { } 。 Ｃ∗ (Ｋ) 即是一串 ｑ 维（整数） 链群 Ｃｑ (Ｋ) 和一串边缘同态 ∂ｑ：Ｃｑ (Ｋ) → Ｃｑ－１ (Ｋ) ，排成 一个序列： … → ０ → Ｃｑ (Ｋ) ∂ｑ→ Ｃｑ－１ (Ｋ) ∂ｑ－１→ … → Ｃ１ (Ｋ) ∂１→ Ｃ０ (Ｋ) ∂０→ ０ （５） 满足条件对每个维数 ｑ 都有 ∂ｑ∂ｑ＋１ ＝ ０，也就是说“２ 次边缘为零”。 定义 ３ 单纯复形 Ｋ 的 ｑ 维闭链群和边缘链群 依次为 Ｚｑ (Ｋ) ＝ Ｋｅｒ∂ｑ ＝ ｚ ｑ ∈ Ｃｑ (Ｋ) ；∂ｑ ｚ ｑ { ＝ ０} （６） Ｂｑ (Ｋ) ＝ Ｉｍ∂ｑ＋１ ＝ ｂ ｑ ∈ Ｃｑ (Ｋ) ；∃ｃ ｑ＋１ ∈ Ｃｑ＋１ (Ｋ) ， 使 ∂ｃ ｑ＋１ ＝ ｂ ｑ { } （７） Ｚｑ (Ｋ) 的元 ｚ ｑ 叫做 ｑ 维闭链， Ｂｑ (Ｋ) 的元 ｂ ｑ 叫做 ｑ 维边缘链。 这 里 Ｂｑ (Ｋ) ⊂ Ｚｑ (Ｋ) ， 而 且 作 为 自 由 群 Ｃｑ (Ｋ) 的子群，它们也都是自由的。 Ｚｑ (Ｋ) 是描述有 可能成为边的图形， Ｂｑ (Ｋ) 是描述真的是边的图形。 那么“有可能成为边，又不真是边”这一事实，用群论 的语 言 来 表 达， 就 应 该 是： 在 有 可 能 成 为 边 的 Ｚｑ (Ｋ) 中，模真是边的部分 Ｂｑ (Ｋ) 。 这样就有商群： Ｈｑ (Ｋ) ＝ Ｚｑ (Ｋ) ／ Ｂｑ (Ｋ) ＝ Ｋｅｒ∂ｑ ／ Ｉｍ∂ｑ＋１ Ｈｑ (Ｋ) 叫做单纯复形 Ｋ 的 ｑ 维（单纯）同调群。 同调群 Ｈｑ (Ｋ) 中的元素为 Ｚｑ (Ｋ) 中元素的模 Ｂｑ (Ｋ) 的等价类，因此，由单纯复形 Ｋ 上 ｑ 维闭链 ｚ ｑ 所决定的模 Ｂｑ (Ｋ) 的等价类是 ｚ ｑ ＋ Ｂｑ (Ｋ) ，记作 ｚ ｑ [ ] ， 称 其 为 ｚ ｑ 的 ｑ 维 同 调 类， 并 且 Ｈｑ (Ｋ) ＝ ｚ ｑ [ ] ；ｚ { ｑ ∈ Ｚｑ (Ｋ) } 。 同一同调类中的元 ｚ ｑ １ 和 ｚ ｑ ２ 称为同调的，记作 ｚ ｑ １ ～ ｚ ｑ ２ 或 ｚ ｑ １ － ｚ ｑ ２ ～ ０。 由定义 ２ 可以看出单纯复形是由简单的图 形———单形构成的。 那么有了一个单纯复形之后， 由此出发也可构成相应的新复形。 其实仔细观察单 纯复形的定义就会发现，单纯复形实际上完全由其 顶点和顶点构成的子集组（单形）所决定，当然这时 顶点的子集组要适合某种条件。 据此，定义 ４ 给出 了抽象复形的定义，该定义则为本文算法中提到的 构造邻域复形提供了理论基础。 定义 ４ 以有限个元素 ｃ０ ，ｃ１ ，…，ｃｑ 的子集做 为元素所得的集 Ｋ，叫做以 ｃ０ ，ｃ１ ，…，ｃｑ 为顶点的抽 象复形，如果满足以下 ２ 个条件： １）由单个元素 ｃｉ 所组成的子集属于 Ｋ，这里 ｉ ＝ ０，１，…，ｑ ； ２）若 Ａ 是 Ｋ 的元，则 Ａ 的子集也是 Ｋ 的元。 抽象复形 Ｋ 中的元 Ａ 叫做抽象单形，它的维数 是其顶点数减 １。 Ａ 的子集叫做 Ａ 的面。 Ｋ 的维数 是 Ｋ 中诸单形的最大维数。 显然，每个单纯复形 Ｋ 都自然地决定一个抽象复形 Ｋ。 实际上， Ｋ 的每个 单 形 ａ０ ａ１…ａｑ ( ) 规 定 Ｋ 的 一 个 抽 象 单 形 ｃ０ ｃ１…ｃｑ ( ) 。 这样规定的 Ｋ，显然是一个抽象复形， 且称 Ｋ 为 Ｋ 的一个几何实现。 ２ 邻域同调学习算法 设 Ｇ ＝ (Ｖ(Ｇ) ，Ｅ(Ｇ) ) 是一个简单连通图。 显 然，一个简单连通图就是一个单纯复形，根据上述定 义即 可 以 看 成 是 有 限 个 单 形 的 集 合， Ｖ(Ｇ) ＝ ａ０ ，ａ１ ，…，ａα０ －１ { } 表示图 Ｇ 的 α０ 个顶点的集合也 就是图 Ｇ 中所有 ０ 维单形的集合， Ｅ(Ｇ) 表示顶点 之间的所有连接边的集合。 令 Ｘ 和 Ｆ 分别是 Ｇ 的 一个顶点子集和边子集，就以 Ｇ － Ｘ 表示 Ｇ 去掉 Ｘ 中的点及其关联边而得的图， Ｇ － Ｆ 表示 Ｇ 去掉 Ｆ 中的边而得到的图。 设 ａ 是 Ｇ 的任意一个顶点，以 Ｎ(ａ) 表示 ａ 的邻域，那么 Ｎ(Ｘ) 表示 Ｘ 中所有点 邻域的并，即 Ｎ(Ｘ) ＝∪ａ∈Ｘ Ｎ(ａ) 。 基于此，可以构造出一幅给定图形 Ｇ 的领域复 形 Ｎ(Ｇ) ， Ｎ(Ｇ) 是以 Ｇ 的顶点为顶点，以 Ｇ 中具有 公共邻接点的子集为单形的一个抽象复形。 根据抽 象复形的概念，可以看出任意的抽象复形都可以在 欧氏空间实现［２ ５ ］ 。 因此邻域复形在欧氏空间中是 有其相对应的单纯复形的，这里仍以 Ｎ(Ｇ) 记邻域 复形所对应的单纯复形。 除非特殊说明，二者不加 以区别，统称为 Ｇ 的邻域复形。 下文中的 Ｎ(Ｇ) 即 指邻域复形在欧氏空间中所对应的单纯复形。 由于构造出的任意图形的邻域复形 Ｎ(Ｇ) 可以 看成是单纯复形，那么可以将 Ｎ(Ｇ) 剖分成有限个 单 形， 根 据 定 义 ２ 可 表 示 为 Ｎ(Ｇ) ＝ Ａ ｑ ｉ ；ｑ ＝ ０，１，…，ｄｉｍ(Ｎ(Ｇ) ) ，ｉ ＝ １，２，…，αｑ { } ； 对 每个单形取定一个指向并记为 σ ｑ ｉ ，根据定义 １，每 个单形 σ ｑ ｉ 都可以根据顶点坐标线性表示出来；再由 式（１）将 ｑ 维单形线性组合就能得出 Ｎ(Ｇ) 的 ｑ 维 链，这些 ｑ 维链组成的自由交换群即为 Ｎ(Ｇ) 的 ｑ 维链群 Ｃｑ (Ｎ(Ｇ) ) 。 再通过计算同调群，就可以得 出 ２ 个图形之间的一种同调关系。 设有 ２ 个图 Ｇ 、 Ｈ ，如果 Ｎ(Ｇ) 和 Ｎ(Ｈ) 的各阶同调群分别同构，就 称 Ｇ 和 Ｈ 是邻域同调的，记为 Ｇ ≃ Ｎ Ｈ 。 ·３３８· 智 能 系 统 学 报 第 ９ 卷
第3期 赵梦梦，等：邻域同调学习算法 ·339 当然，不同类型的连通图，它们是邻域同调的充 k=n-1类。循环判断至所有样本都分类完毕： 分必要条件也是不一样的。例如，2个仙人掌图是 7)通过上述步骤可将样本分成k类，输出H= 邻域同调的，当且仅当这2个图都是二分图或都不 (H)ic 是二分图且它们的非4-圈[26]的圈数相同[27小：同样 由上面的算法可得定理1。 对于两幅立方图（每个顶点的次数都等于3的有限 定理1NHLA算法的所需时间复杂度为 简单连通图)来说，它们是邻域同调的充要条件是 0(n2),空间复杂度为0(n)。 两幅图的二分性相同且D值相同8]：而两个不含 证明假设有一任意图形G,顶点集为V(G)= 4-圈的图是邻域同调的充要条件则是它们的二分性 {ao,a1,…,aao-},根据每个顶点的邻域可以构造 相同且圈秩相同9)。 出它在欧几里德空间里的邻域复形N(G)= 基于上述理论，文中给出了一种邻域同调学习算 {A;9=0,1,…,dim(N(G)),i=1,2,…,ag}。 neighborhood homology learning algorithm,NHLA). 根据步骤2)，对于n个待测的图形样本，需构 该算法主要是针对简单联通图（不含孤立顶点的有限 造出n个邻域复形，因此本文可以得到2)的时间复 简单图)的分类，通过图形的邻域复形的同构性判断出 杂度为O(n),空间复杂度为O(n)。 图形是否是邻域同调，从而进行邻域同调分类。 根据步骤3)~5)，求出每个邻域复形相对应的 假设有一个由n幅图组成的样本集G= g维同调群，此时的时间复杂度为O(n),空间复杂 {G1,G2,…,Gn}。根据邻域复形的的概念，为每一 度为O(n)。 个G:,ie[1,n]构造出其邻域复形N(G:),并计 根据步骤6)程序主体，通过fr循环进行判断 算出N(G)的g阶同调群，其中0≤q≤ 分类直到分类完毕并最终输出分类结果，这里时间 dim(N(G:))。然后判断N(G:)和N(G)的各阶 复杂度为O(n),空间复杂度为O(n)综上可得， 同调群是否同构，进而判断出G,（i∈[1，n-1]） NHLA算法的时间复杂度为O(n2),空间复杂度为 与G(j∈[i+1,n])是否邻域同调的。最终根据 O(n)。 图之间的邻域同调性，可将图分为k类，则输出集合 可表示为H={H,H2,…,H}。具体算法步骤如 实验分析 下： 为了验证本文算法的有效性，本文进行了3组 算法邻域同调学习算法 实验。第1组实验是人工数据，第2组是手写数字 输入：待测样本集合G={G1,G2,…,Gn}。 识别实验，第3组是实物图像。在实验中，本文方法 输出：分类后的集合H={H1,H2,…,H}。 同时也和SVM、TVQ方法进行了对比。本文实验均 1)置每个样本G为一个类，则G,G2,…,Gn, 在MATLAB平台上实现。 共形成n个类； 3.1人工数据 2)找出G的任意一个顶点的邻域，那么G中 本文给出了一次随机生成的二维的连通图集数 的所有顶点邻域的并集即为所要构造的邻域复形 据，该人工数据是3类服从高斯分布的随机数据，每 N(G); 次生成数据时，每类样本是100个。其中符号 3)根据式(3)和式(4)计算出每个G邻域复形 ‘*·,‘0'和V'分别表示不同的类别，将其可视化 N(G:)的q维链群C,(N(G:)),此时可以得到形如 如图1(a)所示。图中的每个点表示每个二维图形 式(5)的一个序列： 所在的位置，是用图形的重心坐标表示的。 …→0一C,(N(G)）C,-1N(G,))→ 分类之前首先对生成图形G进行处理，即需要先 →C,W(G)C,(G)0 提取图形边缘点。将提取的边缘点用V(G)表示，这 些边缘点间的连接边用E(G)表示。接着根据邻域复 4)再由式(6)和式(7)分别可以求出邻域复形 形构造原理构造出N(G),然后再利用上述的邻域同 N(G)的q维闭链群Z,(N(G:))和q维边缘链群 调学习算法进行分类，分类结果如图1(b)所示。图1 B,(N(G:)); (c)和图1(d)分别是用SVM和TVQ算法分类后的结 5)根据H,(N(G))=Z,(N(G))/B,(N(G)) 果。图1(a)中随机生成的这几类数据有交叉重叠部 计算出N(G)的g维同调群： 分，且从图1(b)~(d)可以看出，经过NHA、SVM和 6)如果G,,i∈[1，n-1]与G,j∈ TVQ等3种算法分类后，数据都能不同程度的分开。 [i+1,】的各阶同调群分别同构，则G:二G。那 但比较分类后的3幅图可以看出，本文提出的邻域同 么就将G,与G,合并为一个新类，此时现有的类数为 调学习算法分类后的效果是明显好于另2种算法
当然，不同类型的连通图，它们是邻域同调的充 分必要条件也是不一样的。 例如，２ 个仙人掌图是 邻域同调的，当且仅当这 ２ 个图都是二分图或都不 是二分图且它们的非 ４⁃圈［２ ６ ］ 的圈数相同［２ ７ ］ ；同样 对于两幅立方图（每个顶点的次数都等于 ３ 的有限 简单连通图） 来说，它们是邻域同调的充要条件是 两幅图的二分性相同且 Ｄ 值相同［ ２８ ］ ；而两个不含 ４⁃圈的图是邻域同调的充要条件则是它们的二分性 相同且圈秩相同［ ２９ ］ 。 基于上述理论，文中给出了一种邻域同调学习算 法（ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ， ＮＨＬＡ）。 该算法主要是针对简单联通图（不含孤立顶点的有限 简单图）的分类，通过图形的邻域复形的同构性判断出 图形是否是邻域同调，从而进行邻域同调分类。 假设 有 一 个 由 ｎ 幅 图 组 成 的 样 本 集 Ｇ ＝ Ｇ１ ，Ｇ２ ，…，Ｇｎ { } 。 根据邻域复形的的概念，为每一 个 Ｇｉ ， ｉ ∈ [１，ｎ] 构造出其邻域复形 Ｎ Ｇｉ ( ) ，并计 算出 Ｎ Ｇｉ ( ) 的 ｑ 阶 同 调 群， 其 中 ０ ≤ ｑ ≤ ｄｉｍ Ｎ Ｇｉ ( ( ) ) 。 然后判断 Ｎ Ｇｉ ( ) 和 Ｎ Ｇｊ ( ) 的各阶 同调群是否同构，进而判断出 Ｇｉ （ ｉ ∈ [１，ｎ － １] ） 与 Ｇｊ （ ｊ ∈ [ｉ ＋ １，ｎ] ）是否邻域同调的。 最终根据 图之间的邻域同调性，可将图分为 ｋ 类，则输出集合 可表示为 Ｈ ＝ Ｈ１ ，Ｈ２ ，…，Ｈｋ { } 。 具体算法步骤如 下： 算法 邻域同调学习算法 输入：待测样本集合 Ｇ ＝ Ｇ１ ，Ｇ２ ，…，Ｇｎ { } 。 输出：分类后的集合 Ｈ ＝ Ｈ１ ，Ｈ２ ，…，Ｈｋ { } 。 １） 置每个样本 Ｇｉ 为一个类，则 Ｇ１ ，Ｇ２ ，…，Ｇｎ ， 共形成 ｎ 个类； ２） 找出 Ｇｉ 的任意一个顶点的邻域，那么 Ｇｉ 中 的所有顶点邻域的并集即为所要构造的邻域复形 Ｎ Ｇｉ ( ) ； ３） 根据式（３）和式（４）计算出每个 Ｇｉ 邻域复形 Ｎ Ｇｉ ( ) 的 ｑ 维链群 Ｃｑ Ｎ Ｇｉ ( ( ) ) ，此时可以得到形如 式（５）的一个序列： … → ０ → Ｃｑ Ｎ Ｇｉ ( ( ) ) ∂ｑ→ Ｃｑ－１ Ｎ Ｇｉ ( ( ) ) → … → Ｃ１ Ｎ Ｇｉ ( ( ) ) ∂１→ Ｃ０ Ｎ Ｇｉ ( ( ) ) ∂０→ ０ ４） 再由式（６）和式（７）分别可以求出邻域复形 Ｎ Ｇｉ ( ) 的 ｑ 维闭链群 Ｚｑ Ｎ Ｇｉ ( ( ) ) 和 ｑ 维边缘链群 Ｂｑ Ｎ Ｇｉ ( ( ) ) ； ５） 根据 Ｈｑ Ｎ Ｇｉ ( ( ) ) ＝ Ｚｑ Ｎ Ｇｉ ( ( ) ) ／ Ｂｑ Ｎ Ｇｉ ( ( ) ) 计算出 Ｎ Ｇｉ ( ) 的 ｑ 维同调群； ６） 如 果 Ｇｉ ， ｉ ∈ [１，ｎ － １] 与 Ｇｊ ， ｊ ∈ [ｉ ＋ １，ｎ] 的各阶同调群分别同构，则 Ｇｉ ≃ Ｎ Ｇｊ 。 那 么就将 Ｇｉ 与 Ｇｊ 合并为一个新类，此时现有的类数为 ｋ ＝ ｎ － １ 类。 循环判断至所有样本都分类完毕； ７） 通过上述步骤可将样本分成 ｋ 类，输出 Ｈ ＝ Ｈｉ { } ｋ ｉ ＝ １ 。 由上面的算法可得定理 １。 定理 １ ＮＨＬＡ 算 法 的 所 需 时 间 复 杂 度 为 Ο ｎ ２ ( ) ，空间复杂度为 Ο(ｎ) 。 证明 假设有一任意图形 Ｇ ，顶点集为 Ｖ(Ｇ) ＝ ａ０ ，ａ１ ，…，ａα０ －１ { } ，根据每个顶点的邻域可以构造 出它 在 欧 几 里 德 空 间 里 的 邻 域 复 形 Ｎ(Ｇ) ＝ Ａ ｑ ｉ ；ｑ ＝ ０，１，…，ｄｉｍ(Ｎ(Ｇ) ) ，ｉ ＝ １，２，…，αｑ { } 。 根据步骤 ２），对于 ｎ 个待测的图形样本，需构 造出 ｎ 个邻域复形，因此本文可以得到 ２）的时间复 杂度为 Ο(ｎ) ，空间复杂度为 Ο(ｎ) 。 根据步骤 ３） ～５），求出每个邻域复形相对应的 ｑ 维同调群，此时的时间复杂度为 Ο(ｎ) ， 空间复杂 度为 Ο(ｎ) 。 根据步骤 ６）程序主体，通过 ｆｏｒ 循环进行判断 分类直到分类完毕并最终输出分类结果，这里时间 复杂度为 Ο ｎ ２ ( ) ， 空间复杂度为 Ο(ｎ) 综上可得， ＮＨＬＡ 算法的时间复杂度为 Ο ｎ ２ ( ) ， 空间复杂度为 Ο(ｎ) 。 ３ 实验分析 为了验证本文算法的有效性，本文进行了 ３ 组 实验。 第 １ 组实验是人工数据，第 ２ 组是手写数字 识别实验，第 ３ 组是实物图像。 在实验中，本文方法 同时也和 ＳＶＭ、ＴＶＱ 方法进行了对比。 本文实验均 在 ＭＡＴＬＡＢ 平台上实现。 ３．１ 人工数据 本文给出了一次随机生成的二维的连通图集数 据，该人工数据是 ３ 类服从高斯分布的随机数据，每 次生 成 数 据 时， 每 类 样 本 是 １００ 个。 其 中 符 号 ‘∗’，‘ｏ’和‘ Ñ’分别表示不同的类别，将其可视化 如图 １（ａ）所示。 图中的每个点表示每个二维图形 所在的位置，是用图形的重心坐标表示的。 分类之前首先对生成图形 Ｇ 进行处理，即需要先 提取图形边缘点。 将提取的边缘点用 Ｖ(Ｇ) 表示，这 些边缘点间的连接边用 Ｅ(Ｇ) 表示。 接着根据邻域复 形构造原理构造出 Ｎ(Ｇ) ， 然后再利用上述的邻域同 调学习算法进行分类，分类结果如图 １（ｂ）所示。 图 １ （ｃ）和图 １（ｄ）分别是用 ＳＶＭ 和 ＴＶＱ 算法分类后的结 果。 图 １（ａ）中随机生成的这几类数据有交叉重叠部 分，且从图 １（ｂ） ～ （ｄ）可以看出，经过 ＮＨＬＡ、ＳＶＭ 和 ＴＶＱ 等 ３ 种算法分类后，数据都能不同程度的分开。 但比较分类后的 ３ 幅图可以看出，本文提出的邻域同 调学习算法分类后的效果是明显好于另 ２ 种算法。 第 ３ 期 赵梦梦，等：邻域同调学习算法 ·３３９·
·340· 智能系统学报 第9卷 0.6 3.2手写数字识别实验 0.5 本实验采用USPS_ALL数据库的手写数字集进 0.4 行实验。此手写数字集包含10个数字(0,1，…，9) 0.3 的图片，每个数字含有1100张字迹不同的图片，每 0.21 96 张图片的像素大小为16×16。部分图像如图2。 68 0.1 0 -0.1 图2USPS_ALL数据库部分图像实例 0. 6.20-0.15-0.10-0.0500.050.100.15 Fig.2 Part of the images in USPS_ALL 实验中，从每类数字中选取一定数量的图像构 (a)原始数据 成样本集。样本集大小从1500变化到4500。为 0.6 消除选择样本的随机独立性，独立重复实验100次， 0.5 最后取平均识别率作为最终识别率。图3给出了几 0.4 种算法在数字手写数据集上不同样本点个数情况下 0.3 070 0 00 的实验结果。分类前对图像的边缘处理和人工数据 0.2 81 实验是相同的。图3中，随着选取样本个数的增加， 0.1h 各个方法的识别精度也是随之增加的，而且本文提 出的邻域同调算法始终是好于SVM和TVQ的。 -0.1 0.93 -0.10 -0.05 0 0.05 0.10 0.92 0.91 (b)NHLA 0.6 部0.9 虽0.89 0.4 0.88 0.3 00 0.87 二VR 0.2 .0o2品号哈96 0 8 0 0.86 NHLA 0.1 bcg0, 0.8 10 0 15 20 25 3035 40 45 -0.1 样本个数 -0.2 图3手写数字集上的识别率 0.3 0.4-0.3-0.2-0.10 0.10.20.3 Fig.3 Recognition accuracy on the USPS ALL database 3.3实物图像 (c)SVM 采用MPEG7CE-Shapel Part B图像库对实物 0.15 图像进行分类。该图像库是一个图像模版库，包含 0 0.10 了各种形状特征的物体模版图，由70类物体、每类 6,0 000 0.05 0 20幅共1400幅实物图像组成。部分图像如图4。 0 0 -0.05 -0.10 .088 *080 (a)Bird-15 (b)Bird-16 (c)Bird-17 (d)Bird-16 (e)Bird-16 d◆ dp -0.15 -0.20 -0.10-0.0500.05 0.100.15 (f)Bone-4 (g)Bone-5 (h)Bone-6 (i)Bone-7 (j)Bone-8 (d)TVQ 图4部分实物图像 图1随机数据和可视化结果 Fig.4 Part of the images in MPEG7 CE Fig.1 Random data and the result of visualization 本文在MPEG7CE-Shapel Part B图像库中选
（ａ） 原始数据 （ｂ）ＮＨＬＡ （ｃ） ＳＶＭ （ｄ） ＴＶＱ 图 １ 随机数据和可视化结果 Ｆｉｇ．１ Ｒａｎｄｏｍ ｄａｔａ ａｎｄ ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｖｉｓｕａｌｉｚａｔｉｏｎ ３．２ 手写数字识别实验 本实验采用 ＵＳＰＳ＿ＡＬＬ 数据库的手写数字集进 行实验。 此手写数字集包含 １０ 个数字（０，１，…，９） 的图片，每个数字含有 １ １００ 张字迹不同的图片，每 张图片的像素大小为 １６×１６。 部分图像如图 ２。 图 ２ ＵＳＰＳ＿ＡＬＬ 数据库部分图像实例 Ｆｉｇ．２ Ｐａｒｔ ｏｆ ｔｈｅ ｉｍａｇｅｓ ｉｎ ＵＳＰＳ＿ＡＬＬ 实验中，从每类数字中选取一定数量的图像构 成样本集。 样本集大小从 １ ５００ 变化到 ４ ５００。 为 消除选择样本的随机独立性，独立重复实验 １００ 次， 最后取平均识别率作为最终识别率。 图 ３ 给出了几 种算法在数字手写数据集上不同样本点个数情况下 的实验结果。 分类前对图像的边缘处理和人工数据 实验是相同的。 图 ３ 中，随着选取样本个数的增加， 各个方法的识别精度也是随之增加的，而且本文提 出的邻域同调算法始终是好于 ＳＶＭ 和 ＴＶＱ 的。 图 ３ 手写数字集上的识别率 Ｆｉｇ．３ Ｒｅｃｏｇｎｉｔｉｏｎ ａｃｃｕｒａｃｙ ｏｎ ｔｈｅ ＵＳＰＳ＿ＡＬＬ ｄａｔａｂａｓｅ ３．３ 实物图像 采用 ＭＰＥＧ７ ＣＥ⁃Ｓｈａｐｅ１ Ｐａｒｔ Ｂ 图像库对实物 图像进行分类。 该图像库是一个图像模版库，包含 了各种形状特征的物体模版图，由 ７０ 类物体、每类 ２０ 幅共 １ ４００ 幅实物图像组成。 部分图像如图 ４。 图 ４ 部分实物图像 Ｆｉｇ．４ Ｐａｒｔ ｏｆ ｔｈｅ ｉｍａｇｅｓ ｉｎ ＭＰＥＧ７ ＣＥ 本文在 ＭＰＥＧ７ ＣＥ⁃Ｓｈａｐｅ１ Ｐａｒｔ Ｂ 图像库中选 ·３４０· 智 能 系 统 学 报 第 ９ 卷
第3期 赵梦梦，等：邻域同调学习算法 ·341· 取其中16类，即共320幅图像进行实验。从每类中 [3]PERNKOPF F,WOHLMAYR M,TSCHIATSCHEK S. 选取一定数量的图像构成样本集。其中样本集的大 Maximum margin Bayesian network classifiers[J].Pattern 小从80变化到320。为了消除选择样本的随机独 Analysis and Machine Intelligence,2012,34(3):521- 立性，独立重复实验100次，最后取平均识别率作为 532. 最终识别率。图5给出了在MPEG7CE-Shapel Part [4]PANWAR H,GUPTA S.Advances in Computer Science, Engineering and Applications[M].Berlin:Springer,2012: B图像库上，几种算法在选取不同样本点个数情况 385-392. 下的实验结果。 [5]EIDELMAN V.Optimization strategies for online large-mar- 从图5中可以看出，选取的样本个数越多，各个 gin learning in machine translation[C]//Proceedings of the 方法的识别精度整体趋势也是随之增加。此外在样 7th Workshop on Statistical Machine Translation,Montreal, 本较少的情况下，由于部分图像受到噪声的干扰，本 Canada,2012:480-489. 文提出的NHLA算法识别率受到一定的影响，其识 [6]VAPNIK V.Statistical learning theory M].New York:Wi- 别效果不稳定，有一点降低的趋势。但是与其他算 1ey,1998:1-768. 法相比较，NHLA依然具有较好的识别精度。而且 [7]LEE Y J,HSIEH W F,HUANG C F.e-SSVR:A smooth 随着样本的增多，识别率受噪声干扰的程度也减小， support vector machine for e-insensitive regression[J]. 仍是处于增长趋势的。 IEEE Transactions on Knowledge and data Engineering, 2005,17(5):678-685. 0.95m [8]LIN C F,WANG S D.Fuzzy support vector machines[J]. 0.90 IEEE Transactions on Neural Networks,2002,13 (3): 0.85 466-471. 0.80 证0.75 [9]FABIO A,ALESSANDRO S.A re-weighting strategy for im- 30.70f proving margins [J].Artificial Intelligence,2002,137: 0.65 197-216. 0.60 土品 [10]鲜敏，李凡长.一种同调边缘学习算法[J]计算机工程 0.55 与应用，2008,44(21)：192-194. 0.50l 80 XIAN Min,LI Fanzhang.Learning algorithm based on ho- 120 160200240280320 样本个数 mology margin[J].Computer Engineering and Applica- 图5MPEG7CE上3种算法的识别率 tions,2008,44(21):192-194. Fig.5 Recognition accuracy on the MPEG7 CE database [11]杨季文，李哲硕，何书萍，等.胞腔同调边缘学习算法研 究[J].计算机研究与发展，2013,50(5)：1005-1011. 4 结束语 YANG Jiwen,LI Zheshuo,HE Shuping et al.On celluar ho- mology margin learning algorithms[J].Computer Research 针对边缘可变的划分问题，本文提出了邻域同 and Development,2013,50(5):1005-1011 调学习算法，该算法引进了同调理论，利用复形之间 [12]邓乃杨，田英杰数据挖掘中的新方法一支持向量机 的性质，通过构造图形的邻域复形，并判断这些邻域 「M1.北京：科学出版社，2005：1.408. 复形是否同构来进行对图集的邻域同调分类。利用 [13]BURGES C J C.A tutorial on support vector machines for 该算法进行分类能够有效地保证在分类过程保持图 pattern recognition[J].Data Mining and Knowledge Dis- 形原有的结构特征不变。 covery,1998,2(2):121-167. 通过实验对比可以看出，本文提出的算法的识 [14]SHAWE-TAYLOR J,CRISTININI N.Kernel methods for 别率较高，具有一定的优势。但是，本文的算法目前 pattern analysis[M].Cambridge University Press,2004: 289-436. 只实验于二维图像上，对于更高维的图像分类还有 [15]CORTES C,VAPNIK V.Support-vector networks[J].Ma- 待完善，另外本算法对噪声和扰动的鲁棒性也有待 chine Learning,1995,20(3):273-297. 提高。总之，邻域同调学习算法具有比较坚实的理 [16]SIMARD P Y,LECUN Y,DENKER J.Efficient pattern 论基础，是一种可持续发展的学习方法。 recognition using a new transformation distance[J].Ad- 参考文献： vanced in Neural Information Processing System,1993,5: 50-58. [1]周志华，王珏.机器学习及其应用研究[M].北京：清华大 [17]SCHAPIRE R E,SINGER Y.Improved boosting algo- 学出版社，2007：1-161. rithms using confidence-rated predictions[J].Machine [2]李凡长，张莉，杨季文李群机器学习[M]合肥：中国科 Learning,1999,37(3):297-336. 学技术大学出版社，2013：281-296. [18]DUFFY N,HELMBOLD D.Boosting methods for regres-
取其中 １６ 类，即共 ３２０ 幅图像进行实验。 从每类中 选取一定数量的图像构成样本集。 其中样本集的大 小从 ８０ 变化到 ３２０。 为了消除选择样本的随机独 立性，独立重复实验 １００ 次，最后取平均识别率作为 最终识别率。 图 ５ 给出了在 ＭＰＥＧ７ ＣＥ⁃Ｓｈａｐｅ１ Ｐａｒｔ Ｂ 图像库上，几种算法在选取不同样本点个数情况 下的实验结果。 从图 ５ 中可以看出，选取的样本个数越多，各个 方法的识别精度整体趋势也是随之增加。 此外在样 本较少的情况下，由于部分图像受到噪声的干扰，本 文提出的 ＮＨＬＡ 算法识别率受到一定的影响，其识 别效果不稳定，有一点降低的趋势。 但是与其他算 法相比较，ＮＨＬＡ 依然具有较好的识别精度。 而且 随着样本的增多，识别率受噪声干扰的程度也减小， 仍是处于增长趋势的。 图 ５ ＭＰＥＧ７ ＣＥ 上 ３ 种算法的识别率 Ｆｉｇ．５ Ｒｅｃｏｇｎｉｔｉｏｎ ａｃｃｕｒａｃｙ ｏｎ ｔｈｅ ＭＰＥＧ７ ＣＥ ｄａｔａｂａｓｅ ４ 结束语 针对边缘可变的划分问题，本文提出了邻域同 调学习算法，该算法引进了同调理论，利用复形之间 的性质，通过构造图形的邻域复形，并判断这些邻域 复形是否同构来进行对图集的邻域同调分类。 利用 该算法进行分类能够有效地保证在分类过程保持图 形原有的结构特征不变。 通过实验对比可以看出，本文提出的算法的识 别率较高，具有一定的优势。 但是，本文的算法目前 只实验于二维图像上，对于更高维的图像分类还有 待完善，另外本算法对噪声和扰动的鲁棒性也有待 提高。 总之，邻域同调学习算法具有比较坚实的理 论基础，是一种可持续发展的学习方法。 参考文献： ［１］周志华，王珏．机器学习及其应用研究［Ｍ］．北京：清华大 学出版社， ２００７： １⁃１６１． ［２］李凡长，张莉，杨季文．李群机器学习［Ｍ］．合肥：中国科 学技术大学出版社， ２０１３： ２８１⁃２９６． ［３ ］ ＰＥＲＮＫＯＰＦ Ｆ， ＷＯＨＬＭＡＹＲ Ｍ， ＴＳＣＨＩＡＴＳＣＨＥＫ Ｓ． Ｍａｘｉｍｕｍ ｍａｒｇｉｎ Ｂａｙｅｓｉａｎ ｎｅｔｗｏｒｋ ｃｌａｓｓｉｆｉｅｒｓ［ Ｊ］． Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１２， ３４ （ ３）： ５２１⁃ ５３２． ［４］ ＰＡＮＷＡＲ Ｈ， ＧＵＰＴＡ Ｓ． Ａｄｖａｎｃｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］． Ｂｅｒｌｉｎ： Ｓｐｒｉｎｇｅｒ， ２０１２： ３８５⁃３９２． ［５］ＥＩＤＥＬＭＡＮ Ｖ． Ｏｐｔｉｍｉｚａｔｉｏｎ ｓｔｒａｔｅｇｉｅｓ ｆｏｒ ｏｎｌｉｎｅ ｌａｒｇｅ⁃ｍａｒ⁃ ｇｉｎ ｌｅａｒｎｉｎｇ ｉｎ ｍａｃｈｉｎｅ ｔｒａｎｓｌａｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ７ｔｈ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｔａｔｉｓｔｉｃａｌ Ｍａｃｈｉｎｅ Ｔｒａｎｓｌａｔｉｏｎ，Ｍｏｎｔｒｅａｌ， Ｃａｎａｄａ， ２０１２： ４８０⁃４８９． ［６］ＶＡＰＮＩＫ Ｖ． Ｓｔａｔｉｓｔｉｃａｌ ｌｅａｒｎｉｎｇ ｔｈｅｏｒｙ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｗｉ⁃ ｌｅｙ， １９９８： １⁃７６８． ［７］ ＬＥＥ Ｙ Ｊ，ＨＳＩＥＨ Ｗ Ｆ， ＨＵＡＮＧ Ｃ Ｆ． ｅ⁃ＳＳＶＲ：Ａ ｓｍｏｏｔｈ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｆｏｒ ｅ⁃ｉｎｓｅｎｓｉｔｉｖｅ ｒｅｇｒｅｓｓｉｏｎ ［ Ｊ ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００５， １７（５）： ６７８⁃６８５． ［８］ＬＩＮ Ｃ Ｆ， ＷＡＮＧ Ｓ Ｄ． Ｆｕｚｚｙ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ， ２００２， １３ （ ３ ）： ４６６⁃４７１． ［９］ＦＡＢＩＯ Ａ， ＡＬＥＳＳＡＮＤＲＯ Ｓ． Ａ ｒｅ⁃ｗｅｉｇｈｔｉｎｇ ｓｔｒａｔｅｇｙ ｆｏｒ ｉｍ⁃ ｐｒｏｖｉｎｇ ｍａｒｇｉｎｓ ［ Ｊ ］． Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００２， １３７： １９７⁃２１６． ［１０］鲜敏，李凡长．一种同调边缘学习算法［ Ｊ］．计算机工程 与应用， ２００８， ４４（２１）： １９２⁃１９４． ＸＩＡＮ Ｍｉｎ，ＬＩ Ｆａｎｚｈａｎｇ． Ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｈｏ⁃ ｍｏｌｏｇｙ ｍａｒｇｉｎ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａ⁃ ｔｉｏｎｓ， ２００８， ４４（２１）： １９２⁃１９４． ［１１］杨季文，李哲硕，何书萍，等．胞腔同调边缘学习算法研 究［Ｊ］．计算机研究与发展， ２０１３， ５０（５）： １００５⁃１０１１． ＹＡＮＧ Ｊｉｗｅｎ，ＬＩ Ｚｈｅｓｈｕｏ，ＨＥ Ｓｈｕｐｉｎｇ ｅｔ ａｌ．Ｏｎ ｃｅｌｌｕａｒ ｈｏ⁃ ｍｏｌｏｇｙ ｍａｒｇｉｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ［ Ｊ］．Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２０１３， ５０（５）： １００５⁃１０１１． ［１２］邓乃杨，田英杰．数据挖掘中的新方法———支持向量机 ［Ｍ］．北京：科学出版社， ２００５： １⁃４０８． ［１３］ＢＵＲＧＥＳ Ｃ Ｊ Ｃ． Ａ ｔｕｔｏｒｉａｌ ｏｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ ｆｏｒ ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ［ Ｊ］． Ｄａｔａ Ｍｉｎｉｎｇ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓ⁃ ｃｏｖｅｒｙ， １９９８， ２（２）： １２１⁃１６７． ［１４］ ＳＨＡＷＥ⁃ＴＡＹＬＯＲ Ｊ， ＣＲＩＳＴＩＮＩＮＩ Ｎ． Ｋｅｒｎｅｌ ｍｅｔｈｏｄｓ ｆｏｒ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ［Ｍ］． Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ， ２００４： ２８９⁃４３６． ［１５］ＣＯＲＴＥＳ Ｃ，ＶＡＰＮＩＫ Ｖ． Ｓｕｐｐｏｒｔ⁃ｖｅｃｔｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｍａ⁃ ｃｈｉｎｅ Ｌｅａｒｎｉｎｇ， １９９５， ２０（３）： ２７３⁃２９７． ［１６］ ＳＩＭＡＲＤ Ｐ Ｙ， ＬＥＣＵＮ Ｙ， ＤＥＮＫＥＲ Ｊ． Ｅｆｆｉｃｉｅｎｔ ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ ｕｓｉｎｇ ａ ｎｅｗ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｄｉｓｔａｎｃｅ ［ Ｊ］． Ａｄ⁃ ｖａｎｃｅｄ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍ， １９９３， ５： ５０⁃５８． ［ １７］ ＳＣＨＡＰＩＲＥ Ｒ Ｅ， ＳＩＮＧＥＲ Ｙ． Ｉｍｐｒｏｖｅｄ ｂｏｏｓｔｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍｓ ｕｓｉｎｇ ｃｏｎｆｉｄｅｎｃｅ⁃ｒａｔｅｄ ｐｒｅｄｉｃｔｉｏｎｓ ［ Ｊ ］． Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ， １９９９， ３７（３）： ２９７⁃３３６． ［１８］ＤＵＦＦＹ Ｎ， ＨＥＬＭＢＯＬＤ Ｄ． Ｂｏｏｓｔｉｎｇ ｍｅｔｈｏｄｓ ｆｏｒ ｒｅｇｒｅｓ⁃ 第 ３ 期 赵梦梦，等：邻域同调学习算法 ·３４１·
.342. 智能系统学报 第9卷 sion[J].Machine Learning,2002,47(2/3):153-200. [28]薛秀谦.立方图的邻域同调分类[J].中国矿业大学学 [19]南基诛，王颖同调代数导论[M].大连：大连理工大学 报，1995,24(4)：110-112. 出版社，2011：112-222. XUE Xiugian.The neighborhood homology classification of [20]姜伯驹.同调论[M].北京：北京大学出版社，2006：1- cubic graphs[J].Journal of China University of Mining 90. and Technology,1995,24(4):110-112. [21]江泽涵.拓扑学引论[M].上海：上海科学技术出版社， [29]薛秀谦无C:图的邻域同调分类[J]系统科学与数学， 1978:25-169. 1998,18(1):101-103. [22]孟道骥，白承铭.李群[M].北京：科学出版社，2003：28- XUE Xiugian.The neighborhood homology classification of 92 the Cafree graphs[J].Systems Science and Mathematics, [23]黄保军同调与同伦原理[M].合肥：中国科学技术出版 1998,18(1):101-103. 社.2005：16-59. 作者简介： [24]沈信耀同调论一代数拓扑学之一[M].北京：科学出 赵梦梦，女，1991年生，硕士研究 版社，2002：19-132. 生，主要研究方向为机器学习。 [25]谢力同.组合拓扑方法在图论和拟阵理论中的应用[J]. 数学进展，1983,12(3)：1-5. XIE Litong.Applications of combinatorial topology method in graph theory and matroid theory[J].Advances in Math- ematics,1983,12(3):1-5. [26]方冬云.不包含4,8,9-圈平面图结构的性质[J]长春 李凡长，男，1964年生，教授，博士 工业大学学报，2011,32(5)：485-488. 生导师，中国人工智能学会理事，中国 FANG Dongyun.Nature of stucture planar graph without 人工智能学会的机器学习专委会常务 14,8,9-cycles[J].Journal of Changchun University of 委员，机器感知与虚拟现实专委会委 Technology,2011,32(5):485-488. 员，智能系统工程专委会委员，粗糙集 [27]薛秀谦仙人掌图的邻域同调分类[J].山东大学学报， 与软计算专委会常委，中国计算机学会 1994,29(1):13-17. 高级会员，中国计算机学会的理论计算机科学专委会委员， XUE Xiuqian.The neighborhood homology classification of 人工智能与模式识别专委会委员。主要研究方向是动态模 cactus[J].Journal of Shandong University,1994,29(1): 糊逻辑和李群机器学习等，先后承担国家自然科学基金重 13-17. 点、面上及省级项目8项，获省级科技奖2项，发表学术论文 150余篇，出版专著7部。 2014IEEE模糊系统国际会议 2014 IEEE International Conference on Fuzzy Systems The IEEE World Congress on Computational Intelligence (IEEE WCCI)is the largest technical event in the field of com- putational intelligence.IEEE WCCI 2014 will host three conferences:The 2014 International Joint Conference on Neural Networks IJCNN 2014),the 2014 IEEE International Conference on Fuzzy Systems FUZZ-IEEE 2014),and the 2014 IEEE Congress on Evolutionary Computation (IEEE CEC 2014).IEEE WCCI 2014 will engage in cross-fertilization among the three big areas and provide a stimulating forum for scientists,engineers,educators,and students from all over the world to discuss and present their research findings on computational intelligence. IEEE WCCI 2014 will be held in Beijing,the capital of the People's Republic of China.Beijing is the nation's political, economic,and cultural center as well as China's most important center for international trade and communications.With the biggest central square in the world-Tiananmen Square,the Forbidden City-the largest and best-preserved imperial palace complex,a superbly preserved section of the Great Wall,as well as the largest sacrificial complex in the world-the Temple of Heaven,Beijing attracts both domestic and foreign visitors who all come to wonder at its long history and unique cultural relics. Contact Us E-mail:wcci2014@gmail.com Website:http://www.ieee-wcci2014.org/
ｓｉｏｎ［Ｊ］． Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ， ２００２， ４７（２ ／ ３）： １５３⁃２００． ［１９］南基洙，王颖．同调代数导论［Ｍ］．大连：大连理工大学 出版社， ２０１１： １１２⁃２２２． ［２０］姜伯驹．同调论［Ｍ］．北京：北京大学出版社， ２００６： １⁃ ９０． ［２１］江泽涵．拓扑学引论［Ｍ］．上海：上海科学技术出版社， １９７８： ２５⁃１６９． ［２２］孟道骥，白承铭．李群［Ｍ］．北京：科学出版社， ２００３： ２８⁃ ９２． ［２３］黄保军．同调与同伦原理［Ｍ］．合肥：中国科学技术出版 社， ２００５： １６⁃５９． ［２４］沈信耀．同调论———代数拓扑学之一［Ｍ］．北京：科学出 版社， ２００２： １９⁃１３２． ［２５］谢力同．组合拓扑方法在图论和拟阵理论中的应用［ Ｊ］． 数学进展， １９８３， １２（３）：１⁃５． ＸＩＥ Ｌｉｔｏｎｇ．Ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｃｏｍｂｉｎａｔｏｒｉａｌ ｔｏｐｏｌｏｇｙ ｍｅｔｈｏｄ ｉｎ ｇｒａｐｈ ｔｈｅｏｒｙ ａｎｄ ｍａｔｒｏｉｄ ｔｈｅｏｒｙ［Ｊ］． Ａｄｖａｎｃｅｓ ｉｎ Ｍａｔｈ⁃ ｅｍａｔｉｃｓ， １９８３， １２（３）： １⁃５． ［２６］方冬云．不包含｛４，８，９｝⁃圈平面图结构的性质［ Ｊ］．长春 工业大学学报， ２０１１， ３２（５）： ４８５⁃４８８． ＦＡＮＧ Ｄｏｎｇｙｕｎ． Ｎａｔｕｒｅ ｏｆ ｓｔｕｃｔｕｒｅ ｐｌａｎａｒ ｇｒａｐｈ ｗｉｔｈｏｕｔ ｛４，８，９｝⁃ｃｙｃｌｅｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈａｎｇｃｈｕｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， ２０１１， ３２（５）： ４８５⁃４８８． ［２７］薛秀谦．仙人掌图的邻域同调分类［ Ｊ］．山东大学学报， １９９４， ２９（１）： １３⁃１７． ＸＵＥ Ｘｉｕｑｉａｎ．Ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｏｆ ｃａｃｔｕｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｎｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ， １９９４， ２９（１）： １３⁃１７． ［２８］薛秀谦．立方图的邻域同调分类［ Ｊ］．中国矿业大学学 报， １９９５， ２４（４）： １１０⁃１１２． ＸＵＥ Ｘｉｕｑｉａｎ．Ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｏｆ ｃｕｂｉｃ ｇｒａｐｈｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍｉｎｉｎｇ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， １９９５， ２４（４）： １１０⁃１１２． ［２９］薛秀谦．无 Ｃ４ 图的邻域同调分类［ Ｊ］．系统科学与数学， １９９８， １８（１）： １０１⁃１０３． ＸＵＥ Ｘｉｕｑｉａｎ．Ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｏｆ ｔｈｅ Ｃ４ ｆｒｅｅ ｇｒａｐｈｓ［ Ｊ］． Ｓｙｓｔｅｍｓ Ｓｃｉｅｎｃｅ ａｎｄ Ｍａｔｈｅｍａｔｉｃｓ， １９９８， １８（１）： １０１⁃１０３． 作者简介： 赵梦梦，女，１９９１ 年生，硕士研究 生，主要研究方向为机器学习。 李凡长，男，１９６４ 年生， 教授，博士 生导师，中国人工智能学会理事，中国 人工智能学会的机器学习专委会常务 委员，机器感知与虚拟现实专委会委 员，智能系统工程专委会委员，粗糙集 与软计算专委会常委，中国计算机学会 高级会员，中国计算机学会的理论计算机科学专委会委员， 人工智能与模式识别专委会委员。 主要研究方向是动态模 糊逻辑和李群机器学习等，先后承担国家自然科学基金重 点、面上及省级项目 ８ 项，获省级科技奖 ２ 项，发表学术论文 １５０ 余篇，出版专著 ７ 部。 ２０１４ ＩＥＥＥ 模糊系统国际会议 ２０１４ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ Ｔｈｅ ＩＥＥＥ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ （ＩＥＥＥ ＷＣＣＩ） ｉｓ ｔｈｅ ｌａｒｇｅｓｔ ｔｅｃｈｎｉｃａｌ ｅｖｅｎｔ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ｃｏｍ⁃ ｐｕｔａｔｉｏｎａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ． ＩＥＥＥ ＷＣＣＩ ２０１４ ｗｉｌｌ ｈｏｓｔ ｔｈｒｅｅ ｃｏｎｆｅｒｅｎｃｅｓ： Ｔｈｅ ２０１４ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ （ＩＪＣＮＮ ２０１４）， ｔｈｅ ２０１４ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ （ＦＵＺＺ⁃ＩＥＥＥ ２０１４）， ａｎｄ ｔｈｅ ２０１４ ＩＥＥＥ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ （ＩＥＥＥ ＣＥＣ ２０１４）． ＩＥＥＥ ＷＣＣＩ ２０１４ ｗｉｌｌ ｅｎｇａｇｅ ｉｎ ｃｒｏｓｓ⁃ｆｅｒｔｉｌｉｚａｔｉｏｎ ａｍｏｎｇ ｔｈｅ ｔｈｒｅｅ ｂｉｇ ａｒｅａｓ ａｎｄ ｐｒｏｖｉｄｅ ａ ｓｔｉｍｕｌａｔｉｎｇ ｆｏｒｕｍ ｆｏｒ ｓｃｉｅｎｔｉｓｔｓ， ｅｎｇｉｎｅｅｒｓ， ｅｄｕｃａｔｏｒｓ， ａｎｄ ｓｔｕｄｅｎｔｓ ｆｒｏｍ ａｌｌ ｏｖｅｒ ｔｈｅ ｗｏｒｌｄ ｔｏ ｄｉｓｃｕｓｓ ａｎｄ ｐｒｅｓｅｎｔ ｔｈｅｉｒ ｒｅｓｅａｒｃｈ ｆｉｎｄｉｎｇｓ ｏｎ ｃｏｍｐｕｔａｔｉｏｎａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ． ＩＥＥＥ ＷＣＣＩ ２０１４ ｗｉｌｌ ｂｅ ｈｅｌｄ ｉｎ Ｂｅｉｊｉｎｇ， ｔｈｅ ｃａｐｉｔａｌ ｏｆ ｔｈｅ Ｐｅｏｐｌｅ′ｓ Ｒｅｐｕｂｌｉｃ ｏｆ Ｃｈｉｎａ． Ｂｅｉｊｉｎｇ ｉｓ ｔｈｅ ｎａｔｉｏｎ＇ｓ ｐｏｌｉｔｉｃａｌ， ｅｃｏｎｏｍｉｃ， ａｎｄ ｃｕｌｔｕｒａｌ ｃｅｎｔｅｒ ａｓ ｗｅｌｌ ａｓ Ｃｈｉｎａ＇ｓ ｍｏｓｔ ｉｍｐｏｒｔａｎｔ ｃｅｎｔｅｒ ｆｏｒ ｉｎｔｅｒｎａｔｉｏｎａｌ ｔｒａｄｅ ａｎｄ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ． Ｗｉｔｈ ｔｈｅ ｂｉｇｇｅｓｔ ｃｅｎｔｒａｌ ｓｑｕａｒｅ ｉｎ ｔｈｅ ｗｏｒｌｄ ⁃ Ｔｉａｎａｎｍｅｎ Ｓｑｕａｒｅ， ｔｈｅ Ｆｏｒｂｉｄｄｅｎ Ｃｉｔｙ ⁃ ｔｈｅ ｌａｒｇｅｓｔ ａｎｄ ｂｅｓｔ⁃ｐｒｅｓｅｒｖｅｄ ｉｍｐｅｒｉａｌ ｐａｌａｃｅ ｃｏｍｐｌｅｘ， ａ ｓｕｐｅｒｂｌｙ ｐｒｅｓｅｒｖｅｄ ｓｅｃｔｉｏｎ ｏｆ ｔｈｅ Ｇｒｅａｔ Ｗａｌｌ， ａｓ ｗｅｌｌ ａｓ ｔｈｅ ｌａｒｇｅｓｔ ｓａｃｒｉｆｉｃｉａｌ ｃｏｍｐｌｅｘ ｉｎ ｔｈｅ ｗｏｒｌｄ ⁃ ｔｈｅ Ｔｅｍｐｌｅ ｏｆ Ｈｅａｖｅｎ， Ｂｅｉｊｉｎｇ ａｔｔｒａｃｔｓ ｂｏｔｈ ｄｏｍｅｓｔｉｃ ａｎｄ ｆｏｒｅｉｇｎ ｖｉｓｉｔｏｒｓ ｗｈｏ ａｌｌ ｃｏｍｅ ｔｏ ｗｏｎｄｅｒ ａｔ ｉｔｓ ｌｏｎｇ ｈｉｓｔｏｒｙ ａｎｄ ｕｎｉｑｕｅ ｃｕｌｔｕｒａｌ ｒｅｌｉｃｓ． Ｃｏｎｔａｃｔ Ｕｓ Ｅ⁃ｍａｉｌ：ｗｃｃｉ２０１４＠ ｇｍａｉｌ．ｃｏｍ Ｗｅｂｓｉｔｅ：ｈｔｔｐ： ／ ／ ｗｗｗ．ｉｅｅｅ⁃ｗｃｃｉ２０１４．ｏｒｇ ／ ·３４２· 智 能 系 统 学 报 第 ９ 卷