شکل ۳- ۵: توضیح الگوریتم Apriori 59
شکل ۳- ۶: الگوریتم AprioriTid 60
شکل ۴- ۱: چارچوب تحقیقاتی کاوش- عامل ۶۴
شکل ۴- ۳: لایه‌ی کاربر ۶۶
شکل ۴- ۴: لایه‌ی مدیریت ۶۷
شکل ۴- ۵: لایه‌ی پردازش ۶۸
شکل ۴- ۶: لایه‌ی منابع ۶۹
شکل ۴- ۷: معماری پیشنهادی برای داده کاوی توزیع شده برپایه‌ی سیستمهای چند عامله ۷۰
( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
شکل ۴- ۸: چارچوب F-Trade 77
شکل ۴- ۹: چارچوب MSCM-AKD 78
شکل ۴- ۱۰: کاوش ترکیبی چند منبع بر پایه‌ی عامل ۸۰
شکل ۴- ۱۱: کاوش چند منبع با شبکه‌بندی بر پایه‌ی عامل ۸۱
شکل ۴- ۱۲: چارچوب کشف الگوی غیرعادی بر پایه‌ی عامل ۸۲
فصل اول مقدمه و کلیات تحقیق
۱-۱- مقدمه
در این فصل به معرفی کلیات این پژوهش و ساختار آن میپردازیم. بدین منظور ابتدا به بیان تعریف مسئله، ضرورت، اهداف و پرسشهای این تحقیق خواهیم پرداخت و در نهایت به تعریف واژه‌ها و اصطلاحات مورد استفاده در پایان نامه میپردازیم.
۱-۲- تعریف مسأله و سوالات اصلی تحقیق
امروزه با توجه به گسترش روز افزون اطلاعاتی که بشر با آنها سر و کار دارد، بهرهگیری از روش‌هایی همچون دادهکاوی برای استخراج دانش و اطلاعات نهفته در داده‌ها، امری غیرقابل اجتناب میباشد. یکی از مسائلی که امروزه در بحث دادهکاوی مورد توجه قرار گرفته است، بحث توزیعشدگی ذاتی داده‌ها است. توسعه فناوری شبکه‌های کامپیوتری و تکنولوژی پایگاه داده توزیع شده، ذخیره سازی توزیع شده و نسل فنی جدیدی از داده کاوی توزیع شده را ترویج داده است.
دادهکاوی توزیع شده عبارت است از کشف نیمه خودکار الگوهای پنهان موجود در داده‌ها، در حالتی که داده‌ها و یا مکانیزم‌های استنتاج، به صورت توزیع شده باشند. غیرمتمرکز بودن داده‌ها بدان معناست که داده‌ها به صورت توزیع شده بین دو یا چند سایت بوده و هزینه انتقال تمام یا بخشی از داده‌ها به یک سایت مرکزی، قابل صرفنظر نباشد. توزیع شده بودن مکانیزم‌های استنتاج، به معنای لزوم لحاظ کردن هزینه ارتباط بین مکانیزم‌های مختلف در حال استخراج دانش میباشد. این توزیعشدگی ممکن است به دلایل مختلفی از جمله ارائه شدن مکانیزم استخراج دانش در قالب یک سرویس اینترنتی و یا صرفاً ناشی از توزیعشدگی داده‌ها باشد. چنین رویکردی به دادهکاوی، برخلاف جهت کلی تحقیقات انجام شده است که به طور عمده به تکنیکهای متمرکز پرداخته و نه فقط بر تمرکز، که بر همگونی و ساختار مسطح (در مقابل ساختار رابطهای) داده‌های هدف متکی میباشند. مسائلی نظیر استخراج دانش در حالت عدم دسترسی به تمام داده‌های موجود، برقراری ارتباط موثر و بهینه با سایر مکانیزم‌های در حال استخراج دانش و نیز تبادل دانش یا اطلاعات میانی به جای اطلاعات خام، فقط تعدادی از مسائل اولیه دادهکاوی توزیع شده با توجه به تعریف آن میباشند. بنابراین، دادهکاوی توزیع شده در عین حال که به عنوان راه حلی کلیدی برای مشکلات اصلی پیش روی دادهکاوی مطرح میباشد، خود سرمنشأ چالش‌ها و مسائل متعددی گردیده است؛ حل مؤثر این مشکلات منجر به استفاده هرچه بیشتر از دادهکاوی و ایجاد امکانات جدید و بهره‌برداری از پتانسیل‌های موجود در قلمروهائی خواهد شد که علیرغم نیاز مبرم به دادهکاوی، استفاده بسیار محدودی از آن به عمل میآورند.
۱-۳- اهمیت و ضرورت انجام تحقیق
داده کاوی توزیع شده از محاسبات توزیع شده استفاده میکند، و دانش مورد نیاز کاربران را از پایگاه داده‌های توزیع شده استخراج میکند. این حوزه چشمانداز کاربردی گستردهای دارد. معمولاً پایگاه‌هایی که این داده‌ها را ایجاد یا دریافت میکنند، متعلق به افراد حقیقی یا حقوقی هستند که هر کدام به دنبال اهداف و منافع خود میباشند و حاضر نیستند دانش خود را به طور رایگان در اختیار دیگران قرار دهند. سیستم داده کاوی توزیع شده چند عامله، نسبتاً یک حوزه تحقیقاتی جدید است. با تکنولوژی نوظهور هوش مصنوعی سازگار است، انعطاف پذیری و هوشمندی خاصی دارد، استفاده از منابع را بهبود بخشیده و پایداری سیستم را افزایش داده است. و لذا نتایج این تحقیق میتواند در عمل مورد استفاده قرار گیرد و به عنوان یک موضوع پژوهشی مورد توجه قرار گیرد.
۱-۴- اهداف اساسی از انجام تحقیق
در اینجا اهداف تحقیق را به دو دسته هدف اصلی و اهداف فرعی تقسیم میکنیم: “هدف کلی” که منظور همان موضوع تحقیق است که قصد مشخص نمودن آن‌را داریم و به عبارتی آنچه در پایان مطالعه قصد رسیدن بدان را داریم. “هدف کلی” معمولاً در یک جمله قابل فهم صریح و رسا و مختصر بیان میشود که برای خواننده گویا و قابل فهم است. در گونه دوم “اهداف جزئی یا اختصاصی” تحقیق بیان میشود. این اهداف از تقسیم یا شکستن “هدف کلی” به اجزای کوچک‌تر بدست می‌آیند. اهداف جزئی راه رسیدن به "هدف کلی” را قدم به قدم مشخص مینمایند.
۱-۴-۱- هدف اصلی
ارائه مدلی مبتنی بر سیستمهای چند عامله برای دادهکاوی در محیطهای توزیع شده
سیستم داده کاوی توزیع شده چند عامله، حوزه تحقیقاتی جدیدی است که با تکنولوژی نوظهور هوش مصنوعی سازگار بوده، انعطاف پذیری و هوشمندی خاصی داشته، استفاده از منابع را بهبود بخشیده و پایداری سیستم را افزایش داده است. و لذا ارائه مدلی مبتنی بر سیستمهای چند عامله برای دادهکاوی در محیطهای توزیع شده در دستور کار قرار گرفت. نتایج این تحقیق میتواند در عمل مورد استفاده قرار گرفته و به عنوان یک موضوع پژوهشی مورد توجه قرار گیرد.
۱-۴-۲- اهداف فرعی
بررسی قوانین انجمنی در چند مدل از داده کاوی
ارائه یک مدل مبتنی بر سیستمهای چند عامله
ارزیابی مدل
۱-۵- پرسشهای تحقیق
پرسشهای تحقیق به دنبال چگونگی دست‌یابی به اهداف تحقیق میباشند. لذا مانند اهداف تحقیق، پرسشهای تحقیق را نیز به دو دسته تقسیم میکنیم: پرسش اصلی و پرسشهای فرعی. که “پرسش اصلی” به دنبال جوابی در راستای دست‌یابی به هدف اصلی تحقیق میباشد و “پرسشهای فرعی” نیز به دنبال چگونگی دست یافتن به اهداف فرعی تحقیق هستند.
پرسشهای تحقیق حاضر عبارتند از:
۱-۵-۱- پرسش اصلی
استفاده از عاملها و سیستمهای چندعامله در داده کاوی توزیع شده چه اثراتی ایجاد میکند؟
۱-۵-۲- پرسشهای فرعی
چه روش‌هایی برای بهینه سازی الگوریتمهای موجود، وجود دارد؟
عاملها و سیستمهای چندعامله در حوزه داده کاوی توزیع شده در چه کاربردهایی حائز اهمیت است؟
چه راه حل‌هایی را میتوان برای رفع مشکلات موجود در این حوزه یافت؟
۱-۶- فرضیه‌ها
با توجه به قابلیت‌های به اثبات رسیده‌ی عاملها و سیستمهای چندعامله در زمینه‌های مختلف، فرض ما این است که عاملها و سیستمهای چندعامله میتوانند به عنوان ابزار مناسبی در تأثیر بهبود کارایی الگوریتمهای داده کاوی در محیط توزیع شده به کار گرفته شوند.
۱-۷- روش تحقیق
روش انجام تحقیق از طریق مطالعه الگوریتمها و روشهای مختلف موجود در راستای موضوع تحقیق میباشد. و نیز از طریق مقایسه با روشهای مرتبط موجود انجام خواهد شد.
۱-۸- جنبه‌های نوآوری
با انجام این تحقیق میتوان از تکنیکهای داده کاوی در محیطهای توزیع شده با سرعت و دقت بیشتری بهره برد.
۱-۹- مراحل انجام تحقیق
مطالعه‌ی اولیه و ادبیات مسأله
شناسایی و بیان کامل مسأله
بررسی فعالیتهای پیشین در راستای حل مسأله
بهرهگیری از نقاط قوت روشهای مختلف و دست‌یابی به مدلی کارآمدتر
حل مسأله و تحلیل آن
۱-۱۰- ساختار پایان‌نامه
ساختار این تحقیق شامل پنج فصل است.
فصل یک: مقدمه و کلیات تحقیق ارائه خواهد شد و به تعریف مسئله و ضرورت انجام تحقیق خواهیم پرداخت.
فصل دوم: به بیان ادبیات و تاریخچه‌ای از داده کاوی، داده کاوی توزیع شده، عاملها و سیستمهای چندعامله پرداخته، چندین تکنیک رایج در این حوزه را ذکر میکنیم و کاربردها و خصوصیات آنها را شرح خواهیم داد.
فصل سوم: به بیان روش تحقیق، نحوه‌ی گردآوری داده‌ها و شیوهی تجزیه و تحلیل اطلاعات خواهیم پرداخت.
فصل چهارم: در این فصل، به بیان یافتههای تحقیق در هر یک از مراحل اجرایی تحقیق خواهیم پرداخت و در نهایت مدلی بر پایه سیستمهای چند عامله به منظور بهبود سرعت و دقت عملیات دادهکاوی در محیطهای توزیع شده ارائه خواهیم داد.
فصل پنجم: در این فصل، به پرسشهای تحقیق پاسخ داده خواهد شد و پیشنهادهایی برای کارهای آینده ارائه می شود.
فصل دوم ادبیات و پیشینه تحقیق
۲-۱- مقدمه
در این فصل، به سه بخش اصلی با عناوین دادهکاوی، عاملها و سیستمهای چند عامله، و کاربرد عاملها در دادهکاوی میپردازیم و در نهایت به بررسی کارهای انجام شده در این حوزه خواهیم پرداخت.
۲-۲- داده کاوی
داده کاوی، یک تکنولوژی نوظهور است، که از ابزارها و تکنیکهای مدلسازی و تجزیه و تحلیل آماری، الگوریتمهای ریاضی، و متدهای یادگیری ماشین برای کشف الگوهای معتبر و ناشناخته در مجموعه داده‌های حجیم استفاده میکند. هرچند این تکنولوژی دوران نوباوگی خود را طی میکند، اما شرکت‌ها و سازمان‌های بسیاری از جمله خرده‌فروشی‌ها، بانک‌ها، مراکز درمانی، کارخانجات تولیدی، ارتباطات راه دور، و مؤسسات دولتی از ابزارها و تکنیکهای دادهکاوی برای تحلیل داده‌هایشان و کشف اطلاعات و دانش مفید از آنها استفاده میکنند.[۱, ۲] دادهکاوی اطلاعاتی را از پایگاه داده‌ها استخراج میکند که از طریق کوئری‌ها و گزارش‌گیری‌ها قابل دست‌یابی نیستند.
رشد انفجاری داده‌های ذخیره شده در پایگاه داده‌ها، نیاز به تکنولوژی‌های جدید که بتوانند حجم عظیم داده‌ها را هوشمندانه به دانش مفید تبدیل کنند، را پدید آورده است.[۳] داده کاوی به معنای یافتن نیمه خودکار الگوهای پنهان در مجموعه داده های[۱] موجود میباشد.[۴] این تکنولوژی با دیگر تکنیکهای تحلیل داده، که سیستم، مقادیر اولیه را میگیرد و خود، الگوهایی را تولید میکند، متفاوت است. دادهکاوی توسط ابزارهای الگوریتمیک، الگوها، تغییرات، آنومالی‌ها، قوانین، و ساختارهای مهم آماری، و رویدادها را از مجموعه داده‌های عظیم استخراج میکند.[۵] میتوان گفت که داده کاوی در جهت کشف اطلاعات پنهان و روابط موجود در بین داده های فعلی و پیش بینی موارد نامعلوم و یا مشاهده نشده عمل می کند. برای انجام عملیات کاوش لازم است قبلاً روی داده های موجود پیش پردازش‌هایی انجام گیرد. عمل پیش پردازش اطلاعات خود از دو بخش کاهش اطلاعات، و خلاصهسازی و کلیسازی داده ها تشکیل شده است. کاهش اطلاعات عبارت است از تولید یک مجموعه کوچک‌تر، از داده های اولیه، که تحت عملیات داده کاوی نتایج تقریباً یکسانی با نتایج داده کاوی روی اطلاعات اولیه به دست دهد.[۴] پس از انجام عمل کاهش اطلاعات و حذف خصایص غیر مرتبط نوبت به خلاصهسازی و کلیسازی داده ها میرسد. داده های موجود در بانک‌های اطلاعاتی معمولاً حاوی اطلاعات در سطوح پایینی هستند، بنابراین خلاصهسازی مجموعه بزرگی از داده ها و ارائه آن به صورت یک مفهوم کلی اهمیت بسیار زیادی دارد. کلیسازی اطلاعات، فرآیندی است که تعداد زیادی از رکوردهای یک بانک اطلاعاتی را به صورت مفهومی در سطح بالاتر ارائه می کند. تکنیکهای داده کاوی به چند دسته تقسیم میشوند که سه دسته اصلی عبارتند از خوشهبندی[۲]، طبقه بندی[۳] و کشف قواعد انجمنی[۴]. در ادامه هر یک از این روشها را به طور کلی معرفی مینماییم.
۲-۲-۱- خوشهبندی
فرایند خوشهبندی سعی دارد که یک مجموعه داده را به چندین خوشه تقسیم نماید بطوریکه داده‌های قرار گرفته در یک خوشه با یکدیگر شبیه بوده و با داده های خوشههای دیگر متفاوت باشند. در حال حاضر روشهای متعددی برای خوشهبندی داده ها وجود دارد که بر اساس نوع داده ها، شکل خوشه ها، فاصله داده ها و غیره عمل خوشهبندی را انجام می دهند. مهم‌ترین روشهای خوشهبندی در زیر معرفی شده اند:
۲-۲-۱-۱- روشهای خوشهبندی مبتنی بر تقسیم‌بندی
این روشها، داده های موجود در یک مجموعه داده را به k خوشه تقسیم می کنند، بطوریکه هر خوشه دو خصوصیت زیر را داراست:
هر خوشه یا گروه حداقل شامل یک داده میباشد.
هر داده موجود در مجموعه داده دقیقاً به یک گروه یا خوشه تعلق دارد.
معیار اصلی در چنین مجموعه دادههایی میزان شباهت داده های قرار گرفته در هر خوشه میباشد. در حالیکه داده‌های قرار گرفته در دو خوشه مختلف از نظر شباهت با یکدیگر فاصله زیادی دارند. مقدار k که به عنوان پارامتر استفاده میگردد، هم می تواند به صورت پویا تعیین گردد و هم اینکه قبل از شروع الگوریتم خوشهبندی مقدار آن مشخص گردد.
۲-۲-۱-۲- روشهای سلسله مراتبی[۵]
روشهای سلسله مراتبی به دو دسته کلی روشهای پایین به بالا[۶] و روشهای بالا به پایین[۷] تقسیم میگردند. روشهای سلسله مراتبی پایین به بالا به این صورت عمل می کنند که در شروع هر کدام از داده ها را در یک خوشه جداگانه قرار میدهد و در طول اجرا سعی می کند تا خوشههایی نزدیک به یکدیگر را با هم ادغام نماید. این عمل ادغام تا زمانی که یا تنها یک خوشه داشته باشیم و یا اینکه شرط خاتمه برقرار گردد، ادامه مییابد. روشهای بالا به پایین دقیقاً به طریق عکس عمل می کنند، به این طریق که ابتدا تمام داده ها را در یک خوشه قرار میدهد و در هر تکرار از الگوریتم، هر خوشه به خوشههای کوچک‌تر شکسته می شود و این کار تا زمانی ادامه مییابد که یا هر کدام از خوشه ها تنها شامل یک داده باشند و یا شرط خاتمه الگوریتم برقرار گردد. شرط خاتمه معمولاً تعداد کلاستر یا خوشه میباشد.
۲-۲-۱-۳- روشهای مبتنی بر چگالی[۸]
اکثر روشهای خوشهبندی که به این روش عمل می کنند معمولاً از تابع فاصله به عنوان تابع معیار خود بهره میبرند. استفاده از چنین معیاری باعث میگردد که الگوریتم خوشهبندی تنها قادر به ایجاد خوشههایی با اشکال منظم باشد. در صورتیکه خوشههای واقعی در داده ها دارای اشکال غیر منظمی باشند، این الگوریتمها در خوشهبندی آنها با مشکل مواجه میگردند. برای حل اینگونه مشکلات یکسری از روشها برای خوشهبندی پیشنهاد گردیدهاند که عمل خوشهبندی را بر مبنای چگالی داده ها انجام می‌دهند. ایده‌ی اصلی در این روشها بر این اساس است که تا زمانی که داده های قرار گرفته در همسایگی خوشه‌ها از حد معینی بیشتر باشند، آنها رشد می کنند و بزرگ میشوند. چنین روش‌هایی قادرند خوشههایی با شکل‌های نامنظم نیز ایجاد نمایند.
البته دسته‌ه ای دیگری از روشهای خوشهبندی مانند روشهای مبتنی بر گرید، روشهای مبتنی بر مدل و غیره وجود دارند که میتوانید آنها را در [۴] مطالعه نمایید.
۲-۲-۲- طبقه بندی
فرایند طبقه بندی در واقع نوعی یادگیری با ناظر میباشد که در طی دو مرحله انجام میگردد. در مرحله اول مجموعه ای از داده ها که در آن هر داده شامل تعدادی خصوصیت دارای مقدار و یک خصوصیت بنام خصوصیت کلاس میباشد، برای ایجاد یک مدل داده بکار میروند که این مدل داده در واقع توصیف کننده مفهوم و خصوصیات آن مجموعه داده ها است. مرحله دوم فرایند طبقه بندی، اعمال یا بکارگیری مدل ایجاد شده، بر روی دادههایی است که شامل تمام خصوصیات دادههایی که برای ایجاد مدل بکار گرفته شده اند، میباشند، بجز خصوصیت کلاس، و هدف از عمل طبقه بندی نیز تخمین مقدار این خصوصیت میباشد.
الگوریتمها و روشهای مختلفی برای طبقه بندی تاکنون پیشنهاد شده اند که برای مثال میتوان از روشهای طبقه بندی با بهره گرفتن از درخت تصمیم، طبقه بندی بیزین، [۹]SVM، طبقه بندی با بهره گرفتن از شبکه‌های عصبی، طبقه بندی مبتنی بر قواعد و غیره نام برد.[۶] در اینجا ما قصد نداریم وارد مباحث مربوط به الگوریتمها و روشهای طبقه بندی شویم و تنها روش طبقه بندی مبتنی بر قواعد را معرفی خواهیم نمود. در صورت نیاز به مطالعه بیشتر میتوانید به مرجع [۴] مراجعه نمایید.
۲-۲-۲-۱- طبقه بندی مبتنی بر قواعد
در این قسمت قصد داریم نگاهی به بحث طبقه بندی مبتنی بر قواعد داشته باشیم. در این روش، مدل ایجاد شده از روی داده ها به صورت مجموعه ای از قواعد میباشد. میتوان گفت که هر قاعده به صورت یک قاعده IF P THEN C میباشد که در آن P مجموعه ای از شرایط بوده و C نیز مشخص کننده برچسب یک کلاس یا طبقه خاص میباشد. یک قاعده بدست آمده از مجموعه داده های آموزشی با بهره گرفتن از دو معیار coverage و accuracy می تواند ارزیابی گردد. این دو معیار به صورت زیر تعریف میگردند:
که در تعاریف مذکور تعداد دادههایی در مجموعه داده D است که توسط قاعده پوشش داده میشوند. تعداد دادههایی است که توسط قاعده به درستی طبقه بندی شده اند. |D| تعداد داده‌های موجود در D میباشد.
نکته مهمی که باید اینجا به آن اشاره کرد این بحث است که چگونه داده ها توسط این قواعد طبقهبندی میگردند. همانطور که اشاره گردید این قواعد دارای یک قسمت شرط (P) و یک قسمت C هستند. P یک الگو به صورت میباشد که هر کدام از piها بیان کننده‌ی یک محدودیت برای یکی از خصوصیات هستند. اگر خصوصیات دادهای محدودیتهای مذکور قاعدهای را برآورده سازد آنگاه کلاس یا طبقهبند آن داده، کلاس یا طبقهای است که آن قاعده بیان می کند©. اما مسأله مهمی که اینجا پیش می آید، این است که اگر یک داده در قسمت شرط (P) بیش از یک قاعده صدق کند، آنگاه کدام قاعده را باید انتخاب کرد. بسته به استراتژی های مختلف، این مشکل جواب‌های مختلفی میتواند داشته باشد. دو نمونه از مهم‌ترین استراتژیهایی که معمولاً برای حل این مشکل بکار میروند، استراتژی‌های مرتب‌سازی بر اساس اندازه[۱۰] و مرتب‌سازی بر اساس قاعده[۱۱] میباشند.
در استراتژی مرتب‌سازی بر اساس اندازه، چنانچه یک داده در بیش از یک قاعده صدق کند، قاعدهای برای طبقه بندی داده انتخاب می شود که خصوصیات بیشتری را برای مشخص نمودن کلاس داده تست کرده باشد. در استراتژی مرتب‌سازی بر اساس قاعده، پیش قواعد اولویت دهی میشوند و هنگام طبقه بندی، قاعده با اولویت بالاتر، مشخص کننده کلاس داده خواهد بود. اولویتدهی به قواعد هم به طرق مختلفی ممکن است انجام گردد. برای مثال ممکن است که ابتدا کلاس‌ها اولویتدهی شوند و قواعد مربوط به هر کلاس نیز با تأثیر پذیری از این اولویتدهی، اولویت بگیرند. اولویت کلاس‌ها نیز ممکن است بر اساس اهمیت کلاس یا تعداد داده های متعلق به آن کلاس و یا غیره مشخص گردند. استراتژی های دیگری نیز در این زمینه وجود دارند که ما در اینجا درباره آنها صحبت نمیکنیم. مسأله دیگری که ممکن است پیش بیاید این است که یک داده با هیچ‌کدام از قواعد هم‌خوانی نداشته باشد. برای این مسأله هم میتوان راهحل‌هایی ارائه نمود. معمولترین راهحل این است که چنانچه دادهای با هیچیک از قواعد هم‌خوانی نداشت، کلاسی به عنوان کلاس آن داده انتخاب گردد که بیشترین تعداد داده در بین داده ها به آن کلاس تعلق دارد.
مورد دیگری هم که اینجا قابل ذکر است این مطلب است که قواعدی که برای طبقه بندی استفاده میشوند، چگونه ایجاد میگردند. البته ما نمیخواهیم در اینجا وارد جزئیات مربوط به استخراج قواعد از داده های آموزشی شویم. برای استخراج قواعد از مجموعه داده های آموزشی معمولاً از دستهای از الگوریتمها بنام الگوریتمهای SCA[12] استفاده میگردد که این الگوریتمها در هر مرحله یک قاعده را از داده های آموزشی یاد گرفته و دادههایی را که از آن قاعده پیروی می کنند را از مجموعه داده های آموزشی خود حذف می کنند و با داده های باقی‌مانده، کار خود را ادامه می‌دهند. از نمونه الگوریتمهای معروف SCA میتوان به AQ، CN2 و RIPPER اشاره نمود. البته قابل ذکر است که برای کشف قواعد میتوان از روشهای ایجاد درخت تصمیم و یا کشف قواعد انجمنی نیز استفاده نمود. در درخت تصمیم هر مسیر از ریشه تا یک برگ را میتوان به عنوان قسمت P قاعده در نظر گرفت و کلاسی که برگ مشخص می کند، قسمت C خواهد بود. در مورد نحوه استفاده از روشهای کشف قواعد انجمنی و استفاده از آنها برای طبقهبندی نیز میتوانید به [۷, ۸] مراجعه کنید.
۲-۲-۳- کشف قواعد انجمنی
سازمان‌های کسب و کار، اغلب حجم عظیمی از داده‌ها را از عملیات روزانه جمع آوری میکنند. به عنوان مثال، حجم عظیمی از داده‌ها از خریدهای روزانه مشتریان در فروشگاه‌های خرده فروشی بدست میآید. استخراج قواعد انجمنی، نوعی از عملیات داده کاوی است که به تجزیه و تحلیل داده و جستجو برای یافتن ارتباط بین ویژگیها از قبیل اینکه مشتریان کدام اقلام را هم‌زمان خریداری میکنند، می‌پردازد. نام دیگر روش کشف قواعد انجمنی، تحلیل سبد بازار میباشد. به عبارت دیگر، قواعد انجمنی، مطالعه ویژگیها یا خصوصیاتی میباشد که با یکدیگر همراه بوده و به دنبال استخراج قواعد از میان این خصوصیات میباشد. این روش به دنبال استخراج قواعد به منظور کمی کردن ارتباط میان دو یا چند خصوصیت است. قواعد انجمنی به شکل اگر و آنگاه به همراه دو معیار پشتیبان[۱۳] و اطمینان[۱۴] تعریف میشوند.
در اینجا به مثال‌هایی از کاربرد قوانین انجمنی اشاره میشود:
بررسی ارتباط بین توانایی خواندن کودکان با خواندن داستان توسط والدین برای آنها.
بررسی اینکه چه اقلامی در یک فروشگاه با یکدیگر خریداری میشوند و اینکه چه اقلامی هیچ‌گاه با یکدیگر خریداری نمی‌شوند.
تعیین سهم نمونه‌ها در بررسی تأثیرات خطرناک یک داروی جدید.
قواعد انجمنی، ماهیتا قواعد احتمالی هستند. به عبارت دیگر قاعده لزوماً قاعده را نتیجه نمی‌دهد، زیرا این قاعده ممکن است از شرط حداقل پشتیبان برخوردار نباشد. به طور مشابه قواعد و لزوماً قاعده را نتیجه نمی‌دهند زیرا قاعده اخیر ممکن است از شرط حداقل اطمینان برخوردار نباشد.[۴]
۲-۲-۳-۱- تعاریف و مفاهیم اصلی در قواعد انجمنی
I = {I1, I2, …, Im} : مجموعه اقلام خریداری شده است.
T: هر زیرمجموعهای از I میباشد که از آن به عنوان تراکنش یاد میشود.
D: مجموعه تراکنش‌های موجود در T است.
TID: شناسه منحصر به فرد و یکتایی است که به هر یک از تراکنش‌ها اختصاص مییابد.
نمای کلی یک قاعده انجمنی به شکل زیر میباشد:
[پشتیبان , اطمینان]
به طوری که داریم:
پشتیبان (X, Y): نشان دهنده‌ی درصد یا تعداد مجموعه تراکنش‌های D است که شامل هر دوی X و Y باشند.
اطمینان: میزان وابستگی یک کالای خاص را به دیگری بیان میکند و مطابق فرمول زیر محاسبه میشود:
| (۲-۳) |
(X) پشتیبان / ( )پشتیبان = (Y X,) اطمینان |
این شاخص درجه‌ی وابستگی بین دو مجموعه X و Y را محاسبه میکند و به عنوان شاخصی برای اندازه‌گیری توان یک قاعده در نظر گرفته میشود. غالباً قاعده‌هایی انتخاب میشوند که عدد اطمینان بزرگی داشته باشند.
فرض کنید اطلاعات مشتریانی که محصول X را خریده‌اند، همچنین علاقه دارند در همان زمان از محصول Y نیز بخرند، در قاعده انجمنی زیر نشان داده شده است:
(پشتیبان = ۲۰% و اطمینان = ۶۰%)
شاخص‌های اطمینان و پشتیبان قواعد بیانگر جذابیت آنها هستند. این دو شاخص به ترتیب مفید بودن و اطمینان از قواعد مکشوفه را نشان می‌دهند. پشتیبان ۲۰% برای قاعده انجمنی فوق به این معنی است که ۲۰% همه‌ی تراکنش‌های موجود نشان می‌دهند که کالای X و Y با هم خریداری شدهاند. اطمینان ۶۰% به این معنی است که۶۰% مشتریانی که کالای X را خریده‌اند، کالای Y را نیز خریداری کردهاند.
اگر مجموعه‌ای از عناصر حداقل پشتیبانی لازم را داشته باشند مکرر[۱۵] خوانده میشوند. قواعد قوی[۱۶]، قواعدی هستند که به طور توأمان دارای مقدار پشتیبان و اطمینان بیش از مقدار آستانه باشند. با بهره گرفتن از این مفاهیم، پیدا کردن قواعد انجمنی در دو گام خلاصه میشود، یعنی پیدا کردن مجموعه‌های مکرر و استخراج قواعد قوی.
۲-۲-۳-۱-۱- تقسیم بندی قواعد انجمنی
بر اساس ارزش عناصر درون قواعد، میتوان قواعد را به انواع دودویی و کمی تقسیم کرد، در مثال زیر، قاعده اولی دودویی و دومی، کمی است.
]۶۰% = confidence ,2% Computer ⇒ Financial management software [sup =
Buys (X, high resolution TV)
بر اساس ابعاد یک قاعده میتوان آن را تک بعدی یا چند بعدی نامید. قاعده زیر، فقط بعد خرید را شامل میشود.
Buys (X, Computer) ⇒ Buys (X, “Financial management software”)
اما قاعده‌ی زیر سه بعدی است، و ابعاد سن، درآمد و خرید را شامل میشود.
(X, high resolution TV) Buys ⇒ ("k48.. k42″ X,) and income ("39..30″ X,) Age
از آنجایی که داده‌ها میتوانند در سطوح[۱۷] و یا مقیاس‌های[۱۸] مختلف تعریف شوند، قواعد را میتوان بر اساس این سطوح خلاصه نمود. مراتب خلاصهسازی و اینکه آیا قواعد در یک سطح هستند یا در چند سطح، میتواند مبنای تقسیم‌بندی باشد.
۲-۲-۳-۱-۲- استخراج قواعد تک‌سطحی تک بعدی دودویی
قبل از ارائه الگوریتمهای استخراج قواعد، نمادها و قراردادهایی را به منظور درک بهتر این الگوریتمها مطرح میکنیم.
اقلام مطابق با قاعده ترتیب حروف الفبا[۱۹] چیده میشوند، به عنوان مثال، اگر باشد، مطابق این قاعده، باید رابطه‌ی برقرار باشد.
در تمامی این الگوریتمها مراحلی که طی میشوند به قرار زیر میباشند:
گام اول: در اولین گذر، پشتیبان هر یک از اجزا محاسبه شده، و اقلام مکرر (با بیشترین میزان فراوانی) با در نظر گرفتن آستانه حداقل پشتیبان انتخاب میشوند. (LK)
گام دوم: در هر گذر، اقلام مکرر که از فاز قبلی، محاسبه شدهاند برای ایجاد اقلام کاندیدا به کار میروند. (CK)
گام سوم: پشتیبان هر یک از CK ها محاسبه شده، و بزرگ‌ترین آنها انتخاب میشود. این کار تا زمانی که هیچ قلم بزرگ‌تری یافت نشود، ادامه مییابد.
در هر فاز پس از یافتن اقلام بزرگ (LK)، میتوان قواعد مطلوب را به صورت زیر استخراج کرد:
برای تمامی اقلام مکرر L همه‌ی زیرمجموعه‌های غیرتهی آن را (s) در نظر می‌گیریم. برای تمامی این زیرمجموعه‌ها، یک قاعده به صورت زیر استخراج میکنیم:
“s ⇒ (L – s)” این قاعده در صورتی برقرار میشود که اطمینان حاصل از آن بزرگ‌تر یا مساوی حداقل اطمینان در نظر گرفته شده توسط کاربر باشد، به بیان دیگر اگر رابطه‌ی زیر برقرار باشد، قاعده‌ی فوق پذیرفته میشود و در غیر این صورت این قاعده لغو میشود.
| (۲-۴) |
حداقل اطمینان ( (s) پشتیبان / (L) پشتیبان) |
پروسه استخراج قواعد انجمنی عبارت است از:
ابتدا همه‌ی اقلام مکرر را که بیشتر یا مساوی با آستانه‌ی پشتیبان هستند بیابید.
برای تمامی اقلام مکرر، همه‌ی زیر مجموعه‌های آنها را استخراج کنید.
همه‌ی قواعد ممکن را استخراج کنید.
قواعدی را بپذیرید که از بیشتر و یا آستانه‌ی اطمینان برخوردار باشند.
در اینجا برای پیدا کردن این قواعد از الگوریتم ساده Apriori یا الگوریتم پیش‌نیاز استفاده میکنیم. فرض کنید که ابتدا باید تمام مجموعه‌های تک عضوی مکرر را پیدا کنید، سپس بر اساس آن مجموعه‌های دو عضوی مکرر را پیدا کنید و الی آخر. در هر مرحله باید کل فضا جستجو شود اما این الگوریتم از خصوصیت Apriori استفاده میکند به این صورت که “اگر مجموعه‌ای از عناصر مکرر باشد، تمام زیرمجموعه‌های غیر تهی آن نیز مکرر خواهند بود".[۲۰]
هر زیر مجموعه‌ی یک مجموعه مکرر، خود نیز مکرر است. این خصوصیت را اینگونه نیز میتوان توصیف کرد: اگر مجموعه I به تعداد مشخصی تکرار شده باشد و اگر ما A را به آن اضافه کنیم تعداد تکرار این مجموعه از مجموعه قبلی بیشتر نخواهد بود. پس اگر اولی مکرر نباشد دومی نیز مکرر نخواهد بود. این الگوریتم از این خصوصیت استفاده میکند و در اینجا عملکرد آن را شرح میدهیم: میدانیم که از یک زیرمجموعه ۱-k عضوی یا همان Lk-1 برای به دست آوردن Lk یعنی مجموعه‌های k عضوی استفاده میشود. این کار در دو مرحله صورت میگیرد، ابتدا باید مجموعه‌ای از اعضا پیدا شود که با ترکیب LK-1 با آنها Lk به دست آید. این مجموعه از عناصر را Ck نامیده و مرحله به دست آوردن آنها را پیوست[۲۱] می‌نامیم. مرحله بعد اضافه کردن این عناصر به مجموعه‌های قبلی است که آن را مرحله هرس[۲۲] می‌نامیم. در زیر این دو مرحله شرح داده میشوند.
۲-۲-۳-۱-۲-۱- مرحله پیوست
ابتدا باید مطمئن شویم که عناصر بر مبنای ترتیب حروف الفبا مرتب شدهاند. دو مجموعه از Lk-1 با یکدیگر قابل پیوست هستند اگر ۲-k عنصر اول آنها با یکدیگر برابر باشند. یعنی: توجه کنید که دو عنصر آخر مرتب شدهاند و از وجود عناصر تکراری جلوگیری میکنند. با اجتماع دو مجموعه قابل پیوست، آن دو مجموعه ترکیب میشوند.
با این روش، مجموعه ترکیب شده حاصل k عضو خواهد داشت که البته عنصر آخر (از نظر ترتیبی) از مجموعه دوم خواهد بود. در مثال زیر دو مجموعه (۴، ۲، ۱) و (۳، ۲، ۱) را در نظر بگیرید: مجموعه اول و دوم مرتب هستند و داریم: ۴>3>2>1 پس میتوان مجموعه ترکیب شده زیر را به دست آورد.
(۳ ۲ ۱) = مجموعه‌ی اول = LK-1
|| ||
(۴ ۳ ۲ ۱) = مجموعه‌ی ترکیب شده = Ck
|| ||
(۴ ۲ ۱) = مجموعه‌ی دوم = LK-1
۲-۲-۳-۱-۲-۲- مرحله هرس
Ck مجموعه‌ای از Lkها است که هر عنصر آن یا مکرر است یا خیر، اما تمام عناصر مکرر در آن قرار دارند. حال تمام عناصر این مجموعه باید بررسی شوند تا مکرر بودن آنها مشخص شود اما چون ممکن است تعداد آنها زیاد باشد لذا برای کاهش حجم محاسبات از اصل Apriori استفاده میشود. به این صورت اگر یکی از زیرمجموعه‌های این مجموعه مکرر نباشد آن مجموعه نیز مکرر نخواهد بود. بنابراین برای پیدا کردن مجموعه‌های مکرر کافی است مجموعه‌های غیر مکرر را از آنها جدا کنیم به این صورت که اگر عضوی از Ck در Lk-1 نباشد مکرر نیز نخواهد بود.
۲-۲-۳-۱-۳- محاسبه اطمینان و استخراج قواعد نهایی
پس از آنکه مجموعه‌های قوی استخراج شدند حال نویت استخراج قواعد است:
برای هر مجموعه مکرر L تمام زیر مجموعه‌های غیرتهی را در نظر می‌گیریم. برای هر زیر مجموعه‌ی s قواعد را به صورت زیر شکل میدهیم. “s ⇒ (L - s)” سپس اطمینان را حساب کرده و اگر بیشتر از حداقل قابل قبول بود آن را می‌پذیریم.
۲-۳- داده کاوی توزیع شده
دادهکاوی توزیع شده عبارت است از کشف نیمه خودکار الگوهای پنهان موجود در داده ها، در حالتی که داده ها و یا مکانیزم‌های استنتاج، به صورت توزیع شده باشند. غیرمتمرکز بودن داده ها بدان معناست که داده‌ها به صورت توزیع شده بین دو یا چند سایت بوده و هزینه انتقال تمام یا بخشی از داده ها به یک سایت مرکزی، قابل صرفنظر نباشد. توزیع شده بودن مکانیزم‌های استنتاج، به معنای لزوم لحاظ کردن هزینه ارتباط بین مکانیزم‌های مختلف در حال استخراج دانش میباشد. این توزیعشدگی ممکن است به دلایل مختلفی از جمله ارائه شدن مکانیزم استخراج دانش در قالب یک سرویس اینترنتی و یا صرفاً ناشی از توزیعشدگی داده ها باشد. چنین رویکردی به داده کاوی، برخلاف جهت کلی تحقیقات انجام شده است که به طور عمده به تکنیکهای متمرکز پرداخته و نه فقط بر تمرکز، که بر همگونی و ساختار مسطح (در مقابل ساختار رابطهای) داده های هدف متکی میباشند. مسائلی نظیر استخراج دانش در حالت عدم دسترسی به تمام داده های موجود، برقراری ارتباط موثر و بهینه با سایر مکانیزم‌های در حال استخراج دانش و نیز تبادل دانش یا اطلاعات میانی به جای اطلاعات خام، فقط تعدادی از مسائل اولیه داده کاوی توزیع شده با توجه به تعریف آن میباشند. بنابراین، داده کاوی توزیع شده در عین حال که به عنوان راه حلی کلیدی برای مشکلات اصلی پیش روی داده کاوی مطرح میباشد، خود سرمنشأ چالش‌ها و مسائل متعددی گردیده است؛ حل مؤثر این مشکلات منجر به استفاده هرچه بیشتر از داده کاوی و ایجاد امکانات جدید و بهره برداری از پتانسیل‌های موجود در قلمروهائی خواهد شد که علیرغم نیاز مبرم به داده کاوی، استفاده بسیار محدودی از آن به عمل میآورند.
بحث داده کاوی توزیع شده به طور کلی از دو جهت قابل بررسی میباشد. اول حالتی که در آن داده ها به صورت همسان بین پایگاه‌های مختلف توزیع شده اند و داده های هر پایگاه تمام خصوصیات را دارا هستند. در این حالت داده ها ممکن است ذاتاً توزیع شده باشند و یا اینکه داده های متمرکز به دلایل امنیتی یا غیره بین پایگاه‌های مختلف تقسیم شده باشند. اصطلاحاً به این حالت ، تقسیم شده به صورت افقی[۲۳] نیز گفته می شود.[۹] حالت دوم حالتی است که در آن داده های موجود در هر پایگاه داده دارای خصوصیت‌های مختلف میباشند. معمولاً در این موارد داده ها خود بین پایگاه‌های مختلف تقسیم گردیدهاند و ذاتاً توزیع شده نیستند. از اینرو به این حالت تقسیم شده عمودی[۲۴] نیز گفته می شود.[۹] برای ایجاد ارتباط بین خصوصیت‌های مختلفی که در پایگاه‌های مختلف نگهداری میشوند اما متعلق به یک داده هستند، معمولاً یک خصوصیت مشترک که به عنوان شناسه مورد استفاده قرار میگیرد، بین تمام پایگاه‌های مختلف نگهداری می شود که رکوردهای مختلف را بهم ارتباط میدهد.
در داده کاوی توزیع شده نیز مسأله کشف و استخراج دانش مشابه داده کاوی عادی در زمینه های خوشهبندی توزیع شده، کشف قواعد وابستگی به صورت توزیع شده و طبقه بندی توزیع شده (که با نام یادگیری توزیع شده طبقهبند هم از آن نام برده می شود) مورد تحقیق و بررسی قرار میگیرد. ضمن اینکه در بحث داده کاوی توزیع شده، مسأله مربوط به محرمانگی داده ها[۲۵] حتماً باید مدنظر قرار گیرد. برای مطالعه بیشتر در مورد داده کاوی توزیع شده میتوانید به مرجع [۹] مراجعه نمایید.
۲-۴- عاملها و سیستمهای چندعامله
از آنجا که در طول این پایان نامه با مفهوم عامل و سیستمهای چندعامله سرو کار خواهیم داشت، لذا به نظر میرسد ضروری است تا ابتدا با مفهوم عامل و سیستمهای چندعامله بیشتر آشنا شویم و برخی از خصوصیات آنها را که در طول پایان نامه استفاده خواهیم کرد، را بیان نماییم.
۲-۴-۱- عامل
با توجه به آنکه از این به بعد به طور گستردهای با عاملها سروکار خواهیم داشت، داشتن تعریفی یکنواخت از عامل در طول گزارش ضروری به نظر میرسد. تعاریف متعددی برای عامل وجود دارد که هیچیک دیگری را نقض نمی‌کنند، بلکه رابطه تعاریف موجود با یکدیگر را میتوان یک رابطه مکمل دانست. به بیان دیگر، تعاریف موجود در مورد عامل، تکمیلکننده یکدیگر میباشند.
یک تعریف مختصر و در عین حال نسبتاً کامل و دربردارنده خصوصیات مورد نظر ما از عامل به شرح زیر میباشد:
یک سیستم (نرمافزار) کامپیوتری که خودکار بوده و دارای قابلیت های اجتماعی، توانائی واکنش و برنامه ریزی برای آینده میباشد.[۱۰]
در تعریف فوق، خودکار بودن به معنای انجام عملیات بدون دخالت مستقیم کاربر (انسان) میباشد. توانائی واکنش، عبارت است از توانائی پاسخ به محیط. بدیهی است که این پاسخ به محیط باید به موقع انجام شود. توانائی برنامه ریزی برای آینده، به معنای داشتن هدف است. هدفدار بودن نه یک مفهوم انتزاعی، بلکه به معنای مشاهده رفتار هدفدار از سوی عامل است. در اینجا قصد نداریم یک بحث طولانی را در مورد نکات بسیار زیادی که در تعریف فوق وجود دارد آغاز کنیم اما چند نکته را به ضرورت بیان میکنیم.
اولین مسئلهای که در تعریف فوق حائز اهمیت فراوان میباشد، مسئله رفتار هوشمند است. همانگونه که مشاهده می شود، اثری از مفهوم هوشمندی در تعریف ارائه شده از عامل وجود ندارد؛ حال آنکه در مطالعات و بررسیهای انجام شده روی عامل، هوشمندی از نکات کلیدی است. سوال مطرح در اینجا آن است که آیا ما قصد داریم بدون در نظر گرفتن هوشمندی به بررسی و استفاده از عامل بپردازیم؟ پاسخ این سوال در تعریف ارائه شده وجود دارد: ترکیب صفات خودکار بودن، قابلیت واکنش و برنامه ریزی برای آینده، می تواند از یک منظر به عنوان وجود هوش تلقی شود. این امر با توجه به این نکته مهم، بیشتر تجلی مییابد که پیادهسازی هیچ یک از سه مورد فوق، به تنهایی، در یک سیستم کامپیوتری، چندان مشکل نیست. در حقیقت سیستمهای کامپیوتری زیادی وجود دارند که خودکار بودن و رفتار صرفاً واکنشی، یا خودکار بودن و رفتار برنامه‌ریزی برای آینده را به صورت هم‌زمان دارا میباشند؛ آنچه که می تواند مسئله را پیچیده ساخته و نمادی از هوش باشد، ترکیب صحیح رفتار واکنشی و برنامه ریزی برای آینده است؛ کاری که حتی برای انسانها نیز چندان ساده نیست. انتخاب نوع رفتار واکنشی و مقطع زمانی صحیح برای واکنش به محیط، ضروری است. از سوی دیگر، برنامه ریزی برای آینده، اقدامی لازم برای پیشرفت و بهبود میباشد. حال یک مسئله مهم، نحوه ترکیب این دو رفتار کلیدی با یکدیگر و دست‌یابی به یک حالت تعادل مناسب است که در آن، عامل ضمن واکنش مناسب به تغییرات محیط، هدف یا اهداف خود را نیز دنبال مینماید. برای پیادهسازی این رفتار هوشمند، راهحلها و معماریهای مختلفی ارائه شده است، اگرچه تمام این راهحلها، چنین تعریفی را از هوشمندی ندارند.
۲-۴-۱-۱- مقایسه عامل با شیء
اشیاء در محیط به صورت مجموعه ای از صفات و قابلیتها در نظر گرفته میشوند. شی بر روی وضعیت داخلی خودش کنترل دارد و میتوان گفت شی نوعی خود مختاری بر روی وضعیت خودش به نمایش می‌گذارد. عاملها در واقع اشیاء فعال هستند، یعنی هر عامل دارای یک موجودیت فعال و دارای رشته کنترلی مختص خود است. به عبارت دیگر عامل مستقل از دیگران و بدون نیاز به کنترل توسط عاملهای دیگر و یا انسان قادر به حیات است. اگر عامل بتواند عملی را انجام دهد و عامل دیگری از این عامل بخواهد که این عمل را برایش انجام دهد، عامل در انجام این عمل خود مختار است. شی بر خلاف عامل بر روی رفتار خودش کنترلی ندارد. یعنی اگر شی متد m را برای فراخوانی در اختیار اشیاء دیگر بگذارد، آنگاه در صورتی که متد از نظر دسترسی عمومی باشد، دیگر شی بر روی اجرای متد کنترلی ندارد. واضح است که متد شیء باید برای اغلب شیء های دیگر در دسترس باشد، زیرا در یک سیستم شیگرا، شیهای تشکیل دهنده سیستم از طریق همکاری با یکدیگر و فراخوانی متدهای یکدیگر باعث انجام اعمال مختلف سیستم میشوند، بنابراین در سیستمهای شیگرا، مرکز تصمیم گیری در ارتباط با انجام یک عمل در شی، فراخوانی کننده متد شی دیگر است، اما در سیستمهای چندعامله این مرکز تصمیم گیری، در عامل دریافت کننده درخواست، برای انجام عمل به خصوص میباشد. همچنین عاملها دارای اشیاء دارای هدف میباشند. در راستای هدف‌گرا بودن عامل، نیاز به خودمختاری نیز اهمیت دارد به طوری که عاملها با توجه به هدف تعریف شده بدون دخالت عاملهای دیگر به انجام اعمال خود میپردازند. ارتباطات بین اشیاء از طریق فراخوانی توابع که به صورت مجموعه‌ای از مسئولیت‌های از پیش تعریف شده هستند صورت میگیرد، در حالیکه در عاملها ارتباطات از طریق زبان‌های ارتباطی است که هیچ مجموعه‌ای از پیام‌ها و یا موجودیت‌های از پیش تعریف شده وجود ندارد.
به طور کلی تفاوت بین اشیاء و عاملها را میتوان به صورت زیر خلاصه کرد:
عاملها نسبت به اشیاء خود مختار هستند. عاملها خودشان نسبت به انجام درخواست عامل دیگر تصمیم میگیرند.
عاملها قابلیت رفتار انعطاف پذیر دارند. در مدل استاندارد شی گرا این قابلیتها در نظر گرفته نمیشود.
عاملها فعال هستند.
ارتباطات بین اشیاء از طریق فراخوانی توابع و ارتباطات در عاملها از طریق زبان‌های ارتباطی است.
عاملها هدف گرا هستند.
جدول ۲- ۱: ویژگیهای یک عامل
| ویژگی |
واژه لاتین |
توصیف ویژگی |
| خودمختاری |
Autonomy |
این بدان معنی است که عامل میتواند بدون دخالت مستقیم انسان یا عاملهای دیگر به فعالیت بپردازد، و بر اقدامات خود و شرایط داخلی کنترل دارد. [۱۱] |
| موقعیت گرا یا واکنشی |
Reactivity or situatedness or sensing and acting |
این بدان معنی است که عامل، ورودی‌های حسی را از محیط دریافت میکند، و فعالیت‌هایی را طرح‌ریزی میکند که محیط خود را از برخی جهات تغییر میدهد. به عبارت دیگر، عامل به محیط خود و شرایط عملیاتی وابسته است، آن را درک میکند و به تغییرات آن پاسخ میدهد.[۱۱, ۱۲] |
| کنش‌گرا یا هدف‌گرا |
Proactiveness or goal directed behaviour |
این بدان معنی است که عاملها در پاسخ به محیط به سادگی عمل نمی‌کنند، بلکه قادرند با ابتکار عملشان، رفتاری هدفمند از خود بروز دهند.[۱۲-۱۴] |
| یادگیری یا سازگاری |
Learning or Adaptivity |
این بدان معنی است که یک عامل، قادر است ۱) در برابر تغییرات محیط، کاملاً انعطاف‌پذیر واکنش نشان دهد، ۲) در زمان مناسب، تصمیمات هدف‌گرا بگیرد، و ۳) در تعامل با دیگران از محیط و تجربیات خود استفاده کند، به عبارت دیگر تغییر رفتارها بر اساس تجربیات قبلی[۱۱, ۱۲] |
| صداقت یا قابل اعتماد بودن |
Veracity or Trustworthiness |
این فرض وجود دارد که یک عامل، آگاهانه، اطلاعات نادرست انتقال نمی‌دهد.[۱۴, ۱۵]. به قوانین روباتیک پایبند است و قابل اعتماد میباشد.[۱۳] |
| تحکیم |
Ruggedization |
عامل قادر است با خطاها و مشکل داده‌های ناقص مقابله کند.[۱۳] |
| پایداری |
Persistency |
عامل دارای اهداف و فرآیندهای ذاتی از پیش تعریف شده میباشد. |
| اجتماعی |
Social ability |
این بدان معنی است که عامل، تعاملاتی دارد، و این تعاملات، با روابط اجتماعی خوشایند یا رفاقت و مساعدت مشخص شدهاند، به همین دلیل می‌گویند عاملها، خوش برخورد، و قابل معاشرت هستند و دوستانه برخورد میکنند،[۱۳] به عبارت دیگر، با سایر عاملها در سیستمهای چندعامله همکاری دارد. |
| هماهنگی |
Coordination |
این بدان معنی است که عامل، قادر است برخی از فعالیت‌ها را در محیط اشتراکی با دیگر عاملها انجام دهد.[۱۳] فعالیت‌ها، اغلب از طریق برنامه‌ها، گردش‌های کاری، و یا دیگر مکانیزم‌های مدیریت فرایندها هماهنگ میشوند.[۱۳] |
| همکاری و مشارکت |
Cooperation or collaboration |
این بدان معنی است که عامل، قادر است به منظور رسیدن به یک هدف مشترک، با دیگر عاملها هماهنگ شود، عاملهای غیر رقابتی که با هم به موفقیت یا شکست می‌رسند.[۱۳] |
| انعطاف‌پذیری |
Flexibility |
این بدان معنی است که سیستم پاسخگو است، عاملها باید محیط خود را درک کنند و به موقع، به تغییراتی که در آن رخ میدهد پاسخ دهند.[۱۶] |
| استدلال |
Reasoning or Discourse |
قابلیت استدلال در انتخاب عمل |
| حرکت |
Mobility |
این بدان معنی است که عامل، قادر است از یک ماشین به ماشین دیگر، و در سراسر معماری سیستم‌ها و چارچوب‌های مختلف انتقال یابد، به عبارت دیگر قابلیت انتقال از یک محیط به محیطی دیگر[۱۷] |
| پیوستگی زمانی |
Temporal continuity |
این بدان معنی است که عامل، فرایندی است که به طور مداوم در حال اجرا است، و اینگونه نیست که یک ورودی را به یک خروجی واحد نگاشت کند و پس از آن خاتمه یابد.[۱۷] |
| شخصیت یا اعتبار |
Personality or character or Credibility |
یک عامل، شخصیت قابل باور، خوش تعریف و احساسات دارد.[۱۳, ۱۷] |
| قابلیت استفاده مجدد |
Reusability |
این بدان معنی است که ممکن است فرایندها نیاز داشته باشند نمونه‌های کلاس “عامل” را برای تحویل اطلاعات یا چک کردن و تجزیه و تحلیل آنها بر اساس نتایجشان حفظ کنند.[۱۸] |
| محدودیت منابع |
Resource limitation |
عامل تا زمانی به فعالیت خود ادامه میدهد که منابع را در اختیار داشته باشد.[۱۸] |
| نوع دوستی |
Benevolence |
این فرض وجود دارد که عاملها، اهداف متضاد ندارند و هر عامل کاری را انجام میدهد که از او خواسته شده است.[۱۴, ۱۵] به عبارت دیگر، مصالحه در منافع مرتبط با عاملهای همکار |
| نمایندگی |
Delegacy |
قبول انجام عمل در سیستمهای چندعامله |
| شایستگی یا احساس مسئولیت |
Competency or Amenability |
ارزیابی فعالیت انجام شده در تحقق هدف، تقسیم وظایف در صورت لزوم، و ادامه عمل تا تحقق هدف |
| عقلانیت |
Rationality |
این بدان معنی است که یک عامل در راستای اهداف خود فعالیت میکند، و کاری که مانع رسیدن به آن اهداف شود را انجام نمی‌دهد، حداقل تا جایی که باورهای او اجازه میدهد.[۱۴, ۱۵] به عبارت دیگر، انجام اعمال منطقی (نه لزوماً درست) برای رسیدن به اهداف |
| قابلیت استنتاج |
Inferential capability |
این ویژگی بدان معنی است که یک عامل، میتواند با بهره گرفتن از دانشی که از اهداف کلی دارد، و روشهای ارجح، بر روی مشخصات کار، به فعالیت بپردازد تا به انعطاف‌پذیری دست یابد، اطلاعات بیشتری بدست آورد، و مدل‌های واضح و صریحی از خود، کاربر، شرایط، و یا دیگر عاملها داشته باشد.[۱۹] |
| پاسخگویی |
accountability |
عامل باید وقایع و فعالیتهای خود را ثبت کند تا در صورت نیاز ارائه دهد. [۱۳] |
| غیرقابل پیشبینی بودن |
Unpredictability |
عامل قادر است به نحوی عمل کند که به طور کامل قابل پیشبینی نباشد، حتی اگر تمام شرایط اولیه شناخته شده باشند.[۱۳] |
۲-۴-۱-۲- معماری عاملها
معماری عاملها یک متدولوژی خاص برای ساخت عاملها فرض می شود، بطوریکه معماری بیانگر چگونگی تقسیم عاملها به پیمانه‌های مختلف و ارتباط بین آنها میباشد. معماری در برگیرنده تکنیک‌ها و الگوریتمهایی است که این متدولوژی را پشتیبانی می کنند. معماریهای مختلفی برای ساخت عاملها پیشنهاد شده است. میدانیم در بررسی عاملها از مواردی که دارای اهمیت است بحث تکنیک مورد استفاده در آنها میباشد که مسائلی نظیر اخذ دانش، اکتساب دانش و بازنمایی دانش را در بر میگیرد. انتخاب و طراحی معماری مناسب برای عامل به پارامترهای مختلفی وابسته است. حوزه کاربردی، محیطی که عامل در آن عمل می کند، اطلاعات در اختیار عامل، نیازها و ویژگیهای مورد انتظار از عامل، میزان انعطاف پذیری، تکنولوژی مورد استفاده، برای پیاده سازی از جمله مهم‌ترین این پارامترها هستند. معماری عامل به مکانیزمی برای برنامه ریزی و اجرا، به شکل هم‌زمان هم نیاز خواهد داشت. بدون چنین مکانیزمی عامل یا در حالت برنامه‌ریزی گرفتار خواهد شد و نمیتواند به موقع به رویدادها پاسخ دهد و یا با تمرکز بسیار زیاد بر روی پاسخگویی به رویدادهای محیط نمیتواند رفتار هدفمند از خود نشان دهد. در چنین محیط‌هایی عامل باید امکان تطبیق دادن رفتار خودش با محیط را نیز داشته باشد. بدون چنین امکانی عامل توانایی انجام درست وظایفش را به تدریج از دست خواهد داد. در محیطهای پویایی که عاملها باید رفتار خود را با عاملهای دیگر هماهنگ کنند، داشتن مکانیزم هماهنگ سازی با حداقل ارتباط یکی دیگر از نیازهای معماری عامل است.
به طور کلی چهار نوع معماری برای چهار گروه از عاملها مطرح شده است:
عاملهای منطقی/ نمادین: عامل‌هایی که تصمیم گیری‌های آنها بر مبنای استنتاج منطقی است.
عاملهای واکنشی: عامل‌هایی که در آنها فرایند تصمیم گیری به صورت تابع نگاشتی از وضعیت به عمل است.
عاملهای BDI[26] : عامل‌هایی که در آنها تصمیم گیری بر مبنای کار بر روی ساختار دادههایی است که بیانگر باورها و تمایلات و قصدهای عامل است.
عاملهای ترکیبی و چند لایه: عامل‌هایی که تصمیم گیری در آنها از طریق لایه های نرمافزاری مختلف صورت میگیرد که هر لایه کما بیش استدلال‌هایی درباره محیط خود در سطوح مختلف انتزاع دارد.
در اینجا ما تنها معماری BDI را معرفی مینماییم. برای مطالعه بقیه موارد میتوانید به [۱۰] مراجعه نمایید.
۲-۴-۱-۲-۱- معماری BDI
در معماری BDI رسیدن به هدف و انجام عمل از طرف عامل بر اساس نحوه تصمیم گیری انسانها درباره مسائل مختلف زندگی است که هر روزه انجام می دهند.[۲۰, ۲۱] انسانها در هر موقعیتی بر اساس باورهایی که از موقعیت خود و دنیای بیرون دارند، به بررسی انتخاب‌های ممکن (تمایلات) میپردازند و در نهایت یکی از گزینه های ممکن انتخاب می شود تا رسیدن به آن هدف حاصل آید. به عبارت دیگر در این معماری رسیدن به هدف با توجه به مفهوم “استدلال عملی” صورت میگیرد. از دیدگاه فلسفی، استدلال عملی مستلزم دو فعالیت مهم تصمیم گیری در مورد اهداف مورد نظر و چگونگی رسیدن به این اهداف میباشد. بحث اول تحت عنوان بررسی و قیاس و بحث دوم نتیجه گیری بر مبنای تحلیل استدلال عملی مطرح است.
یک عامل می تواند تصمیم گیری کند که چه کاری را انجام دهد و چگونه به این کار برسد. در این راستا عامل سعی میکند انتخاب‌های مختلف را درک کند و سپس یکی از آنها را انتخاب می کند. مسأله اصلی در استدلال عملی دست‌یابی به قصدهای صحیح با توجه به تغییرات محیط است. ممکن است قصد در زمان‌های مختلف تغییر کند و لذا نیاز به تجدید نظر نمودن قصد خواهد بود. تجدید نظر خود با هزینههایی همراه است. با توجه به موضوع عنوان شده، برای عاملهای BDI تابعی تحت عنوان تابع تبادل نظر در نظر گرفته می شود که به دو جزء تقسیم میگردد. بخش اول ایجاد کننده انتخاب‌ها و بخش دوم فیلتر کردن انتخاب‌ها. بخش ایجاد کننده انتخاب‌ها به گونه‌ای است که هر عامل مجموعه ای از پیشنهادهای مختلف را تولید می کند. این کار از طریق تابعی بنام Option که باورهای جاری عامل و قصدهای جاری آن‌را میگیرد، صورت میپذیرد و بر این اساس مجموعه انتخاب‌ها (تمایلات) تعیین می شود. در بخش فیلتر کردن، عامل بین حالت‌ها و پیشنهادهای مختلف، انتخاب انجام داده و برای رسیدن به آنها به توافق میرسد. به عبارتی از تابعی که فیلتر نامیده می شود برای انتخاب حالت‌های مختلف استفاده مینماید. در ادامه نیاز به بازنمایی اهداف/ قصد برای رسیدن به آنها و نیز اعمالی که می تواند انجام بدهد و بازنمایی محیط خواهد داشت. بطوریکه برای رسیدن به هدف برنامه ریزی نموده، و این کار به صورت برنامهسازی اتوماتیک صورت میپذیرد. همانگونه که قبلاً نیز مطرح شد، معماری BDI بر مبنای استدلال عملی است. در این معماری، تصمیم گیری بر اساس ساختارهای دادهای است که باورها، تمایلات و قصد عامل را بیان می کنند. باورها بیانگر اطلاعات عامل در مورد وضعیتهای جاری بوده، و تمایلات مجموعه ای است که کانون فعالیت عامل را بیان کرده، بطوریکه همان اهداف ممکن است. انتخاب اهداف نیز همان قصد است. فرایند استدلال عملی در عامل BDI در شکل (۲-۱) به صورت تصویری و صوری آورده شده است. با توجه به این شکل، یک معماری BDI شامل هفت جزء میباشد:
یک تابع بازنگری باورها (brf) که به عنوان ورودی درک عامل را با نگاشت بر روی محیط دریافت نموده و باورهای جاری را به هنگام میسازد.
پایگاه دانش باورهای جاری، که اطلاعات عامل را در محیط جاریاش بیان می کند.
تابع تولید گزینه های انتخاب (Option) که ورودی آن، باورها و قصد عامل بوده و بر اساس آنها انتخاب‌های ممکن برای عامل را که در واقع همان تمایلات وی است، تعیین می کند. توصیف صوری این تابع به صورت زیر است:
مجموعه ای از گزینه های معتبر، که مبین اعمالی است که عامل می تواند انجام دهد.
Filter: یک تابع فیلتر که ورودی آن، عقاید، باورها و قصدهای عامل بوده و خروجی آن بر اساس فرایند تبادل نظر (قیاس) اهداف (قصد) جدید عامل است:
مجموعه ای از قصدهای، جاری که کانون فعالیت عامل را تعیین می کند.
Execute : تابع انتخاب عمل بر پایه قصد و اهداف فعلی که عملی را که باید انجام شود، تعیین میکند:
۲-۴-۲- سیستمهای چندعامله
سیستمهای چندعامله، زیر حوزهای در حال رشد از هوش مصنوعی است که هدفش فراهم ساختن اصول ساخت سیستمهای پیچیدهای است که شامل چند عامل و ساز و کارهایی برای هماهنگ سازی رفتارهای این عاملها میباشد. چگونگی هماهنگ سازی دانش، اهداف، مهارت‌ها و برنامه ریزیهای عاملها برای حل مسائل در این مقوله میگنجد. عاملها در محیط ممکن است در راستای هدفی خاص و مشترک و یا در راستای اهداف خاص و جداگانه ای که در تعامل با یکدیگر میباشند، کار کنند. بحث هماهنگی در سیستمهای چندعامله از مباحث اساسی بوده و بدون آن مزایای تعامل و رفتارهای اجتماعی عاملها محو میگردد. از دیدگاه هوش مصنوعی توزیع شده، سیستم چندعامله، اجتماعی از عاملهای مستقل برای حل مسأله است که هر عامل کلیه خصوصیات مطرح شده را داراست. سیستمهای چندعامله دارای مشخصات زیر هستند[۲۲] :
دانش کافی و لازم برای حل یک مسأله در یک عامل وجود ندارد.
کنترل سیستم توزیع شده است. (یک سیستم کنترل کلی وجود ندارد.)
داده‌ها غیر متمرکز میباشند.
محاسبات به صورت غیر هم‌زمان صورت میگیرند.
شکل ۲- ۱: معماری BDI در عامل
سیستمهای چندعامله راهحل‌هایی را برای مسائل توزیعشده در محیطهای محاسباتی باز و پویا فراهم میآورند. راه حل چنین مسائلی می تواند بر مبنای چندین عامل که توزیعشدگی مسأله، وجود چندین نقطه کنترل، چندین دیدگاه یا علائق در حالت رقابت را پوشش دهند، ارائه گردد. علاوه بر این، عاملها برای رسیدن به اهداف خود نیاز به تعامل با یکدیگر خواهند داشت. این تعاملات که در سطح دانش صورت میپذیرد، می تواند یک تبادل عقاید ساده، تمایلات، یا قصدها برای درخواست انجام عمل باشد که لازم است از طریق هماهنگی، همکاری و یا مذاکره برای مدیریت اعمال وابسته بهم صورت گیرد[۲۳]. این تعامل با تعامل در سایر سیستمهای محاسباتی دو تفاوت عمده دارد: اول آنکه تعامل میان عاملها در سطح دانش صورت میگیرد [۲۳, ۲۴]. یعنی این تعاملات بر حسب اینکه چه هدفی باید در چه زمانی، توسط چه افرادی دنبال شود بیان میشوند و دوم اینکه چون عاملها موجودیت‌هایی انعطاف پذیر هستند که در محیطی که تنها بر روی بخشی از آن کنترل دارند عمل می کنند، تعاملات بین آنها نیز باید انعطافپذیرتر باشد. لذا عاملها باید بتوانند درباره محدوده تعاملات خود در زمان اجرا تصمیم گیری داشته و تعاملاتی را که در زمان طراحی نیز دیده نشدهاند، آغاز کنند و یا به آنها پاسخ دهند. تعامل اجتماعی در عاملها بدین معنی است که روابط موجود میان عاملها در حال تکامل میباشد و روابط جدیدی ایجاد میگردد. بدین منظور لازم است تا قوانینی به منظور شکل دهی به روابط سازمانی و مکانیزم‌هایی به منظور تضمین انسجام گروهی و ساختارهایی برای مشخص کردن رفتار کلان مجموعهها در نظر گرفته شود. به عبارتی عاملها، تعاملات سطح بالا و روابط سازمانی، مفاهیم اساسی در سیستمهای چندعامله را به وجود میآورند. یک سیستم چندعامله، از اجزای زیر تشکیل شده است:
یک محیط که در بر گیرنده اجزاء تأثیرگذار در سیستم چندعامله میباشد. اما لزوماً تمام عوامل تأثیرگذار در حالت سیستم چندعامله، درون آن قرار ندارند.
تعدادی عامل. به طور معمول هیچگونه پیشفرضی در مورد نوع، معماری و تعداد عاملها در یک سیستم چندعامله وجود ندارد. از این جهت میتوان یک سیستم چندعامله را به یک جامعه انسانی تشبیه نمود.
مجموعه ای از اشیاء درون محیط. هیچ پیشفرض اولیهای در مورد این اشیاء نیز وجود ندارد.
مجموعه ای از روابط. این روابط، که میتوان آنها را به قوانین نیز تعبیر نمود، ارتباطات میان اشیاء با اشیاء دیگر و نیز ارتباطات بین عاملها با اشیاء را مشخص مینمایند.
مجموعه عملیات قابل انجام توسط عاملها. این مجموعه شامل دو دسته کلی از عملیات میباشد. عملیات حس (دریافت اطلاعات) از محیط و عملیات تأثیرگذار بر محیط.
البته به طور رسمی و دقیق سیستم چندعامله به صورت یک چهارتایی است که در آن Ag = {Ag1, Ag2, …, Agn} مجموعه عاملهای تشکیل دهنده سیستم چندعامله میباشد. Env محیطی است که سیستم چندعامله در آن عمل می کند. Org سازمان سیستم چندعامله و D قلمروی آن سیستم چندعامله است.
در ادامه، ما مذاکره که یکی از مباحث مهم موجود در بحث سیستمهای چندعامله است را معرفی خواهیم نمود. برای مطالعه بیشتر در مورد سیستمهای چندعامله میتوانید به [۱۰] مراجعه کنید.
۲-۴-۲-۱- مذاکره
بیان شد که هماهنگی، صفت سیستمی از عاملها میباشد که هر کدام فعالیتی را در محیطی مشترک انجام می دهند. همکاری، هماهنگی میان عاملهای غیر خودخواه است در حالیکه مذاکره، هماهنگی میان عاملهای رقابتی یا منفعت طلب میباشد.
مذاکره نوعی تعامل است که میان عامل‌هایی با اهداف یا مقاصد متفاوت صورت میگیرد. مذاکره راهحلی برای بعضی از مسائل مطرح در هوش مصنوعی توزیع شده مانند تجزیه و تخصیص مسئله، یکپارچگی و حل تضاد میباشد. اهمیت و استفاده از سیستمهای خودکار شده در حال افزایش است. یک دلیل برای این اهمیت ایجاد و رشد زیرساختار ارتباطی و محیطهای ساخت و تولید استاندارد شده – اینترنت، وب، KQML، FIPA، محیطهای ساخت سیستمهای مبتنی بر عامل و زبان‌های برنامهنویسی- میباشد. دلیل دوم، نیاز به استفاده از مذاکره خودکار شده، در ایجاد برنامه های کاربردی که در سطح تصمیم گیری عمل می کنند، میباشد. به عنوان مثال میتوان به سیستمهای تجارت الکترونیکی برای خرید و فروش کالاها، اطلاعات و پهنای باند ارتباطی بر روی اینترنت، سازمان‌های مجازی، مدیریت شبکه های مخابراتی، سیستمهای مبتنی بر وب و مدیریت فرآیندهای سازمانی اشاره نمود. تکنولوژی عامل، مذاکره در سطح تصمیم گیری عملیاتی را در این کاربردها تسهیل می کند. مذاکره خودکار شده در این کاربردها میتواند باعث صرفهجویی در زمان مذاکره کنندگان انسانی شود. علاوه بر این چون عاملهای محاسباتی در موقعیت‌های استراتژیک و پیچیده در یافتن قراردادهای کوتاه مدت از مذاکره کنندگان انسانی کاراتر هستند، میتوان به مزایای دیگری نیز دست یافت. محققین حوزه سیستمهای چندعامله، مذاکره را راهی برای به اشتراک گذاشتن کارهای لازم برای انجام یک طرح مشترک یا مکانیزمی برای برطرف نمودن تضادهای پیش آمده بین عاملها میدانند. بسیاری از تکنیک‌هایی که برای هماهنگی استفاده میشوند، شامل نوعی مذاکره هستند. Bussman و Muller تعریفی ابتدایی از مذاکره را به شکل زیر ارائه می دهند [۲۵] :
“… مذاکره فرایند ارتباطی گروهی از عاملها به منظور رسیدن به اتفاق نظر بر روی موضوعی خاص میباشد …".
اگر عاملها بخواهند به شکلی موثر مذاکره کنند، باید درباره باورها، تمایلات و قصدهای سایر عاملها استدلال نمایند و این مسأله باعث به وجود آمدن تکنیک‌هایی برای نمایش و نگهداری مدل‌هایی از باورها، استدلال درباره عقاید سایر عاملها و تأثیرگذاری بر روی مقاصد و باورهای سایر عاملها شده است. اجازه دهید تا فرایند مذاکره را از یک دیدگاه رسمی تعریف نماییم [۲۶]. هر فرایند مذاکره شامل چهار مؤلفه اصلی میباشد:
مجموعه مذاکره: فضای نمونه‌ای که پیشنهادات ممکن عاملها را در بر میگیرد.
پروتکل مذاکره: مجموعه پیشنهادات قانونی را که یک عامل در یک مرحله از مذاکره میتواند ارائه دهد را تعریف میکند.
مجموعه استراتژیها: در یک مذاکره ممکن است دو یا چندین عامل شرکت داشته باشند که هر یک دارای استراتژی خاص خود بوده و این استراتژی هر عامل است که مشخص میکند آن عامل چه پیشنهاداتی را ارائه خواهد کرد. مسلماً استراتژی یک عامل شرکت کننده در یک مذاکره از دید بقیه عاملهای موجود در مذاکره پنهان خواهد بود.
یک قاعده یا قانون که مشخص میکند، چه هنگام توافق بین مذاکره کنندگان حاصل گردیده است.
پیشنهادهایی که در فضای نمونه ای که توسط مجموعه مذاکره مشخص میگردد، وجود دارند همگی شامل دو شرط مهم هستند. شرط اول این است که هیچ‌کدام از پیشنهادات به گونه‌ای نباشد که قبول آن برای عامل مقابل بدتر از حالت Conflict deal باشد. حالت Conflict deal حالتی است که در آن عامل پیشنهادات را قبول نکرده و خود تنها کار می کند. شرط مهم دیگری که باید وجود داشته باشد، شرط pareto optimal بودن پیشنهادات است به این معنی که پیشنهادات به گونه‌ای باشند که هیچیک از عاملهای درگیر در مذاکره نتوانند سودمندی بیشتری داشته باشد، مگر اینکه عامل دیگری در قبال این سود بیشتر متحمل ضرر گردد.
پروتکل مذاکره مشخص کننده تعداد تکرارهای مذاکره، نحوه شروع مذاکره، قوانین لازم برای انجام مذاکره و مواردی از این قبیل خواهد بود.
استراتژی یک عامل در مذاکره باید پاسخ سوالات زیر را مشخص کند:
اولین پیشنهاد چگونه باید باشد؟
چه هنگام باید در مورد کاهش یا افزایش سودمندی پیشنهادی انعطاف به خرج داد؟
اگر تصمیم به کاهش یا افزایش سودمندی گرفته شد، مقدار این کاهش یا افزایش چقدر باید باشد؟
پس از معرفی عامل و سیستمهای چندعامله در این بخش، حال قصد داریم تا مبحث بهرهگیری از عامل برای داده کاوی را مطرح نماییم. بخش آتی به بررسی این موضوع می پردازد.
۲-۵- بهره گیری از عامل برای داده کاوی
در این قسمت قصد داریم تا دلایل استفاده از عامل و سیستمهای چندعامله را برای عمل داده کاوی بیان نماییم. سیستمهای چندعامله را میتوان به عنوان یکی از انواع سیستمهای باز در نظر گرفت که امکان همکاری یا رقابت تحت قواعد محیطی مشخص را برای دست‌یابی به هدف مشترک یا هدف خاص هر عامل فراهم میسازند. هر عامل، بدون توجه به معماری آن، می تواند در محیط فعالیت کرده و سود خود یا محیط (که می تواند به هر صورتی تعریف شود) را به حداکثر برساند. سیستمهای چندعامله به صورت ذاتی با یک محیط داده کاوی توزیع شده تطبیق دارند و همین امر موجب گستردگی کاربرد آنها در این قلمرو شده است.
۲-۵-۱- سیستمهای چندعامله، بستری برای داده کاوی توزیع شده
چرا تعاملات و یکپارچه کردن عاملها و دادهکاوی (به طور مخفف، کاوش عامل[۲۷-۳۰]) اهمیت دارد؟ برای درک بهتر این بحث، در اینجا، موارد شباهت سیستمهای چندعامله و داده کاوی توزیع شده را مطرح کرده و به توضیح هر یک میپردازیم.
توزیعشدگی منابع اطلاعاتی
با توجه به عدم امکان تجمیع داده ها جهت اجرای فرایند داده کاوی، میتوان منابع اطلاعاتی یا همان پایگاه داده ها را به دو صورت در نظر گرفت. یک راه آن است که هر منبع اطلاعاتی را به صورت یک شیء در نظر بگیریم. چنین رویکردی می تواند اجازه بهره برداری از منبع اطلاعاتی را به عاملهای موجود بدهد. اما هیچگونه خاصیت خود آغازی و یا خواص دیگری از عامل را به منبع اطلاعاتی نخواهد داد. راه دوم، در نظر گرفتن یک عامل مسئول به ازای هر منبع اطلاعاتی است. چنین عاملی می تواند ضمن بر عهده داشتن نقشهای متداول یک سیستم مدیریت بانک اطلاعاتی رابطهای، وظایفی نظیر اعلام موجودیت (مثلاً به یک دایرکتوری مرکزی یا به صورت آگهی در منابع خاص)، انجام پیش‌پردازشهای لازم و اعلام توانائیها و سرفصلهای منبع اطلاعاتی ذی‌ربط را بر عهده بگیرد. چنین عاملی می تواند در صورت لزوم، آمادگی خود را برای انجام یک وظیفه خاص که توسط یک عامل دیگر (کارفرما) تعریف می شود اعلام نموده و در صورت توافق، پس از اجرای وظیفه و ارائه نتایج، هزینه های مربوطه را از عامل کارفرما دریافت دارد. در مجموع، ارائه هر منبع اطلاعاتی به صورت یک عامل، ضمن آنکه با توجه به منفعتگرا بودن عامل مربوطه، منجر به افزایش احتمال کشف وجود آن منبع اطلاعاتی توسط عاملهای دیگر می شود، می تواند بسیاری از وظایف مفید دیگر را نیز بر عهده عامل مربوطه قرار داده و منجر به افزایش منفعت برای آن (از طریق انجام فعالیتهای مورد درخواست سایر عاملها و ارائه نتایج) شود.
توزیعشدگی و تنوع روشها و سیستمهای داده کاوی
رویکردها و روشهای بسیار متنوعی در داده کاوی وجود داشته و هر روشی برای کاربرد خاصی مناسب بوده و نوع مشخصی از دانش را از اطلاعات استخراج مینماید. این تعدد و تکثر روشها، اگرچه منجر به کاربرد بیشتر داده کاوی در مسائل عملی گردیده، اما از سوی دیگر، موجب مشکلی به نام انتخاب روش یا سیستم داده کاوی مناسب یک کاربرد یا مسئله خاص، برای کاربران و سازمانها گردیده است. سیستمهای داده کاوی تجاری، به پیادهسازی روشهای معمول داده کاوی میپردازند؛ حال آنکه الگوریتمهای مجزا، معمولاً آخرین دستاوردها در زمینه داده کاوی را به نمایش میگذارند. به کارگیری یک ابزار یا الگوریتم داده کاوی نیز خود می تواند یک مسئله نه چندان ساده باشد. یک راه برای غلبه بر چنین مشکلی، توسعه عاملهائی است که در داده کاوی تخصص دارند. این تخصص می تواند از دو بعد مطرح باشد، از جنبه روش داده کاوی و از جنبه کاربرد. به عنوان مثال میتوان عاملهای متخصصی داشت که در کشف موارد نامتعارف موجود در منابع اطلاعاتی که با الگوهای عادی آنها سازگار نیست (نظیر سوء استفاده از کارتهای اعتباری و یا ادعاهای غیرواقعی خسارت توسط بیمهشدگان) مهارت دارند. چنین تخصصی می تواند مورد استفاده بسیاری از سازمانها قرار گیرد. با در اختیار داشتن عاملهای نماینده منابع اطلاعاتی مختلف، میتوان عامل متخصصی داشت که ضمن فاش نکردن منابع اطلاعاتی دیگر، خود بتواند به عنوان مثال، احتمال واهی بودن یک ادعای خسارت را مشخص نماید.
در نظر گرفتن عاملهای داده کاوی متخصص در یک کاربرد خاص نیز چشمانداز امیدبخشی دارد. میتوان عاملهائی را در نظر گرفت که در تشخیص نوع خاصی از یک بیماری مهارت دارند. این عاملها ممکن است به نوبه خود، بخشی از وظایف را از طریق مکانیزم های پیمانکار-کارفرما، به عاملهای متخصص در یک فرایند داده کاوی خاص واگذار نموده و دقت پیش بینیهای خود را به صورت قابل ملاحظهای افزایش دهند. در نظر گرفتن عاملهای متخصص داده کاوی، نه تنها منجر به مزایائی که ذکر گردید می شود، بلکه راه را برای فعالیتهای پیچیدهتر و مفیدتر نیز باز می کند.
بکارگیری مکانیزم های مناسب برای حل مسائل پیچیده
فرایند حل مسئله، از دیگر مواردی است که می تواند در چارچوب پیشنهادی مورد بررسی قرار بگیرد. مکانیزم های متعددی برای حل مسئله از طریق همکاری عاملها، در سیستمهای چندعامله وجود دارد. از آن جمله میتوان مکانیزم تختهسیاه را نام برد. توضیح تفصیلی این مکانیزم ها، خارج از محدوده این گزارش است؛ صرفاً به عنوان یک مثال، مکانیزم تختهسیاه را مورد بررسی اجمالی قرار میدهیم. در روش تختهسیاه، یک عامل وظیفه نظارت را بر عهده داشته و سایر عاملها که نماینده متخصصین هستند، برای حل مسئله با یکدیگر همکاری می کنند. هر عامل (متخصص)، در صورتی که بر اساس محتوای تخته سیاه تشخیص دهد که می تواند به پیشرفت راهحل مسئله کمک کند، این اقدام را از طریق افزودن مطالبی به راهحل موجود (تخته سیاه) انجام میدهد. ناظر، وظیفه دادن نوبت به عاملها برای افزودن به راهحل موجود یا کاستن از آن را بر عهده دارد. این فرایند تا حل کامل مسئله مورد نظر ادامه خواهد یافت.
داده کاوی توزیعی به عنوان یک اتحاد موقت و مسئله مذاکره
همانگونه که در بخش‌های قبل نیز بیان شد، یکی از دلائل رشد و توسعه داده کاوی توزیع شده، وجود رقابت بین سازمان‌های مرتبط و عدم تمایل آنها به اشتراک گذاری اطلاعات خام میباشد. میتوان مکانیزمهائی را در نظر گرفت (نظیر مکانیزم مزایده) که بتوانند بستر مناسب برای این نوع از داده کاوی را فراهم نمایند. مکانیزم باید به هر عامل (نماینده سازمان ذی‌ربط) امکان برآورد منافع و خطرات موجود در شرکت در فرایند داده کاوی مشترک را ارائه نماید. همچنین نحوه مبادله اطلاعات و مذاکره در مورد اطلاعات قابل مبادله نیز می تواند موضوعی برای تحقیق باشد.
۲-۶- مروری بر کارهای انجام شده
در این بخش قصد داریم کارهای انجام شده در زمینه‌ی داده کاوی توزیع شده، و استفاده از عامل برای داده کاوی را بررسی نماییم. قبل از بیان این موارد ابتدا لازم است تا با ارائه یک ساختار درختی جایگاه کارهای مورد بررسی در حوزه داده کاوی را به صورت کلی نشان دهیم (شکل ۲-۲). تقریباً اکثر کارهایی که در بخش داده کاوی توزیع شده و نیز کاربرد عامل برای داده کاوی انجام شده و در این گزارش مورد بررسی قرار گرفتهاند، شامل کارهایی هستند که در درخت شکل ۲-۲ در نود شماره ۱.۱.۲.۲ و نودهای فرزند آن قرار میگیرند.
از آنجا که بیشتر کارهای انجام شده در زمینه استفاده از عامل برای داده کاوی در زمینه داده کاوی توزیع شده بوده است، لذا اجازه دهید تا ابتدا بحث داده کاوی توزیع شده را به همراه برخی از مهم‌ترین کارهای انجام شده مورد بررسی قرار دهیم و سپس به بحث استفاده از عاملها در این زمینه بپردازیم.
۱
۱.۲
۱.۱
Data Mining
Static
Dynamic
(Active)
۱.۱.۲
۱.۱.۱
Central
Vertically partitioned
Horizontally partitioned
Data Integration
Distributed
۱.۱.۲.۱
۱.۱.۲.۲
۱.۱.۲.۲.۲
۱.۱.۲.۲.۱
Model Integration
شکل ۲- ۲: درخت تحقیق مبحث دادهکاوی
۲-۶-۱- داده کاوی توزیع شده
در [۳۱] آقای گروسمن، دادهکاوی را استخراج نیمه اتوماتیک مدل‌ها، الگوها، تغییرات، ناهنجاری‌ها، و دیگر ساختارهای مهم آماری از مجموعه داده‌های بزرگ تعریف کرده است. کاوش پایگاه داده‌های توزیع شده [۳۱-۳۳] موضوعی کاربردی است که حجم عظیم تحقیقات انجام شده در این حوزه، سبب پیشرفت چشمگیری در تکنیکهای طبقهبندی [۳۴-۳۶]، خوشهبندی [۳۷, ۳۸]، OLAP [39, ۴۰]، کاوش الگوریتمهای پرتکرار [۴۱-۴۴]، کاوش جریان داده [۴۵, ۴۶]، و ارزیابی شباهت پایگاه داده‌ها [۴۷, ۴۸] شده است. تقریباً، در هر حوزه اصلی پژوهشی داده کاوی، حداقل یک ماژول یا الگوریتم کاوش توزیع شده وجود دارد. موضوعات اصلی این فعالیتهای تحقیقاتی، به اشتراک گذاشتن شباهت‌هاست به این ترتیب که همه‌ی آنها از روش یکپارچه کردن و/ یا مقایسه منابع داده توزیع شده برای رسیدن به هدف مشترک بهره میبرند.
به طور کلی، دو گروه عمده در تحقیقات مربوط به داده کاوی توزیع شده قابل تشخیص است. گروه اول عبارت است از کارهائی که به از بین بردن مشکل توزیع اطلاعات از راه تجمع اطلاعات در یک نقطه مرکزی با بهره گرفتن از الگوریتمها و پروتکل‌های بهبود یافته شبکه میپردازند و با فرض این مسئله که در داده کاوی توزیع شده دقت و هزینه (ناشی از انتقال اطلاعات) مقابل یکدیگر قرار دارند، برای دست‌یابی به یک راهحل قابل قبول از طریق وضع یک استراتژی افزایش دقت در مقابل حداقل هزینه (در حالتی که هزینه انتقال اطلاعات قابل صرفنظر نیست) تلاش می کنند. سیستم Papyrus بر این مبنا استوار است.[۴۹] این دسته از کارها در درخت تحقیق شکل ۲-۲ در نود ۱.۱.۲.۲.۱ قرار میگیرند. گروه دوم از کارهای انجام شده در زمینه داده کاوی توزیع شده، با در نظر گرفتن حالت‌های مختلف توزیع اطلاعات، به ارائه روش‌هایی برای داده کاوی بدون انتقال اطلاعات خام به یک نقطه مرکزی و معمولاً از طریق جابهجائی اطلاعات میانی مختلف بین سایت‌ها میپردازند؛ معمولاً در تمام این روشها، تلاش بر حداقل ساختن ارتباطات است. این گروه از کارها در درخت تحقیق شکل ۲-۲ در جایگاه ۱.۱.۲.۲.۲ قرار دارند. در پژوهش [۵۰] روشی برای استخراج قواعد وابستگی از اطلاعات توزیع شده، با حداقل ارتباط بین فرآیندهای در حال استخراج قوانین ارائه می کند. همچنین به عنوان نمونه ای از تحقیقات انجام شده در زمینه حفظ حریم خصوصی در فرایند داده کاوی، میتوان به [۵۱] اشاره نمود. دو نمونه دیگر از کاربردهای داده کاوی توزیع شده را میتوانید در [۵۲] و [۵۳] مشاهده کنید. در این دو مرجع با بهره گرفتن از مدل‌های ایجاد شده به صورت توزیع شده توسط نودهای مختلف در شبکه و سپس ایجاد مدل داده کلی، سعی می شود تا عملیات نفوذ به شبکه شناسایی و خنثی گردد. البته در [۵۳] در هر نود مذکور در شبکه یک عامل قرار دارد که فعالیتهای مربوط به ایجاد مدل داده و ارتباط با دیگر عاملها را بر عهده دارد.
از دیدگاه طبقهبندی و خوشهبندی، مشکل کشف الگو از پایگاه داده‌های توزیع شده ناشی از چگونگی آموزش مدل‌های کلی از اطلاعات بدست آمده از چندین پایگاه داده است. برای تحقق این هدف از دو روش میتوان استفاده کرد، جمع آوری داده‌ها در قالب یک نگاه واحد، و یا یکپارچه‌سازی مدل‌های ساخته شده از پایگاه داده‌های مجزا.[۵۴, ۵۵] Kargupta و همکاران یک چارچوب داده کاوی اشتراکی با یک کلید اصلی برای یکپارچه کردن داده‌ها در یک نگاه واحد پیشنهاد دادند.[۵۶] فرضیات مشابهی برای حفظ حریم خصوصی در داده کاوی [۵۷, ۵۸]، یک‌دسته کردن و جمع آوری خوشه‌ها [۳۸]، و یکپارچه سازی مدل برپایه‌ی کرنل [۵۴]، از داده‌های ناهمگون ارائه شده است. یین[۲۷] و همکارانش یک کاوشگر عرضی برای طبقهبندی پایگاه داده‌های رابطهای چندگانه پیشنهاد داده بودند. [۵۹] وانگ[۲۸] و همکارانش، مشکل تقویت خوشهبندی چند نوع شی بین رابطهای (به عنوان مثال اسناد وب) را مورد بررسی قرار دادند.[۶۰] مشکل کاوش الگوی پرتکرار برای پایگاه داده‌های توزیع شده به خوبی مورد مطالعه قرار گرفته است [۴۲, ۴۳, ۵۰, ۵۶, ۶۱-۶۷] و سه سازوکار توزیع شمارشی[۲۹]، توزیع داده‌ها، و توزیع کاندید[۳۰] ارائه شده است. [۵۶] در تمام این فعالیتهای پژوهشی، در درجه‌ی اول، تمرکز بر روی کاوش پایگاه داده‌های بزرگ، یا جریان‌های داده متوالی (به عبارتی کاوش الگوهای ال[۳۱])، یا یکپارچه کردن الگوهای کشف شده از پایگاه داده‌های مجزا در قالب یک دانش جدید (به عبارتی کاوش الگوهای جی[۳۲]) بوده است. همچنین برخی از معماریهای سیستم به منظور کشف الگوهای پرتکرار از مجموعه داده‌های در مقیاس ترابایت که بر روی سیستمهای خوشه‌ای اجرا میشوند [۶۸]، طراحی شدهاند که از داده ساختارهای فشرده (مشابه درخت FP[33] [۶۹])، و متدهای رمزنگاری مختصر استفاده میکنند. هرچند، این چارچوب‌ها و راه حل‌ها دامنه‌ی کاری خود را به حجم داده محدود میکنند، اما، هیچ سازوکاری برای مطالعه‌ی مقایسه‌ای بر روی پایگاه داده‌های متعدد و کشف روابط بین الگوها ندارند.
هنگامی که داده‌ها در چندین منبع داده (متمرکز یا توزیع شده) وجود دارند، یکی از مهم‌ترین کارها، بررسی شباهت بین پایگاه داده‌ها برای کشف اطلاعات ساختاری بین آنها به منظور خوشهبندی[۷۰] یا طبقهبندی[۷۱] است. آقایان parthasarathy [72] و لی [۴۷] مشکل ارزیابی شباهت پایگاه داده با مقایسه قوانین انجمنی از پایگاه داده‌های مختلف، به عنوان مثال، قوانین یکسان کشف شده از پایگاه داده‌های مختلف، و تعداد تکرار نمونه‌هایی که از آن قانون تبعیت میکنند، را مورد بررسی و مطالعه قرار دادند. اهمیت یافتن اختلافات بین پایگاه داده‌ها، مسئلهای است که توسط محققان بسیاری مورد مطالعه قرار گرفته است [۴۸, ۷۳-۷۵]، و اکثر روشها بر روی مقایسه‌ی یک جفت پایگاه داده در یک زمان تمرکز دارند. وب[۳۴] و همکارانش، یک روش بر پایه‌ی قانون، به منظور کشف مجموعه تضادهای بین دو پایگاه داده پیشنهاد دادند.[۴۸] Xu و همکارانش، روشی برای کشف انتظارات نسبی بین محصولات از دیدگاه مشتریان پیشنهاد دادند.[۷۶] در مرجع [۷۵]، روش‌هایی برای ارزیابی هم‌ارزی مفهومی بین دو پایگاه داده ارائه شده است. جی و همکارانش، روش‌هایی برای کشف الگوهای متوالی با حداقل تمایز بین دو مجموعه داده، پیشنهاد دادند [۷۷] که در آن الگوها به صورت “پرتکرار در پایگاه داده‌ی A و به طور قابل توجهی کم تکرار در پایگاه داده‌ی B"، به عبارت دیگر، {(A≥α) & (B≤β)} وجود دارند. تمام این روشها بر یافتن اختلافات (در قالب اقلام داده و یا الگوها) بین دو مجموعه داده، تمرکز دارند، اما نمی‌توانند از جستجوهای پیچیده پشتیبانی کنند.
تحقیقات بسیاری در حوزه جستجوی پایگاه داده، و پشتیبانی از عملیات داده کاوی [۷۸-۸۱] صورت گرفته است، و زبان‌های جستجوی پایگاه داده برای پشتیبانی از عملیات کاوش، گسترش یافتهاند، اما اغلب فعالیتهای پژوهشی بر روی یک پایگاه داده‌ی مستقل با شرایط جستجوی نسبتاً ساده تمرکز کردهاند. در مرجع [۷۸] جین و Agrawal، یک سازوکار برپایه‌ی SQL برای کاوش الگوهای پرتکرار بین چندین پایگاه داده، با هدف بهینه سازی جستجوهای کاربران به منظور یافتن الگوهای واجد شرایط ارائه دادند. ۳ نکتهای که در مورد این مقاله باید مورد توجه قرار گیرد: ۱) فعالیتهای انجام شده در تحقیقات آنها تنها بر روی شمارش برنامه‌های جستجو و انتخاب موردی که کم‌ترین هزینه را دارد، تمرکز کردهاند. ۲) به دلیل محدودیتهای چارچوب کاوش الگوی آنها (که بر روی پایگاه داده‌های مستقل کار می‌کردند)، راه حلی که آنها ارائه دادند، تنها میتواند پاسخگوی جستجوهای ساده باشد، به عبارت دیگر، هر کدام از مؤلفه‌های این جستجو باید به صراحت یک پایگاه داده‌ی واحد و مقدار آستانه‌ی متناظر با آن را مشخص کنند، مانند {(Si≥α۱) & (Sj≥α۲) & (Sk≤β)}. بنابراین روشهای آنها نمیتواند جستجوهای پیچیده را جوابگو باشد، و بنابراین کاربرد آن محدود است؛ و ۳ ) روشهای آنها فقط برای پایگاه داده‌های متمرکز قابل اجرا هستند، در صورتی که ما قصد داریم داده کاوی و کشف دانش را بر روی پایگاه داده‌های توزیع شده انجام دهیم.
۲-۶-۲- کارهای مهم انجام شده در زمینه داده کاوی با بهره گرفتن از عامل
این دسته از روشها، رویکرد مبتنی بر عامل را در مواجهه با مسئله داده کاوی توزیع شده پیش میگیرند. اگرچه، همانگونه که در ادامه به تفصیل بیان خواهد گردید، این رویکرد غالباً به نوع نامگذاری راهحل ارائه شده بازمیگردد و نه به خصایص ذاتی عامل (به خصوص هوشمندی). این دسته از روشها در درخت تحقیق شکل ۲-۲ در نود ۱.۲.۲ و به طور دقیق‌تر در نود ۱.۱.۲.۲ قرار میگیرند.
سیستمهای شناخته شده که داده کاوی توزیع شده را با بهره گرفتن از عاملها پیادهسازی می کنند عبارتند از: سیستمهای [۳۵]JAM [82] و [۳۶]PADMA [83]. عاملهای جاوا برای ابریادگیری (JAM)، نام یک سیستم توزیع شده است که با بهره گرفتن از عاملها به داده کاوی می پردازد. این سیستم از تعدادی سایت تشکیل شده است که هر سایت دارای بانک اطلاعاتی خاص خود و نیز تعدادی یادگیرنده میباشد. دو گروه کلی از یادگیرندهها وجود دارد: یادگیرندههائی که در سطح اطلاعات خام عمل می کنند و یادگیرندههائی که توانائی ادغام یادگیرندههای دیگر را دارند (ابریادگیرندهها). سایت‌ها با رابط تعریف شدهای با یکدیگر ارتباط برقرار کرده و درخواست مواردی نظیر ساختار بانک اطلاعاتی یک سایت دیگر (در اینجا صرفاً ساختار یک جدول اطلاعاتی مورد نظر است) و یا فهرست یادگیرندههای آن را مطرح مینمایند. در اینجا قصد نداریم به بررسی نقاط ضعف چنین رویکردی برای داده کاوی روی اطلاعات ناهمگون بپردازیم، بلکه موضوع را صرفاً از دید عاملها و سیستمهای چندعامله مورد بررسی قرار میدهیم.
سیستم JAM دارای تعدادی خصیصه مفید و مهم است. نسبتاً باز بودن سیستم، به این صورت که هر یادگیرندهای در صورت پیادهسازی یک واسط تعریف شده توسط سیستم، که بسیار ساده بوده و یک یادگیرنده صرف نظر از تمایل آن به حضور در سیستم JAM، باید دارای چنین واسطی باشد، می تواند در سیستم به کار گرفته شود. به اشتراک گذاشتن یادگیرندهها بین سایت‌های مختلف، از دیگر مزایای این سیستم است که امکان جابهجائی یادگیرندهها (عملاً برنامه های یادگیرنده) را بین سایت‌های مختلف امکان‌پذیر میسازد. لازم به ذکر است که چنین امکانی به مفهوم ساخت یک طبقهبندی کننده بر روی داده‌های توزیع شده نیست، بلکه صرفاً به معنی امکان بهره گیری از یادگیرندههای متنوع در حل یک مسئله محلی است.
سیستم JAM، علیرغم مزایایی که برشمرده شد، دچار کاستیهائی است که حتی نحوه نامگذاری آن را نیز با پرسش روبرو میسازند. نخستین نقص به نحوه عملکرد سایت‌ها برمیگردد. سایت‌ها در سیستم JAM، بر اساس وقایع عمل می کنند که هر واقعه یا توسط سرپرست سایت ایجاد شده و یا توسط سایت‌های دیگر، که در مورد اخیر نیز در نهایت یک کاربر درخواست کار را مطرح نموده است. چنین رویکردی با یکی از اصول بنیادین مطرح در تعریف عامل در تضاد است: خودآغاز بودن و دریافت پیوسته علائم از محیط و عمل بر اساس این دریافت‌ها. بنابراین اطلاق لفظ عامل به یادگیرندههای مطرح در سیستم JAM با اشکال همراه است. دومین اشکالی که بر اساس تعریف عامل در سیستم مذکور وجود دارد، عدم توجه به مسئله تعادل بین رفتار واکنشی و رفتار پیش فعال است. در اینجا یادگیرندهها صرفاً بر اساس یک الگوریتم یادگیری ماشین، به استخراج دانش از مجموعه اطلاعات ارائه شده به عنوان ورودی پرداخته و هیچ رفتار دیگری برای آنها در نظر گرفته نمی شود.
اگرچه سیستم JAMهرگز اشارهای به مفهوم سیستمهای چندعامله ندارد، اما جهت فراهم آمدن امکان مقایسه بعدی، سیستم مذکور را از این جنبه نیز مورد توجه قرار میدهیم. در نگاه نخست، JAM دارای خواصی مشابه با سیستمهای چندعامله میباشد: وجود اشیاء و قوانین محیطی؛ اما از سوی دیگر، حتی با قبول وجود عاملها (در واقع یادگیرندهها) در سیستم مذکور، با چند مورد نقض تعریف سیستم چندعامله مواجه هستیم. نخست آنکه مفهوم ارتباط بین عاملها فراتر از تعریف یک یا چند واسط مشخص و ثابت، آن گونه که در سیستم JAM انجام شده است، میباشد؛ در واقع در یک سیستم چندعامله به حداقل یک پروتکل ارتباطی که قوانینی را برای مشخص کردن نحوه به کارگیری زبان ارتباطی مشخص مینماید، نیاز داریم. هر عامل بر حسب معماری و هدف خود، با سایر عوامل محیطی ارتباط برقرار خواهد کرد. همچنین مسئله تأثیر عاملها بر محیط نیز در اینجا در نظر گرفته نشده است.
دومین سیستمی که در اینجا مورد بررسی قرار میدهیم، سیستم PADMA (داده کاوی موازی توسط عاملها) میباشد. سیستم مذکور، شامل تعدادی عامل، واسط کاربری و یک هماهنگکننده میباشد. نقش اصلی هماهنگکننده در سیستم، دریافت درخواستهای کاربر و ارجاع آنها به عاملها و سپس جمع آوری و ترکیب نتایج دریافت شده از عاملها میباشد. هر عامل دارای دو توانائی اصلی میباشد: خوشهبندی و پاسخ به پرسوجو، که قابلیت اخیر امکان دسترسی موازی به اطلاعات ذخیره شده در یک بانک اطلاعاتی را فراهم می آورد. نتایج هر یک از این دو فرایند انجام شده توسط هر عامل، به هماهنگکننده منتقل میگردد تا نتیجه نهایی از ترکیب نتایج میانی حاصل شود. هر عامل به صورت مستقل بر روی اطلاعات در دسترس خود عمل می کند؛ به عبارت دیگر، یکی از خواص سیستمهای چندعامله که عدم دسترسی یک عامل تنها به تمامی منابع لازم برای دست‌یابی به هدف میباشد، در اینجا رعایت شده است.
سیستم PADMA نیز با کمبودهائی مشابه با سیستم JAM همراه است. همچنان که از تعریف سیستم مشخص است، در این مورد نیز مسئله خودکار بودن عامل و همچنین تعدد عملیات انجامپذیر در هر لحظه، نادیده گرفته شده است و عاملها صرفاً به پرسوجوی کاربر پاسخ می دهند. دخالت مستقیم کاربر در عملیات، با تعریف عامل در تضاد آشکار است. همچنین مسئله ارتباط بین عاملها در مورد سیستم PADMA نیز حل نشده باقی مانده و به جای پروتکل ارتباطی، یک زبان ارتباطی با امکان انتقال اطلاعات خام و گراف‌های مفهوم، تعریف شده است. تصمیم گیری برای شرکت یا عدم شرکت در یک فرایند دادهکاوی توزیع شده، به هیچ وجه جزء اختیارات عامل منظور نشده و تنها میتوان نوعی همکاری ساده (در قالب انتقال نتایج به یک هماهنگکننده) را بین عاملها تشخیص داد؛ بدیهی است که این نوع از همکاری، با آنچه در مورد سیستمهای چندعامله مطرح است تفاوت زیادی دارد؛ در اینجا حتی هماهنگی بین عاملها (انجام بعضی عملیات در صورت وقوع شرایط خاص ناشی از اعمال سایر عاملها) نیز ضروری نبوده و صرف ادغام نتایج پس از حصول اطمینان از دریافت نتایج کار تمام عاملها، برای دست‌یابی به هدف کفایت خواهد کرد. بنا به دلایل فوق، ۱) سیستم PADMA بر مبنای سیستمهای چندعامله نیست، اگرچه نویسندگان نیز چنین ادعایی را مطرح نکرده اند و ۲) برخلاف نامگذاری انجام شده در مورد PADMA، این سیستم را نمی توان مبتنی بر عامل دانست. بدیهی است که با توجه به موارد مطرح شده، اطلاق عنوان داده کاوی توزیع شده از طریق سیستمهای چندعامله به سیستم PADMA صحیح نمی باشد. البته در زمینه بهرهگیری از عاملها برای داده کاوی کارهای دیگری نیز انجام گردیده است که برای مطالعه بیشتر میتوانید به [۸۴] مراجعه نمایید.
۲-۷- جمعبندی
در این فصل ما ابتدا به معرفی داده کاوی و تکنیکهای آن پرداختیم، تکنیک کاوش قواعد انجمنی را به تفصیل مورد بررسی قرار دادیم، سپس داده کاوی توزیع شده، عامل و سیستمهای چندعامله، و موارد کاربرد عامل را برای داده کاوی مورد بررسی قرار دادیم، و پس از آن، الگوریتم ژنتیک و مفاهیم بنیادی این حوزه را بیان داشتیم. و در نهایت کارها و تحقیقات انجام شده در این زمینه‌ها را بررسی نمودیم. همانطور که مشاهده گردید در مبحث مربوط به استفاده از عامل برای داده کاوی توزیع شده بیشتر خصوصیاتی از عامل همچون خودمختاری، خودآغازی و بیشتر از همه بحث متحرک بودن و قابلیت استفاده از آن در محیطهای توزیع شده مورد بررسی قرار گرفته است، در حالیکه به بهره گیری از بسیاری از خصوصیات مهم عامل همچون هوشمندی، قابلیت یادگیری و استدلال، هدفگرایی و غیره چندان توجهی نشده است.
فصل سوم روش تحقیق
۳-۱- مقدمه
در این فصل، ابتدا شرح مختصری بر دادهکاوی در محیطهای توزیع شده و مشکلات و چالش‌های مرتبط با این تکنولوژی ارائه خواهد شد. سپس عاملها و سیستمهای چند عامله، به عنوان اهرمی برای رفع مشکلات و اصلاح این تکنولوژی مطرح گردیده و مزایای آن برشمرده میشود. و در نهایت الگوریتمهای مطرح در حوزه کشف قوانین انجمنی مورد بررسی قرار خواهند گرفت.
۳-۲- داده کاوی توزیع شده
همانطور که در فصل قبل اشاره شد، داده کاوی توزیع شده به معنای کاوش مجموعه داده‌های توزیع شده میباشد. مجموعه داده‌ها در پایگاه داده‌های محلی که توسط کامپیوترهای محلی و از طریق یک شبکه کامپیوتری بهم متصل هستند، ذخیره میگردند.[۸۵] در شرایط کنونی، اغلب پایگاه داده‌های بزرگ به صورت توزیع شده وجود دارند، و با توسعه تکنولوژی اینترنت و تعمیم یافتن شبکه‌های کامپیوتری، کشف دانش منابع شبکه، مورد توجه افراد قرار گرفته است، و محیط شبکه‌ای، یک پایگاه داده توزیع شده‌ی بزرگ محسوب میشود. زمانی که داده کاوی در محیطی صورت میگیرد که کاربران، داده‌ها، سخت‌افزار و نرمافزار داده کاوی در مکان‌های جغرافیایی مختلفی هستند، به این عمل داده کاوی توزیع شده می‌گویند. اینگونه محیط‌ها به طور خاص دارای ویژگی‌هایی مانند غیریکنواختی داده‌ها، کاربران متعدد و حجم زیاد داده‌ها هستند. دادهکاوی در یک سطح محلی و همچنین در یک سطح عمومی جایی که نتایج دادهکاوی محلی برای رسیدن به یافتههای عمومی ترکیب میشوند، صورت میپذیرد. از داده کاوی توزیع شده اغلب در منابع موجود با عنوان داده کاوی موازی نام برده میشود.[۸۶]
با اینکه هر دو روش سعی در بهبود کارایی سیستمهای داده کاوی سنتی دارند اما آنها ساختارهای متفاوتی را برای سیستم‌ها در نظر میگیرند و از شیوه‌های مختلفی بهره میگیرند. در داده کاوی توزیع شده کامپیوترها در مکان‌های مختلفی قرار دارند و از طریق تبادل پیام‌ها ارتباط برقرار میکنند. در داده کاوی موازی یک کامپیوتر موازی دارای پردازنده‌هایی است که حافظه و یا دیسک را به اشتراک میگذارند.
به کامپیوترهایی که در یک سیستم داده کاوی توزیع شده فعالیت میکنند میتوان به دید پردازنده‌هایی که هیچ چیزی را به اشتراک نمی‌گذارند نگریست. این تفاوت در ساختار، تأثیر زیادی بر روی طراحی الگوریتم، مدل هزینه‌ای و اندازه‌گیری کارایی در داده کاوی توزیع شده و موازی دارد.[۸۶]
دو مسئله نیاز به داده کاوی توزیع شده را به ما تحمیل میکنند: داده‌ها ممکن است به طور ذاتی توزیع شده باشند و این مسئله میتواند به دلایل عملیاتی مختلفی مانند توزیع امن و مقاوم به خطای داده‌ها و خدمات و یا پلت فرم‌های متحرک باشد. همچنین، هزینه انتقال داده‌ها به یک سایت واحد، معمولاً بالا و گاهی اوقات غیرقابل قبول است.[۸۷]
مسئله دوم اینست که تعداد زیادی از الگوریتمهای کاوش نیاز به این دارند که تمام داده‌ها در حافظه موجود باشند. این امر شاید برای مجموعه داده‌های بزرگ غیرممکن باشد زیرا این الگوریتمهای یادگیری توانایی پردازش این حجم عظیم داده‌ها را ندارند. قسمت‌بندی داده‌ها یکی از راه حل های معمول برای این مشکل میباشد.
در نتیجه، داده کاوی توزیع شده تکنیک‌هایی برای کشف الگوهای مهم در پایگاه داده‌های مجزا، بررسی الگوها از یک منظر واحد، و کشف روابط خاص بین مجموعه داده‌های متفاوت است.[۸۸] الگوریتمهای داده کاوی توزیع شده معمول، تحلیل داده‌های محلی را صورت می‌دهند که پس از آن با بهره گرفتن از روشهای یکپارچه‌سازی دانش، دانش عمومی از آنها استخراج میشود. یک نمونه از داده کاوی توزیع شده در شکل ۳-۱ نشان داده شده است.
شکل ۳- ۱:یک چارچوب دادهکاوی توزیع شده
۳-۲-۱- گروه‌بندی مدل‌های دادهکاوی توزیع شده
به طور کلی، دو نوع مدل معماری در توسعه‌ی سیستمهای دادهکاوی توزیع شده مورد استفاده قرار میگیرند، که عبارتند از: کلاینت سرور، و عاملهای نرمافزاری. همانطور که در شکل ۳-۲ نشان داده شده است، دسته‌ی عاملها، خود میتوانند با توجه به اینکه آیا قابلیت جابجایی با هدایت خود را دارند یا خیر، به دو گروه تقسیم شوند.[۸۹]
سیستمهای دادهکاوی توزیع شده
معماری‌ها
کلاینت - سرور
عاملهای نرمافزاری
جابجایی با هدایت خود
ساکن و بی حرکت
موبایل
شکل ۳- ۲: گروه‌بندی سیستمهای دادهکاوی توزیع شده
۳-۲-۲- مشکلات دادهکاوی توزیع شده
مسئلهای که داده کاوی توزیع شده می‌خواهد آن را حل کند، کشف و استخراج دانش از پایگاه داده توزیع شده است، که این کار با مشکلات پیچیدهای روبرو است، مانند منابع دادهای بزرگ، مشکلات انتقال داده، ترکیب داده‌ها، و غیره. در زیر به تعدادی از این موارد اشاره شده است:
۳-۲-۲-۱- افزونگی داده
برای استفاده و مدیریت درست، معمولاً حجم عظیمی از افزونگی داده در پایگاه داده توزیع شده وجود دارد، و این مسئله تأثیرات منفی بسیاری بر روی دادهکاوی می‌گذارد، و منجر به بروز مشکل داده‌های ناجور میشود.
۳-۲-۲-۲- تغییرات پویای محیط
در محیط شبکه‌ای داده متغیر است، دادهکاوی و جمع آوری نتایج درست که وابسته به زمان باشند، مشکل است.
۳-۲-۲-۳- سربار ارتباطات
در محیط توزیع شده، ارتباطات دادهای تأثیر قابل توجهی بر روی زمان سپری شده دارند، و هزینه‌ها به طور عمده مرتبط با پهنای باند و ترافیک شبکه هستند، بنابراین در زمان طراحی سیستم دادهکاوی، تا جایی که امکان دارد باید ارتباطات دادهای کاهش یابد.
۳-۲-۲-۴- مشکلات دادهکاوی توزیع شده به روش سنتی
پردازش داده‌ها با بهره گرفتن از روش داده کاوی و مدل سیستم کاوش سنتی برپایه‌ی روش متمرکز هستند. راه حل کلی داده کاوی بر روی مخازن توزیع شده، انتقال داده‌های سایت‌های محلی به بخش مرکزی و سپس اجرای متد داده کاوی متمرکز برای کاوش داده است. مزیت این روش این است که با بهره گرفتن از تکنولوژی داده کاوی و سیستم کاوش، میتوان به نتایج ایده‌آل رسید، اما معایب و نواقص این روش نیز بارز است، که در اینجا به دو مورد اشاره میشود:
داده کاوی به معنای استخراج دانش از حجم عظیم داده است، و انتقال حجم عظیم داده به بخش مرکزی میتواند منجر به تراکم زیاد بر روی شبکه شود.
دادهای که میبایست در این روش، بر روی شبکه منتقل شود، اغلب با مشکلات و مسائل امنیتی روبرو است.
۳-۳- عاملها و دادهکاوی
در بسیاری از حالات، هم سیستمهای چند عامله و هم سیستمهای دادهکاوی، درگیر مسائل هوشمندی میشوند. این مورد، چالش‌های مشترکی که هر دو حوزه با آنها روبرو هستند را آشکار میسازد. برای مقابله با چنین چالش‌هایی، در کنار تکنیکهای جدیدی که در هر یک از این دو حوزه باید ابداع شوند، یک روش قابل اطمینان، ترکیب این دو رشته است که بتوانند مکمل یکدیگر باشند.
چرا تعاملات و یکپارچه کردن عاملها و دادهکاوی اهمیت دارد؟ دلائل صریح و روشن و غیر صریحی برای این مسئله وجود دارد. دلائل صریح میتوانند شامل موارد زیر باشند [۹۰, ۹۱]:
محدودیت‌ها و چالش‌های سیستم‌هایی که تنها بر پایه‌ی عاملها بنا نهاده شدهاند، با دادهکاوی قابل حل است. در واقع تکنولوژی دادهکاوی مکمل تکنولوژی عامل میباشد. به عنوان نمونه، میتوان از یادگیری عاملها بر پایه‌ی دادهکاوی، مدلسازی کاربر و تجزیه و تحلیل اطلاعات نام برد.
محدودیت‌ها و چالش‌هایی که سیستمهای دادهکاوی با آنها روبرو هستند، میتوانند توسط تکنولوژی عامل بهتر پاسخ داده شوند. به عنوان مثال، زیرساخت دادهکاوی برپایه‌ی عامل، استفاده از عاملها برای آماده سازی و مدیریت داده‌ها، و سرویس‌دهی بر پایه‌ی عامل.
کاوش-عامل، میتواند نتایج و دستاوردهای بهتری را نسبت به حالتی که این دو تکنولوژی بطور مجزا بکار گرفته میشوند، به ارمغان آورد. به عنوان نمونه، هوشمندی بیشتر قابلیتها در درک بهتر مسائل، یادگیری، سازگاری، تصمیم‌گیری، کشف، و استدلال.
و دلائل غیرصریح که مهم هستند و باید مورد توجه قرار بگیرند، میتوانند شامل موارد زیر باشند:
کاوش-عامل، برای مقابله با پدیده‌ی هوشمندی و پیچیدگی‌های سیستم در سیستمهای هوشمند پیچیده، ضروری است. سیستمهای هوشمند ساده، و سایر مسائل که بتوانند با بهره گرفتن از یکی از این دو تکنولوژی پاسخ داده شوند، مانند سیستم یکپارچه کردن داده‌ها بر پایه‌ی عامل، نیازی به بکارگیری هر دو تکنولوژی ندارند.
ظهور هوشمندی، در کاوش عامل، میتواند قابلیت حل مشکل سیستمهای هوشمند را قدرت بخشد، که این تنها، با بهره گرفتن از یکی از این دو تکنولوژی قابل انجام نیست.
نقشهای غیرواضح باید از طریق مطالعات میان رشته‌ای کشف شوند. شناسایی نقش‌ها و توسعه آنها، میتواند یکی از دو طرف یا کل سیستم یکپارچه‌ی کاوش عامل را بطور گستردهای توسعه دهد.
مباحث تحقیقاتی، فرصت‌ها، تکنیک‌ها، و سیستمهای جدید در جامعه کاوش عامل، شکل میگیرد.
این مورد که تکنولوژی عاملها و دادهکاوی میتوانند مکمل یکدیگر باشند، باید مورد بحث و بررسی قرار گیرد. کاوش عامل، میتواند با ارائه تکنیک‌ها و رویکردهای نوین، هر دو حوزه را توسعه دهد و چالش‌های آنها را بگونه‌ای رفع کند که هر کدام به تنهایی قادر به آن نیستند. مزایایی که کاوش عامل برای حوزه‌های دادهکاوی و عاملها به ارمغان می‌آورد عبارتند از:
بهبود تکنولوژی عاملها از طریق دادهکاوی: تعاملات کاوش-عامل، اولین بار در سال ۱۹۹۱ با یادگیری عاملها بر پایه‌ی دادهکاوی صورت گرفت. دادهکاوی، میتواند در جنبه‌های مختلف، علی‌الخصوص، در یادگیری عامل، هماهنگی و برنامه‌ریزی عامل، مدلسازی و سرویس‌دهی کاربر، و سرویس‌دهی شبکه، تاثیر قابل توجهی در رشد و بهبود تکنولوژی عامل داشته باشد.
توسعه دادن دادهکاوی از طریق عاملها: حدود سال ۱۹۹۳ تلاش برای استفاده از دادهکاوی برپایه‌ی عاملها یا به عبارتی استفاده از تکنولوژی عامل برای بهبود دادهکاوی شکل گرفت. بهبود این تکنولوژی میتواند از جنبه‌های مختلفی مورد بررسی قرار گیرد، به عنوان نمونه، زیرساخت کشف دانش بر پایه‌ی عامل، پردازش توزیع شده بر پایه‌ی عامل، دادهکاوی تعاملی بر پایه‌ی عامل، و ذخیره کردن داده بر پایه‌ی عامل.
ساخت سیستمهای فوق هوشمند: استفاده از کاوش عامل میتواند منجر به ساخت سیستمهای هوشمندتری شود که به بهترین نحو از قدرت هوشمندی عاملها و قدرت دادهکاوی در پردازش دانش بهره میبرند.
۳-۳-۱- حوزه کاوش عامل
یکپارچه‌سازی و تعاملات دادهکاوی و عاملها، یا بطور مخفف، کاوش عامل، حوزه‌ی تحقیقاتی جدید و نویدبخشی را شکل داده است. محققان این حوزه، همچون سایر حوزه‌های علمی نوظهور، بر روی متدولوژی‌ها، اصول، تکنیک‌ها و برنامه‌های کاربردی یکپارچه‌سازی و تعاملات بین عاملها و دادهکاوی مطالعاتی را انجام می‌دهند. کاوش عامل، یک حوزه جامع، چند بعدی و میان رشته‌ای است.
به منظور تلفیق این دو تکنولوژی، نکتهای که باید مورد توجه قرار بگیرد این است که کاوش عامل، باید بین آنها از ابعاد مختلف (شکل ۳-۳)، به عنوان مثال، منابع، زیرساخت، یادگیری، دانش، تعامل، واسط، اجتماعی، برنامه کاربردی، و کارایی اشتراک عمل برقرار کند [۹۲]. این ابعاد به اختصار در زیر شرح داده شدهاند:
لایه‌ی منابع: تعاملات و یکپارچه‌سازی در سطح داده‌ها و اطلاعات صورت میگیرد.
لایه‌ی زیرساخت: تعاملات و یکپارچه‌سازی در زیرساخت، معماری، و یا در سطح پردازشی شکل میگیرد.
لایه‌ی دانش: در این لایه، تعاملات و یکپارچه‌سازی بر مبنای دانش هستند، که شامل دانش دامنه، دانش افراد خبره، متا دانش، دانش بازیافتی، استخراج شده یا کشف شده از منابع میباشند.
لایه‌ی یادگیری: تعاملات و یکپارچه‌سازی این لایه بر پایه‌ی متدهای یادگیری، قابلیت‌های یادگیری، و دیدگاه کارایی شکل میگیرد.
لایه‌ی تعاملات: در این لایه، به تعاملات و یکپارچه‌سازی از دیدگاه هماهنگی، مشارکت، مذاکره، و ارتباطات پرداخته میشود.
لایه‌ی واسط: تعاملات و یکپارچه‌سازی این دو تکنولوژی در این لایه درارتباط با واسط بین کاربر و سیستم، مدلسازی کاربر و طراحی واسط است.
لایه‌ی اجتماعی: در این لایه، تعاملات و یکپارچه‌سازی میتواند بر روی فاکتورهای سازمانی و اجتماعی، به عنوان مثال، نقش انسان، باشد.
لایه‌ی برنامه کاربردی: تعاملات و یکپارچه‌سازی این لایه در ارتباط با مشکلات برنامه‌ها و دامنه است.
لایه‌ی کارایی: تعاملات و یکپارچه‌سازی به منظور افزایش کارایی یکی از تکنولوژی‌ها و یا کل سیستم صورت میگیرد.
شکل ۳- ۳: اشتراک عمل چند بعدی کاوش- عامل
اگر از این ابعاد به مبحث کاوش عامل پرداخته شود، مسائل و مباحث تحقیقاتی بسیاری ظهور پیدا میکنند. میتوان باتوجه به مسائل گفته شده، نقشه‌ی راه تحقیقاتی کاوش عامل، به عنوان یک حوزه‌ی میان رشته‌ای را ایجاد کرد.
۳-۳-۲- دادهکاوی برپایه‌ی عامل
آقای وولدریج[۳۷]، عاملها را به عنوان نوعی نرمافزار کامپیوتری معرفی کرده است، که میتوانند به صورت خودمختار به فعالیت بپردازند و اهداف مدنظر را تأمین کنند.[۲۶] عاملهای هوشمند، عامل‌هایی پیشرفته هستند که میتوانند به تغییرات محیط واکنش نشان دهند، در تعامل با دیگر عاملها باشند، و از محاسبات هوشمند برای رسیدن به اهدافشان بهره ببرند.[۹۳] عاملها، فعال، وظیفه محور، طراحی شده برای کارهای خاص، قادر به تصمیم‌گیری، و خودمختار هستند.
در برخی سیستم‌ها، به منظور رفع یک مشکل، از ترکیب چند عامل استفاده میشود، به این سیستم‌ها، سیستمهای چند عامله می‌گویند. این سیستم‌ها، از عامل‌هایی تشکیل شدهاند که هرکدام، مشکلاتی ساده‌تر از مشکل اصلی را حل میکنند. آنها میتوانند با یکدیگر در ارتباط باشند و به هم کمک کنند تا به اهداف بزرگ‌تر و پیچیده‌تری دست یابند.
تکنولوژی چند عامله، در حوزه‌ی تعاملات کاربر، محاسبات خودمختار، قابلیت سازماندهی خود، همکاری، مشارکت، ارتباطات، مذاکرات، محاسبات فرد به فرد، محاسبات موبایل، و هوشمندی جمعی خوب عمل میکند. اینها نقاط قوت اصلی این تکنولوژی هستند و میتوانند فرایند دادهکاوی را به میزان قابل توجهی بهبود بخشند و مشکلات خاص و پیچیده‌ی دادهکاوی را در حوزه‌هایی مانند پردازش داده، پردازش اطلاعات، کاوش الگو، مدلسازی و تعاملات کاربر، زیرساخت و سرویس‌ها برطرف کنند. یکی از موارد اصلی، دادهکاوی بر پایه‌ی عامل است.
منظور از دادهکاوی بر پایه‌ی عامل، نسخه‌هایی از سیستمهای چند عامله است که برای بهبود فرایند داده کاوی ایجاد شدهاند. توسعه‌ی سیستمهای چند عامله میتواند به حل مسائل داده کاوی کمک کند. به عنوان مثال، معماری و زیرساخت دادهکاوی بر پایه‌ی عامل، کاوش تعاملی بر پایه‌ی عامل، تعامل کاربر بر پایه‌ی عامل، کاوش الگوی اتوماتیک، کاوش داده توزیع شده بر پایه‌ی عامل، کاوش پویا بر پایه‌ی عامل، کاوش چندین منبع داده بر پایه‌ی عامل، کاوش داده فرد به فرد بر پایه‌ی عامل، و کاوش وب بر پایه‌ی عامل. در ادامه، نقشهای عاملها در حمایت از دادهکاوی توزیع شده شرح داده خواهد شد.
در برنامه‌های سازمانی، داده‌ها در منابع ناهمگن توزیع شدهاند. منابع داده توزیع شده مرتبط با یک کسب و کار اغلب پیچیده هستند. به عنوان نمونه، برخی از منابع داده از چگالی و فرکانس بالایی برخوردارند، و شامل داده‌های پویا و ایستا، و ساختارهای دادهای چندگانه هستند. در برخی از موارد، چند منبع داده در سیستمهای ذخیره‌سازی موازی نگهداری میشوند. منابع داده محلی ممکن است بخاطر ارزش تجاری، پوشیدگی، و غیره مشکل محدودیت دسترسی داشته باشند که این مورد سبب میشود حتی در وضعیت مشارکتی، از پردازش‌های متمرکز جلوگیری شود. برای این قبیل داده، ادغام و یکپارچه‌سازی داده، کاری مشکل است. نمی‌توان آنها را در یک مخزن مرکزی ذخیره کرد و پردازش‌های را بصورت متمرکز بر روی داده‌ها اعمال نمود. به منظور کاوش داده، با توجه به ضعف موجود در معماری و زیرساخت سیستمهای دادهکاوی توزیع شده موجود، نیاز به پشتیبانی انعطاف‌پذیر، هوشمندانه، و مقیاس پذیر وجود دارد.
تکنولوژی عامل میتواند با قابلیت‌های خودمختاری، تعامل، انتخاب پویا، مقیاس‌پذیری، قابلیت داشتن چند استراتژی و مشارکت، در رفع این چالش‌ها کمک کند. دلائل دیگر، شامل پوشیدگی، جابجایی، محدودیت زمان (جریان داده، زمان بر بودن فرایند استخراج و کاوش بر روی آن)، و هزینه‌های محاسباتی و نیازهای کارایی میشوند. درواقع تکنولوژی چند عامله، از خیلی جهات مکمل دادهکاوی توزیع شده است، به عنوان مثال:
منابع داده چندگانه و توزیع شده، اغلب بصورت جدا از هم هستند. برای درک بهتر یک مشکل کسب و کار، لازم است داده‌های مرتبط از طریق یکپارچه‌سازی مرکزی یا ارتباطات محلی در کنار هم قرار گیرند. با توجه به این، مشارکت و برنامه‌ریزی عامل، عاملهای موبایل، ارتباطات و مذاکرات عاملها میتوانند مفید باشند.
جابجایی داده و دستگاه، نیازمند درک و استفاده از الگوریتمهای دادهکاوی بر مبنای قابلیت تحرک است. عاملهای موبایل بخوبی میتوانند با خصیصه جابجایی سازگار شوند.
عاملی برای محدود کردن میزان نظارت و دخالت کاربر در اجرای فرایند دادهکاوی لازم است.
در محیط توزیع شده باز و متغیر، میتوان از عاملهای کشف دانش برای انتخاب منابع داده برحسب معیارهای داده شده به آنها استفاده کرد، به عنوان مثال معیارهایی مانند مقدار، نوع، و کیفیت مدنظر از یک منبع خاص، شبکه واقعی و بار شدن سرور کشف دانش. به عنوان نمونه میتوان از عاملها برای انجام پروسه‌ی گرداوری داده استفاده کرد.
برخی از داده‌های توزیع شده در منابع ذخیره‌سازی مختلف، وابسته به زمان هستند.
برای برخی از برنامه‌های پیچیده، ترکیبی مناسب از چندین تکنیک دادهکاوی بهتر از یک تکنیک خاص عمل میکند. عاملهای کشف دانش، میتوانند بر اساس نوع داده سایت‌های مختلف و اعمال کاوشی که باید صورت گیرد، تصمیم بگیرند.
عاملها میتوانند بطور مستقل بر روی داده‌های سایت‌های مختلف، اعمال کاوش را انجام دهند و در نهایت مدل‌های حاصله را با هم ترکیب کنند. همچنین میتوانند دانشی که استخراج کردهاند را به اشتراک بگذارند تا از قابلیت‌های سایر عاملها بهره‌مند شوند.
داده‌های محلی توزیع شده، براساس مسائل پوشیدگی داده‌ها، اجازه ندارند استخراج و با سایر منابع بطور مستقیم، یکپارچه شوند. یک عامل که مجوز دسترسی و پردازش داده‌ها را دارد، میتواند الگوهای محلی شناسایی شده را برای ترکیب با یافتههای سایر منابع به کار بندد.
در برخی از سازمانها، منطق کسب و کار، فرایندها، و گردش کاری، ترتیب منابع داده و دسترسی به آنها را تعیین میکنند. بنابراین پیچیدگی دادهکاوی توزیع شده را افزایش می‌دهند. عامل‌هایی که در هریک از منابع قرار گرفتهاند میتوانند با یکدیگر ارتباط برقرار کنند.
در واقع دادهکاوی توزیع شده بر پایه‌ی عاملها، رویکردی منحصربفرد برای بکارگیری قابلیتها، ارائه دادن، و انجام برخی مسئولیت‌هاست که عبارتند از:
هوشمندی داده از قبیل دسترسی به داده توزیع شده و مشارکت و همکاری بر پایه عامل
هوشمندی بشر از طریق تعامل کاربر-عامل، مدلسازی کاربر و سرویس دهی به وی
فاکتورهای سازمانی و دامنه مانند هوشمندی گروه برپایه‌ی سیستمهای چند عامله، هوشمندی جمعی، و ظهور هوشمندی
هوشمندی شبکه از طریق عاملهای موبایل، مشارکت و ارتباطات بر پایه‌ی سیستمهای چند عامله، و
هوشمندی اجتماعی از قبیل شناخت و تعاملات اجتماعی بر مبنای سیستمهای چند عامله تا بتوان گروهی از افراد خبره را در فرایند کاوش درگیر کرد.
۳-۳-۳- مزیت بهرهگیری از عاملها در دادهکاوی
تکنولوژی دادهکاوی زمانی که وارد دنیای واقعی حل مشکل، بطور خاص‌تر در حوزه مدیریت داده‌ها و برنامه‌های پیچیده شود، با چالش‌ها و مشکلات بسیاری روبرو خواهد شد. در اینجا، برخی از موارد که از طریق تکنولوژی عامل قابل حل میباشند، مورد بررسی قرار میگیرد. این موارد شامل زیرساخت دادهکاوی سازمانی، بکارگیری هوشمندی انسان و دامنه، پشتیبانی از کاوش توزیع شده و موازی، آماده‌سازی و اصلاح داده، یادگیری سازگار، و کاوش تعاملی.
۳-۳-۳-۱- زیرساخت دادهکاوی سازمانی
توسعه سیستمهای دادهکاوی که از برنامه‌های کاربردی سازمان پشتیبانی کنند، بسیار چالش برانگیز است. چالش‌های این حوزه ممکن است از خیلی جهات بروز کنند، به عنوان نمونه، یکپارچه‌سازی یا کاوش منابع داده چندگانه، دسترسی به برنامه‌های توزیع شده، ارتباط متقابل با کاربران متنوع کسب و کار، و ارتباطات با برنامه‌های کاربردی چندگانه. علی الخصوص، ساخت یک پلت فرم توزیع شده، انعطاف‌پذیر، سازگار، و کارا که از کاوش تعاملی پشتیبانی کند چالش بزرگی محسوب میشود.
۳-۳-۳-۲- بکارگیری هوشمندی انسان و دامنه
چالش بزرگ دیگری که تکنیک‌ها و متدولوژی‌های دادهکاوی موجود با آن روبرو هستند، نقش‌ها و بکارگیری هوشمندی انسان و هوشمندی دامنه در دادهکاوی است. علیرغم مزایای بسیار هوشمندی دامنه، چگونگی بکارگیری، بیان کردن، تائید کردن و اتصال به کامپوننت‌هایی همچون دانش دامنه، دانش پیشین، فرایند کسب و کار، و منطق کسب و کار در سیستمهای دادهکاوی، یک مشکل تحقیقاتی است. در ارتباط با هوشمندی انسان، تشخیص نقش انسانها در برنامه‌های خاص مورد نیاز است، تا بتوان یک سیستم پشتیبانی برای مدلسازی رفتار انسان تهیه نمود. این سیستم به عنوان پلی برای ایجاد ارتباطات بین سیستمهای دادهکاوی و انسانها عمل کرده و مزیت دانش انسانی و نظارت وی بر سیستم را به ارمغان می‌آورد.
۳-۳-۳-۳- پشتیبانی از کاوش توزیع شده و موازی
یکی از موضوعات پژوهشی دادهکاوی که تلاش بسیاری در آن صورت میگیرد، افزایش کارایی الگوریتمهای دادهکاوی است. معمولا از طریق طراحی ساختار داده‌ها و متدهای محاسباتی کارامد به منظور کاهش پیچیدگی محاسباتی به آن پرداخته میشود. در بسیاری از حالات، کارایی محاسباتی میتواند از طریق توسعه‌ی الگوریتمهای موازی، رشد و پیشرفت خوبی داشته باشد. در سایر حالات، از قبیل سروکار داشتن با منابع داده و برنامه‌های توزیع شده، و یا محاسبات فرد به فرد، محاسبات توزیع شده نیاز است. به هر حال، چگونگی طراحی الگوریتمهای کارامد و موثر توزیع شده و موازی یک موضوع مهم محسوب میشود.
۳-۳-۳-۴- پیش پردازش داده
در دنیای واقعی، داده‌ها روز به روز پیچیدهتر میشوند، علی الخصوص داده‌های پراکنده و ناهمگن که در مکان‌های مختلف توزیع شدهاند. برای دسترسی و ترکیب اینگونه داده‌ها نیاز به تکنیک‌ها و متدهای هوشمند است. از طرفی دیگر، تحقیقات کنونی بر روی آماده‌سازی داده با چالش‌های جدیدی همچون پردازش جریان داده‌های وابسته به زمان با فرکانس بالا، توزیع داده غیرمتوازن، استخراج شواهد پراکنده، اما مهم از مجموعه داده‌های پراکنده، ارتباط منابع داده مختلف، و دسترسی به داده‌های پویا روبرو است. همچین شرایطی، نیازمند تکنیکهای جدید آماده‌سازی داده است.
۳-۳-۳-۵- یادگیری سازگار
بطور کلی، الگوریتمهای دادهکاوی اینگونه تعریف شدهاند که مجموعه‌های داده را اسکن کنند. در شرایط دنیای واقعی، از مدل‌ها و الگوریتمهای دادهکاوی انتظار می‌رود بتوانند براساس قابلیت‌های خود یادگیری و خود سازماندهی، با شرایط پویا در داده متغیر سازگار شوند. به عبارت دیگر، مدل‌ها و الگوریتمها، میتوانند بطور اتوماتیک، الگوهایی را از داده متغیر استخراج کنند. در هر صورت، این حوزهای چالش برانگیز است، چراکه متدولوژی‌ها و تکنیکهای موجود دادهکاوی اتوماتیک و سازگارپذیر نیستند. به منظور اصلاح قابلیت اتوماتیک و سازگارپذیری الگوریتمها و متدهای دادهکاوی، نیاز به پشتیبانی از دانش و تخصص‌هایی میباشد که مرتبط با تکنیکهای هوشمند سازگاری و اتوماتیک هستند.
۳-۳-۳-۶- کاوش تعاملی
بحث‌های مرتبط با دادهکاوی تعاملی یا اتوماتیک در گذشته شروع شده است. یک مسئله واضح برای این مشکل این است که ارتباطات متقابل بین انسانها و سیستمهای دادهکاوی، نقش مهم و عینی در دادهکاوی برپایه‌ی دامنه دارد. در توسعه‌ی دادهکاوی تعاملی، یک محقق باید در مورد مباحثی چون مدلسازی کاربر، شبیه‌سازی رفتار، تجزیه و تحلیل شرایط، طراحی واسط کاربر، مدیریت دانش کاربر، تنظیمات ورودی مدل، یا الگوریتم توسط کاربران، نظارت و کنترل بر فرایند کاوش، و پالایش و تصحیح خروجی، به مطالعه بپردازد. بسیاری از این موارد نمی‌توانند توسط رویکردهای موجود دادهکاوی انجام شوند.
۳-۳-۴- دادهکاوی توزیع شده برپایه‌ی عاملها
این بخش بطور خاص بر روی حوزه‌ی پیشرفته و به روز کشف دانش بر پایه‌ی عاملها به بحث می‌پردازد. همانطور که در بخش‌های قبل گفته شد، کشف دانش بر پایه‌ی عاملها، حوزه‌ی بزرگی برای کاوش عامل را شکل میدهد. در واقع حوزهای است که در کاوش عامل بیش از همه به آن پرداخته شده است.
۳-۳-۴-۱- چالش‌های دادهکاوی توزیع شده
دادهکاوی و یادگیری ماشین، در حال حاضر، حوزهای را در هوش مصنوعی شکل دادهاند که توسط رویکردها، الگوریتمها، و ابزارهای نرمافزاری متعددی پشتیبانی میشوند. برنامه‌های کاربردی و تکنولوژی‌های اطلاعاتی جدید الهام بخش نیازمندی‌های مدرن در دادهکاوی و یادگیری ماشین بوده است و ویژگیهای خاص منابع داده بطور فزاینده‌ای کار را مشکل کرده، و نیازمندی‌هایی را آشکار میکنند که عبارتند از:
در برنامه‌های سازمانی، داده‌ها در منابع ناهمگن توزیع شدهاند و بصورات آزاد و رها یا محکم و سخت به هم متصل شدهاند.
منابع داده توزیع شده مرتبط با یک کسب و کار اغلب پیچیده‌اند، به عنوان مثال، برخی چگالی و فرکانس بالایی دارند، و ترکیبی از داده‌های پویا و استاتیک و ساختارهای دادهای متنوع هستند.
ادغام و یکپارچه‌سازی داده کار مشکلی است. نمی‌توان آنها را در یک مخزن مرکزی ذخیره کرد، و پردازش بر روی آنها بصورت متمرکز کار آسانی نیست.
در برخی از حالات، چندین منبع داده در سیستمهای ذخیره‌سازی موازی ذخیره شدهاند.
منابع داده محلی، ممکن است بخاطر مسائل پوشیدگی، ارزش تجاری، و غیره از نظر میزان دسترسی در محدودیت باشند. که این سبب میشود در بسیاری از حالات امکان پردازش بصورت متمرکز حتی در حالت همکاری و مشارکت وجود نداشته باشد.
در بسیاری از حالات، داده‌های توزیع شده در سیستمهای ذخیره‌سازی عمومی وابسته به زمان هستند.
دسترسی به منابع داده در یک محیط موبایلی به زمان وابسته است.
ضعف در معماری و زیرساخت سیستمهای دادهکاوی موجود نیازمند پشتیبانی انعطاف‌پذیر، هوشمند، و مقیاس‌پذیر است.
این موارد و موارد دیگر، نیاز به توسعه‌ی رویکردها و تکنولوژی‌های جدید دادهکاوی برای شناسایی الگوها در داده‌های توزیع شده را ایجاد میکند. دادهکاوی توزیع شده، و بطور خاص‌تر دادهکاوی فرد به فرد، و تکنولوژی چند عامله، دو پاسخ به چالش‌های ذکر شده است. اگر از تکنولوژی چندعامله در سیستم داده کاوی توزیع شده بهره گرفته شود، نه تنها مشکلات مطرح شده به میزان قابل توجهی کاهش مییابد، مزایای بسیاری نیز به ارمغان می‌آورد [۹۴, ۹۵]. برخی از این مزایا عبارتند از:
کنترل غیر متمرکز
کنترل غیرمتمرکز، تقریباً، مهم‌ترین خصوصیت سیستمهای چندعامله است که آنها را از رویکردهای موازی و توزیع شده متمایز میکند. کنترل غیرمتمرکز به این معنی است، که هر عامل در یک سیستم چندعامله، خودمختار عمل میکند.
مقاوم در برابر خرابی
این خصوصیت، یکی از ویژگیهای کنترل غیرمتمرکز است، به این معنا که حتی اگر تعدادی از عاملها دچار مشکل شوند و از کار بیفتند، سیستم کلی به عملیاتش ادامه خواهد داد.
پیچیدگی توسعه سیستم را کاهش میدهد
سیستم چندعامله نه تنها در ساختار توزیع شده است، بلکه در منطق نیز توزیع شده است، بنابراین برای کاوش توزیع شده در محاسبات موازی بسیار مناسب است و میتواند پیچیدگی توسعه سیستم را کاهش دهد. این خصوصیت نیز نشأت گرفته از کنترل غیرمتمرکز اینگونه سیستم‌ها است، چرا که میتوان از طریق افزودن عاملها کاربردهای سیستم را افزایش داد.
هوشمندی سیستم را افزایش میدهد
نسبت به سایر سیستمهای نرمافزاری، عامل، استعداد و شایستگی بالایی دارد و میتواند سرویس دقیق و مناسب ارائه دهد.
آشکاری و آزادی سیستم را افزایش میدهد
به عبارت دیگر، در متدهای پیادهسازی، عامل نوعی از مدل کپسوله‌سازی است.
ترافیک سیستم را کاهش میدهد
عاملی که در سایت‌های محلی وجود دارد میتواند نتایج کاوش خود را به سایت‌های مرتبط برای تجزیه و تحلیل نتایج کلی ارسال کند، که این عمل میتواند تا حدی ترافیک داده بر روی شبکه را کاهش دهد.
پایداری سیستم را افزایش میدهد
در مقابل آشفتگی‌ها و اختلالات خارجی، عامل میتواند به منظور تنظیم کردن پارامترها از طریق یادگیری تعاملی، با محیط جدید سازگار شود و کارایی و پایداری سیستم را تضمین کند.
۳-۳-۵- مزیت بهرهگیری از عاملها در دادهکاوی توزیع شده
پیادهسازی عملی دادهکاوی توزیع شده و فرد به فرد و یادگیری ماشین، چالش‌های جدیدی را ایجاد کردهاند. در حین تجزیه و تحلیل این چالش‌ها، این بحث مطرح میشود که چرا تکنولوژی عامل، بهترین تکنولوژی برای مقابله با این چالش‌هاست که پاسخ این سوال را میتوان در قابلیت‌های عامل همچون خودمختاری، ارتباطات متقابل، گرداوری و انتخاب پویا، مقیاس‌پذیری، چند استراتژی و همکاری یافت. دلائل دیگر شامل پوشیدگی، قابلیت جابجایی، محدودیت زمانی (جریان داده که فرایند استخراج و پس از آن عمل کاوش بسیار زمانبر خواهد بود)، هزینه‌های محاسباتی و نیازهای کارایی میشوند.
۳-۳-۵-۱- ایزوله بودن منابع داده
منابع داده چندگانه و توزیع شده، اغلب بصورت ایزوله و جدا از هم هستند. برای درک بهتر یک مشکل کسب و کار، نیاز است که داده‌های مرتبط از طریق یکپارچه‌سازی متمرکز و ارتباطات محلی جمع آوری شود. به همین دلیل، برنامه‌ریزی و همکاری عاملها، عاملهای موبایل، و ارتباطات و مذاکرات عاملها میتوانند سودمند باشند.
۳-۳-۵-۲- پویایی منابع داده و دستگاه‌های محاسباتی
پویایی داده و دستگاه نیازمند ادراک و بکارگیری الگوریتمهای دادهکاوی بر پایه‌ی موبایل است. عاملهای موبایل میتوانند بخوبی با پویایی وفق پیدا کنند.
۳-۳-۵-۳- دادهکاوی توزیع شده‌ی تعاملی
نیاز به عامل‌هایی است تا بتوان میزان نظارت و مداخله کاربر در اجرای فرایند دادهکاوی را محدود کرد.
۳-۳-۵-۴- انتخاب منابع و جمع‌اوری داده پویا
یکی از چالش‌های یک عامل دادهکاوی هوشمند، فعالیت در محیطهای توزیع شده‌ی باز و پیگیری کارهای دادهکاوی است. به عنوان مثال، در جایی که ممکن است میزان دسترسی به داده‌های سایت‌ها و محتوای آنها در هر زمانی تغییر کند، کشف و انتخاب منابع مرتبط یک چالش است. عاملهای دادهکاوی، منابع داده را بطور پویا و بر اساس معیارهای تعیین شده، از قبیل میزان، نوع، و کیفیت در منبع موردنظر، شبکه واقعی، و بار شدن سرور دادهکاوی انتخاب میکنند. عاملها میتوانند برای کنترل و مدیریت گرداوری داده مورد استفاده قرار بگیرند.
۳-۳-۵-۵- محدودیتهای زمانی در منابع داده توزیع شده
بسیاری از دادههایی که در مخزن‌های متفاوتی توزیع شدهاند، وابسته به زمان هستند.
۳-۳-۵-۶- دادهکاوی توزیع شده با چند استراتژی
برای برخی از برنامه‌های پیچیده، ترکیبی مناسب از چندین تکنیک دادهکاوی بهتر و سودمندتر از اجرای یک تکنیک خاص عمل میکند. عاملهای دادهکاوی، میتوانند یاد بگیرند، آنها بر اساس نوع داده سایت‌های مختلف و اعمال کاوشی که باید صورت گیرد، از بین فعالیت‌هایشان انتخاب میکنند.
۳-۳-۵-۷- دادهکاوی توزیع شده‌ی مشارکتی
عاملهای دادهکاوی، میتوانند بطور مستقل بر روی داده‌های سایت‌های مختلف، اعمال کاوش را انجام دهند و در نهایت مدل‌های حاصله را با هم ترکیب کنند. همچنین میتوانند دانشی که استخراج کردهاند را به اشتراک بگذارند تا از قابلیت‌های سایر عاملها بهره‌مند شوند.
۳-۳-۵-۸- پوشیدگی داده‌های منبع
داده‌های محلی توزیع شده، براساس مسائل پوشیدگی داده‌ها، اجازه ندارند استخراج و با سایر منابع بطور مستقیم، یکپارچه شوند. یک عامل دادهکاوی که مجوز دسترسی و پردازش داده‌ها را بصورت محلی دارد، میتواند الگوهای محلی شناسایی شده را برای ترکیب با یافتههای سایر منابع به کار بندد.
۳-۳-۵-۹- محدودیتهای سازمانی در منابع داده توزیع شده
در برخی از سازمانها، منطق کسب و کار، فرایندها، و گردش کاری، ترتیب منابع داده و دسترسی به آنها را تعیین میکنند. بنابراین پیچیدگی دادهکاوی توزیع شده را افزایش می‌دهند. عامل‌هایی که در هریک از منابع قرار گرفتهاند میتوانند با یکدیگر ارتباط برقرار کنند و عاملهای الگوریتم دادهکاوی را انتقال دهند.
۳-۴- الگوریتمهای کشف قوانین انجمنی
۳-۴-۱- الگوریتم AIS
این الگوریتم از اولین الگوریتمهایی بود که برای استخراج همه اقلام مکرر از پایگاه داده در سال ۱۹۹۳ توسط اگریوال، ایمیلنسکی و سوامی[۳۸] ابداع گردید. نام این الگوریتم برگرفته از حروف اول نام ابداع کنندگان آن میباشد. این الگوریتم چندین گذر بر روی پایگاه داده انجام داده و در هر گذر همه تراکنش‌ها را می‌پیماید. گام‌های این الگوریتم به صورت زیر میباشند:
- برای هر یک از تراکنش‌ها بزرگ‌ترین قلم انتخاب میشود.
- اقلام کاندید (Ck) با گسترش هر یک از این اقلام مکرر به سایر اقلام، در هر تراکنش ساخته میشوند.
بنابراین، در گام اول پشتیبان هر قلم محاسبه شده و آن‌هایی که بیشتر از حداقل پشتیبان هستند در L1 ثبت میشوند. در گام دوم به ازای تک تک اقلام مرحله‌یL1 به پایگاه داده‌ی اصلی برگشته و تمامی مجموعه‌های دوتایی را ساخته و پشتیبان آنها را محاسبه میکنیم. خروجی این مراحل در ۲C ذخیره میشود. در گام سوم همانند مرحله قبل به محاسبه ۳C میپردازیم این اعمال را تا جایی ادامه میدهیم که دیگر مجموعه مکرر جدیدی اضافه نشود.
از معایب این روش این است که در هر گذر تعدادی از اقلام انتخاب شده که حداقل مقدار پشتیبان (در اینجا ۲) را نداشته و باید کنار گذاشته شوند.
۳-۴-۲- الگوریتم SETM
این الگوریتم توسط هوتسما[۳۹] در سال ۱۹۹۵ ابداع شد و در سال ۱۹۹۶ نسخه دوم آن به منظور محاسبه اقلام مکرر در SQL توسط اسریکنت[۴۰] مطرح شد در این الگوریتم هر یک از اعضای مجموعه به فرم <TID,Itemset> هستند.
مشابه الگوریتم AIS، این الگوریتم نیز چندین گذر بر روی پایگاه داده انجام میدهد. گام‌های این الگوریتم به قرار زیر میباشند:
پشتیبان هر یک از اقلام به طور مجزا محاسبه و بزرگ‌ترین آنها انتخاب میشوند. اقلام کاندید (CK) با گسترش هر یک از این قلم‌های مکرر به سایر اقلام در هر تراکنش ساخته میشوند. علاوه بر آن در این مرحله TIDهای مربوط به هر یک از Ckها را در یک ساختار ترتیبی به نام ۲C نگهداری کرده و سپس پشتیبان هر یک از CKها با جمع کردن تعداد تکرار آنها در مرحله قبل محاسبه شده و ۳C ساخته میشود. این مراحل ادامه پیدا کرده تا جایی که دیگر مجموعه مکرر جدیدی اضافه نشود. عمده‌ترین معایب این الگوریتم ناشی از تعداد CKها است و از آنجایی که مقدار TID هر CK، نگهداری میشود، فضای بیشتری اشغال میشود.
معایب الگوریتمهای SETM و AIS :
- این الگوریتمها خیلی کند هستند.
- اقلام زیادی با «پشتیبانی» پایین‌تر از حداقل پشتیبان در نظر گرفته شده توسط کاربر، تولید میکنند.
۳-۴-۳- الگوریتم Apriori یا پیشینار
این الگوریتم در سال ۱۹۹۶ توسط چیونگ[۴۱] ابداع شد و یکی از مهم‌ترین یافته‌ها در تاریخ استخراج قواعد انجمنی است. در این الگوریتم از این حقیقت که همه زیرمجموعه‌های اقلام مکرر، خود نیز مکرر هستند و اقلام باید بر مبنای قاعده ترتیب الفبا مرتب باشند، استفاده شده است. تفاوت اساسی این الگوریتم با الگوریتمهای دیگر در روش محاسبه اقلام Ck و گزینش آنها برای مراحل بعدی است. در الگوریتمهای دیگر اقلام مکرر با گسترش به هر یک از اقلام مجزا (که ممکن است خودشان مکرر نباشند) در هر یک از تراکنش‌ها ایجاد می‌شدند تا CKها را تولید کنند و به این ترتیب Ckهای زیادی تولید شده که باید در مراحل بعدی کوچک می‌شدند و پایگاه داده چندین بار پیموده می‌شد، در حالی که این الگوریتم پایگاه داده را فقط یک بار می‌پیماید و اقلام مکرر را پیدا میکند.
الگوریتم Apriori این موضوع مهم را مدنظر قرار میدهد و Ckها را با اتصال اقلام مکرر حاصل از فاز قبلی و حذف آن‌هایی که در فاز قبلی بوده‌اند، بدون توجه به هر یک از تراکنش‌ها به طور مجزا تولید میکند. بدین ترتیب تعداد Ckهای اضافی به طور چشمگیری کاهش می‌یابند.
تذکر: Ckها در این الگوریتم مطابق الگوریتم زیر محاسبه میشوند (شکل ۳-۴):
|
Apriori-gen(Lk-1)
Join step
Insert into Ck
Select p. item1, p. item2, …, p. itemk-1 from Lk-1 p, Lk-1 q
Where p. item1=q. item1, …, p. itemk-2= q. itemk-2,
Prune step
p. itemk-1 < q. itemk-1
for all item sets c Ck do
for all (k-1)-subsets s of c do
if (s Lk-1) then
delete c from Ck;
|
شکل ۳- ۴: الگوریتم Apriori
|
فقط آن‌هایی که از حداقل پشتیبان بزرگ‌تر یا مساویند را در Lk قرار میدهد.
Ckهای جدید را مطابق الگوریتم بیان شده تولید میکند.
بزرگ‌ترین اقلام را در نظر میگیرد.
پشتیبان هر یک از اقلام Ck را محاسبه میکند.
|
L1 = {large 1-itemsets}
For (k=2; Lk-1 ≠ ; k++) do begin
Ck = apriori-gen(Lk-1);
for all transactions t D do begin
Ct = subset(Ck, t);
for all candidates c Ct do
c.count++;
end
end
Lk = {c Ck|c.count minsup};
end
Answer =
|
شکل ۳- ۵: توضیح الگوریتم Apriori
تفاوت عمده این الگوریتم با الگوریتمهای دیگر در حجم محاسبات کمتر آن است. در این الگوریتم اقلام زاید کمتری در هر مرحله ایجاد شده و با آزمایش‌های مختلفی که برای کشف اقلام مکرر توسط ۶۰۰۰/IBM RS انجام شد مشخص شد که این الگوریتم عملکرد بسیار بهتری نسبت به الگوریتمهای قبلی دارد. اما از معایب این الگوریتم، این است که برای محاسبه پشتیبان اقلام کاندیدا، الگوریتم همه تراکنش‌ها را بررسی میکند و بنابراین نیازمند زمان زیادی است.
۳-۴-۴- الگوریتم AprioriTid
همان گونه که قبلاً نیز ذکر شد الگوریتم Apriori در هر گذر همه‌ی پایگاه داده را می‌پیماید تا پشتیبان‌ها را محاسبه کند و پیمودن همه‌ی پایگاه داده ممکن است در همه‌ی فازها مورد نیاز نباشد. بر مبنای این مشکل، الگوریتم دیگری بنام AprioriTid ابداع شد. این الگوریتم نیز روشی مشابه با الگوریتم Apriori، برای محاسبه Ckها در هر فاز به کار میبرد. تفاوت عمده‌ای که این الگوریتم با الگوریتم Apriori دارد در این است که این الگوریتم کل پایگاه داده را برای محاسبه پشتیبان بعد از مرحله اول نمی‌پیماید و از مجموعه برای محاسبه پشتیبان استفاده میکند. مشابه الگوریتم SETM اعضای این الگوریتم نیز به فرم <TID, Xk> ذخیره میشوند (شکل ۳-۶).
| |
L1 = {large 1-itemsets}
اقلام با بیشترین فراوانی را محاسبه میکند.
= database D;
For (k=2; Lk-1 ≠ ; k++) do begin
موجودیت‌های خالی را حذف میکند.
پشتیبان را محاسبه میکند.
Ckهای جدید را مطابق الگوریتم بیان شده تولید میکند.
مقداردهی اولیه پایگاه داده موجود
یک انباره‌ی جدید ایجاد میکند.
فقط آن‌هایی که از حداقل پشتیبان بزرگ‌تر یا مساویند را در Lk قرار میدهد.
Ck = apriori-gen(Lk-1);
for all entries t do begin
for all candidates c Ct do
c.count++;
end
end
Lk = {c Ck|c.count minsup}
end
Answer = UkLk ;
|
شکل ۳- ۶: الگوریتم AprioriTid
مزایای الگوریتم: از مزایای عمده این روش این است که در فازهای آخر اندازه بسیار کوچک‌تر از کل اندازه پایگاه داده شده و باعث صرفه جویی در زمان میشود. این الگوریتم از نظر عملکرد نیز بر الگوریتمهای SETM و AIS برتری دارد. مشکلی که ممکن است وجود داشته باشد مدیریت حافظه است و دیده میشود که این الگوریتم در فازهای انتهایی ( اندازه کوچک‌تر میشود ) عملکرد بهتری نسبت به الگوریتم Apriori دارد.
معایب الگوریتم: در فازهای اولیه های تولید شده بزرگ بوده و فضای زیادی اشغال میکنند. بنابراین مدت زمانی معادل زمان الگوریتم Apriori را نیازمند است. اگر فضای اشغال شده بیشتر از حافظه در دسترس باشد، هزینه اضافه‌ای را نیز در بر خواهد داشت.
۳-۵- جمعبندی
در این فصل، ابتدا شرح مختصری بر دادهکاوی توزیع شده داده شد. همانطور که گفته شد این تکنولوژی با مشکلات پیچیدهای، مانند منابع دادهای بزرگ، مشکلات انتقال داده، ترکیب داده‌ها، و غیره روبرو است. سپس عاملها و سیستمهای چند عامله، و مزایای بهرهگیری ازین تکنولوژی در دادهکاوی و دادهکاوی توزیع شده مورد بررسی قرار گرفت. در نهایت الگوریتمهای مطرح در حوزه کشف قوانین انجمنی معرفی شدند. در فصل بعد، محاسبات و یافتههای تحقیق ارائه خواهند شد.
فصل چهارم محاسبات و یافتههای تحقیق
۴-۱- مقدمه
در این فصل قصد داریم، معماری پیشنهادی برای داده کاوی برپایه‌ی سیستمهای چند عامله را ارائه کرده و به شرح مختصری از داده کاوی توزیع شده بپردازیم.
مباحث تحقیقاتی باز بسیاری در حوزه‌ی دادهکاوی بر پایه‌ی عامل وجود دارد. در تاسیس یک زیرساخت دادهکاوی سازمانی بر پایه‌ی عامل، ممکن است یک نفر بر روی تکنیکهای طراحی و تجزیه و تحلیل سیستم بررسی اجتماع محور و سازمانی برای سیستمهای بر پایه‌ی عامل در مقیاس بالا مطالعه کند. به همان نسبت، راه حل‌هایی برای یکپارچه‌سازی برنامه‌ها بر پایه‌ی سرویس عامل، آماده‌سازی داده توزیع شده، مشارکت عامل توزیع شده و محاسبات عامل موازی باید درنظر گرفته شود. در بسیاری از حالات دادهکاوی، افراد باید بر روی الگوریتمهایی که بتوانند با تغییرات پویای داده و درخواستهای پویای کاربر سازگاری پیدا کنند، مطالعه و بررسی انجام دهند. الگوریتمهای دادهکاوی سازگارپذیر و اتوماتیک باید مورد بررسی قرار گیرند. در ادامه لیستی از برخی از مباحث باز این حوزه آورده شده است:
کاوش و مدلسازی فعالیت
دادهکاوی سازمانی بر پایه‌ی عامل
زیرساخت دادهکاوی بر پایه‌ی عامل
مدیریت پروژه و فرایند کاوش بر پایه‌ی عامل
دادهکاوی توزیع شده بر پایه‌ی عامل
یادگیری توزیع شده بر پایه‌ی عامل
محاسبات گرید بر پایه‌ی عامل
دادهکاوی تعاملی بر پایه‌ی عامل
دادهکاوی موازی بر پایه‌ی عامل
کاوش وب برپایه‌ی عامل
مدیریت دانش در دادهکاوی توزیع شده بر پایه‌ی عامل
دادهکاوی همیاری انسان با عامل
عاملهای شبکه در کشف دانش و سرویس‌دهی توزیع شده
یادگیری خودمختار
پیش‌پردازش داده بر پایه‌ی عامل بصورت توزیع شده
یادگیری توزیع شده
کشف دانش بر پایه‌ی عاملهای موبایل
پروتکل‌های دادهکاوی بر پایه‌ی عامل
شکل ۴-۴ چارچوبی را نشان میدهد که شامل مولفه‌های تحقیقاتی این حوزه است که عبارتند از: اساس و بنیان کاوش عامل، پردازش داده بر پایه‌ی عامل، کشف دانش بر پایه‌ی عامل، سیستمهای چند عامله بر پایه‌ی کاوش، پردازش اطلاعات بر پایه‌ی عامل، مباحث مشترک در کاوش عامل، سیستمهای کاوش عامل، برنامه‌های کاربردی کاوش عامل، مدیریت دانش کاوش عامل، و ارزیابی کارایی کاوش عامل.
شکل ۴- ۱: چارچوب تحقیقاتی کاوش- عامل
این پژوهش در حوزه کشف دانش بر پایه‌ی عامل قرار دارد. عملکرد کلی معماری پیشنهاد شده به این شکل است که پس از آنکه کاربر وارد سیستم شد و با موفقیت رجیستر کرد، یک عامل کاربر تولید میشود که نشان دهنده‌ی این کاربر است، این عامل در سیستم مستقر میشود، با کاربر ارتباط برقرار میکند، از وی در ارتباط با دانش مورد نیازش سوال می‌پرسد، و پارامترهای ورودی آن را دریافت میکند. سپس، یک گروه کاری عامل فعال میشود و عملیات داده کاوی را راه اندازی میکند تا داده کاوی را شروع کند. پس از آنکه نتیجه‌ی کاوش به کاربر ارائه شد، از او پرسیده میشود که آیا دانش دیگری را نیز می‌خواهد مورد جستجو قرار دهد یا خیر. اگر درخواست برای جستجوی جدید وجود داشت، منتظر می‌ماند تا کاربر پارامترهای لازم را وارد کند، و اگر وجود نداشت، عامل کاربر حذف میشود. شکل ۴-۱۴ یک نمودار گردش کاری را نشان میدهد که برپایه‌ی سیستم داده کاوی توزیع شده‌ی چندعامله است.
شکل ۴- ۲: گردش کار سیستم داده کاوی توزیع شده بر پایه سیستم چند عامله
۴-۲- معماری پیشنهادی برای داده کاوی توزیع شده برپایه‌ی سیستمهای چند عامله
با توجه به کارهایی که یک سیستم داده کاوی توزیع شده باید انجام دهد، عملکرد سیستم به دو بخش تقسیم میشوند، بخش توابع تعاملات کاربر، و بخش تابع پیش‌پردازش داده و تابع داده کاوی. هر تابع با یک عامل مرتبط است، بنابراین این سیستم به طور عمده از دو نوع عامل تشکیل شده است: عامل کاربر، عامل پیش‌پردازش داده و عامل داده کاوی. برای کاوش بر روی داده‌های سایت‌های مختلف، عامل پیش‌پردازش داده و عامل داده کاوی در قالب یک زوج در نظر گرفته میشود، و در سایت‌هایی که قرار است مورد کاوش قرار گیرند، توزیع میشوند. عامل پیش‌پردازش داده، داده‌ها را برای عامل داده کاوی آماده میکند. عامل داده کاوی، کار داده کاوی را به پایان می‌رساند و نتایج را برای یکپارچه شدن و دست‌یابی به نتایج درست به سایت مرکزی داده کاوی ارائه میدهد.
۴-۲-۱- معماری چهار لایه‌ی پیشنهادی
همان طور که در ادامه خواهید دید، معماری پیشنهادی به صورت چهار لایه است که توضیح هر لایه به شرح ذیل میباشد:
۴-۲-۱-۱- لایه‌ی اول، لایه‌ی کاربر
همانطور که در شکل ۴-۹ نشان داده شده است، اولین لایه از این معماری، شامل کاربران، عامل کاربر و پایگاه داده اطلاعات کاربر است.
شکل ۴- ۳: لایه‌ی کاربر
عامل کاربر: وظیفه‌ی اصلی این عامل، تکمیل تعاملات بین سیستم و کاربر است. بدین منظور عامل کاربر یک واسط تعاملی ارائه میدهد که از طریق آن کاربر درخواستهای خود را مطرح میکند، و نتایج داده کاوی به وی نشان داده میشود. هوشمندی عامل کاربر در بلند مدت نمود پیدا میکند، بدین ترتیب که در فرایند داده کاوی، اطلاعات درخواستهای کاوش کاربر، در پایگاه داده اطلاعات وظیفهها، که میتواند نشان دهنده‌ی علاقه‌مندی‌های کاربر باشد، ذخیره می شود. همچنین این اطلاعات جمع آوری شده می تواند تأثیر شایانی در بهبود کیفیت خدمات سیستم داشته باشند. این عامل برای پردازش درخواستهای کاربر با عامل اولویت دهی وظیفهها در ارتباط است.
پایگاه داده اطلاعات کاربر: در این پایگاه داده رکوردها و اطلاعات کاربر ذخیره می شود.
۴-۲-۱-۲- لایه‌ی دوم، لایه‌ی مدیریت
همانطور که در شکل زیر می‌بینید، اجزای این لایه شامل عامل ثبت، عامل اولویت دهی وظیفهها، عامل وظیفه، عامل داده کاوی عمومی و پایگاه داده اطلاعات وظیفهها میباشد.
شکل ۴- ۴: لایه‌ی مدیریت
عامل اولویتدهی وظیفهها: این عاملها، تعداد درخواستها در یک بازه زمانی خاص و اطلاعات درخواستها را ثبت می کنند. سپس وزنی را برای هر درخواست بر اساس اطلاعات ثبت شده تعیین میکند که در واقع هدف اصلی این عامل است. زمانی که سیستم و شبکه در حالت بیکار قرار دارند این عامل می تواند اطلاعات ثبت شدهای که وزنشان بیشتر از مقدار بحرانی است را پیدا کند. بر طبق این وزنها اطلاعات مورد نیاز کاوش برای درخواستها به عامل وظیفه فرستاده می شود.
عامل وظیفه: این عاملها، عاملهای موقتی هستند که به طور اتوماتیک توسط عامل اولویت دهی وظیفهها تولید میشوند تا درخواستهای داده کاوی را مورد بررسی قرار دهند، و تا زمانی که درخواست مربوطه به طور کامل انجام شود وجود دارند. مسئولیت ارتباط با عاملها و در صورت لزوم فعال‌سازی و همگام سازی آنها بر عهده عامل وظیفه است. به طور کلی، زمانی که یک عامل وظیفه ایجاد میشود، این عامل از گروهی از عاملهای پیش‌پردازش داده و داده کاوی سرویس مورد نظر را درخواست میکند و نتیجه عمل کاوش را به عامل کاربر ارائه میدهد.
پایگاه داده اطلاعات وظیفهها: برای ذخیره اطلاعات درخواستهایی که توسط عامل اولویت دهی از عامل کاربر دریافت می شود، مورد استفاده قرار میگیرد.
عامل ثبت: این عامل از توابعی تشکیل شده است که وظیفه کنترل انواع دسترسی، تغییرات، ثبت و غیره را برای کاربران مختلف اعم از ادمین، کاربران عادی، کاربران توسعه دهنده وغیره دارد.
۴-۲-۱-۳- لایه‌ی سوم، لایه پردازش
همانطور که در شکل ۴-۱۱ نشان داده شده است، این لایه شامل عامل داده کاوی و عامل پیش پردازشی است.
شکل ۴- ۵: لایه‌ی پردازش
عامل پیش‌پردازش داده: این عامل در سایت محلی قرار دارد، و اطلاعاتی در ارتباط با منابع داده آن سایت دارد. وظیفه‌ی اصلی آن، انجام عملیات پیش پردازشی و ارائه داده نرمال است. بدین منظور، داده مورد نظر را از منابع داده استخراج میکند، عملیات پیش پردازشی همچون نرمال سازی داده‌ها را انجام میدهد و در نهایت داده را به عامل داده کاوی ارائه میدهد. این عامل از چهار تابع اصلی استخراج داده‌ها، پاک‌سازی، تبدیل فرمت، و ساده سازی داده‌ها تشکیل شده است. داده مورد نظر یک عمل کاوش، ممکن است یک مجموعه داده، و یا بخشی از یک یا تعدادی مجموعه داده باشد.
عامل داده کاوی: هرکدام از عاملهای داده کاوی، پیادهسازی یک الگوریتم یا تکنیک دادهکاوی خاص هستند. عاملهای داده کاوی، شامل متد‌هایی برای مقداردهی اولیه، انجام عمل کاوش، و ارائه نتایج به عامل وظیفه مورد نظر هستند. با توجه به تابع عامل داده کاوی، میتوان آن را به دو جزء تقسیم کرد: عامل داده کاوی عمومی، و عامل داده کاوی محلی. عامل داده کاوی عمومی در سایت مرکزی قرار دارد و بر روی دادهای کار میکند که نتایج حاصل از کار عاملهای داده کاوی محلی در سایت‌های مختلف است. عامل داده کاوی محلی عمل کاوش در سایت‌های محلی را انجام میدهد و از دادهای استفاده میکند که عامل پیش‌پردازش داده در آن سایت در اختیار وی گذارده است. همچنین عامل داده کاوی محلی این قابلیت را دارد که هنگامی که سیستم در حالت بیکار قرار دارد می تواند روی الگوریتمهای موجود بررسیهای لازم را انجام دهد و از بین آنها مؤثرترین الگوریتم را برای انجام عمل کاوش انتخاب کند.
کتابخانه الگوریتمها: در این کتابخانه الگوریتمهای کاوش و نتیجه استفاده از هر الگوریتمی در کاوش مورد نظر، ذخیره میشوند که این الگوریتمها میتوانند حذف، بروز و توسعه داده شوند.
۴-۲-۱-۴- لایه‌ی چهارم، لایه‌ی منابع
این لایه شامل منابع داده میباشد (شکل ۴-۱۲).
شکل ۴- ۶: لایه‌ی منابع
همانطور که در بالا ذکر شد، هر لایه از این معماری از اجزایی تشکیل شده است. برای پیادهسازی ارتباطات سیستم بین عاملهای مختلف از سرور ارتباطی استفاده میشود، و هر عامل از طریق این سرور، اطلاعات را به مرحله بعد و عامل بعد انتقال میدهد. تصویر کلی این معماری در شکل ۴-۱۳ نشان داده شده است.
شکل ۴- ۷: معماری پیشنهادی برای داده کاوی توزیع شده برپایه‌ی سیستمهای چند عامله
در این سیستم، عامل کاربر باید ارتباط متقابل با سایر عاملها برقرار کند، و تعاملات لازم را انجام دهد تا درخواست کاوش کاربر به اتمام برسد. روش تخصیص کار به هر عامل به شرح زیر است:
کاربر کار را به عامل کاربر میدهد، و بدین ترتیب یک کار داده کاوی ایجاد میشود.
از طریق عامل وظیفه، کار کاوش به عامل پیش پردازش داده مستقر در هر سایت داده میشود.
پس از اتمام کار عامل پیش‌پردازش داده، نتایج آن به عامل داده کاوی این سایت تحویل داده میشود تا عملیات داده کاوی را بر روی داده انجام دهد.
پس از اینکه نتایج داده کاوی هر سایت توسط عامل وظیفه جمع آوری شد، نتایج به عامل داده کاوی عمومی در سایت مرکزی تحویل داده میشود، تا این عامل، نتایج را یکپارچه کند.
عامل داده کاوی عمومی نتایج نهایی را آماده میکند و در اختیار عامل کاربر قرار میدهد.
عامل کاربر نتایج را به کاربر ارائه میدهد.
۴-۳- مطالعه موردی
۴-۳-۱- تحلیل عملکرد الگوریتمهای کشف قوانین انجمنی
تفاوت عمده الگوریتمهایی که در فصل قبل شرح داده شد، در روش تولید اقلام مکرر (L) میباشد. عملکرد الگوریتمها در دو نوع داده شامل داده‌های آزمایشی و داده‌های واقعی با یکدیگر مقایسه شدهاند. پارامترهای به کار رفته به منظور مقایسه این الگوریتمها به قرار زیر میباشند:
:D تعداد تراکنش‌ها
T5.I2.D100k ⇒ T=5, I=2, D=100,000
T10.I2.D100k
T10.I4.D100k
T20.I2.D100k
T20.I4.D100k
T20.I6.D100k
:T میانگین اندازه تراکنش‌ها
:I میانگین اندازه اقلام مکرر
:L تعداد اقلام مکرر
:Nتعداد اقلام
:K 1000
تعداد اقلام = ۱۰۰۰
نمادی بالای هر کدام از نمودارها نوشته شده است که معرف تراکنش‌ها، میانگین اندازه اقلام مکرر و میانگین اندازه تراکنش‌ها میباشد به عنوان نمونه K100D2I5T عبارت است از ۱۰۰۰۰=D و ۲=I و ۵=T و به این معنی است که آزمایش برای تعداد تراکنش‌های ۱۰۰۰۰ و میانگین اندازهی اقلام مکرر ۲ و میانگین اندازهی تراکنش‌های ۵ انجام شده است. محور افقی نیز حداقل پشتیبان است. آزمایش‌های مختلفی برای نمونه‌های متفاوت انجام شده است و نتایج حاصله در نمودارهای زیر آمده‌اند. البته زمان‌های ناشی از اجرای الگوریتم SETM آن قدر زیاد بوده‌اند که نتوانسته‌اند در نمودارهای زیر بگنجند (نمودار ۴-۱).
با دقت در این نمودارها در می‌یابیم که: الگوریتم Apriori همواره بر الگوریتم AIS غالب است و Apriori در اندازه‌های بزرگ بهتر از AprioriTid عمل میکند. در الگوریتم AprioriTid مقادیر بجای پایگاه داده در نظر گرفته میشوند. اگر بتواند در حافظه جای گیرد، این الگوریتم سریع‌تر از Apriori عمل خواهد کرد. زمانی که خیلی بزرگ باشد، نمیتواند در حافظه جای بگیرد. و در نتیجه زمان محاسبه بسیار بالا می‌رود، بنابراین الگوریتمApriori سریع‌تر از الگوریتم AprioriTid عمل خواهد کرد.
|
T10.I2.D100k
T20.I2.D100k
|
T5.I2.D100k
T10.I4.D100k
|
| |
|
| T20.I6.D100k |
T20.I4.D100k |
نمودار ۴- ۱: تغییرات رفتار الگوریتمهای مختلف
داده‌های واقعی
فروشگاه خرده فروشی شامل:
- ۶۳ بخش
- ۴۶۸۷۳ تراکنش (با میانگین اندازه ۲/۴۷)
نمودار ۴- ۲: تغییرات رفتار الگوریتمهای مختلف در یک فروشگاه خرده فروشی
همان گونه که مشاهده میشود در اینجا اندازه پایگاه داده کوچک است و بنابراین مشکلی با حافظه نخواهد داشت و در نتیجه الگوریتم AprioriTid در زمان کمتری نسبت به الگوریتم Apriori اجرا میشود. بنابراین کدامیک بهتر است؟ ApririTid یا Apriori
به منظور پاسخ به این سوال مقایسه‌ای بین این دو الگوریتم در طی فازهای مختلف صورت گرفته است که نتایج آن در نمودار زیر آمده است (نمودار ۴-۳):
نمودار ۴- ۳: مقایسه‌ی رفتار الگوریتمهای AprioriTid و Apriori
در مراحل انتهایی به اندازه کافی کوچک شده و حافظه مصرفی کم میشود. بنابراین از فاز ۴ به بعد زمان اجرای الگوریتم AprioriTid بسیار کم شده و تقریباً این زمان برابر صفر شده است. به منظور استفاده بهینه از این دو الگوریتم، الگوریتم جدیدی بنام AprioriHybrid شکل گرفت. خصوصیات این الگوریتم به ترتیب زیر است:
این الگوریتم در فازهای اولیه اجرا مطابق الگوریتمApriori عمل میکند.
اندازه تخمینی به صورت زیر محاسبه میشود:
تعداد تراکنش‌ها + حاصل جمع پشتیبان همه اقلام = اندازه تخمینی
وقتی که ها به اندازه کافی کوچک شده و حافظه مصرفی کم میشود به الگوریتم AprioriTid سوئیچ کرده و مطابق این الگوریتم پیش می‌رود.
اگر چه تغییر از Apriori به AprioriTid زمانبر است، اما در بسیاری از موارد نتایج مثبتی دارد. در نمودارهای زیر (نمودار ۴-۴)، عملکرد سه الگوریتم اخیر با یکدیگر مقایسه شده است. در تمامی این نمودارها نشان داده شده است که الگوریتم ترکیبی زمان اجرای کمتری نسبت به Apriori و AprioriTid دارد.
| T10.I4.D100k |
T10.I2.D100k |
| T20.I6.D100k |
نمودار ۴- ۴: مقایسه عملکرد الگوریتمهای AprioriTid ، Apriori Hybrid و Apriori در آزمایش‌های مختلف
۴-۳-۲- F-Trade: یک سیستم کاوش عامل برای سرویس‌های مالی
F-Trade مخفف عبارت Financial Trading Rules Automated Development and Evaluation به معنای توسعه و ارزیابی اتوماتیک قوانین تبادلات مالی است، که یک زیرساخت سازمانی اتوماتیک بر مبنای وب برای استراتژی‌های تجاری و دادهکاوی بر روی داده‌های سرمایه یا سهم بازار است. این سیستم، سرویس‌های ارتباطات، مدیریت، و پردازش داده ارائه میدهد. F-Trade از رقابت اتوماتیک آنلاین، و ساخت واسط ورودی یا خروجی اتوماتیک، برای سیگنال‌ها و قوانین تجاری، و الگوریتمهای دادهکاوی، منابع داده، و کامپوننت‌های سیستم پشتیبانی میکند. این سیستم، پشتیبانی انعطاف‌پذیر و قدرتمندی را برای تست آنلاین[۴۲]، آموزش یا تست، بهینه‌سازی و ارزیابی استراتژیها و الگوریتمهای دادهکاوی فراهم می‌آورد. کاربران میتوانند به سیستم متصل شوند، مشترک شوند، و استراتژی‌های تجاری و الگوریتمهای دادهکاوی را به صورت مشارکت انسان- ماشین مورد نظارت و بهینه‌سازی قرار دهند.
F-Trade در Java agent services بر روی سیستم عاملهای ویندوز، لینوکس، و یونیکس ساخته شده است. از XML برای پیکربندی سیستم و مدیریت متادیتا استفاده شده است. یک سوپر- سرور به عنوان سرور برنامه عمل میکند، و دیگری به عنوان انبار داده. این سیستم به گونه‌ای ساخته شده که ارتباطات آنلاین با منابع داده توزیع شده همچون منابع داده خاص کاربر دارد.
نقشهای اصلی عاملها در سیستم F-Trade شامل معماری بر پایه‌ی سرویس با بهره گرفتن از عامل، ارتباطات متقابل انسانی بر پایه‌ی عامل، عامل برای مدیریت منابع داده، جمع آوری داده و ارسال عاملها به منابع داده، الگوریتمهای دادهکاوی و استراتژی‌های تجاری بر پایه‌ی عامل، عامل و پیشنهاد دهنده‌ی سرویس که الگوریتمها و قوانین مناسب را برای کاربران فراهم می‌اورد، و غیره است. دادهکاوی از چند جهت به سیستم کمک میکند، از قبیل عاملهای پیشنهاد دهنده‌ی الگوریتم یا قانون‌های تجاری بر پایه‌ی دادهکاوی، سرویس‌دهی کاربر بر پایه‌ی دادهکاوی، بهینه‌سازی عامل تجاری بر پایه‌ی دادهکاوی، قوانین تجاری کاوش در مجموعه جامع الگوهای تجاری، تصحیح پارامتر عاملهای الگوریتم از طریق دادهکاوی، و غیره. مباحث مشترک شامل نمایش دانش دامنه بر پایه‌ی آنتولوژی، درگیر شدن انسانها و ارتباطات متقابل انسان با الگوریتمها بر پایه‌ی عاملها، و سیستمی برای نظارت بر الگوریتم، بهینه‌سازی و ارزیابی.
با این زیرساخت، تاجران مالی و محققان، و داده‌کاوان مالی میتوانند الگوریتم‌هایشان را وارد سیستم کنند و بر روی بهبود کارایی آنها متمرکز شوند و توسط حجم عظیم داده‌های واقعی از بازارهای بین‌المللی، ارزیابی کنند. سرویس های سیستم شامل این موارد میشود: ۱) پشتیبانی از سرویس‌های تجاری، ۲) پشتیبانی از سرویس‌های کاوش، ۳) پشتیبانی از سرویس‌های داده، ۴) پشتیبانی از سرویس‌های الگوریتم، و ۵) پشتیبانی از سرویس‌های سیستم. هر کامپوننت سیستم، از طریق شمای XML ارتباط برقرار میکند که جزئیات کامپوننت‌ها را مشخص میکند و به عاملها اجازه‌ی آزمایش و استفاده از آنها را میدهد.
شکل ۴- ۸: چارچوب F-Trade
۴-۳-۳- دادهکاوی چند منبع بر پایه‌ی عامل
برنامه‌های دادهکاوی سازمانی، اغلب از منابع داده متعدد استفاده میکنند که توزیع شده و ناهمگن هستند و یکپارچه‌سازی آنها هزینه‌بر است. عاملهای دادهکاوی که هر کدام برای الگوریتمهای خاصی طراحی شدهاند بر روی کاوش الگوهای محلی در هر منبع داده‌ی مجزا تمرکز میکنند، و سایر عاملهای هماهنگ کننده با یکدیگر در ارتباطند تا کاوش الگوی توزیع شده را سازماندهی کنند، و عاملهای ادغام الگو، عمل تجمیع الگوهای محلی و ایجاد الگوهای کلی را کنترل میکنند.
به عنوان مثال، در شکل زیر اصول اساسی کاوش ترکیبی چند منبع در چارچوب MSCM-AKD[43] نشان داده شده است. سیستم میتواند توسط عاملها پیادهسازی شود. همانطور که در شکل ۴-۹ می‌بینید، این سیستم میتواند شامل عاملهای زیر باشد:
شکل ۴- ۹: چارچوب MSCM-AKD
عاملهای مدیریت منابع داده: کنترل کننده‌های داده و هماهنگ کننده‌های داده، که مسئولیت مدیریت ارتباطات مجموعه‌های داده، قسمت‌بندی داده‌ها و ارسال کاراهای دادهکاوی به مجموعه‌های داده را به عهده دارند. در یادگیری سازگار، کنترل کننده‌های تغییر داده توسعه می‌یابند تا تغییرات مهم داده را کنترل کنند.
عاملهای دادهکاوی محلی: داده‌کاوان m1 تا mN به منظور انجام دادن عملیات کاوش بر روی مجموعه‌های داده DB1 تا DBN.
عاملهای هماهنگ کننده دادهکاوی: وظیفه‌ی این عاملها، هماهنگ کردن زمانبندی کاوش الگوی محلی توسط داده کاوان بر روی هر مجموعه‌ی داده است. آنها این کار را برحسب یک پروتکل خاص، که میتواند یک دستور از قبل تعریف شده یا تصمیمی که بصورت پویا گرفته شده باشد، انجام می‌دهند. وظیفه‌ی دیگر این عامل، کنترل حالت اجرای یک داده‌کاو و سپس اطلاع دادن به سایرین برای شروع کاوش الگو است.
عاملهای مدیریت مجموعه الگوی محلی: عاملهای مدیریت الگوی محلی به مدیریت الگوهای محلی تولید شده توسط
