Get a site

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

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

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

داده ­کاوی پویا با بهره گرفتن از عامل

استاد

۱۳۹۳

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

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

۱-۱- مقدمه­ای بر داده ­کاوی ۲
۱-۱-۱- خوشه­بندی ۳
۱-۱-۲- کشف قواعد وابستگی ۴
۱-۱-۳- طبقه ­بندی ۴
۱-۱-۳-۱- طبقه ­بندی مبتنی بر قواعد ۵
۱-۲- داده ­کاوی توزیع­شده ۷
۱-۳- عاملها و سیستم های چندعامله ۸
۱-۳-۱- عامل ۸
۱-۳-۱-۱- مقایسه عامل با شی ۹
۱-۳-۱-۲- معماری عاملها ۱۱
۱-۳-۱-۳- معماری BDI. 12
۱-۳-۲- سیستم­های چندعامله ۱۴
۱-۳-۲-۱- مذاکره ۱۷
۱-۴- بهره­ گیری از عامل برای داده ­کاوی ۱۹
۱-۴-۱- سیستم­های چندعامله، بستری برای داده ­کاوی توزیع شده ۱۹
۱-۵- جمع­بندی ۲۲

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

۲-۱- مقدمه­ای بر داده ­کاوی پویا ۲۴
۲-۲- جریان داده ۲۵
۲-۳- طبقه ­بندی جریان داده ۲۶
۲-۳-۱- موضوعات پژوهشی ۲۷
۲-۴- جمع­بندی ۳۱

  1. فصل سوم – مروری بر کارهای انجام شده ۳۳

۳-۱- مقدمه ۳۴
۳-۲- داده ­کاوی توزیع­شده ایستا ۳۵
۳-۲-۱- روش های غیرمتمرکز ۳۶
۳-۲-۲- روش های مبتنی بر توزیع ذاتی داده­ ها ۳۷
۳-۳- کارهای مهم انجام شده در زمینه داده ­کاوی با بهره گرفتن از عامل   ۳۸
۳-۴- کارهای انجام شده در زمینه طبقه ­بندی جریان داده­ ها ۴۱
۳-۴-۱- روش های طبقه ­بندی Ensemble-based. 41
۳-۴-۲- درختهای تصمیم بسیار سریع ۴۳
۳-۴-۳- طبقه ­بندی On-Demand. 46
۳-۴-۴- OLIN 48
۳-۴-۵- الگوریتمهای LWClass. 49
۳-۴-۶- الگوریتم ANNCAD 51
۳-۴-۷- الگوریتم SCALLOP. 51
۳-۴-۸- طبقه ­بندی جریان داده­ ها با بهره گرفتن از یک روش Rule-based. 53
۳-۵- جمع­بندی ۵۴

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

۴-۱- مقدمه ۵۶
۴-۲- تعریف مساله برای فاز اول ۵۶
۴-۲-۱- جریان داده ۵۷
۴-۲-۲- مفهوم یا مدل موجود در جریان داده ۵۷
۴-۲-۳- مساله طبقه ­بندی جریان داده ­های دارای تغییر مفهوم ۵۷
۴-۳- تعریف مساله برای فاز دوم ۵۹

  1. فصل پنجم – رویکردهای پیشنهادی ۶۲

