SSXCS：半监督学习分类系统

南京大学学报(自然科学版) ›› 2013, Vol. 49 ›› Issue (5): 611–618.

SSXCS：半监督学习分类系统

俞亚君，霍静，史颖欢，高阳，张剡

出版日期:2014-02-08 发布日期:2014-02-08
作者简介:（南京大学计算机软件新技术国家重点实验室南京210023）
基金资助:
国家自然科学基金 (61035003, 61175042, 61021062, 61305068) ，国家 973 项目 (2009CB320702) ，江苏省 973 项目 (BK2011005) ，教育部新世纪优秀人才支持计划 (NCET-10-0476)

SSXCSSemi-upervised learning classifier system

Yu Ya-Jun,Huo Jing，Shi Ying，Gao Yang，Zhang Yan

Online:2014-02-08 Published:2014-02-08
About author:(State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210023, China)

摘要/Abstract

摘要： 学习分类系统作为一种自适应的机器学习技术，已经被成功地运用于解决多种学习问题。传统的学习分类系统的工作主要关注监督学习分类和无监督学习聚类环境下的研究，而学习分类系统在半监督学习环境下的效果不得而知。新的半监督学习分类系统(SSXCS)，目的是研究学习分类系统是否能够在已知少量的已标记数据的情况下利用大量的未标记数据来提高学习性能。SSXCS先通过更新与进化得到对应的已标记规则集与无标记规则集，然后利用提出的规则标记算法对无标记规则集进行标记，约简规则后生成最终的分类系统。实验结果表明SSXCS能够有效地利用提供的无标记数据来提高分类器性能，同时相比较于一般的半监督学习算法，SSXCS能够取得更好或者相当的分类性能。

Abstract: Learning classifier system, which belongs to adaptive machine learning techniques, has been successfully applied to various learning problems. Previous works for learning classifier system mainly focused on the supervised learning manner (classification) and unsupervised learning manner (clustering). However, the research of the learning classifier system on semi-supervised learning is still untouched. To this end, a novel Semi-Supervised Learning Classifier System (SSXCS) is presented, whose goal is to investigate the problem that if the learning classifier system can use small amount of the labeled data as well as large amount of the unlabeled data to improve the learning performance. The proposed SSXCS first employs the updating and evolution strategies to initialize the labeled and unlabeled rule sets. Then, the obtained unlabeled rule sets will be automatically labeled by rule labeling algorithm proposed. Finally, rule compacting is adopted to obtain the learning classifier system. The experiments have demonstrated that the proposed SSXCS is able to use the unlabeled data to improve the learning ability. Also, compared with traditional semi-supervised learning algorithms, SSXCS can achieve superior or comparable classification performance

俞亚君，霍静，史颖欢，高阳，张剡. SSXCS：半监督学习分类系统[J]. 南京大学学报(自然科学版), 2013, 49(5): 611–618.

Yu Ya-Jun,Huo Jing，Shi Ying，Gao Yang，Zhang Yan. SSXCSSemi-upervised learning classifier system[J]. Journal of Nanjing University(Natural Sciences), 2013, 49(5): 611–618.

参考文献

[1] Bull L. Learning classifier systems: A brief introduction. Applications of Learning Classifier Systems. Springer Berlin Heidelberg, 2004, 1~12.

[2] Holland J H. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control and artificial intelligence. Cambridge, MA, USA: MIT Press, 1992, 228.

[3] Goldberg D E. Genetic algorithm in search, optimization, and machine learning. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1989, 372.

[4] Sutton R S, Barto A G. Reinforcement learning: An introduction. Cambridge, MA, USA: MIT Press, 1998, 322.

[5] Stolzmann W, Butz M. Latent learning and action planning in robots with anticipatory classifier systems. Pier L L, Wolfgang S, Stewart W W. Learning Classifier Systems. London, UK: Springer -Verlag, 2000: 301~320.

[6] Schulenburg S, Ross P. An adaptive agent based economic model. Pier L L, Wolfgang S, Stewart W W. Learning Classifier Systems. London, UK: Springer -Verlag, 2000: 263~282.

[7] Richards R A. Zeroth-order shape optimization utilizing a learning classifier system. Ph.D. Dissertation. Stanford University, Stanford, CA, 1995.

[8] Wilson S W. Classifier fitness based on accuracy. Evolutionary Computation, 1995, 3(2): 149~175.

[9] Wilson S W. Get real! XCS with continuous-valued inputs. Pier L L, Wolfgang S, Stewart W W. Learning Classifier Systems. London, UK: Springer -Verlag, 2000: 209~219.

[10] Wilson S W. Compact rulesets from XCSI. Lanzi P L, Stolzmann W, Wilson S W. Advances in Learning Classifier Systems: Fourth International Workshop, IWLCS2001. Berlin Heidelberg: Springer-Verlag, 2002: 197~208.

[11] Dixon P W, Corne D W, Oates M J. A ruleset reduction algorithm for the xcs learning classifier system. Lanzi P L, Stolzmann W, Wilson S W. Learning Classifier System: Fifth International Workshop, IWLCS2002. Berlin Heidelberg: Springer-Verlag, 2003: 20~29.

[12] Holmes J, Sager J, Bilker W. A comparison of three methods for covering missing data in XCS. Proceeding of the 7^th International Workshop on Learning Classifier Systems (IWLCS 2004), Seattle, Washington, USA, 2004.

[13] Gu D Q, Gao Y. Incremental gradient descent imputation method for missing data in learning classifier systems. Proceedings of the 2005 Workshops on Genetic and Evolutionary Computation. ACM, 2005: 72~73.

[14] Gao Y, Huang Z X, Wu L. Learning classifier system ensemble and compact rule set. Connection Science, 2007, 19(4): 321~337.

[15] Shi L D, Shi Y H, Gao Y. Clustering with XCS and agglomerative rule merging. Proceeding of the 10^th international conference on Intelligent Data Engineering and Automated Learning (IDEAL 2009). Berlin Heidelberg, Springer-Verlag, 2009: 242~250.

[16] Karypis G, Han E H, Kumar V. Chameleon: Hierarchical clustering using dynamic modeling. Computer, 1999, 32(8): 68~75.

[17] Zhu X J. Semi-supervised learning literature survey. Technical Report. University of Wisconsin at Madison, Madison, 2006.

[18] Seeger M. Learning with labeled and unlabeled data. Technical Report. University of Edinburgh, Edinburgh, 2001.

[19] Zhou Z H, Li M. Tri-training: Exploiting unlabeled data using three classifiers. IEEE Transactions on Knowledge and Data Engineering , 2005, 17(11): 1529~1541.

[20] Chang Y, Liang J Y, Gao J W, et al. A semi-supervised clustering algorithm based on seeds and pair-wise constraints. Journal of Nanjing University (Natural Sciences), 2012, 48(4): 405~411.（常瑜，梁吉业，高嘉伟等. 一种基于Seeds集和成对约束的半监督聚类算法. 南京大学学报（自然科学），2012，48（4）：405~411）.

[21] Narayanan H, Belkin M, Niyogi P. On the relation between low density separation, spectral clustering and graph cuts. Advances in Neural Information Processing Systems, 2007, 19: 1025.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed