第5復雜對數(shù)據(jù)挖掘

1、slide no 1數(shù)據(jù)挖掘原理與數(shù)據(jù)挖掘原理與spss clementine應用寶典應用寶典 元昌安元昌安 主編主編 鄧松李文敬劉海濤編著鄧松李文敬劉海濤編著 電子工業(yè)出版社電子工業(yè)出版社slide no 2 slide no 315.1 15.1 空間數(shù)據(jù)庫挖掘空間數(shù)據(jù)庫挖掘 15.2 15.2 多媒體數(shù)據(jù)挖掘多媒體數(shù)據(jù)挖掘 15.3 15.3 文本挖掘文本挖掘15.4 15.4 挖掘萬維網(wǎng)挖掘萬維網(wǎng)15.5 15.5 挖掘數(shù)據(jù)流挖掘數(shù)據(jù)流15.6 15.6 時間序列數(shù)據(jù)挖掘時間序列數(shù)據(jù)挖掘 15.7 15.7 挖掘事務數(shù)據(jù)庫中的序列模式挖掘事務數(shù)據(jù)庫中的序列模式15.8 15.8 挖掘生

2、物學數(shù)據(jù)中的序列模式挖掘生物學數(shù)據(jù)中的序列模式slide no 4 空間數(shù)據(jù)庫挖掘（sdm）實質(zhì)上是空間信息技術(shù)發(fā)展的必然結(jié)果，它是數(shù)據(jù)庫挖掘（dm）的一個重要分支，面對的都是空間數(shù)據(jù)庫（spatial database,sdb）。 空間實體之間又具有空間拓撲、空間距離、空間方位這3種關(guān)系 slide no 5 空間數(shù)據(jù)是指與二維、三維或更高維空間的空間坐標及空間范圍相關(guān)的數(shù)據(jù) 空間數(shù)據(jù)的復雜性特征有： 空間屬性之間的非線性關(guān)系 空間數(shù)據(jù)的多尺度特征 空間信息的模糊性 空間維數(shù)的增高 空間數(shù)據(jù)的缺值slide no 6 空間查詢及其操作的主要特點有：空間操作相對復雜和不精確空間連接（spati

3、al join）問題相同的地理區(qū)域經(jīng)常有不同的視圖一個空間實體可用空間和非空間的屬性來描述slide no 7 很多基本空間查詢是數(shù)據(jù)挖掘行為的基礎(chǔ)，這些查詢包括： 區(qū)域查詢或范圍查詢：尋找那些與在查詢中指定區(qū)域相交的實體。 最鄰近查詢：尋找與指定實體相鄰的實體 距離掃描：尋找與指定的實體相距一段確定距離的實體，這個距離是逐漸增大的。 小提示：所有這些查詢都可以用來輔助空間聚類或分類操作。 slide no 8 空間關(guān)系計算 (1) 常用的兩個空間實體之間的距離有： 最小值方法最小值方法：定義實體a和b的距離為a中的所有點與和b中的所有點之間的歐氏或曼哈頓距離中最小的，即 （15 -1）(,)

4、,(,)( , )min(,),(,)aabbaabbxya xybdis a bdis xyxyslide no 9大值方法大值方法：定義實體a和b的距離為a中的所有點與和b中的所有點之間的歐氏或曼哈頓距離中最大的，即 （15-2）平均值方法平均值方法：定義實體a和b的距離為a中的所有點與和b中的所有點之間的歐氏或曼哈頓距離的平均值，即 （15-3）(,),(,)( , )max(,),(,)aabbaabbxya xybdis a bdis xyxy(,),(,)( , )(,),(,)aabbaabbxya xybdis a baveragedis xyxyslide no 10 中心方

5、法中心方法：定義實體a和b的距離為a中的中心點與和b中的中心點之間的歐氏或曼哈頓距離的平均值，即 (15-4) 其中最簡單的方法就是取實體a的中心點和b的中心點，該中心點可以通過查找實體的幾何中心來識別。 ( , )(,),(,)cacacbcbdis a bdis xyxyslide no 11 （2） 兩個空間實體之間存在若干拓撲關(guān)系。這些關(guān)系基于兩個實體的位置：分離（disjoint） ：a與b分離，表示b中任何點都不在a中，反之亦然。重疊/相交： a與b重疊或相交表示至少有一個點既在a里也在b里。等價： a與b這兩個實體的所有點都是共有的。slide no 12l包含于： a包含于b，

6、表示a的所有點都在b里，反之不一定。l覆蓋/包含： a覆蓋或包含b，當且僅當b包含于a。 (3) 方位是描述兩個點狀實體位置關(guān)系的一種度量，如果要分析面狀實體間的方位關(guān)系，則應把多邊形轉(zhuǎn)換為重心點或其它點狀實體。 slide no 13 空間場模型空間場模型空間場模型主要用于模擬在空間上連續(xù)分布的地理現(xiàn)象，屬性取值既可以式連續(xù)的，也可以是離散的?？臻g場數(shù)據(jù)模型的優(yōu)點是數(shù)據(jù)結(jié)構(gòu)簡單，便于空間法分析與模擬。缺點是不利于表達空間實體，數(shù)據(jù)量也大。slide no 14 空間要素模型圖15-3 基于要素的空間信息模型對現(xiàn)實世界的抽象基于要素的空間信息模型對現(xiàn)實世界的抽象現(xiàn)實世界現(xiàn)實世界專題要素專題要素

