盧莉娜等

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

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

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

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

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

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

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

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

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

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

（二）GSCDS算法

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

（三）HCluStream算法

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

三、未來集中研究的幾個(gè)方向

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

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

參考文獻(xiàn)：

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

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