1、第6章現(xiàn)代數(shù)據(jù)挖掘技術(shù)與發(fā)展,本章學(xué)習(xí)目標： (1) 通過知識挖掘系統(tǒng)的體系結(jié)構(gòu)的學(xué)習(xí)掌握知識發(fā)現(xiàn)的定義和知識發(fā)現(xiàn)系統(tǒng)的結(jié)構(gòu) 。 (2) 通過現(xiàn)代挖掘技術(shù)及應(yīng)用的學(xué)習(xí)掌握規(guī)則型、神經(jīng)網(wǎng)絡(luò)型、遺傳算法型、粗糙集型和決策樹型現(xiàn)代挖掘技術(shù)。 (3) 通過知識發(fā)現(xiàn)工具與應(yīng)用的學(xué)習(xí)掌握知識挖掘工具的系統(tǒng)結(jié)構(gòu)、運用中的問題和知識挖掘的價值。 (4) 經(jīng)過數(shù)據(jù)挖掘技術(shù)的發(fā)展的學(xué)習(xí)了解文本挖掘、Web挖掘、可視化數(shù)據(jù)挖掘、空間數(shù)據(jù)挖掘和分布式數(shù)據(jù)挖掘。,現(xiàn)代數(shù)據(jù)挖掘技術(shù)與發(fā)展,6.1知識挖掘系統(tǒng)的體系結(jié)構(gòu) 6.2現(xiàn)代挖掘技術(shù)及應(yīng)用 6.3知識發(fā)現(xiàn)工具與應(yīng)用 6.4數(shù)據(jù)挖掘技術(shù)的發(fā)展 練 習(xí),6.1知識挖掘系統(tǒng)

2、的體系結(jié)構(gòu),6.1.1知識發(fā)現(xiàn)的定義 知識發(fā)現(xiàn)是用一種簡潔的方式從大量數(shù)據(jù)中抽取信息的一種技術(shù)，所抽取的信息是隱含的、未知的，并且具有潛在應(yīng)用價值。 知識發(fā)現(xiàn)可看成是一種有價值信息的搜尋過程，它不必預(yù)先假設(shè)或提出問題，仍然能夠找到那些非預(yù)期的令人關(guān)注的信息，這些信息表示了不同研究對象之間的關(guān)系和模式。它還能通過全面的信息發(fā)現(xiàn)與分析，找到有價值的商業(yè)規(guī)則。 知識發(fā)現(xiàn)意味著在數(shù)據(jù)倉庫或數(shù)據(jù)集市的幾千兆、幾萬兆字節(jié)數(shù)據(jù)中尋找預(yù)先未知的商業(yè)模式與事實。 6.1.2 知識發(fā)現(xiàn)系統(tǒng)的結(jié)構(gòu) 知識發(fā)現(xiàn)系統(tǒng)的結(jié)構(gòu)由知識發(fā)現(xiàn)系統(tǒng)管理器、知識庫、商業(yè)分析員、數(shù)據(jù)倉庫的數(shù)據(jù)庫接口、數(shù)據(jù)選擇、知識發(fā)現(xiàn)引擎、知識發(fā)現(xiàn)評價

3、和知識發(fā)現(xiàn)描述等部分組成（圖6.1）。,1.知識發(fā)現(xiàn)系統(tǒng)管理器 控制并管理整個知識發(fā)現(xiàn)過程 2.知識庫和商業(yè)分析員 知識庫包含了源于各方面的知識。商業(yè)分析員要按一種有效的方式指導(dǎo)關(guān)注信息的發(fā)現(xiàn)。 3.數(shù)據(jù)倉庫的數(shù)據(jù)庫接口 知識發(fā)現(xiàn)系統(tǒng)的數(shù)據(jù)庫接口可以直接與數(shù)據(jù)倉庫通信。 4.數(shù)據(jù)選擇 確定從數(shù)據(jù)倉庫中需要抽取的數(shù)據(jù)及數(shù)據(jù)結(jié)構(gòu) 5.知識發(fā)現(xiàn)引擎 將知識庫中的抽取算法提供給數(shù)據(jù)選擇構(gòu)件抽取的數(shù)據(jù) 6.發(fā)現(xiàn)評價 有助于商業(yè)分析員篩選模式，選出那些關(guān)注性的信息 7.發(fā)現(xiàn)描述 發(fā)現(xiàn)、評價并輔助商業(yè)分析員在知識庫中保存關(guān)注性發(fā)現(xiàn)結(jié)果以備將來引用,并保持知識發(fā)現(xiàn)與管理人員的通信。,6.2現(xiàn)代挖掘技術(shù)及應(yīng)用,

