數據流聚類的分析與思考

盧莉娜等

【摘要】數據流聚類是目前國際數據庫和數據管理領域的新型研究熱點，綜述了數據流聚類的研究進展，在介紹數據流聚類的相關理論和常用技術的基礎上，探討了目前基于聚類的數據流演化國內外研究的狀況，最后展望了將來可能的研究方向。

【關鍵詞】數據流 聚類 交互式數據

【中圖分類號】G64 【文獻標識碼】A 【文章編號】2095-3089（2014）04-0236-01

一、數據流及其聚類

在線交互式數據分析與處理的難點在于從多源異構，復雜內聯和動態演化的角度構建新的數據處理策略與方法。基于在線數據獲得的知識通常具有不確定性、不完整性、不協調性和不恒常性等特點，對在線數據進行提煉、排疑、融合、重組等處理，結合數據的動態變化規律定性和定量地分析隱藏在數據中的知識演化規律，從而為提高數據的應用價值提供解決方案和技術支撐。

在線交互式數據處理應該具備在線短的時間內，有效地整合與調度資源、數據源之間彼此關聯、快速演化形式、進而提出在用戶體驗方面與之前業務截然不同的表現，適應在線信息服務的靈活性和快速演化的要求。基本的動態數據模型有三種：1.動態模糊數據模型DFDM；2.動態模糊數據的擴展模型EMDFD；3.動態模糊關系數據模型DFRDM。

隨著時間的變化，數據的統計性質往往會發生變化，即數據的分布是隨時間而變化的，這也被稱為“分布漂移”。造成這種分布變化的因素可以分為兩種，一種是數據本身的本質“概念”變化，另一種是噪聲的變化，如在不同的時刻，搜集數據時條件不相同，數據噪聲也不相同，在這樣的數據上的聚類就是一個新問題——演化聚類。在數據流上進行聚類，其基本任務就是要在對當前數據進行聚類的同時，隨著新數據的不斷流入，動態地調整和更新聚類的結果以真實反映數據流的聚類形態。這種在線的增量聚類使得常規的聚類技術難以在數據流上直接應用，算法必須要滿足如下要求：1.內存限制。由于內存容量有限，不可能將數據量龐大的數據流全部存儲于內存，再進行聚類。在內存中只維護一個反應當前數據流特征的概要數據結構是目前常用的技術；2.實時性。數據流聚類要求具備很短的響應時間，能夠響應anytime的用戶聚類請求，要求算法處理速度快；3.單遍掃描或者有限次掃描。在對數據流進行聚類時，只能按數據點流入的順序訪問一次或幾次。以上只是基本要求，對一個搞笑的實時數據流聚類算法來說，還必須考慮：1.聚類簇數事先未知。算法不可能預知數據流將會被分為幾個聚類簇，不但如此，隨著新數據不斷地流入，聚類簇數目和狀態都在不斷地變化；2.對孤立點的分析能力。由于數據流的不斷流動和進化，當前時間窗口內的孤立點，有可能隨著新數據的加入變成一個新聚類簇，也有可能仍然是孤立點而被剔除，聚類算法必須能對這一情況及時鑒別和處理；3.聚類形狀任意。傳統的基于歐式距離的相似度準則易于產生球形聚類，真實數據流所隱含的聚類簇一般包含很多非凸形狀的聚類，算法必須具備識別任意形狀聚類的能力。

二、目前國內外研究狀況分析

在演化聚類中，算法最終的目的是要為每個時刻的數據給出聚類結果，該結果不僅要求能夠把當前時刻的數據劃分的很好，還要求各時刻的聚類模式在時間軸上保持一定的連續性。聚類結果應保持時間軸上的連續性是演化聚類問題中很重要的一點，它來自于實際應用的需要。在實際應用中，這樣的性質能帶來很多益處。演化聚類算法可以是在線的，第一個在線的演化數據聚類方法是CHAKRABARTI D等在evolutionary clustering論文中提出。他們在靜態聚類的損失函數上增加一個時間損失項，每一個聚類都被匹配到上一時刻距離最近的那個聚類，把所有這種配對的聚類之間的距離相加作為時間損失。這種啟發式最近匹配方法可能不穩定，會對聚類中心小的擾動十分敏感。

