یادگیری قانون وابستگی
در داده‌کاوی، یادگیری قانون وابستگی یک متد مناسب برای یافتن روابط جذاب بین متغیرهای موجود در پایگاه داده‌های بزرگ است. پیاتتسکی-شاپیرو در چگونگی تحلیل و ارائه قوانین قوی یافته شده را در پایگاه‌های داده با استفاده از معیارهای متفاوت جذابیت توضیح می‌دهد. بر مبنای مفهوم قوانین قوی، راکش اگرول و همکارانش در قوانین وابستگی را برای کشف قاعده‌های موجود بین مصحولات در داده‌های تراکنشی با مقیاس بالا معرفی می‌کنند. به عنوان مثال، قانون وابستگی formula_1 در داده‌های فروش یک سوپرمارکت، نشان می‌دهد در صورتی که یک مشتری پیاز (onions) و سیب زمینی (potatoes) را در سبد خرید خود قرار داده است، احتمالاً او مایل به خرید گوشت همبرگر نیز خواهد بود. چنین اطلاعاتی می‌تواند به عنوان مبنای تصمیماتی برای برخی از فعالیت‌های فروشگاهی همچون ارائه مناسب تخفیف برای محصولات یا قراردادن مناسب محصولات در کنار هم، مورد استفاده قرار گیرد. علاوه بر مثال فوق که در مورد تحلیل سبد خرید مطرح شد، امروزه یادگیری قانون وابستگی در کاربردهای متفاوت همچون مصرف کاوی وب، تشخیص نفوذ، و بیوانفورماتیک مورد استفاده قرار می‌گیرد. بر خلاف دنباله کاوی در یادگیری قانون وابستگی، ترتیب چه در میان آیتم‌ها و چه در میان تراکنش‌ها در نظر گرفته نمی‌شود.
در ادامه، تعریف اصلی کاوش قانون وابستگی، ارائه شده توسط اگرول و همکارانش آمده است: مجموعه formula_2 را به عنوان مجموعه‌ای از formula_3 صفت دودویی به نام آیتم در نظر می‌گیریم. فرض کنیم formula_4 مجموعه تراکنش‌ها یا همان پایگاه داده باشد. هر تراکنش در formula_5 شامل یک کد تراکنش منحصربه‌فرد و زیرمجموعه‌ای از آیتم‌های formula_6 است. یک قانون به عنوان یک دلالت به فرم formula_7 تعریف می‌شود. به طوری که formula_8 و formula_9. مجموعه آیتم‌های formula_10، "مقدم" و مجموعه آیتم‌های formula_11، "نتیجه" خوانده می‌شوند.
برای توضیح مفهوم، ما از یک مثال کوچک در مورد سبد خرید در سوپرمارکت استفاده می‌کنیم. مجموعه آیتم‌های formula_12 و یک پایگاه داده کوچک شامل آیتم‌ها (کد ۱ به معنی حضور و کد ۰ به معنی عدم خضور آن آیتم در یک تراکنش است) در جدول مقابل نشان داده شده‌است. به عنوان مثال formula_13 یک قانون وابستگی موجود در این پایگاه داده است. مفهوم این قانون این است که اگر مشتری کره (butter) و نان (bread ) خریده باشد، شیر (milk) هم خواهد خرید.
تذکر: مثال فوق مطرح شده بسیار کوچک است. در عمل یک قانون نیازمند پشتیبانی صدها تراکنش است تا بتواند به صورت آماری مهم باشد. از طرفی، معمولاً یک پایگاه داده شامل صدها یا هزاران تراکنش است.
برای انتخاب قوانین جذاب از بین مجموعه قوانین ممکن، محدودیت‌های مختلف روی معیارهای سنجش اهمیت و جذابیت به کار می‌رود. معروف‌ترین محدودیت‌ها شامل آستانه کمینه برای پشتیبان و اطمینان است.
مفهوم قوانین وابستگی در سال ۱۹۹۳ پس از انتشار مقاله اگرول مورد توجه خاص قرار گرفت. با توجه به اطلاعات آماری سرویس Google Scholar، در مارس ۲۰۰۸ این مقاله بیش از ۶۰۰۰ نقل قول (citation) دریافت کرده‌است که آن را در صدر بیشترین تعداد نقل قول‌ها در گرایش داده کاوی قرار می‌دهد. اگرچه ممکن است آنچه که امروزه قوانین وابستگی نامیده می‌شود، همان مفهوم مطرح شده در مقاله سال 1966 تحت عنوان GUHA (یک متد عمومی داده کاوی) مطرح شده‌است.
علاوه بر اطمینان، معیارهای دیگری نیز برای سنجش جذابیت قوانین مطرح شده‌است که از مهم‌ترین آن‌ها می‌توان به موارد زیر اشاره کرد:
در طول زمان، الگوریتم‌های متعددی برای تولید قوانین وابستگی پیشنهاد شده‌اند.
بعضی الگوریتم‌های معروف در این زمینه عبارتند از: آپریوری، اکلات (Eclat) و FP-Growth. تمامی این الگوریتم‌ها تنها انجام دهنده نیمی از مسیر تولید قوانین وابستگی هستند. چرا که این الگوریتم‌ها برای کاوش مجموعه آیتم‌های مکرر ساخته شده‌اند و پروسه دیگری روی مجموعه آیتم‌های مکرر باید انجام شود تا منتهی به قوانین وابستگی شوند.
آپریوری بهترین الگوریتم برای کاوش قوانین وابستگی است. این الگوریتم از استراتژی جستجوی اول-سطح برای شمارش پشتیبان مجموعه آیتم‌ها استفاده می‌کند و با استفاده از یک تابع تولید کاندید، از خصوصیت بستار رو به پایین پشتیبان بهره می‌برد.
اکلات یک الگوریتم جستجوی اول-عمق با استفاده از اشتراک مجموعه است.