4、6.2.1 規(guī)則型現(xiàn)代挖掘技術(shù)及應(yīng)用 1.關(guān)聯(lián)規(guī)則的基本概念,buys(x,“computer”)=buys(x,“finacial_management_software”) age(“30.40”)income(“42000.50000”)=buys(x,“high_resolution_TV”) 布爾關(guān)聯(lián)規(guī)則 量化關(guān)聯(lián)規(guī)則 單維規(guī)則 多維關(guān)聯(lián) 多層關(guān)聯(lián)規(guī)則 單層關(guān)聯(lián)規(guī)則 age(“30.40”)=buys(x,“IBM computer”) (6.3) age(“30.40”)=buys(x,“computer”) (6.4),第2步算法較為簡單。如果只考慮規(guī)則的右邊只有一項的情況，給定

5、一個頻集Y=I1,I2,I3,Ik,k2,IjI，那么只有包含集合 I1,I2,I3,Ik中的項的規(guī)則最多有k條。這種規(guī)則形如I1,I2,I3,Ii-1,Ii+1,IkIi,。這些規(guī)則置信度必須大于用戶給定的最小置信度。,由L2產(chǎn)生C3 L3,4.關(guān)聯(lián)規(guī)則的應(yīng)用,前件和后件規(guī)則中的正確率和覆蓋率 規(guī)劃覆蓋率和正確率的平衡,6.2.2 神經(jīng)網(wǎng)絡(luò)型現(xiàn)代挖掘技術(shù),1.神經(jīng)網(wǎng)絡(luò)及其學(xué)習(xí)方法 神經(jīng)網(wǎng)絡(luò)的工作過程主要分兩個階段：學(xué)習(xí)階段和工作階段。 學(xué)習(xí)方式則有三種：有教師（監(jiān)督）學(xué)習(xí)、無教師（監(jiān)督）學(xué)習(xí)和強化學(xué)習(xí)。,6.2.2 神經(jīng)網(wǎng)絡(luò)型現(xiàn)代挖掘技術(shù),2.基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)挖掘 （1）基于自組織神經(jīng)網(wǎng)絡(luò)

6、的數(shù)據(jù)挖掘技術(shù) 一種無教師學(xué)習(xí)過程 、可以提取一組數(shù)據(jù)中的重要特征或某種內(nèi)在知識 （2）模糊神經(jīng)網(wǎng)絡(luò)類型數(shù)據(jù)挖掘技術(shù) 模糊BP網(wǎng)絡(luò)、模糊Kohonen聚類網(wǎng)絡(luò)、模糊推理網(wǎng)絡(luò)、模糊ART模型等 模糊BP網(wǎng)絡(luò)中，樣本的希望輸出值改為樣本相對各類的希望隸屬度 輸出表達方面實現(xiàn)了模糊化，而且將樣本的隸屬度引入了權(quán)系數(shù)的修正規(guī)則中，使權(quán)系數(shù)的修正規(guī)則也實現(xiàn)了模糊化。,6.2.2 神經(jīng)網(wǎng)絡(luò)型現(xiàn)代挖掘技術(shù),3.后向傳播模型（BP,Back Propagation）及其算法 具體過程如下： 選定p個樣本； 權(quán)值初始化（隨機生成）； 依次輸入樣本； 依次計算各層的輸出； 求各層的反傳誤差； 按權(quán)值調(diào)整公式修正各

