大數(shù)據(jù)

數(shù)據(jù)是與自然資源一樣重要的戰(zhàn)略資源，大數(shù)據(jù)技術(shù)就是從數(shù)量巨大、結(jié)構(gòu)復(fù)雜、類型眾多的數(shù)據(jù)中，快速獲得有價(jià)值信息的能力，它已成為學(xué)術(shù)界、企業(yè)界甚至各國(guó)政府關(guān)注的熱點(diǎn)。本講座將分3期對(duì)大數(shù)據(jù)進(jìn)行討論：第1期介紹了大數(shù)據(jù)的提出、含義、特點(diǎn)，大數(shù)據(jù)和云計(jì)算的關(guān)系以及大數(shù)據(jù)典型應(yīng)用；第2期介紹大數(shù)據(jù)獲取、存貯、搜索、分享、分析、可視化等方面的關(guān)鍵技術(shù)，并對(duì)當(dāng)前熱點(diǎn)技術(shù)—可視化進(jìn)行重點(diǎn)分析；第3期探討數(shù)據(jù)流挖掘等實(shí)時(shí)數(shù)據(jù)分析技術(shù)，介紹大數(shù)據(jù)中非結(jié)構(gòu)化數(shù)據(jù)處理和挖掘技術(shù)，并給出大數(shù)據(jù)發(fā)展面臨的挑戰(zhàn)與應(yīng)用前景。

7 數(shù)據(jù)挖掘和數(shù)據(jù)流挖掘

7.1 大數(shù)據(jù)挖掘技術(shù)的簡(jiǎn)介和分類

大數(shù)據(jù)技術(shù)廣義上包括大數(shù)據(jù)相關(guān)的獲取、存儲(chǔ)、處理、挖掘等技術(shù)，但就美國(guó)政府2012年提出的“大數(shù)據(jù)研究與發(fā)展計(jì)劃”而言，它主要指的是面向大數(shù)據(jù)的數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)技術(shù)。此期重點(diǎn)介紹大數(shù)據(jù)中的數(shù)據(jù)挖掘技術(shù)，重點(diǎn)是數(shù)據(jù)流挖掘技術(shù)。

數(shù)據(jù)挖掘技術(shù)是一個(gè)涉及數(shù)據(jù)庫(kù)、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)、神經(jīng)網(wǎng)絡(luò)、高性能計(jì)算和數(shù)據(jù)可視化的多學(xué)科領(lǐng)域，是計(jì)算機(jī)模仿人類學(xué)習(xí)機(jī)理和方法，利用數(shù)據(jù)自動(dòng)獲取知識(shí)的一種技術(shù)。數(shù)據(jù)挖掘出現(xiàn)于20世紀(jì)80年代末，在過(guò)去的20年中得到了廣泛的研究和快速的發(fā)展，表現(xiàn)在出現(xiàn)了大量的算法，并可以處理各種類型數(shù)據(jù)。然而隨著大數(shù)據(jù)時(shí)代的來(lái)臨，數(shù)據(jù)挖掘技術(shù)迎來(lái)了空前廣泛的應(yīng)用機(jī)會(huì)，也面臨新的挑戰(zhàn)。大數(shù)據(jù)是伴隨智能終端的普及和互聯(lián)網(wǎng)上微博、社交網(wǎng)絡(luò)等業(yè)務(wù)的廣泛應(yīng)用而出現(xiàn)的，因此面向大數(shù)據(jù)的數(shù)據(jù)挖掘的應(yīng)用首推Google、Amazon、Yahoo、阿里巴巴等互聯(lián)網(wǎng)公司，比如2009年甲型H1N1流感爆發(fā)時(shí)，Google利用海量的用戶搜索詞及其組合，比美國(guó)國(guó)家疾控中心更及時(shí)更準(zhǔn)確地報(bào)告了疫情；Amazon公司首先提出并應(yīng)用協(xié)同過(guò)濾技術(shù)進(jìn)行書(shū)籍推薦，其應(yīng)用效果超過(guò)了之前被譽(yù)為“公司皇冠之上寶石“的書(shū)評(píng)團(tuán)隊(duì)，開(kāi)啟了電子商務(wù)應(yīng)用中商品推薦的先河?；诨ヂ?lián)網(wǎng)上海量語(yǔ)言材料應(yīng)用機(jī)器學(xué)習(xí)技術(shù)的Google語(yǔ)言翻譯系統(tǒng)，則是目前為止最為成功的計(jì)算機(jī)自動(dòng)翻譯系統(tǒng)。面向大數(shù)據(jù)的數(shù)據(jù)挖掘技術(shù)的一個(gè)挑戰(zhàn)是：大數(shù)據(jù)時(shí)代我們能得到現(xiàn)象相關(guān)的所有數(shù)據(jù)，即統(tǒng)計(jì)學(xué)上所說(shuō)的總體，而不再是傳統(tǒng)的統(tǒng)計(jì)學(xué)和數(shù)據(jù)挖掘中一個(gè)容量有限的樣本或容量有限的訓(xùn)練集。另外一個(gè)挑戰(zhàn)是所得到的數(shù)據(jù)不是絕對(duì)精確的，只要在保證速度的前提下近似地反映宏觀和整體情況[12]，這一挑戰(zhàn)要求數(shù)據(jù)挖掘要能處理非結(jié)構(gòu)化數(shù)據(jù)和含噪音的數(shù)據(jù)，而挖掘結(jié)果的正確性則只要保證在期望的區(qū)間內(nèi)。目前來(lái)看，應(yīng)對(duì)這兩個(gè)挑戰(zhàn)的主要技術(shù)之一就是數(shù)據(jù)流的挖掘。

