復(fù)雜對(duì)象數(shù)據(jù)挖掘

1、復(fù)雜對(duì)象數(shù)據(jù)挖掘第1頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二1第15章 復(fù)雜對(duì)象數(shù)據(jù)挖掘 第2頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二215.1 空間數(shù)據(jù)庫挖掘 15.2 多媒體數(shù)據(jù)挖掘 15.3 文本挖掘15.4 挖掘萬維網(wǎng)15.5 挖掘數(shù)據(jù)流15.6 時(shí)間序列數(shù)據(jù)挖掘 15.7 挖掘事務(wù)數(shù)據(jù)庫中的序列模式15.8 挖掘生物學(xué)數(shù)據(jù)中的序列模式第3頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二315.1 空間數(shù)據(jù)庫挖掘 空間數(shù)據(jù)庫挖掘（SDM）實(shí)質(zhì)上是空間信息技術(shù)發(fā)展的必然結(jié)果，它是數(shù)據(jù)庫挖掘（DM）的一個(gè)重要分支，面對(duì)的都是空間數(shù)據(jù)庫（s

2、patial database,SDB）。 空間實(shí)體之間又具有空間拓?fù)?、空間距離、空間方位這3種關(guān)系 第4頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二415.1.1 空間數(shù)據(jù)概述空間數(shù)據(jù)是指與二維、三維或更高維空間的空間坐標(biāo)及空間范圍相關(guān)的數(shù)據(jù) 空間數(shù)據(jù)的復(fù)雜性特征有： 空間屬性之間的非線性關(guān)系空間數(shù)據(jù)的多尺度特征空間信息的模糊性空間維數(shù)的增高空間數(shù)據(jù)的缺值第5頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二5 空間查詢工作 空間查詢及其操作的主要特點(diǎn)有：空間操作相對(duì)復(fù)雜和不精確空間連接（Spatial Join）問題相同的地理區(qū)域經(jīng)常有不同的視圖一個(gè)空間實(shí)體可用空

3、間和非空間的屬性來描述第6頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二6很多基本空間查詢是數(shù)據(jù)挖掘行為的基礎(chǔ)，這些查詢包括：區(qū)域查詢或范圍查詢：尋找那些與在查詢中指定區(qū)域相交的實(shí)體。最鄰近查詢：尋找與指定實(shí)體相鄰的實(shí)體距離掃描：尋找與指定的實(shí)體相距一段確定距離的實(shí)體，這個(gè)距離是逐漸增大的。小提示：所有這些查詢都可以用來輔助空間聚類或分類操作。 空間查詢工作 第7頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二715.1.2 空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型 空間關(guān)系計(jì)算 (1) 常用的兩個(gè)空間實(shí)體之間的距離有：最小值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有

4、點(diǎn)之間的歐氏或曼哈頓距離中最小的，即 （15 -1）第8頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二8大值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)之間的歐氏或曼哈頓距離中最大的，即 （15-2）平均值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)之間的歐氏或曼哈頓距離的平均值，即 （15-3）空間關(guān)系計(jì)算第9頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二9中心方法：定義實(shí)體A和B的距離為A中的中心點(diǎn)與和B中的中心點(diǎn)之間的歐氏或曼哈頓距離的平均值，即 (15-4) 其中最簡單的方法就是取實(shí)體A的中心點(diǎn)和B的中心點(diǎn)，該中心點(diǎn)可以通過查找實(shí)體的

5、幾何中心來識(shí)別。 空間關(guān)系計(jì)算第10頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二1015.1.2 空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型（2） 兩個(gè)空間實(shí)體之間存在若干拓?fù)潢P(guān)系。這些關(guān)系基于兩個(gè)實(shí)體的位置：分離（Disjoint） ：A與B分離，表示B中任何點(diǎn)都不在A中，反之亦然。重疊/相交： A與B重疊或相交表示至少有一個(gè)點(diǎn)既在A里也在B里。等價(jià)： A與B這兩個(gè)實(shí)體的所有點(diǎn)都是共有的。第11頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二11包含于： A包含于B，表示A的所有點(diǎn)都在B里，反之不一定。覆蓋/包含： A覆蓋或包含B，當(dāng)且僅當(dāng)B包含于A。(3) 方位是描述兩個(gè)點(diǎn)狀

6、實(shí)體位置關(guān)系的一種度量，如果要分析面狀實(shí)體間的方位關(guān)系，則應(yīng)把多邊形轉(zhuǎn)換為重心點(diǎn)或其它點(diǎn)狀實(shí)體。 15.1.2 空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型第12頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二12空間實(shí)體信息模型 空間場模型空間場模型主要用于模擬在空間上連續(xù)分布的地理現(xiàn)象，屬性取值既可以式連續(xù)的，也可以是離散的?？臻g場數(shù)據(jù)模型的優(yōu)點(diǎn)是數(shù)據(jù)結(jié)構(gòu)簡單，便于空間法分析與模擬。缺點(diǎn)是不利于表達(dá)空間實(shí)體，數(shù)據(jù)量也大。第13頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二13空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型 空間要素模型圖15-3 基于要素的空間信息模型對(duì)現(xiàn)實(shí)世界的抽象現(xiàn)實(shí)世界專題要

7、素1實(shí)體1專題要素2專題要素n實(shí)體2實(shí)體n時(shí)間特征屬性特征空間關(guān) 系特征幾何特征第14頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二1415.1.2 空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型小提示：實(shí)體必須符合三個(gè)條件：可被識(shí)別，重要（與問題相關(guān)），可被描述（有特征）。表15-2 現(xiàn)實(shí)世界與信息世界的對(duì)應(yīng)關(guān)系 第15頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二15空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型空間網(wǎng)絡(luò)模型 空間網(wǎng)絡(luò)結(jié)構(gòu)模型中地理現(xiàn)象被抽象為鏈、結(jié)點(diǎn)以及它們之間的連通關(guān)系（圖15-4 對(duì)空間網(wǎng)絡(luò)的抽象）。 圖的形式化定義為 （15-10） 圖15-4 對(duì)空間網(wǎng)絡(luò)的抽象ACDB第1