7、權(quán)值和閥值； 按新權(quán)值計算各層的輸出，直到誤差小于事先設(shè)定閥值； 變換函數(shù)可以采用這樣幾種： 階躍函數(shù)、S型函數(shù)、比例函數(shù)、符號函數(shù)、飽和函數(shù) 、雙曲函數(shù),6.2.2 神經(jīng)網(wǎng)絡(luò)型現(xiàn)代挖掘技術(shù),4.神經(jīng)網(wǎng)絡(luò)的應(yīng)用,6.2.3 遺傳算法型現(xiàn)代挖掘技術(shù),1.遺傳算法的基本原理 達爾文的“適者生存”理論、繼承的信息由基因攜帶 、多個基因組成了染色體 、基因座、等位基因 、基因型和表現(xiàn)型 染色體對應(yīng)的是一系列符號序列，通常用0、1的位串表示 進行生物的遺傳進化。在這一過程中包括三種演化操作：在父代基因群中的雙親選擇操作、兩個父代雙親產(chǎn)生子代基因的交叉操作和在子代基因群體中的變異操作。 兩種數(shù)據(jù)轉(zhuǎn)換：從表

8、現(xiàn)型到基因型的轉(zhuǎn)換，另一種是從基因型到表現(xiàn)型的轉(zhuǎn)換 遺傳算法實質(zhì)上是一種繁衍、檢測和評價的迭代算法 最大優(yōu)點是問題的最優(yōu)解與初始條件無關(guān)，而且搜索最優(yōu)解的能力極強,6.2.3 遺傳算法型現(xiàn)代挖掘技術(shù),2.遺傳算法的處理過程 （1）編碼并生成祖先群體 要用遺傳算法解決問題，首先要定義有待解決的問題： F=f(a,b,c),FR ,(a,b,c) F=f(a,b,c)是屬于實數(shù)域R的一個實數(shù)，也是每一組解(ai,bi,ci)的適應(yīng)度的度量，算法的目標是找一個(ao ,bo ,co)，使F=f(ao ,bo ,co)取最大值。 （2）計算當前基因群體中所有個體的環(huán)境適合度 （3）用適應(yīng)函數(shù)評價每一個

9、體對環(huán)境的適應(yīng)度 （4）選擇適應(yīng)度好的生物個體進行復(fù)制 （5）選擇適應(yīng)度好的生物個體進行復(fù)制交叉配對繁殖 （6）新生代的變異操作,6.2.3 遺傳算法型現(xiàn)代挖掘技術(shù),6.2.3 遺傳算法型現(xiàn)代挖掘技術(shù),3.遺傳算法的應(yīng)用 用四個染色體來定義客戶類型： 基因1：客戶的年齡下限 基因2：客戶的年齡上限 基因3：客戶的收入水平 基因4：客戶的人口狀況（人口狀況可以分成：少（1至2人）、一般（3至4人）和多（5人以上）三種狀況）,6.2.3 遺傳算法型現(xiàn)代挖掘技術(shù),所有的生物個體按順序排放在一張二維表格上，使每個生物體的上、下、左、右都與其它生物體相鄰接。 （1）競爭復(fù)制 （2）雜交繁殖 （3）異變處

10、理,6.2.4 粗糙集型現(xiàn)代挖掘技術(shù),1粗糙集技術(shù) 2.粗糙集的應(yīng)用 表中的970230、980304、990211客戶的“贊揚競爭對手的產(chǎn)品”屬性是相似的；980304、990327客戶的“挑選產(chǎn)品時間很長”和“客戶流失”屬性是相似的；970230、990211客戶的“贊揚競爭對手的產(chǎn)品”、“ 挑選產(chǎn)品時間很長”和“距最后一次銷售時間”屬性是相似的；這樣，圍繞“贊揚競爭對手的產(chǎn)品”屬性就可以產(chǎn)生兩個初等集合：970230、980304、990211和970102、980625、990327；而“贊揚競爭對手的產(chǎn)品”和“挑選產(chǎn)品時間很長”屬性可以生成三個初等集合：970102、980625、9

11、90327、970230、990211和980304。,6.2.4 粗糙集型現(xiàn)代挖掘技術(shù),因為客戶970230已經(jīng)流失，而客戶990211沒有流失，由于屬性“贊揚競爭對手的產(chǎn)品”、“ 挑選產(chǎn)品時間很長”和“距最后一次銷售時間”是相似的。因此，客戶流失不能以屬性“贊揚競爭對手的產(chǎn)品”、“ 挑選產(chǎn)品時間很長”和“距最后一次銷售時間”作為特征進行描述。 而970230、990211就是邊界實例，即它們不能根據(jù)有效知識進行適當?shù)姆诸悺Ｓ嘞碌目蛻?70102、980304和990327所顯示的特征，可以將他們確定為已經(jīng)流失的客戶。當然，也不能排除970230和990211已經(jīng)流失，而980625毫無疑問