7、1實體實體1專題要素專題要素2專題要素專題要素n實體實體2實體實體n時間特征時間特征屬性特征屬性特征空間關(guān)空間關(guān) 系特征系特征幾何特征幾何特征slide no 15 小提示：實體必須符合三個條件：可被識別，重要（與問題相關(guān)），可被描述（有特征）。表15-2 現(xiàn)實世界與信息世界的對應關(guān)系 slide no 16空間網(wǎng)絡模型空間網(wǎng)絡模型 空間網(wǎng)絡結(jié)構(gòu)模型中地理現(xiàn)象被抽象為鏈、結(jié)點以及它們之間的連通關(guān)系（圖15-4 對空間網(wǎng)絡的抽象）。 圖的形式化定義為 （15-10） 圖15-4 對空間網(wǎng)絡的抽象 ( ),( ),ggv g e g racdbslide no 17 位置位置屬性一體化的空間實體信

8、息模型屬性一體化的空間實體信息模型 一般空間實體的形式化模型為一個四元組，分別代表空間實體四個方面的特征。其中位置特征數(shù)據(jù)為 （15-11） 1122112211( , ),exxxexxxxeiippnnnnx yp當 為點（ ,y）,（,y ）, ,（,y ）,當 為折線（ ,y）,（,y ）, ,（,y ）,( ,y ),當 為面slide no 18 空間數(shù)據(jù)挖掘（sdm）是指對空間數(shù)據(jù)庫中非明確存在的知識，空間關(guān)系，或其它有意義的模式等的提取。 空間數(shù)據(jù)挖掘的框架體系空間數(shù)據(jù)挖掘的框架體系 一般認為可以大致分為三 層結(jié)構(gòu)，如圖15-5空間數(shù)據(jù)挖掘的

9、體系結(jié)構(gòu)所示。其中，第一層是數(shù)據(jù)源；第二層是挖掘器；第三層是用戶界面。 slide no 19圖15-5 空間數(shù)據(jù)挖掘的體系結(jié)構(gòu)slide no 20 空間評價。 空間分類與聚類。 空間分布計算。 空間優(yōu)化。 空間回歸分析。 空間動態(tài)模擬與預測。 空間與時序關(guān)聯(lián)知識歸納。 slide no 2 空間關(guān)聯(lián)分析 空間關(guān)聯(lián)規(guī)則挖掘是傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘的延伸，常用最小支持度和最小可信度來作為基本的統(tǒng)計參數(shù)，由于空間數(shù)據(jù)的特點，往往是在多層概念上進行歸納。slide no 22 挖掘空間關(guān)聯(lián)規(guī)則的有效方法是自上而下、逐步加深的搜索技術(shù)。首先在高的概念層次進行搜索，在較粗的精度級別查找頻繁

10、發(fā)生的模式和在這些模式中較強的隱含關(guān)系；然后，對頻繁發(fā)生的模式加深搜索至較低的概念層次，這種處理持續(xù)到找不到頻繁發(fā)生的模式為止。slide no 23典型的五步算法：典型的五步算法： step1：通過給定的查詢抽取出相關(guān)的數(shù)據(jù)。 step2：應用一個粗的空間運算方法，計算整個相關(guān)數(shù)據(jù)的集合。 step3：過濾出那些支持度小于最小支持度閾值的1階謂詞。 step4：應用一個細化的空間計算方法，從所導出的粗的謂詞集合中計算謂詞。 step5：向低層深入，在多個概念層次上找到關(guān)聯(lián)規(guī)則的完整集合。slide no 24空間分類指分析空間對象導出與一定空間特征有關(guān)的分類模式 小提示：小提示：空間因素可以

11、是非空間屬性和空間屬性，也可以是二者同時使用。 (1) 對于樣本數(shù)據(jù)的訓練可以通過改造傳統(tǒng)的分類算法來完成 (2) 空間決策樹 空間分類技術(shù)建構(gòu)決策樹采用兩步方法。這個方法的思想基礎(chǔ)是空間實體可以與其接近的實體來描述。假設類的描述是基于與實體相近最相關(guān)的謂詞的集合。建造一個決策樹slide no 25空間決策樹有五個主要步驟： 根據(jù)已知的分類，從數(shù)據(jù)d中找到例子s。 確定最佳謂詞p用來分類。一般首先在較粗的層次中尋找相關(guān)謂詞，然后再在較為細化的層次。slide no 26 找到最佳的緩沖區(qū)大小和形狀。對于取樣中的每個實體，它周圍的區(qū)域被稱為緩沖區(qū)。目標是選擇一個能產(chǎn)生對測試集中的類型進行最不同

