1-6. نگاهی کلی به فصول رساله. 6

 

فصل دوم  

 

پیشینه تحقیق   

 

 

2. پیشینه تحقیق …………………………………………………………………………………………………………………..8

 

2-1. مقدمه. 8

 

2-2. اهمیت مسائل چندکلاسه. 8

 

2-3. روش‌های BOOSTING. 11

 

2-3-1. مسائل دوکلاسه. 13

 

2-3-2. مسائل چند‌کلاسه. 14

 

تکنیک های تجزیه کلاسی… 15

 

یکی-در مقابل-همه(OAA). 15

 

یکی-در مقابل-یکی(OAO). 16

 

روش P در مقابل Q… 17

 

روش‌های Boosting چند‌کلاسه.. 18

 

.. 18

 

روش AdaBoost.OC.. 21

 

روش AdaBoost.ECC.. 22

 

2-4. روش‌های جمعی سریال.. 23

 

2-4-1. دسته‌بندی‌‌‌کننده‌ی سریال.. 24

 

دسته‌بندی‌کننده‌های سریال همزمان… 28

 

ساختار‌های سریال درختی… 30

 

2-5. خلاصه. 31

 

فصل سوم  

 

راهکارهای پیشنهادی

 

 

3. راهکارهای پیشنهادی… 33

 

3-1. مقدمه. 33

 

3-2. روش LogitBoost سریال تودرتو. 34

 

کلیات روش….. 34

 

جزییات روش….. 34

 

3-3. ساختار سریال پایش داد‌ه‌ها به کمک الگوریتم – نزدیک‌ترین‌همسایه. 39

 

3-4. خلاصه. 41

 

فصل چهارم  

 

روال آزمایش‌ها 

 

 

4. روال آزمایش‌‌ها ………………………………………………………………………………………………………………..43

 

4-1. مقدمه. 43

 

4-2. دسته‌بندی‌کننده‌های مورد استفاده برای مقایسه. 43

 

4-2-1. دلایل انتخاب روش‌های رقیب… 43

 

4-2-2. جزییات پیاده‌سازی روش‌های رقیب… 44

 

4-3. معیار‌های ارزیابی.. 46

 

 

4-4. مجموعه داده‌های به‌کار رفته در آزمایش‌ها 48

 

مجموعه داده‌های مربوط به مسائل چندکلاسه.. 48

 

مجموعه داد‌ه‌های مربوط به مسائل دوکلاسه.. 49

 

4-5. تست آماری فریدمن.. 50

 

4-6. خلاصه. 52

 

فصل پنجم  

 

نتایج   

 

 

5. نتایج……………………………………………………………………………………………………………………………….54

 

5-1. مقدمه. 54

 

5-2. نتایج حاصل از آزمایش هفت ترکیب مختلف از پارامترها برای روش پیشنهادی اول.. 54

 

5-2-1. تحلیل نتایج حاصل از آزمایش هفت ترکیب مختلف از پارامترها برای روش پیشنهادی اول.. 56

 

5-3. نتایج حاصل از آزمایش روش پیشنهادی اول و روش‌های رقیب… 58

 

5-4. نتایج حاصل از آزمایش روش پیشنهادی دوم. 61

 

5-5. خلاصه. 63

 

فصل ششم  

 

نتیجه‌گیری و کارهای آینده

 

 

6. 6. نتیجه‌گیری و کارهای آینده. 65

 

6-1. نتیجه‌گیری.. 65

 

6-2. کارهای آینده 66

 

اختصارات………….. 67

 

واژه نامه فارسی به انگلیسی… 68

 

واژه نامه انگلیسی به فارسی… 72

 

فهرست منابع……. 76

 

فهرست جداول

 

 

 

عنوان                                                                                                                صفحه

 

 

 

جدول 2-1.مثال از یک ماتریس کد گذاری به روش ECOC برای یک مساله چهار کلاسه   17

 

جدول 3-1.ترکیب پارامتری استفاده شده در راستای تحلیل تاثیر پارامترهای موجود در الگوریتم پیشنهادی اول…….. 39

 

جدول 4-1.     جزییات مجموعه داده‌‌های چندکلاسه.. 49

 

جدول 4-2.     جزییات مجموعه داده‌های دوکلاسه.. 50

 

