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

1、數(shù)據(jù)流挖掘,常艷,目錄,㈠ 數(shù)據(jù)挖掘概念 ㈡ 數(shù)據(jù)流 ㈢ 數(shù)據(jù)流挖掘概念 ㈣ 數(shù)據(jù)流模型 ㈤ 幾種數(shù)據(jù)流挖掘算法 ㈥ 數(shù)據(jù)挖掘的應(yīng)用,㈠數(shù)據(jù)挖掘的概念,數(shù)據(jù)挖掘是指從海量數(shù)據(jù)中發(fā)現(xiàn)一些有趣的趨勢(shì)或模式, 以便指導(dǎo)有關(guān)未來(lái)的活動(dòng)的決策。數(shù)據(jù)挖掘與傳統(tǒng)的數(shù)據(jù)分析(如查詢(xún)、 報(bào)表、 聯(lián)機(jī)應(yīng)用分析) 的本質(zhì)區(qū)別是數(shù)據(jù)挖掘是在沒(méi)有明確假設(shè)的前提下去挖掘信息、 發(fā)現(xiàn)知識(shí)。數(shù)據(jù)挖掘所得到的信息應(yīng)具有先前未知、 有效和可實(shí)用三個(gè)特

2、征。,數(shù)據(jù)挖掘可以是針對(duì)一般的數(shù)據(jù)源也可以針對(duì)特殊應(yīng)用的數(shù)據(jù)源。針對(duì)一般數(shù)據(jù)源的挖掘主要有序列數(shù)據(jù)挖掘、流數(shù)據(jù)挖掘、文本數(shù)據(jù)挖掘、多媒體數(shù)據(jù)挖掘、空間數(shù)據(jù)挖掘等; 針對(duì)特殊應(yīng)用數(shù)據(jù)源的挖掘有交易數(shù)據(jù)挖掘、Web數(shù)據(jù)挖掘、生物數(shù)據(jù)挖掘、金融數(shù)據(jù)挖掘、氣象數(shù)據(jù)挖掘、統(tǒng)計(jì)數(shù)據(jù)挖掘、電信數(shù)據(jù)挖掘等。,㈡數(shù)據(jù)流,概念： 一個(gè)實(shí)時(shí)的、連續(xù)的、潛在無(wú)界的、不確定的、隨時(shí)間變化的(隱含的通過(guò)到達(dá)時(shí)間或者明確的時(shí)間戳)數(shù)據(jù)項(xiàng)的序列，又

3、稱(chēng)流數(shù)據(jù)或流式數(shù)據(jù)。其到達(dá)的速度可能突然發(fā)生變化、數(shù)據(jù)流的更新通常以插入為主。令t表示任一時(shí)間戳，at表示在該時(shí)間戳到達(dá)的數(shù)據(jù)，數(shù)據(jù)流可以表示成{…，at-1，at， at+1，…}。,特點(diǎn)： ①數(shù)據(jù)流中的數(shù)據(jù)元素是聯(lián)機(jī)實(shí)時(shí)、快速到達(dá)的; ②系統(tǒng)無(wú)法控制將被處理的數(shù)據(jù)元素的到達(dá)次序; ③ 數(shù)據(jù)規(guī)模宏大, 不可能把所有的數(shù)據(jù)都放入內(nèi)存甚至是硬盤(pán);(ID3,C4.5,CART假設(shè)所有樣本都存在主存，SLIQ和SPRINT假設(shè)樣本

4、都存在硬盤(pán)上) ④數(shù)據(jù)流中的數(shù)據(jù)元素一旦被處理，要么丟棄，要么存檔。除非顯示地存儲(chǔ)在內(nèi)存里，否則很難檢索，因?yàn)閮?nèi)存相對(duì)于數(shù)據(jù)流的尺寸要小得多。,㈢數(shù)據(jù)挖掘概念,概念： 由于數(shù)據(jù)流自身的特性,數(shù)據(jù)流挖掘已經(jīng)成為數(shù)據(jù)挖掘的一個(gè)新的研究方向。數(shù)據(jù)流挖掘就是在數(shù)據(jù)流上發(fā)現(xiàn)提取隱含在其中的、 人們事先不知道的、 但又潛在有用的信息和知識(shí)的過(guò)程。數(shù)據(jù)流挖掘的難點(diǎn)： 流數(shù)據(jù)挖掘的特點(diǎn)決定了它比傳統(tǒng)的數(shù)據(jù)挖