12、的緩沖區(qū)。 使用p和c，對每個緩沖區(qū)歸納謂詞。 使用泛化的謂詞和id3建造二叉樹t。slide no 27 空間聚類分析是空間模式識別和空間數(shù)據(jù)挖掘的重要手段之一。它的目的是要在一個較大的多維數(shù)據(jù)集中根據(jù)距離的計算找出簇，或稠密區(qū)域。 小提示：空間聚類找到的聚類不應該依賴于檢驗空間中的點的順序，而且聚類也不應該受不相干的點影響。 本節(jié)介紹的空間聚類方法是基于坐標屬性一體化的空間信息模型， slide no 28從兩類直至每個樣本為一類的系統(tǒng)聚類算法步驟如下： 對地理特征向量中的每一個元素進行無量綱化。 令類別數(shù)k = 2 ，置迭代誤差閾值emin =0.100001 (可根據(jù)需要設置) 。 置

13、迭代次數(shù)t = 0 ，k 個初始聚類中心為： 對第t 次迭代,若有 則把樣本si 分配到第j0 個聚類域 。如此，所有的m 個樣本可以被劃分到k 個聚類域 中.( )jc= s , j = 1 ,2 , ,ktj(t)(t)jiji0sc sc , j = 1 ,2 , ,k, ; i = 1 ,2 , ,m且jj0( ) tjd( ) tjdslide no 29 計算新的聚類中心 式中nj 為第j個聚類域中包含的樣本個數(shù)。 若 則停止迭代，第t 次迭代結(jié)果為劃分為k 個類別的聚類方案，轉(zhuǎn)向(7) ；否則,t = t + 1 ，轉(zhuǎn)向(4) 。 當k m 時，k = k + 1 ，轉(zhuǎn)向(3)

14、；否則，系統(tǒng)聚類結(jié)束。( )(1)1,1,2,ti djtjisjcsjkn(1)( )min,1,2,ttjjccejkslide no 3015.2.1 多媒體數(shù)據(jù)挖掘的特點 多媒體數(shù)據(jù)復雜。 多媒體信息語義關(guān)聯(lián)性強。 多媒體信息具有時空相關(guān)性。 知識的表達和解釋比較困難，多媒體挖掘所得出的模式往往比較隱晦。slide no 31多媒體數(shù)據(jù)挖掘典型系統(tǒng)結(jié)構(gòu) 多媒體數(shù)據(jù)挖掘系統(tǒng)是在基于內(nèi)容的多媒體數(shù)據(jù)檢索系統(tǒng)發(fā)展的基礎(chǔ)上出現(xiàn)的。它的一般結(jié)構(gòu)圖如圖15-8所示。圖圖15-8 多媒體數(shù)據(jù)挖掘系統(tǒng)結(jié)構(gòu)多媒體數(shù)據(jù)挖掘系統(tǒng)結(jié)構(gòu)挖掘任務媒體數(shù)據(jù)庫多媒體數(shù)據(jù)集知識庫挖掘引擎數(shù)據(jù)立方體媒體屬性特征數(shù)據(jù)預處理

15、用戶挖掘接口slide no 32 關(guān)于多媒體數(shù)據(jù)挖掘的內(nèi)容一般包括圖像數(shù)據(jù)挖掘、音頻數(shù)據(jù)挖掘、關(guān)于多媒體數(shù)據(jù)挖掘的內(nèi)容一般包括圖像數(shù)據(jù)挖掘、音頻數(shù)據(jù)挖掘、視頻數(shù)據(jù)挖掘等。視頻數(shù)據(jù)挖掘等。 圖像挖掘圖像挖掘 圖像包含著豐富的視覺特性和空間特性。 視頻挖掘視頻挖掘 視頻包括豐富的內(nèi)容特性，除了圖像具有的視覺特性和空間特性外,還具有時間特性、視頻對象特性和運動特性等。 slide no 33 音頻挖掘音頻挖掘 音頻挖掘通常有兩種途徑: 運用語音識別技術(shù)將語音識別成文字，將音頻挖掘轉(zhuǎn)換成文本挖掘； 直接從音頻中提取聲音特征，如音調(diào)、韻律等,運用聚類的方法分析聲音模式。 web web 挖掘挖掘 多媒

16、體綜合挖掘多媒體綜合挖掘 多媒體概念與單媒體的區(qū)別在于，它是一個集成的系統(tǒng)概念，媒體之間有聯(lián)系。slide no 34 在圖像和視頻數(shù)據(jù)庫中可以挖掘涉及多媒體對象的關(guān)聯(lián)規(guī)則，至少包含以下三類： 圖像內(nèi)容和非圖像內(nèi)容特征間的關(guān)聯(lián) 與空間關(guān)系無關(guān)的圖像內(nèi)容的關(guān)聯(lián) 與空間關(guān)系有關(guān)的圖像內(nèi)容的關(guān)聯(lián)slide no 35 對多媒體數(shù)據(jù)相似性搜索，主要考慮兩種多媒體標引和檢索系統(tǒng)： （1）基于描述的檢索系統(tǒng)，主要是在圖像描述之上建立標引和執(zhí)行對象檢索，如關(guān)鍵字、標題、尺寸、創(chuàng)建時間等； （2）基于內(nèi)容的檢索系統(tǒng)，它支持基于圖像內(nèi)容的檢索，如顏色構(gòu)成、質(zhì)地、形狀、對象和小波變換等。slide no 36 在

