貝葉斯與頻繁模式

1DataMining:

ConceptsandTechniques

—Chapter9—

Classification:AdvancedMethods

姓名：周芳學(xué)號(hào)：20152161409.1貝葉斯信念網(wǎng)絡(luò)樸素貝葉斯分類(lèi)假定類(lèi)條件獨(dú)立（實(shí)際上在現(xiàn)實(shí)應(yīng)用中幾乎不可能做到完全獨(dú)立），在實(shí)踐中，變量之間的依賴(lài)可能存在。各個(gè)特征屬性間往往并不條件獨(dú)立，而是具有較強(qiáng)的相關(guān)性，這樣就限制了樸素貝葉斯分類(lèi)的能力。貝葉斯信念網(wǎng)絡(luò)說(shuō)明聯(lián)合條件概率分布。它允許在變量的子集間定義類(lèi)條件獨(dú)立性。它提供一種因果關(guān)系的圖形，可以在其上進(jìn)行學(xué)習(xí)訓(xùn)練后的貝葉斯網(wǎng)絡(luò)可以用于分類(lèi)February6,2023DataMining:ConceptsandTechniques2兩個(gè)成分定義第一部分是有向無(wú)環(huán)圖，其每個(gè)節(jié)點(diǎn)代表一個(gè)隨機(jī)變量，而每條弧代表一個(gè)概率依賴(lài)。（變量可以是離散的或連續(xù)值的）第二部分是條件概率表。February6,2023DataMining:ConceptsandTechniques39.1貝葉斯網(wǎng)絡(luò)February6,2023DataMining:ConceptsandTechniques4在貝葉斯信念網(wǎng)絡(luò)中對(duì)應(yīng)于屬性或變量Z1....Zn的任意元組(Z1....Zn)的聯(lián)合概率由下式計(jì)算：如上圖，對(duì)于FamilyHistory，Smoker，LungCancer這三個(gè)屬性，用樸素貝葉斯計(jì)算，得到的聯(lián)合概率是貝葉斯網(wǎng)絡(luò)求得聯(lián)合概率為：由條件概率表（CPT）求聯(lián)合分布變量Z的CPT說(shuō)明條件分布P(Z|Parents(Z))，其中Parents(Z)是Z的雙親。對(duì)于其雙親值的每個(gè)可能組合，表中給出了LangCancer的每個(gè)值的條件概率。例如，由左上角和右下角，P(LangCancer=”yes”

|

FamilyHistory=”yes”,

Smoker=”yes”)=0.8

P(LangCancer=”no”

|

FamilyHistory=”no”,

Smoker=”no”)=0.9

