數(shù)據(jù)挖掘原理與SPSS-Clementine應(yīng)用寶典第15章-復(fù)雜對(duì)象數(shù)據(jù)挖掘課件

數(shù)據(jù)挖掘原理與SPSSClementine應(yīng)用寶典元昌安主編鄧松李文敬劉海濤編著電子工業(yè)出版社1Copyright2003-12,SPSSTaiwanCorp.數(shù)據(jù)挖掘原理與SPSSClementine應(yīng)用寶典1Cop第15章復(fù)雜對(duì)象數(shù)據(jù)挖掘

2Copyright2003-12,SPSSTaiwanCorp.第15章復(fù)雜對(duì)象數(shù)據(jù)挖掘2Copyright2003-15.1空間數(shù)據(jù)庫(kù)挖掘

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

15.3文本挖掘15.4挖掘萬維網(wǎng)15.5挖掘數(shù)據(jù)流15.6時(shí)間序列數(shù)據(jù)挖掘15.7挖掘事務(wù)數(shù)據(jù)庫(kù)中的序列模式15.8挖掘生物學(xué)數(shù)據(jù)中的序列模式3Copyright2003-12,SPSSTaiwanCorp.15.1空間數(shù)據(jù)庫(kù)挖掘15.5挖掘數(shù)據(jù)流3Copyri15.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)系

4Copyright2003-12,SPSSTaiwanCorp.15.1空間數(shù)據(jù)庫(kù)挖掘空間數(shù)據(jù)庫(kù)挖掘（SDM）實(shí)15.1.1空間數(shù)據(jù)概述空間數(shù)據(jù)是指與二維、三維或更高維空間的空間坐標(biāo)及空間范圍相關(guān)的數(shù)據(jù)空間數(shù)據(jù)的復(fù)雜性特征有：

空間屬性之間的非線性關(guān)系空間數(shù)據(jù)的多尺度特征空間信息的模糊性空間維數(shù)的增高空間數(shù)據(jù)的缺值5Copyright2003-12,SPSSTaiwanCorp.15.1.1空間數(shù)據(jù)概述5Copyright2003

空間查詢工作

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

空間查詢工作

7Copyright2003-12,SPSSTaiwanCorp.很多基本空間查詢是數(shù)據(jù)挖掘行為的基礎(chǔ)，這些查詢包括：空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型

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

(1)常用的兩個(gè)空間實(shí)體之間的距離有：最小值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)之間的歐氏或曼哈頓距離中最小的，即（15-1）8Copyright2003-12,SPSSTaiwanCorp.15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型空間關(guān)系計(jì)算大值方法：定義實(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ì)算9Copyright2003-12,SPSSTaiwanCorp.大值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)中心方法：定義實(shí)體A和B的距離為A中的中心點(diǎn)與和B中的中心點(diǎn)之間的歐氏或曼哈頓距離的平均值，即(15-4)

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

空間關(guān)系計(jì)算10Copyright2003-12,SPSSTaiwanCorp.中心方法：定義實(shí)體A和B的距離為A中的中心點(diǎn)與和B中的中心點(diǎn)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)都是共有的。11Copyright2003-12,SPSSTaiwanCorp.15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型（2）兩個(gè)空間包含于：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ì)算模型12Copyright2003-12,SPSSTaiwanCorp.包含于：A包含于B，表示A的所有點(diǎn)都在B里，反之不一定。1空間實(shí)體信息模型

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

15Copyright2003-12,SPSSTaiwanCorp.15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型小提示：實(shí)體必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ò)的抽象ACDB16Copyright2003-12,SPSSTaiwanCorp.15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型空間網(wǎng)絡(luò)模型空15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型位置—屬性一體化的空間實(shí)體信息模型

一般空間實(shí)體的形式化模型為一個(gè)四元組，分別代表空間實(shí)體四個(gè)方面的特征。其中位置特征數(shù)據(jù)為

…（15-11）

17Copyright2003-12,SPSSTaiwanCorp.15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型位置—屬性一體化的空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ù)源；第二層是挖掘器；第三層是用戶界面。18Copyright2003-12,SPSSTaiwanCorp.15.1.3空間數(shù)據(jù)挖掘基礎(chǔ)圖15-5空間數(shù)據(jù)挖掘的體系結(jié)構(gòu)19Copyright2003-12,SPSSTaiwanCorp.圖15-5空間數(shù)據(jù)挖掘的體系結(jié)構(gòu)19Copyrigh