17、基于內(nèi)容的檢索系統(tǒng)中,通常有兩種查詢： 基于圖像樣本的查詢（image sample-based queries）。圖像樣本查詢是指找出所有與給定圖像樣本相似的圖像。 圖像特征描述查詢(image feature specification queries) 。圖像特征描述查詢是指給出圖像的特征描述或概括slide no 37 到目前為止人們已經(jīng)提出了幾種在圖像數(shù)據(jù)庫中基于圖像特征標識的相似檢索方法： 基于顏色直方圖的特征標識 多特征構(gòu)成的特征標識 基于小波的特征標識 帶有區(qū)域粒度的小波特征標識slide no 38 我們也可以對多媒體數(shù)據(jù)進行分類和預測分析，尤其用在如天文學、地震學、地理科學

18、等的研究中。分類是多媒體數(shù)據(jù)的一種分析形式,它根據(jù)媒體某一特征(或一組特征)將數(shù)據(jù)分成不同的類。它是一個兩步過程：第1步，建立一個模型，用來描述預定義類集。第2步，使用模型進行分類。slide no 3915.3.1文本挖掘概述 數(shù)據(jù)庫挖掘處理的對象是結(jié)構(gòu)化的數(shù)據(jù)，目的是從結(jié)構(gòu)化數(shù)據(jù)源中發(fā)現(xiàn)不同屬性之間的關(guān)聯(lián)規(guī)則，或者是對數(shù)據(jù)對象進行聚類及分類處理，或者是構(gòu)造數(shù)據(jù)的預測模型。 slide no 40文本挖掘的一般過程 文本挖掘過程一般包括文本準備、特征標引、特征集縮減、知識模式的提取、知識模式的評價、知識模式的輸出等過程 .文本特征標引特征集縮減知識模型的提取知識模型的評價知識模型的輸出sli

19、de no 41文本挖掘的主要目標是獲得文本的主要內(nèi)容特征文本挖掘的主要目標是獲得文本的主要內(nèi)容特征 特征提取 主題標引 文本分類 文本聚類 自動摘要slide no 42 文本的預處理 目前，人們在對文本集進行自動分類、自動聚類、自動摘要或更深層次的挖掘處理時常常采用這樣的策略:先用一個高度概括的向量來表示一篇文本，將文本集概括成一個向量集，這個向量集等同于一個二維表格，然后通過對文本集對應的向量集進行相關(guān)的分析，達到對文本集進行自動分類、自動聚類、自動產(chǎn)生文摘或自動挖掘出更深層的隱含知識的目的。slide no 43文本的表示文本的表示 文本表示是指用文本的特征信息集合來代表原來的文本.向

