user8127

وزارت علوم، تحقیقات و فناوری
دانشگاه علوم و فنون مازندران
پایان نامه
مقطع کارشناسی ارشد
رشته : مهندسی فناوری اطلاعات
عنوان :
طراحی سیستم دسته‌بند فازی مبتنی بر بهینه سازی ازدحام ذرات برای تشخیص بیماری دیابت
استاد راهنما:
دکتر جواد وحیدی
استاد مشاور:
دکتر همایون موتمنی
دانشجو :
حسین مهدیان
(زمستان 1392)
بسم اللّه الرحمن الرحیم

تقدیم به:
ساحت مقدس آموزگارن علم و دین که معلمان بشریتند
و ادامه دهنده و فرزند آخرین فرستاده‌ی نور امام عصر (ع) …
پدر و مادر مهربانم که دعای خیرشان بهترین توشه من است
و خواهران عزیزم که همیشه مشوقم بوده‌اند
صمیمانه از درگاه خداوند مهربان سلامتی و تندرستی این عزیزان را خواستارم.

سپاسگذاری:
از زحمات اساتید گرانقدرم جناب آقای دکتر وحیدی که در این مدت مرا راهنمایی نمودند و همین طور آقای دکتر موتمنی تشکر و قدردانی می‌کنم.

چکیده
تشخیص بیماری دیابت و یا آگاهی یافتن از احتمال بالای ابتلا به این بیماری همواره کار آسانی نخواهد بود. چرا که این بیماری علائم متعددی را بروز می‌دهد که بعضی از این علائم در سایر بیماری‌های دیگر نیز وجود دارند. بنابراین پزشک برای اتخاذ یک تصمیم مناسب، باید نتیجه‌ی آزمایش‌های بیمار و تصمیم‌هایی که در گذشته برای بیماران با وضیعت مشابه گرفته است، را بررسی کند.
در این پایان نامه از یک الگوریتم دسته‌بندی مبتنی بر قانون برای دسته‌بندی بیماران دیابتی استفاده شده است. برای استخراج قوانین فازی از یک الگوریتم بهینه سازی ازدحام ذرات استفاده شده است. این الگوریتم دارای ویژگی‌هایی است که آن را از سایر الگوریتم مورد استفاده متمایز می‌کند. از جمله‌ی این ویژگی‌ها می‌توان به تابع افزایش تنوع ذرات و تکامل هم‌زمان توابع عضویت و قوانین فازی اشاره کرد. برای ارزیابی کارایی الگوریتم از مجموعه داده‌ی دیابت استفاده شده است. نتایج ارزیابی‌ها نشان می‌دهد که الگوریتم برای مجموعه داده‌ی دیابت دارای کارایی بسیار بالایی می‌باشد. همچنین کارایی الگوریتم پیشنهادی به علت بالا بردن قابلیت تفسیرپذیری دسته‌بند (کاهش تعداد قوانین فازی) بسیار مناسب می‌باشد.
کلمات کلیدی:
تشخیص بیماری دیابت، دسته‌بند مبتنی بر قانون، الگوریتم بهینه‌سازی ازدحام ذرات، تکامل همزمان توابع عضویت و قوانین فازی.
فهرست رئوس مطالب
عنوان صفحه TOC h z u t “Heading 1,2,Heading 2,3,Heading 3,1” فصل اول – مقدمه و کلیات تحقیق PAGEREF _Toc374799610 h 11-1- مقدمه PAGEREF _Toc374799611 h 21-2- بیان مسأله PAGEREF _Toc374799612 h 31-3- اهداف تحقیق PAGEREF _Toc374799613 h 51-4- سوالات تحقیق PAGEREF _Toc374799614 h 61-5- فرضیات مسأله PAGEREF _Toc374799615 h 61-6- نوآوری‌های تحقیق PAGEREF _Toc374799616 h 71-7- تعریف واژگان PAGEREF _Toc374799617 h 71-8- ساختار پایان نامه PAGEREF _Toc374799618 h 8فصل دوم – ادبیات و پیشینه تحقیق PAGEREF _Toc374799619 h 102-1- مقدمه PAGEREF _Toc374799620 h 112-2- داده‌کاوی PAGEREF _Toc374799621 h 112-3- دسته‌بندی PAGEREF _Toc374799622 h 132-4- الگوریتم‌های رایج دسته‌بندی PAGEREF _Toc374799623 h 152-4-1- شبکه‌های عصبی مصنوعی PAGEREF _Toc374799624 h 152-4-2- درخت‌های تصمیم PAGEREF _Toc374799625 h 192-4-3- شبکه‌های بیزین PAGEREF _Toc374799626 h 212-4-4- K نزدیک‌ترین همسایه PAGEREF _Toc374799627 h 232-4-5- ماشین بردار پشتیبان PAGEREF _Toc374799628 h 242-4-6- روش‌های مبتنی بر قانون PAGEREF _Toc374799629 h 282-5- الگوریتم بهینه‌سازی ازدحام ذرات PAGEREF _Toc374799630 h 322-5-1- پارامترهای پایه بهینه‌سازی ازدحام ذرات PAGEREF _Toc374799631 h 352-5-2- چالش‌ها و مسائل پیش روی الگوریتم بهینه‌سازی ازدحام ذرات PAGEREF _Toc374799632 h 392-5-2-1- مشکل ابعاد بالا PAGEREF _Toc374799633 h 402-5-2-2- مشکل همبستگی میان داده‌ها PAGEREF _Toc374799634 h 432-5-3- گونه‌های مختلف PSO PAGEREF _Toc374799635 h 472-5-3-1- بهینه‌سازی ازدحام ذرات مبتنی بر شبکه‌های جمعی PAGEREF _Toc374799636 h 482-5-3-1-1- همسایگی مبتنی بر فاصله فضایی PAGEREF _Toc374799637 h 482-5-3-1-2- همسایگی فزاینده PAGEREF _Toc374799638 h 482-5-3-1-3- بهینه‌سازی ازدحام ذرات کاملاً آگاه (FIPS) PAGEREF _Toc374799639 h 492-5-3-2- مدل پیوندی بهینه‌سازی ازدحام ذرات PAGEREF _Toc374799640 h 502-5-3-3- بهینه‌سازی ازدحام ذرات چند جمعیتی PAGEREF _Toc374799641 h 532-6- سیستم‌های فازی PAGEREF _Toc374799642 h 562-6-1- ساختار یک سیستم دسته‌بندی مبتنی بر قوانین فازی PAGEREF _Toc374799643 h 572-6-2- دسته‌بندی بدون استفاده از درجه قطعیت PAGEREF _Toc374799644 h 582-6-3- دسته‌بندی با استفاده از درجه قطعیت PAGEREF _Toc374799645 h 622-6-4- استنتاج فازی PAGEREF _Toc374799646 h 662-7- معیار‌های ارزیابی دسته‌بند‌ها PAGEREF _Toc374799647 h 68فصل سوم – روش تحقیق PAGEREF _Toc374799648 h 723-1- مقدمه PAGEREF _Toc374799649 h 733-2- تبدیل داده‌های حقیقی به ترم‌های فازی PAGEREF _Toc374799650 h 753-3- تولید توابع عضویت و قوانین فازی با استفاده از الگوریتم بهینه‌سازی ازدحام ذرات PAGEREF _Toc374799651 h 773-3-1- کدگذاری توابع عضویت فازی PAGEREF _Toc374799652 h 783-3-2- کدگذاری قوانین فازی PAGEREF _Toc374799653 h 803-3-3- PSO پیشنهادی PAGEREF _Toc374799654 h 823-3-5- توابع برازش کیفیت قوانین PAGEREF _Toc374799655 h 873-5- نتیجه‌گیری PAGEREF _Toc374799656 h 90فصل چهارم – محاسبات و یافته‌های تحقیق PAGEREF _Toc374799657 h 914-1- داده‌های مورد استفاده PAGEREF _Toc374799658 h 924-2- تنظیم پارامترها PAGEREF _Toc374799659 h 944-3- روش‌های استفاده شده به منظور مقایسه PAGEREF _Toc374799660 h 974-4- نتایج PAGEREF _Toc374799661 h 984-5- نتیجه گیری PAGEREF _Toc374799662 h 101فصل پنجم – نتیجه گیری و پیشنهادات PAGEREF _Toc374799663 h 1025-1- خلاصه و نتیجه‌ گیری PAGEREF _Toc374799664 h 1035-2- پیشنهادات PAGEREF _Toc374799665 h 103منابع: PAGEREF _Toc374799666 h 105
فهرست جداول
عنوان صفحه TOC h z t “Caption1,1” جدول 2-1: مجموعه داده‌های آموزش PAGEREF _Toc374809173 h 20جدول 2-2: جدول توزیع احتمال گره تنگی نفس PAGEREF _Toc374809174 h 23جدول 2-3: توابع فاصله میان نمونه‌های x و y PAGEREF _Toc374809175 h 23جدول 2-4: ماتریس اغتشاش دودویی PAGEREF _Toc374809176 h 69جدول 4- 1: خصیصه‌های مجموعه داده Pima Indian Diabetes PAGEREF _Toc374809177 h 92جدول 4- 2: پارامترهای قابل تنظیم توسط کاربر PAGEREF _Toc374809178 h 94جدول 4- 3: مقادیر در نظر گرفته شده برای پارامترهای الگوریتم PAGEREF _Toc374809179 h 96جدول 4- 4: نتایج بدست آمده از الگوریتم پیشنهادی بر روی مجموعه داده Pima PAGEREF _Toc374809180 h 99جدول 4- 5:مقایسه نتایج بدست آمده برای مجموعه داده Pima با سایر روش‌ها PAGEREF _Toc374809181 h 99جدول 4- 6: نتایج سایر مطالعات صورت گرفته بر روی مجموعه داده Pima PAGEREF _Toc374809182 h 100
فهرست تصاویر و نمودارها
عنوان صفحه
TOC h z t “Caption,1″ شکل 2- 1: فرآیند داده‌کاوی و کشف دانش PAGEREF _Toc374808951 h 12شکل 2- 2: ساختار SLP PAGEREF _Toc374808952 h 17شکل 2- 3: ساختار یک نرون (گره) PAGEREF _Toc374808953 h 18شکل 2- 4: درخت تصمیم جدول (2-1) PAGEREF _Toc374808954 h 21شکل 2- 5: مثالی از شبکه‌ی بیزین PAGEREF _Toc374808955 h 22شکل 2- 6: دسته‌بند ماشین بردار پشتیبان PAGEREF _Toc374808956 h 25شکل 2- 7: دسته‌بند ماشین بردار پشتیبان با حاشیه نرم PAGEREF _Toc374808957 h 27شکل 2- 8: شبه کد الگوریتم بهینه‌سازی ازدحام ذرات PAGEREF _Toc374808958 h 34شکل 2- 9: تشریح هندسی مولفه‌های شخصی و اجتماعی در PSO PAGEREF _Toc374808959 h 35شکل 2- 10: ساختار یک سیستم قانونمند فازی PAGEREF _Toc374808960 h 59شکل 2- 11: ناحیه تصمیم هر قانون فازی PAGEREF _Toc374808961 h 60شکل 2- 12: مرزهای دسته‌بندی نُه قانون فازی PAGEREF _Toc374808962 h 60شکل 2- 13:مرز دسته‌بندی بعد از اصلاح توابع عضویت PAGEREF _Toc374808963 h 61شکل 2- 14: ناحیه تصمیم هر قانون فازی در حالتی که جداول قانون فازی ناکامل باشد PAGEREF _Toc374808964 h 62شکل 2- 15: ناحیه تصمیم هر قانون فازی با درجات PAGEREF _Toc374808965 h 63شکل 2- 16: تنظیم مرزهای دسته‌بندی بدون استفاده از درجه قطعیت PAGEREF _Toc374808966 h 63شکل 2- 17: تنظیم مرزهای دسته‌بندی با استفاده از درجه قطعیت PAGEREF _Toc374808967 h 64شکل 2- 18: تعیین دسته نتیجه و درجه قطعیت PAGEREF _Toc374808968 h 65شکل 2- 19: بیش برازش PAGEREF _Toc374808969 h 71شکل 3- 1: نمای کلی مدل پیشنهادی برای واکشی سیستم فازی PAGEREF _Toc374808970 h 74شکل 3- 2: توابع عضویت فازی (S:Small, MS: Medium Small, M: Medium, ML: Medium Large, L: Large) PAGEREF _Toc374808971 h 76شکل 3- 3: نمایش گرافیکی پارامترهای توابع عضویت پیشنهادی PAGEREF _Toc374808972 h 77شکل 3- 4: نمایش گرافیکی فضای جستجو برای یک مسئله چهار بعدی با سه بازه فازی PAGEREF _Toc374808973 h 78شکل 3- 5: کدگذاری پارامترهای متغیرهای ورودی و خروجی PAGEREF _Toc374808974 h 79شکل 3- 6:کدگذاری هر ذره شامل پارامترهای توابع عضویت و مجموعه قوانین PAGEREF _Toc374808975 h 80شکل 3- 7: فلوچارتPSO PAGEREF _Toc374808976 h 83شکل 3- 8: تابع Membership_and_Rule_Learn PAGEREF _Toc374808977 h 86شکل 4- 1: توزیع مقادیر خصیصه‌های مختل مجموعه داده Pima PAGEREF _Toc374808978 h 93شکل 4- 2: توزیع خصیصه اول 20 نمونه‌ی اول pima PAGEREF _Toc374808979 h 94شکل 4- 3: تأثیر پارامتر SwarmSize بر کارایی PAGEREF _Toc374808980 h 95شکل 4- 4: تأثیر پارامتر w بر کارایی PAGEREF _Toc374808981 h 96
فصل اول – مقدمه و کلیات تحقیق
1-1- مقدمهافزایش استفاده از کامپیوترها در فعالیت‌های کسب و کار، منجر به رشد سریع پایگاه‌های اطلاعاتی و اجتماع داده‌ها توسط بیشتر سازمان‌ها شده است. روزانه حجم عظیمی از داده‌ها تولید شده و در پایگاه‌های مختلف داده ذخیره می‌شود. در سال‌های اخیر تمایل به جستجو برای کشف الگوهای تکرار‌پذیر به منظور بهبود در تصمیم گیری افزایش چشمگیری داشته است. همچنین کاوش در داده‌های تراکنشی جهت یافتن الگوهای پنهان و تکنیک‌های کشف دانش به منظور شناخت دقیق‌تر و بیشتر تراکنش‌ها، اهمیت بسزایی یافته است. ADDIN EN.CITE <EndNote><Cite><Author>Maimon</Author><Year>2010</Year><RecNum>92</RecNum><DisplayText>[1]</DisplayText><record><rec-number>92</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>92</key></foreign-keys><ref-type name=”Book Section”>5</ref-type><contributors><authors><author>Maimon, Oded</author><author>Rokach, Lior</author></authors></contributors><titles><title>Introduction to knowledge discovery and data mining</title><secondary-title>Data Mining and Knowledge Discovery Handbook</secondary-title></titles><pages>1-15</pages><dates><year>2010</year></dates><publisher>Springer</publisher><isbn>0387098224</isbn><urls></urls></record></Cite></EndNote>[1]. در حوزه پزشکی و سلامت با افزایش استفاده از سیستم‌های جامع درمانی و پرونده‌های الکترونیک بیمار در بیمارستان‌ها و مراکز درمانی حجم انبوهی از اطلاعات مربوط بیماران و انواع بیماری‌ها مهیا می‌شود. ADDIN EN.CITE <EndNote><Cite><Author>Koh</Author><Year>2011</Year><RecNum>89</RecNum><DisplayText>[2]</DisplayText><record><rec-number>89</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>89</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Koh, Hian Chye</author><author>Tan, Gerald</author></authors></contributors><titles><title>Data mining applications in healthcare</title><secondary-title>Journal of Healthcare Information Management—Vol</secondary-title></titles><periodical><full-title>Journal of Healthcare Information Management—Vol</full-title></periodical><pages>65</pages><volume>19</volume><number>2</number><dates><year>2011</year></dates><urls></urls></record></Cite></EndNote>[2]. استخراج دانایی از حجم عظیم داده‌های مرتبط با سوابق بیماری و پرونده‌های پزشکی افراد با استفاده از فرآیند داده‌کاوی می‌تواند منجر به شناسایی قوانین حاکم بر ایجاد، رشد و افت بیماری‌ها گردیده و اطلاعات ارزشمندی را به منظور شناسایی علل وقوع بیماری‌ها با توجه به عوامل محیطی حاکم در اختیار متخصصین و دست اندر کاران حوزه سلامت قرار دهد؛ که این امر در نهایت منجر به افزایش متوسط طول عمر افراد جامعه و ایجاد آرامش می‌گردد. ADDIN EN.CITE <EndNote><Cite><Author>Bellazzi</Author><Year>2008</Year><RecNum>94</RecNum><DisplayText>[3]</DisplayText><record><rec-number>94</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>94</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Bellazzi, Riccardo</author><author>Zupan, Blaz</author></authors></contributors><titles><title>Predictive data mining in clinical medicine: current issues and guidelines</title><secondary-title>international journal of medical informatics</secondary-title></titles><periodical><full-title>international journal of medical informatics</full-title></periodical><pages>81-97</pages><volume>77</volume><number>2</number><dates><year>2008</year></dates><isbn>1386-5056</isbn><urls></urls></record></Cite></EndNote>[3].
آنچه مسلم است با افزایش سیستم‌های الکترونیک سلامت حجم داده‌های پزشکی هر روزه در حال افزایش است. اما این مجموعه داده‌های بزرگ به طور خام هیچ کاربردی ندارد برای آنکه بتوان از این داده‌ها ارزشی را استخراج کرد نیاز به تحلیل داده‌ها و تبدیل آن به اطلاعات و دانش، یک نیاز اساسی است. با توجه به چنین حجمی از داده‌ها استفاده از عامل انسانی به عنوان تشخیص دهنده الگوها و تحلیلگر داده‌ها پاسخگو نمی‌باشد؛ لذا داده کاوی روی داده‌های پزشکی از اهمیت بالایی برخوردار است. داده‌کاوی را می‌توان از جنبه‌های مختلف در پیشگیری یا تشخیص انواع بیماری، انتخاب روش‌های درمان بیماری، مدت زمان بستری بیمار و … به کار برد.
1-2- بیان مسألهدیابت یکی از بیماری‌های رایج در جوامع امروزی است که دارای عوارض خطرناکی می‌باشد. این بیماری اگر چه گونه‌ای از بیماری‌های قلبی محسوب نمی‌شود ولی اغلب سبب بیماری‌های قلبی می‌شود.
تشخیص بیماری دیابت و یا آگاهی یافتن از احتمال بالای ابتلا به این بیماری همواره کار آسانی نخواهد بود. چرا که این بیماری علائم متعددی را بروز می‌دهد که بعضی از این علائم در سایر بیماری‌ها نیز وجود دارند. بنابراین پزشک برای اتخاذ یک تصمیم مناسب، باید نتیجه‌ی آزمایش‌های بیمار و تصمیم‌های که در گذشته برای بیماران با وضیعت مشابه گرفته است، را بررسی کند. با توجه به حجم انبوه تعداد بیماران، می‌توان از یک ابزار داده‌کاوی برای شناخت الگوی بیماران قبلی استفاده کرد.
در این پایان‌نامه با توجه به ماهیت مسأله از یک الگوریتم دسته‌بندی برای تشخیص بیماری دیابت استفاده می‌کنیم سپس آن‌را با سایر روش‌ها ارائه شده مقایسه می‌کنیم. روش دسته بندی یک روش یادگیری با نظارت است که داده‌های ورودی به دو بخش داده‌های آموزش و داده‌های آزمون تقسیم می‌شوند. هر الگوریتم کاندید، ابتدا با استفاده از مجموعه داده آموزش یک مدل را که نشان دهنده الگوی حاکم بر داده‌ها می‌باشد را استخراج می‌کند و سپس با استفاده از مجموعه آزمون دقت مدل ارائه شده برای دسته‌بندی را بررسی می‌کند.
الگوریتم‌های متعددی برای دسته بندی ارائه شده‌اند که از آن دسته می‌توان؛ به شبکه‌های بیزین ADDIN EN.CITE <EndNote><Cite><Author>Heckerman</Author><Year>1996</Year><RecNum>15</RecNum><DisplayText>[4]</DisplayText><record><rec-number>15</rec-number><foreign-keys><key app=”EN” db-id=”svfzx9x57wvvpoeavxmvfr2gfserrpar2v90″>15</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Heckerman, David</author><author>Breese, John S</author></authors></contributors><titles><title>Causal independence for probability assessment and inference using Bayesian networks</title><secondary-title>Sys–s, Man and Cybernetics, Part A: Sys–s and Humans, IEEE Transactions on</secondary-title></titles><periodical><full-title>Sys–s, Man and Cybernetics, Part A: Sys–s and Humans, IEEE Transactions on</full-title></periodical><pages>826-831</pages><volume>26</volume><number>6</number><dates><year>1996</year></dates><isbn>1083-4427</isbn><urls></urls></record></Cite></EndNote>[4]، روش‌های مبتنی بر درخت ADDIN EN.CITE <EndNote><Cite><Author>Olaru</Author><Year>2003</Year><RecNum>87</RecNum><DisplayText>[5]</DisplayText><record><rec-number>87</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>87</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Olaru, Cristina</author><author>Wehenkel, Louis</author></authors></contributors><titles><title>A complete fuzzy decision tree technique</title><secondary-title>Fuzzy Sets and Sys–s</secondary-title></titles><periodical><full-title>Fuzzy Sets and Sys–s</full-title></periodical><pages>221-254</pages><volume>138</volume><number>2</number><dates><year>2003</year></dates><isbn>0165-0114</isbn><urls></urls></record></Cite></EndNote>[5]، الگوریتم ماشین بردار پشتیبان ADDIN EN.CITE <EndNote><Cite><Author>Wang</Author><Year>2005</Year><RecNum>91</RecNum><DisplayText>[6]</DisplayText><record><rec-number>91</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>91</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Wang, Lipo</author></authors></contributors><titles><title>Support Vector Machines: theory and applications</title></titles><volume>177</volume><dates><year>2005</year></dates><publisher>Springer</publisher><isbn>3540243887</isbn><urls></urls></record></Cite></EndNote>[6]، روش‌های مبتنی بر مجموعه فازی ADDIN EN.CITE <EndNote><Cite><Author>Baranyi</Author><Year>2004</Year><RecNum>93</RecNum><DisplayText>[7]</DisplayText><record><rec-number>93</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>93</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Baranyi, Péter</author><author>Kóczy, László T</author><author>Gedeon, Tamás D</author></authors></contributors><titles><title>A generalized concept for fuzzy rule interpolation</title><secondary-title>Fuzzy Sys–s, IEEE Transactions on</secondary-title></titles><periodical><full-title>Fuzzy Sys–s, IEEE Transactions on</full-title></periodical><pages>820-837</pages><volume>12</volume><number>6</number><dates><year>2004</year></dates><isbn>1063-6706</isbn><urls></urls></record></Cite></EndNote>[7]، الگوریتم‌های فرا اکتشافی ADDIN EN.CITE <EndNote><Cite><Author>Blum</Author><Year>2008</Year><RecNum>86</RecNum><DisplayText>[8]</DisplayText><record><rec-number>86</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>86</key></foreign-keys><ref-type name=”Book Section”>5</ref-type><contributors><authors><author>Blum, Christian</author><author>Roli, Andrea</author></authors></contributors><titles><title>Hybrid metaheuristics: an introduction</title><secondary-title>Hybrid Metaheuristics</secondary-title></titles><pages>1-30</pages><dates><year>2008</year></dates><publisher>Springer</publisher><isbn>354078294X</isbn><urls></urls></record></Cite></EndNote>[8] و شبکه‌های عصبی ADDIN EN.CITE <EndNote><Cite><Author>Santos</Author><Year>2000</Year><RecNum>95</RecNum><DisplayText>[9]</DisplayText><record><rec-number>95</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>95</key></foreign-keys><ref-type name=”Conference Proceedings”>10</ref-type><contributors><authors><author>Santos, Raul T</author><author>Nievola, Júlio C</author><author>Freitas, Alex A</author></authors></contributors><titles><title>Extracting comprehensible rules from neural networks via genetic algorithms</title><secondary-title>Combinations of Evolutionary Computation and Neural Networks, 2000 IEEE Symposium on</secondary-title></titles><pages>130-139</pages><dates><year>2000</year></dates><publisher>IEEE</publisher><isbn>0780365720</isbn><urls></urls></record></Cite></EndNote>[9] اشاره کرد.
در این نوشتار قصد داریم برای استخراج قوانین فازی از یک الگوریتم آموزش دیده مبتنی بر هوش جمعی، بهینه‌سازی ازدحام ذرات (PSO) استفاده کنیم. خاصیت اصلی الگوریتم‌های هوش جمعی تبادل اطلاعات بین ذرات است که در یافتن حالت بهینه بسیار موثر می‌باشند.
سعی شده با در نظر گرفتن نقاط ضعف و قوت روش‌های مختلف داده کاوی یک الگوریتم ترکیبی برای تشخیص بیماری ارائه شود. الگوریتم شبکه عصبی معمولاً نرخ دسته بندی مناسبی را ارائه می‌دهد ولی از شفافیت لازم برخوردار نیست. بنابراین نمی‌توان این اطلاعات را توسط سیستم‌های خبره بررسی کرد. برای حل این مسئله باید یک ارائه قابل فهم انسانی از دسته‌بندی ایجاد کرد. این هدف می‌تواند با استخراج قوانین فازی تولید شده که برای کاربر قابل فهم است بدست بیاید.
دو معیار اصلی برای برازش الگوریتم‌های دسته‌بندی؛ نرخ دسته بندی و قابلیت تفسیر می‌باشد. نرخ دسته بندی میزان دقت کار الگوریتم در دسته بندی نمونه‌های آزمون را نشان می‌دهد و قابلیت تفسیر به معنی میزان سادگی و قابلیت توسعه روش دسته بندی می‌باشد.
در سال‌های اخیر قوانین فازی از آن جهت که هم دقت مناسبی دارند وهم قابلیت تفسیر مناسبی را ارائه می‌دهند بیشتر مورد توجه قرار گرفته‌اند. یک الگوریتم فازی از آن جهت مورد توجه می‌باشد که شامل مجموعه‌ای از قوانین اگر-آنگاه فازی می‌شود که تفسیر آن‌ها توسط انسان خبره امکان پذیر است. مسئله اساسی در چنین سیستم‌هایی انتخاب مجموعه‌ای از قوانین فازی بهینه است؛ لذا این مسئله را می‌توان نوعی از بهینه سازی ترکیبی در نظر گرفت که با رشد ابعاد مسئله دسته بندی، تعداد جواب‌های بهینه محلی نیز به صورت نمایی افزایش می‌یابد و الگوریتم کاندید برای حل آن باید مجموعه‌ای از جواب‌های بهینه یا نزدیک به بهینه را ارائه دهد ADDIN EN.CITE <EndNote><Cite><Author>Ishibuchi</Author><Year>2007</Year><RecNum>90</RecNum><DisplayText>[10]</DisplayText><record><rec-number>90</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>90</key></foreign-keys><ref-type name=”Conference Proceedings”>10</ref-type><contributors><authors><author>Ishibuchi, Hisao</author></authors></contributors><titles><title>Evolutionary multiobjective design of fuzzy rule-based sys–s</title><secondary-title>Foundations of Computational Intelligence, 2007. FOCI 2007. IEEE Symposium on</secondary-title></titles><pages>9-16</pages><dates><year>2007</year></dates><publisher>IEEE</publisher><isbn>1424407036</isbn><urls></urls></record></Cite></EndNote>[10].
روش‌های مختلفی برای استخراج قوانین از مجموعه داده وجود دارد ازجمله آن‌ها می‌توان به روش‌های مبتنی بر شبکه‌های عصبی ADDIN EN.CITE <EndNote><Cite><Author>Towell</Author><Year>1993</Year><RecNum>88</RecNum><DisplayText>[11]</DisplayText><record><rec-number>88</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>88</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Towell, Geoffrey G</author><author>Shavlik, Jude W</author></authors></contributors><titles><title>Extracting refined rules from knowledge-based neural networks</title><secondary-title>Machine learning</secondary-title></titles><periodical><full-title>Machine learning</full-title></periodical><pages>71-101</pages><volume>13</volume><number>1</number><dates><year>1993</year></dates><isbn>0885-6125</isbn><urls></urls></record></Cite></EndNote>[11] و روش‌های مبتنی بر خوشه‌بندی ADDIN EN.CITE <EndNote><Cite><Author>Tang</Author><Year>2010</Year><RecNum>97</RecNum><DisplayText>[12]</DisplayText><record><rec-number>97</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>97</key></foreign-keys><ref-type name=”Conference Proceedings”>10</ref-type><contributors><authors><author>Tang, Zhi-hang</author><author>Peng, Hui-ying</author></authors></contributors><titles><title>A Novel Rules Extraction Method Based on Clustering Analysis</title><secondary-title>Intelligent Sys–s and Applications (ISA), 2010 2nd International Workshop on</secondary-title></titles><pages>1-4</pages><dates><year>2010</year></dates><publisher>IEEE</publisher><isbn>1424458722</isbn><urls></urls></record></Cite></EndNote>[12] اشاره کرد. با توجه به قابلیت‌های روش‌های فرا اکتشافی برای پوشش فضای جستجو، این الگوریتم‌ها برای استخراج قوانین می‌توانند یک گزینه مناسب باشند. این روش‌ها با ایجاد یک راه حل اولیه در فضای جستجو آغاز می‌شوند و سپس به وسیله یک مجموعه قواعد جستجوی بهینه شروع می‌شود. در هر مرحله از الگوریتم جستجو همواره یک راه حل یا یک مجموعه از راه حل‌ها وجود دارند که وضعیت فعلی الگوریتم را نشان می‌دهند. برخی از روش‌های اکتشافی، روش‌های راه حل به راه حل هستند یعنی در فضای جستجوی مسئله از طریق یک راه حل به راه حل دیگر دست می‌یابند. بقیه روش‌ها بر پایه مجموعه می‌باشند که با اعمال تغییراتی در مجموعه فعلی به مجموعه جدید می‌رسیم. برای استفاده از روش‌های مکاشفه‌ای در برنامه‌های داده کاوی باید آن‌ها را با یک روش محلی ادغام کنیم. این روش‌های محلی، استراتژی کلی روش‌های مکاشفه‌ای را هدایت می‌کنند.
1-3- اهداف تحقیقهدف از روش ارائه شده کشف الگوها در میان مجموعه داده بیماران دیابتی برای کمک به پزشکان در تصمیم گیری می‌باشد رسیدن به نرخ دسته بندی و قابلیت تفسیر مطلوب از مجموعه داده با ترکیب مفهوم فازی و الگوریتم هوش جمعی بهینه‌سازی ازدحام ذرات برای استخراج قوانین فازی بدست می‌آید.
1-4- سوالات تحقیقسوالاتی که در این تحقیق سعی شده به آن‌ها پاسخ دهیم به شرح زیر می‌باشد:
در داده‌های با ابعاد بالا چه روشی برای انجام دسته بندی با نرخ صحیح دسته بندی مناسب است؟
چگونه با ترکیب الگوریتم بهینه‌سازی محلی و سراسری نتایج جستجو را بهبود دهیم؟
چه الگوریتمی ارائه دهیم برای اینکه هم نرخ دسته بندی بهبود یابد و هم قابلیت تفسیر خوبی داشته باشد؟
نقش روش ترکیبی از سیستم فازی، الگوریتم ازدحام ذرات در انجام بهتر عمل دسته بندی چه خواهد بود؟
1-5- فرضیات مسألهدر این پایان نامه قصد داریم با کمک تکنیک دسته بندی، دانش را از مجموعه داده‌های دیابت واکشی کنیم که این دانش در قالب مجموعه قوانین فازی نمایش داده می‌شود. الگوریتم پیشنهادی با استفاده از ترکیب مکاشفه‌ی بهینه سازی ازدحام ذرات ارتقاء یافته مجموعه‌ای از قوانین فازی که بیانگر الگوی حاکم بر داده‌های مربوط به بیماران دیابتی است، استخراج خواهند شد. این الگوریتم با توجه به معیارهای مورد استفاده برای بهینه سازی پایگاه قوانین به دنبال مجموعه قوانینی می‌گردد که بهترین معیارهای ذکر شده را دارا باشد. هدف ما به دست آوردن دانش بهینه می‌باشد که با معیارهای نظیر دقت و قابلیت تفسیر مورد ارزیابی قرار می‌گیرد.
مجموعه داده دیابت بکار گرفته شده در این پایان نامه مجموعه داده Pima از دانشگاه UCI است که شامل 786 نمونه و 8 صفت می‌باشد. متغیر کلاس این مجموعه دو مقدار 0 و 1 را به خود اختصاص می‌دهد که به ترتیب بیانگر عدم ابتلا و ابتلا به این بیماری می‌باشند. که صفت‌های آن شامل: تعداد دفعات بارداری، غلظت گلوکز پلاسما، فشارخون دیاستولی بر حسب میلی لیتر جیوه، ضخامت چین پوستی یک عضله در بازوها، تزریق سرم دو ساعت، شاخص توده‌ای بدن برای بررسی چاقی، سن و متغیر کلاس (0 و 1) می‌باشد.
1-6- نوآوری‌های تحقیقارائه یک مدل ترکیبی از الگوریتم ازدحام ذرات و مجموعه فازی
ارائه یک روش جدید برای افزایش قابلیت اکتشاف در الگوریتم بهینه‌سازی ازدحام ذرات
ارائه یک روش جدید برای افزایش قابلیت بهره‌کشی در الگوریتم بهینه‌سازی ازدحام ذرات
روش کدگذاری هم‌زمان توابع عضویت و قوانین فازی
1-7- تعریف واژگانداده کاوی: به استخراج اطلاعات از میان حجم انبوهی از اطلاعات که به آن کشف دانش نیز می‌گویند.
دسته‌بندی: برای تخصیص یک برچسب به مجموعه‌ای از داده‌ها که دسته‌بندی نشده‌اند، استفاده می‌شود. در دسته‌بندی یک متغیر هدف گروهی وجود دارد که به دسته‌ها و گروه‌های از پیش تعیین شده افراز می‌گردد. سپس داده‌ها بر اساس ویژگی‌هایشان به دسته‌هایی که نام آن‌ها از قبل مشخص می‌باشد، تخصیص داده می‌شوند.
الگوریتم‌های تکاملی: الگوریتم‌هایی که جنبه‌های انتخاب طبیعی و بقای بهترین‌ها را با هم ترکیب می‌کنند. یک الگوریتم تکاملی جمعیتی که شامل ساختارهایی می‌شوند که عموماً به صورت تصادفی مقدار دهی اولیه شده‌اند و سپس این ساختارها طبق قوانین مشخصی مانند انتخاب و جهش تکامل می‌یابند. یک محیط که برای تمام اعضا مشترک است مناسب بودن و کارایی هر یک از اعضای جمعیت را مشخص می‌کند. اعضای مناسب‌تر شانس بیشتر برای انتخاب و یا ساخت مجدد توسط هر یک از عملگرهای الگوریتم را دارند.
هوش جمعی: نوعی از روش‌های تکاملی هستند که شیوه ارتباط عامل‌ها با یکدیگر از طریق محیط و به صورت غیر مستقیم است. این قابلیت اجازه می‌دهد، این الگوریتم‌ها به صورت توزیع شده بخش عظیمی از فضای جستجو را پوشش دهند و در نتیجه شانس الگوریتم برای یافتن یک راه‌حل مناسب افزایش یابد. در سطح بالاتر، گروهی از عامل‌ها که با هم برای رسیدن به اهداف مشخص رفتار خاصی را بروز می‌دهند. هوش همگانی از مجموع گروه‌های بزرگی از عامل‌های نسبتاً ساده پدیدار می‌شود. ADDIN EN.CITE <EndNote><Cite><Author>Grosan</Author><Year>2006</Year><RecNum>1</RecNum><DisplayText>[13]</DisplayText><record><rec-number>1</rec-number><foreign-keys><key app=”EN” db-id=”svfzx9x57wvvpoeavxmvfr2gfserrpar2v90″>1</key></foreign-keys><ref-type name=”Book Section”>5</ref-type><contributors><authors><author>Grosan, Crina</author><author>Abraham, Ajith</author><author>Chis, Monica</author></authors></contributors><titles><title>Swarm intelligence in data mining</title><secondary-title>Swarm Intelligence in Data Mining</secondary-title></titles><pages>1-20</pages><dates><year>2006</year></dates><publisher>Springer</publisher><isbn>3540349553</isbn><urls></urls></record></Cite></EndNote>[13].
استنتاج فازی: وظیفه فرایند استنتاج نگاشت ورودی‌های فازی (که از فرایند فازی سازی دریافت شدند) به پایگاه قوانین فازی و تولید خروجی فازی برای هر یک از قوانین است.
1-8- ساختار پایاننامهمطالبی که در فصول بعدی ارائه خواهد شد به شرح زیر خواهد بود:
در فصل دوم مفاهیم پایه‌ای مانند داده‌کاوی، کلیات مربوط به الگوریتم‌های دسته بندی، الگوریتم‌های رایج دسته‌بندی و معیارهای ارزیابی این الگوریتم‌ها مورد بحث قرار می‌گیرد.
در فصل سوم حاوی کارهای انجام شده و تحقیقات مرتبط با موضوع می‌باشد، همچنین فضای کلی مسأله معرفی شده و الگوریتم‌های بهینه سازی ازدحام ذرات پیشنهادی برای ایجاد دسته‌بند فازی شرح داده می‌شوند.
در فصل چهارم مدل پیشنهادی برای دسته‌بندی بر روی مجموعه داده‌های دیابت اعمال و نتایج روش پیشنهادی با نتایج روش‌های معروف در این زمینه مورد مقایسه و ارزیابی قرار گرفته است.
فصل پنجم نیز حاوی خلاصه، نتیجه‌گیری و پیشنهادات می‌باشد.
فصل دوم – ادبیات و پیشینه تحقیق
2-1- مقدمهدنیای مدرن در حقیقت دنیایی در محاصره حجم عظیمی از داده‌ها، چه عددی و چه انواع دیگر است. پیشرفت فناوری اطلاعات و مجهز شدن به ابزار رایانه‌ای امکان جمع‌آوری اطلاعات در زمینه‌های مختلف را فراهم آورده و منجر به پیدایش ساختارهای داده‌ای با حجم عظیم شده است. دست پیدا کردن به اطلاعات نهفته در پایگاه داده شرکت‌ها، دانشگاه‌ها، مؤسسات دولتی و سایر مراکز نیازمند مدیریتی جدید است و با به‌کارگیری سیستم‌های سنتی این امر تحقق نمی‌یابد. ضمن اینکه با گسترش رقابت در بخش‌های مختلف علمی، اجتماعی، سیاسی و غیره زمان مورد نیاز برای دسترسی به این اطلاعات نیز اهمیت دوچندان پیدا کرده است. بنابراین نیاز به طراحی سیستم‌های هوشمندی که توانایی دست‌یابی به اطلاعات مورد نظر کاربر را در مدت زمان کوتاه و با کم‌ترین مداخله کاربر را داشته باشند کاملاً مشهود است.
2-2- داده‌کاویداده کاوی فرآیندی است که از آغاز دهه‌ی 90 پا به عرصه‌ی ظهور گذاشته و با نگرشی نو به مسئله‌ی استخراج اطلاعات از پایگاه داده می‌نگرد. این فرآیند یک مرحله فراتر از بازیابی ساده داده‌ها است و این اجازه را می‌دهد که دانش را در میان حجم انبوه داده‌ها کشف کرد ADDIN EN.CITE <EndNote><Cite><Author>Fayyad</Author><Year>1996</Year><RecNum>2</RecNum><DisplayText>[14]</DisplayText><record><rec-number>2</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>2</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Fayyad, Usama</author><author>Piatetsky-Shapiro, Gregory</author><author>Smyth, Padhraic</author></authors></contributors><titles><title>From data mining to knowledge discovery in databases</title><secondary-title>AI magazine</secondary-title></titles><periodical><full-title>AI magazine</full-title></periodical><pages>37</pages><volume>17</volume><number>3</number><dates><year>1996</year></dates><isbn>0738-4602</isbn><urls></urls></record></Cite></EndNote>[14]. داده کاوی یک علم میان رشته‌ای است و ترکیبی از علومی نظیر پایگاه داده، تحلیل آماری، هوش مصنوعی و بینایی ماشین می‌باشد. داده کاوی یک مرحله ضروری از فرآیند بزرگ‌تر کشف دانش می‌باشد که شامل مراحل زیر می‌باشد ADDIN EN.CITE <EndNote><Cite><Author>Mariscal</Author><Year>2010</Year><RecNum>3</RecNum><DisplayText>[15]</DisplayText><record><rec-number>3</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>3</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Mariscal, Gonzalo</author><author>Marbán, Óscar</author><author>Fernández, Covadonga</author></authors></contributors><titles><title>A survey of data mining and knowledge discovery process models and methodologies</title><secondary-title>Knowledge Engineering Review</secondary-title></titles><periodical><full-title>Knowledge Engineering Review</full-title></periodical><pages>137</pages><volume>25</volume><number>2</number><dates><year>2010</year></dates><isbn>0269-8889</isbn><urls></urls></record></Cite></EndNote>[15] :
1.پاک‌سازی داده‌ها: حذف نویز و داده‌های ناسازگار و نا ایستا.
2.یکپارچگی داده‌ها: ترکیب انواع داده‌های پراکنده و ناهمگن از منابع مختلف.
3.انتخاب ویژگی‌ها: انتخاب صفت‌های تأثیرگذار از داده‌ها.
4.تبدیل داده‌ها: تبدیل یا ترکیب داده‌ها به اشکالی که برای بکار بردن در داده‌کاوی مناسب باشند.
5.داده‌کاوی: روش‌های مختلف را برای استخراج الگو استفاده می‌کند.
6.ارزیابی الگو: الگوهای مناسب برای ارائه دانش را بر اساس معیارهای مشخص شناسایی می‌کند.
7.ارائه دانش: دانش کشف شده را با استفاده از روش‌های نمایش اطلاعات نشان می‌دهد.
-590552204085شکل 2- SEQ شکل_2- * ARABIC 1: فرآیند داده‌کاوی و کشف دانش00شکل 2- SEQ شکل_2- * ARABIC 1: فرآیند داده‌کاوی و کشف دانش10096595250داده کاوی
داده‌های
خام
داده‌های
هدف
پاک‌سازی
داده‌ها
ارائه دانش
الگوها
یکپارچگی
داده‌ها
تبدیل داده‌ها
پیش پردازش داده‌ها
تشخیص الگو
00داده کاوی
داده‌های
خام
داده‌های
هدف
پاک‌سازی
داده‌ها
ارائه دانش
الگوها
یکپارچگی
داده‌ها
تبدیل داده‌ها
پیش پردازش داده‌ها
تشخیص الگو

