RIPPER অ্যালগরিদম কী?

RIPPER হলো একটি জনপ্রিয় রুল ইন্ডাকশন অ্যালগরিদম। এই অ্যালগরিদম ট্রেনিং ইন্সট্যান্সের সংখ্যার সাথে প্রায় লিনিয়ারলি স্কেল করে এবং ওভারলোডেড ক্লাস ডিস্ট্রিবিউশন যুক্ত ডেটাসেট থেকে মডেল তৈরি করতে খুবই উপযোগী। RIPPER নויזি ডেটাসেটের সাথে ভালো কাজ করে কারণ এটি ওভারফিটিং রোধের জন্য একটি ভ্যালিডেশন সেট ব্যবহার করে।

RIPPER-এর কাজ করার পদ্ধতি

RIPPER মেজরিটি ক্লাসকে ডিফল্ট ক্লাস হিসেবে বেছে নেয় এবং মাইনরিটি ক্লাস চিহ্নিত করার জন্য রুল শিখে। মাল্টিক্লাস সমস্যার জন্য, ক্লাসগুলো তাদের ফ্রিকোয়েন্সি অনুযায়ী সাজানো হয়।

মান লও (y₁, y₂, ..., y_c) অর্ডার করা ক্লাসগুলো, যেখানে y₁ সবচেয়ে কম ফ্রিকোয়েন্ট এবং y_c সবচেয়ে বেশি ফ্রিকোয়েন্ট। প্রথম ইটারেশনে, y₁-এ অনuge যেসব ইন্সট্যান্স আছে সেগুলো পজিটিভ এক্সাম্পেল হিসেবে লেবেল করা হয়, বাকিগুলো নেগেটিভ এক্সাম্পেল।

সিকোয়েনশিয়াল কভারিং এপ্রোচ

পজিটিভ এবং নেগেটিভ এক্সাম্পেলের মধ্যে পার্থক্য করার রুল তৈরি করতে সিকোয়েনশিয়াল কভারিং এপ্রোচ ব্যবহার করা হয়। এরপর RIPPER y₂ কে বাকি ক্লাসগুলোর থেকে আলাদা করার রুল বের করে। এই প্রক্রিয়া y_c পর্যন্ত চলতে থাকে, যা ডিফল্ট ক্লাস হিসেবে নির্ধারিত হয়।

রুল গ্রোইং এবং প্রুনিং

RIPPER জেনারেল-টু-স্পেসিফিক পদ্ধতিতে রুল বড়ায় এবং FOIL-এর ইনফরমেশন গেইন মেজার ব্যবহার করে রুলের অ্যান্টেসিডেন্টে যোগ করার জন্য সেরা কানজাঙ্ক্ট বেছে নেয়। নেগেটিভ ইন্সট্যান্স কভার হলে কানজাঙ্ক্ট যোগ করা বন্ধ করা হয়।

নতুন রুলটি ভ্যালিডেশন সেটে এর পারফরম্যান্সের ভিত্তিতে প্রুন করা হয়। নিচের মেট্রিক দিয়ে প্রুনিংয়ের প্রয়োজন কিনা নির্ধারণ করা হয়:

(p - n) / (p + n), যেখানে p (n) হলো ভ্যালিডেশন সেটে রুল দ্বারা কভার করা পজিটিভ (নেগেটিভ) এক্সাম্পেলের সংখ্যা।

এই মেট্রিক রুলের ভ্যালিডেশন সেটে একিউরেসির সাথে মনোটোনিক্যালি সম্পর্কিত। প্রুনিংয়ের পর মেট্রিক উন্নত হলে কানজাঙ্ক্টটি মুছে ফেলা হয়। প্রুনিং রুলে শেষে যোগ করা কানজাঙ্ক্ট থেকে শুরু হয়। উদাহরণস্বরূপ, ABCD → y রুলে প্রথম D, তারপর CD, BCD এইভাবে চেক করা হয়। প্রাথমিক রুল শুধু পজিটিভ ইন্সট্যান্স কভার করলেও, প্রুন করা রুল ট্রেনিং সেটে কিছু নেগেটিভ ইন্সট্যান্স কভার করতে পারে।

স্টপিং কন্ডিশন

রুল বানালে, রুল দ্বারা কভার করা কিছু পজিটিভ এবং নেগেটিভ ইন্সট্যান্স মুছে ফেলা হয়। রুলটি রুলসেটে যোগ করা হয় যতক্ষণ না স্টপিং কন্ডিশন ভাঙে, যা মিনিমাম ডেসক্রিপশন লেন্থ প্রিন্সিপলে ভিত্তি করে।

নতুন রুল যদি রুল সেটের টোটাল রিপ্রেজেন্টেশন লেন্থ কমানো d বিট দিয়ে উন্নত করে, তবে RIPPER রুল যোগ করা বন্ধ করে (ডিফল্টরূপে d = ৬৪ বিট)। আরেকটা স্টপিং কন্ডিশন হলো ভ্যালিডেশন সেটে রুলের এরর রেট ৫০% অতিক্রম করবে না। RIPPER আরও অপ্টিমাইজেশন স্টেপ চালায় যাতে বিদ্যমান রুলগুলো কি बेटার অল্টারনেটিভ রুল দিয়ে রিপ্লেস করা যায় সেটা চেক করে।