پاورپوینت کاوش الگوهای پرتکرار، انجمن ها و همبستگی ها: مفاهیم اولیه و متدها

بخشی از پاورپوینت

اسلاید 1 :

فصل 6: کاوش الگوهای پرتکرار، انجمن ها و همبستگی ها: مفاهیم اولیه و متدها
مفاهیم اولیه
متدهای کاوش مجموعه آیتم پرتکرار
الگوریتم آپریوری
تولید قوانین انجمنی
بهبود آپریوری

اسلاید 2 :

تحلیل الگوهای پرتکرار چیست؟
الگوی پرتکرار(Frequent Pattern – FP): یک الگو ( مجموعه ای از آیتم ها، زیرتوالی ها، زیرساختارها و.) که به دفعات در یک مجموعه داده اتفاق می افتد.
اولین باردرسال 1993 توسط Agrawal، Imielinski و Swami در زمینه آیتم های پرتکرار و کاوش قوانین انجمنی پیشنهاد شد.
الگوهای پرتکرار دو نوع هستند:
به صورت یک زیرتوالی : مثل خرید ابتدا یک PC، سپس یک دوربین دیجیتال و درنهایت یک کارت حافظه اگر به صورت پرتکرار درتاریخچه پایگاه داده یک فروشگاه اتفاق بیفتد، یک الگوی ترتیبی(پرتکرار) خواهد بود.
به صورت یک زیرساختار: اشاره به اشکال ساختاری مختلفی همانند زیرگراف ها، زیردرخت ها یا زیرشبکه ها دارد که ممکن است با مجموعه های آیتم یا زیرتوالی ها ترکیب شده باشند.اگر یک زیرساختار به دفعات تکرار شود به آن الگوی ساختاری (پرتکرار) گویند.

اسلاید 3 :

تحلیل الگوهای پرتکرار چیست؟
انگیزش: یافتن نظم ذاتی در داده ها
چه محصولاتی اغلب با هم خریداری می شوند؟ آبجو و پوشک؟! نان و پنیر؟
بعد از خرید PC چه محصولات دیگری خریداری می شوند؟
کدام نوع DNA به داروی جدید حساس است؟
آیا می توانیم به طور خودکار مستندات وب را طبقه بندی کنیم؟
کاربردها
تحلیل سبد خرید، بازاریابی متقابل، طراحی کاتالوگ، تحلیل کمپین فروش و تحلیل دنباله DNA

اسلاید 4 :

چرا کاوش الگوهای پرتکرار مهم است؟
الگوهای پرتکرار: نقش مهم و اساسی در مجموعه داده ها
نقشی اساسی در بسیاری از کارهای ضروری داده کاوی:
تحلیل های انجمنی و همبستگی
الگوهای ساختاری و ترتیبی
تحلیل الگوها در داده های مکان-زمانی، چندرسانه ای، سری های زمانی و داده های جریانی
کلاس بندی داده ها
تحلیل خوشه بندی
انبارسازی داده ها
فشرده سازی داده های معنایی
و دیگر زمینه ها.

اسلاید 5 :

تحلیل سبد خرید

اسلاید 6 :

تحلیل سبد خرید
جهان را مجموعه ای از آیتم های موجود در یک فروشگاه تصور کنید.هر آیتم دارای یک متغیر بولی است که نشان دهنده حضور یا غیبت آن است.
هر سبد خرید می تواند از طریق مقادیر بردار بولی تخصیص یافته به این متغیرها نشان داده شود.
بردارهای بولی میتوانند برای الگوهای خریدی که نشان دهنده آیتم های پرتکرار مرتبط باهم یا خریداری شده باهم هستند تجزیه و تحلیل شوند.
این الگوها میتوانند به فرم قوانین انجمنی (association rules) ارائه شوند.

computer => antivirus_software [support = 2% , confidence = 60%]
support و confidence دو معیار از قانون علاقه مندی هستند و به ترتیب منعکس کننده سودمندی و قطعیت قانون های آشکار شده هستند.
support به مقدار 2% یعنی 2% از تمام تراکنش های بررسی شده نشان میدهند که کامپیوتر و آنتی ویروس با هم خریداری شده اند.
cofidence به مقدار 60 % یعنی 60% از مشتریانی که کامپیوتر خریده اند همراه با آن آنتی ویروس هم خریده اند.

اسلاید 7 :

مجموعه آیتم های پرتکرار و قوانین انجمنی

اسلاید 9 :

مجموعه آیتم های پرتکرار و قوانین انجمنی
قوانین انجمنی را مطلوب گویند اگر هم حداقل آستانه support و هم حداقل آستانه confidence را برآورده سازند.
چنین قوانینی را قوانین قوی می گویند.
آستانه ها توسط کاربران یا خبرگان این حوزه تعیین میشوند.

