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

به نام خدا

مقدمه

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

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

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

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

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

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

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

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

 

مروری بر مقاله‌ای با عنوان "الگوریتم ممتیکی تکاملی برای استخراج قانون"

به نام خدا

مقدمه

در ادامه مروری بر مقاله‌ای با عنوان "الگوریتم ممتیکی تکاملی برای استخراج قانون" خواهیم داشت. 

 الگوریتم‌های ممتیکی تکاملی EMAs(Evolutionary Memetic Algorithm) بر روی طرح‌هایِ اضافه کردن جستجوی محلی، برای تکمیل قابلیت جستجوی سرتاسری الگوریتم‌های تکاملی EAs، تمرکز دارند.

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

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

در این مقاله دو الگوریتم جستجوی بهبود محلی به کارگرفته شده است؛ یکی از الگوریتم میکروژنتیک μGA استفاده می‌کند که منجر به بهبود کارایی و راهنمایی هدایت شده بر روی نسل‌ها می‌گردد؛ و دیگری AIS(Artificial Immune System) سیستم ایمنی مصنوعی، که به طور گسترده برای تجزیه و تحلیل داده‌ها در الگوریتم‌های یادگیری ماشین بدون ناظر استفاده شده است.

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

در این مقاله دو ضریب پشتیبانی(Support) و اعتماد(Confidence) که از داده‌کاوی قوانین انجمنی به عاریت گرفته شده‌اند در توابع ارزیابی برازندگی استفاده شده است؛ یعنی تابع برازندگی استفاده شده برای ارزیابی مجموعه قوانین، ترکیبی از معیار اصلی یعنی دقت دسته‌بندی به علاوه ایده‌های برگرفته شده از ارزیابی قوانین انجمنی است. قوانین انجمنی قوانینی هستند که تلاش می‌کنند روابط جالب بین متغیر‌ها در یک پایگاه داده را بیابند.

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

 

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

چندین معیار ارزیابی مختلف برای سنجش عملکرد الگوریتم‌ها استفاده شده از جمله : دقت دسته‌بندی، حساسیت و خاص بودن؛ علاوه بر این‌ها در این مقاله، دو معیار ارزیابی که کمتر مورد توجه بوده‌اند نیز بررسی شده‌اند؛ قابلیت فهم(درک) (comprehensibility) و جذابیت(interestingness).

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