روش One Rule به همراه شبه کد — استنتاج قوانین اولیه در داده کاوی

یک روش بسیار آسان به منظور یافتن قوانین ساده دسته‌بندی برای مجموعه داده‌ها در ادامه بیان شده است. این روش 1R یا One-Rule (و یا One-R) نامیده می‌شود. روش مذکور، درخت تصمیم یک-سطحی بیان شده به صورت مجموعه قوانینی که همگی یک ویژگی (خصیصه) خاص را در مجموعه داده مورد تست قرار می‌دهند، تولید می‌کند. 1R یک روش ساده و ارزان است که اغلب قوانین خوبی برای مشخصه‌سازی ساختار داده‌ها فراهم می‌کند. نکته جالب توجه آن است که این قوانین ساده، اغلب صحت بالایی کسب می‌کنند.

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

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

1For each attribute,
2   For each value of that attribute, make a rule as follows:
3     count how often each class appears
4     find the most frequent class
5     make the rule assign that class to this attribute value.
6   Calculate the error rate of the rules.
7 Choose the rules with the smallest error rate.

برای آنکه عملکرد روش 1R در عمل مشخص شود، الگوریتم روی داده‌های آب و هوا که در جدول زیر آمده، پیاده خواهد شد. این مجموعه دارای ۱۴ نمونه و ۴ ویژگی است. ویژگی اول (Outlook) چشم‌انداز کلی آب و هوا (آفتابی، بارانی یا ابری) را مشخص می‌کند. ویژگی دوم، دما (که در اینجا یک ویژگی اسمی است)، بر اساس یکی از دسته‌های گرم، سرد و معتدل تعیین می‌شود.

فیلم آموزش اصول و روش های متن کاوی Text Mining در فرادرس

کلیک کنید

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

برای انجام دسته‌بندی بر اساس ستون آخر یعنی «play»، الگوریتم 1R چهار مجموعه از قوانین (یک قانون برای هر ویژگی) را در نظر می‌گیرد. این قوانین در ادامه نشان داده شده‌اند. وجود ستاره (*) در کنار یک قانون به معنای آن است که باید یک انتخاب تصادفی از بین دو مقدار خروجی دارای احتمال مشابه انجام شود.

تعداد خطاها برای هر قانون و تعداد کل خطاها برای یک مجموعه قوانین به عنوان خطای کل، محاسبه شده است. 1R ویژگی‌هایی را انتخاب می‌کند که قوانین دارای کمترین تعداد خطا را می‌سازند. در این مثال، اولین و سومین مجموعه قوانین حائز این شرایط هستند، بنابراین یکی از آن دو به طور تصادفی انتخاب می‌شود.

outlook: sunny → no 
overcast → yes
 rainy → yes

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

مقادیر از دست رفته و مشخصه‌های عددی در روش One-Rule

با وجود اینکه الگوریتم 1R یکی از پایه‌ای‌ترین الگوریتم‌های یادگیری است، اما برای استفاده در مجموعه داده‌های دارای مقادیر از دست رفته (missing values) و ویژگی‌های عددی تطابق نیافته. اما با کمی تغییرات توانایی مواجهه با چنین مسائلی را به شیوه موثر دارد. مقدار از دست رفته به عنوان یک مقدار ویژگی دیگر در نظر گرفته می‌شود. برای مثال، اگر مجموعه داده آب و هوا دارای مقادیر از دست رفته برای ویژگی outlook باشد، یک مجموعه قوانین برای این خصیصه شکل می‌گیرد که چهار دسته مقدار ممکن را مشخص می‌کنند، این دسته‌ها sunny ،overcast ، rainy و مقادیر از دست رفته هستند.

فیلم آموزش داده کاوی Data Mining در متلب MATLAB در فرادرس

کلیک کنید

در الگوریتم 1R برای مواجهه با مشخصه‌های عددی (مانند آنچه در جدول زیر وجود دارد) می‌توان آن‌ها را با یک روش گسسته‌سازی ساده به نوع اسمی تبدیل کرد. برای انجام این کار، ابتدا باید نمونه‌های آموزش بر اساس مقدار مشخصه عددی مرتب‌سازی شوند. این فرآیند یک توالی از مقادیر دسته ایجاد می‌کند. برای مثال، مقادیر موجود در نسخه عددی مجموعه داده آب و هوا بر اساس مشخصه temperature مرتب‌سازی شده‌اند و یک دنباله ایجاد می‌کنند.

64   65   68   69   70   71   72   72   75   75   80   81   83   85
yes  no   yes  yes  yes   no  no   yes  yes  yes   no  yes  yes  no

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

yes | no | yes yes yes | no no | yes yes yes | no | yes yes | no

