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

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

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

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

7.2概念漂移

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

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

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

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

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

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

7.3 聚類

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

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

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

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

7.3.1 基于劃分的聚類

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

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

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

7.3.2 基于層次的聚類

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

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

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

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

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

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

7.3.4 基于模型的聚類

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

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

數(shù)據(jù)挖掘中的分類指的是：首先根據(jù)已知類別的一些樣本進行學(xué)習(xí)，得到一個分類的規(guī)則或者說是模型，然后利用學(xué)習(xí)得到的模型對另外一些類別未知其他屬性值已知的樣本進行類別的判斷或者預(yù)測。可以看出，分類和聚類的不同之處在于：分類學(xué)習(xí)時，樣本類別時已知的；而聚類學(xué)習(xí)時，樣本類別甚至類別數(shù)目是未知的。因此前者是有監(jiān)督的學(xué)習(xí)，后者則是一種無監(jiān)督的學(xué)習(xí)。分類學(xué)習(xí)的一個經(jīng)典的例子是對銀行現(xiàn)有的顧客信用信息進行學(xué)習(xí)，建立信用良好或欺詐客戶的判斷模型，當一個新的顧客申請銀行借貸時，利用學(xué)習(xí)模型進行判斷，給出新客戶良好或是欺詐客戶的可能性，從而提高銀行業(yè)務(wù)決策的科學(xué)性。

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

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

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

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

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

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

7.5 頻繁模式挖掘

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

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

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

（2）產(chǎn)生關(guān)聯(lián)規(guī)則。分解頻繁項集，獲取滿足最小置信度的規(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ī)則集，其影響深遠，后續(xù)許多算法都是基于其思想提出的，并統(tǒng)稱為類Apriori算法。該類算法首先是利用k—頻繁項集，計算得到對應(yīng)的（k +1）-候選項集；其次利用先驗定理（頻繁項集的子集一定是頻繁項集）裁剪非頻繁項集；最后使用支持度裁剪機制獲取（k +1）-頻繁項集。之后重復(fù)上述迭代過程，直到無法產(chǎn)生新的頻繁候選項集為止。其算法的缺點是產(chǎn)生過多的候選項集，并且多次掃描數(shù)據(jù)庫。

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

通過多年的發(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)的研究熱點已經(jīng)從如何產(chǎn)生關(guān)聯(lián)規(guī)則逐漸轉(zhuǎn)變?yōu)槿绾萎a(chǎn)生有效的關(guān)聯(lián)規(guī)則，例如目前有效規(guī)則的一個研究熱點是如何挖掘高“效用”的關(guān)聯(lián)規(guī)則[23]。

7.5.2 頻繁序列模式挖掘算法

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

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

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

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

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

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

挖掘算法

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

8 結(jié)束語

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

參考文獻

[12] MAYER-SCHONBERGER V， CUKIER K.大數(shù)據(jù)時代：生活、工作與思維的大變革[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.