數(shù)據(jù)挖掘技術(shù)主要分為如下幾個(gè)分支：分類、聚類、關(guān)聯(lián)規(guī)則挖掘、序列模式挖掘、異常點(diǎn)挖掘、時(shí)間序列分析預(yù)測(cè)等。在大數(shù)據(jù)的相關(guān)挖掘應(yīng)用中，雖然處理的數(shù)據(jù)形式更豐富，但就學(xué)習(xí)方法來(lái)看并沒(méi)有根本差別，因?yàn)槿渴腔跀?shù)字化后信息的學(xué)習(xí)。

7.2概念漂移

“概念漂移”是Schlimmer等人于1986年首次提出的[13]。大部分的數(shù)據(jù)挖掘技術(shù)都有一個(gè)假設(shè)前提：樣本是隨機(jī)獲取的，并且服從同一穩(wěn)定的分布。然而在大數(shù)據(jù)場(chǎng)景下，數(shù)據(jù)源源不斷地到來(lái)，樣本具有不穩(wěn)定和不確定性。例如，顧客的購(gòu)買興趣隨著時(shí)間很有可能發(fā)生變化；用戶上網(wǎng)的瀏覽習(xí)慣也會(huì)隨著時(shí)間的推移而發(fā)生明顯地改變。因此大數(shù)據(jù)場(chǎng)景中不可避免的，一定要考慮概念漂移問(wèn)題。如圖8，樣本的統(tǒng)計(jì)特性在某一時(shí)刻開(kāi)始發(fā)生變化，我們認(rèn)為此時(shí)發(fā)生了“概念漂移”。

從樣本是否服從相同分布的維度，可以將數(shù)據(jù)流劃分為2類：穩(wěn)定數(shù)據(jù)流，樣本服從同一分布；動(dòng)態(tài)數(shù)據(jù)流，隨著時(shí)間推移，樣本服從不同分布，只有動(dòng)態(tài)數(shù)據(jù)流中才存在“概念漂移”現(xiàn)象。概念漂移又可以分為：突變式和漸變式，對(duì)這兩種漂移的處理方式和難度通常并不相同，在設(shè)計(jì)漂移算法時(shí)，應(yīng)該分別進(jìn)行考慮。如圖9所示，在t 0 時(shí)刻之前，數(shù)據(jù)樣本服從同一分布A，而在t 0和t 1之間，數(shù)據(jù)流發(fā)生概念漂移，在t 1時(shí)刻之后，數(shù)據(jù)重新趨于穩(wěn)定，并服從同一分布B。

當(dāng)概念漂移發(fā)生之后，最直接的結(jié)果就是從之前樣本中學(xué)習(xí)獲得的概念模型，已經(jīng)不再適用，必須盡快更新?，F(xiàn)有概念漂移檢測(cè)的方法，可以分為3類：模型性能監(jiān)測(cè)法、概念聚類法、樣本分布監(jiān)測(cè)法。

（1）模型性能監(jiān)測(cè)法。以分類挖掘?yàn)槔紫刃枰獙?duì)分類器的性能進(jìn)行跟蹤監(jiān)測(cè)，當(dāng)使用新采集的訓(xùn)練集，對(duì)現(xiàn)有分類器進(jìn)行更新之后，如果分類器在測(cè)試集上表現(xiàn)出的性能明顯下降，我們則認(rèn)為發(fā)生了概念漂移。Windmer和Kubat提出的FLORA系列算法[14]、Last提出的OLIN算法[15]等都是屬于這一類。模型性能監(jiān)測(cè)是十分常用的方法，但當(dāng)數(shù)據(jù)流中存在類別不平衡或者進(jìn)行半監(jiān)督學(xué)習(xí)時(shí)，此方法將不再適用。

（2）概念聚類法。Katakis在2010年首次提出這一方法[15]，基本思路是將數(shù)據(jù)流劃分為數(shù)據(jù)塊，并且再將其映射為“概念向量”，對(duì)多個(gè)概念向量進(jìn)行聚類，每一個(gè)聚類代表一個(gè)概念。當(dāng)一個(gè)新的數(shù)據(jù)塊到來(lái)時(shí)，計(jì)算其對(duì)應(yīng)的概念向量與各個(gè)聚類中心之間的距離，并以此判斷是否發(fā)生了漂移。這一方法可以解決概念漂移領(lǐng)域的一個(gè)重要問(wèn)題：重復(fù)概念的檢測(cè)。概念聚類法局限的地方在于：假設(shè)每次劃分的數(shù)據(jù)塊內(nèi)所有數(shù)據(jù)都屬于同一概念。

（3）樣本分布監(jiān)測(cè)法。針對(duì)樣本集，提取其中的統(tǒng)計(jì)特性：特征值分布等，以這些參數(shù)的變化來(lái)判斷是否發(fā)生概念漂移。2006-2011年間，Alippi[17-18]、Peter[19]、Kuncheva[20]等人都是基于此原理提出了檢測(cè)概念漂移的具體策略。

7.3 聚類

Han Jiawei教授在《Data Mining： Concept and Techniques》中，對(duì)聚類有一個(gè)簡(jiǎn)短的定義：將物理或抽象對(duì)象的集合分成相似的對(duì)象類的過(guò)程稱為聚類。更形式化的一個(gè)描述方法是：聚類分析就是按照某種相似性度量方法對(duì)對(duì)象進(jìn)行分組，使得各組內(nèi)的相似度高，而組間的相似度低。俗語(yǔ)“物以類聚，人以群分”可以說(shuō)是聚類作用的一個(gè)生動(dòng)說(shuō)明。

