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

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

3、al Join）問題相同的地理區域經常有不同的視圖一個空間實體可用空間和非空間的屬性來描述Slide no 7 很多基本空間查詢是數據挖掘行為的基礎，這些查詢包括： 區域查詢或范圍查詢：尋找那些與在查詢中指定區域相交的實體。 最鄰近查詢：尋找與指定實體相鄰的實體 距離掃描：尋找與指定的實體相距一段確定距離的實體，這個距離是逐漸增大的。 小提示：所有這些查詢都可以用來輔助空間聚類或分類操作。 Slide no 8 空間關系計算 (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） 兩個空間實體之間存在若干拓撲關系。這些關系基于兩個實體的位置：分離（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) 方位是描述兩個點狀實體位置關系的一種度量，如果要分析面狀實體間的方位關系，則應把多邊形轉換為重心點或其它點狀實體。 Slide no 13 空間場模型空間場模型空間場模型主要用于模擬在空間上連續分布的地理現象，屬性取值既可以式連續的，也可以是離散的?？臻g場數據模型的優點是數據結構簡單，便于空間法分析與模擬。缺點是不利于表達空間實體，數據量也大。Slide no 14 空間要素模型圖15-3 基于要素的空間信息模型對現實世界的抽象基于要素的空間信息模型對現實世界的抽象現實世界現實世界專題要素專題要素

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

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

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

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

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

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

13、迭代次數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個聚類域中包含的樣本個數。 若 則停止迭代，第t 次迭代結果為劃分為k 個類別的聚類方案，轉向(7) ；否則,t = t + 1 ，轉向(4) 。 當k m 時，k = k + 1 ，轉向(3)

14、；否則，系統聚類結束。( )(1)1,1,2,ti DjtjisjCsjkN(1)( )min,1,2,ttjjCCejkSlide no 3015.2.1 多媒體數據挖掘的特點 多媒體數據復雜。 多媒體信息語義關聯性強。 多媒體信息具有時空相關性。 知識的表達和解釋比較困難，多媒體挖掘所得出的模式往往比較隱晦。Slide no 31多媒體數據挖掘典型系統結構 多媒體數據挖掘系統是在基于內容的多媒體數據檢索系統發展的基礎上出現的。它的一般結構圖如圖15-8所示。圖圖15-8 多媒體數據挖掘系統結構多媒體數據挖掘系統結構挖掘任務媒體數據庫多媒體數據集知識庫挖掘引擎數據立方體媒體屬性特征數據預處理

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

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

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

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

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

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

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

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

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

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

25、挖掘屬于信息結構（IA）方面的研究內容。對對于一個站點而言，按結構層次高低可以分出三種結構：站于一個站點而言，按結構層次高低可以分出三種結構：站點結構、頁面（框架）結構、頁內結構。點結構、頁面（框架）結構、頁內結構。Slide no 56 Page-rank Page-rank方法方法 大量的Web鏈接信息提供了豐富的關于Web內容相關性、質量和結構方面的信息，這對Web挖掘是可以利用的一個重要資源。Slide no 57 基于以上考慮，人們提出了如下的概念：基于以上考慮，人們提出了如下的概念： Web可以用一個有向圖來表示，G=（V，E），V是頁面的集合，E

26、是頁面之間的超鏈接集合。頁面抽象為圖中的頂點，而頁面之間的超鏈接抽象為圖中的有向邊。頂點V的入邊表示對V的引用，出邊表示V引用了其他的頁面。所以Web頁面之間的超鏈接揭示了Web結構。Slide no 58 鏈接文本（Anchor Texts）可以用來對被引用的頁面進行索引（例如：Webor,WWW，Google）。超鏈接可以用來計算頁面的rankings core,通過超鏈接可以將一個頁面的ranking core傳遞到相鄰的頁面。Slide no 59 Page-rank的基本思想如下： 頁面被多次引用，則這個頁面很可能是重要的。一個頁面盡管沒有被多次引用，但被一個重要頁面引用，則這個頁面

27、很可能是重要的。一個頁面的重要性被均分并被傳遞到它所引用的頁面。Slide no 60 Hub/authority方法 挖掘Web上的多媒體數據 關于多媒體的數據挖掘一般包括圖像數據挖掘、音頻數據挖掘、視頻數據挖掘等。Slide no 6圖像挖掘 圖像挖掘（Image Mining）指對圖形圖像數據信息的自動處理和知識發現，包含模式識別、圖像檢索以及特征分析等。 圖像的空間特性是非常重要的特性，包括圖像中各種對像的模式、布局、空間層次等。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模式發現模式發現 要解決的問題就是數據的預處理，它主要包括兩個部分： （1）數據清洗（Data Cleaning）:包括無關記錄的剔除、判斷是否有重要的訪問沒有被記錄、用戶的識別等問題。 （2）事務識別（Transaction Identification）:是指將頁面訪問序列劃分為代表Web事務或用戶會話的邏輯單元。 如路徑分析、關聯

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

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

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

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

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

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

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

36、O examplesO A2inf()(log ()jiikiktkO APpPijkikijkanPnSlide no 792.數據帶概念漂移的分類方法數據帶概念漂移的分類方法下面介紹各種概念漂移學習方法。下面介紹各種概念漂移學習方法。 FLORA FLORA 框架框架 由于FLORA 算法每次只能處理一個樣本,所以它對數據到達的速度是有限制的。 Slide no 80 CVFDTCVFDT 該算法在葉節點可能會產生概念漂移時產生一棵備選子樹,并且在新子樹變得更精確時用新子樹替代原先的子樹,從而解決了概念漂移所導致的預測性能下降的問題。 離線離線C4.5C4.5 Harries 和Sammu

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

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

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

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

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

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

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

44、SPADE算法等 . Slide no 95 AprioriAll算法將序列的長度定義為序列中包含的項集的數量。該算法將序列模式挖掘過程分為五個階段。 (1) 排序階段 (2) 頻繁項集階段 (3) 轉換階段 (4) 序列階段 (5) 最大序列階段Slide no 96 第二類是J.Han等人提出的基于模式增長的算法，包括FreeSpan算法、PrefixSpan算法等。PrefixSpan(Prefix-projected equential Pattern Mining)算法和FreeSpan算法都是基于模式增長的挖掘方法。Slide no 97 約束可以用多種形式表示。可能是屬性，屬性質之間的聯系或者結果模式中的聚集。 第一個約束是時間序列的持續時間（duration）T。 第二個約束是事件重疊窗口（event folding window），w。 第三個約束是被發現的模式中時間之間的時間間隔（interval）int。 Slide no 9815.7.4 15.7.4 時間相關序列數據的周期性分析時間相關序列數據的周期性分析 “什么是周期分析？”周期分析（periodicity analysis）是指對周期模式的挖掘，即在時序數據庫中找出重復出現的模式。 Slide no 99 周期模式挖掘可以從不同的角度觀察，基于模式覆蓋，可