王大將，孫 潔

（1.南京陸軍指揮學院 作戰(zhàn)實驗中心，南京 210045，2.常州技術(shù)師范學院 計算機系，江蘇 常州 213001）

數(shù)據(jù)流挖掘技術(shù)研究

王大將1，孫 潔2

（1.南京陸軍指揮學院 作戰(zhàn)實驗中心，南京 210045，2.常州技術(shù)師范學院 計算機系，江蘇 常州 213001）

數(shù)據(jù)流挖掘技術(shù)是數(shù)據(jù)挖掘技術(shù)的新研究方向之一。文章介紹了數(shù)據(jù)流、數(shù)據(jù)流挖掘的特點，對現(xiàn)有的數(shù)據(jù)流挖掘算法進行了總結(jié)、分析，提出了數(shù)據(jù)流挖掘的研究方向和應用前景。

數(shù)據(jù)流；數(shù)據(jù)流挖掘；聚類；分類；頻繁模式

0 引言

近年來，隨著軟硬件技術(shù)的高速發(fā)展，人們獲取數(shù)據(jù)的能力得到了很大的提高，獲取數(shù)據(jù)的領(lǐng)域越來越廣。經(jīng)常有大量需要處理的數(shù)據(jù)以很快的速度產(chǎn)生。由于數(shù)據(jù)量太大、而且數(shù)據(jù)產(chǎn)生的速度太快，如果仍然按傳統(tǒng)的數(shù)據(jù)庫應用模式來處理這些數(shù)據(jù)，則這樣的任務將是不可能完成的。于是，一種新型的解決方案應運而生，其最大特點是，待處理的數(shù)據(jù)以一種動態(tài)、流式的形式出現(xiàn)，即數(shù)據(jù)流(Data Streams)，對數(shù)據(jù)流中的數(shù)據(jù)只能按順序進行一次或有限次的訪問[1]。與傳統(tǒng)的靜態(tài)存儲在磁盤上的數(shù)據(jù)相比，數(shù)據(jù)流具有連續(xù)快速、短暫易逝以及不可預測等特點，因此對數(shù)據(jù)流的處理必須要實時地進行，并且無法直接訪問所有的數(shù)據(jù)，只能存儲數(shù)據(jù)的摘要信息。數(shù)據(jù)流的這些特性使得傳統(tǒng)的數(shù)據(jù)挖掘算法不再適用，基于數(shù)據(jù)流的挖掘算法也就成了當前的研究熱點和難點。

1 數(shù)據(jù)流

所謂數(shù)據(jù)流就是大量連續(xù)到達的、潛在無限的、隨時間不斷變化的數(shù)據(jù)有序序列，令t表示任一時間點，dt表示在該時間點到達的數(shù)據(jù)，則數(shù)據(jù)流可表示為{…,dt-1,dt,dt+1,…}。這些數(shù)據(jù)或其摘要信息無法全部保存在內(nèi)存中，只能按照順序存取并被讀取一次或有限次。許多應用領(lǐng)域，例如通信領(lǐng)域的通話記錄數(shù)據(jù)分析、網(wǎng)絡流量分析、電子商務和在線股票交易數(shù)據(jù)分析、氣象衛(wèi)星數(shù)據(jù)分析等等都面臨著如何分析和處理數(shù)據(jù)流的問題，都要求在海量、連續(xù)、快速到達的數(shù)據(jù)流上應用高級的數(shù)據(jù)分析和數(shù)據(jù)挖掘技術(shù)以捕捉趨勢、模式、變化、孤立點等知識。

數(shù)據(jù)流具有與傳統(tǒng)數(shù)據(jù)庫模式下的數(shù)據(jù)集合不同的特征：數(shù)據(jù)流中的數(shù)據(jù)是隨著時間的推進而連續(xù)不斷產(chǎn)生的，其總量潛在無限；數(shù)據(jù)流中的數(shù)據(jù)是動態(tài)變化的；數(shù)據(jù)流中數(shù)據(jù)的到達次序是不可控制的，對數(shù)據(jù)流中數(shù)據(jù)的讀取與處理只能被動地依據(jù)數(shù)據(jù)的到達次序進行，不可能通過改變數(shù)據(jù)的輸入次序來對處理的結(jié)果進行改進。由于數(shù)據(jù)流具有時效性、實時性、無限性和瞬時性等特點，在處理數(shù)據(jù)流時，必須注重時空性，對數(shù)據(jù)流中的數(shù)據(jù)通常只能采取單一掃描的線性算法，用精度換時間，盡量在對數(shù)據(jù)的一次訪問中獲得較優(yōu)的解。一些傳統(tǒng)數(shù)據(jù)庫應用中常用的操作，如排序、找最值、計數(shù)等在數(shù)據(jù)流處理中是不可行的，并且一般的數(shù)據(jù)流算法是不可回溯的。

