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

復(fù)雜對(duì)象數(shù)據(jù)挖掘1第1頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月第15章復(fù)雜對(duì)象數(shù)據(jù)挖掘

2第2頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1空間數(shù)據(jù)庫(kù)挖掘

15.2多媒體數(shù)據(jù)挖掘

15.3文本挖掘15.4挖掘萬(wàn)維網(wǎng)15.5挖掘數(shù)據(jù)流15.6時(shí)間序列數(shù)據(jù)挖掘15.7挖掘事務(wù)數(shù)據(jù)庫(kù)中的序列模式15.8挖掘生物學(xué)數(shù)據(jù)中的序列模式3第3頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1空間數(shù)據(jù)庫(kù)挖掘

空間數(shù)據(jù)庫(kù)挖掘（SDM）實(shí)質(zhì)上是空間信息技術(shù)發(fā)展的必然結(jié)果，它是數(shù)據(jù)庫(kù)挖掘（DM）的一個(gè)重要分支，面對(duì)的都是空間數(shù)據(jù)庫(kù)（spatialdatabase,SDB）。空間實(shí)體之間又具有空間拓?fù)?、空間距離、空間方位這3種關(guān)系

4第4頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1.1空間數(shù)據(jù)概述空間數(shù)據(jù)是指與二維、三維或更高維空間的空間坐標(biāo)及空間范圍相關(guān)的數(shù)據(jù)空間數(shù)據(jù)的復(fù)雜性特征有：

空間屬性之間的非線(xiàn)性關(guān)系空間數(shù)據(jù)的多尺度特征空間信息的模糊性空間維數(shù)的增高空間數(shù)據(jù)的缺值5第5頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

空間查詢(xún)工作

空間查詢(xún)及其操作的主要特點(diǎn)有：空間操作相對(duì)復(fù)雜和不精確空間連接（SpatialJoin）問(wèn)題相同的地理區(qū)域經(jīng)常有不同的視圖一個(gè)空間實(shí)體可用空間和非空間的屬性來(lái)描述6第6頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月很多基本空間查詢(xún)是數(shù)據(jù)挖掘行為的基礎(chǔ)，這些查詢(xún)包括：區(qū)域查詢(xún)或范圍查詢(xún)：尋找那些與在查詢(xún)中指定區(qū)域相交的實(shí)體。最鄰近查詢(xún)：尋找與指定實(shí)體相鄰的實(shí)體距離掃描：尋找與指定的實(shí)體相距一段確定距離的實(shí)體，這個(gè)距離是逐漸增大的。小提示：所有這些查詢(xún)都可以用來(lái)輔助空間聚類(lèi)或分類(lèi)操作。

空間查詢(xún)工作

7第7頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型

空間關(guān)系計(jì)算

