數(shù)據(jù)分析方法以及模型

1、關(guān)于數(shù)據(jù)分析方法及模型1第一張，PPT共二百頁(yè)，創(chuàng)作于2022年6月2分析技術(shù)及模型數(shù)據(jù)預(yù)處理第二張，PPT共二百頁(yè)，創(chuàng)作于2022年6月3數(shù)據(jù)預(yù)處理各種數(shù)據(jù)分析技術(shù)的對(duì)象是數(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ù)第三張，PPT共二百頁(yè)，創(chuàng)作于2022年6月4數(shù)據(jù)清理數(shù)據(jù)清理用于消除噪聲、數(shù)據(jù)不一致及數(shù)據(jù)

2、不完整噪聲可以通過(guò)平滑、識(shí)別孤立點(diǎn)等方法進(jìn)行消除分箱技術(shù)：將數(shù)據(jù)排序，根據(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,

3、 18.3, 18.3第四張，PPT共二百頁(yè)，創(chuàng)作于2022年6月5數(shù)據(jù)清理數(shù)據(jù)不完整可以使用下列方法消除：1）使用一個(gè)全局常量填充2）使用屬性平均值填充3）使用相同類(lèi)的屬性平均值填充4）使用最可能的值填充 需要采用預(yù)測(cè)算法，預(yù)測(cè)給定樣本的最可能的值并填充數(shù)據(jù)不一致可以通過(guò)元數(shù)據(jù)消除（描述數(shù)據(jù)的數(shù)據(jù)）第五張，PPT共二百頁(yè)，創(chuàng)作于2022年6月6數(shù)據(jù)集成數(shù)據(jù)集成是將多個(gè)數(shù)據(jù)源中的數(shù)據(jù)結(jié)合起來(lái)存放在一個(gè)一致的數(shù)據(jù)存儲(chǔ)（如數(shù)據(jù)倉(cāng)庫(kù)）中這些數(shù)據(jù)源可能包括多個(gè)數(shù)據(jù)庫(kù)、數(shù)據(jù)立方體或一般文件在數(shù)據(jù)集成時(shí)，需要消除冗余能夠由另外的屬性“導(dǎo)出”、命名的不一致的屬性冗余可以通過(guò)相關(guān)分析進(jìn)行檢測(cè)屬性A、B之間的相

4、關(guān)性計(jì)算：rA,B0，A與B正相關(guān)，A的值隨著B(niǎo)的值的增加而增加rA,B0，A與B負(fù)相關(guān)，A的值隨著B(niǎo)的值的增加而減少rA,B=0，A與B獨(dú)立。因此，|rA,B|很大時(shí)，A與B可以去除一個(gè) 平均值方差第六張，PPT共二百頁(yè)，創(chuàng)作于2022年6月7數(shù)據(jù)變換將屬性數(shù)據(jù)按比例縮放，使之落入一個(gè)小的特定區(qū)間，如1.0到1.0或0.0到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 第七張，PPT共二百

5、頁(yè)，創(chuàng)作于2022年6月8數(shù)據(jù)變換零-均值規(guī)格化：對(duì)均值為 、方差為的數(shù)值屬性A將A的值v規(guī)格化為值v設(shè)某屬性的平均值、標(biāo)準(zhǔn)差分別為80、25，采用零-均值規(guī)格化66 小數(shù)定標(biāo)規(guī)格化 ：數(shù)值屬性A的最大絕對(duì)值為max|A|A，j為滿足 的最小整數(shù) 將A的值v規(guī)格化為值v規(guī)格化 100，100中的66A的最大絕對(duì)值為120，j為3 第八張，PPT共二百頁(yè)，創(chuàng)作于2022年6月9數(shù)據(jù)規(guī)約數(shù)據(jù)歸約技術(shù)可以用來(lái)得到數(shù)據(jù)集的歸約表示，它小得多，但仍接近于保持原數(shù)據(jù)集的完整性在歸約后的數(shù)據(jù)集上分析將更有效，并產(chǎn)生相同（或幾乎相同）的分析結(jié)果歸約方法主要有：屬性歸約 、記錄歸約 屬性規(guī)約：刪除不相關(guān)的或冗余

6、的屬性減小數(shù)據(jù)集，目標(biāo)是找出最小屬性集， 使得數(shù)據(jù)在其上的概率分布盡可能地接近在原屬性集上的概率分布 常用方法：粗糙集中的屬性約簡(jiǎn)、決策樹(shù)記錄規(guī)約：用少量記錄代表或替換原有記錄，從而減小數(shù)據(jù)集常用方法： 抽樣、數(shù)據(jù)概化第九張，PPT共二百頁(yè)，創(chuàng)作于2022年6月10數(shù)據(jù)規(guī)約數(shù)據(jù)概化：采用面向?qū)傩詺w納，根據(jù)屬性的概念分層，通過(guò)閾值控制，將屬性的低層屬性值用相應(yīng)高層概念替換，并合并由此得到的相同記錄 概念分層一般用樹(shù)結(jié)構(gòu)描述，稱為概念層次樹(shù)閾值控制面向?qū)傩詺w納過(guò)程，每個(gè)屬性都有概念層次樹(shù)及閾值首先根據(jù)屬性A的概念層次樹(shù)，將關(guān)系表中A的屬性值轉(zhuǎn)換為最低層的相應(yīng)概念（葉概念），統(tǒng)計(jì)關(guān)系表中A的不同葉概

7、念個(gè)數(shù)如果A的不同葉概念個(gè)數(shù)大于A的屬性閾值，再根據(jù)A的概念層次樹(shù)，將關(guān)系表中A的葉概念轉(zhuǎn)換為上一層的相應(yīng)概念如此重復(fù)，直至關(guān)系表中A的不同概念個(gè)數(shù)小于等于A的屬性閾值；最后合并相同記錄，并統(tǒng)計(jì)重復(fù)記錄數(shù)目第十張，PPT共二百頁(yè)，創(chuàng)作于2022年6月11數(shù)據(jù)規(guī)約屬性閾值均為4記錄由6個(gè)歸約為3個(gè)count的值表示重復(fù)記錄數(shù)目第十一張，PPT共二百頁(yè)，創(chuàng)作于2022年6月12屬性概念分層的自動(dòng)生成 概念分層一般由系統(tǒng)用戶、領(lǐng)域?qū)＜姨峁浅：臅r(shí)、乏味介紹離散屬性與連續(xù)屬性自動(dòng)生成概念分層的方法 離散屬性概念分層的自動(dòng)生成 概念層次樹(shù)中高層的概念個(gè)數(shù)一般少于低層的概念個(gè)數(shù)首先統(tǒng)計(jì)各個(gè)概念的不同值