20、量空間模型的基本思想是以向量來表示文本，其中為第i個特征項的權(quán)重。 相對詞頻的計算方法主要運用tf-idf公式。公式如下： （15-15）)(),(),(tidftdtftdidftfslide no 44 所謂標引，是指給出信息內(nèi)容特征的過程。 漢語自動分詞方法有多種，主要有詞典法、切分標記法等。 1詞典分詞法 2. 切分標記分詞法 小提示：切分標記法的典型代表是非用詞后綴表法。該法將漢字分為“非用字”、“條件用字”、“表內(nèi)用字”、“表外用字”。主要利用“非用字”和“條件用字”進行詞語的切分。slide no 45 1 1基于評估函數(shù)的方法基于評估函數(shù)的方法 基于評估函數(shù)的特征集縮減算法使用

21、特征獨立性假設以簡化特征選擇。 2 2潛在語義標引潛在語義標引 潛在語義標引法利用矩陣理論中的“奇異值分解”技術(shù)，將詞頻矩陣轉(zhuǎn)化為維數(shù)大大減小的奇異矩陣。 slide no 46 文本自動分類的一般過程如下：首先，取一個預分類的文本集作為訓練集。然后，分析訓練集以導出分類模型。通常，需要用一個檢驗過程對該分類模型求精。所導出的分類模型可以用于其它聯(lián)機文本分類。slide no 47 下面介紹幾種已經(jīng)成功應用于文本分類的典型的分類方法。1簡單向量距離分類 具體步驟如下:(1). 根據(jù)訓練集文本向量空間模型計算每類文本集的中心向量；(2). 將新文本表示為特征向量；(3). 計算新文本特征向量和每

22、類中心向量間的相似度；(4). 比較每類中心向量與新文本的相似度，將文本分到相似度最大的那個類別中。slide no 48 2簡單貝葉斯分類算法算法具體步驟如下：計算特征詞屬于每個類別的概率向量 。對于新文本di，計算該文本屬于類cj 的概率。比較新文本屬于所有類的概率，將文本分到概率最大的那個類別中。n,21slide no 49 3 3k k最近鄰居（最近鄰居（knnknn）算法）算法 該算法的基本思路是:在給定新文本后，考慮在訓練文本集中與該新文本距離最近(最相似)的k篇文本，根據(jù)這幾篇文本所屬的類別判定新文本所屬的類別，該算法具體的步驟如下: slide no 50(1). 根據(jù)特征項

23、集合重新描述訓練文本向量；(2). 將新文本表示為特征向量；(3).比較類的權(quán)重，將文本分到權(quán)重最大的那個類別中 (4).在訓練文本集中選出與新文本最相似的k個文本，計算公式為： mkjkmkikmkjkikjiwwwwddsim12121,.(15-16)slide no 51 (5).在新文本的k個鄰居中，依次計算每類的權(quán)重，計算公式： jiknndijcdydxsimcxp,.(15-17)其中， 為新文本的特征向量， 為相似度計算公式， 為類別屬性函數(shù)，即如果 屬于類 ，那么函數(shù)值為1，否則為0。xidxsim ,jicdy,idjcslide no 521 1光譜聚類方法光譜聚類方法

24、 首先，對原始數(shù)據(jù)進行光譜嵌入（維度歸約），然后對維度歸約后的文本空間運用傳統(tǒng)的聚類算法（如k均值）。slide no 532 2混合模型聚類方法混合模型聚類方法 用混合模型對文本數(shù)據(jù)聚類包括兩個步驟： (1) 基于文本數(shù)據(jù)和附加的先驗知識估計模型參數(shù)； (2) 基于估計的模型參數(shù)推斷聚類。slide no 54 遺傳算法(ga)為文本聚類提供了一種非層次的聚類方法，其核心思想是使簇內(nèi)文本間的相似度最大化。其核心思想是使簇內(nèi)文本間的相似度最大化。 slide no 5515.4 15.4 挖掘互聯(lián)網(wǎng)挖掘互聯(lián)網(wǎng) 15.4.1 15.4.1 挖掘挖掘webweb頁面布局結(jié)構(gòu)頁面布局結(jié)構(gòu) web結(jié)構(gòu)

25、挖掘?qū)儆谛畔⒔Y(jié)構(gòu)（ia）方面的研究內(nèi)容。對對于一個站點而言，按結(jié)構(gòu)層次高低可以分出三種結(jié)構(gòu)：站于一個站點而言，按結(jié)構(gòu)層次高低可以分出三種結(jié)構(gòu)：站點結(jié)構(gòu)、頁面（框架）結(jié)構(gòu)、頁內(nèi)結(jié)構(gòu)。點結(jié)構(gòu)、頁面（框架）結(jié)構(gòu)、頁內(nèi)結(jié)構(gòu)。slide no 56 page-rank page-rank方法方法 大量的web鏈接信息提供了豐富的關(guān)于web內(nèi)容相關(guān)性、質(zhì)量和結(jié)構(gòu)方面的信息，這對web挖掘是可以利用的一個重要資源。slide no 57 基于以上考慮，人們提出了如下的概念：基于以上考慮，人們提出了如下的概念： web可以用一個有向圖來表示，g=（v，e），v是頁面的集合，e

26、是頁面之間的超鏈接集合。頁面抽象為圖中的頂點，而頁面之間的超鏈接抽象為圖中的有向邊。頂點v的入邊表示對v的引用，出邊表示v引用了其他的頁面。所以web頁面之間的超鏈接揭示了web結(jié)構(gòu)。slide no 58 鏈接文本（anchor texts）可以用來對被引用的頁面進行索引（例如：webor,www，google）。超鏈接可以用來計算頁面的rankings core,通過超鏈接可以將一個頁面的ranking core傳遞到相鄰的頁面。slide no 59 page-rank的基本思想如下： 頁面被多次引用，則這個頁面很可能是重要的。一個頁面盡管沒有被多次引用，但被一個重要頁面引用，則這個頁面

27、很可能是重要的。一個頁面的重要性被均分并被傳遞到它所引用的頁面。slide no 60 hub/authority方法 挖掘web上的多媒體數(shù)據(jù) 關(guān)于多媒體的數(shù)據(jù)挖掘一般包括圖像數(shù)據(jù)挖掘、音頻數(shù)據(jù)挖掘、視頻數(shù)據(jù)挖掘等。slide no 6圖像挖掘 圖像挖掘（image mining）指對圖形圖像數(shù)據(jù)信息的自動處理和知識發(fā)現(xiàn)，包含模式識別、圖像檢索以及特征分析等。 圖像的空間特性是非常重要的特性，包括圖像中各種對像的模式、布局、空間層次等。slide no 62 音頻挖掘（audio mining）指對音頻信息的自動處理和分析過程。 語音挖掘的另外一個用途在于將語音對應到個人s

