مهندسی کامپیوتر

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

 دانلود متن کامل پایان نامه داده کاوی پویا با استفاده از عامل

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

داده­کاوی پویا با استفاده از عامل

استاد

1393

(در فایل دانلودی نام نویسنده موجود است)

چکیده

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

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

 

کلمات کلیدی:

داده­کاوی[1]، طبقه­بندی[2]، جریان داده[3]، عامل[4].

 

فهرست مطالب

 

  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

  1. فصل دوم – داده­کاوی پویا 23

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

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

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

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

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

  1. فصل سوم – مروری بر کارهای انجام شده 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

  1. فصل چهارم – تعریف مساله 55

4-1- مقدمه 56

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

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

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

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

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

  1. فصل پنجم – رویکردهای پیشنهادی 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

  1. فصل ششم – آزمایشات و نتایج 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

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

 فهرست مراجع 136

 

فهرست اشکال

 

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

 

فهرست جدولها

 

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

 

 

فصل اول

 

معرفی و آشنایی با مفاهیم اولیه

 

فصل اول

 

معرفی و آشنایی با مفاهیم اولیه

 

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

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

 

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

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

  • روشهای تقسیم­بندی : روشهای خوشه­بندی که بروش تقسیم بندی عمل می­کنند، داده­های موجود در یک مجموعه داده را به k خوشه تقسیم می­کنند، بطوریکه هر خوشه دو خصوصیت زیر را داراست :
    • هر خوشه یا گروه حداقل شامل یک داده می­باشد.
    • هر داده موجود در مجموعه داده دقیقا به یک گروه یا خوشه تعلق دارد.

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

 

  • روشهای سلسله مراتبی : روشهای سلسله مراتبی به دو دسته کلی روشهای bottom-up و روشهای top-down تقسیم می­گردند. روشهای سلسله مراتبی bottom-up به این صورت عمل می­کنند که در شروع هر کدام از داده­ها را در یک خوشه جداگانه قرار می­دهد و در طول اجرا سعی می­کند تا خوشه­هایی نزدیک به یکدیگر را با هم ادغام نماید. این عمل ادغام تا زمانی که یا تنها یک خوشه داشته باشیم و یا اینکه شرط خاتمه برقرار گردد، ادامه می­یابد. روشهای top-down دقیقا بطریقه عکس عمل می­کنند، به این طریق که ابتدا تمام داده­ها را در یک خوشه­ قرار می­دهد و در هر تکرار از الگوریتم، هر خوشه به خوشه­های کوچکتر شکسته می­شود و اینکار تا زمانی ادامه می­یابد که یا هر کدام از خوشه­ها تنها شامل یک داده باشند و یا شرط خاتمه الگوریتم برقرار گردد. شرط خاتمه معمولا تعداد کلاستر یا خوشه می­باشد.

 

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

البته دسته دیگری از روشهای خوشه­بندی مانند روشهای مبتنی بر گرید، روشهای مبتنی بر مدل و . وجود دارند که می­توانید آنها را در ]38[ مطالعه نمایید.

 

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

بحث قواعد وابستگی به مقوله کشف عناصری یا المان­هایی در یک مجموعه داده می­پردازد که معمولا با یکدیگر اتفاق می­افتند و بعبارتی رخداد آنها بنوعی با یکدیگر ارتباط دارد. بطور کلی هر قاعده یا rule که از این مجموعه داده­ بدست می­­آید، دارای شکل کلی بصورت  می­باشد که نشان می­دهد چنانچه الگوی X اتفاق بیفتد، با احتمال بالایی الگوی Y نیز اتفاق خواهد افتاد. برای مطالعه بیشتر در مورد مقوله کشف قواعد وابستگی می­توانید به ]38[ مراجعه نمایید.

 

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

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

الگوریتم­ها و روشهای مختلفی برای طبقه­بندی تاکنون پیشنهاد شده­اند که برای مثال می­توان از روشهای طبقه­بندی با استفاده از درخت تصمیم، طبقه­بندی بیزین، SVM ، طبقه­بندی با استفاده از شبکه­های عصبی، طبقه­بندی مبتنی بر قواعد و . ]56[ نام برد. در اینجا ما قصد نداریم وارد مباحث مربوط به الگوریتم­ها و روشهای طبقه­بندی شویم و تنها روش طبقه­بندی مبتنی بر قواعد را بدلیل استفاده از آن در فاز دوم پروژه در اینجا معرفی خواهیم نمود. در صورت نیاز به مطالعه بیشتر می­توانید به فصل ششم مرجع ]38[ مراجعه نمایید.

 

تعداد صفحه :157

قیمت : 14700تومان

بلافاصله پس از پرداخت لینک دانلود فایل در اختیار شما قرار می گیرد

و در ضمن فایل خریداری شده به ایمیل شما ارسال می شود.

پشتیبانی سایت :               serderehi@gmail.com

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

***  *** ***