۵-۱- مقدمه ۶۳
۵-۲- رویکرد پیشنهادی برای فاز اول پروژه ۶۳
۵-۲-۱- عامل و ویژگیهای آن در این مساله ۶۴
۵-۲-۲- عملکرد کلی عامل ۶۵
۵-۲-۳- معماری عامل ۶۶
۵-۲-۳-۱- حسگرها ۶۷
۵-۲-۳-۲- پایگاه دانش عامل ۶۸
۵-۲-۳-۳- تابع ارزیابی محیط ۷۰
۵-۲-۳-۳-۱- نحوه تشخیص اطلاعات و نگهداری الگوهای recur در جریان داده   ۷۰
۵-۲-۳-۳-۲- نحوه استخراج الگوهای recur 70
۵-۲-۳-۳-۳- نحوه بروزرسانی اطلاعات مربوط به الگوهای recur 73
۵-۲-۳-۳-۴- نحوه محاسبه وقوع احتمال وقوع یک الگوی خاص ۷۴
۵-۲-۳-۴- تابع سودمندی ۷۵
۵-۲-۳-۵- بخش تصمیم ­گیری و Planning. 79
۵-۲-۳-۵-۱- بخش تصمیم ­گیری ۷۹
۵-۲-۳-۵-۲- Planning. 83
۵-۲-۳-۶- بخش Action. 86
۵-۳- رویکرد پیشنهادی برای فاز دوم مساله ۸۷
۵-۳-۱- عاملهای مشتری ۸۸
۵-۳-۲- عامل صفحه زرد ۹۰
۵-۳-۳- عاملهای داده­کاو ۹۱
۵-۳-۳-۱- معماری عاملهای داده­کاو ۹۲
۵-۳-۳-۱-۱- تابع BRF. 94
۵-۳-۳-۱-۲- تابع Generate Options. 95
۵-۳-۳-۱-۳- تابع فیلتر ۹۵
۵-۳-۳-۱-۴- بخش Actions. 96
۵-۳-۳-۱-۵- Plan های عامل ۹۷
۵-۳-۳-۱-۵- ۱- Plan مربوط به طبقه ­بندی ۹۷
۵-۳-۳-۱-۵-۲- Plan مربوط به تطبیق طبقه­بند ۹۸
۵-۳-۳-۱-۵-۳- Plan مربوط به خرید و فروش قواعد با بهره گرفتن از مذاکره   ۱۰۱
۵-۴- جمع­بندی ۱۱۱

  1. فصل ششم – آزمایشات و نتایج ۱۱۳

۶-۱- مقدمه ۱۱۴
۶-۲- محیط عملیاتی ۱۱۴
۶-۳- مجموعه داده ­های مورد استفاده ۱۱۶
۶-۳-۱- مجموعه داده ­های استاندارد ۱۱۶
۶-۳-۲- مجموعه داده ­های واقعی ۱۱۷
۶-۴- معیارهای ارزیابی و روش های مورد استفاده برای مقایسه ۱۱۷
۶-۵- آزمایشات انجام شده ۱۱۸
۶-۵-۱- آزمایشات مربوط به فاز اول ۱۱۹
۶-۵-۲- آزمایشات مربوط به فاز دوم ۱۲۸
۶-۶- جمع­بندی ۱۳۰

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

فهرست مراجع ۱۳۶
فهرست اشکال

  1. شکل ۱-۱- معماری BDI در عامل ۱۵
  2. شکل ۳-۱- درخت تحقیق مربوط به طبقه ­بندی در مبحث داده ­کاوی ۳۴
  3. شکل ۳-۲- طبقه ­بندی مبتنی بر Ensemble.  .44
  4. شکل ۳-۳- چارچوب روش On-Demand. 47
  5. شکل ۳-۴- نمایی از سیستم OLIN 49
  6. شکل ۳-۵- پروسه SCALLOP. 53
  7. شکل ۵-۱- نمودار ترتیب عملکرد عامل پیشنهادی ۶۶
  8. شکل ۵-۲- معماری عامل پیشنهادی ۶۷
  9. شکل ۵-۳- پنجره نظاره بر روی جریان داده­ ها ۶۸
  10. شکل ۵-۴- گراف ایجاد شده از روی رشته مفهوم­ها ۷۱
  11. شکل ۵-۵- محل تجمع الگوهای استخراج شده از رشته مفهوم­ها ۷۳
  12. شکل ۵-۶- میزان محاسبه شده احتمالها به ازای مقادیر مختلف K 81
  13. شکل ۵-۷- شبه کد Plan کلی عامل ۸۳
  14. شکل ۵-۸- نسبت واریانس به حاصلضرب ۵۰ متغیر دارای مجموع ثابت ۸۵
  15. شکل ۵-۹- وزن دهی چند داده مختلف ۸۶
  16. شکل ۵-۱۰- نمایی کلی از سیستم چندعامله ایجاد شده ۸۸
  17. شکل ۵-۱۱- معماری BDI عامل داده­کاو ۹۳
  18. شکل ۵-۱۲- بخشی از جریان داده و قواعد استخراج شده از آن ۹۹
  19. شکل ۵-۱۳- بخشی از جریان داده و قواعد استخراج شده از آن ۱۰۱
  20. شکل ۶-۱- کد نمونه برای استفاده از بسته نرم افزاری weka. 115
  21. شکل ۶-۲- زمان لازم بر حسب میلی ثانیه برای داده ­های Stagger 120
  22. شکل ۶-۳- زمان مصرف شده برای تطبیق طبقه­بند ۱۲۰
  23. شکل ۶-۴- نمودار مربوط به زمان پردازش روش های مختلف برای داده ­های HyperPlan 121
  24. شکل ۶-۵- زمان مصرف شده برای تطبیق طبقه­بند ۱۲۱
  25. شکل ۶-۶- نمودار مربوط به زمان پردازش روش های مختلف برای داده ­های Nursery 122
  26. شکل ۶-۷- زمان مصرف شده برای تطبیق طبقه­بند برای داده ­های Nursery 122
  27. شکل ۶-۸- عملکرد روش های مختلف بر روی مجموعه داده HyperPlan 124
  28. شکل ۶-۹- نمودار عملکرد روش های مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر ۱۲۴
  29. شکل ۶-۱۰- نمودار عملکرد روش های مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر ۱۲۵
  30. شکل ۶-۱۱- زمان مصرف شده برای تطبیق طبقه­بند برای داده ­های HyperPlan 125
  31. شکل ۶-۱۲- عملکرد روش های مختلف بر روی مجموعه داده Stagger 126
  32. شکل ۶-۱۳- زمان مصرف شده برای تطبیق طبقه­بند برای داده ­های Stagger 126
  33. شکل ۶-۱۴- عملکرد روش های مختلف بر روی مجموعه داده Nursery 127
  34. شکل ۶-۱۵- زمان مصرف شده برای تطبیق طبقه­بند برای داده ­های Nursery 127
  35. شکل ۶-۱۶- نمودار نتایج حاصل از طبقه ­بندی توزیع ­شده مجموعه داده Nursery 130