12、沒有流失。 所以客戶集合中“流失”的下近似集合是970102、980304、990327，上近似集合是970102、970230、980304、990211、990327。 同樣，980625沒有流失，但是不能排除970230和990211流失。因此，客戶“沒有流失”概念的下近似是980625，上近似是970230、980625、990211。,6.2.5 決策樹型現(xiàn)代挖掘技術(shù),1決策樹技術(shù) ID3，該算法建立在推理系統(tǒng)和概念學(xué)習(xí)系統(tǒng)的基礎(chǔ)之上，基本步驟是。 （1）創(chuàng)建一個節(jié)點。如果樣本都在同一類，則算法停止，把該節(jié)點改成樹葉節(jié)點，并用該類標記。 （2）否則，選擇一個能夠最好的將訓(xùn)練集分類的屬

13、性，該屬性作為該節(jié)點的測試屬性。 （3）對測試屬性中的每一個值，創(chuàng)建相應(yīng)的一個分支，并據(jù)此劃分樣本。 （4）使用同樣的過程自頂向下的遞歸，直到滿足下面的三個條件中的一個時，就停止遞歸。 (a)給定節(jié)點的所有樣本都屬于同一類。 (b)沒有剩余的屬性可以用來進一步劃分。 (c)繼續(xù)劃分得到的改進不明顯。,6.2.5 決策樹型現(xiàn)代挖掘技術(shù),1決策樹技術(shù) 信息增益被定義為原始分割的熵與劃分以后各分割的熵累加得到的總熵之間的差。 信息增益是指劃分前后進行正確預(yù)測所需的信息量之差。 選擇具有最高信息增益的屬性作為當前節(jié)點的測試屬性。 一個給定的樣本分類所需要的期望信息為 由A劃分成子集的熵或期望信息是,6

14、.2.5 決策樹型現(xiàn)代挖掘技術(shù),1決策樹技術(shù) 為第j個子集的權(quán)，等于子集（A值為aj）中的樣本數(shù)除以S中的樣本數(shù)。對于給定的子集Sj， I(s1j,s2j,smj)可用下式計算 是Sj中的樣本屬于類Ci的概率 由A劃分的信息增益是Gain(A)=I(s1,s2,sm)-E(A),6.2.5 決策樹型現(xiàn)代挖掘技術(shù),2.決策樹的應(yīng)用,6.2.5 決策樹型現(xiàn)代挖掘技術(shù),6.2.5 決策樹型現(xiàn)代挖掘技術(shù),“年齡”在各個屬性中具有最大的信息增益，所以選擇“年齡”屬性作為第一個測試屬性，創(chuàng)建一個節(jié)點，用“年齡”標記。 計算剩余各個屬性的相應(yīng)的信息增益，選擇信息增益最大的屬性作為測試屬性，這時信息增益最大的

15、是“學(xué)生”屬性，創(chuàng)建一個節(jié)點，用“學(xué)生”標記 。,6.3知識發(fā)現(xiàn)工具與應(yīng)用,6.3.1 知識挖掘工具的系統(tǒng)結(jié)構(gòu) 1.無耦合（no coupling） DM系統(tǒng)不利用DB或DW系統(tǒng)的任何功能 2.松散耦合（loose coupling） DM系統(tǒng)將使用DB/DW的某些工具 3.半緊密耦合（semitight coupling） DM系統(tǒng)連接到一個DB/DW系統(tǒng)，一些基本數(shù)據(jù)挖掘原語可以在DB/DW系統(tǒng)中實現(xiàn)。 4.緊密耦合（tight coupling） DM系統(tǒng)被平滑地集成到DB/DW系統(tǒng)中,6.3知識發(fā)現(xiàn)工具與應(yīng)用,6.3.2 知識挖掘工具運用中的問題 1.數(shù)據(jù)挖掘技術(shù)應(yīng)用中的共性問題 (1

16、)數(shù)據(jù)質(zhì)量 (2)數(shù)據(jù)可視化 (3)極大數(shù)據(jù)庫(vLDB)的問題 (4)性能和成本 (5)商業(yè)分折員的技能 (6)處理噪聲和不完全數(shù)據(jù) (7)模式評估興趣度問題,6.3知識發(fā)現(xiàn)工具與應(yīng)用,6.3.2 知識挖掘工具運用中的問題 2.數(shù)據(jù)挖掘技術(shù)應(yīng)用中的個性問題 (1)規(guī)則歸納應(yīng)用中的問題 主要用于顯式描述數(shù)據(jù)抽取的規(guī)則 、找到所有的規(guī)則，工作量是巨大的 (2)神經(jīng)網(wǎng)絡(luò)應(yīng)用中的問題 受訓(xùn)練過度的影響 、神經(jīng)網(wǎng)絡(luò)的訓(xùn)練速度問題 (3)遺傳算法應(yīng)用中的問題,6.3知識發(fā)現(xiàn)工具與應(yīng)用,6.3.3 知識挖掘的價值 1.了解商業(yè)活動 2.發(fā)現(xiàn)商業(yè)異常 3.預(yù)測模型 6.3.4 現(xiàn)代數(shù)據(jù)挖掘工具簡介 1.DB