داده‌کاوی از دو مرحله اصلی تشکیل شده است؛ مرحله اول پیش پردازش داده‌ها که در این مرحله خصیصه‌های با تأثیر بالاتر از داده‌های سطح پایین استخراج می‌شود. مرحله دوم تشخیص الگو می‌باشد که به کشف الگوی موجود در داده‌ها به کمک صفات و خصیصه‌های بدست آمده می‌پردازد.
داده‌کاوی را می‌توان سیر تکاملی طبیعی تکنولوژی اطلاعات دانست، که این سیر تکاملی ناشی از یک بلوغ در صنعت پایگاه داده نظیر: عملیات جمع‌آوری داده‌ها و ایجاد پایگاه داده، مدیریت داده و تحلیل و فهم داده می‌باشد.
داده کاوی تحلیل داده‌های قابل مشاهده برای کشف ارتباطات غیرمنتظره و خلاصه کردن داده‌ها به صورتی بدیع است که برای دارنده‌ی اطلاعات مفید و قابل درک باشد ADDIN EN.CITE <EndNote><Cite><Author>Hong</Author><Year>2009</Year><RecNum>4</RecNum><DisplayText>[16]</DisplayText><record><rec-number>4</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>4</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Hong, Tzung-Pei</author><author>Wu, Yi-Ying</author><author>Wang, Shyue-Liang</author></authors></contributors><titles><title>An effective mining approach for up-to-date patterns</title><secondary-title>Expert sys–s with applications</secondary-title></titles><periodical><full-title>Expert sys–s with applications</full-title></periodical><pages>9747-9752</pages><volume>36</volume><number>6</number><dates><year>2009</year></dates><isbn>0957-4174</isbn><urls></urls></record></Cite></EndNote>[16]. کاوش اطلاعات، حجم عظیمی از داده‌های خام را به فرمی تغییر می‌دهد که انسان بتواند آن‌ها را به راحتی بفهمد و برای تصمیم گیری بتواند از این اطلاعات استفاده کند. در مسائل داده کاوی، هر چه حجم داده‌ها بیشتر می‌شود، میل بیشتری برای کشف الگوهای مخفی در داده‌ها به وجود می‌آید. در قدم اصلی داده کاوی ممکن است از چندین الگوریتم داده کاوی استفاده شود. کار اصلی الگوریتم داده کاوی با توجه به نوع مسئله‌ی کشف دانش تغییر می‌کند اما دو نوع اصلی الگوریتم‌های داده کاوی، دسته‌بندی و خوشه‌بندی است.
اصلی‌ترین دلیلی که باعث شد داده کاوی در علوم پزشکی مورد توجه بسیاری قرار بگیرد، مسأله در دسترس بودن حجم وسیعی از داده‌ها و نیاز شدید به اینکه از این داده‌ها، اطلاعات و دانش استخراج شود. داده‌کاوی عبارت است از استخراج دانش از مجموعه‌ای از داده‌ها.
2-3- دسته‌بندیهرگاه داده‌ها دارای خصیصه‌ای خاص باشند که مستقیماً از دیگر خصایص به وجود نیامده باشد اما بین آن مشخصه و دیگر ابعاد رابطه وابستگی وجود داشته باشد، در این صورت می‌توان با کشف مدلی بر اساس دیگر مشخصه‌ها، آن بعد مذکور (که نشان دهنده دسته خاصی از داده‌ها است) را شناسایی نمود. فرض کنید که مشخصات تعدادی بیمار در پایگاه داده‌ای وجود دارد که قبلاً با استفاده از آزمایش خاص دو نوع بیماری مشخص شده که هر‌کدام از این بیماران به کدام بیماری مبتلا هستند، در این جا هیچ فردی حق ندارد هر دو بیماری را داشته باشد، سالم بوده و یا بیماری دیگری داشته باشد، به این معنی که دسته‌ها فضای مسئله را افراز می‌کند. در چنین پایگاه داده‌هایی برای هر بیمار یک رکورد خاص وجود دارد که شامل علائم بیمار و در نهایت نام یا برچسب بیماری که بیمار به آن مبتلا شده است می‌باشد. یک داده کاو تصمیم می‌گیرد سیستمی را ابداع کند که طی آن بدون آزمایش و فقط از روی علائم بیمار بتوان نوع بیماری وی را تشخیص داد. این تصمیم ممکن است به هر دلیلی مثلاً کمبود امکانات صورت گرفته باشد. آنچه باید انجام شود عملیات دسته بندی نامیده می‌شود. هدف دسته‌بندی؛ آموزش یک نگاشت از ورودی‌های x به خروجی‌های y است، که در آن ، C تعداد کلاس‌ها را مشخص می‌کند. اگر C=2 دسته‌بندی را دسته‌بندی دودویی می‌نامیم ()، اگر C>2 باشد، این نوع دسته‌بندی را دسته‌بندی چند کلاسه می‌نامیم ADDIN EN.CITE <EndNote><Cite><Author>Murphy</Author><Year>2012</Year><RecNum>6</RecNum><DisplayText>[17]</DisplayText><record><rec-number>6</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>6</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Kevin P. Murphy</author></authors></contributors><titles><title>Machine Learning: A Probabilistic Perspective</title></titles><pages>3</pages><dates><year>2012</year></dates><publisher>The MIT Press</publisher><isbn>0262018020, 9780262018029</isbn><urls></urls></record></Cite></EndNote>[17].
دسته‌بندی داده‌ها یک فرآیند دو مرحله‌ای است. اولین مرحله ساخت مدل و دومین مرحله استفاده از مدل و پیش‌بینی کلاس از طریق مدل ساخته شده است. برای این منظور باید مجموعه داده‌ها را به دو دسته داده‌های آموزش و داده‌های تست تقسیم کنیم. با استفاده از داده‌هایی که برچسب آموزش خورده‌اند یک دسته‌بند ایجاد می‌شود که بر اساس آن بتوان داده‌های فاقد برچسب را در دسته‌های مربوط به خودشان قرار داد. کارایی دسته‌بند ساخته شده با داده‌های تست (که به صورت تصادفی از میان داده‌ها انتخاب شده‌اند) مورد سنجش قرار می‌گیرد و مدل روی آن‌ها اجرا می‌شود تا دقت پیش بینی دسته‌بند بررسی گردد، چنان که مدل دارای دقت مناسبی باشد برای دسته‌بندی داده‌ها به کار می‌رود.
در دسته‌بندی یادگیری به وسیله نمونه‌ها انجام می‌گیرید و برچسب هر یک از دسته‌ها مشخص است. سپس نمونه‌ها بر حسب ویژگی‌هایشان به دسته‌های از قبل مشخص شده، تخصیص داده می‌شوند. در حالی که در خوشه‌بندی داده‌ها به خوشه‌های مختلف که از قبل معین نیستند تقسیم می‌شوند، بر این اساس که داده‌های درون خوشه مشابه و داده‌های خوشه‌های مختلف متفاوت باشند. خوشه بندی به فرآیند تقسیم بندی داده به یک یا چند گروه به طوری که فاصله‌ی بین خوشه‌ها حداکثر و فاصله‌ی درون خوشه‌ها حداقل باشد، اطلاق می‌شود.
2-4- الگوریتم‌های رایج دسته‌بندیروش‌های زیادی برای دسته‌بندی وجود دارد که از جمله می‌توان به مواردی که در ادامه به آن‌ها اشاره می‌شود اشاره کرد:
شبکه‌های عصبی مصنوعی
درخت‌های تصمیم
شبکه‌های بیزین
k نزدیک‌ترین همسایه
ماشین بردار پشتیبان
روش‌های مبتنی بر قانون
2-4-1- شبکه‌های عصبی مصنوعیمطالعه شبکه‌های عصبی مصنوعی تا حد زیادی الهام گرفته از سیستم‌های یادگیر طبیعی است که در آن‌ها یک مجموعه پیچیده از نرون‌های به هم متصل در کار یادگیری دخیل هستند. گمان می‌رود که مغز انسان از تعداد 1011 نرون تشکیل شده باشد که هر نرون با تقریباً 104 نرون دیگر در ارتباط است. سرعت انتقال نرون‌ها در حدود 10-3 ثانیه است که در مقایسه با کامپیوترها ( 10-10 ثانیه) بسیار ناچیز می‌نماید. با این وجود آدمی قادر است در 0.1 ثانیه تصویر یک انسان را باز شناسائی نماید. این قدرت فوق‌العاده باید از پردازش موازی توزیع شده در تعدادی زیادی از نرون‌ها حاصل شده باشد ADDIN EN.CITE <EndNote><Cite><Author>Haykin</Author><Year>2007</Year><RecNum>7</RecNum><DisplayText>[18]</DisplayText><record><rec-number>7</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>7</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Haykin, Simon S</author></authors></contributors><titles><title>Neural networks: a comprehensive foundation</title></titles><pages>28-32</pages><dates><year>2007</year></dates><publisher>Prentice Hall Englewood Cliffs NJ</publisher><isbn>0131471392</isbn><urls></urls></record></Cite></EndNote>[18].
این شبکه‌ها یادگیری را از روی مثال‌ها و نمونه‌ها انجام می‌دهند و از این لحاظ در عمل یادگیری شبیه به انسان عمل می‌کنند. مزیت دیگر آن‌ها این است که این شبکه‌ها از توانایی تعمیم دهی ذاتی برخوردار هستند؛ یعنی این شبکه‌ها توانایی تشخیص الگوهایی را که شبیه نمونه‌هایی که قبلاً یاد گرفته باشد را دارد نه اینکه تنها الگوهای دقیقاً همانند نمونه‌های آموزشی را تشخیص دهد ADDIN EN.CITE <EndNote><Cite><Author>Benardos</Author><Year>2007</Year><RecNum>8</RecNum><DisplayText>[19]</DisplayText><record><rec-number>8</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>8</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Benardos, PG</author><author>Vosniakos, G-C</author></authors></contributors><titles><title>Optimizing feedforward artificial neural network architecture</title><secondary-title>Engineering Applications of Artificial Intelligence</secondary-title></titles><periodical><full-title>Engineering Applications of Artificial Intelligence</full-title></periodical><pages>365-382</pages><volume>20</volume><number>3</number><dates><year>2007</year></dates><isbn>0952-1976</isbn><urls></urls></record></Cite></EndNote>[19].
شبکه عصبی مصنوعی روشی عملی برای یادگیری توابع گوناگون نظیر توابع با مقادیر حقیقی، توابع با مقادیر گسسته و توابع با مقادیر برداری می‌باشد. یک نرون به تنهایی فقط می‌تواند برای شناسایی توابعی که به صورت خطی تفکیک پذیرند بکار رود، از آنجا که در مسائل واقعی عموماً توابع به صورت خطی جدایی پذیر نیستند شبکه‌ای از نرون‌ها مورد نیاز می‌باشد.
انواع شبکه‌های عصبی برای حل مسائل مختلف یادگیری بانظارت، یادگیری بدون نظارت و یادگیری تقویتی استفاده می‌شوند. شبکه‌های عصبی بر حسب انواع اتصالات به دو نوع رو به جلو FNN و بازگشتی RNN تقسیم می‌شوند. FNN ها معمول‌ترین نوع شبکه‌های عصبی است که در کاربردهای مختلف استفاده می‌شوند. لایه اول لایه ورودی نامیده می‌شود و لایه آخر لایه خروجی است و هر تعداد لایه میان این دو لایه را لایه‌های میانی یا مخفی می‌نامند زیرا در عمل ما تنها با ورودی و خروجی‌های شبکه عصبی کار داریم. شبکه عصبی به صورت یک جعبه سیاه کار می‌کند و دسترسی مستقیم به لایه‌های میانی میسّر نیست. شبکه‌های عصبی بازگشتی دارای چرخه‌های جهت‌دار در ساختار گراف‌های ارتباطشان هستند یعنی با دنبال کردن ارتباطات بین گره‌ها می‌توان به گره‌ها قبلی و آغازین بازگشت. RNN ها با توجه به ساختارشان دینامیک پیچیده‌ای دارند و این امر آموزش این شبکه‌ها را بسیار پیچیده می‌کند. ضمن اینکه از لحاظ بیولوژیکی شبکه‌های عصبی بازگشتی به واقعیت نزدیک‌تر هستند.
شبکه‌های FNN با بیش از یک لایه مخفی را MLP و شبکه‌های FNN با یک لایه مخفی را SLP می‌نامیم و در آن خروجی نرون‌ها در هر لایه تابعی غیر خطی از خروجی‌های لایه‌های قبلی است. تعداد نرون‌های لایه ورودی و خروجی ثابت است، تعداد نرون‌های لایه ورودی برابر با فضای مشخصه‌ها و تعداد نرون‌های لایه خروجی با توجه به تعداد کلاس‌ها مشخص می‌شود. در MLP گره‌ها (نرون‌ها) معمولاً در لایه‌هایی در شبکه عصبی مرتب می‌شوند هر گره تنها ورودی‌هایی از لایه قبل دریافت می‌کند و تابعی از ورودی‌ها را ارائه می‌دهد.
100076031115لایه ورودی
لایه مخفی
لایه خروجی
فضای خصیصه‌ها
تعداد کلاس‌ها
00لایه ورودی
لایه مخفی
لایه خروجی
فضای خصیصه‌ها
تعداد کلاس‌ها
10007602163445شکل 2- SEQ شکل_2- * ARABIC 2: ساختار SLP [20]
00شکل 2- SEQ شکل_2- * ARABIC 2: ساختار SLP [20]

