基于商空间的构造性学习算法研究
|
摘要
粒计算的目的是建立一种体现人类问题求解特征的一般模型，其基本思想是在不同的粒度层次上进行问题求解。粒是粒计算的最基本的原语，它是一簇点(对象、物体)由于难以区别，或相似、或接近、或某种功能而结合在一起所构成的。
从粒计算的角度来看，问题求解的商空间理论用拓扑来描述论域的结构、用等价关系来完成粒化，借助于自然映射实现在不同粒度层次上的转换。
商空间理论作为一种问题求解的方法，有着坚实的理论基础，它采用多侧面、多角度的问题求解方法，可以在解决问题时缩小求解难度，降低计算量。商空间理论把定性的思维和定量的分析有机地统一起来，合理地对复杂问题进行粒度描述，把复杂问题分解为可求解的、不同粒度的学习规则，然后再合成相关的规则，最终得到复杂问题的综合规则。
传统的基于距离或相似度的聚类算法一般都基于“特征矢量”的方法，这种方法并不适宜用来处理个体数据。往往由于进行了数据矢量转化操作而造成信息丢失，最终可能会导致聚类结果的不准确。
覆盖方法最优之处在于覆盖领域完全真实地反映了样本的分布情况，本文中分析了覆盖算法中需要进一步研究的三个问题：第一个是对该算法识别的正确率与泛化能力之间矛盾的解决，第二个是如何改进覆盖方法，第三是如何提高泛化能力。
基于商空间理论，作者提出了对于覆盖算法的改进思想，它能在基本保持分类能力的前提下，提高分类的速度和识别的精度。从对平面双螺旋线数据的实验结果可以看出，与交叉覆盖聚类算法对比，改进的算法的正确识别率显著提高，随着训练样本数据的增加，拒识率为0，若不计训练时间，那么改进的算法是可行的。
作为一种正在兴起的智能计算方法，商空间理论和覆盖算法本身还有许多地方有待发展和完善。
As an emerging research sub-field of artificial intelligence, granular computing, whose philosophy is to implement the problem solving at different levels of granularity, aims to establish much more general model reflecting the process of human problem solving. Granule, a clump of points (objects) drawn together by indistinguishability, similarity, proximity or functionality, is the primitive notion of granular computing.
Quotient space theory of problem solving is generalized from two directions, namely the structure of the universe of discourse and granulation criteria. In the light of granular computing quotient space theory of problem solving exploits topology to describe the structure of the universe of discourse, and utilizes equivalence relation to implement granulation, and relies on the natural mapping to realize the translations among different levels of granulariy.
As a method of problem solving, quotient space theory, based on substantial theory, considering the problem from different aspects and multi-hierarchy in the process of problem solving, is a kind of powerful tool in that it can decrease the difficulty of the problem and reduce the computational cost. Unifying the quantitative analysis and the qualitative analysis by utilizing quotient space theory, complex problems are represented by different granules based quotient space. After learning rules of different granules achieved, integrate rules of the complex problem can be gained by composing relative rules.
The traditional clustering algorithms based on distance or similarity are vector-based, these methods are unfit for individual behavioral data, there will be a lot of information lost and will lead to the clustering inaccurate.
Directed by the theory of quotient space, a improved algorithm of covering algorithm is presented. It can keep the sorting accuracy and cut down the occupying of memory and the cost of data collecting. The simulation experiment about dual spiral data shows the feasibility of the improved alternative coving algorithm proposed above.
As a means of the rising artificial intelligence, quotient space theory and covering algorithm itself need more development and consummate.
从粒计算的角度来看，问题求解的商空间理论用拓扑来描述论域的结构、用等价关系来完成粒化，借助于自然映射实现在不同粒度层次上的转换。
商空间理论作为一种问题求解的方法，有着坚实的理论基础，它采用多侧面、多角度的问题求解方法，可以在解决问题时缩小求解难度，降低计算量。商空间理论把定性的思维和定量的分析有机地统一起来，合理地对复杂问题进行粒度描述，把复杂问题分解为可求解的、不同粒度的学习规则，然后再合成相关的规则，最终得到复杂问题的综合规则。
传统的基于距离或相似度的聚类算法一般都基于“特征矢量”的方法，这种方法并不适宜用来处理个体数据。往往由于进行了数据矢量转化操作而造成信息丢失，最终可能会导致聚类结果的不准确。
覆盖方法最优之处在于覆盖领域完全真实地反映了样本的分布情况，本文中分析了覆盖算法中需要进一步研究的三个问题：第一个是对该算法识别的正确率与泛化能力之间矛盾的解决，第二个是如何改进覆盖方法，第三是如何提高泛化能力。
基于商空间理论，作者提出了对于覆盖算法的改进思想，它能在基本保持分类能力的前提下，提高分类的速度和识别的精度。从对平面双螺旋线数据的实验结果可以看出，与交叉覆盖聚类算法对比，改进的算法的正确识别率显著提高，随着训练样本数据的增加，拒识率为0，若不计训练时间，那么改进的算法是可行的。
作为一种正在兴起的智能计算方法，商空间理论和覆盖算法本身还有许多地方有待发展和完善。
As an emerging research sub-field of artificial intelligence, granular computing, whose philosophy is to implement the problem solving at different levels of granularity, aims to establish much more general model reflecting the process of human problem solving. Granule, a clump of points (objects) drawn together by indistinguishability, similarity, proximity or functionality, is the primitive notion of granular computing.
Quotient space theory of problem solving is generalized from two directions, namely the structure of the universe of discourse and granulation criteria. In the light of granular computing quotient space theory of problem solving exploits topology to describe the structure of the universe of discourse, and utilizes equivalence relation to implement granulation, and relies on the natural mapping to realize the translations among different levels of granulariy.
As a method of problem solving, quotient space theory, based on substantial theory, considering the problem from different aspects and multi-hierarchy in the process of problem solving, is a kind of powerful tool in that it can decrease the difficulty of the problem and reduce the computational cost. Unifying the quantitative analysis and the qualitative analysis by utilizing quotient space theory, complex problems are represented by different granules based quotient space. After learning rules of different granules achieved, integrate rules of the complex problem can be gained by composing relative rules.
The traditional clustering algorithms based on distance or similarity are vector-based, these methods are unfit for individual behavioral data, there will be a lot of information lost and will lead to the clustering inaccurate.
Directed by the theory of quotient space, a improved algorithm of covering algorithm is presented. It can keep the sorting accuracy and cut down the occupying of memory and the cost of data collecting. The simulation experiment about dual spiral data shows the feasibility of the improved alternative coving algorithm proposed above.
As a means of the rising artificial intelligence, quotient space theory and covering algorithm itself need more development and consummate.
引文
[1] Bo Zhang and Ling Zhang, Theory and Application of Problem Solving[M], Tsinghua University Publisher. 1990. 《问题求解的理论及应用》，清华大学出版社，1990
[2] Z. Pawlak, Rough Sets: Theorencal Aspects of Reasonging about Data[M], Kluwer Academic Publishers, Dordrecht, 1991
[3] McCulloch W.S., Pitts W. A logical calculus of the ideas immanent in nervous activity[J]. Bulletin of athematical Biophysics, 1943, 5:115-133
[4] Rujan P, Marchand M. Ageometric approach to learning in neural networks[J]. In: Proceedings of the International Joint Conference on Neural Networks. Washington, DC:IEEE TAB Neural Network Committee, 1989(2),105-110
[5] Ramacher U, Wesseling M. A geometrical approach to neural neywork design [J]. In: Proceedings of the International Joint Conference on Neural Networks. Washington, DC:IEEE TAB Neural Network Committee, 1989(2).147-154
[6] 张铃，吴福朝，张钹．多层前馈神经网络的学习和综合算法[J]．软件学报，1995，6(7)，440-448
[7] 张铃，张钹．MP神经元模型的几何意义及其应用[J]．软件学报，1998，9(5)：334-338
[8] 张铃，张钹，殷海风．多层前向网络的交叉覆盖设计算法[J]．软件学报，1999，10(7)，737-742
[9] Zadeh L.A. Towards a theow of fuzzy information granulation and its centrality in human reasoning and fuzzy logic [J]. Fuzzy Sets and Systems, 1997(90): 111-127
[10] Lin. T.Y Granular computing, announcement of the BISC special interest group on granular computing[J]. 1997. http://www.cs.uregina.ca/～yyao/grc
[11] Yao, Y.Y. Granular computing:basic issues and possible solutions [C]. Proceedings of the 5th Joint Conference on Information Sciences. 2000: 186-189
[12] Yao. Y.Y. A partition model of granular computing[J].2004 http://www.cs.uregina.ca/～yyao/GrC/
[13] Zadeh. L.A Some reflections on soft computing, granular computing and their roles in the conception, design and utilization of information intelligent systems [J]. Soft Computuig. 1998(2),23-25
[14] Yao. Y.Y. Granular computing[J].2005 http://www.cs.ureguia.ca/～yyao/GrC/
[15] Zadeh. L.A. Fuzzy sets [J]. Information and ontrol. 1965, 8: 338-353
[16] Zadeh L. A. Announcement of GrC[J].1997 http://www.cs.uregina.ca/～yyao/GrC/
[17] Hobbs. J.R. Granulariy [C]. Proceedings of the Ninth International Joint Conference on Artificial Intelligence,1985:432-435
[18] Pawlak. Z. Rough sets [J]. International Journal of Computer and Information Sciences, 1982(11): 341-356
[19] Pawlak, Z. Rough Sets: Theoretical aspects of reasoning about data[M]. Kluwer Academic Publishers. Boston, 1991
[20] 刘清．Rough集及Rough推理[M]．北京：科学出版社，2001
[21] 张燕平，张铃，夏莹．商空间理论与粗糙集的比较[J]．微机发展，2004，14(10)，21-24
[22] 张铃，张拔．模糊商空间理论(模糊粒度计算方法)[J]．2003，14(4)，770-776
[23] M.J.A. Berry, G. Linoff. Data Mining Techniques[J]. New York: Wilery, 1997
[24] J. Han, M. Kamber, Data Mining Concepts and Techniques[M].北京：高等教育出版，2001
[25] Zadeh. L.A. Fuzzy logic=computing with words [J]. IEEE Transactions on Fuzzy System 1996, 4, 103-111
[26] 方开泰，潘恩沛．聚类分析[M]．北京：地质出版社，1982
[27] 吴涛，张旻，张燕萍等．交叉覆盖网络的球形领域构造与功能函数[J]．计算机工程与应用．2003，16，43-45
[28] 张铃，张拔，神经网络中BP算法分析[J]，模式识别与人工智能，1994，7(3)，191-195
[29] 张铃，张拔，人工神经网络理论及应用[M]．杭州：浙江科学技术出版社，1997
[30] 张铃，张钹．多层反馈神经网络的FP学习和综合算法[J]．软件学报，1997，8 (4)，252-258
[31] 张铃．关于前向神经网络的设计问题[J]．安徽大学学报．1998，22(3)，31-41
[32] 张铃，张钹．神经网络学习中“附加样本”的技术[J]．计算机学报，1998，5，131-141
[33] 陶品，张钹，叶榛．构造型神经网络双交叉覆盖增量学习算法[J]．软件学报，2003，14(2)，194-201
[34] 陶品，张钹，叶榛．可继续学习的构造型神经网络构造算法[J]．计算机工程与应用．2003，8，10-13
[35] 张玲．支持向量机理论与基于规划的神经网络学习算法[J]．计算机学报．2001，24 (2)，113-118
[36] 张铃．基于核函数的SVM机与三层前向神经网络的关系[J]．2002，25(7)，696-700
[37] 徐峰，李旸，吴涛等．基于核函数的构造型网络二分覆盖算法[J]．计算机工程与应用．2004，9，21-23
[38] 赵姝，张燕平，张媛等．基于交叉覆盖算法的改进算法—核平移覆盖算法[J]．微机发展．2004，14(11)，1-3
[39] 张旻，张铃，程家兴．一种加权的构造型神经网络覆盖算法设计与实现[J]．2005，31(2)，36-38
[40] 张燕平，张铃，吴涛．机器学习中的多侧面递进算法MIDA[J]．电子学报．2005，33(2)，327-331
[41] 周瑛，张铃．基于概率的覆盖算法的研究．计算机技术与发展[J]．2006，16(3)，29-31
[42] 杨涛，李龙澍．基于粗糙集的交叉覆盖神经网络研究[J]．微机发展．2005，15(6)，22-24
[43] 吴涛，张玲，张燕平．机器学习中的核覆盖算法[J]．计算机学报，2005，28(8)，1294-1301
[44] J. Han, M. Kamber, Data Mining Concepts and Techniques[M].北京：高等教育出版，2001
[2] Z. Pawlak, Rough Sets: Theorencal Aspects of Reasonging about Data[M], Kluwer Academic Publishers, Dordrecht, 1991
[3] McCulloch W.S., Pitts W. A logical calculus of the ideas immanent in nervous activity[J]. Bulletin of athematical Biophysics, 1943, 5:115-133
[4] Rujan P, Marchand M. Ageometric approach to learning in neural networks[J]. In: Proceedings of the International Joint Conference on Neural Networks. Washington, DC:IEEE TAB Neural Network Committee, 1989(2),105-110
[5] Ramacher U, Wesseling M. A geometrical approach to neural neywork design [J]. In: Proceedings of the International Joint Conference on Neural Networks. Washington, DC:IEEE TAB Neural Network Committee, 1989(2).147-154
[6] 张铃，吴福朝，张钹．多层前馈神经网络的学习和综合算法[J]．软件学报，1995，6(7)，440-448
[7] 张铃，张钹．MP神经元模型的几何意义及其应用[J]．软件学报，1998，9(5)：334-338
[8] 张铃，张钹，殷海风．多层前向网络的交叉覆盖设计算法[J]．软件学报，1999，10(7)，737-742
[9] Zadeh L.A. Towards a theow of fuzzy information granulation and its centrality in human reasoning and fuzzy logic [J]. Fuzzy Sets and Systems, 1997(90): 111-127
[10] Lin. T.Y Granular computing, announcement of the BISC special interest group on granular computing[J]. 1997. http://www.cs.uregina.ca/～yyao/grc
[11] Yao, Y.Y. Granular computing:basic issues and possible solutions [C]. Proceedings of the 5th Joint Conference on Information Sciences. 2000: 186-189
[12] Yao. Y.Y. A partition model of granular computing[J].2004 http://www.cs.uregina.ca/～yyao/GrC/
[13] Zadeh. L.A Some reflections on soft computing, granular computing and their roles in the conception, design and utilization of information intelligent systems [J]. Soft Computuig. 1998(2),23-25
[14] Yao. Y.Y. Granular computing[J].2005 http://www.cs.ureguia.ca/～yyao/GrC/
[15] Zadeh. L.A. Fuzzy sets [J]. Information and ontrol. 1965, 8: 338-353
[16] Zadeh L. A. Announcement of GrC[J].1997 http://www.cs.uregina.ca/～yyao/GrC/
[17] Hobbs. J.R. Granulariy [C]. Proceedings of the Ninth International Joint Conference on Artificial Intelligence,1985:432-435
[18] Pawlak. Z. Rough sets [J]. International Journal of Computer and Information Sciences, 1982(11): 341-356
[19] Pawlak, Z. Rough Sets: Theoretical aspects of reasoning about data[M]. Kluwer Academic Publishers. Boston, 1991
[20] 刘清．Rough集及Rough推理[M]．北京：科学出版社，2001
[21] 张燕平，张铃，夏莹．商空间理论与粗糙集的比较[J]．微机发展，2004，14(10)，21-24
[22] 张铃，张拔．模糊商空间理论(模糊粒度计算方法)[J]．2003，14(4)，770-776
[23] M.J.A. Berry, G. Linoff. Data Mining Techniques[J]. New York: Wilery, 1997
[24] J. Han, M. Kamber, Data Mining Concepts and Techniques[M].北京：高等教育出版，2001
[25] Zadeh. L.A. Fuzzy logic=computing with words [J]. IEEE Transactions on Fuzzy System 1996, 4, 103-111
[26] 方开泰，潘恩沛．聚类分析[M]．北京：地质出版社，1982
[27] 吴涛，张旻，张燕萍等．交叉覆盖网络的球形领域构造与功能函数[J]．计算机工程与应用．2003，16，43-45
[28] 张铃，张拔，神经网络中BP算法分析[J]，模式识别与人工智能，1994，7(3)，191-195
[29] 张铃，张拔，人工神经网络理论及应用[M]．杭州：浙江科学技术出版社，1997
[30] 张铃，张钹．多层反馈神经网络的FP学习和综合算法[J]．软件学报，1997，8 (4)，252-258
[31] 张铃．关于前向神经网络的设计问题[J]．安徽大学学报．1998，22(3)，31-41
[32] 张铃，张钹．神经网络学习中“附加样本”的技术[J]．计算机学报，1998，5，131-141
[33] 陶品，张钹，叶榛．构造型神经网络双交叉覆盖增量学习算法[J]．软件学报，2003，14(2)，194-201
[34] 陶品，张钹，叶榛．可继续学习的构造型神经网络构造算法[J]．计算机工程与应用．2003，8，10-13
[35] 张玲．支持向量机理论与基于规划的神经网络学习算法[J]．计算机学报．2001，24 (2)，113-118
[36] 张铃．基于核函数的SVM机与三层前向神经网络的关系[J]．2002，25(7)，696-700
[37] 徐峰，李旸，吴涛等．基于核函数的构造型网络二分覆盖算法[J]．计算机工程与应用．2004，9，21-23
[38] 赵姝，张燕平，张媛等．基于交叉覆盖算法的改进算法—核平移覆盖算法[J]．微机发展．2004，14(11)，1-3
[39] 张旻，张铃，程家兴．一种加权的构造型神经网络覆盖算法设计与实现[J]．2005，31(2)，36-38
[40] 张燕平，张铃，吴涛．机器学习中的多侧面递进算法MIDA[J]．电子学报．2005，33(2)，327-331
[41] 周瑛，张铃．基于概率的覆盖算法的研究．计算机技术与发展[J]．2006，16(3)，29-31
[42] 杨涛，李龙澍．基于粗糙集的交叉覆盖神经网络研究[J]．微机发展．2005，15(6)，22-24
[43] 吴涛，张玲，张燕平．机器学习中的核覆盖算法[J]．计算机学报，2005，28(8)，1294-1301
[44] J. Han, M. Kamber, Data Mining Concepts and Techniques[M].北京：高等教育出版，2001