8、6頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二16空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型位置屬性一體化的空間實(shí)體信息模型 一般空間實(shí)體的形式化模型為一個(gè)四元組，分別代表空間實(shí)體四個(gè)方面的特征。其中位置特征數(shù)據(jù)為 （15-11） 第17頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二1715.1.3 空間數(shù)據(jù)挖掘基礎(chǔ) 空間數(shù)據(jù)挖掘（SDM）是指對(duì)空間數(shù)據(jù)庫中非明確存在的知識(shí)，空間關(guān)系，或其它有意義的模式等的提取。 空間數(shù)據(jù)挖掘的框架體系 一般認(rèn)為可以大致分為三 層結(jié)構(gòu)，如圖15-5空間數(shù)據(jù)挖掘的體系結(jié)構(gòu)所示。其中，第一層是數(shù)據(jù)源；第二層是挖掘器；第三層是用戶界面。 第18頁，共

9、111頁，2022年，5月20日，13點(diǎn)25分，星期二18圖15-5 空間數(shù)據(jù)挖掘的體系結(jié)構(gòu)第19頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二19 空間數(shù)據(jù)挖掘的方法體系空間評(píng)價(jià)?？臻g分類與聚類?？臻g分布計(jì)算?？臻g優(yōu)化?？臻g回歸分析?？臻g動(dòng)態(tài)模擬與預(yù)測?？臻g與時(shí)序關(guān)聯(lián)知識(shí)歸納。 第20頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二20幾種空間數(shù)據(jù)挖掘算法 空間關(guān)聯(lián)分析 空間關(guān)聯(lián)規(guī)則挖掘是傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘的延伸，常用最小支持度和最小可信度來作為基本的統(tǒng)計(jì)參數(shù)，由于空間數(shù)據(jù)的特點(diǎn)，往往是在多層概念上進(jìn)行歸納。第21頁，共111頁，2022年，5月20日，13點(diǎn)25分，

10、星期二21 挖掘空間關(guān)聯(lián)規(guī)則的有效方法是自上而下、逐步加深的搜索技術(shù)。首先在高的概念層次進(jìn)行搜索，在較粗的精度級(jí)別查找頻繁發(fā)生的模式和在這些模式中較強(qiáng)的隱含關(guān)系；然后，對(duì)頻繁發(fā)生的模式加深搜索至較低的概念層次，這種處理持續(xù)到找不到頻繁發(fā)生的模式為止。空間關(guān)聯(lián)分析第22頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二22空間關(guān)聯(lián)分析典型的五步算法：Step1：通過給定的查詢抽取出相關(guān)的數(shù)據(jù)。Step2：應(yīng)用一個(gè)粗的空間運(yùn)算方法，計(jì)算整個(gè)相關(guān)數(shù)據(jù)的集合。Step3：過濾出那些支持度小于最小支持度閾值的1階謂詞。Step4：應(yīng)用一個(gè)細(xì)化的空間計(jì)算方法，從所導(dǎo)出的粗的謂詞集合中計(jì)算謂詞。S

11、tep5：向低層深入，在多個(gè)概念層次上找到關(guān)聯(lián)規(guī)則的完整集合。第23頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二23空間分類算法和空間趨勢分析空間分類指分析空間對(duì)象導(dǎo)出與一定空間特征有關(guān)的分類模式 小提示：空間因素可以是非空間屬性和空間屬性，也可以是二者同時(shí)使用。 (1) 對(duì)于樣本數(shù)據(jù)的訓(xùn)練可以通過改造傳統(tǒng)的分類算法來完成 (2) 空間決策樹 空間分類技術(shù)建構(gòu)決策樹采用兩步方法。這個(gè)方法的思想基礎(chǔ)是空間實(shí)體可以與其接近的實(shí)體來描述。假設(shè)類的描述是基于與實(shí)體相近最相關(guān)的謂詞的集合。建造一個(gè)決策樹第24頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二24空間決策樹有五個(gè)

12、主要步驟：根據(jù)已知的分類，從數(shù)據(jù)D中找到例子S。確定最佳謂詞p用來分類。一般首先在較粗的層次中尋找相關(guān)謂詞，然后再在較為細(xì)化的層次?？臻g決策樹第25頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二25找到最佳的緩沖區(qū)大小和形狀。對(duì)于取樣中的每個(gè)實(shí)體，它周圍的區(qū)域被稱為緩沖區(qū)。目標(biāo)是選擇一個(gè)能產(chǎn)生對(duì)測試集中的類型進(jìn)行最不同的緩沖區(qū)。使用p和C，對(duì)每個(gè)緩沖區(qū)歸納謂詞。使用泛化的謂詞和ID3建造二叉樹T。第26頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二26 空間聚類方法 空間聚類分析是空間模式識(shí)別和空間數(shù)據(jù)挖掘的重要手段之一。它的目的是要在一個(gè)較大的多維數(shù)據(jù)集中根據(jù)距離

