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

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

2、據(jù)等深或等寬分布規(guī)則將數(shù)據(jù)分布到不同箱中，將同一箱中的數(shù)據(jù)用用該箱中數(shù)據(jù)的平均值或中值、邊界值替換（平均值平滑、中值平滑、邊界平滑）每個箱中的數(shù)據(jù)個數(shù)或取值區(qū)間相等設某屬性的值為18，12，3，9，7，6，15，21，16，采用分箱技術(shù)平滑數(shù)據(jù)消除噪聲。分布規(guī)則為等深、深度為3，平滑規(guī)則為平均值平滑 首先，將屬性的值排序為3, 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、個全局常量填充2）使用屬性平均值填充3）使用相同類的屬性平均值填充4）使用最可能的值填充 需要采用預測算法，預測給定樣本的最可能的值并填充數(shù)據(jù)不一致可以通過元數(shù)據(jù)消除（描述數(shù)據(jù)的數(shù)據(jù)）數(shù)據(jù)集成數(shù)據(jù)集成是將多個數(shù)據(jù)源中的數(shù)據(jù)結(jié)合起來存放在一個一致的數(shù)據(jù)存儲（如數(shù)據(jù)倉庫）中這些數(shù)據(jù)源可能包括多個數(shù)據(jù)庫、數(shù)據(jù)立方體或一般文件在數(shù)據(jù)集成時，需要消除冗余能夠由另外的屬性“導出”、命名的不一致的屬性冗余可以通過相關(guān)分析進行檢測屬性A、B之間的相關(guān)性計算：rA,B0，A與B正相關(guān)，A的值隨著B的值的增加而增加rA,B0，A與B負相關(guān)，A的值隨著B的值的增加而減少rA,B=0，A與B獨立。因此，|rA,B|很

4、大時，A與B可以去除一個 平均值方差數(shù)據(jù)變換將屬性數(shù)據(jù)按比例縮放，使之落入一個小的特定區(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設某屬性的平均值、標準差分別為80、25，采用零-均值規(guī)格化66 小數(shù)定標規(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ù)集，目標是找出最小屬性集， 使得數(shù)據(jù)在其上的概率分布盡可能地接近在原屬性集上的概率分布 常用方法：粗糙集中的屬性約簡、決策樹記錄規(guī)約：用少量記錄代表或替換原有記錄，從而減小數(shù)據(jù)集常用方法： 抽樣、數(shù)據(jù)概化數(shù)據(jù)規(guī)約數(shù)據(jù)概化：采用面向?qū)傩詺w納，根據(jù)屬性的概念分層，通過閾值控制，將屬性的低層屬性值用相應高層概念

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

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

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

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

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

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

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

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

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

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

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

17、有頻繁項集 （） /找出由頻繁閉(k+1)-項集推導的頻繁k-項集 （）CLk=l|lCL,|l|=k /找出頻繁閉k-項集頻繁項集的緊湊表示通過頻繁閉項集的支持計數(shù)計算其它頻繁非閉項集的支持計數(shù)的算法描述（）for TLk中每個項集 /計算頻繁非閉k-項集的支持計數(shù) （）if then Lk= Lkl（） Lk= LkCLk（）L=LLk頻繁項集的緊湊表示最小支持計數(shù)閾值是5，項集b:9、ad:5、bc:7、bd:6和bcd:5是頻繁閉項集。寫出計算頻繁非閉項集的支持計數(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)生大量候選項集2）可能需要重復掃描數(shù)據(jù)庫，通過模式匹配檢查龐大的候選集合FP-growth算法采用一種稱為FP樹的結(jié)構(gòu)表示事務集合中項集的關(guān)聯(lián)，并在FP樹上遞歸地找出所有頻繁項集，算法并不產(chǎn)生候選基本思想：掃描

