數(shù)據(jù)挖掘第9章--分類：高級(jí)方法

1、數(shù)據(jù)挖掘與商務(wù)智能范勤勤范勤勤物流研究中心物流研究中心第九章 分類：高級(jí)方法1用后向傳播分類2使用頻繁模式分類3惰性學(xué)習(xí)法1 用后向傳播分類25用后向傳播分類4 神經(jīng)網(wǎng)絡(luò)最早是由心理學(xué)家和神經(jīng)學(xué)家提出 在學(xué)習(xí)階段，通過調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)，使得能夠預(yù)測(cè)輸入樣本的正確類標(biāo)號(hào)來學(xué)習(xí)。由于單元之間的連接，神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)又稱連接者學(xué)習(xí)。 由于人們很難解釋蘊(yùn)涵在學(xué)習(xí)權(quán)之中的符號(hào)含義，神經(jīng)網(wǎng)絡(luò)常常因其可解釋性差而受到批評(píng)。這些特點(diǎn)使得神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘的初期并不看好。 然而，神經(jīng)網(wǎng)絡(luò)的優(yōu)點(diǎn)包括其對(duì)噪音數(shù)據(jù)的高承受能力，以及它對(duì)未經(jīng)訓(xùn)練的數(shù)據(jù)的分類能力。 另外，最近已提出了一些由訓(xùn)練過的神經(jīng)網(wǎng)絡(luò)提取規(guī)則的算法，推

2、動(dòng)了神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘分類方面的應(yīng)用25用后向傳播分類多層前饋神經(jīng)網(wǎng)絡(luò) 多層前饋神經(jīng)網(wǎng)絡(luò)由一個(gè)輸入層、一個(gè)或多個(gè)隱藏層和一個(gè)輸出層組成5輸入層隱藏層輸出層一個(gè)多層前饋神經(jīng)網(wǎng)絡(luò)輸入單元xWij25用后向傳播分類神經(jīng)元及其特性 連接機(jī)制結(jié)構(gòu)的基本處理單元與神經(jīng)生理學(xué)類比往往稱為神經(jīng)元。每個(gè)構(gòu)造起網(wǎng)絡(luò)的神經(jīng)元模型模擬一個(gè)生物神經(jīng)元；61( )()njjiijiytfw xj為神經(jīng)元單元的偏置（閾值），wji為連接權(quán)系數(shù)（對(duì)于激發(fā)狀態(tài)，wji取正值，對(duì)于抑制狀態(tài)，wji取負(fù)值），n為輸入信號(hào)數(shù)目，yj為神經(jīng)元輸出，t為時(shí)間，f()為輸出變換函數(shù)，有時(shí)叫做激發(fā)或激勵(lì)函數(shù) 25用后向傳播分類神經(jīng)元及其特性

3、 輸出變換函數(shù)f（.）的幾種常見形式（a）二值函數(shù)7001, ( )0, xxfxxx（b）S形函數(shù)1( ), 0( )11exfxfxe25用后向傳播分類神經(jīng)元及其特性 輸出變換函數(shù)f（.）的幾種常見形式（c）雙曲線正切函數(shù)81( ), 1( )11exexefxfxe（d）高斯函數(shù)22()2( ), 0( )1xufxefxf(x)x25用后向傳播分類一個(gè)多層神經(jīng)網(wǎng)絡(luò)如何工作？ 網(wǎng)絡(luò)的輸入對(duì)應(yīng)于對(duì)每個(gè)訓(xùn)練元組的觀測(cè)屬性 輸入同時(shí)提供給構(gòu)成輸入層 這些輸入通過輸入層，然后加權(quán)同時(shí)地提供給隱藏層的“類神經(jīng)元的”第二層 隱藏層的數(shù)量是任意的，盡管實(shí)踐中通常只用一層 最后一個(gè)隱藏層的權(quán)重輸出作為構(gòu)

4、成輸出層的單元的輸入。輸出層發(fā)布給定元組的網(wǎng)絡(luò)預(yù)測(cè) 網(wǎng)絡(luò)是前饋的，因?yàn)槠錂?quán)重都不回送到輸入單元，或前一層的輸出單元 從統(tǒng)計(jì)學(xué)角度來講，網(wǎng)絡(luò)進(jìn)行非線性回歸。給定足夠多的隱藏單元和足夠的訓(xùn)練樣本，多層前饋神經(jīng)網(wǎng)絡(luò)可以逼近任意函數(shù)925用后向傳播分類定義網(wǎng)絡(luò)拓?fù)?確定網(wǎng)路拓?fù)浣Y(jié)構(gòu)：說明輸入層的單元數(shù)、隱藏層數(shù)（如果多一層）、每個(gè)隱藏層的單元數(shù)和輸出層的單元數(shù) 規(guī)范化輸入測(cè)量值：對(duì)輸入值規(guī)范化，使其落在0.0與1.0之間。離散值屬性可以重新編碼，使得每個(gè)值域有一個(gè)輸入單元（每個(gè)輸入單元代表一個(gè)屬性的離散值） 一個(gè)輸出單元可以用來表示兩個(gè)類（其中值1代表一個(gè)類，而值0代表另一個(gè)類）。如果多于兩個(gè)類，則每