對(duì)應(yīng)于屬性或變量Z1,Z2,…Zn的任意元組（z1,z2,…zn）的聯(lián)合概率由下式計(jì)算February6,2023DataMining:ConceptsandTechniques5February6,2023DataMining:ConceptsandTechniques6例子：i、真實(shí)賬號(hào)比非真實(shí)賬號(hào)平均具有更大的日志密度、更大的好友密度以及更多的使用真實(shí)頭像。ii、日志密度與好友密度、日志密度與是否使用真實(shí)頭像在賬號(hào)真實(shí)性給定的條件下是獨(dú)立的。iii、使用真實(shí)頭像的用戶(hù)比使用非真實(shí)頭像的用戶(hù)平均有更大的好友密度。February6,2023DataMining:ConceptsandTechniques7通過(guò)對(duì)訓(xùn)練數(shù)據(jù)集的統(tǒng)計(jì)，得到下表（R表示賬號(hào)真實(shí)性，H表示頭像真實(shí)性）：例如，現(xiàn)隨機(jī)抽取一個(gè)賬戶(hù)，已知其頭像為假，求其賬號(hào)也為假的概率：February6,2023DataMining:ConceptsandTechniques8我們的模型中存在四個(gè)隨機(jī)變量：賬號(hào)真實(shí)性R，頭像真實(shí)性H，日志密度L，好友密度F訓(xùn)練貝葉斯信念網(wǎng)絡(luò)---構(gòu)建：1、主觀(guān)網(wǎng)絡(luò)拓?fù)淇梢杂蓪?zhuān)家構(gòu)造或數(shù)據(jù)導(dǎo)出。專(zhuān)家通常對(duì)所分析領(lǐng)域成了的直接條件依賴(lài)有很好的把握，但是必須說(shuō)明參與直接依賴(lài)接單的條件概率。馬爾科夫假設(shè)：在直接原因已知前提下，一個(gè)變量獨(dú)立于與其沒(méi)有影響的變量。E.g.,S?—F—?A?—T,在已知F—?A的前提下，pathS—?A不通隱馬爾科夫模型：常用于動(dòng)態(tài)系統(tǒng)模型的狀態(tài)是不明顯的,但是他們的輸出明顯。February6,2023DataMining:ConceptsandTechniques9訓(xùn)練貝葉斯信念網(wǎng)絡(luò)設(shè)S是s個(gè)訓(xùn)練樣本X1,X2,…Xs的集合，Wijk是具有是雙親Ui=uik的變量Y=yij的CPT項(xiàng)。Wijk可以看作權(quán)，類(lèi)似于神經(jīng)網(wǎng)絡(luò)中隱藏單元的權(quán)。權(quán)的集合總稱(chēng)為w。這些權(quán)被初始化為隨機(jī)概率值。梯度下降策略采用貪心爬山法。在每次迭代中，修改這些權(quán)，并最終收斂到一個(gè)局部最優(yōu)解。

基于w的每個(gè)可能設(shè)置都等可能地假定，該方法搜索能最好地對(duì)數(shù)據(jù)建模的Wijk值。目標(biāo)是最大化

。這通過(guò)按梯度來(lái)做，使得問(wèn)題更簡(jiǎn)單。給定網(wǎng)絡(luò)結(jié)構(gòu)和Wijk的初值，該算法按以下步驟處理：February6,2023DataMining:ConceptsandTechniques10梯度下降1.計(jì)算梯度2.沿梯度方向前進(jìn)一小步，下式更新權(quán)重3.更新規(guī)格化權(quán)值保證權(quán)重在0—1之間，進(jìn)行歸格化操作。February6,2023DataMining:ConceptsandTechniques11梯度下降February6,2023DataMining:ConceptsandTechniques12梯度訓(xùn)練是用于解決信念網(wǎng)絡(luò)中隱藏?cái)?shù)據(jù)問(wèn)題的，例如，已知上圖（a），不知道上圖（b）。9.4使用頻繁模式分類(lèi)February6,2023DataMining:ConceptsandTechniques13

頻繁模式顯示了頻繁地出現(xiàn)在給定數(shù)據(jù)集上的屬性——值對(duì)之間的有趣聯(lián)系。例如，我們可能發(fā)現(xiàn)屬性——值對(duì)age=youth和credit=OK出現(xiàn)在20%的購(gòu)買(mǎi)計(jì)算機(jī)的AllRlectronics顧客元組中。我們可以把每個(gè)屬性——值對(duì)看作一個(gè)項(xiàng)，因此搜索這種頻繁模式稱(chēng)作頻繁模式挖掘或頻繁項(xiàng)集挖掘。頻繁模式February6,2023DataMining:ConceptsandTechniques14下面是從數(shù)據(jù)集D中挖掘的一個(gè)關(guān)聯(lián)規(guī)則，顯示了它的置信度和支持度：其中，“^”表示邏輯“AND“。意味著，D中20%的顧客是青年、信譽(yù)為Ok，并且屬于類(lèi)buys_computer=yes；D中身為青年人并且信譽(yù)度為OK的顧客中，93%屬于類(lèi)buys_computer=yes。設(shè)D是元組的數(shù)據(jù)集合。D中每個(gè)元組用n個(gè)屬性A1，A2，…，An和一個(gè)類(lèi)標(biāo)號(hào)屬性Aclass描述。所有的連續(xù)屬性都被離散化并按分類(lèi)（或標(biāo)稱(chēng)）屬性處理。項(xiàng)p是一個(gè)形如（Ai，v）的屬性——值對(duì)，其中Ai是屬性，取值v。數(shù)據(jù)元組X=（x1，x2，…,xn）滿(mǎn)足項(xiàng)p=（Ai，v），當(dāng)且僅當(dāng)xi=v，其中xi是X的第i個(gè)屬性（Ai）的值。在挖掘用于分類(lèi)的關(guān)聯(lián)規(guī)則時(shí)，我們只對(duì)形如p1^p2^…pl=>Aclass=C的關(guān)聯(lián)規(guī)則感興趣，其中規(guī)則的前件是項(xiàng)的合取，與一個(gè)類(lèi)標(biāo)號(hào)C相關(guān)聯(lián)。