هر واحد یک خروجی را منتشر می‌کند که تابعی غیر خطی از مقادیر ورودی است ADDIN EN.CITE <EndNote><Cite><Author>Zhang</Author><Year>2000</Year><RecNum>13</RecNum><DisplayText>[20]</DisplayText><record><rec-number>13</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>13</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Zhang, Guoqiang Peter</author></authors></contributors><titles><title>Neural networks for classification: a survey</title><secondary-title>Sys–s, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on</secondary-title></titles><periodical><full-title>Sys–s, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on</full-title></periodical><pages>451-462</pages><volume>30</volume><number>4</number><dates><year>2000</year></dates><isbn>1094-6977</isbn><urls></urls></record></Cite></EndNote>[20]. f تابع فعال‌سازی است که بر روی مجموع ضرب وزن‌ها در ورودی‌های هر گره اعمال می‌گردد. معروف‌ترین تابع فعال‌سازی که در شبکه‌های عصبی استفاده می‌شود تابع سیگموئید یا لجستیک نام دارد که در آن؛
(2-1)
رفتار شبکه عصبی با توجه به مقادیر وزن‌های آن تعیین می‌شود. شبکه عصبی بهترین مقادیر وزن‌ها و بایاس‌ها را با توجه به مجموعه داده موجود یاد می‌گیرد، در واقع آموزش شبکه عصبی شامل تنظیم وزن‌ها و بایاس‌ها تا موقعی که شرایط مشخصی برآورده گردد می‌شود. تنظیم وزن‌ها به گونه‌ای صورت می‌گیرد که میزان خطا میان خروجی مطلوب و خروجی شبکه عصبی را کاهش دهد.
688340-33020Net j
f(Netj)
yj
X1
X2
Xd