28、lide no 63 視頻挖掘視頻挖掘 15.4.4 web15.4.4 web文檔的自動分類文檔的自動分類 15.4.5 web15.4.5 web使用挖掘使用挖掘 slide no 6415.4.5 .115.4.5 .1模式發(fā)現(xiàn)模式發(fā)現(xiàn) 要解決的問題就是數(shù)據(jù)的預處理，它主要包括兩個部分： （1）數(shù)據(jù)清洗（data cleaning）:包括無關(guān)記錄的剔除、判斷是否有重要的訪問沒有被記錄、用戶的識別等問題。 （2）事務識別（transaction identification）:是指將頁面訪問序列劃分為代表web事務或用戶會話的邏輯單元。 如路徑分析、關(guān)聯(lián)

29、規(guī)則挖掘、時序模式以及聚類和分類技術(shù)。slide no 65相關(guān)分析方法如下相關(guān)分析方法如下： (1) 可視化技術(shù)對于理解web用戶的行為模式來講是一個自然的選擇。(2) 聯(lián)機分析處理（olap）技術(shù)也可以應用到模式的分析中來。(3) 計劃挖掘（plan mining）挖掘通常的存取規(guī)律，可以調(diào)整web連接，改善性能。slide no 66(4) 相關(guān)序列存取模式分析，可以對服務器的緩存、預取和交換參數(shù)進行調(diào)整。(5) 趨勢分析，可以了解web下在發(fā)生的變化，用戶的個性化分析可以為用戶提供定制的服務。slide no 67 對web訪問日志（web log）進行分析和挖掘要經(jīng)過一系列的數(shù)據(jù)準備

30、工和和建模工作。一個基本的流程包括如下步驟。 （1）首先要對web log進行清洗、過濾和轉(zhuǎn)換，從中抽取感興趣的數(shù)據(jù)。slide no 68 （2）將資源的類型、資源的大小、請求的時間、在資源上停留的時間、請求次數(shù)、來自不同internet域的請求次數(shù)、事件、會話、錯誤次數(shù)作為在這些維變量下的度量變量建立數(shù)據(jù)立方體（data cube）。 （3）利用成熟的數(shù)據(jù)挖掘技術(shù)（如特征、分類、關(guān)聯(lián)、預測、時間序列分析、趨勢分析） slide no 69 為了從數(shù)據(jù)流中發(fā)現(xiàn)知識或模式，有必要開發(fā)單遍掃描的、聯(lián)機的、多層的、多維的流處理和分析方法。 單遍掃描的聯(lián)機數(shù)據(jù)分析方法，不應該只限于流數(shù)據(jù)，它對于處理

31、海量的非數(shù)據(jù)流也是至關(guān)重要的。 slide no 70 本節(jié)，我們考慮一些常用的大綱數(shù)據(jù)結(jié)構(gòu)和技術(shù)。 1 1隨機抽樣隨機抽樣 一種叫做水庫抽樣，可以用來無放回的選取一個無偏的s個元素的隨機樣本，沒有更換。水庫抽樣的想法相對簡單。2 2滑動窗口滑動窗口 基本的思想是：僅僅基于最近的數(shù)據(jù)做出決策，而不是對目前為止看到的所有數(shù)據(jù)或?qū)δ硞€樣本進行計算。slide no 71 3. 3.直方圖直方圖 直方圖是一種大綱的數(shù)據(jù)結(jié)構(gòu)，可以用來近似數(shù)據(jù)流中元素值的頻率分布。4. 4.多分辨方法多分辨方法 處理大量數(shù)據(jù)的一種常見方式是使用數(shù)據(jù)歸約方法。一種流行的數(shù)據(jù)歸約方法是采用分治策略，如多分辨率數(shù)據(jù)結(jié)構(gòu)5.

32、5.數(shù)據(jù)流管理系統(tǒng)和流查詢數(shù)據(jù)流管理系統(tǒng)和流查詢 流數(shù)據(jù)的查詢處理結(jié)構(gòu)包括三個部分：終端用戶，查詢處理器和臨時空間（這可能由主存和磁盤構(gòu)成）。slide no 721 1壓縮時間尺度的時間維：傾斜時間框架壓縮時間尺度的時間維：傾斜時間框架 這種模型對許多分析任務來說是足夠的，也能保證駐留在內(nèi)存或存儲在硬盤上的數(shù)據(jù)總量很小。 2. 2.關(guān)鍵層關(guān)鍵層 第一層稱作最小興趣層（minimal interesting layer），是分析人員想要研究的最小興趣層。 第二層稱觀察層（observation layer），是分析人員（或自動化系統(tǒng)）希望不斷研究數(shù)據(jù)的層。slide no 733. 3. 流立

