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

復(fù)雜對象數(shù)據(jù)挖掘1第1頁，共111頁，2023年，2月20日，星期一第15章復(fù)雜對象數(shù)據(jù)挖掘

2第2頁，共111頁，2023年，2月20日，星期一15.1空間數(shù)據(jù)庫挖掘

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

15.3文本挖掘15.4挖掘萬維網(wǎng)15.5挖掘數(shù)據(jù)流15.6時間序列數(shù)據(jù)挖掘15.7挖掘事務(wù)數(shù)據(jù)庫中的序列模式15.8挖掘生物學(xué)數(shù)據(jù)中的序列模式3第3頁，共111頁，2023年，2月20日，星期一15.1空間數(shù)據(jù)庫挖掘

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

4第4頁，共111頁，2023年，2月20日，星期一15.1.1空間數(shù)據(jù)概述空間數(shù)據(jù)是指與二維、三維或更高維空間的空間坐標(biāo)及空間范圍相關(guān)的數(shù)據(jù)空間數(shù)據(jù)的復(fù)雜性特征有：

空間屬性之間的非線性關(guān)系空間數(shù)據(jù)的多尺度特征空間信息的模糊性空間維數(shù)的增高空間數(shù)據(jù)的缺值5第5頁，共111頁，2023年，2月20日，星期一

空間查詢工作

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

空間查詢工作

7第7頁，共111頁，2023年，2月20日，星期一15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計算模型

空間關(guān)系計算

(1)常用的兩個空間實(shí)體之間的距離有：最小值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)之間的歐氏或曼哈頓距離中最小的，即（15-1）8第8頁，共111頁，2023年，2月20日，星期一大值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)之間的歐氏或曼哈頓距離中最大的，即（15-2）平均值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)之間的歐氏或曼哈頓距離的平均值，即（15-3）空間關(guān)系計算9第9頁，共111頁，2023年，2月20日，星期一中心方法：定義實(shí)體A和B的距離為A中的中心點(diǎn)與和B中的中心點(diǎn)之間的歐氏或曼哈頓距離的平均值，即(15-4)

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

空間關(guān)系計算10第10頁，共111頁，2023年，2月20日，星期一15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計算模型（2）兩個空間實(shí)體之間存在若干拓?fù)潢P(guān)系。這些關(guān)系基于兩個實(shí)體的位置：分離（Disjoint）：A與B分離，表示B中任何點(diǎn)都不在A中，反之亦然。重疊/相交：A與B重疊或相交表示至少有一個點(diǎn)既在A里也在B里。等價：A與B這兩個實(shí)體的所有點(diǎn)都是共有的。11第11頁，共111頁，2023年，2月20日，星期一包含于：A包含于B，表示A的所有點(diǎn)都在B里，反之不一定。覆蓋/包含：A覆蓋或包含B，當(dāng)且僅當(dāng)B包含于A。(3)方位是描述兩個點(diǎn)狀實(shí)體位置關(guān)系的一種度量，如果要分析面狀實(shí)體間的方位關(guān)系，則應(yīng)把多邊形轉(zhuǎn)換為重心點(diǎn)或其它點(diǎn)狀實(shí)體。15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計算模型12第12頁，共111頁，2023年，2月20日，星期一空間實(shí)體信息模型

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

15第15頁，共111頁，2023年，2月20日，星期一15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計算模型空間網(wǎng)絡(luò)模型

空間網(wǎng)絡(luò)結(jié)構(gòu)模型中地理現(xiàn)象被抽象為鏈、結(jié)點(diǎn)以及它們之間的連通關(guān)系（圖15-4對空間網(wǎng)絡(luò)的抽象）。

圖的形式化定義為

（15-10）

圖15-4對空間網(wǎng)絡(luò)的抽象ACDB16第16頁，共111頁，2023年，2月20日，星期一15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計算模型位置—屬性一體化的空間實(shí)體信息模型一般空間實(shí)體的形式化模型為一個四元組，分別代表空間實(shí)體四個方面的特征。其中位置特征數(shù)據(jù)為

…（15-11）

17第17頁，共111頁，2023年，2月20日，星期一15.1.3空間數(shù)據(jù)挖掘基礎(chǔ)

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

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

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

