وزارت علوم، تحقيقات و فناوري
دانشگاه علوم و فنون مازندران
پايان نامه
مقطع كارشناسي ارشد
رشته : مهندسی فناوری اطلاعات
عنوان :
طراحی سیستم دسته‌بند فازي مبتنی بر بهینه سازي ازدحام ذرات براي تشخیص بیماري دیابت
استاد راهنما:
دکتر جواد وحیدی
استاد مشاور:
دکتر همایون موتمنی
دانشجو :
حسین مهدیان
(زمستان 1392)
بسم اللّه الرحمن الرحیم
تقدیم به:
ساحت مقدس آموزگارن علم و دین که معلمان بشریتند
و ادامه دهنده و فرزند آخرین فرستاده‌ی نور امام عصر (ع) …
پدر و مادر مهربانم که دعای خیرشان بهترین توشه من است
و خواهران عزیزم که همیشه مشوقم بوده‌اند
صمیمانه از درگاه خداوند مهربان سلامتی و تندرستی این عزیزان را خواستارم.
سپاسگذاری:
از زحمات اساتید گرانقدرم جناب آقای دکتر وحیدی که در این مدت مرا راهنمایی نمودند و همین طور آقای دکتر موتمنی تشکر و قدردانی می‌کنم.
چکیده
تشخیص بیماري دیابت و یا آگاهی یافتن از احتمال بالاي ابتلا به این بیماري همواره کار آسانی نخواهد بود. چرا که این بیماري علائم متعددي را بروز می‌دهد که بعضی از این علائم در سایر بیماری‌های دیگر نیز وجود دارند. بنابراین پزشک براي اتخاذ یک تصمیم مناسب، باید نتیجه‌ی آزمایش‌های بیمار و تصمیم‌هایی که در گذشته براي بیماران با وضیعت مشابه گرفته است، را بررسی کند.
در این پایان نامه از یک الگوریتم دسته‌بندی مبتنی بر قانون براي دسته‌بندی بیماران دیابتی استفاده شده است. براي استخراج قوانین فازي از یک الگوریتم بهینه سازي ازدحام ذرات استفاده شده است. این الگوریتم داراي ویژگی‌هایی است که آن را از سایر الگوریتم مورد استفاده متمایز می‌کند. از جمله‌ی این ویژگی‌ها می‌توان به تابع افزایش تنوع ذرات و تکامل هم‌زمان توابع عضویت و قوانین فازي اشاره کرد. براي ارزیابی کارایی الگوریتم از مجموعه داده‌ی دیابت استفاده شده است. نتایج ارزیابی‌ها نشان می‌دهد که الگوریتم براي مجموعه داده‌ی دیابت داراي کارایی بسیار بالایی می‌باشد. همچنین کارایی الگوریتم پیشنهادي به علت بالا بردن قابلیت تفسیرپذیري دسته‌بند (کاهش تعداد قوانین فازي) بسیار مناسب می‌باشد.
کلمات کلیدی:
تشخیص بیماری دیابت، دسته‌بند مبتنی بر قانون، الگوریتم بهینه‌سازی ازدحام ذرات، تکامل همزمان توابع عضویت و قوانین فازی.
فهرست رئوس مطالب
عنوان صفحه
فصل اول – مقدمه و کلیات تحقیق1
1-1- مقدمه2
1-2- بیان مسأله3
1-3- اهداف تحقیق5
1-4- سوالات تحقیق6
1-5- فرضیات مسأله6
1-6- نوآوری‌های تحقیق7
1-7- تعریف واژگان7
1-8- ساختار پایان نامه8
فصل دوم – ادبیات و پیشینه تحقیق10
2-1- مقدمه11
2-2- داده‌کاوی11
2-3- دسته‌بندی13
2-4- الگوریتم‌های رایج دسته‌بندی15
2-4-1- شبکه‌های عصبی مصنوعی15
2-4-2- درخت‌های تصمیم19
2-4-3- شبکه‌های بیزین21
2-4-4- K نزدیک‌ترین همسایه23
2-4-5- ماشین بردار پشتیبان24
2-4-6- روش‌های مبتنی بر قانون28
2-5- الگوریتم بهینه‌سازی ازدحام ذرات32
2-5-1- پارامترهاي پايه بهينه‌سازي ازدحام ذرات35
2-5-2- چالش‌ها و مسائل پیش روی الگوریتم بهینه‌سازی ازدحام ذرات39
2-5-2-1- مشکل ابعاد بالا40
2-5-2-2- مشکل همبستگی میان داده‌ها43
2-5-3- گونه‌های مختلف PSO47
2-5-3-1- بهینه‌سازی ازدحام ذرات مبتنی بر شبکه‌های جمعی48
2-5-3-1-1- همسایگی مبتنی بر فاصله فضایی48
2-5-3-1-2- همسایگی فزاینده48
2-5-3-1-3- بهینه‌سازی ازدحام ذرات کاملاً آگاه (FIPS)49
2-5-3-2- مدل پیوندی بهینه‌سازی ازدحام ذرات50
2-5-3-3- بهینه‌سازی ازدحام ذرات چند جمعیتی53
2-6- سیستم‌های فازی56
2-6-1- ساختار یک سیستم دسته‌بندی مبتنی بر قوانین فازی57
2-6-2- دسته‌بندی بدون استفاده از درجه قطعیت58
2-6-3- دسته‌بندی با استفاده از درجه قطعیت62
2-6-4- استنتاج فازی66
2-7- معیار‌های ارزیابی دسته‌بند‌ها68
فصل سوم – روش تحقیق72
3-1- مقدمه73
3-2- تبدیل داده‌های حقیقی به ترم‌های فازی75
3-3- تولید توابع عضویت و قوانین فازي با استفاده از الگوریتم بهینه‌سازی ازدحام ذرات77
3-3-1- کدگذاري توابع عضویت فازي78
3-3-2- کدگذاري قوانین فازي80
3-3-3- PSO پیشنهادی82
3-3-5- توابع برازش کیفیت قوانین87
3-5- نتیجه‌گیری90
فصل چهارم – محاسبات و یافته‌های تحقیق91
4-1- داده‌های مورد استفاده92
4-2- تنظیم پارامترها94
4-3- روش‌های استفاده شده به منظور مقایسه97
4-4- نتایج98
4-5- نتیجه گیری101
فصل پنجم – نتیجه گیری و پیشنهادات102
5-1- خلاصه و نتیجه‌ گیری103
5-2- پیشنهادات103
منابع:105
فهرست جداول
عنوان صفحه
جدول 2-1: مجموعه داده‌های آموزش20
جدول 2-2: جدول توزیع احتمال گره تنگی نفس23
جدول 2-3: توابع فاصله میان نمونه‌های x و y23
جدول 2-4: ماتریس اغتشاش دودویی69
جدول 4- 1: خصیصه‌های مجموعه داده Pima Indian Diabetes92
جدول 4- 2: پارامترهای قابل تنظیم توسط کاربر94
جدول 4- 3: مقادیر در نظر گرفته شده برای پارامترهای الگوریتم96
جدول 4- 4: نتایج بدست آمده از الگوریتم پیشنهادی بر روی مجموعه داده Pima99
جدول 4- 5:مقایسه نتایج بدست آمده برای مجموعه داده Pima با سایر روش‌ها99
جدول 4- 6: نتایج سایر مطالعات صورت گرفته بر روی مجموعه داده Pima100
فهرست تصاویر و نمودارها
عنوان صفحه
شکل 2- 1: فرآیند داده‌کاوی و کشف دانش12
شکل 2- 2: ساختار SLP17
شکل 2- 3: ساختار یک نرون (گره)18
شکل 2- 4: درخت تصمیم جدول (2-1)21
شکل 2- 5: مثالی از شبکه‌ی بیزین22
شکل 2- 6: دسته‌بند ماشین بردار پشتیبان25
شکل 2- 7: دسته‌بند ماشین بردار پشتیبان با حاشیه نرم27
شکل 2- 8: شبه کد الگوریتم بهینه‌سازی ازدحام ذرات34
شکل 2- 9: تشریح هندسی مولفه‌های شخصی و اجتماعی در PSO35
شکل 2- 10: ساختار یک سیستم قانونمند فازی59
شکل 2- 11: ناحیه تصمیم هر قانون فازی60
شکل 2- 12: مرزهای دسته‌بندی نُه قانون فازی60
شکل 2- 13:مرز دسته‌بندی بعد از اصلاح توابع عضویت61
شکل 2- 14: ناحیه تصمیم هر قانون فازی در حالتی که جداول قانون فازی ناکامل باشد62
شکل 2- 15: ناحیه تصمیم هر قانون فازی با درجات63
شکل 2- 16: تنظیم مرزهای دسته‌بندی بدون استفاده از درجه قطعیت63
شکل 2- 17: تنظیم مرزهای دسته‌بندی با استفاده از درجه قطعیت64
شکل 2- 18: تعیین دسته نتیجه و درجه قطعیت65
شکل 2- 19: بیش برازش71
شکل 3- 1: نمای کلی مدل پیشنهادی برای واکشی سیستم فازی74
شکل 3- 2: توابع عضویت فازی (S:Small, MS: Medium Small, M: Medium, ML: Medium Large, L: Large)76
شکل 3- 3: نمایش گرافیکی پارامترهای توابع عضویت پیشنهادی77
شکل 3- 4: نمایش گرافیکی فضای جستجو برای یک مسئله چهار بعدی با سه بازه فازی78
شکل 3- 5: کدگذاری پارامترهای متغیرهای ورودی و خروجی79
شکل 3- 6:کدگذاری هر ذره شامل پارامترهای توابع عضویت و مجموعه قوانین80
شکل 3- 7: فلوچارتPSO83
شکل 3- 8: تابع Membership_and_Rule_Learn86
شکل 4- 1: توزیع مقادیر خصیصه‌های مختل مجموعه داده Pima93
شکل 4- 2: توزیع خصیصه اول 20 نمونه‌ی اول pima94
شکل 4- 3: تأثیر پارامتر SwarmSize بر کارایی95
شکل 4- 4: تأثیر پارامتر w بر کارایی96
فصل اول – مقدمه و کلیات تحقیق

