بررسی کاربرد عامل و سیستمهای چندعامله در داده کاوی

پروژه جهت اخذ درجه كارشناسی رشته كامپیوتر

امروزه با توجه به گسترش روز افزون اطلاعاتی که بشر با آنها سر و کار دارد، بهره­ گیری از روشهایی همچون داده کاوی برای استخراج دانش و اطلاعات نهفته در داده ­ها، امری غیرقابل اجتناب می­باشد. بدلیل حجم بسیار بالای داده ­ها در بسیاری از کاربردها و اهمیت بیشتر داده ­های جدید، ذخیره­ سازی این داده­ ها امری مقرون به صرفه نیست، لذا داده ­هایی که باید مورد پردازش قرار گیرند، همواره بصوت پویا در حال تغییر و تحول هستند. مساله دیگری که امروزه در بحث داده­ کاوی وجود دارد، بحث توزیع شدگی ذاتی داده­ ها است. معمولا پایگاه هایی که این داده­ ها را ایجاد یا دریافت می­کنند، متعلق به افراد حقیقی یا حقوقی هستند که هر کدام بدنبال اهداف و منافع خود می­باشند و حاضر نیستند دانش خود را بطور رایگان در اختیار دیگران قرار دهند.

با توجه به قابلیتهای عامل و سیستمهای چندعامله و مناسب بودن آنها برای محیط های پویا و توزیع شده بنظر می­رسد که بتوان از قابلیتهای آنها برای داده­ کاوی در محیط های پویا و محیط های توزیع شده بهره برد. اکثر کارهایی که تاکنون در زمینه بهره ­گیری از عامل و سیستمهای چندعامله انجام شده است خصوصیتهایی همانند خودآغازی و بخصوص متحرک بودن عاملها را مورد بررسی قرار داده است و در آنها مواردی همچون هوشمندی، یادگیری، قابلیت استدلال، هدفگرایی و قابلیتهای اجتماعی عاملها مورد بررسی قرار نگرفته است. در این تحقیق ما قصد داریم تا ضمن بررسی کارهای موجود در زمینه کاربرد عامل و سیستمهای چندعامله در داده­ کاوی، بحث طبقه­ بندی جریان داده ­ها را در یک محیط پویا مورد بررسی قرار دهیم. ما مساله خود را در دو فاز مورد بررسی قرار خواهیم داد. در فاز اول خصوصیتهای یک عامل تنها مورد بررسی قرار خواهد گرفت و در فاز دوم قابلیتهای اجتماعی عاملها مانند مذاکره، دستیابی به توافق و ... برای داده ­کاوی در یک محیط پویا و توزیع­ شده رقابتی مورد استفاده قرار خواهد گرفت. بطور کلی دستاوردهای اصلی این تحقیق عبارتند از 1) ارائه یک رویکرد مبتنی بر عامل برای مساله طبقه ­بندی جریان داده­ های دارای تغییر مفهوم و پویا با استفاده از قابلیتهای هدفگرایی، هوشمندی، یادگیری و استدلال 2) ارائه یک رویکرد مبتنی بر سیستمهای چندعامله برای طبقه­بندی جریان داده­های توزیع­شده در یک محیط رقابتی با استفاده از قابلیتهای اجتماعی عاملها و دستیابی به توافق. نتایج حاصل از آزمایشات انجام شده در این پایان ­نامه نشان­ دهنده برتری استفاده از عاملها و سیستمهای چندعامله برای بحث طبقه بندی و داده­ کاوی در محیطهای پویا و توزیع شده می­باشد.

 فهرست مطالب

1. فصل اول - معرفی و آشنایی با مفاهیم اولیه. 1

1-1- مقدمه­ای بر داده ­کاوی.. 2

1-1-1- خوشه­ بندی.. 3

1-1-2- کشف قواعد وابستگی.. 4

1-1-3- طبقه ­بندی.. 4

1-1-3-1- طبقه­ بندی مبتنی بر قواعد. 5

1-2- داده­ کاوی توزیع ­شده. 7

1-3- عاملها و سیستمهای چندعامله. 8

1-3-1- عامل. 8

1-3-1-1- مقایسه عامل با شی.. 9

1-3-1-2- معماری عاملها11

1-3-1-3- معماری BDI. 12

1-3-2- سیستم­های چندعامله. 14

1-3-2-1- مذاکره. 17

1-4- بهره ­گیری از عامل برای داده ­کاوی.. 19

1-4-1- سیستم­های چندعامله، بستری برای داده ­کاوی توزیع شده. 19

