基于人工免疫网络的分类算法及其应用
|
摘要
人工免疫网络算法是基于免疫学原理特别是独特型免疫网络原理提出的应用于智能计算领域的奠基性算法。然而目前不少人工免疫网络分类算法都或多或少的存在一些缺陷,其一是算法机制的问题:网络规模庞大、计算复杂、对抗原采用一次递呈,这些导致了算法运行效率低;其二是应用领域比较窄,多数集中于标准数据的分类与聚类。
基于此,针对复杂数据分类与图像处理问题,本文分别提出了一种新的人工免疫网络分类算法、基于自适应PSO的人工免疫网络分类算法以及基于人工免疫网络的关联规则挖掘算法,具体研究工作如下:
1.提出了一种新的人工免疫网络分类算法。该算法利用每个类别对应单个B细胞的策略,简化网络规模并减少了同类别B细胞之间的抑制操作,同时引入了新的基于对训练样本正确识别率的亲合度评价函数,实现了基于抗原的优先级的选择策略。实验结果表明,该算法在分类精度上具有一定的优势,鲁棒性更好。
2.提出了基于自适应PSO的人工免疫网络分类算法。该方法将自适应权值的PSO算法引入到人工免疫网络算法的变异算子中,同时采用各个B细胞包含抗原(即训练样本)所有类别的信息的策略。使得该算法具有良好的全局搜索能力以及快速的收敛速度。
3.提出了基于人工免疫网络的关联规则挖掘算法。该方法将数据挖掘中的关联规则引入人工免疫网络算法中,用寻找最优关联规则来替代最佳聚类中心。对比实验表明,该方法在处理多类别以及名词性(nominal)特征数据时具有令人满意的分类精度和收敛速度。
Artificial Immune Network (AIN) algorithm is the foundational algorithm which is based on Immune theory and especial the Idiotypic Immune Network (IIN) theory. And AIN has been applied into the field of intelligent computing. However, there are some shortcomings in the most existing AIN classification algorithms. On the one hand, the shortcomings lie in the mechanism of algorithm such as large-scale network, complex computation, and only once presenting the antigens, which resulted in the problem of low efficiency. On the other hand, they lie in the narrow applications, most AIN algorithms focus on the standard datasets classification and clustering.
After analyzing above problems and aim to solve complex data classification and image classification problems, three AIN classification algorithms are proposed in this paper, the main work can be outlined as follows:
(1) A new Artificial Immune Network classification algorithm is proposed. In the proposed algorithm, only one B-cell is used to denote single class in order to reduce the scale of network, and avoid the suppression operation between B-cells, moreover, a new affinity function based on the correct rate is proposed to realize the evaluation strategy based on antigen priority. The results of experiments indicate that the new algorithm has better accuracy and robustness.
(2) A self-adaptive PSO based Artificial Immune Network classification algorithm is proposed. This method applies the self-adaptive PSO into the mutation process of the artificial immune network algorithm. Moreover, the strategy of every B-cell containing all types of information for antigens is used in the proposed algorithm. So the new algorithm has good global search ability and fast convergence speed.
(3) An associate rules mining algorithm based on artificial immune network is proposed. This method introduces the association rules used in the data mining into the Artificial Immune Network algorithm. And it uses researching the optimal association rules to replace finding the best cluster center. Comparative experiments show that the method has satisfactory classification accuracy and convergence speed in dealing with multi-class and nominal attributes data.
基于此,针对复杂数据分类与图像处理问题,本文分别提出了一种新的人工免疫网络分类算法、基于自适应PSO的人工免疫网络分类算法以及基于人工免疫网络的关联规则挖掘算法,具体研究工作如下:
1.提出了一种新的人工免疫网络分类算法。该算法利用每个类别对应单个B细胞的策略,简化网络规模并减少了同类别B细胞之间的抑制操作,同时引入了新的基于对训练样本正确识别率的亲合度评价函数,实现了基于抗原的优先级的选择策略。实验结果表明,该算法在分类精度上具有一定的优势,鲁棒性更好。
2.提出了基于自适应PSO的人工免疫网络分类算法。该方法将自适应权值的PSO算法引入到人工免疫网络算法的变异算子中,同时采用各个B细胞包含抗原(即训练样本)所有类别的信息的策略。使得该算法具有良好的全局搜索能力以及快速的收敛速度。
3.提出了基于人工免疫网络的关联规则挖掘算法。该方法将数据挖掘中的关联规则引入人工免疫网络算法中,用寻找最优关联规则来替代最佳聚类中心。对比实验表明,该方法在处理多类别以及名词性(nominal)特征数据时具有令人满意的分类精度和收敛速度。
Artificial Immune Network (AIN) algorithm is the foundational algorithm which is based on Immune theory and especial the Idiotypic Immune Network (IIN) theory. And AIN has been applied into the field of intelligent computing. However, there are some shortcomings in the most existing AIN classification algorithms. On the one hand, the shortcomings lie in the mechanism of algorithm such as large-scale network, complex computation, and only once presenting the antigens, which resulted in the problem of low efficiency. On the other hand, they lie in the narrow applications, most AIN algorithms focus on the standard datasets classification and clustering.
After analyzing above problems and aim to solve complex data classification and image classification problems, three AIN classification algorithms are proposed in this paper, the main work can be outlined as follows:
(1) A new Artificial Immune Network classification algorithm is proposed. In the proposed algorithm, only one B-cell is used to denote single class in order to reduce the scale of network, and avoid the suppression operation between B-cells, moreover, a new affinity function based on the correct rate is proposed to realize the evaluation strategy based on antigen priority. The results of experiments indicate that the new algorithm has better accuracy and robustness.
(2) A self-adaptive PSO based Artificial Immune Network classification algorithm is proposed. This method applies the self-adaptive PSO into the mutation process of the artificial immune network algorithm. Moreover, the strategy of every B-cell containing all types of information for antigens is used in the proposed algorithm. So the new algorithm has good global search ability and fast convergence speed.
(3) An associate rules mining algorithm based on artificial immune network is proposed. This method introduces the association rules used in the data mining into the Artificial Immune Network algorithm. And it uses researching the optimal association rules to replace finding the best cluster center. Comparative experiments show that the method has satisfactory classification accuracy and convergence speed in dealing with multi-class and nominal attributes data.
引文
[1]王卫民.基于人工免疫系统的否定选择算法改进的相关研究.成都电子科技大学, 2008: 1~15.
[2] Jerne N K. The immune system. Scientific American, 1973, 229(1):51~60.
[3] Jerne N K. Towards a network theory of the immune system. Annual Immunology, 1974, 125C: 373~389.
[4] Perelson A. Immune Network theory. Immunological Review, 1989, 110: 5~36.
[5] Farmer J D, Packard N H, Perelson A S. The immune system, adaptation, and machine learning. Physical D, 1986, 22: 187~204.
[6]莫红伟.人工免疫系统原理与应用.哈尔滨工业大学出版社, 2002.
[7] Hunt J E, Cooke D E. Learning using an artificial immune system. Journal of Network and Computer Applications, 1996, 19(2): 189~212.
[8] Hunt J E, Fellowa A, Introducing an immune response into a CRB system for data mining. BCS ESG’96 Conference and Published as Research and development in Expert system XIII, 1996.
[9] Tang Z, Yamaguchi T, Tashima K, et al.. Multiple-valued immune network model and its simulations. Proceedings of the 27th International Symposium on Multiple-valued logic, Autigonish, Canada, May. 28-30, 1997: 233~238.
[10] De Castro. An evolutionary immune network for data clustering. VI Brazilian Symposium on Neural Networks (SBRN'00), Brazil, Jan, 22-25, 2000: 84~89.
[11] De Castrol, and Von Zuben. Immune Neural Network Models: Theoretical and Emprical Comparisons. International Journal of Computational Intelligence and Applications, 2001, 1(3): 239~257.
[12] Timmis J, Neal M.A resource limited artificial immune system for data analysis. Knowledge Based Systems, 2001, 14(3-4): 121~130.
[13] Watkins A, Timmis J, and Boggess L. Artificial Immune Recognition System (AIRS): An Immune-Inspired Supervised Learning Algorithm. Genetic Programming and Evolvable Machines, 2004(5): 291~317.
[14] Watkins A, and Timmis J. Artificial Immune Recognition System (AIRS): Revisions and Refinements. Proceeding of ICARIS2002, Springer Verlag, 2002: 173~181.
[15] Watkins A, and Timmis J. Exploiting the Parallelism Inherent in AIRS, an Artificial Immune Classifier. Proceeding of ICARIS2004, Springer Verlag, 2004: 427~438.
[16] De Castro L N, Von Zuben F J. Artificial immune systems: a new approach to pattern recognition. In: L Alonso, J Corchado. C Fyfe, eds. Artificial Neural Networks in Pattern Recognition. University of Paisley, UK, 2002.
[17] Knight T and Timmis J. AINE: An Immunological Approach to Data Mining. In N Cercone, T Lin and Xindong Wu, editors, IEEE International Conference on Data Mining, San Jose, CA. USA, December 2001, 297~304.
[18] Neal M. An Artificial Immune System for Continuous Analysis of Time-varying Data. In: Timmis, J, Bentley, P. (eds.) In: Proc. of the 1st Int. Conf. Artificial Immune System, 2002: 76~85.
[19] Gong Maoguo, Jiao Lichen, and Du Haifeng. Mutiobjective immune algorithm with nondom inated neighbor-based selection. Evolutionary Computation, 2008, 16(2): 255~265.
[20]左兴权,莫宏伟,范玉顺.参数化活动调度及其混合免疫调度算法.哈尔滨工程大学学报, 2006, 27(增): 257~263.
[21]公茂果,焦李成,杜海峰,等.用于约束优化的人工免疫相应进化策略.计算机学报, 2007, 30(1): 37~47.
[22]马文萍,焦李成,张向荣,等.基于量子克隆优化的SAR图像分类.电子学报, 2007, 35(12): 2241~2246.
[23] Freitas A A, and Timmis J. Revisiting the foundations of artificial immune systems for data mining. IEEE transactions on evolutionary computation, 2007, 11(4): 521~540.
[24] De Castro. The Immune Response of an Artificial Immune Network (AINet). Canberra: IEEE Congress on Evolutionary Computation, 2003:8~12.
[25]钟燕飞,张良培,李平湘.基于多值免疫网络的多光谱遥感影像分类.计算机学报, 2007, 30(12): 2181~2188.
[26] Zhong Yangfei, Zhang Liangpei, and Gong Jianya, et al.. A supervised artificial immune classifier for remote-sensing imagery. IEEE Transactions on Geosciences and Remote Sensing, 2007, 45 (12): 3957~3966.
[27] Colaco C. Acquired Wisdom in Innate Immunity. Immunology Today. 1998, 19(1):50.
[28] Medzhitov R, and Janeway C A. Innate Immunity: Impact on the Adaptive Immune Response. Current Opinion in Immunology. 1997, (9): 4~9.
[29] Zinkernagel R M, and Kelly J. How Antigen Influences Immunity. The Immunologist. 1997, 4/5: 114~120.
[30]童健华.基于人工免疫网络的聚类分析.中山大学, 2008: 54.
[31] Jerne N K. The Immune System. Scientific American. 1973, 229(1): 52~60.
[32] Perelson A S, Hightower, RForrest S. Evolution and Somatic Learning of V-Region Genes, Research in Immunology, 1996, 147: 202~208.
[33] De Castro L N, Von Zuben F J. The clonal selection algorithm with engineering application. Proc. Of GECCO’00, Workshop on Artificial Immune Systems and Their Applications, 2000: 36~37.
[34] Kevin Leung, France Cheong, and Christopher Cheong. Generating Compact Classifier Systems Using a Simple Artificial Immune System. IEEE Transactions on System, Man and Cybernetics, Part B, 2007, 10(5): 1344~1356.
[35] Du Haifeng, Jiao Licheng, and Wang Sunan. Clonal operator and antibody clone algorithms. Proceedings of the First International Conference on Machine Learning and Cybernetics, Beijing, 2002: 506~510.
[36] Clausi D A and Yue B. Comparing concurrence probabilities and Markov fields for texture analysis of SAR sea ice image. IEEE Transactions on Geosciences and Remote Sensing, 2004, 42(1): 215~228.
[37] Mazidah puteh FTMSK and Khairuddin Omar FTSM. Classifying heterogeneous data with artificial immune system. International Symposium Information Technology, Shanghai, China, Dec. 21-22, 2008, 3: 1~5.
[38] Adnan Acan, and Ahmet Unveren. A Memory-Based Colonization Scheme for Particle Swarm Optimization. Evolutionary Computation 2009, IEEE Congress on 18-21May 2009: 1965~1972.
[39]丛林,焦李成,沙宇恒.正交免疫克隆粒子群多目标优化问题.电子与信息学报. 2008, 10, 30(10): 2320~2324.
[40] Kosmas V. Deligkaris, Zaharias D. Zaharis, and Dimaitra G. Kampitaki. Thinned Planar Array Design Using Boolean PSO With Velocity Mutation. IEEE TRANSACTION ON MAGNETICS, 2009, 45(3): 1490~1493.
[41] Chen Ailing, and Guo Qiang. An Effective Hybrid Optimization Algorithm based on Self-adaptive Particle Swarm Optimization Algorithm and Artificial Immune Clone Algorithm. Fourth International Conference on Natural Computation. IEEE 2008: 129~132.
[42] Ge Hongwei, Sun Liang, Liang and Yanchun. An Effective PSO and AIS-Based Hybrid Intelligent Algorithm for Job-Shop Scheduling. IEEE TRANSACTIONSON SYSTEMS, MAN, AND CYBERNETICS—PART A: SYSTEMS AND HUMANS, 2008, 38(2): 358~368.
[43] Shi Y, and Eberhart R. Empirical study of particle swarm optimization. Proceedings of congress on evolutionary computation, 1999: 1945~1950.
[44] Zhan ZhiHui, Zhang Jun, Li Yun, and Henry Chung. Adaptive Particle Swarm Optimization. IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, 2009: 1~20.
[45] Liu Bo, Wang Ling, and Jin YiHui. Improved particle swarm optimization combined with chaos, Chaos, Solitons and Fractals, 2005: 1261~1271.
[46] Blake C L, and Merz C J. UCI Repository of Machine Learning Databases. [Online]. Available: http://archive.ics.uci.edu/ml/datasets.html.
[47]潘晓英.多智能体社会协同进化模型及其算法研究.西安电子科技大学, 2008, 12: 150~152.
[48] Tien Dung Do, Siu Cheung Hui, and Fong A. C. M.. Associative Classification With Artificial Immune System. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, APRIL 2009, 13(2): 217~228.
[49]宋媛媛.人工免疫算法研究及其在数据挖掘上的应用.青岛大学, 2008: 22~23.
[50] Agrawal R, Imiclinski T, and Swami A. A performance perspective. IEEE Transknowledge and Data Enginnering, 1993, 5: 914~925.
[51]武建华,沈均毅,王元元.一种改进的关联分类方法.计算机工程, 2009, 35(9): 63~65.
[2] Jerne N K. The immune system. Scientific American, 1973, 229(1):51~60.
[3] Jerne N K. Towards a network theory of the immune system. Annual Immunology, 1974, 125C: 373~389.
[4] Perelson A. Immune Network theory. Immunological Review, 1989, 110: 5~36.
[5] Farmer J D, Packard N H, Perelson A S. The immune system, adaptation, and machine learning. Physical D, 1986, 22: 187~204.
[6]莫红伟.人工免疫系统原理与应用.哈尔滨工业大学出版社, 2002.
[7] Hunt J E, Cooke D E. Learning using an artificial immune system. Journal of Network and Computer Applications, 1996, 19(2): 189~212.
[8] Hunt J E, Fellowa A, Introducing an immune response into a CRB system for data mining. BCS ESG’96 Conference and Published as Research and development in Expert system XIII, 1996.
[9] Tang Z, Yamaguchi T, Tashima K, et al.. Multiple-valued immune network model and its simulations. Proceedings of the 27th International Symposium on Multiple-valued logic, Autigonish, Canada, May. 28-30, 1997: 233~238.
[10] De Castro. An evolutionary immune network for data clustering. VI Brazilian Symposium on Neural Networks (SBRN'00), Brazil, Jan, 22-25, 2000: 84~89.
[11] De Castrol, and Von Zuben. Immune Neural Network Models: Theoretical and Emprical Comparisons. International Journal of Computational Intelligence and Applications, 2001, 1(3): 239~257.
[12] Timmis J, Neal M.A resource limited artificial immune system for data analysis. Knowledge Based Systems, 2001, 14(3-4): 121~130.
[13] Watkins A, Timmis J, and Boggess L. Artificial Immune Recognition System (AIRS): An Immune-Inspired Supervised Learning Algorithm. Genetic Programming and Evolvable Machines, 2004(5): 291~317.
[14] Watkins A, and Timmis J. Artificial Immune Recognition System (AIRS): Revisions and Refinements. Proceeding of ICARIS2002, Springer Verlag, 2002: 173~181.
[15] Watkins A, and Timmis J. Exploiting the Parallelism Inherent in AIRS, an Artificial Immune Classifier. Proceeding of ICARIS2004, Springer Verlag, 2004: 427~438.
[16] De Castro L N, Von Zuben F J. Artificial immune systems: a new approach to pattern recognition. In: L Alonso, J Corchado. C Fyfe, eds. Artificial Neural Networks in Pattern Recognition. University of Paisley, UK, 2002.
[17] Knight T and Timmis J. AINE: An Immunological Approach to Data Mining. In N Cercone, T Lin and Xindong Wu, editors, IEEE International Conference on Data Mining, San Jose, CA. USA, December 2001, 297~304.
[18] Neal M. An Artificial Immune System for Continuous Analysis of Time-varying Data. In: Timmis, J, Bentley, P. (eds.) In: Proc. of the 1st Int. Conf. Artificial Immune System, 2002: 76~85.
[19] Gong Maoguo, Jiao Lichen, and Du Haifeng. Mutiobjective immune algorithm with nondom inated neighbor-based selection. Evolutionary Computation, 2008, 16(2): 255~265.
[20]左兴权,莫宏伟,范玉顺.参数化活动调度及其混合免疫调度算法.哈尔滨工程大学学报, 2006, 27(增): 257~263.
[21]公茂果,焦李成,杜海峰,等.用于约束优化的人工免疫相应进化策略.计算机学报, 2007, 30(1): 37~47.
[22]马文萍,焦李成,张向荣,等.基于量子克隆优化的SAR图像分类.电子学报, 2007, 35(12): 2241~2246.
[23] Freitas A A, and Timmis J. Revisiting the foundations of artificial immune systems for data mining. IEEE transactions on evolutionary computation, 2007, 11(4): 521~540.
[24] De Castro. The Immune Response of an Artificial Immune Network (AINet). Canberra: IEEE Congress on Evolutionary Computation, 2003:8~12.
[25]钟燕飞,张良培,李平湘.基于多值免疫网络的多光谱遥感影像分类.计算机学报, 2007, 30(12): 2181~2188.
[26] Zhong Yangfei, Zhang Liangpei, and Gong Jianya, et al.. A supervised artificial immune classifier for remote-sensing imagery. IEEE Transactions on Geosciences and Remote Sensing, 2007, 45 (12): 3957~3966.
[27] Colaco C. Acquired Wisdom in Innate Immunity. Immunology Today. 1998, 19(1):50.
[28] Medzhitov R, and Janeway C A. Innate Immunity: Impact on the Adaptive Immune Response. Current Opinion in Immunology. 1997, (9): 4~9.
[29] Zinkernagel R M, and Kelly J. How Antigen Influences Immunity. The Immunologist. 1997, 4/5: 114~120.
[30]童健华.基于人工免疫网络的聚类分析.中山大学, 2008: 54.
[31] Jerne N K. The Immune System. Scientific American. 1973, 229(1): 52~60.
[32] Perelson A S, Hightower, RForrest S. Evolution and Somatic Learning of V-Region Genes, Research in Immunology, 1996, 147: 202~208.
[33] De Castro L N, Von Zuben F J. The clonal selection algorithm with engineering application. Proc. Of GECCO’00, Workshop on Artificial Immune Systems and Their Applications, 2000: 36~37.
[34] Kevin Leung, France Cheong, and Christopher Cheong. Generating Compact Classifier Systems Using a Simple Artificial Immune System. IEEE Transactions on System, Man and Cybernetics, Part B, 2007, 10(5): 1344~1356.
[35] Du Haifeng, Jiao Licheng, and Wang Sunan. Clonal operator and antibody clone algorithms. Proceedings of the First International Conference on Machine Learning and Cybernetics, Beijing, 2002: 506~510.
[36] Clausi D A and Yue B. Comparing concurrence probabilities and Markov fields for texture analysis of SAR sea ice image. IEEE Transactions on Geosciences and Remote Sensing, 2004, 42(1): 215~228.
[37] Mazidah puteh FTMSK and Khairuddin Omar FTSM. Classifying heterogeneous data with artificial immune system. International Symposium Information Technology, Shanghai, China, Dec. 21-22, 2008, 3: 1~5.
[38] Adnan Acan, and Ahmet Unveren. A Memory-Based Colonization Scheme for Particle Swarm Optimization. Evolutionary Computation 2009, IEEE Congress on 18-21May 2009: 1965~1972.
[39]丛林,焦李成,沙宇恒.正交免疫克隆粒子群多目标优化问题.电子与信息学报. 2008, 10, 30(10): 2320~2324.
[40] Kosmas V. Deligkaris, Zaharias D. Zaharis, and Dimaitra G. Kampitaki. Thinned Planar Array Design Using Boolean PSO With Velocity Mutation. IEEE TRANSACTION ON MAGNETICS, 2009, 45(3): 1490~1493.
[41] Chen Ailing, and Guo Qiang. An Effective Hybrid Optimization Algorithm based on Self-adaptive Particle Swarm Optimization Algorithm and Artificial Immune Clone Algorithm. Fourth International Conference on Natural Computation. IEEE 2008: 129~132.
[42] Ge Hongwei, Sun Liang, Liang and Yanchun. An Effective PSO and AIS-Based Hybrid Intelligent Algorithm for Job-Shop Scheduling. IEEE TRANSACTIONSON SYSTEMS, MAN, AND CYBERNETICS—PART A: SYSTEMS AND HUMANS, 2008, 38(2): 358~368.
[43] Shi Y, and Eberhart R. Empirical study of particle swarm optimization. Proceedings of congress on evolutionary computation, 1999: 1945~1950.
[44] Zhan ZhiHui, Zhang Jun, Li Yun, and Henry Chung. Adaptive Particle Swarm Optimization. IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, 2009: 1~20.
[45] Liu Bo, Wang Ling, and Jin YiHui. Improved particle swarm optimization combined with chaos, Chaos, Solitons and Fractals, 2005: 1261~1271.
[46] Blake C L, and Merz C J. UCI Repository of Machine Learning Databases. [Online]. Available: http://archive.ics.uci.edu/ml/datasets.html.
[47]潘晓英.多智能体社会协同进化模型及其算法研究.西安电子科技大学, 2008, 12: 150~152.
[48] Tien Dung Do, Siu Cheung Hui, and Fong A. C. M.. Associative Classification With Artificial Immune System. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, APRIL 2009, 13(2): 217~228.
[49]宋媛媛.人工免疫算法研究及其在数据挖掘上的应用.青岛大学, 2008: 22~23.
[50] Agrawal R, Imiclinski T, and Swami A. A performance perspective. IEEE Transknowledge and Data Enginnering, 1993, 5: 914~925.
[51]武建华,沈均毅,王元元.一种改进的关联分类方法.计算机工程, 2009, 35(9): 63~65.