(1) 樸素貝葉斯算法

設(shè)每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量來描述n個(gè)屬性的值，即：X={x1，x2，…，xn}，假定有m個(gè)類，分別用C1, C2,…，Cm表示。給定一個(gè)未知的數(shù)據(jù)樣本X（即沒有類標(biāo)號(hào)），若樸素貝葉斯分類法將未知的樣本X分配給類Ci，則一定是

P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i

根據(jù)貝葉斯定理

由于P(X)對(duì)于所有類為常數(shù)，最大化后驗(yàn)概率P(Ci|X)可轉(zhuǎn)化為最大化先驗(yàn)概率P(X|Ci)P(Ci)。如果訓(xùn)練數(shù)據(jù)集有許多屬性和元組，計(jì)算P(X|Ci)的開銷可能非常大，為此，通常假設(shè)各屬性的取值互相獨(dú)立，這樣

先驗(yàn)概率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以從訓(xùn)練數(shù)據(jù)集求得。

根據(jù)此方法，對(duì)一個(gè)未知類別的樣本X，可以先分別計(jì)算出X屬于每一個(gè)類別Ci的概率P(X|Ci)P(Ci)，然后選擇其中概率最大的類別作為其類別。

樸素貝葉斯算法成立的前提是各屬性之間互相獨(dú)立。當(dāng)數(shù)據(jù)集滿足這種獨(dú)立性假設(shè)時(shí),分類的準(zhǔn)確度較高，否則可能較低。另外，該算法沒有分類規(guī)則輸出。

(2) TAN算法

TAN算法通過發(fā)現(xiàn)屬性對(duì)之間的依賴關(guān)系來降低NB中任意屬性之間獨(dú)立的假設(shè)。它是在NB網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上增加屬性對(duì)之間的關(guān)聯(lián)(邊)來實(shí)現(xiàn)的。

實(shí)現(xiàn)方法是：用結(jié)點(diǎn)表示屬性，用有向邊表示屬性之間的依賴關(guān)系，把類別屬性作為根結(jié)點(diǎn)，其余所有屬性都作為它的子節(jié)點(diǎn)。通常，用虛線代表NB所需的邊，用實(shí)線代表新增的邊。屬性Ai與Aj之間的邊意味著屬性Ai對(duì)類別變量C的影響還取決于屬性Aj的取值。

這些增加的邊需滿足下列條件：類別變量沒有雙親結(jié)點(diǎn)，每個(gè)屬性有一個(gè)類別變量雙親結(jié)點(diǎn)和最多另外一個(gè)屬性作為其雙親結(jié)點(diǎn)。

找到這組關(guān)聯(lián)邊之后，就可以計(jì)算一組隨機(jī)變量的聯(lián)合概率分布如下：

其中ΠAi代表的是Ai的雙親結(jié)點(diǎn)。由于在TAN算法中考慮了n個(gè)屬性中(n-1)個(gè)兩兩屬性之間的關(guān)聯(lián)性，該算法對(duì)屬性之間獨(dú)立性的假設(shè)有了一定程度的降低，但是屬性之間可能存

在更多其它的關(guān)聯(lián)性仍沒有考慮，因此其適用范圍仍然受到限制。

2.3 基于關(guān)聯(lián)規(guī)則的分類算法

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的一個(gè)重要的、高度活躍的領(lǐng)域。近年來，數(shù)據(jù)挖掘技術(shù)己將關(guān)聯(lián)規(guī)則挖掘用于分類問題，取得了很好的效果。

ARCS(Association Rule Clustering System)基于聚類挖掘關(guān)聯(lián)規(guī)則，然后使用規(guī)則進(jìn)行分類。將關(guān)聯(lián)規(guī)則畫在2-D柵格上，算法掃描柵格，搜索規(guī)則的矩形聚類。實(shí)踐發(fā)現(xiàn)，當(dāng)數(shù)據(jù)中存在孤立點(diǎn)時(shí)，ARCS比C4.5稍微精確一點(diǎn)。ARCS的準(zhǔn)確性與離散化程度有關(guān)。從可伸縮性來說，不論數(shù)據(jù)庫多大，ARCS需要的存儲(chǔ)容量為常數(shù)。

CBA(classification based on association)是基于關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法的分類算法。該算法分兩個(gè)步驟構(gòu)造分類器。第一步：發(fā)現(xiàn)所有形如xi1∧x => Ci 的關(guān)聯(lián)規(guī)則，即右部為類別屬性值的類別關(guān)聯(lián)規(guī)則(classification association rules，CAR)。第二步：從已發(fā)現(xiàn)的CAR中選擇高優(yōu)先度的規(guī)則來覆蓋訓(xùn)練集，也就是說，如果有多條關(guān)聯(lián)規(guī)則的左部相同，而右部為不同的類，則選擇具有最高置信度的規(guī)則作為可能規(guī)則。文獻(xiàn)[4]對(duì)該過程進(jìn)行了較深入的研究，使得算法在此步驟不需要對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行過多的掃描。