5、掘要復(fù)雜，一般我們要考慮下面三個(gè)問(wèn)題。,① ：流數(shù)據(jù)是不停產(chǎn)生的，而內(nèi)存的大小是有限的，我們無(wú)法把收集到的數(shù)據(jù)都放在內(nèi)存中等待挖掘，而只能實(shí)時(shí)的進(jìn)行處理。所以在設(shè)計(jì)挖掘算法時(shí)要注意怎樣才能將有限的內(nèi)存充分利用，使得一次能處理更多的數(shù)據(jù)。 ②：儲(chǔ)存在內(nèi)存中的數(shù)據(jù)都是最新產(chǎn)生的數(shù)據(jù)，我們必須在這些數(shù)據(jù)還沒(méi)被后來(lái)的數(shù)據(jù)替代前，對(duì)它進(jìn)行處理。,這就要求我們?cè)谠O(shè)計(jì)算法時(shí)要考慮算法的效率，如何在最短的時(shí)間內(nèi)完成對(duì)數(shù)據(jù)的處理。 ③：我們沒(méi)有任

6、何可以暫時(shí)阻塞數(shù)據(jù)流的操作，所以所有的數(shù)據(jù)只能掃描一次.所以我們?cè)O(shè)計(jì)的都應(yīng)該是一次掃描算法(single-scan algorithm),㈣數(shù)據(jù)流模型,為提高數(shù)據(jù)挖掘的效率 ,首先應(yīng)該對(duì)數(shù)據(jù)流建模。根據(jù)適用范圍的不同 ,存在多種不同的數(shù)據(jù)流式模型 ,可以按照不同的標(biāo)準(zhǔn)對(duì)其進(jìn)行分類(lèi)。 4.1 按照數(shù)據(jù)描述方式進(jìn)行分類(lèi)設(shè)數(shù)據(jù)流中的數(shù)據(jù)項(xiàng) x 1 , …, xi , …, xn 依次按下標(biāo)順序到達(dá) ,它們描述了一個(gè)信號(hào) A。按 xi描述

7、信號(hào) A的方式 ,數(shù)據(jù)流模型可分為以下幾類(lèi)[ 2 ]:,(1)時(shí)序 ( Ti me Series)模型:A [ i ] = xi ,用來(lái)描述時(shí)間序列數(shù)據(jù)。此時(shí) ,數(shù)據(jù)流中的每個(gè)數(shù)據(jù)項(xiàng)都代表一個(gè)獨(dú)立的信號(hào)。(2)現(xiàn)金登記 (Cash Register)模型:令 xi = ( j,Ii ) ,且 Ii≥0,則 Ai [ j ] =Ai - 1 [ j ] + I i。此時(shí) ,數(shù)據(jù)流中的多個(gè)數(shù)據(jù)項(xiàng)增量式地表達(dá)一個(gè) A [ j ]。(3)十

8、字轉(zhuǎn)門(mén) ( Turnstile)模型:令 xi = ( j,Ui) ,則Ai[ j ] =Ai - 1 [ j ] +Ui。其中 , Ui可為正數(shù) ,也可為負(fù)數(shù)。此時(shí) ,數(shù)據(jù)流中的多個(gè)數(shù)據(jù)項(xiàng)表達(dá)一個(gè) A [ j ]。A[ j ]隨著數(shù)據(jù)的流入 ,可能會(huì)增加 ,也可能會(huì)減小。,4.2按照時(shí)序范圍分類(lèi)按照算法處理數(shù)據(jù)流時(shí)所采用的時(shí)序范圍 ,數(shù)據(jù)流模型可分為以下幾類(lèi)[ 3 ]: (1)快照模型 ( Snap shotModel) :處

9、理數(shù)據(jù)的范圍限制在兩個(gè)預(yù)定義的時(shí)間戳之間。 (2)界標(biāo)模型 (Landmark Model) :處理數(shù)據(jù)的范圍從某一個(gè)已知的初始時(shí)間點(diǎn)到當(dāng)前時(shí)間點(diǎn)為止。 (3)滑動(dòng)窗口模型 ( SlidingWindow Model) :處理數(shù)據(jù)的范圍由某個(gè)固定大小的滑動(dòng)窗口確定 ,此滑動(dòng)窗口的終點(diǎn)永遠(yuǎn)為當(dāng)前時(shí)刻。其中 ,滑動(dòng)窗口的大小可以由一個(gè)時(shí)間區(qū)間定義 ,也可以由窗口所包含的數(shù)據(jù)項(xiàng)數(shù)目定義。,（五）數(shù)據(jù)流挖掘算法,5.1 聚類(lèi)(cl

10、ustering)算法 聚類(lèi)是在預(yù)先不知道劃分類(lèi)的情況下根據(jù)信息相似度原則將信息分成簇的過(guò)程。同一個(gè)簇中的對(duì)象之間具有很高的相似度 ,而不同簇中的對(duì)象高度相異。流數(shù)據(jù)動(dòng)態(tài)增量的進(jìn)入系統(tǒng)使得對(duì)數(shù)據(jù)流的聚類(lèi)必須增量更新 ,而且只能在有限的空間上對(duì)其進(jìn)行單次掃描。 近年來(lái) ,有學(xué)者提出了應(yīng)用于大規(guī)模數(shù)據(jù)集的一趟聚類(lèi)算法 ,如 Birch算法 ,它們可以應(yīng)用于某些數(shù)據(jù)流問(wèn)題;也有學(xué)者提出了針對(duì)流數(shù)據(jù)的聚

