分析技術(shù)分類及模型分析

1、分析技術(shù)分類及模型分析1數(shù)據(jù)預(yù)處理關(guān)聯(lián)分析技術(shù)聚類分析技術(shù)分類分析技術(shù)異常分析技術(shù)影響圖分析技術(shù)及模型數(shù)據(jù)預(yù)處理3數(shù)據(jù)預(yù)處理各種數(shù)據(jù)分析技術(shù)的對象是數(shù)據(jù)源中的數(shù)據(jù)數(shù)據(jù)源中的數(shù)據(jù)可能不完整（如某些屬性的值不確定或空缺）、含噪聲和不一致（如同一個(gè)屬性在不同表中的名稱不同） 、量綱不同如果直接在這些未經(jīng)處理的數(shù)據(jù)上進(jìn)行分析，結(jié)果不一定準(zhǔn)確，效率也可能較低需要使用清理、集成、變換、歸約等預(yù)處理方法改善數(shù)據(jù)質(zhì)量，從而提高數(shù)據(jù)分析的效率與質(zhì)量 主要介紹數(shù)據(jù)清理、集成、變換、規(guī)約等預(yù)處理技術(shù)數(shù)據(jù)清理數(shù)據(jù)清理用于消除噪聲、數(shù)據(jù)不一致及數(shù)據(jù)不完整噪聲可以通過平滑、識(shí)別孤立點(diǎn)等方法進(jìn)行消除分箱技術(shù)：將數(shù)據(jù)排序，根

2、據(jù)等深或等寬分布規(guī)則將數(shù)據(jù)分布到不同箱中，將同一箱中的數(shù)據(jù)用用該箱中數(shù)據(jù)的平均值或中值、邊界值替換（平均值平滑、中值平滑、邊界平滑）每個(gè)箱中的數(shù)據(jù)個(gè)數(shù)或取值區(qū)間相等設(shè)某屬性的值為18，12，3，9，7，6，15，21，16，采用分箱技術(shù)平滑數(shù)據(jù)消除噪聲。分布規(guī)則為等深、深度為3，平滑規(guī)則為平均值平滑 首先，將屬性的值排序?yàn)?, 6, 7, 9, 12, 15, 16, 18, 21箱1：3, 6, 7箱2：9, 12, 15箱3：16, 18, 21箱1：5.3, 5.3, 5.3箱2：12, 12, 12箱3：18.3, 18.3, 18.3數(shù)據(jù)清理數(shù)據(jù)不完整可以使用下列方法消除：1）使用一

3、個(gè)全局常量填充2）使用屬性平均值填充3）使用相同類的屬性平均值填充4）使用最可能的值填充 需要采用預(yù)測算法，預(yù)測給定樣本的最可能的值并填充數(shù)據(jù)不一致可以通過元數(shù)據(jù)消除（描述數(shù)據(jù)的數(shù)據(jù)）數(shù)據(jù)集成數(shù)據(jù)集成是將多個(gè)數(shù)據(jù)源中的數(shù)據(jù)結(jié)合起來存放在一個(gè)一致的數(shù)據(jù)存儲(chǔ)（如數(shù)據(jù)倉庫）中這些數(shù)據(jù)源可能包括多個(gè)數(shù)據(jù)庫、數(shù)據(jù)立方體或一般文件在數(shù)據(jù)集成時(shí)，需要消除冗余能夠由另外的屬性“導(dǎo)出”、命名的不一致的屬性冗余可以通過相關(guān)分析進(jìn)行檢測屬性A、B之間的相關(guān)性計(jì)算：rA,B0，A與B正相關(guān)，A的值隨著B的值的增加而增加rA,B0，A與B負(fù)相關(guān)，A的值隨著B的值的增加而減少rA,B=0，A與B獨(dú)立。因此，|rA,B|很

4、大時(shí)，A與B可以去除一個(gè) 平均值方差數(shù)據(jù)變換將屬性數(shù)據(jù)按比例縮放，使之落入一個(gè)小的特定區(qū)間，如到或到1.0 最小-最大規(guī)格化：minA，maxA為數(shù)值屬性A規(guī)格化前的取值區(qū)間new_ minA，new_ maxA 為A規(guī)格化后的取值區(qū)間，最小-最大規(guī)格化根據(jù)下式將A的值v規(guī)格化為值v采用最小-最大規(guī)格化方法將100，100中的66規(guī)格化到區(qū)間0，1 數(shù)據(jù)變換零-均值規(guī)格化：對均值為 、方差為的數(shù)值屬性A將A的值v規(guī)格化為值v設(shè)某屬性的平均值、標(biāo)準(zhǔn)差分別為80、25，采用零-均值規(guī)格化66 小數(shù)定標(biāo)規(guī)格化 ：數(shù)值屬性A的最大絕對值為max|A|A，j為滿足 的最小整數(shù) 將A的值v規(guī)格化為值v規(guī)格

5、化 100，100中的66A的最大絕對值為120，j為3 數(shù)據(jù)規(guī)約數(shù)據(jù)歸約技術(shù)可以用來得到數(shù)據(jù)集的歸約表示，它小得多，但仍接近于保持原數(shù)據(jù)集的完整性在歸約后的數(shù)據(jù)集上分析將更有效，并產(chǎn)生相同（或幾乎相同）的分析結(jié)果歸約方法主要有：屬性歸約 、記錄歸約 屬性規(guī)約：刪除不相關(guān)的或冗余的屬性減小數(shù)據(jù)集，目標(biāo)是找出最小屬性集， 使得數(shù)據(jù)在其上的概率分布盡可能地接近在原屬性集上的概率分布 常用方法：粗糙集中的屬性約簡、決策樹記錄規(guī)約：用少量記錄代表或替換原有記錄，從而減小數(shù)據(jù)集常用方法： 抽樣、數(shù)據(jù)概化數(shù)據(jù)規(guī)約數(shù)據(jù)概化：采用面向?qū)傩詺w納，根據(jù)屬性的概念分層，通過閾值控制，將屬性的低層屬性值用相應(yīng)高層概念

6、替換，并合并由此得到的相同記錄 概念分層一般用樹結(jié)構(gòu)描述，稱為概念層次樹閾值控制面向?qū)傩詺w納過程，每個(gè)屬性都有概念層次樹及閾值首先根據(jù)屬性A的概念層次樹，將關(guān)系表中A的屬性值轉(zhuǎn)換為最低層的相應(yīng)概念（葉概念），統(tǒng)計(jì)關(guān)系表中A的不同葉概念個(gè)數(shù)如果A的不同葉概念個(gè)數(shù)大于A的屬性閾值，再根據(jù)A的概念層次樹，將關(guān)系表中A的葉概念轉(zhuǎn)換為上一層的相應(yīng)概念如此重復(fù)，直至關(guān)系表中A的不同概念個(gè)數(shù)小于等于A的屬性閾值；最后合并相同記錄，并統(tǒng)計(jì)重復(fù)記錄數(shù)目數(shù)據(jù)規(guī)約屬性閾值均為4記錄由6個(gè)歸約為3個(gè)count的值表示重復(fù)記錄數(shù)目屬性概念分層的自動(dòng)生成 概念分層一般由系統(tǒng)用戶、領(lǐng)域?qū)＜姨峁浅：臅r(shí)、乏味介紹離散屬性

7、與連續(xù)屬性自動(dòng)生成概念分層的方法 離散屬性概念分層的自動(dòng)生成 概念層次樹中高層的概念個(gè)數(shù)一般少于低層的概念個(gè)數(shù)首先統(tǒng)計(jì)各個(gè)概念的不同值個(gè)數(shù)，個(gè)數(shù)最少的概念在最高層，依次類推，然后根據(jù)結(jié)構(gòu)的從屬關(guān)系，確定各層的概念及從屬關(guān)系 地址國家省市中國云南省昆明市中國云南省大理市中國四川省成都市中國貴州省貴陽市中國云南省玉溪市中國云南省曲靖市屬性概念分層的自動(dòng)生成 連續(xù)屬性概念分層的自動(dòng)生成 連續(xù)屬性可以通過離散化遞歸地自動(dòng)生成概念分層離散化可以基于熵完成，主要步驟：1）計(jì)算關(guān)系表r中在屬性A的取值區(qū)間V上的記錄集合S的熵 |c|：S中屬于目標(biāo)類c的記錄數(shù)|S|：S中的記錄數(shù) 2）對A在V上取的每個(gè)v，用

