پایان نامه ارائه روشی جدید در خوشه بندی اطلاعات با استفاده ازترکیب الگوریتم خفاش و Fuzzy c- means

فهرست:

1- فصل اول: مقدمه ....................................................................................................................................... 2

  1-1- بیان مسأله .......................................................................................................................................... 3

  1-2- پیشینه تحقیق ..................................................................................................................................... 4

  1-3- هدف تحقیق ........................................................................................................................................5

  1-4- اهمیت تحقیق .......................................................................................................................................5

  1-5- گفتارهای پایان نامه ..............................................................................................................................8

2- فصل دوم: خوشه بندی بر مبنای الگوریتم Fuzzy c-means ...............................................................10

  2-1- مقدمه .................................................................................................................................................11

  2-2- خوشه بندی اطلاعات ........................................................................................................................11

    2-2-1- تفاوت خوشه­بندی و طبفه­بندی ..................................................................................................13

    2-2-2-کاربردهای خوشه­بندی............................................................................................................... 13    

    2-2-3- انواع خوشه­ها..............................................................................................................................15

    2-2-4- مراحل خوشه بندی ....................................................................................................................15

    2-2-5- انواع روش های خوشه بندی .................................................................................................. 18

    2-2-6- خوشه بندی سلسله مراتبی ...................................................................................................... 18

      2-2-6-1- خوشه بندی سلسله مراتبی تقسیم شونده ............................................................................19

      2-2-6-2- خوشه بندی سلسله مراتبی متراکم شونده ......................................................................... 19

عنوان                                                                                                                   صفحه

    2-2-7- خوشه بندی افراز­بندی یا پارتیشنی .............................................................................................22

      2-2-7-1- الگوریتم k-means ...........................................................................................................23

    2-2-8- خوشه بندی همپوشانی................................................................................................................26

      2-2-8-1- خوشه بندی فازی.................................................................................................................27

3- فصل سوم: بهینه سازی بر مبنای الگوریتم خفاش .................................................................................. 33

  3-1- مقدمه .............................................................................................................................................. 34

  3-2- شرح مسئله بهینه سازی .................................................................................................................. 35

  3-3- روش های حل مسائل بهینه سازی ................................................................................................. 39

    3-3-1- الگوریتم بهینه­سازی توده ذرات .............................................................................................  43

    3-3-2- الگوریتم جفت گیری زنبور عسل ........................................................................................... 45

    3-3-3- الگوریتم مورچگان .................................................................................................................. 46

    3-3-4- الگوریتم الگوی جستجوی ممنوع ........................................................................................... 48

    3-3-5-الگوریتم آبکاری فولاد .............................................................................................................. 49

    3-3-6- الگوریتم خفاش ....................................................................................................................... 51

    3-3-7-راه­حلهای پیشنهادی برای بهبود عملکرد الگوریتم خفاش ......................................................... 54

     3-3-7-1-انتخاب جمعیت اولیه بر اساس قاعده نولید عدد متضاد ...................................................... 54

     3-3-7-2-استراتژی جهش خود تطبیق ................................................................................................ 55

  3-4- معیارهای مقایسه الگوریتمهای بهینه­سازی ...................................................................................... 58

      3-4-1- کارایی.................................................................................................................................... 58

      3-4-2- انحراف استاندارد................................................................................................................... 58

      3-4-3- قابلیت اعتماد.......................................................................................................................... 59

      3-4-4- سرعت همگرایی.................................................................................................................... 59

     عنوان                                                                                                                                                 صفحه

  3-5-تعریف مسایل عددی گوناگون.......................................................................................................... 60

    3-5-1-تابع Rosenbrock.................................................................................................................. 61

    3-5-2- تابع Schewefel  ....................................................................................................................62

    3-5-3- تابع Rastragin  ......................................................................................................................63

    3-5-4- تابعAchley .............................................................................................................................64

    3-5-5- تابع Greiwank .......................................................................................................................65