8、個(gè)數(shù)，個(gè)數(shù)最少的概念在最高層，依次類(lèi)推，然后根據(jù)結(jié)構(gòu)的從屬關(guān)系，確定各層的概念及從屬關(guān)系 地址國(guó)家省市中國(guó)云南省昆明市中國(guó)云南省大理市中國(guó)四川省成都市中國(guó)貴州省貴陽(yáng)市中國(guó)云南省玉溪市中國(guó)云南省曲靖市第十二張，PPT共二百頁(yè)，創(chuàng)作于2022年6月13屬性概念分層的自動(dòng)生成 連續(xù)屬性概念分層的自動(dòng)生成 連續(xù)屬性可以通過(guò)離散化遞歸地自動(dòng)生成概念分層離散化可以基于熵完成，主要步驟：1）計(jì)算關(guān)系表r中在屬性A的取值區(qū)間V上的記錄集合S的熵 |c|：S中屬于目標(biāo)類(lèi)c的記錄數(shù)|S|：S中的記錄數(shù) 2）對(duì)A在V上取的每個(gè)v，用v劃分V為v1（v）、v2（v），劃分S為S1，S2，計(jì)算在此劃分下S的熵 E(S1

9、)、E(S2)分別為S1、S2的熵 第十三張，PPT共二百頁(yè)，創(chuàng)作于2022年6月14屬性概念分層的自動(dòng)生成 連續(xù)屬性概念分層的自動(dòng)生成 3）對(duì)在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作為其概念層次樹(shù)的根，形成最高層第一次劃分區(qū)間V1、V2是根的兩個(gè)子結(jié)點(diǎn)，形成次高層遞歸地應(yīng)用步驟1）4）就可以得到各層結(jié)點(diǎn)第十四張，PPT共二百頁(yè)，創(chuàng)作于2

10、022年6月15屬性概念分層的自動(dòng)生成 連續(xù)屬性概念分層的自動(dòng)生成 設(shè)“氣溫”屬性是目標(biāo)屬性，取值區(qū)間為100,100屬性值及記錄數(shù)如表所示屬性值36182226記錄數(shù)69362821劃分區(qū)間100,100第十五張，PPT共二百頁(yè)，創(chuàng)作于2022年6月16屬性概念分層的自動(dòng)生成 連續(xù)屬性概念分層的自動(dòng)生成 屬性值36182226記錄數(shù)69362821劃分區(qū)間100,100G(100, 100, 3)=2.03782.0378=0G(100, 100, 6)= 2.03781.7465=0.2913G(100, 100, 18)= 2.03781.464=0.5738G(100, 100, 22

11、)= 2.03781.0741=0.9637G(100, 100, 26)= 2.03781.3323=0.7055最佳劃分：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ī)則l=i1i2i5lvi1、i2lui1i2第三十六張，PPT共二百頁(yè)，創(chuàng)作于2022年6月37Apriori算法壓縮強(qiáng)關(guān)聯(lián)搜索空間對(duì)于每個(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ī)則，并