空間數(shù)據(jù)挖掘的方法體系空間評(píng)價(jià)?？臻g分類與聚類?？臻g分布計(jì)算?？臻g優(yōu)化?？臻g回歸分析?？臻g動(dòng)態(tài)模擬與預(yù)測(cè)。空間與時(shí)序關(guān)聯(lián)知識(shí)歸納。20Copyright2003-12,SPSSTaiwanCorp.空間數(shù)據(jù)挖掘的方法體系空間評(píng)價(jià)。20C15.1.4幾種空間數(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)行歸納。21Copyright2003-12,SPSSTaiwanCorp.15.1.4幾種空間數(shù)據(jù)挖掘算法空間關(guān)挖掘空間關(guān)聯(lián)規(guī)則的有效方法是自上而下、逐步加深的搜索技術(shù)。首先在高的概念層次進(jìn)行搜索，在較粗的精度級(jí)別查找頻繁發(fā)生的模式和在這些模式中較強(qiáng)的隱含關(guān)系；然后，對(duì)頻繁發(fā)生的模式加深搜索至較低的概念層次，這種處理持續(xù)到找不到頻繁發(fā)生的模式為止?？臻g關(guān)聯(lián)分析22Copyright2003-12,SPSSTaiwanCorp.挖掘空間關(guān)聯(lián)規(guī)則的有效方法是自上而下空間關(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ì)算謂詞。Step5：向低層深入，在多個(gè)概念層次上找到關(guān)聯(lián)規(guī)則的完整集合。23Copyright2003-12,SPSSTaiwanCorp.空間關(guān)聯(lián)分析典型的五步算法：23Copyri空間分類算法和空間趨勢(shì)分析空間分類指分析空間對(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è)決策樹24Copyright2003-12,SPSSTaiwanCorp.空間分類算法和空間趨勢(shì)分析空間分類指分析空間空間決策樹有五個(gè)主要步驟：根據(jù)已知的分類，從數(shù)據(jù)D中找到例子S。確定最佳謂詞p用來分類。一般首先在較粗的層次中尋找相關(guān)謂詞，然后再在較為細(xì)化的層次?？臻g決策樹25Copyright2003-12,SPSSTaiwanCorp.空間決策樹有五個(gè)主要步驟：空間決策樹25Copyright找到最佳的緩沖區(qū)大小和形狀。對(duì)于取樣中的每個(gè)實(shí)體，它周圍的區(qū)域被稱為緩沖區(qū)。目標(biāo)是選擇一個(gè)能產(chǎn)生對(duì)測(cè)試集中的類型進(jìn)行最不同的緩沖區(qū)。使用p和C，對(duì)每個(gè)緩沖區(qū)歸納謂詞。使用泛化的謂詞和ID3建造二叉樹T。26Copyright2003-12,SPSSTaiwanCorp.找到最佳的緩沖區(qū)大小和形狀。對(duì)于取樣中的每個(gè)實(shí)體，它周圍的區(qū)

空間聚類方法

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

空間聚類方法從兩類直至每個(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è)聚類域中.28Copyright2003-12,SPSSTaiwanCorp.空間聚類方法從兩類直至每個(gè)樣本為一類計(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ù)）29Copyright2003-12,SPSSTaiwanCorp.計(jì)算新的聚類中心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á)和解釋比較困難，多媒體挖掘所得出的模式往往比較隱晦。30Copyright2003-12,SPSSTaiwanCorp.15.2多媒體數(shù)據(jù)挖掘15.2.1多媒體數(shù)據(jù)挖掘的特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ù)處理用戶挖掘接口31Copyright2003-12,SPSSTaiwanCorp.15.2.2多媒體數(shù)據(jù)挖掘概述多媒體數(shù)據(jù)挖掘典型系統(tǒng)結(jié)構(gòu)

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

圖像挖掘

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

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

在圖像和視頻數(shù)據(jù)庫(kù)中可以挖掘涉及多媒體對(duì)象的關(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)34Copyright2003-12,SPSSTaiwanCorp.15.2.3多媒體數(shù)據(jù)挖掘方法在圖像和視

多媒體數(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ì)象和小波變換等。35Copyright2003-12,SPSSTaiwanCorp.多媒體數(shù)據(jù)的相似搜索對(duì)多媒體數(shù)據(jù)相似性搜兩種查詢?cè)诨趦?nèi)容的檢索系統(tǒng)中,通常有兩種查詢：基于圖像樣本的查詢（imagesample-basedqueries）。圖像樣本查詢是指找出所有與給定圖像樣本相似的圖像。圖像特征描述查詢(imagefeaturespecificationqueries)。圖像特征描述查詢是指給出圖像的特征描述或概括36Copyright2003-12,SPSSTaiwanCorp.兩種查詢?cè)诨趦?nèi)容的檢索系統(tǒng)中,通常有兩種查詢：36Copy

多媒體數(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í)37Copyright2003-12,SPSSTaiwanCorp.多媒體數(shù)據(jù)的相似搜索

多媒體數(shù)據(jù)的分類和預(yù)測(cè)分析我們也可以對(duì)多媒體數(shù)據(jù)進(jìn)行分類和預(yù)測(cè)分析，尤其用在如天文學(xué)、地震學(xué)、地理科學(xué)等的研究中。分類是多媒體數(shù)據(jù)的一種分析形式,它根據(jù)媒體某一特征(或一組特征)將數(shù)據(jù)分成不同的類。它是一個(gè)兩步過程：第1步，建立一個(gè)模型，用來描述預(yù)定義類集。第2步，使用模型進(jìn)行分類。38Copyright2003-12,SPSSTaiwanCorp.多媒體數(shù)據(jù)的分類和預(yù)測(cè)分析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)行聚類及分類處理，或者是構(gòu)造數(shù)據(jù)的預(yù)測(cè)模型。

39Copyright2003-12,SPSSTaiwanCorp.15.3文本挖掘15.3.1文本挖掘概述39Copy文本挖掘的一般過程文本挖掘的一般過程文本挖掘過程一般包括文本準(zhǔn)備、特征標(biāo)引、特征集縮減、知識(shí)模式的提取、知識(shí)模式的評(píng)價(jià)、知識(shí)模式的輸出等過程

.文本特征標(biāo)引特征集縮減知識(shí)模型的提取知識(shí)模型的評(píng)價(jià)知識(shí)模型的輸出40Copyright2003-12,SPSSTaiwanCorp.文本挖掘的一般過程文本挖掘的一般過程文本特征特征知識(shí)模型知識(shí)

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

特征提取主題標(biāo)引文本分類文本聚類自動(dòng)摘要41Copyright2003-12,SPSSTaiwanCorp.文本挖掘的主要任務(wù)文本挖掘的主要目標(biāo)是獲得

文本挖掘與信息檢索文本的預(yù)處理目前，人們?cè)趯?duì)文本集進(jìn)行自動(dòng)分類、自動(dòng)聚類、自動(dòng)摘要或更深層次的挖掘處理時(shí)常常采用這樣的策略:先用一個(gè)高度概括的向量來表示一篇文本，將文本集概括成一個(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í)的目的。42Copyright2003-12,SPSSTaiwanCorp.文本挖掘與信息檢索文本的預(yù)處理42Cop文本的表示

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

…（15-15）43Copyright2003-12,SPSSTaiwanCorp.文本的表示43Copyright2003-12,SPSS

文本特征標(biāo)引

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

小提示：切分標(biāo)記法的典型代表是非用詞后綴表法。該法將漢字分為“非用字”、“條件用字”、“表內(nèi)用字”、“表外用字”。主要利用“非用字”和“條件用字”進(jìn)行詞語(yǔ)的切分。44Copyright2003-12,SPSSTaiwanCorp.文本特征標(biāo)引所謂標(biāo)

文本維度規(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ù)大大減小的奇異矩陣。

45Copyright2003-12,SPSSTaiwanCorp.文本維度規(guī)約1．基于評(píng)估函數(shù)的方法4

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

文本自動(dòng)分類的一般過程如下：首先，取一個(gè)預(yù)分類的文本集作為訓(xùn)練集。然后，分析訓(xùn)練集以導(dǎo)出分類模型。通常，需要用一個(gè)檢驗(yàn)過程對(duì)該分類模型求精。所導(dǎo)出的分類模型可以用于其它聯(lián)機(jī)文本分類。46Copyright2003-12,SPSSTaiwanCorp.文本的自動(dòng)分類文本分類的典型的分類方法

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

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

該算法的基本思路是:在給定新文本后，考慮在訓(xùn)練文本集中與該新文本距離最近(最相似)的K篇文本，根據(jù)這幾篇文本所屬的類別判定新文本所屬的類別，該算法具體的步驟如下:49Copyright2003-12,SPSSTaiwanCorp.文本分類的典型的分類方法（續(xù)）3．K最近鄰居（KNK最近鄰居（KNN）算法(1).根據(jù)特征項(xiàng)集合重新描述訓(xùn)練文本向量；(2).將新文本表示為特征向量；(3).比較類的權(quán)重，將文本分到權(quán)重最大的那個(gè)類別中

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

….(15-16)50Copyright2003-12,SPSSTaiwanCorp.K最近鄰居（KNN）算法(1).根據(jù)特征項(xiàng)集合重新描述訓(xùn)練(5).在新文本的K個(gè)鄰居中，依次計(jì)算每類的權(quán)重，計(jì)算公式：…..(15-17)其中，為新文本的特征向量，為相似度計(jì)算公式，為類別屬性函數(shù)，即如果屬于類，那么函數(shù)值為1，否則為0。K最近鄰居（KNN）算法51Copyright2003-12,SPSSTaiwanCorp.(5).在新文本的K個(gè)鄰居中，依次計(jì)算每類

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

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

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

