單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,第6章,現(xiàn)代數(shù)據(jù)挖掘技術(shù)與發(fā)展,本章學(xué)習(xí)目標(biāo)：,(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)的體系結(jié)構(gòu),知識發(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è)模式與事實。,知識發(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)評價和知識發(fā)現(xiàn)描述等部分組成（圖,6.1,）。,數(shù)據(jù)倉庫,知識庫,數(shù)據(jù)庫接口,數(shù)據(jù)選擇,知識發(fā)現(xiàn)引擎,知識發(fā)現(xiàn)評價,知識發(fā)現(xiàn)描述,知識發(fā)現(xiàn)管理器,商業(yè)分析員,圖6.1 知識發(fā)現(xiàn)系統(tǒng)結(jié)構(gòu),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)用,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ān)聯(lián)規(guī)則的應(yīng)用目標(biāo),置信度或正確率可以定義為：,(6.5),覆蓋率可以定義為,“興趣度”為目標(biāo)的關(guān)聯(lián)規(guī)則,3.,關(guān)聯(lián)規(guī)則的算法,Apriori算法,1,找出所有支持度大于最小支持度的項集，這些項集稱為頻集，包含,k,個項的頻集稱為,k-,項集。,2,使用第,1,步找到的頻集產(chǎn)生所期望的規(guī)則。,Apriori,算法的第,1,步采用了遞歸方法，算法表示為,L,1,=large 1-itemsets;/,產(chǎn)生頻繁,1,項集,L,1,for(k=2;L,k-1,;k+)do/,循環(huán)產(chǎn)生頻繁,2,項集,L,2,直到某個,r使L,r,為空,begin,C,k,=apriori-gen(L,k-1,);/,產(chǎn)生,k-,項集的候選集,for all transactions t,D do,begin,C,t,=subset(C,k,t);/,事務(wù),t,中包含的候選集,for all candidates c,C,t,do,c.count+;,end,L,k,=c,C,k,|c.count,minsup,end,Answer=U,k,L,k,第,2,步算法較為簡單。如果只考慮規(guī)則的右邊只有一項的情況，給定一個頻集,Y=I,1,I,2,I,3,I,k,k,2,I,j,I,，那么只有包含集合,I,1,I,2,I,3,I,k,中的項的規(guī)則最多有,k,條。這種規(guī)則形如,I,1,I,2,I,3,I,i-1,I,i+1,I,k,I,i,。這些規(guī)則置信度必須大于用戶給定的最小置信度。,數(shù)據(jù)庫D,C,1,L,1,事務(wù)標(biāo)識,項集,項集,支持度,項集,支持度,A1,1,3,4,掃描數(shù)據(jù),庫D,1,2,1,2,A2,2,3,5,2,3,比較,支持度,2,3,A3,1,2,3,5,3,3,3,3,A4,2,5,4,1,5,3,5,3,由,L,1,產(chǎn)生,C,2,C,2,L,2,項集,項集,支持度,項集,支持度,1,2,掃描數(shù)據(jù),庫D,1,2,1,1,2,2,1,3,1,3,2,比較,支持度,2,3,2,1,5,1,5,1,2,5,3,2,3,2,3,2,3,5,2,2,5,2,5,3,3,5,3,5,2,項集,掃描數(shù)據(jù),庫D,項集,支持度,2,3,5,2,3,5,2,由L,2,產(chǎn)生C,3,L,3,4.,關(guān)聯(lián)規(guī)則的應(yīng)用,前件和后件規(guī)則中的正確率和覆蓋率,規(guī)劃覆蓋率和正確率的平衡,前件,后件,正確率,覆蓋率,百吉餅,奶油干酪,80%,5%,百吉餅,橙汁,40%,3%,百吉餅,咖啡,40%,2%,百吉餅,雞蛋,25%,2%,面包,牛奶,35%,30%,黃油,牛奶,65%,20%,雞蛋,牛奶,35%,15%,奶酪,牛奶,40%,8%,規(guī)劃覆蓋率,正確率低,正確率高,覆蓋率高,規(guī)劃很少是正確的，但可以使用,規(guī)劃多數(shù)情況下是正確的，而且可以經(jīng)常使用,覆蓋率低,規(guī)劃很少是正確的，一般不被使用,規(guī)劃多數(shù)情況下是正確的，但很少被使用,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ò)的數(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ò)中，樣本的希望輸出值改為樣本相對各類的希望隸屬度,輸出表達(dá)方面實現(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)整公式修正各權(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)用,47歲,收入6500元,節(jié)點,借貸拖欠？,連接,0.47,0.65,0.39,Weight=0.7,Weight=0.1,年齡,收入,0.47（0.7）+0.65（0.1）0.39,6.2.3,遺傳算法型現(xiàn)代挖掘技術(shù),1.,遺傳算法的基本原理,達(dá)爾文的“適者生存”理論、繼承的信息由基因攜帶、多個基因組成了染色體、基因座、等位基因、基因型和表現(xiàn)型,染色體對應(yīng)的是一系列符號序列，通常用0、1的位串表示,進行生物的遺傳進化。在這一過程中包括三種演化操作：在父代基因群中的雙親選擇操作、兩個父代雙親產(chǎn)生子代基因的交叉操作和在子代基因群體中的變異操作。,兩種數(shù)據(jù)轉(zhuǎn)換：從表現(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),F,R,(a,b,c),F=f(a,b,c),是屬于實數(shù)域,R,的一個實數(shù)，也是每一組解,(a,i,b,i,c,i,),的適應(yīng)度的度量，算法的目標(biāo)是找一個,(a,o,b,o,c,o,),，,使,F=f(a,o,b,o,c,o,),取最大值。,（2）計算當(dāng)前基因群體中所有個體的環(huán)境適合度,（3）用適應(yīng)函數(shù)評價每一個體對環(huán)境的適應(yīng)度,（4）選擇適應(yīng)度好的生物個體進行復(fù)制,（5）選擇適應(yīng)度好的生物個體進行復(fù)制交叉配對繁殖,（6）新生代的變異操作,6.2.3,遺傳算法型現(xiàn)代挖掘技術(shù),編碼并生成祖先群體,計算當(dāng)前基因群體中所有個體的適合度,是否滿足最優(yōu)解條件？,選擇群體中適應(yīng)值高的個體進行復(fù)制,交叉操作,變異操作,終止,6.2.3,遺傳算法型現(xiàn)代挖掘技術(shù),3.,遺傳算法的應(yīng)用,用四個染色體來定義客戶類型：,基因1：客戶的年齡下限,基因2：客戶的年齡上限,基因3：客戶的收入水平,基因4：客戶的人口狀況（人口狀況可以分成：少（1至2人）、一般（3至4人）和多（5人以上）三種狀況）,客戶ID,年齡,累計購買金額,收入,家庭人口,性別,10985,46,1843,中等,4,女,18595,49,0,中等,2,男,47382,61,3628,低,5,男,74912,36,18463,高,6,女,95623,29,8463,高,3,男,85526,32,274,中等,2,男,58753,52,1846,低,2,女,64957,48,0,中等,3,女,76957,27,21634,高,5,男,65839,45,842,低,1,女,6.2.3,遺傳算法型現(xiàn)代挖掘技術(shù),所有的生物個體按順序排放在一張二維表格上，使每個生物體的上、下、左、右都與其它生物體相鄰接。,（1）競爭復(fù)制,（2）雜交繁殖,（3）異變處理,年齡下限,年齡上限,高收入,中等收入,低收入,人口少,人口一般,人口多,客戶群1,38,64,是,是,否,否,是,是,客戶群2,26,50,是,否,是,是,否,是,客戶群3,20,40,否,是,是,是,否,否,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、990327、970230、990211和980304。,客戶編號,贊揚競爭對手的產(chǎn)品否,挑選產(chǎn)品時間很長,距最后一次銷售時間,客戶流失否,970102,否,是,長,是,970230,是,否,長,是,980304,是,是,很長,是,980625,否,是,正常,否,990211,是,否,長,否,990327,否,是,很長,是,6.2.4,粗糙集型現(xiàn)代挖掘技術(shù),因為客戶,970230,已經(jīng)流失，而客戶,990211,沒有流失，由于屬性“贊揚競爭對手的產(chǎn)品”、“,挑選產(chǎn)品時間很長”和“距最后一次銷售時間”是相似的。因此，客戶流失不能以屬性“贊揚競爭對手的產(chǎn)品”、“,挑選產(chǎn)品時間很長”和“距最后一次銷售時間”作為特征進行描述。,而,970230,、,990211,就是邊界實例，即它們不能根據(jù)有效知識進行適