聚類挖掘已廣泛用于各種應(yīng)用領(lǐng)域的模式識(shí)別以及離群點(diǎn)檢測(cè)中。市場(chǎng)分析人員可以在沒(méi)有任何先驗(yàn)知識(shí)的情況下，應(yīng)用聚類方法基于購(gòu)買模式數(shù)據(jù)庫(kù)發(fā)現(xiàn)不同的顧客群；網(wǎng)絡(luò)數(shù)據(jù)分析人員針對(duì)web文檔數(shù)據(jù)或網(wǎng)絡(luò)訪問(wèn)日志數(shù)據(jù)對(duì)訪問(wèn)的網(wǎng)頁(yè)進(jìn)行聚類，以發(fā)現(xiàn)對(duì)不同網(wǎng)頁(yè)信息感興趣的人群，來(lái)支持精準(zhǔn)營(yíng)銷或分析社會(huì)學(xué)上原因。應(yīng)用聚類還可以發(fā)現(xiàn)異常點(diǎn)，即那些無(wú)法歸入任何簇的點(diǎn)，離群點(diǎn)檢測(cè)廣泛應(yīng)用于信用卡欺詐檢測(cè)和監(jiān)控電子商務(wù)中的犯罪活動(dòng)。聚類分析還可以作為研究數(shù)據(jù)分布的功能以及作為其他算法的預(yù)處理步驟。

從1967年研究人員提出第一種聚類算法開(kāi)始，目前為止已經(jīng)有多種可用的聚類算法。但是沒(méi)有任何一種是普遍適用的，因?yàn)椴煌瑔?wèn)題中數(shù)據(jù)的維度高低不同、各維數(shù)據(jù)特性不同、數(shù)據(jù)分布情況不同、數(shù)據(jù)規(guī)模不同，而隨著大數(shù)據(jù)時(shí)代數(shù)據(jù)流的出現(xiàn)，對(duì)聚類算法更提出了內(nèi)存限制、處理時(shí)間限制等挑戰(zhàn)。但這些算法可以按照聚類依據(jù)不同進(jìn)行分類，首先總體分為2大類：基于樣本的聚類、基于變量的聚類。其中，基于樣本的聚類人們研究的比較多，前面的聚類舉例也全部是針對(duì)基于樣本的；基于變量的聚類顧名思義就是對(duì)變量（即維度或?qū)傩裕┻M(jìn)行分組，它和數(shù)據(jù)分析中的因子分析及主成分分析（PCA）比較像；但聚類分析并不會(huì)對(duì)變量進(jìn)行合并，只是用層次式等方法對(duì)變量的遠(yuǎn)近親疏程度進(jìn)行判別。在某些領(lǐng)域，基于變量聚類非常有用，比如傳感器網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)、電力供應(yīng)、股票市場(chǎng)上，比如通過(guò)聚類分析我們可以發(fā)現(xiàn)各支股票之間的關(guān)系，而通過(guò)流數(shù)據(jù)聚類則可以發(fā)現(xiàn)這種關(guān)系的變化的情況。

基于樣本的聚類是目前為止研究的最多，這些算法又可以分為：基于劃分的聚類、基于層次的聚類、基于網(wǎng)格的聚類、基于密度的聚類、基于模型的聚類。對(duì)流數(shù)據(jù)的聚類也是在這些聚類算法的基礎(chǔ)上發(fā)展而來(lái)的，因此，接下來(lái)簡(jiǎn)要介紹下這幾種聚類算法及其特點(diǎn)。

7.3.1 基于劃分的聚類

經(jīng)典的聚類算法k-means就是基于劃分的，這種算法之所以應(yīng)用廣泛是因?yàn)槠浜?jiǎn)單快速。但該算法需要人為設(shè)定一個(gè)代表聚類個(gè)數(shù)的參變量k，如何正確設(shè)置這個(gè)值是個(gè)難題。另外，k-means算法的理論基礎(chǔ)是找到k個(gè)點(diǎn)（所謂中心點(diǎn)centroid）使得相應(yīng)簇中的點(diǎn)到這k個(gè)點(diǎn)的距離平方和最小。由此可見(jiàn)，采用這種理論所找到的簇是球形的，而且這種方法對(duì)噪聲和孤立點(diǎn)敏感。而k-中心點(diǎn)法則是克服了這個(gè)問(wèn)題的另一種基于劃分的聚類算法。為了處理大規(guī)模數(shù)據(jù)集，人們?cè)谶@些算法基礎(chǔ)上進(jìn)行了改進(jìn)，提出一些新的算法如最大期望算法（EM）、基于隨機(jī)選擇的聚類算法（CLARANS）等。

對(duì)數(shù)據(jù)流聚類時(shí)，因?yàn)榱鲾?shù)據(jù)不斷到達(dá)，所以無(wú)法在數(shù)據(jù)完全到達(dá)后進(jìn)行聚類，部分?jǐn)?shù)據(jù)上的聚類結(jié)果也很可能不再適用后面到達(dá)的數(shù)據(jù)，因此必須進(jìn)行增量式聚類。而且，為了及時(shí)對(duì)后面很快到達(dá)的數(shù)據(jù)進(jìn)行處理，每次的聚類操作必須在指定時(shí)間內(nèi)完成，同時(shí)內(nèi)存也要不斷騰出來(lái)配合下一次聚類操作。當(dāng)然，聚類結(jié)果可能達(dá)不到理論上的完美效果，但是要有盡可能好的效果，最好這個(gè)結(jié)果和理想結(jié)果差多少有一個(gè)理論上的范圍。這些問(wèn)題其實(shí)是所有流數(shù)據(jù)挖掘和靜態(tài)數(shù)據(jù)的區(qū)別所在：要在有限內(nèi)存有限時(shí)間內(nèi)給出一個(gè)準(zhǔn)確性有一定保證的挖掘結(jié)果，