5、個(gè)類使用一個(gè)輸出單元 對(duì)于“最好的”隱藏層單元數(shù)，沒有明確的規(guī)則確定。一旦網(wǎng)絡(luò)經(jīng)過訓(xùn)練，并且其準(zhǔn)確率不能被接受，則通常使用不同的網(wǎng)絡(luò)拓?fù)浠蚴褂貌煌某跏紮?quán)重集，重復(fù)訓(xùn)練過程1025用后向傳播分類一個(gè)隱藏或輸出單元 一個(gè)隱藏或輸出單元j是來自上一層的輸出。這些與對(duì)應(yīng)的權(quán)重相乘，以形成加權(quán)和。加權(quán)和加到與單元j相關(guān)聯(lián)的偏倚上。一個(gè)非線性的激活函數(shù)用于凈輸入11f加權(quán)和輸入輸出激活函數(shù)權(quán)重w0w1wnx0 x1xnni 0ysign()iijw x例如 偏倚 j25用后向傳播分類黑盒內(nèi)部：后向傳播和可解釋性 神經(jīng)網(wǎng)絡(luò)的主要缺點(diǎn)是其知識(shí)的表示，用加權(quán)鏈連接單元的網(wǎng)絡(luò)表示的知識(shí)讓人很難解釋（采用全連接的

6、方式）靈敏度分析 用于評(píng)估一個(gè)給定的輸入變量對(duì)網(wǎng)絡(luò)輸出的影響。改變?cè)撟兞康妮斎?，而其他輸入變量為某固定值。其間，監(jiān)測(cè)網(wǎng)絡(luò)輸出的改變。由這種形式的分析得到的知識(shí)是形如“IF X減少5% THEN Y增加8%”的規(guī)則方法（提取規(guī)則） step1：網(wǎng)絡(luò)剪枝：剪去對(duì)訓(xùn)練后的網(wǎng)絡(luò)影響最小的加權(quán)鏈，簡(jiǎn)化網(wǎng)絡(luò) step2：將進(jìn)行鏈、單元或活化值聚類，研究輸入 值和活化值的集合，導(dǎo)出描述輸入和隱藏層單元聯(lián)系的規(guī)則。 step3:兩個(gè)規(guī)則的集合結(jié)合在一起，形成IF-THEN規(guī)則。122 使用頻繁模式分類25使用頻繁模式分類頻繁模式 頻繁模式顯示了頻繁地出現(xiàn)在給定數(shù)據(jù)集中的屬性-值對(duì)之間的有趣聯(lián)系。我們可以把每個(gè)

7、屬性-值對(duì)看做一個(gè)項(xiàng)，因此搜索這種頻繁模式稱作頻繁模式挖掘或頻繁項(xiàng)集挖掘1425使用頻繁模式分類關(guān)聯(lián)規(guī)則挖掘 step1：頻繁模式挖掘，搜索反復(fù)出現(xiàn)在數(shù)據(jù)集中的屬性-值對(duì)的模式，其中屬性-值對(duì)看做項(xiàng) step2：規(guī)則產(chǎn)生，分析關(guān)聯(lián)規(guī)則模式，以便產(chǎn)生關(guān)聯(lián)規(guī)則（大于最小支持度或最小置信度） 例：age=youthcredit=ok buys_computer =yessupport=20%,confidence=93%關(guān)聯(lián)規(guī)則分類的步驟 step1：挖掘數(shù)據(jù)，得到頻繁項(xiàng)集，即找出 數(shù)據(jù)中經(jīng)常出現(xiàn)的屬性-值對(duì)。 step2:分析頻繁項(xiàng)集，產(chǎn)生每個(gè)類的關(guān)聯(lián)規(guī)則，它 們滿足置信度和支持度的標(biāo)準(zhǔn)。 ste

8、p3:組織規(guī)則，形成基于規(guī)則的分類器。1525使用頻繁模式分類關(guān)聯(lián)分類的三種方法：CBA、CMAR、CPAR CBA（基于分類的關(guān)聯(lián)）：使用迭代方法挖掘頻繁項(xiàng)集，多遍掃描數(shù)據(jù)集，導(dǎo)出的頻繁項(xiàng)集用來產(chǎn)生和測(cè)試更長(zhǎng)的項(xiàng)集。找出滿足最小置信度和最小支持閾值的規(guī)則的完全集后，然后分析，找出包含在分類器中的規(guī)則。使用一種啟發(fā)式方法構(gòu)造分類器，其中規(guī)則按照它們的置信度和支持度遞減優(yōu)先級(jí)排列。 CMAR（基于多關(guān)聯(lián)規(guī)則的分類）：借助于樹結(jié)構(gòu)有效存儲(chǔ)和檢索規(guī)則，使用多種規(guī)則剪枝策略。CMAR采用FP-growth算法的變形來滿足最小支持度和最小置信度閾值的規(guī)則的完全集。CMAR還使用另一種樹結(jié)構(gòu)來有效的存儲(chǔ)和