فهرست جدولها

  1. جدول ۱-۱- ویژگیهای یک عامل ۱۱
  2. جدول ۳-۱- ماتریس حاصل از روش LWClass. 51
  3. جدول ۳-۲- مقایسه تکنیکهای ذکر شده ۵۴
  4. جدول ۵-۱- ساختار اطلاعاتی ذخیره شده برای هر مفهوم و الگو ۶۹
  5. جدول ۵-۲- ساختار اطلاعاتی مربوط به وقوع الگوی “CFDA” 75
  6. جدول ۵-۳- نمونه ای از خروجی تابع سودمندی عامل ۸۱
  7. جدول ۵-۴- اطلاعات مورد استفاده برای تخمین سودمندی یک قاعده ۱۰۵
  8. جدول ۶-۱- دقت طبقه ­بندی روش های مختلف ۱۲۸
  9. جدول ۶-۲- نتایج حاصل از طبقه ­بندی توزیع شده مجموعه داده Nursery در سه مفهوم مختلف ۱۳۰

 
فصل اول
 
معرفی و آشنایی با مفاهیم اولیه
فصل اول
 
معرفی و آشنایی با مفاهیم اولیه
 
۱-۱- مقدمه­ای بر داده ­کاوی
داده ­کاوی به معنای یافتن نیمه خودکار الگوهای پنهان موجود در مجموعه داده ­های[۵] موجود می­باشد[۳۸]. داده ­کاوی از مدلهای تحلیلی ، کلاس بندی و تخمین و برآورد اطلاعات و ارائه نتایج با بهره گرفتن از ابزارهای مربوطه بهره می گیرد. می­توان گفت که داده کاوی در جهت کشف اطلاعات پنهان و روابط موجود در بین داده ­های فعلی و پیش ­بینی موارد نامعلوم و یا مشاهده نشده عمل می­ کند. برای انجام عملیات داده ­کاوی لازم است قبلا روی داده ­های موجود پیش­پردازشهایی انجام گیرد. عمل پیش پردازش اطلاعات خود از دو بخش کاهش اطلاعات و خلاصه­سازی و کلی­سازی داده­ ها تشکیل شده است. کاهش اطلاعات عبارت است از تولید یک مجموعه کوچکتر، از داده ­های اولیه، که تحت عملیات داده ­کاوی نتایج تقریبا یکسانی با نتایج داده ­کاوی روی اطلاعات اولیه به دست دهد[۳۸]. پس از انجام عمل کاهش اطلاعات و حذف خصایص غیر مرتبط نوبت به خلاصه­سازی و کلی­سازی داده­ ها می رسد. داده ­های موجود در بانک­های اطلاعاتی معمولا حاوی اطلاعات در سطوح پایینی هستند، بنابراین خلاصه­سازی مجموعه بزرگی از داده­ ها و ارائه آن به صورت یک مفهوم کلی اهمیت بسیار زیادی دارد. کلی­سازی اطلاعات، فرایندی است که تعداد زیادی از رکوردهای یک بانک اطلاعاتی را به صورت مفهومی در سطح بالاتر ارائه می نماید. خود روش های داده ­کاوی به سه دسته کلی تقسیم می­شوند که عبارتند از خوشه­بندی، طبقه ­بندی و کشف قواعد وابستگی. در ادامه هر یک از این روشها را بطور کلی معرفی می­نماییم.
۱-۱-۱- خوشه­بندی
فرایند خوشه­بندی سعی دارد که یک مجموعه داده را به چندین خوشه­ تقسیم نماید بطوریکه داده ­های قرار گرفته در یک خوشه با یکدیگر شبیه بوده و با داده ­های خوشه ­های دیگر متفاوت باشند. در حال حاضر روش های متعددی برای خوشه­بندی داده­ ها وجود دارد که بر اساس نوع داده­ ها، شکل خوشه ­ها، فاصله داده­ ها و غیره عمل خوشه­بندی را انجام می­ دهند. مهمترین روش های خوشه­بندی در زیر معرفی شده ­اند:

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

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

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

 

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