Farnstrom等人提出的一趟k-mean算法是適應(yīng)流數(shù)據(jù)挖掘的k-means算法，它只對(duì)數(shù)據(jù)進(jìn)行一趟掃描，當(dāng)然歷史結(jié)果的保存需要采用一種叫做聚類特征的概要數(shù)據(jù)。Domingos和Hulten在此基礎(chǔ)上提出的快速K均值算法（VFKM）則對(duì)每次增量聚類時(shí)需要的樣本個(gè)數(shù)給出了理論上計(jì)算方法，其采用的理論基礎(chǔ)是Hoeffding不等式，這個(gè)不等式和契比雪夫不等式性質(zhì)類似，都是對(duì)于一個(gè)分布特性未知的隨機(jī)變量，已知很少量的統(tǒng)計(jì)參數(shù)，可以在任意置信度之下計(jì)算出相應(yīng)的置信區(qū)間。而Guha等人則提出了數(shù)據(jù)流聚類的k-中心點(diǎn)算法，并給出所需的樣本個(gè)數(shù)及所需時(shí)間和空間的理論計(jì)算結(jié)果。

7.3.2 基于層次的聚類

層次聚類也是一種常用聚類方法。它不再是只給出k個(gè)聚類而成的簇，而是給出多層的樹(shù)狀聚類結(jié)果。層次聚類又可分為凝聚和分裂兩類，分別采用自底向上和自頂向下兩種方法。BIRCH算法則綜合了這兩種方法。

Aggarwal、J. Han等人提出的CluStream算法則是BIRCH算法在數(shù)據(jù)流挖掘上的擴(kuò)展。該算法的特征之一是：提出了傾斜時(shí)間窗口的概念，依據(jù)較近的數(shù)據(jù)比歷史數(shù)據(jù)更重要的理念，最近的時(shí)間變化以較細(xì)的時(shí)間粒度刻畫(huà)，而離現(xiàn)在較遠(yuǎn)的數(shù)據(jù)則采用較粗的時(shí)間粒度。該算法的另一個(gè)重要特點(diǎn)是，整個(gè)流聚類分為在線和離線兩部分。在線部分增量式進(jìn)行數(shù)據(jù)處理，獲得摘要信息微簇（micro-cluster），離線部分宏簇（macro-cluster）通過(guò)對(duì)在線部分的結(jié)果進(jìn)行再處理獲得層次的聚類結(jié)果。

7.3.3 基于網(wǎng)格和密度的聚類

基于密度的聚類不再按之前兩種聚類采用的距離的遠(yuǎn)近作為分劃的依據(jù)，而是按照單位空間范圍內(nèi)點(diǎn)的個(gè)數(shù)即密度來(lái)劃分空間，只要某一范圍內(nèi)密度大于某一指定參變量，則認(rèn)為是同一簇?；诿芏鹊木垲愃惴ǎ―BSCAN）、通過(guò)對(duì)象排序識(shí)別聚類結(jié)構(gòu)算法（OPTICS）等是經(jīng)典基于密度聚類算法。

基于網(wǎng)格的聚類是面向時(shí)空相關(guān)問(wèn)題。它采用一個(gè)多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，這些網(wǎng)格把空間量化為有限數(shù)目的單元，所有聚類操作都在這些網(wǎng)格上進(jìn)行。這些方法的主要優(yōu)點(diǎn)是處理速度快，挈獨(dú)立于數(shù)據(jù)對(duì)象數(shù)目，只與每一維上的單元數(shù)目相關(guān)。經(jīng)典算法是信息網(wǎng)格算法（STING）、WaveCluster，而Quest上聚類（CLIQUE）則綜合了密度和網(wǎng)格兩種方法。

在流數(shù)據(jù)聚類中，分形聚類則是一種基于網(wǎng)格的聚類，它將具有相同分形維的具有高自相似性的點(diǎn)分為一類。

7.3.4 基于模型的聚類

基于模型的聚類其實(shí)是把回歸擬合應(yīng)用在聚類中，它為每一簇?cái)M合一個(gè)模型，根據(jù)擬合模型的方法不同又分為統(tǒng)計(jì)學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法，屬于前者的有簡(jiǎn)單增量概念聚類算法（COBWEB）方法，屬于后者的有學(xué)習(xí)矢量量化網(wǎng)絡(luò)（LVQM）、自組織映射（SOM）等方法。

7.4 數(shù)據(jù)挖掘中的分類

數(shù)據(jù)挖掘中的分類指的是：首先根據(jù)已知類別的一些樣本進(jìn)行學(xué)習(xí)，得到一個(gè)分類的規(guī)則或者說(shuō)是模型，然后利用學(xué)習(xí)得到的模型對(duì)另外一些類別未知其他屬性值已知的樣本進(jìn)行類別的判斷或者預(yù)測(cè)?？梢钥闯觯诸惡途垲惖牟煌幵谟冢悍诸悓W(xué)習(xí)時(shí)，樣本類別時(shí)已知的；而聚類學(xué)習(xí)時(shí)，樣本類別甚至類別數(shù)目是未知的。因此前者是有監(jiān)督的學(xué)習(xí)，后者則是一種無(wú)監(jiān)督的學(xué)習(xí)。分類學(xué)習(xí)的一個(gè)經(jīng)典的例子是對(duì)銀行現(xiàn)有的顧客信用信息進(jìn)行學(xué)習(xí)，建立信用良好或欺詐客戶的判斷模型，當(dāng)一個(gè)新的顧客申請(qǐng)銀行借貸時(shí)，利用學(xué)習(xí)模型進(jìn)行判斷，給出新客戶良好或是欺詐客戶的可能性，從而提高銀行業(yè)務(wù)決策的科學(xué)性。

