معیارهای ارزیابی قوانین در داده‌کاوی

به نام خدا

مقدمه

معیارهای بسیاری برای ارزیابی عملکرد در یادگیری ماشین و کشف دانش استفاده می‌شود. در استنتاج پیشگویانه (Predictive induction) مبتنی بر دسته‌بندی، اغلب معیار دقت(Accuracy) دسته‌بندی، استفاده می‌شود. در حالیکه سایر معیارهای استاندارد عبارتند از: دقت(Precision)، یادآوری(Recall)، حساسیت(Sensitivity) و اختصاصی کردن(Specificity).

در سایر عملیات‌های کشف دانش مانند قوانین انجمنی که از  جمله روش‌های استنتاج توصیفی(Descriptive Induction) است از معیارهای دیگری نظیر پشتیبانی(Support)، اعتماد(Confidence)، جذابیت(Interestingness) و قابلیت فهم(Comprehensibility) تعریف می‌شود.

در این پست به معرفی چندین معیار انتخاب شده برای ارزیابی قوانین در داده‌کاوی قوانین انجمنی می‌پردازیم. این معیارها جائیکه یک قانون بایستی رتبه‌بندی شود، با توجه با اینکه به چه خوبی توسط داده‌ها پشتیبانی می‌شوند؛ به کار برده می‌شوند.

معیارهای جالب در داده‌کاوی قوانین انجمنی

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

طی سالیان گذشته کارهای بسیاری در زمینه داده‌کاوی به ویژه در زمینه یافتن انجمن‌ها و همبستگی‌ها در میان آیتم‌ها در یک پایگاه داده از تراکنش‌های مشتریان انجام شده است. در زمینه تحلیل سبد خرید(Market Basket Analysis) قوانین انجمنی آیتم‌های را متمایز می‌کند که در اغلب موارد، بخش قابل توجهی از مشتریان، همراه با آیتم‌های خاص دیگری خریداری کرده‌اند. به عنوان مثال ممکن است ما متوجه شویم که 95 درصد از مشتریانی که نان خریده‌اند شیر نیز خریداری کرده‌اند.

هر قانون در داده‌کاوی قوانین انجمنی بایستی دو محدودیت مشخص شده کاربر را برآورده کند؛ یکی معیاری از اهمیت آماری است که پشتیبانی(Support) نامیده می‌شود و دیگری معیاری از خوب بودن قانون است که اعتماد(Confidence) نامیده می‌شود.

در ادامه به تعریف رسمی(Formal Definition) و برخی توضیحات در خصوص تعدادی از معیارهای ارزیابی قوانین انجمنی که در ابتدا معرفی شدند، خواهیم پرداخت.

 

 شرح معیارهای مختلف

برای اینکه مقایسه بین معیارهای مختلف امکان‌پذیر باشد تمامی معیارها با استفاده از احتمالات تعریف می‌شوند:

احتمال مواجهه با آیتم X توسط فرمول زیر تعیین می‌گردد.

$$P(X)=\frac{Count(X)}{|D|}$$