8、v劃分V為v1（v）、v2（v），劃分S為S1，S2，計(jì)算在此劃分下S的熵 E(S1)、E(S2)分別為S1、S2的熵 屬性概念分層的自動(dòng)生成 連續(xù)屬性概念分層的自動(dòng)生成 3）對在V上的每個(gè)劃分v1（v）、v2（v），計(jì)算在此劃分下S的信息增益 4）選擇使S的信息增益最大的劃分作為最佳劃分，記為V1（T）、V2（T）（T是使S的信息增益最大的v）5）遞歸地應(yīng)用步驟1）4）于V1、V2及S1、S2上，直至滿足一定的結(jié)束條件，例如，最大信息增益小于某個(gè)閾值 屬性A的取值區(qū)間V作為其概念層次樹的根，形成最高層第一次劃分區(qū)間V1、V2是根的兩個(gè)子結(jié)點(diǎn)，形成次高層遞歸地應(yīng)用步驟1）4）就可以得到各層結(jié)點(diǎn)

9、屬性概念分層的自動(dòng)生成 連續(xù)屬性概念分層的自動(dòng)生成 設(shè)“氣溫”屬性是目標(biāo)屬性，取值區(qū)間為100,100屬性值及記錄數(shù)如表所示屬性值36182226記錄數(shù)69362821劃分區(qū)間100,100屬性概念分層的自動(dòng)生成 連續(xù)屬性概念分層的自動(dòng)生成 屬性值36182226記錄數(shù)69362821劃分區(qū)間100,100G(100, 100, 2.0378=0G(G(G(G(最佳劃分：V1=100, 22) (llu)不是強(qiáng)關(guān)聯(lián)規(guī)則，則規(guī)則lv=(llv)也不是強(qiáng)關(guān)聯(lián)規(guī)則 證明： sup_count(lv)sup_count(lu)i1i2 i5不是強(qiáng)關(guān)聯(lián)規(guī)則i2i1i5、 i1i2i5都不可能是強(qiáng)關(guān)聯(lián)規(guī)則

10、l=i1i2i5lvi1、i2lui1i2Apriori算法壓縮強(qiáng)關(guān)聯(lián)搜索空間對于每個(gè)頻繁項(xiàng)集，第一層產(chǎn)生后件只有一項(xiàng)的強(qiáng)關(guān)聯(lián)規(guī)則，并生成它們的1-后件集合R1第二層產(chǎn)生后件有兩項(xiàng)的強(qiáng)關(guān)聯(lián)規(guī)則，并生成它們的2-后件集合R2R2通過R1中的后件進(jìn)行連接運(yùn)算，再通過置信度計(jì)算產(chǎn)生依次類推，可以產(chǎn)生所有強(qiáng)關(guān)聯(lián)規(guī)則Apriori算法算法描述輸入：事務(wù)集合T，最小支持度閾值min_sup，最小置信度閾值min_conf輸出：強(qiáng)關(guān)聯(lián)規(guī)則集合SR變量：頻繁k-項(xiàng)集集合Lk，候選k-項(xiàng)集集合Ck，頻繁項(xiàng)集集合L，k-后件集合Rk步驟：/頻繁項(xiàng)集產(chǎn)生（1）for T中的每個(gè)事務(wù)t （）for t中的每個(gè)項(xiàng)i （

11、）=+1 /1-項(xiàng)集支持計(jì)數(shù)（2）for 每個(gè)項(xiàng)i （）if nmin_sup then L1=L1i /找出頻繁1-項(xiàng)集Apriori算法算法描述（3）for (k=2；Lk-1；k+) （）for Lk-1中的每個(gè)項(xiàng)集lu （）for Lk-1中項(xiàng)集lu之后的每個(gè)項(xiàng)集lv if (lu1=lv1)(luk-2=lvk-2)(luk-1lvk-1) then /連接 Ck=Ckc /找出候選k-項(xiàng)集 for c中的每個(gè)(k-1)-項(xiàng)集s if then Ck=Ck-c /剪枝 （）for T中的每個(gè)事務(wù)t （）for t中的每個(gè)k-項(xiàng)集s if sCk then =+1 /k-項(xiàng)集支持計(jì)數(shù)A

12、priori算法算法描述 （）for Ck中的每個(gè)項(xiàng)集c （）if nmin_sup then Lk=Lkc /找出頻繁k-項(xiàng)集 （） L=LLk /規(guī)則產(chǎn)生（4）for L中的每個(gè)頻繁項(xiàng)集l （）for l中的每個(gè)1-項(xiàng)集l1 （） if then SR=SR(l-l1)=l1 /找出后件只有1項(xiàng)的強(qiáng)關(guān)聯(lián)規(guī)則 R1=R1l1 /找出1-后件 Apriori算法算法描述（）for (j=2；Rj-1；j+) （）for Rj-1中的每個(gè)后件lu for Rj-1中后件lu之后的每個(gè)后件lv if (lu1=lv1)(luj-2=lvj-2)(luj-1lvj-1) then /連接 if th

13、en SR=SR(l-lj)=lj /找出后件有j項(xiàng)的強(qiáng)關(guān)聯(lián)規(guī)則 Rj=Rjlj /找出j-后件l=i1i2i5lui1lvi2Apriori算法影響Apriori算法時(shí)間復(fù)雜度主要因素（1）事務(wù)集合當(dāng)項(xiàng)數(shù)m增加：候選項(xiàng)集的數(shù)目和長度可能增加，頻繁項(xiàng)集的數(shù)目和長度也可能增加，從而計(jì)算頻繁項(xiàng)集及其支持計(jì)數(shù)的時(shí)間、掃描事務(wù)集合的次數(shù)、計(jì)算強(qiáng)關(guān)聯(lián)規(guī)則的時(shí)間可能增加事務(wù)數(shù)n、事務(wù)平均寬度w增加：每次掃描事務(wù)集合的時(shí)間增加（2）最小支持度閾值min_supmin_sup越小，候選項(xiàng)集和頻繁項(xiàng)集的數(shù)目越多、長度越長，掃描事務(wù)集合的次數(shù)越多，算法的運(yùn)行時(shí)間越長（3）最小置信度閾值min_confmin_co

14、nf越小，強(qiáng)關(guān)聯(lián)規(guī)則的數(shù)目越多，產(chǎn)生規(guī)則的運(yùn)行時(shí)間越長頻繁項(xiàng)集的緊湊表示 通常，從現(xiàn)實(shí)事務(wù)集合中產(chǎn)生的頻繁項(xiàng)集的數(shù)量龐大為了提高關(guān)聯(lián)規(guī)則挖掘算法的效率，頻繁項(xiàng)集使用緊湊表示最大頻繁項(xiàng)集：一個(gè)頻繁項(xiàng)集的所有直接超集都不是頻繁項(xiàng)集由最大頻繁項(xiàng)集可以推導(dǎo)所有頻繁項(xiàng)集 頻繁項(xiàng)集非頻繁項(xiàng)集最大頻繁項(xiàng)集由 ad可以推導(dǎo)頻繁項(xiàng)集a、d和ad由bcd可以推導(dǎo)b、c、d、bc、bd、cd和bcd 頻繁項(xiàng)集的緊湊表示 為了高效找出最大頻繁項(xiàng)集，可以將搜索空間按前綴或后綴變換為樹（前綴樹、后綴樹 ），然后采用寬度或深度優(yōu)先策略進(jìn)行搜索前綴樹后綴樹頻繁項(xiàng)集的緊湊表示 寬度優(yōu)先是先搜索同一層的頻繁項(xiàng)集，再搜索下一層的頻

15、繁項(xiàng)集 深度優(yōu)先是搜索到某層的一個(gè)頻集時(shí)，先搜索更深層的頻集，若沒有頻集則回溯，直至沒有頻項(xiàng)集產(chǎn)生也沒有回溯 深度優(yōu)先搜索策略可以更快地檢測到頻繁項(xiàng)集邊界，通常用于搜索最大頻繁項(xiàng)集 深度優(yōu)先與最大頻繁項(xiàng)集搜索頻繁項(xiàng)集的緊湊表示 最大頻繁項(xiàng)集集合是頻繁項(xiàng)集集合的緊湊表示由最大頻繁項(xiàng)集可以推導(dǎo)所有頻繁項(xiàng)集，但由最大頻繁項(xiàng)集不能推導(dǎo)它們的支持計(jì)數(shù)閉項(xiàng)集：一個(gè)項(xiàng)集的所有直接超集的支持計(jì)數(shù)都不等于該項(xiàng)集的支持計(jì)數(shù)頻繁閉項(xiàng)集：一個(gè)項(xiàng)集是頻繁項(xiàng)集并且是閉項(xiàng)集最小支持計(jì)數(shù)閾值是5 頻繁項(xiàng)集的緊湊表示 定理 對于頻繁項(xiàng)集l及其所有直接超集li=li(iI)，如果l是最大頻繁項(xiàng)集，則l是頻繁閉項(xiàng)集 sup_cou

16、nt(l) nmin_sup 證明： 定理 對于頻繁項(xiàng)集l及其所有直接超集li=li(iI)，如果l不是閉項(xiàng)集，則 證明： 基于該定理，頻繁非閉項(xiàng)集的支持計(jì)數(shù)可以通過頻繁閉項(xiàng)集的支持計(jì)數(shù)確定頻繁項(xiàng)集的緊湊表示 項(xiàng)集c不是閉項(xiàng)集，它的支持計(jì)數(shù)等于項(xiàng)集bc的支持計(jì)數(shù) 頻繁項(xiàng)集、頻繁閉項(xiàng)集與最大頻繁項(xiàng)集的關(guān)系 ： 頻繁項(xiàng)集的緊湊表示通過頻繁閉項(xiàng)集的支持計(jì)數(shù)計(jì)算其它頻繁非閉項(xiàng)集的支持計(jì)數(shù)的算法描述輸入：頻繁閉項(xiàng)集集合CL輸出：頻繁項(xiàng)集集合L步驟：（1） /找出頻繁閉項(xiàng)集的最大長度（2） /找出最長頻繁閉項(xiàng)集（3） /最長頻繁閉項(xiàng)集也是最長頻繁項(xiàng)集（4）for (k=kmax-1；k1；k-) /找出所

17、有頻繁項(xiàng)集 （） /找出由頻繁閉(k+1)-項(xiàng)集推導(dǎo)的頻繁k-項(xiàng)集 （）CLk=l|lCL,|l|=k /找出頻繁閉k-項(xiàng)集頻繁項(xiàng)集的緊湊表示通過頻繁閉項(xiàng)集的支持計(jì)數(shù)計(jì)算其它頻繁非閉項(xiàng)集的支持計(jì)數(shù)的算法描述（）for TLk中每個(gè)項(xiàng)集 /計(jì)算頻繁非閉k-項(xiàng)集的支持計(jì)數(shù) （）if then Lk= Lkl（） Lk= LkCLk（）L=LLk頻繁項(xiàng)集的緊湊表示最小支持計(jì)數(shù)閾值是5，項(xiàng)集b:9、ad:5、bc:7、bd:6和bcd:5是頻繁閉項(xiàng)集。寫出計(jì)算頻繁非閉項(xiàng)集的支持計(jì)數(shù)的過程 L3 = CL3 = bcd TL2 = bc,bd,cd CL2 = ad,bc,bd cd.sup_count

18、 = bcd.sup_count = 5 L2 = ad,bc,bd,cd TL1 = a,b,c,d CL1 = b a.sup_count = ad.sup_count = 5 c.sup_count = bc.sup_count = 7 d.sup_count = bd.sup_count = 6 L1 = a,b,c,dFP-growth算法 Apriori算法的不足：1）可能產(chǎn)生大量候選項(xiàng)集2）可能需要重復(fù)掃描數(shù)據(jù)庫，通過模式匹配檢查龐大的候選集合FP-growth算法采用一種稱為FP樹的結(jié)構(gòu)表示事務(wù)集合中項(xiàng)集的關(guān)聯(lián)，并在FP樹上遞歸地找出所有頻繁項(xiàng)集，算法并不產(chǎn)生候選基本思想：掃描

19、一次事務(wù)集合，找出頻繁1-項(xiàng)集合L1基于L1，再掃描一次事務(wù)集合，構(gòu)造表示事務(wù)集合中項(xiàng)集關(guān)聯(lián)的FP樹在FP樹上遞歸地找出所有頻繁項(xiàng)集最后在所有頻繁項(xiàng)集中產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則 FP-growth算法 1）掃描一次事務(wù)集合，找出頻繁1-項(xiàng)集合L，并按支持計(jì)數(shù)降序排序L中的頻繁項(xiàng)FP樹構(gòu)造 事務(wù)項(xiàng)t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3min_sup=20% L=i2:7, i1:6, i3:5, i4:2, i5:2 2）創(chuàng)建FP樹的根節(jié)點(diǎn)，用“null”標(biāo)記nullFP-growth算法 3）

20、再掃描一次事務(wù)集合，對每個(gè)事務(wù)找出其中的頻繁項(xiàng)并按L中的順序排序，為每個(gè)事務(wù)創(chuàng)建一個(gè)分枝，事務(wù)分枝路徑上的節(jié)點(diǎn)就是該事務(wù)中的已排序頻繁項(xiàng)對于各個(gè)事務(wù)分枝，如果可以共享路徑則共享并且在各個(gè)節(jié)點(diǎn)上記錄共享事務(wù)數(shù)目FP樹構(gòu)造 事務(wù)項(xiàng)t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3L=i2:7, i1:6, i3:5, i4:2, i5:2 FP-growth算法 FP樹構(gòu)造 事務(wù)項(xiàng)t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，

21、i2，i5t9i1，i2，i3L=i2:7, i1:6, i3:5, i4:2, i5:2 4）為方便遍歷FP樹，為FP樹創(chuàng)建一個(gè)項(xiàng)表項(xiàng)表中每一行表示一個(gè)頻繁項(xiàng)，并有一個(gè)指針指向它在FP樹中的節(jié)點(diǎn)FP樹中相同頻繁項(xiàng)的節(jié)點(diǎn)通過指針連成鏈表 FP-growth算法 FP樹構(gòu)造 事務(wù)項(xiàng)t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3FP-growth算法 由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基。然后，構(gòu)造它的條件FP樹，并遞歸地在該樹上進(jìn)行挖掘。模式增長通過后綴模式與由條件FP

22、樹產(chǎn)生的頻繁模式連接實(shí)現(xiàn)條件模式基：一個(gè)“子數(shù)據(jù)庫”，由FP樹中與后綴模式一起出現(xiàn)的前綴路徑集組成條件FP樹：條件模式基中，由滿足最小支持度閾值的節(jié)點(diǎn)構(gòu)成的樹FP樹挖掘i5:2的條件模式基null,i2,i1:2 i5:2 與條件FP樹 FP-growth算法 遞歸過程：1）如果條件FP樹只有一個(gè)分枝，則分枝路徑上的節(jié)點(diǎn)的一個(gè)組合就是一個(gè)前綴模式，一個(gè)前綴模式與后綴模式產(chǎn)生一個(gè)頻繁項(xiàng)集（遞歸出口）2）否則用L中的頻繁項(xiàng)i增長后綴模式 （i ，增長時(shí)，按逆序方式處理，即先考慮L的最后一項(xiàng)），然后構(gòu)造增長后綴模式i 的條件模式基與條件FP樹，遞歸上述過程初始時(shí)，=null，null的條件FP樹就是

23、FP樹FP樹挖掘FP-growth算法 第二層遞歸：FP樹挖掘條件模式基條件FP樹產(chǎn)生的頻繁項(xiàng)集i5:2null,i2,i1:2i2i5:2、i1i5:2、i2i1i5:2i4:2null,i2,i1:1、null,i2:1i2i4 :2i3:5null,i2,i1:1、null,i2:2、null,i1:2、i1:6null,i2:4、null:2i2i1 :4i2:7null:7第一層遞歸：=nullnull的條件FP樹有多個(gè)分枝，進(jìn)入第二層遞歸i3:5的條件FP樹有兩個(gè)分枝，進(jìn)入第三層遞歸 FP-growth算法 第三層遞歸：FP樹挖掘條件模式基條件FP樹產(chǎn)生的頻繁項(xiàng)集i1i3:3nul

24、l,i2:1、null:2i1i3:3i2i3:3null:3i2i3:3FP-growth算法 輸入：事務(wù)集合T，最小支持度閾值min_sup，最小置信度閾值min_conf輸出：強(qiáng)關(guān)聯(lián)規(guī)則集合R_S步驟：（1）掃描T找出頻繁1-項(xiàng)集合L（2）L中的項(xiàng)按支持計(jì)數(shù)降序排序（3）創(chuàng)建FP樹的根節(jié)點(diǎn)null /創(chuàng)建FP樹（4）for T中的每個(gè)事務(wù)t （）找出t中的頻繁1-項(xiàng)集合Lt （）Lt中的項(xiàng)按L中的順序排序 （）Insert-FP（Lt, null） /創(chuàng)建事務(wù)分枝（5）L_S=Search-FP（FP, null） /找出所有頻繁項(xiàng)集（6）在L_S中產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則集合R_S算法描述FP-

25、growth算法 算法：Insert-FP算法（Li, Tr）輸入：已排序頻繁1-項(xiàng)集合Li，F(xiàn)P（子）樹的根節(jié)點(diǎn)Tr輸出：FP樹（1）if Li不空 then （）取出Li中的第1個(gè)項(xiàng)i （）if Tr的某個(gè)子節(jié)點(diǎn)Node是i then （）=+1 （）else （）創(chuàng)建Tr的子節(jié)點(diǎn)Node為i （）=1 （）將Node加入項(xiàng)表鏈中（）Insert-FP（Li-i, Node）算法描述FP-growth算法 算法：Search-FP算法（T，）輸入：（條件）FP樹T，后綴模式輸出：頻繁項(xiàng)集集合L_S（1）if T中只有一個(gè)分枝P then （）for P上的節(jié)點(diǎn)的每個(gè)組合 （）= /產(chǎn)生頻繁

26、項(xiàng)集 （）L_S= L_S（2）else （）for T中的每個(gè)頻繁項(xiàng)i （）=i /增長后綴模式 （）構(gòu)造的條件模式基及其條件FP樹T （） Search-FP（T, ）算法描述分析技術(shù)及模型聚類分析65將物理或抽象對象的集合分成相似的對象類的過程使得同一個(gè)簇中的對象之間具有較高的相似性，而不同簇中的對象具有較高的相異性是數(shù)據(jù)挖掘、模式識(shí)別等研究方向的重要研究內(nèi)容之一，在識(shí)別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面具有極其重要的作用 廣泛應(yīng)用于模式識(shí)別、數(shù)據(jù)分析、圖像處理和市場研究等領(lǐng)域，對生物學(xué)、心理學(xué)、考古學(xué)、地質(zhì)學(xué)及地理學(xué)等研究也有重要作用 主要介紹聚類概念、聚類過程、常用聚類算法 聚類分析=o1, o2,

27、 , on表示一個(gè)對象集合oi表示第i個(gè)對象，i=1, 2,nCx表示第x個(gè)簇，Cx，x=1，2，kSimilarity(oi, oj)表示對象oi與對象oj之間的相似度若各簇Cx是剛性聚類結(jié)果，則各Cx需滿足如下條件：1）2）對于 有3）聚類分析的形式描述數(shù)據(jù)準(zhǔn)備屬性選擇屬性提取聚類結(jié)果評估聚類過程為聚類分析準(zhǔn)備數(shù)據(jù)，包括屬性值標(biāo)準(zhǔn)化從最初的屬性中選擇最有效的屬性通過對所選擇的屬性進(jìn)行轉(zhuǎn)換形成新的更有代表性的屬性度量對象間的相似性程度，執(zhí)行聚類或分組 聚類分析的三要素是相似性測度、聚類準(zhǔn)則和聚類算法聚類分析中的數(shù)據(jù)類型聚類分析中常用的數(shù)據(jù)類型有：數(shù)據(jù)矩陣、相異度矩陣1）數(shù)據(jù)矩陣：對象在多維空

28、間中通常表示為點(diǎn)（向量），其每一維表示為不同屬性，這些屬性描述出對象數(shù)據(jù)矩陣每行代表一個(gè)對象，每列代表對象的一個(gè)屬性2）相異度矩陣：存儲(chǔ)n個(gè)對象兩兩之間的近似性，d(i,j)是對象i和對象j之間相異性的量化表示聚類分析三要素相似性測度、聚類準(zhǔn)則和聚類算法相似性測度：衡量同簇對象的類似性和不同簇對象的差異性 聚類準(zhǔn)則：評價(jià)聚類結(jié)果的好壞 聚類算法：用于找出使準(zhǔn)則函數(shù)取極值的最好聚類結(jié)果 實(shí)際上，確定了相似性測度和聚類準(zhǔn)則后，聚類就變成了使準(zhǔn)則函數(shù)取極值的優(yōu)化問題了 沒有任何一種聚類算法可以普遍適用于揭示各種多維數(shù)據(jù)集所呈現(xiàn)出來的多種多樣的結(jié)構(gòu) 因此聚類算法有多種，不同的聚類算法使用不同的相似性度

29、量和準(zhǔn)則對象之間的相似性根據(jù)描述對象的屬性值評估，可以使用距離、密度、連通性或概念度量距離相似性度量：距離越近越相似，不同簇中任意兩個(gè)對象間的距離都大于簇內(nèi)任意兩個(gè)對象之間的距離 密度相似性度量：密度（單位區(qū)域內(nèi)的對象數(shù) ）越相近，相似性越高，簇是對象的稠密區(qū)域，被低密度的區(qū)域環(huán)繞 連通性相似性度量：使用圖的連通性度量相似性，簇定義為圖的連通分支，即互相連通但不與組外對象連通的對象組 概念相似性度量：共性（比如共享最近鄰）越多越相似 ，簇定義為有某種共同性質(zhì)的對象的集合 相似性測度主要的聚類算法大致可以分為：劃分式聚類算法、基于密度的聚類算法、層次聚類算法、基于網(wǎng)格的聚類算法和基于模型的聚類算

30、法聚類算法分類劃分式聚類算法（partitioning method）預(yù)先指定聚類數(shù)目或聚類中心，通過反復(fù)迭代運(yùn)算，逐步優(yōu)化準(zhǔn)則函數(shù)的值，當(dāng)準(zhǔn)則函數(shù)收斂時(shí)，得到最終聚類結(jié)果k均值算法、k中心點(diǎn)算法及它們的變種基于密度的聚類算法（density-based method）通過數(shù)據(jù)密度來發(fā)現(xiàn)簇DBSCAN、OPTICS、DENCLUE聚類算法分類基于網(wǎng)格的聚類算法（gridbased method）將對象空間量化為有限數(shù)目的單元，形成網(wǎng)格結(jié)構(gòu)，所有的聚類操作都在網(wǎng)格上進(jìn)行，從而獲得較快的處理速度STING、WaveCluster層次聚類算法（hierarchical method）將數(shù)據(jù)對象組織成

31、一棵聚類樹，使用數(shù)據(jù)的聯(lián)接規(guī)則，透過一種架構(gòu)方式，反復(fù)將數(shù)據(jù)進(jìn)行分裂或聚合，以形成一個(gè)層次序列的聚類問題解 BIRCH、ROCK和Chameleon 等聚類算法分類基于模型的聚類算法（model-based method）基于“數(shù)據(jù)根據(jù)潛在的混合概率分布生成”假設(shè)，為每個(gè)簇假定一個(gè)模型，并尋找數(shù)據(jù)對給定模型的最佳擬合這類算法通過構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來定位簇，能考慮“噪聲”數(shù)據(jù)和離群點(diǎn)的影響，魯棒性較好 EM 、COBWEB 、SOM 均值聚類算法均值聚類算法假定所有數(shù)據(jù)對象可分為k個(gè)簇，每個(gè)簇的中心用均值表示對象間的相似性用距離度量聚類的準(zhǔn)則是誤差平方和準(zhǔn)則 核心思想：首先選定k個(gè)

32、初始聚類中心，根據(jù)最小距離原則將每個(gè)數(shù)據(jù)對象分配到某一簇中然后不斷迭代計(jì)算各個(gè)簇的聚類中心并依新的聚類中心調(diào)整聚類情況，直至收斂（J 值不再變化）均值聚類算法誤差平方和準(zhǔn)則若Nx是第Cx個(gè)簇中的對象數(shù)目，mx是這些對象的均值， J是所有簇的簇中各個(gè)對象與均值間的誤差平方和之和對于不同的聚類，J的值不同使J 值極小的聚類是誤差平方和準(zhǔn)則下的最優(yōu)結(jié)果度量了用k個(gè)聚類中心m1,mk代表k個(gè)簇C1,Ck時(shí)所產(chǎn)生的總的誤差平方和均值聚類算法算法描述輸入：數(shù)據(jù)對象集合D，簇?cái)?shù)目k輸出：k個(gè)簇的集合步驟：1. 從D中隨機(jī)選取k個(gè)不同的數(shù)據(jù)對象作為k個(gè)簇C1，Ck的中心m1，mk2. repeat1）for

33、D中每個(gè)數(shù)據(jù)對象oa. 尋找i，b. 將o分配給簇Ci2）for 每個(gè)簇Ci（i=1，k）計(jì)算 3）計(jì)算平方誤差3. Until J不再發(fā)生變化計(jì)算新的聚類中心，|Ci|為當(dāng)前簇中的對象數(shù)目均值聚類算法算法簡單，計(jì)算復(fù)雜度是O(nkt)，其中n是對象的總數(shù)，k是簇的個(gè)數(shù)，t是迭代次數(shù)，通常，kn且t ，繼續(xù)計(jì)算5步迭代后的結(jié)果：x1x2x3x4x5(0.826,0.961)T(0.501,0.981)T(0.653,0.945)T(3.452,0.038)T(3.811,0.040)T(4.106,0.039)T(3.614,0.019)T(2.720,0.055)T(0.688,0.962)

34、T(0.777,0.960)T模糊c-均值聚類算法xi相對于 的隸屬度 x1x2x3x4x50.9610.9810.9460.0380.0400.0390.0190.0540.9620.960聚類過程終止 分析技術(shù)及模型分類分析103分類與預(yù)測是普遍存在的問題，具有廣泛的應(yīng)用領(lǐng)域分類的任務(wù)是通過分析由已知類別數(shù)據(jù)對象組成的訓(xùn)練數(shù)據(jù)集，建立描述并區(qū)分?jǐn)?shù)據(jù)對象類別的分類函數(shù)或分類模型（分類器）分類的目的是利用分類模型判定未知類別數(shù)據(jù)對象的所屬類別，判定的目標(biāo)是數(shù)據(jù)對象在類別屬性（離散）上的取值預(yù)測也要通過分析訓(xùn)練數(shù)據(jù)集建立預(yù)測模型，然后利用模型預(yù)測數(shù)據(jù)對象，預(yù)測的目標(biāo)是判定數(shù)據(jù)對象在預(yù)測屬性（連續(xù)