12、生成它們的2-后件集合R2R2通過(guò)R1中的后件進(jìn)行連接運(yùn)算，再通過(guò)置信度計(jì)算產(chǎn)生依次類(lèi)推，可以產(chǎn)生所有強(qiáng)關(guān)聯(lián)規(guī)則第三十七張，PPT共二百頁(yè)，創(chuàng)作于2022年6月38Apriori算法算法描述輸入：事務(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 （1.1）for t中的每個(gè)項(xiàng)i （1.1.1）i.sup_count=i.sup_count+1 /1-項(xiàng)集支持計(jì)數(shù)（2）for 每個(gè)項(xiàng)i （2.1）if i.sup_co

13、untnmin_sup then L1=L1i /找出頻繁1-項(xiàng)集第三十八張，PPT共二百頁(yè)，創(chuàng)作于2022年6月39Apriori算法算法描述（3）for (k=2；Lk-1；k+) （3.1）for Lk-1中的每個(gè)項(xiàng)集lu （3.1.1）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 /剪枝 （3.2）for T中的每個(gè)事務(wù)t （3.2.1）for t中的每個(gè)k-項(xiàng)集s if sCk then

14、s.sup_count=s.sup_count+1 /k-項(xiàng)集支持計(jì)數(shù)第三十九張，PPT共二百頁(yè)，創(chuàng)作于2022年6月40Apriori算法算法描述 （3.3）for Ck中的每個(gè)項(xiàng)集c （3.3.1）if c.sup_countnmin_sup then Lk=Lkc /找出頻繁k-項(xiàng)集 （3.4） L=LLk /規(guī)則產(chǎn)生（4）for L中的每個(gè)頻繁項(xiàng)集l （4.1）for l中的每個(gè)1-項(xiàng)集l1 （4.1.1） if then SR=SR(l-l1)=l1 /找出后件只有1項(xiàng)的強(qiáng)關(guān)聯(lián)規(guī)則 R1=R1l1 /找出1-后件 第四十張，PPT共二百頁(yè)，創(chuàng)作于2022年6月41Apriori算法算

15、法描述（4.2）for (j=2；Rj-1；j+) （4.2.1）for Rj-1中的每個(gè)后件lu for Rj-1中后件lu之后的每個(gè)后件lv if (lu1=lv1)(luj-2=lvj-2)(luj-1lvj-1) then /連接 if then SR=SR(l-lj)=lj /找出后件有j項(xiàng)的強(qiáng)關(guān)聯(lián)規(guī)則 Rj=Rjlj /找出j-后件l=i1i2i5lui1lvi2第四十一張，PPT共二百頁(yè)，創(chuàng)作于2022年6月42Apriori算法影響Apriori算法時(shí)間復(fù)雜度主要因素（1）事務(wù)集合當(dāng)項(xiàng)數(shù)m增加：候選項(xiàng)集的數(shù)目和長(zhǎng)度可能增加，頻繁項(xiàng)集的數(shù)目和長(zhǎng)度也可能增加，從而計(jì)算頻繁項(xiàng)集及其支

16、持計(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ù)目越多、長(zhǎng)度越長(zhǎng)，掃描事務(wù)集合的次數(shù)越多，算法的運(yùn)行時(shí)間越長(zhǎng)（3）最小置信度閾值min_confmin_conf越小，強(qiáng)關(guān)聯(lián)規(guī)則的數(shù)目越多，產(chǎn)生規(guī)則的運(yùn)行時(shí)間越長(zhǎng)第四十二張，PPT共二百頁(yè)，創(chuàng)作于2022年6月43頻繁項(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)集可以推

17、導(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 第四十三張，PPT共二百頁(yè)，創(chuàng)作于2022年6月44頻繁項(xiàng)集的緊湊表示 為了高效找出最大頻繁項(xiàng)集，可以將搜索空間按前綴或后綴變換為樹(shù)（前綴樹(shù)、后綴樹(shù) ），然后采用寬度或深度優(yōu)先策略進(jìn)行搜索前綴樹(shù)后綴樹(shù)第四十四張，PPT共二百頁(yè)，創(chuàng)作于2022年6月45頻繁項(xiàng)集的緊湊表示 寬度優(yōu)先是先搜索同一層的頻繁項(xiàng)集，再搜索下一層的頻繁項(xiàng)集 深度優(yōu)先是搜索到某層的一個(gè)頻集時(shí)，先搜索更深層的頻集，若沒(méi)有頻集則回溯，直至沒(méi)有頻項(xiàng)集產(chǎn)生也沒(méi)有回溯 深度優(yōu)先搜索策略可以更快地檢測(cè)到

18、頻繁項(xiàng)集邊界，通常用于搜索最大頻繁項(xiàng)集 深度優(yōu)先與最大頻繁項(xiàng)集搜索第四十五張，PPT共二百頁(yè)，創(chuàng)作于2022年6月46頻繁項(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 第四十六張，PPT共二百頁(yè)，創(chuàng)作于2022年6月47頻繁項(xiàng)集的緊湊表示 定理 對(duì)于頻繁項(xiàng)集l及其所有直接超集li=li(iI)，如果l是最大頻繁項(xiàng)集，則l是頻繁閉項(xiàng)集 sup_count(l) nmin_sup 證明：

19、定理 對(duì)于頻繁項(xiàng)集l及其所有直接超集li=li(iI)，如果l不是閉項(xiàng)集，則 證明： 基于該定理，頻繁非閉項(xiàng)集的支持計(jì)數(shù)可以通過(guò)頻繁閉項(xiàng)集的支持計(jì)數(shù)確定第四十七張，PPT共二百頁(yè)，創(chuàng)作于2022年6月48頻繁項(xiàng)集的緊湊表示 項(xiàng)集c不是閉項(xiàng)集，它的支持計(jì)數(shù)等于項(xiàng)集bc的支持計(jì)數(shù) 頻繁項(xiàng)集、頻繁閉項(xiàng)集與最大頻繁項(xiàng)集的關(guān)系 ： 第四十八張，PPT共二百頁(yè)，創(chuàng)作于2022年6月49頻繁項(xiàng)集的緊湊表示通過(guò)頻繁閉項(xiàng)集的支持計(jì)數(shù)計(jì)算其它頻繁非閉項(xiàng)集的支持計(jì)數(shù)的算法描述輸入：頻繁閉項(xiàng)集集合CL輸出：頻繁項(xiàng)集集合L步驟：（1） /找出頻繁閉項(xiàng)集的最大長(zhǎng)度（2） /找出最長(zhǎng)頻繁閉項(xiàng)集（3） /最長(zhǎng)頻繁閉項(xiàng)集也是最

20、長(zhǎng)頻繁項(xiàng)集（4）for (k=kmax-1；k1；k-) /找出所有頻繁項(xiàng)集 （4.1） /找出由頻繁閉(k+1)-項(xiàng)集推導(dǎo)的頻繁k-項(xiàng)集 （4.2）CLk=l|lCL,|l|=k /找出頻繁閉k-項(xiàng)集第四十九張，PPT共二百頁(yè)，創(chuàng)作于2022年6月50頻繁項(xiàng)集的緊湊表示通過(guò)頻繁閉項(xiàng)集的支持計(jì)數(shù)計(jì)算其它頻繁非閉項(xiàng)集的支持計(jì)數(shù)的算法描述（4.3）for TLk中每個(gè)項(xiàng)集 /計(jì)算頻繁非閉k-項(xiàng)集的支持計(jì)數(shù) （4.3.1）if then Lk= Lkl（4.4） Lk= LkCLk（4.5）L=LLk第五十張，PPT共二百頁(yè)，創(chuàng)作于2022年6月51頻繁項(xiàng)集的緊湊表示最小支持計(jì)數(shù)閾值是5，項(xiàng)集b:9

21、、ad:5、bc:7、bd:6和bcd:5是頻繁閉項(xiàng)集。寫(xiě)出計(jì)算頻繁非閉項(xiàng)集的支持計(jì)數(shù)的過(guò)程 L3 = CL3 = bcd TL2 = bc,bd,cd CL2 = ad,bc,bd cd.sup_count = 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,d第五十一張，PPT共二百頁(yè)，創(chuàng)作于2022年6月52FP-gr

22、owth算法 Apriori算法的不足：1）可能產(chǎn)生大量候選項(xiàng)集2）可能需要重復(fù)掃描數(shù)據(jù)庫(kù)，通過(guò)模式匹配檢查龐大的候選集合FP-growth算法采用一種稱為FP樹(shù)的結(jié)構(gòu)表示事務(wù)集合中項(xiàng)集的關(guān)聯(lián)，并在FP樹(shù)上遞歸地找出所有頻繁項(xiàng)集，算法并不產(chǎn)生候選基本思想：掃描一次事務(wù)集合，找出頻繁1-項(xiàng)集合L1基于L1，再掃描一次事務(wù)集合，構(gòu)造表示事務(wù)集合中項(xiàng)集關(guān)聯(lián)的FP樹(shù)在FP樹(shù)上遞歸地找出所有頻繁項(xiàng)集最后在所有頻繁項(xiàng)集中產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則 第五十二張，PPT共二百頁(yè)，創(chuàng)作于2022年6月53FP-growth算法 1）掃描一次事務(wù)集合，找出頻繁1-項(xiàng)集合L，并按支持計(jì)數(shù)降序排序L中的頻繁項(xiàng)FP樹(shù)構(gòu)造 事務(wù)項(xiàng)t

23、1i1，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樹(shù)的根節(jié)點(diǎn)，用“null”標(biāo)記null第五十三張，PPT共二百頁(yè)，創(chuàng)作于2022年6月54FP-growth算法 3）再掃描一次事務(wù)集合，對(duì)每個(gè)事務(wù)找出其中的頻繁項(xiàng)并按L中的順序排序，為每個(gè)事務(wù)創(chuàng)建一個(gè)分枝，事務(wù)分枝路徑上的節(jié)點(diǎn)就是該事務(wù)中的已排序頻繁項(xiàng)對(duì)于各個(gè)事務(wù)分枝，如果可以共享路徑則共享并且在各個(gè)節(jié)點(diǎn)上記錄共享事務(wù)數(shù)目FP樹(shù)構(gòu)造 事務(wù)項(xiàng)t1i1，

24、i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3L=i2:7, i1:6, i3:5, i4:2, i5:2 第五十四張，PPT共二百頁(yè)，創(chuàng)作于2022年6月55FP-growth算法 FP樹(shù)構(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 4）為方便遍歷FP樹(shù)，為FP樹(shù)創(chuàng)建一個(gè)項(xiàng)表項(xiàng)表中每一行表示一個(gè)頻繁項(xiàng)，并有一個(gè)指針指向它在F

25、P樹(shù)中的節(jié)點(diǎn)FP樹(shù)中相同頻繁項(xiàng)的節(jié)點(diǎn)通過(guò)指針連成鏈表 第五十五張，PPT共二百頁(yè)，創(chuàng)作于2022年6月56FP-growth算法 FP樹(shù)構(gòu)造 事務(wù)項(xiàng)t1i1，i2，i5t2i2，i4t3i2，i3t4i1，i2，i4t5i1，i3t6i2，i3t7i1，i3t8i1，i2，i5t9i1，i2，i3第五十六張，PPT共二百頁(yè)，創(chuàng)作于2022年6月57FP-growth算法 由長(zhǎng)度為1的頻繁模式（初始后綴模式）開(kāi)始，構(gòu)造它的條件模式基。然后，構(gòu)造它的條件FP樹(shù)，并遞歸地在該樹(shù)上進(jìn)行挖掘。模式增長(zhǎng)通過(guò)后綴模式與由條件FP樹(shù)產(chǎn)生的頻繁模式連接實(shí)現(xiàn)條件模式基：一個(gè)“子數(shù)據(jù)庫(kù)”，由FP樹(shù)中與后綴模式一起出

26、現(xiàn)的前綴路徑集組成條件FP樹(shù)：條件模式基中，由滿足最小支持度閾值的節(jié)點(diǎn)構(gòu)成的樹(shù)FP樹(shù)挖掘i5:2的條件模式基null,i2,i1:2 i5:2 與條件FP樹(shù) 第五十七張，PPT共二百頁(yè)，創(chuàng)作于2022年6月58FP-growth算法 遞歸過(guò)程：1）如果條件FP樹(shù)只有一個(gè)分枝，則分枝路徑上的節(jié)點(diǎn)的一個(gè)組合就是一個(gè)前綴模式，一個(gè)前綴模式與后綴模式產(chǎn)生一個(gè)頻繁項(xiàng)集（遞歸出口）2）否則用L中的頻繁項(xiàng)i增長(zhǎng)后綴模式 （i ，增長(zhǎng)時(shí)，按逆序方式處理，即先考慮L的最后一項(xiàng)），然后構(gòu)造增長(zhǎng)后綴模式i 的條件模式基與條件FP樹(shù)，遞歸上述過(guò)程初始時(shí)，=null，null的條件FP樹(shù)就是FP樹(shù)FP樹(shù)挖掘第五十八張，

27、PPT共二百頁(yè)，創(chuàng)作于2022年6月59FP-growth算法 第二層遞歸：FP樹(shù)挖掘條件模式基條件FP樹(shù)產(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樹(shù)有多個(gè)分枝，進(jìn)入第二層遞歸i3:5的條件FP樹(shù)有兩個(gè)分枝，進(jìn)入第三層遞歸 第五十九張，PPT共二百頁(yè)，創(chuàng)作于2022年6月60FP-growth算法

28、 第三層遞歸：FP樹(shù)挖掘條件模式基條件FP樹(shù)產(chǎn)生的頻繁項(xiàng)集i1i3:3null,i2:1、null:2i1i3:3i2i3:3null:3i2i3:3第六十張，PPT共二百頁(yè)，創(chuàng)作于2022年6月61FP-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樹(shù)的根節(jié)點(diǎn)null /創(chuàng)建FP樹(shù)（4）for T中的每個(gè)事務(wù)t （4.1）找出t中的頻繁1-項(xiàng)集合Lt （4.2）Lt中的項(xiàng)按L中的順序排序 （4.3）Insert-FP（Lt, null

29、） /創(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算法描述第六十一張，PPT共二百頁(yè)，創(chuàng)作于2022年6月62FP-growth算法 算法：Insert-FP算法（Li, Tr）輸入：已排序頻繁1-項(xiàng)集合Li，F(xiàn)P（子）樹(shù)的根節(jié)點(diǎn)Tr輸出：FP樹(shù)（1）if Li不空 then （1.1）取出Li中的第1個(gè)項(xiàng)i （1.2）if Tr的某個(gè)子節(jié)點(diǎn)Node是i then （1.2.1）Node.count=Node.count+1 （1.3）else （1.3.1）創(chuàng)建Tr的子節(jié)點(diǎn)Node為i （1.3.2）Node.c

30、ount=1 （1.3.3）將Node加入項(xiàng)表鏈中（1.4）Insert-FP（Li-i, Node）算法描述第六十二張，PPT共二百頁(yè)，創(chuàng)作于2022年6月63FP-growth算法 算法：Search-FP算法（T，）輸入：（條件）FP樹(shù)T，后綴模式輸出：頻繁項(xiàng)集集合L_S（1）if T中只有一個(gè)分枝P then （1.1）for P上的節(jié)點(diǎn)的每個(gè)組合 （1.1.1）= /產(chǎn)生頻繁項(xiàng)集 （1.1.2）L_S= L_S（2）else （2.1）for T中的每個(gè)頻繁項(xiàng)i （2.1.1）=i /增長(zhǎng)后綴模式 （2.1.2）構(gòu)造的條件模式基及其條件FP樹(shù)T （2.1.3） Search-FP（T

31、, ）算法描述第六十三張，PPT共二百頁(yè)，創(chuàng)作于2022年6月64分析技術(shù)及模型聚類(lèi)分析第六十四張，PPT共二百頁(yè)，創(chuàng)作于2022年6月65將物理或抽象對(duì)象的集合分成相似的對(duì)象類(lèi)的過(guò)程使得同一個(gè)簇中的對(duì)象之間具有較高的相似性，而不同簇中的對(duì)象具有較高的相異性是數(shù)據(jù)挖掘、模式識(shí)別等研究方向的重要研究?jī)?nèi)容之一，在識(shí)別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面具有極其重要的作用 廣泛應(yīng)用于模式識(shí)別、數(shù)據(jù)分析、圖像處理和市場(chǎng)研究等領(lǐng)域，對(duì)生物學(xué)、心理學(xué)、考古學(xué)、地質(zhì)學(xué)及地理學(xué)等研究也有重要作用 主要介紹聚類(lèi)概念、聚類(lèi)過(guò)程、常用聚類(lèi)算法 聚類(lèi)分析第六十五張，PPT共二百頁(yè)，創(chuàng)作于2022年6月66=o1, o2, , on表示

32、一個(gè)對(duì)象集合oi表示第i個(gè)對(duì)象，i=1, 2,nCx表示第x個(gè)簇，Cx，x=1，2，kSimilarity(oi, oj)表示對(duì)象oi與對(duì)象oj之間的相似度若各簇Cx是剛性聚類(lèi)結(jié)果，則各Cx需滿足如下條件：1）2）對(duì)于 有3）聚類(lèi)分析的形式描述第六十六張，PPT共二百頁(yè)，創(chuàng)作于2022年6月67數(shù)據(jù)準(zhǔn)備屬性選擇屬性提取聚類(lèi)結(jié)果評(píng)估聚類(lèi)過(guò)程為聚類(lèi)分析準(zhǔn)備數(shù)據(jù)，包括屬性值標(biāo)準(zhǔn)化從最初的屬性中選擇最有效的屬性通過(guò)對(duì)所選擇的屬性進(jìn)行轉(zhuǎn)換形成新的更有代表性的屬性度量對(duì)象間的相似性程度，執(zhí)行聚類(lèi)或分組 聚類(lèi)分析的三要素是相似性測(cè)度、聚類(lèi)準(zhǔn)則和聚類(lèi)算法第六十七張，PPT共二百頁(yè)，創(chuàng)作于2022年6月68聚類(lèi)

33、分析中的數(shù)據(jù)類(lèi)型聚類(lèi)分析中常用的數(shù)據(jù)類(lèi)型有：數(shù)據(jù)矩陣、相異度矩陣1）數(shù)據(jù)矩陣：對(duì)象在多維空間中通常表示為點(diǎn)（向量），其每一維表示為不同屬性，這些屬性描述出對(duì)象數(shù)據(jù)矩陣每行代表一個(gè)對(duì)象，每列代表對(duì)象的一個(gè)屬性2）相異度矩陣：存儲(chǔ)n個(gè)對(duì)象兩兩之間的近似性，d(i,j)是對(duì)象i和對(duì)象j之間相異性的量化表示第六十八張，PPT共二百頁(yè)，創(chuàng)作于2022年6月69聚類(lèi)分析三要素相似性測(cè)度、聚類(lèi)準(zhǔn)則和聚類(lèi)算法相似性測(cè)度：衡量同簇對(duì)象的類(lèi)似性和不同簇對(duì)象的差異性 聚類(lèi)準(zhǔn)則：評(píng)價(jià)聚類(lèi)結(jié)果的好壞 聚類(lèi)算法：用于找出使準(zhǔn)則函數(shù)取極值的最好聚類(lèi)結(jié)果 實(shí)際上，確定了相似性測(cè)度和聚類(lèi)準(zhǔn)則后，聚類(lèi)就變成了使準(zhǔn)則函數(shù)取極值的優(yōu)

34、化問(wèn)題了 沒(méi)有任何一種聚類(lèi)算法可以普遍適用于揭示各種多維數(shù)據(jù)集所呈現(xiàn)出來(lái)的多種多樣的結(jié)構(gòu) 因此聚類(lèi)算法有多種，不同的聚類(lèi)算法使用不同的相似性度量和準(zhǔn)則第六十九張，PPT共二百頁(yè)，創(chuàng)作于2022年6月70對(duì)象之間的相似性根據(jù)描述對(duì)象的屬性值評(píng)估，可以使用距離、密度、連通性或概念度量距離相似性度量：距離越近越相似，不同簇中任意兩個(gè)對(duì)象間的距離都大于簇內(nèi)任意兩個(gè)對(duì)象之間的距離 密度相似性度量：密度（單位區(qū)域內(nèi)的對(duì)象數(shù) ）越相近，相似性越高，簇是對(duì)象的稠密區(qū)域，被低密度的區(qū)域環(huán)繞 連通性相似性度量：使用圖的連通性度量相似性，簇定義為圖的連通分支，即互相連通但不與組外對(duì)象連通的對(duì)象組 概念相似性度量：共

35、性（比如共享最近鄰）越多越相似 ，簇定義為有某種共同性質(zhì)的對(duì)象的集合 相似性測(cè)度第七十張，PPT共二百頁(yè)，創(chuàng)作于2022年6月71主要的聚類(lèi)算法大致可以分為：劃分式聚類(lèi)算法、基于密度的聚類(lèi)算法、層次聚類(lèi)算法、基于網(wǎng)格的聚類(lèi)算法和基于模型的聚類(lèi)算法聚類(lèi)算法分類(lèi)劃分式聚類(lèi)算法（partitioning method）預(yù)先指定聚類(lèi)數(shù)目或聚類(lèi)中心，通過(guò)反復(fù)迭代運(yùn)算，逐步優(yōu)化準(zhǔn)則函數(shù)的值，當(dāng)準(zhǔn)則函數(shù)收斂時(shí)，得到最終聚類(lèi)結(jié)果k均值算法、k中心點(diǎn)算法及它們的變種基于密度的聚類(lèi)算法（density-based method）通過(guò)數(shù)據(jù)密度來(lái)發(fā)現(xiàn)簇DBSCAN、OPTICS、DENCLUE第七十一張，PPT共二百

36、頁(yè)，創(chuàng)作于2022年6月72聚類(lèi)算法分類(lèi)基于網(wǎng)格的聚類(lèi)算法（gridbased method）將對(duì)象空間量化為有限數(shù)目的單元，形成網(wǎng)格結(jié)構(gòu)，所有的聚類(lèi)操作都在網(wǎng)格上進(jìn)行，從而獲得較快的處理速度STING、WaveCluster層次聚類(lèi)算法（hierarchical method）將數(shù)據(jù)對(duì)象組織成一棵聚類(lèi)樹(shù)，使用數(shù)據(jù)的聯(lián)接規(guī)則，透過(guò)一種架構(gòu)方式，反復(fù)將數(shù)據(jù)進(jìn)行分裂或聚合，以形成一個(gè)層次序列的聚類(lèi)問(wèn)題解 BIRCH、ROCK和Chameleon 等第七十二張，PPT共二百頁(yè)，創(chuàng)作于2022年6月73聚類(lèi)算法分類(lèi)基于模型的聚類(lèi)算法（model-based method）基于“數(shù)據(jù)根據(jù)潛在的混合概率分

37、布生成”假設(shè)，為每個(gè)簇假定一個(gè)模型，并尋找數(shù)據(jù)對(duì)給定模型的最佳擬合這類(lèi)算法通過(guò)構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來(lái)定位簇，能考慮“噪聲”數(shù)據(jù)和離群點(diǎn)的影響，魯棒性較好 EM 、COBWEB 、SOM 第七十三張，PPT共二百頁(yè)，創(chuàng)作于2022年6月74均值聚類(lèi)算法均值聚類(lèi)算法假定所有數(shù)據(jù)對(duì)象可分為k個(gè)簇，每個(gè)簇的中心用均值表示對(duì)象間的相似性用距離度量聚類(lèi)的準(zhǔn)則是誤差平方和準(zhǔn)則 核心思想：首先選定k個(gè)初始聚類(lèi)中心，根據(jù)最小距離原則將每個(gè)數(shù)據(jù)對(duì)象分配到某一簇中然后不斷迭代計(jì)算各個(gè)簇的聚類(lèi)中心并依新的聚類(lèi)中心調(diào)整聚類(lèi)情況，直至收斂（J 值不再變化）第七十四張，PPT共二百頁(yè)，創(chuàng)作于2022年6月75均

38、值聚類(lèi)算法誤差平方和準(zhǔn)則若Nx是第Cx個(gè)簇中的對(duì)象數(shù)目，mx是這些對(duì)象的均值， J是所有簇的簇中各個(gè)對(duì)象與均值間的誤差平方和之和對(duì)于不同的聚類(lèi)，J的值不同使J 值極小的聚類(lèi)是誤差平方和準(zhǔn)則下的最優(yōu)結(jié)果度量了用k個(gè)聚類(lèi)中心m1,mk代表k個(gè)簇C1,Ck時(shí)所產(chǎn)生的總的誤差平方和第七十五張，PPT共二百頁(yè)，創(chuàng)作于2022年6月76均值聚類(lèi)算法算法描述輸入：數(shù)據(jù)對(duì)象集合D，簇?cái)?shù)目k輸出：k個(gè)簇的集合步驟：1. 從D中隨機(jī)選取k個(gè)不同的數(shù)據(jù)對(duì)象作為k個(gè)簇C1，Ck的中心m1，mk2. repeat1）for D中每個(gè)數(shù)據(jù)對(duì)象oa. 尋找i，b. 將o分配給簇Ci2）for 每個(gè)簇Ci（i=1，k）計(jì)算

39、3）計(jì)算平方誤差3. Until J不再發(fā)生變化計(jì)算新的聚類(lèi)中心，|Ci|為當(dāng)前簇中的對(duì)象數(shù)目第七十六張，PPT共二百頁(yè)，創(chuàng)作于2022年6月77均值聚類(lèi)算法算法簡(jiǎn)單，計(jì)算復(fù)雜度是O(nkt)，其中n是對(duì)象的總數(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)T(0.777,0.960)T第一百?gòu)垼琍P

40、T共二百頁(yè)，創(chuàng)作于2022年6月101模糊c-均值聚類(lèi)算法xi相對(duì)于 的隸屬度 x1x2x3x4x50.9610.9810.9460.0380.0400.0390.0190.0540.9620.960聚類(lèi)過(guò)程終止 第一百零一張，PPT共二百頁(yè)，創(chuàng)作于2022年6月102分析技術(shù)及模型分類(lèi)分析第一百零二張，PPT共二百頁(yè)，創(chuàng)作于2022年6月103分類(lèi)與預(yù)測(cè)是普遍存在的問(wèn)題，具有廣泛的應(yīng)用領(lǐng)域分類(lèi)的任務(wù)是通過(guò)分析由已知類(lèi)別數(shù)據(jù)對(duì)象組成的訓(xùn)練數(shù)據(jù)集，建立描述并區(qū)分?jǐn)?shù)據(jù)對(duì)象類(lèi)別的分類(lèi)函數(shù)或分類(lèi)模型（分類(lèi)器）分類(lèi)的目的是利用分類(lèi)模型判定未知類(lèi)別數(shù)據(jù)對(duì)象的所屬類(lèi)別，判定的目標(biāo)是數(shù)據(jù)對(duì)象在類(lèi)別屬性（離散）