انتخاب خطوط جداساز میانی ( و محاسبه میانگین طرفین خط) در بین نمونه‌ها به ترتیب مقادیر 64.5، 66.5، 70.5، 72، 77.5، 80.5 و 84 را به دست می‌دهد. در این حال، وجود دو نمونه با مقدار ۷۲ مشکل ایجاد می‌کند زیرا با وجود مقادیر مشابه برای درجه حرارت، متعلق به دو دسته جدا هستند. ساده‌ترین راه انتقال خط جداساز به یک نمونه جلوتر (پس از ۷۲) است. در این صورت عدد میانی برابر با ۷۳.۵ خواهد بود که یک بخش ترکیبی است و در آن no اکثریت آرا را در اختیار دارد.

یک مساله جدی‌تر آن است که این فرآیند تعداد دسته‌های زیادی را به همراه دارد. الگوریتم 1R به طور طبیعی گرایش به انتخاب مشخصه‌ای دارد که به دسته‌های زیادی تقسیم می‌شوند. زیرا این کار مجموعه داده را به بخش‌های زیادی تقسیم می‌کند که در آن نمونه‌ها دسته مشابهی با اکثریت موجود در بخش خود دارند.

فیلم آموزش اصول و روش های متن کاوی Text Mining در فرادرس

کلیک کنید

در واقع، عامل محدود کننده، مشخصه‌ای است که برای هر نمونه مقدار متفاوتی دارد (که مشخصه identification code به صورت یکتا به نمونه‌ها اشاره دارد) و این منجر به نرخ خطای صفر در مجموعه داده آموزش می‌شود، زیرا هر بخش تنها دارای یک نمونه است. البته، مشخصه‌هایی که داده‌ها را زیاد منشعب می‌کنند برای نمونه‌های تست معمولا عملکرد خوبی ندارند. در واقع، کد شناسایی هرگز هیچ نمونه‌ای را خارج از مجموعه داده آموزش به درستی پیش‌بینی نمی‌کند. این پدیده «بیش برازش» (overfitting) نام دارد.

در الگوریتم 1R، احتمال وقوع بیش برازش هنگامی ایجاد می‌شود که یک مشخصه دارای تعداد زیادی از مقادیر محتمل باشد. در نتیجه، هنگام گسسته‌سازی یک مشخصه عددی، یک محدودیت حداقلی روی تعداد نمونه‌های موجود در دسته اکثریت در هر بخش اعمال می‌شود. فرض می‌شود که این حداقل ۳ است. این کار همه بخش‌های قبلی به جز دو مورد را حذف می‌کند. در عوض ساخت بخش‌ها با حصول اطمینان از این امر انجام می‌شود که سه بار وقوع yes (اکثریت دسته) در اولین بخش وجود داشته باشد.

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

فیلم آموزش داده کاوی Data Mining در متلب MATLAB در فرادرس

کلیک کنید

هنگامی که بخش‌های مجاور دارای دسته اکثریت مشابه باشند (مانند دو بخش اول بالا) می‌توان آن‌ها را بدون تحت تاثیر قرار دادن معنای مجموعه قوانین با یکدیگر ادغام کرد. بنابراین، گسسته‌سازی نهایی به صورت زیر خواهد بود.

yes no yes yes yes no no yes yes yes | no yes yes no

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

temperature: ≤ 77.5 → yes 
> 77.5 → no

دومین قانون مربوط به انتخاب‌های اختیاری (به نوعی تصادفی) برای هنگامی که no انتخاب شود است. در عوض اگر yes انتخاب می‌شد، نیازی به هیچ خط جداسازی نبود و این مثال نشان می‌دهد که بهتر است از دسته‌های مجاور برای کمک به از بین بردن گره‌ها استفاده شود. در حقیقت، این قانون پنج خطا در مجموعه آموزش ایجاد می‌کند و بنابراین از قانون پیشین که برای outlook ایجاد شد تاثیرگذاری کمتری دارد. اگرچه، فرآیند مشابهی منجر به ایجاد قانون زیر برای humidity می‌شود:

humidity: ≤ 82.5 → yes 
> 82.5 and ≤ 95.5 → no 
> 95.5 → yes

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

سایر مباحث

در مقاله‌ای (از ابتدایی‌ترین مقاله‌ها پیرامون روش One-Rule) با عنوان «Very simple classification rules perform well on most commonly used datasets» (ارائه شده توسط Holte در سال ۱۹۹۳)، بررسی جامعی روی کارایی الگوریتم 1R انجام شد. در مقاله مذکور، از ۱۶ مجموعه داده پر استفاده در یادگیری ماشین برای ارزیابی عملکرد الگوریتم‌های گوناگون استفاده شده است.

فیلم آموزش اصول و روش های متن کاوی Text Mining در فرادرس

کلیک کنید

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

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

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

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

فیلم مجموعه آموزش داده کاوی و یادگیری ماشین – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

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

اگر نوشته بالا برای شما مفید بود، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• آمار، احتمالات و داده‌کاوی
• الگوریتم ژنتیک و محاسبات تکاملی
• یادگیری ماشین و بازشناسی الگو
• مجموعه آموزش‌های برنامه نویسی متلب (MATLAB)
• شبکه‌های عصبی مصنوعی

^^