بخشی از مقاله
چكیده
مسئله استخراج مجموعه اقالم با ارزش باال توسعهای از مسئله کشف قوانین انجمنی است که دو هدف را دنبال میکنند؛ اول اینکه اقالم بتوانند بیش از یک بار در تراکنشها حضور داشته باشند و همچنین ارزش و اهمیت اقالم یكسان در نظر گرفته نشود. از نقاط ضعف روشهای ارائه شده برای این مسئله، این است که در آنها، مجموعه هایی با تعداد اقالم بیشتر، شانس بیشتری برای انتخاب شدن به عنوان مجموعهی با ارزش دارند. در صورتیكه در دنیای واقعی اینگونه نیست و مجموعههایی با تعداد اقالم باال ارزش زیادی برای تصممممیم گیری ندارند. به منظور حل این مشمممكل، الگوریتمهای متعددی معرفی شمممدهاند که هدفشمممان یافتن مجموعههایی با متوسط ارزش باالست. اگرچه تالشهای خوبی در این زمینه انجام پذیرفته است، هنوز نیاز به الگوریتمهایی با کارایی باالتر وجود دارد. در این تحقیق الگوریتم EFIM که رو شی کارا در ا ستخراج مجموعه هایی با ارزش باال ست را به گونهای تو سعه داده ایم که بتواند مجموعه اقالم با متو سط ارزش باال را بیابد. آزمایشهای انجام شده نشان میدهد روش پیشنهادی کارایی بهتری نسبت به روش MHAI دارد.
كلمات كلیدی:داده کاوی، الگوهای پرتکرار، الگوهایی با متوسط ارزش باال، الگوریتم .EFIM
-1 مقدمه
رشدروزاداون داده های دیجی تالی منجر به ظهور تکنیک های مت عدد دادهکاوی گردیده ا ست. یکی از این تکنیک ها ک شف الگوهای پرتکرار اسددت که اولین بار توسددر اگراوال در سددال 1993 معردی شددد [1] و از آن لحظدده تددا کنون تحتیتدداد گسددددتردهای در این زمیندده انجدداف گردتدده است.[2]–[4] در تعریف اولیه این مسئله، درض شده است که هر قلم داده1 تنها یک بار میتواند در هر تراکنش قرار بگیرد؛ همچنین ارزش و اهمیت اقالف باهم برابر اسددت. این در لالیسددت که در دنیای واقعی یک قلم داده میتوانددد بیش از یددک بددار در یددک تراکنش اتفددا بیددادتددد و همچنین ارزش اقالف ممکن اسددت متفاود باشددد به طور مثال در یک درو شگاه، یک م شتری میتواند از یک کاال چند عدد در سبد خرید خود قرار دهد و ارزش کاالها که مثال میتوان قیمت آنها در نظر گردت نیا با هم متفاود ا ست.
برای لل این م شکل، زمینه تحتیتاتی جدیدی ارائهشدددد که هددش اسدددتخراج مجموعه اقالف با ارزش اسدددت و نه صدددردا پرتکرار. در مسئله کشف الگوهای پرتکرار، بر اساس خاصیت بستار رو به پایین2 دضددای جسددتجو به سددادگی هرس میشددد. به عبارد دیگر، بر اسددددداس خاصددددیت apriori، اگر مجموعهای کم تکرار باشدددددد هی ابرمجموعهای از آن نمیتواند پرتکرار باشددد. بنابراین چنانچه در دضددای ج ستجو به یک مجموعه با تعداد کمتر از لدآ ستانه بر سیم میتوانیم زیر درخت آن مجموعه را در دضای جستجو هرس کنیم. این خاصیت برای ارزش مجموعه ها صاد نی ست و ممکن ا ست مجموعه ای کم ارزش باشد ولی با اداوده شدن یک قلم داده، با ارزش باال، ارزش ابرمجموعه آن بیشددددتر از لداقل آسددددتانه گردد.
بنابراین برای لل مسددددئله کشددددف مجموعه اقالف با ارزش، مهمترین چالش هرس دضای جستجو است و محت تان تالش کردهاند با باالتر براورد کردن3 ارزش یک مجموعه به ویژگی ای دسددت یابند که خاصددیت بسددتار رو به پایین را داشددته باشددد. اولین بار لین و همکارانش ویژگی TWU را معردی کردند[5] که برابر اسددت با مجموعه ارزش تراکنشددهای که شددامل مجموعه x هسددتند ودارای خاصیت بستار رو به پایین است. در داز اول تماف مجموعه های که دارای TWU باالتر از لداقل آ ستانه ه ستند پیدا می شود سپس با محاسددبه متدار واقعی ارزش این مجموعهها، در داز دوف مجموعههای با ارزش باال استخراج میشوند. الگوریتمهای متعددی در این خصوص ارائه شده است .[5]–[8]
از آنجاییکه ارزش یک مجموعه با مجموع ارزش اقالف آن برابر اسددددت، هر چه تعداد عناصدددر یک مجموعه بیشدددتر باشدددد ارزش کل آن بیشدددتر خواهد شدددد. بنابراین مجموعه های با طول بیشدددتر شدددانس بیشدددتری خواهند داشت که به عنوان الگوی با ارزش انتخاب شوند. برای برطرف کردن این م شکل، م سئله ک شف الگوهای با متو سر ارزش باال مطرح شد که با تت سیم کردن ارزش یک مجموعه بر تعداد اقالف آن، واب ستگی به طول را از بین میبردند. الگوریتمهای ارائه شددددده برای این مسددددئله جدیدبه سه گروه تتسیم میشوند. دسته اول مبتنی بر الگوریتم apriori بوده و به صورد مرلله ای و با تولید مجموعه های کاندید الگوهای با متوسددددر ارزش باال را تولید میکنند.[9], [10] این روشددددها نیاز به پیمای شهای متعدد پایگاه داده و تولید مجموعههای کاندید دارند.
د سته دوف روشددهای مبتنی بر درخت هسددتند که با نگهداری مجموعه داده در درخت و پردازش درخت به صورد بازگشتی بدون نیاز به اسکن مجدد میتواننددد الگوهددای بددا ارزش را بیددابنددد.[11], [12] گروه سددددوف، الگوریتمهای مبتنی بر لیسددددت هسددددتند که با ذخیره اطالعاد الزف در لیستها و ترکیب آنها به صورد اول عمق میتوانند الگوهای باارزش را بیابند.[13]–[15] با وجود ارائه شددددن روشدددهای متعدد، هنوز نیاز به الگوریتمهای با کارای باالتر الساس میشود.در این تحتیق الگوریتم EFIM [7] را گسددترش دادهایم. این الگوریتم، روشی کارا در کشف مجموعه های با ارزش باال است. هدف از روش پیشددنهادی این اسددت که با تغییر در مرالل مختلف الگوریتم EFIM و روشددهای هرس تعریف شددده در آن، بتوان الگوهای با متوسددر ارزش باال را استخراج نمود. ساختار ادامه الگوریتم به شرح زیر است: بخش دوف به ب یان مسددددئ له و کار های ان جاف پتیرد ته قبلی میپردازد.روش پیشددنهادی در دصددل سددوف تودددیو داده خواهد شددد. نتای آزمایشددها و ارزیاب ها در بخش چهارف ارائه شدددده و در نهایت بخش پنجم شدددامل نتیجه گیری است.
-2 تعریف مسئله و کارهای انجام شده قبلی
در این دصددل ابتدا مسددئله کشددف مجموعه اقالف با ارزش متوسددر باال تعریف شده و سپس به مرور کارهای انجاف شده قبلی میپردازد.
-2-1 بیان مسئله
درض کنیددد = { 1, 2, … , } مجموعددهی تراکنشهددا و = { 1, 2, … , } مجموعهی کل اقالف مجاای موجود در مجموعه داده باشدددد. یک تراکنش دلخواه را با = { 1, 2, … , } نشدددان میدهیم - ∈ - که دارای یک شددناسددهی یکتا - q - میباشددد که TID نامیده میشدددود. همچنین زیرمجموعهای از اقالف را، یک مجموعه قلم تعریف میکنیم به عبارد دیگر: = { 1, 2, … , } و آن را یک مجموعهی k تای مینامیم و اگر مجموعه قلم X ، زیرمجموعهای از یک تراکنش دلخواه با شد - ⊆ - آنگاه میگوییم شامل X ا ست و یا X در ظاهر شده است. برای هر قلم، دو متدار ارزش بیرونی - مثال: سودواقعی یک قلم در دروشگاه - و ارزش درونی - مثال: تعداد قلم خریداری شده در یک سبد خرید - تعریف شده است.
ارزش کل یک مجموعه قلم داده - - , - - برابر است با لاصلضرب دو ارزش بیرونی و درونی آن. ارزش مجموعه قلم در تراکنش که با - , - نمایش داده میشود توسر درمول زیر محاسبه میگردد.ارزش مجمو عه قلم در پای گاه داده از جمع ارزش این مجمو عه در تماف تراکنشها لاصددددل میشددددود. این متدار از درمول زیر محاسددددبه میگردد.همچنین ارزش یک تراکنش که با - - ن مایش داده میشددددود از مجموع ارزش تماف قلم دادههای آن و توسر درمول زیر بدست میآید.متوسددددر ارزش مجمو عه قلم k تای در تراکنش با نمایش داده میشود و اینگونه محاسبه میگردد: در این درمول k ت عداد اقالف موجود در X اسدددددت - به ع بارد دیگردر مسددددئله کشددددف اقالف با متوسددددر ارزش باال، به دنبال یادتن تماف مجموعه اقالمی - HAUIs - هستیم که متوسر ارزش آنها در کل پایگاه داده D ، از مینیمم از پیش تعریف شده - minUtil - کمتر نباشد.
-2-2 مرور کارهای گذشته
کشدددف مجموعه قلمهای با ارزش باال، توسدددعهای از مسدددئلهی کشدددف الگوهددای پرتکرار اسدددددت. همددانطور کدده در بخش قبددل بیددان شدددددد، مجموعههای با ارزش، خاصددددیت بسددددتار رو به پایین ندارند و نمیتوان د ضای ج ستجو را در پرو سه ک شف آنها، به رالتی هرس کرد. زیرا اگر مجمو عه قلمی دارای ارزش کمتر از مینیمم باشدددددد ممکن اسدددددت ابر مجموعهای از آن، دارای ارزش باالتر از مینیمم شددددود. به عبارد دیگر یک قلم دادهی با ارزش باال به آن اداده شود که ارزش کم اقالف قبلی را جبران کند. بنابراین، در الگوریتمهای کشددددف مجموعه های با ارزش، یادتن مع یاری که بتوا ند جایگاین ارزش مجمو عه قلم شددددود و دارای خا صیت ب ستار رو به پایین با شد دارای اهمیت باالی ا ست.
این معیار باید یک تخمین بیش از لد از ارزش مجموعه باشددددد که هرس کردن توسددددر آن خللی به درسددددتی الگوریتم وارد نسدددددازد. اولین بار لیو و همکارانش، مفهوف ارزش مبتنی بر تراکنش - TWU4 - را معردی کردند .]5[ برای هر مجموعه قلم X، TWU برابر اسددددت با مجموع ارزش تراکنشدددهای که X عضدددو آنها اسدددت. این متدار یک لد باالسدددت و همی شه بارگتر یا م ساوی ارزش واقعی مجموعه قلم X ا ست؛ بنابراین اگر کمتر از مینیمم باشددددد میتوان گفت ارزش مجموعه قلم نیا کمتر ازمینیمم اسددددت. همچنین این ویژگی دارای خاصددددی بسددددتار رو به پایین اسدددددت؛ هر توسدددد عه Y از مجمو عه قلم X، دتر میتوا ند در ه مان تراکن شهای رخ دهد که X در آنها ظاهر شده ا ست؛ بنابراین مجموعهارزش تراکن شهای که Y در آنها رخ داده ا ست، کمتر م ساوی مجموع ارزش تراکنشدددهای اسدددت که X در آنها رخ داده اسدددت.
پس می توانگفت اگر مجموع ارزش تراکن شهای که X در آنها رخ داده ا ست کمتر از مینیمم بداشدددددد تمداف ابرمجموعدههدای X نیا دارای مجموع ارزش تراکنش کمتر از مینیمم هسدددتند و میتوانند هرس شدددوند. بنابراین لیو و همکارانش الگوریتمی دو مرللهای معردی کردهاند. در مرلله اول، تماف مجموعه های کاندید که TWU آنها کمتر از لداقل از پیش تعریف شددده نباشددد را بر اسدداس الگوریتم Apriori و با چندین گتر از پایگاه داده پیدا میکند. سددپس در مرلله دوف، با پیمایشددی دیگر ارزش واقعی این مجموعهها را به دسددددت آورده و مجموعههای با ارزش مشددددخ میشوند.از آنجدداییکدده در تعریف مجموعددهی بددا ارزش بدداال، توجهی بدده طول مجموعه نمی شود، مجموعههای طوالنیتر شانس بیشتری پیدا میکنند که به عنوان مجموعهی با ارزش باال انتخاب شدددوند.
در صدددورتیکه در دنیای واقعی مجموعههای کوتاهتر اهمیت بیشددتری دارند. الگوریتمهای متعددی معردی شددده که سددعی کردهاند طول مجموعه را نیا در پروسدده کشددددف الگوهای با ارزش در نظر بگیرند. به طور مثال در ]16[ عالوه بر ارزش مجموعدده، محدددودیتی نیا روی طول مجموعددههددای خروجی اعمال میشددددود و تنها مجموعه های به عنوان الگوهای با ارزش باال معردی می شوند که طولشان از لداقل از پیش تعریف شده کمتر باشد. روشهای متعدد دیگری نیا برای متابله با این مشددکل ارائه شدددهاند که اکثر آن ها به جای ارزش یک مجموعه از متوسططططز ارزش آن مجموعه اسددددتفاده میکنند. به عبارد دیگر برای دخالت دادن طول مجموعه در پروسهی کشف، ارزش کل مجموعه را بر طول آن نیا تتسیم میکنند.
بر خالف مسدددئلهی کشدددف الگوهای با ارزش که در آن، امکان اسدددتفاده از ارزش مبتنی بر تراکنش - TWU - ، برای هرس کردن اولیدده وجود داشددددت، در کشددددف مجموعههای با متوسططططز ارزش باال، نمیتوان ازمتو سز ارزش مبتنی بر تراکنش برای هرس ا ستفاده نمود. زیرا متو سز ارزش یک تراکنش ممکن اسددددت از متوسططططز ارزش زیرمجموعههایش کمتر باشددددد. به طور مثال درض کنید، = { , } و = { }، و ارزش b از a بی شتر با شد، آنگاه ارزش برابر ا ست با مجموع ارزش a و b که از ارزش X بیشتر میشود؛ در صورتیکه متوسز ارزش از متوسططز ارزش X کمتر خواهد بود.
بنابراین در این دسددته از الگوریتمها از معیار ماکزیمم ارزش تراکنش - TMU - 5 اسددتفاده میشددود. در هر مجموعهای ماکزیمم ارزش از متوسططططز ارزش تماف زیرمجموعههایش بیشتر است؛ بنابراین یک لد باال برای متوسز ارزش محسوب میشود. ب نابراین برای هرس کردن از حد باالی متوسططططز ارزش - AUUB - 6 استفاده میشود که برابر است با مجموع ماکزیمم ارزش تراکنشهای که مجموعه مورد نظر در آنها رخ داده اسددددت. برای این ویژگی خاصددددیت بستار رو به پایین برقرار است.اولین الگوریتم برای لل مسئلهی کشف مجموعههای با متوسز ارزش باال روش TPAU اسدددددت]10[ که مبتنی بر Apriori اسدددددت. این الگوریتم مشابه روش دو مرللهای، ابتدا مجموعههای کاندید را، که حدباالی متوسططططز ارزش آنها از لداقل ارزش از پیش تعریف شددددده کمتر نیسدددت را پیدا میکند و در مرلله بعد با اسدددکن مجدد متوسطططز ارزش واقعی را پیدا میکند.
پیمایشهای متعدد پایگاهداده و تولید لجم باالی مجموعههای کاندید از نتاط دددعف این روش اسددت. روش HAUI-Growth یک روش درختی اسدددددت ]11[ که با نگ هداری اطال عاد مربوط به اقالف و وزن آن ها در تراکنشدددد ها ن یاز به چ ندین پی مایش و همچنین تولید مجموعه های کاندید را از بین میبرد. HAUI-Tree ]12[روش درختی دیگری ا ست که با ا ستفاده از شنا سهی تراکن شها به پایگاهدادهی ت صویر شده در لادظهی ا صلی د ستر سی پیدا میکند و در نتی جه دیگر ن یازی به چ ندین پی مایش از پای گاهداده نخواهد داشدددددت. روشهای جدید دیگر همچون MHAI]14[ و [15] EHAUPM که همه آنها مبتنی بر لیست هستند نیا اخیرا معردی شدهاند.
-3 روش پیشنهادی
الگوریتم EFIM یک روش مبتنی بر لیسددددت اسددددت که میتواند تماف مجموعه های با ارزش را اسددتخراج کند.هدف از این تحتیق، توسددعهی الگوریتم EFIM اسدددت به گونه ای که بتواند مجموعه اقالف با متوسدددر ارزش باال را بیابد. به این منظور در تعریف کران متوسددددر ارزش یک مجمو عه و روش هرس این مجمو عه تغییراتی اع مال کردهایم. در این بخش بدده معردی مرالددل الگوریتم پیشددددنهددادی میپردازیم کدده مبتنی برEFIM است:
-3-1 محاسبه AUUB
در ابتدددای الگوریتم، بددا پیمددایش پددایگدداه داده AUUB تمدداف اقالف، محاسبه شده و پایگاه داده بازبینی شده با لتف آیتمهای که این متدار در آنها از minUtil کمتر باشدددد، سددداخته میشدددود. در ادامه آیتمها بر اسدداس متدار AUUB مرتب میشددوند - در مثالها برای نمایش بهتر از ترتیب لروف الفبا اسددتفاده شددده اسددت - . بر اسدداس این ترتیب میتوان دضدددای جسدددتجو را به صدددورد درختی در نظر گردت. در این دضدددای جستجو به صورد اول عمق پیش ردته و در هر سطو، یک قلم داده به مجموعه X ا داده می شود. اقالمی که بتوان از آنها در تو سعه مجموعه X اسددددتفدداده کرد بددا E - X - نشددددددان داده میشددددونددد.
-3-2 ایجاد تصویر و پرتو پایگاه داده7
به منظور کاهش لجم پایگاه داده و در نتیجه کاهش زمان محاسددددبه ارزش واقعی مجموعه ها، در EFIM، پرتو پایگاه داده ایجاد میشددود و در هر سدددطو تنها تراکنشدددهای نگهداشدددته میشدددوند که شدددامل اقالف E - X - ه ستند.همچنین سایر اقالف نیا لتف می شوند. پرتو تراکنش نسددددبددت بدده مجموعدده X اینگوندده تعریف میشددددود: _ = .{ ∈ | ∈ - - } بنابراین به مرور که در درخت جسددتجو پیش میرویم لجم پایگاه داده کاهش یادته و زمان جستجو کم میشود.
