GSP står করে Generalised Sequential Patterns। এটি একটি সিকোয়েনশিয়াল প্যাটার্ন মাইনিং পদ্ধতি যা স্রিকান্ত (Srikant) এবং আগ্রাওয়াল (Agrawal) द्वारा ১৯৯৬ সালে তৈরি করা হয়েছিল। এটি তাদের সশক্ত অ্যালগরিদমের একটি প্রসারন যা সাধারণ আইটেমসেট মাইনিং-এ ব্যবহৃত হয়, যাকে Apriori নামে জানা যায়। GSP সিকোয়েনশিয়াল প্যাটার্নের ডাউনওয়ার্ড-ক্লোজার প্রোপার্টি (downward-closure property) ব্যবহার করে এবং একটি মাল্টি-পাস, অভ্যর্থী-জেনারেট-এন্ড-টেস্ট (candidate generate-and-test) পদ্ধতি আডোপ্ট করে।
GSP অ্যালগরিদমের ধাপসমূহ
- প্রথম স্ক্যান: ডাটাবেসের প্রথম স্ক্যানে সব ফ্রিকোয়েন্ট আইটেম (যাদের মিনিমাম সাপোর্ট আছে) খুঁজে বের করা হয়। প্রতিটি আইটেম একটি ১-ইভেন্ট ফ্রিকোয়েন্ট সিকোয়েন্স দেয় যেটি ওই আইটেমটি ধারণ করে।
- পরবর্তী পাস: প্রতিটি পরবর্তী পাস একটি সিড সেট (seed set) অফ সিকোয়েনশিয়াল প্যাটার্ন এবং পূর্বের পাসে পাওয়া সিকোয়েনশিয়াল প্যাটার্নের সেট দিয়ে শুরু হয়।
- অভ্যর্থী জেনারেশন: এই সিড সেট নতুন সম্ভাব্য ফ্রিকোয়েন্ট প্যাটার্ন তৈরি করে, যাকে ক্যান্ডিডেট সিকোয়েন্স (candidate sequences) বলা হয়। প্রতিটি ক্যান্ডিডেট সিকোয়েন্স সিড সিকোয়েনশিয়াল প্যাটার্নের চেয়ে একটি আইটেম বেশি ধারণ করে (যেখানে প্যাটার্নের প্রতিটি ইভেন্ট এক বা একাধিক আইটেম ধারণ করতে পারে)।
- সিকোয়েন্সের দৈর্ঘ্য (Length): একটি সিকোয়েন্সে আইটেমের উদাহরণের সংখ্যাকে সিকোয়েন্সের দৈর্ঘ্য (length) বলা হয়। তাই, একটি দেয়া পাসে কিছু ক্যান্ডিডেট সিকোয়েন্সের দৈর্ঘ্য একই থাকবে। দৈর্ঘ্য k-র একটি সিকোয়েন্সকে k-সিকোয়েন্স (k-sequence) বলা হয়।
- সাপোর্ট গণনা: Cₖ কে ক্যান্ডিডেট k-সিকোয়েন্সের সেট বোঝাতে দিয়ে। ডাটাবেসের ওপর একটি পাস করে প্রতিটি ক্যান্ডিডেট k-সিকোয়েন্সের সাপোর্ট খুঁজে বের করা হয়। Cₖ-এ যেসব ক্যান্ডিডেট মিন_সাপোর্ট (min_sup) পূরণ করে সেগুলো Lₖ তৈরি করে, অর্থাৎ সব ফ্রিকোয়েন্ট k-সিকোয়েন্সের সেট। এই সেট পরবর্তী পাস (k+1)-এর জন্য সিড সেটে পরিণত হয়।
- টারমিনেশন: অ্যালগরিদম থামে যখন কোনো পাসে নতুন সিকোয়েনশিয়াল প্যাটার্ন পাওয়া যায় না, অথবা কোনো ক্যান্ডিডেট সিকোয়েন্স তৈরি করা যায় না।
অপ্রায়রি প্রোপার্টি ব্যবহার করে ক্যান্ডিডেট ছোট করা
GSP অপ্রায়রি প্রোপার্টি ব্যবহার করে ক্যান্ডিডেট সেট ছোট করে: k-th পাসে, একটি সিকোয়েন্স ক্যান্ডিডেট হবে শুধু যদি এর সব দৈর্ঘ্য-(k−1) সাবসিকোয়েন্স (k−1)-th পাসে পাওয়া একটি সিকোয়েনশিয়াল প্যাটার্ন হয়।
ডাটাবেসের একটি নতুন স্ক্যান প্রতিটি ক্যান্ডিডেট সিকোয়েন্সের সাপোর্ট সংগ্রহ করে এবং একটি নতুন সিকোয়েনশিয়াল প্যাটার্নের সেট Lₖ আবিষ্কার করে। এই সেট পরবর্তী পাসের জন্য সিডে পরিণত হয়। অ্যালগরিদম থামে যখন কোনো পাসে কোনো সিকোয়েনশিয়াল প্যাটার্ন পাওয়া যায় না অথবা কোনো ক্যান্ডিডেট সিকোয়েন্স তৈরি করা যায় না।
ভার্টিক্যাল ডেটা ফরম্যাটে বিশ্লেষণ
অপ্রায়রি-সদৃশ সিকোয়েনশিয়াল প্যাটার্ন মাইনিং কৌশল (ক্যান্ডিডেট জেনারেট-এন্ড-টেস্ট ভিত্তিক) একটি সিকোয়েন্স ডাটাবেসকে ভার্টিক্যাল ডেটা ফরম্যাটে রূপান্তর করে বিশ্লেষণ করা যায়। ভার্টিক্যাল ডেটা ফরম্যাটে, ডাটাবেস (আইটেমসেট: (সিকোয়েন্স_আইডি, ইভেন্ট_আইডি)) রূপের টাপলের একটি সেটে পরিণত হয়।
ইভেন্ট আইডেন্টিফায়ার একটি সিকোয়েন্সের ভিতরে টাইমস্ট্যাম্প হিসেবে কাজ করে। একটি সিকোয়েন্সে i-তম আইটেমসেট (বা ইভেন্ট)-এর ইভেন্ট_আইডি হল i। একটি আইটেমসেট একাধিক সিকোয়েন্সে উপস্থিত থাকতে পারে। একটি দেয়া আইটেমসেটের জন্য (সিকোয়েন্স আইডি, ইভেন্ট আইডি) জোড়ার সেট হল আইটেমসেটের আইডি_লিস্ট (ID_list)।
