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

تعداد صفحات: ۱۴۲ | قابل ویرایش

فهرست مطالب

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

۱-۱- مقدمه­ای بر داده­کاوی.. ۲

۱-۱-۱- خوشه­بندی.. ۳

۱-۱-۲- کشف قواعد وابستگی.. ۴

۱-۱-۳- طبقه­بندی.. ۴

۱-۱-۳-۱- طبقه­بندی مبتنی بر قواعد.. ۵

۱-۲- داده­کاوی توزیع­شده.. ۷

۱-۳- عاملها و سیستمهای چندعامله.. ۸

۱-۳-۱- عامل.. ۸

۱-۳-۱-۱- مقایسه عامل با شی.. ۹

۱-۳-۱-۲- معماری عاملها.. ۱۱

۱-۳-۱-۳- معماری BDI. 12

۱-۳-۲- سیستم­های چندعامله.. ۱۴

۱-۳-۲-۱- مذاکره.. ۱۷

۱-۴- بهره­گیری از عامل برای داده­کاوی.. ۱۹

۱-۴-۱- سیستم­های چندعامله، بستری برای داده­کاوی توزیع شده.. ۱۹

۱-۵- جمع­بندی.. ۲۲

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

۲-۱- مقدمه­ای بر داده­کاوی پویا.. ۲۴

۲-۲- جریان داده.. ۲۵

۲-۳- طبقه­بندی جریان داده.. ۲۶

۲-۳-۱- موضوعات پژوهشی.. ۲۷

۲-۴- جمع­بندی.. ۳۱

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

۳-۱- مقدمه.. ۳۴

۳-۲- داده­کاوی توزیع­شده ایستا.. ۳۵

۳-۲-۱- روشهای غیرمتمرکز.. ۳۶

۳-۲-۲- روشهای مبتنی بر توزیع ذاتی داده­ها.. ۳۷

۳-۳- کارهای مهم انجام شده در زمینه داده­کاوی با استفاده از عامل   ۳۸

۳-۴- کارهای انجام شده در زمینه طبقه­بندی جریان داده­ها.. ۴۱

۳-۴-۱- روشهای طبقه­بندی Ensemble-based. 41

۳-۴-۲- درختهای تصمیم بسیار سریع.. ۴۳

۳-۴-۳- طبقه­بندی On-Demand. 46

۳-۴-۴- OLIN.. 48

۳-۴-۵- الگوریتمهای LWClass. 49

۳-۴-۶- الگوریتم ANNCAD.. 51

۳-۴-۷- الگوریتم SCALLOP. 51

۳-۴-۸- طبقه­بندی جریان داده­ها با استفاده از یک روش Rule-based. 53

۳-۵- جمع­بندی.. ۵۴

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

۴-۱- مقدمه.. ۵۶

۴-۲- تعریف مساله برای فاز اول.. ۵۶

۴-۲-۱- جریان داده.. ۵۷

۴-۲-۲- مفهوم یا مدل موجود در جریان داده.. ۵۷

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

۴-۳- تعریف مساله برای فاز دوم.. ۵۹

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

۵-۱- مقدمه.. ۶۳

۵-۲- رویکرد پیشنهادی برای فاز اول پروژه.. ۶۳

۵-۲-۱- عامل و ویژگیهای آن در این مساله.. ۶۴

۵-۲-۲- عملکرد کلی عامل.. ۶۵

۵-۲-۳- معماری عامل.. ۶۶

۵-۲-۳-۱- حسگرها .. ۶۷

۵-۲-۳-۲- پایگاه دانش عامل.. ۶۸

۵-۲-۳-۳- تابع ارزیابی محیط.. ۷۰

۵-۲-۳-۳-۱- نحوه تشخیص اطلاعات و نگهداری الگوهای recur در جریان داده   ۷۰

۵-۲-۳-۳-۲- نحوه استخراج الگوهای recur 70

۵-۲-۳-۳-۳- نحوه بروزرسانی اطلاعات مربوط به الگوهای recur 73

۵-۲-۳-۳-۴- نحوه محاسبه وقوع احتمال وقوع یک الگوی خاص.. ۷۴

۵-۲-۳-۴- تابع سودمندی.. ۷۵

۵-۲-۳-۵- بخش تصمیم­گیری و Planning. 79

۵-۲-۳-۵-۱- بخش تصمیم­گیری.. ۷۹

۵-۲-۳-۵-۲- Planning. 83

۵-۲-۳-۶- بخش Action. 86

۵-۳- رویکرد پیشنهادی برای فاز دوم مساله.. ۸۷

۵-۳-۱- عاملهای مشتری.. ۸۸

۵-۳-۲- عامل صفحه زرد.. ۹۰

۵-۳-۳- عاملهای داده­کاو.. ۹۱

۵-۳-۳-۱- معماری عاملهای داده­کاو.. ۹۲

۵-۳-۳-۱-۱- تابع BRF. 94

۵-۳-۳-۱-۲- تابع Generate Options. 95

۵-۳-۳-۱-۳- تابع فیلتر.. ۹۵

۵-۳-۳-۱-۴- بخش Actions. 96

