火龍果數(shù)據(jù)挖掘概念與技術(shù)

1、數(shù)據(jù)挖掘第13章2022年9月12日2 /72Course Outline挖掘復(fù)雜的數(shù)據(jù)數(shù)據(jù)挖掘的其他方法數(shù)據(jù)挖掘的應(yīng)用數(shù)據(jù)挖掘與社會(huì)2022年9月12日3 /72數(shù)據(jù)挖掘的對(duì)象簡(jiǎn)單數(shù)據(jù) 關(guān)系數(shù)據(jù)庫(kù)、事務(wù)數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)復(fù)雜類型數(shù)據(jù) 復(fù)雜對(duì)象、空間數(shù)據(jù)、多媒體數(shù)據(jù)、時(shí)間序列數(shù)據(jù)、符號(hào)序列數(shù)據(jù)、生物學(xué)序列、文本數(shù)據(jù)、Web數(shù)據(jù)等 復(fù)雜的數(shù)據(jù)類型復(fù)雜的數(shù)據(jù)類型序列數(shù)據(jù)圖與網(wǎng)絡(luò)其他類型數(shù)據(jù)時(shí)間序列數(shù)據(jù)符號(hào)序列數(shù)據(jù)生物學(xué)序列同質(zhì)數(shù)據(jù)或異質(zhì)數(shù)據(jù)例子空間數(shù)據(jù)時(shí)間空間數(shù)據(jù)物流網(wǎng)系統(tǒng)數(shù)據(jù)多媒體數(shù)據(jù)文本數(shù)據(jù)Web數(shù)據(jù)數(shù)據(jù)流挖掘序列數(shù)據(jù)序列是事件的有序列表。根據(jù)事件的特征，序列數(shù)據(jù)可以分為三類（1）時(shí)間序列數(shù)據(jù)；

2、（2）符號(hào)序列數(shù)據(jù)；（3）生物學(xué)序列。時(shí)間序列數(shù)據(jù)由相等時(shí)間間隔記錄的數(shù)值數(shù)據(jù)的長(zhǎng)序列組成。符號(hào)序列數(shù)據(jù)由事件或標(biāo)稱數(shù)據(jù)的長(zhǎng)序列組成，通常不是相等的時(shí)間間隔觀測(cè)。生物學(xué)序列包括DNA序列和蛋白質(zhì)序列。這種序列通常很長(zhǎng)，攜帶重要的、復(fù)雜的、隱含的語(yǔ)義。2022年9月12日6 /72時(shí)序數(shù)據(jù)庫(kù)和序列數(shù)據(jù)庫(kù)時(shí)序數(shù)據(jù)庫(kù)：由隨時(shí)間變化的序列或事件組成的數(shù)據(jù)庫(kù)等時(shí)間間隔測(cè)得的數(shù)據(jù) (regular intervals)時(shí)序數(shù)據(jù)庫(kù)是一種序列數(shù)據(jù)庫(kù)序列數(shù)據(jù)庫(kù)：由有序事件序列組成的數(shù)據(jù)庫(kù)可有時(shí)間標(biāo)記，也可以沒有時(shí)間標(biāo)記可以是時(shí)序數(shù)據(jù)庫(kù)，也可以不是。如WEB遍歷。2022年9月12日7 /72時(shí)序數(shù)據(jù)例子Time

3、-series plot2022年9月12日8 /72時(shí)序數(shù)據(jù)和序列數(shù)據(jù)的挖掘（一）趨勢(shì)分析 通過對(duì)趨勢(shì)，循環(huán)，季節(jié)和非規(guī)則成分的運(yùn)動(dòng)的系統(tǒng)分析，使人們可以在較合理的情況下，制定出長(zhǎng)期或短期的預(yù)測(cè)（即預(yù)報(bào)時(shí)序） 相似搜索 找出與給定查詢序列最接近的數(shù)據(jù)序列。 子序列匹配（subsequence matching）是找出與給定序列相似的所有數(shù)據(jù)序列， 整體序列匹配（whole sequence matching）是找出彼此間相似的序列。 例如：對(duì)金融市場(chǎng)的分析（如股票數(shù)據(jù)分析），醫(yī)療診斷（如心電圖分析），和科學(xué)與工程數(shù)據(jù)庫(kù)（如能量消耗分析）等 2022年9月12日9 /72時(shí)序數(shù)據(jù)和序列數(shù)據(jù)的挖