1-1- مقدمه
افزایش استفاده از کامپیوترها در فعالیت‌های کسب و کار، منجر به رشد سریع پایگاه‌های اطلاعاتی و اجتماع داده‌ها توسط بیشتر سازمان‌ها شده است. روزانه حجم عظیمی از داده‌ها تولید شده و در پایگاه‌های مختلف داده ذخیره می‌شود. در سال‌های اخیر تمایل به جستجو برای کشف الگوهای تکرار‌پذیر به منظور بهبود در تصمیم گیری افزایش چشمگیری داشته است. همچنین کاوش در داده‌های تراکنشی جهت یافتن الگوهای پنهان و تکنیک‌های کشف دانش به منظور شناخت دقیق‌تر و بیشتر تراکنش‌ها، اهمیت بسزایی یافته است. [1]. در حوزه پزشکی و سلامت با افزایش استفاده از سیستم‌های جامع درمانی و پرونده‌های الکترونیک بیمار در بیمارستان‌ها و مراکز درمانی حجم انبوهی از اطلاعات مربوط بیماران و انواع بیماری‌ها مهیا می‌شود. [2]. استخراج دانایی از حجم عظیم داده‌های مرتبط با سوابق بیماری و پرونده‌های پزشکی افراد با استفاده از فرآیند داده‌کاوی می‌تواند منجر به شناسایی قوانین حاکم بر ایجاد، رشد و افت بیماری‌ها گردیده و اطلاعات ارزشمندی را به منظور شناسایی علل وقوع بیماری‌ها با توجه به عوامل محیطی حاکم در اختیار متخصصین و دست اندر کاران حوزه سلامت قرار دهد؛ که این امر در نهایت منجر به افزایش متوسط طول عمر افراد جامعه و ایجاد آرامش می‌گردد. [3].
آنچه مسلم است با افزایش سیستم‌های الکترونیک سلامت حجم داده‌های پزشکی هر روزه در حال افزایش است. اما این مجموعه داده‌های بزرگ به طور خام هیچ کاربردی ندارد برای آنکه بتوان از این داده‌ها ارزشی را استخراج کرد نیاز به تحلیل داده‌ها و تبدیل آن به اطلاعات و دانش، یک نیاز اساسی است. با توجه به چنین حجمی از داده‌ها استفاده از عامل انسانی به عنوان تشخیص دهنده الگوها و تحلیلگر داده‌ها پاسخگو نمی‌باشد؛ لذا داده کاوی روی داده‌های پزشکی از اهمیت بالایی برخوردار است. داده‌کاوی را می‌توان از جنبه‌های مختلف در پیشگیری یا تشخیص انواع بیماری، انتخاب روش‌های درمان بیماری، مدت زمان بستری بیمار و … به کار برد.
1-2- بیان مسأله
دیابت یکی از بیماری‌های رایج در جوامع امروزی است که دارای عوارض خطرناکی می‌باشد. این بیماری اگر چه گونه‌ای از بیماری‌های قلبی محسوب نمی‌شود ولی اغلب سبب بیماری‌های قلبی می‌شود.
تشخیص بیماری دیابت و یا آگاهی یافتن از احتمال بالای ابتلا به این بیماری همواره کار آسانی نخواهد بود. چرا که این بیماری علائم متعددی را بروز می‌دهد که بعضی از این علائم در سایر بیماری‌ها نیز وجود دارند. بنابراین پزشک برای اتخاذ یک تصمیم مناسب، باید نتیجه‌ی آزمایش‌های بیمار و تصمیم‌های که در گذشته برای بیماران با وضیعت مشابه گرفته است، را بررسی کند. با توجه به حجم انبوه تعداد بيماران، مي‌توان از يك ابزار داده‌كاوي براي شناخت الگوي بيماران قبلي استفاده كرد.
در اين پايان‌نامه با توجه به ماهیت مسأله از يك الگوريتم دسته‌بندي برای تشخیص بیماری دیابت استفاده می‌کنیم سپس آن‌را با سایر روش‌ها ارائه شده مقایسه می‌کنیم. روش دسته بندی یک روش یادگیری با نظارت است که داده‌های ورودی به دو بخش داده‌های آموزش و داده‌های آزمون تقسیم می‌شوند. هر الگوریتم کاندید، ابتدا با استفاده از مجموعه داده آموزش یک مدل را که نشان دهنده الگوی حاکم بر داده‌ها می‌باشد را استخراج می‌کند و سپس با استفاده از مجموعه آزمون دقت مدل ارائه شده برای دسته‌بندی را بررسی می‌کند.
الگوریتم‌های متعددی برای دسته بندی ارائه شده‌اند که از آن دسته می‌توان؛ به شبکه‌های بیزین [4]، روش‌های مبتنی بر درخت [5]، الگوریتم ماشین بردار پشتیبان [6]، روش‌های مبتنی بر مجموعه فازی [7]، الگوریتم‌های فرا اکتشافی [8] و شبکه‌های عصبی [9] اشاره کرد.
در این نوشتار قصد داریم برای استخراج قوانين فازي از يك الگوريتم آموزش دیده مبتنی بر هوش جمعی، بهینه‌سازی ازدحام ذرات (PSO) استفاده کنیم. خاصیت اصلی الگوریتم‌های هوش جمعی تبادل اطلاعات بین ذرات است که در یافتن حالت بهینه بسیار موثر می‌باشند.
سعی شده با در نظر گرفتن نقاط ضعف و قوت روش‌های مختلف داده کاوی یک الگوریتم ترکیبی برای تشخیص بیماری ارائه شود. الگوریتم شبکه عصبی معمولاً نرخ دسته بندی مناسبی را ارائه می‌دهد ولی از شفافیت لازم برخوردار نیست. بنابراین نمی‌توان این اطلاعات را توسط سیستم‌های خبره بررسی کرد. برای حل این مسئله باید یک ارائه قابل فهم انسانی از دسته‌بندی ایجاد کرد. این هدف می‌تواند با استخراج قوانین فازی تولید شده که برای کاربر قابل فهم است بدست بیاید.
دو معیار اصلی برای برازش الگوریتم‌های دسته‌بندی؛ نرخ دسته بندی و قابلیت تفسیر می‌باشد. نرخ دسته بندی میزان دقت کار الگوریتم در دسته بندی نمونه‌های آزمون را نشان می‌دهد و قابلیت تفسیر به معنی میزان سادگی و قابلیت توسعه روش دسته بندی می‌باشد.
در سال‌های اخیر قوانین فازی از آن جهت که هم دقت مناسبی دارند وهم قابلیت تفسیر مناسبی را ارائه می‌دهند بیشتر مورد توجه قرار گرفته‌اند. یک الگوریتم فازی از آن جهت مورد توجه می‌باشد که شامل مجموعه‌ای از قوانین اگر-آنگاه فازی می‌شود که تفسیر آن‌ها توسط انسان خبره امکان پذیر است. مسئله اساسی در چنین سیستم‌هایی انتخاب مجموعه‌ای از قوانین فازی بهینه است؛ لذا این مسئله را می‌توان نوعی از بهینه سازی ترکیبی در نظر گرفت که با رشد ابعاد مسئله دسته بندی، تعداد جواب‌های بهینه محلی نیز به صورت نمایی افزایش می‌یابد و الگوریتم کاندید برای حل آن باید مجموعه‌ای از جواب‌های بهینه یا نزدیک به بهینه را ارائه دهد [10].
روش‌های مختلفی برای استخراج قوانین از مجموعه داده وجود دارد ازجمله آن‌ها می‌توان به روش‌های مبتنی بر شبکه‌های عصبی [11] و روش‌های مبتنی بر خوشه‌بندی [12] اشاره کرد. با توجه به قابلیت‌های روش‌های فرا اکتشافی برای پوشش فضای جستجو، این الگوریتم‌ها برای استخراج قوانین می‌توانند یک گزینه مناسب باشند. این روش‌ها با ایجاد یک راه حل اولیه در فضای جستجو آغاز می‌شوند و سپس به وسیله یک مجموعه قواعد جستجوی بهینه شروع می‌شود. در هر مرحله از الگوریتم جستجو همواره یک راه حل یا یک مجموعه از راه حل‌ها وجود دارند که وضعیت فعلی الگوریتم را نشان می‌دهند. برخی از روش‌های اکتشافی، روش‌های راه حل به راه حل هستند یعنی در فضای جستجوی مسئله از طریق یک راه حل به راه حل دیگر دست می‌یابند. بقیه روش‌ها بر پایه مجموعه می‌باشند که با اعمال تغییراتی در مجموعه فعلی به مجموعه جدید می‌رسیم. برای استفاده از روش‌های مکاشفه‌ای در برنامه‌های داده کاوی باید آن‌ها را با یک روش محلی ادغام کنیم. این روش‌های محلی، استراتژی کلی روش‌های مکاشفه‌ای را هدایت می‌کنند.
1-3- اهداف تحقیق
هدف از روش ارائه شده کشف الگوها در میان مجموعه داده بیماران دیابتی برای کمک به پزشکان در تصمیم گیری می‌باشد رسیدن به نرخ دسته بندی و قابلیت تفسیر مطلوب از مجموعه داده با ترکیب مفهوم فازی و الگوریتم هوش جمعی بهینه‌سازی ازدحام ذرات برای استخراج قوانین فازی بدست می‌آید.
1-4- سوالات تحقیق
سوالاتی که در این تحقیق سعی شده به آن‌ها پاسخ دهیم به شرح زیر می‌باشد:
در داده‌های با ابعاد بالا چه روشی برای انجام دسته بندی با نرخ صحیح دسته بندی مناسب است؟
چگونه با ترکیب الگوریتم بهینه‌سازی محلی و سراسری نتایج جستجو را بهبود دهیم؟
چه الگوریتمی ارائه دهیم برای اینکه هم نرخ دسته بندی بهبود یابد و هم قابلیت تفسیر خوبی داشته باشد؟
نقش روش ترکیبی از سیستم فازی، الگوریتم ازدحام ذرات در انجام بهتر عمل دسته بندی چه خواهد بود؟
1-5- فرضیات مسأله
در این پایان نامه قصد داریم با کمک تکنیک دسته بندی، دانش را از مجموعه داده‌های دیابت واکشی کنیم که این دانش در قالب مجموعه قوانین فازی نمایش داده می‌شود. الگوریتم پیشنهادی با استفاده از ترکیب مکاشفه‌ی بهینه سازی ازدحام ذرات ارتقاء یافته مجموعه‌ای از قوانین فازی که بیانگر الگوی حاکم بر داده‌های مربوط به بیماران دیابتی است، استخراج خواهند شد. این الگوریتم با توجه به معیارهای مورد استفاده برای بهینه سازی پایگاه قوانین به دنبال مجموعه قوانینی می‌گردد که بهترین معیارهای ذکر شده را دارا باشد. هدف ما به دست آوردن دانش بهینه می‌باشد که با معیارهای نظیر دقت و قابلیت تفسیر مورد ارزیابی قرار می‌گیرد.
مجموعه داده دیابت بکار گرفته شده در این پایان نامه مجموعه داده Pima از دانشگاه UCI است که شامل 786 نمونه و 8 صفت می‌باشد. متغیر کلاس این مجموعه دو مقدار 0 و 1 را به خود اختصاص می‌دهد که به ترتیب بیانگر عدم ابتلا و ابتلا به این بیماری می‌باشند. که صفت‌های آن شامل: تعداد دفعات بارداری، غلظت گلوکز پلاسما، فشارخون دیاستولی بر حسب میلی لیتر جیوه، ضخامت چین پوستی یک عضله در بازوها، تزریق سرم دو ساعت، شاخص توده‌ای بدن برای بررسی چاقی، سن و متغیر کلاس (0 و 1) می‌باشد.
1-6- نوآوری‌های تحقیق
ارائه یک مدل ترکیبی از الگوریتم ازدحام ذرات و مجموعه فازی
ارائه یک روش جدید برای افزایش قابلیت اکتشاف در الگوریتم بهینه‌سازی ازدحام ذرات
ارائه یک روش جدید برای افزایش قابلیت بهره‌کشی در الگوریتم بهینه‌سازی ازدحام ذرات
روش کدگذاری هم‌زمان توابع عضویت و قوانین فازی
1-7- تعریف واژگان
داده کاوی: به استخراج اطلاعات از میان حجم انبوهی از اطلاعات که به آن کشف دانش نیز می‌گویند.
دسته‌بندی: برای تخصیص یک برچسب به مجموعه‌ای از داده‌ها که دسته‌بندی نشده‌اند، استفاده می‌شود. در دسته‌بندی یک متغیر هدف گروهی وجود دارد که به دسته‌ها و گروه‌های از پیش تعیین شده افراز می‌گردد. سپس داده‌ها بر اساس ویژگی‌هایشان به دسته‌هایی که نام آن‌ها از قبل مشخص می‌باشد، تخصیص داده می‌شوند.
الگوریتم‌های تکاملی: الگوریتم‌هایی که جنبه‌های انتخاب طبیعی و بقای بهترین‌ها را با هم ترکیب می‌کنند. یک الگوریتم تکاملی جمعیتی که شامل ساختارهایی می‌شوند که عموماً به صورت تصادفی مقدار دهی اولیه شده‌اند و سپس این ساختارها طبق قوانین مشخصی مانند انتخاب و جهش تکامل می‌یابند. یک محیط که برای تمام اعضا مشترک است مناسب بودن و کارایی هر یک از اعضای جمعیت را مشخص می‌کند. اعضای مناسب‌تر شانس بیشتر برای انتخاب و یا ساخت مجدد توسط هر یک از عملگرهای الگوریتم را دارند.
هوش جمعی: نوعی از روش‌های تکاملی هستند که شیوه ارتباط عامل‌ها با یکدیگر از طریق محیط و به صورت غیر مستقیم است. این قابلیت اجازه می‌دهد، این الگوریتم‌ها به صورت توزیع شده بخش عظیمی از فضای جستجو را پوشش دهند و در نتیجه شانس الگوریتم برای یافتن یک راه‌حل مناسب افزایش یابد. در سطح بالاتر، گروهی از عامل‌ها که با هم برای رسیدن به اهداف مشخص رفتار خاصی را بروز می‌دهند. هوش همگانی از مجموع گروه‌های بزرگی از عامل‌های نسبتاً ساده پدیدار می‌شود. [13].
استنتاج فازی: وظیفه فرایند استنتاج نگاشت ورودی‌های فازی (که از فرایند فازی سازی دریافت شدند) به پایگاه قوانین فازی و تولید خروجی فازی برای هر یک از قوانین است.
1-8- ساختار پایاننامه
مطالبی که در فصول بعدی ارائه خواهد شد به شرح زیر خواهد بود:
در فصل دوم مفاهیم پایه‌ای مانند داده‌کاوی، کلیات مربوط به الگوریتم‌های دسته بندی، الگوریتم‌های رایج دسته‌بندی و معیارهای ارزیابی این الگوریتم‌ها مورد بحث قرار می‌گیرد.
در فصل سوم حاوی کارهای انجام شده و تحقیقات مرتبط با موضوع می‌باشد، همچنین فضای کلی مسأله معرفی شده و الگوریتم‌های بهینه سازی ازدحام ذرات پیشنهادی برای ایجاد دسته‌بند فازی شرح داده می‌شوند.
در فصل چهارم مدل پیشنهادی برای دسته‌بندی بر روی مجموعه داده‌های دیابت اعمال و نتایج روش پیشنهادی با نتایج روش‌های معروف در این زمینه مورد مقایسه و ارزیابی قرار گرفته است.
فصل پنجم نیز حاوی خلاصه، نتیجه‌گیری و پیشنهادات می‌باشد.
فصل دوم – ادبیات و پیشینه تحقیق

