متد ها و روش های داده کاوی برای یافتن مجموعه اقلام داده تکرار شونده و با ارزش در پایگاه داده ها بزرگ

چکیده

کاوش قوانین انجمنی در پایگاه داده های بزرگ یکی از محبوب ترین تکنیک های شناسایی داده برای تصمصم گیرنده های کسب و کار می باشد . اکتشاف مجموعه اقلام تکرار شونده یک فرآیند اولیه در کاوش قوانین انجمنی می باشد . الگوریتم های بسیاری برای پیداکردن الگو های تکرار شونده در مقالات مطرح شده اند . این الگوریتم ها برای گرفتن آستانه minimum support همه ترکیب های از مجموعه اقلام تکرار شونده را کشف می کنند . در بین همه الگوریتم ها Apriori و FP-tree رایج ترین تکنیک هایی برای کشف مجموعه اقلام تکرار شونده ، هستند. Apriori با چندین دفعه اسکن پایگاه داده ، همه مجموعه اقلام تکرار شونده قابل توجه را پیدا می کند. FP-tree با دو بار اسکن پایگاه داده ، همه مجموعه اقلام تکرار شونده قابل توجه را پیدا می کند. چون پایگاه داده ها بسیار بزرگ هستند ، تعداد دفعات اسکن پایگاه داده در صرف هزینه و وقت بسیار مهم می باشد .

مقدمه

در سالهاي اخير توانايي توليد و جمع آوري اطلاعات افزايش چشم گيري داشته و حجم اطلاعات با سرعت زياد رو به افزايش است . داده کاوي يا اکتشاف دانش از پايگاههاي داده ، به معناي فرايند استخراج غير بديهي اطلاعات ضمني (غير صريح) است که قبلا بر ما پوشيده بوده و احتمالاً مورد استفاده و با ارزش خواهند بود .یکی از تکنیکها و مفاهیم اصلی در داده کاوی قوانين انجمني هستند . قوانين انجمني روابط و وابستگيهاي متقابل بين مجموعه بزرگي از اقلام داده اي را نشان ميدهند. پيدا کردن چنين قوانيني ميتواند در حوزه های مختلف مورد توجه بوده و کاربردهاي متفاوتي داشته باشد بعنوان مثال کشف روابط انجمني بين حجم عظيم تراکنش هاي کسب و کار ميتواند درتشخيص تقلب ، در حوزه پزشکي و همچنين داده کاوي در مورد اطلاعات روش بکارگيري وب توسط کاربران و شخصي سازي مورد استفاده قرار گیرد يا در طراحي کاتالوگ ، بازاريابي و ديگر مراحل فرايند تصميم گيري کسب و کار موثر باشد. مثال متداول در رابطه با کشف قوانين انجمني "تحليل سبد خريد" است. در اين فرايند با توجه به اقلام مختلفي که مشتريان در سبد خريدشان قرار ميدهند ، عادات و رفتار خريد مشتريان مورد تحليل قرار ميگيرد.الگوهای موجود در اقلام خریداری شده کشف می شود ، بعنوان مثال مشخص مي شود مشترياني که براي خريد نان به فروشگاه آمده اند اغلب شير نيز خريداري می کنند و البته معيارهاي مختلف برای اعتبار و قابلبت تعمیم این الگوها در نظر گرفته می شود .Agrawal در بحث قوانين انجمني را مطرح کرده و براي توضيح موضوع از کشف اين قوانين در پايگاه داده اي از تراکنش هاي فروش استفاده ميکند. هدف در اين فرآيند پيدا کردن خودکار قوانيني مثل "60% افرادي که نان خريداري ميکنند شير هم ميخرند و ... " است ، البته براي قابل قبول بودن قوانين معيار هايي مطرح ميکند.

بررسی ادبیات موضوع

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

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

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

