یادگیری قانون وابستگی

در ادامه، تعریف اصلی کاوش قانون وابستگی، ارائه شده توسط اگرول و همکارانش آمده است: مجموعه ${\displaystyle I=\{i_1,i_2,\dots ,i_n\}}$

برای توضیح مفهوم، ما از یک مثال کوچک در مورد سبد خرید در سوپرمارکت استفاده می‌کنیم. مجموعه آیتم‌های ${\displaystyle I=\{\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{k},\mathrm{b}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d},\mathrm{b}\mathrm{u}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r},\mathrm{d}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{k}\}}$

تذکر: مثال فوق مطرح شده بسیار کوچک است. در عمل یک قانون نیازمند پشتیبانی صدها تراکنش است تا بتواند به صورت آماری مهم باشد. از طرفی، معمولاً یک پایگاه داده شامل صدها یا هزاران تراکنش است.

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

• پشتیبان مجموعه آیتم ${\displaystyle X}$
  که به صورت ${\displaystyle \mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(X)}$
  نشان داده می‌شود، نسبت تراکنش‌های شامل مجموعه آیتم ${\displaystyle X}$
  است. در پایگاه داده مثال، مجموعه آیتم ${\displaystyle \{\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{k},\mathrm{b}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d},\mathrm{b}\mathrm{u}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\}}$
  دارای پشتیبان ${\displaystyle 1/5=0.2}$
  است، چرا که این مجموعه آیتم در بیست درصد تراکنش‌ها اتفاق می‌افتد.
• اطمینان یک قانون به این صورت تعریف می‌شود: ${\displaystyle \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}(X\Rightarrow Y)=\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(X\cup Y)/\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(X)}$
  . برای مثال، قانون ${\displaystyle \{\mathrm{m}\mathrm{i}\mathrm{l}\mathrm{k},\mathrm{b}\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}\}\Rightarrow \{\mathrm{b}\mathrm{u}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\}}$
  دارای اطمینان ${\displaystyle 0.2/0.4=0.5}$
  در پایگاه داده است، به این معنا که قانون فوق برای پنجاه درصد تراکنش‌های شامل شیر (milk) و نان (bread) صدق می‌کند.

مفهوم قوانین وابستگی در سال ۱۹۹۳ پس از انتشار مقاله اگرول مورد توجه خاص قرار گرفت. با توجه به اطلاعات آماری سرویس Google Scholar، در مارس ۲۰۰۸ این مقاله بیش از ۶۰۰۰ نقل قول (citation) دریافت کرده‌است که آن را در صدر بیشترین تعداد نقل قول‌ها در گرایش داده کاوی قرار می‌دهد. اگرچه ممکن است آنچه که امروزه قوانین وابستگی نامیده می‌شود، همان مفهوم مطرح شده در مقاله سال 1966 تحت عنوان GUHA (یک متد عمومی داده کاوی) مطرح شده‌است.

علاوه بر اطمینان، معیارهای دیگری نیز برای سنجش جذابیت قوانین مطرح شده‌است که از مهم‌ترین آن‌ها می‌توان به موارد زیر اشاره کرد:

• اطمینان-کامل
• توان جمعی
• عقیده
• نفوذ
• بالابری

در طول زمان، الگوریتم‌های متعددی برای تولید قوانین وابستگی پیشنهاد شده‌اند.

بعضی الگوریتم‌های معروف در این زمینه عبارتند از: آپریوری، اکلات (Eclat) و FP-Growth. تمامی این الگوریتم‌ها تنها انجام دهنده نیمی از مسیر تولید قوانین وابستگی هستند. چرا که این الگوریتم‌ها برای کاوش مجموعه آیتم‌های مکرر (به انگلیسی: Frequent item-set mining) ساخته شده‌اند و پروسه دیگری روی مجموعه آیتم‌های مکرر باید انجام شود تا منتهی به قوانین وابستگی شوند.

الگوریتم آپریوری

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

الگوریتم اکلات

اکلات یک الگوریتم جستجوی اول-عمق با استفاده از اشتراک مجموعه است.

• داده کاوی
• دنباله کاوی