54Copyright2003-12,SPSSTaiwanCorp.基于遺傳算法（GA）的文本聚類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)。55Copyright2003-12,SPSSTaiwanCorp.15.4挖掘互聯(lián)網(wǎng)15.4.1挖掘We15.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è)重要資源。56Copyright2003-12,SPSSTaiwanCorp.15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面

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

Web可以用一個(gè)有向圖來表示，G=（V，E），V是頁(yè)面的集合，E是頁(yè)面之間的超鏈接集合。頁(yè)面抽象為圖中的頂點(diǎn)，而頁(yè)面之間的超鏈接抽象為圖中的有向邊。頂點(diǎn)V的入邊表示對(duì)V的引用，出邊表示V引用了其他的頁(yè)面。所以Web頁(yè)面之間的超鏈接揭示了Web結(jié)構(gòu)。57Copyright2003-12,SPSSTaiwanCorp.15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面

鏈接文本（AnchorTexts）可以用來對(duì)被引用的頁(yè)面進(jìn)行索引（例如：Webor,WWW，Google）。超鏈接可以用來計(jì)算頁(yè)面的rankingscore,通過超鏈接可以將一個(gè)頁(yè)面的rankingcore傳遞到相鄰的頁(yè)面。58Copyright2003-12,SPSSTaiwanCorp.15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面

rank的基本思想如下：頁(yè)面被多次引用，則這個(gè)頁(yè)面很可能是重要的。一個(gè)頁(yè)面盡管沒有被多次引用，但被一個(gè)重要頁(yè)面引用，則這個(gè)頁(yè)面很可能是重要的。一個(gè)頁(yè)面的重要性被均分并被傳遞到它所引用的頁(yè)面。59Copyright2003-12,SPSSTaiwanCorp.15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面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ù)挖掘等。60Copyright2003-12,SPSSTaiwanCorp.15.4.2挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面圖像挖掘圖像挖掘（ImageMining）指對(duì)圖形圖像數(shù)據(jù)信息的自動(dòng)處理和知識(shí)發(fā)現(xiàn)，包含模式識(shí)別、圖像檢索以及特征分析等。圖像的空間特性是非常重要的特性，包括圖像中各種對(duì)像的模式、布局、空間層次等。61Copyright2003-12,SPSSTaiwanCorp.挖掘Web鏈接結(jié)構(gòu)識(shí)別權(quán)威Web頁(yè)面圖像挖掘

音頻挖掘音頻挖掘（AudioMining）指對(duì)音頻信息的自動(dòng)處理和分析過程。語(yǔ)音挖掘的另外一個(gè)用途在于將語(yǔ)音對(duì)應(yīng)到個(gè)人62Copyright2003-12,SPSSTaiwanCorp.音頻挖掘音頻挖掘（AudioMini

音頻挖掘

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

63Copyright2003-12,SPSSTaiwanCorp.音頻挖掘63Copyright200

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

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

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

（2）將資源的類型、資源的大小、請(qǐng)求的時(shí)間、在資源上停留的時(shí)間、請(qǐng)求次數(shù)、來自不同Internet域的請(qǐng)求次數(shù)、事件、會(huì)話、錯(cuò)誤次數(shù)作為在這些維變量下的度量變量建立數(shù)據(jù)立方體（DataCube）。（3）利用成熟的數(shù)據(jù)挖掘技術(shù)（如特征、分類、關(guān)聯(lián)、預(yù)測(cè)、時(shí)間序列分析、趨勢(shì)分析）68Copyright2003-12,SPSSTaiwanCorp.15.4.5.３使用記錄挖掘的基本流程68Copyri15.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)重要的。69Copyright2003-12,SPSSTaiwanCorp.15.5挖掘數(shù)據(jù)流為了從數(shù)據(jù)流中發(fā)15.5.1流數(shù)據(jù)處理方法和流數(shù)據(jù)系統(tǒng)