9、提取規(guī)則，并根據(jù)置信度、相關(guān)度和數(shù)據(jù)庫的覆蓋率對(duì)規(guī)則剪枝。當(dāng)規(guī)則插入樹時(shí)就觸發(fā)規(guī)則剪枝策略。其基本原理是：如果存在更高置信度的更泛化的版本，則可以減去具有低置信度的更特殊化的規(guī)則。1625使用頻繁模式分類關(guān)聯(lián)分類的三種方法：CBA、CMAR、CPAR CPAR（基于預(yù)測(cè)關(guān)聯(lián)規(guī)則的分類）:采用FOLF的分類規(guī)則產(chǎn)生算法（產(chǎn)生較少的規(guī)則），但是，相比FOLF， CPAR 允許被覆蓋的元組留下并被考慮，但是降低它們的權(quán)重。 與CMAR的區(qū)別：CPAR根據(jù)期望準(zhǔn)確率，使用每組中最好的K個(gè)規(guī)則預(yù)測(cè)X的類標(biāo)號(hào)。通過考慮組中最好的規(guī)則而不是所有的規(guī)則，這避免了較低秩規(guī)則的影響。在大量數(shù)據(jù)集上，CPAR的準(zhǔn)確

10、率與CMAR接近。然而，由于CPAR產(chǎn)生的規(guī)則比CMAR少得多，對(duì)于大型訓(xùn)練數(shù)據(jù)集，CPAR有效的多。1725使用頻繁模式分類單個(gè)特征與頻繁模式18(a) Austral(c) Sonar(b) CleveFig. 1. Information Gain vs. Pattern Length結(jié)論：某些頻繁模式的區(qū)分能力比單個(gè)特征強(qiáng)25使用頻繁模式分類模式頻度（支持度）與信息增益19(a) Austral(c) Sonar(b) BreastFig. 2. Information Gain vs. Pattern Frequency結(jié)論：并非所有頻繁模式都是有用的25使用頻繁模式分類基于有區(qū)別力

11、的頻繁模式分類-刪除區(qū)別能力較弱和冗余的頻繁模式 基于有區(qū)別力的頻繁模式分類的一般框架如下： （1）特征產(chǎn)生：根據(jù)類別號(hào)劃分?jǐn)?shù)據(jù)集D。使用頻繁項(xiàng)集挖掘，發(fā)現(xiàn)每個(gè)分區(qū)中滿足最小支持度的頻繁模式。頻繁模式的集合F形成候選特征。 （2）特征選擇：對(duì)F進(jìn)行特征選擇，得到選擇后的（更有區(qū)別能力的）頻繁模式集Fs。數(shù)據(jù)集D變成D。 （3）學(xué)習(xí)分類模型：在數(shù)據(jù)集D上建立分類器。任何學(xué)習(xí)方法都可以用來建立分類模型。203惰性學(xué)習(xí)法（或從近鄰學(xué)習(xí)）25惰性學(xué)習(xí)法（或從近鄰學(xué)習(xí)）22k -最近鄰分類 所有的訓(xùn)練元組都存放在n維模式空間中 “臨近性”用距離度量，如歐幾里得距離，dist(X1, X2) 目標(biāo)函數(shù)可以

12、是離散的或是實(shí)數(shù)值 對(duì)于k-最近鄰分類，未知元組被指派到它的k個(gè)最近鄰中的多數(shù)類 . _+_xq+_+_+.25惰性學(xué)習(xí)法（或從近鄰學(xué)習(xí)）k -最近鄰分類算法 最近鄰分類用于數(shù)值預(yù)測(cè)，即返回給定未知元組的實(shí)數(shù)值預(yù)測(cè) 分類器返回未知元組的k個(gè)最近鄰的實(shí)數(shù)值標(biāo)號(hào)的平均值 比較的屬性是分類類型而不是數(shù)值類型的：同則差為0，異則差為1。有時(shí)候可以作更為精確的處理，比如黑色與白色的差肯定要大于灰色與白色的差 缺失值的處理：取最大的可能差，對(duì)于分類屬性，如果屬性A的一個(gè)或兩個(gè)對(duì)應(yīng)值丟失，則取差值為1；如果A是數(shù)值屬性，若兩個(gè)比較的元組A屬性值均缺失，則取差值為1，若只有一個(gè)缺失，另一個(gè)值為v，則取差值為1-v和0-v中的最大值 確定k的值：通過實(shí)驗(yàn)確定。進(jìn)行若干次實(shí)驗(yàn)，取分類誤差率最小的k值 最近鄰分類法使用基于距離的比較，本質(zhì)上賦予每個(gè)屬性相等的權(quán)重。當(dāng)數(shù)據(jù)存在噪聲或不相關(guān)屬性時(shí)，它們的準(zhǔn)確率可能會(huì)受到影響2325惰性學(xué)習(xí)法（或從近鄰學(xué)習(xí)）基于案例的推理 基于案例的推理（CBR）分類法使用一個(gè)存放問題解決