(1)常用的兩個(gè)空間實(shí)體之間的距離有：最小值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)之間的歐氏或曼哈頓距離中最小的，即（15-1）8第8頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月大值方法：定義實(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第9頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月中心方法：定義實(shí)體A和B的距離為A中的中心點(diǎn)與和B中的中心點(diǎn)之間的歐氏或曼哈頓距離的平均值，即(15-4)

其中最簡(jiǎn)單的方法就是取實(shí)體A的中心點(diǎn)和B的中心點(diǎn)，該中心點(diǎn)可以通過(guò)查找實(shí)體的幾何中心來(lái)識(shí)別。

空間關(guān)系計(jì)算10第10頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.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第11頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月包含于：A包含于B，表示A的所有點(diǎn)都在B里，反之不一定。覆蓋/包含：A覆蓋或包含B，當(dāng)且僅當(dāng)B包含于A。(3)方位是描述兩個(gè)點(diǎn)狀實(shí)體位置關(guān)系的一種度量，如果要分析面狀實(shí)體間的方位關(guān)系，則應(yīng)把多邊形轉(zhuǎn)換為重心點(diǎn)或其它點(diǎn)狀實(shí)體。15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型12第12頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月空間實(shí)體信息模型

空間場(chǎng)模型空間場(chǎng)模型主要用于模擬在空間上連續(xù)分布的地理現(xiàn)象，屬性取值既可以式連續(xù)的，也可以是離散的。空間場(chǎng)數(shù)據(jù)模型的優(yōu)點(diǎn)是數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，便于空間法分析與模擬。缺點(diǎn)是不利于表達(dá)空間實(shí)體，數(shù)據(jù)量也大。13第13頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型空間要素模型圖15-3基于要素的空間信息模型對(duì)現(xiàn)實(shí)世界的抽象現(xiàn)實(shí)世界專(zhuān)題要素1實(shí)體1專(zhuān)題要素2專(zhuān)題要素n實(shí)體2實(shí)體n時(shí)間特征屬性特征空間關(guān)系特征幾何特征14第14頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型小提示：實(shí)體必須符合三個(gè)條件：①可被識(shí)別，②重要（與問(wèn)題相關(guān)），③可被描述（有特征）。表15-2現(xiàn)實(shí)世界與信息世界的對(duì)應(yīng)關(guān)系

15第15頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1.2空間數(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ò)的抽象ACDB16第16頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型位置—屬性一體化的空間實(shí)體信息模型一般空間實(shí)體的形式化模型為一個(gè)四元組，分別代表空間實(shí)體四個(gè)方面的特征。其中位置特征數(shù)據(jù)為

…（15-11）

17第17頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1.3空間數(shù)據(jù)挖掘基礎(chǔ)

空間數(shù)據(jù)挖掘（SDM）是指對(duì)空間數(shù)據(jù)庫(kù)中非明確存在的知識(shí)，空間關(guān)系，或其它有意義的模式等的提取。

空間數(shù)據(jù)挖掘的框架體系

一般認(rèn)為可以大致分為三層結(jié)構(gòu)，如圖15-5空間數(shù)據(jù)挖掘的體系結(jié)構(gòu)所示。其中，第一層是數(shù)據(jù)源；第二層是挖掘器；第三層是用戶(hù)界面。18第18頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月圖15-5空間數(shù)據(jù)挖掘的體系結(jié)構(gòu)19第19頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

空間數(shù)據(jù)挖掘的方法體系空間評(píng)價(jià)。空間分類(lèi)與聚類(lèi)?？臻g分布計(jì)算?？臻g優(yōu)化?？臻g回歸分析?？臻g動(dòng)態(tài)模擬與預(yù)測(cè)?？臻g與時(shí)序關(guān)聯(lián)知識(shí)歸納。20第20頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.1.4幾種空間數(shù)據(jù)挖掘算法

空間關(guān)聯(lián)分析

空間關(guān)聯(lián)規(guī)則挖掘是傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘的延伸，常用最小支持度和最小可信度來(lái)作為基本的統(tǒng)計(jì)參數(shù)，由于空間數(shù)據(jù)的特點(diǎn)，往往是在多層概念上進(jìn)行歸納。21第21頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月挖掘空間關(guān)聯(lián)規(guī)則的有效方法是自上而下、逐步加深的搜索技術(shù)。首先在高的概念層次進(jìn)行搜索，在較粗的精度級(jí)別查找頻繁發(fā)生的模式和在這些模式中較強(qiáng)的隱含關(guān)系；然后，對(duì)頻繁發(fā)生的模式加深搜索至較低的概念層次，這種處理持續(xù)到找不到頻繁發(fā)生的模式為止?？臻g關(guān)聯(lián)分析22第22頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月空間關(guān)聯(lián)分析典型的五步算法：Step1：通過(guò)給定的查詢(xún)抽取出相關(guān)的數(shù)據(jù)。Step2：應(yīng)用一個(gè)粗的空間運(yùn)算方法，計(jì)算整個(gè)相關(guān)數(shù)據(jù)的集合。Step3：過(guò)濾出那些支持度小于最小支持度閾值的1階謂詞。Step4：應(yīng)用一個(gè)細(xì)化的空間計(jì)算方法，從所導(dǎo)出的粗的謂詞集合中計(jì)算謂詞。Step5：向低層深入，在多個(gè)概念層次上找到關(guān)聯(lián)規(guī)則的完整集合。23第23頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月空間分類(lèi)算法和空間趨勢(shì)分析空間分類(lèi)指分析空間對(duì)象導(dǎo)出與一定空間特征有關(guān)的分類(lèi)模式小提示：空間因素可以是非空間屬性和空間屬性，也可以是二者同時(shí)使用。

(1)對(duì)于樣本數(shù)據(jù)的訓(xùn)練可以通過(guò)改造傳統(tǒng)的分類(lèi)算法來(lái)完成(2)空間決策樹(shù)空間分類(lèi)技術(shù)建構(gòu)決策樹(shù)采用兩步方法。這個(gè)方法的思想基礎(chǔ)是空間實(shí)體可以與其接近的實(shí)體來(lái)描述。假設(shè)類(lèi)的描述是基于與實(shí)體相近最相關(guān)的謂詞的集合。建造一個(gè)決策樹(shù)24第24頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月空間決策樹(shù)有五個(gè)主要步驟：根據(jù)已知的分類(lèi)，從數(shù)據(jù)D中找到例子S。確定最佳謂詞p用來(lái)分類(lèi)。一般首先在較粗的層次中尋找相關(guān)謂詞，然后再在較為細(xì)化的層次?？臻g決策樹(shù)25第25頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月找到最佳的緩沖區(qū)大小和形狀。對(duì)于取樣中的每個(gè)實(shí)體，它周?chē)膮^(qū)域被稱(chēng)為緩沖區(qū)。目標(biāo)是選擇一個(gè)能產(chǎn)生對(duì)測(cè)試集中的類(lèi)型進(jìn)行最不同的緩沖區(qū)。使用p和C，對(duì)每個(gè)緩沖區(qū)歸納謂詞。使用泛化的謂詞和ID3建造二叉樹(shù)T。26第26頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

空間聚類(lèi)方法

空間聚類(lèi)分析是空間模式識(shí)別和空間數(shù)據(jù)挖掘的重要手段之一。它的目的是要在一個(gè)較大的多維數(shù)據(jù)集中根據(jù)距離的計(jì)算找出簇，或稠密區(qū)域。小提示：空間聚類(lèi)找到的聚類(lèi)不應(yīng)該依賴(lài)于檢驗(yàn)空間中的點(diǎn)的順序，而且聚類(lèi)也不應(yīng)該受不相干的點(diǎn)影響。本節(jié)介紹的空間聚類(lèi)方法是基于坐標(biāo)—屬性一體化的空間信息模型，27第27頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