Node j
b=1
wj1
wj2
wjd
wj0
00Net j
f(Netj)
yj
X1
X2
Xd

Node j
b=1
wj1
wj2
wjd
wj0

702310356235شکل 2- SEQ شکل_2- * ARABIC 3: ساختار یک نرون (گره) [20]
00شکل 2- SEQ شکل_2- * ARABIC 3: ساختار یک نرون (گره) [20]

برای آموزش (تعیین وزن‌ها و بایاس‌ها) شبکه عصبی FNN دو راه وجود دارد: روش‌های کلاسیک مانند الگوریتم انتشار به عقب (BP) و روش‌های بهینه‌سازی هوشمند مانند الگوریتم ژنتیک و الگوریتم بهینه‌سازی ازدحام ذرات PSO.
روش BP بر پایه گرادیان نزولی در فضای خطا است که دارای قابلیت جستجوی محلی می‌باشد. اصلاح وزن‌های شبکه عصبی به گونه‌ای صورت می‌گیرد که در هر دور خطای میان خروجی مطلوب و خروجی شبکه عصبی کاهش یابد. این خطا به صورت زیر تعریف می‌شود:
(2-2)
به این صورت خطا برای مجموع n نمونه آموزشی محاسبه می‌گردد. خروجی مطلوب و خروجی شبکه عصبی می‌باشد. قدرت الگوریتم BP در قابلیت محاسبه خطای موثر برای هر واحد مخفی است. نهایتاً هر یک از وزن‌ها در دور m+1 به صورت زیر تغییر می‌کند:
(2-3)
(2-4)
در رابطه (2-4) نرخ یادگیری و اختلاف میان خروجی مطلوب و خروجی شبکه عصبی است. در روش‌های مبتنی بر گرادیان نزولی مانند BP ممکن است همگرا شدن به یک مقدار مینیمم زمان زیادی لازم داشته باشد. همچنین در این روش‌ها اگر در سطح خطا چندین مینیمم محلی وجود داشته باشد تضمینی وجود ندارد که الگوریتم بتواند مینیمم مطلق را پیدا بکند ADDIN EN.CITE <EndNote><Cite><Author>Engelbrecht</Author><Year>2007</Year><RecNum>14</RecNum><DisplayText>[21]</DisplayText><record><rec-number>14</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>14</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Engelbrecht, Andries P</author></authors></contributors><titles><title>Computational intelligence: an introduction</title></titles><dates><year>2007</year></dates><publisher>Wiley</publisher><isbn>0470512504</isbn><urls></urls></record></Cite></EndNote>[21].
روش‌های تکاملی برای اجتناب از گیر افتادن در مینیمم محلی و افزایش قدرت تعمیم دهی که از نقاط ضعف الگوریتم‌های مبتنی بر گرادیان نزولی برای آموزش شبکه عصبی بود بکار گرفته شدند. در این روش‌ها ابتدا جمعیت اولیه به صورت از پیش تعریف شده یا تصادفی مشخص می‌شود. هر یک از اعضای جمعیت یکی از راه‌حل‌های بالقوه است که الگوریتم تکاملی مورد نظر در طول دوره‌های مختلف فضای مسأله را جستجو و جمعیت را به سمت نقطه بهینه که کارایی را بهبود می‌دهد حرکت می‌دهد ADDIN EN.CITE <EndNote><Cite><Author>Jin</Author><Year>2012</Year><RecNum>11</RecNum><DisplayText>[22]</DisplayText><record><rec-number>11</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>11</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Jin, Cong</author><author>Jin, Shu-Wei</author><author>Qin, Li-Na</author></authors></contributors><titles><title>Attribute selection method based on a hybrid BPNN and PSO algorithms</title><secondary-title>Applied Soft Computing</secondary-title></titles><periodical><full-title>Applied Soft Computing</full-title></periodical><pages>2147-2155</pages><volume>12</volume><number>8</number><dates><year>2012</year></dates><isbn>1568-4946</isbn><urls></urls></record></Cite></EndNote>[22].
2-4-2- درخت‌های تصمیمدرخت‌های تصمیم از بالا به پایین یکی از الگوریتم‌های رایج دسته‌بندی می‌باشند ADDIN EN.CITE <EndNote><Cite><Author>Quinlan</Author><Year>1993</Year><RecNum>12</RecNum><DisplayText>[23]</DisplayText><record><rec-number>12</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>12</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Quinlan, J Ross</author></authors></contributors><titles><title>C4. 5: Programs for machine learning (morgan kaufmann series in machine learning)</title><secondary-title>Morgan Kaufmann</secondary-title></titles><periodical><full-title>Morgan Kaufmann</full-title></periodical><dates><year>1993</year></dates><urls></urls></record></Cite></EndNote>[23]. از مهم‌ترین دلایل رایج بودن این الگوریتم شفافیت و قابلیت تفسیر بالای این الگویتم است. مزیت دیگر موجود بودن پیاده‌سازی‌های قوی نظیر C4.5 است. الگوریتم‌های درخت‌های تصمیم با ساخت یک الگوریتم از بالا به پایین توسط انتخاب صفت در هر لحظه و جداسازی داده‌ها با توجه به مقادیر صفتشان انجام می‌شود ADDIN EN.CITE <EndNote><Cite><Author>Quinlan</Author><Year>1993</Year><RecNum>12</RecNum><DisplayText>[23]</DisplayText><record><rec-number>12</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>12</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Quinlan, J Ross</author></authors></contributors><titles><title>C4. 5: Programs for machine learning (morgan kaufmann series in machine learning)</title><secondary-title>Morgan Kaufmann</secondary-title></titles><periodical><full-title>Morgan Kaufmann</full-title></periodical><dates><year>1993</year></dates><urls></urls></record></Cite></EndNote>[23]. مهم‌ترین صفت به عنوان ریشه درخت و بقیه گره‌ها نیز به ترتیب اولویت در سطح‌های بعدی قرار می‌گیرند به گونه‌ای که گره‌هایی که ضریب دست‌یابی اطلاعات و برچسب دسته را نشان می‌دهند نزدیک ریشه قرار می‌گیرند. شکل (2-4) چگونگی ساخت درخت تصمیم برای جدول (2-1) را نمایش می‌دهد.
جدول 2-1: مجموعه داده‌های آموزشصفت اول صفت دوم صفت سوم صفت چهارم کلاس
a1 a2 a3 a4 Yes
a1 a2 a3 b4 Yes
a1 b2 a3 a4 Yes
a1 b2 b3 b4 No
a1 c2 a3 a4 Yes
a1 c2 a3 b4 No
b1 b2 b3 b4 No
c1 b2 b3 b4 No
برای بالا بردن قابلیت تفسیر درخت لازم است که اندازه درخت را کاهش دهیم که این کار موجب کمتر شدن پایداری می‌گردد. روش‌های بهینه‌سازی مختلفی برای تعیین ساختار بهینه درخت در مسائل دسته‌بندی مورد استفاده قرار گرفته‎اند. هنگامی که بخواهیم الگوریتم‌های درخت‌های تصمیم را بر روی مجموعه داده‌های بزرگی به کار گیریم، ناپایدار بودن این الگوریتم‌ها بیشتر نمایان می‌شود زیرا دست‌یابی یکباره به همه داده‌ها و ایجاد یک درخت تصمیم یکتا عملی نمی‌باشد.
360680-34925صفت 1
صفت 2
No
No
Yes
Yes
صفت 3
صفت 4
No
Yes
No
a1
c1
b1
a2
b2
c2
a3
b3
a4
b4
00صفت 1
صفت 2
No
No
Yes
Yes
صفت 3
صفت 4
No
Yes
No
a1
c1
b1
a2
b2
c2
a3
b3
a4
b4

