【正文】 quence候選序列集 forall customsequences in the dataset do { forall cancidates c∈ Ck contained in customsequence do ++。 } Lk:={ c∈ Ck | ≥ minsupport} } Answer:=Maximal sequences in ∪ kLk。 end 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 63 .(3)數(shù)據(jù)挖掘的基本方法 AprioriG() : insert into Ck select ,…, 1, from Lk1 p, Lk1 q where =, … 2=, 1。 其中 fitemset是頻繁數(shù)據(jù)項(xiàng)集。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 64 .(3)數(shù)據(jù)挖掘的基本方法 從此算法的實(shí)現(xiàn)過程看，與前面關(guān)聯(lián)分析算法 Apriori較為相像，實(shí)際上將帶時(shí)間的交易數(shù)據(jù)轉(zhuǎn)換為顧客的數(shù)據(jù)項(xiàng)集序列，就為尋找頻繁數(shù)據(jù)項(xiàng)集作了準(zhǔn)備。算法實(shí)施前，先將交易數(shù)據(jù)排序（以顧客標(biāo)識(shí)為主鍵，交易時(shí)間為次鍵進(jìn)行升序排序），然后篩選出頻繁數(shù)據(jù)項(xiàng)集，在此基礎(chǔ)上經(jīng)過變換發(fā)現(xiàn)頻繁序列。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 65 .(3)數(shù)據(jù)挖掘的基本方法 ③ 時(shí)間序列挖掘的其它內(nèi)容 時(shí)間序列是指包含隨時(shí)間變化而發(fā)生的數(shù)值或事件序列，對(duì)這類數(shù)據(jù)的挖掘，上面所述內(nèi)容屬于挖掘序列模式，即從與時(shí)間相關(guān)的數(shù)據(jù)中，挖掘出相關(guān)的頻繁發(fā)生模式，例如所舉例子，從購(gòu)買某類商品的顧客可能會(huì)在近期內(nèi)購(gòu)買另一類商品，就是一種序列模式。除此以外，時(shí)序數(shù)據(jù)挖掘還有趨勢(shì)分析，相似搜索等重要內(nèi)容。 趨勢(shì)分析 ——時(shí)序數(shù)據(jù)中包含一個(gè)變量 Y，可以認(rèn)為是時(shí)間的函數(shù) Y=F(t)，時(shí)序分析即研究其中的趨勢(shì)變化、循環(huán)變化、季節(jié)性變化或無規(guī)律變化。采用數(shù)學(xué)上的平滑方法、曲線擬合方法、最小二乘法等可以完成有關(guān)的數(shù)據(jù)分析，制定預(yù)測(cè)方案。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 66 .(3)數(shù)據(jù)挖掘的基本方法 相似搜索 ——給定了一個(gè)時(shí)間序列數(shù)據(jù)，相似搜索是發(fā)現(xiàn)所有與它相似的時(shí)序數(shù)據(jù)，是一種序列匹配問題。相似搜索有如下主要的方法：（ 1）數(shù)據(jù)轉(zhuǎn)換，從時(shí)域到頻域。通常采用傅立葉變換、小波變換就可以完成這種轉(zhuǎn)換。采用歐幾里德的概念進(jìn)行相似性測(cè)量，完成數(shù)據(jù)匹配。（ 2）索引方法。采用 R樹、 R*樹，改進(jìn)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，提高相似搜索的速度。（ 3）時(shí)間序列查詢語言，完成復(fù)雜查詢，支持范圍查詢、最鄰近查詢等，搜索與給定時(shí)序數(shù)據(jù)相似的時(shí)序數(shù)據(jù)。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 67 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 前面所介紹的數(shù)據(jù)挖掘，主要針對(duì)結(jié)構(gòu)化數(shù)據(jù)進(jìn)行討論的。而復(fù)雜數(shù)據(jù)類型，諸如文本數(shù)據(jù)、多媒體數(shù)據(jù)、 Web數(shù)據(jù)都表現(xiàn)為半結(jié)構(gòu)化或非結(jié)構(gòu)化形式，此處對(duì)復(fù)雜數(shù)據(jù)類型的挖掘，舉文本、多媒體和 Web這三類較流行的數(shù)據(jù)進(jìn)行簡(jiǎn)要介紹。 1）文本數(shù)據(jù)挖掘 以文本形式存放的數(shù)據(jù)，包含一些半結(jié)構(gòu)化字段，如標(biāo)題、作者、出版社、出版時(shí)間、長(zhǎng)度等，但也包含無結(jié)構(gòu)的文本內(nèi)容。對(duì)這類半結(jié)構(gòu)化的文本數(shù)據(jù)，傳統(tǒng)的數(shù)據(jù)分析方法是采用情報(bào)檢索（ Information Retrieval），大部分是利用索引來完成檢索。但是，在文本數(shù)據(jù)迅猛增加時(shí)，傳統(tǒng)情報(bào)檢索已無法滿足實(shí)際需求。例如，不知道文本中究竟包含哪些內(nèi)容時(shí)，要想準(zhǔn)確查詢較為困難，想對(duì)文本進(jìn)行比較，評(píng)估文本的重要性、相關(guān)性等等，文本數(shù)據(jù)挖掘應(yīng)運(yùn)而生。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 68 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 文本挖掘的主要內(nèi)容有：（ 1）基于關(guān)鍵字關(guān)聯(lián)分析。首先收集經(jīng)常一起出現(xiàn)的關(guān)鍵字或詞匯，然后對(duì)其進(jìn)行關(guān)聯(lián)分析。關(guān)聯(lián)分析的方法與前面所述的事務(wù)數(shù)據(jù)關(guān)聯(lián)分析相似，但在此以前，要完成詞根處理、去除非用詞等預(yù)處理，將數(shù)據(jù)表示為包含 {文檔標(biāo)識(shí)符，關(guān)鍵字集合 }在內(nèi)的形式，轉(zhuǎn)換為事務(wù)數(shù)據(jù)關(guān)聯(lián)分析問題。（ 2）文本分類分析。自動(dòng)地對(duì)大量文本進(jìn)行分類，是一種重要的文本挖掘。一般做法是：先把一組預(yù)先分類過的文本當(dāng)作訓(xùn)練集，然后對(duì)訓(xùn)練集進(jìn)行分析得出分類模式。對(duì)這種分類模式需經(jīng)一定的測(cè)試，不斷細(xì)化。粗看起來，與前面事務(wù)數(shù)據(jù)的分類很相似，但因兩類數(shù)據(jù)的不同，不能采用事務(wù)數(shù)據(jù)分類時(shí)的決策樹分析，而是采用基于關(guān)聯(lián)的分類，細(xì)節(jié)不贅述。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 69 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 2）多媒體數(shù)據(jù)挖掘 現(xiàn)實(shí)生活中存在大量多媒體數(shù)據(jù)，例如，圖像數(shù)據(jù)、音頻數(shù)據(jù)、視頻數(shù)據(jù)等等，對(duì)這類數(shù)據(jù)的管理，從一般性的數(shù)據(jù)庫(kù)管理到數(shù)據(jù)挖掘進(jìn)行數(shù)據(jù)分析，是當(dāng)前數(shù)據(jù)庫(kù)技術(shù)的一個(gè)熱門領(lǐng)域。 此處，以圖像數(shù)據(jù)挖掘?yàn)橹鹘榻B一些多媒體數(shù)據(jù)挖掘的主要方法：多媒體數(shù)據(jù)的相似搜索，多媒體數(shù)據(jù)的多維分析，多媒體數(shù)據(jù)的分類與預(yù)測(cè)分析以及多媒體數(shù)據(jù)的關(guān)聯(lián)挖掘。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 70 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 多媒體數(shù)據(jù)的相似搜索 ——主要有兩種方法：（ 1）基于描述的搜索方法，在多媒體數(shù)據(jù)上建立標(biāo)引（如：關(guān)鍵字、標(biāo)題等）再進(jìn)行檢索。這種方法若手工完成是很費(fèi)勁的，若自動(dòng)完成，往往檢索結(jié)果質(zhì)量較差。（ 2）基于內(nèi)容的搜索方法，是近年來的主要方法，針對(duì)圖像內(nèi)容中的顏色構(gòu)成、紋理、形狀等進(jìn)行特征描述再檢索。例如，基于顏色直方圖的特征表示，多特征（顏色直方圖、形狀、位置和結(jié)構(gòu)）構(gòu)成的特征標(biāo)識(shí)，基于小波變換的特征標(biāo)識(shí)，建立了特征標(biāo)識(shí)以后，就可以利用圖像特征向量匹配來進(jìn)行相似搜索。 多媒體數(shù)據(jù)的多維分析 ——采用按傳統(tǒng)的從關(guān)系數(shù)據(jù)構(gòu)造數(shù)據(jù)立方體相似的方法，設(shè)計(jì)和構(gòu)造多媒體數(shù)據(jù)立方體。多媒體數(shù)據(jù)立方體可包含針對(duì)多媒體的維和度量，如顏色、紋理和形狀。在此基礎(chǔ)上，進(jìn)行基于視覺內(nèi)容的多維分析，并完成多種知識(shí)的挖掘，包括匯總、比較、分類、關(guān)聯(lián)和聚類。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 71 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 多媒體數(shù)據(jù)的分類和預(yù)測(cè)分析 ——分類和預(yù)測(cè)分析已經(jīng)用于多媒體數(shù)據(jù)挖掘，尤其在科學(xué)研究中，如天文學(xué)、地震學(xué)和地理科學(xué)的研究。目前圖像數(shù)據(jù)挖掘應(yīng)用中決策樹分類是最基本的數(shù)據(jù)挖掘方法。數(shù)據(jù)預(yù)處理在圖像數(shù)據(jù)挖掘中是相當(dāng)重要的，它包括數(shù)據(jù)清理、數(shù)據(jù)聚焦和特征提取，同時(shí)由于數(shù)據(jù)量很大，需要使用并行、分布處理等技術(shù)來加強(qiáng)處理能力。 多媒體數(shù)據(jù)中的關(guān)聯(lián)分析 ——多媒體數(shù)據(jù)中的關(guān)聯(lián)可能會(huì)涉及三類：（ 1）圖像內(nèi)容和非圖像內(nèi)容特征間的關(guān)聯(lián)，如規(guī)劃“如果照片的上半部分的 50%是藍(lán)色，那它很可能是天空”屬于此類，它把圖像內(nèi)容和關(guān)鍵字“天空”關(guān)聯(lián)在一起。（ 2）與空間關(guān)系無關(guān)的圖像內(nèi)容的關(guān)聯(lián)，如規(guī)劃“若一個(gè)圖像包含兩個(gè)藍(lán)方框，那么就可能包含一個(gè)紅色圓”，所描述的關(guān)聯(lián)構(gòu)思關(guān)于圖像內(nèi)容的，但與空間關(guān)系無關(guān)。（ 3）有空間關(guān)系的圖像內(nèi)容間的關(guān)聯(lián)，如“若兩個(gè)黃方框之間有一個(gè)紅色三角形，那么下面就可能有一個(gè)大的橢圓物體”，這里所描述的與圖像關(guān)聯(lián)的對(duì)象具有空間關(guān)系。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 72 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 3） Web挖掘 隨著 Inter技術(shù)的發(fā)展，尤其是 Web的全球普及，使得 Web上的信息無比豐富。但是，這些信息主要是一些大量的異構(gòu)數(shù)據(jù)源，文檔結(jié)構(gòu)性差，其數(shù)據(jù)多為半結(jié)構(gòu)化或非結(jié)構(gòu)化。對(duì)這些數(shù)據(jù)如何管理、分析，一種有效的方法是互聯(lián)網(wǎng)搜索引擎，利用此引擎可以有效發(fā)現(xiàn)和很好利用互聯(lián)網(wǎng)的信息資源。但是，這種方法存在如下不足：首先是一個(gè)主題可能包含成千上萬的文檔，從而導(dǎo)致搜索引擎的查詢結(jié)果結(jié)構(gòu)常常也是非常巨大，而其中只有較少以部分與用戶相關(guān)；其次是許多與主題相關(guān)的文檔或許沒有包含相應(yīng)的關(guān)鍵字。例如“ data mining”關(guān)鍵字，可能會(huì)發(fā)現(xiàn)與“ mining industry”有關(guān)的網(wǎng)頁(yè)。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 73 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 搜索引擎顯然不能作為利用 Web信息資源的唯一方法，同時(shí)我們還可看出，要對(duì) Web數(shù)據(jù)進(jìn)行有效的知識(shí)發(fā)現(xiàn)存在以下問題： 1）互聯(lián)網(wǎng)數(shù)據(jù)太大以至無法有效構(gòu)造數(shù)據(jù)倉(cāng)庫(kù)并進(jìn)行數(shù)據(jù)挖掘。 2）網(wǎng)頁(yè)的復(fù)雜性遠(yuǎn)遠(yuǎn)要大于任何傳統(tǒng)的文本文檔。 3）互聯(lián)網(wǎng)的資源具有很大的動(dòng)態(tài)性。 4）互聯(lián)網(wǎng)的用戶群體具有多樣性。 5）互聯(lián)網(wǎng)上的信息只有一小部分是真正有用的或相關(guān)的，通常來說互聯(lián)網(wǎng)上 99％的信息對(duì) 99％的用戶是無用的。 正因?yàn)檫@樣， Web數(shù)據(jù)挖掘應(yīng)運(yùn)而生。 Web挖掘就是要發(fā)現(xiàn)網(wǎng)頁(yè)的讀取模式、互聯(lián)網(wǎng)結(jié)構(gòu)和互聯(lián)網(wǎng)內(nèi)容描述所存在的規(guī)律和動(dòng)態(tài)特點(diǎn)，從網(wǎng)頁(yè)的海洋中（據(jù)統(tǒng)計(jì)， 2021年初，網(wǎng)頁(yè)數(shù)已達(dá) 8億頁(yè)，并估計(jì)每 4個(gè)月要翻一番。）發(fā)現(xiàn)高質(zhì)量的信息，有效地進(jìn)行知識(shí)發(fā)現(xiàn)。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 74 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 Web挖掘是將傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)和 Web結(jié)合起來，進(jìn)行 Web知識(shí)的提取，從 Web文檔和 Web活動(dòng)中抽取感興趣的潛在的有用模式和隱藏的信息。一般地， Web挖掘可以分為三類： Web內(nèi)容挖掘， Web結(jié)構(gòu)挖掘和 Web使用挖掘。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 75 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 （ 1） Web內(nèi)容挖掘 Web內(nèi)容挖掘是對(duì) Web上大量文檔集合的內(nèi)容進(jìn)行總結(jié)、分類、聚類、關(guān)聯(lián)分析以及利用 Web文檔進(jìn)行趨勢(shì)預(yù)測(cè)等，其中最重要的是，文本的特征表示、分類和聚類。 文本的特征表示 ——Web文檔是半結(jié)構(gòu)化或非結(jié)構(gòu)化的，這樣的特殊性使得現(xiàn)存的數(shù)據(jù)挖掘技術(shù)無法直接加以應(yīng)用。我們需要對(duì) Web文本進(jìn)行預(yù)處理，抽取代表其特征的元數(shù)據(jù)。這些特征可以用結(jié)構(gòu)化形式保存，作為文檔的中間表示形式。 W3C近來制定的 XML、 RDF等規(guī)范提供了對(duì) Web文檔進(jìn)行描述的語言和框架。矢量空間模型（VSM）是近年來應(yīng)用較多且效果較好的方法之一。在該模型中，文檔空間被看作是由一組正交詞條矢量所形成的矢量空間，每個(gè)文檔d表示為其中的一個(gè)范式特征矢量V(d)=(k1,w1(d)?！?。ki,wi(d)?！n,wn(d)) ，其中 ki為詞條項(xiàng)， wi(d)為 ki在 d中的權(quán)值，可以將 d中出現(xiàn)的所有單詞作為 ki，也可以要求ki是 d中出現(xiàn)的所有短語，從而提高內(nèi)容特征表示的準(zhǔn)確性。 wi(d)一般被定義為 ki在 d中出現(xiàn)頻率 tfi(d)的函數(shù)，即 wi(d)=ψ(tfi(d))，常用的 ψ函數(shù)有：布爾函數(shù)、平方根函數(shù)、對(duì)數(shù)函數(shù)和 TF1DF函數(shù)。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 76 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 Web文本分類 —— 文本分類是一種典型的有知道的機(jī)器學(xué)習(xí)問題，一般分為訓(xùn)練和分類兩個(gè)階段。具體過程為： 訓(xùn)練階段 —— 1）定義類別集合 Z={z1,…,zi,…,zm} ，這些類別可以是層次式的，頁(yè)可以是并列式的； 2）給出訓(xùn)練文檔集合 F={f1,…,fj,…fn} ，每個(gè)訓(xùn)練文檔 fj被標(biāo)上所屬的類別標(biāo)識(shí) zi； 3）統(tǒng)計(jì)文本集合 F中所有文檔的特征矢量 V(fj)，確定代表 Z中每個(gè)類別的特征矢量 V(zi)。 分類階段 —— 1）對(duì)測(cè)試文檔集合 TD={d1,…,dk,…,dr} 中的每個(gè)待分類文檔 dk，計(jì)算其特征向量 V(dk)與每個(gè) V(zi)之間的相似度 Sim(dk,zi)； 2）選取相似度最大的一個(gè)類別作為 dk的類別。 在計(jì)算 Sim(dk, zi)時(shí)，有多種方法可供選擇。最簡(jiǎn)單的方式是僅考慮兩個(gè)特征矢量中所包含的詞條的重疊程度，即 Sim(dk, zi)=(∩n(dk, zi))/(∪ n(dk, zi))，其中， ∩n(dk,zi)是 V(dk)和 V(zi)具有的相同詞條數(shù)目， ∪ n(dk,zi)是V(dk)和 V(zi)具有的所有詞條數(shù)目；最常用的方法是考慮兩個(gè)特征矢量之間的夾角余弦，即 Sim(dk,zi)=(V(dk).V(zi))/(|V(dk)|*|V(zi)|)。 2021年 6月 14日星期一 數(shù)據(jù)庫(kù)教程（沈 ） 77 （ 4）復(fù)雜數(shù)據(jù)類型的挖掘 Web文本聚類 —— Web文本聚類是一種典型的無指導(dǎo)的機(jī)器學(xué)習(xí)問題。目前的文本聚類方法大致可以分為層次凝聚法和平面劃分法兩種類型。對(duì)于給定的文檔集合 D={d1,…,di,…,dn} ，層次凝聚法的具體過程如下。 1）將 D中的每個(gè)文檔 di看作是一個(gè)具有單個(gè)成員的簇zi={di}，這些簇構(gòu)成了 D的一個(gè)聚類 Z={z1,…,zi,…zn} ； 2）計(jì)算 Z中每對(duì)簇 (zi,zj)之間的相似度 Sim(zi,zj)； 3）選取具有最大相似度的簇對(duì)，并將它們合并為一個(gè)新的簇， zk=zi∪ zj，從而構(gòu)成了 D的一個(gè)新的聚類，Z={z1,…,zn