فرضيات ابتدايي از اين قرارند : مجموعه I = I1 ,I2 ,I3 ,… را بعنوان مجموعه اقلام در نظر بگيريد. مجموعه D را بعنوان مجموعه داده ها يعني تراکنشهاي پايگاه داده ها در نظر بگيريد بطوريکه هر تراکنش شامل مجموعه اي از اقلام باشد ، يعني هر تراکنش T زير مجموعه اي از I است ) (. هر تراکنش شناسه اي بنام TID دارد.اگر A يک مجموعه از اقلام باشد ، مي گوييم تراکنش T شامل A است اگر و فقط اگر باشد. يک قانون انجمني گزاره اي است به صورت ،در حاليکه ، و باشد. براي بررسي ارزش و معيار مقبوليت قوانين انجمني دو پارامتر مهم يعني Support و Confidence قوانين را معرفي ميکنيم. قانون در مجموعه تراکنشهاي D داراي Support برابر با s است اگر s در صد از تراکنشهاي D شامل باشند و اين قانون داراي Confidence برابر c است اگر c درصد ازتراکنشهايي که شامل A هستند شامل B نيز باشند. يا به قول ديگر :

قوانيني که حد پايين Support ياmin-sup و را دارا باشند قوانين انجمني قوي ناميده ميشوند و هدف تمام الگوريتمها چنين قوانيني است .مثلا قانون زير بيانگر اين است که 70% کساني که تلويزيون خريداري مي کنند دستگاه پخش ويدئو نيز ميخرند و 3% از کل تراکنشات شامل هر دو قلم تلويزيون و دستگاه پخش ويدئو است :

در بيشتر الگوريتمها از جمله Appriori پيدا کردن قوانين انجمني فرايندي است دو مرحله اي، در مرحله اول مجموعه اقلام مهم يعني آنهايي که داراي Support بيشتر از min-sup هستند شناسايي ميشوند و در مرحله دوم از اين مجموعه اقلام براي توليد قوانين انجمني قوي استفاده ميشود.نکته جالب توجه اين است که کارايي کلي الگوريتمهاي کشف قوانين انجمني وابسته به مرحله اول فرايند است و پس از پيدا شدن اقلام داده اي مهم ، قوانين انجمني به سادگي از روي آنها قابل استخراج خواهد بود.دو الگوريتم اوليه براي پيدا کردن قوانين انجمني Appriori و FP-tree هستند .

بدنه ی تحقیق

الگوريتم Appriori

Appriori نام خود را از اين مساله گرفته که از دانش قبلي در مورد خواص مجموعه اقلام مهم (يا بزگ) استفاده مي کند.يک مجموعه از اقلام را که شامل k قلم باشد يک k-مجموعه اقلام مي ناميم. اين الگوريتم يک روش افزايشي را بکار ميگيرد که در آن از مجموعه اقلام k تايي (يا k-مجموعه اقلام ها) براي بدست آوردن مجموعه اقلام (K+1) تايي استفاده ميکند.از اين به بعد به مجموعه اقلام مهم k تايي ميگوييم.در اين الگوريتم ابتدا مجموعه اقلام مهم تک عضوي پيدا ميشوند که همان مجموعه خواهد بود.

واضح است که شامل تمام اقلامي است که حداقل در min-sup درصد تراکنشها ظاهر شده باشند.از مجموعه براي بدست آوردن و بهمين ترتيب از براي بدست آوردن استفاده ميشود.ويژگي مهمي که در توليد ها به کارايي الگوريتم کمک ميکند اين است که "تمام زير مجموعه هاي غير تهي يک مجموعه اقلام بزرگ بايد مجموعه اقلام بزرگي باشند". صحت اين گزاره به سادگي قابل مشاهده است ، بنابر تعريف مجموعه اقلامي مثل A که داراي حداقل Support نباشد يک مجموعه غير مهم است، اگر قلم (يا اقلام) ديگري مثل X به A اضافه شود مجموعه حاصل يعني نيز مسلما نميتواند يک مجموعه مهم باشد. مراحل توليد ها بطور خلاصه به اين صورت است : ابتدا براي بدست آوردن ها مجموعه اي از مجموعه اقلام k تايي با ترکيب اعضاء بعنوان کانديد توليد ميشوند که ناميده ميشوند. ترکيب در صورتي انجام مي شود که اعضاي دقيقا k-2 قلم مشترک داشته باشند يا به عبارت ديگر:

مرحله بعدي مرحله حرس است ، در واقع ابر مجموعه است يعني تمام اعضا در آن هستند ولي تمام اعضاء لزوما مهم نيستند. يک بار بررسي پايگاه داده ها ميتواند اعضاء مهم را مشخص کند اما راه حل بهتري نيز وجود دارد.براي اين کار از خاصيت Appriori استفاده ميشود يعني اگر هر يک از زير مجموعه هاي k-1 عضوي در نباشد مطمئناً نميتواند يک مجموعه مهم باشد.در اين صورت فقط براي تعدادي از اعضاي که شرايط را دارا هستند سراغ پايگاه داده ها ميرويم. پس از پيدا کردن مجموعه اقلام مهم قدم بعدي پيدا کردن قوانين انجمني قوي از اين مجموعه است که شامل قوانيني مي شود که در شرط زير صدق کنند :

بر اساس اين رابطه قوانين به اين صورت توليد ميشوند: براي هر مجموعه اقلام مهم l تمام زيرمجموعه هاي غير تهي آن را توليد کرده ، سپس براي هر زير مجموعه s در صورتيکه باشد قانون را به مجموعه قوانين اضافه مي کنيم.ضمن اينکه چون مجموعه هاي مهم قبلاً توليد شده اند مقدار Support هر يک از آنها و زير مجموعه هايشان محاسبه شده و نياز به محاسبه مجدد نيست.

الگوریتم FP-growth

این الگوریتم جزو شناخته ترین الگوریتم های داده کاوی جهت کاوش قلمداد های مکرر بر روی پایگاه داده های عظیم می باشد و طی دوبار پیمایش دورن پایگاه داده ، اقلام تکرار شونده را استخراج می کند . در اولین پیمایش ابتدا قلمداد های تکرار شونده را استخراج می کند . در اولین پیمایش ابتدا اقلام تکرار شونده از مرتبه یک استخراج شده و سپس بر اساس میزان پشتیبانی آنها به ترتیب نزولی ، در لیستی به نام L دخیره و بعد از آن در جدولی به نام جدول سرآیند به همان ترتیب قرار می دهند .جدول سرآیند نه تنها شامل قلمداد ها و مقدار پشتیبانی انهاست بلکه شامل یک اشاره گر به همان اقلام در درخت FP-tree می باشد . در پیمایش دوم اقلام های هر تراکنش ، به ترتیب موجود در لیست L به عنوان یک مسیر درون درخت FP-tree قرار می گیرند . کسیر های مجزایی مه دارای پیشوند یکسان می باشند در هنگام اضافه شدن به درخت ادغام می گردند تا از مصرف حافظه کاسته شود.

از آنجا مه درخت FP-tree حاوی همه اطلاعات لازم برای کاوش اقلام تکرار شونده می باشد کاوش آن در حقیقت برابر با کاوش کل پایگاه داده است . با تعقیب اشاره گر یک اقلم داده در جدول سرآیند ، تمام مسیر های شامل آن قلمداده ملاقات می شوند . در این حالت به مسیر های از ریشه تا گره والد X اصطلاحا الگوهای شرطی پایه گفته می شود و بر اساس این الگوهای شرطی پایه ، FP-growth به طول بازگشتی یک درخت FP-tree جدید ایجاد می کند (که به آن درخت FP-tree شرطی نیز می گویند ) و مجدد یک الگوی شرطی پایه شکل می گیرد . با الحاق قلم داده X با قلمدادهای تکرار شونده که آیتم X پسوند آنهاست کشف می شوند . با اعمال چنین کاوشی برای هر قلم داده تکرار شونده از مزتبه یک همه اقلام داده تکرار شونده درون درخت FP-tree کشف می گردند .

در کل می توان سه مزیت عمده را برای FP-growth نام برد : اول آنکه FP-growth کل پایگاه داده را درون یک ساختمان داده کوچکتر (درخت FP-tree ) فشرده می کند و در نتیجه پیمایش کل پایگاه داده تنها در دو مرحله انجام می شود . دوم اینکه از تولید بی رویه اقلام داده تکرار شونده کاندید جلوگیری می کند و سوم استفاده از درخت الگوی شرطی برای کاوش اقلام داده تکرار شونده و نتیجه آن کاهش فضای جستجو می باشد .

تحلیل و ارزیابی الگوريتم Appriori در مقایسه با الگوریتم FP-growth

درخت دانش

جدول دانش

مقالات و منابع مورد مطالعه

1) Boosted Apriori: an Effective Data Mining Association Rules for Heart Disease Prediction System