13、的計(jì)算找出簇，或稠密區(qū)域。 小提示：空間聚類找到的聚類不應(yīng)該依賴于檢驗(yàn)空間中的點(diǎn)的順序，而且聚類也不應(yīng)該受不相干的點(diǎn)影響。 本節(jié)介紹的空間聚類方法是基于坐標(biāo)屬性一體化的空間信息模型， 第27頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二27 空間聚類方法從兩類直至每個(gè)樣本為一類的系統(tǒng)聚類算法步驟如下：對(duì)地理特征向量中的每一個(gè)元素進(jìn)行無量綱化。令類別數(shù)k = 2 ，置迭代誤差閾值emin =0.100001 (可根據(jù)需要設(shè)置) 。置迭代次數(shù)t = 0 ，k 個(gè)初始聚類中心為：對(duì)第t 次迭代,若有 則把樣本Si 分配到第j0 個(gè)聚類域 。如此，所有的m 個(gè)樣本可以被劃分到k 個(gè)聚類域

14、 中.第28頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二28計(jì)算新的聚類中心 式中Nj 為第j個(gè)聚類域中包含的樣本個(gè)數(shù)。若 則停止迭代，第t 次迭代結(jié)果為劃分為k 個(gè)類別的聚類方案，轉(zhuǎn)向(7) ；否則,t = t + 1 ，轉(zhuǎn)向(4) 。當(dāng)k m 時(shí)，k = k + 1 ，轉(zhuǎn)向(3) ；否則，系統(tǒng)聚類結(jié)束。聚類算法步驟(續(xù)）第29頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二2915.2 多媒體數(shù)據(jù)挖掘15.2.1 多媒體數(shù)據(jù)挖掘的特點(diǎn)多媒體數(shù)據(jù)復(fù)雜。多媒體信息語義關(guān)聯(lián)性強(qiáng)。多媒體信息具有時(shí)空相關(guān)性。知識(shí)的表達(dá)和解釋比較困難，多媒體挖掘所得出的模式往往比較隱晦。第

15、30頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二3015.2.2 多媒體數(shù)據(jù)挖掘概述多媒體數(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)挖掘任務(wù)媒體數(shù)據(jù)庫多媒體數(shù)據(jù)集知識(shí)庫挖掘引擎數(shù)據(jù)立方體媒體屬性特征數(shù)據(jù)預(yù)處理用戶挖掘接口第31頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二31 多媒體數(shù)據(jù)挖掘的內(nèi)容 關(guān)于多媒體數(shù)據(jù)挖掘的內(nèi)容一般包括圖像數(shù)據(jù)挖掘、音頻數(shù)據(jù)挖掘、視頻數(shù)據(jù)挖掘等。 圖像挖掘 圖像包含著豐富的視覺特性和空間特性。 視頻挖掘 視頻包括豐富的內(nèi)容

16、特性，除了圖像具有的視覺特性和空間特性外,還具有時(shí)間特性、視頻對(duì)象特性和運(yùn)動(dòng)特性等。 第32頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二32多媒體數(shù)據(jù)挖掘的內(nèi)容音頻挖掘 音頻挖掘通常有兩種途徑: 運(yùn)用語音識(shí)別技術(shù)將語音識(shí)別成文字，將音頻挖掘轉(zhuǎn)換成文本挖掘； 直接從音頻中提取聲音特征，如音調(diào)、韻律等,運(yùn)用聚類的方法分析聲音模式。Web 挖掘多媒體綜合挖掘 多媒體概念與單媒體的區(qū)別在于，它是一個(gè)集成的系統(tǒng)概念，媒體之間有聯(lián)系。第33頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二3315.2.3 多媒體數(shù)據(jù)挖掘方法 在圖像和視頻數(shù)據(jù)庫中可以挖掘涉及多媒體對(duì)象的關(guān)聯(lián)規(guī)則，

17、至少包含以下三類：圖像內(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)第34頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二34 多媒體數(shù)據(jù)的相似搜索對(duì)多媒體數(shù)據(jù)相似性搜索，主要考慮兩種多媒體標(biāo)引和檢索系統(tǒng)：（1）基于描述的檢索系統(tǒng)，主要是在圖像描述之上建立標(biāo)引和執(zhí)行對(duì)象檢索，如關(guān)鍵字、標(biāo)題、尺寸、創(chuàng)建時(shí)間等；（2）基于內(nèi)容的檢索系統(tǒng)，它支持基于圖像內(nèi)容的檢索，如顏色構(gòu)成、質(zhì)地、形狀、對(duì)象和小波變換等。第35頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二35兩種查詢?cè)诨趦?nèi)容的檢索系統(tǒng)中,通常有兩種查詢：基于圖像樣本的查詢（im

18、age sample-based queries）。圖像樣本查詢是指找出所有與給定圖像樣本相似的圖像。圖像特征描述查詢(image feature specification queries) 。圖像特征描述查詢是指給出圖像的特征描述或概括第36頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二36 多媒體數(shù)據(jù)的相似搜索 到目前為止人們已經(jīng)提出了幾種在圖像數(shù)據(jù)庫中基于圖像特征標(biāo)識(shí)的相似檢索方法： 基于顏色直方圖的特征標(biāo)識(shí)多特征構(gòu)成的特征標(biāo)識(shí)基于小波的特征標(biāo)識(shí)帶有區(qū)域粒度的小波特征標(biāo)識(shí)第37頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二37 多媒體數(shù)據(jù)的分類和預(yù)測分析 我

19、們也可以對(duì)多媒體數(shù)據(jù)進(jìn)行分類和預(yù)測分析，尤其用在如天文學(xué)、地震學(xué)、地理科學(xué)等的研究中。分類是多媒體數(shù)據(jù)的一種分析形式,它根據(jù)媒體某一特征(或一組特征)將數(shù)據(jù)分成不同的類。它是一個(gè)兩步過程：第1步，建立一個(gè)模型，用來描述預(yù)定義類集。第2步，使用模型進(jìn)行分類。第38頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二3815.3 文本挖掘文本挖掘概述 數(shù)據(jù)庫挖掘處理的對(duì)象是結(jié)構(gòu)化的數(shù)據(jù)，目的是從結(jié)構(gòu)化數(shù)據(jù)源中發(fā)現(xiàn)不同屬性之間的關(guān)聯(lián)規(guī)則，或者是對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類及分類處理，或者是構(gòu)造數(shù)據(jù)的預(yù)測模型。 第39頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二39文本挖掘的一般過程文本