本節(jié)，我們考慮一些常用的大綱數(shù)據(jù)結(jié)構(gòu)和技術(shù)。1．隨機(jī)抽樣一種叫做水庫(kù)抽樣，可以用來無放回的選取一個(gè)無偏的S個(gè)元素的隨機(jī)樣本，沒有更換。水庫(kù)抽樣的想法相對(duì)簡(jiǎn)單。2．滑動(dòng)窗口基本的思想是：僅僅基于最近的數(shù)據(jù)做出決策，而不是對(duì)目前為止看到的所有數(shù)據(jù)或?qū)δ硞€(gè)樣本進(jìn)行計(jì)算。70Copyright2003-12,SPSSTaiwanCorp.15.5.1流數(shù)據(jù)處理方法和流數(shù)據(jù)系統(tǒng)本節(jié)，我們考慮一些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è)部分：終端用戶，查詢處理器和臨時(shí)空間（這可能由主存和磁盤構(gòu)成）。71Copyright2003-12,SPSSTaiwanCorp.15.5.1流數(shù)據(jù)處理方法和流數(shù)據(jù)系統(tǒng)3.直方圖71C流OLAP和流數(shù)據(jù)立方體（續(xù)）1．壓縮時(shí)間尺度的時(shí)間維：傾斜時(shí)間框架

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

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

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

1.數(shù)據(jù)流頻繁模式挖掘2.數(shù)據(jù)流頻繁模式挖掘算法數(shù)據(jù)流頻繁模式挖掘的關(guān)鍵問題就是如何快速對(duì)數(shù)據(jù)流中所出現(xiàn)的模式進(jìn)行計(jì)數(shù)。74Copyright2003-12,SPSSTaiwanCorp.15.5.3數(shù)據(jù)流中的頻繁模式挖掘1.數(shù)據(jù)流頻繁模式數(shù)據(jù)流所出現(xiàn)的模式數(shù)據(jù)流所出現(xiàn)的模式分成三類:

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

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

(3)當(dāng)sup(X)<s時(shí),稱X為非頻繁模式,并在算法中舍棄非頻繁的模式以減少算法的空間復(fù)雜度。75Copyright2003-12,SPSSTaiwanCorp.數(shù)據(jù)流所出現(xiàn)的模式數(shù)據(jù)流所出現(xiàn)的模式分成三類:75Copyr15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類

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

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

76Copyright2003-12,SPSSTaiwanCorp.15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類增量式方法又稱15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類

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

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

77Copyright2003-12,SPSSTaiwanCorp.15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類1.數(shù)據(jù)平穩(wěn)分布的分類方15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類信息增益用于表達(dá)計(jì)算分類到達(dá)該節(jié)點(diǎn)的樣本所需要的信息,其計(jì)算公式為屬性j的熵為,其中

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

VFDT的另一重要性質(zhì)是它所產(chǎn)生的決策樹在大量減少處理樣本數(shù)目的同時(shí),能夠保證和使用全部樣本所產(chǎn)生的決策樹具有無限接近的精度。78Copyright2003-12,SPSSTaiwanCorp.15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類信息增益用于表達(dá)計(jì)算分類到15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類2.數(shù)據(jù)帶概念漂移的分類方法下面介紹各種概念漂移學(xué)習(xí)方法。①FLORA框架

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

79Copyright2003-12,SPSSTaiwanCorp.15.5.4動(dòng)態(tài)數(shù)據(jù)流的分類2.數(shù)據(jù)帶概念漂移的分類方②CVFDT

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

Harries和Sammut基于C4.5開發(fā)了一個(gè)離線學(xué)習(xí)系統(tǒng),該系統(tǒng)將數(shù)據(jù)流分為一個(gè)關(guān)于時(shí)間的“概念聚類”集合。80Copyright2003-12,SPSSTaiwanCorp.②CVFDT80Copyright2003-12,15.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ī)處理81Copyright2003-12,SPSSTaiwanCorp.15.5.5聚類演變數(shù)據(jù)流為了對(duì)數(shù)據(jù)流進(jìn)聚類演變數(shù)據(jù)流

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

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

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

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

82Copyright2003-12,SPSSTaiwanCorp.聚類演變數(shù)據(jù)流已開發(fā)了幾個(gè)算法為聚類數(shù)據(jù)流的算15.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）更新微簇。

83Copyright2003-12,SPSSTaiwanCorp.15.5.5聚類演變數(shù)據(jù)流2.CluStream：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）84Copyright2003-12,SPSSTaiwanCorp.15.6時(shí)間序列數(shù)據(jù)挖掘15.6.1趨勢(shì)分析84Co時(shí)間序列數(shù)據(jù)挖掘“怎樣確定數(shù)據(jù)的趨勢(shì)?”一個(gè)確定的趨勢(shì)的常用方法是用下面的算數(shù)均值序列計(jì)算n階移動(dòng)平均：85Copyright2003-12,SPSSTaiwanCorp.時(shí)間序列數(shù)據(jù)挖掘“怎樣確定數(shù)據(jù)的趨勢(shì)?”一15.6.2時(shí)間序列分析中的相似性搜索