41、上的取值預(yù)測(cè)也要通過(guò)分析訓(xùn)練數(shù)據(jù)集建立預(yù)測(cè)模型，然后利用模型預(yù)測(cè)數(shù)據(jù)對(duì)象，預(yù)測(cè)的目標(biāo)是判定數(shù)據(jù)對(duì)象在預(yù)測(cè)屬性（連續(xù)）上的取值或取值區(qū)間分類(lèi)與聚類(lèi)有顯著區(qū)別：分類(lèi)中，訓(xùn)練樣本的類(lèi)別是已知的（有指導(dǎo)），而聚類(lèi)中所有數(shù)據(jù)都沒(méi)有類(lèi)別標(biāo)簽（無(wú)指導(dǎo)）主要介紹分類(lèi)過(guò)程、分類(lèi)模型評(píng)估方法、常用分類(lèi)算法分類(lèi)分析第一百零三張，PPT共二百頁(yè)，創(chuàng)作于2022年6月104分類(lèi)過(guò)程分為兩個(gè)階段：學(xué)習(xí)階段與分類(lèi)階段分類(lèi)過(guò)程訓(xùn)練樣本輸入分類(lèi)模型測(cè)試樣本輸入新數(shù)據(jù)分類(lèi)算法學(xué)習(xí)過(guò)程分類(lèi)過(guò)程每個(gè)訓(xùn)練樣本由m+1個(gè)屬性描述，X=（A1, , Am, C）Ai對(duì)應(yīng)描述屬性，可以是連續(xù)屬性或離散屬性C表示類(lèi)別屬性，有k個(gè)不同的類(lèi)別，C

