貝葉斯與頻繁模式

1DataMining:

ConceptsandTechniques

—Chapter9—

Classification:AdvancedMethods

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

|

FamilyHistory=”yes”,

Smoker=”yes”)=0.8

P(LangCancer=”no”

|

FamilyHistory=”no”,

Smoker=”no”)=0.9

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

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

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

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

置信度：對于一個給定的規(guī)則R，D中滿足該規(guī)則前件也具有類標號C的元組所占的百分比稱作R的置信度。從分類角度看，這類似于規(guī)則的準確率。

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

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

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