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

چکیده

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

مقدمه

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

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

در سالهاي اخير توانايي توليد و جمع آوري اطلاعات افزايش چشم گيري داشته و حجم اطلاعات با سرعت زياد رو به افزايش است . داده کاوي يا اکتشاف دانش از پايگاههاي داده ، به معناي فرايند استخراج غير بديهي اطلاعات ضمني (غير صريح) است که قبلا بر ما پوشيده بوده و احتمالاً مورد استفاده و با ارزش خواهند بود .یکی از تکنیکها و مفاهیم اصلی در داده کاوی قوانين انجمني هستند . قوانين انجمني روابط و وابستگيهاي متقابل بين مجموعه بزرگي از اقلام داده اي را نشان ميدهند. پيدا کردن چنين قوانيني ميتواند در حوزه های مختلف مورد توجه بوده و کاربردهاي متفاوتي داشته باشد بعنوان مثال کشف روابط انجمني بين حجم عظيم تراکنش هاي کسب و کار ميتواند درتشخيص تقلب ، در حوزه پزشکي و همچنين داده کاوي در مورد اطلاعات روش بکارگيري وب توسط کاربران و شخصي سازي مورد استفاده قرار گیرد يا در طراحي کاتالوگ ، بازاريابي و ديگر مراحل فرايند تصميم گيري کسب و کار موثر باشد. مثال متداول در رابطه با کشف قوانين انجمني "تحليل سبد خريد" است. در اين فرايند با توجه به اقلام مختلفي که مشتريان در سبد خريدشان قرار ميدهند ، عادات و رفتار خريد مشتريان مورد تحليل قرار ميگيرد.الگوهای موجود در اقلام خریداری شده کشف می شود ، بعنوان مثال مشخص مي شود مشترياني که براي خريد نان به فروشگاه آمده اند اغلب شير نيز خريداري می کنند و البته معيارهاي مختلف برای اعتبار و قابلبت تعمیم این الگوها در نظر گرفته می شود .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 هستند .

درخت دانش

جدول دانش

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

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