25336516510شکل 2- SEQ شکل_2- * ARABIC 4: درخت تصمیم جدول (2-1)00شکل 2- SEQ شکل_2- * ARABIC 4: درخت تصمیم جدول (2-1)
2-4-3- شبکه‌های بیزیندر روش‌های دسته‌بندی آماری برخلاف سایر دسته‌بندها میزان عضویت یک نمونه به هر کلاس را با یک احتمال نشان می‌دهد. روش شبکه‌های بیزین رایج‌ترین روش دسته‌بندی آماری و از روش‌های ساده و موثر محسوب می‌شود. در این روش احتمال شرطی هر صفت داده شده را توسط برچسب دسته مربوطه از داده‌های آموزشی یاد می‌گیرید. سپس عمل دسته‌بندی توسط بکار بردن قوانین بیز برای محاسبه مقدار احتمالی دسته نتیجه نمونه داده شده با دقت بالایی انجام می‌شود. در حالت معمولی این کار با تخمین احتمالاتی هر ترکیب ممکن از صفات صورت می‌گیرد ولی هنگامی که تعداد صفات خیلی زیاد باشد، این امر امکان پذیر نیست. بنابراین یک فرض مستقل قوی اتخاذ می‌شود که همه صفات با مشخص بودن مقدار صفت دسته مستقل می‌باشند. با در نظر گرفتن این فرض لازم است که فقط احتمالات حاشیه‌ای هر صفت دسته محاسبه گردد. با این حال این فرض به صورت غیرواقعی می‌باشد و شبکه‌های بیزین با مدل کردن صریح، وابستگی بین صفات آن را در نظر نمی‌گیرند ADDIN EN.CITE <EndNote><Cite><Author>Heckerman</Author><Year>1996</Year><RecNum>20</RecNum><DisplayText>[4]</DisplayText><record><rec-number>20</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>20</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Heckerman, David</author><author>Breese, John S</author></authors></contributors><titles><title>Causal independence for probability assessment and inference using Bayesian networks</title><secondary-title>Sys–s, Man and Cybernetics, Part A: Sys–s and Humans, IEEE Transactions on</secondary-title></titles><periodical><full-title>Sys–s, Man and Cybernetics, Part A: Sys–s and Humans, IEEE Transactions on</full-title></periodical><pages>826-831</pages><volume>26</volume><number>6</number><dates><year>1996</year></dates><isbn>1083-4427</isbn><urls></urls></record></Cite></EndNote>[4].
مسأله یادگیری ساختار شبکه بیزین به این صورت بیان می‌شود که با داشتن یک مجموعه آموزشی از n نمونه u؛ یک شبکه پیدا کنیم که بهترین تطبیق را با A داشته باشد. معمول‌ترین روش برای این مسأله معرفی یک تابع هدف است که هر شبکه با توجه به داده‌های آموزشی و جستجوی بهترین شبکه بر اساس این تابع ارزیابی شود ADDIN EN.CITE <EndNote><Cite><Author>Kotsiantis</Author><Year>2007</Year><RecNum>15</RecNum><DisplayText>[24]</DisplayText><record><rec-number>15</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>15</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Kotsiantis, Sotiris B</author><author>Zaharakis, ID</author><author>Pintelas, PE</author></authors></contributors><titles><title>Supervised machine learning: A review of classification techniques</title></titles><pages>249-268</pages><dates><year>2007</year></dates><urls></urls></record></Cite></EndNote>[24]. چالش‌های بهینه‌سازی کلیدی انتخاب تابع هدف و تعیین روال جستجو برای بهترین شبکه می‌باشد.
شبکه بیزین مدلی گرافیکی برای نشان دادن توزیع احتمالی مجموعه‌ای از متغیرها است. دانش بدست آمده برای یک مسئله به صورت اطلاعات کمی و کیفی در این گراف مدل می‌شود. این کار با مشخص کردن مجموعه‌ای از فرضیات استقلال خطی توسط کمان‌های گراف، همراه با ذکر مقادیر احتمال شرطی گره‌ها انجام می‌شود ADDIN EN.CITE <EndNote><Cite><Author>Murphy</Author><Year>2012</Year><RecNum>6</RecNum><DisplayText>[17]</DisplayText><record><rec-number>6</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>6</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Kevin P. Murphy</author></authors></contributors><titles><title>Machine Learning: A Probabilistic Perspective</title></titles><pages>3</pages><dates><year>2012</year></dates><publisher>The MIT Press</publisher><isbn>0262018020, 9780262018029</isbn><urls></urls></record></Cite></EndNote>[17].
سرطان شش
سیگار
اشعه x
نارحتی ریوی
تنگی نفس
P(D|C,B)
P(B|S)
P(S)
P(X|C,S)
P(C|S)
سرطان شش
سیگار
اشعه x
نارحتی ریوی
تنگی نفس
P(D|C,B)
P(B|S)
P(S)
P(X|C,S)
P(C|S)