CBA算法的優(yōu)點(diǎn)是其分類準(zhǔn)確度較高，在許多數(shù)據(jù)集上比C4.5更精確。此外，上述兩步都具有線性可伸縮性。

CBA(Classification Based on Association)是關(guān)聯(lián)分類。此算法把分類規(guī)則挖掘和關(guān)聯(lián)規(guī)則挖掘整合到一起。與CART和C4.5只產(chǎn)生部分規(guī)則不同的是,CBA產(chǎn)生所有的類關(guān)聯(lián)規(guī)則CARs(Class Association Rules)，然后選擇最好的規(guī)則去覆蓋訓(xùn)練集。另外，在此算法的框架中，數(shù)據(jù)庫可以駐留在磁盤中

CAEP使用項(xiàng)集支持度挖掘HV露模式(Emerging Pattern), 而EP用于構(gòu)造分類。CAEP找出滿足給定支持度和增長(zhǎng)率閾值的EP。己經(jīng)發(fā)現(xiàn)，在許多數(shù)據(jù)集上，CAEP比C4.5和基于關(guān)聯(lián)的分類更精確。一種替代的、基于跳躍的HV露模式JEP(Jnmping Emerging Pattern)是一種特殊類型的EP，項(xiàng)集的支持度由在一個(gè)數(shù)據(jù)集中的0陡峭地增長(zhǎng)到另一個(gè)數(shù)據(jù)集中的非0。在一此大的多維數(shù)據(jù)庫中，JEP性能優(yōu)于CAEP, 但在一些小型數(shù)據(jù)庫中，CAEP比JEP優(yōu)，這二種分類法被認(rèn)為是互補(bǔ)的。

ADT(Association Decision Trec)分二步實(shí)現(xiàn)以精確度驅(qū)動(dòng)為基礎(chǔ)的過度適合規(guī)則的剪枝。第一步，運(yùn)用置信度規(guī)則建立分類器。主要是采用某種置信度的單調(diào)性建立基于置信度的剪枝策略。第二步，為實(shí)現(xiàn)精確性，用關(guān)聯(lián)規(guī)則建立一種平衡于DT(Dccision Tree)歸納的精確度驅(qū)動(dòng)剪枝。這樣的結(jié)果就是ADT(Association Based Decision Trec)。它聯(lián)合了大量的關(guān)聯(lián)規(guī)則和DT歸納精確性驅(qū)動(dòng)剪枝技術(shù)。

基于多維關(guān)聯(lián)規(guī)則的分類算法CMAR(Classification Based on Multiple Class-Association Rules)是利用FP-Growth算法挖掘關(guān)聯(lián)規(guī)則，建立類關(guān)聯(lián)分布樹FP－樹。采用CR－樹(Classification Rulc Trcc)結(jié)構(gòu)有效地存儲(chǔ)關(guān)聯(lián)規(guī)則。基于置信度、相關(guān)性和數(shù)據(jù)庫覆蓋來剪枝。分類的具體執(zhí)行采用加權(quán)廠來分析。與CBA和C 4.5相比，CMAR性能優(yōu)異且伸縮性較好。但CMAR優(yōu)先生成的是長(zhǎng)規(guī)則，對(duì)數(shù)據(jù)庫的覆蓋效果較差;利用加權(quán)x2統(tǒng)計(jì)量進(jìn)行分類，會(huì)造成x2統(tǒng)計(jì)量的失真，致使分類值的準(zhǔn)確程度降低。CPAR(Classification Based on Predictive Association Rules)整合了關(guān)聯(lián)規(guī)則分類和傳統(tǒng)的基于規(guī)則分類的優(yōu)點(diǎn)。為避免過度適合，在規(guī)則生成時(shí)采用貪心算法，這比產(chǎn)生所有候選項(xiàng)集的效率高;采用一種動(dòng)態(tài)方法避免在規(guī)則生成時(shí)的重復(fù)計(jì)算;采用頂期精確性評(píng)價(jià)規(guī)則，并在預(yù)測(cè)時(shí)應(yīng)用最優(yōu)的規(guī)則，避免產(chǎn)生冗余的規(guī)則。另外，MSR(Minimnm Set Rule)針對(duì)基于關(guān)聯(lián)規(guī)則分類算法中產(chǎn)生的關(guān)聯(lián)規(guī)則集可能太大的問題，在分類中運(yùn)用最小關(guān)聯(lián)規(guī)則集。在此算法中，CARS并不是通過置信度首先排序，因?yàn)楦咧眯哦纫?guī)則對(duì)噪聲是很敏感的。采用早期剪枝力方法可減少關(guān)聯(lián)規(guī)則的數(shù)量，并保證在最小集中沒有不相關(guān)的規(guī)則。實(shí)驗(yàn)證實(shí)，MSR比C45和CBA的錯(cuò)誤率要低得多。

