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

از OCCC Wiki
پرش به ناوبری پرش به جستجو

چکیده

کاوش قوانین انجمنی در پایگاه داده های بزرگ یکی از محبوب ترین تکنیک های شناسایی داده برای تصمصم گیرنده های کسب و کار می باشد . اکتشاف مجموعه اقلام تکرار شونده یک فرآیند اولیه در کاوش قوانین انجمنی می باشد . الگوریتم های بسیاری برای پیداکردن الگو های تکرار شونده در مقالات مطرح شده اند . این الگوریتم ها برای گرفتن آستانه 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 نيز باشند. يا به قول ديگر :

image3791.gif

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

image3771.gif

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

بدنه ی تحقیق

درخت دانش

KowledgeTree.jpg

جدول دانش

KnowledgeTable.jpg

نتیجه گیری

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

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