پروژه کامل و جامع بررسی مفصل داده کاوی پویا با استفاده از عامل

فرمت فایل : word (قابل ویرایش) تعداد صفحات : 190 صفحه

چکیده

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

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

کلمات کلیدی:

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

فهرست مطالب

فصل اول - معرفی و آشنایی با مفاهیم اولیه. 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

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

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

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

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

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

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

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

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

4-1- مقدمه. 56

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

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

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

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

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

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

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

فصل هفتم- جمع­بندی و نتیجه­گیری.. 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

فصل اول

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

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[ مراجعه نمایید.

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

در این قسمت قصد داریم نگاهی به بحث طبقه­بندی مبتنی بر قواعد داشته باشیم. دراین روش مدل ایجاد شده از روی داده­ها بصورت مجموعه­ای از قواعد می­باشد. می­توان گفت که هر قاعده بصورت یک قاعده IF P THEN C می­باشد که در آن P مجموعه­ای از شرایط بوده و C نیز مشخص کننده برچسب یک کلاس یا طبقه­ خاص می­باشد. یک قاعده بدست آمده از مجموعه داده­های آموزشی با استفاده از دو معیار coverage و accuracy می­تواند ارزیابی گردد. این دو معیار بصورت زیر تعریف می­گردند:

                                                                          (1-1)

                                                                                      (1-2)

که در تعاریف مذکور  تعداد داده­هایی در مجموعه داده D است که توسط قاعده پوشش داده می­شوند.  تعداد داده­هایی است که توسط قاعده بدرستی طبقه­بندی شده­اند.  تعداد داده­های موجود در D می­باشد.