جدول 5-1.      مشخصات مجموعه داده‌های استفاده شده برای بررسی تاثیر پارامترها در روش پیشنهادی اول……. 55

 

جدول 5-2.مقادیر آزمایشی ترکیبات مختلف پارامترها برای روش پیشنهادی اول   55

 

جدول 5-3.نرخ خطا و انحراف معیار به‌دست آمده از ترکیبات مختلف پارامترها برای روش پیشنهادی اول   ………………………………………………………………………………………….55

 

جدول 5-4.میانگین رتبه بندی برای 7 ترکیب پارامتری مقایسه شده بر 11 مجموعه داده چندکلاسه………. 58

 

جدول 5-5.تست فریدمن و تست تعقیبی Bonferroni-Dunn. برای  7 ترکیب پارامتری ، اختلافات معنادار با فونت توپر نمایش داده شده است. 58

 

جدول 5-6.نتایج حاصل از اعمال روش‌‌ پیشنهادی اول و روش‌های رقیب، در قالب نرخ خطای آزمایش و انحراف معیار  59

 

جدول 5-7.میانگین رتبه بندی برای 5 روش مقایسه شده بر 11 مجموعه داده چندکلاسه   60

 

جدول 5-8.نتایج تست فریدمن و تست تعقیبی Bonferroni-Dunn. برای روش پیشنهادی اول، اختلافات معنادار با فونت توپر نمایش داده شده است. 60

 

جدول 5-9. نتایج اعمال روش پیشنهادی دوم و روشKNN  به ازای مقادیر مختلف k، در قالب نرخ خطای آزمایش و انحراف معیار  61

 

جدول 5-10.میانگین رتبه بندی برای 4 روش بر روی 12 مجموعه داده دوکلاسه   62

 

جدول 5-11.نتایج تست فریدمن و تست تعقیبی Bonferroni-Dunn. برای روش پیشنهادی دوم، اختلافات معنادار با فونت توپر نمایش داده شده است. 62

 

 

 

فهرست الگوریتم‌ها

 

عنوان                                                                                                                صفحه

 

الگوریتم 1……… شبه کد مربوط به روش AdaBoost. 14

 

الگوریتم 2……… شبه کد مربوط به روش AdaBoost.M2. 19

 

الگوریتم 3……… شبه کد مربوط به روش AdaBoost.OC. 21

 

الگوریتم 4……… شبه کد مربوط به روش AdaBoost.ECC. 23

 

الگوریتم 5……… ساختار سریال Viola-Jones. 25

 

الگوریتم 6……… شبه کد مربوط به فاز آموزش ساختار سریال پیشنهادی اول  38

 

الگوریتم 7……… شبه‌کد مربوط به الگوریتم LogitBoost برای مسائل چندکلاسه  46

 

 فهرست شکل ها

 

 

 

عنوان                                                                                                                صفحه

 

شکل 2-1.          ساختار سریال Viola-Jones [42] 26

 

شکل 2-2.         ساختار دسته‌بندی‌کننده‌ سریال همزمان.. 29

 

شکل 2-3.         ساختار درختی ارائه شده توسط لینهارت… 31

 

شکل 3-1.          ساختار کلی روش دسته‌بندی‌ سریال پیشنهادی اول.. 35

 

شکل 3-2.         مکانیزم انتقال داده از یک لایه به لایه بعدی در روش پیشنهادی اول.. 37

 

شکل 3-3.         ساختار سریال پیشنهادی دوم.. 40

 

 

 

فصل اول

 

مقدمه

 

 

1. مقدمه

    

    

   • مقدمه

 

امروزه شاهد رشد عظیمی در تولید داده هستیم. فعالیت‌ها و تعامل‌های روزانه انسان‌ها، حجم چشمگیری از داده‌ها و اطلاعات را به وجود می‌آورد؛ به عنوان مثال در ارتباطات از راه دور، تراکنش های‌مالی و بانکی، شبکه‌های اجتماعی، فعالیت‌های اینترنتی عام، امور مربوط به بهداشت و درمان، پایش اطلاعات امنیتی، اطلاعات و داده‌های آماری مانند سرشماری نفوس و بسیاری موارد دیگر [1,2]. با پیشرفت چشمگیر تجهیزات سخت افزاری، هزینه ذخیره داده کم شده است؛ این در حالی است که آنالیز صحیح و استخراج اطلاعات مفید از این حجم از داده به یک دغدغه تبدیل شده است. هوش مصنوعی[1] و به ویژه حوزه یادگیری ماشین[2]، به دنبال یافتن روش‌ها و ابزار‌های موثر جهت رفع این مشکل می باشد.

 

 

 

 

 