42、=（c1, c2, , ck）從描述屬性矢量（X-C）到類(lèi)別屬性C的映射函數(shù)H:（X-C）C分類(lèi)規(guī)則、判定樹(shù)等形式X=（A1, , Am）確定CX=（A1, , Am,C）提供X=（A1, , Am)，確定C，比較C、C用于尋找映射函數(shù)H第一百零四張，PPT共二百頁(yè)，創(chuàng)作于2022年6月105分類(lèi)算法有多種：決策樹(shù)分類(lèi)算法、神經(jīng)網(wǎng)絡(luò)分類(lèi)算法、貝葉斯分類(lèi)算法、k-最近鄰分類(lèi)算法、遺傳分類(lèi)算法、粗糙集分類(lèi)算法、模糊集分類(lèi)算法等 分類(lèi)算法可以根據(jù)下列標(biāo)準(zhǔn)進(jìn)行比較和評(píng)估：1）準(zhǔn)確率：分類(lèi)模型正確地預(yù)測(cè)新樣本所屬類(lèi)別的能力2）速度：建立和使用分類(lèi)模型的計(jì)算開(kāi)銷(xiāo)3）強(qiáng)壯性：給定噪聲數(shù)據(jù)或具有空缺值的數(shù)據(jù)，

43、分類(lèi)模型正確地預(yù)測(cè)的能力4）可伸縮性：給定大量數(shù)據(jù)，有效地建立分類(lèi)模型的能力5）可解釋性：分類(lèi)模型提供的理解和洞察的層次分類(lèi)算法評(píng)估標(biāo)準(zhǔn)第一百零五張，PPT共二百頁(yè)，創(chuàng)作于2022年6月106利用測(cè)試數(shù)據(jù)集評(píng)估分類(lèi)模型的準(zhǔn)確率分類(lèi)模型正確分類(lèi)的測(cè)試樣本數(shù)占總測(cè)試樣本數(shù)的百分比準(zhǔn)確率可以接受，對(duì)新樣本進(jìn)行分類(lèi)；否則，重新建立分類(lèi)模型評(píng)估分類(lèi)模型準(zhǔn)確率的方法有保持、k-折交叉確認(rèn)保持方法將已知類(lèi)別的樣本隨機(jī)地劃分為訓(xùn)練數(shù)據(jù)集與測(cè)試數(shù)據(jù)集兩個(gè)集合，一般，訓(xùn)練數(shù)據(jù)集占2/3，測(cè)試數(shù)據(jù)集占1/3k-折交叉確認(rèn)方法將已知類(lèi)別的樣本隨機(jī)地劃分為大小大致相等的k個(gè)子集S1, , Sk，并進(jìn)行k次訓(xùn)練與測(cè)試第i