33、方體的部分物化流立方體的部分物化 常用路徑立方體計算（popular path cubing）,它通過一條常用下鉆路徑，從最小興趣層到觀察層執(zhí)行上卷操作，僅僅物化該路徑中的層次，其它層僅在需要的時候計算。這種方法在空間，計算時間和靈活性上取得了適度平衡，并具有快速增量聚集時間，快速下鉆時間，并且空間需求很小。slide no 74 1. 1.數(shù)據(jù)流頻繁模式挖掘數(shù)據(jù)流頻繁模式挖掘2. 2.數(shù)據(jù)流頻繁模式挖掘算法數(shù)據(jù)流頻繁模式挖掘算法 數(shù)據(jù)流頻繁模式挖掘的關(guān)鍵問題就是如何快速對數(shù)據(jù)流中所出現(xiàn)的模式進行計數(shù)。slide no 75數(shù)據(jù)流所出現(xiàn)的模式分成三類數(shù)據(jù)流所出現(xiàn)的模式分成三類: : (1) 當

34、sup(x)s 時,稱x 為頻繁模式； (2) 當sup(x)s 時,稱x 為潛在頻繁模式； (3) 當sup(x)s 時,稱x 為非頻繁模式,并在算法中舍棄非頻繁的模式以減少算法的空間復雜度。slide no 7615.5.4 15.5.4 動態(tài)數(shù)據(jù)流的分類動態(tài)數(shù)據(jù)流的分類 增量式方法又稱為在線式、連續(xù)式或序列式方法等 ,定義為s t = ( x , y) | y = f ( x ) , t = 1 , 2 , 。 數(shù)據(jù)流挖掘的增量式方法一般都假設取得的樣本是由平穩(wěn)分布的數(shù)據(jù)中所獲得。 很多研究者提出了解決數(shù)據(jù)流上概念漂移問題的分類技術(shù) 。 slide no 77 1. 1.數(shù)據(jù)平穩(wěn)分布的分

35、類方法數(shù)據(jù)平穩(wěn)分布的分類方法 vfdt( very fast decision tree) 是一種基于hoeffding 不等式建立決策樹的方法,它通過不斷地將葉節(jié)點替換為決策節(jié)點而生成。 其中每個葉節(jié)點都保存有關(guān)于屬性值的統(tǒng)計信息, 這些統(tǒng)計信息用于計算基于屬性值的測試。 slide no 78 信息增益用于表達計算分類到達該節(jié)點的樣本所需要的信息,其計算公式為 屬性j 的熵為 ,其中 表示類別k 已知的情況下屬性值取i 的概率。 vfdt 的另一重要性質(zhì)是它所產(chǎn)生的決策樹在大量減少處理樣本數(shù)目的同時,能夠保證和使用全部樣本所產(chǎn)生的決策樹具有無限接近的精度。()inf()inf()jjh a