空間聚類(lèi)方法從兩類(lèi)直至每個(gè)樣本為一類(lèi)的系統(tǒng)聚類(lèi)算法步驟如下：對(duì)地理特征向量中的每一個(gè)元素進(jìn)行無(wú)量綱化。令類(lèi)別數(shù)k=2，置迭代誤差閾值emin=0.100001(可根據(jù)需要設(shè)置)。置迭代次數(shù)t=0，k個(gè)初始聚類(lèi)中心為：對(duì)第t次迭代,若有則把樣本Si分配到第j0個(gè)聚類(lèi)域。如此，所有的m個(gè)樣本可以被劃分到k個(gè)聚類(lèi)域中.28第28頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月計(jì)算新的聚類(lèi)中心式中Nj為第j個(gè)聚類(lèi)域中包含的樣本個(gè)數(shù)。若則停止迭代，第t次迭代結(jié)果為劃分為k個(gè)類(lèi)別的聚類(lèi)方案，轉(zhuǎn)向(7)；否則,t=t+1，轉(zhuǎn)向(4)。當(dāng)k<m時(shí)，k=k+1，轉(zhuǎn)向(3)；否則，系統(tǒng)聚類(lèi)結(jié)束。聚類(lèi)算法步驟(續(xù)）29第29頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.2多媒體數(shù)據(jù)挖掘15.2.1多媒體數(shù)據(jù)挖掘的特點(diǎn)多媒體數(shù)據(jù)復(fù)雜。多媒體信息語(yǔ)義關(guān)聯(lián)性強(qiáng)。多媒體信息具有時(shí)空相關(guān)性。知識(shí)的表達(dá)和解釋比較困難，多媒體挖掘所得出的模式往往比較隱晦。30第30頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.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ù)庫(kù)多媒體數(shù)據(jù)集知識(shí)庫(kù)挖掘引擎數(shù)據(jù)立方體媒體屬性特征數(shù)據(jù)預(yù)處理用戶(hù)挖掘接口31第31頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

多媒體數(shù)據(jù)挖掘的內(nèi)容關(guān)于多媒體數(shù)據(jù)挖掘的內(nèi)容一般包括圖像數(shù)據(jù)挖掘、音頻數(shù)據(jù)挖掘、視頻數(shù)據(jù)挖掘等。

圖像挖掘

圖像包含著豐富的視覺(jué)特性和空間特性。視頻挖掘視頻包括豐富的內(nèi)容特性，除了圖像具有的視覺(jué)特性和空間特性外,還具有時(shí)間特性、視頻對(duì)象特性和運(yùn)動(dòng)特性等。

32第32頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月多媒體數(shù)據(jù)挖掘的內(nèi)容音頻挖掘音頻挖掘通常有兩種途徑:①運(yùn)用語(yǔ)音識(shí)別技術(shù)將語(yǔ)音識(shí)別成文字，將音頻挖掘轉(zhuǎn)換成文本挖掘；②直接從音頻中提取聲音特征，如音調(diào)、韻律等,運(yùn)用聚類(lèi)的方法分析聲音模式。Web挖掘多媒體綜合挖掘多媒體概念與單媒體的區(qū)別在于，它是一個(gè)集成的系統(tǒng)概念，媒體之間有聯(lián)系。33第33頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.2.3多媒體數(shù)據(jù)挖掘方法

在圖像和視頻數(shù)據(jù)庫(kù)中可以挖掘涉及多媒體對(duì)象的關(guān)聯(lián)規(guī)則，至少包含以下三類(lèi)：圖像內(nèi)容和非圖像內(nèi)容特征間的關(guān)聯(lián)與空間關(guān)系無(wú)關(guān)的圖像內(nèi)容的關(guān)聯(lián)與空間關(guān)系有關(guān)的圖像內(nèi)容的關(guān)聯(lián)34第34頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

多媒體數(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第35頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月兩種查詢(xún)?cè)诨趦?nèi)容的檢索系統(tǒng)中,通常有兩種查詢(xún)：基于圖像樣本的查詢(xún)（imagesample-basedqueries）。圖像樣本查詢(xún)是指找出所有與給定圖像樣本相似的圖像。圖像特征描述查詢(xún)(imagefeaturespecificationqueries)。圖像特征描述查詢(xún)是指給出圖像的特征描述或概括36第36頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

多媒體數(shù)據(jù)的相似搜索

到目前為止人們已經(jīng)提出了幾種在圖像數(shù)據(jù)庫(kù)中基于圖像特征標(biāo)識(shí)的相似檢索方法：基于顏色直方圖的特征標(biāo)識(shí)多特征構(gòu)成的特征標(biāo)識(shí)基于小波的特征標(biāo)識(shí)帶有區(qū)域粒度的小波特征標(biāo)識(shí)37第37頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

多媒體數(shù)據(jù)的分類(lèi)和預(yù)測(cè)分析我們也可以對(duì)多媒體數(shù)據(jù)進(jìn)行分類(lèi)和預(yù)測(cè)分析，尤其用在如天文學(xué)、地震學(xué)、地理科學(xué)等的研究中。分類(lèi)是多媒體數(shù)據(jù)的一種分析形式,它根據(jù)媒體某一特征(或一組特征)將數(shù)據(jù)分成不同的類(lèi)。它是一個(gè)兩步過(guò)程：第1步，建立一個(gè)模型，用來(lái)描述預(yù)定義類(lèi)集。第2步，使用模型進(jìn)行分類(lèi)。38第38頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.3文本挖掘15.3.1文本挖掘概述數(shù)據(jù)庫(kù)挖掘處理的對(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)行聚類(lèi)及分類(lèi)處理，或者是構(gòu)造數(shù)據(jù)的預(yù)測(cè)模型。

39第39頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月文本挖掘的一般過(guò)程文本挖掘的一般過(guò)程文本挖掘過(guò)程一般包括文本準(zhǔn)備、特征標(biāo)引、特征集縮減、知識(shí)模式的提取、知識(shí)模式的評(píng)價(jià)、知識(shí)模式的輸出等過(guò)程

.文本特征標(biāo)引特征集縮減知識(shí)模型的提取知識(shí)模型的評(píng)價(jià)知識(shí)模型的輸出40第40頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

文本挖掘的主要任務(wù)文本挖掘的主要目標(biāo)是獲得文本的主要內(nèi)容特征

特征提取主題標(biāo)引文本分類(lèi)文本聚類(lèi)自動(dòng)摘要41第41頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

