روش های مبتنی بر قانون

هدف از کلاسه بندی قوانین استخراجی، استخراج کردن مجموعه کوچکی از قوانین است تا یک کلاسه بند دقیق ساخته شود. الگوریتم های استخراج قانون مانند Apriori [61] و FPgrowth [15، 16] بکار گرفته می شوند تا مجموعه کاملی از الگوها استخراج شوند. سپس مجموعه کوچکی از قوانین با کیفیت بالا انتخاب می شوند که برای کلاسه بندی بکار می روند. الگوریتم های شناخته شده برای کلاسه بند های انجمنی[1] شامل CBA، CMAR و CPAR می شوند که جزئیات این الگوریتم ها در ادامه بیان خواهند شد.

• روش  Classification Based on Association (CBA) [27]

روش CBA در دو فاز اجرا می شود: تولید کننده قانون[2] و سازنده کلاسه بند[3]. تولید کننده قانون، الگوریتم Appriori را بکار می گیرد تا همه قوانینی با حداقل آستانه[4] فراوانی نسبی[5] و درجه اطمینان[6] را استخراج کند. برای کلاسه بندی کردن یک نمونه تست، سازنده کلاسه بند، قوانین را بر اساس مقادیر فراوانی نسبی و درجه اطمینانشان مرتب می کند. سپس، سازنده کلاس، اولین قانون را بعنوان بهترین قانون انتخاب می کند تا بر چسب کلاس را به نمونه تست اختصاص دهد. بدلیل اینکه CBA کلاسه بندی را بر اساس فقط یک قانون برای یک نمونه تست انجام می دهد، ممکن است باعث بروز مشکل بیش یادگیر[7] شود.

 

• روش کلاسه بندی Classification based on Multiple-class Association Rule (CMAR) [28]

با توجه به اینکه CBA فقط بر اساس یک قانون با درجه اطمینان و فراوانی بالا کلاسه بندی را انجام می دهد، مشکل بیش یادگیری صورت می گیرد و لذا دقت کلاسه بند برای نمونه های تست کم خواهد شد. برای حل این مشکل، CMAR کلاسه بندی را بر اساس چندین قانون انجام می دهد. CMAR، درخت الگوی مکرر[8] را توسعه می دهد بطوری که بتواند الگوهای مکرر[9] را بصورت کارایی استخراج کند. CMAR چندین قانون را با استفاده از وزن دهی بر اساس χ برای کلاسه بندی بکار می گیرد.

• روش کلاسه بندیClassification based on Predictive Association Rule (CPAR) [29]

CPAR با الهام از الگوریتم FOIL [62] قوانین را تولید می کند. CPAR، مجموعه بسیار کوچکی از قوانین با قابلیت پیش بینی را با استفاده از الگوریتم حریصانه بطور مستقیم از مجموعه آموزشی استخراج می کند. برای جلوگیری از بیش یادگیری، CPAR بهترین k قانون را جهت کلاسه بندی کردن نمونه تست بکار می گیرد. CPAR در مقایسه با دیگر الگوریتم های استخراج قوانین دارای مزایایی بدین شرح است: 1) مجوعه خیلی کوچکتری از قوانین با کیفیت بالا بطور مستقیم از نمونه های آموزشی[10] استخراج می کند. 2) برای پرهیز از تولید قوانین تکراری، CPAR هر قانون را با توجه به مجموعه قوانینی که از قبل استخراج کرده است، تولید می کند. 3) برای کلاسه بندی، بهترین k قانون بکار گرفته می شود.

[1] Associative classifiers

[2] Rule generator

[3] Classifier builder

[4] Threshold

[5] Support

[6] Confidence

[7] Overfit

[8] Frequent pattern tree

[9] Frequent patterns

[10] Training instances