شکل 2- SEQ شکل_2- * ARABIC 5: مثالی از شبکه‌ی بیزین [24]
هر متغیری به صورت یک گره در شبکه بیزین نمایش داده شده و برای هر متغیر دو نوع اطلاعات ارائه می‌گردد: کمان‌های شبکه برای نشان دادن رابطه استقلال شرطی بکار می‌رود یک متغیر با دانستن والدین آن از گره‌های غیر فرزند آن مستقل است. جدولی نیز ارائه می‌گردد که توزیع احتمال هر گره برای والدین بلا فصل آن را مشخص می‌کند.
جدول 2-2: جدول توزیع احتمال گره تنگی نفس [24]
D=1 D=0 B C
0.8 0.2 0 0
0.2 0.8 1 0
0.9 0.1 0 1
0.6 0.4 1 1
2-4-4- K نزدیک‌ترین همسایهالگوریتم k نزدیک‌ترین همسایه مثالی از یادگیری بر اساس نمونه است که در آن مجموعه داده آموزشی برای ایجاد یک مدل دسته‌بندی مورد استفاده قرار می‌گیرند. بنابراین یک دسته‌بندی برای یک نمونه دسته‌بندی نشده ممکن است به سادگی با مقایسه آن با شبیه‌ترین نمونه‌ها در مجموعه آموزشی یافت شود. روال این الگوریتم به این صورت است که برای هر نمونه جدید با مقایسه آن با k نمونه آموزشی نزدیکتر، دسته نتیجه را مشخص می‌کنیم ADDIN EN.CITE <EndNote><Cite><Author>Duda</Author><Year>2012</Year><RecNum>18</RecNum><DisplayText>[25]</DisplayText><record><rec-number>18</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>18</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Duda, Richard O</author><author>Hart, Peter E</author><author>Stork, David G</author></authors></contributors><titles><title>Pattern classification</title></titles><dates><year>2012</year></dates><publisher>John Wiley &amp; Sons</publisher><isbn>111858600X</isbn><urls></urls></record></Cite></EndNote>[25]. بنابراین لازم است معیاری را برای تعیین فاصله بین نمونه‌ها مشخص نماییم. برای تعیین فاصله بین دو نمونه و توابع فاصله فراوانی می‌تواند مورد استفاده قرار گیرد جدول (2-3).
جدول 2-3: توابع فاصله میان نمونه‌های x و yتابع فاصله فرمول
فاصله اقلیدسی d(x,y)=i=1n(xi-yi)2
فاصله همینگ d(x,y)=i=1nxi-yi
فاصله چبیشف d(x,y)=maxi=1,2,…,nxi-yi
فاصله مینکوفسکی d(x,y)=pi=1n(xi-yi)pp>0
فاصله کانبرا d(x,y)=i=1nxi-yixi+yi
به دست آوردن معیار فاصله برای داده‌های عددی آسان است ولی متغیرهای گروهی نیاز به مکانیزم خاصی برای فاصله دارند. زمان محاسباتی روش k نزدیک‌ترین همسایه به صورت نمایی از تمام نقاط افزایش می‌یابد لذا از لحاظ محاسباتی الگوریتم پر هزینه‌ای می‌باشد. این در حالی است که به کار بردت درخت تصمیم یا شبکه عصبی سریع‌تر می‌باشد.
2-4-5- ماشین بردار پشتیبانماشین بردار پشتیبان دسته‌بندی کننده‌ای است که جزو روش‌های بر پایه هسته در یادگیری ماشین محسوب می‌شود. SVM در سال 1992 توسط وپ‌نیک معرفی شده و بر پایه نظریه آماری یادگیری بنا گردیده است. الگوریتم SVM یکی از الگوریتم‌های معروف در زمینه یادگیری با نظارت است که برای دسته‌بندی و رگرسیون استفاده می‌شود. این الگوریتم به طور هم‌زمان حاشیه‌های هندسی را بیشینه کرده و خطای تجربی دسته‌بندی را کمینه می‌کند لذا به عنوان دسته‌بندی حداکثر حاشیه نیز نامیده می‌شود ADDIN EN.CITE <EndNote><Cite><Author>Bishop</Author><Year>2006</Year><RecNum>21</RecNum><DisplayText>[26]</DisplayText><record><rec-number>21</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>21</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Bishop, Christopher M</author><author>Nasrabadi, Nasser M</author></authors></contributors><titles><title>Pattern recognition and machine learning</title></titles><volume>1</volume><dates><year>2006</year></dates><publisher>springer New York</publisher><urls></urls></record></Cite></EndNote>[26].
برای یک مسأله دسته‌بندی با دو دسته نتیجه خطوط بی‌شماری ممکن است وجود داشته باشند که توسط آن‌ها دسته‌بندی انجام شود ولی فقط یکی از این خطوط ماکزیمم تفکیک و جداسازی را فراهم می‌آورد. از بین جداسازهای خطی، آن جداسازی که حاشیه داده‌های آموزشی را حداکثر می‌کند خطای تعمیم را حداقل خواهد کرد. نقاط داده‌ای ممکن است ضرورتاً نقاط داده‌ای در فضای R2 نباشند و ممکن است در فضای چند بعدی Rn مربوط باشند. دسته‌بندهای خطی بسیاری ممکن است این خصوصیت را ارضا کنند اما SVM به دنبال جداکننده‌ای است که حداکثر جداسازی را برای دسته‌ها انجام دهد.
86360069215w.x+b = 1
w.x+b = -1
w.x+b = 0
SV
SV
SV
کلاس 1-
کلاس 1
00w.x+b = 1
w.x+b = -1
w.x+b = 0
SV
SV
SV
کلاس 1-
کلاس 1

