پایان نامه الگوریتم Apriori و FP-Growth

برای دانلود روی لینک زیر کلیک کنید

پایان نامه الگوریتم Apriori و FP-Growth

درخت های FP و الگوریتم FP-Growth در بیگ دیتا | یادداشت های یک ...FP17 سپتامبر 2016 ... الگوریتم Apriori نخستین الگوریتم غیربدیهی است که برای کاوش مجموعه ... کاوش  یک درخت FP-tree مانند T با استفاده از الگوریتم FP-Growth را ...
افزایش بهرهوری الگوریتم Apriori و شروع FP-growth - بستیوالAprioriمکتب خونه - دانشگاه اصفهان-داده کاوی-جلسه سیزدهم - افزایش بهرهوری الگوریتم  Apriori و شروع FP-growth-محمد پورزعفرانی در حال حاضر (۱۳۹۴) دانشجوی دکتری  نرمافزار ...


ﺑﺮرﺳﻲ ﺟﺎﻣﻊ روﺷﻬﺎی ﻛﺎوش اﻟﮕﻮﻫﺎی ﻣﺘﻨﺎوب A Comprehensive Survey on ...PDFApriori. ،. FPGrowth. و. Eclat. 5. 2 -1 -1 -. ﻛﺎوش ﺑﺮ اﺳﺎس ﺗﻮﻟﻴﺪ ﻛﺎﻧﺪﻳﺪاﻫﺎ ﺑﺎ اﺳﺘﻔﺎده از. Apriori. و  روش ..... ﻫﺎی ﻣﺘﻨﺎوب ﻣﻮﺟﻮد در. ﭘﺎﻳﮕﺎه ﺗﺮاﻛﻨﺶ اداﻣﻪ ﻣﻲ. ﻳﺎﺑﺪ . اﻳﻦ روش ﺧﻤﻴﺮﻣﺎﻳﻪ اﻟﮕﻮرﻳﺘﻢ. Apriori. ]2[.
1- کاوش الگوهای متناوب در این بخش از نوشتار، در ارتباط با هریک از ...DOCالگوریتم Apriori نخستین الگوریتم غیربدیهی است که برای کاوش مجموعه آیتم های  .... کاوش یک درخت FP-tree مانند T با استفاده از الگوریتم FP-Growth را می توان به ...
 پیاده سازی الگوریتم Apriori:
1- مجموعه تک عضوی‌هایی که بیش از آستانه تکرار شده‌اند، را استخراج و L1 می‌نامیم.
2- از مجموعه L1 ، مجموعه دوعضویهایی که بیش از آستانه تکرار شده‌اند انتخاب و L2 می‌نامیم.
3- مرحله 2 برای پیدا کردن مجموعه‌های سه عضوی از مجموعه دوعضویها و مجموعه‌ چهار عضوی‌ها از مجموعه سه عضوی تا مجموعه k عضوی تولید شود، تکرار شود.
چون در این الگوریتم برای یافتن هر مجموعه کل پایگاه داده باید خوانده شود، برای افزایش کارایی از خصیصه Apriori استفاده می‌شود که بکارگیری این خصیصه در دو مرحله صورت می‌گیرد.
مرحله اول- الحاقی: برای استخراج k عضوی که به کررات با هم تکرار شده‌اند، ابتدا با استفاده از مجموعه 1- k عضوی‌هایی که به کررات تکرار شده‌اند، تمام حالات k عضوی ممکن را ایجاد می‌کنیم.
مرحله دوم- هرس کردن: در این مرحله تعدادی از عناصر مجموعه حذف خواهند شد و اعضای حذف شده، اعضایی هستند که خصوصیت Apriori رانقض می‌کنند.
شبه کد الگوریتم Apriori به طریق زیر است:
CK: Candidate item set of size k;
LK: frequent item set of size k;
L1: {frequent item set};
 
              begin
          Ck+1= candidates generated from Lk ;
          For each transaction t in database do
                 increment the cont of all candidates in ck+1 that are contained in t.
          Lk+1= Candidates in ck+1 whith min – support
      end
retum Uk Lk,
برای تولید کاندیدها (Ck+1) ، دو گام باید انجام داد که قبلاً نیز به آن اشاره شد.
1-    الحاق Lk با خودش :
2-    هرس کردن :
برای درک الگوریتم، یک مثال کاربردی خواهیم زد.
مثال: فرض کنیم که در یک سوپر مارکت پایگاه داده لیست فروش بصورت زیر باشد (بجای اینکه از اسامی اجناس استفاده کنیم، از حروف   استفاده کردیم.
فرض برآن است که عدد حداقل حمایت 2 است. (بعبارت دیگر  )

List of Items    Transaction ID
{I1, I2, I5}    T1
{I2, I4}    T2
{I2, I3}    T3
{I1, I2, I4}    T4
{I1, I3}    T5
{I2, I3}    T6
{I1, I3}    T7
{I1, I2, I3, I5}    T8
{I1, I2, I3}    T9
همچنین حداقل اطمینان مورد نیاز، 70% است.


در ابتدا، ما مجموعه اقلام تکراری را با استفاده از الگوریتم Apriori پیدا کرده و سپس، قوانین ارتباطی با استفاده از حداقل حمایت و حداقل اطمینان تولید خواهند شد.



گام 1: تولید الگوی تکراری مجموعه اقلام تکراری 1 تایی.

 
همانطور که مشاهده می‌کنید، در دور اول الگوریتم، هر آیتم یک عضو از مجموعه کاندید است.
گام 2: تولید الگوریتم تکراری مجموعه اقلام 2 تایی:
برای پیداکردن مجموعه اقلام تکراری 2 تایی، L2، الگوریتم از الحاق L1 ، با خودش (L1 join L1) استفاده می‌کند تا یک مجموعه کاندید از مجموعه اقلام 2تایی، C2 ، تولید کند. سپس تراکنش‌ها در D (پایگاه داده مثال) مرور می‌شوند و عدد حمایت برای هر مجموعه اقلام کاندید در C2 را حساب می‌کند (جدول میانی در شکل) سپس مجموعه اقلام 2 تایی تکراری، L2، تعیین می شود، شامل مجموعه اقلام 2تایی کاندید در C2 که حداقل حمایت را داشتند.
 

نکته: ما هنوز از خصوصیت Apriori استفاده نکردیم.
گام 3 : تولید الگوی تکرار مجموعه اقلام 3 تایی
 
تولید مجموعه مجموعه اقلام 3تایی کاندید، C3 ، با استفاده از خصوصیت Apriori  سرو کار دارد. به منظور پیداکردن C3، L2 L2 join را محاسبه می‌کنیم. پس خواهیم داشت:
C3=L2 join L2 = {{I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}
حال مرحله join کامل شد و مرحله هرس کردن برای کاهش اندازه C3 استفاده خواهد شد. مرحله هرس کردن کمک می‌کند تا از محاسبات سنگین بخاطر Ck بزرگ، جلوگیری شود.
بر¬اساس خصوصیت Apriori، همه زیر مجموعه‌های مجموعه اقلام تکراری نیز باید تکرار شوند. ما می‌توانیم تعیین کنیم که چهار کاندید آخر امکان تکرار شدن ندارند. چگونه؟
برای مثال، {I1,I2,I3} را در نظر بگیرید. زیر مجموعه‌های آیتم‌های دوتایی از این عبارتند از: {I1,I2} و {I1,I3} و {I2,I3} . چون همه زیر مجموعه‌های 2تایی از {I1,I2,I3} اعضای L2 هستند، پس ما {I1,I2,I3} را در C3 نگه می‌داریم.
حال مثال دیگری مثل {I2,I3,I5} را در نظر بگیرید که نشان می‌دهد عمل هرس روی آن انجام گرفته است. زیر مجموعه‌های 2تایی عبارتند از: {I2,I3} و {I2,I5} و {I3,I5} . امّا همانطور که مشاهده می‌کنید {I3,I5} عضو L2 نیستند و بنابراین این تکرار نشده است و خصوصیت Apriori را نقص کرده است. بنابراین، C3= {{I1,I2,I3},{I1,I2,I3}} بعد از چک کردن همه اعضای نتیجه الحاق برای هرس کردن است.
حال تراکنش‌ها در D مرور می‌شوند تا L3 مشخص شود. شامل مجموعه اقلام 3 تایی کاندید در C3 دارای حداقل حمایت است.
گام 4: تولید الگوی تکراری مجموعه اقلام 4تایی:
الگوریتم برای تولید مجموعه کاندید اقلام 4 تایی، C4، از L3 join L3 استفاده می‌کند. اگرچه، نتایج الحاق در {{I1,I2,I3,I5}} است، این مجموعه اقلام هرس می‌شوند چون زیر مجموعه‌اش {{I2,I3,I5}} تکرار نشده است. بنابراین   و الگوریتم پایان می‌یابد با داشتن همه ایتم‌های تکرارشونده. این پایان الگوریتم Apriori است. (شکل 5-2)
و حالا از این مجموعه اقلام تکراری برای تولید قوانین ارتباطی قوی استفاده خواهیم کرد (جایی که قوانین ارتباطی قوی هر دوی حداقل حمایت و حداقل اطمینان را قانع می‌کند.)
 
شکل4-2 پایان الگوریتم Apriori
گام 5: تولید قوانین ارتباطی از جموعه اقلام تکراری:
زیربرنامه آن به اینگونه است:
for each frequent item set "I" , generate all nonempty subsets of "I"
for every nonempty subset S of I, output the rule "S  (I-S)"  if
support _ count (I) / support _ count (S) > = min-conf where min-conf is minimum confidence threshold.

به مثال بر می‌گردیم:
ما داشتیم:
L= {{I1},{I2},{I3},{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I3},
      {I1,I2,I3},{I1,I2,I5}}.
حال I={I1,I2,I5} در نظر بگیرید، همه زیر مجموعه‌های غیر تهی آن عبارتند از:
{I1,I2},{I1,I5},{I2,I5},{I1},{I2},{5}.
آستانه حداقل اطمینان 70% است. قوانین ارتباطی نتیجه‌گیری شده در زیر نشان داده شده‌اند:
-R1:I1^I2 I5 
  confidence = Sc {I1,I2,I5} / {I1,I2}= 2/4 = 50%
پس R1   مورد قبول نیست.
-R2:I1^I5 I2 
  confidence = Sc {I1,I2,I5} / Sc {I1,I5}= 2/2 = 100%
R2 مورد قبول است.
-R3:I2^I5 I1 
  confidence = Sc {I1,I2,I5} / Sc {I2,I5}= 2/2 = 100%
پس R3   مورد قبول است.
-R4:I1 I2^I5 
  confidence = Sc {I1,I2,I5} / Sc {I1}= 2/6 = 33%
پس R4   مورد قبول نیست.
-R5:I2I1^I5 
  confidence = Sc {I1,I2,I5} / Sc {I2}= 2/7 =29%
پس R5   مورد قبول نیست.
-R6:I5I1^I2
  confidence = Sc {I1,I2,I5} / {I5}= 2/2 = 100%
پس R6   مورد قبول است.
و به این طریق ما سه قانون ارتباطی قوی داریم .
3-4-2- معایب Apriori و رفع آنها:
آیا Apriori به اندازه کافی سریع هست؟ هسته الگوریتم Apriori عبارتست از:
1- استفاده از مجموع اقلام (k-1) تای تکراری برای تولید مجموعه اقلام k تایی تکراری کاندید.
2- استفاده از مرور پایگاه داده و شناسایی الگو برای جمع‌آوری شمارش¬ها برای مجموعه اقلام کاندید.
عامل کند¬کننده Apriori چیست؟ تولید کاندید. به عبارت دیگر دو عیب وجود دارد:
1-    مجموعه‌های کاندید بزرگ:
برای مثال اگر تعداد مجموعه اقلام 1 تایی تکرارشونده 104  باشد، 107 مجموعه اقلام 2 تایی کاندید تولید خواهد شد. همچنین برای پیدا کرد یک الگوی تکرار از سایز 100، بعنوان مثال {a1, a2,...,a100} ، نیاز به تولید 2100 (که تقریباً برابر 1030 است) کاندید می‌باشد.
2-    مرورهای متعدد از پایگاه داده:
اگر طول بلندترین الگو n باشد، نیاز به n+1  مرور خواهد بود.

برای بهبود کاراریی Apriori چندین روش وجود دارد:
1- شمارش مجموعه اقلام براساس hash (تکنیک Hash)
2- کاهش تراکنش‌ها 
3- Partitioning

4- نمونه برداری 
5- شمارش مجموعه اقلام بصورت پویا
که از توضیح آنها در این مقاله صرفنظر می‌کنیم.

5-2- الگوریتم رشد الگوی تکرار شونده(FP-growth)
اطلاعات تراکنش‌های پایگاه داده قسمت مهمی برای کاوش الگوی تکرار می‌باشد. بنابراین اگر ما می‌توانیم اطلاعات را برای کاهش الگوی تکرار خارج ‌کنیم و در یک ساختار فشرده ذخیره کنیم، سپس این ممکن کاوش الگوی تکرار را آسان کند. با این ایده، در این قسمت، ما یک ساختمان داده فشرده را به نام FP-tree توسعه خواهیم داد که اطلاعات کامل ولی نه زائد برای کاوش الگوی تکرار فشرده می‌شود.
در این روش یک پایگاه داده بزرگ در ساختار فشرده درخت الگو تکرار فشرده می شود و به این ترتیب از مرورهای پرهزینه پایگاه داده جلوگیری می‌شود. این روش از طریق متدلوژی تقسیم و حل عمل می‌کند. همچنین از تولید کاندید نیز خودداری می‌کند.
مثال: مثال قبل را با این روش بررسی می‌کنیم.
آستانه حداقل حمایت برابر 2 است.
List of Items    Transaction ID
{I1, I2, I5}    T1
{I2, I4}    T2
{I2, I3}    T3
{I1, I2, I4}    T4
{I1, I3}    T5
{I2, I3}    T6
{I1, I3}    T7
{I1, I2, I3, I5}    T8
{I1, I2, I3}    T9

 اولین مرور پایگاه داده مثل الگوریتم Apriori است، که مجموعه مجموعه اقلام 1 تایی و عدد حمایتشان نتیجه می‌دهد. سپس آیتم‌های تکرار بر¬اساس عدد حمایتشان بصورت نزولی مرتب می‌شوند: نام این مجموعه را L می‌نامیم.
L= {I2:7  , I1:6  ,I3:6  ,I4:2  ,I5:2}



ساخت درخت الگوی تکرار
 حال درخت الگوی تکرار را می‌سازیم. درابتدا ریشه درخت را ایجاد می‌کنیم و آنرا Null می نامیم.
پایگاه داده  Dرا برای بار دوم مرور می‌کنیم برای هر تراکنش یک شاخه ایجاد می‌گردد هر آیتم در هر تراکنش تبدیل به یک گره می‌شود. هنگام برخورد به گره مشابه در یک تراکنش دیگر، فقط عدد حمایت آن گره و پیشوندهایش را افزایش می‌دهیم.
برای اولین تراکنش {I1,I2,I5} چنین شاخه‌ای ایجاد می‌شود:
 

اینکه چرا ابتدا گره I2 و سپس I1 و نهایتاً I5 در درخت قرار گرفتند، بخاطر اینست که در مجموعه L، اول I2 و بعد I1 و سپس I5 آمده است (یعنی بر اساس عدد حمایتشان). وقتی تراکنش دوم را بررسی می‌کنیم، چون گره I2 قبلا ً ایجاد شده یکی به آن اضافه و I4 را به فرزند آن اضافه می‌کنیم.
 

وقتی تمام تراکنش‌‌ها مرور شدند، درخت الگوی تکرار مانند شکل 6-2 می‌شود.
برای سهولت پیمایش درخت، جدول سرآیند آیتم  ساخته می‌شود که هر آیتم اشاره¬گری است به پیدایش در درخت از یک زنجیر اتصالات گره.
و به این طریق، مشکل کاوش الگوهای تکرار در پایگاه داده تبدیل به کاوش درخت الگوی تکرار شد.
  
5-2 درخت الگوی تکرار
کاوش درخت الگوی تکرار باایجاد پایگاه‌های الگو شرطی (جدول 1-2)
برای ساخت پایگاه الگوی شرطی   ابتدا گره هایی که دارای پیشوند هستند را در نظر می‌گیریم. پس نگاه می‌کنیم که در چند شاخه گره مورد نظر بوجود آمده است (گره بعنوان پسوند در نظر گرفته می‌شود). بعنوان مثال با گره I5 شروع می‌کنیم. I5 در دو شاخه بوجود آمده است که عبارتند از: {I1 I2 I3 I5:1} , {I2 I1 I5:1}
سپس بادر نظر گرفتن I5 بعنوان پسوند، دو مسیر پیشوند بوجود می‌آید که {I2 I1:1} و {I2 I1 I3: 1} هستند که این دو در پایگاه الگوی شرطی قرار می‌گیرند.
سپس I2 , I1 در FP-tree شرطی   قرار می‌گیرند، ولی I3 قرار نمی‌گیرد. چون I3 به حداقل حمایت نرسیده است.
2= 1+1 = عدد حمایت در پایگاه الگو شرطی : I1 برای
2= 1+1 = عدد حمایت در پایگاه الگو شرطی : I2 برای
1= عدد حمایت در پایگاه الگو شرطی : I3 برای
بنابراین عدد حمایت برای I3 کمتر از حداقل حمایت مورد نظر است که در مسئله 2 بود.
با بررسی کردن همه ترکیب‌های ممکن از FP-tree, I5 شرطی، همه الگوهای تکرار متناسب با پسوند I5 تولید می‌شوند.
چنین روالی را برای پسوندهای I1 , I4 , I3 در پیش می‌گیریم.
جدول کامل شده در جدول 2-1 است.
نکته اینکه I2 نمی‌تواند بعنوان پسوند در نظر گرفته شود چون هیچ پیشوندی ندارد.

جدول 1-2 کاوش FP- Tree با ایجاد پایگاه‌های الگو شرطی
Freruent pattern generated    Conditional FP- tree    Conditional base pattern    Item
I2I5:2 , I1I5:2 , I2I1I5:2    < I2:2 , I1:2>    {(I2 I1:1)  , (I2I1I3:1)}    I5
I2 I4:2    < I2: 2>    {(I2I1:1) , (I2:1)}    I4
I2I3 : 4 , I1I3:4 , I2I1I3:2    <I2:4 , I1:2>, <I1:2>    {(I2 I1:2), (I2:2), (I1:2)}    I3
I2I1:4    < I2:4>    {(I2:4)}    I1

1-5-2 چرا رشد الگوی تکرار سریع است؟
مطالعات کارایی نشان می‌دهد که رشد الگوی تکرار خیلی سریعتر از Apriori  است. به این دلیل که:
1- تولید کاندید و تست کاندید وجود ندارد.
2- از ساختمان داده فشرده‌ای استفاده می‌کند.
3- مرور مکرر پایگاه داده را حذف کرده است. (حداکثر 2 بار مرور)
4- عمل اصلی شمارش و ساخت FP-tree است.

6-2-مقایسه دوالگوریتم Apriori  و FD Growth
دو الگوریتم استخراج الگوی تکرار شونده در جاوا پیاده سازی شده‌اند و بر روی چندین مجموعه داده تست شده است. مشخصات platform مورد استفاده برای تست این بود:
Windows 2000, 256 MBRAM , Pentium4 1.7GHz processor 
برای بدست آوردن نتایج واقعیتر Microsoft SQL 2000 Server استفاده شد و با واسط ODBC استاندارد مورد دستیابی بودند. برای مطالعه کارایی و الگوریتم ها، مجموعه‌های داده با 10000 تا 500000 تراکنش تولید شدند، و فاکتورهای حمایت بین 5% و 40% استفاده شدند. هر تراکنش ممکن است شامل بیش از یک مجموعه اقلام تکرار شونده باشد.  تعداد اقلام ها در تراکنش ممکن است تغییر کند، همچنین اندازه مجموعه اقلام تکرار شونده. تعداد اقلام در یک مجموعه اقلام نیز متغیر است. با در نظر گرفتن این ملاحظات، مجموعه‌های داده تولید شده به تعداد اقلام در یک تراکنش،  تعداد اقلام در یک مجموعه اقلام تکرار شونده و غیره بستگی دارد.
پارامترهای ضروری برای تولید تست مجموعه‌های داده در جدول 2-2 مشخص شده است.

تعداد تراکنش¬ها     |D|
اندازه میانگین تراکنش¬ها     |L|
تعداد مجموعه اقلام بزرگ بالقوه بزرگ     |L|
تعداد اقلام     |N|
جدول2-2 : پارامترها
تست مجموعه داده برای تعداد اقلام N=100 ایجاد شده است و ماکسیم تعداد مجموعه اقلام تکرار شونده |L|=10 , |L|=3000 انتخاب شده است.
بعضی از نتایج مقایسه بین FP- growth , Apriori برای عامل حمایت از 5%  و برای مجموعه‌های داده متفاوت در جدول 2-2 نشان داده شده است.
جدول 3-2 نشان می‌دهد که زمان اجرای الگوریتم با اندازه مجموعه داده رشد می‌کند. بهترین کارایی توسّط الگوریتم FP- Growth بدست آمده است. شکل 6-2 نشان می‌دهد که زمان اجرای برای FP- growth برای یک مجموعه داده دقیق ثابت است وقتی که فاکتور حمایت از 40% به 5% کاهش می‌یابد، در حالی که در زمان مشابه، زمان اجرای الگوریتم Apriori بطور شگرفی افزایش می‌یابد.


زمان اجراء (sec)    تراکنش ها(k)
FD- growth    Apriori   
32/2    94/13    10
98/3    98/21    20
23/8    37/48    30
10/12    50/66    40
50/19    65/107    50
90/37    30/198    80
00/55    40/1471    110
90/98    20/3097    150
70/152    60/5320    190
00/284    80/9904    300
10/458    20/17259    400
20/610    60/20262    520
جدول 3-2 : نتایج برای فاکتور حمایت 5%
برای یک درجه حمایت از 30% یا بالاتر و مجموعه داده‌های 40000 تراکنش، الگوریتم Apriori کارایی بهتری دارد نسبت به الگوریم .FP-growth امّا برای درجه حمایت 20% یا کمتر کارایی اش بطور شگرفی کاهش می‌یابد. بنابراین، برای درجه حمایت 5% زمان اجراء برای الگوریتم Apriori سه برابر طولانی تر از زمان اجراء الگوریتم FP-growth است.
زمان اجراء برای دو الگوریتم برای مقادیر مختلف درجه حمایت بر روی مجموعه داده‌ها با 150000 تراکنش در جدول 4-2 نشان داده شده است. متذکر می‌شویم که الگوریتم Apriori کارایی کمتری نسبت به FP-growth دارد.
شکل 7-2 زمان اجرای الگوریتم Apriori برای مقادیر مختلف درجه حمایت بر روی مجموعه داده‌های با سایر مختلف را نشان می‌دهد. از اینجا ما نتیجه می‌گیریم که کارایی الگوریتم تحت تاثیر اندازه مجموعه داده‌ها و درجه حمایت قرار گرفته است.
 
شکل 6-2 : اندازه¬گیری کارکرد درجه حمایت برای پایگاه داده D1 40K

شکل 8-2 زمان اجرای الگوریتم FP-growth برای مقادیر مختلف درجه حمایت بر روی مجموعه داده های با سایر متفاوت را نشان می‌دهد. از اینجا نتیجه می‌گیریم که کارایی الگوریتم فقط به اندازه مجموعه داده‌ها وابسته است، درجه حمایت کوچکترین تاثیر را دارد.

زمان اجراء (sec)    (%) درجه حمایت
FP-growth    Apriori   
60/174    20/3097    5
80/170    10/2186    10
20/170    90/1308    15
90/170    60/1305    20
30/171    50/870    25
50/172    00/875    30
80/169    00/440    35
20/175    60/441    40
جدول 4-2 : نتایج برای D1 I50K با درجه حمایت

 
شکل 7-2 : اندازه¬گیری الگوریتم  Apriori با transaction / support


 
شکل 8-2 : اندازه¬گیری الگوریتم FP-growth با transaction / support





7-2-تحلیل ارتباطات:
تحلیل ارتباط یک رهیافت توصیفی برای اکتشاف داده است که می¬تواند به مشخص¬سازی ارتباطات میان مقادیر در پایگاه¬ داده کمک نماید. دو رهیافت عام برای رسیدن به تحلیل ارتباطی اکتشاف ارتباطی و اکتشاف توالی می¬باشد. اکتشاف ارتباطات قوانینی را در مورد مواردی را که باید با هم در یک رویداد ظاهر شوند مانند تراکنش خرید می¬یابد. تحلیل سبد عرضه یک نمونه شناخته شده از کشف ارتباط می¬باشد. کشف توالی بسیار شبیه کشف ارتباط است با توجه به این نکته که در اینجا توالی یک ارتباط است که در طول یک بازه زمانی صورت می¬¬گیرد.
ارتباطات به صورت A=>B نوشته می شود که به A مقدم یا طرف سمت چپ و به B تالی یا طرف سمت راست می¬گویند. برای مثال در قانون ارتباطی "اگر مردم یک چکش بخرند آنگاه می¬توانند میخ بخرند" جمله مقدم "خرید چکش" و جمله تالی "خرید میخ" می¬باشد.
براحتی میتوان نسبت تراکنشهایی را که شامل مورد یا لیستی ازموارد خاص می¬باشد با شمردن آنها تعیین کرد (که در اینجا موارد میخ¬ها و چکش¬ها می¬باشد) را تعیین کرد. تعداد موجود از یک نوع ارتباط خاص که در یک پایگاه داده به نظر می¬رسد را موجودی یا شیوع آن مورد می¬گویند. اگر برای مثال گفته شود که از هر 1000 تراکنش 15 تای آن شامل "میخ و چکش" می¬باشد موجودی این ارتباط 1.5% خواهد بود. یک موجودی کم (مثلا یک در میلیون) می تواند بیانگر این باشد که آن ارتباط خاص در پایگاه داده چندان مهم نیست.
برای کشف قوانین معنا¬دار ما باید به فراوانی متناسب دفعات اتفاق موارد و ترکیباتشان نیز بنگریم. با داشتن تعداد دفعات اتفاق مورد A مورد B چند بار اتفاق می¬افتد؟ به عبارت دیگر سوال این است که ببینیم "هنگامی که مردم یک چکش می¬خرند چه تعداد از این افراد میخ هم می¬خرند؟". عبارت دیگر برای این پیش بینی شرطی اطمینان نام دارد.
فرض کنید پایگاه داده فرضی¬مان رابه صورت زیر و با جزئیات بیشتر برای بیان این مفاهیم در نظر بگیریم:
تمام تراکنشهای سخت افزار: 1000
تعداد تراکنشهایی که شامل "چکش" می¬باشد: 50
تعداد تراکنشهایی که شامل "میخ" می¬باشد: 80
تعداد تراکنشهایی که شامل "تخته " می¬باشد: 20
تعداد تراکنشهایی که شامل " میخ و چکش" می¬باشد: 15
تعداد تراکنشهایی که شامل " میخ و تخته " می¬باشد: 10
تعداد تراکنشهایی که شامل " چکش و تخته" می¬باشد: 10
تعداد تراکنشهایی که شامل " چکش و تخته و میخ " می¬باشد: 5
حال قادر به محاسبه¬ایم:
موجودی "میخ و چکش"= 1.5%
موجودی     " میخ و چکش وتخته"= 0.5%
درصد اطمینان "چکش=>میخ" = 30%
درصد اطمینان " میخ=> چکش" = 19%
درصد اطمینان " چکش و میخ=>تخته" = 33%
درصد اطمینان " تخته=> چکش و میخ " = 25%

بنابراین ما می¬بینیم که احتمال اینکه یک خرنده چکش میخ هم بخرد(30%) بیشتر از احتمال آن است که فردی که میخ می¬خرد چکش هم بخرد(19%). ارتباط چکش و میخ به اندازه¬ای بزرگ است که یک قانون با معنی باشد.
الگوریتمهای ارتباط این قوانین را با معادل مرتب¬سازی داده هنگام شمارش دفعاتی که می¬توانند درصد اطمینان و موجودی را محاسبه کنند می¬یابد. اثراتی که هر یک از این قوانین می¬توانند داشته باشند یکی از معیارهای تفاوت این الگوریتم¬هاست. این معیار مهم است زیرا که نتایج ترکیبی بسیار زیادی از تعداد بی¬شماری از قوانین بدست می¬آید حتی برای سبد¬های خرید. برخی از الگوریتمها یک پایگاه داده از قوانین، فاکتورهای ایمن، و فراهم آوردن امکان جستجو (برای مثال تمام ارتباطاتی که در آن کلمه بستنی در قوانین به عنوان نتیجه آمده و فاکتوری برابر 80%را دارند نشان بده) را ایجاد می نمایند.
اغلب تصمیم¬گیری در مورد کار با قوانینی که شما کشف کرده¬اید دشوار است. به عنوان مثال در یک نقشه خرید برای مشتریان در یک فروشگاه قراردادن تمام اجناس مرتبط منطقی به صورت فیزیکی در کنار یکدیگر ممکن است ارزش کامل سبد خرید را کاهش دهد – مشتریان ممکن است در مجموع ارزش کمتری خرید کنند چون آنها بر خلاف نقشه خرید مورد نظر شما در حین راه رفتن در مغازه اجناس مورد دلخواه خود را خرید می¬کنند. در چنین حالتی تقریب و تحلیل ارتباطات معمولا برای بدست آوردن هر گونه سودی از قوانین مرتبط با هم مورد نیاز خواهد بود.
روشهای گرافیکی می¬توانند در نمایش ساختار ارتباطات نقش داشته باشند. در شکل زیر هر یک از دوایر یک مقدار یا یک رویداد را نمایش می¬دهد. خطوط ارتباطی میان این دایره¬ها یک ارتباط را نشان می¬دهند. خطوط کلفت¬تر ارتباطات قوی¬تر و فراوان¬تری را نمایش می¬دهند.

 




فصل سوم

     وب¬کاوی و متن¬کاوی
 
1-3-کاوش وب (وب¬کاری)
در یک محیط اطلاعاتی توزیع شده، معمولاً اشیاء یا مستندات به منظور تسریع در دسترسی تعاملی به یکدیگر پیوند زده می‌شوند. نمونه¬ها و مثال¬هایی برای یک چنین فراهم¬سازی اطلاعات محیطی شامل وب جهانی (WWW) و خدمات برخطی مانند American online می‌باشد بنحوی که زمانی کاربران به دنبال اطلاعات مورد نیاز و مورد علاقه خود هستند، از یک شی ء به شی‌ء دیگر با استفاده از امکاناتی مانند ابراتصال¬ها   و آدرس¬های URL در حرکت هستند. در حقیقت، وب یک بدنه ابر متن  با بیش از 800 میلیون صفحه بوده که در حال رشد سریعی است. اطلاعات آن بالغ بر شش ترابایت می‌باشد که بر روی حدود سه میلیون سرویس دهنده قرار گرفته است. تقریباً یک میلیون صفحه روزانه به این حجم از اطلاعات اضافه می‌شود و نوعاً هر چند ماه یک بار این صفحات تغییر می‌یابند‌ و در نتیجه، چند صد گیگابایت ماهانه به روز و به هنگام می‌شوند. مادامی که اطلاعات ارائه شده در وب روزانه در حال تغییر می‌باشد، بدست آوردن این اطلاعات تا حدود زیادی کسل کننده خواهد شد. حتی بزرگ ترین موتورهای جست و جو مانند آلتاویستا  و هات بات  کمتر از 18% از صفحات وب قابل دسترس را در ماه خاصی مانند فوریه ثبت کرده‌اند. باید توجه داشتکه مشکل اصلی در این رابطه در محتویات غیر ساخت یافته و یا شبه ساخت یافته وب نهفته است که به نظم آوردن آن کار بسیار ساده‌ای نخواهد بود و همچنین اعمال یک ساختار یا استاندارد مناسب بسیار مشکل به نظر می‌رسد. مجموعه‌ای از صفحات وب از یک ساختار واحد رنج برده و از سبک و شیوه نگارشی و تنوع محتوایی نسبت به آنچه که در مجموعه مستندات کاغذی مرسوم مشاهده می¬شوند، فاصله زیادی دارند. این سطح از پیچیدگی موجب ایجاد یک مدیریت بانک اطلاعاتی در دسترس و آماده می‌گردد و راه حل¬های بازیابی اطلاعات بسیار دشوار بوده و می‌توان ادعا نمود که به کارگیری آنها تقریباً غیر ممکن می‌باشد . مسلماً با این شرایط، روش¬ها و شیوه‌های جدید کاملاً ضروری به نظر می‌رسند. در حقیقت وب¬کاوی ممکن است بعنوان به کارگیری تکنیک‌های داده¬کاوی و به منظور کشف و استخراج خودکار اطلاعات از مستندات، محتویات و سرویس‌های وب معرفی گردد. به تعبیر دیگر وب¬کاوی به فرآیند کلی اکتشاف و استخراج اشاره دارد نه تنها به کاربردهای ابزار کاوش داده‌های استاندارد. بعضی از نویسندگان فرآیند وب¬کاوی را به چهار زیر وظیفه زیر تجزیه می‌کنند:
1- پیدا کردن منبع: این زیر وظیفه شامل فرآیند بازیابی داده‌هایی که می‌تواند بصورت برخط یا غیر بر خط از منبع چند رسانه‌ای بر روی وب باشد، در نظر گرفته می¬شود، مانند خبرنامه‌های الکترونیکی، گروه‌های خبری و محتویات متن اسناد HTML حاصل از حذف برچسب‌های HTML.
2- انتخاب و پیش¬پردازش اطلاعات. این مرحله فرآیندی است که توسّط انواع گوناگونی از داده‌های اصلی بازیابی شده در زیر وظیفه قبلی، تبدیل و تغییر وضعیت داده می‌شود این تبدیل و تغییر وضعیت می‌تواند یا یک نوع پیش¬پردازش مانند حذف کلمات توقف، کلمات هم¬ریشه یا غیره انجام شود یا یک پیش¬پردازش با هدف بدست آوردن نمایش دلخواه مانند پیدا کردن یک عبارت در متن و بدنه آموزشی، نمایش متن در شکل منطقی اولیه و غیره صورت گیرد.
3- تعمیم¬سازی (عمومیت¬سازی) : تعمیم¬سازی به فرآیند جست و جو و کشف خودکار الگوهای عمومی در داخل سایت¬های وب مجزا علاوه بر سایت¬های چندگانه متقاطع اطلاق می‌گردد. در این خصوص، تکنیک‌های یادگیری ماشین همه منظوره مختلف، تکنیک‌های داده¬کاوی و روش‌های با گرایش وب خاص مورد استفاده قرار می‌گیرد.
4- تحلیل: این مورد، مرحله‌ای است که  در آن معتبر¬سازی و یا تفسیر الگوهای کاوش شده اجراء می‌شود.
باید توجه داشت که در اینجا سه عامل بر روی روشی که یک کاربر سایت¬های وب را از طریق فرآیند داده¬کاوی ارزیابی و درک می¬کنند، اثرگذار می‌باشد:


Apriori vs FP-Growth for Frequent Item Set Mining | Blog | SingularitiesAprioriComparison between Apriori and FP-Growth algorithms. ... The Apriori algorithm  is based on the fact that if a subset S appears k times, any other subset S' that ...
تخته سفید | داده کاوی یا Data Mining در متلب -درس نهم: جامع کاوش قواعد ...Data8 نوامبر 2015 ... معرفی و بررسی کامل الگوریتم Apriori برای استخراج و کاوش قواعد وابستگی ...  پیاده سازی گام به گام الگوریتم FP-Growth در محیط متلب به همراه حل ...


جلسه سیزدهم - افزایش بهرهوری الگوریتم Apriori و شروع FP-growthAprioriدادهکاوی به عنوان یکی از علوم کامپیوتری همواره مورد استقبال جمع کثیری از محققین  بوده است. بانکها، موسسات، شبکههای اجتماعی و کسبوکارهای نوین به دنبال یافتن ...
مقاله بررسی و ارائه الگوریتم جدید در داده کاوی پارامتر های الگوهای ......https://www.civilica.com/Paper-CSITM01-CSITM01_570=ما در این مقاله الگوریتم جدید با نام APFT پیشنهاد داده ایم که ترکیبی از روش های  apriori و FP-growth می باشد و نتایج و عملکرد بهتری نسبت به آنها دارد. در...


Performance comparison of Apriori and FP-Growth algorithms in ...PDFThis article includes two processes, the first uses the Apriori algorithm and the  second one uses the two algorithms FP-. Growth and Create Association Rules.
ﻣﺮﻭﺭ ﺑﺮ ﮐﺸﻒ ﻗﻮﺍﻋﺪ ﻭﺍﺑﺴﺘﮕﻲ ﻓﻀﺎﻳﻲPDFApriori , Apriori TID, Partition,. ٢[,٣. ٤,. ] Fp-Growth. ﻭ ﺳﺎﻳﺮ. ﺍﻟﮕﻮﺭﻳﺘﻢ ﻫﺎ ﻭﺍﺑﺴﺘﻪ ﺑﻪ ﺁﻧﻬﺎ. ﺑﻴﺎﻥ  ﺧﻮﺍﻫﻨﺪ ﺷﺪ. ﻭ. ﺑﺮﺍ. ﻫﺮ ﻣﻮﺭﺩ ﻣﺜﺎﻟﻬﺎ. ،. ﻣﻮﺍﺭﺩ ﮐﺎﺭﺑﺮ. ﺩ. ،. ﺗﮑﻨﻴﮑﻬﺎ ﻭ ﻧﻘﺎﻁ ﻗﻮﺕ ﻭ ﺿﻌﻒ. ﻣﻮﺭﺩ ﺑﺮﺭﺳﻲ ﻗﺮﺍﺭ  ﺧﻮﺍﻫﻨﺪ.


The comparative study of apriori and FP-growth algorithm - SlideshareThe7 Mar 2013 ... This ppt will surely help to understand Apriori and FP-growth algorithm.
The FP-growth/Apriori DebatePPTFP-Growth Algorithm. Association Rule Mining. Generate Frequent Itemsets.  Apriori generates candidate sets; FP-Growth uses specialized data structures (no  ...


Performance Evaluation of Apriori and FP-Growth ... - CiteSeerXPDFis to guage the performance of the Apriori algorithm and. Frequent Pattern (FP)  growth algorithm by comparing their capabilities. The evaluation study shows that  ...
Fp growth algorithm - SlideShareFp2 Sep 2013 ... Fp growth algorithm. 1. FP-Growth algorithm Vasiljevic Vladica, vv113314m@ student.etf.rs; 2. Introduction Apriori: uses a generate-and-test ...


13 افزایش بهرهوری الگوریتم Apriori و شروع FP growth - YouTube1310 Oct 2015 - 81 min - Uploaded by saeid shamsData Mining Lecture - - Finding frequent item sets | Apriori Algorithm | Solved Example (Eng ...
Apriori and FP Growth - YouTubeApriori7 Mar 2015 - 2 min - Uploaded by Suyeon Jungfarzi... nothing about fp tree here :o. Read more ... http://singularities.com/blog/ 2015/08/apriori-vs ...


IAFP: Integration of Apriori and FP-Growth Techniques to ...PDFIndex Terms- Apriori, FP-Growth, Association Rule, Item Set. I. INTRODUCTION  ... Apriori algorithm is used for frequent item set mining and association rule ...
Analysis of FP-growth and Apriori algorithms on pattern discovery ...AnalysisThe Apriori algorithm and FP Growth algorithm are compared by applying the  rapid miner tool to discover frequent user patterns along with user behavior in the  ...


Association rule learning - WikipediaAssociationAssociation rule learning is a rule-based machine learning method for  discovering interesting ... 7.1 Apriori algorithm; 7.2 Eclat algorithm; 7.3 FP-growth  algorithm; 7.4 Others. 7.4.1 AprioriDP; 7.4.2 Context Based Association Rule  Mining ...
Comparative Study On Apriori Algorithm And Fp Growth ... - IJCSTPDFwww.ijcstjournal.org. Page 161. Comparative Study on Apriori Algorithm and Fp  Growth. Algorithm with Pros and Cons. Mrs. M.Kavitha [1], Ms.S.T.Tamil Selvi [2].


Association rule learning - WikipediaAssociationAssociation rule learning is a rule-based machine learning method for  discovering interesting ... 7.1 Apriori algorithm; 7.2 Eclat algorithm; 7.3 FP-growth  algorithm; 7.4 Others. 7.4.1 AprioriDP; 7.4.2 Context Based Association Rule  Mining ...
Frequent Pattern Growth (FP-Growth) Algorithm Outline - Wim LeersPDF10 Jan 2008 ... Apriori: uses a generate-and-test approach generates candidate itemsets ... FP- Growth: allows frequent itemset discovery without candidate ...


What is the difference between FPgrowth and Apriori algorithms in ...WhatApriori and FPGrowth are two algorithms for frequent itemset mining. They have  the same input and ... Sign In. Apriori (algorithm) · Learning Algorithm Design.
FP-growthPDFImproving Apriori. ▫ Fp-growth. ▫ Fp-tree. ▫ Mining frequent patterns with FP- tree. ▫ Visualization of ... Apriori algorithm is mining frequent itemsets for  Boolean ...


Research and Improvement on Association Rule Algorithm Based ...ResearchApriori algorithm and FP-growth algorithm are famous algorithms to find frequent  item sets. Based on analyzing on an association rule mining algorithm, a new ...
جلسه سیزدهم - افزایش بهرهوری الگوریتم Apriori و شروع FP-growth ...Aprioriجلسه سیزدهم – افزایش بهرهوری الگوریتم Apriori و شروع FP-growth. جلسه سیزدهم –  افزایش بهرهوری الگوریتم Apriori و شروع FP-growth. 00:00. /. 00:00. download ...


Is there any tool that is used to generate frequent patterns...Is... gave execution time of each algorithm to generate frequent pattern. Specific  algorithms can be Apriori Algorithm, ECLAT algorithm, and FP Growth Algorithm  ...
A New Algorithm for Frequent Itemsets Mining Based on Apriori and ...NewFrequent item sets mining plays an important role in association rules mining.  The apriori algorithm and the FP-growth algorithm are the most famous  algorithms, ...


market basket analysis using fp growth and apriori algorithm - bvimsrPDFKeywords: Market Basket Analysis, FP Growth and Apriori algorithm, cross-sale  campaigns, promotional support, inventory control, and frequent item sets, data ...
Improved Algorithm for Frequent Item sets Mining Based on Apriori ...PDFAbstract - Frequent itemset mining plays an important role in association rule  mining. The Apriori &. FP-growth algorithms are the most famous algorithms  which ...