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

از 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 و FP-tree هستند .

بدنه ی تحقیق

درخت دانش

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