置信度：對(duì)于一個(gè)給定的規(guī)則R，D中滿(mǎn)足該規(guī)則前件也具有類(lèi)標(biāo)號(hào)C的元組所占的百分比稱(chēng)作R的置信度。從分類(lèi)角度看，這類(lèi)似于規(guī)則的準(zhǔn)確率。

支持度：D中滿(mǎn)足規(guī)則前件并具有類(lèi)標(biāo)號(hào)C的元組所占的百分比稱(chēng)作規(guī)則R的支持度。關(guān)聯(lián)規(guī)則分類(lèi)的步驟February6,2023DataMining:ConceptsandTechniques15一般而言，關(guān)聯(lián)規(guī)則分類(lèi)包括以下步驟：（1）挖掘數(shù)據(jù)，得到頻繁項(xiàng)集，即找出數(shù)據(jù)中經(jīng)常出現(xiàn)的屬性——值對(duì)。（2）分析頻繁項(xiàng)集，產(chǎn)生每個(gè)類(lèi)的關(guān)聯(lián)規(guī)則，它們滿(mǎn)足置信度和支持度標(biāo)準(zhǔn)。（3）組織規(guī)則，形成基于規(guī)則的分類(lèi)器。關(guān)聯(lián)規(guī)則分類(lèi)方法的不同在于挖掘頻繁項(xiàng)集所用的方法、如何將被分析的規(guī)則導(dǎo)出并用于分類(lèi)。典型的關(guān)聯(lián)分類(lèi)方法February6,2023DataMining:ConceptsandTechniques16CBA（基于關(guān)聯(lián)分類(lèi)）主要可能的關(guān)聯(lián)規(guī)則的形式項(xiàng)（一組屬性-值對(duì)）類(lèi)標(biāo)簽在優(yōu)先級(jí)遞減的基礎(chǔ)上的信任和支持，然后組織規(guī)則，建立分類(lèi)CMAR（基于多關(guān)聯(lián)規(guī)則分類(lèi)）分類(lèi)：對(duì)多個(gè)規(guī)則統(tǒng)計(jì)分析CPAR（基于預(yù)測(cè)關(guān)聯(lián)規(guī)則分類(lèi)）產(chǎn)生預(yù)測(cè)規(guī)則（FOIL分析），但允許覆蓋規(guī)則具有減小權(quán)重高效率，高精度類(lèi)似于CMARCBA算法February6,2023DataMining:ConceptsandTechniques17最早最簡(jiǎn)單的關(guān)聯(lián)分類(lèi)算法時(shí)基于分類(lèi)的關(guān)聯(lián)（ClassificationBasedonAssociation，CBA）。CBA使用迭代方法挖掘頻繁項(xiàng)集，類(lèi)似于A(yíng)priori算法。找出滿(mǎn)足最小置信度和支持度閾值的規(guī)則的完全集后，然后分析，找出包含在分類(lèi)器中的規(guī)則。CBA使用一種啟發(fā)式方法構(gòu)造分類(lèi)器，其中規(guī)則按照它們的置信度和支持度遞減優(yōu)先級(jí)排序。（1）如果一組規(guī)則具有相同的前件，則選取具有最高置信度的規(guī)則代表該集合。（2）在對(duì)新元組分類(lèi)時(shí)，使用滿(mǎn)足該元組的第一個(gè)規(guī)則對(duì)它進(jìn)行分類(lèi)。（3）分類(lèi)器還包含一個(gè)默認(rèn)規(guī)則，具有最低優(yōu)先級(jí)，用來(lái)為不能被分類(lèi)器中其他規(guī)則滿(mǎn)足的新元組指定默認(rèn)類(lèi)。這樣，構(gòu)成分類(lèi)器的規(guī)則的集合形成一個(gè)決策表。一般而言，實(shí)驗(yàn)表明CBA在大量數(shù)據(jù)集上比C4.5更準(zhǔn)確。CMAR算法February6,2023DataMining:ConceptsandTechniques18