4、掘（一）序列模式挖掘（sequence pattern mining） 是指挖掘相對(duì)時(shí)間或其它模式出現(xiàn)頻率高的模式。 周期分析 （periodicity analysis） 對(duì)周期模式的挖掘，即在時(shí)序數(shù)據(jù)庫(kù)中找出重復(fù)出現(xiàn)的模式。 例如: 季節(jié)，潮汐，行星軌道，每日能源消耗，每日交通模式 符號(hào)序列中的序列模式挖掘序列模式是一個(gè)存在于單個(gè)序列或一個(gè)序列集中的頻繁子序列。序列模式挖掘是挖掘在一個(gè)序列或序列集中頻繁的子序列。序列分類基于特征的分類基于序列距離的分類基于模型的分類把序列轉(zhuǎn)換成特征向量，然后使用傳統(tǒng)的方法分類度量序列之間相似性的距離函數(shù)決定分類的質(zhì)量如使用隱馬爾科夫模型(HMM)或其他統(tǒng)計(jì)

5、學(xué)模型來(lái)對(duì)2022年9月12日11 /722022年9月12日12 /72生物學(xué)序列對(duì)比序列對(duì)比基于如下事實(shí)：所有活的生物體都是進(jìn)化相關(guān)的。這意味著進(jìn)化中相近物種的核苷酸和蛋白質(zhì)序列應(yīng)該表現(xiàn)出更多的相似性。比對(duì)是對(duì)學(xué)列排列以便獲取最大程度的一致性，它也表示序列之間的相似程度。同源：兩個(gè)序列具有共同的祖先。生物學(xué)序列比對(duì)生物序列比對(duì)：對(duì)于給定的兩個(gè)或多個(gè)輸入生物序列，識(shí)別具有長(zhǎng)保守子序列的相似序列。局部比對(duì)：僅有部分序列進(jìn)行比對(duì)。全局比對(duì)：在序列的整個(gè)長(zhǎng)度上進(jìn)行比對(duì)。圖模式挖掘是在一個(gè)圖或者一個(gè)圖集中挖掘頻繁子圖（又稱（子）圖模式）。圖模式挖掘的應(yīng)用：產(chǎn)生圖的索引結(jié)構(gòu)，用于搜索；用頻繁的和有區(qū)別

6、力的子圖作為特征，可有效地進(jìn)行圖分類。挖掘圖和網(wǎng)絡(luò)同質(zhì)網(wǎng)絡(luò)：所有的節(jié)點(diǎn)和邊都具有相同的類型。異質(zhì)網(wǎng)絡(luò)：節(jié)點(diǎn)和邊具有不同的類型。網(wǎng)絡(luò)的統(tǒng)計(jì)建模通過網(wǎng)絡(luò)分析，可以探查網(wǎng)絡(luò)中的信息冗余，以進(jìn)行高質(zhì)量的數(shù)據(jù)清理、數(shù)據(jù)集成、信息驗(yàn)證和可信性分析。網(wǎng)絡(luò)大型圖和同質(zhì)網(wǎng)絡(luò)具有內(nèi)聚結(jié)構(gòu)，通常隱藏在大量互連的節(jié)點(diǎn)和鏈接中。異質(zhì)網(wǎng)絡(luò)包含不同類型的互聯(lián)的節(jié)點(diǎn)和鏈接。這種互連結(jié)構(gòu)包含豐富的信息，可以用來(lái)相互加強(qiáng)節(jié)點(diǎn)和鏈接，從一種類型到另一種類型傳播知識(shí)。網(wǎng)絡(luò)的監(jiān)督分類和半監(jiān)督分類是當(dāng)前的熱門課題。圖和網(wǎng)絡(luò)的聚類、秩評(píng)定和分類2022年9月12日19 /72空間數(shù)據(jù)庫(kù)挖掘空間數(shù)據(jù)庫(kù)及其一般特點(diǎn)存儲(chǔ)了大量與空間有關(guān)的數(shù)據(jù)包