• یادگیری ماشین

 

اصلی‌ترین زمینه تحقیقاتی در حوزه یادگیری ماشین، شناسایی الگو[3] است؛ یعنی استخراج اطلاعات و الگو‌های تکرار‌ شونده از داده ورودی[4]، که این اطلاعات برای انجام تصمیم‌گیری در مورد داده‌های نادیده[5] کاربرد دارد.

 

بر اساس نوع پیش بینی داده‌های ‌نادیده، انواع روش‌های شناسایی الگو را می توان به دو گروه کلی روش‌های مبتنی بر دسته‌بندی[6] و روش‌های مبتنی بر رگرسیون[7] تقسیم‌بندی کرد. سیستم‌های مبتنی بر دسته‌بندی، سعی در ساختن مدلی دارند که خروجی آن گسسته[8] می‌باشد و این خروجی در واقع برچسب کلاسی[9] است که سیستم برای یک نمونه خاص پیشنهاد می‌دهد؛ در مقابل، سیستم‌های مبتنی بر رگرسیون، تابعی پیوسته[10] را مدل می‌کنند و خروجی آنها به صورت عددی[11] می‌باشد.

 

یادگیری ماشین را می‌توان به چهار دسته کلی یادگیری با نظارت[12] و یادگیری بدون نظارت[13]، یادگیری نیمه نظارتی[14] و یادگیری فعال[15] تقسیم‌بندی کرد. در یادگیری با نظارت، سیستم با داده‌های آموزشی که دارای برچسب‌های کلاس معین هستند آموزش داده می‌شود. این گروه از الگوریتم‌ها که بسیار رایج نیز می‌باشند، سعی در ساخت مدلی دارند که به بهترین نحو داده‌های آموزشی را به برچسب کلاس داده شده‌ی آنها مرتبط سازند. مدل ساخته شده بر این اساس، در مرحله آزمایش[16] سعی در پیش بینی برچسب کلاس داده‌های آزمایشی خواهد کرد. در مقابل این گروه از الگوریتم ها، الگوریتم های مبتنی بر یادگیری بدون نظارت، بدون دریافت برچسب کلاس داده‌های آموزشی، سعی در دسته‌بندی داده‌های آموزشی می‌کنند؛ به این نوع از یادگیری، خوشه‌بندی[17] نیز گفته می‌شود. گاهی تنها بخشی از برچسب کلاس داده‌های آموزشی در دسترس است بنابر این دسته سوم از الگوریتم‌ها، یعنی الگوریتم‌های نیمه‌نظارتی، عملکردی مابین الگوریتم‌های نظارتی و الگوریتم‌های بدون نظارت دارند. در یادگیری فعال، سیستم در مرحله آموزش، با انسان تعامل دارد؛ به این صورت که انسان برچسب‌های مناسب را به داده‌‌های ورودی نسبت می‌دهد و سیستم با توجه به برچسب‌های اختصاص داده شده، به پایش اطلاعات خود و مدل آموزشی می‌پردازد.

 

این رساله منحصرا بر روش‌های دسته‌بندی مبتنی بر یادگیری نظارتی تمرکز دارد. به بیان رسمی‌تر، الگوریتم‌هایی که از یک مجموعه آموزشی[18] مانند D، شامل n داده نمونه ورودی به فرم {(x₁,y₁),…, (x_n,y_n)} که هر نمونه متشکل از یک بردار خصیصه[19]  با بعد d و یک برچسب کلاس  که  برای مسائل K کلاسه، آموزش می‌بینند و خروجی این آموزش، یک دسته‌بندی‌کننده[20] یا فرضیه[21] است که در حالت ایده آل یک مرزبندی تصمیم[22] دقیق برای جدا‌سازی کلاس‌ها در کل فضای  انجام خواهد داد.