11、類(lèi)算法 ,典型的有 Stream算法CluStream算法。,5.2 頻繁項(xiàng)挖掘 數(shù)據(jù)流上的頻繁項(xiàng)集挖掘就是單遍掃描數(shù)據(jù)流來(lái)連續(xù)發(fā)現(xiàn)其中的頻繁項(xiàng)集。頻繁項(xiàng)集滿(mǎn)足最小支持度的項(xiàng)集。Manku 等人提出一個(gè)近似的數(shù)據(jù)流頻繁項(xiàng)挖掘算法, 該算法采用的是數(shù)據(jù)流的界標(biāo)模型, 在整個(gè)數(shù)據(jù)流上進(jìn)行計(jì)算。Giannella 等人提出了 FP-Stream 的模型，它以 FP-tree 為基礎(chǔ)，用來(lái)從數(shù)據(jù)流中挖掘頻繁模型。 一

12、個(gè) FP-Stream 模型包括：一個(gè)在內(nèi)存中的，用來(lái)捕捉數(shù)據(jù)流中最頻繁和次頻繁元組集信息的 FP-tree 結(jié)構(gòu)和為每個(gè)頻繁模式建立的非均衡時(shí)間窗口(tilted-time window)表。,例如，圖 3 是基于非均衡時(shí)間窗口的頻繁模式。我們把 t3 時(shí)刻的頻繁模式以 FP-tree 的結(jié)構(gòu)刻畫(huà)出來(lái)就是圖 4 所描述的。然而，為每個(gè)時(shí)間窗口都建立一棵樹(shù)需要大量的空間，通常的做法是，只建立一棵樹(shù)，然后把每個(gè)模式的非均衡時(shí)間窗口表嵌入到

13、相應(yīng)的節(jié)點(diǎn)中。以模式 ac 為例，創(chuàng)建的 FP-tree 如圖 5。,5.3 數(shù)據(jù)流分類(lèi)算法研究 數(shù)據(jù)流上的分類(lèi)就是提出一個(gè)分類(lèi)模型, 通過(guò)單遍掃描數(shù)據(jù)流, 持續(xù)地利用分類(lèi)模型將數(shù)據(jù)流對(duì)象影射到某一個(gè)給定的類(lèi)別中。數(shù)據(jù)流分類(lèi)算法主要是 P.Domings 和 G.Hulten 的研究成果. 一種是改造的 Hoeffding決策樹(shù)分類(lèi)算法 VFDT, 使用恒定的內(nèi)存大小和時(shí)間處理每個(gè)樣本, 有效地解決了時(shí)間、

14、內(nèi)存和樣本對(duì)數(shù)據(jù)挖掘, 特別是高速數(shù)據(jù)流上的挖掘的限制。VFDT使用信息熵選擇屬性, 通過(guò)建立Hoeffding樹(shù)來(lái)進(jìn)行決策支持, 并使用 Hoeffding約束來(lái)保證高精度地處理數(shù)據(jù)流。,既可連續(xù)處理數(shù)據(jù), 也可通過(guò)二次抽樣, 重新掃描數(shù)據(jù)集, 因此可以處理非常龐大的數(shù)據(jù)集。另一種對(duì) VFDT算法引入了滑動(dòng)窗口技術(shù), 提出了 CVFDT算法。保留了 VFDT算法在速度上和精度上的優(yōu)點(diǎn), 增加了對(duì)數(shù)據(jù)產(chǎn)生過(guò)程中變化趨勢(shì)的監(jiān)測(cè), 使算法更

15、好的適應(yīng)對(duì)高速、隨時(shí)間變化數(shù)據(jù)流的分類(lèi)。 Aggarwal 設(shè)計(jì)了一個(gè)基于聚類(lèi)分類(lèi)的數(shù)據(jù)流分類(lèi)算法。Wang等人提出了一種數(shù)據(jù)流挖掘增量模糊決策樹(shù)分類(lèi)算法。,數(shù)據(jù)挖掘的應(yīng)用,應(yīng)用環(huán)境中的數(shù)據(jù)主要是以連續(xù)的、無(wú)界的、快速的、隨時(shí)間變化的數(shù)據(jù)項(xiàng)的無(wú)限序列的形式出現(xiàn)的應(yīng)用。典型的數(shù)據(jù)流應(yīng)用領(lǐng)域如下： (1)傳感器網(wǎng)絡(luò)：可用于地理位置監(jiān)控、公路擁塞監(jiān)控、運(yùn)動(dòng)物追蹤、生命信號(hào)的醫(yī)療監(jiān)控和制造過(guò)程的超級(jí)監(jiān)控。這些應(yīng)用都涉及復(fù)雜的過(guò)濾和發(fā)現(xiàn)數(shù)據(jù)中異