44、次，Si作為測(cè)試數(shù)據(jù)集，其余子集的并集作為訓(xùn)練數(shù)據(jù)集k次訓(xùn)練得到k個(gè)分類(lèi)模型，測(cè)試時(shí)，將出現(xiàn)次數(shù)最多的分類(lèi)結(jié)果作為最終的分類(lèi)結(jié)果分類(lèi)模型評(píng)估方法第一百零六張，PPT共二百頁(yè)，創(chuàng)作于2022年6月107適宜多峰分布的分類(lèi)問(wèn)題 決策樹(shù)以樹(shù)結(jié)構(gòu)的形式表示，類(lèi)似流程圖一棵決策樹(shù)由一個(gè)根節(jié)點(diǎn)，一組內(nèi)部節(jié)點(diǎn)和一組葉節(jié)點(diǎn)組成決策樹(shù)分類(lèi)算法每個(gè)分枝表示一個(gè)測(cè)試輸出每個(gè)葉節(jié)點(diǎn)表示一個(gè)類(lèi)，不同的葉節(jié)點(diǎn)可表示相同的類(lèi) 根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試第一百零七張，PPT共二百頁(yè)，創(chuàng)作于2022年6月108建立了決策樹(shù)之后，可以對(duì)從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每條路徑創(chuàng)建一條IF-THEN分類(lèi)規(guī)則，易于理解沿著路徑，每個(gè)內(nèi)

45、部節(jié)點(diǎn)-分枝對(duì)形成規(guī)則前件（IF部分）的一個(gè)合取項(xiàng)，葉節(jié)點(diǎn)形成規(guī)則后件（THEN部分）決策樹(shù)分類(lèi)算法IF 年齡=41 AND 信譽(yù)=中 THEN 購(gòu)買(mǎi)計(jì)算機(jī)=是IF 年齡=30 AND 學(xué)生=否 THEN 購(gòu)買(mǎi)計(jì)算機(jī)=否-否新顧客：教師，年齡45歲，收入較低但信譽(yù)很好該顧客是否會(huì)購(gòu)買(mǎi)計(jì)算機(jī)？第一百零八張，PPT共二百頁(yè)，創(chuàng)作于2022年6月109決策樹(shù)分類(lèi)算法的關(guān)鍵是建立決策樹(shù)建立一棵決策樹(shù)，需要解決的問(wèn)題主要有：1）如何選擇測(cè)試屬性？測(cè)試屬性的選擇順序影響決策樹(shù)的結(jié)構(gòu)甚至決策樹(shù)的準(zhǔn)確率一般使用信息增益度量來(lái)選擇測(cè)試屬性2）如何停止劃分樣本？從根節(jié)點(diǎn)測(cè)試屬性開(kāi)始，每個(gè)內(nèi)部節(jié)點(diǎn)測(cè)試屬性都把樣本空