典型的分類方法有很多，主要包括基于決策樹(shù)（DT）的分類、基于貝頁(yè)斯（Beyesian）分類、基于神經(jīng)網(wǎng)絡(luò)的分類等。決策樹(shù)分類是基于信息論中的信息熵的概念，學(xué)習(xí)結(jié)果是一個(gè)由各個(gè)屬性及其取值形成的代表判斷流程的樹(shù)狀結(jié)構(gòu)，稱為決策樹(shù)。典型的算法包括ID3、C4.5等。適用于大規(guī)模數(shù)據(jù)集決策樹(shù)構(gòu)造的算法則有Quest上的有監(jiān)督學(xué)習(xí)（SLIQ）和可伸縮并行決策樹(shù)（SPRINT）等。貝葉斯分類算法基于統(tǒng)計(jì)學(xué)中的貝頁(yè)斯后驗(yàn)概率定理，并應(yīng)用各屬性間類條件獨(dú)立的樸素假定，方法簡(jiǎn)單，可伸縮性好，很多實(shí)驗(yàn)表明其分類效果與復(fù)雜的決策樹(shù)和神經(jīng)網(wǎng)絡(luò)相媲美。

傳統(tǒng)的分類方法多是非增量式的，即當(dāng)全部訓(xùn)練樣本準(zhǔn)備好之后，對(duì)樣本集進(jìn)行多次掃描，獲得一個(gè)分類器，例如工業(yè)界廣泛應(yīng)用的分類算法C4.5和CART；而數(shù)據(jù)流場(chǎng)景下，由于數(shù)據(jù)源源不斷地到來(lái)并且數(shù)據(jù)量巨大，完全將數(shù)據(jù)存儲(chǔ)下來(lái)再進(jìn)行處理，是無(wú)法實(shí)現(xiàn)的，這就要求分類算法必須是增量式的，即訓(xùn)練樣本集不能一次性全部獲取的情況下，先利用已經(jīng)獲得的樣本集來(lái)建立分類器，再用新到達(dá)的樣本來(lái)修正分類器。

快速?zèng)Q策樹(shù)算法（VFDT）是由Domingos、Hulten等人在2000年提出的[21]，主要用于解決穩(wěn)定數(shù)據(jù)流的分類問(wèn)題，性能漸進(jìn)逼近傳統(tǒng)的C4.5算法，其基本思路為：利用Hoeffding不等式來(lái)保證選取的分裂屬性的可信程度，并且不斷地將葉子節(jié)點(diǎn)替換為中間節(jié)點(diǎn)（決策節(jié)點(diǎn)），最終生成一棵決策樹(shù)。其中每個(gè)葉節(jié)點(diǎn)都保存著樣本屬性值的統(tǒng)計(jì)信息，這些信息將用于選取分裂屬性。當(dāng)一個(gè)新樣本到來(lái)后，它將沿著決策樹(shù)從根節(jié)點(diǎn)向葉節(jié)點(diǎn)去遍歷，它在樹(shù)的每個(gè)中間節(jié)點(diǎn)都進(jìn)行屬性值判斷，并進(jìn)入不同的分支，最終到達(dá)葉節(jié)點(diǎn)，并更新葉節(jié)點(diǎn)上的統(tǒng)計(jì)信息。每隔一段時(shí)間重新評(píng)估每個(gè)葉節(jié)點(diǎn)，選取滿足Hoeffding不等式的屬性，進(jìn)行分裂。

現(xiàn)在通過(guò)一個(gè)簡(jiǎn)單的實(shí)例，來(lái)說(shuō)明VFDT算法的基本過(guò)程。如圖10所示，假設(shè)從t 0時(shí)刻開(kāi)始進(jìn)行挖掘，樣本源源不斷地到來(lái)，此時(shí)節(jié)點(diǎn)1是葉節(jié)點(diǎn)（根節(jié)點(diǎn)），樣本到達(dá)節(jié)點(diǎn)1之后，更新其中的屬性值統(tǒng)計(jì)信息，并判斷是否有屬性滿足Hoeffding不等式；假設(shè)在t 1時(shí)刻，一個(gè)樣本到達(dá)后，節(jié)點(diǎn)1內(nèi)某一屬性滿足Hoeffding不等式，則按照此屬性進(jìn)行分裂，產(chǎn)生節(jié)點(diǎn)2和節(jié)點(diǎn)3，節(jié)點(diǎn)1由葉節(jié)點(diǎn)變?yōu)橹虚g節(jié)點(diǎn)；此時(shí)，t 0到t 1之間所有到達(dá)樣本的統(tǒng)計(jì)信息，都被舍棄；從t 1時(shí)刻起，所有新到達(dá)的樣本數(shù)據(jù)，根據(jù)節(jié)點(diǎn)1中的屬性分裂條件，到葉節(jié)點(diǎn)（達(dá)節(jié)點(diǎn)2或者節(jié)點(diǎn)3），并更新葉節(jié)點(diǎn)中的統(tǒng)計(jì)數(shù)據(jù)，同時(shí)判斷是否有屬性滿足Hoeffding不等式，若有則繼續(xù)進(jìn)行分裂生長(zhǎng)。從上述過(guò)程可以看出，決策樹(shù)每次進(jìn)行生長(zhǎng)時(shí)，都會(huì)單獨(dú)占用并消耗一部分?jǐn)?shù)據(jù)：節(jié)點(diǎn)1分裂時(shí)，消耗了t 0到t 1之間所有到達(dá)節(jié)點(diǎn)1的樣本，這些樣本將不再對(duì)此后決策樹(shù)的生長(zhǎng)產(chǎn)生任何影響；當(dāng)節(jié)點(diǎn)2分裂時(shí)，消耗了t 1到t 2之間所有到達(dá)節(jié)點(diǎn)2的樣本，這些樣本將不再對(duì)此后決策樹(shù)的生長(zhǎng)產(chǎn)生任何影響。

