ความหมายของ STREAM
STREAM เป็นอัลกอริทึมประมาณค่าคงที่แบบ single-pass (หนึ่งผ่าน) และ constant-factor approximation algorithm ที่พัฒนาขึ้นสำหรับปัญหา k-medians ปัญหา k-medians คือ การจัดกลุ่ม N จุดข้อมูล (data points) เป็น k คลัสเตอร์หรือกลุ่ม เพื่อให้ sum squared error (SSQ) ระหว่างจุดและ cluster center ที่พวกเขาถูกมอบหมาย ถูกลดลง (minimized) แนวคิดคือการมอบหมายจุดที่คล้ายกันไปยังคลัสเตอร์เดียวกัน โดยที่จุดเหล่านี้แตกต่างจากจุดในคลัสเตอร์อื่นๆ
โมเดลข้อมูลสตรีม (Stream Data Model)
ในโมเดลข้อมูลสตรีม จุดข้อมูลสามารถมองเห็นได้เพียงครั้งเดียว (seen once) และหน่วยความจำ (memory) และเวลา (time) จำกัด เพื่อทำ clustering คุณภาพสูง (high-quality clustering) อัลกอริทึม STREAM ประมวลผล data streams ใน buckets (ถัง) หรือ batches (ชุด) ของ m จุด โดยแต่ละ bucket พอดีกับ main memory (หน่วยความจำหลัก)
สำหรับแต่ละ bucket bi STREAM จัดกลุ่มจุดของ bucket นั้นเป็น k คลัสเตอร์ มันสรุปข้อมูลของ bucket โดยเก็บเฉพาะข้อมูลเกี่ยวกับ k centers โดยแต่ละ cluster center มีน้ำหนัก (weighted) ตามจำนวนจุดที่มอบหมายให้กับคลัสเตอร์ของมัน
STREAM จากนั้นทิ้งจุดข้อมูล (discards the points) เก็บเฉพาะข้อมูล center เนื่องจากเก็บ centers เพียงพอแล้ว weighted centers จะถูกจัดกลุ่มเพื่อสร้างกลุ่ม O(k) cluster centers อีกกลุ่มหนึ่ง สิ่งนี้ทำซ้ำเพื่อที่ในทุกระดับ จะเก็บได้สูงสุด m จุด แนวทางนี้ทำให้ได้ single-pass, O(kN)-time, O(Nε)-space (สำหรับค่าคงที่ ε < 1) constant-factor approximation algorithm สำหรับ data stream k-medians
ข้อจำกัดและการพัฒนา
STREAM สร้าง quality k-medians clusters ด้วยพื้นที่และเวลาที่แน่นอน อย่างไรก็ มันไม่ได้จัดการกับ การวิวัฒนาการของระเบียน (evolution of the records) และ time granularity (รายละเอียดเวลา) การจัดกลุ่มอาจถูกครอบครองโดยข้อมูลเก่า (older, outdated data) ของสตรีม ลักษณะของคลัสเตอร์อาจเปลี่ยนแปลงทั้งกับเวลาที่พวกเขาถูกประเมิน และ time horizon (ช่วงเวลา) ที่พวกเขาถูกวัด
ตัวอย่างเช่น ผู้ใช้อาจต้องการทดสอบคลัสเตอร์ที่ปรากฏเมื่อสัปดาห์ที่แล้ว เดือนที่แล้ว หรือปีที่แล้ว สิ่งเหล่านี้อาจแตกต่างกัน ดังนั้น อัลกอริทึมการจัดกลุ่ม data stream จึงต้องรองรับความยืดหยุ่นในการคำนวณคลัสเตอร์ผ่านช่วงเวลาที่ผู้ใช้กำหนด (user-defined time periods) แบบโต้ตอบ (interactive manner)
CluStream เป็นอัลกอริทึมสำหรับการจัดกลุ่ม evolving data streams (สตรีมข้อมูลที่วิวัฒนาการ) ตามคิวรี่การจัดกลุ่มออนไลน์ที่ผู้ใช้ระบุ (user-specified, online clustering queries) มันแบ่งกระบวนการจัดกลุ่มเป็น on-line และ offline components
Online component คำนวณและจัดเก็บ summary statistics เกี่ยวกับ data stream โดยใช้ micro-clusters และดำเนินการคำนวณและบำรุงรักษา micro-clusters แบบ incremental online Offline component ทำ macro-clustering และแก้คำถามของผู้ใช้หลายข้อโดยใช้ summary statistics ที่จัดเก็บ ซึ่งขึ้นอยู่กับ tilted time frame model (โมเดลกรอบเวลาที่เอียง)
เพื่อจัดกลุ่ม evolving data streams ตามข้อมูลสตรีมทั้งประวัติศาสตร์และปัจจุบัน โมเดล tilted time frame (เช่น โมเดลลอการิทึมแบบก้าวหน้า progressive logarithmic model) ถูกนำมาใช้ ซึ่งจัดเก็บ snapshots ของเซตของ microclusters ที่ระดับรายละเอียดต่างๆ ขึ้นอยู่กับ recency (ความเป็นปัจจุบัน)