雖然數(shù)據(jù)挖掘的創(chuàng)始人主要是數(shù)據(jù)庫領(lǐng)域的研究人員，然而提出的大多數(shù)算法則沒有利用數(shù)據(jù)庫的相關(guān)技術(shù)。在分類算法中，致力于解決此問題的算法有MIND （mining in database）和GAC-RDB（grouping and counting-relational database）。

(1) MIND算法
MIND 算法是采用數(shù)據(jù)庫中用戶定義的函數(shù)(user-defined function，UDF)實(shí)現(xiàn)發(fā)現(xiàn)分類規(guī)則的算法。MIND采用典型的決策樹構(gòu)造方法構(gòu)建分類器。具體步驟與SLIQ類似。其主要區(qū)別在于它采用數(shù)據(jù)庫提供的UDF方法和SQL語句實(shí)現(xiàn)樹的構(gòu)造。簡(jiǎn)而言之，就是在樹的每一層，為每一個(gè)屬性建立一個(gè)維表，存放各屬性的每個(gè)取值屬于各個(gè)類別的個(gè)數(shù)以及所屬的結(jié)點(diǎn)編號(hào)。根據(jù)這些信息可以為當(dāng)前結(jié)點(diǎn)計(jì)算每種分裂標(biāo)準(zhǔn)的值，選出最優(yōu)的分裂標(biāo)準(zhǔn)，然后據(jù)此對(duì)結(jié)點(diǎn)進(jìn)行分裂，修改維表中結(jié)點(diǎn)編號(hào)列的值。在上述過程中，對(duì)維表的創(chuàng)建和修改需要進(jìn)行多次，若用SQL實(shí)現(xiàn)，耗時(shí)很多，因此用UDF實(shí)現(xiàn)。而分類標(biāo)準(zhǔn)的尋找過程則通過創(chuàng)建若干表和視圖，利用連接查詢實(shí)現(xiàn)。

該算法的優(yōu)點(diǎn)是通過采用UDF實(shí)現(xiàn)決策樹的構(gòu)造過程使得分類算法易于與數(shù)據(jù)庫系統(tǒng)集成。其缺點(diǎn)是算法用UDF完成主要的計(jì)算任務(wù)，而UDF一般是由用戶利用高級(jí)語言實(shí)現(xiàn)的，無法使用數(shù)據(jù)庫系統(tǒng)提供的查詢處理機(jī)制，無法利用查詢優(yōu)化方法，且UDF的編寫和維護(hù)相當(dāng)復(fù)雜。此外，MIND中用SQL語句實(shí)現(xiàn)的那部分功能本身就是比較簡(jiǎn)單的操作，而采用SQL實(shí)現(xiàn)的方法卻顯得相當(dāng)復(fù)雜。

(2) GAC-RDB算法
GAC -RDB算法是一種利用SQL語句實(shí)現(xiàn)的分類算法。該算法采用一種基于分組計(jì)數(shù)的方法統(tǒng)計(jì)訓(xùn)練數(shù)據(jù)集中各個(gè)屬性取值組合的類別分布信息，通過最小置信度和最小支持度兩個(gè)閾值找出有意義的分類規(guī)則。在該算法中，首先利用SQL語句計(jì)算每個(gè)屬性進(jìn)行類別判定的信息量，從而選擇一個(gè)最優(yōu)的分裂屬性，并且按照信息量的大小對(duì)屬性進(jìn)行排序，隨后重復(fù)地進(jìn)行屬性的選擇、候選分類表的生成、剪裁以及分類誤差的計(jì)算，直到滿足結(jié)束條件為止，比如，直到小于誤差閾值和誤差沒有改變?yōu)橹埂?/p>

該算法的優(yōu)點(diǎn)是具有與現(xiàn)有的其他分類器相同的分類準(zhǔn)確度，執(zhí)行速度有較大提高，而且具有良好的伸縮性，應(yīng)用程序易于與數(shù)據(jù)庫系統(tǒng)集成。其缺點(diǎn)是參數(shù)的取值需用戶完成等。