基于VFDT算法，Hulten、Domingos等人于2001年提出可以解決概念漂移問(wèn)題的概念自適應(yīng)快速?zèng)Q策樹(shù)算法（CVFDT）。此后近十多年時(shí)間里，針對(duì)VFDT算法拓展和應(yīng)用的層出不窮，CVFDT算法都取得了不錯(cuò)的性能測(cè)試效果。然而在2012年Rutkowsk等人在TKDE上發(fā)表一篇文章指出，VFDT算法中使用的Hoeffding界不符合數(shù)據(jù)流的應(yīng)用場(chǎng)景，應(yīng)該改為McDiarmid’s界[22]。這一點(diǎn)感興趣的讀者可以自己查閱，但不可否認(rèn)的是在各式各樣的測(cè)試數(shù)據(jù)集上，VFDT確實(shí)顯示出令人滿意的測(cè)試性能。

此外，數(shù)據(jù)流中經(jīng)典的分類算法還有：基于模糊信息網(wǎng)絡(luò)的2002年Last提出的OLIN算法等。特別要說(shuō)明的是，近幾年在數(shù)據(jù)流分類挖掘中，基于單分類器的集合分類器方法得到了較廣泛的研究和應(yīng)用。

7.5 頻繁模式挖掘

7.5.1 關(guān)聯(lián)規(guī)則挖掘算法

關(guān)聯(lián)規(guī)則挖掘算法的基本概念包括兩個(gè)方面的內(nèi)容：項(xiàng)以及項(xiàng)集，其中項(xiàng)是基本單元，用來(lái)表示實(shí)際環(huán)境中的單個(gè)具體事物，例如在超市購(gòu)買的物品；項(xiàng)集是由一個(gè)或者多個(gè)項(xiàng)組成的集合，表示的是具體的一次事務(wù)，例如顧客的一次購(gòu)買行為，在項(xiàng)集內(nèi)部，項(xiàng)與項(xiàng)之間不存在次序關(guān)系。而所謂的關(guān)聯(lián)規(guī)則是形如X ->Y的蘊(yùn)涵表達(dá)式，其中X和Y是不相交的項(xiàng)集，即X∩Y = ?。通常的關(guān)聯(lián)規(guī)則算法主要分為兩個(gè)步驟：

（1）產(chǎn)生頻繁項(xiàng)集。其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集，并將這些項(xiàng)集稱為頻繁項(xiàng)集。

（2）產(chǎn)生關(guān)聯(lián)規(guī)則。分解頻繁項(xiàng)集，獲取滿足最小置信度的規(guī)則集，并將這些規(guī)則稱為關(guān)聯(lián)規(guī)則。

其中，支持度表示給定數(shù)據(jù)集的頻繁程度，而置信度是指在包含的事務(wù)中出現(xiàn)的頻繁程度。

關(guān)聯(lián)規(guī)則算法是由R.Agrawal首次提出的，稱為Apriori算法。它采用“支持度—置信度”的框架產(chǎn)生關(guān)聯(lián)規(guī)則集，其影響深遠(yuǎn)，后續(xù)許多算法都是基于其思想提出的，并統(tǒng)稱為類Apriori算法。該類算法首先是利用k—頻繁項(xiàng)集，計(jì)算得到對(duì)應(yīng)的（k +1）-候選項(xiàng)集；其次利用先驗(yàn)定理（頻繁項(xiàng)集的子集一定是頻繁項(xiàng)集）裁剪非頻繁項(xiàng)集；最后使用支持度裁剪機(jī)制獲?。╧ +1）-頻繁項(xiàng)集。之后重復(fù)上述迭代過(guò)程，直到無(wú)法產(chǎn)生新的頻繁候選項(xiàng)集為止。其算法的缺點(diǎn)是產(chǎn)生過(guò)多的候選項(xiàng)集，并且多次掃描數(shù)據(jù)庫(kù)。

另一個(gè)有影響深遠(yuǎn)的算法是FP-growth算法，針對(duì)Apriori算法多次掃描數(shù)據(jù)庫(kù)的缺點(diǎn)，F(xiàn)P-growth算法設(shè)計(jì)了一種FP-Tree的數(shù)據(jù)結(jié)構(gòu)體，通過(guò)讀取一次數(shù)據(jù)庫(kù)將其所有的數(shù)據(jù)壓縮到一棵FP-Tree上，并通過(guò)循環(huán)產(chǎn)生前綴序列的FP-Tree，獲取對(duì)應(yīng)的頻繁項(xiàng)集。該算法的優(yōu)點(diǎn)在于利用FP-Tree結(jié)構(gòu)壓縮原始數(shù)據(jù)集，縮小搜索范圍，快速產(chǎn)生頻繁項(xiàng)集。

通過(guò)多年的發(fā)展，目前關(guān)聯(lián)規(guī)則算法已經(jīng)定義了許多新類型的模式，如模糊關(guān)聯(lián)規(guī)則、稀有關(guān)聯(lián)規(guī)則、基于權(quán)重的關(guān)聯(lián)規(guī)則等。由于關(guān)聯(lián)規(guī)則算法的日趨成熟，其相應(yīng)的研究熱點(diǎn)已經(jīng)從如何產(chǎn)生關(guān)聯(lián)規(guī)則逐漸轉(zhuǎn)變?yōu)槿绾萎a(chǎn)生有效的關(guān)聯(lián)規(guī)則，例如目前有效規(guī)則的一個(gè)研究熱點(diǎn)是如何挖掘高“效用”的關(guān)聯(lián)規(guī)則[23]。

7.5.2 頻繁序列模式挖掘算法

