基于數據流的移動數據挖掘研究綜述

摘要：無線網絡和移動設備的應用為我們帶來巨大的便利，可以隨時隨地獲得信息，同時它也引發了對高效數據流分析工具的需求。移動數據挖掘是在普適環境下的數據流挖掘，從連續的數據流中發現知識。討論了數據流、數據流管理系統和移動數據挖掘以及它們的特點，介紹了該領域的一些研究成果，突出了面臨的挑戰和一些相應的策略，并對這些策略進行了比較，最后展望了這一領域的研究前景。

關鍵詞：移動數據挖掘; 數據挖掘; 數據流; 普適計算

中圖法分類號：TP391文獻標識碼：A

文章編號：1001－3695(2007)01－0005－05

1991 年Weiser 提出普適計算[1](Ubiquitous Computing)。普適被認為是一種特殊的環境特征，隨著移動設備以及網絡的發展，這一特征越來越受到重視。Robert Grossman根據系統的復雜性、數據與算法的結合程度、數據模型、分布程度將數據挖掘系統劃分為四代。經過十多年的發展，數據挖掘的研究重點逐漸從發現方法轉向系統應用，注重知識發現策略和技術的集成以及學科之間的相互滲透。數據挖掘系統也從第一、第二代系統轉向第三、第四代系統的研制。

移動數據挖掘屬于第四代數據挖掘系統，它最大的特色是將數據挖掘轉移到嵌入式設備和移動環境。自2002年以來，移動數據管理已經召開了兩次國際會議，主要討論都是圍繞普適環境這一特征，討論如何管理在該環境下的數據，開發移動設備上的復雜計算程序并進行移動數據挖掘。移動數據挖掘與傳統挖掘方法不同，具有很多獨特的地方，它們會導致傳統的數據挖掘算法無效。這種現象主要的原因是在應用上的不同，即移動挖掘算法和系統需要為應用量身定做。

（1）傳統的數據挖掘系統面向的應用是知識發現、模式識別、決策支持、預測預警等，它們關心挖掘結果的正確性、完整性，導致了這類應用空間消耗大、計算密集、計算時間長。

（2）移動數據挖掘系統面向的是移動用戶，這些用戶需要獲得的是即時數據挖掘結果。對于一些檢測和監控程序，甚至需要處理實時數據獲得實時結果和反饋。如旅行或者出差的時候，用戶無法在股票市場或PC 機前關注自己的股票信息，但是又希望了解最新的股票動態，他們可以在智能手機等移動設備上通過移動數據挖掘系統對股市數據流進行挖掘，利用全局優化的方法自動篩選股票進行監視，并預測股票發展趨勢[2]。再如，在交通工具上安裝傳感器，通過分析傳感器回傳的狀態數據，及時發現可能發生嚴重事故的狀態，提前報警，阻止事故發生[3]。

無線網絡及移動設備帶來的新基礎架構和開發環境，引發了面向數據流分析系統的研究和開發。其研究目的是如何在普適性環境下進行挖掘，并提出一個較為通用的面向數據流的挖掘系統的架構。本文介紹了數據流環境的特點以及數據流管理系統，重點突出了普適環境和數據流給移動數據挖掘帶來的挑戰；詳細描述了移動數據挖掘所采用的幾種處理數據流的策略，著重介紹了AOG方法，并對這些策略進行了比較。

1數據流特點與數據流管理系統

數據流與移動數據挖掘緊密相關，移動挖掘的數據大部分是數據流，而且未來移動數據挖掘的一個發展方向是在數據流管理系統上建立移動數據挖掘系統。

網絡上的數據是以流形式傳輸的，網絡管理軟件是最早包含了數據流處理的軟件，它可以統計網絡上的數據包，并可以進行實時的分析。隨著數據流應用的發展，在設備中嵌入實時處理程序來處理數據流的方法已經不能滿足應用需求，如衛星返回拍攝的圖像數據、宇宙探測器發送探測數據、傳感器監控器傳回的實時狀態信息。人們希望存儲這樣一些數據，使它們能夠查詢方便，所以提出了數據流管理系統(Data Stream Mana￣gement System，DSMS)。