جائیکه( Count(X تعداد تراکنش‌های است که شامل آیتم X است و |D| اندازه پایگاه داده یا به عبارتی دیگر تعداد کل تراکنش‌ها است.

پشتیبانی(Support)

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

$$Support(X)=p(X)$$

پشتیبانی بر روی مجموعه آیتم‌های(Z) تعریف می‌شود و نسبت تراکنش‌هایی را که حاوی Z هستند را می‌دهد و به عنوان معیاری از اهمیت مجموعه آیتم‌ها مورد استفاده قرار می‌گیرد. و از آنجا که اساسا از تعداد تراکنش‌ها استفاده می‌کند، اغلب یک محدودیت تکرار(Frequency Constraint ) نامیده می‌شود. یک مجموعه آیتم با پشتیبانی بیشتر از حداقل آستانه پشتیبانی(α)، مجموعه پرتکرار یا بزرگ نامیده می‌شود.

ویژگی اصلی معیار پشتیبانی این است که تمامی زیر مجموعه‌های یک مجموعه پرتکرار نیز پرتکرار هستند؛ از این ویژگی که به عنوان Down-Ward Closure یاد می‌شود برای هرس کردن فضای جستجو استفاده می‌شود. مشکل معیار پشتیبانی مسئله آیتم کمیاب یا نادر است. آیتم‌های که در یک مجموعه داده بسیار نادر رخ می‌دهند؛ هرس می‌شوند؛ هر چند که آن‌ها قوانین جالب و بالقوه ارزشمندی را ارائه می‌دهند. مسئله آیتم‌های نادر برای داده‌های سبد خرید مهم است، که معمولا توزیع بسیار نامناسب از پشتیبانی برای آیتم‌های تکی دارند؛ یعنی تعدادی از آیتم‌ها در همه زمان‌ها استفاده می‌شوند و بیشتر آیتم‌ها به ندرت استفاده می‌شوند.

مقادیر مربوط به معیار پشتیبانی در محدوده [0,1] هستند. اگر یک آیتم در هیچ تراکنشی دیده نشود ارزش آن صفر و اگر یک آیتم در تمامی تراکنش‌ها آمده باشد مقدارش یک است.

اعتماد(Confidence)

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

$$Confidence(X\rightarrow Y)=\frac{P(X \ and \ Y) }{P(X)}$$

اعتماد یعنی، احتمالِ اینکه یک تراکنش حاوی X حاوی Y هم باشد. به بیان دیگر، اعتماد به عنوان احتمال مشاهده تالی قانون، تحت شرایطی که تراکنش‌ها همچنین حاوی مقدم هستند، تعریف می‌شود. اعتماد مقادیر متفاوتی برای قوانین $$X\rightarrow Y و Y\rightarrow X$$ می‌دهد؛ که اصطلاحا معیار ارزیابی نامتقارن نامیده می‌شود؛ بر خلاف معیار پشتیبانی که یک معیار متقارن است.

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

مشکل معیار اعتماد این است که به تکرار تالی (Y) در پایگاه داده حساس است و این ناشی از روشی است، که محاسبه می‌شود تالی‌هایی با پشتیبانی بیشتر به طور خودکار مقادیر اعتماد بالاتری تولید می‌کنند؛ حتی اگر هیچ ارتباطی ما بین آیتم‌ها وجود نداشته باشد.

مقادیر اعتماد در محدوده [0,1] است. اگر مقدم و تالی مستقل باشند اعتماد برابر صفر است؛ و برای وقوع انجمن‌ها در تمامی موارد، مقدارش برابر یک است.

مقایسه معیارها

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

داده‌های نمونه

داده‌های نمونه برای مقایسه معیارها از پایگاه دادة تراکنش‌های مشتریان یک فروشگاه گرفته شده است. 6 نوع مختلف از آیتم‌ها و در کل 10 تراکنش وجود دارد. در هر تراکنش عدد 1 نشان دهنده وجود یک آیتم است و عدد 0 نشان دهنده عدم وجود یک آیتم از یک سبد خرید است.

آیتم‌های پرتکرار 

با در نظر گرفتن حداقل آستانه پشتیبانی به مقدار 40%، آیتم‌های پرتکرار را مشخص می‌کنیم. نتیجه در جدول 2 آورده‌ شده است. به عنوان مثال آیتم‌های A,D حداقل در 40% تراکنش‌ها با هم حضور داشته‌اند.

تولید قوانین انجمنی از مجموعه آیتم‌های پرتکرار

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

به عنوان مثال

$$Confidence(A\rightarrow F)=\frac{P(A \ and \ F) }{P(A)}=\frac{0.5}{0.6}=0.83$$

با توجه به جدول 3 قوانین F→A و B→D جالب به نظر می‌رسند؛ و اما سوال، از بین این دو، کدام یک می‌تواند جالبتر باشد؟ برای پاسخ به این سوال لازم است تعداد بیشتری معیار ارزیابی وجود داشته باشد. مثلا معیار همبستگی(Correlation) می‌تواند مفید باشد.

همبستگی(Correlation)

همبستگی یک تکنیک آماری است که می‌تواند نوع و درجه همبستگی(رابطة) جفت متغیر‌ها(مجموعه آیتم‌ها) را نشان دهد. به عبارتی دیگر از همبستگی برای کمی کردن رابطه بین متغیرها(مجموعه آیتم‌ها)  استفاده می‌شود.

$$Correlation(X\rightarrow Y)=\frac{P(X \ and \ Y)-P(X)P(Y)}{\sqrt{P(X)P(Y)(1-P(X))(1-P(Y))}}$$

همبستگی از 1(رابطه خطی مثبت قوی) تا 1-(رابطه خطی منفی قوی) متغیر است. و در بین آن‌ها 0 به معنای هیچ ارتباطی است.

 اگر همبستگی دو متغیر مثبت باشد، به این معناست که افزایش یکی، با افزایش دیگری و کاهش یکی با کاهش دیگری همراه است. 

اگر همبستگی دو متغیر با یکدیگر منفی باشد، به این معناست، که افزایش یکی با کاهش دیگری و کاهش یکی با افزایش دیگری همراه است.

صفر بودن همبستگی به این معناست که دو متغیر مستقل از یکدیگر بوده‌اند و بر اساس اطلاعات موجود از کاهش یا افزایش یکی، نمی‌توان در مورد کاهش یا افزایش دیگری اظهار نظر کرد.

مثلا معیار همبستگی برای F→A به صورت زیر محاسبه می‌شود.

$$Correlation(F\rightarrow A)=\frac{0.5-(0.5*0.6)}{\sqrt{0.5*0.6*0.5*0.4}}=\frac{0.2}{0.245}=0.82$$

با توجه به معیار همبستگی می‌توان گفت:« قانون F→A قانون جالبتری است».

نتیجه‌گیری

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