Abstract
Previously, exception rules have been defined as association rules with low support and high confidence. Exception rules are important in data mining, as they form rules that can be categorized as an exception. This is the opposite of general association rules in data mining, which focus on high support and high confidence. In this paper, a new approach to mining exception rules is proposed and evaluated. A relationship between exception and positive/negative association rules is considered, whereby the candidate exception rules are generated based on knowledge of the positive and negative association rules in the database. As a result, the exception rules exist in the form of negative, as well as positive, association. A novel exceptionality measure is proposed to evaluate the candidate exception rules. The candidate exceptions with high exceptionality form the final set of exception rules. Algorithms for mining exception rules are developed and evaluated using an exceptionality measurement, the desired performance of which has been proven
چکیده
پیش از این قوانین استثنا به صورت قوانین همبستگی با اثبات و اطمینان بالا تعریف شده است. قوانین استثنا در داده کاوی مهم هستند زیرا قوانینی را تشکیل می دهند که می توانند بعنوان یک استثنا دسته بندی شوند. این برخلاف قوانین همبستگی عمومی در داده کاوی است که بر اثبات و اطمینان بالا تاکید دارند. در این مقاله، رویکرد جدیدی در قوانین استثنای داده کاوی پیشنهاد و ارزیابی می شود. رابطه ای بین قوانین همبستگی منفی/مثبت و قوانین استثنا فرض می شود و بدین وسیله قوانین استثنای کاندید بر اساس آگاهی نسبت به قوانین همبستگی منفی و مثبت در پایگاه داد تولید می شوند. درنتیجه، قوانین استثنا به فرم رابطه منفی و نیز مثبت وجود دارند. یک معیار استثناپذیری جدید پیشنهاد می شود تا قوانین استثنای ارائه شده ارزیابی گردند. استثنائات کاندید با استثناپذیری بالا، مجموعه نهایی قوانین استثنا را شکل می دهند. الگوریتم های مخصوص کاوش قوانین استثنا ایجاد شده و با استفاده از یک اندازه گیری استثنایی ارزیابی می شوند که عملکرد مطلوب آن اثبات می شود.
کلیدواژه ها: داده کاوی، قوانین همبستگی، قوانین استثنا، قوانین همبستگی منفی، داده کاوش قانون همبستگی، اثبات، اطمینان، استثناپذیری، کشف دانش، قوانین همبستگی فازی
1-مقدمه
کاوش قانون انجمنی تحقیقات بسیاری را به خود جلب کرده است. قوانین استثنا به صورت قوانینی تعریف می شوند که اثبات (برهان) (support) کم و اطمینان (confidence) بالایی دارند. یک مثال معمول از قوانین استثنا ، قانون شامپانی ← خاویار (Champagne→Caviar) است. این قانون ممکن است اثبات قوی ای نداشته باشد ولی اطمینان بالایی دارد. این آیتم ها گران هستند بنابراین در پایگاه داده رایج نیستند، ولی آنها را همواره با هم می خرند، بنابراین این قانون اطمینان بالایی دارد. قوانین استثنا اطلاعات ارزشمندی را درباره الگوهای پایگاه داده به دست می دهند.
این مقاله به کاوش قوانین استثنا بر اساس قوانین انجمنی (association rule) در پایگاه های داده می پردازد. قوانین استثنا، اطلاعات غیرمعمول و متناقض در پایگاه های داده را شرح می دهند. یک ارتباط متقابل بین قوانین استثنا و قوانین انجمنی بررسی خواهد شد. بر اساس اطلاعات درباره قوانین انجمنی در پایگاه داده، قوانین استثنا به وجود خواهند آمد. در این مقاله، ما ملاحظه می کنیم که قوانین انجمنی می توانند به شکل انجمنی مثبت و منفی وجود داشته باشند. از آنجایی که قوانین استثنا مخالف قوانین انجمنی هستند، قوانین استثنا به صورت انجمنی مثبت و نیز منفی وجود دارند. یک معیار استثنا بودن مطرح می شود تا قوانین استثنای قابل اطمینان ارزیابی شوند. استثنائات با استثنایی بودن بالا، قوانین استثنای معتبری هستند.
اهمیت قوانین استثنا در تعدادی کارهای تحقیقاتی بررسی شده است. چیزی که با باور معمول یک کاربر تضاد دارد، جالب توجه است. حسین و همکارانش (4) بیان می کنند که استثنائات می توانند نقش مهمی را در تصمیم گیری های مهم ایفا کنند. بیشتر محققان بر قوانین انجمنیی تاکید می کنند که نشان دهنده پدیده های رایجی هستند که با اثبات و اطمینان بالا رخ می دهند. استثنائات علی رغم نقش مهمشان در تصمیم گیری، هنوز برای بسیاری از کاربران بیگانه هستند. استثنائات بدون تردید بسیار ارزشمند هستند.
لیو و همکارانش (16) تاکید می کنند که "استثنائات معتبر نامعلوم، غیرقابل پیش بینی یا متناقض با باورهای کاربر هستند. از این رو آنها جدید و بالقوه جالب تر از الگوهای قوی برای کاربر هستند". مثلا قانون "به متقاضیان بیکار کمک مالی داده می شود" بدیع تر از "به متقاضیان بیکار کمک مالی داده نخواهد شد" است. آنها تاکید می کنند که "یک قانون استثنا اغلب سودمند است چون با یک قانون منطقی که اغلب پایه ای برای فعالیت روزانه مردم است، متفاوت است ".
مثالهای اشاره شده اهمیت قوانین استثنا در کاوش داده را نشان می دهند. قوانین انجمنی و استثنا انواع مختلفی از قوانین را به دست می دهند. قوانین انجمنی نشان دهنده اطلاعات منطقی و معمول هستند در حالی که قوانین استثنا حقایق غیرمعمول و تعجب برانگیز در داده ها هستند...