空間數(shù)據(jù)挖掘的方法體系空間評價?？臻g分類與聚類?？臻g分布計算?？臻g優(yōu)化?？臻g回歸分析?？臻g動態(tài)模擬與預(yù)測?？臻g與時序關(guān)聯(lián)知識歸納。20第20頁，共111頁，2023年，2月20日，星期一15.1.4幾種空間數(shù)據(jù)挖掘算法

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

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

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

空間聚類方法

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

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

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

圖像挖掘

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

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

在圖像和視頻數(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)34第34頁，共111頁，2023年，2月20日，星期一

多媒體數(shù)據(jù)的相似搜索對多媒體數(shù)據(jù)相似性搜索，主要考慮兩種多媒體標(biāo)引和檢索系統(tǒng)：（1）基于描述的檢索系統(tǒng)，主要是在圖像描述之上建立標(biāo)引和執(zhí)行對象檢索，如關(guān)鍵字、標(biāo)題、尺寸、創(chuàng)建時間等；（2）基于內(nèi)容的檢索系統(tǒng)，它支持基于圖像內(nèi)容的檢索，如顏色構(gòu)成、質(zhì)地、形狀、對象和小波變換等。35第35頁，共111頁，2023年，2月20日，星期一兩種查詢在基于內(nèi)容的檢索系統(tǒng)中,通常有兩種查詢：基于圖像樣本的查詢（imagesample-basedqueries）。圖像樣本查詢是指找出所有與給定圖像樣本相似的圖像。圖像特征描述查詢(imagefeaturespecificationqueries)。圖像特征描述查詢是指給出圖像的特征描述或概括36第36頁，共111頁，2023年，2月20日，星期一

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

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

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

39第39頁，共111頁，2023年，2月20日，星期一文本挖掘的一般過程文本挖掘的一般過程文本挖掘過程一般包括文本準(zhǔn)備、特征標(biāo)引、特征集縮減、知識模式的提取、知識模式的評價、知識模式的輸出等過程

.文本特征標(biāo)引特征集縮減知識模型的提取知識模型的評價知識模型的輸出40第40頁，共111頁，2023年，2月20日，星期一

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

特征提取主題標(biāo)引文本分類文本聚類自動摘要41第41頁，共111頁，2023年，2月20日，星期一

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

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

…（15-15）43第43頁，共111頁，2023年，2月20日，星期一

文本特征標(biāo)引

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

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

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

45第45頁，共111頁，2023年，2月20日，星期一

文本的自動分類

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

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

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

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

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

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

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

基于遺傳算法（GA）的文本聚類

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

54第54頁，共111頁，2023年，2月20日，星期一15.4挖掘互聯(lián)網(wǎng)

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

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

rank方法

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

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

Web可以用一個有向圖來表示，G=（V，E），V是頁面的集合，E是頁面之間的超鏈接集合。頁面抽象為圖中的頂點(diǎn)，而頁面之間的超鏈接抽象為圖中的有向邊。頂點(diǎn)V的入邊表示對V的引用，出邊表示V引用了其他的頁面。所以Web頁面之間的超鏈接揭示了Web結(jié)構(gòu)。57第57頁，共111頁，2023年，2月20日，星期一15.4.2挖掘Web鏈接結(jié)構(gòu)識別權(quán)威Web頁面

鏈接文本（AnchorTexts）可以用來對被引用的頁面進(jìn)行索引（例如：Webor,WWW，Google）。超鏈接可以用來計算頁面的rankingscore,通過超鏈接可以將一個頁面的rankingcore傳遞到相鄰的頁面。58第58頁，共111頁，2023年，2月20日，星期一15.4.2挖掘Web鏈接結(jié)構(gòu)識別權(quán)威Web頁面

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

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

音頻挖掘音頻挖掘（AudioMining）指對音頻信息的自動處理和分析過程。語音挖掘的另外一個用途在于將語音對應(yīng)到個人62第62頁，共111頁，2023年，2月20日，星期一

音頻挖掘

視頻挖掘15.4.4Web文檔的自動分類15.4.5Web使用挖掘

63第63頁，共111頁，2023年，2月20日，星期一

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

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

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

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

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