2 數(shù)據(jù)流挖掘技術(shù)

數(shù)據(jù)挖掘也稱為知識發(fā)現(xiàn)，就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。數(shù)據(jù)流挖掘就是從連續(xù)不斷的數(shù)據(jù)流中提取潛在有用的信息和知識的過程。

針對數(shù)據(jù)流的特殊性，許多傳統(tǒng)的數(shù)據(jù)挖掘算法不適合于數(shù)據(jù)流的挖掘，數(shù)據(jù)流的數(shù)據(jù)挖掘系統(tǒng)應滿足以下標準：處理單條記錄的平均時間要短，否則數(shù)據(jù)的處理會落后于數(shù)據(jù)的產(chǎn)生；使用的內(nèi)存數(shù)量是相對固定的，與數(shù)據(jù)的量是沒關(guān)系的；一條數(shù)據(jù)記錄最多使用一次，因為系統(tǒng)沒有時間第二次訪問一條數(shù)據(jù)，并且數(shù)據(jù)量很大，處理過的數(shù)據(jù)很快被存到低速設備上去，要重新訪問非常困難；系統(tǒng)隨時都可以提供有效的信息，而不是在處理完所有數(shù)據(jù)后再提供信息，因為數(shù)據(jù)不可能被處理完；隨著數(shù)據(jù)產(chǎn)生的變化，系統(tǒng)應當在任何時候都保持最新，既能正確反應數(shù)據(jù)中新出現(xiàn)的模式，又不使未過時的信息丟失。由于數(shù)據(jù)產(chǎn)生速度非?？?，同時，內(nèi)存相對于數(shù)據(jù)量又是非常有限的，所以滿足前三項是非常困難的，所以現(xiàn)有的多數(shù)數(shù)據(jù)流挖掘算法，在結(jié)果的準確性可以接受的前提下，盡量減少實際處理的數(shù)據(jù)的量。

目前數(shù)據(jù)流挖掘方面的研究成果主要集中在數(shù)據(jù)流的聚類、分類和頻繁模式挖掘方面。雖然已存在許多有效的方法應用于挖掘靜態(tài)數(shù)據(jù)集，但數(shù)據(jù)流挖掘?qū)@些方法又有額外的限制，只能使用有界的內(nèi)存和有限的處理時間，并對數(shù)據(jù)單遍掃描。為了有效的挖掘出數(shù)據(jù)流中潛在的信息，需要對傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)進行改進或者針對數(shù)據(jù)流提出新的方法。

2.1 數(shù)據(jù)流聚類

聚類技術(shù)是把一個數(shù)據(jù)集中的數(shù)據(jù)分成不同的組，在同一組中的數(shù)據(jù)彼此相似，不同組的數(shù)據(jù)彼此相異。聚類可以應用在模式識別、空間數(shù)據(jù)分析、圖象處理、市場調(diào)查等方面。數(shù)據(jù)流上的聚類就是通過單遍掃描數(shù)據(jù)流，持續(xù)地將數(shù)據(jù)流數(shù)據(jù)對象分組成多個類，在同一個簇中的數(shù)據(jù)對象之間具有較高的相似度，而不同簇間的數(shù)據(jù)對象的相似度很小。數(shù)據(jù)流的聚類算法不同于傳統(tǒng)數(shù)據(jù)的聚類算法，必須是增量式的，對聚類的表示要簡潔，對新數(shù)據(jù)的數(shù)理要快速，對噪音和異常數(shù)據(jù)必須是穩(wěn)健的。因而，基于數(shù)據(jù)流的聚類算法是在一個相對較小的內(nèi)存空間上，對數(shù)據(jù)流進行一遍掃描后，把數(shù)據(jù)集合分成不同的組。另外，在一些應用中需要對多條數(shù)據(jù)流進行聚類。對多條數(shù)據(jù)流聚類是將每一數(shù)據(jù)流看成一個聚類對象，考慮的是數(shù)據(jù)流間的相似度。近年來，根據(jù)實際使用情況，人們不僅希望知道數(shù)據(jù)流在某一時刻的聚類結(jié)果，也希望得到在某一時間段中產(chǎn)生的聚簇結(jié)果及聚簇是如何隨時間變化的，從而得到數(shù)據(jù)流的生成規(guī)律，從而產(chǎn)生了基于網(wǎng)格和密度的聚類算法。例如文獻[2]中提出的GDDS算法，該算法把數(shù)據(jù)空間劃分為網(wǎng)格單元，然后在網(wǎng)格的基礎上對稠密的單元進行聚類。