數據流模型中，需要處理的數據可能不在內存或硬盤上，因為數據流是連續的，可能還沒到達。數據流模型與傳統關系數據模型有四個不同點[4]：①數據記錄是在線的，即數據不是一開始就各就各位，其存儲在管理系統中以備使用。

②DSMS 無法知道下一個到達的數據是什么，更無法控制待處理的數據記錄的順序，在同一個數據流中不行，跨數據流更加不可能。

③本質上，數據流的長度可以是無限制的，DSMS 可能需要接收高速連續的、隨時間變化而變化的數據流。

④數據流中的記錄一旦被處理、被拋棄或被歸檔后，無論是哪一種方式，其查詢都不再方便。當然有部分可以存放在主存中，這些數據一般是一些概要數據，細節數據一般很難再找回來。很多時候，數據流處理算法的關鍵在于設計一個遠小于數據集規模的結構，從而可以在內存中處理數據。相對于數據流的規模而言，這種名為概要數據結構(Synopsis Data Structure)的規模至多是次線性的，即如果流的長度為N，則概要數據結構大小不超過O(polylog(N))，并且處理流上每一組數據的時間不超過O(polylog(N))[4]。

數據流查詢與傳統DBMS 的查詢在很多地方相同，主要的差別在于前者是連續查詢(Continuous Query)，后者是一次查詢(Onetime Query)[5]。連續查詢是指不僅對已經到達的數據進行查詢，在新數據到來時還會不斷更新查詢結果；一次查詢只是針對當前數據快照的查詢。實際的數據流查詢中還區分下面兩種查詢：①預定義查詢(Predefined Query)，是指在查詢語句發出前，相關的數據還沒有到達，所以可以忽略對歷史記錄的操作；②特別查詢(Ad hoc Query)，是指在查詢語句發出時，部分數據已經到達，則需處理已經接收的數據以及后來接收的數據。前者一定是連續查詢，而后者可能是連續查詢也可能是一次查詢。

STREAM和Aurora是兩個著名的DSMS研究項目。STREAM（Stanford Stream Data Manager）是斯坦福大學研究的通用數據流管理系統，可以對多個數據流以及關系表進行連續查詢[6]。系統設計了一種聲明式的查詢語言——CQL（Conti￣nuous Query Language），它繼承了部分SQL語言的語法，同時引入語法表達新語義：從關系到關系的操作、從數據流到關系的操作以及從關系到數據流的操作。

Aurora系統類似于工作流系統，所有處理的流程采用盒框（Box）與箭頭（Arrow）描述，盒框代表數據處理，箭頭表示數據的流動，整個流程可以轉換成等價的有向無環圖。系統內建八種原始的操作符，可以使用這些操作符來描述各種操作處理。Aurora系統也維護歷史數據，提供對特別查詢的支持[7]。

2面臨的挑戰

決策者為了避免把太多精力用在冗雜的數據處理上，一般由挖掘系統代替決策者做底層分析工作，輸出有用的、值得重視的決策信息，然后再由決策人員綜合其他各種因素進行評估，作最終決定，這種挖掘系統可以稱為決策支持系統。由于移動環境和數據流的特點，決策支持所采取的方法會有所不同，例如，為了適應高速的數據流，目前有些基于移動設備的挖掘算法采用負載脫落的方法保證與輸入的數據流同步。雖然在PC 機上的挖掘也是采用不精確的抽樣技術，但是兩者有區別：

（1）PC 機上具備大量的內存與外存，可以采用多次抽樣來彌補采樣所造成的正確性損失。所以采樣在提高算法計算速率的同時，又可以保證相當的正確性。

（2）移動環境不像PC具有充足的資源，可以進行多次抽樣：①PDA 存儲容量小，無法保存太多數據；②數據流的特點是數據量大、持續時間長；③可能要求挖掘程序對數據流實時響應。因此在這種情況下作出負載脫落的選擇，代價是犧牲準確性。

從上面分析可以看到，在移動環境下，由于受到一些限制，在系統設計和方法選擇以及性能和資源之間必須慎重考慮。在移動環境下進行數據流挖掘有以下幾個特有的挑戰：

（1）資源限制。無論是移動設備本身、CPU 處理速度、內存、輔助存儲器容量還是無線網絡帶寬，遠遠比不上普通PC 和有線網絡，因此希望智能實體具備資源感知意識。

（2）數據流同步。由于移動挖掘的數據可能是連續的、不間斷的數據流，如果算法處理太慢可能會跟不上數據流的速度，所以多數情況下采用一次遍歷(Onepass)的算法取代多次遍歷算法，其挖掘的效果稍差一些，但是有實驗結果表明正確性可以與多次遍歷相當[8，9]。

（3）通信成本。單機挖掘系統或者是普通的分布式挖掘系統可以不考慮通信成本。但是在現階段，無線網絡是通過流量來計費的，而且價格昂貴，即便在將來3G 網絡普及之后也不會有太大改變，畢竟無線網絡帶寬仍屬于有限資源。所以，挖掘算法增加一次掃描數據庫的次數將增加這個挖掘算法的使用費，降低其可用性。

（4）可視化與人機交互。在15 寸的屏幕上要生動地展示數據挖掘的結果已經是困難的事情，要在一寸見方的空間表達復雜的結果就更困難了。由于移動設備操作起來遠不如鍵盤，因此需要更人性化的設計，以提高可操作性。Kargupta[2]采用一種顏色編碼的方法來展示決策樹，雖然可以很方便地把一棵樹用一些帶顏色的方框圈出來，但是對于普通人來說，看懂這樣一棵決策樹還是比較困難的。可見，設計出好的人機交互界面是一大挑戰。（5）移動性、協作性給數據管理提出難題。無線網絡和便攜設備就是為了用戶可以在移動的情況下使用。用戶可能不知不覺離開一個網絡，進入到另一個網絡，從一個服務區進入另一個服務區。在位置遷移的同時需要保持用戶與數據服務器的連接，保證數據交付的一致性。在一些應用中，還要求移動代理具備地理位置意識。

綜上所述，對移動環境下的數據挖掘不是側重強調復雜數據結構的設計和復雜數學方法的運用，而是如何選擇一個恰當的可以解決問題的算法，優化其性能以滿足用戶對響應速度的要求，同時保證算法的挖掘結果準確度在用戶可以接受的范圍內。總之，當前移動挖掘的研究重點是：

①設計實現輕量級的學習算法以彌補資源有限的移動設備的缺陷。

②為移動數據挖掘設計出能有資源意識以及地理位置意識的移動智能代理框架。Gaber[10]提出了一種具有資源感知的移動挖掘框架。

3當前研究狀況

對于上述所提出的各種挑戰沒有特別通用的解決方法，在特定的環境會采用特定的優化策略。目前，仍然存在一些比較簡單的策略，主要分為兩類，即基于數據的策略和基于任務的策略。

3．1基于數據的策略

基于數據的策略是指在處理和分析數據前對數據集進行概括或取出其中一個子集進行處理。數據抽象、概要結構和聚合屬于前者；抽樣、過濾和負載脫落屬于后者。

3．1．1抽樣 

采用一種統計方法來選擇一部分輸入數據作為分析數據。根據元素入選幾率的不同，抽樣方法可分成均勻抽樣(Uniform Sampling)和偏倚抽樣(Biased Sampling)。均勻抽樣對于每個元素的入選幾率是一樣的，偏倚抽樣則相反。比較實用的數據流抽樣方法有水庫抽樣(Reservoir Sampling)[11]、精確抽樣(Concise Sampling)[12]和計數抽樣(Counting Sampling)[12]，前兩者屬于均勻抽樣，后者屬于偏倚抽樣。抽樣大小往往確定了算法的錯誤極限。Very Fast Machine Learning技術[26]采用了Hoeffding邊界作為抽樣大小的度量。因為抽樣丟棄了一些數據，因此需要一些特定的分析以確定抽樣對算法準確度的影響。另外，抽樣不太適合監視數據流異常的挖掘算法。對于抽樣方法，需注意的三個參數是數據率、抽樣率和錯誤極限，一般給定算法可以接受的錯誤極限，從而計算出抽樣率。

3．1．2過濾

過濾可以看作是一種語義抽樣操作，它對每個數據元素進行分析，丟棄對某些挖掘結果影響比較小的數據。一般來說，過濾是較消耗計算資源的，因為它要對每個數據元素判斷是否舍棄。

3．1．3負載脫落

負載脫落是指當數據流速度過快來不及處理時，暫時放棄當前的數據，直到上一批數據處理完[13~16]。負載脫落技術對于挖掘算法的準確度影響是很大的，因為丟棄的數據可能在構建模型和表現時序分析的模式時很重要。

3．1．4數據抽象和概要結構

通常，捕獲傳輸的數據流數據屬于層次結構中比較底層的對象。根據后繼分析的需要，有選擇地采用高層次的抽象對象來分類，減少數據元素的種類。將數據抽象成較少的分類，可以減少內存的消耗，同時也可以減少CPU的時間消耗。這種方法結合數據流按時間分段技術可以統計每個時間段中的數據種類和出現次數，不必記錄全部數據。如何合理劃分出時間段也是一個復雜的問題，是時態數據庫研究的重點[17]。

概要結構是指對需要分析的數據流在處理之前進行概括，從而減少隨后處理的空間和時間消耗。小波變換、直方圖和分位數均被應用于構建概要結構。Gilbert的文章[22]將小波變換應用于構建概要結構。小波變換是一種數字信號處理技術，小波分析根據輸入的模擬量變換成一系列的小波參數，并且少數幾個小波就擁有大部分的能量，即可以選擇少數小波來還原原始信號。由于概要結構不能表現數據的全部特征，因此使用概要結構的算法一般只能得到近似的結果。

3．1．5聚合

聚合是指用一些統計方法對數據集進行統計，如求和、求平均等，這些聚合結果可以用于數據挖掘算法。聚合帶來的問題是它不能很好地反映數據的分布或者變化特征。文獻[23，24]討論了如何將在線聚合結果與離線結果合并。

3．2基于任務的策略

基于任務的方法是指對現有方法進行修改或者發明一種新的方法以滿足處理數據流的需要。近似算法、滑動窗口和AOG算法均屬于這類方法。

3．2．1近似算法

近似算法一般用來處理一些很難精確計算的問題，該類算法可以在一個指定的誤差極限內獲得近似解。對于移動數據挖掘，算法面臨的困難是連續高速的數據流、資源限制和對實時處理的要求。現在大多數的數據流挖掘算法都是一次遍歷的近似算法，選擇與設計好的滿足資源限制的挖掘算法是任何移動挖掘系統設計的關鍵。

3．2．2滑動窗口

滑動窗口比較適合那些對最近數據比較感興趣的應用，它只對當前處于滑動窗口內的數據進行分析，然后再與以前的歷史分析結果進行綜合。假設窗口的大小是W， 在任一時間點n， 滑動窗口的范圍是{amax(0，n-W+1)， …，an}，時間點max(0，n-W+1)之前的數據全部忽略。Kargupta設計了一個基于滑動窗口的數據流間相關度分析算法，用來分析股票數據流之間的依賴關系。

3．2．3AOG（Algorithm Output Granularity）算法

AOG是一種基于相似度的算法，該算法引入了算法閾值、時間閾值和時間幀這幾個概念。算法閾值是算法內在的控制參數，它可以用來控制算法的輸出粒度。算法閾值一般由剩余空間的大小、在不作增量知識集成的情況下填滿剩余空間的時間和輸入的數據率決定，算法閾值影響算法的準確度。時間閾值是指填滿結果空間所需的時間，它可以事先計算出來，也可以根據歷史記錄計算獲得。時間幀是指進行算法閾值調整的時間間隔。該算法流程如圖1所示。

算法的基本思路為：

①確定時間閾值和算法輸出粒度；

②由輸入數據速率計算算法輸出數據率和算法閾值；

③按算法閾值來挖掘數據流；

④一個時間幀后，通過輸入數據率增（減）量用線性回歸方法調整算法閾值；

⑤重復步驟③和步驟④直到結果空間填滿或者達到時間閾值；

⑥對當前的結果進行知識集成。

可以看出， AOG算法思想并不會與傳統的數據挖掘方法相沖突，它只是設法使算法可以在內存緊缺的環境下運行。因此，可以將傳統挖掘方法與AOG算法結合。文獻[18，19]介紹了基于AOG的幾種算法：

（1）LWC(Light Weight Clustering)算法是一個聚類算法，這個算法比較簡單。

①取第一個到達的元素，將它作為一個中心點；

②取隨后到達的新數據元素，計算它與各個中心點的距離；

③如果新到達的元素與其他中心點的距離均大于閾值，則將該數據元素設定為新的中心點，否則選擇與該元素距離最短的中心點，將該中心點的權重加1并根據新來的元素修正該中心點；

④重復步驟③和步驟④；

⑤如果中心點的個數等于k（根據內存大小來確定），則對這k個點進行聚類運算生成新的中心點；

⑥重復步驟③~步驟⑥，直到內存消耗完；

⑦如果內存消耗完，則將當前的聚類集成到以后的結果中或者發送到服務器。

試驗結果表明，在一定的準確度要求下，LWC的性能比Kmeans要好。

（2）LWClass(Light Weight KNearestNeighbors Classification)是一個分類算法。

①根據當前空間的大小確定能存放的實例個數。

②當新的數據元素到達時，如果當前實例集為空，則根據該元素增加新的實例，并置實例的權重為1；如果當前實例集不為空，則查找內存中與該實例最相似的實例。

(3)判斷相似度是否大于某個閾值，如果大于閾值，則在結果空間根據新到的元素增加新的實例，并將權重置為1；如果小于閾值，則檢查內存中實例的分類，若與新到的元素具有相同的分類，則將該實例的權重加1，否則減1。如果實例的權重變為0，則將它從內存中去除掉。

表1對這幾種方法的優缺點進行了比較。

在移動挖掘算法的研究中，也有很多人在傳統挖掘上取得突破，如挖掘頻繁項集、構造決策樹分類器。有人討論了一種奇特的樹Hoeffding Trees，可以用于決策樹學習，它所需的內存空間是固定的，而且每個實例的學習時間也不變，適合在移動設備上使用[20]。Pittie等人[21]介紹了一個MobiMine系統，討論了采用統計學中計算相關系數的方法來檢測數據流中的依賴關系。

4展望

本文綜述了移動挖掘當前的研究狀況，討論了在數據流環境下，對移動數據挖掘提出的挑戰及有待解決的各種問題，也介紹了國外的一些研究動態以及解決問題的方法，包括幾個著名的研究性數據流管理系統。但是，在實際系統中將DSMS 與移動數據挖掘相結合仍然是宏遠的目標。正如文中始終強調的，過分強調算法的復雜性和準確性是傳統數據挖據的研究范疇，移動數據挖掘的研究重點在于尋找研究輕量級的學習算法以滿足資源有限的移動設備的要求，設計出有資源意識、地理位置意識的移動智能代理。

全球信息化的發展、數據挖掘理論的廣泛應用、新一代3G 網絡的到來和移動智能終端的普及將大大推動移動數據挖掘的研究和應用。

參考文獻：

［1］Weiser Mark. The Computer for the Twentyfirst Century [J]. Scientific American，1991，265(3)： 94100.

［2］H Kargupta， B Park， et al. MobiMine： Monitoring the Stock Market from a PDA[J].ACM SIGKDD Explorations， 2002， 3(2)： 3746.

［3］H Kargupta， R Bhargava， K Liu， et al. VEDAS： A Mobile and Distributed Data Stream Mining System for Realtime Vehicle Monitoring[C].Proceedings of SIAM International Conference on Data Mining， Madison：ACM Press， 2004.

［4］B Babcock， S Babu， M Datar， et al. Models and Issues in Data Streams[C]. Proceedings of the 21th ACM Symposium on Principles of Database Systems，Madison： ACM Press， 2002.116.

［5］D Terry， D Goldberg， D Nichols， et al. Continuous Queries over Appendonly Databases[C]. Proceedings of the ACM SIGMOD Int’l Conf. on Management of Data，Madison： ACM Press， 2002.126.

［6］A Arasu， B Babcock， et al. STREAM： The Stanford Stream Data Manager[J].IEEE Data Engineering Bulletin， 2003， 26(1)：1926.

［7］D Carney， U Cetintemel， et al. Monitoring Streams:A New Class of Data Management Applications[C]. Proceedings of the 28th International Conference on Very Large Data Bases， 2002. 215226.

［8］R Jin， G Agrawal. An Algorithm for Incore Frequent Itemset Mining on Streaming Data[A]. Proceedings of the 5th IEEE International Conference on Data Mining[EB/OL]. http://www.cse.ohiostate.edu/~agrawal/p/sarm.pdf，2005.

［9］G S Manku， R Motwani. Approximate Frequency Counts over Data Streams[C]. Proceedings of the 28th International Conference on Very Large Data Bases， 2002.346357.

［10］Mohamed Medhat Gaber， Shonali Krishnaswamy， Arkady Zaslavsky. A Wireless Data Stream Mining Model[J]. Wireless Information Systems， 2004.152160.

［11］JS Vitter. Random Sampling with a Reservoir[J]. ACM Trans. on Mathematical Software， 1985，11(1)：3757.

［12］PB Gibbons， Y Matias. New Samplingbased Summary Statistics for Improving Approximate Query Answers[C]. Proceedings of the ACM SIGMOD Int’l Conf. on Management of Data， Seattle： ACM Press， 1998. 331342.

［13］B Babcock， M Datar， R Motwani. Load Shedding Techniques for Data Stream Systems[C]. Proc. of the Workshop on Mana￣gement and Processing of Data Streams (MPDS)， 2003.

［14］N Tatbul， U Cetintemel， S Zdonik， et al. Load Shedding in a Data Stream Mana￣ger[C]. Proceedings of the 29th International Conference on Very Large Data Bases (VLDB)， 2003.309320.

［15］N Tatbul， U Cetintemel， S Zdonik， et al. Load Shedding on Data Streams[C]. Proceedings of the Workshop on Management and Processing of Data Streams (MPDS)， 2003.566576.

［16］S D Viglas， J Naughton. Rate Based Query Optimization for Strea￣ming Information Sources[C]. Proceedings of SIGMOD， Madison： ACM Press， 2002.3748.

［17］J Himberg， K Korpiaho， H Mannla， et al. Time Series Segmentation for Context Recognition in Mobile Devices[C]. Proceedings of the IEEE International Conference on Data Mining， 2001.203210.

［18］M M Gaber， S Krishnaswamy， A Zaslavsky. Adaptive Mining Techniques for Data Streams Using Algorithm Output Granularity[C]. Australasian Data Mining Workshop Conjunction with the Congress on Evolutionary Computation， 2003.

［19］M M Gaber， A Zaslavsky， S Krishnaswamy. A CostEfficient Model for Ubiquitous Data Stream Mining[C]. Proceedings of the 10th International Conference on Information Processing and Management of Uncertainty in Knowledgebased Systems (IPMU)， 2004.

［20］P Domingos， G Hulten. Mining HighSpeed Data Streams[C]. Proceedings of the Association for Computing Machinery， the 6th International Conference on Knowledge Discovery and Data Mining， 2000.7180.

［21］S Pittie， H Kargupta， B Park. Dependency Detection in MobiMine： A Systems Perspective[J]. Information Sciences Journal， 2003， 155(34)：227243.

［22］A C Gilbert， Y Kotidis， S Muthukrishnan， et al. Onepass Wavelet Decompositions of Data Streams[J]. IEEE Transactions on Know￣ledge and Data Engineering， 2003，15(3)：541554.

［23］C Aggarwal， J Han， J Wang， et al. A Framework for Projected Clustering of High Dimensional Data Streams[C]. Proceedings of the 30th Int. Conf. on Very Large Data Bases， 2004.

［24］C Aggarwal， J Han， J Wang， et al. On Demand Classification of Data Streams[C]. Proc. of the 10th Int. Conf. on Knowledge Discovery and Data Mining， 2004.

［25］S Muthukrishnan. Data Streams： Algorithms and Applications[A]. Proceedings of the 14th Annual ACMSIAM Symposium on Discrete Algorithms[EB/OL]. http：//athos.rutgers.edu/~muthu/stream11.ps，2003.

［26］P Domingos， G Hulten. A General Method for Scaling up Machine Learning Algorithms and Its Application to Clustering[C]. Procee￣dings of the 18th International Conference on Machine Learning， 2001.106113.

作者簡介：

鄧維維，（1978），湖南人，博士研究生，主要研究方向為移動計算、數據挖掘；彭宏(1956)，重慶人，教授，博導，主要研究方向為智能計算；鄭啟倫(1938)，廣東人，教授，博導，主要研究方向為神經網絡、數據挖掘。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文