35、）上的取值或取值區(qū)間分類與聚類有顯著區(qū)別：分類中，訓(xùn)練樣本的類別是已知的（有指導(dǎo)），而聚類中所有數(shù)據(jù)都沒有類別標(biāo)簽（無指導(dǎo)）主要介紹分類過程、分類模型評估方法、常用分類算法分類分析分類過程分為兩個(gè)階段：學(xué)習(xí)階段與分類階段分類過程訓(xùn)練樣本輸入分類模型測試樣本輸入新數(shù)據(jù)分類算法學(xué)習(xí)過程分類過程每個(gè)訓(xùn)練樣本由m+1個(gè)屬性描述，X=（A1, , Am, C）Ai對應(yīng)描述屬性，可以是連續(xù)屬性或離散屬性C表示類別屬性，有k個(gè)不同的類別，C=（c1, c2, , ck）從描述屬性矢量（X-C）到類別屬性C的映射函數(shù)H:（X-C）C分類規(guī)則、判定樹等形式X=（A1, , Am）確定CX=（A1, , Am,C

36、）提供X=（A1, , Am)，確定C，比較C、C用于尋找映射函數(shù)H分類算法有多種：決策樹分類算法、神經(jīng)網(wǎng)絡(luò)分類算法、貝葉斯分類算法、k-最近鄰分類算法、遺傳分類算法、粗糙集分類算法、模糊集分類算法等 分類算法可以根據(jù)下列標(biāo)準(zhǔn)進(jìn)行比較和評估：1）準(zhǔn)確率：分類模型正確地預(yù)測新樣本所屬類別的能力2）速度：建立和使用分類模型的計(jì)算開銷3）強(qiáng)壯性：給定噪聲數(shù)據(jù)或具有空缺值的數(shù)據(jù)，分類模型正確地預(yù)測的能力4）可伸縮性：給定大量數(shù)據(jù)，有效地建立分類模型的能力5）可解釋性：分類模型提供的理解和洞察的層次分類算法評估標(biāo)準(zhǔn)利用測試數(shù)據(jù)集評估分類模型的準(zhǔn)確率分類模型正確分類的測試樣本數(shù)占總測試樣本數(shù)的百分比準(zhǔn)確率