在研究中，其中包括兩種數據形式：1.與傳統的學習問題相同，數據樣本被表示為共同的有限維特征空間中的向量。2.關系型數據。數據樣本沒有自身的特征表示，而只有樣本之間的鏈接關系，這樣的數據實際構成一個圖，圖的結點就是一個樣本點，而隨時間推進，結點之間的鏈接關系會發生變化，之前存在的鏈接可能消失，之前沒有的鏈接可能建立。在非參數貝葉斯方法中能夠發現多個關聯演化子集中的復雜演化模式，包括聚類的出現、變化、消失以及在不同子集之間的傳播，而且，在該方法中，所有的聚類數都是從數據中自動學習，不需要人為指定。另外，在馬爾可夫跳轉模型中不難發現難點在于如何定義“狀態”以及不同時刻之間的轉移矩陣。該方法采用了傳統的優先混合模型，需要用戶指定每一時刻的聚類數目，屬于參數化方法。

在最近的數據流聚類研究中，有將多種原有技術進行結合使用，也有很多新穎的方法不斷出現，其中受到廣泛關注的3類方法是基于網格的數據流聚類技術、子空間聚類技術、混合屬性數據流聚類，代表了當前數據流聚類研究的主流方向。

（一）D-Stream算法

網格聚類首先將數據局空間網格化為由一定數目的網格單元組成的網格結構，然后將數據流映射到網格結構中，應用類似于密度的方法，形成網格密度的概念，網格空間里相鄰的高密度網格的集合代表一個聚類，聚類操作就在網格上進行。

（二）GSCDS算法

最近的研究中，子空間聚類技術也被借鑒到數據流模型，最近公布的GSCDS算法就是一個代表。子空間聚類算法是一類在數據空間的所有子空間搜尋聚類的方法，根據搜索策略不同一般分為自底向上的模式和自頂向下的模式。GSCDS算法充分利用自底向上網格方法的壓縮能力和自頂向下網格方法處理高維數據的能力，將它們結合起來應用于實時數據流。

（三）HCluStream算法

真實數據流一般具有混合屬性，全連續或全離散屬性的數據流在現實中幾乎不存在，而目前大多的算法僅局限于處理連續屬性，對離散屬性采取簡單的舍棄方法。為了使算法有效處理真實數據流，有專家學者提出了一種基于混合屬性的數據聚類算法HCluStream。

三、未來集中研究的幾個方向

針對在線數據實時分類的研究，將在線數據流進行整合，從而應用到具體問題中。這些數據流中往往包含多種類型的數據，不僅是數值型數據，還包含其他類型的數據，因此該算法能對這些數據類型進行實時分類。在線交互式數據具有不確定性，不穩定性等特點。不同類型的是數據，例如在線視頻流，各自具有不同的特點。從解決實際問題的角度出發，需要對這些多源異質數據源特性進行深入分析，但是目前研究中對多源異質數據源的特征提取考慮較少。其主要原因是對這些數據流對時間的要求很高，數據特征不明顯、并且數據量巨大，進行分析有很大的難度。針對動態數據分析進行抽象建模是解決問題的關鍵。目前針對在線交互式數據問題的研究中，常見的解決思路是將數據提取后進行靜態分析，再利用相關的成熟理論和方法進行求解，不能實現真正意義上的是實時性，這樣建立的模型存在的一個主要問題是為了模型的標準化，忽略了一些實際問題要素。

未來的研究會集中在以下幾個方面：第一，基于資源約束的自適應實時數據流聚類。主要針對無線傳感網絡等資源約束環境進行數據流聚類。第二，高維度實時數據流的聚類。大多數真實數據流都具有高維特性，高維空間中對象分布稀疏，噪聲不易識別，是一個較難解決的問題，也給聚類帶來嚴重的障礙。第三，分布式環境下的多數據流實時聚類。在分布式環境中，數據流廣泛分布于分散的、異構的數據源中，研究新的技術使其在分布式環境具有更好的健壯性和更高的效率是一個亟需解決的難題。

參考文獻：

[1]金澈清，錢衛寧.流數據分析與管理綜述[J].軟件學報，2004，15（8）；1172-1181.

[2]周曉云，張柏禮.高維數據流聚類及演化分析研究[J].計算機研究與發展，2006，43（11）：2005-2011.