文本挖掘與信息檢索文本的預(yù)處理目前，人們?cè)趯?duì)文本集進(jìn)行自動(dòng)分類(lèi)、自動(dòng)聚類(lèi)、自動(dòng)摘要或更深層次的挖掘處理時(shí)常常采用這樣的策略:先用一個(gè)高度概括的向量來(lái)表示一篇文本，將文本集概括成一個(gè)向量集，這個(gè)向量集等同于一個(gè)二維表格，然后通過(guò)對(duì)文本集對(duì)應(yīng)的向量集進(jìn)行相關(guān)的分析，達(dá)到對(duì)文本集進(jìn)行自動(dòng)分類(lèi)、自動(dòng)聚類(lèi)、自動(dòng)產(chǎn)生文摘或自動(dòng)挖掘出更深層的隱含知識(shí)的目的。42第42頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月文本的表示

文本表示是指用文本的特征信息集合來(lái)代表原來(lái)的文本.向量空間模型的基本思想是以向量來(lái)表示文本，其中為第i個(gè)特征項(xiàng)的權(quán)重。相對(duì)詞頻的計(jì)算方法主要運(yùn)用TF-IDF公式。公式如下：

…（15-15）43第43頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

文本特征標(biāo)引

所謂標(biāo)引，是指給出信息內(nèi)容特征的過(guò)程。漢語(yǔ)自動(dòng)分詞方法有多種，主要有詞典法、切分標(biāo)記法等。1．詞典分詞法2.切分標(biāo)記分詞法

小提示：切分標(biāo)記法的典型代表是非用詞后綴表法。該法將漢字分為“非用字”、“條件用字”、“表內(nèi)用字”、“表外用字”。主要利用“非用字”和“條件用字”進(jìn)行詞語(yǔ)的切分。44第44頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

文本維度規(guī)約1．基于評(píng)估函數(shù)的方法基于評(píng)估函數(shù)的特征集縮減算法使用特征獨(dú)立性假設(shè)以簡(jiǎn)化特征選擇。2．潛在語(yǔ)義標(biāo)引潛在語(yǔ)義標(biāo)引法利用矩陣?yán)碚撝械摹捌娈愔捣纸狻奔夹g(shù)，將詞頻矩陣轉(zhuǎn)化為維數(shù)大大減小的奇異矩陣。

45第45頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

文本的自動(dòng)分類(lèi)

文本自動(dòng)分類(lèi)的一般過(guò)程如下：首先，取一個(gè)預(yù)分類(lèi)的文本集作為訓(xùn)練集。然后，分析訓(xùn)練集以導(dǎo)出分類(lèi)模型。通常，需要用一個(gè)檢驗(yàn)過(guò)程對(duì)該分類(lèi)模型求精。所導(dǎo)出的分類(lèi)模型可以用于其它聯(lián)機(jī)文本分類(lèi)。46第46頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月文本分類(lèi)的典型的分類(lèi)方法

下面介紹幾種已經(jīng)成功應(yīng)用于文本分類(lèi)的典型的分類(lèi)方法。1．簡(jiǎn)單向量距離分類(lèi)具體步驟如下:(1).根據(jù)訓(xùn)練集文本向量空間模型計(jì)算每類(lèi)文本集的中心向量；(2).將新文本表示為特征向量；(3).計(jì)算新文本特征向量和每類(lèi)中心向量間的相似度；(4).比較每類(lèi)中心向量與新文本的相似度，將文本分到相似度最大的那個(gè)類(lèi)別中。47第47頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月文本分類(lèi)的典型的分類(lèi)方法（續(xù)）2．簡(jiǎn)單貝葉斯分類(lèi)算法算法具體步驟如下：計(jì)算特征詞屬于每個(gè)類(lèi)別的概率向量。對(duì)于新文本di，計(jì)算該文本屬于類(lèi)Cj的概率。比較新文本屬于所有類(lèi)的概率，將文本分到概率最大的那個(gè)類(lèi)別中。48第48頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月文本分類(lèi)的典型的分類(lèi)方法（續(xù)）

3．K最近鄰居（KNN）算法

該算法的基本思路是:在給定新文本后，考慮在訓(xùn)練文本集中與該新文本距離最近(最相似)的K篇文本，根據(jù)這幾篇文本所屬的類(lèi)別判定新文本所屬的類(lèi)別，該算法具體的步驟如下:49第49頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月K最近鄰居（KNN）算法(1).根據(jù)特征項(xiàng)集合重新描述訓(xùn)練文本向量；(2).將新文本表示為特征向量；(3).比較類(lèi)的權(quán)重，將文本分到權(quán)重最大的那個(gè)類(lèi)別中

(4).在訓(xùn)練文本集中選出與新文本最相似的K個(gè)文本，計(jì)算公式為：

….(15-16)50第50頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月(5).在新文本的K個(gè)鄰居中，依次計(jì)算每類(lèi)的權(quán)重，計(jì)算公式：…..(15-17)其中，為新文本的特征向量，為相似度計(jì)算公式，為類(lèi)別屬性函數(shù)，即如果屬于類(lèi)，那么函數(shù)值為1，否則為0。K最近鄰居（KNN）算法51第51頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

文本聚類(lèi)1．光譜聚類(lèi)方法首先，對(duì)原始數(shù)據(jù)進(jìn)行光譜嵌入（維度歸約），然后對(duì)維度歸約后的文本空間運(yùn)用傳統(tǒng)的聚類(lèi)算法（如k均值）。52第52頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月文本聚類(lèi)(續(xù))2．混合模型聚類(lèi)方法用混合模型對(duì)文本數(shù)據(jù)聚類(lèi)包括兩個(gè)步驟：(1)基于文本數(shù)據(jù)和附加的先驗(yàn)知識(shí)估計(jì)模型參數(shù)；(2)基于估計(jì)的模型參數(shù)推斷聚類(lèi)。53第53頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