頻繁序列模式挖掘算法是由Agrawal和Srikant首次提出的，并且隨著其被廣泛應(yīng)用在分析用戶的購(gòu)物習(xí)慣、異常行為檢測(cè)以及網(wǎng)絡(luò)入侵檢測(cè)等應(yīng)用場(chǎng)景中，序列模式挖掘算法的研究取得了迅猛發(fā)展。從宏觀上講，序列模式的組成包括3方面的內(nèi)容：序列、事件（事務(wù)或者項(xiàng)集）以及項(xiàng)，它們?nèi)咧g的關(guān)系是序列是由一個(gè)或者多個(gè)事件組成的，而事件是由一個(gè)或者多個(gè)項(xiàng)組成的；在組成序列的事件中，事件與事件之間存在著先后時(shí)間關(guān)系，而在組成事件的項(xiàng)中，項(xiàng)與項(xiàng)之間不存在先后時(shí)間關(guān)系。

頻繁序列模式依據(jù)產(chǎn)生序列模式的方法不同可以分為兩種：一種可以被稱為類Apriori算法，其基于“候選-測(cè)試”的思想，利用前一步產(chǎn)生的k -頻繁序列模式，產(chǎn)生（k +1）-頻繁序列模式候選集，并利用支持度測(cè)試的裁剪機(jī)制，從而獲取最終的（k +1）-頻繁序列模式集。其具有代表性的算法包括：AprioriAll以及SPADE[24]算法，其中圖11展現(xiàn)了使用SPADE算法產(chǎn)生新的候選序列的過(guò)程。

如圖11所示，SPADE算法使用樹(shù)形結(jié)構(gòu)，利用上層的2-頻繁序列模式a1-b1以及a1-d1產(chǎn)生3-頻繁序列模式a1-b1-d1。類Apriori算法的優(yōu)點(diǎn)是可以挖掘出在限制條件下所有的頻繁序列模式集，其缺點(diǎn)是有些類Apriori算法會(huì)在產(chǎn)生頻繁序列模式集的時(shí)候，多次掃描數(shù)據(jù)庫(kù)，增加算法的I/O操作；其次在產(chǎn)生頻繁序列模式的時(shí)候，會(huì)產(chǎn)生大量的無(wú)用候選序列，增加算法的計(jì)算時(shí)間，降低算法的挖掘效率。

另一類算法是采用“投影”技術(shù)，依據(jù)不同的前綴序列對(duì)原始數(shù)據(jù)集進(jìn)行劃分，并通過(guò)不斷更新前綴序列以及劃分?jǐn)?shù)據(jù)集的操作，最終獲取完整的頻繁序列模式集，其具有代表性的算法是PrefixSpan[25]。圖12顯示了利用“投影”技術(shù)，獲取的原始數(shù)據(jù)集中所有1-前綴序列所對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)：

在圖12中顯示了利用“投影”技術(shù)，獲取原始數(shù)據(jù)集對(duì)應(yīng)的所有1-前綴序列的投影數(shù)據(jù)庫(kù)。其算法的優(yōu)點(diǎn)在于利用“投影”技術(shù)可以將原始數(shù)據(jù)集的規(guī)模不斷縮小，以縮小算法的搜索范圍，同時(shí)由于各個(gè)前綴的投影數(shù)據(jù)庫(kù)是相互獨(dú)立的，所以可以并行地挖掘?qū)?yīng)的各個(gè)投影數(shù)據(jù)庫(kù)，提高算法的挖掘效率；該算法的缺點(diǎn)是如果前綴序列在原始序列集中分布均勻，即對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)變小趨勢(shì)緩慢，則無(wú)法縮小算法的搜索空間。根據(jù)算法挖掘結(jié)果的不同，可以將序列模式算法分為：全集頻繁序列模式挖掘算法、閉合頻繁序列模式挖掘算法以及最長(zhǎng)頻繁序列模式挖掘算法等。

7.5.3 基于數(shù)據(jù)流的頻繁序列模式

挖掘算法

由于數(shù)據(jù)流具有無(wú)限性以及動(dòng)態(tài)性的特點(diǎn)，因此傳統(tǒng)的頻繁序列模式挖掘算法已經(jīng)無(wú)法適用于數(shù)據(jù)流對(duì)象，如何在數(shù)據(jù)流中獲取頻繁序列模式已經(jīng)成為了序列模式挖掘算法中的一個(gè)研究熱點(diǎn)，由于其尚處在一個(gè)發(fā)展階段，大部分的算法還是在原有的數(shù)據(jù)流基本算法的基礎(chǔ)上，結(jié)合序列模式挖掘算法設(shè)計(jì)完成的。根據(jù)使用不同基本算法，數(shù)據(jù)流挖掘算法大致可以分為3類，第1類是利用給定的界限值，挖掘近似的頻繁序列模式集；第2類是設(shè)計(jì)一種新的滑動(dòng)時(shí)間窗口，基于批處理的思想，挖掘頻繁序列模式集；第3類是設(shè)計(jì)一種新的數(shù)據(jù)結(jié)構(gòu)，例如FP-Growth中的FP-Tree結(jié)構(gòu)體，保存對(duì)應(yīng)的壓縮信息，結(jié)合滑動(dòng)時(shí)間窗口，挖掘頻繁序列模式集。根據(jù)數(shù)據(jù)流動(dòng)態(tài)變化的性質(zhì)，又可以將數(shù)據(jù)流挖掘算法分為兩類，一類是針對(duì)分布固定不變的數(shù)據(jù)流對(duì)象，挖掘近似完備的頻繁序列模式集，另一類是針對(duì)動(dòng)態(tài)分布變化的數(shù)據(jù)流對(duì)象，檢測(cè)數(shù)據(jù)流中出現(xiàn)的“概念漂移”的現(xiàn)象，解決模型失效的問(wèn)題。

8 結(jié)束語(yǔ)