20、挖掘的一般過程文本挖掘過程一般包括文本準(zhǔn)備、特征標(biāo)引、特征集縮減、知識(shí)模式的提取、知識(shí)模式的評(píng)價(jià)、知識(shí)模式的輸出等過程 .文本特征標(biāo)引特征集縮減知識(shí)模型的提取知識(shí)模型的評(píng)價(jià)知識(shí)模型的輸出第40頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二40 文本挖掘的主要任務(wù)文本挖掘的主要目標(biāo)是獲得文本的主要內(nèi)容特征 特征提取 主題標(biāo)引 文本分類 文本聚類 自動(dòng)摘要第41頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二41 文本挖掘與信息檢索文本的預(yù)處理 目前，人們?cè)趯?duì)文本集進(jìn)行自動(dòng)分類、自動(dòng)聚類、自動(dòng)摘要或更深層次的挖掘處理時(shí)常常采用這樣的策略:先用一個(gè)高度概括的向量來表示一篇文

21、本，將文本集概括成一個(gè)向量集，這個(gè)向量集等同于一個(gè)二維表格，然后通過對(duì)文本集對(duì)應(yīng)的向量集進(jìn)行相關(guān)的分析，達(dá)到對(duì)文本集進(jìn)行自動(dòng)分類、自動(dòng)聚類、自動(dòng)產(chǎn)生文摘或自動(dòng)挖掘出更深層的隱含知識(shí)的目的。第42頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二42文本的表示 文本表示是指用文本的特征信息集合來代表原來的文本.向量空間模型的基本思想是以向量來表示文本，其中為第i個(gè)特征項(xiàng)的權(quán)重。相對(duì)詞頻的計(jì)算方法主要運(yùn)用TF-IDF公式。公式如下： （15-15）第43頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二43 文本特征標(biāo)引 所謂標(biāo)引，是指給出信息內(nèi)容特征的過程。 漢語自動(dòng)分詞方法

22、有多種，主要有詞典法、切分標(biāo)記法等。 1詞典分詞法 2. 切分標(biāo)記分詞法 小提示：切分標(biāo)記法的典型代表是非用詞后綴表法。該法將漢字分為“非用字”、“條件用字”、“表內(nèi)用字”、“表外用字”。主要利用“非用字”和“條件用字”進(jìn)行詞語的切分。第44頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二44 文本維度規(guī)約1基于評(píng)估函數(shù)的方法 基于評(píng)估函數(shù)的特征集縮減算法使用特征獨(dú)立性假設(shè)以簡化特征選擇。 2潛在語義標(biāo)引潛在語義標(biāo)引法利用矩陣?yán)碚撝械摹捌娈愔捣纸狻奔夹g(shù)，將詞頻矩陣轉(zhuǎn)化為維數(shù)大大減小的奇異矩陣。 第45頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二45 文本的自動(dòng)分類

23、文本自動(dòng)分類的一般過程如下：首先，取一個(gè)預(yù)分類的文本集作為訓(xùn)練集。然后，分析訓(xùn)練集以導(dǎo)出分類模型。通常，需要用一個(gè)檢驗(yàn)過程對(duì)該分類模型求精。所導(dǎo)出的分類模型可以用于其它聯(lián)機(jī)文本分類。第46頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二46文本分類的典型的分類方法 下面介紹幾種已經(jīng)成功應(yīng)用于文本分類的典型的分類方法。1簡單向量距離分類 具體步驟如下:(1). 根據(jù)訓(xùn)練集文本向量空間模型計(jì)算每類文本集的中心向量；(2). 將新文本表示為特征向量；(3). 計(jì)算新文本特征向量和每類中心向量間的相似度；(4). 比較每類中心向量與新文本的相似度，將文本分到相似度最大的那個(gè)類別中。第47頁

24、，共111頁，2022年，5月20日，13點(diǎn)25分，星期二47文本分類的典型的分類方法（續(xù)）2簡單貝葉斯分類算法算法具體步驟如下：計(jì)算特征詞屬于每個(gè)類別的概率向量 。對(duì)于新文本di，計(jì)算該文本屬于類Cj 的概率。比較新文本屬于所有類的概率，將文本分到概率最大的那個(gè)類別中。第48頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二48文本分類的典型的分類方法（續(xù)） 3K最近鄰居（KNN）算法 該算法的基本思路是:在給定新文本后，考慮在訓(xùn)練文本集中與該新文本距離最近(最相似)的K篇文本，根據(jù)這幾篇文本所屬的類別判定新文本所屬的類別，該算法具體的步驟如下: 第49頁，共111頁，2022年，

25、5月20日，13點(diǎn)25分，星期二49K最近鄰居（KNN）算法(1). 根據(jù)特征項(xiàng)集合重新描述訓(xùn)練文本向量；(2). 將新文本表示為特征向量；(3).比較類的權(quán)重，將文本分到權(quán)重最大的那個(gè)類別中 (4).在訓(xùn)練文本集中選出與新文本最相似的K個(gè)文本，計(jì)算公式為： .(15-16)第50頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二50 (5).在新文本的K個(gè)鄰居中，依次計(jì)算每類的權(quán)重，計(jì)算公式：.(15-17)其中， 為新文本的特征向量， 為相似度計(jì)算公式， 為類別屬性函數(shù)，即如果 屬于類 ，那么函數(shù)值為1，否則為0。K最近鄰居（KNN）算法第51頁，共111頁，2022年，5月20

