چکیده امروزه با توجه به گسترش روز افزون اطلاعاتی که بشر با آنها سر و کار دارد، بهره‌گيری از روش‌هايی همچون داده‌کاوی برای استخراج دانش و اطلاعات نهفته در داده‌ها، امری غيرقابل اجتناب می‌باشد. یکی از مسائلی که امروزه در بحث داده‌کاوی مورد توجه قرار گرفته است، بحث توزیع‌شدگی ذاتی داده‌ها است. توسعه فناوری شبکه‌های کامپیوتری و تکنولوژی پایگاه داده توزیع شده، ذخیره سازی توزیع شده و نسل فنی جدیدی از داده کاوی توزیع شده را ترویج داده است. داده کاوی توزیع شده از محاسبات توزیع شده استفاده می‌کند، و دانش مورد نیاز کاربران را از پایگاه داده‌های توزیع شده استخراج می‌کند. این حوزه چشم‌انداز کاربردی گسترده‌ای دارد. سه هدف اصلی برای داده کاوی از سیستم‌های اطلاعاتی توزیع شده وجود دارد: 1) شناسایی الگوهای مهم محلی در پایگاه داده‌های مجزا، 2) ادغام الگوهای محلی و استخراج الگوهای کلی پس از یکپارچه شدن پایگاه داده‌های توزیع شده، و 3) شناسایی الگوهای رابطه‌ای خاص در مجموعه داده‌های مختلف.با توجه به قابليت‌های عامل و سيستم‌های چندعامله و مناسب بودن آنها برای محيط‌های توزيع شده به نظر می‌رسد که بتوان از قابليت‌های آنها برای داده‌کاوی در محيط‌های توزيع شده بهره برد. در اين تحقيق ما قصد داريم تا ضمن بررسی کارهای موجود در زمينه کاربرد عامل و سيستم‌های چندعامله در داده‌کاوی، بحث کاوش قوانین انجمنی در محیط‌های توزیع شده را مورد بررسی قرار دهیم. ما مساله خود را در دو فاز مورد بررسی قرار خواهيم داد. در فاز اول خصوصيت‌ها و قابلیت‌های يک عامل و مزایای ترکیب تکنولوژی چند عامله با داده‌کاوی توزیع شده مورد بررسی قرار خواهند گرفت، و در فاز دوم یک معماری برای داده‌کاوی در محیط‌های توزیع شده برپایه‌ی تکنولوژی چند عامله ارائه می‌دهیم. بطور کلی دستاورد اصلی اين تحقيق ارائه يک رويکرد مبتنی بر عامل برای مساله کاوش قوانین انجمنی با استفاده از قابليت‌های هدفگرايی، هوشمندی، يادگيری و استدلال است. کلمات کلیدی: داده کاوی توزیع شده، سیستم چند عامله، قوانین انجمنی Abstract Due to the ever-growing increase in the amount of data we deal with, tapping methods like data mining to extract hidden knowledge and information in the data seems inevitable. One of the topics of data mining that has recently attracted a lot of attention is the inherent distribution of data. The development of computer network technology and distributed database technology has promoted distributed data storage and the new technical generation of distributed data mining. Distributed data mining (DDM) uses distributed computing and finds the required knowledge for the users from the distributed database. This domain has widespread applications. The purpose of data mining from distributed information systems is usually threefold: 1) Identifying locally significant patterns in individual databases; 2) Combining local patterns and discovering global patterns after unifying distributed databases in a single view; and 3) Finding patterns which follow special relationships across different data collections.Considering agent and multi-agent capabilities in distributed environments, it seems that using their features can be useful in these environments. In this study, in addition to reviewing the related work and researches in agent-based data mining area, we intend to consider the problem of mining association rules in distributed environments. We study this problem in two phases. First we mention the features and capabilities of agents for data mining task, and analyze the advantages of multi-agent combining with distributed data mining. Then, in the second phase we propose a DDM architecture based on multi-agent technology. To conclude, the main result of this thesis is the presentation of agent-based approach for DDM with concept drift using goal-oriented, intelligence, learning and reasoning features of agents. Keywords: Distributed data mining, M-Agent system, Association rules فهرست رئوس مطالبفصل اول مقدمه و کلیات تحقیق. 11-1- مقدمه. 21-2- تعریف مسأله و سوالات اصلی تحقیق. 21-3- اهمیت و ضرورت انجام تحقیق. 31-4- اهداف اساسی از انجام تحقیق. 31-4-1- هدف اصلی. 31-4-2- اهداف فرعی. 31-5- پرسش‌های تحقیق. 41-5-1- پرسش اصلی. 41-5-2- پرسش‌های فرعی. 41-6- فرضیه‌ها. 41-7- روش تحقیق. 41-8- جنبه‌های نوآوری. 51-9- مراحل انجام تحقیق. 51-10- ساختار پایان‌نامه. 5فصل دوم ادبیات و پیشینه تحقیق. 62-1- مقدمه. 72-2- داده‌کاوی. 72-2-1- خوشه‌بندی. 82-2-1-1- روش‌های تقسيم‌بندی. 82-2-1-2- روش‌های سلسله مراتبی. 82-2-1-3- روش‌های مبتنی بر چگالی. 92-2-2- طبقه‌بندی. 92-2-2-1- طبقه‌بندی مبتنی بر قواعد. 102-2-3- کشف قواعد انجمنی. 122-2-3-1- تعاریف و مفاهیم اصلی در قواعد انجمنی. 122-2-3-1-1- تقسیم بندی قواعد انجمنی. 142-2-3-1-2- استخراج قواعد تک‌سطحی تک بعدی دودویی. 142-2-3-1-2-1- مرحله پیوست. 162-2-3-1-2-2- مرحله هرس. 172-2-3-1-3- محاسبه اطمینان و استخراج قواعد نهایی. 172-3- داده‌کاوی توزيع شده. 172-4- عامل‌ها و سيستم‌های چندعامله. 182-4-1- عامل. 192-4-1-1- مقايسه عامل با شیء. 202-4-1-2- معماری عامل‌ها. 232-4-1-2-1- معماری BDI242-4-2- سيستم‌های چندعامله. 252-4-2-1- مذاکره. 282-5- بهره‌گيری از عامل برای داده‌کاوی. 302-5-1- سيستم‌های چندعامله، بستری برای داده‌کاوی توزيع شده 302-6- مروری بر کارهای انجام شده. 322-6-1- داده‌کاوی توزيع شده. 332-6-2- کارهای مهم انجام شده در زمينه داده‌کاوی با استفاده از عامل. 362-7- جمع‌بندی. 39فصل سوم روش تحقیق. 403-1- مقدمه. 413-2- داده‌کاوی توزیع شده. 413-2-1- گروه‌بندی مدل‌های داده‌کاوی توزیع شده. 423-2-2- مشکلات داده‌کاوی توزیع شده. 433-2-2-1- افزونگی داده. 433-2-2-2- تغییرات پویای محیط. 433-2-2-3- سربار ارتباطات. 443-2-2-4- مشکلات داده‌کاوی توزیع شده به روش سنتی. 443-3- عامل‌ها و داده‌کاوی. 443-3-1- حوزه کاوش عامل. 463-3-2- داده‌کاوی برپایه‌ی عامل. 483-3-3- مزیت بهره‌گیری از عامل‌ها در داده‌کاوی. 503-3-3-1- زیرساخت داده‌کاوی سازمانی. 513-3-3-2- بکارگیری هوشمندی انسان و دامنه. 513-3-3-3- پشتیبانی از کاوش توزیع شده و موازی. 513-3-3-4- پیش پردازش داده. 523-3-3-5- یادگیری سازگار. 523-3-3-6- کاوش تعاملی. 523-3-4- داده‌کاوی توزیع شده برپایه‌ی عامل‌ها. 533-3-4-1- چالش‌های داده‌کاوی توزیع شده. 533-3-5- مزیت بهره‌گیری از عامل‌ها در داده‌کاوی توزیع شده 553-3-5-1- ایزوله بودن منابع داده. 553-3-5-2- پویایی منابع داده و دستگاه‌های محاسباتی. 553-3-5-3- داده‌کاوی توزیع شده‌ی تعاملی. 563-3-5-4- انتخاب منابع و جمع‌اوری داده پویا. 563-3-5-5- محدودیت‌های زمانی در منابع داده توزیع شده. 563-3-5-6- داده‌کاوی توزیع شده با چند استراتژی. 563-3-5-7- داده‌کاوی توزیع شده‌ی مشارکتی. 563-3-5-8- پوشیدگی داده‌های منبع. 563-3-5-9- محدودیت‌های سازمانی در منابع داده توزیع شده 573-4- الگوریتم‌های کشف قوانین انجمنی. 573-4-1- الگوریتم AIS. 573-4-2- الگوریتم SETM.. 583-4-3- الگوریتم Apriori یا پیشینار. 583-4-4- الگوریتمAprioriTid. 603-5- جمع‌بندی. 61فصل چهارم محاسبات و یافته‌های تحقیق. 624-1- مقدمه. 634-2- معماری پیشنهادی برای داده کاوی توزیع شده برپایه‌ی سیستم‌های چند عامله. 664-2-1- معماری چهار لایه‌ی پیشنهادی. 664-2-1-1- لایه‌ی اول، لایه‌ی کاربر. 664-2-1-2- لایه‌ی دوم، لایه‌ی مدیریت. 674-2-1-3- لایه‌ی سوم، لایه پردازش. 684-2-1-4- لایه‌ی چهارم، لایه‌ی منابع. 694-3- مطالعه موردی. 714-3-1- تحلیل عملکرد الگوریتم‌های کشف قوانین انجمنی. 714-3-2- F-Trade: یک سیستم کاوش عامل برای سرویس‌های مالی 754-3-3- داده‌کاوی چند منبع بر پایه‌ی عامل. 774-3-4- کاوش الگوی رفتار سازگار بر پایه‌ی عامل توسط HMM 814-3-4-1- چارچوب سیستم. 814-3-4-2- مدلسازی عامل. 834-4- جمع‌بندی. 84فصل پنجم نتیجه‌گیری و پیشنهادات. 865-1- مقدمه. 875-2- خلاصه تحقیق. 875-3- پیشنهادات برای کارهای آتی. 87پیوست منابع و مآخذ. 89 فهرست جداول و نمودارهاجدول 2- 1: ویژگی‌های يک عامل. 21نمودار 4- 1: تغییرات رفتار الگوریتم‌های مختلف. 73نمودار 4- 2: تغییرات رفتار الگوریتم‌های مختلف در یک فروشگاه خرده فروشی. 74نمودار 4- 3: مقایسه‌ی رفتار الگوریتم‌های AprioriTid و Apriori74نمودار 4- 4: مقایسه عملکرد الگوریتم‌هایAprioriTid ، Apriori Hybrid و Apriori در آزمایش‌های مختلف. 75 فهرست تصاویرشکل 2- 1: معماری BDI در عامل. 26شکل 2- 2: درخت تحقيق مبحث داده‌کاوی. 33شکل 3- 1:یک چارچوب داده‌کاوی توزیع شده. 42شکل 3- 2: گروه‌بندی سیستم‌های داده‌کاوی توزیع شده. 43شکل 3- 3: اشتراک عمل چند بعدی کاوش- عامل. 47شکل 3- 4: الگوریتم Apriori59شکل 3- 5: توضیح الگوریتم Apriori59شکل 3- 6: الگوریتم AprioriTid. 60شکل 4- 1: چارچوب تحقیقاتی کاوش- عامل. 64شکل 4- 3: لایه‌ی کاربر. 66شکل 4- 4: لایه‌ی مدیریت. 67شکل 4- 5: لایه‌ی پردازش. 68شکل 4- 6: لایه‌ی منابع. 69شکل 4- 7: معماری پیشنهادی برای داده کاوی توزیع شده برپایه‌ی سیستم‌های چند عامله. 70شکل 4- 8: چارچوب F-Trade. 77شکل 4- 9: چارچوب MSCM-AKD.. 78شکل 4- 10: کاوش ترکیبی چند منبع بر پایه‌ی عامل. 80شکل 4- 11: کاوش چند منبع با شبکه‌بندی بر پایه‌ی عامل. 81شکل 4- 12: چارچوب کشف الگوی غیرعادی بر پایه‌ی عامل. 82 فصل اول مقدمه و کلیات تحقیق 1-1- مقدمهدر این فصل به معرفی کلیات این پژوهش و ساختار آن می‌پردازیم. بدین منظور ابتدا به بیان تعریف مسئله، ضرورت، اهداف و پرسش‌های این تحقیق خواهیم پرداخت و در نهایت به تعریف واژه‌ها و اصطلاحات مورد استفاده در پایان نامه می‌پردازیم.1-2- تعریف مسأله و سوالات اصلی تحقیقامروزه با توجه به گسترش روز افزون اطلاعاتی که بشر با آنها سر و کار دارد، بهره‌گيری از روش‌هايی همچون داده‌کاوی برای استخراج دانش و اطلاعات نهفته در داده‌ها، امری غيرقابل اجتناب می‌باشد. یکی از مسائلی که امروزه در بحث داده‌کاوی مورد توجه قرار گرفته است، بحث توزیع‌شدگی ذاتی داده‌ها است. توسعه فناوری شبکه‌های کامپیوتری و تکنولوژی پایگاه داده توزیع شده، ذخیره سازی توزیع شده و نسل فنی جدیدی از داده کاوی توزیع شده را ترویج داده است.داده‌کاوی توزيع شده عبارت است از کشف نيمه خودکار الگوهای پنهان موجود در داده‌ها، در حالتی که داده‌ها و يا مکانيزم‌های استنتاج، به صورت توزيع شده باشند. غيرمتمرکز بودن داده‌ها بدان معناست که داده‌ها به صورت توزيع شده بين دو يا چند سايت بوده و هزينه انتقال تمام يا بخشی از داده‌ها به يک سايت مرکزی، قابل صرف‌نظر نباشد. توزيع شده بودن مکانيزم‌های استنتاج، به معنای لزوم لحاظ کردن هزينه ارتباط بين مکانيزم‌های مختلف در حال استخراج دانش می‌باشد. اين توزیع‌شدگی ممکن است به دلايل مختلفی از جمله ارائه شدن مکانيزم استخراج دانش در قالب يک سرويس اينترنتی و يا صرفاً ناشی از توزیع‌شدگی داده‌ها باشد. چنين رويکردی به داده‌کاوی، برخلاف جهت کلی تحقيقات انجام شده است که به طور عمده به تکنيک‌های متمرکز پرداخته و نه فقط بر تمرکز، که بر همگونی و ساختار مسطح (در مقابل ساختار رابطه‌ای) داده‌های هدف متکی می‌باشند. مسائلی نظير استخراج دانش در حالت عدم دسترسی به تمام داده‌های موجود، برقراری ارتباط موثر و بهينه با ساير مکانيزم‌های در حال استخراج دانش و نيز تبادل دانش يا اطلاعات ميانی به جای اطلاعات خام، فقط تعدادی از مسائل اوليه داده‌کاوی توزيع شده با توجه به تعريف آن می‌باشند. بنابراين، داده‌کاوی توزيع شده در عين حال که به عنوان راه حلی کليدی برای مشکلات اصلی پيش روی داده‌کاوی مطرح می‌باشد، خود سرمنشأ چالش‌ها و مسائل متعددی گرديده است؛ حل مؤثر اين مشکلات منجر به استفاده هرچه بيشتر از داده‌کاوی و ايجاد امکانات جديد و بهره‌برداری از پتانسيل‌های موجود در قلمروهائی خواهد شد که عليرغم نياز مبرم به داده‌کاوی، استفاده بسيار محدودی از آن به عمل می‌‌آورند. 1-3- اهمیت و ضرورت انجام تحقیقداده کاوی توزیع شده از محاسبات توزیع شده استفاده می‌کند، و دانش مورد نیاز کاربران را از پایگاه داده‌های توزیع شده استخراج می‌کند. این حوزه چشم‌انداز کاربردی گسترده‌ای دارد. معمولاً پايگاه‌هايی که اين داده‌ها را ايجاد يا دريافت می‌کنند، متعلق به افراد حقيقی يا حقوقی هستند که هر کدام به دنبال اهداف و منافع خود می‌باشند و حاضر نيستند دانش خود را به طور رايگان در اختيار ديگران قرار دهند. سیستم داده کاوی توزیع شده چند عامله، نسبتاً یک حوزه تحقیقاتی جدید است. با تکنولوژی نوظهور هوش مصنوعی سازگار است، انعطاف پذیری و هوشمندی خاصی دارد، استفاده از منابع را بهبود بخشیده و پایداری سیستم را افزایش داده است. و لذا نتایج این تحقیق می‌تواند در عمل مورد استفاده قرار گیرد و به عنوان یک موضوع پژوهشی مورد توجه قرار گیرد.1-4- اهداف اساسی از انجام تحقیقدر اینجا اهداف تحقیق را به دو دسته هدف اصلی و اهداف فرعی تقسیم میکنیم: "هدف کلی" که منظور همان موضوع تحقیق است که قصد مشخص نمودن آن‌را داریم و به عبارتی آنچه در پایان مطالعه قصد رسیدن بدان را داریم. "هدف کلی" معمولاً در یک جمله قابل فهم صریح و رسا و مختصر بیان می‌شود که برای خواننده گویا و قابل فهم است. در گونه دوم "اهداف جزئی یا اختصاصی"تحقیق بیان می‌شود. این اهداف از تقسیم یا شکستن "هدف کلی" به اجزای کوچک‌تر بدست می‌آیند.اهداف جزئی راه رسیدن به "هدف کلی"را قدم به قدم مشخص مینمایند.1-4-1- هدف اصلیارائه مدلی مبتنی بر سیستم‌های چند عامله برای داده‌کاوی در محیط‌های توزیع شدهسیستم داده کاوی توزیع شده چند عامله، حوزه تحقیقاتی جدیدی است که با تکنولوژی نوظهور هوش مصنوعی سازگار بوده، انعطاف پذیری و هوشمندی خاصی داشته، استفاده از منابع را بهبود بخشیده و پایداری سیستم را افزایش داده است. و لذا ارائه مدلی مبتنی بر سیستم‌های چند عامله برای داده‌کاوی در محیط‌های توزیع شده در دستور کار قرار گرفت. نتایج این تحقیق می‌تواند در عمل مورد استفاده قرار گرفته و به عنوان یک موضوع پژوهشی مورد توجه قرار گیرد.1-4-2- اهداف فرعی1-5- پرسش‌های تحقیقپرسشهای تحقیق به دنبال چگونگی دست‌یابی به اهداف تحقیق می‌باشند. لذا مانند اهداف تحقیق، پرسش‌های تحقیق را نیز به دو دسته تقسیم میکنیم: پرسش اصلی و پرسش‌های فرعی. که "پرسش اصلی" به دنبال جوابی در راستای دست‌یابی به هدف اصلی تحقیق می‌باشد و "پرسش‌های فرعی" نیز به دنبال چگونگی دست یافتن به اهداف فرعی تحقیق هستند.پرسش‌های تحقیق حاضر عبارتند از:1-5-1- پرسش اصلی1-5-2- پرسش‌های فرعی1-6- فرضیههابا توجه به قابلیت‌های به اثبات رسیده‌ی عامل‌ها و سیستم‌های چندعامله در زمینه‌های مختلف، فرض ما این است که عامل‌ها و سیستم‌های چندعامله می‌توانند به عنوان ابزار مناسبی در تأثیر بهبود کارایی الگوریتم‌های داده کاوی در محیط توزیع شده به کار گرفته شوند.