BP算法并行化及在数据挖掘中的应用研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
数据挖掘是帮助人们在海量数据中发现信息和知识的工具。近年来数据挖掘技术成了商业智能的核心技术,被广泛应用到了诸多领域,引起了学术界极大的关注。数据挖掘是一个决策支持过程,技术基础是人工智能。目前数据挖掘主要利用人工智能中的一些的算法和技术,包括人工神经网络技术等来进行预测、模式识别、分类和聚类分析。本文主要针对神经网络作为数据挖掘的一种手段,在商业行为趋势预测方面的应用研究。
    BP(Back Propagation)算法, 即误差反传训练算法,以其良好的非线形映射逼近能力和泛化能力以及易实现性成为人工神经网络应用最广泛的训练算法。但是BP算法也有其明显的缺陷,即训练速度慢、容易陷入局部极值等。通过反复的实验研究和分析发现,通常为了避免初始权值过大,导致训练伊始就使网络处于S型函数的饱和区,使训练陷入局部极小,在选取初始权值的时候,通常选取较小随机数。如果选取的权值范围距离目标极值区域很远,搜索空间越大,目标极值区域越窄,搜索时间就越长,训练速度就越缓慢。针对这种情况,本文提出了首先通过不等量划分权值搜索空间获取全局最小极值区域,在此基础上均衡分配训练样本集进行并行训练的二次并行搜索策略,实验证明这种新的并行算法能在迅速找到全局最小的基础上大大提高收敛速度,得到优于一般并行算法的加速比。此并行算法实现简单有效,能更好地应用于现实问题。
    本文选用通过商用网络连接起来的PC机,以及并行虚拟机PVM和分布式操作系统LINUX,共同构成了一个机群系统作为并行计算平台。在并行程序的模型上选用了Master/Slave模型。算法并行化方式采用了将训练数据平均分配到各节点机的数据并行方式。
     最后,讨论了BP算法在数据挖掘中的应用。将此策略应用于医药物流系统的销售预测,建立了基于并行BP算法的物流销售预测模型。本文详细地讨论了销售预测模型的样本的选择和预处理方法、网络拓扑结构的选定,如输入输出层以及隐含层数和隐含层节点数的选择、网络参数的选择等。最后实现了一个可视化的预测系统,可以在此基础上方便的选择不同训练集重新训练网络,并将训练好的网络用于真实的销售趋势预测,取得了令人满意的效果。
Data mining technology is used to help people finding the information and knowledge in the data. It has become the core technology of the intelligence commerce. It has been widely used in many areas and drawn the attention of the whole academe. Some algorithms and techniques of artificial intelligence, including neural networks, have been applied in data mining to do prediction, pattern recognition, classification and Clustering. One important application of neural network in data mining is sales trend prediction.
     BP (Back Propagation) algorithm is the most popular training algorithm in applications for its non-linear mapping approach capability and robustness. However, it is known to have some defects, such as converging slowly and immersing in local vibration frequently. Generally, we often choose small random initial weights to void training process immerse in local minimum. If it is far from chosen range of weights to goal area, the search space is wider, goal area is narrower, search time is longer and training speed is slower. To solve this problem, the paper proposed a solution named two times parallel search strategy, that is, obtaining global minimum area by dividing weight space unequally at first and then training network using data parallelism. The experiment results show that the strategy reaches global minimum soon and converges at high rate, especially to a large training samples.
     The hardware platform is PC connected with LAN. The software platform is PVM and LINUX. They construct the whole PC-cluster system. The parallel program model is master/slave model. The algorithm assign data set to each node realizes the data-parallel.
     The application of BP algorithm in data mining is discussed in this paper. The strategy mentioned is applied to sales prediction of medicine logistics system and a sales prediction model based on parallel algorithm is established. How to choose and preprocess training set and how to select network topology is proposed in detail in this paper. At last, a visual prediction system is realized to achieve prediction result, which makes prediction works easy.