37、可以接受，對新樣本進(jìn)行分類；否則，重新建立分類模型評估分類模型準(zhǔn)確率的方法有保持、k-折交叉確認(rèn)保持方法將已知類別的樣本隨機(jī)地劃分為訓(xùn)練數(shù)據(jù)集與測試數(shù)據(jù)集兩個(gè)集合，一般，訓(xùn)練數(shù)據(jù)集占2/3，測試數(shù)據(jù)集占1/3k-折交叉確認(rèn)方法將已知類別的樣本隨機(jī)地劃分為大小大致相等的k個(gè)子集S1, , Sk，并進(jìn)行k次訓(xùn)練與測試第i次，Si作為測試數(shù)據(jù)集，其余子集的并集作為訓(xùn)練數(shù)據(jù)集k次訓(xùn)練得到k個(gè)分類模型，測試時(shí)，將出現(xiàn)次數(shù)最多的分類結(jié)果作為最終的分類結(jié)果分類模型評估方法適宜多峰分布的分類問題 決策樹以樹結(jié)構(gòu)的形式表示，類似流程圖一棵決策樹由一個(gè)根節(jié)點(diǎn)，一組內(nèi)部節(jié)點(diǎn)和一組葉節(jié)點(diǎn)組成決策樹分類算法每個(gè)分枝表示