本節(jié)，我們考慮一些常用的大綱數(shù)據(jù)結(jié)構(gòu)和技術(shù)。1．隨機(jī)抽樣一種叫做水庫抽樣，可以用來無放回的選取一個無偏的S個元素的隨機(jī)樣本，沒有更換。水庫抽樣的想法相對簡單。2．滑動窗口基本的思想是：僅僅基于最近的數(shù)據(jù)做出決策，而不是對目前為止看到的所有數(shù)據(jù)或?qū)δ硞€樣本進(jìn)行計算。70第70頁，共111頁，2023年，2月20日，星期一15.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òu)成）。71第71頁，共111頁，2023年，2月20日，星期一流OLAP和流數(shù)據(jù)立方體（續(xù)）1．壓縮時間尺度的時間維：傾斜時間框架

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

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

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

1.數(shù)據(jù)流頻繁模式挖掘2.數(shù)據(jù)流頻繁模式挖掘算法數(shù)據(jù)流頻繁模式挖掘的關(guān)鍵問題就是如何快速對數(shù)據(jù)流中所出現(xiàn)的模式進(jìn)行計數(shù)。74第74頁，共111頁，2023年，2月20日，星期一數(shù)據(jù)流所出現(xiàn)的模式數(shù)據(jù)流所出現(xiàn)的模式分成三類:

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

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

(3)當(dāng)sup(X)<s時,稱X為非頻繁模式,并在算法中舍棄非頻繁的模式以減少算法的空間復(fù)雜度。75第75頁，共111頁，2023年，2月20日，星期一15.5.4動態(tài)數(shù)據(jù)流的分類

增量式方法又稱為在線式、連續(xù)式或序列式方法等

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

76第76頁，共111頁，2023年，2月20日，星期一15.5.4動態(tài)數(shù)據(jù)流的分類

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

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

77第77頁，共111頁，2023年，2月20日，星期一15.5.4動態(tài)數(shù)據(jù)流的分類信息增益用于表達(dá)計算分類到達(dá)該節(jié)點(diǎn)的樣本所需要的信息,其計算公式為屬性j的熵為,其中

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

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

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

79第79頁，共111頁，2023年，2月20日，星期一②CVFDT

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

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

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

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

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

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

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

82第82頁，共111頁，2023年，2月20日，星期一15.5.5聚類演變數(shù)據(jù)流

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

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

83第83頁，共111頁，2023年，2月20日，星期一15.6時間序列數(shù)據(jù)挖掘

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

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

“什么是相似搜索（similaritysearch）？”通常數(shù)據(jù)庫查詢是要找出符合查詢的精確數(shù)據(jù)，相似搜索與之不同，它是找出與給定查詢序列最接近的數(shù)據(jù)序列。86第86頁，共111頁，2023年，2月20日，星期一15.6.2時間序列分析中的相似性搜索

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

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

1．原子匹配（atomicmatching）

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

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

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

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

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

94第94頁，共111頁，2023年，2月20日，星期一挖掘序列模式的可伸縮方法

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

(1)排序階段

(2)頻繁項集階段

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

(4)序列階段

(5)最大序列階段95第95頁，共111頁，2023年，2月20日，星期一15.7.2挖掘序列模式的可伸縮方法

第二類是J.Han等人提出的基于模式增長的算法，包括FreeSpan算法、PrefixSpan算法等。PrefixSpan(Prefix-projectedequentialPatternMining)算法和FreeSpan算法都是基于模式增長的挖掘方法。96第96頁，共111頁，2023年，2月20日，星期一15.7.3基于約束的序列模式挖掘

約束可以用多種形式表示。可能是屬性，屬性質(zhì)之間的聯(lián)系或者結(jié)果模式中的聚集。第一個約束是時間序列的持續(xù)時間（duration）T。第二個約束是事件重疊窗口（eventfoldingwindow），w。第三個約束是被發(fā)現(xiàn)的模式中時間之間的時間間隔（interval）int。97第97頁，共111頁，2023年，2月20日，星期一15.7.4時間相關(guān)序列數(shù)據(jù)的周期性分析

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

98第98頁，共111頁，2023年，2月20日，星期一

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