具有容錯特性的兩層數據流聚類方法

由育陽 朱紀洪

(清華大學計算機系，北京100084)

楊志宏

(中國醫學科學院藥用植物研究所，北京100193)

近年來數據流環境下的聚類研究工作廣泛展開，具有代表性的相關研究包括基于k-median聚類思想的LOCAL SERACH算法和在此基礎上進行改進的STREAM 聚類算法［1］.文獻［2］將密度聚類與網格聚類聯合應用，提出了基于密度和網格技術的數據流實時聚類算法D-Stream，實現了數據流環境下的高效密度聚類，相關研究被認為是近年來數據流聚類技術的重要發展.文獻［3］首次提出了進化數據流聚類框架CluStream，其基本思想是將聚類過程分為在線的微觀聚類(mi-cro-cluster)過程和離線的宏觀聚類(macro-cluster)過程，CluStream算法是一種通用的數據流聚類算法，用戶可以根據不同處理需求在算法基礎上進行多種方式的擴展分析，該算法靈活的擴展性是其受到廣泛關注的主要原因之一.CluStream同樣存在一些缺點:首先更適合對球形數域空間進行聚類，然而在真實世界數據流中聚簇往往具有非凸的空間形狀;其次對于含有大量噪聲的原始數據適應性較差;最后需要預先指定聚簇數量，極大的影響了原始數據聚簇的形態分布.針對以上問題在CluStream算法的基礎上提出了HPStream算法［4］，采用高維投影和衰減函數來適應對高維數據流的挖掘，但是仍然需要用戶預先指定平均聚類數目.

本文提出了一種具有容錯特性的數據流網格密度聚類算法FTGDStream(Fault-Tolerant Grid-Density Clustering over Data Stream)，設計了一種新的概要數據結構HLSFTS(Hierarchical Lifting Scheme Fault-Tolerant Synopses)，利用概要結構的單次掃描、高壓縮和容錯程度可控的……