1-5- جمع­ بندی.. 22

2. فصل دوم - داده­ کاوی پویا23

2-1- مقدمه ­ای بر داده ­کاوی پویا24

2-2- جریان داده. 25

2-3- طبقه بندی جریان داده. 26

2-3-1- موضوعات پژوهشی.. 27

2-4- جمع­ بندی.. 31

3. فصل سوم - مروری بر کارهای انجام شده. 33

3-1- مقدمه. 34

3-2- داده ­کاوی توزیع­ شده ایستا. 35

3-2-1- روشهای غیرمتمرکز. 36

3-2-2- روشهای مبتنی بر توزیع ذاتی داده ­ها37

3-3- کارهای مهم انجام شده در زمینه داده­ کاوی با استفاده از عامل. 38

3-4- کارهای انجام شده در زمینه طبقه ­بندی جریان داده­ها41

3-4-1- روشهای طبقه­ بندی Ensemble-based. 41

3-4-2- درختهای تصمیم بسیار سریع. 43

3-4-3- طبقه­ بندی On-Demand. 46

3-4-4- OLIN.. 48

3-4-5- الگوریتمهای LWClass. 49

3-4-6- الگوریتم ANNCAD.. 51

3-4-7- الگوریتم SCALLOP. 51

3-4-8- طبقه­ بندی جریان داده ­ها با استفاده از یک روش Rule-based. 53

3-5- جمع ­بندی.. 54

4. فصل چهارم - تعریف مساله. 55

4-1- مقدمه. 56

4-2- تعریف مساله برای فاز اول. 56

4-2-1- جریان داده. 57

4-2-2- مفهوم یا مدل موجود در جریان داده. 57

4-2-3- مساله طبقه­ بندی جریان داده­ های دارای تغییر مفهوم. 57

4-3- تعریف مساله برای فاز دوم. 59

5. فصل پنجم - رویکردهای پیشنهادی.. 62

5-1- مقدمه. 63

5-2- رویکرد پیشنهادی برای فاز اول پروژه. 63

5-2-1- عامل و ویژگیهای آن در این مساله. 64

5-2-2- عملکرد کلی عامل. 65

5-2-3- معماری عامل. 66

5-2-3-1- حسگرها 67

5-2-3-2- پایگاه دانش عامل. 68

5-2-3-3- تابع ارزیابی محیط.. 70

5-2-3-3-1- نحوه تشخیص اطلاعات و نگهداری الگوهای recur در جریان داده. 70

5-2-3-3-2- نحوه استخراج الگوهای recur70

5-2-3-3-3- نحوه بروزرسانی اطلاعات مربوط به الگوهای recur73

5-2-3-3-4- نحوه محاسبه وقوع احتمال وقوع یک الگوی خاص.... 74

5-2-3-4- تابع سودمندی.. 75

5-2-3-5- بخش تصمیم­ گیری Planning. 79

5-2-3-5-1- بخش تصمیم­ گیری.. 79

5-2-3-5-2- Planning. 83

5-2-3-6- بخش Action. 86

5-3- رویکرد پیشنهادی برای فاز دوم مساله. 87

5-3-1- عاملهای مشتری.. 88

5-3-2- عامل صفحه زرد. 90

5-3-3- عاملهای داده­ کاو. 91

5-3-3-1- معماری عاملهای داده­ کاو. 92

5-3-3-1-1- تابع BRF. 94

5-3-3-1-2- تابع Generate Options. 95

5-3-3-1-3- تابع فیلتر. 95

5-3-3-1-4- بخش Actions. 96

5-3-3-1-5- Plan های عامل. 97

5-3-3-1-5- 1- Plan مربوط به طبقه­ بندی.. 97

5-3-3-1-5-2- Plan مربوط به تطبیق طبقه­ بندی98

5-3-3-1-5-3- Plan مربوط به خرید و فروش قواعد با استفاده از مذاکره. 101

5-4- جمع ­بندی.. 111

6. فصل ششم - آزمایشات و نتایج.. 113

6-1- مقدمه. 114

6-2- محیط عملیاتی.. 114

6-3- مجموعه داده ­های مورد استفاده. 116

6-3-1- مجموعه داده­ های استاندارد. 116

6-3-2- مجموعه داده­ های واقعی.. 117

6-4- معیارهای ارزیابی و روشهای مورد استفاده برای مقایسه. 117

6-5- آزمایشات انجام شده. 118