26、日，13點(diǎn)25分，星期二51 文本聚類1光譜聚類方法 首先，對(duì)原始數(shù)據(jù)進(jìn)行光譜嵌入（維度歸約），然后對(duì)維度歸約后的文本空間運(yùn)用傳統(tǒng)的聚類算法（如k均值）。第52頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二52文本聚類(續(xù))2混合模型聚類方法 用混合模型對(duì)文本數(shù)據(jù)聚類包括兩個(gè)步驟： (1) 基于文本數(shù)據(jù)和附加的先驗(yàn)知識(shí)估計(jì)模型參數(shù)； (2) 基于估計(jì)的模型參數(shù)推斷聚類。第53頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二53 基于遺傳算法（GA）的文本聚類 遺傳算法(GA)為文本聚類提供了一種非層次的聚類方法，其核心思想是使簇內(nèi)文本間的相似度最大化。 第54頁，共1

27、11頁，2022年，5月20日，13點(diǎn)25分，星期二5415.4 挖掘互聯(lián)網(wǎng) 15.4.1 挖掘Web頁面布局結(jié)構(gòu) Web結(jié)構(gòu)挖掘?qū)儆谛畔⒔Y(jié)構(gòu)（IA）方面的研究內(nèi)容。對(duì)于一個(gè)站點(diǎn)而言，按結(jié)構(gòu)層次高低可以分出三種結(jié)構(gòu)：站點(diǎn)結(jié)構(gòu)、頁面（框架）結(jié)構(gòu)、頁內(nèi)結(jié)構(gòu)。第55頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二5515.4.2 挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁面 rank方法 大量的Web鏈接信息提供了豐富的關(guān)于Web內(nèi)容相關(guān)性、質(zhì)量和結(jié)構(gòu)方面的信息，這對(duì)Web挖掘是可以利用的一個(gè)重要資源。第56頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二5615.4.2 挖掘Web

28、鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁面 基于以上考慮，人們提出了如下的概念： Web可以用一個(gè)有向圖來表示，G=（V，E），V是頁面的集合，E是頁面之間的超鏈接集合。頁面抽象為圖中的頂點(diǎn)，而頁面之間的超鏈接抽象為圖中的有向邊。頂點(diǎn)V的入邊表示對(duì)V的引用，出邊表示V引用了其他的頁面。所以Web頁面之間的超鏈接揭示了Web結(jié)構(gòu)。第57頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二5715.4.2 挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁面 鏈接文本（Anchor Texts）可以用來對(duì)被引用的頁面進(jìn)行索引（例如：Webor,WWW，Google）。超鏈接可以用來計(jì)算頁面的rankings core,通

29、過超鏈接可以將一個(gè)頁面的ranking core傳遞到相鄰的頁面。第58頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二5815.4.2 挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁面 rank的基本思想如下： 頁面被多次引用，則這個(gè)頁面很可能是重要的。一個(gè)頁面盡管沒有被多次引用，但被一個(gè)重要頁面引用，則這個(gè)頁面很可能是重要的。一個(gè)頁面的重要性被均分并被傳遞到它所引用的頁面。第59頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二5915.4.2 挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁面 Hub/authority方法 挖掘Web上的多媒體數(shù)據(jù) 關(guān)于多媒體的數(shù)據(jù)挖掘一般包括圖像數(shù)據(jù)挖掘

30、、音頻數(shù)據(jù)挖掘、視頻數(shù)據(jù)挖掘等。第60頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二60挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁面圖像挖掘 圖像挖掘（Image Mining）指對(duì)圖形圖像數(shù)據(jù)信息的自動(dòng)處理和知識(shí)發(fā)現(xiàn)，包含模式識(shí)別、圖像檢索以及特征分析等。 圖像的空間特性是非常重要的特性，包括圖像中各種對(duì)像的模式、布局、空間層次等。第61頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二61 音頻挖掘音頻挖掘（Audio Mining）指對(duì)音頻信息的自動(dòng)處理和分析過程。語音挖掘的另外一個(gè)用途在于將語音對(duì)應(yīng)到個(gè)人第62頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二

31、62 音頻挖掘 視頻挖掘15.4.4 Web文檔的自動(dòng)分類 15.4.5 Web使用挖掘 第63頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二63 音頻挖掘15.4.5 .1模式發(fā)現(xiàn) 要解決的問題就是數(shù)據(jù)的預(yù)處理，它主要包括兩個(gè)部分： （1）數(shù)據(jù)清洗（Data Cleaning）:包括無關(guān)記錄的剔除、判斷是否有重要的訪問沒有被記錄、用戶的識(shí)別等問題。 （2）事務(wù)識(shí)別（Transaction Identification）:是指將頁面訪問序列劃分為代表Web事務(wù)或用戶會(huì)話的邏輯單元。 如路徑分析、關(guān)聯(lián)規(guī)則挖掘、時(shí)序模式以及聚類和分類技術(shù)。第64頁，共111頁，2022年，5月20日

32、，13點(diǎn)25分，星期二6415.4.5. 模式的分析相關(guān)分析方法如下： (1) 可視化技術(shù)對(duì)于理解Web用戶的行為模式來講是一個(gè)自然的選擇。(2) 聯(lián)機(jī)分析處理（OLAP）技術(shù)也可以應(yīng)用到模式的分析中來。(3) 計(jì)劃挖掘（plan mining）挖掘通常的存取規(guī)律，可以調(diào)整Web連接，改善性能。第65頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二65相關(guān)分析方法(4) 相關(guān)序列存取模式分析，可以對(duì)服務(wù)器的緩存、預(yù)取和交換參數(shù)進(jìn)行調(diào)整。(5) 趨勢分析，可以了解Web下在發(fā)生的變化，用戶的個(gè)性化分析可以為用戶提供定制的服務(wù)。第66頁，共111頁，2022年，5月20日，13點(diǎn)25分

