دانلود پایان نامه کارشناسی ارشد رشته مهندسی نرم افزار 

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

 

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

داده کاوی

جریان داده

معماری BDI

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

طبقه بندی جریان داده ها در یک محیط پویا

استخراج دانش و اطلاعات نهفته در داده ها

 
 
 

مقدمه ای بر داده کاوی

داده کاوی به معنای یافتن نیمه خودکار الگوهای پنهان موجود در مجموعه داده های  موجود می باشد[38]. داده کاوی از مدلهای تحلیلی ، کلاس بندی و تخمین و برآورد اطلاعات و ارائه نتایج با استفاده از ابزارهای مربوطه بهره می گیرد. می توان گفت که داده کاوی در جهت کشف اطلاعات پنهان و روابط موجود در بین داده های فعلی و پیش بینی موارد نامعلوم و یا مشاهده نشده عمل می کند. برای انجام عملیات داده کاوی لازم است قبلا روی داده های موجود پیش پردازشهایی انجام گیرد. عمل پیش پردازش اطلاعات خود از دو بخش کاهش اطلاعات و خلاصه سازی و کلی سازی داده ها تشکیل شده است. 
 
کاهش اطلاعات عبارت است از تولید یک مجموعه کوچکتر، از داده های اولیه، که تحت عملیات داده کاوی نتایج تقریبا یکسانی با نتایج داده کاوی روی اطلاعات اولیه به دست دهد[38]. پس از انجام عمل کاهش اطلاعات و حذف خصایص غیر مرتبط نوبت به خلاصه سازی و کلی سازی داده ها می رسد. داده-های موجود در بانک های اطلاعاتی معمولا حاوی اطلاعات در سطوح پایینی هستند، بنابراین خلاصه سازی مجموعه بزرگی از داده ها و ارائه آن به صورت یک مفهوم کلی اهمیت بسیار زیادی دارد. کلی سازی اطلاعات، فرآیندی است که تعداد زیادی از رکوردهای یک بانک اطلاعاتی را به صورت مفهومی در سطح بالاتر ارائه می نماید. خود روشهای داده کاوی به سه دسته کلی تقسیم می شوند که عبارتند از خوشه بندی، طبقه-بندی و کشف قواعد وابستگی. در ادامه هر یک از این روشها را بطور کلی معرفی می نماییم.
 
 
 
 
فهرست مطالب
 
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- نحوه استخراج الگوهای recur 70
5-2-3-3-3- نحوه بروزرسانی اطلاعات مربوط به الگوهای recur 73
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
شکل 3-1- درخت تحقیق مربوط به طبقه بندی در مبحث داده کاوی 34
شکل 3-2- طبقه بندی مبتنی بر Ensemble .44 
شکل 3-3- چارچوب روش On-Demand 47
شکل 3-4- نمایی از سیستم OLIN 49
شکل 3-5- پروسه SCALLOP 53
شکل 5-1- نمودار ترتیب عملکرد عامل پیشنهادی 66
شکل 5-2- معماری عامل پیشنهادی 67
شکل 5-3- پنجره نظاره بر روی جریان داده ها 68
شکل 5-4- گراف ایجاد شده از روی رشته مفهوم ها 71
شکل 5-5- محل تجمع الگوهای استخراج شده از رشته مفهوم ها 73
شکل 5-6- میزان محاسبه شده احتمالها به ازای مقادیر مختلف K 81
شکل 5-7- شبه کد Plan کلی عامل 83
شکل 5-8- نسبت واریانس به حاصلضرب 50 متغیر دارای مجموع ثابت 85
شکل 5-9- وزن دهی چند داده مختلف 86
شکل 5-10- نمایی کلی از سیستم چندعامله ایجاد شده 88
شکل 5-11- معماری BDI عامل داده کاو 93
شکل 5-12- بخشی از جریان داده و قواعد استخراج شده از آن 99
شکل 5-13- بخشی از جریان داده و قواعد استخراج شده از آن 101
شکل 6-1- کد نمونه برای استفاده از بسته نرم افزاری weka 115 
شکل 6-2- زمان لازم بر حسب میلی ثانیه برای داده های Stagger 120 
شکل 6-3- زمان مصرف شده برای تطبیق طبقه بند 120 
شکل 6-4- نمودار مربوط به زمان پردازش روشهای مختلف برای داده های HyperPlan 121 
شکل 6-5- زمان مصرف شده برای تطبیق طبقه بند 121 
شکل 6-6- نمودار مربوط به زمان پردازش روشهای مختلف برای داده های Nursery 122 
شکل 6-7- زمان مصرف شده برای تطبیق طبقه بند برای داده های Nursery 122 
شکل 6-8- عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan 124 
شکل 6-9- نمودار عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر 124 
شکل 6-10- نمودار عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر 125 
شکل 6-11- زمان مصرف شده برای تطبیق طبقه بند برای داده های HyperPlan 125 
شکل 6-12- عملکرد روشهای مختلف بر روی مجموعه داده Stagger 126 
شکل 6-13- زمان مصرف شده برای تطبیق طبقه بند برای داده های Stagger 126 
شکل 6-14- عملکرد روشهای مختلف بر روی مجموعه داده Nursery 127 
شکل 6-15- زمان مصرف شده برای تطبیق طبقه بند برای داده های Nursery 127 
شکل 6-16- نمودار نتایج حاصل از طبقه بندی توزیع  شده مجموعه داده Nursery 130 
 
فهرست جدولها
جدول 1-1- ویژگیهای یک عامل 11 
جدول 3-1- ماتریس حاصل از روش LWClass 51 
جدول 3-2- مقایسه تکنیکهای ذکر شده 54 
جدول 5-1- ساختار اطلاعاتی ذخیره شده برای هر مفهوم و الگو 69
جدول 5-2- ساختار اطلاعاتی مربوط به وقوع الگوی "CFDA" 75 
جدول 5-3- نمونه ای از خروجی تابع سودمندی عامل 81
جدول 5-4- اطلاعات مورد استفاده برای تخمین سودمندی یک قاعده 105
جدول 6-1- دقت طبقه بندی روشهای مختلف 128
جدول 6-2- نتایج حاصل از طبقه بندی توزیع شده مجموعه داده Nursery در سه مفهوم مختلف 130