در کل کاوش قانون انجمنی یک فرآیند دو مرحله ایست:
یافتن تمام مجموعه های آیتم پرتکرار: طبق تعریف هریک از این مجموعه آیتم ها دست کم به تعداد حداقل min_sup تکرار خواهند شد.
تولید قوانین انجمنی قوی از مجموعه آیتم های پرتکرار: طبق تعریف این قوانین باید حداقل های support و confidence را برآورده کنند.

اسلاید 11 :

خاصیت الگوهای پرتکرار و متدهای کاوش مقیاس پذیر
خاصیت الگوهای پرتکرار:
هر زیرمجموعه ای از یک itemset پرتکرار باید پرتکرار باشد.
اگر {beer, diaper, nuts} پرتکرار است، پس{beer, diaper} هم هست.
یعنی هر تراکنشی که {beer, diaper, nuts} را دارد شامل {beer, diaper} نیز هست.
متدهای کاوش مقیاس پذیر: سه رهیافت اصلی
آپریوری(Apriori)
Frequent Pattern growth (Fpgrowth)
رهیافت فرمت داده عمودی

اسلاید 12 :

آپریوری: راه کار تولید کاندیدا و تست آن
اصل هرس کردن آپریوری: اگر itemset ی وجود دارد که پرتکرار نیست، مجموعه بالاتر از آن نباید تولید/تست شود!
Apriori یک الگوریتم اولیه پیشنهاد شده توسط Agrawal و Srikant در سال 94 برای کاوش مجموعه های آیتم پرتکرار برای قوانین انجمنی بولی است.
روش آپریوری:
اسکن اولیه DB برای به دست آوردن 1-itemset پرتکرار
تولیدitemsetهای کاندید به طول(k+1) از itemset های پرتکرار به طول k
تست کاندیدها در DB
پایان دادن به کار وقتی دیگر هیچ مجموعه کاندید یا پرتکراری تولید نشود.

اسلاید 13 :

الگوریتم آپریوری: یک مثال
داده های تراکنشی برای یک شعبه فروشگاه

اسلاید بعدی تولید مجموعه های آیتم کاندیدا و مجموعه ایتم پرتکرار را نشان میدهد. حداقل support برابر 2 است.

اسلاید 15 :

پیاده سازی آپریوری
چگونه کاندیدها را تولید کنیم؟
گام اول: اتصال Lk با خودش
گام دوم: هرس کردن
مثال از تولید کاندید
L3={abc, abd, acd, ace, bcd}
اتصال : L3*L3
abcd from abc and abd
acde from acd and ace
هرس:
Acde حذف می شود زیرا ade درL3 نیست.
C4 = {abcd}

اسلاید 16 :

تولید قوانین انجمنی از مجموعه های آیتم پرتکرار
بعد از اینکه مجموعه های ایتم پرتکرار از تراکنش ها در پایگاه داده D پیدا شدند تولید قوانین انجمنی کار سرراستی است.
تولید قوانین انجمنی:
برای هر مجموعه آیتم پرتکرار l، همه زیرمجموعه های غیرتهی از l تولید می شوند.
برای هرزیرمجموعه غیرتهی s از l، قانون خروجی s=>(l-s) است در جایی که confidence قانون بزرگتر از حداقل آستانه اطمینان (min_conf) باشد.

اسلاید 17 :

تولید قوانین انجمنی: مثال
مجموعه آیتم پرتکرار: l ={I1,I2,I5}
قوانین انجمنی که میتوانند از l تولید شوند؟
زیرمجموعه های غیر تهی از l:
{I1,I2} {I1,I5} {I2,I5} {I1} {I2} {I5}
قوانین انجمنی به دست آمده به همراه confidence هریک:

اسلاید 18 :

چالش های کاوش الگوهای پرتکرار
چالش ها:
اسکن چندباره پایگاه داده
تعداد زیاد کاندیدها
کار زیاد برای شمارش support کاندیدها
بهبود آپریوری: ایده عمومی
کاهش تعداد اسکن ها روی پایگاه داده
کم کردن تعداد کاندیدها
تسهیل کردن شمارش support کاندیدها

اسلاید 19 :

بهبود کارایی آپریوری
تکنیک مبتنی بر هش:
تولید همه k-itemset ها برای هرتراکنش و نگاشت آنها به باکت های مختلف از یک جدول هش و افزایش شماره باکت متناظر K-itemset ی که شماره باکت آن کمتر از support آستانه باشد نمیتواند پرتکرار بوده و حذف میشود.