پایاننامه کارشناسی رشته مهندسی کامپیوتر گرایش نرم افزار
داده کاوی پویا با بهره گرفتن از عامل
استاد
1393
(در فایل دانلودی نام نویسنده موجود است)
تکه هایی از متن پایان نامه به عنوان نمونه :
چکیده
امروزه با توجه به گسترش روز افزون اطلاعاتی که بشر با آنها سر و کار دارد، بهره گیری از روش هایی همچون داده کاوی برای استخراج دانش و اطلاعات نهفته در داده ها، امری غیرقابل اجتناب میباشد. بدلیل حجم بسیار بالای داده ها در بسیاری از کاربردها و اهمیت بیشتر داده های جدید، ذخیرهسازی این داده ها امری مقرون به صرفه نیست، لذا داده هایی که باید مورد پردازش قرار گیرند، همواره بصوت پویا در حال تغییر و تحول هستند. مساله دیگری که امروزه در بحث داده کاوی وجود دارد، بحث توزیع شدگی ذاتی داده ها است. معمولا پایگاه هایی که این داده ها را ایجاد یا دریافت می کنند، متعلق به افراد حقیقی یا حقوقی هستند که هر کدام بدنبال اهداف و منافع خود میباشند و حاضر نیستند دانش خود را بطور رایگان در اختیار دیگران قرار دهند.
با توجه به قابلیتهای عامل و سیستمهای چندعامله و مناسب بودن آنها برای محیطهای پویا و توزیع شده بنظر میرسد که بتوان از قابلیتهای آنها برای داده کاوی در محیطهای پویا و محیطهای توزیع شده بهره برد. اکثر کارهایی که تاکنون در زمینه بهره گیری از عامل و سیستمهای چندعامله انجام شده است خصوصیتهایی همانند خودآغازی و بخصوص متحرک بودن عاملها را مورد بررسی قرار داده است و در آنها مواردی همچون هوشمندی، یادگیری، قابلیت استدلال، هدفگرایی و قابلیتهای اجتماعی عاملها مورد بررسی قرار نگرفته است. در این تحقیق ما قصد داریم تا ضمن بررسی کارهای موجود در زمینه کاربرد عامل و سیستمهای چندعامله در داده کاوی، بحث طبقه بندی جریان داده ها را در یک محیط پویا مورد بررسی قرار دهیم. ما مساله خود را در دو فاز مورد بررسی قرار خواهیم داد. در فاز اول خصوصیتهای یک عامل تنها مورد بررسی قرار خواهد گرفت و در فاز دوم قابلیتهای اجتماعی عاملها مانند مذاکره، دستیابی به توافق و … برای داده کاوی در یک محیط پویا و توزیعشده رقابتی مورد استفاده قرار خواهد گرفت. بطور کلی دستاوردهای اصلی این تحقیق عبارتند از 1) ارائه یک رویکرد مبتنی بر عامل برای مساله طبقه بندی جریان داده های دارای تغییر مفهوم و پویا با بهره گرفتن از قابلیتهای هدفگرایی، هوشمندی، یادگیری و استدلال 2) ارائه یک رویکرد مبتنی بر سیستمهای چندعامله برای طبقه بندی جریان داده های توزیعشده در یک محیط رقابتی با بهره گرفتن از قابلیتهای اجتماعی عاملها و دستیابی به توافق. نتایج حاصل از آزمایشات انجام شده در این پایان نامه نشاندهنده برتری استفاده از عاملها و سیستمهای چندعامله برای بحث طبقه بندی و داده کاوی در محیطهای پویا و توزیع شده میباشد.
کلمات کلیدی:
داده کاوی[1]، طبقه بندی[2]، جریان داده[3]، عامل[4].
فهرست مطالب
1-1- مقدمهای بر داده کاوی.. 2
1-1-3-1- طبقه بندی مبتنی بر قواعد.. 5
1-3- عاملها و سیستمهای چندعامله.. 8
1-3-1-1- مقایسه عامل با شی.. 9
1-3-2- سیستمهای چندعامله.. 14
1-4- بهره گیری از عامل برای داده کاوی.. 19
1-4-1- سیستمهای چندعامله، بستری برای داده کاوی توزیع شده.. 19
2-1- مقدمهای بر داده کاوی پویا.. 24
2-3- طبقه بندی جریان داده.. 26
3-2- داده کاوی توزیعشده ایستا.. 35
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-5- الگوریتمهای LWClass. 49
3-4-8- طبقه بندی جریان داده ها با بهره گرفتن از یک روش Rule-based. 53
4-2- تعریف مساله برای فاز اول.. 56
4-2-2- مفهوم یا مدل موجود در جریان داده.. 57
4-2-3- مساله طبقه بندی جریان داده های دارای تغییر مفهوم.. 57
4-3- تعریف مساله برای فاز دوم.. 59
5-2- رویکرد پیشنهادی برای فاز اول پروژه.. 63
5-2-1- عامل و ویژگیهای آن در این مساله.. 64
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-5- بخش تصمیم گیری و Planning. 79
5-2-3-5-1- بخش تصمیمگیری.. 79
5-3- رویکرد پیشنهادی برای فاز دوم مساله.. 87
5-3-3-1- معماری عاملهای دادهکاو.. 92
5-3-3-1-2- تابع Generate Options. 95
5-3-3-1-5- 1- Plan مربوط به طبقه بندی.. 97
5-3-3-1-5-2- Plan مربوط به تطبیق طبقهبند .. 98
5-3-3-1-5-3- Plan مربوط به خرید و فروش قواعد با بهره گرفتن از مذاکره 101
6-3- مجموعه داده های مورد استفاده.. 116
6-3-1- مجموعه داده های استاندارد.. 116
6-3-2- مجموعه داده های واقعی.. 117
6-4- معیارهای ارزیابی و روش های مورد استفاده برای مقایسه.. 117
6-5-1- آزمایشات مربوط به فاز اول.. 119
6-5-2- آزمایشات مربوط به فاز دوم.. 128
فهرست اشکال
- شکل 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[ مراجعه نمایید.
(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)
تعداد صفحه :157
قیمت :14700 تومان
بلافاصله پس از پرداخت لینک دانلود فایل در اختیار شما قرار می گیرد
و در ضمن فایل خریداری شده به ایمیل شما ارسال می شود.
پشتیبانی سایت : serderehi@gmail.com
در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.
14,700 تومانافزودن به سبد خرید