2.2 數(shù)據(jù)流分類

分類是一種非常重要的數(shù)據(jù)挖掘技術(shù)，其目的是根據(jù)已有的數(shù)據(jù)集學習構(gòu)造一個分類函數(shù)或分類模型,該分類模型能夠?qū)⑿碌綐颖居成涞揭粋€具體的類別上。傳統(tǒng)的分類模型包括決策樹、決策規(guī)則、貝葉斯理論分類、神經(jīng)網(wǎng)絡法、支持向量機法、K近鄰分類器、范例式推理、進化算法、粗糙集法及模糊集法等。但是，這些算法都要求對數(shù)據(jù)集進行多次掃描，因此并不適用于數(shù)據(jù)流的分類。因為,隨著時間的更迭而生成的數(shù)據(jù)流,其數(shù)據(jù)量大且數(shù)據(jù)分布可能會發(fā)生變化，即概念漂移(concept—drift)。數(shù)據(jù)流的這些特性要求分類算法不僅能夠利用有限的內(nèi)存和空間，而且學習到的模型能夠不斷調(diào)整來適應新流入的數(shù)據(jù)以提高分類準確率。數(shù)據(jù)流上的分類就是提出一個分類模型通過單遍掃描數(shù)據(jù)流，持續(xù)地利用分類模型將數(shù)據(jù)流對象影射到某一個給定的類別中，并以特定的頻度重新修正模型以消除舊樣本的影響。例如文獻[3]中提出的增量決策樹算法，該方法用固定的內(nèi)存和固定的時間為每個樣本構(gòu)建一顆決策樹，有效地解決了時間、內(nèi)存和樣本對高速數(shù)據(jù)流上的數(shù)據(jù)挖掘的限制。

2.3 數(shù)據(jù)流頻繁模式挖掘

頻繁模式挖掘的任務是通過對一個數(shù)據(jù)集進行統(tǒng)計，找出出現(xiàn)頻率最高的一個數(shù)據(jù)或一組數(shù)據(jù)，從而挖掘出頻繁模式。雖然頻繁模式挖掘已經(jīng)被廣泛研究，出現(xiàn)了許多經(jīng)典算法，但這些算法難以增量式更新，不適合數(shù)據(jù)流挖掘。因為數(shù)據(jù)流的流動性和連續(xù)性，數(shù)據(jù)流上頻繁模式信息隨著數(shù)據(jù)流的連續(xù)產(chǎn)生而不斷發(fā)生變化。在大多數(shù)數(shù)據(jù)流應用中，用戶往往更加關(guān)注數(shù)據(jù)流上最近事務數(shù)據(jù)所包含的信息。數(shù)據(jù)流上的頻繁項集挖掘就是單遍掃描數(shù)據(jù)流來連續(xù)發(fā)現(xiàn)其中的頻繁項集。對于數(shù)據(jù)流，內(nèi)存的限制導致只能選擇可能成為頻繁的項來進行快速近似地進行頻度計數(shù)?，F(xiàn)有的頻繁模式挖掘算法主要分為兩類：批處理方法和啟發(fā)式方法。批處理方法的主要思想是對數(shù)據(jù)流分段，通過分段上的局部頻繁模式來求解全局近似頻繁模式，該類算法實時性不高。啟發(fā)式方法的主要思想是隨著數(shù)據(jù)流中數(shù)據(jù)的不斷到達，由已知頻繁模式逐步生成新的頻繁模式，該方法能夠隨著數(shù)據(jù)的到達直接進行處理，在一定程度上可以實時地反應頻繁模式的變化，但模式估計與查詢精度較低。針對數(shù)據(jù)流的無限性、流動性和不規(guī)則性等特點，人們不斷提出新的頻繁模式挖掘算法。如文獻[4]提出的FP-IDS算法，該方法采用時序數(shù)據(jù)分段的思想，逐段挖掘局部頻繁項集，然后以及局部頻繁項集有效地挖掘出所有的全局頻繁項集。

