FP-ট্রির রিপ্রেজেন্টেশন কী?

FP-ট্রি হলো ইনপুট ডেটার একটি কম্প্যাক্ট রিপ্রেজেন্টেশন। এটিকে ডেটাসেট এক ট্রানজ্যাকশন করেই পড়ে এবং প্রতিটি ট্রানজ্যাকশনকে FP-ট্রিতে একটা পাথে ম্যাপ করে বানানো হয়। অনেক ট্রানজ্যাকশনে কমন আইটেম থাকলে তাদের পাথ ওভারল্যাপ করে।

পাথগুলো যত বেশি ওভারল্যাপ করবে, FP-ট্রি আর্কিটেকচার দিয়ে তত বেশি কম্প্রেশন অর্জন করা যায়। যদি FP-ট্রির সাইজ মেইন মেমরিতে ফিট হয়, তবে ডিস্কে সেভ করা ডেটার ওপর বারবার পাস দিয়ে না যায় সরাসরি মেমরি থেকে ফ্রিকোয়েন্ট আইটেমসেট বের করা সম্ভব।

FP-ট্রির নোড এবং কনস্ট্রাকশন

ট্রির প্রতিটি নোডে একটা আইটেমের লেবেল এবং একটা কাউন্টার থাকে যা দেখায় কতগুলো ট্রানজ্যাকশন ঐ পাথে ম্যাপ হয়েছে। শুরুতে FP-ট্রিতে শুধু রুট নোড থাকে যা null সিম্বল দিয়ে ডিফাইন করা হয়।

FP-ট্রি কনস্ট্রাকশনের ধাপসমূহ

1. ফার্স্ট পাস: ডেটাসেট একবার স্ক্যান করে প্রতিটি আইটেমের সাপোর্ট কাউন্ট বের করা হয়। ইনফ্রিকোয়েন্ট আইটেমগুলো ড্রপ করা হয়, বাকি ফ্রিকোয়েন্ট আইটেমগুলো কমে হয়েছে সাপোর্ট কাউন্ট অনুযায়ী সাজানো হয়।
2. সেকেন্ড পাস: FP ট্রি বানাতে ডেটার ওপর দ্বিতীয় পাস দেওয়া হয়। প্রথম ট্রানজ্যাকশন {a, b} রিভিউ করার পর a এবং b লেবেলযুক্ত নোড তৈরি হয়। null → a → b পাথ তৈরি হয় ট্রানজ্যাকশন এনকোড করার জন্য। পাথে প্রতিটি নোডের ফ্রিকোয়েন্সি কাউন্ট ১।
3. দ্বিতীয় ট্রানজ্যাকশন {b, c, d}: b, c, d আইটেমের জন্য নতুন নোড তৈরি হয়। null → b → c → d পাথ বানানো হয়। এই পাথে প্রতিটি নোডের ফ্রিকোয়েন্সি কাউন্ট ১। যদিও প্রথম দুটি ট্রানজ্যাকশনে b কমন, তবুও তাদের পাথ ডিসজয়েন্ট কারণ কমন প্রিফিক্স শেয়ার করা নেই।
4. তৃতীয় ট্রানজ্যাকশন {a, c, d, e}: এটি প্রথম ট্রানজ্যাকশনের সাথে কমন প্রিফিক্স আইটেম a শেয়ার করে। তাই এর পাথ null → a → c → d → e প্রথম ট্রানজ্যাকশনের পাথ null → a → b এর সাথে ওভারল্যাপ করে। ওভারল্যাপের কারণে a নোডের ফ্রিকোয়েন্সি কাউন্ট ২ হয়ে যায়, নতুন নোড c, d, e-এর কাউন্ট ১ থাকে।

এই প্রক্রিয়া সব ট্রানজ্যাকশন FP-ট্রির পাথে ম্যাপ হয় না পর্যন্ত চলে। FP-ট্রির সাইজ আনকমপ্রেসড ডেটার চেয়ে ছোট হয় কারণ মার্কেট বাস্কেট ডেটাতে অনেক ট্রানজ্যাকশনে কমন আইটেম থাকে।