4- فصل چهارم: الگوریتم پیشنهادی ..............................................................................................................66

  4-1- مقدمه .............................................................................................................................................. 67

  4-2- خوشه بندی اطلاعات به روش ترکیبی پیشنهادی ........................................................................... 68

  4-3- تنظیم پارامترهای الگوریتم پیشنهادی .............................................................................................. 71

  4-4- بررسی نتایج حاصل از الگوریتم پیشنهادی و مقایسه آن با دیگر الگوریتم ها.................................. 71

    4-4-1- معرفی داده های استفاده شده و نتایج شبیه سازی مربوط به آن  ..................................................72     

      4-4-1-1- مجموعه داده Iris ............................................................................................................ 72

      4-4-1-2- مجموعه داده Wine ........................................................................................................ 75

      4-4-1-3- مجموعه داده CMC ....................................................................................................... 77

      4-4-1-4- مجموعه داده Vowel ..................................................................................................... 80

5- فصل پنجم: نتیجه گیری و پیشنهادات ......................................................................................................82

  5-1- نتیجه ............................................................................................................................................... 83

  5-2- پیشنهاد کارهای آینده ...................................................................................................................... 

منبع:

[1]M.R. Anderberg, 'Cluster Analysis for Application.', New Yourk Academic Press, 1973.

[2]J.A. Hartigan, “Statistical theory in clustering.”, Journal of Classification, 1985, Vol.2, pp.63-76.

[3]Jon R Kettering, “The Practice of Cluster Analysis.”, Journal of Classification, 2006, Vol.23, pp.3-30.

[4]J.J. H.Ward, “Hierarchical Grouping to Optimize an Objective Function.”, Journal of the American Statistical Association, 1963, Vol.58, pp.236-244.

[5]J. MacQueen, “Some Methods for Classification and Analysis of MultivariateObservations.”, Fifth Berkeley Symp. Math.Statistics and Probability, 1967, Vol.2. pp.281-297.

[6] Bezdek, J. “Fuzzy mathematics in pattern classification”, Ph.D. thesis. Ithaca, NY: Cornell University, 1794

[7] I. Karen, A.R. Yildiz, N. Kaya, N. Ozturk, F. Ozturk, Hybrid approach

       for genetic algorithm and Taguchi’s method based design

      optimization in the automotive industry, International Journal of

       Production Research 4 (2006) 4897–4914.

 [8] Yi-Tung Kao, Erwie Zahara, I-Wei Kao,“A hybridized approach to data clustering.”, Expert Systems with Applications, 2008, Vol.34. pp.1754-1762.

 [9] احسان عسگریان ، حسین معین زاده ، محسن سریانی ، جعفر حبیبی ”رویکرد جدید برای خوشه بندی فازی بوسیله الگوریتم ژنتیک.“.,سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران.1386.

 [10] Hesam Izakian, Ajith Abraham, “Fuzzy C - means and fuzzy swarm            for fuzzy clustering problem”, Expert Systems with

      Applications 38, 1835–1838, 2011.  

 [11] K.S.F. Shu, Z. Erwie, A hybrid simplex search and particle swarm                optimization for unconstrained optimization, European Journal            of Operational Research 181 (2007) 527–548.

[12] Fatemeh Golichenari, Mohammad Saniee Abadeh, A new Method For         Fuzzy Clustering Besed - on Fuzzy C - means Algorithm and

       Memetic Algorithm,2007

 [13] S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi,

        “Optimization by Simulated Annealing”, Science, 220, 4598, pp. 671-680, 1983.

 [14] Saeed parsa, Hamid saadi, Hamid mohamadi , Scheduling jobs on                computational grid using imulated annealings,2007 

 [15] Suman, B. (2004) "Study of simulated annealing based algorithms for multi objective optimization of a constrained problem", Computers and Chemical Engineering, Volume 28, Issue 9, pp. 1849-1871.

  [16] Zhang, R. and Wu, C. (2010) "A hybrid immune simulated annealing         algorithm for the job shop scheduling problem", Applied Soft              Computing, 10, pp. 79–89.

[17]آیدا خیابانی، جمال شهرابی، رسول علیان نژاد، آرش صباغی،”کاربرد داده کاوی در تشخیص بیماری سل.“،سومین کنفرانس داده کاوی ایران، 1388.

[18]محمدرضا تقوا، لعیا الفت،”بکارگیری تکنیک های داده کاوی جهت مدیریت ارتباط با مشتری در صنعت بانکداری.“،سومین کنفرانس داده کاوی ایران، 1388.