基于多關(guān)聯(lián)規(guī)則的分類(lèi)（ClassificationbasedonMultipleAssociationRules，CMAR）在頻繁項(xiàng)集挖掘和分類(lèi)器構(gòu)造方面都不同于CBA。CMAR采用FP—Growth算法的變形來(lái)發(fā)現(xiàn)滿(mǎn)足最小支持度和最小置信度閾值的規(guī)則的完全集。CMAR使用一種加強(qiáng)的FP-樹(shù)，記錄滿(mǎn)足每個(gè)頻繁項(xiàng)集的元組的類(lèi)標(biāo)號(hào)分布。這樣，它可以把規(guī)則產(chǎn)生與頻繁項(xiàng)集挖掘合并成一步。CMAR還使用另一種樹(shù)結(jié)構(gòu)來(lái)有效地存儲(chǔ)和提取規(guī)則，并根據(jù)置信度、相關(guān)度和數(shù)據(jù)庫(kù)覆蓋率對(duì)規(guī)則剪枝。當(dāng)規(guī)則插入該樹(shù)時(shí)就觸發(fā)規(guī)則剪枝策略。例如，給定兩個(gè)規(guī)則R1和R2，如果R1的前件比R2更一般，并且conf（R1）>=conf（R2），則剪去R2。其基本原理是：如果規(guī)則存在具有更高置信度的更泛化的版本，則可以剪去具有低置信度的更特殊化的規(guī)則。

