STREAM হল একটি সিঙ্গেল-পাস, কনস্ট্যান্ট-ফ্যাক্টর অ্যাপ্রক্সিমেশন অ্যালগরিদম যা k-মেডিয়ান সমস্যার জন্য তৈরি হয়েছিল। k-মেডিয়ান সমস্যা হল N ডেটা পয়েন্টকে k ক্লাস্টারে গোষ্ঠীভুক্ত করা যাতে পয়েন্ট এবং তাদের বরাদ্দ করা ক্লাস্টার কেন্দ্রের মধ্যে সম বর্গ ত্রুটি (SSQ) ন্যূনতম হয়। উদ্দেশ্য হল সাদৃশ্যমান পয়েন্টগুলো একই ক্লাস্টারে বরাদ্দ করা, যেখানে এগুলো অন্য ক্লাস্টারের পয়েন্ট থেকে ভিন্ন।
স্ট্রিম ডেটা মডেলে চ্যালেঞ্জ
স্ট্রিম ডেটা মডেলে, ডেটা পয়েন্ট শুধু একবার দেখা যায়, এবং মেমরি ও সময় সীমিত। উচ্চ-গুণমানের ক্লাস্টারিং পেতে, STREAM অ্যালগরিদম ডেটা স্ট্রিমকে m পয়েন্টের বালতি (buckets বা batches) তে প্রক্রিয়া করে, যেখানে প্রতিটি বালতি মেইন মেমরিতে ফিট হয়।
STREAM-এর কাজ করার পদ্ধতি
- প্রতিটি বালতি bᵢ-এর জন্য, STREAM বালতির পয়েন্টগুলিকে k ক্লাস্টারে ক্লাস্টার করে।
- তারপর বালতির তথ্য সারসংক্ষেপ করে শুধু k কেন্দ্র সংক্রান্ত তথ্য রাখে, যেখানে প্রতিটি ক্লাস্টার কেন্দ্র তার ক্লাস্টারে বরাদ্দ পয়েন্টের সংখ্যা দ্বারা ওজনিত (weighted) হয়।
- STREAM পয়েন্টগুলো ফেলে দেয়, শুধু কেন্দ্রের তথ্য রাখে।
- যখন পর্যাপ্ত কেন্দ্র সংগ্রহ করা হয়, ওজনিত কেন্দ্রগুলোকে ক্লাস্টার করে O(k) ক্লাস্টার কেন্দ্রের একটি নতুন গোষ্ঠী তৈরি করা হয়।
- এটি প্রতিটি লেভেলে করা হয় যাতে সর্বোচ্চ m পয়েন্ট সংরক্ষিত থাকে।
এই পদ্ধতির ফলে ডেটা স্ট্রিম k-মেডিয়ানের জন্য একটি वन-পাস, O(kN)-টাইম, O(N^ε)-স্পেস (কোনো কনস্ট্যান্ট ε < 1 জন্য), কনস্ট্যান্ট-ফ্যাক্টর অ্যাপ্রক্সিমেশন অ্যালগরিদম তৈরি হয়।
STREAM-এর সীমাবদ্ধতা এবং CluStream
STREAM নির্দিষ্ট স্থান ও সময়ে গুণমানযুক্ত k-মেডিয়ান ক্লাস্টার দেয়। কিন্তু এটি রেকর্ডের বিবর্তন বা টাইম গ্র্যানুলারিটি বিবেচনা করে না। ক্লাস্টারিং পুরনো, আউটডেটেড স্ট্রিম ডেটা দ্বারা ডোমিনেটেড হতে পারে। ক্লাস্টারটির বৈশিষ্ট্য তখন ওপর নির্ভর করে যখন সেগুলো মূল্যায়ন করা হচ্ছে, এবং কোন টাইম হরাইজন ওপর সেগুলো মাপা হচ্ছে।
উদাহরণস্বরূপ, একজন ব্যবহারকারী গত সপ্তাহ, গত মাস, বা গত বছরের ক্লাস্টার দেখতে চাইতে পারে। এগুলো ভিন্ন হতে পারে। তাই একটি ডেটা স্ট্রিম ক্লাস্টারিং অ্যালগরিদম ব্যবহারকারী-নির্দিষ্ট টাইম পিরিয়ডের ওপর ইন্টারঅ্যাক্টিভভাবে ক্লাস্টার গণনা সমর্থন করতে হবে।
CluStream হল ব্যবহারকারী-নির্দিষ্ট, অনলাইন ক্লাস্টারিং কোয়েরি alapján বিবর্তমান ডেটা স্ট্রিম ক্লাস্টারিং-এর একটি অ্যালগরিদম। এটি ক্লাস্টারিং প্রক্রিয়াকে অনলাইন এবং অফলাইন কম্পোনেন্টে ভাগ করে।
- অনলাইন কম্পোনেন্ট: মাইক্রো-ক্লাস্টার ব্যবহার করে ডেটা স্ট্রিমের সারসংক্ষেপ পরিসংখ্যান গণনা ও সংরক্ষণ করে, এবং মাইক্রো-ক্লাস্টারগুলোর ইনক্রিমেন্টাল অনলাইন ক্যালকুলেশন ও রক্ষণাবেক্ষণ করে।
- অফলাইন কম্পোনেন্ট: সংরক্ষিত সারসংক্ষেপ পরিসংখ্যান ব্যবহার করে (যা টিল্টেড টাইম ফ্রেম মডেলের ওপর ভিত্তি করে) ম্যাক্রো-ক্লাস্টারিং করে এবং ব্যবহারকারী কোয়েরি সমাধান করে।
ঐতিহাসিক এবং বর্তমান স্ট্রিম ডেটা উভয়ের ওপর ভিত্তি করে ক্লাস্টার বিবর্তনশীল ডেটা স্ট্রিম করার জন্য, টিল্টেড টাইম ফ্রেম মডেল (যেমন প্রোগ্রেসিভ লগারিদমিক মডেল) গ্রহণ করা হয়, যা মাইক্রো-ক্লাস্টার সেটের স্ন্যাপশট ভিন্ন গ্র্যানুলারিটিতে সংরক্ষণ করে রিসেন্সি (recency) অনুযায়ী।