البته دسته دیگری از روش های خوشه­بندی مانند روش های مبتنی بر گرید، روش های مبتنی بر مدل و . وجود دارند که می­توانید آنها را در ]۳۸[ مطالعه نمایید.
۱-۱-۲- کشف قواعد وابستگی
بحث قواعد وابستگی به مقوله کشف عناصری یا المان­هایی در یک مجموعه داده می ­پردازد که معمولا با یکدیگر اتفاق می­افتند و بعبارتی رخداد آنها بنوعی با یکدیگر ارتباط دارد. بطور کلی هر قاعده یا rule که از این مجموعه داده­ بدست می­­آید، دارای شکل کلی بصورت  می­باشد که نشان می­دهد چنانچه الگوی X اتفاق بیفتد، با احتمال بالایی الگوی Y نیز اتفاق خواهد افتاد. برای مطالعه بیشتر در مورد مقوله کشف قواعد وابستگی می­توانید به ]۳۸[ مراجعه نمایید.
۱-۱-۳- طبقه ­بندی
فرایند طبقه ­بندی در واقع نوعی یادگیری با ناظر می­باشد که در طی دو مرحله انجام می­گردد. در مرحله اول مجموعه ­ای از داده­ ها که در آن هر داده شامل تعدادی خصوصیت دارای مقدار و یک خصوصیت بنام خصوصیت کلاس می­باشد، برای ایجاد یک مدل داده بکار می­روند که این مدل داده در واقع توصیف کننده مفهوم و خصوصیات مجموعه داده ­هایی است که این مدل از روی آنها ایجاد شده است. مرحله دوم فرایند طبقه ­بندی اعمال یا بکارگیری مدل داده ایجاد شده بر روی داده ­هایی است که شامل تمام خصوصیات داده ­هایی که برای ایجاد مدل داده بکار گرفته­ شده ­اند، می­باشد، بجز خصوصیت کلاس این مقادیر که هدف از عمل طبقه ­بندی نیز تخمین مقدار این خصوصیت می­باشد.
الگوریتم­ها و روش های مختلفی برای طبقه ­بندی تاکنون پیشنهاد شده ­اند که برای مثال می­توان از روش های طبقه ­بندی با بهره گرفتن از درخت تصمیم، طبقه ­بندی بیزین، SVM ، طبقه ­بندی با بهره گرفتن از شبکه ­های عصبی، طبقه ­بندی مبتنی بر قواعد و . ]۵۶[ نام برد. در اینجا ما قصد نداریم وارد مباحث مربوط به الگوریتم­ها و روش های طبقه ­بندی شویم و تنها روش طبقه ­بندی مبتنی بر قواعد را بدلیل استفاده از آن در فاز دوم پروژه در اینجا معرفی خواهیم نمود. در صورت نیاز به مطالعه بیشتر می­توانید به فصل ششم مرجع ]۳۸[ مراجعه نمایید.
تعداد صفحه :۱۵۷
قیمت : ۱۴۷۰۰ تومان

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

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

پشتیبانی سایت :               [email protected]

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