盧莉娜等

【摘要】數(shù)據(jù)流聚類是目前國際數(shù)據(jù)庫和數(shù)據(jù)管理領(lǐng)域的新型研究熱點(diǎn)，綜述了數(shù)據(jù)流聚類的研究進(jìn)展，在介紹數(shù)據(jù)流聚類的相關(guān)理論和常用技術(shù)的基礎(chǔ)上，探討了目前基于聚類的數(shù)據(jù)流演化國內(nèi)外研究的狀況，最后展望了將來可能的研究方向。

【關(guān)鍵詞】數(shù)據(jù)流 聚類 交互式數(shù)據(jù)

【中圖分類號】G64 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2014）04-0236-01

一、數(shù)據(jù)流及其聚類

在線交互式數(shù)據(jù)分析與處理的難點(diǎn)在于從多源異構(gòu)，復(fù)雜內(nèi)聯(lián)和動態(tài)演化的角度構(gòu)建新的數(shù)據(jù)處理策略與方法?；谠诰€數(shù)據(jù)獲得的知識通常具有不確定性、不完整性、不協(xié)調(diào)性和不恒常性等特點(diǎn)，對在線數(shù)據(jù)進(jìn)行提煉、排疑、融合、重組等處理，結(jié)合數(shù)據(jù)的動態(tài)變化規(guī)律定性和定量地分析隱藏在數(shù)據(jù)中的知識演化規(guī)律，從而為提高數(shù)據(jù)的應(yīng)用價值提供解決方案和技術(shù)支撐。

在線交互式數(shù)據(jù)處理應(yīng)該具備在線短的時間內(nèi)，有效地整合與調(diào)度資源、數(shù)據(jù)源之間彼此關(guān)聯(lián)、快速演化形式、進(jìn)而提出在用戶體驗方面與之前業(yè)務(wù)截然不同的表現(xiàn)，適應(yīng)在線信息服務(wù)的靈活性和快速演化的要求?；镜膭討B(tài)數(shù)據(jù)模型有三種：1.動態(tài)模糊數(shù)據(jù)模型DFDM；2.動態(tài)模糊數(shù)據(jù)的擴(kuò)展模型EMDFD；3.動態(tài)模糊關(guān)系數(shù)據(jù)模型DFRDM。

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

二、目前國內(nèi)外研究狀況分析

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

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

在最近的數(shù)據(jù)流聚類研究中，有將多種原有技術(shù)進(jìn)行結(jié)合使用，也有很多新穎的方法不斷出現(xiàn)，其中受到廣泛關(guān)注的3類方法是基于網(wǎng)格的數(shù)據(jù)流聚類技術(shù)、子空間聚類技術(shù)、混合屬性數(shù)據(jù)流聚類，代表了當(dāng)前數(shù)據(jù)流聚類研究的主流方向。

（一）D-Stream算法

網(wǎng)格聚類首先將數(shù)據(jù)局空間網(wǎng)格化為由一定數(shù)目的網(wǎng)格單元組成的網(wǎng)格結(jié)構(gòu)，然后將數(shù)據(jù)流映射到網(wǎng)格結(jié)構(gòu)中，應(yīng)用類似于密度的方法，形成網(wǎng)格密度的概念，網(wǎng)格空間里相鄰的高密度網(wǎng)格的集合代表一個聚類，聚類操作就在網(wǎng)格上進(jìn)行。

（二）GSCDS算法

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

（三）HCluStream算法

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

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

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

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

參考文獻(xiàn)：

[1]金澈清，錢衛(wèi)寧.流數(shù)據(jù)分析與管理綜述[J].軟件學(xué)報，2004，15（8）；1172-1181.

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