پـــایان نامه روش های دسته بندی جریان داده

چکیده

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

تعداد صفحات 112 word

فهرست مطالب

تقدیم به: 3

تقدیر و تشکر. 4

فصل اول مقدمه ای بر داده کاوی. 1

1-1 مقدمه 2

1-2عامل مسبب پیدایش داده کاوی. 2

1-3داده کاوی و مفهوم اکتشاف دانش (K.D.D) 3

1-3-1 تعریف داده کاوی. 5

2-3-1 فرایند داده‌کاوی. 6

1-3-3 قابلیتهای داده کاوی. 7

4-3-1 چه نوع داده‌هایی مورد کاوش قرار می گیرند؟ 8

4-1 وظایف داده کاوی. 9

1-4-1 کلاس بندی. 10

2-4-1 مراحل یک الگوریتم کلاس‌بندی. 11

3-4-1 انواع روش‌های کلاس‌بندی. 11

1-3-4-1 درخت تصمیم. 12

1-1-3-4-1 کشف تقسیمات.. 13

2-1-3-4-1 دسته بندی با درخت تصمیم. 15

3-1-3-4-1 انواع درخت‌های تصمیم. 17

4-1-3-4-1 نحوه‌ی هرس کردن درخت.. 17

2-3-4-1 بیزی. 18

1-2-3-4-1 تئوری بیز. 20

2-2-3-4-1 دسته بندی ساده بیزی. 22

4-4-1 ارزیابی روش‌های کلاس‌بندی. 28

4-1-6 انواع روش‌های پیش بینی. 29

1-4-6-1 رگرسیون. 29

1-4-6-1-1 رگرسیون خطی. 29

1-4-6-1-2 رگرسیون منطقی. 31

1-4-7 تخمین. 32

فصل دوم خوشه بندی. 34

2 1-تعریف فرایند خوشه‌بندی. 35

2-2 روش ها و الگوریتم‌های خوشه‌بندی. 36

2-3 روش و الگوریتم سلسله مراتبی. 37

2 3-1-روش های سلسله‌مراتبی. 37

2 3-2-الگوریتم های سلسله مراتبی. 38

2-3-3- الگوریتم خوشه بندی single-linkage. 39

2 3-4-الگوریتم‌های تفکیک... 45

3-5-2روش‌های متکی برچگالی. 46

3-7-2 روش‌‌های متکی بر مدل. 47

فصل سوم خوشه بندی CS tree. 48

3-1مقدمه 49

3-2 مروری بر روش های خوشه بندی جریان داده 50

3-3 خوشه بندی توری جریان داده 52

3-1-3 مروری بر روش خوشه بندی توری CS tree. 53

3-2- 3 بررسی نقاط ضعف الگوریتم CS tree. 56

3-4 الگوریتم پیشنهادی. 60

3-1-4 بازتعریف مفهوم همسایگی و رفع مشکل تقسیم بی معنی خوشه ها 63

3-5 اصلاح روند بروز رسانی خوشه ها 66

3-6 اصلاح ساختار نمایش خوشه ها 67

فصل چهارم جریان داده و مدل های ان. 69

4-1 مقدمه 70

4-2 کاربردهای داده های جریانی. 71

4-2-1 شبکه های حسگر. 71

4-2-2 تحلیل ترافیک شبکه 72

4-2-3 محرک های مالی. 73

4-2-4 تحلیل تراکنش ها 73

4-3 مدل داده های جریانی. 74

4-4 زیربنای نظری. 75

4-4-1 تکنیک های مبتنی بر داده 76

4-4-1-1 نمونه برداری. 76

4-4-1-2 پراکنده ساختن بار 77

4-4-1-3 طراحی اولیه 77

4-4-1-4 ساختمان داده خلاصه 78

4-4-1-5 انبوه سازی. 78

4-4-2 تکنیک های مبتنی بر وظیفه 78

4-4-2-1 الگوریتم های تخمین. 79

4-4-2-2 الگوریتم های مبتنی بر پنجره 79

4-4-2-3 الگوریتم های دانه دانه سازی نتایج. 80

4-5 خوشه بندی داده های جریانی. 80

4-5-1 بهبود روش های سنتی. 81

4-5-1-1 الگوریتم CLARANS. 82

4-5-1-2 الگوریتم BIRCH.. 84

4-5-2 ظهور تکنیک های جدید. 87

4-5-2-1 الگوریتم مبتنی بر چگالی DBSCAN.. 87

4-5-2-2 الگوریتم مبتنی بر گریدSTING.. 90

4-6 بحث در مورد الگوریتم ها 93

4-6-1 ایا توسعه روش های سنتی درست است؟ 93

4-6-2 روش های جدید چه پیشنهاداتی دارند؟ 94

منابع. 96

فهرست اشکال

شکل 1-1 فرآینده داده کاوی.. 7

شکل1-2 نمونه یک درخت تصمیم.. 13

شکل 1-3 یک تقسیم بندی خوب ، درجه خلوص را برای فرزندان افزایش می دهد. 15

شکل 3-1 تقسیم خوشه های با معنی به زیر خوشه های بی معنی.. 58

شکل3-2 خطاهای روش Cs tree در ترکیب خوشه های یک بعدی و ایجاد خوشه های چند بعدی- قسمت A خطا در تعداد خوشه ها ، قسمت B خطا در شکل خوشه ها، قسمت C خطا در مرز خوشه ها59

شکل3 -3 روی هم افتادگی خوشه ها در بروز رسانی به روش Cs tree. 60

شکل 4-2 الگوریتم خوشه بندیCLARA.. 82

شکل 4-3 الگوریتم خوشه بندیCLARANS . 84

شکل 4-4 الگوریتم خوشه بندیBIRCH.. 86

شکل 4-6 الگوریتم خوشه بندی.STING.. 92

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

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

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

فرمت فایل: word

تعداد صفحات: 148

شرح مختصر:

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

با توجه به قابلیتهای عامل و سیستمهای چندعامله و مناسب بودن آنها برای محیط های پویا و توزیع شده بنظر می­رسد که بتوان از قابلیتهای آنها برای داده­ کاوی در محیط های پویا و محیط های توزیع شده بهره برد. اکثر کارهایی که تاکنون در زمینه بهره ­گیری از عامل و سیستمهای چندعامله انجام شده است خصوصیتهایی همانند خودآغازی و بخصوص متحرک بودن عاملها را مورد بررسی قرار داده است و در آنها مواردی همچون هوشمندی، یادگیری، قابلیت استدلال، هدفگرایی و قابلیتهای اجتماعی عاملها مورد بررسی قرار نگرفته است. در این تحقیق ما قصد داریم تا ضمن بررسی کارهای موجود در زمینه کاربرد عامل و سیستمهای چندعامله در داده­ کاوی، بحث طبقه­ بندی جریان داده ­ها را در یک محیط پویا مورد بررسی قرار دهیم. ما مساله خود را در دو فاز مورد بررسی قرار خواهیم داد. در فاز اول خصوصیتهای یک عامل تنها مورد بررسی قرار خواهد گرفت و در فاز دوم قابلیتهای اجتماعی عاملها مانند مذاکره، دستیابی به توافق و ... برای داده ­کاوی در یک محیط پویا و توزیع­ شده رقابتی مورد استفاده قرار خواهد گرفت. بطور کلی دستاوردهای اصلی این تحقیق عبارتند از 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

 فهرست جدولها

 جدول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