7、含拓?fù)?距離信息復(fù)雜的、多維的索引結(jié)構(gòu)訪問通過空間數(shù)據(jù)的方法，通常需要空間推理、地理計(jì)算、空間知識(shí)表示技術(shù)空間數(shù)據(jù)挖掘：要綜合數(shù)據(jù)挖掘與空間數(shù)據(jù)庫(kù)技術(shù)2022年9月12日20 /72空間數(shù)據(jù)庫(kù)挖掘傳統(tǒng)空間數(shù)據(jù)分析（統(tǒng)計(jì)方法）的不足統(tǒng)計(jì)方法通常假設(shè)空間分布的數(shù)據(jù)間是統(tǒng)計(jì)上獨(dú)立的，但現(xiàn)實(shí)是空間對(duì)象間是相互關(guān)聯(lián)的；大部分統(tǒng)計(jì)模型只有具有相當(dāng)豐富領(lǐng)域知識(shí)和統(tǒng)計(jì)方面經(jīng)驗(yàn)的統(tǒng)計(jì)專家才用得起來(lái)；統(tǒng)計(jì)方法不適用符號(hào)值，或不完整或非確定的數(shù)據(jù)，對(duì)大規(guī)模數(shù)據(jù)庫(kù)其計(jì)算代價(jià)也十分昂貴?？臻g數(shù)據(jù)挖掘?qū)?duì)傳統(tǒng)的空間分析方法加以擴(kuò)展，重點(diǎn)解決其高效性，可伸縮性，與數(shù)據(jù)庫(kù)系統(tǒng)的緊密結(jié)合，改進(jìn)與用戶的交互，以及新的知識(shí)的發(fā)現(xiàn)。

8、 2022年9月12日21 /72空間聚類方法 空間數(shù)據(jù)聚類是要在一個(gè)較大的多維數(shù)據(jù)集中根據(jù)距離的計(jì)算找出簇，或稠密區(qū)域。 2022年9月12日22 /72空間分類和空間趨勢(shì)分析空間分類指分析空間對(duì)象導(dǎo)出與一定空間特征有關(guān)的分類模式，如郊區(qū)，高速公路，河流的鄰接?？臻g趨勢(shì)分析處理的是另一類問題：根據(jù)某空間維找出變化趨勢(shì) 。 例如，當(dāng)離城市中心越來(lái)越遠(yuǎn)時(shí)，我們要分析經(jīng)濟(jì)形勢(shì)的變化趨勢(shì)，或離海洋越來(lái)越遠(yuǎn)時(shí)，氣候與植物的變化趨勢(shì)。 集成在物聯(lián)網(wǎng)系統(tǒng)中的數(shù)據(jù)是動(dòng)態(tài)的、異變的、含噪聲的、不一致的和相互依賴的，包含豐富而復(fù)雜的信息，并且對(duì)于實(shí)事決策是至關(guān)重要的。需要把當(dāng)前環(huán)境與大型信息庫(kù)聯(lián)系，進(jìn)行實(shí)時(shí)計(jì)算

9、并準(zhǔn)時(shí)返回響應(yīng)。該領(lǐng)域的研究包括物聯(lián)數(shù)據(jù)流中稀有事件監(jiān)測(cè)和異常分析，物聯(lián)數(shù)據(jù)分析的可靠性，網(wǎng)聯(lián)網(wǎng)中有效的時(shí)空數(shù)據(jù)分析，以及數(shù)據(jù)流挖掘與實(shí)時(shí)自動(dòng)控制過程的集成。挖掘物聯(lián)網(wǎng)系統(tǒng)數(shù)據(jù)2022年9月12日24 /72多媒體數(shù)據(jù)庫(kù)挖掘多媒體數(shù)據(jù)庫(kù)是指存儲(chǔ)和管理大量多媒體對(duì)象的數(shù)據(jù)庫(kù)，如音頻數(shù)據(jù)，圖象數(shù)據(jù)，視頻數(shù)據(jù)，序列數(shù)據(jù)，以及超文本數(shù)據(jù)，包含文本，文本標(biāo)記(text markup)，和鏈接(linkage)。多媒體數(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)，它支持基

10、于圖象內(nèi)容的檢索，如顏色構(gòu)成，質(zhì)地，形狀，對(duì)象，和小波變換等。多媒體數(shù)據(jù)的分類和預(yù)測(cè)分析 多媒體數(shù)據(jù)中的關(guān)聯(lián)規(guī)則挖掘 2022年9月12日25 /72文本數(shù)據(jù)庫(kù)和信息檢索（IR）文本數(shù)據(jù)庫(kù) 半結(jié)構(gòu)化數(shù)據(jù)： 它既不是完全無(wú)結(jié)構(gòu)的也不是完全結(jié)構(gòu)的。例如，一個(gè)文檔可能包含結(jié)構(gòu)字段，如標(biāo)題，作者，出版日期，長(zhǎng)度，分類，等等，也可能包含大量的非結(jié)果化的文本成分，如摘要和內(nèi)容。 典型的信息檢索問題是基于用戶的輸入（如關(guān)鍵字或樣例文檔）定位相關(guān)的文檔。典型的信息檢索系統(tǒng)聯(lián)機(jī)圖書館目錄聯(lián)機(jī)文檔管理系統(tǒng)信息檢索與數(shù)據(jù)庫(kù)系統(tǒng)DB：并發(fā)控制、恢復(fù)、事務(wù)管理、更新IR：非結(jié)構(gòu)化文檔、基于關(guān)鍵字的近似搜索2022年9月