33、，星期二6615.4.5. 使用記錄挖掘的基本流程 對(duì)Web訪問日志（Web Log）進(jìn)行分析和挖掘要經(jīng)過一系列的數(shù)據(jù)準(zhǔn)備工和和建模工作。一個(gè)基本的流程包括如下步驟。 （1）首先要對(duì)Web Log進(jìn)行清洗、過濾和轉(zhuǎn)換，從中抽取感興趣的數(shù)據(jù)。第67頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二6715.4.5. 使用記錄挖掘的基本流程 （2）將資源的類型、資源的大小、請(qǐng)求的時(shí)間、在資源上停留的時(shí)間、請(qǐng)求次數(shù)、來自不同Internet域的請(qǐng)求次數(shù)、事件、會(huì)話、錯(cuò)誤次數(shù)作為在這些維變量下的度量變量建立數(shù)據(jù)立方體（Data Cube）。 （3）利用成熟的數(shù)據(jù)挖掘技術(shù)（如特征、分類、關(guān)聯(lián)、

34、預(yù)測、時(shí)間序列分析、趨勢分析） 第68頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二6815.5 挖掘數(shù)據(jù)流 為了從數(shù)據(jù)流中發(fā)現(xiàn)知識(shí)或模式，有必要開發(fā)單遍掃描的、聯(lián)機(jī)的、多層的、多維的流處理和分析方法。 單遍掃描的聯(lián)機(jī)數(shù)據(jù)分析方法，不應(yīng)該只限于流數(shù)據(jù)，它對(duì)于處理海量的非數(shù)據(jù)流也是至關(guān)重要的。 第69頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二6915.5.1 流數(shù)據(jù)處理方法和流數(shù)據(jù)系統(tǒng) 本節(jié)，我們考慮一些常用的大綱數(shù)據(jù)結(jié)構(gòu)和技術(shù)。 1隨機(jī)抽樣 一種叫做水庫抽樣，可以用來無放回的選取一個(gè)無偏的S個(gè)元素的隨機(jī)樣本，沒有更換。水庫抽樣的想法相對(duì)簡單。2滑動(dòng)窗口 基本的思

35、想是：僅僅基于最近的數(shù)據(jù)做出決策，而不是對(duì)目前為止看到的所有數(shù)據(jù)或?qū)δ硞€(gè)樣本進(jìn)行計(jì)算。第70頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二7015.5.1 流數(shù)據(jù)處理方法和流數(shù)據(jù)系統(tǒng) 3.直方圖 直方圖是一種大綱的數(shù)據(jù)結(jié)構(gòu)，可以用來近似數(shù)據(jù)流中元素值的頻率分布。4.多分辨方法 處理大量數(shù)據(jù)的一種常見方式是使用數(shù)據(jù)歸約方法。一種流行的數(shù)據(jù)歸約方法是采用分治策略，如多分辨率數(shù)據(jù)結(jié)構(gòu)5.數(shù)據(jù)流管理系統(tǒng)和流查詢 流數(shù)據(jù)的查詢處理結(jié)構(gòu)包括三個(gè)部分：終端用戶，查詢處理器和臨時(shí)空間（這可能由主存和磁盤構(gòu)成）。第71頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二71流OLAP和流數(shù)

36、據(jù)立方體（續(xù)）1壓縮時(shí)間尺度的時(shí)間維：傾斜時(shí)間框架 這種模型對(duì)許多分析任務(wù)來說是足夠的，也能保證駐留在內(nèi)存或存儲(chǔ)在硬盤上的數(shù)據(jù)總量很小。 2.關(guān)鍵層 第一層稱作最小興趣層（minimal interesting layer），是分析人員想要研究的最小興趣層。 第二層稱觀察層（observation layer），是分析人員（或自動(dòng)化系統(tǒng)）希望不斷研究數(shù)據(jù)的層。第72頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二723. 流立方體的部分物化 常用路徑立方體計(jì)算（popular path cubing）,它通過一條常用下鉆路徑，從最小興趣層到觀察層執(zhí)行上卷操作，僅僅物化該路徑中的層次

37、，其它層僅在需要的時(shí)候計(jì)算。這種方法在空間，計(jì)算時(shí)間和靈活性上取得了適度平衡，并具有快速增量聚集時(shí)間，快速下鉆時(shí)間，并且空間需求很小。流OLAP和流數(shù)據(jù)立方體（續(xù)）第73頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二7315.5.3 數(shù)據(jù)流中的頻繁模式挖掘 1.數(shù)據(jù)流頻繁模式挖掘2.數(shù)據(jù)流頻繁模式挖掘算法 數(shù)據(jù)流頻繁模式挖掘的關(guān)鍵問題就是如何快速對(duì)數(shù)據(jù)流中所出現(xiàn)的模式進(jìn)行計(jì)數(shù)。第74頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二74數(shù)據(jù)流所出現(xiàn)的模式數(shù)據(jù)流所出現(xiàn)的模式分成三類: (1) 當(dāng)sup(X)s 時(shí),稱X 為頻繁模式； (2) 當(dāng)sup(X)s 時(shí),稱X 為