19、一次事務集合，找出頻繁1-項集合L1基于L1，再掃描一次事務集合，構(gòu)造表示事務集合中項集關(guān)聯(lián)的FP樹在FP樹上遞歸地找出所有頻繁項集最后在所有頻繁項集中產(chǎn)生強關(guān)聯(lián)規(guī)則 FP-growth算法 1）掃描一次事務集合，找出頻繁1-項集合L，并按支持計數(shù)降序排序L中的頻繁項FP樹構(gòu)造 事務項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é)點，用“null”標記nullFP-growth算法 3）

20、再掃描一次事務集合，對每個事務找出其中的頻繁項并按L中的順序排序，為每個事務創(chuàng)建一個分枝，事務分枝路徑上的節(jié)點就是該事務中的已排序頻繁項對于各個事務分枝，如果可以共享路徑則共享并且在各個節(jié)點上記錄共享事務數(shù)目FP樹構(gòu)造 事務項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)造 事務項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)建一個項表項表中每一行表示一個頻繁項，并有一個指針指向它在FP樹中的節(jié)點FP樹中相同頻繁項的節(jié)點通過指針連成鏈表 FP-growth算法 FP樹構(gòu)造 事務項t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3FP-growth算法 由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基。然后，構(gòu)造它的條件FP樹，并遞歸地在該樹上進行挖掘。模式增長通過后綴模式與由條件FP

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

23、FP樹FP樹挖掘FP-growth算法 第二層遞歸：FP樹挖掘條件模式基條件FP樹產(chǎn)生的頻繁項集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樹有多個分枝，進入第二層遞歸i3:5的條件FP樹有兩個分枝，進入第三層遞歸 FP-growth算法 第三層遞歸：FP樹挖掘條件模式基條件FP樹產(chǎn)生的頻繁項集i1i3:3nul

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

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

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

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

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

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

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

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

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

33、D中每個數(shù)據(jù)對象oa. 尋找i，b. 將o分配給簇Ci2）for 每個簇Ci（i=1，k）計算 3）計算平方誤差3. Until J不再發(fā)生變化計算新的聚類中心，|Ci|為當前簇中的對象數(shù)目均值聚類算法算法簡單，計算復雜度是O(nkt)，其中n是對象的總數(shù)，k是簇的個數(shù)，t是迭代次數(shù)，通常，kn且t ，繼續(xù)計算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分類與預測是普遍存在的問題，具有廣泛的應用領(lǐng)域分類的任務是通過分析由已知類別數(shù)據(jù)對象組成的訓練數(shù)據(jù)集，建立描述并區(qū)分數(shù)據(jù)對象類別的分類函數(shù)或分類模型（分類器）分類的目的是利用分類模型判定未知類別數(shù)據(jù)對象的所屬類別，判定的目標是數(shù)據(jù)對象在類別屬性（離散）上的取值預測也要通過分析訓練數(shù)據(jù)集建立預測模型，然后利用模型預測數(shù)據(jù)對象，預測的目標是判定數(shù)據(jù)對象在預測屬性（連續(xù)

35、）上的取值或取值區(qū)間分類與聚類有顯著區(qū)別：分類中，訓練樣本的類別是已知的（有指導），而聚類中所有數(shù)據(jù)都沒有類別標簽（無指導）主要介紹分類過程、分類模型評估方法、常用分類算法分類分析分類過程分為兩個階段：學習階段與分類階段分類過程訓練樣本輸入分類模型測試樣本輸入新數(shù)據(jù)分類算法學習過程分類過程每個訓練樣本由m+1個屬性描述，X=（A1, , Am, C）Ai對應描述屬性，可以是連續(xù)屬性或離散屬性C表示類別屬性，有k個不同的類別，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)絡分類算法、貝葉斯分類算法、k-最近鄰分類算法、遺傳分類算法、粗糙集分類算法、模糊集分類算法等 分類算法可以根據(jù)下列標準進行比較和評估：1）準確率：分類模型正確地預測新樣本所屬類別的能力2）速度：建立和使用分類模型的計算開銷3）強壯性：給定噪聲數(shù)據(jù)或具有空缺值的數(shù)據(jù)，分類模型正確地預測的能力4）可伸縮性：給定大量數(shù)據(jù)，有效地建立分類模型的能力5）可解釋性：分類模型提供的理解和洞察的層次分類算法評估標準利用測試數(shù)據(jù)集評估分類模型的準確率分類模型正確分類的測試樣本數(shù)占總測試樣本數(shù)的百分比準確率

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

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

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

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

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