基于遺傳算法（GA）的文本聚類(lèi)

遺傳算法(GA)為文本聚類(lèi)提供了一種非層次的聚類(lèi)方法，其核心思想是使簇內(nèi)文本間的相似度最大化。

54第54頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.4挖掘互聯(lián)網(wǎng)

15.4.1挖掘Web頁(yè)面布局結(jié)構(gòu)

Web結(jié)構(gòu)挖掘?qū)儆谛畔⒔Y(jié)構(gòu)（IA）方面的研究?jī)?nèi)容。對(duì)于一個(gè)站點(diǎn)而言，按結(jié)構(gòu)層次高低可以分出三種結(jié)構(gòu)：站點(diǎn)結(jié)構(gòu)、頁(yè)面（框架）結(jié)構(gòu)、頁(yè)內(nèi)結(jié)構(gòu)。55第55頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面

rank方法

大量的Web鏈接信息提供了豐富的關(guān)于Web內(nèi)容相關(guān)性、質(zhì)量和結(jié)構(gòu)方面的信息，這對(duì)Web挖掘是可以利用的一個(gè)重要資源。56第56頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面

基于以上考慮，人們提出了如下的概念：

Web可以用一個(gè)有向圖來(lái)表示，G=（V，E），V是頁(yè)面的集合，E是頁(yè)面之間的超鏈接集合。頁(yè)面抽象為圖中的頂點(diǎn)，而頁(yè)面之間的超鏈接抽象為圖中的有向邊。頂點(diǎn)V的入邊表示對(duì)V的引用，出邊表示V引用了其他的頁(yè)面。所以Web頁(yè)面之間的超鏈接揭示了Web結(jié)構(gòu)。57第57頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面

鏈接文本（AnchorTexts）可以用來(lái)對(duì)被引用的頁(yè)面進(jìn)行索引（例如：Webor,WWW，Google）。超鏈接可以用來(lái)計(jì)算頁(yè)面的rankingscore,通過(guò)超鏈接可以將一個(gè)頁(yè)面的rankingcore傳遞到相鄰的頁(yè)面。58第58頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面

rank的基本思想如下：頁(yè)面被多次引用，則這個(gè)頁(yè)面很可能是重要的。一個(gè)頁(yè)面盡管沒(méi)有被多次引用，但被一個(gè)重要頁(yè)面引用，則這個(gè)頁(yè)面很可能是重要的。一個(gè)頁(yè)面的重要性被均分并被傳遞到它所引用的頁(yè)面。59第59頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面Hub/authority方法挖掘Web上的多媒體數(shù)據(jù)

關(guān)于多媒體的數(shù)據(jù)挖掘一般包括圖像數(shù)據(jù)挖掘、音頻數(shù)據(jù)挖掘、視頻數(shù)據(jù)挖掘等。60第60頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面圖像挖掘圖像挖掘（ImageMining）指對(duì)圖形圖像數(shù)據(jù)信息的自動(dòng)處理和知識(shí)發(fā)現(xiàn)，包含模式識(shí)別、圖像檢索以及特征分析等。圖像的空間特性是非常重要的特性，包括圖像中各種對(duì)像的模式、布局、空間層次等。61第61頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

音頻挖掘音頻挖掘（AudioMining）指對(duì)音頻信息的自動(dòng)處理和分析過(guò)程。語(yǔ)音挖掘的另外一個(gè)用途在于將語(yǔ)音對(duì)應(yīng)到個(gè)人62第62頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

音頻挖掘

視頻挖掘15.4.4Web文檔的自動(dòng)分類(lèi)15.4.5Web使用挖掘

63第63頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

音頻挖掘15.4.5.1模式發(fā)現(xiàn)

要解決的問(wèn)題就是數(shù)據(jù)的預(yù)處理，它主要包括兩個(gè)部分：（1）數(shù)據(jù)清洗（DataCleaning）:包括無(wú)關(guān)記錄的剔除、判斷是否有重要的訪(fǎng)問(wèn)沒(méi)有被記錄、用戶(hù)的識(shí)別等問(wèn)題。（2）事務(wù)識(shí)別（TransactionIdentification）:是指將頁(yè)面訪(fǎng)問(wèn)序列劃分為代表Web事務(wù)或用戶(hù)會(huì)話(huà)的邏輯單元。如路徑分析、關(guān)聯(lián)規(guī)則挖掘、時(shí)序模式以及聚類(lèi)和分類(lèi)技術(shù)。64第64頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.4.5.２模式的分析相關(guān)分析方法如下：(1)可視化技術(shù)對(duì)于理解Web用戶(hù)的行為模式來(lái)講是一個(gè)自然的選擇。(2)聯(lián)機(jī)分析處理（OLAP）技術(shù)也可以應(yīng)用到模式的分析中來(lái)。(3)計(jì)劃挖掘（planmining）挖掘通常的存取規(guī)律，可以調(diào)整Web連接，改善性能。65第65頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月相關(guān)分析方法(4)相關(guān)／序列存取模式分析，可以對(duì)服務(wù)器的緩存、預(yù)取和交換參數(shù)進(jìn)行調(diào)整。(5)趨勢(shì)分析，可以了解Web下在發(fā)生的變化，用戶(hù)的個(gè)性化分析可以為用戶(hù)提供定制的服務(wù)。66第66頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.4.5.３使用記錄挖掘的基本流程