[19] J. C. Bezdek, "Feature selection for binary data-Medical diagnosis

        with fuzzy sets," in Proc. Nat. Comput. Conf. AFIPS Press, 1972,

         pp. 1057-1068.

[20]مسعود یقینی، مریم رنجپور، فرید یوسفی، ”مروری بر الگوریتم های خوشه بندی فازی.“، سوین کنفرانس داده کاوی ایران، 1388.

[21]Jiawei Han, MichelineKamber,. 'Data Mining consepts and techniques.',Diane Cerra, 2006.

[22]Gabriela Czibula, Grigreta Sofia Cojocar, Istvan Gergely Czibula,

   “A Partitional Clustering Algorithm for Crosscutting Concerns          

       Identification.”,proceedings of the 8th wseas int. conference on  

       software engineering, parallel and distributed systems, 2010,       

       pp.111-116.

[23]Jiahai Wang, Yalan Zhou, “Stochastic optimal competitive Hopfield network for partitional clustering”,. Expert Systems with Applications, 2009, Vol.36. pp.2072-2080.

[24]A.K.Jain, M.N. Murty, P.J. Flynn,“Data Clustering: A Review.”,ACM Computing Surveys, 1999, Vol.31. pp.264-323.

[25]Georgios P. Papamichail, Dimitrios P. Papamichail,“The k-means range algorithm for personalized data clustering in e-commerce.”,European Journal of Operational Research, 2007, Vol.177. pp.1400-1408.

[26]Ohn Mar San, Van-Nam Huynh,Yoshiteru Nakamori, “An alternative extension of the k-means algorithm for clustering.”,Int. J. Appl. Math. Comput, 2004, Vol.14. pp.241-247.

[27]Tarsitano Agostino, “A computational studyof several relocation methods for k-means algorithms.”,Pattern Recognition, 2003, Vol.36. pp.2955-2966.

[28]H. Ralambondrainy,“A conceptual version of the K-means algorithm. ”, Pattern Recognition Letters, 1995, Vol.16. pp.1147-1157.

[29]Dingxi Qiu, Ajit C. Tamhane,“A comparative study of the K-means algorithm and the normal mixture model for clustering: Univariate case.”,Journal of Statistical Planning and Inference, 2007, Vol.137. pp.3722-3740.

 [30]Stephen J. Redmond, Conor Heneghan,“A method for initialising the K-means clustering algorithm using kd-trees.”,Pattern Recognition Letters, 2007, Vol.28. pp.965-973.

[31] Yiu-Ming Cheung, “k*-Means: A new generalized k-means clustering algorithm.”,Pattern Recognition Letters, 2003, Vol. 24. 2883-2893.

[32]K. S. Al-Sultan and S. Z. Selim, “A Global Algorithm for the Fuzzy                              

      Clustering Problem”, Pattern Recognition, vol. 26, no. 9, pp. 1357-           

       1361, 1993.

[33] George E. Tsekouras, Haralambos Sarimveis, " A newapproach for 

       measurin g the validity of the fuzzy c-means algorithm", Advances in

  Engineering Software, vol. 35, pp. 567–575, July 2004.

 [34] Li-Xin Wang,"A Course in Fuzzy Systems and Control" , Prentice- 

   Hall International, Inc. 1997

[35]Sadaaki Miyamoto," An Overview and New Methods in Fuzzy

      Clustering"  , 2nd Inter. Conf. on Knowledge-Based Intelligent  

      Electronic Systems, 21-23 April 1998

 [36]Beightler, C.S., D.T. Phillips, and D. J. Wilde.1979. Foundations of   

       Optimization (2nd ed.). Englewood Cliffs, NJ: Printice-Hall.

 [37] مسعود یقینی، محمد رحیم اخوان کاظم ‌زاده. "الگوریتم‌های بهینه‌سازی فراابتکاری"، جهاد دانشگاهی واحد صنعتی امیر کبیر

[38]M. Murugan, V. Selladurai,“Optimization and implementation of cellular manufacturing system in a pump industry using three cell formation algorithms.”,Int J Adv Manuf Technol, 2007, Vol.35. pp.135-149.