42、（1jv） （）產(chǎn)生S的一個子集Sj （）if Sj為空 then 創(chuàng)建對應Sj的節(jié)點Nj，以S中占多數(shù)的樣本類別c標識Nj，并將Nj作為葉節(jié)點形成Node的一個分枝 （）else 由（Sj, A-Ai）創(chuàng)建子樹形成Node的一個分枝決策樹分類算法算法描述決策樹分類算法信息增益類別屬性C的無條件熵：給定描述屬性Ak，類別屬性C的條件熵：n：樣本總數(shù) u：C的可能取值個數(shù)，即類別數(shù)si：屬于類別ci的記錄集合 |si|：屬于類別ci的記錄總數(shù)v：Ak的可能取值個數(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不確定性的貢獻越大 決策樹分類算法信息增益 蔬菜數(shù)據(jù)表如表所示，“顏色”、“形狀”是描述屬性，“蔬菜”是類別屬性，分別求給定“顏色”、“形狀”屬性時，“蔬菜”屬性的信息增益 顏色形狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜G(蔬菜，顏色)G(蔬菜，形狀)1.5850-0.6667=0.9183 G(蔬菜，顏色)G(蔬菜，形狀) 不同描述屬性減少類別屬性不確定性的程度不同決策樹分類算法信息增益盡量選擇對減少類別屬性不確定性貢獻最大

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

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

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

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

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

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

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

52、算法網(wǎng)絡學習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)絡分類算法算法描述輸入：訓練數(shù)據(jù)集S，前饋神經(jīng)網(wǎng)絡NT，學習率l輸出：經(jīng)過訓練的前饋神經(jīng)網(wǎng)絡NT步驟：（1）在區(qū)間-1, 1上隨機初始化NT中每條有向加權(quán)邊的權(quán)值、每個隱藏層與輸出層單元的偏置（2）while 結(jié)束條件不滿足 （）for S中每個訓練樣本s （）for 隱藏層與輸出層中每個單元j （）for 輸出層中每個單元k Errk=Ok(1- Ok)( Tk

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

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

56、c的后驗概率）貝葉斯分類的分類就是給定新樣本的描述屬性值a1,am，計算各個類別的后驗概率，后驗概率最大的類別就是新樣本的類別貝葉斯分類算法怎樣算 、 ？先驗概率p(c) 可以通過統(tǒng)計訓練數(shù)據(jù)集中每個類別訓練樣本所占比例進行估計在計算各個類條件概率時，一般應用條件獨立假設簡化計算樸素貝葉斯分類 C和A1, ., Am有直接依賴關(guān)系，A1, ., Am之間相互獨立 貝葉斯分類算法新樣本為（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年齡收入學生信譽購買計算機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所以新樣本的類別為是 年齡收入學生信譽購買計算機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)否貝葉斯分類算法輸入：訓練數(shù)據(jù)集S、新樣本r( ar1, , arm )輸出：新樣本的類別cr步驟：（1）for S中每個訓練樣本s(as1, , asm, cs) （）增加類別cs的計數(shù)cs.count （）for 每個描述屬性值asi 增加類別cs中描述屬性值asi的計數(shù)cs.asi.count（2）for 每個類別c （） 算法描述貝葉斯分類算法 （）for 每個描述屬性Ai （）for 每個描述屬性值ai （）for 每個a1, , am（3）算法描述樸素貝葉斯分類假設各個描述屬性在給定

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

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