16、常模式的被激活的報(bào)警設(shè)置。傳感器的數(shù)據(jù)挖掘可能需要訪問(wèn)一些歷史數(shù)據(jù)，代表性的查詢(xún)操作有： 激活觸發(fā)器。例如，當(dāng)同一地域的幾個(gè)傳感器報(bào)告測(cè)量值超過(guò)給定閾值; 在氣象圖上繪制溫度控制線(xiàn)，執(zhí)行由氣象監(jiān)控站產(chǎn)生的溫度流的連接，連接結(jié)果形成帶有每個(gè)站的經(jīng)度和緯度的靜態(tài)表，將報(bào)告同一溫度的點(diǎn)連成線(xiàn)。,(2)網(wǎng)絡(luò)流量分析： 實(shí)時(shí)分析Internet流量的特殊網(wǎng)絡(luò)已經(jīng)被使用。與傳感器網(wǎng)絡(luò)功能相同的是：多個(gè)數(shù)據(jù)源到達(dá)的數(shù)據(jù)連接、包監(jiān)控、包過(guò)濾、檢測(cè)異常情

17、況和支持歷史查詢(xún)。此外，它的功能還包括監(jiān)控對(duì)熱點(diǎn)URL的需求或發(fā)現(xiàn)用戶(hù)消耗的最大帶寬。在網(wǎng)絡(luò)流量分析中典型的查詢(xún)是： 流量許可、決定源目的節(jié)點(diǎn)對(duì)以及不同IP地址組、子網(wǎng)掩碼和協(xié)議類(lèi)型站點(diǎn)的總帶寬。IP流量是多元統(tǒng)計(jì)的，因此，流量數(shù)據(jù)流必須能邏輯分解以便能重構(gòu)基本的 TCP/IP會(huì)話(huà)。而且，分解進(jìn)入會(huì)話(huà)的數(shù)據(jù)流涉及臨時(shí)語(yǔ)義問(wèn)題。比較不同的源目的站點(diǎn)對(duì)的數(shù)量; 比較在TCP三次握手中分別包含第二步和第三步的邏輯流中不同的源目的站點(diǎn)對(duì)的數(shù)量。

18、若計(jì)數(shù)值超過(guò)一個(gè)大的極限，那么一個(gè)拒絕服務(wù)事件將會(huì)產(chǎn)生。,(3)金融分析： 在線(xiàn)股票價(jià)格分析涉及發(fā)現(xiàn)關(guān)聯(lián)、鑒別趨勢(shì)、仲裁機(jī)會(huì)和預(yù)測(cè)未來(lái)值。典型的基于Web金融分析器允許用戶(hù)作如下查詢(xún)： 查詢(xún)所有股票價(jià)格在20～200美元，其最高價(jià)和最低價(jià)之間在過(guò)去30分鐘高過(guò)3個(gè)百分點(diǎn)的股票分布圖，以及最后5分鐘其震蕩平均量超過(guò)300%的股票; 查詢(xún) NASDAQ指數(shù)高于200天的平均變動(dòng)，以及當(dāng)天開(kāi)盤(pán)起價(jià)格盈利在2～10個(gè)百分點(diǎn)，買(mǎi)賣(mài)量超過(guò)50億的股

19、票; 查詢(xún)所有價(jià)格在52周高度的2個(gè)百分點(diǎn)，每天成交量至少100萬(wàn)的股票。,(4)事務(wù)日志分析： 在線(xiàn)挖掘Web使用日志、電話(huà)記錄和自動(dòng)銀行取款交易也符合數(shù)據(jù)流應(yīng)用模型。其目標(biāo)在于發(fā)現(xiàn)有趣的客戶(hù)行為模式，鑒別可疑的開(kāi)銷(xiāo)行為以便防止欺詐和預(yù)測(cè)未來(lái)數(shù)據(jù)。與其他數(shù)據(jù)流應(yīng)用一樣，它需要多個(gè)數(shù)據(jù)流的連接、復(fù)雜的過(guò)濾和統(tǒng)計(jì)分析。常見(jiàn)的查詢(xún)有： 查詢(xún)某一服務(wù)器的最近15分鐘被訪問(wèn)的、其速率至少高于日平均速率40%的所有Web頁(yè)：如果主服務(wù)器過(guò)載，實(shí)時(shí)