對(duì)Web訪(fǎng)問(wèn)日志（WebLog）進(jìn)行分析和挖掘要經(jīng)過(guò)一系列的數(shù)據(jù)準(zhǔn)備工和和建模工作。一個(gè)基本的流程包括如下步驟。（1）首先要對(duì)WebLog進(jìn)行清洗、過(guò)濾和轉(zhuǎn)換，從中抽取感興趣的數(shù)據(jù)。67第67頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.4.5.３使用記錄挖掘的基本流程

（2）將資源的類(lèi)型、資源的大小、請(qǐng)求的時(shí)間、在資源上停留的時(shí)間、請(qǐng)求次數(shù)、來(lái)自不同Internet域的請(qǐng)求次數(shù)、事件、會(huì)話(huà)、錯(cuò)誤次數(shù)作為在這些維變量下的度量變量建立數(shù)據(jù)立方體（DataCube）。（3）利用成熟的數(shù)據(jù)挖掘技術(shù)（如特征、分類(lèi)、關(guān)聯(lián)、預(yù)測(cè)、時(shí)間序列分析、趨勢(shì)分析）68第68頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5挖掘數(shù)據(jù)流

為了從數(shù)據(jù)流中發(fā)現(xiàn)知識(shí)或模式，有必要開(kāi)發(fā)單遍掃描的、聯(lián)機(jī)的、多層的、多維的流處理和分析方法。單遍掃描的聯(lián)機(jī)數(shù)據(jù)分析方法，不應(yīng)該只限于流數(shù)據(jù)，它對(duì)于處理海量的非數(shù)據(jù)流也是至關(guān)重要的。69第69頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5.1流數(shù)據(jù)處理方法和流數(shù)據(jù)系統(tǒng)

本節(jié)，我們考慮一些常用的大綱數(shù)據(jù)結(jié)構(gòu)和技術(shù)。1．隨機(jī)抽樣一種叫做水庫(kù)抽樣，可以用來(lái)無(wú)放回的選取一個(gè)無(wú)偏的S個(gè)元素的隨機(jī)樣本，沒(méi)有更換。水庫(kù)抽樣的想法相對(duì)簡(jiǎn)單。2．滑動(dòng)窗口基本的思想是：僅僅基于最近的數(shù)據(jù)做出決策，而不是對(duì)目前為止看到的所有數(shù)據(jù)或?qū)δ硞€(gè)樣本進(jìn)行計(jì)算。70第70頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5.1流數(shù)據(jù)處理方法和流數(shù)據(jù)系統(tǒng)

3.直方圖直方圖是一種大綱的數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)近似數(shù)據(jù)流中元素值的頻率分布。4.多分辨方法處理大量數(shù)據(jù)的一種常見(jiàn)方式是使用數(shù)據(jù)歸約

方法。一種流行的數(shù)據(jù)歸約方法是采用分治策略，如多分辨率數(shù)據(jù)結(jié)構(gòu)5.數(shù)據(jù)流管理系統(tǒng)和流查詢(xún)流數(shù)據(jù)的查詢(xún)處理結(jié)構(gòu)包括三個(gè)部分：終端用戶(hù)，查詢(xún)處理器和臨時(shí)空間（這可能由主存和磁盤(pán)構(gòu)成）。71第71頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月流OLAP和流數(shù)據(jù)立方體（續(xù)）1．壓縮時(shí)間尺度的時(shí)間維：傾斜時(shí)間框架

這種模型對(duì)許多分析任務(wù)來(lái)說(shuō)是足夠的，也能保證駐留在內(nèi)存或存儲(chǔ)在硬盤(pán)上的數(shù)據(jù)總量很小。2.關(guān)鍵層

第一層稱(chēng)作最小興趣層（minimalinterestinglayer），是分析人員想要研究的最小興趣層。

第二層稱(chēng)觀察層（observationlayer），是分析人員（或自動(dòng)化系統(tǒng)）希望不斷研究數(shù)據(jù)的層。72第72頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月3.流立方體的部分物化常用路徑立方體計(jì)算（popularpathcubing）,它通過(guò)一條常用下鉆路徑，從最小興趣層到觀察層執(zhí)行上卷操作，僅僅物化該路徑中的層次，其它層僅在需要的時(shí)候計(jì)算。這種方法在空間，計(jì)算時(shí)間和靈活性上取得了適度平衡，并具有快速增量聚集時(shí)間，快速下鉆時(shí)間，并且空間需求很小。流OLAP和流數(shù)據(jù)立方體（續(xù)）73第73頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5.3數(shù)據(jù)流中的頻繁模式挖掘

1.數(shù)據(jù)流頻繁模式挖掘2.數(shù)據(jù)流頻繁模式挖掘算法數(shù)據(jù)流頻繁模式挖掘的關(guān)鍵問(wèn)題就是如何快速對(duì)數(shù)據(jù)流中所出現(xiàn)的模式進(jìn)行計(jì)數(shù)。74第74頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月數(shù)據(jù)流所出現(xiàn)的模式數(shù)據(jù)流所出現(xiàn)的模式分成三類(lèi):

(1)當(dāng)sup(X)≥s時(shí),稱(chēng)X為頻繁模式；

(2)當(dāng)ε≤sup(X)<s時(shí),稱(chēng)X為潛在頻繁模式；

(3)當(dāng)sup(X)<s時(shí),稱(chēng)X為非頻繁模式,并在算法中舍棄非頻繁的模式以減少算法的空間復(fù)雜度。75第75頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類(lèi)

增量式方法又稱(chēng)為在線(xiàn)式、連續(xù)式或序列式方法等

,定義為St={(x,y)|y=f(x)},t=1,2,?,∞。數(shù)據(jù)流挖掘的增量式方法一般都假設(shè)取得的樣本是由平穩(wěn)分布的數(shù)據(jù)中所獲得。很多研究者提出了解決數(shù)據(jù)流上概念漂移問(wèn)題的分類(lèi)技術(shù)。