38、潛在頻繁模式； (3) 當(dāng)sup(X)s 時(shí),稱X 為非頻繁模式,并在算法中舍棄非頻繁的模式以減少算法的空間復(fù)雜度。第75頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二7515.5.4 動(dòng)態(tài)數(shù)據(jù)流的分類 增量式方法又稱為在線式、連續(xù)式或序列式方法等 ,定義為S t = ( x , y) | y = f ( x ) , t = 1 , 2 , 。 數(shù)據(jù)流挖掘的增量式方法一般都假設(shè)取得的樣本是由平穩(wěn)分布的數(shù)據(jù)中所獲得。 很多研究者提出了解決數(shù)據(jù)流上概念漂移問題的分類技術(shù) 。 第76頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二7615.5.4 動(dòng)態(tài)數(shù)據(jù)流的分類 1.數(shù)據(jù)

39、平穩(wěn)分布的分類方法 VFDT( very fast decision tree) 是一種基于Hoeffding 不等式建立決策樹的方法,它通過不斷地將葉節(jié)點(diǎn)替換為決策節(jié)點(diǎn)而生成。 其中每個(gè)葉節(jié)點(diǎn)都保存有關(guān)于屬性值的統(tǒng)計(jì)信息, 這些統(tǒng)計(jì)信息用于計(jì)算基于屬性值的測試。 第77頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二7715.5.4 動(dòng)態(tài)數(shù)據(jù)流的分類信息增益用于表達(dá)計(jì)算分類到達(dá)該節(jié)點(diǎn)的樣本所需要的信息,其計(jì)算公式為 屬性j 的熵為 ,其中 表示類別k 已知的情況下屬性值取i 的概率。 VFDT 的另一重要性質(zhì)是它所產(chǎn)生的決策樹在大量減少處理樣本數(shù)目的同時(shí),能夠保證和使用全部樣本所

40、產(chǎn)生的決策樹具有無限接近的精度。第78頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二7815.5.4 動(dòng)態(tài)數(shù)據(jù)流的分類2.數(shù)據(jù)帶概念漂移的分類方法下面介紹各種概念漂移學(xué)習(xí)方法。 FLORA 框架 由于FLORA 算法每次只能處理一個(gè)樣本,所以它對(duì)數(shù)據(jù)到達(dá)的速度是有限制的。 第79頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二79 CVFDT 該算法在葉節(jié)點(diǎn)可能會(huì)產(chǎn)生概念漂移時(shí)產(chǎn)生一棵備選子樹,并且在新子樹變得更精確時(shí)用新子樹替代原先的子樹,從而解決了概念漂移所導(dǎo)致的預(yù)測性能下降的問題。 離線C4.5 Harries 和Sammut基于C4.5 開發(fā)了一個(gè)離線學(xué)習(xí)系統(tǒng)

41、,該系統(tǒng)將數(shù)據(jù)流分為一個(gè)關(guān)于時(shí)間的“概念聚類”集合。 第80頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二8015.5.5 聚類演變數(shù)據(jù)流 為了對(duì)數(shù)據(jù)流進(jìn)行有效的聚類，幾個(gè)新的方法已制定，具體情況如下：計(jì)算和存儲(chǔ)過去匯總的數(shù)據(jù)應(yīng)用分治策略增量聚類傳入的數(shù)據(jù)流進(jìn)行微聚類以及宏聚類分析利用多個(gè)時(shí)間粒度為分析集群的演變把流聚類劃分為聯(lián)機(jī)和脫機(jī)處理第81頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二81聚類演變數(shù)據(jù)流 已開發(fā)了幾個(gè)算法為聚類數(shù)據(jù)流的算法。這里介紹其中兩個(gè)，即STREAM和CluStream。 1. STREAM：基于k中位數(shù)的流聚類算法 STREAM是一種單

42、遍掃描，常數(shù)因子的近似算法，是為K -中位數(shù)問題開發(fā)的。 STREAM源于k中位數(shù)聚類，使用有限的時(shí)間和空間。第82頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二8215.5.5 聚類演變數(shù)據(jù)流 2. CluStream：聚類演變的數(shù)據(jù)流 CluStream是一種基于用戶指定的、聯(lián)機(jī)聚類查詢的演變數(shù)據(jù)流聚類算法。 聯(lián)機(jī)微簇的處理分為兩個(gè)階段進(jìn)行： （1）收集統(tǒng)計(jì)數(shù)據(jù) （2）更新微簇 。 第83頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二8315.6 時(shí)間序列數(shù)據(jù)挖掘 趨勢分析 “如何處理時(shí)序數(shù)據(jù)？”目前一般有四種主要的變化成分用于特征化時(shí)序數(shù)據(jù)： 1長期或趨勢變化

43、(trend movement) 2循環(huán)運(yùn)動(dòng)或循環(huán)變化(cyclic movement or cyclic variations) 3季節(jié)性運(yùn)動(dòng)或季節(jié)性變化(seasonal movements or seasonal variations) 4非規(guī)則或隨機(jī)變化（irregular or random movements）第84頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二84時(shí)間序列數(shù)據(jù)挖掘 “怎樣確定數(shù)據(jù)的趨勢?”一個(gè)確定的趨勢的常用方法是用下面的算數(shù)均值序列計(jì)算n階移動(dòng)平均：第85頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二8515.6.2 時(shí)間序列分析中的

44、相似性搜索 “什么是相似搜索（similarity search）？”通常數(shù)據(jù)庫查詢是要找出符合查詢的精確數(shù)據(jù)，相似搜索與之不同，它是找出與給定查詢序列最接近的數(shù)據(jù)序列。 第86頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二8615.6.2 時(shí)間序列分析中的相似性搜索 數(shù)據(jù)變換(data transformation)：從時(shí)間域(time domain)到頻率域(frequency domain)對(duì)時(shí)序數(shù)據(jù)的相似分析，通常采用歐氏距離作為相似計(jì)算的依據(jù)。兩個(gè)常見的獨(dú)立于數(shù)據(jù)的變換是離散傅立葉變換（DFT）和離散小波變（DWT）。第87頁，共111頁，2022年，5月20日，13點(diǎn)

