第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. 线性不可分支持向量机。线性可分支持向量机又叫第 ９ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．３ ２０１４ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０３０６３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｏｉ ／ １０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３４７８５．２０１４０３０６３．ｈｔｍｌ 邻域同调学习算法 赵梦梦，李凡长 （苏州大学 计算机科学与技术学院，江苏 苏州 ２１５００６） 摘 要：目前已有的边缘学习算法对边缘可变的数据划分问题存在一些不足，这些算法在分类过程中不能有效地保 证数据的结构特征不变。 因而文章首先通过引进同调代数中的单形划分理论，从机器学习的角度对分类问题中的 边缘划分进行研究，提出了一种邻域同调学习算法。 算法给出了图形的邻域复形的构造方法和判断 ２ 个给定图形 相似性的判定标准。 最后通过在 ＵＳＰＳ＿ＡＬＬ 手写数字集数据库和 ＭＰＥＧ７ ＣＥ 图像库上与 ＳＶＭ、ＴＶＱ 算法的对比实 验验证了本算法的有效性。 关键词：同调学习；同调代数；机器学习；边缘划分；边缘同调学习；邻域同调学习算法；邻域复形图；相似性 中图分类号： ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０３⁃０３３６⁃０７ 中文引用格式：赵梦梦，李凡长． 邻域同调学习算法［Ｊ］． 智能系统学报， ２０１４， ９（３）： ３３６⁃３４３． 英文引用格式：ＺＨＡＯ Ｍｅｎｇｍｅｎｇ，ＬＩ Ｆａｎｚｈａｎｇ． Ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（３）： ３３６⁃３４３． Ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ＺＨＡＯ Ｍｅｎｇｍｅｎｇ，ＬＩ Ｆａｎｚｈａｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｓｏｏｃｈｏｗ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｕｚｈｏｕ ２１５００６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｔ ｐｒｅｓｅｎｔ ，ｔｈｅ ｅｘｉｓｔｉｎｇ ｍａｒｇｉｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｓｔｉｌｌ ｈａｖｅ ｓｏｍｅ ａｆｆｅｃｔｓ ｗｈｅｎ ａｔｔｅｍｐｔｉｎｇ ｔｏ ｓｏｌｖｅ ｔｈｅ ｄａｔａ ｐａｒｔｉｔｉｏｎｉｎｇ ｐｒｏｂｌｅｍ ｏｆ ｖａｒｉａｂｌｅ ｍａｒｇｉｎｓ．Ｔｈｅｓｅ ａｌｇｏｒｉｔｈｍｓ ｃａｎ ｎｏｔ ｅｆｆｅｃｔｉｖｅｌｙ ｍａｉｎｔａｉｎ ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｆｅａｔｕｒｅ ｏｆ ｄａｔａｓ ｉｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ．． Ａｔ ｐｒｅｓｅｎｔ， ｔｈｅ ｅｘｉｓｔｉｎｇ ｍａｒｇｉｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｓｔｉｌｌ ｈａｖｅ ｄｅｆｅｃｔｓ ｗｈｅｎ ａｔｔｅｍｐｔｉｎｇ ｔｏ ｓｏｌｖｅ ｔｈｅ ｄａｔａ ｐａｒｔｉｔｉｏｎｉｎｇ ｐｒｏｂｌｅｍ ｏｆ ｖａｒｉａｂｌｅ ｍａｒｇｉｎｓ． Ａｓ ａ ｃｏｎｓｅｑｕｅｎｃｅ， ｔｈｉｓ ｐａｐｅｒ ｉｎｉｔｉａｌｌｙ ｐｒｏｐｏｓｅｓ ａ ｎｅｉｇｈｂｏｒ⁃ ｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｔｈｒｏｕｇｈ ｕｓｉｎｇ ｔｈｅ ｍｏｎｏｍｏｒｐｈｉｃ ｄｉｖｉｓｉｏｎ ｔｈｅｏｒｙ ｉｎ ｈｏｍｏｌｏｇｙ ａｌｇｅｂｒａ． Ｔｈｅ ｎｅｉｇｈ⁃ ｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｒｅａｓｅａｒｃｈｓ ｔｈｅ ｍａｒｇｉｎ ｐａｒｔｉｔｉｏｎｉｎｇ ｐｒｏｂｌｅｍ ｆｒｏｍ ｔｈｅ ｐｅｒｓｐｅｃｔｉｖｅ ｏｆ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ． Ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｎｃｌｕｄｅｓ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｓｔｒｕｃｔｕｒｉｎｇ ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｃｏｍ⁃ ｐｌｅｘ， ａｎｄ ｔｈｅ ｃｒｉｔｅｒｉｏｎ ｆｏｒ ｊｕｄｇｉｎｇ ｔｈｅ ｓｉｍｉｌａｒｉｔｙ ｂｅｔｗｅｅｎ ｔｗｏ ｇｉｖｅｎ ｇｒａｐｈｓ． Ｆｉｎａｌｌｙ， ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｉｓ ｊｕｓｔｉｆｉｅｄ ｔｈｒｏｕｇｈ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｃｏｎｔｒａｓｔｅｄ ｗｉｔｈ ＳＶＭ ａｎｄ ＴＶＱ ｏｎ ａｎ ｉｍａｇｅ ｄａｔａｓｅｔ ｎａｍｅｄ ＭＰＥＧ７ ＣＥ ａｎｄ ａ ｄａｔａ⁃ ｂａｓｅ ｏｆ ｈａｎｄｗｒｉｔｔｅｎ ｄｉｇｉｔｓ ｎａｍｅｄ ＵＳＰＳ＿ＡＬＬ． Ｋｅｙｗｏｒｄｓ：ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ； ｈｏｍｏｌｏｇｙ ａｌｇｅｂｒａ； ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ； ｍａｒｇｉｎ ｐａｒｔｉｔｉｏｎｉｎｇ； ｍａｒｇｉｎ ｈｏｍｏｌｏｇｙ ｌｅａｒｎ⁃ ｉｎｇ； ｎｅｉｇｈｂｏｒｈｏｏｄ ｈｏｍｏｌｏｇｙ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ； ｎｅｉｇｈｂｏｒｈｏｏｄ ｃｏｍｐｌｅｘ ｇｒａｐｈｓ； ｓｉｍｉｌａｒｉｔｙ 收稿日期：２０１４⁃０３⁃２２． 网络出版日期：２０１４⁃０６⁃１４． 基金项目：国家自然科学基金资助项目（６１０３３０１３，６０７７５０４５）． 通信作者：李凡长． Ｅ⁃ｍａｉｌ：ｌｆｚｈ＠ ｓｕｄａ．ｅｄｕ．ｃｎ． 边缘学习［１⁃５ ］是机器学习的核心问题之一。 目 前比较成功的边缘学习算法主要有 Ｖ．Ｖａｐｎｉｋ 提出 的 ＳＶＭ 最大边缘算法［ ６⁃８ ］ ， Ｆａｂｉｏ Ａｉｌｌｉ、 Ａｌｅｓｓａｎｄｒｏ Ｓｐｅｒｄｕｔｉ 提出的 ＴＶＱ 算法［ ９ ］ 和同调边缘胞腔学习 算法等［１０⁃１１］ 。 支持向量机（ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ，ＳＶＭ）是一 种努力最小化结构风险［１ ２ ⁃１ ３ ］的算法，主要有线性可 分支持向量机［１ ２ ］ 、近似线性可分支持向量机［１ ２ ］ 和 线性不可分支持向量机。 线性可分支持向量机又叫