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


== چکیده ==

کاوش قوانین انجمنی در پایگاه داده های بزرگ  یکی از محبوب ترین تکنیک های شناسایی  داده برای تصمصم گیرنده های کسب و کار می باشد . اکتشاف  مجموعه اقلام تکرار شونده یک فرآیند اولیه در کاوش قوانین انجمنی می باشد .  الگوریتم های  بسیاری  برای پیداکردن الگو های تکرار شونده در مقالات مطرح شده اند . این الگوریتم ها برای گرفتن آستانه 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 نيز باشند. يا به قول ديگر : 
  
http://s8.picofile.com/file/8273024934/image3791.gif
 
قوانيني که حد پايين Support ياmin-sup و را دارا باشند قوانين انجمني قوي ناميده ميشوند و هدف تمام الگوريتمها چنين قوانيني است .مثلا قانون زير بيانگر اين است که 70% کساني که تلويزيون خريداري مي کنند دستگاه پخش ويدئو نيز ميخرند و 3% از کل تراکنشات شامل هر دو قلم تلويزيون و دستگاه پخش ويدئو است :

http://s9.picofile.com/file/8273025100/image3771.gif
   
در بيشتر الگوريتمها از جمله Appriori پيدا کردن قوانين انجمني فرايندي است دو مرحله اي، در مرحله اول مجموعه اقلام مهم يعني آنهايي که داراي Support بيشتر از  min-sup هستند شناسايي ميشوند و در مرحله دوم از اين مجموعه اقلام براي توليد قوانين انجمني قوي استفاده ميشود.نکته جالب توجه اين است که کارايي کلي الگوريتمهاي کشف قوانين انجمني وابسته به مرحله اول فرايند است و پس از پيدا شدن اقلام داده اي مهم ، قوانين انجمني به سادگي از روي آنها قابل استخراج خواهد بود.دو الگوريتم اوليه براي پيدا کردن قوانين انجمني Appriori و FP-tree هستند .

== بدنه ی تحقیق ==

'''الگوريتم  Appriori''' 
 
Appriori نام خود را از اين مساله گرفته که از دانش قبلي در مورد خواص مجموعه اقلام مهم (يا بزگ) استفاده مي کند.يک مجموعه از اقلام را که شامل k قلم باشد يک k-مجموعه اقلام مي ناميم. اين الگوريتم يک روش افزايشي را بکار ميگيرد که در آن از مجموعه اقلام k تايي (يا k-مجموعه اقلام ها) براي بدست آوردن مجموعه اقلام (K+1) تايي استفاده ميکند.از اين به بعد به مجموعه اقلام مهم k تايي http://s9.picofile.com/file/8273106684/8.png ميگوييم.در اين الگوريتم ابتدا مجموعه اقلام مهم تک عضوي پيدا ميشوند که همان مجموعه http://s8.picofile.com/file/8273109642/10.png خواهد بود.

واضح است که http://s8.picofile.com/file/8273109642/10.png  شامل تمام اقلامي است که حداقل در min-sup درصد تراکنشها ظاهر شده باشند.از مجموعه http://s8.picofile.com/file/8273109642/10.png براي بدست آوردن http://s8.picofile.com/file/8273110076/11.png و بهمين ترتيب از http://s9.picofile.com/file/8273107468/9.png براي بدست آوردن http://s9.picofile.com/file/8273106684/8.png استفاده ميشود.ويژگي مهمي که در توليد http://s9.picofile.com/file/8273106684/8.png ها به کارايي الگوريتم کمک ميکند اين است که "تمام زير مجموعه هاي غير تهي يک مجموعه اقلام بزرگ بايد مجموعه اقلام بزرگي باشند". صحت اين گزاره به سادگي قابل مشاهده است ، بنابر تعريف مجموعه اقلامي مثل A که داراي حداقل Support نباشد يک مجموعه غير مهم است، اگر قلم (يا اقلام) ديگري مثل X به A اضافه شود مجموعه حاصل يعني http://s9.picofile.com/file/8273103268/5.png نيز مسلما نميتواند يک مجموعه مهم باشد. مراحل توليد http://s9.picofile.com/file/8273106684/8.png  ها بطور خلاصه به اين صورت است :
ابتدا براي بدست آوردن http://s9.picofile.com/file/8273106684/8.png  ها مجموعه اي از مجموعه اقلام k تايي با ترکيب اعضاء http://s9.picofile.com/file/8273107468/9.png بعنوان کانديد توليد ميشوند که http://s8.picofile.com/file/8273105776/7.png   ناميده ميشوند. ترکيب http://s8.picofile.com/file/8273103442/6.png در صورتي انجام مي شود که اعضاي http://s9.picofile.com/file/8273107468/9.png دقيقا k-2 قلم مشترک داشته باشند يا به عبارت ديگر:  

http://s8.picofile.com/file/8273103100/4.png
 
مرحله بعدي مرحله حرس است ، http://s8.picofile.com/file/8273105776/7.png در واقع ابر مجموعه http://s9.picofile.com/file/8273106684/8.png است يعني تمام اعضا http://s9.picofile.com/file/8273106684/8.png در آن هستند ولي تمام اعضاء http://s8.picofile.com/file/8273105776/7.png لزوما مهم نيستند. يک بار بررسي پايگاه داده ها ميتواند اعضاء مهم را مشخص کند اما راه حل بهتري نيز وجود دارد.براي اين کار از خاصيت Appriori استفاده ميشود يعني اگر هر يک از  زير مجموعه هاي k-1 عضوي http://s8.picofile.com/file/8273105776/7.png  در http://s9.picofile.com/file/8273107468/9.png نباشد مطمئناً http://s8.picofile.com/file/8273105776/7.png  نميتواند يک مجموعه مهم باشد.در اين صورت فقط براي تعدادي از اعضاي http://s8.picofile.com/file/8273105776/7.png که شرايط را دارا هستند سراغ پايگاه داده ها ميرويم.
پس از پيدا کردن مجموعه اقلام مهم قدم بعدي پيدا کردن قوانين انجمني قوي از اين مجموعه است که شامل قوانيني مي شود که در شرط زير صدق کنند : 

http://s9.picofile.com/file/8273103076/3.png
 
بر اساس اين رابطه قوانين به اين صورت توليد ميشوند: براي هر مجموعه اقلام مهم l تمام زيرمجموعه هاي غير تهي آن را توليد کرده ، سپس براي هر زير مجموعه s در صورتيکه http://s9.picofile.com/file/8273103000/1.png باشد قانون http://s8.picofile.com/file/8273103050/2.png را به مجموعه قوانين اضافه مي کنيم.ضمن اينکه چون مجموعه هاي مهم قبلاً توليد شده اند مقدار 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  ) فشرده می کند و در نتیجه پیمایش کل پایگاه داده تنها در دو مرحله انجام می شود . دوم اینکه از تولید بی رویه اقلام داده تکرار شونده کاندید جلوگیری می کند و سوم استفاده از درخت الگوی شرطی برای کاوش اقلام داده تکرار شونده و نتیجه آن کاهش فضای جستجو می باشد .

                                    
                                                               
http://s8.picofile.com/file/8273147192/P_conditional_Database.png
 



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


http://s8.picofile.com/file/8273196876/21.png            http://s8.picofile.com/file/8273197542/22.png

'''درخت دانش''' 
http://s8.picofile.com/file/8273201200/24.jpg

'''جدول دانش'''
http://s8.picofile.com/file/8273201168/27.png

== نتیجه گیری == 

== مقالات و منابع مورد مطالعه ==
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