863600130810شکل 2- SEQ شکل_2- * ARABIC 6: دسته‌بند ماشین بردار پشتیبان [26]
00شکل 2- SEQ شکل_2- * ARABIC 6: دسته‌بند ماشین بردار پشتیبان [26]

همان‌طور که در شکل (2-6) مشاهده می‌شود فراصفحه‌هایی که از نزدیکی داده‌های آموزش می‌گذرند حساس به خطا می‌باشند و احتمال اینکه برای داده‌های خارج از مجموعه آموزش قدرت تعمیم دهی خوبی داشته باشند بسیار کم است. در عوض، به نظر می‌رسد فراصفحه ای که بیشترین فاصله را از تمام نمونه‌های آموزشی دارد قابلیت‌های تعمیم دهی مناسبی را فراهم آورد. نزدیک‌ترین داده‌های آموزشی به فراصفحه‌های تفکیک کننده را بردار پشتیبان (SV) نامیده می‌شوند ADDIN EN.CITE <EndNote><Cite><Author>Bishop</Author><Year>2006</Year><RecNum>21</RecNum><DisplayText>[26]</DisplayText><record><rec-number>21</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>21</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Bishop, Christopher M</author><author>Nasrabadi, Nasser M</author></authors></contributors><titles><title>Pattern recognition and machine learning</title></titles><volume>1</volume><dates><year>2006</year></dates><publisher>springer New York</publisher><urls></urls></record></Cite></EndNote>[26]. اگر مجموعه داده به صورت نشان داده شود. Yi می‌تواند مقدار 1 و 1- دریافت کند که توسط این ثابت‌ها دسته‌های نقاط Xi مشخص می‌گردد که هر Xi یک بردار n بعدی است. هنگامی که داده‌های آموزشی که در دسته‌های صحیح دسته‌بندی شده‌اند را در اختیار داریم، SVM توسط تقسیم‌بندی فراصفحه ای آن‌ها را از هم جدا کرده و در دسته‌های جداگانه قرار می‌دهد به طوری که ، بردار W نقاط عمودی فراصفحه‌ها را جدا می‌کند و b میزان حاشیه را مشخص می‌کند. فراصفحه‌های موازی را می‌توان به صورت و تعریف کرد.
اگر داده‌های آموزشی به صورت خطی جدایی پذیر باشند، می‌توان فراصفحه‌ها را به طوری انتخاب نمود که هیچ نمونه‌ای میان آن‌ها نباشد و سپس تلاش کرد تا فاصله آن‌ها را به حداکثر رسانید. برای هر نمونه i از داده‌ها رابطه زیر را داریم:
(2-5) or
(2-6)
فاصله بین دو فراصفحه را از طریق تحلیل هندسی با رابطه می‌توان بدست آورد. بنابراین مسأله بهینه‌سازی ما به صورت زیر خواهد بود:
(2-7) or
می‌توان تصور کرد SVM بین دو دسته داده صفحه‌ای را ترسیم می‌کند و داده‌ها را در دو طرف این صفحه تفکیک می‌نماید. این فراصفحه به گونه‌ای قرار می‌گیرد که ابتدا دو بردار از یکدیگر دور می‌شوند و به گونه‌ای حرکت می‌کنند که هر یک به اولین داده نزدیک به خود برسد. سپس صفحه‌ای که در میان حد واسط این دو بردار رسم می‌شود از داده‌ها حداکثر فاصله را خواهد داشت و تقسیم کننده بهینه است.
تا اینجا، با این فرض که نمونه‌های آموزشی به صورت خطی جدایی پذیرند به استفاده از الگوریتم ماشین بردار پشتیبان پرداختیم. همان‌طور که می‌دانیم در عمل توزیع داده‌های دسته‌های مختلف ممکن است به راحتی جدایی پذیر نبوده و دارای تداخل باشد ADDIN EN.CITE <EndNote><Cite><Author>Bishop</Author><Year>2006</Year><RecNum>21</RecNum><DisplayText>[26]</DisplayText><record><rec-number>21</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>21</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Bishop, Christopher M</author><author>Nasrabadi, Nasser M</author></authors></contributors><titles><title>Pattern recognition and machine learning</title></titles><volume>1</volume><dates><year>2006</year></dates><publisher>springer New York</publisher><urls></urls></record></Cite></EndNote>[26]. در این صورت، تفکیک سازی دقیق نمونه‌ها ممکن است سبب تعمیم دهی ضعیف گردد.
یک راه حل این است که مقداری خطا در دسته‌بندی را بپذیریم. این کار با معرفی متغیر بی دقت (ξi) انجام می‌شود که نشانگر نمونه‌هایی است که توسط تابع غلط ارزیابی می‌شوند. این روش که به SVM با حاشیه‌ی نرم معروف است که اجازه می‌دهد بعضی از نمونه‌ها در ناحیه اشتباه قرار گیرند سپس آن‌ها را جریمه می‌کند؛ لذا این روش برخلاف SVM حاشیه‌ی سخت برای مواردی که نمونه‌های آموزشی به صورت خطی جدایی پذیر نیستند قابل استفاده است.
با معرفی متغیر ξi محدودیت‌های قبلی ساده‌تر شده و رابطه (2-3) به صورت زیر تغییر می‌کند:
(2-8)
5943602451735شکل 2- SEQ شکل_2- * ARABIC 7: دسته‌بند ماشین بردار پشتیبان با حاشیه نرم [26]
00شکل 2- SEQ شکل_2- * ARABIC 7: دسته‌بند ماشین بردار پشتیبان با حاشیه نرم [26]
594360184785w
ξi
ξi
00w
ξi
ξi