物聯(lián)網(wǎng)興起，互聯(lián)網(wǎng)高速發(fā)展，各種信息普遍數(shù)字化，PB級(jí)數(shù)據(jù)廣泛出現(xiàn)，云計(jì)算和云存儲(chǔ)技術(shù)都正在改變?nèi)藗兪褂糜?jì)算機(jī)使用信息服務(wù)的方式，企業(yè)依托海量數(shù)據(jù)學(xué)習(xí)來(lái)解決以往無(wú)法解決問(wèn)題，互聯(lián)網(wǎng)企業(yè)則利用數(shù)據(jù)挖掘技術(shù)獲得高額利潤(rùn)和社會(huì)影響力，這些都意味著大數(shù)據(jù)時(shí)代的來(lái)臨。大數(shù)據(jù)的獲取和應(yīng)用對(duì)企業(yè)來(lái)講，意味著經(jīng)濟(jì)效益，Google、Yahoo、阿里巴巴等是大數(shù)據(jù)應(yīng)用獲益的典型代表；對(duì)科技界來(lái)講，意味著新的科學(xué)研究方法甚至是新的科研范式；而大數(shù)據(jù)對(duì)政府而言則是與人力資源、自然資源一樣重要的國(guó)家戰(zhàn)略資源。但是，在大數(shù)據(jù)的研究和應(yīng)用中，存在著很多問(wèn)題和挑戰(zhàn)，包括：（1）傳統(tǒng)關(guān)系數(shù)據(jù)模型無(wú)法高效處理非結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)，以MapReduce和Hadoop為代表的非關(guān)系數(shù)據(jù)分析技術(shù)在應(yīng)用性能等方面仍存在很多問(wèn)題，尚沒(méi)有一個(gè)像當(dāng)年Codd所提出的關(guān)系數(shù)據(jù)庫(kù)那樣的理論來(lái)統(tǒng)一解決非結(jié)構(gòu)化處理問(wèn)題。（2）適合不同行業(yè)的大數(shù)據(jù)挖掘分析工具和開(kāi)發(fā)環(huán)境。不同行業(yè)需要不同的大數(shù)據(jù)分析工具，當(dāng)前跨領(lǐng)域跨行業(yè)數(shù)據(jù)共享仍存在很多壁壘。（3）數(shù)據(jù)隱私保護(hù)。大數(shù)據(jù)以數(shù)據(jù)的共享為基礎(chǔ)，但如何同時(shí)保護(hù)用戶的隱私則是需要解決的問(wèn)題。相信隨著大數(shù)據(jù)技術(shù)問(wèn)題逐步解決，大數(shù)據(jù)應(yīng)用必將給我們社會(huì)和生活帶來(lái)更多的正能量。

參考文獻(xiàn)

[12] MAYER-SCHONBERGER V， CUKIER K.大數(shù)據(jù)時(shí)代：生活、工作與思維的大變革[M].盛楊燕，周濤， 譯. 杭州：浙江人民出版社， 2012.

[13] Schlimmer J C，Granger R H Jr. Incremental Learning from Noisy Data[J].Machine Learning，1986，1（3）：317-354.

[14] Gerhard W，Kubat M. Effective Learning in Dynamic Environments by Explicit Context Tracking[C]//Proceedings of the European Conference on Machine Learning （ECM’93），Apr 5-7，1993，Vienna， Austria. Berlin，Germany： Springer， 1993.

[15] Last M. Online Classification of Nonstationary Data Streams[J].Intelligent Data Analysis， 2002，6（2）：129-147.

[16] Katakis I， Tsoumakas G， VLAHAVAS L. Tracking Recurring Contexts Using Ensemble Classifiers： An Application to Email Filtering[J].Knowledge and Information Systems，2010， 22（3）： 371-391.

[17] Alippi C， Roveri M. Just-in-time Adaptive Classifiers—Part II： Designing the Classifier[J]. IEEE Transactions on Neural Networks，2008，19（12）：2053-2064.

[18] Alippi C， Boracchi G， Roveri M. An Effective Just-in-Time Adaptive Classifier for Gradual Concept Drifts[C]// Proceedings of the IEEE International Joint Conference on Neural Networks （IJCNN’11），Jun 31-Aug 5， 2011， San Jose，CA，USA . Piscataway， NJ， USA： IEEE， 2011：1675 - 1682 .

[19] Vorburger P， Bernstein A. Entropy-Based Concept Shift Detection[C]// Proceedings of the 6th IEEE International Conference on Data Mining （ICDM’06）， Dec 18-22，2007， Hong Kong，China . Los Alamitos， CA， USA： IEEE Computer Society，2006：1113 - 1118.

[20] Kuncheva L I. Change Detection in Streaming Multivariate Data Using Likelihood Detectors[J]. IEEE Transactions on Knowledge and Data Engineering， 2013，25（5）：1175 - 1180 .

[21] Domingos P， Hulten G. Mining High-Speed Data Streams[C]//Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD’00）， Aug 20-23， 2000， Boston， MA， USA . New York， NY， USA： ACM， 2000：71-80.

[22] Rutkowski L， Pietruczuk L，DUDA P. et al. Decision Trees for Mining Data Streams Based on the McDiarmid's Bound[J].IEEE Transactions on Kowledge and Data Engineering， To be published.

[23] Tseng V S， WU C W， Shie B E，et al. UPGrowth： An Efficient Algorithm for High Utility Itemset Mining[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining （KDD’10）， Jul 25-28， 2010， Washington， DC， USA. New York， NY， USA： ACM， 2010：253-262.

[24] Zaki M J. SPADE： An Efficient Algorithm for Mining Frequent Sequences[J].Machine Learning，2001，42（1/2）：31-60.

[25] Pei J， Han J W， MORTAZAVI-ASL B， et al. PrefixSpan： Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth[C]//Proceedings of the 17th International Conference on Data Engineering （ICDE’01）， Apr 2-6，2001，Heidelberg， Germany. Piscataway， NJ， USA： IEEE， 2001：215-224.