۵-۳-۳-۱-۵- Plan های عامل.. ۹۷

۵-۳-۳-۱-۵- ۱- Plan مربوط به طبقه­بندی.. ۹۷

۵-۳-۳-۱-۵-۲- Plan مربوط به تطبیق طبقه­بند .. ۹۸

۵-۳-۳-۱-۵-۳- Plan مربوط به خرید و فروش قواعد با استفاده از مذاکره   ۱۰۱

۵-۴- جمع­بندی.. ۱۱۱

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

۶-۱- مقدمه.. ۱۱۴

۶-۲- محیط عملیاتی.. ۱۱۴

۶-۳- مجموعه داده­های مورد استفاده.. ۱۱۶

۶-۳-۱- مجموعه داده­های استاندارد.. ۱۱۶

۶-۳-۲- مجموعه داده­های واقعی.. ۱۱۷

۶-۴- معیارهای ارزیابی و روشهای مورد استفاده برای مقایسه.. ۱۱۷

۶-۵- آزمایشات انجام شده.. ۱۱۸

۶-۵-۱- آزمایشات مربوط به فاز اول.. ۱۱۹

۶-۵-۲- آزمایشات مربوط به فاز دوم.. ۱۲۸

۶-۶- جمع­بندی.. ۱۳۰

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

 فهرست مراجع.. ۱۳۶

چکیده

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

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

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

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

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

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

داده ­کاوی به معنای یافتن نیمه خودکار الگوهای پنهان موجود در مجموعه داده­های موجود می­باشد[۳۸]. داده­کاوی از مدلهای تحلیلی، کلاس بندی و تخمین و برآورد اطلاعات و ارائه نتایج با استفاده از ابزارهای مربوطه بهره می گیرد. می­توان گفت که داده کاوی در جهت کشف اطلاعات پنهان و روابط موجود در بین داده­های فعلی و پیش­بینی موارد نامعلوم و یا مشاهده نشده عمل می­کند.

برای انجام عملیات داده­کاوی لازم است قبلا روی داده­های موجود پیش­پردازشهایی انجام گیرد. عمل پیش پردازش اطلاعات خود از دو بخش کاهش اطلاعات و خلاصه­سازی و کلی­سازی داده­ها تشکیل شده است. کاهش اطلاعات عبارت است از تولید یک مجموعه کوچکتر، از داده­های اولیه، که تحت عملیات داده­کاوی نتایج تقریبا یکسانی با نتایج داده­کاوی روی اطلاعات اولیه به دست دهد[۳۸].

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

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

خوشه ­بندی

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

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

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

•  روشهای سلسله مراتبی : روشهای سلسله مراتبی به دو دسته کلی روشهای bottom-up و روشهای top-down تقسیم می­ گردند.

طبقه­ بندی

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

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

الگوریتم­ها و روشهای مختلفی برای طبقه­بندی تاکنون پیشنهاد شده­اند که برای مثال می­توان از روشهای طبقه­بندی با استفاده از درخت تصمیم، طبقه­بندی بیزین، SVM ، طبقه­بندی با استفاده از شبکه­های عصبی، طبقه­بندی مبتنی بر قواعد و … ]۵۶[ نام برد.

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

فهرست مراجع

1. عبدالله زاده احمد، معصومی بهروز و آیت­الله زاده شیرازی محمدرضا، مقدمه­ای بر هوش مصنوعی توزیع شده (معرفی عامل و سیستمهای چندعامله)، تهران: انتشارات جلوه، ۱۳۸۴.
2. Aggarwal, C; Han, J; Wang, J; Yu, P. S. “A Framework for Clustering Evolving Data Streams”, Proc. 2003 Int. Con$ on Very Large Data Bases (VLDB’03), Berlin, Germany, Sept. 2003.
3. Aggarwal, C; Han, J; Wang, J; Yu, P. S., “On Demand Classification of Data Streams”, Proc. 2004 Int. Con$ on Knowledge Discovery and Data Mining (KDD ’04), Seattle, WA, 2004.
4. Aggarwal, C. “Data Streams:Models and Algorithms”, Advances in Database Systems, Vol. 31, 2007, ISBN: 978-0-387-28759-1.
5. Babcock, B; Babu, S; Datar, M; Motwani, R; Widom, J. “Models and issues in data stream systems”. In Proceedings of PODS, 2002.
6. Babcock, B; Datar, M; Motwani, R. “Load Shedding Techniques for Data Stream Systems”, In Proc. of the 2003 Workshop on Management and Processing of Data Streams (MPDS 2003).
7. Bailey, S; Grossman, R; Sivakumar, H; Turinsky, H. “Papyrus: A System for Data Mining Over Local and Wide Area Clusters and Super-clusters”. In Proceedings of the 1999 ACM/IEEE conference on Supercomputing, page 63, Portland, OR, 1999. ACM Press.
8. Bala, J; Baik, S; Hadjarian, A; Gogia, B. K ; Manthorne, C. “Application of a Distributed Data Mining Approach to Network Intrusion Detection”. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems, pages 1419–۱۴۲۰, Bologna, Italy, 2002. ACM Press.