46、間劃分為若干個(gè)（子）區(qū)域一般當(dāng)某個(gè)（子）區(qū)域的樣本同類(lèi)時(shí)，就停止劃分樣本，有時(shí)也通過(guò)閾值提前停止劃分樣本決策樹(shù)分類(lèi)算法第一百零九張，PPT共二百頁(yè)，創(chuàng)作于2022年6月110使用遞歸方式完成基本思想：首先，將整個(gè)訓(xùn)練數(shù)據(jù)集S、所有描述屬性A1, A2, , Am作為分析對(duì)象如果S中的樣本屬于同一類(lèi)別，則將S作為葉節(jié)點(diǎn)并用其中樣本的類(lèi)別標(biāo)識(shí)，決策樹(shù)建立完成否則在S上計(jì)算各個(gè)屬性的信息增益G(C, Ak)，選擇信息增益最大的屬性Ai作為根節(jié)點(diǎn)的測(cè)試屬性如果Ai的取值個(gè)數(shù)為v（取值記為a1, a2, , av），則Ai將S劃分為v個(gè)子集S1, S2, , Sv，同時(shí)根節(jié)點(diǎn)產(chǎn)生v個(gè)分枝與之對(duì)應(yīng)分別在訓(xùn)

47、練數(shù)據(jù)子集S1, S2, , Sv、剩余描述屬性A1, , Ai-1, Ai+1, , Am上采用相同方法遞歸地建立決策樹(shù)子樹(shù)決策樹(shù)分類(lèi)算法建立決策樹(shù)Sv：S中Ai=av的樣本集合第一百一十張，PPT共二百頁(yè)，創(chuàng)作于2022年6月111遞歸過(guò)程中，某節(jié)點(diǎn)對(duì)應(yīng)的訓(xùn)練數(shù)據(jù)（子）集由整個(gè)訓(xùn)練數(shù)據(jù)集S中滿足從根節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所有屬性測(cè)試的訓(xùn)練樣本組成某節(jié)點(diǎn)對(duì)應(yīng)的描述屬性是去除從根節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所有已選描述屬性后的剩余描述屬性同一層內(nèi)部節(jié)點(diǎn)選擇的測(cè)試屬性可能相同也可能不同決策樹(shù)分類(lèi)算法建立決策樹(shù)第一百一十一張，PPT共二百頁(yè)，創(chuàng)作于2022年6月112遞歸結(jié)束條件：1）某節(jié)點(diǎn)對(duì)應(yīng)的訓(xùn)練數(shù)據(jù)（子）

48、集中的樣本屬于同一類(lèi)別2）某節(jié)點(diǎn)對(duì)應(yīng)的訓(xùn)練數(shù)據(jù)（子）集為空此時(shí)，該節(jié)點(diǎn)作為葉節(jié)點(diǎn)并用父節(jié)點(diǎn)中占多數(shù)的樣本類(lèi)別標(biāo)識(shí)3）某節(jié)點(diǎn)沒(méi)有對(duì)應(yīng)的（剩余）描述屬性此時(shí)，該節(jié)點(diǎn)作為葉節(jié)點(diǎn)并用該節(jié)點(diǎn)中占多數(shù)的樣本類(lèi)別標(biāo)識(shí)決策樹(shù)分類(lèi)算法建立決策樹(shù)第一百一十二張，PPT共二百頁(yè)，創(chuàng)作于2022年6月113輸入：訓(xùn)練數(shù)據(jù)集S，描述屬性集合A輸出：決策樹(shù)步驟：（1）創(chuàng)建對(duì)應(yīng)S的節(jié)點(diǎn)Node（2）if S中的樣本屬于同一類(lèi)別c then 以c標(biāo)識(shí)Node并將Node作為葉節(jié)點(diǎn)返回（3）if A為空 then 以S中占多數(shù)的樣本類(lèi)別c標(biāo)識(shí)Node并將Node作為葉節(jié)點(diǎn)返回（4）從A中選擇對(duì)S而言信息增益最大的描述屬性Ai作

49、為Node的測(cè)試屬性決策樹(shù)分類(lèi)算法算法描述第一百一十三張，PPT共二百頁(yè)，創(chuàng)作于2022年6月114（5）for Ai的每個(gè)可能取值aj（1jv） （5.1）產(chǎn)生S的一個(gè)子集Sj （5.2）if Sj為空 then 創(chuàng)建對(duì)應(yīng)Sj的節(jié)點(diǎn)Nj，以S中占多數(shù)的樣本類(lèi)別c標(biāo)識(shí)Nj，并將Nj作為葉節(jié)點(diǎn)形成Node的一個(gè)分枝 （5.3）else 由（Sj, A-Ai）創(chuàng)建子樹(shù)形成Node的一個(gè)分枝決策樹(shù)分類(lèi)算法算法描述第一百一十四張，PPT共二百頁(yè)，創(chuàng)作于2022年6月115決策樹(shù)分類(lèi)算法信息增益類(lèi)別屬性C的無(wú)條件熵：給定描述屬性Ak，類(lèi)別屬性C的條件熵：n：樣本總數(shù) u：C的可能取值個(gè)數(shù)，即類(lèi)別數(shù)si：

50、屬于類(lèi)別ci的記錄集合 |si|：屬于類(lèi)別ci的記錄總數(shù)v：Ak的可能取值個(gè)數(shù) sj：Ak=aj的記錄集合 |sj|：Ak=aj的記錄數(shù)目Sij：Ak=aj且屬于類(lèi)別ci的記錄集合 |sij|：Ak=aj且屬于類(lèi)別ci的記錄數(shù)目 給定描述屬性Ak，類(lèi)別C的信息增益：G(C, Ak)=E(C)-E(C, Ak) G(C, Ak)反映Ak減少C不確定性的程度，G(C, Ak)越大，Ak對(duì)減少C不確定性的貢獻(xiàn)越大 第一百一十五張，PPT共二百頁(yè)，創(chuàng)作于2022年6月116決策樹(shù)分類(lèi)算法信息增益 蔬菜數(shù)據(jù)表如表所示，“顏色”、“形狀”是描述屬性，“蔬菜”是類(lèi)別屬性，分別求給定“顏色”、“形狀”屬性時(shí)，

51、“蔬菜”屬性的信息增益 顏色形狀蔬菜紅圓蕃茄紫長(zhǎng)茄子綠長(zhǎng)黃瓜G(蔬菜，顏色)1.5850-0=1.5850G(蔬菜，形狀)1.5850-0.6667=0.9183 G(蔬菜，顏色)G(蔬菜，形狀) 不同描述屬性減少類(lèi)別屬性不確定性的程度不同第一百一十六張，PPT共二百頁(yè)，創(chuàng)作于2022年6月117決策樹(shù)分類(lèi)算法信息增益盡量選擇對(duì)減少類(lèi)別屬性不確定性貢獻(xiàn)最大的描述屬性分類(lèi)模型包含盡可能少的描述屬性從而使模型簡(jiǎn)單 G(蔬菜，顏色)G(蔬菜，形狀) 測(cè)試屬性的選擇順序影響決策樹(shù)的結(jié)構(gòu)甚至決策樹(shù)的準(zhǔn)確率決策樹(shù)分類(lèi)算法要求描述屬性是離散屬性，連續(xù)屬性需要離散化 第一百一十七張，PPT共二百頁(yè)，創(chuàng)作于20

52、22年6月118決策樹(shù)分類(lèi)算法噪聲處理如果訓(xùn)練數(shù)據(jù)集含有噪聲，決策樹(shù)的某些分枝反映的是噪聲而不是總體，應(yīng)該剪去這些不可靠的分枝，提高決策樹(shù)的分類(lèi)準(zhǔn)確率有兩種剪枝策略： 先剪枝策略：在建立決策樹(shù)的過(guò)程中，通過(guò)某度量標(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ù)的記錄類(lèi)別標(biāo)識(shí) 后剪枝策略：首先，建立完整的決策樹(shù)；然后，通過(guò)某度量標(biāo)準(zhǔn)判斷哪些內(nèi)部節(jié)點(diǎn)分枝是不可靠的，將這些內(nèi)部節(jié)點(diǎn)變成葉節(jié)點(diǎn)并用其中占多數(shù)的記錄類(lèi)別標(biāo)識(shí)，從而達(dá)到剪枝第一百一十八張，PPT共二百頁(yè)，創(chuàng)作于2022年6月119前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)