“什么是相似搜索（similaritysearch）？”通常數(shù)據(jù)庫(kù)查詢是要找出符合查詢的精確數(shù)據(jù)，相似搜索與之不同，它是找出與給定查詢序列最接近的數(shù)據(jù)序列。86Copyright2003-12,SPSSTaiwanCorp.15.6.2時(shí)間序列分析中的相似性搜索“什么15.6.2時(shí)間序列分析中的相似性搜索

數(shù)據(jù)變換(datatransformation)：從時(shí)間域(timedomain)到頻率域(frequencydomain)對(duì)時(shí)序數(shù)據(jù)的相似分析，通常采用歐氏距離作為相似計(jì)算的依據(jù)。兩個(gè)常見的獨(dú)立于數(shù)據(jù)的變換是離散傅立葉變換（DFT）和離散小波變（DWT）。87Copyright2003-12,SPSSTaiwanCorp.15.6.2時(shí)間序列分析中的相似性搜索數(shù)據(jù)變換(d15.6.2時(shí)間序列分析中的相似性搜索

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

1．原子匹配（atomicmatching）

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

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

91Copyright2003-12,SPSSTaiwanCorp.15.7挖掘事務(wù)數(shù)據(jù)庫(kù)中的序列模式15.7.1序列模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使得,則稱S1包含于S2,

記作在一個(gè)序列集中,若序列S不包含于任何其它的序列,我們稱S是極大的；在D中,我們可以將某個(gè)顧客的項(xiàng)集按時(shí)間順序排成一個(gè)序列,我們稱這個(gè)序列為這個(gè)顧客的顧客序列；92Copyright2003-12,SPSSTaiwanCorp.15.7挖掘事務(wù)數(shù)據(jù)庫(kù)中的序列模式序列是一個(gè)向量,這個(gè)向若一個(gè)序列包含于某個(gè)顧客的顧客序列中,則稱此顧客支持此序列；支持某序列的顧客數(shù)與總顧客數(shù)之比稱為此序列的支持率；當(dāng)一個(gè)序列的支持率不小于一個(gè)給定的值時(shí),稱這個(gè)序列為頻繁序列；而這個(gè)值稱為最小支持,記作min_sup；序列所擁有的項(xiàng)集個(gè)數(shù)稱為序列的長(zhǎng)度。一個(gè)長(zhǎng)度為k的序列稱為k序列；設(shè)<i>為1序列,I為其中唯一項(xiàng)集。若某客戶支持<i>,則稱此客戶支持項(xiàng)集I；若<i>為頻繁序列,則稱I為頻繁項(xiàng)集。93Copyright2003-12,SPSSTaiwanCorp.若一個(gè)序列包含于某個(gè)顧客的顧客序列中,則稱此顧客支持此序列15.7.2挖掘序列模式的可伸縮方法

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

94Copyright2003-12,SPSSTaiwanCorp.15.7.2挖掘序列模式的可伸縮方法挖掘序列模式的可伸縮方法

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

(1)排序階段

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

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

(4)序列階段

(5)最大序列階段95Copyright2003-12,SPSSTaiwanCorp.挖掘序列模式的可伸縮方法AprioriA15.7.2挖掘序列模式的可伸縮方法

第二類是J.Han等人提出的基于模式增長(zhǎng)的算法，包括FreeSpan算法、PrefixSpan算法等。PrefixSpan(Prefix-projectedequentialPatternMining)算法和FreeSpan算法都是基于模式增長(zhǎng)的挖掘方法。96Copyright2003-12,SPSSTaiwanCorp.15.7.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。97Copyright2003-12,SPSSTaiwanCorp.15.7.3基于約束的序列模式挖掘約15.7.4時(shí)間相關(guān)序列數(shù)據(jù)的周期性分析

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

98Copyright2003-12,SPSSTaiwanCorp.15.7.4時(shí)間相關(guān)序列數(shù)據(jù)的周期性分析“什

周期模式挖掘可以從不同的角度觀察，基于模式覆蓋，可以把模式周期分為三類：挖掘全周期模式（fullperiodicpattern）挖掘部分周期模式(partialperiodicpattern)挖掘循環(huán)或周期關(guān)聯(lián)規(guī)則(cyclicorperiodicassociationrule)99Copyright2003-12,SPSSTaiwanCorp.周期模式挖掘可以從不同的角度觀察，基于模15.8挖掘生物學(xué)數(shù)據(jù)中的序列模式

挖掘生物學(xué)數(shù)據(jù)中的序列模式生物信息學(xué)是一個(gè)充滿活力的新興的研究領(lǐng)域，它將計(jì)算機(jī)技術(shù)應(yīng)用分子生物學(xué)，并開發(fā)新的算法和方法來管理和分析生物學(xué)數(shù)據(jù)。生物學(xué)序列比對(duì)生物序列比對(duì)的問題可以描述如下：對(duì)于給定的兩個(gè)或多個(gè)輸入生物序列，識(shí)別具有長(zhǎng)的恒定子序列的相似序列。100Copyright2003-12,SPSSTaiwanCorp.15.8挖掘生物學(xué)數(shù)據(jù)中的序列模式挖掘生物學(xué)數(shù)據(jù)中的序15.8挖掘生物學(xué)數(shù)據(jù)中的序列模式

雙比對(duì)

有兩個(gè)有影響的啟發(fā)式比對(duì)程序：(1)BLAST(2)FASTA。二者都在查詢序列和目標(biāo)數(shù)據(jù)庫(kù)之間尋找最高得分的局部比對(duì)。它們的基本思想是：首先確定最高得分的短段，然后擴(kuò)展它們得到最優(yōu)比對(duì)。101Copyright2003-12,SPSSTaiwanCorp.15.8挖掘生物學(xué)數(shù)據(jù)中的序列模式雙比對(duì)101C

局部比對(duì)算法BLAST

BLAST算法是Altschul,Gish,Miller等人1990年左右在美國(guó)國(guó)家生物技術(shù)信息中心首先提出的。

BLAST算法通過把比較序列分裂成序列斷片并在這些詞中開始尋找匹配，從而提高查詢的整體速度。102Copyright2003-12,SPSSTaiwanCorp.局部比對(duì)算法BLASTBL

局部比對(duì)算法BLAST多序列比對(duì)方法多序列比對(duì)通常對(duì)氨基酸序列集進(jìn)行，該序列集被認(rèn)為具有相似的結(jié)構(gòu)，其目標(biāo)是發(fā)現(xiàn)所考慮的所有序列中的公共模式。多序列比對(duì)有很多應(yīng)用。103Copyright2003-12,SPSSTaiwanCorp.局部比對(duì)算法BLAST多序列比對(duì)方法首先，這種比對(duì)可能有助于識(shí)別高度恒定的殘基(氨基酸)，它們可能是結(jié)構(gòu)和功能上的基本要素。它可以指導(dǎo)或幫助雙比對(duì)。第二，它將有助于使用恒定的區(qū)域構(gòu)建基因或者蛋白質(zhì)組，形成種系發(fā)生分析(即推斷基因間的進(jìn)化關(guān)系)的基礎(chǔ)。第三，恒定區(qū)域可以用于開發(fā)放大DNA序列的底層和DNA微陣列分析的試樣。

104Copyright2003-12,SPSSTaiwanCorp.首先，這種比對(duì)可能有助于識(shí)別高度恒定的殘基(氨基酸)，它們可15.8.2生物學(xué)序列分析的隱馬爾可夫模型

生物學(xué)家在研究DNA序列時(shí)有兩個(gè)重要的問題：(1)給定一個(gè)短序列，它是否來自CpG島？(2)給定一個(gè)長(zhǎng)序列，能否從中找到所有的CpG島？下面通過介紹馬爾可夫鏈開始考察這些問題。

105Copyright2003-12,SPSSTaiwanCorp.15.8.2生物學(xué)序列分析的隱馬爾可夫模型馬爾可夫鏈

馬爾可夫鏈模型由(a)發(fā)射符號(hào)的狀態(tài)集和(b)一個(gè)狀態(tài)之間的轉(zhuǎn)移集定義。

圖15-9一個(gè)馬爾可夫鏈模型106Copyright2003-12,SPSSTaiwanCorp.馬爾可夫鏈馬爾可夫鏈模型

隱馬爾可夫模型

使用隱馬爾可夫模型的任務(wù)包括：

(1)估計(jì)：給定一個(gè)序列x,確定從模型中獲得x的概率P(x)。

(2)解碼：給定一個(gè)序列，在模型中確定產(chǎn)生序列的最可能的途徑。

(3)學(xué)習(xí)：給定一個(gè)模型和一個(gè)訓(xùn)練序列集，尋找以相對(duì)高的概率來解釋訓(xùn)練序列的模型參數(shù)。

107Copyright2003-12,SPSSTaiwanCorp.隱馬爾可夫模型使用隱馬爾可夫模型的任算法1.前向算法2.維特比算法每一步，維特比算法都嘗試找出從序列中的一個(gè)符號(hào)到另一個(gè)符號(hào)的最可能的路徑。3.Baum-Welch算法

108Copyright2003-12,SPSSTaiwanCorp.算法1.前向算法108Copyright2003-12,15.9本章小結(jié)大量數(shù)據(jù)具有各種各樣的復(fù)雜形式，如結(jié)構(gòu)化或非結(jié)構(gòu)化、超文本和多媒體等?？臻g數(shù)據(jù)挖掘是指從大數(shù)據(jù)量的地理空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)有意義的模式。109Copyright2003-12,SPSSTaiwanCorp.15.9本章小結(jié)大量數(shù)據(jù)具有各種各樣的復(fù)雜形式，如結(jié)構(gòu)化或多媒體數(shù)據(jù)挖掘是指從多媒體數(shù)據(jù)庫(kù)中發(fā)現(xiàn)有意義的模式。時(shí)序數(shù)據(jù)庫(kù)是指由隨時(shí)間變化的值或事件序列組成的數(shù)據(jù)庫(kù)，如股票市場(chǎng)數(shù)據(jù)、商業(yè)交易序列、動(dòng)態(tài)產(chǎn)品處理、醫(yī)療、Web頁(yè)面訪問序列，等等。110Copyright2003-12,SPSSTaiwanCorp.多媒體數(shù)據(jù)挖掘是指從多媒體數(shù)據(jù)庫(kù)中發(fā)現(xiàn)有意義的模式。110C