76第76頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類(lèi)

1.數(shù)據(jù)平穩(wěn)分布的分類(lèi)方法

VFDT(veryfastdecisiontree)是一種基于Hoeffding不等式建立決策樹(shù)的方法,它通過(guò)不斷地將葉節(jié)點(diǎn)替換為決策節(jié)點(diǎn)而生成。其中每個(gè)葉節(jié)點(diǎn)都保存有關(guān)于屬性值的統(tǒng)計(jì)信息,這些統(tǒng)計(jì)信息用于計(jì)算基于屬性值的測(cè)試。

77第77頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類(lèi)信息增益用于表達(dá)計(jì)算分類(lèi)到達(dá)該節(jié)點(diǎn)的樣本所需要的信息,其計(jì)算公式為屬性j的熵為,其中

表示類(lèi)別k已知的情況下屬性值取i的概率。

VFDT的另一重要性質(zhì)是它所產(chǎn)生的決策樹(shù)在大量減少處理樣本數(shù)目的同時(shí),能夠保證和使用全部樣本所產(chǎn)生的決策樹(shù)具有無(wú)限接近的精度。78第78頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類(lèi)2.數(shù)據(jù)帶概念漂移的分類(lèi)方法下面介紹各種概念漂移學(xué)習(xí)方法。①FLORA框架

由于FLORA算法每次只能處理一個(gè)樣本,所以它對(duì)數(shù)據(jù)到達(dá)的速度是有限制的。

79第79頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月②CVFDT

該算法在葉節(jié)點(diǎn)可能會(huì)產(chǎn)生概念漂移時(shí)產(chǎn)生一棵備選子樹(shù),并且在新子樹(shù)變得更精確時(shí)用新子樹(shù)替代原先的子樹(shù),從而解決了概念漂移所導(dǎo)致的預(yù)測(cè)性能下降的問(wèn)題。③離線(xiàn)C4.5

Harries和Sammut基于C4.5開(kāi)發(fā)了一個(gè)離線(xiàn)學(xué)習(xí)系統(tǒng),該系統(tǒng)將數(shù)據(jù)流分為一個(gè)關(guān)于時(shí)間的“概念聚類(lèi)”集合。80第80頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5.5聚類(lèi)演變數(shù)據(jù)流

為了對(duì)數(shù)據(jù)流進(jìn)行有效的聚類(lèi)，幾個(gè)新的方法已制定，具體情況如下：計(jì)算和存儲(chǔ)過(guò)去匯總的數(shù)據(jù)應(yīng)用分治策略增量聚類(lèi)傳入的數(shù)據(jù)流進(jìn)行微聚類(lèi)以及宏聚類(lèi)分析利用多個(gè)時(shí)間粒度為分析集群的演變把流聚類(lèi)劃分為聯(lián)機(jī)和脫機(jī)處理81第81頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月聚類(lèi)演變數(shù)據(jù)流

已開(kāi)發(fā)了幾個(gè)算法為聚類(lèi)數(shù)據(jù)流的算法。這里介紹其中兩個(gè)，即STREAM和CluStream。

1.STREAM：基于k中位數(shù)的流聚類(lèi)算法

STREAM是一種單遍掃描，常數(shù)因子的近似算法，是為K-中位數(shù)問(wèn)題開(kāi)發(fā)的。

STREAM源于k中位數(shù)聚類(lèi)，使用有限的時(shí)間和空間。

82第82頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.5.5聚類(lèi)演變數(shù)據(jù)流

2.CluStream：聚類(lèi)演變的數(shù)據(jù)流

CluStream是一種基于用戶(hù)指定的、聯(lián)機(jī)聚類(lèi)查詢(xún)的演變數(shù)據(jù)流聚類(lèi)算法。聯(lián)機(jī)微簇的處理分為兩個(gè)階段進(jìn)行：（1）收集統(tǒng)計(jì)數(shù)據(jù)（2）更新微簇。

83第83頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.6時(shí)間序列數(shù)據(jù)挖掘

15.6.1趨勢(shì)分析“如何處理時(shí)序數(shù)據(jù)？”目前一般有四種主要的變化成分用于特征化時(shí)序數(shù)據(jù)：

1．長(zhǎng)期或趨勢(shì)變化(trendmovement)2．循環(huán)運(yùn)動(dòng)或循環(huán)變化(cyclicmovementorcyclicvariations)3．季節(jié)性運(yùn)動(dòng)或季節(jié)性變化(seasonalmovementsorseasonalvariations)4．非規(guī)則或隨機(jī)變化（irregularorrandommovements）84第84頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月時(shí)間序列數(shù)據(jù)挖掘“怎樣確定數(shù)據(jù)的趨勢(shì)?”一個(gè)確定的趨勢(shì)的常用方法是用下面的算數(shù)均值序列計(jì)算n階移動(dòng)平均：85第85頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.6.2時(shí)間序列分析中的相似性搜索

“什么是相似搜索（similaritysearch）？”通常數(shù)據(jù)庫(kù)查詢(xún)是要找出符合查詢(xún)的精確數(shù)據(jù)，相似搜索與之不同，它是找出與給定查詢(xún)序列最接近的數(shù)據(jù)序列。86第86頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.6.2時(shí)間序列分析中的相似性搜索

數(shù)據(jù)變換(datatransformation)：從時(shí)間域(timedomain)到頻率域(frequencydomain)對(duì)時(shí)序數(shù)據(jù)的相似分析，通常采用歐氏距離作為相似計(jì)算的依據(jù)。兩個(gè)常見(jiàn)的獨(dú)立于數(shù)據(jù)的變換是離散傅立葉變換（DFT）和離散小波變（DWT）。87第87頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.6.2時(shí)間序列分析中的相似性搜索