17、Miner的體系結(jié)構(gòu) 2.DBMiner的數(shù)據(jù)挖掘類型,6.4數(shù)據(jù)挖掘技術(shù)的發(fā)展,6.4.1 文本挖掘 1.文本分析和語義網(wǎng)絡(luò) 文本分析 語義網(wǎng)絡(luò) 2.文本挖掘 文本總結(jié) 基于關(guān)鍵字的關(guān)聯(lián)分析 文檔分類分析 文檔聚類分析 文本挖掘的應(yīng)用,6.4數(shù)據(jù)挖掘技術(shù)的發(fā)展,6.4.2 Web挖掘技術(shù) 1. Web的特點 2. Web內(nèi)容挖掘 基于文本信息的挖掘 基于多媒體信息的挖掘 3.Web結(jié)構(gòu)挖掘 4. Web使用記錄的挖掘 數(shù)據(jù)預(yù)處理階段 模式識別階段 模式分析階段 5.Web數(shù)據(jù)挖掘的應(yīng)用,6.4數(shù)據(jù)挖掘技術(shù)的發(fā)展,6.4.3 可視化數(shù)據(jù)挖掘技術(shù) 1.數(shù)據(jù)的可視化 2.可視化數(shù)據(jù)挖掘技術(shù) 數(shù)據(jù)可

18、視化 數(shù)據(jù)挖掘結(jié)果可視化 數(shù)據(jù)挖掘過程可視化 交互式可視化數(shù)據(jù)挖掘,6.4數(shù)據(jù)挖掘技術(shù)的發(fā)展,6.4.4 空間數(shù)據(jù)挖掘 1.地理信息系統(tǒng) 地理信息系統(tǒng)概念 地理信息系統(tǒng)的特點 2.數(shù)據(jù)挖掘技術(shù)和地理信息系統(tǒng)相結(jié)合 3.地理信息系統(tǒng)的數(shù)據(jù)挖掘特點 圖形化數(shù)據(jù)挖掘 圖形化統(tǒng)計查詢 圖形化報表輸出 專業(yè)的地理分析功能 4.空間數(shù)據(jù)挖掘 5.空間數(shù)據(jù)挖掘用途,6.4數(shù)據(jù)挖掘技術(shù)的發(fā)展,6.4.5 分布式數(shù)據(jù)挖掘 1.分布式數(shù)據(jù)挖掘 2.適合水平式數(shù)據(jù)劃分的分布式挖掘方法,6.4數(shù)據(jù)挖掘技術(shù)的發(fā)展,6.4.5 分布式數(shù)據(jù)挖掘 3.適合垂直式數(shù)據(jù)劃分的分布式數(shù)據(jù)挖掘方法,練 習(xí),1.知識挖掘系統(tǒng)的結(jié)構(gòu)包括哪幾個部分？它們是如何相互配合完成知識發(fā)現(xiàn)的？ 2.現(xiàn)有某企業(yè)的員工數(shù)據(jù)庫，數(shù)據(jù)已經(jīng)概括處理，其中的合計數(shù)為對應(yīng)所給定的部門、職務(wù)、年齡和工資值的人數(shù)。,練 習(xí),