6-5-1- آزمایشات مربوط به فاز اول. 119

6-5-2- آزمایشات مربوط به فاز دوم. 128

6-6- جمع ­بندی.. 130

7. فصل هفتم- جمع­ بندی و نتیجه­ گیری.. 132

فهرست مراجع. 136

 فهرست اشکال

 شکل1-1- معماری BDI در عامل. 15

1. شکل3-1- درخت تحقیق مربوط به طبقه­بندی در مبحث داده­کاوی.. 34
2. شکل3-2-طبقه­بندی مبتنی بر Ensemble. .44
3. شکل3-3- چارچوب روش On-Demand. 47
4. شکل 3-4- نمایی از سیستم OLIN.. 49
5. شکل3-5- پروسه SCALLOP 53
6. شکل5-1- نمودار ترتیب عملکرد عامل پیشنهادی.. 66
7. شکل5-2- معماری عامل پیشنهادی.. 67
8. شکل 5-3- پنجره نظاره بر روی جریان داده­ها68
9. شکل 5-4-گراف ایجاد شده از روی رشته مفهوم­ها71
10. شکل5-5-محل تجمع الگوهای استخراج شده از رشته مفهوم­ها73
11. شکل 5-6- میزان محاسبه شده احتمالها به ازای مقادیر مختلف K.. 81
12. شکل5-7- شبه کد Plan کلی عامل. 83
13. شکل5-8- نسبت واریانس به حاصلضرب 50 متغیر دارای مجموع ثابت.. 85
14. شکل5-9-وزن دهی چند داده مختلف... 86
15. شکل5-10- نمایی کلی از سیستم چندعامله ایجاد شده88
16. شکل 5-11- معماری BDI عامل داده­کاو. 93
17. شکل5-12- بخشی از جریان داده و قواعد استخراج شده از آن. 99
18. شکل5-13- بخشی از جریان داده و قواعد استخراج شده از آن. 101
19. شکل6-1- کد نمونه برای استفاده از بسته نرم افزاری weka. 115
20. شکل 6-2- زمان لازم بر حسب میلی ثانیه برای داده­هایStagger120
21. شکل 6-3- زمان مصرف شده برای تطبیق طبقه­بند. 120
22. شکل 6-4- نمودار مربوط به زمان پردازش روشهای مختلف برای داده­های HyperPlan121
23. شکل 6-5- زمان مصرف شده برای تطبیق طبقه­بند 121
24. شکل 6-6- نمودار مربوط به زمان پردازش روشهای مختلف برای داده­های Nursery122
25. شکل 6-7- زمان مصرف شده برای تطبیق طبقه­بند برای داده­های Nursery122
26. شکل 6-8- عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan124
27. شکل 6-9- نمودار عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر124
28. شکل 6-10- نمودار عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر 125
29. شکل 6-11- زمان مصرف شده برای تطبیق طبقه­بند برای داده­های HyperPlan125
30. شکل 6-12- عملکرد روشهای مختلف بر روی مجموعه دادهStagger126
31. شکل 6-13- زمان مصرف شده برای تطبیق طبقه­بند برای داده­هایStagger126
32. شکل 6-14- عملکرد روشهای مختلف بر روی مجموعه داده Nursery127
33. شکل 6-15- زمان مصرف شده برای تطبیق طبقه­بند برای داده­های Nursery127
34. شکل 6-16- نمودار نتایج حاصل از طبقه­بندی توزیع ­شده مجموعه داده Nursery130
35.  

 فهرست جدولها

 جدول1-1- ویژگیهای یک عامل 11

7. جدول3-1- ماتریس حاصل از روش LWClass. 51
8. جدول3-2- مقایسه تکنیکهای ذکر شده54
9. جدول 5-1- ساختار اطلاعاتی ذخیره شده برای هر مفهوم و الگو. 69
10. جدول5-2- ساختار اطلاعاتی مربوط به وقوع الگوی "CFDA". 75
11. جدول5-3- نمونه ای از خروجی تابع سودمندی عامل. 81
12. جدول5-4-اطلاعات مورد استفاده برای تخمین سودمندی یک قاعده105
13. جدول 6-1- دقت طبقه­بندی روشهای مختلف... 128
14. جدول6-2- نتایج حاصل از طبقه­بندی توزیع شده مجموعه داده Nursery در سه مفهوم مختلف... 130

برچسب ها : بررسی کاربرد عامل و سیستمهای چندعامله در داده کاوی , داده کاوی , طبقه بندی , جریان داده , عامل