2-1- مقدمه
دنیای مدرن در حقیقت دنیایی در محاصره حجم عظیمی از داده‌ها، چه عددی و چه انواع دیگر است. پیشرفت فناوری اطلاعات و مجهز شدن به ابزار رایانه‌ای امکان جمع‌آوری اطلاعات در زمینه‌های مختلف را فراهم آورده و منجر به پیدایش ساختارهای داده‌ای با حجم عظیم شده است. دست پیدا کردن به اطلاعات نهفته در پایگاه داده شرکت‌ها، دانشگاه‌ها، مؤسسات دولتی و سایر مراکز نیازمند مدیریتی جدید است و با به‌کارگیری سیستم‌های سنتی این امر تحقق نمی‌یابد. ضمن اینکه با گسترش رقابت در بخش‌های مختلف علمی، اجتماعی، سیاسی و غیره زمان مورد نیاز برای دسترسی به این اطلاعات نیز اهمیت دوچندان پیدا کرده است. بنابراین نیاز به طراحی سیستم‌های هوشمندی که توانایی دست‌یابی به اطلاعات مورد نظر کاربر را در مدت زمان کوتاه و با کم‌ترین مداخله کاربر را داشته باشند کاملاً مشهود است.
2-2- داده‌کاوی
داده کاوی فرآیندی است که از آغاز دهه‌ی 90 پا به عرصه‌ی ظهور گذاشته و با نگرشی نو به مسئله‌ی استخراج اطلاعات از پایگاه داده می‌نگرد. این فرآیند یک مرحله فراتر از بازیابی ساده داده‌ها است و این اجازه را می‌دهد که دانش را در میان حجم انبوه داده‌ها کشف کرد [14]. داده کاوی یک علم میان رشته‌ای است و ترکیبی از علومی نظیر پایگاه داده، تحلیل آماری، هوش مصنوعی و بینایی ماشین می‌باشد. داده کاوی یک مرحله ضروری از فرآیند بزرگ‌تر کشف دانش می‌باشد که شامل مراحل زیر می‌باشد [15] :
1.پاک‌سازی داده‌ها: حذف نویز و داده‌های ناسازگار و نا ایستا.
2.یکپارچگی داده‌ها: ترکیب انواع داده‌های پراکنده و ناهمگن از منابع مختلف.
3.انتخاب ویژگی‌ها: انتخاب صفت‌های تأثیرگذار از داده‌ها.
4.تبدیل داده‌ها: تبدیل یا ترکیب داده‌ها به اشکالی که برای بکار بردن در داده‌کاوی مناسب باشند.
5.داده‌کاوی: روش‌های مختلف را برای استخراج الگو استفاده می‌کند.
6.ارزیابی الگو: الگوهای مناسب برای ارائه دانش را بر اساس معیارهای مشخص شناسایی می‌کند.
7.ارائه دانش: دانش کشف شده را با استفاده از روش‌های نمایش اطلاعات نشان می‌دهد.
داده‌کاوی از دو مرحله اصلی تشکیل شده است؛ مرحله اول پیش پردازش داده‌ها که در این مرحله خصیصه‌های با تأثیر بالاتر از داده‌های سطح پایین استخراج می‌شود. مرحله دوم تشخیص الگو می‌باشد که به کشف الگوی موجود در داده‌ها به کمک صفات و خصیصه‌های بدست آمده می‌پردازد.
داده‌کاوی را می‌توان سیر تکاملی طبیعی تکنولوژی اطلاعات دانست، که این سیر تکاملی ناشی از یک بلوغ در صنعت پایگاه داده نظیر: عملیات جمع‌آوری داده‌ها و ایجاد پایگاه داده، مدیریت داده و تحلیل و فهم داده می‌باشد.
داده كاوي تحليل داده‌های قابل مشاهده براي كشف ارتباطات غيرمنتظره و خلاصه كردن داده‌ها به صورتي بديع است كه براي دارنده‌ی اطلاعات مفيد و قابل درك باشد [16]. كاوش اطلاعات، حجم عظيمي از داده‌های خام را به فرمي تغيير می‌دهد كه انسان بتواند آن‌ها را به راحتي بفهمد و براي تصميم گيري بتواند از اين اطلاعات استفاده كند. در مسائل داده كاوي، هر چه حجم داده‌ها بيشتر می‌شود، ميل بيشتري براي كشف الگوهاي مخفي در داده‌ها به وجود می‌آيد. در قدم اصلي داده كاوي ممكن است از چندين الگوريتم داده كاوي استفاده شود. كار اصلي الگوريتم داده كاوي با توجه به نوع مسئله‌ي كشف دانش تغيير می‌کند اما دو نوع اصلي الگوریتم‌های داده كاوي، دسته‌بندي و خوشه‌بندي است.
اصلی‌ترین دلیلی که باعث شد داده کاوی در علوم پزشکی مورد توجه بسیاری قرار بگیرد، مسأله در دسترس بودن حجم وسیعی از داده‌ها و نیاز شدید به اینکه از این داده‌ها، اطلاعات و دانش استخراج شود. داده‌کاوی عبارت است از استخراج دانش از مجموعه‌ای از داده‌ها.
2-3- دسته‌بندی
هرگاه داده‌ها دارای خصیصه‌ای خاص باشند که مستقیماً از دیگر خصایص به وجود نیامده باشد اما بین آن مشخصه و دیگر ابعاد رابطه وابستگی وجود داشته باشد، در این صورت می‌توان با کشف مدلی بر اساس دیگر مشخصه‌ها، آن بعد مذکور (که نشان دهنده دسته خاصی از داده‌ها است) را شناسایی نمود. فرض کنید که مشخصات تعدادی بیمار در پایگاه داده‌ای وجود دارد که قبلاً با استفاده از آزمایش خاص دو نوع بیماری مشخص شده که هر‌کدام از این بیماران به کدام بیماری مبتلا هستند، در این جا هیچ فردی حق ندارد هر دو بیماری را داشته باشد، سالم بوده و یا بیماری دیگری داشته باشد، به این معنی که دسته‌ها فضای مسئله را افراز می‌کند. در چنین پایگاه داده‌هایی برای هر بیمار یک رکورد خاص وجود دارد که شامل علائم بیمار و در نهایت نام یا برچسب بیماری که بیمار به آن مبتلا شده است می‌باشد. یک داده کاو تصمیم می‌گیرد سیستمی را ابداع کند که طی آن بدون آزمایش و فقط از روی علائم بیمار بتوان نوع بیماری وی را تشخیص داد. این تصمیم ممکن است به هر دلیلی مثلاً کمبود امکانات صورت گرفته باشد. آنچه باید انجام شود عملیات دسته بندی نامیده می‌شود. هدف دسته‌بندی؛ آموزش یک نگاشت از ورودی‌های x به خروجی‌های y است، که در آن ، C تعداد کلاس‌ها را مشخص می‌کند. اگر C=2 دسته‌بندی را دسته‌بندی دودویی می‌نامیم ()، اگر C>2 باشد، این نوع دسته‌بندی را دسته‌بندی چند کلاسه می‌نامیم [17].
دسته‌بندی داده‌ها یک فرآیند دو مرحله‌ای است. اولین مرحله ساخت مدل و دومین مرحله استفاده از مدل و پیش‌بینی کلاس از طریق مدل ساخته شده است. برای این منظور باید مجموعه داده‌ها را به دو دسته داده‌های آموزش و داده‌های تست تقسیم کنیم. با استفاده از داده‌هایی که برچسب آموزش خورده‌اند یک دسته‌بند ایجاد می‌شود که بر اساس آن بتوان داده‌های فاقد برچسب را در دسته‌های مربوط به خودشان قرار داد. کارایی دسته‌بند ساخته شده با داده‌های تست (که به صورت تصادفی از میان داده‌ها انتخاب شده‌اند) مورد سنجش قرار می‌گیرد و مدل روی آن‌ها اجرا می‌شود تا دقت پیش بینی دسته‌بند بررسی گردد، چنان که مدل دارای دقت مناسبی باشد برای دسته‌بندی داده‌ها به کار می‌رود.
در دسته‌بندی یادگیری به وسیله نمونه‌ها انجام می‌گیرید و برچسب هر یک از دسته‌ها مشخص است. سپس نمونه‌ها بر حسب ویژگی‌هایشان به دسته‌های از قبل مشخص شده، تخصیص داده می‌شوند. در حالی که در خوشه‌بندی داده‌ها به خوشه‌های مختلف که از قبل معین نیستند تقسیم می‌شوند، بر این اساس که داده‌های درون خوشه مشابه و داده‌های خوشه‌های مختلف متفاوت باشند. خوشه بندي به فرآيند تقسيم بندي داده به يك يا چند گروه به طوري كه فاصله‌ی بين خوشه‌ها حداكثر و فاصله‌ی درون خوشه‌ها حداقل باشد، اطلاق می‌شود.
2-4- الگوریتم‌های رایج دسته‌بندی
روش‌های زیادی برای دسته‌بندی وجود دارد که از جمله می‌توان به مواردی که در ادامه به آن‌ها اشاره می‌شود اشاره کرد:
شبکه‌های عصبی مصنوعی1
درخت‌های تصمیم2
شبکه‌های بیزین
k نزدیک‌ترین همسایه3
ماشین بردار پشتیبان4
روش‌های مبتنی بر قانون
2-4-1- شبکه‌های عصبی مصنوعی
مطالعه شبکه‌های عصبی مصنوعی تا حد زیادی الهام گرفته از سیستم‌های یادگیر طبیعی است که در آن‌ها یک مجموعه پیچیده از نرون‌های به هم متصل در کار یادگیری دخیل هستند. گمان می‌رود که مغز انسان از تعداد 1011 نرون تشکیل شده باشد که هر نرون با تقریباً 104 نرون دیگر در ارتباط است. سرعت انتقال نرون‌ها در حدود 10-3 ثانیه است که در مقایسه با کامپیوترها ( 10-10 ثانیه) بسیار ناچیز می‌نماید. با این وجود آدمی قادر است در 0.1 ثانیه تصویر یک انسان را باز شناسائی نماید. این قدرت فوق‌العاده باید از پردازش موازی توزیع شده در تعدادی زیادی از نرون‌ها حاصل شده باشد [18].
این شبکه‌ها یادگیری را از روی مثال‌ها و نمونه‌ها انجام می‌دهند و از این لحاظ در عمل یادگیری شبیه به انسان عمل می‌کنند. مزیت دیگر آن‌ها این است که این شبکه‌ها از توانایی تعمیم دهی ذاتی برخوردار هستند؛ یعنی این شبکه‌ها توانایی تشخیص الگوهایی را که شبیه نمونه‌هایی که قبلاً یاد گرفته باشد را دارد نه اینکه تنها الگوهای دقیقاً همانند نمونه‌های آموزشی را تشخیص دهد [19].
شبکه عصبی مصنوعی روشی عملی برای یادگیری توابع گوناگون نظیر توابع با مقادیر حقیقی، توابع با مقادیر گسسته و توابع با مقادیر برداری می‌باشد. یک نرون به تنهایی فقط می‌تواند برای شناسایی توابعی که به صورت خطی تفکیک پذیرند بکار رود، از آنجا که در مسائل واقعی عموماً توابع به صورت خطی جدایی پذیر نیستند شبکه‌ای از نرون‌ها مورد نیاز می‌باشد.
انواع شبکه‌های عصبی برای حل مسائل مختلف یادگیری بانظارت، یادگیری بدون نظارت و یادگیری تقویتی استفاده می‌شوند. شبکه‌های عصبی بر حسب انواع اتصالات به دو نوع رو به جلو FNN5 و بازگشتی RNN6 تقسیم می‌شوند. FNN ها معمول‌ترین نوع شبکه‌های عصبی است که در کاربردهای مختلف استفاده می‌شوند. لایه اول لایه ورودی نامیده می‌شود و لایه آخر لایه خروجی است و هر تعداد لایه میان این دو لایه را لایه‌های میانی یا مخفی می‌نامند زیرا در عمل ما تنها با ورودی و خروجی‌های شبکه عصبی کار داریم. شبکه عصبی به صورت یک جعبه سیاه کار می‌کند و دسترسی مستقیم به لایه‌های میانی میسّر نیست. شبکه‌های عصبی بازگشتی دارای چرخه‌های جهت‌دار در ساختار گراف‌های ارتباطشان هستند یعنی با دنبال کردن ارتباطات بین گره‌ها می‌توان به گره‌ها قبلی و آغازین بازگشت. RNN ها با توجه به ساختارشان دینامیک پیچیده‌ای دارند و این امر آموزش این شبکه‌ها را بسیار پیچیده می‌کند. ضمن اینکه از لحاظ بیولوژیکی شبکه‌های عصبی بازگشتی به واقعیت نزدیک‌تر هستند.
شبکه‌های FNN با بیش از یک لایه مخفی را MLP7 و شبکه‌های FNN با یک لایه مخفی را SLP می‌نامیم و در آن خروجی نرون‌ها در هر لایه تابعی غیر خطی از خروجی‌های لایه‌های قبلی است. تعداد نرون‌های لایه ورودی و خروجی ثابت است، تعداد نرون‌های لایه ورودی برابر با فضای مشخصه‌ها و تعداد نرون‌های لایه خروجی با توجه به تعداد کلاس‌ها مشخص می‌شود. در MLP گره‌ها (نرون‌ها) معمولاً در لایه‌هایی در شبکه عصبی مرتب می‌شوند هر گره تنها ورودی‌هایی از لایه قبل دریافت می‌کند و تابعی از ورودی‌ها را ارائه می‌دهد.
هر واحد یک خروجی را منتشر می‌کند که تابعی غیر خطی از مقادیر ورودی است [20]. f تابع فعال‌سازی است که بر روی مجموع ضرب وزن‌ها در ورودی‌های هر گره اعمال می‌گردد. معروف‌ترین تابع فعال‌سازی که در شبکه‌های عصبی استفاده می‌شود تابع سیگموئید یا لجستیک نام دارد که در آن؛
(2-1)
رفتار شبکه عصبی با توجه به مقادیر وزن‌های آن تعیین می‌شود. شبکه عصبی بهترین مقادیر وزن‌ها و بایاس‌ها را با توجه به مجموعه داده موجود یاد می‌گیرد، در واقع آموزش شبکه عصبی شامل تنظیم وزن‌ها و بایاس‌ها تا موقعی که شرایط مشخصی برآورده گردد می‌شود. تنظیم وزن‌ها به گونه‌ای صورت می‌گیرد که میزان خطا میان خروجی مطلوب و خروجی شبکه عصبی را کاهش دهد.
برای آموزش (تعیین وزن‌ها و بایاس‌ها) شبکه عصبی FNN دو راه وجود دارد: روش‌های کلاسیک مانند الگوریتم انتشار به عقب (8BP) و روش‌های بهینه‌سازی هوشمند مانند الگوریتم ژنتیک و الگوریتم بهینه‌سازی ازدحام ذرات9 PSO.
روش BP بر پایه گرادیان نزولی در فضای خطا است که دارای قابلیت جستجوی محلی می‌باشد. اصلاح وزن‌های شبکه عصبی به گونه‌ای صورت می‌گیرد که در هر دور خطای میان خروجی مطلوب و خروجی شبکه عصبی کاهش یابد. این خطا به صورت زیر تعریف می‌شود:
(2-2)
به این صورت خطا برای مجموع n نمونه آموزشی محاسبه می‌گردد. خروجی مطلوب و خروجی شبکه عصبی می‌باشد. قدرت الگوریتم BP در قابلیت محاسبه خطای موثر برای هر واحد مخفی است. نهایتاً هر یک از وزن‌ها در دور m+1 به صورت زیر تغییر می‌کند:
(2-3)
(2-4)
در رابطه (2-4) نرخ یادگیری و اختلاف میان خروجی مطلوب و خروجی شبکه عصبی است. در روش‌های مبتنی بر گرادیان نزولی مانند BP ممکن است همگرا شدن به یک مقدار مینیمم زمان زیادی لازم داشته باشد. همچنین در این روش‌ها اگر در سطح خطا چندین مینیمم محلی وجود داشته باشد تضمینی وجود ندارد که الگوریتم بتواند مینیمم مطلق را پیدا بکند [21].
روش‌های تکاملی برای اجتناب از گیر افتادن در مینیمم محلی و افزایش قدرت تعمیم دهی که از نقاط ضعف الگوریتم‌های مبتنی بر گرادیان نزولی برای آموزش شبکه عصبی بود بکار گرفته شدند. در این روش‌ها ابتدا جمعیت اولیه به صورت از پیش تعریف شده یا تصادفی مشخص می‌شود. هر یک از اعضای جمعیت یکی از راه‌حل‌های بالقوه است که الگوریتم تکاملی مورد نظر در طول دوره‌های مختلف فضای مسأله را جستجو و جمعیت را به سمت نقطه بهینه که کارایی را بهبود می‌دهد حرکت می‌دهد [22].
2-4-2- درخت‌های تصمیم
درخت‌های تصمیم از بالا به پایین یکی از الگوریتم‌های رایج دسته‌بندی می‌باشند [23]. از مهم‌ترین دلایل رایج بودن این الگوریتم شفافیت و قابلیت تفسیر بالای این الگویتم است. مزیت دیگر موجود بودن پیاده‌سازی‌های قوی نظیر C4.5 است. الگوریتم‌های درخت‌های تصمیم با ساخت یک الگوریتم از بالا به پایین توسط انتخاب صفت در هر لحظه و جداسازی داده‌ها با توجه به مقادیر صفتشان انجام می‌شود [23]. مهم‌ترین صفت به عنوان ریشه درخت و بقیه گره‌ها نیز به ترتیب اولویت در سطح‌های بعدی قرار می‌گیرند به گونه‌ای که گره‌هایی که ضریب دست‌یابی اطلاعات و برچسب دسته را نشان می‌دهند نزدیک ریشه قرار می‌گیرند. شکل (2-4) چگونگی ساخت درخت تصمیم برای جدول (2-1) را نمایش می‌دهد.
جدول 2-1: مجموعه داده‌های آموزش
صفت اولصفت دومصفت سومصفت چهارمکلاسa1a2a3a4Yesa1a2a3b4Yesa1b2a3a4Yesa1b2b3b4Noa1c2a3a4Yesa1c2a3b4Nob1b2b3b4Noc1b2b3b4No
برای بالا بردن قابلیت تفسیر درخت لازم است که اندازه درخت را کاهش دهیم که این کار موجب کمتر شدن پایداری می‌گردد. روش‌های بهینه‌سازی مختلفی برای تعیین ساختار بهینه درخت در مسائل دسته‌بندی مورد استفاده قرار گرفته‎اند. هنگامی که بخواهیم الگوریتم‌های درخت‌های تصمیم را بر روی مجموعه داده‌های بزرگی به کار گیریم، ناپایدار بودن این الگوریتم‌ها بیشتر نمایان می‌شود زیرا دست‌یابی یکباره به همه داده‌ها و ایجاد یک درخت تصمیم یکتا عملی نمی‌باشد.
2-4-3- شبکه‌های بیزین
در روش‌های دسته‌بندی آماری برخلاف سایر دسته‌بندها میزان عضویت یک نمونه به هر کلاس را با یک احتمال نشان می‌دهد. روش شبکه‌های بیزین رایج‌ترین روش دسته‌بندی آماری و از روش‌های ساده و موثر محسوب می‌شود. در این روش احتمال شرطی هر صفت داده شده را توسط برچسب دسته مربوطه از داده‌های آموزشی یاد می‌گیرید. سپس عمل دسته‌بندی توسط بکار بردن قوانین بیز برای محاسبه مقدار احتمالی دسته نتیجه نمونه داده شده با دقت بالایی انجام می‌شود. در حالت معمولی این کار با تخمین احتمالاتی هر ترکیب ممکن از صفات صورت می‌گیرد ولی هنگامی که تعداد صفات خیلی زیاد باشد، این امر امکان پذیر نیست. بنابراین یک فرض مستقل قوی اتخاذ می‌شود که همه صفات با مشخص بودن مقدار صفت دسته مستقل می‌باشند. با در نظر گرفتن این فرض لازم است که فقط احتمالات حاشیه‌ای هر صفت دسته محاسبه گردد. با این حال این فرض به صورت غیرواقعی می‌باشد و شبکه‌های بیزین با مدل کردن صریح، وابستگی بین صفات آن را در نظر نمی‌گیرند [4].
مسأله یادگیری ساختار شبکه بیزین به این صورت بیان می‌شود که با داشتن یک مجموعه آموزشی از n نمونه u؛ یک شبکه پیدا کنیم که بهترین تطبیق را با A داشته باشد. معمول‌ترین روش برای این مسأله معرفی یک تابع هدف است که هر شبکه با توجه به داده‌های آموزشی و جستجوی بهترین شبکه بر اساس این تابع ارزیابی شود [24]. چالش‌های بهینه‌سازی کلیدی انتخاب تابع هدف و تعیین روال جستجو برای بهترین شبکه می‌باشد.
شبکه بیزین مدلی گرافیکی برای نشان دادن توزیع احتمالی مجموعه‌ای از متغیرها است. دانش بدست آمده برای یک مسئله به صورت اطلاعات کمی و کیفی در این گراف مدل می‌شود. این کار با مشخص کردن مجموعه‌ای از فرضیات استقلال خطی توسط کمان‌های گراف، همراه با ذکر مقادیر احتمال شرطی گره‌ها انجام می‌شود [17].
شکل 2- 5: مثالی از شبکه‌ی بیزین [24]
هر متغیری به صورت یک گره در شبکه بیزین نمایش داده شده و برای هر متغیر دو نوع اطلاعات ارائه می‌گردد: کمان‌های شبکه برای نشان دادن رابطه استقلال شرطی بکار می‌رود یک متغیر با دانستن والدین آن از گره‌های غیر فرزند آن مستقل است. جدولی نیز ارائه می‌گردد که توزیع احتمال هر گره برای والدین بلا فصل آن را مشخص می‌کند.
جدول 2-2: جدول توزیع احتمال گره تنگی نفس [24]
D=1D=0BC0.80.2000.20.8100.90.1010.60.4112-4-4- K نزدیک‌ترین همسایه
الگوریتم k نزدیک‌ترین همسایه مثالی از یادگیری بر اساس نمونه است که در آن مجموعه داده آموزشی برای ایجاد یک مدل دسته‌بندی مورد استفاده قرار می‌گیرند. بنابراین یک دسته‌بندی برای یک نمونه دسته‌بندی نشده ممکن است به سادگی با مقایسه آن با شبیه‌ترین نمونه‌ها در مجموعه آموزشی یافت شود. روال این الگوریتم به این صورت است که برای هر نمونه جدید با مقایسه آن با k نمونه آموزشی نزدیکتر، دسته نتیجه را مشخص می‌کنیم [25]. بنابراین لازم است معیاری را برای تعیین فاصله بین نمونه‌ها مشخص نماییم. برای تعیین فاصله بین دو نمونه و توابع فاصله فراوانی می‌تواند مورد استفاده قرار گیرد جدول (2-3).
جدول 2-3: توابع فاصله میان نمونه‌های x و y
تابع فاصلهفرمولفاصله اقلیدسیd(x,y)=√(∑_(i=1)^n▒〖(x_i-y_i)〗^2 ) فاصله همینگd(x,y)=∑_(i=1)^n▒|x_i-y_i | فاصله چبیشفd(x,y)=max_(i=1,2,…,n) |x_i-y_i | فاصله مینکوفسکیd(x,y)=√(p&∑_(i=1)^n▒〖(x_i-y_i)〗^p ) p>0 فاصله کانبراd(x,y)=∑_(i=1)^n▒|x_i-y_i |/(x_i+y_i ) به دست آوردن معیار فاصله برای داده‌های عددی آسان است ولی متغیرهای گروهی نیاز به مکانیزم خاصی برای فاصله دارند. زمان محاسباتی روش k نزدیک‌ترین همسایه به صورت نمایی از تمام نقاط افزایش می‌یابد لذا از لحاظ محاسباتی الگوریتم پر هزینه‌ای می‌باشد. این در حالی است که به کار بردت درخت تصمیم یا شبکه عصبی سریع‌تر می‌باشد.
2-4-5- ماشین بردار پشتیبان
ماشین بردار پشتیبان دسته‌بندی کننده‌ای است که جزو روش‌های بر پایه هسته10 در یادگیری ماشین محسوب می‌شود. SVM در سال 1992 توسط وپ‌نیک11 معرفی شده و بر پایه نظریه آماری یادگیری بنا گردیده است. الگوریتم SVM یکی از الگوریتم‌های معروف در زمینه یادگیری با نظارت است که برای دسته‌بندی و رگرسیون استفاده می‌شود. این الگوریتم به طور هم‌زمان حاشیه‌های هندسی را بیشینه کرده و خطای تجربی دسته‌بندی را کمینه می‌کند لذا به عنوان دسته‌بندی حداکثر حاشیه12 نیز نامیده می‌شود [26].
برای یک مسأله دسته‌بندی با دو دسته نتیجه خطوط بی‌شماری ممکن است وجود داشته باشند که توسط آن‌ها دسته‌بندی انجام شود ولی فقط یکی از این خطوط ماکزیمم تفکیک و جداسازی را فراهم می‌آورد. از بین جداسازهای خطی، آن جداسازی که حاشیه داده‌های آموزشی را حداکثر می‌کند خطای تعمیم را حداقل خواهد کرد. نقاط داده‌ای ممکن است ضرورتاً نقاط داده‌ای در فضای R2 نباشند و ممکن است در فضای چند بعدی Rn مربوط باشند. دسته‌بندهای خطی بسیاری ممکن است این خصوصیت را ارضا کنند اما SVM به دنبال جداکننده‌ای است که حداکثر جداسازی را برای دسته‌ها انجام دهد.
همان‌طور که در شکل (2-6) مشاهده می‌شود فراصفحه‌هایی که از نزدیکی داده‌های آموزش می‌گذرند حساس به خطا می‌باشند و احتمال اینکه برای داده‌های خارج از مجموعه آموزش قدرت تعمیم دهی خوبی داشته باشند بسیار کم است. در عوض، به نظر می‌رسد فراصفحه ای که بیشترین فاصله را از تمام نمونه‌های آموزشی دارد قابلیت‌های تعمیم دهی مناسبی را فراهم آورد. نزدیک‌ترین داده‌های آموزشی به فراصفحه‌های تفکیک کننده را بردار پشتیبان (SV13) نامیده می‌شوند [26]. اگر مجموعه داده به صورت نشان داده شود. Yi می‌تواند مقدار 1 و 1- دریافت کند که توسط این ثابت‌ها دسته‌های نقاط Xi مشخص می‌گردد که هر Xi یک بردار n بعدی است. هنگامی که داده‌های آموزشی که در دسته‌های صحیح دسته‌بندی شده‌اند را در اختیار داریم، SVM توسط تقسیم‌بندی فراصفحه ای آن‌ها را از هم جدا کرده و در دسته‌های جداگانه قرار می‌دهد به طوری که ، بردار W نقاط عمودی فراصفحه‌ها را جدا می‌کند و b میزان حاشیه را مشخص می‌کند. فراصفحه‌های موازی را می‌توان به صورت و تعریف کرد.
اگر داده‌های آموزشی به صورت خطی جدایی پذیر باشند، می‌توان فراصفحه‌ها را به طوری انتخاب نمود که هیچ نمونه‌ای میان آن‌ها نباشد و سپس تلاش کرد تا فاصله آن‌ها را به حداکثر رسانید. برای هر نمونه i از داده‌ها رابطه زیر را داریم:
(2-5) or
(2-6)
فاصله بین دو فراصفحه را از طریق تحلیل هندسی با رابطه می‌توان بدست آورد. بنابراین مسأله بهینه‌سازی ما به صورت زیر خواهد بود:
(2-7) or
می‌توان تصور کرد SVM بین دو دسته داده صفحه‌ای را ترسیم می‌کند و داده‌ها را در دو طرف این صفحه تفکیک می‌نماید. این فراصفحه به گونه‌ای قرار می‌گیرد که ابتدا دو بردار از یکدیگر دور می‌شوند و به گونه‌ای حرکت می‌کنند که هر یک به اولین داده نزدیک به خود برسد. سپس صفحه‌ای که در میان حد واسط این دو بردار رسم می‌شود از داده‌ها حداکثر فاصله را خواهد داشت و تقسیم کننده بهینه است.
تا اینجا، با این فرض که نمونه‌های آموزشی به صورت خطی جدایی پذیرند به استفاده از الگوریتم ماشین بردار پشتیبان پرداختیم. همان‌طور که می‌دانیم در عمل توزیع داده‌های دسته‌های مختلف ممکن است به راحتی جدایی پذیر نبوده و دارای تداخل باشد [26]. در این صورت، تفکیک سازی دقیق نمونه‌ها ممکن است سبب تعمیم دهی ضعیف گردد.
یک راه حل این است که مقداری خطا در دسته‌بندی را بپذیریم. این کار با معرفی متغیر بی دقت14 (ξi) انجام می‌شود که نشانگر نمونه‌هایی است که توسط تابع غلط ارزیابی می‌شوند. این روش که به SVM با حاشیه‌ی نرم15 معروف است که اجازه می‌دهد بعضی از نمونه‌ها در ناحیه اشتباه قرار گیرند سپس آن‌ها را جریمه می‌کند؛ لذا این روش برخلاف SVM حاشیه‌ی سخت16 برای مواردی که نمونه‌های آموزشی به صورت خطی جدایی پذیر نیستند قابل استفاده است.
با معرفی متغیر ξi محدودیت‌های قبلی ساده‌تر شده و رابطه (2-3) به صورت زیر تغییر می‌کند:
(2-8)
در این صورت مسأله بهینه‌سازی تبدیل می‌شود به یافتن w به نحوی که معادله زیر مینیمم شود:
(2-9)
ماشین بردار پشتیبان با حاشیه نرم تلاش می‌کند ξi را صفر نگه دارد در حالی که حاشیه‌های دسته‌بند را حداکثر می‌کند. SVM تعداد نمونه‌هایی که به اشتباه دسته‌بندی شده‌اند را کمینه نمی‌کند بلکه سعی دارد مجموع فواصل از حاشیه‌ی فراصفحه‌ها را کمینه نماید [26]. مقادیر بزرگ برای c سبب می‌شود که رابطه (2-6) مانند روش با حاشیه سخت عمل کند. ماشین بردار پشتیبان با حاشیه نرم همیشه یک راه حل پیدا می‌کند و در مقابل مجموعه داده‌هایی که دارای یک عضو جدا17 هستند مقاوم است و به خوبی عمل می‌کند.
2-4-6- روش‌های مبتنی بر قانون
روش‌های دسته‌بندی مبتنی بر قانون دانش خروجی را به صورت یک مجموعه از قوانین اگر-آنگاه ارائه می‌دهد. این قوانین به صورت زیر می‌باشند:
If <Conditions> then <Class>
که Condition شامل یک مجموعه از شرایط می‌باشد که با عملگرهای منطقی به یکدیگر متصل می‌شوند. هر شرط شامل یک سه‌تایی مرتب <Atti, Opp, Valj> می‌باشد که Atti i امین صفت، Opp عملگر مورد استفاده برای مقایسه یک صفت با یک مقدار است و Valj نشان دهنده‌ی j امین مقدار دامنه صفت Atti می‌باشد. به عنوان مثال عبارت <Gender=Male> بررسی می‌کند که آیا مقدار صفت Gender برابر با Male هست یا خیر. در یک مجموعه شرایط نباید دو ترم متناقض وجود داشته باشد. یک قانون تنها در صورتی ارضا می‌شود که کلیه ترم‌های آن ارضا شوند که در این صورت کلاس متناظر رویت می‌شود.
مهم‌ترین مزیت روش‌های دسته‌بندی مبتنی بر قانون، قابلیت تفسیر بسیار مناسب آن‌ها می‌باشد. این قابلیت مهم سبب شده که در سال‌های اخیر توجه بسیاری از پژوهشگران به روش‌های مبتنی بر قانون جلب شود. کاربرانی که از این سیستم‌ها استفاده می‌کنند بیشتر افرادی هستند که در حوزه‌های دیگر فعالیت می‌کنند. به عنوان مثال نباید انتظار داشت که یک پزشک که می‌خواهد از یک سیستم دسته‌بندی استفاده کند، دارای اطلاعات تخصصی در مورد سیستم‌های دسته‌بندی باشد. بنابراین این پزشک نیازمند یک سیستم دسته‌بند است که دانش خروجی را به ساده‌ترین روش ممکن به او نمایش دهد. دیگر مزیت مهم این روش‌ها، نرخ دسته‌بندی قابل قبول سیستم‌های دسته‌بندی که از روش‌های مبتنی بر قانون استفاده می‌کنند می‌باشد. هر چند ممکن است روش‌های دسته‌بندی معروفی مانند SVM و ANN دقت بهتری را فراهم کنند ولی در این روش‌ها کاربر در تفسیر دانش خروجی دچار مشکل می‌شود [27]. در نتیجه روش‌های مبتنی بر قانون که دارای قابلیت تفسیر و دقت مناسبی هستند، می‌توانند بسیار مورد توجه قرار گیرند.
روش‌های گوناگون دسته‌بندی مبتنی بر قانون مانند AQ15، CART، CN2، ID3 و C4.5 را می‌توان به دو دسته کلی تقسیم نمود؛ الگوریتم‌های پوششی ترتیبی و الگوریتم‌های پوششی آنی. الگوریتم‌های پوششی آنی مانند C4.5 و ID3 کل مجموع قوانین را در یک زمان و به صورت گروهی استخراج می‌کنند. این روش‌ها از تقسیم و غلبه برای کشف قوانین استفاده می‌کنند. به این صورت که ابتدا مجموعه آموزش را به زیر مجموعه‌هایی تقسیم نموده سپس برای هر زیرمجموعه یک درخت ایجاد می‌کنند. در مرحله بعدی ساختار هر درخت به قوانین معادل ترجمه می‌شود. الگوریتم‌های پوششی ترتیبی مانند CN2 و AQ15 به صورت افزایشی قوانین دسته‌بندی را کشف می‌کنند. یعنی برای هر قسمت از داده‌های آموزش یک مجموعه از قوانین استخراج شده و از بین این قوانین بهترین قانون انتخاب شده و نمونه‌هایی که توسط این قانون پوشش داده شده‌اند از مجموعه آموزش حذف می‌شوند.
در استخراج مجموعه قوانین از مجموعه داده‌ها با یک مسأله بهینه‌سازی رو به رو هستیم. الگوریتم‌های تکاملی روال‌های جستجوی تصادفی الهام گرفته شده از طبیعت هستند که به عنوان روش‌های بهینه‌سازی استفاده می‌شوند. الگوریتم‌های تکاملی بر روی یک جمعیت از رشته‌ها که بیانگر راه‌حل‌های ممکن برای یک مسأله می‌باشند، کار می‌کنند. جمعیت اولیه می‌تواند تصادفی یا به کمک دانش قبلی ایجاد شود. الگوریتم هر یک از رشته راه‌حل‌ها را با یک تابع هدف که وابسته به مسأله



قیمت: تومان

دسته بندی : مقاله و پایان نامه

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