能夠處理存在間隙和偏移與振幅差異的相似搜索的執(zhí)行步驟如下：

1．原子匹配（atomicmatching）

2．窗口結(jié)合(windowstitching)3．子序列排序(subsequenceordering)88第88頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.6.2時(shí)間序列分析中的相似性搜索下圖是子序列S(sequenceS)和子序列T(sequenceT)的原始序列（Originalsequence）、刪除間隙（Removinggap）、偏移變換（offsettranslation）和振幅變換（Amplitudescaling）的差別。此圖是在時(shí)序數(shù)據(jù)中的子序列匹配：原始序列形狀相同，但需要調(diào)整以處理存在于間隙、偏移和振幅中的差異。這些調(diào)整允許子序列在一定寬度∈的范圍內(nèi)匹配。89第89頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月90第90頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.7挖掘事務(wù)數(shù)據(jù)庫(kù)中的序列模式

15.7.1序列模式挖掘：概念和原語(yǔ)“什么是序列模式挖掘？”序列模式挖掘是指挖掘相對(duì)時(shí)間或其它模式出現(xiàn)頻率高的模式。舉個(gè)例子，順序模式是“顧客在購(gòu)買(mǎi)佳能數(shù)碼相機(jī)有可能在一個(gè)月以?xún)?nèi)購(gòu)買(mǎi)HP彩色打印機(jī)”。項(xiàng)集是一個(gè)非空的商品名的集合,D的第三個(gè)屬性便是項(xiàng)集。

91第91頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.7挖掘事務(wù)數(shù)據(jù)庫(kù)中的序列模式序列是一個(gè)向量,這個(gè)向量的每一維均為項(xiàng)集。用(s1，s2，?，sn)表示向量,其中sj為項(xiàng)集；對(duì)于兩個(gè)向量S1=<a1，a2，?，an>、S2=<b1，b2，?，bm>,若存在整數(shù)0<i1<i2<?<in<m+1使得,則稱(chēng)S1包含于S2,

記作在一個(gè)序列集中,若序列S不包含于任何其它的序列,我們稱(chēng)S是極大的；在D中,我們可以將某個(gè)顧客的項(xiàng)集按時(shí)間順序排成一個(gè)序列,我們稱(chēng)這個(gè)序列為這個(gè)顧客的顧客序列；92第92頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月若一個(gè)序列包含于某個(gè)顧客的顧客序列中,則稱(chēng)此顧客支持此序列；支持某序列的顧客數(shù)與總顧客數(shù)之比稱(chēng)為此序列的支持率；當(dāng)一個(gè)序列的支持率不小于一個(gè)給定的值時(shí),稱(chēng)這個(gè)序列為頻繁序列；而這個(gè)值稱(chēng)為最小支持,記作min_sup；序列所擁有的項(xiàng)集個(gè)數(shù)稱(chēng)為序列的長(zhǎng)度。一個(gè)長(zhǎng)度為k的序列稱(chēng)為k序列；設(shè)<i>為1序列,I為其中唯一項(xiàng)集。若某客戶(hù)支持<i>,則稱(chēng)此客戶(hù)支持項(xiàng)集I；若<i>為頻繁序列,則稱(chēng)I為頻繁項(xiàng)集。93第93頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.7.2挖掘序列模式的可伸縮方法

對(duì)于序列模式挖掘，如何開(kāi)發(fā)有效的和可伸縮的方法？最近的研究在這兩方面取得了進(jìn)展：（1）挖掘序列模式完全集的有效方法，（2）僅挖掘序列模式閉集的有效方法第一類(lèi)是基于R.Agrawal等人提出的Apriori特性的算法，主要包括AprioriAll算法、GSP算法、SPADE算法等.

94第94頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月挖掘序列模式的可伸縮方法

AprioriAll算法將序列的長(zhǎng)度定義為序列中包含的項(xiàng)集的數(shù)量。該算法將序列模式挖掘過(guò)程分為五個(gè)階段。

(1)排序階段

(2)頻繁項(xiàng)集階段

(3)轉(zhuǎn)換階段

(4)序列階段

(5)最大序列階段95第95頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.7.2挖掘序列模式的可伸縮方法

第二類(lèi)是J.Han等人提出的基于模式增長(zhǎng)的算法，包括FreeSpan算法、PrefixSpan算法等。PrefixSpan(Prefix-projectedequentialPatternMining)算法和FreeSpan算法都是基于模式增長(zhǎng)的挖掘方法。96第96頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.7.3基于約束的序列模式挖掘

約束可以用多種形式表示?？赡苁菍傩裕瑢傩再|(zhì)之間的聯(lián)系或者結(jié)果模式中的聚集。第一個(gè)約束是時(shí)間序列的持續(xù)時(shí)間（duration）T。第二個(gè)約束是事件重疊窗口（eventfoldingwindow），w。第三個(gè)約束是被發(fā)現(xiàn)的模式中時(shí)間之間的時(shí)間間隔（interval）int。97第97頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月15.7.4時(shí)間相關(guān)序列數(shù)據(jù)的周期性分析

“什么是周期分析？”周期分析（periodicityanalysis）是指對(duì)周期模式的挖掘，即在時(shí)序數(shù)據(jù)庫(kù)中找出重復(fù)出現(xiàn)的模式。

98第98頁(yè)，課件共111頁(yè)，創(chuàng)作于2023年2月

周期模式挖掘可以從不同的角度觀察，基于模式覆蓋，可以把模式周期分為三類(lèi)：挖掘全周期模式（full