در این صورت مسأله بهینه‌سازی تبدیل می‌شود به یافتن w به نحوی که معادله زیر مینیمم شود:
(2-9)
ماشین بردار پشتیبان با حاشیه نرم تلاش می‌کند ξi را صفر نگه دارد در حالی که حاشیه‌های دسته‌بند را حداکثر می‌کند. SVM تعداد نمونه‌هایی که به اشتباه دسته‌بندی شده‌اند را کمینه نمی‌کند بلکه سعی دارد مجموع فواصل از حاشیه‌ی فراصفحه‌ها را کمینه نماید ADDIN EN.CITE <EndNote><Cite><Author>Bishop</Author><Year>2006</Year><RecNum>21</RecNum><DisplayText>[26]</DisplayText><record><rec-number>21</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>21</key></foreign-keys><ref-type name=”Book”>6</ref-type><contributors><authors><author>Bishop, Christopher M</author><author>Nasrabadi, Nasser M</author></authors></contributors><titles><title>Pattern recognition and machine learning</title></titles><volume>1</volume><dates><year>2006</year></dates><publisher>springer New York</publisher><urls></urls></record></Cite></EndNote>[26]. مقادیر بزرگ برای c سبب می‌شود که رابطه (2-6) مانند روش با حاشیه سخت عمل کند. ماشین بردار پشتیبان با حاشیه نرم همیشه یک راه حل پیدا می‌کند و در مقابل مجموعه داده‌هایی که دارای یک عضو جدا هستند مقاوم است و به خوبی عمل می‌کند.
2-4-6- روش‌های مبتنی بر قانونروش‌های دسته‌بندی مبتنی بر قانون دانش خروجی را به صورت یک مجموعه از قوانین اگر-آنگاه ارائه می‌دهد. این قوانین به صورت زیر می‌باشند:
If <Conditions> then <Class>
که Condition شامل یک مجموعه از شرایط می‌باشد که با عملگرهای منطقی به یکدیگر متصل می‌شوند. هر شرط شامل یک سه‌تایی مرتب <Atti, Opp, Valj> می‌باشد که Atti i امین صفت، Opp عملگر مورد استفاده برای مقایسه یک صفت با یک مقدار است و Valj نشان دهنده‌ی j امین مقدار دامنه صفت Atti می‌باشد. به عنوان مثال عبارت <Gender=Male> بررسی می‌کند که آیا مقدار صفت Gender برابر با Male هست یا خیر. در یک مجموعه شرایط نباید دو ترم متناقض وجود داشته باشد. یک قانون تنها در صورتی ارضا می‌شود که کلیه ترم‌های آن ارضا شوند که در این صورت کلاس متناظر رویت می‌شود.
مهم‌ترین مزیت روش‌های دسته‌بندی مبتنی بر قانون، قابلیت تفسیر بسیار مناسب آن‌ها می‌باشد. این قابلیت مهم سبب شده که در سال‌های اخیر توجه بسیاری از پژوهشگران به روش‌های مبتنی بر قانون جلب شود. کاربرانی که از این سیستم‌ها استفاده می‌کنند بیشتر افرادی هستند که در حوزه‌های دیگر فعالیت می‌کنند. به عنوان مثال نباید انتظار داشت که یک پزشک که می‌خواهد از یک سیستم دسته‌بندی استفاده کند، دارای اطلاعات تخصصی در مورد سیستم‌های دسته‌بندی باشد. بنابراین این پزشک نیازمند یک سیستم دسته‌بند است که دانش خروجی را به ساده‌ترین روش ممکن به او نمایش دهد. دیگر مزیت مهم این روش‌ها، نرخ دسته‌بندی قابل قبول سیستم‌های دسته‌بندی که از روش‌های مبتنی بر قانون استفاده می‌کنند می‌باشد. هر چند ممکن است روش‌های دسته‌بندی معروفی مانند SVM و ANN دقت بهتری را فراهم کنند ولی در این روش‌ها کاربر در تفسیر دانش خروجی دچار مشکل می‌شود ADDIN EN.CITE <EndNote><Cite><Author>Parpinelli</Author><Year>2002</Year><RecNum>22</RecNum><DisplayText>[27]</DisplayText><record><rec-number>22</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>22</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Parpinelli, Rafael S</author><author>Lopes, Heitor S</author><author>Freitas, Alex Alves</author></authors></contributors><titles><title>Data mining with an ant colony optimization algorithm</title><secondary-title>Evolutionary Computation, IEEE Transactions on</secondary-title></titles><periodical><full-title>Evolutionary Computation, IEEE Transactions on</full-title></periodical><pages>321-332</pages><volume>6</volume><number>4</number><dates><year>2002</year></dates><isbn>1089-778X</isbn><urls></urls></record></Cite></EndNote>[27]. در نتیجه روش‌های مبتنی بر قانون که دارای قابلیت تفسیر و دقت مناسبی هستند، می‌توانند بسیار مورد توجه قرار گیرند.
روش‌های گوناگون دسته‌بندی مبتنی بر قانون مانند AQ15، CART، CN2، ID3 و C4.5 را می‌توان به دو دسته کلی تقسیم نمود؛ الگوریتم‌های پوششی ترتیبی و الگوریتم‌های پوششی آنی. الگوریتم‌های پوششی آنی مانند C4.5 و ID3 کل مجموع قوانین را در یک زمان و به صورت گروهی استخراج می‌کنند. این روش‌ها از تقسیم و غلبه برای کشف قوانین استفاده می‌کنند. به این صورت که ابتدا مجموعه آموزش را به زیر مجموعه‌هایی تقسیم نموده سپس برای هر زیرمجموعه یک درخت ایجاد می‌کنند. در مرحله بعدی ساختار هر درخت به قوانین معادل ترجمه می‌شود. الگوریتم‌های پوششی ترتیبی مانند CN2 و AQ15 به صورت افزایشی قوانین دسته‌بندی را کشف می‌کنند. یعنی برای هر قسمت از داده‌های آموزش یک مجموعه از قوانین استخراج شده و از بین این قوانین بهترین قانون انتخاب شده و نمونه‌هایی که توسط این قانون پوشش داده شده‌اند از مجموعه آموزش حذف می‌شوند.
در استخراج مجموعه قوانین از مجموعه داده‌ها با یک مسأله بهینه‌سازی رو به رو هستیم. الگوریتم‌های تکاملی روال‌های جستجوی تصادفی الهام گرفته شده از طبیعت هستند که به عنوان روش‌های بهینه‌سازی استفاده می‌شوند. الگوریتم‌های تکاملی بر روی یک جمعیت از رشته‌ها که بیانگر راه‌حل‌های ممکن برای یک مسأله می‌باشند، کار می‌کنند. جمعیت اولیه می‌تواند تصادفی یا به کمک دانش قبلی ایجاد شود. الگوریتم هر یک از رشته راه‌حل‌ها را با یک تابع هدف که وابسته به مسأله است ارزیابی می‌کند. رشته‌هایی با کارایی بهتر برای ایجاد رشته‌های جدید مورد استفاده قرار می‌گیرند. الگوریتم‌های تکاملی رشته‌های جدید را با استفاده از عملگرهای ساده و تصادفی نظیر تبادل و جهش ایجاد می‌کنند و آن‌ها مورد ارزیابی قرار می‌دهند. چرخه انتخاب و ایجاد راه‌حل‌های جدید ادامه می‌یابد تا اینکه راه‌حل مطلوب یافت شود و یا یک شرط از پیش تعیین شده برای پایان الگوریتم تکاملی ارضا شود. از روش‌های مهم یادگیری تکاملی می‌توان به الگوریتم ژنتیک، الگوریتم بهینه‌سازی ازدحام ذرات، الگوریتم کلونی مورچه‌ها، الگوریتم زنبور عسل BA، الگوریتم رقابت استعماری ICA و روش SA اشاره کرد.
الگوریتم ژنتیک یکی از مطرح‌ترین روش‌ها برای استخراج قوانین بوده است. این الگوریتم ابتدا مجموعه از قوانین اولیه را استخراج و سپس با استفاده از عملگرهای جهش و تبدیل به مرور زمان این قوانین را تکامل می‌دهد تا مجموعه بیشتری از نمونه‌ها را پوشش دهند ADDIN EN.CITE <EndNote><Cite><Author>Cordón</Author><Year>2004</Year><RecNum>25</RecNum><DisplayText>[28]</DisplayText><record><rec-number>25</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>25</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Cordón, Oscar</author><author>Gomide, F</author><author>Herrera, Francisco</author><author>Hoffmann, Frank</author><author>Magdalena, Luis</author></authors></contributors><titles><title>Genetic fuzzy sys–s. New developments</title><secondary-title>Fuzzy Sets and Sys–s</secondary-title></titles><periodical><full-title>Fuzzy Sets and Sys–s</full-title></periodical><pages>1-3</pages><volume>141</volume><number>1</number><dates><year>2004</year></dates><isbn>0165-0114</isbn><urls></urls></record></Cite></EndNote>[28]. شرط پایانی برای این الگوریتم می‌تواند یک تعداد مشخص از تکرارها باشد و یا یک مقدار مشخص از تابع برازش باشد.
الگوریتم ژنتیک به دو دسته عمده پیتسبورگ و میشیگان تقسیم می‌شود ADDIN EN.CITE <EndNote><Cite><Author>Cordón</Author><Year>2004</Year><RecNum>25</RecNum><DisplayText>[28]</DisplayText><record><rec-number>25</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>25</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Cordón, Oscar</author><author>Gomide, F</author><author>Herrera, Francisco</author><author>Hoffmann, Frank</author><author>Magdalena, Luis</author></authors></contributors><titles><title>Genetic fuzzy sys–s. New developments</title><secondary-title>Fuzzy Sets and Sys–s</secondary-title></titles><periodical><full-title>Fuzzy Sets and Sys–s</full-title></periodical><pages>1-3</pages><volume>141</volume><number>1</number><dates><year>2004</year></dates><isbn>0165-0114</isbn><urls></urls></record></Cite></EndNote>[28]. در روش پیتسبورگ مجموعه‌ای از قوانین اگر-آنگاه در یک قالب رشته کد می‌شوند در حالی که در روش میشیگان یک قانون اگر-آنگاه به صورت یک رشته کد می‌شود.
روش پیتسبورگ کارایی هر مجموعه از قوانین را به عنوان درجه شایستگی در نظر می‌گیرد. بنابراین جستجو به دنبال مجموعه‌هایی با کارایی بالاتر است. تعدادی از قوانین بدون هیچ تغییری به عنوان قوانین ممتاز از جمعیت کنونی به نسل بعد انتقال می‌یابند. در روش پیتسبورگ یک قانون درون مجموعه خود حائز اهمیت است. چه بسا که قوانین خوبی در مجموعه ضعیفی قرار بگیرند و در روند به روز رسانی یک نسل، نادیده گرفته شوند. از آنجایی که جمعیت شامل تعدادی مجموعه می‌باشد و هر مجموعه نیز شامل تعدادی قانون است، لذا زمان اجرای آن طولانی و فضای حافظه زیادی نیز نیاز می‌باشد.
از سوی دیگر در روش میشیگان یک قانون اگر-آنگاه در قالب یک رشته کد می‌شود و کارایی یک قانون به عنوان درجه شایستگی آن مورد استفاده قرار می‌گیرد. در اینجا نیز تعدادی از قوانین بدون تغییری به عنوان قوانین ممتاز به نسل بعد منتقل می‌شوند. از آنجایی که در روش میشیگان جمعیت مورد بررسی در هر لحظه فقط شامل تعدادی قانون است، بنابراین زمان محاسبات و فضای حافظه‌ی مورد نیاز بسیار کم‌تر از روش پیتسبورگ است. در واقع می‌توان روش یادگیری به صورت آنی را معادل روش پیتسبورگ و روش یادگیری ترتیبی را معادل روش میشیگان دانست.
یکی از شاخه‌های مهم الگوریتم‌های تکاملی روش‌های هوش جمعی می‌باشند که شامل الگوریتم‌هایی نظیر الگوریتم بهینه‌سازی ازدحام ذرات، الگوریتم کلونی مورچه‌ها و الگوریتم رقابت استعماری می‌باشند. این الگوریتم‌ها قادر هستند یک جواب مناسب را برای مسأله با ابعاد بالا پیدا کنند. مهم‌ترین تفاوت این الگوریتم‌ها با سایر الگوریتم‌های تکاملی، ارتباط عامل‌ها با یکدیگر است که به صورت غیر مستقیم است ADDIN EN.CITE <EndNote><Cite><Author>Grosan</Author><Year>2006</Year><RecNum>23</RecNum><DisplayText>[13]</DisplayText><record><rec-number>23</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>23</key></foreign-keys><ref-type name=”Book Section”>5</ref-type><contributors><authors><author>Grosan, Crina</author><author>Abraham, Ajith</author><author>Chis, Monica</author></authors></contributors><titles><title>Swarm intelligence in data mining</title><secondary-title>Swarm Intelligence in Data Mining</secondary-title></titles><pages>1-20</pages><dates><year>2006</year></dates><publisher>Springer</publisher><isbn>3540349553</isbn><urls></urls></record></Cite></EndNote>[13]. این قابلیت به آن‌ها اجازه می‌دهد تا به صورت توزیع شده بخش اعظمی از فضای جستجو را پوشش دهند و در نتیجه شانس الگوریتم برای یافتن یک راه‌حل مناسب افزایش یابد.
2-5- الگوریتم بهینه‌سازی ازدحام ذراتالگوریتم بهینه‌سازی ازدحام ذرات و کلا الگوریتم‌هایی که از مفهوم حرکت دسته جمعی حیوانات نظیر دسته‌های ماهی و پرندگان الگو گرفته‌اند، سعی در به کار بردن ذراتی با هوش کم و در عین حال استفاده از هوش گروهی برخاسته از جمعیت دارند ADDIN EN.CITE <EndNote><Cite><Author>Green</Author><Year>2012</Year><RecNum>79</RecNum><DisplayText>[29]</DisplayText><record><rec-number>79</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>79</key></foreign-keys><ref-type name=”Journal Article”>17</ref-type><contributors><authors><author>Green, Robert C</author><author>Wang, Lingfeng</author><author>Alam, Mansoor</author></authors></contributors><titles><title>Training neural networks using central force optimization and particle swarm optimization: insights and comparisons</title><secondary-title>Expert sys–s with applications</secondary-title></titles><periodical><full-title>Expert sys–s with applications</full-title></periodical><pages>555-563</pages><volume>39</volume><number>1</number><dates><year>2012</year></dates><isbn>0957-4174</isbn><urls></urls></record></Cite></EndNote>[29]. از زمان معرفی PSO در سال 1995 ADDIN EN.CITE <EndNote><Cite><Author>Eberhart</Author><Year>1995</Year><RecNum>71</RecNum><DisplayText>[30]</DisplayText><record><rec-number>71</rec-number><foreign-keys><key app=”EN” db-id=”92s9f5r5x0rwr7ezx935zxfnpxazas09a9dd”>71</key></foreign-keys><ref-type name=”Conference Proceedings”>10</ref-type><contributors><authors><author>Eberhart, Russell</author><author>Kennedy, James</author></authors></contributors><titles><title>A new optimizer using particle swarm theory</title><secondary-title>Micro Machine and Human Science, 1995. MHS&apos;95., Proceedings of the Sixth International Symposium on</secondary-title></titles><pages>39-43</pages><dates><year>1995</year></dates><publisher>IEEE</publisher><isbn>0780326768</isbn><urls></urls></record></Cite></EndNote>[30]، الگوریتم بهینه‌سازی ازدحام ذرات کاربردها و بهبودهای زیادی پیدا کرده است. بسیاری تغییرات در PSO اولیه، باعث بهبود همگرایی PSO و افزایش تنوع پراکندگی ازدحام ذرات شده است.

Author:

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *