基于數(shù)據(jù)流的移動數(shù)據(jù)挖掘研究綜述

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

關(guān)鍵詞：移動數(shù)據(jù)挖掘; 數(shù)據(jù)挖掘; 數(shù)據(jù)流; 普適計算

中圖法分類號：TP391文獻標(biāo)識碼：A

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

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

移動數(shù)據(jù)挖掘?qū)儆诘谒拇鷶?shù)據(jù)挖掘系統(tǒng)，它最大的特色是將數(shù)據(jù)挖掘轉(zhuǎn)移到嵌入式設(shè)備和移動環(huán)境。自2002年以來，移動數(shù)據(jù)管理已經(jīng)召開了兩次國際會議，主要討論都是圍繞普適環(huán)境這一特征，討論如何管理在該環(huán)境下的數(shù)據(jù)，開發(fā)移動設(shè)備上的復(fù)雜計算程序并進行移動數(shù)據(jù)挖掘。移動數(shù)據(jù)挖掘與傳統(tǒng)挖掘方法不同，具有很多獨特的地方，它們會導(dǎo)致傳統(tǒng)的數(shù)據(jù)挖掘算法無效。這種現(xiàn)象主要的原因是在應(yīng)用上的不同，即移動挖掘算法和系統(tǒng)需要為應(yīng)用量身定做。

（1）傳統(tǒng)的數(shù)據(jù)挖掘系統(tǒng)面向的應(yīng)用是知識發(fā)現(xiàn)、模式識別、決策支持、預(yù)測預(yù)警等，它們關(guān)心挖掘結(jié)果的正確性、完整性，導(dǎo)致了這類應(yīng)用空間消耗大、計算密集、計算時間長。

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

無線網(wǎng)絡(luò)及移動設(shè)備帶來的新基礎(chǔ)架構(gòu)和開發(fā)環(huán)境，引發(fā)了面向數(shù)據(jù)流分析系統(tǒng)的研究和開發(fā)。其研究目的是如何在普適性環(huán)境下進行挖掘，并提出一個較為通用的面向數(shù)據(jù)流的挖掘系統(tǒng)的架構(gòu)。本文介紹了數(shù)據(jù)流環(huán)境的特點以及數(shù)據(jù)流管理系統(tǒng)，重點突出了普適環(huán)境和數(shù)據(jù)流給移動數(shù)據(jù)挖掘帶來的挑戰(zhàn)；詳細描述了移動數(shù)據(jù)挖掘所采用的幾種處理數(shù)據(jù)流的策略，著重介紹了AOG方法，并對這些策略進行了比較。

1數(shù)據(jù)流特點與數(shù)據(jù)流管理系統(tǒng)

數(shù)據(jù)流與移動數(shù)據(jù)挖掘緊密相關(guān)，移動挖掘的數(shù)據(jù)大部分是數(shù)據(jù)流，而且未來移動數(shù)據(jù)挖掘的一個發(fā)展方向是在數(shù)據(jù)流管理系統(tǒng)上建立移動數(shù)據(jù)挖掘系統(tǒng)。

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

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

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

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

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

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

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

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

2面臨的挑戰(zhàn)

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

（1）PC 機上具備大量的內(nèi)存與外存，可以采用多次抽樣來彌補采樣所造成的正確性損失。所以采樣在提高算法計算速率的同時，又可以保證相當(dāng)?shù)恼_性。

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

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

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

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

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

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

綜上所述，對移動環(huán)境下的數(shù)據(jù)挖掘不是側(cè)重強調(diào)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的設(shè)計和復(fù)雜數(shù)學(xué)方法的運用，而是如何選擇一個恰當(dāng)?shù)目梢越鉀Q問題的算法，優(yōu)化其性能以滿足用戶對響應(yīng)速度的要求，同時保證算法的挖掘結(jié)果準(zhǔn)確度在用戶可以接受的范圍內(nèi)。總之，當(dāng)前移動挖掘的研究重點是：

①設(shè)計實現(xiàn)輕量級的學(xué)習(xí)算法以彌補資源有限的移動設(shè)備的缺陷。

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

3當(dāng)前研究狀況

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

3．1基于數(shù)據(jù)的策略

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

3．1．1抽樣 

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

3．1．2過濾

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

3．1．3負載脫落

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

3．1．4數(shù)據(jù)抽象和概要結(jié)構(gòu)

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

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

3．1．5聚合

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

3．2基于任務(wù)的策略

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

3．2．1近似算法

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

3．2．2滑動窗口

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

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

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

算法的基本思路為：

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

②由輸入數(shù)據(jù)速率計算算法輸出數(shù)據(jù)率和算法閾值；

③按算法閾值來挖掘數(shù)據(jù)流；

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

⑤重復(fù)步驟③和步驟④直到結(jié)果空間填滿或者達到時間閾值；

⑥對當(dāng)前的結(jié)果進行知識集成。

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

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

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

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

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

④重復(fù)步驟③和步驟④；

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

⑥重復(fù)步驟③~步驟⑥，直到內(nèi)存消耗完；

⑦如果內(nèi)存消耗完，則將當(dāng)前的聚類集成到以后的結(jié)果中或者發(fā)送到服務(wù)器。

試驗結(jié)果表明，在一定的準(zhǔn)確度要求下，LWC的性能比Kmeans要好。

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

①根據(jù)當(dāng)前空間的大小確定能存放的實例個數(shù)。

②當(dāng)新的數(shù)據(jù)元素到達時，如果當(dāng)前實例集為空，則根據(jù)該元素增加新的實例，并置實例的權(quán)重為1；如果當(dāng)前實例集不為空，則查找內(nèi)存中與該實例最相似的實例。

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

表1對這幾種方法的優(yōu)缺點進行了比較。

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

4展望

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

全球信息化的發(fā)展、數(shù)據(jù)挖掘理論的廣泛應(yīng)用、新一代3G 網(wǎng)絡(luò)的到來和移動智能終端的普及將大大推動移動數(shù)據(jù)挖掘的研究和應(yīng)用。

參考文獻：

［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），湖南人，博士研究生，主要研究方向為移動計算、數(shù)據(jù)挖掘；彭宏(1956)，重慶人，教授，博導(dǎo)，主要研究方向為智能計算；鄭啟倫(1938)，廣東人，教授，博導(dǎo)，主要研究方向為神經(jīng)網(wǎng)絡(luò)、數(shù)據(jù)挖掘。

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