文章快速检索 高级检索

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 neighborhood homology learning algorithm through using the monomorphic division theory in homology algebra. The neighborhood 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 complex, 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 database of handwritten digits named USPS_ALL.
Key words: homology learning     homology algebra     machine learning     margin partitioning     margin homology learning     neighborhood homology learning algorithm     neighborhood complex graphs     similarity

SVM和TVQ在一定程度上都提高了边缘划分效果和准确度。但是这些方法对边缘可变的划分问题就显得不足了，因此本文提出了一种邻域同调学习算法。邻域同调学习算法是通过引进同调论思想，从机器学习的角度出发研究的一种边缘学习新方法。该方法针对图集的分类问题，在分类过程中能够有效地保证图形的结构特征不变。该方法主要是通过判断给定图形的邻域复形的各阶同调群是否同构，对图形进行邻域同调分类。

1 邻域同调的基本概念

Aqq维几何单形，简称q维单形，记作〈a0, a1, …, aq〉，a0, a1, …, aq称为q维单形Aq的顶点，实数λi称为点xq维单形Aq中的重心坐标。

1)K中任意2个单形都是规则相处的；

2)K中任意单形的任意一个面仍是K中的单形。

 (1)

 (2)

 (3)

Cq(K)叫作Kq维(整数)链群。且对于任意Kq维链，令

 (4)

qCq(K)→Cq－1(K)是群同态。这里的q即为q维边缘算子或边缘同态。其实，边缘同态是几何上概念的代数化，是用来反映图形的边界关系的。

 (5)

 (6)
 (7)

Zq(K)的元zq叫做q维闭链，Bq(K)的元bq叫做q维边缘链。

Hq(K)叫做单纯复形Kq维(单纯)同调群。

1)由单个元素ci所组成的子集属于K，这里i=0, 1, …, q

2)若AK的元，则A的子集也是K的元。

2 邻域同调学习算法

G=(V(G), E(G))是一个简单连通图。显然，一个简单连通图就是一个单纯复形，根据上述定义即可以看成是有限个单形的集合，V(G)={a0, a1, …, aα0－1表示图Gα0个顶点的集合也就是图G中所有0维单形的集合，E(G)表示顶点之间的所有连接边的集合。令XF分别是G的一个顶点子集和边子集，就以GX表示G去掉X中的点及其关联边而得的图，GF表示G去掉F中的边而得到的图。设aG的任意一个顶点，以N(a)表示a的邻域，那么N(X)表示X中所有点邻域的并，即

1)置每个样本Gi为一个类，则G1, G2, …, Gn，共形成n个类；

2)找出Gi的任意一个顶点的邻域，那么Gi中的所有顶点邻域的并集即为所要构造的邻域复形N(Gi)；

3)根据式(3)和式(4)计算出每个Gi邻域复形N(Gi)的q维链群Cq(N(Gi))，此时可以得到形如式(5)的一个序列：

4)再由式(6)和式(7)分别可以求出邻域复形N(Gi)的q维闭链群Zq(N(Gi))和q维边缘链群Bq(N(Gi))；

5)根据Hq(N(Gi))=Zq(N(Gi))/Bq(N(Gi))计算出N(Gi)的q维同调群；

6)如果Gii∈[1, n－1]与Gjj∈[i+1, n]的各阶同调群分别同构，则。那么就将GiGj合并为一个新类，此时现有的类数为k=n－1类。循环判断至所有样本都分类完毕；

7)通过上述步骤可将样本分成k类，输出H={Hi}i=1k

3 实验分析

3.1 人工数据

 图 1 随机数据和可视化结果 Fig. 1 Random data and the result of visualization

3.2 手写数字识别实验

 图 2 USPS_ALL数据库部分图像实例 Fig. 2 Part of the images in USPS_ALL

 图 3 手写数字集上的识别率 Fig. 3 Recognition accuracy on the USPS_ALL database
3.3 实物图像

 图 4 部分实物图像 Fig. 4 Part of the images in MPEG7 CE

 图 5 MPEG7 CE上3种算法的识别率 Fig. 5 Recognition accuracy on the MPEG7 CE database

