ความหมายของ Data Stream Clustering
Data stream clustering (การจัดกลุ่มสตรีมข้อมูล) นิยามว่าเป็นการจัดกลุ่มข้อมูลที่ปรากฏต่อเนื่อง (continuously) รวมถึง ข้อมูลโทรศัพท์ (telephone data), ข้อมูลมัลติมีเดีย (multimedia data), ธุรกรรมทางการเงิน (monetary transactions) เป็นต้น Data stream clustering โดยทั่วไปถูกมองว่าเป็น streaming algorithm และวัตถุประสงค์คือ กำหนดลำดับของจุด (sequence of points) เพื่อทำ clustering ที่ดีที่สุดของสตรีม โดยใช้หน่วยความจำ (memory) และเวลา (time) ในปริมาณน้อย
บางแอปพลิเคชันต้องการการจัดกลุ่มอัตโนมัติของข้อมูลดังกล่าวเข้าเป็นเซต ตามความคล้ายคลึงของพวกเขา ตัวอย่างประกอบด้วย แอปพลิเคชันสำหรับ web intrusion detection (การตรวจจับการบุกรุกเว็บ), การวิเคราะห์ Web clickstreams, และ การวิเคราะห์ตลาดหุ้น (stock market analysis)
ความท้าทายเพิ่มเติมจาก Static Clustering
มีหลายวิธีไดนามิก (dynamic methods) สำหรับการจัดกลุ่ม static data sets การจัดกลุ่ม data streams วางแรงกดดันเพิ่มเติม (additional pressure) ให้กับอัลกอริทึมเหล่านั้น สามารถเห็นได้ว่า data stream model of computation ต้องการอัลกอริทึมที่ทำ single pass (หนึ่งผ่าน) ผ่านข้อมูล ด้วย bounded memory (หน่วยความจำจำกัด) และ definite processing time (เวลาประมวลผลที่แน่นอน) ในขณะที่สตรีมอาจเป็น highly dynamic (ไดนามิกสูง) และ evolving over time (วิวัฒนาการตามเวลา)
Methodologies ของ Data Stream Clustering
มีหลาย methodologies (วิธีการ) ของ data stream clustering ดังนี้:
1. Compute and Store Summaries of Past Data (คำนวณและจัดเก็บสรุปข้อมูลอดีต)
เนื่องจากพื้นที่หน่วยความจำจำกัด และข้อกำหนดตอบสนองรวดเร็ว (quick response requirements) คำนวณสรุปของข้อมูลที่เคยมองเห็น จัดเก็บผลลัพธ์ที่เกี่ยวข้อง และใช้สรุปเหล่านั้นเพื่อคำนวณสถิติสำคัญเมื่อจำเป็น
2. Apply a Divide-and-Conquer Strategy (ใช้กลยุทธ์แบ่งและเอาชนะ)
แบ่ง data streams เป็น chunks (กลุ่ม) ตามลำดับการมาถึง (order of arrival) คำนวณสรุปสำหรับ chunks เหล่านี้ และจากนั้น merge (รวม) สรุปเหล่านั้น ด้วยวิธีนี้ โมเดลระดับสูง (higher models) สามารถสร้างขึ้นจาก building blocks (บล็อกสร้าง) ที่เล็กกว่า
3. Incremental Clustering of Incoming Data Streams (การจัดกลุ่มเพิ่มเติมของสตรีมข้อมูลเข้า)
เนื่องจาก stream data เข้าสู่ระบบอย่างต่อเนื่องและเพิ่มเติม (continuously and incrementally) คลัสเตอร์ที่เปลี่ยนแปลงควรถูกปรับปรุงแบบ incremental (incrementally refined)
4. Perform Microclustering as well as Macroclustering Analysis (ทำ Microclustering และ Macroclustering)
Stream clusters สามารถคำนวณได้ในสองขั้นตอน:
คำนวณและจัดเก็บสรุปที่ระดับ microcluster โดยที่ microclusters สร้างขึ้นโดยการใช้ hierarchical bottom-up clustering algorithm
คำนวณ macroclusters (เช่น โดยใช้ clustering algorithm อื่นเพื่อจัดกลุ่ม microclusters) ที่ระดับที่ผู้ใช้ระบุ (user-specified level) การคำนวณสองขั้นตอนนี้ บีบอัดข้อมูลได้อย่างมีประสิทธิภาพ และให้ผลลัพธ์ในพื้นที่ข้อผิดพลาดที่เล็กลง
5. Explore Multiple Time Granularity for Cluster Evolution Analysis (สำรวจ Time Granularity หลายระดับสำหรับการวิเคราะห์วิวัฒนาการคลัสเตอร์)
เนื่องจากข้อมูลที่เป็นปัจจุบันมักเล่นบทบาทแตกต่างจากข้อมูลที่ remote (เก่า/ไกล) ในการวิเคราะห์ stream data ใช้ tilted time frame model เพื่อจัดเก็บ snapshots ของข้อมูลที่สรุปแล้ว ที่จุดต่างๆ ในเวลา
6. Divide Stream Clustering into On-line and Off-line Processes (แบ่ง Stream Clustering เป็นกระบวนการ On-line และ Off-line)
ขณะที่ข้อมูลกำลังสตรีมเข้า สรุปพื้นฐานของ data snapshots ควรคำนวณ จัดเก็บ และอัปเดตแบบ incremental ดังนั้น จำเป็นต้องมี on-line process เพื่อรักษาคลัสเตอร์ที่เปลี่ยนแปลงแบบไดนามิกไว้ ในขณะเดียวกัน ผู้ใช้อาจถามคิวรี่เกี่ยวกับคลัสเตอร์อดีต ปัจจุบัน หรือที่กำลังวิวัฒนาการ การวิเคราะห์เช่นนี้สามารถทำได้แบบ off-line หรือเป็นกระบวนการอิสระจาก online cluster maintenance