引文
[1] Chua Boon Lay; Khalid, M.; Yusof, R.; An enhanced intelligent database engine by neural network and data mining ;TENCON 2000. Proceedings , Volume: 2 , 2000 ,Page(s): 518 -523 vol.2
    [2] Jovanovic, N.; Milutinovic, V.; Obradovic, Z.; Foundations of predictive data mining; Neural Network Applications in Electrical Engineering, 2002. NEUREL '02. 2002 6th Seminar on , 2002 ,Page(s): 53 –58
    [3] Ampazis, N.; Perantonis, S.J.; Levenberg-Marquardt algorithm with adaptive momentum for the efficient training of feedforward networks; Neural Networks, 2000. IJCNN 2000, Proceedings of the IEEE-INNS-ENNS International Joint Conference on , Volume: 1 , 2000 ,Page(s): 126 -131 vol.1
    [4] Atluri, V.; Chih-Cheng Hung; Coleman, T.L.; An artificial neural network for classifying and predicting soil moisture and temperature using Levenberg-Marquardt algorithm; Southeastcon '99. Proceedings. IEEE , 1999 ,Page(s): 10 –13
    [5] Wilamowski, B.M.; Iplikci, S.; Kaynak, O.; Efe, M.O.; An algorithm for fast convergence in training neural networks; Neural Networks, 2001. Proceedings. IJCNN '01. International Joint Conference on , Volume: 3 , 2001 ,Page(s): 1778 -1782 vol.3
    [6] Mu-Song Chen; A comparative study of learning methods in tuning parameters of fuzzy membership functions; Systems, Man, and Cybernetics, 1999. IEEE SMC '99 Conference Proceedings. 1999 IEEE International Conference on , Volume: 3 , 1999 ,Page(s): 40 -44 vol.3
    [7] Yanlai Li; Kuanquan Wang; Zhang, D.; Step acceleration based training algorithm for feedforward neural networks; Pattern Recognition, 2002. Proceedings. 16th International Conference on , Volume: 2 , 2002 ,Page(s): 84 -87 vol.2
    [8] Riedmiller, M.; Braun, H.; A direct adaptive method for faster backpropagation learning: the RPROP algorithm; Neural Networks, 1993., IEEE International Conference on , 1993 ,Page(s): 586 -591 vol.1
    [9] Shamsuddin Ahmed , James Cross; A Tourist Growth Model to Predict Accommodation Nights Spent in Australian Hotel Industry; Presented at SIRC 99-The 11th Annual Colloquium of the Spatial Information Research Centre,University of Otago, Dunedin, New Zealand,December 13-15th 1999 ,Available:http://divcom.otago.ac.nz/sirc/webpages/99Ahmed.pdf
    [10] Onoda, T.; Neural network information criterion for the optimal number of hidden units; Neural
    
    
    Networks, 1995. Proceedings., IEEE International Conference on , Volume: 1 , Nov/Dec 1995 ,Page(s): 275 -280 vol.1
    [11] Murata, N.; Yoshizawa, S.; Amari, S.; Network information criterion-determining the number of hidden units for an artificial neural network model; Neural Networks, IEEE Transactions on , Volume: 5 Issue: 6 , Nov 1994 ,Page(s): 865 –872
    [12] Weishui Wan; Hirasawa, K.; Jinglu Hu; Chunzhi Jin; A new method to prune the neural network; Neural Networks, 2000. IJCNN 2000, Proceedings of the IEEE-INNS-ENNS International Joint Conference on , Volume: 6 , 2000 ,Page(s): 449 -454 vol.6
    [13] Daohang Sha, Vladimir B; On-line adaptive learning rate bp algorithm for mlp and application to an identification problem; Available:
    http://sdmc.lit.org.sg:8080/iaamsad/papers/JACS_1999.pdf
    [14] Gordon (gordon@cs.curtin.edu.au); Neural Network Classifiers for GIS Data: Improved Search Strategies; GERMAN, Curtin University of Technology, School of Computing, Kent Street, Perth, Western Australia; Available:
    http://www.geovista.psu.edu/sites/geocomp99/Gc99/093/abs99-093.htm
    [15] Jaesoo Kim; A New Perspective for Data Mining Problems; Available:
    http://www.ssgrr.it/en/ssgrr2001/papers/Jaesoo Kim.pdf
    [16] 刘晋刚,韩燮,李华玲.BP神经网络改进算法的应用.华北工学院学报.2002,23(6):449-451
    [17] 王继成.一种新的神经网络学习算法.计算机工程与科学.2000,22(3):6-9,17
    [18] 司捷,周贵安,李函,韩英铎.基于梯度监督学习的理论与应用(Ⅰ)――基本算法.清华大学学报(自然科学版).1997,37(7):71-73
    [19] 司捷,周贵安,李函,韩英铎.基于梯度监督学习的理论与应用(Ⅱ)――训练机制.清华大学学报(自然科学版).1997,37(9):104-107
    [20] 高雪鹏,从爽. BP网络改进算法的性能对比研究.控制与决策.2001,16(3):167-171
    [21] 金峤,方帅,阎石,李宏男. BP网络模型的改进方法综述.沈阳建筑工程学院学报(自然科学版).2001,17(3):197-199,205
    [22] 吴成东,王长涛.人工神经元BP网络在股市预测方面的应用.控制工程.2002,9(3):48-50,57
    [23] 王越,曹长修.BP算法在HIS药品计划系统中的应用研究.计算机工程与设计.2002,23(4):19-22
    [24] 向国全.前向网络BP算法在数据挖掘中的运用.河南大学学报(自然科学版).1999,29(3):42-45
    [25] 张新龙,朱友芹,夏国平.基于快速BP算法的城市可持续发展综合评价.计算机应用研究.2002, (7):16-18
    [26] 向国全,董道珍.BP模型中的激励函数和改进的网络训练法.计算机研究与发
    
    
    展.1997,34(2):113-117
    [27] Neural Network Toolbox User’s Guide.The Math Works.Inc.2000
    [28] Li Jun; Li Yuanxiang; Xu Jingwen; Zhang Jinbo; Parallel training algorithm of BP neural networks;Intelligent Control and Automation, 2000. Proceedings of the 3rd World Congress on , Volume: 2 , 2000;Page(s): 872 -876 vol.2
    [29] Syeda, M.; Yan-Qing Zhang; Yi Pan; Parallel granular neural networks for fast credit card fraud detection;Fuzzy Systems, 2002. FUZZ-IEEE'02. Proceedings of the 2002 IEEE International Conference on , Volume: 1 , 2002;Page(s): 572 –577
    [30] Yamamori, K.; Abe, T.; Horiguchi, S.; Two-stage parallel partial retraining scheme for defective multi-layer neural networks;High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on , Volume:2 , 2000;Page(s): 642 -647 vol.2
    [31] 冯百鸣,经彤.BP算法并行程序的自动生成与并行效率预测.电光与控制.1997(2):1-5
    [32] 余英泽,杨大春,廖里,陈艺华.基于VC++(MFC)的并行神经网络学习系统的设计及实现.电脑开发与应用.2000,13(8):6-8
    [33] 任立勇,卢显良.基于串-并行计算BP网络拓扑结构的研究与实现.电子科技大学学报.2000,29(2):197-200
    [34] 高曙.基于机群的并行BP算法的设计与实现.武汉理工大学学报(交通科学与工程版).2002,26(5):589-591
    [35] 刘皓,魏平,肖先赐.面向特定结构的几种BP并行算法及比较.系统工程与电子技术.2000,22(1):70-76
    [36] 刘鹰,赵琳.神经网络BP算法的改进和仿真.计算机仿真.1999,16(3):12-14
    [37] 章锦文,马远良.神经网络算法的并行实现.计算机工程与设计.1994,16(4):16-21
    [38] 袁曾任.人工神经元网络及其应用.清华大学出版社.1999.ISBN:7-302-03580-6
    [39] Christian Igel and Michael Hüsken. Empirical Evaluation of the Improved Rprop Learning Algorithm. Neurocomputing 50(C):105--123, 2003.
    [40] M. Riedmiller, Advanced supervised learning in multi-layer perceptrons—from backpropagation to adaptive learning algorithms, Comput. Standards Interfaces 16 (5) (1994) 265–278.
    [41] W. SchiJmann, M. Joost, R. Werner, Comparison of optimized backpropagation algorithms, in: M.Verleysen (Ed.), Proceedings of the European Symposium on Arti-cial Neural Networks, ESANN ’93, Brussels, 1993, D-Facto, Brussels, pp. 97–104.
    [42] F.M. Silva, L.B. Almeida, Speeding up backpropagation, in: R. Eckmiller (Ed.), Advanced Neural Computers, North-Holland, Amsterdam, 1990, pp. 151–158.
    
    [43] 许东,吴铮.基于MATLAB6.x的系统分析与设计.西安电子科技大学出版社.2002.9.ISBN:7-5606-0646-6
    [44] Christian Igel and Michael Hüsken. Improving the Rprop Learning Algorithm. Proceedings of the Second International Symposium on Neural Computation,NC’2000,pp.115--121, 2002.
    [45] Jiawei Han, Micheline Kambr. Data Mining Concepts and Techniques. Higher Education Press.2001.ISBN:7-04-010041-X
    [46] Agrawal R. Psaila G.. Wimmers E. L. and Zait M.· Querying shapes of histories.· In Proc. of the VLDB Conference.·1995
    [47] Jay-Louise Weldon.· Data mining and visualization. ·Database Programming and Design,· 9(5):21~24· May 1996
    [48] 王珊等编著.数据仓库技术与分联机分析处理.北京.科学出版社.1998:1-17
    [49] Piatetsky-shapiro G. Data mining and Knowledge Discovery in Business Databases. ISMIS’96,56-57
    [50] 陈文伟编著. 智能决策技术. 北京. 电子工业出版社.1998.5-6,114-149
    [51] 陈文伟、邓苏、张维明. 数据挖掘与知识发现综述. 计算机世界报. 24期专题版。1997
    [52] 李水平、陈意云、黄刘生. 数据采掘技术回顾. 小型微型计算机系统. 1998,19(4)
    [53] Barry Wilkinson, Michael Allen 著·陆鑫达 等译·并行程序设计·机械工业出版社·2002

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700