大量可獲得信息是存儲(chǔ)在文本或文檔數(shù)據(jù)庫(kù)中，它包含了豐富的文檔內(nèi)容，如新聞文章、技術(shù)論文、書籍、數(shù)字圖書館、電子郵件信息和Web頁(yè)面。萬維網(wǎng)作為一個(gè)巨大，廣泛分布的全球信息服務(wù)中心，服務(wù)內(nèi)容涉及新聞、消費(fèi)信息、金融管理、教育、政府、電子商務(wù)和許多其它服務(wù)。111Copyright2003-12,SPSSTaiwanCorp.大量可獲得信息是存儲(chǔ)在文本或文檔數(shù)據(jù)庫(kù)中，它包含了豐富的文數(shù)據(jù)挖掘原理與SPSSClementine應(yīng)用寶典元昌安主編鄧松李文敬劉海濤編著電子工業(yè)出版社112Copyright2003-12,SPSSTaiwanCorp.數(shù)據(jù)挖掘原理與SPSSClementine應(yīng)用寶典1Cop第15章復(fù)雜對(duì)象數(shù)據(jù)挖掘

113Copyright2003-12,SPSSTaiwanCorp.第15章復(fù)雜對(duì)象數(shù)據(jù)挖掘2Copyright2003-15.1空間數(shù)據(jù)庫(kù)挖掘

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