38、一個(gè)測試輸出每個(gè)葉節(jié)點(diǎn)表示一個(gè)類，不同的葉節(jié)點(diǎn)可表示相同的類 根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測試建立了決策樹之后，可以對從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每條路徑創(chuàng)建一條IF-THEN分類規(guī)則，易于理解沿著路徑，每個(gè)內(nèi)部節(jié)點(diǎn)-分枝對形成規(guī)則前件（IF部分）的一個(gè)合取項(xiàng)，葉節(jié)點(diǎn)形成規(guī)則后件（THEN部分）決策樹分類算法IF 年齡=41 AND 信譽(yù)=中 THEN 購買計(jì)算機(jī)=是IF 年齡=30 AND 學(xué)生=否 THEN 購買計(jì)算機(jī)=否-否新顧客：教師，年齡45歲，收入較低但信譽(yù)很好該顧客是否會(huì)購買計(jì)算機(jī)？決策樹分類算法的關(guān)鍵是建立決策樹建立一棵決策樹，需要解決的問題主要有：1）如何選擇測試屬性？測試屬性的

39、選擇順序影響決策樹的結(jié)構(gòu)甚至決策樹的準(zhǔn)確率一般使用信息增益度量來選擇測試屬性2）如何停止劃分樣本？從根節(jié)點(diǎn)測試屬性開始，每個(gè)內(nèi)部節(jié)點(diǎn)測試屬性都把樣本空間劃分為若干個(gè)（子）區(qū)域一般當(dāng)某個(gè)（子）區(qū)域的樣本同類時(shí)，就停止劃分樣本，有時(shí)也通過閾值提前停止劃分樣本決策樹分類算法使用遞歸方式完成基本思想：首先，將整個(gè)訓(xùn)練數(shù)據(jù)集S、所有描述屬性A1, A2, , Am作為分析對象如果S中的樣本屬于同一類別，則將S作為葉節(jié)點(diǎn)并用其中樣本的類別標(biāo)識(shí)，決策樹建立完成否則在S上計(jì)算各個(gè)屬性的信息增益G(C, Ak)，選擇信息增益最大的屬性Ai作為根節(jié)點(diǎn)的測試屬性如果Ai的取值個(gè)數(shù)為v（取值記為a1, a2, , a