11、12日26 /72文本檢索的基本度量查準(zhǔn)率:反映正確性查全率: 反映全面性RelevantRelevant & RetrievedRetrievedAll Documents應(yīng)該被檢索到的2022年9月12日27 /72文本檢索的基本度量查準(zhǔn)率:反映正確性查全率: 反映全面性RelevantRelevant & RetrievedRetrievedAll Documents實(shí)際被檢索到的2022年9月12日28 /72文本檢索的基本度量查準(zhǔn)率:反映正確性查全率: 反映全面性RelevantRelevant & RetrievedRetrievedAll Documents2022年9月12日2

12、9 /72基于關(guān)鍵字的檢索在關(guān)鍵字檢索中，文檔被看作字符串，可用一組關(guān)鍵字識(shí)別查詢由關(guān)鍵字表達(dá)式構(gòu)成例子, 汽車 and 修理店查詢應(yīng)考慮同義詞問題, 如： 修理 和 維修困難同義詞問題（Synonymy）:文檔與Key相關(guān)，但Key在文檔中不出現(xiàn)多義詞問題（Polysemy）:同一Key在不同的上下文有不同的含義，如Mine。2022年9月12日30 /72基于相似性的檢索（1）相似檢索是指基于一組共同的關(guān)鍵字找出相似的文檔檢索結(jié)果基于相關(guān)度，即：與關(guān)鍵詞的近似性，關(guān)鍵詞的出現(xiàn)頻率等。非用詞表（Stop list）無(wú)關(guān)的高頻詞，如：a, the, of, for, etc.文檔不同時(shí)，非用詞

13、表也不同2022年9月12日31 /72基于相似性的檢索（2） 由于相似文檔具有相似的相對(duì)詞頻，因此我們可以基于頻率表中的相對(duì)詞頻，計(jì)算一組文檔的相似性。 詞頻矩陣相似度: 基于一組關(guān)鍵詞的文檔相似性相關(guān)詞的出現(xiàn)次數(shù)余弦距離：缺點(diǎn)：當(dāng)詞數(shù)T和文檔數(shù)目D很大時(shí)，高的維數(shù)導(dǎo)致低的計(jì)算效率，且出現(xiàn)大的稀疏向量。用奇異值分解 (SVD)技術(shù)減小詞頻矩陣大小保留詞頻矩陣中最有意義的K行和K列，K值為幾百。詞/文檔d1d2d3d4d5d6d7t13218431687215430t2354917156826392t3223216746289225172022年9月12日32 /72文本數(shù)據(jù)挖掘的類型1.基于

14、關(guān)鍵字的關(guān)聯(lián)分析2.文檔分類分析2022年9月12日33 /72基于關(guān)鍵字的關(guān)聯(lián)分析動(dòng)機(jī)收集經(jīng)常一起出現(xiàn)的關(guān)鍵字或詞匯，然后找出其關(guān)聯(lián)或相互關(guān)系關(guān)聯(lián)分析過程文檔預(yù)處理：文本數(shù)據(jù)分解，詞根處理，過濾非用詞等調(diào)用關(guān)聯(lián)挖掘算法將每一文檔看作一個(gè)事務(wù)將文檔中的關(guān)鍵詞組看作事務(wù)中的一組事務(wù)項(xiàng)2022年9月12日34 /72文檔分類動(dòng)機(jī)自動(dòng)對(duì)大量聯(lián)機(jī)文檔（web頁(yè)面，email等）進(jìn)行分類組織，以便于對(duì)文檔進(jìn)行檢索和分析。分類過程數(shù)據(jù)預(yù)處理：提出關(guān)鍵字和詞匯定義訓(xùn)練集和測(cè)試集調(diào)用分類算法創(chuàng)建分類模式測(cè)試分類模式應(yīng)用導(dǎo)出的分類模式對(duì)其他新的、未知的聯(lián)機(jī)文檔分類文檔分類與關(guān)系數(shù)據(jù)庫(kù)中的數(shù)據(jù)分類之間的區(qū)別文檔數(shù)