36、o exampleso a2inf()(log ()jiikiktko apppijkikijkanpnslide no 792.數(shù)據(jù)帶概念漂移的分類方法數(shù)據(jù)帶概念漂移的分類方法下面介紹各種概念漂移學習方法。下面介紹各種概念漂移學習方法。 flora flora 框架框架 由于flora 算法每次只能處理一個樣本,所以它對數(shù)據(jù)到達的速度是有限制的。 slide no 80 cvfdtcvfdt 該算法在葉節(jié)點可能會產(chǎn)生概念漂移時產(chǎn)生一棵備選子樹,并且在新子樹變得更精確時用新子樹替代原先的子樹,從而解決了概念漂移所導致的預測性能下降的問題。 離線離線c4.5c4.5 harries 和sammu

37、t基于c4.5 開發(fā)了一個離線學習系統(tǒng),該系統(tǒng)將數(shù)據(jù)流分為一個關(guān)于時間的“概念聚類”集合。 slide no 81 為了對數(shù)據(jù)流進行有效的聚類，幾個新的方法已制定，具體情況如下： 計算和存儲過去匯總的數(shù)據(jù) 應用分治策略 增量聚類傳入的數(shù)據(jù)流 進行微聚類以及宏聚類分析 利用多個時間粒度為分析集群的演變 把流聚類劃分為聯(lián)機和脫機處理slide no 82 已開發(fā)了幾個算法為聚類數(shù)據(jù)流的算法。這里介紹其中兩個，即streamstream和和clustreamclustream。 1. stream1. stream：基于：基于k k中位數(shù)的流聚類算法中位數(shù)的流聚類算法 stream是一種單遍掃描，常

38、數(shù)因子的近似算法，是為k -中位數(shù)問題開發(fā)的。 stream源于k中位數(shù)聚類，使用有限的時間和空間。 slide no 83 2. clustreamclustream：聚類演變的數(shù)據(jù)流：聚類演變的數(shù)據(jù)流 clustream是一種基于用戶指定的、聯(lián)機聚類查詢的演變數(shù)據(jù)流聚類算法。 聯(lián)機微簇的處理分為兩個階段進行：聯(lián)機微簇的處理分為兩個階段進行： （1）收集統(tǒng)計數(shù)據(jù) （2）更新微簇 。 slide no 84 .1趨勢分析趨勢分析 “如何處理時序數(shù)據(jù)？”目前一般有四種主要的變化成分用于特征化時序數(shù)據(jù)： 1長期或趨勢變化(trend movement) 2循環(huán)運動或循環(huán)變化(c

39、yclic movement or cyclic variations) 3季節(jié)性運動或季節(jié)性變化(seasonal movements or seasonal variations) 4非規(guī)則或隨機變化（irregular or random movements）slide no 85 “怎樣確定數(shù)據(jù)的趨勢?”一個確定的趨勢的常用方法是用下面的算數(shù)均值序列計算n階移動平均：slide no 86 “什么是相似搜索（similarity search）？”通常數(shù)據(jù)庫查詢是要找出符合查詢的精確數(shù)據(jù)，相似搜索與之不同，它是找出與給定查詢序列最接近的數(shù)據(jù)序列。 slide no 87 數(shù)據(jù)變換(da

40、ta transformation)：從時間域(time domain)到頻率域(frequency domain)對時序數(shù)據(jù)的相似分析，通常采用歐氏距離作為相似計算的依據(jù)。 兩個常見的獨立于數(shù)據(jù)的變換是離散傅立葉變換（dft）和離散小波變（dwt）。slide no 88 能夠處理存在間隙和偏移與振幅差異的相似搜索的執(zhí)行步驟如下： 1原子匹配（atomic matching） 2窗口結(jié)合(window stitching) 3子序列排序(subsequence ordering)slide no 89 下圖是子序列s(sequence s)和子序列t(sequence t)的原始序列（ori

41、ginal sequence）、刪除間隙（removing gap）、偏移變換（offset translation）和振幅變換（amplitude scaling）的差別。 此圖是在時序數(shù)據(jù)中的子序列匹配：原始序列形狀相同，但需要調(diào)整以處理存在于間隙、偏移和振幅中的差異。這些調(diào)整允許子序列在一定寬度的范圍內(nèi)匹配。 slide no 90slide no 91 15.7.1 15.7.1 序列模式挖掘：概念和原語序列模式挖掘：概念和原語 “什么是序列模式挖掘？”序列模式挖掘是指挖掘相對時間或其它模式出現(xiàn)頻率高的模式。舉個例子，順序模式是“顧客在購買佳能數(shù)碼相機有可能在一個月以內(nèi)購買hp彩色打印

42、機 ”。 項集是一個非空的商品名的集合, d 的第三個屬性便是項集。 slide no 92 序列是一個向量, 這個向量的每一維均為項集。用( s1，s2， ，sn) 表示向量, 其中sj 為項集； 對于兩個向量s1=、s2=, 若存在整數(shù)0i1i2 inm+1 使得 , 則稱s1 包含于s2, 記作 在一個序列集中, 若序列s 不包含于任何其它的序列, 我們稱s 是極大的； 在d 中, 我們可以將某個顧客的項集按時間順序排成一個序列, 我們稱這個序列為這個顧客的顧客序列；slide no 93 若一個序列包含于某個顧客的顧客序列中, 則稱此顧客支持此序列； 支持某序列的顧客數(shù)與總顧客數(shù)之比稱

43、為此序列的支持率； 當一個序列的支持率不小于一個給定的值時, 稱這個序列為頻繁序列；而這個值稱為最小支持, 記作min_sup； 序列所擁有的項集個數(shù)稱為序列的長度。一個長度為k 的序列稱為k 序列； 設為1 序列, i 為其中唯一項集。若某客戶支持,則稱此客戶支持項集i； 若為頻繁序列, 則稱i 為頻繁項集。slide no 94 對于序列模式挖掘，如何開發(fā)有效的和可伸縮的方法？最近的研究在這兩方面取得了進展：（1）挖掘序列模式完全集的有效方法，（2）僅挖掘序列模式閉集的有效方法 第一類是基于r.agrawal等人提出的apriori特性的算法，主要包括aprioriall算法、gsp算法、

44、spade算法等 . slide no 95 aprioriall算法將序列的長度定義為序列中包含的項集的數(shù)量。該算法將序列模式挖掘過程分為五個階段。 (1) 排序階段 (2) 頻繁項集階段 (3) 轉(zhuǎn)換階段 (4) 序列階段 (5) 最大序列階段slide no 96 第二類是j.han等人提出的基于模式增長的算法，包括freespan算法、prefixspan算法等。prefixspan(prefix-projected equential pattern mining)算法和freespan算法都是基于模式增長的挖掘方法。slide no 97 約束可以用多種形式表示?？赡苁菍傩?，屬性質(zhì)之間的聯(lián)系或者結(jié)果模式中的聚集。 第一個約束是時間序列的持續(xù)時間（duration）t。 第二個約束是事件重疊窗口（event folding window），w。 第三個約束是被發(fā)現(xiàn)的模式中時間之間的時間間隔（interval）int。 slide no 9815.7.4 15.7.4 時間相關(guān)序列數(shù)據(jù)的周期性分析時間相關(guān)序列數(shù)據(jù)的周期性分析 “什么是周期分析？”周期分析（periodicity analysis）是指對周期模式的挖掘，即在時序數(shù)據(jù)庫中找出重復出現(xiàn)的模式。 slide no 99 周期模式挖掘可以從不同的角度觀察，基于模式覆蓋，可