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).


پاسخ دهید