15、據(jù)庫(kù)是非結(jié)構(gòu)化的，沒有“屬性值”對(duì)2022年9月12日35 /72 Web挖掘挑戰(zhàn)對(duì)數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘而言，Web太龐大了Web頁(yè)面數(shù)據(jù)太復(fù)雜：沒有結(jié)構(gòu)，不標(biāo)準(zhǔn)不斷增長(zhǎng)，不斷變化廣泛的用戶群體僅有很小部分的Web數(shù)據(jù)是有用的或相關(guān)的 99%的Web 信息對(duì)99% 的Web用戶是無(wú)用的2022年9月12日36 /72Web 搜索引擎基于索引: 搜索Web頁(yè)面,對(duì)Web頁(yè)面作索引，建立和存儲(chǔ)大量的基于關(guān)鍵字的索引，定位包含關(guān)鍵字的Web頁(yè)面不足之處：對(duì)任一范圍的話題，返回的文檔數(shù)太龐大很多與話題相關(guān)的文檔并不包含相應(yīng)的關(guān)鍵字（多義問題）2022年9月12日37 /72如何高效地發(fā)現(xiàn)和利用因特網(wǎng)上的

16、資源？Web挖掘2022年9月12日38 /72Web挖掘 Web挖掘可分為三類：Web內(nèi)容挖掘(Web content mining)，Web結(jié)構(gòu)挖掘(Web structure mining)，Web使用記錄的挖掘(Web usage mining)。 2022年9月12日39 /72挖掘Web鏈接結(jié)構(gòu)權(quán)威Web頁(yè)面：不僅相關(guān)，而且高質(zhì)量，或針對(duì)該話題具有權(quán)威性超鏈能夠推斷權(quán)威頁(yè)面Web頁(yè)面包含指向其他頁(yè)面的超鏈超鏈包含了大量人類潛在的注釋超鏈可以看作是作者對(duì)鏈接頁(yè)面的認(rèn)可Web超鏈結(jié)構(gòu)存在的問題并不是每一個(gè)超鏈都代表對(duì)尋找內(nèi)容的認(rèn)可導(dǎo)航、廣告因競(jìng)爭(zhēng)、商業(yè)等原因而不鏈接權(quán)威廣告權(quán)威頁(yè)面很少

17、具有特別的描述2022年9月12日40 /72Web 使用記錄的挖掘Web日志記錄提供了有關(guān)Web動(dòng)態(tài)的豐富信息 典型的Web日志記錄條目包含了所請(qǐng)求的URL，發(fā)出請(qǐng)求的IP地址，時(shí)間戳等在Weblog記錄上可以進(jìn)行數(shù)據(jù)挖掘，用于找出關(guān)聯(lián)模式，序列模式，和Web訪問趨勢(shì)等。 數(shù)據(jù)挖掘的其他方法其他數(shù)據(jù)挖掘方法統(tǒng)計(jì)學(xué)數(shù)據(jù)挖掘數(shù)據(jù)挖掘基礎(chǔ)可視與可聽數(shù)據(jù)挖掘回歸廣義線性模型方差分析混合效應(yīng)模型因素分析判別式分析生存分析數(shù)據(jù)歸約數(shù)據(jù)壓縮概率統(tǒng)計(jì)理論微觀經(jīng)濟(jì)學(xué)觀點(diǎn)模式發(fā)現(xiàn)和歸納數(shù)據(jù)庫(kù)數(shù)據(jù)可視化數(shù)據(jù)挖掘結(jié)果可視化數(shù)據(jù)挖掘過程可視化交互式可視數(shù)據(jù)挖掘聽覺數(shù)據(jù)挖掘統(tǒng)計(jì)學(xué)分析方法在數(shù)據(jù)挖掘中，統(tǒng)計(jì)學(xué)可應(yīng)用于預(yù)測(cè)、聚類規(guī)則挖掘和時(shí)序數(shù)據(jù)的趨勢(shì)分析等。預(yù)測(cè)是數(shù)據(jù)分析的一種重要形式，通過建立連續(xù)值函數(shù)模型，可以預(yù)測(cè)數(shù)據(jù)的未來(lái)變化趨勢(shì)。連續(xù)值的預(yù)測(cè)可以使用統(tǒng)計(jì)學(xué)中的回歸統(tǒng)計(jì)技術(shù)建模，如線性回歸、多元回歸、非線性回歸、廣義線性回歸（對(duì)數(shù)回歸、泊松回歸等）。許多問題可以用線性回歸方法解決，而更多的問題則可以對(duì)變量進(jìn)行變換，使得非線性的問題轉(zhuǎn)換為線性的問題加以處理。統(tǒng)計(jì)學(xué)分析方法預(yù)測(cè)在數(shù)據(jù)屬性之間存在兩種關(guān)系：函數(shù)關(guān)系：能用函數(shù)公式表示的確定性關(guān)系，可以采用回歸分析的方法；相關(guān)關(guān)系：不能用函數(shù)公式表示，但仍是相關(guān)確定的關(guān)系，可以采用相關(guān)分析和主成分