در داده کاوی، یادگیری قانون وابستگی (به انگلیسی: association rule learning) یک متد مناسب برای یافتن روابط جذاب بین متغیرهای موجود در پایگاه داده های بزرگ است. پیاتتسکی-شاپیرو در چگونگی تحلیل و ارائه قوانین قوی یافته شده را در پایگاه های داده با استفاده از معیارهای متفاوت جذابیت توضیح می دهد. بر مبنای مفهوم قوانین قوی، راکش اگرول و همکارانش در قوانین وابستگی را برای کشف قاعده های موجود بین مصحولات در داده های تراکنشی با مقیاس بالا معرفی می کنند. به عنوان مثال، قانون وابستگی { o n i o n s , p o t a t o e s } ⇒ { b u r g e r } {\displaystyle \{\mathrm {onions,potatoes} \}\Rightarrow \{\mathrm {burger} \}} در داده های فروش یک سوپرمارکت، نشان می دهد در صورتی که یک مشتری پیاز (onions) و سیب زمینی (potatoes) را در سبد خرید خود قرار داده است، احتمالاً او مایل به خرید گوشت همبرگر نیز خواهد بود. چنین اطلاعاتی می تواند به عنوان مبنای تصمیماتی برای برخی از فعالیت های فروشگاهی همچون ارائه مناسب تخفیف برای محصولات یا قراردادن مناسب محصولات در کنار هم، مورد استفاده قرار گیرد. علاوه بر مثال فوق که در مورد تحلیل سبد خرید مطرح شد، امروزه یادگیری قانون وابستگی در کاربردهای متفاوت همچون مصرف کاوی وب، تشخیص نفوذ، و بیوانفورماتیک مورد استفاده قرار می گیرد. بر خلاف دنباله کاوی (به انگلیسی: sequence mining) در یادگیری قانون وابستگی، ترتیب چه در میان آیتم ها و چه در میان تراکنش ها در نظر گرفته نمی شود.
پشتیبان مجموعه آیتم X {\displaystyle X} که به صورت s u p p ( X ) {\displaystyle \mathrm {supp} (X)} نشان داده می شود، نسبت تراکنش های شامل مجموعه آیتم X {\displaystyle X} است. در پایگاه داده مثال، مجموعه آیتم { m i l k , b r e a d , b u t t e r } {\displaystyle \{\mathrm {milk,bread,butter} \}} دارای پشتیبان 1 / 5 = 0.2 {\displaystyle 1/5=0.2} است، چرا که این مجموعه آیتم در بیست درصد تراکنش ها اتفاق می افتد.
اطمینان یک قانون به این صورت تعریف می شود: c o n f ( X ⇒ Y ) = s u p p ( X ∪ Y ) / s u p p ( X ) {\displaystyle \mathrm {conf} (X\Rightarrow Y)=\mathrm {supp} (X\cup Y)/\mathrm {supp} (X)} . برای مثال، قانون { m i l k , b r e a d } ⇒ { b u t t e r } {\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}} دارای اطمینان 0.2 / 0.4 = 0.5 {\displaystyle 0.2/0.4=0.5} در پایگاه داده است، به این معنا که قانون فوق برای پنجاه درصد تراکنش های شامل شیر (milk) و نان (bread) صدق می کند.
در ادامه، تعریف اصلی کاوش قانون وابستگی، ارائه شده توسط اگرول و همکارانش آمده است: مجموعه I = { i 1 , i 2 , … , i n } {\displaystyle I=\{i_{1},i_{2},\ldots ,i_{n}\}} را به عنوان مجموعه ای از n {\displaystyle n} صفت دودویی به نام آیتم در نظر می گیریم. فرض کنیم D = { t 1 , t 2 , … , t m } {\displaystyle D=\{t_{1},t_{2},\ldots ,t_{m}\}} مجموعه تراکنش ها یا همان پایگاه داده باشد. هر تراکنش در D {\displaystyle D} شامل یک کد تراکنش منحصربه فرد و زیرمجموعه ای از آیتم های I {\displaystyle I} است. یک قانون به عنوان یک دلالت به فرم X ⇒ Y {\displaystyle X\Rightarrow Y} تعریف می شود. به طوری که X , Y ⊆ I {\displaystyle X,Y\subseteq I} و X ∩ Y = ∅ {\displaystyle X\cap Y=\emptyset } . مجموعه آیتم های X {\displaystyle X} ، مقدم و مجموعه آیتم های Y {\displaystyle Y} ، نتیجه خوانده می شوند.
برای توضیح مفهوم، ما از یک مثال کوچک در مورد سبد خرید در سوپرمارکت استفاده می کنیم. مجموعه آیتم های I = { m i l k , b r e a d , b u t t e r , d r i n k } {\displaystyle I=\{\mathrm {milk,bread,butter,drink} \}} و یک پایگاه داده کوچک شامل آیتم ها (کد ۱ به معنی حضور و کد ۰ به معنی عدم خضور آن آیتم در یک تراکنش است) در جدول مقابل نشان داده شده است. به عنوان مثال { b u t t e r , b r e a d } ⇒ { m i l k } {\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}} یک قانون وابستگی موجود در این پایگاه داده است. مفهوم این قانون این است که اگر مشتری کره (butter) و نان (bread ) خریده باشد، شیر (milk) هم خواهد خرید.
تذکر: مثال فوق مطرح شده بسیار کوچک است. در عمل یک قانون نیازمند پشتیبانی صدها تراکنش است تا بتواند به صورت آماری مهم باشد. از طرفی، معمولاً یک پایگاه داده شامل صدها یا هزاران تراکنش است.
پشتیبان مجموعه آیتم X {\displaystyle X} که به صورت s u p p ( X ) {\displaystyle \mathrm {supp} (X)} نشان داده می شود، نسبت تراکنش های شامل مجموعه آیتم X {\displaystyle X} است. در پایگاه داده مثال، مجموعه آیتم { m i l k , b r e a d , b u t t e r } {\displaystyle \{\mathrm {milk,bread,butter} \}} دارای پشتیبان 1 / 5 = 0.2 {\displaystyle 1/5=0.2} است، چرا که این مجموعه آیتم در بیست درصد تراکنش ها اتفاق می افتد.
اطمینان یک قانون به این صورت تعریف می شود: c o n f ( X ⇒ Y ) = s u p p ( X ∪ Y ) / s u p p ( X ) {\displaystyle \mathrm {conf} (X\Rightarrow Y)=\mathrm {supp} (X\cup Y)/\mathrm {supp} (X)} . برای مثال، قانون { m i l k , b r e a d } ⇒ { b u t t e r } {\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}} دارای اطمینان 0.2 / 0.4 = 0.5 {\displaystyle 0.2/0.4=0.5} در پایگاه داده است، به این معنا که قانون فوق برای پنجاه درصد تراکنش های شامل شیر (milk) و نان (bread) صدق می کند.
در ادامه، تعریف اصلی کاوش قانون وابستگی، ارائه شده توسط اگرول و همکارانش آمده است: مجموعه I = { i 1 , i 2 , … , i n } {\displaystyle I=\{i_{1},i_{2},\ldots ,i_{n}\}} را به عنوان مجموعه ای از n {\displaystyle n} صفت دودویی به نام آیتم در نظر می گیریم. فرض کنیم D = { t 1 , t 2 , … , t m } {\displaystyle D=\{t_{1},t_{2},\ldots ,t_{m}\}} مجموعه تراکنش ها یا همان پایگاه داده باشد. هر تراکنش در D {\displaystyle D} شامل یک کد تراکنش منحصربه فرد و زیرمجموعه ای از آیتم های I {\displaystyle I} است. یک قانون به عنوان یک دلالت به فرم X ⇒ Y {\displaystyle X\Rightarrow Y} تعریف می شود. به طوری که X , Y ⊆ I {\displaystyle X,Y\subseteq I} و X ∩ Y = ∅ {\displaystyle X\cap Y=\emptyset } . مجموعه آیتم های X {\displaystyle X} ، مقدم و مجموعه آیتم های Y {\displaystyle Y} ، نتیجه خوانده می شوند.
برای توضیح مفهوم، ما از یک مثال کوچک در مورد سبد خرید در سوپرمارکت استفاده می کنیم. مجموعه آیتم های I = { m i l k , b r e a d , b u t t e r , d r i n k } {\displaystyle I=\{\mathrm {milk,bread,butter,drink} \}} و یک پایگاه داده کوچک شامل آیتم ها (کد ۱ به معنی حضور و کد ۰ به معنی عدم خضور آن آیتم در یک تراکنش است) در جدول مقابل نشان داده شده است. به عنوان مثال { b u t t e r , b r e a d } ⇒ { m i l k } {\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}} یک قانون وابستگی موجود در این پایگاه داده است. مفهوم این قانون این است که اگر مشتری کره (butter) و نان (bread ) خریده باشد، شیر (milk) هم خواهد خرید.
تذکر: مثال فوق مطرح شده بسیار کوچک است. در عمل یک قانون نیازمند پشتیبانی صدها تراکنش است تا بتواند به صورت آماری مهم باشد. از طرفی، معمولاً یک پایگاه داده شامل صدها یا هزاران تراکنش است.
wiki: یادگیری قانون وابستگی