4 结束语

 [1] 周志华, 王珏. 机器学习及其应用研究[M]. 北京: 清华大学出版社, 2007 : 1 -161. [2] 李凡长, 张莉, 杨季文. 李群机器学习[M]. 合肥: 中国科学技术大学出版社, 2013 : 281 -296. [3] PERNKOPF F, WOHLMAYR M, TSCHIATSCHEK S. Maximum margin Bayesian network classifiers[J]. Pattern Analysis and Machine Intelligence , 2012, 34 (3) : 521-532 DOI:10.1109/TPAMI.2011.149 [4] PANWAR H, GUPTA S. Advances in Computer Science, Engineering and Applications[M]. Berlin: Springer, 2012 : 385 -392. [5] EIDELMAN V. Optimization strategies for online large-margin learning in machine translation[C]//Proceedings of the 7th Workshop on Statistical Machine Translation, Montreal, Canada, 2012: 480-489. [6] VAPNIK V. Statistical learning theory[M]. New York: Wiley, 1998 : 1 -768. [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 DOI:10.1109/TKDE.2005.77 [8] LIN C F, WANG S D. Fuzzy support vector machines[J]. IEEE Transactions on Neural Networks , 2002, 13 (3) : 466-471 [9] FABIO A, ALESSANDRO S. A re-weighting strategy for improving margins[J]. Artificial Intelligence , 2002, 137 : 197-216 DOI:10.1016/S0004-3702(02)00122-4 [10] 鲜敏, 李凡长. 一种同调边缘学习算法[J]. 计算机工程与应用 , 2008, 44 (21) : 192-194 XIAN Min, LI Fanzhang. Learning algorithm based on homology margin[J]. Computer Engineering and Applications , 2008, 44 (21) : 192-194 [11] 杨季文, 李哲硕, 何书萍, 等. 胞腔同调边缘学习算法研究[J]. 计算机研究与发展 , 2013, 50 (5) : 1005-1011 YANG Jiwen, LI Zheshuo, HE Shuping, et al. On celluar homology margin learning algorithms[J]. Computer Research and Development , 2013, 50 (5) : 1005-1011 [12] 邓乃杨, 田英杰. 数据挖掘中的新方法——支持向量机[M]. 北京: 科学出版社, 2005 : 1 -408. [13] BURGES C J C. A tutorial on support vector machines for pattern recognition[J]. Data Mining and Knowledge Discovery , 1998, 2 (2) : 121-167 DOI:10.1023/A:1009715923555 [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]. Machine Learning , 1995, 20 (3) : 273-297 [16] SIMARD P Y, LECUN Y, DENKER J. Efficient pattern recognition using a new transformation distance[J]. Advanced in Neural Information Processing System , 1993, 5 : 50-58 [17] SCHAPIRE R E, SINGER Y. Improved boosting algorithms using confidence-rated predictions[J]. Machine Learning , 1999, 37 (3) : 297-336 DOI:10.1023/A:1007614523901 [18] DUFFY N, HELMBOLD D. Boosting methods for regression[J]. Machine Learning , 2002, 47 (2/3) : 153-200 DOI:10.1023/A:1013685603443 [19] 南基洙, 王颖. 同调代数导论[M]. 大连: 大连理工大学出版社, 2011 : 112 -222. [20] 姜伯驹. 同调论[M]. 北京: 北京大学出版社, 2006 : 1 -90. [21] 江泽涵. 拓扑学引论[M]. 上海: 上海科学技术出版社, 1978 : 25 -169. [22] 孟道骥, 白承铭. 李群[M]. 北京: 科学出版社, 2003 : 28 -92. [23] 黄保军. 同调与同伦原理[M]. 合肥: 中国科学技术出版社, 2005 : 16 -59. [24] 沈信耀. 同调论——代数拓扑学之一[M]. 北京: 科学出版社, 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 Mathematics , 1983, 12 (3) : 1-5 [26] 方冬云. 不包含{4, 8, 9}-圈平面图结构的性质[J]. 长春工业大学学报 , 2011, 32 (5) : 485-488 FANG Dongyun. Nature of stucture planar graph without {4, 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 [28] 薛秀谦. 立方图的邻域同调分类[J]. 中国矿业大学学报 , 1995, 24 (4) : 110-112 XUE Xiuqian. The neighborhood homology classification of cubic graphs[J]. Journal of China University of Mining and Technology , 1995, 24 (4) : 110-112 [29] 薛秀谦. 无C4图的邻域同调分类[J]. 系统科学与数学 , 1998, 18 (1) : 101-103 XUE Xiuqian. The neighborhood homology classification of the C4 free graphs[J]. Systems Science and Mathematics , 1998, 18 (1) : 101-103
DOI: 10.3969/j.issn.1673-4785.201403063

0

#### 文章信息

ZHAO Mengmeng, LI Fanzhang

Neighborhood homology learning algorithm

CAAI Transactions on Intelligent Systems, 2014, 9(3): 336-342
http://dx.doi.org/10.3969/j.issn.1673-4785.201403063