40、v），則Ai將S劃分為v個(gè)子集S1, S2, , Sv，同時(shí)根節(jié)點(diǎn)產(chǎn)生v個(gè)分枝與之對應(yīng)分別在訓(xùn)練數(shù)據(jù)子集S1, S2, , Sv、剩余描述屬性A1, , Ai-1, Ai+1, , Am上采用相同方法遞歸地建立決策樹子樹決策樹分類算法建立決策樹Sv：S中Ai=av的樣本集合遞歸過程中，某節(jié)點(diǎn)對應(yīng)的訓(xùn)練數(shù)據(jù)（子）集由整個(gè)訓(xùn)練數(shù)據(jù)集S中滿足從根節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所有屬性測試的訓(xùn)練樣本組成某節(jié)點(diǎn)對應(yīng)的描述屬性是去除從根節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所有已選描述屬性后的剩余描述屬性同一層內(nèi)部節(jié)點(diǎn)選擇的測試屬性可能相同也可能不同決策樹分類算法建立決策樹遞歸結(jié)束條件：1）某節(jié)點(diǎn)對應(yīng)的訓(xùn)練數(shù)據(jù)（子）集中的樣本屬于同一類

41、別2）某節(jié)點(diǎn)對應(yīng)的訓(xùn)練數(shù)據(jù)（子）集為空此時(shí)，該節(jié)點(diǎn)作為葉節(jié)點(diǎn)并用父節(jié)點(diǎn)中占多數(shù)的樣本類別標(biāo)識(shí)3）某節(jié)點(diǎn)沒有對應(yīng)的（剩余）描述屬性此時(shí)，該節(jié)點(diǎn)作為葉節(jié)點(diǎn)并用該節(jié)點(diǎn)中占多數(shù)的樣本類別標(biāo)識(shí)決策樹分類算法建立決策樹輸入：訓(xùn)練數(shù)據(jù)集S，描述屬性集合A輸出：決策樹步驟：（1）創(chuàng)建對應(yīng)S的節(jié)點(diǎn)Node（2）if S中的樣本屬于同一類別c then 以c標(biāo)識(shí)Node并將Node作為葉節(jié)點(diǎn)返回（3）if A為空 then 以S中占多數(shù)的樣本類別c標(biāo)識(shí)Node并將Node作為葉節(jié)點(diǎn)返回（4）從A中選擇對S而言信息增益最大的描述屬性Ai作為Node的測試屬性決策樹分類算法算法描述（5）for Ai的每個(gè)可能取值aj

42、（1jv） （）產(chǎn)生S的一個(gè)子集Sj （）if Sj為空 then 創(chuàng)建對應(yīng)Sj的節(jié)點(diǎn)Nj，以S中占多數(shù)的樣本類別c標(biāo)識(shí)Nj，并將Nj作為葉節(jié)點(diǎn)形成Node的一個(gè)分枝 （）else 由（Sj, A-Ai）創(chuàng)建子樹形成Node的一個(gè)分枝決策樹分類算法算法描述決策樹分類算法信息增益類別屬性C的無條件熵：給定描述屬性Ak，類別屬性C的條件熵：n：樣本總數(shù) u：C的可能取值個(gè)數(shù)，即類別數(shù)si：屬于類別ci的記錄集合 |si|：屬于類別ci的記錄總數(shù)v：Ak的可能取值個(gè)數(shù) sj：Ak=aj的記錄集合 |sj|：Ak=aj的記錄數(shù)目Sij：Ak=aj且屬于類別ci的記錄集合 |sij|：Ak=aj且屬于類

43、別ci的記錄數(shù)目 給定描述屬性Ak，類別C的信息增益：G(C, Ak)=E(C)-E(C, Ak) G(C, Ak)反映Ak減少C不確定性的程度，G(C, Ak)越大，Ak對減少C不確定性的貢獻(xiàn)越大 決策樹分類算法信息增益 蔬菜數(shù)據(jù)表如表所示，“顏色”、“形狀”是描述屬性，“蔬菜”是類別屬性，分別求給定“顏色”、“形狀”屬性時(shí)，“蔬菜”屬性的信息增益 顏色形狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜G(蔬菜，顏色)G(蔬菜，形狀)1.5850-0.6667=0.9183 G(蔬菜，顏色)G(蔬菜，形狀) 不同描述屬性減少類別屬性不確定性的程度不同決策樹分類算法信息增益盡量選擇對減少類別屬性不確定性貢獻(xiàn)最大

44、的描述屬性分類模型包含盡可能少的描述屬性從而使模型簡單 G(蔬菜，顏色)G(蔬菜，形狀) 測試屬性的選擇順序影響決策樹的結(jié)構(gòu)甚至決策樹的準(zhǔn)確率決策樹分類算法要求描述屬性是離散屬性，連續(xù)屬性需要離散化 決策樹分類算法噪聲處理如果訓(xùn)練數(shù)據(jù)集含有噪聲，決策樹的某些分枝反映的是噪聲而不是總體，應(yīng)該剪去這些不可靠的分枝，提高決策樹的分類準(zhǔn)確率有兩種剪枝策略： 先剪枝策略：在建立決策樹的過程中，通過某度量標(biāo)準(zhǔn)判斷每個(gè)內(nèi)部節(jié)點(diǎn)是否需要進(jìn)一步劃分，如果進(jìn)一步劃分將導(dǎo)致建立不可靠的分枝，則停止劃分，從而達(dá)到剪枝。此時(shí)，該內(nèi)部節(jié)點(diǎn)變成葉節(jié)點(diǎn)并用其中占多數(shù)的記錄類別標(biāo)識(shí) 后剪枝策略：首先，建立完整的決策樹；然后，通