53、算法神經(jīng)網(wǎng)絡(luò)可以模仿人腦，通過(guò)學(xué)習(xí)訓(xùn)練數(shù)據(jù)集，生成分類(lèi)模型適用于數(shù)據(jù)沒(méi)有任何明顯模式的情況 樣本屬性可以是連續(xù)的，也可以是離散的神經(jīng)網(wǎng)絡(luò)由許多單元（神經(jīng)元）以適當(dāng)?shù)姆绞竭B接起來(lái)構(gòu)成單元模仿人腦的神經(jīng)元，單元之間的連接相當(dāng)于人腦中神經(jīng)元的連接單元之間的連接方式有多種，從而形成了多種神經(jīng)網(wǎng)絡(luò)在分類(lèi)中，應(yīng)用較多的是前饋神經(jīng)網(wǎng)絡(luò)主要介紹前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)、網(wǎng)絡(luò)學(xué)習(xí)及網(wǎng)絡(luò)分類(lèi)方法 第一百一十九張，PPT共二百頁(yè)，創(chuàng)作于2022年6月120前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)算法網(wǎng)絡(luò)結(jié)構(gòu)前饋神經(jīng)網(wǎng)絡(luò)是分層網(wǎng)絡(luò)模型，具有一個(gè)輸入層和一個(gè)輸出層，輸入層和輸出層之間有一個(gè)或多個(gè)隱藏層每個(gè)層具有若干單元，前一層單元與后一層單元之間通過(guò)

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

55、個(gè)單元的輸入都是前一層各單元輸出的加權(quán)和，輸出是輸入的某種函數(shù)，稱為激活函數(shù)第一百二十一張，PPT共二百頁(yè)，創(chuàng)作于2022年6月122前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)算法網(wǎng)絡(luò)結(jié)構(gòu)隱藏層、輸出層任意單元j的輸入： 輸出 ： Oj= f (netj) 如果f采用S型激活函數(shù)：對(duì)于隱藏層、輸出層任意單元j，由輸入計(jì)算輸出的過(guò)程 ： 單元i的輸出單元j與前一層單元i之間的連接權(quán)改變單元j活性的偏置，1，1上取值則第一百二十二張，PPT共二百頁(yè)，創(chuàng)作于2022年6月123前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)算法網(wǎng)絡(luò)學(xué)習(xí)不同的單元的偏置及單元之間的連接權(quán)會(huì)獲得不同的輸出學(xué)習(xí)過(guò)程就是調(diào)整各單元的偏置及單元之間的連接權(quán)值，使每個(gè)訓(xùn)練樣本在輸出層

56、單元上獲得的輸出與其期望輸出間的誤差最小學(xué)習(xí)使用誤差后向傳播算法基本思想：首先賦予每條有向加權(quán)邊初始權(quán)值、每個(gè)隱藏層與輸出層單元初始偏置然后迭代地處理每個(gè)訓(xùn)練樣本，輸入它的描述屬性值，計(jì)算實(shí)際輸出，獲取實(shí)際輸出與期望輸出間的誤差將誤差從輸出層經(jīng)每個(gè)隱藏層到輸入層“后向傳播”，根據(jù)誤差修改權(quán)值和單元的偏置，使實(shí)際輸出與期望輸出之間的誤差最小第一百二十三張，PPT共二百頁(yè)，創(chuàng)作于2022年6月124前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)算法網(wǎng)絡(luò)學(xué)習(xí)樣本實(shí)際輸出與期望輸出的誤差Error： c：輸出層的單元數(shù)目 Tk：輸出層單元k的期望輸出 Ok：?jiǎn)卧猭的實(shí)際輸出 輸出層單元k與前一層單元j之間的權(quán)值wjk的修改量wjk

57、、單元k的偏置修改量為使Error最小，采用使Error沿梯度方向下降的方式單元j的輸出Error對(duì)單元k的輸入netk的負(fù)偏導(dǎo)數(shù)學(xué)習(xí)率，l 0, 1，避免陷入局部最優(yōu)解單元k的輸出第一百二十四張，PPT共二百頁(yè)，創(chuàng)作于2022年6月125前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)算法網(wǎng)絡(luò)學(xué)習(xí)隱藏層單元j與前一層單元i之間的權(quán)值wij的修改量wij、單元j的偏置j的修改量j ：?jiǎn)卧猧的輸出單元j的輸出與單元j相連的后一層單元k的誤差 權(quán)值、偏置的修改 ：權(quán)值、偏置的更新有兩種策略：1）實(shí)例更新：處理一個(gè)訓(xùn)練樣本更新一次，常采用2）周期更新：處理所有訓(xùn)練樣本后再一次更新處理所有訓(xùn)練樣本一次，稱為一個(gè)周期第一百二十五張，P

58、PT共二百頁(yè)，創(chuàng)作于2022年6月126前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)算法網(wǎng)絡(luò)學(xué)習(xí)結(jié)束條件：1）誤差Error小于設(shè)定閾值，此時(shí)認(rèn)為網(wǎng)絡(luò)收斂，結(jié)束迭代2）前一周期所有的權(quán)值變化都很小，小于某個(gè)設(shè)定閾值3）前一周期預(yù)測(cè)的準(zhǔn)確率很大，大于某個(gè)設(shè)定閾值3）周期數(shù)大于某個(gè)設(shè)定閾值在實(shí)際應(yīng)用中，訓(xùn)練樣本很多，學(xué)習(xí)需要很多次迭代才能完成迭代次數(shù)與網(wǎng)絡(luò)結(jié)構(gòu)、初始權(quán)值與偏置、學(xué)習(xí)率的值有很大關(guān)系這些參數(shù)都是憑經(jīng)驗(yàn)選取 算法特點(diǎn)第一百二十六張，PPT共二百頁(yè)，創(chuàng)作于2022年6月127前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)算法網(wǎng)絡(luò)學(xué)習(xí)設(shè)訓(xùn)練樣本s的描述屬性值與類(lèi)別屬性值分別為1, 0, 1與1，前饋神經(jīng)網(wǎng)絡(luò)NT如圖所示，NT中每條有向加權(quán)邊的權(quán)值

59、、每個(gè)隱藏層與輸出層單元的偏置如表所示，學(xué)習(xí)率為0.9。寫(xiě)出輸入s訓(xùn)練NT的過(guò)程 x1x2x3w14w15w24w25w34w35w46w564561010.20.30.40.10.50.20.30.20.40.20.1第一百二十七張，PPT共二百頁(yè)，創(chuàng)作于2022年6月128前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)算法網(wǎng)絡(luò)學(xué)習(xí)x1x2x3w14w15w24w25w34w35w46w564561010.20.30.40.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.

60、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第一百二十八張，PPT共二百頁(yè)，創(chuàng)作于2022年6月129前饋神經(jīng)網(wǎng)絡(luò)分類(lèi)算法網(wǎng)絡(luò)學(xué)習(xí)x1x2x3w14w15w24w25w34w35w46w564561010.20.30.40.10.50.20.30.20.40.