2.4 數(shù)據(jù)流挖掘應用

由于數(shù)據(jù)流在人們的日常生活很常見，目前，數(shù)據(jù)流挖掘系統(tǒng)已初步得到發(fā)展，主要應用于一些需要處理海量數(shù)據(jù)的重要部門[5]。例如：用于股票市場的數(shù)據(jù)流系統(tǒng)，可以幫助人們預測股市的起伏；用于零售業(yè)的交易數(shù)據(jù)流挖掘系統(tǒng)，可以對促銷活動的有效性、顧客的忠誠度等進行分析；用于醫(yī)學監(jiān)視中的數(shù)據(jù)流分析系統(tǒng)，可以得到治療效果的測量數(shù)據(jù)，發(fā)現(xiàn)生死攸關(guān)的征兆；用于航天科技中的數(shù)據(jù)流挖掘系統(tǒng)，可以從空間對象的實時圖像中提取模式，從而利用高度自動化的航天器以及傳感器進行空間探測；用于移動車輛的監(jiān)控和信息提取的數(shù)據(jù)流系統(tǒng)，可以對駕駛員進行行為分析；用于網(wǎng)絡監(jiān)控的數(shù)據(jù)流系統(tǒng)，通過跟蹤網(wǎng)絡中數(shù)據(jù)的流動變化來研究網(wǎng)絡流通模式及可能的非法入侵等。隨著技術(shù)的不斷發(fā)展，數(shù)據(jù)流挖掘技術(shù)將在更多的領(lǐng)域得到應用。

3 結(jié)論

隨著信息技術(shù)的發(fā)展，越來越多的應用領(lǐng)域產(chǎn)生或獲得了大量的源源不斷的數(shù)據(jù)流。數(shù)據(jù)流的分析與挖掘已成為一個研究熱點。本文介紹了數(shù)據(jù)流挖掘有關(guān)的概念、特點、研究現(xiàn)狀和應用。由于數(shù)據(jù)流具有的時效性、實時性、無限性和瞬時性等特點，傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)面臨巨大的挑戰(zhàn)，它們必須根據(jù)數(shù)據(jù)流的需要重新建模，當前的有關(guān)算法的研究有很多是在傳統(tǒng)的增量式挖掘技術(shù)基礎之上發(fā)展而來的，探索數(shù)據(jù)流挖掘技術(shù)與傳統(tǒng)的靜態(tài)數(shù)據(jù)挖掘技術(shù)之間的本質(zhì)區(qū)別，提出更有效、新穎、快速挖掘算法是當前研究面臨的重要問題。數(shù)據(jù)流挖掘面臨著內(nèi)存的限制、實時響應、單次掃描、結(jié)果的近似性、算法的自適應性等困難。提高數(shù)據(jù)流挖掘算法的精度和適應性，使得算法具有較小的內(nèi)存開銷和快速的數(shù)據(jù)處理能力，并利用挖掘的知識幫助人們做出決策將會是一項非常有實際應用前景的工作。

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

[2]高永梅，黃亞樓.一種基于網(wǎng)格和密度的數(shù)據(jù)流聚類算法,計算機科學[J],2008：35（2）.

[3]G.Hulten,L.Spencer, P.Domingos.Mining Time-changing Data Streams[C].In Proc.of ACM SIGKDD,2001.

[4]朱瓊，施榮華.一種數(shù)據(jù)流中的頻繁模式挖掘算法[J].計算機應用,2008,28(6).

[5]王濤，李舟軍，顏躍進，陳火旺.數(shù)據(jù)流挖掘分類技術(shù)綜述[J].計算機研究與發(fā)展，2007，44（11）.

TP274

A

1002－6487（2010）07－0161-02

王大將（1983-），女，江蘇淮安人，助教，研究方向：數(shù)據(jù)挖掘、智能決策。

孫潔（1983-），女，江蘇鹽城人，助教，研究方向：粗糙集、神經(jīng)網(wǎng)絡。

（責任編輯/易永生）