R. Thanigaivel and K. Ramesh Kumar Middle-East Journal of Scientific Research 24 (1): 192-200, 2016 ISSN 1990-9233 © IDOSI Publications, 2016 DOI: 10.5829/idosi.mejsr.2016.24.01.22944

2) Four Chechpoint Modified Aprior Algorithm for Data Minig in Accident Analysis

Shivangi Dheer & Miss. Priyanka Punjabi Gyan Vihar University

Imperial Journal of Interdisciolinary Research (IJIR) Vol-2,Issuse-7 ,2016 ISSN : 2452-1362 , http://www.onlinejournal.in

3) An Efficient Frequent Pattern Mining Algorithm to Find the Existence of

K-Selective Interesting Patterns in Large Dataset Using SIFPMM

Saravanan Suba Department of Computer Science, Kamarajar Government Arts College, Surandai-627859, Tamil Nadu, India. Dr. Christopher. T Department of Computer Science, Government Arts College, Coimbatore-641018, Tamil Nadu, India.

International Journal of Applied Engineering Research ISSN 0973-4562 Volume 11, Number 7 (2016) pp 5038-5045 ©Research India Publications. http://www.ripublication.com

4)Data Mining: Concepts and Techniques, 3rd Edition

Author(s):Han & Kamber&Pei Release Date:25 Jul 2011 Imprint:Morgan Kaufmann Print Book ISBN :9780123814791