CMAR算法February6,2023DataMining:ConceptsandTechniques19“如果多個(gè)規(guī)則可用，我們使用哪一個(gè)？”作為分類(lèi)法，假設(shè)多個(gè)規(guī)則滿(mǎn)足或匹配X，這些規(guī)則形成一個(gè)集合S。使用哪個(gè)規(guī)則確定X的類(lèi)標(biāo)號(hào)？CMAR在做出它的類(lèi)預(yù)測(cè)時(shí)考慮多個(gè)規(guī)則。它根據(jù)類(lèi)標(biāo)號(hào)將規(guī)則分組。在一個(gè)組中的所有規(guī)則都具有相同的類(lèi)標(biāo)號(hào)，而在不同組中的規(guī)則具有不同的類(lèi)標(biāo)號(hào)。CMAR使用加權(quán)的X2度量，根據(jù)組中規(guī)則的統(tǒng)計(jì)相關(guān)性找出“最強(qiáng)的”規(guī)則組。然后把X的類(lèi)標(biāo)號(hào)指派為最強(qiáng)的組的類(lèi)標(biāo)號(hào)。這樣，在預(yù)測(cè)新元組的類(lèi)標(biāo)號(hào)時(shí)，它考慮多個(gè)規(guī)則，而不只是一個(gè)具有最高置信度的規(guī)則。實(shí)驗(yàn)表明，CMAR比CBA的平均準(zhǔn)確率稍高。它的運(yùn)行時(shí)間、可伸縮性和內(nèi)存使用都更有效。CPAR算法February6,2023DataMining:ConceptsandTechniques20CPAR（ClassificationbasedonPredictiveAssociationRules，基于預(yù)測(cè)關(guān)聯(lián)規(guī)則的分類(lèi)）采用了不同方法產(chǎn)生規(guī)則，基于一種稱(chēng)作FOIL的分類(lèi)規(guī)則產(chǎn)生算法。FOIL構(gòu)造規(guī)則來(lái)區(qū)別正元組（如類(lèi)buys_computer=yes的元組）和負(fù)元組（如類(lèi)buys_computer=no的元組）。對(duì)于多類(lèi)問(wèn)題，將FOIL用于每一個(gè)類(lèi)。也就是說(shuō)，對(duì)于類(lèi)C，類(lèi)C的所有元組都看做正元組，而其余的都看做負(fù)元組。產(chǎn)生規(guī)則以區(qū)分C類(lèi)和其他類(lèi)的元組。每當(dāng)產(chǎn)生一個(gè)規(guī)則時(shí)，就刪除它滿(mǎn)足（或覆蓋）的正樣本，直到數(shù)據(jù)集合中所有的正元組都被覆蓋。這樣，產(chǎn)生的規(guī)則更少，CPAR放寬了這一步，允許被覆蓋的元組留下并被考慮，但是降低它們的權(quán)重。對(duì)每個(gè)類(lèi)重復(fù)該過(guò)程。結(jié)果規(guī)則被合并在一起，形成分類(lèi)器的規(guī)則集。在分類(lèi)時(shí)，CPAR采用多少有些不同于CMAR的多規(guī)則策略。如果多個(gè)規(guī)則滿(mǎn)足新元組X，則類(lèi)似于CMAR，這些規(guī)則將按類(lèi)分組。然而，CPAR根據(jù)期望準(zhǔn)確率，使用每組中的最好的k個(gè)規(guī)則預(yù)測(cè)X的類(lèi)標(biāo)號(hào)。通過(guò)考慮組中最好的k個(gè)規(guī)則而不是所有的規(guī)則，這避免了較低秩規(guī)則的影響。在大量數(shù)據(jù)集上，CPAR的準(zhǔn)確率與CMAR接近。然而，由于CPAR產(chǎn)生的規(guī)則比CMAR少得多，對(duì)于大型訓(xùn)練數(shù)據(jù)集，CMAR有效得多。頻繁模式分類(lèi)February6,2023DataMining:ConceptsandTechniques21精度問(wèn)題提高辨別力增加特征空間的表現(xiàn)力可伸縮性問(wèn)題它是計(jì)算上不可行生成所有的特征組合，并用信息增益閾值進(jìn)行篩選有效的方法（DDPMine：FPtree修剪）：H.Cheng,X.Yan,J.Han,andP.S.Yu“直接識(shí)別圖案為挖掘有效的分類(lèi)”，ICDE'08頻繁模式VS單個(gè)特征February6,2023DataMining:ConceptsandTechniques22一些頻繁模式的辨別力比的單個(gè)特征更高，如圖繪制了長(zhǎng)度等于1的信息增益(a)Austral(c)Sonar(b)Cleve圖1.信息增益vs.模式長(zhǎng)度實(shí)驗(yàn)結(jié)果February6,2023DataMining:ConceptsandTechniques23(a)Austral(c)Sonar(b)Breast圖2.信息增益vs.模式頻率如圖繪制了UCI數(shù)據(jù)集的模式頻度（支持度）與信息增益，及理論上界。低頻度的模式的區(qū)別能力受限于一個(gè)小上界，信息增益的上界隨著模式頻度單調(diào)增加特征選擇February6,2023DataMining:ConceptsandTechniques24給定一組頻繁模式，無(wú)判別和冗余型態(tài)都存在，可能會(huì)導(dǎo)致過(guò)度擬合我們要挑出判別模式，并刪除冗余的模式借用最大邊際關(guān)聯(lián)的概念（MMR