45、過某度量標(biāo)準(zhǔn)判斷哪些內(nèi)部節(jié)點(diǎn)分枝是不可靠的，將這些內(nèi)部節(jié)點(diǎn)變成葉節(jié)點(diǎn)并用其中占多數(shù)的記錄類別標(biāo)識(shí)，從而達(dá)到剪枝前饋神經(jīng)網(wǎng)絡(luò)分類算法神經(jīng)網(wǎng)絡(luò)可以模仿人腦，通過學(xué)習(xí)訓(xùn)練數(shù)據(jù)集，生成分類模型適用于數(shù)據(jù)沒有任何明顯模式的情況 樣本屬性可以是連續(xù)的，也可以是離散的神經(jīng)網(wǎng)絡(luò)由許多單元（神經(jīng)元）以適當(dāng)?shù)姆绞竭B接起來構(gòu)成單元模仿人腦的神經(jīng)元，單元之間的連接相當(dāng)于人腦中神經(jīng)元的連接單元之間的連接方式有多種，從而形成了多種神經(jīng)網(wǎng)絡(luò)在分類中，應(yīng)用較多的是前饋神經(jīng)網(wǎng)絡(luò)主要介紹前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)、網(wǎng)絡(luò)學(xué)習(xí)及網(wǎng)絡(luò)分類方法 前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)結(jié)構(gòu)前饋神經(jīng)網(wǎng)絡(luò)是分層網(wǎng)絡(luò)模型，具有一個(gè)輸入層和一個(gè)輸出層，輸入層和輸出層之間

46、有一個(gè)或多個(gè)隱藏層每個(gè)層具有若干單元，前一層單元與后一層單元之間通過有向加權(quán)邊相連 ai：輸入層第i個(gè)單元的輸入 Ok：輸出層第k個(gè)單元的輸出 wij：隱藏層第j個(gè)單元與輸入層第i個(gè)單元之間的連接權(quán)wjk：輸出層第k個(gè)單元與隱藏層第j個(gè)單元之間的連接權(quán) 前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)結(jié)構(gòu)輸入層單元的數(shù)目與訓(xùn)練樣本的描述屬性數(shù)目對應(yīng)，通常一個(gè)連續(xù)屬性對應(yīng)一個(gè)輸入層單元，一個(gè)p值離散屬性對應(yīng)p個(gè)輸入層單元輸出層單元的數(shù)目與訓(xùn)練樣本的類別數(shù)目對應(yīng)（兩類時(shí)，可以只有一個(gè)輸出單元）隱層的層數(shù)及隱層的單元數(shù)尚無理論指導(dǎo)，一般通過實(shí)驗(yàn)選取輸入層，各單元的輸出可以等于輸入，也可以按一定比例調(diào)節(jié)，使其值落在1和+1之

47、間其他層，每個(gè)單元的輸入都是前一層各單元輸出的加權(quán)和，輸出是輸入的某種函數(shù)，稱為激活函數(shù)前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)結(jié)構(gòu)隱藏層、輸出層任意單元j的輸入： 輸出 ： Oj= f (netj) 如果f采用S型激活函數(shù)：對于隱藏層、輸出層任意單元j，由輸入計(jì)算輸出的過程 ： 單元i的輸出單元j與前一層單元i之間的連接權(quán)改變單元j活性的偏置，1，1上取值則前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)學(xué)習(xí)不同的單元的偏置及單元之間的連接權(quán)會(huì)獲得不同的輸出學(xué)習(xí)過程就是調(diào)整各單元的偏置及單元之間的連接權(quán)值，使每個(gè)訓(xùn)練樣本在輸出層單元上獲得的輸出與其期望輸出間的誤差最小學(xué)習(xí)使用誤差后向傳播算法基本思想：首先賦予每條有向加權(quán)邊初始權(quán)值

48、、每個(gè)隱藏層與輸出層單元初始偏置然后迭代地處理每個(gè)訓(xùn)練樣本，輸入它的描述屬性值，計(jì)算實(shí)際輸出，獲取實(shí)際輸出與期望輸出間的誤差將誤差從輸出層經(jīng)每個(gè)隱藏層到輸入層“后向傳播”，根據(jù)誤差修改權(quán)值和單元的偏置，使實(shí)際輸出與期望輸出之間的誤差最小前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)學(xué)習(xí)樣本實(shí)際輸出與期望輸出的誤差Error： c：輸出層的單元數(shù)目 Tk：輸出層單元k的期望輸出 Ok：單元k的實(shí)際輸出 輸出層單元k與前一層單元j之間的權(quán)值wjk的修改量wjk、單元k的偏置修改量為使Error最小，采用使Error沿梯度方向下降的方式單元j的輸出Error對單元k的輸入netk的負(fù)偏導(dǎo)數(shù)學(xué)習(xí)率，l 0, 1，避免陷入局

49、部最優(yōu)解單元k的輸出前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)學(xué)習(xí)隱藏層單元j與前一層單元i之間的權(quán)值wij的修改量wij、單元j的偏置j的修改量j ：單元i的輸出單元j的輸出與單元j相連的后一層單元k的誤差 權(quán)值、偏置的修改 ：權(quán)值、偏置的更新有兩種策略：1）實(shí)例更新：處理一個(gè)訓(xùn)練樣本更新一次，常采用2）周期更新：處理所有訓(xùn)練樣本后再一次更新處理所有訓(xùn)練樣本一次，稱為一個(gè)周期前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)學(xué)習(xí)結(jié)束條件：1）誤差Error小于設(shè)定閾值，此時(shí)認(rèn)為網(wǎng)絡(luò)收斂，結(jié)束迭代2）前一周期所有的權(quán)值變化都很小，小于某個(gè)設(shè)定閾值3）前一周期預(yù)測的準(zhǔn)確率很大，大于某個(gè)設(shè)定閾值3）周期數(shù)大于某個(gè)設(shè)定閾值在實(shí)際應(yīng)用中，訓(xùn)練樣

50、本很多，學(xué)習(xí)需要很多次迭代才能完成迭代次數(shù)與網(wǎng)絡(luò)結(jié)構(gòu)、初始權(quán)值與偏置、學(xué)習(xí)率的值有很大關(guān)系這些參數(shù)都是憑經(jīng)驗(yàn)選取 算法特點(diǎn)前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)學(xué)習(xí)設(shè)訓(xùn)練樣本s的描述屬性值與類別屬性值分別為1, 0, 1與1，前饋神經(jīng)網(wǎng)絡(luò)NT如圖所示，NT中每條有向加權(quán)邊的權(quán)值、每個(gè)隱藏層與輸出層單元的偏置如表所示，學(xué)習(xí)率為。寫出輸入s訓(xùn)練NT的過程 x1x2x3w14w15w24w25w34w35w46w564561010.20.30.40.10.50.20.30.20.40.20.1前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)學(xué)習(xí)x1x2x3w14w15w24w25w34w35w46w564561010.20.30.40.