15.3文本挖掘15.4挖掘萬維網(wǎng)15.5挖掘數(shù)據(jù)流15.6時(shí)間序列數(shù)據(jù)挖掘15.7挖掘事務(wù)數(shù)據(jù)庫(kù)中的序列模式15.8挖掘生物學(xué)數(shù)據(jù)中的序列模式114Copyright2003-12,SPSSTaiwanCorp.15.1空間數(shù)據(jù)庫(kù)挖掘15.5挖掘數(shù)據(jù)流3Copyri15.1空間數(shù)據(jù)庫(kù)挖掘

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

115Copyright2003-12,SPSSTaiwanCorp.15.1空間數(shù)據(jù)庫(kù)挖掘空間數(shù)據(jù)庫(kù)挖掘（SDM）實(shí)15.1.1空間數(shù)據(jù)概述空間數(shù)據(jù)是指與二維、三維或更高維空間的空間坐標(biāo)及空間范圍相關(guān)的數(shù)據(jù)空間數(shù)據(jù)的復(fù)雜性特征有：

空間屬性之間的非線性關(guān)系空間數(shù)據(jù)的多尺度特征空間信息的模糊性空間維數(shù)的增高空間數(shù)據(jù)的缺值116Copyright2003-12,SPSSTaiwanCorp.15.1.1空間數(shù)據(jù)概述5Copyright2003

空間查詢工作

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

空間查詢工作

118Copyright2003-12,SPSSTaiwanCorp.很多基本空間查詢是數(shù)據(jù)挖掘行為的基礎(chǔ)，這些查詢包括：空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型

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

(1)常用的兩個(gè)空間實(shí)體之間的距離有：最小值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)之間的歐氏或曼哈頓距離中最小的，即（15-1）119Copyright2003-12,SPSSTaiwanCorp.15.1.2空間數(shù)據(jù)挖掘中的基礎(chǔ)計(jì)算模型空間關(guān)系計(jì)算大值方法：定義實(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ì)算120Copyright2003-12,SPSSTaiwanCorp.大值方法：定義實(shí)體A和B的距離為A中的所有點(diǎn)與和B中的所有點(diǎn)