45、25分，星期二8715.6.2 時(shí)間序列分析中的相似性搜索 能夠處理存在間隙和偏移與振幅差異的相似搜索的執(zhí)行步驟如下： 1原子匹配（atomic matching） 2窗口結(jié)合(window stitching) 3子序列排序(subsequence ordering)第88頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二8815.6.2 時(shí)間序列分析中的相似性搜索下圖是子序列S(sequence S)和子序列T(sequence T)的原始序列（Original sequence）、刪除間隙（Removing gap）、偏移變換（offset translation）和振幅變換（

46、Amplitude scaling）的差別。此圖是在時(shí)序數(shù)據(jù)中的子序列匹配：原始序列形狀相同，但需要調(diào)整以處理存在于間隙、偏移和振幅中的差異。這些調(diào)整允許子序列在一定寬度的范圍內(nèi)匹配。 第89頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二89第90頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二9015.7 挖掘事務(wù)數(shù)據(jù)庫中的序列模式 15.7.1 序列模式挖掘：概念和原語 “什么是序列模式挖掘？”序列模式挖掘是指挖掘相對(duì)時(shí)間或其它模式出現(xiàn)頻率高的模式。舉個(gè)例子，順序模式是“顧客在購買佳能數(shù)碼相機(jī)有可能在一個(gè)月以內(nèi)購買HP彩色打印機(jī) ”。 項(xiàng)集是一個(gè)非空的商品名的集合

47、, D 的第三個(gè)屬性便是項(xiàng)集。 第91頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二9115.7 挖掘事務(wù)數(shù)據(jù)庫中的序列模式序列是一個(gè)向量, 這個(gè)向量的每一維均為項(xiàng)集。用( s1，s2，sn) 表示向量, 其中sj 為項(xiàng)集；對(duì)于兩個(gè)向量S1=、S2=, 若存在整數(shù)0i1i2inm+1 使得 , 則稱S1 包含于S2, 記作在一個(gè)序列集中, 若序列S 不包含于任何其它的序列, 我們稱S 是極大的；在D 中, 我們可以將某個(gè)顧客的項(xiàng)集按時(shí)間順序排成一個(gè)序列, 我們稱這個(gè)序列為這個(gè)顧客的顧客序列；第92頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二92若一個(gè)序列包含于某個(gè)

48、顧客的顧客序列中, 則稱此顧客支持此序列； 支持某序列的顧客數(shù)與總顧客數(shù)之比稱為此序列的支持率；當(dāng)一個(gè)序列的支持率不小于一個(gè)給定的值時(shí), 稱這個(gè)序列為頻繁序列；而這個(gè)值稱為最小支持, 記作min_sup；序列所擁有的項(xiàng)集個(gè)數(shù)稱為序列的長度。一個(gè)長度為k 的序列稱為k 序列；設(shè)為1 序列, I 為其中唯一項(xiàng)集。若某客戶支持,則稱此客戶支持項(xiàng)集I； 若為頻繁序列, 則稱I 為頻繁項(xiàng)集。第93頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二9315.7.2 挖掘序列模式的可伸縮方法 對(duì)于序列模式挖掘，如何開發(fā)有效的和可伸縮的方法？最近的研究在這兩方面取得了進(jìn)展：（1）挖掘序列模式完全集的

49、有效方法，（2）僅挖掘序列模式閉集的有效方法 第一類是基于R.Agrawal等人提出的Apriori特性的算法，主要包括AprioriAll算法、GSP算法、SPADE算法等 . 第94頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二94挖掘序列模式的可伸縮方法 AprioriAll算法將序列的長度定義為序列中包含的項(xiàng)集的數(shù)量。該算法將序列模式挖掘過程分為五個(gè)階段。 (1) 排序階段 (2) 頻繁項(xiàng)集階段 (3) 轉(zhuǎn)換階段 (4) 序列階段 (5) 最大序列階段第95頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二9515.7.2 挖掘序列模式的可伸縮方法 第二類是J.

50、Han等人提出的基于模式增長的算法，包括FreeSpan算法、PrefixSpan算法等。PrefixSpan(Prefix-projected equential Pattern Mining)算法和FreeSpan算法都是基于模式增長的挖掘方法。第96頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二9615.7.3 基于約束的序列模式挖掘 約束可以用多種形式表示。可能是屬性，屬性質(zhì)之間的聯(lián)系或者結(jié)果模式中的聚集。 第一個(gè)約束是時(shí)間序列的持續(xù)時(shí)間（duration）T。 第二個(gè)約束是事件重疊窗口（event folding window），w。 第三個(gè)約束是被發(fā)現(xiàn)的模式中時(shí)間之間

51、的時(shí)間間隔（interval）int。 第97頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二9715.7.4 時(shí)間相關(guān)序列數(shù)據(jù)的周期性分析 “什么是周期分析？”周期分析（periodicity analysis）是指對(duì)周期模式的挖掘，即在時(shí)序數(shù)據(jù)庫中找出重復(fù)出現(xiàn)的模式。 第98頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二98 周期模式挖掘可以從不同的角度觀察，基于模式覆蓋，可以把模式周期分為三類： 挖掘全周期模式（full periodic pattern） 挖掘部分周期模式(partial periodic pattern) 挖掘循環(huán)或周期關(guān)聯(lián)規(guī)則(cyclic or periodic association rule)第99頁，共111頁，2022年，5月20日，13點(diǎn)25分，星期二9915.8 挖掘生物學(xué)數(shù)據(jù)中的序列模式