(1) 樸素貝葉斯算法
設每個數(shù)據(jù)樣本用一個n維特征向量來描述n個屬性的值,即:X={x1,x2,…,xn},假定有m個類,分別用C1, C2,…,Cm表示。給定一個未知的數(shù)據(jù)樣本X(即沒有類標號),若樸素貝葉斯分類法將未知的樣本X分配給類Ci,則一定是
P(Ci|X)>P(Cj|X) 1≤j≤m,j≠i
根據(jù)貝葉斯定理
由于P(X)對于所有類為常數(shù),最大化后驗概率P(Ci|X)可轉(zhuǎn)化為最大化先驗概率P(X|Ci)P(Ci)。如果訓練數(shù)據(jù)集有許多屬性和元組,計算P(X|Ci)的開銷可能非常大,為此,通常假設各屬性的取值互相獨立,這樣
先驗概率P(x1|Ci),P(x2|Ci),…,P(xn|Ci)可以從訓練數(shù)據(jù)集求得。
根據(jù)此方法,對一個未知類別的樣本X,可以先分別計算出X屬于每一個類別Ci的概率P(X|Ci)P(Ci),然后選擇其中概率最大的類別作為其類別。
樸素貝葉斯算法成立的前提是各屬性之間互相獨立。當數(shù)據(jù)集滿足這種獨立性假設時,分類的準確度較高,否則可能較低。另外,該算法沒有分類規(guī)則輸出。
(2) TAN算法
TAN算法通過發(fā)現(xiàn)屬性對之間的依賴關系來降低NB中任意屬性之間獨立的假設。它是在NB網(wǎng)絡結(jié)構(gòu)的基礎上增加屬性對之間的關聯(lián)(邊)來實現(xiàn)的。
實現(xiàn)方法是:用結(jié)點表示屬性,用有向邊表示屬性之間的依賴關系,把類別屬性作為根結(jié)點,其余所有屬性都作為它的子節(jié)點。通常,用虛線代表NB所需的邊,用實線代表新增的邊。屬性Ai與Aj之間的邊意味著屬性Ai對類別變量C的影響還取決于屬性Aj的取值。
這些增加的邊需滿足下列條件:類別變量沒有雙親結(jié)點,每個屬性有一個類別變量雙親結(jié)點和最多另外一個屬性作為其雙親結(jié)點。
找到這組關聯(lián)邊之后,就可以計算一組隨機變量的聯(lián)合概率分布如下:
其中ΠAi代表的是Ai的雙親結(jié)點。由于在TAN算法中考慮了n個屬性中(n-1)個兩兩屬性之間的關聯(lián)性,該算法對屬性之間獨立性的假設有了一定程度的降低,但是屬性之間可能存
在更多其它的關聯(lián)性仍沒有考慮,因此其適用范圍仍然受到限制。
2.3 基于關聯(lián)規(guī)則的分類算法
關聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的一個重要的、高度活躍的領域。近年來,數(shù)據(jù)挖掘技術(shù)己將關聯(lián)規(guī)則挖掘用于分類問題,取得了很好的效果。
ARCS(Association Rule Clustering System)基于聚類挖掘關聯(lián)規(guī)則,然后使用規(guī)則進行分類。將關聯(lián)規(guī)則畫在2-D柵格上,算法掃描柵格,搜索規(guī)則的矩形聚類。實踐發(fā)現(xiàn),當數(shù)據(jù)中存在孤立點時,ARCS比C4.5稍微精確一點。ARCS的準確性與離散化程度有關。從可伸縮性來說,不論數(shù)據(jù)庫多大,ARCS需要的存儲容量為常數(shù)。
CBA(classification based on association)是基于關聯(lián)規(guī)則發(fā)現(xiàn)方法的分類算法。該算法分兩個步驟構(gòu)造分類器。第一步:發(fā)現(xiàn)所有形如xi1∧x => Ci 的關聯(lián)規(guī)則,即右部為類別屬性值的類別關聯(lián)規(guī)則(classification association rules,CAR)。第二步:從已發(fā)現(xiàn)的CAR中選擇高優(yōu)先度的規(guī)則來覆蓋訓練集,也就是說,如果有多條關聯(lián)規(guī)則的左部相同,而右部為不同的類,則選擇具有最高置信度的規(guī)則作為可能規(guī)則。文獻[4]對該過程進行了較深入的研究,使得算法在此步驟不需要對訓練數(shù)據(jù)集進行過多的掃描。
CBA算法的優(yōu)點是其分類準確度較高,在許多數(shù)據(jù)集上比C4.5更精確。此外,上述兩步都具有線性可伸縮性。
CBA(Classification Based on Association)是關聯(lián)分類。此算法把分類規(guī)則挖掘和關聯(lián)規(guī)則挖掘整合到一起。與CART和C4.5只產(chǎn)生部分規(guī)則不同的是,CBA產(chǎn)生所有的類關聯(lián)規(guī)則CARs(Class Association Rules),然后選擇最好的規(guī)則去覆蓋訓練集。另外,在此算法的框架中,數(shù)據(jù)庫可以駐留在磁盤中
CAEP使用項集支持度挖掘HV露模式(Emerging Pattern), 而EP用于構(gòu)造分類。CAEP找出滿足給定支持度和增長率閾值的EP。己經(jīng)發(fā)現(xiàn),在許多數(shù)據(jù)集上,CAEP比C4.5和基于關聯(lián)的分類更精確。一種替代的、基于跳躍的HV露模式JEP(Jnmping Emerging Pattern)是一種特殊類型的EP,項集的支持度由在一個數(shù)據(jù)集中的0陡峭地增長到另一個數(shù)據(jù)集中的非0。在一此大的多維數(shù)據(jù)庫中,JEP性能優(yōu)于CAEP, 但在一些小型數(shù)據(jù)庫中,CAEP比JEP優(yōu),這二種分類法被認為是互補的。
ADT(Association Decision Trec)分二步實現(xiàn)以精確度驅(qū)動為基礎的過度適合規(guī)則的剪枝。第一步,運用置信度規(guī)則建立分類器。主要是采用某種置信度的單調(diào)性建立基于置信度的剪枝策略。第二步,為實現(xiàn)精確性,用關聯(lián)規(guī)則建立一種平衡于DT(Dccision Tree)歸納的精確度驅(qū)動剪枝。這樣的結(jié)果就是ADT(Association Based Decision Trec)。它聯(lián)合了大量的關聯(lián)規(guī)則和DT歸納精確性驅(qū)動剪枝技術(shù)。
基于多維關聯(lián)規(guī)則的分類算法CMAR(Classification Based on Multiple Class-Association Rules)是利用FP-Growth算法挖掘關聯(lián)規(guī)則,建立類關聯(lián)分布樹FP-樹。采用CR-樹(Classification Rulc Trcc)結(jié)構(gòu)有效地存儲關聯(lián)規(guī)則?;谥眯哦?、相關性和數(shù)據(jù)庫覆蓋來剪枝。分類的具體執(zhí)行采用加權(quán)廠來分析。與CBA和C 4.5相比,CMAR性能優(yōu)異且伸縮性較好。但CMAR優(yōu)先生成的是長規(guī)則,對數(shù)據(jù)庫的覆蓋效果較差;利用加權(quán)x2統(tǒng)計量進行分類,會造成x2統(tǒng)計量的失真,致使分類值的準確程度降低。CPAR(Classification Based on Predictive Association Rules)整合了關聯(lián)規(guī)則分類和傳統(tǒng)的基于規(guī)則分類的優(yōu)點。為避免過度適合,在規(guī)則生成時采用貪心算法,這比產(chǎn)生所有候選項集的效率高;采用一種動態(tài)方法避免在規(guī)則生成時的重復計算;采用頂期精確性評價規(guī)則,并在預測時應用最優(yōu)的規(guī)則,避免產(chǎn)生冗余的規(guī)則。另外,MSR(Minimnm Set Rule)針對基于關聯(lián)規(guī)則分類算法中產(chǎn)生的關聯(lián)規(guī)則集可能太大的問題,在分類中運用最小關聯(lián)規(guī)則集。在此算法中,CARS并不是通過置信度首先排序,因為高置信度規(guī)則對噪聲是很敏感的。采用早期剪枝力方法可減少關聯(lián)規(guī)則的數(shù)量,并保證在最小集中沒有不相關的規(guī)則。實驗證實,MSR比C45和CBA的錯誤率要低得多。
雖然數(shù)據(jù)挖掘的創(chuàng)始人主要是數(shù)據(jù)庫領域的研究人員,然而提出的大多數(shù)算法則沒有利用數(shù)據(jù)庫的相關技術(shù)。在分類算法中,致力于解決此問題的算法有MIND (mining in database)和GAC-RDB(grouping and counting-relational database)。
(1) MIND算法
MIND 算法是采用數(shù)據(jù)庫中用戶定義的函數(shù)(user-defined function,UDF)實現(xiàn)發(fā)現(xiàn)分類規(guī)則的算法。MIND采用典型的決策樹構(gòu)造方法構(gòu)建分類器。具體步驟與SLIQ類似。其主要區(qū)別在于它采用數(shù)據(jù)庫提供的UDF方法和SQL語句實現(xiàn)樹的構(gòu)造。簡而言之,就是在樹的每一層,為每一個屬性建立一個維表,存放各屬性的每個取值屬于各個類別的個數(shù)以及所屬的結(jié)點編號。根據(jù)這些信息可以為當前結(jié)點計算每種分裂標準的值,選出最優(yōu)的分裂標準,然后據(jù)此對結(jié)點進行分裂,修改維表中結(jié)點編號列的值。在上述過程中,對維表的創(chuàng)建和修改需要進行多次,若用SQL實現(xiàn),耗時很多,因此用UDF實現(xiàn)。而分類標準的尋找過程則通過創(chuàng)建若干表和視圖,利用連接查詢實現(xiàn)。
該算法的優(yōu)點是通過采用UDF實現(xiàn)決策樹的構(gòu)造過程使得分類算法易于與數(shù)據(jù)庫系統(tǒng)集成。其缺點是算法用UDF完成主要的計算任務,而UDF一般是由用戶利用高級語言實現(xiàn)的,無法使用數(shù)據(jù)庫系統(tǒng)提供的查詢處理機制,無法利用查詢優(yōu)化方法,且UDF的編寫和維護相當復雜。此外,MIND中用SQL語句實現(xiàn)的那部分功能本身就是比較簡單的操作,而采用SQL實現(xiàn)的方法卻顯得相當復雜。
(2) GAC-RDB算法
GAC -RDB算法是一種利用SQL語句實現(xiàn)的分類算法。該算法采用一種基于分組計數(shù)的方法統(tǒng)計訓練數(shù)據(jù)集中各個屬性取值組合的類別分布信息,通過最小置信度和最小支持度兩個閾值找出有意義的分類規(guī)則。在該算法中,首先利用SQL語句計算每個屬性進行類別判定的信息量,從而選擇一個最優(yōu)的分裂屬性,并且按照信息量的大小對屬性進行排序,隨后重復地進行屬性的選擇、候選分類表的生成、剪裁以及分類誤差的計算,直到滿足結(jié)束條件為止,比如,直到小于誤差閾值和誤差沒有改變?yōu)橹埂?/p>
該算法的優(yōu)點是具有與現(xiàn)有的其他分類器相同的分類準確度,執(zhí)行速度有較大提高,而且具有良好的伸縮性,應用程序易于與數(shù)據(jù)庫系統(tǒng)集成。其缺點是參數(shù)的取值需用戶完成等。
評論
查看更多