51、10.50.20.30.20.40.20.1單元j輸入netj輸出Oj40.2*1+0.4*0+(0.5)*1+(0.4)=0.71/(1+e(0.7)=0.3325(0.3)*1+0.1*0+(0.2)*1+0.2=0.11/(1+e0.1)=0.5256(0.3) *0.332+(0.2)*0.525+0.1=0.1051/(1+e(0.105)=0.474單元jErrj60.474*(10.474)*(10.474)=0.131150.525*(10.525)*(0.1311*(0.2)=0.006540.332*(10.332)*(0.1311*(0.3)=0.0087前饋神經(jīng)網(wǎng)絡(luò)分類

52、算法網(wǎng)絡(luò)學(xué)習(xí)x1x2x3w14w15w24w25w34w35w46w564561010.20.30.40.10.50.20.30.20.40.20.1w340.5+0.9*(0.0087)*1=0.508w350.2+0.9*(0.0065)*1=0.19460.1+0.9*0.1311=0.21850.2+0.9*(0.0065)=0.19440.4+0.9*(0.0087)=0.408w460.3+0.9*0.1311*0.332=0.261w560.2+0.9*0.1311*0.525=0.138w140.2+0.9*(0.0087)*1=0.192w150.3+0.9*(0.0065)

53、*1=0.306w240.4+0.9*(0.0087)*0=0.4w250.1+0.9*(0.0065)*0=0.1單元jErrj60.131150.006540.0087單元j輸出Oj40.33250.52560.474前饋神經(jīng)網(wǎng)絡(luò)分類算法算法描述輸入：訓(xùn)練數(shù)據(jù)集S，前饋神經(jīng)網(wǎng)絡(luò)NT，學(xué)習(xí)率l輸出：經(jīng)過訓(xùn)練的前饋神經(jīng)網(wǎng)絡(luò)NT步驟：（1）在區(qū)間-1, 1上隨機(jī)初始化NT中每條有向加權(quán)邊的權(quán)值、每個(gè)隱藏層與輸出層單元的偏置（2）while 結(jié)束條件不滿足 （）for S中每個(gè)訓(xùn)練樣本s （）for 隱藏層與輸出層中每個(gè)單元j （）for 輸出層中每個(gè)單元k Errk=Ok(1- Ok)( Tk

54、- Ok)從第一個(gè)隱藏層開始向前傳播輸入 前饋神經(jīng)網(wǎng)絡(luò)分類算法算法描述 （）for 隱藏層中每個(gè)單元j （）for NT中每條有向加權(quán)邊的權(quán)值wij wij= wij+lErrjOi （）for 隱藏層與輸出層中每個(gè)單元的偏置j j=j+lErrj從最后一個(gè)隱藏層開始向后傳播誤差 學(xué)習(xí)過程由正向傳播和反向傳播組成正向傳播過程：訓(xùn)練樣本從輸入層，經(jīng)隱藏層，傳向輸出層，每一層單元的狀態(tài)只影響下一層單元的狀態(tài)反向傳播過程：輸出層不能得到期望輸出，則將誤差沿原來的連接通路傳回，通過修改權(quán)值和偏置，使誤差最小 前饋神經(jīng)網(wǎng)絡(luò)分類算法網(wǎng)絡(luò)分類學(xué)習(xí)結(jié)束后，神經(jīng)網(wǎng)絡(luò)得到一組固定的權(quán)值及偏置新樣本到來后，將其描述

55、屬性值送入輸入層各單元，從輸入層到輸出層正向傳播，計(jì)算輸出層各單元的值O1, O2, , On令r=max(O1, O2, , On)，則第r個(gè)輸出層單元所代表的類別就是該樣本所屬的類別新樣本X=（x1, x2, x3）送入輸入層計(jì)算出O61，則表示X應(yīng)屬于A類O60，則表示X應(yīng)屬于B類若O6，則拒絕分類貝葉斯分類算法貝葉斯分類：應(yīng)用貝葉斯公式求解分類問題 貝葉斯公式：貝葉斯分類公式：m個(gè)描述屬性A1=a1, , Am=am的聯(lián)合概率 類別屬性C=c的概率（先驗(yàn)概率 ）已知C=c時(shí)，A1=a1, , Am=am的條件概率（類條件概率 ）已知A1=a1, , Am=am時(shí)，C=c的條件概率（類別

56、c的后驗(yàn)概率）貝葉斯分類的分類就是給定新樣本的描述屬性值a1,am，計(jì)算各個(gè)類別的后驗(yàn)概率，后驗(yàn)概率最大的類別就是新樣本的類別貝葉斯分類算法怎樣算 、 ？先驗(yàn)概率p(c) 可以通過統(tǒng)計(jì)訓(xùn)練數(shù)據(jù)集中每個(gè)類別訓(xùn)練樣本所占比例進(jìn)行估計(jì)在計(jì)算各個(gè)類條件概率時(shí)，一般應(yīng)用條件獨(dú)立假設(shè)簡化計(jì)算樸素貝葉斯分類 C和A1, ., Am有直接依賴關(guān)系，A1, ., Am之間相互獨(dú)立 貝葉斯分類算法新樣本為（3140，中，否，優(yōu)） p(是)9/14 p(3140|是)4/9；p(中|是)4/9；p(否|是)3/9；p(優(yōu)|是)3/9；p(是)p(3140|是)p(中|是)p(否|是)p(優(yōu)|是)9/144/94/9

57、3/93/98/567年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高否中否30高否優(yōu)否3140高否中是41中否中是41低是中是41低是優(yōu)否3140低是優(yōu)是30中否中否30低是中是41中是中是30中是優(yōu)是3140中否優(yōu)是3140高是中是41中否優(yōu)否貝葉斯分類算法新樣本為（3140，中，否，優(yōu)）p(否)5/14；p(3140|否)0；p(中|否)2/5；p(否|否)4/5；p(優(yōu)|否)3/5；p(否)p(3140|否)p(中|否)p(否|否)p(優(yōu)|否)5/1402/54/53/50所以新樣本的類別為是 年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高否中否30高否優(yōu)否3140高否中是41中否中是41低是中是41低是優(yōu)否314

58、0低是優(yōu)是30中否中否30低是中是41中是中是30中是優(yōu)是3140中否優(yōu)是3140高是中是41中否優(yōu)否貝葉斯分類算法輸入：訓(xùn)練數(shù)據(jù)集S、新樣本r( ar1, , arm )輸出：新樣本的類別cr步驟：（1）for S中每個(gè)訓(xùn)練樣本s(as1, , asm, cs) （）增加類別cs的計(jì)數(shù)cs.count （）for 每個(gè)描述屬性值asi 增加類別cs中描述屬性值asi的計(jì)數(shù)cs.asi.count（2）for 每個(gè)類別c （） 算法描述貝葉斯分類算法 （）for 每個(gè)描述屬性Ai （）for 每個(gè)描述屬性值ai （）for 每個(gè)a1, , am（3）算法描述樸素貝葉斯分類假設(shè)各個(gè)描述屬性在給定

59、類別屬性時(shí)條件獨(dú)立這個(gè)條件獨(dú)立假設(shè)在現(xiàn)實(shí)應(yīng)用中可能不成立樹增強(qiáng)樸素貝葉斯分類削弱了這個(gè)限制 樹增強(qiáng)樸素貝葉斯分類算法樹增強(qiáng)樸素貝葉斯分類假設(shè)C和A1, ., Am有直接依賴關(guān)系，A1, ., Am之間也有依賴關(guān)系（允許各個(gè)描述屬性之間形成樹型結(jié)構(gòu)），削弱了各個(gè)描述屬性在給定類別屬性時(shí)條件獨(dú)立假設(shè)，增強(qiáng)了樸素貝葉斯分類節(jié)點(diǎn)C和節(jié)點(diǎn)A1, ., Am有有向邊相連，C是A1, ., Am的父節(jié)點(diǎn)A1, ., Am之間有有向邊相連并形成樹，根節(jié)點(diǎn)的父節(jié)點(diǎn)只有C，其它節(jié)點(diǎn)的父節(jié)點(diǎn)除了C之外還有一個(gè)節(jié)點(diǎn) 新樣本a1, , a5的類別： 樹增強(qiáng)樸素貝葉斯分類算法樹增強(qiáng)樸素貝葉斯分類樹型結(jié)構(gòu)構(gòu)造方法的基本思想

60、：首先，計(jì)算在給定類別屬性C時(shí)，描述屬性A1, ., Am之間的依賴強(qiáng)度，共得到 個(gè)依賴強(qiáng)度然后，根據(jù)從強(qiáng)到弱的原則選擇m-1個(gè)依賴強(qiáng)度，添加相應(yīng)描述屬性之間的無向邊，并使各個(gè)描述屬性之間形成無向樹最后，選擇根節(jié)點(diǎn)，為無向邊添加方向形成有向樹在給定類別屬性C時(shí)，描述屬性Ai和 Aj之間的依賴強(qiáng)度可以利用條件互信息描述： 樹增強(qiáng)樸素貝葉斯分類算法輸入：訓(xùn)練數(shù)據(jù)集S輸出：樹增強(qiáng)樸素貝葉斯分類的貝葉斯網(wǎng)結(jié)構(gòu)TAN步驟：（1）掃描S，計(jì)算在給定類別屬性C時(shí)，描述屬性A1, ., Am之間的條件互信息（2）構(gòu)造一個(gè)無向完全圖，以描述屬性為節(jié)點(diǎn)，以條件互信息為邊的權(quán)重（3）構(gòu)造上述無向完全圖的最大生成樹（