فهرست:
عنوان صفحه
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- پیشنهاد کارهای آینده ...................................................................................................................... 84
فهرست جدولها
عنوان و شماره صفحه
جدول2‑1 مزایا و معایب الگوریتم k-means ...............................................................................................................26
جدول2‑2 معایب و محاسن الگوریتم c میانگین فازی ................................................................................................ 31
جدول2‑3 معیارهای تشابه بر اساس توابع فاصله مختلف..............................................................................................32
جدول3-1 توابع عددی مورد استفاده برای تست الگوریتمها ....................................................................................60
جدول4‑1 پارامترهای مربوط به الگوریتم های پیشنهادی ...........................................................................................71 جدول4‑2مراکز خوشه به دست آمده با اجرای الگوریتم FCM-BA روی مجموعه دادهIris ......................73
جدول4‑3پاسخ الگوریتم های موجود بر روی مجموعه دادهIris ...............................................................................74
جدول4‑4 پاسخ الگوریتم FCM-BA بازاء مقادیر مختلف پارامترها بر روی مجموعه داده Iris ................... 74
جدول4‑5 پاسخ الگوریتم های موجود بر روی مجموعه داده Wine........................................................................75
جدول4‑6 مراکز خوشه به دست آمده بااجرای الگوریتم FCM-BA روی مجموعه داده Wine....................76
جدول4‑7پاسخ الگوریتمFCM-BA بازاء مقادیر مختلف پارامترها برروی مجموعه دادهWine ................. 77
جدول 4‑8 مراکز خوشه به دست آمده با اجرای الگوریتم پیشنهادی روی مجموعه داده CMC ................... 78
جدول 4‑9پاسخ الگوریتم های موجود بر روی مجموعه داده CMC .......................................................................79
جدول4‑10پاسخ الگوریتم FCM-BAبازاء مقادیر مختلف پارامترها بر روی مجموعه داده CMC ............79
جدول 4‑11 مراکز خوشه به دست آمده با اجرای الگوریتم پیشنهادی روی مجموعه داده Vowel ...............80
جدول 4-12 پاسخ الگوریتم های موجود بر روی مجموعه داده Vowel ................................................................80
جدول 4‑13 پاسخ الگوریتمFCM-BA بازاء مقادیر مختلف پارامترهابرروی مجموعه داده Vowel .......... 81
منبع:
مراجع
[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.