[39]Tushar Jain, M.J. Nigam,“Synergy of evolutionary algorithm and socio-political process for global optimization.”,Expert Systems with Applications, 2010, Vol.37. pp.3706–3713.

[40]Yaghini, Masoud; Akhavan, Rahim, DIMMA: "A Design and   

        Implementation Methodology for Metaheuristic Algorithms"،1993

[41]A.R. Yildiz, "A novel particle swarm optimization approach for product

       design and manufacturing", International Journal of Advanced      

  Manufacturing Technology 40 (2009) 617–628.

[42]Chui-Yu Chiu, I-Ting Kuo,“Applying particle swarm optimization and honey bee mating optimization in developing an intelligent market segmentation system.”,Journal of Systems Science and Systems Engineering, 2010, Vol.19. pp.182-191.

[43]Xin Zhang, Hong Peng, Qilun Zheng. Beijing,“A Novel Ant Colony Optimization Algorithm for Clustering.”,8th International Conference on Signal Processing, 2006.

[44]P.S. Shelokar, V.K. Jayaraman, B.D. Kulkarni,“An ant colony approach for clustering.”, Analytica Chimica Acta, 2004, Vol.509. pp.187–195.

[45] A. Fanni, A. Manunza, M. Marchesi, and F. Pilo, “Tabu search  

       metaheuristics for electromagnetic problems optimization continuous   

       domains,” IEEE Trans. Magn., vol. 35, no. 3, pp. 1694–1697, 1999.

 [46]Xiao Ying Wang, Glenn Whitwell, Jonathan M Garibaldi,“Simulated Annealing Fuzzy Clustering in Cancer Diagnosis.”,Informatica, 2005, Vol.29. pp.61-70.

[47]D. Janaki Ram, T. H. Sreenivas, K. Ganapathy Subramaniam, “Parallel Simulated Annealing Algorithms.”,Journal of Parallel and Distributed Computing, 1996, Vol.37. pp.207-212.

[48]X. S. Yang, “A new bat-inspired algorithm,” Nature Inspired 

      Cooperative Strategies for Optimization (NICSO 2010), vol. 284,

      Springer, Studies Computational Intelligence, pp. 65–74, 2010.

[49]K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms.

       New York:Wiley-Interscience Series Systems and Optimization, 2001.

[50] Rosenbrock, H. H. (1960), "An automatic method for finding the greatest or least value of a function", The Computer Journal 3: 175–184 [52]G.W. Gates,“The Reduced Nearest Neighbor Rule”,. IEEE Transactions on Information Theory, 1972. pp.431-433.

[51]A. Törn and A. Zilinskas. "Global Optimization". Lecture Notes in Computer Science, Nº 350, Springer-Verlag, Berlin, 1989.

[52] Cho, H.; Olivera, F.; and Guikema, S. D. "A Derivation of the Number of Minima of the Griewank Function." Appl. Math. Comput. 204, 694-701, 2008. [54]T.S. Lim, W.Y Loh, Y.S Shih,“A Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-three Old and New Classification Algorithms.”,Machine Learning, 2000, Vol.40. pp.203-229.

[53]M. Kudo, J. Toyama, M. Shimbo,“Multidimensional Curve 

      Classification Using Passing-Through Regions.”,Pattern Recognition  

      Letters, 1999, Vol.20. pp.1103-1111.

[54] B.V. Dasarathy,Nosing Around the Neighborhood: “A New System Structure and Classification Rule for Recognition in Partially Exposed Environments.”,IEEE Transactions on Pattern Analysis and Machine Intelligence, 1980, Vol.PAMI-2. pp.67-71.

[55] P. Cortez, A. Cerdeira, F. Almeida, T. Matos, J. Reis,“Modeling wine preferences by data mining from physicochemical properties.”,In Decision Support Systems, Elsevier, 2009, Vol.47. pp.547-553.

[56] T.S. Lim, W.Y Loh, Y.S Shih,“A Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-three Old and New Classification Algorithms.”,Machine Learning, 2000, Vol.40. pp.203-229.

[57] M. Kudo, J. Toyama, M. Shimbo,“Multidimensional Curve       

        Classification Using Passing-Through Regions.”,Pattern   

        Letters, 1999, Vol.20. pp.1103-1111