摘 要:分類是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和模式識別中一個重要的研究領(lǐng)域。通過對當(dāng)前數(shù)據(jù)挖掘中具有代表性的優(yōu)秀分類算法進(jìn)行分析和比較,總結(jié)出了各種算法的特性,為使用者選擇算法或研究者改進(jìn)算法提供了依據(jù)。
1 概述
分類是一種重要的數(shù)據(jù)挖掘技術(shù)。分類的目的是根據(jù)數(shù)據(jù)集的特點(diǎn)構(gòu)造一個分類函數(shù)或分類模型(也常常稱作分類器),該模型能把未知類別的樣本映射到給定類別中的某一個。分類和回歸都可以用于預(yù)測。和回歸方法不同的是,分類的輸出是離散的類別值,而回歸的輸出是連續(xù)或有序值。本文只討論分類。
構(gòu)造模型的過程一般分為訓(xùn)練和測試兩個階段。在構(gòu)造模型之前,要求將數(shù)據(jù)集隨機(jī)地分為訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集。在訓(xùn)練階段,使用訓(xùn)練數(shù)據(jù)集,通過分析由屬性描述的數(shù)據(jù)庫元組來構(gòu)造模型,假定每個元組屬于一個預(yù)定義的類,由一個稱作類標(biāo)號屬性的屬性來確定。訓(xùn)練數(shù)據(jù)集中的單個元組也稱作訓(xùn)練樣本,一個具體樣本的形式可為:(u1,u2,……un;c);其中ui表示屬性值,c表示類別。由于提供了每個訓(xùn)練樣本的類標(biāo)號,該階段也稱為有指導(dǎo)的學(xué)習(xí),通常,模型用分類規(guī)則、判定樹或數(shù)學(xué)公式的形式提供。在測試階段,使用測試數(shù)據(jù)集來評估模型的分類準(zhǔn)確率,如果認(rèn)為模型的準(zhǔn)確率可以接受,就可以用該模型對其它數(shù)據(jù)元組進(jìn)行分類。一般來說,測試階段的代價遠(yuǎn)遠(yuǎn)低于訓(xùn)練階段。
為了提高分類的準(zhǔn)確性、有效性和可伸縮性,在進(jìn)行分類之前,通常要對數(shù)據(jù)進(jìn)行預(yù)處理,包括:
(1) 數(shù)據(jù)清理。其目的是消除或減少數(shù)據(jù)噪聲,處理空缺值。
(2) 相關(guān)性分析。由于數(shù)據(jù)集中的許多屬性可能與分類任務(wù)不相關(guān),若包含這些屬性將減慢和可能誤導(dǎo)學(xué)習(xí)過程。相關(guān)性分析的目的就是刪除這些不相關(guān)或冗余的屬性。
(3) 數(shù)據(jù)變換。數(shù)據(jù)可以概化到較高層概念。比如,連續(xù)值屬性“收入”的數(shù)值可以概化為離散值:低,中,高。又比如,標(biāo)稱值屬性“市”可概化到高層概念“省”。此外,數(shù)據(jù)也可以規(guī)范化,規(guī)范化將給定屬性的值按比例縮放,落入較小的區(qū)間,比如[0,1]等。
2 分類算法的種類及特性
分類模型的構(gòu)造方法有決策樹、統(tǒng)計(jì)方法、機(jī)器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法等。按大的方向分類主要有:決策樹,關(guān)聯(lián)規(guī)則,貝葉斯,神經(jīng)網(wǎng)絡(luò),規(guī)則學(xué)習(xí),k-臨近法,遺傳算法,粗糙集以及模糊邏輯技術(shù)。
2.1 決策樹(decision tree)分類算法
決策樹是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它從一組無次序、無規(guī)則的元組中推理出決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式,在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性值的比較,并根據(jù)不同的屬性值從該結(jié)點(diǎn)向下分支,葉結(jié)點(diǎn)是要學(xué)習(xí)劃分的類。從根到葉結(jié)點(diǎn)的一條路徑就對應(yīng)著一條合取規(guī)則,整個決策樹就對應(yīng)著一組析取表達(dá)式規(guī)則。1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎(chǔ)上,1993年Quinlan又提出了C4.5算法。為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需要,后來又提出了若干改進(jìn)的算法,其中SLIQ (super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比較有代表性的兩個算法。
(1) ID3算法
ID3算法的核心是:在決策樹各級結(jié)點(diǎn)上選擇屬性時,用信息增益(information gain)作為屬性的選擇標(biāo)準(zhǔn),以使得在每一個非葉結(jié)點(diǎn)進(jìn)行測試時,能獲得關(guān)于被測試記錄最大的類別信息。其具體方法是:檢測所有的屬性,選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn),由該屬性的不同取值建立分支,再對各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點(diǎn)的分支,直到所有子集僅包含同一類別的數(shù)據(jù)為止。最后得到一棵決策樹,它可以用來對新的樣本進(jìn)行分類。
某屬性的信息增益按下列方法計(jì)算。通過計(jì)算每個屬性的信息增益,并比較它們的大小,就不難獲得具有最大信息增益的屬性。
設(shè)S是s個數(shù)據(jù)樣本的集合。假定類標(biāo)號屬性具有m個不同值,定義m個不同類Ci(i=1,…,m)。設(shè)si是類Ci中的樣本數(shù)。對一個給定的樣本分類所需的期望信息由下式給出:
其中pi=si/s是任意樣本屬于Ci的概率。注意,對數(shù)函數(shù)以2為底,其原因是信息用二進(jìn)制編碼。
設(shè)屬性A具有v個不同值{a1,a2,……,av}??梢杂脤傩訟將S劃分為v個子集{S1,S2,……,Sv},其中Sj中的樣本在屬性A上具有相同的值aj(j=1,2,……,v)。設(shè)sij是子集Sj中類Ci的樣本數(shù)。由A劃分成子集的熵或信息期望由下式給出:
熵值越小,子集劃分的純度越高。對于給定的子集Sj,其信息期望為
其中pij=sij/sj 是Sj中樣本屬于Ci的概率。在屬性A上分枝將獲得的信息增益是
Gain(A)= I(s1, s2, …,sm)-E(A)
ID3算法的優(yōu)點(diǎn)是:算法的理論清晰,方法簡單,學(xué)習(xí)能力較強(qiáng)。其缺點(diǎn)是:只對比較小的數(shù)據(jù)集有效,且對噪聲比較敏感,當(dāng)訓(xùn)練數(shù)據(jù)集加大時,決策樹可能會隨之改變。
(2) C4.5算法
C4.5算法繼承了ID3算法的優(yōu)點(diǎn),并在以下幾方面對ID3算法進(jìn)行了改進(jìn):
1) 用信息增益率來選擇屬性,克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足;
2) 在樹構(gòu)造過程中進(jìn)行剪枝;
3) 能夠完成對連續(xù)屬性的離散化處理;
4) 能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。
C4.5算法與其它分類算法如統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)等比較起來有如下優(yōu)點(diǎn):產(chǎn)生的分類規(guī)則易于理解,準(zhǔn)確率較高。其缺點(diǎn)是:在構(gòu)造樹的過程中,需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序,因而導(dǎo)致算法的低效。此外,C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集,當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運(yùn)行。
(3) SLIQ算法
SLIQ算法對C4.5決策樹分類算法的實(shí)現(xiàn)方法進(jìn)行了改進(jìn),在決策樹的構(gòu)造過程中采用了“預(yù)排序”和“廣度優(yōu)先策略”兩種技術(shù)。
1) 預(yù)排序。對于連續(xù)屬性在每個內(nèi)部結(jié)點(diǎn)尋找其最優(yōu)分裂標(biāo)準(zhǔn)時,都需要對訓(xùn)練集按照該屬性的取值進(jìn)行排序,而排序是很浪費(fèi)時間的操作。為此,SLIQ算法采用了預(yù)排序技術(shù)。所謂預(yù)排序,就是針對每個屬性的取值,把所有的記錄按照從小到大的順序進(jìn)行排序,以消除在決策樹的每個結(jié)點(diǎn)對數(shù)據(jù)集進(jìn)行的排序。具體實(shí)現(xiàn)時,需要為訓(xùn)練數(shù)據(jù)集的每個屬性創(chuàng)建一個屬性列表,為類別屬性創(chuàng)建一個類別列表。
2) 廣度優(yōu)先策略。在C4.5算法中,樹的構(gòu)造是按照深度優(yōu)先策略完成的,需要對每個屬性列表在每個結(jié)點(diǎn)處都進(jìn)行一遍掃描,費(fèi)時很多,為此,SLIQ采用廣度優(yōu)先策略構(gòu)造決策樹,即在決策樹的每一層只需對每個屬性列表掃描一次,就可以為當(dāng)前決策樹中每個葉子結(jié)點(diǎn)找到最優(yōu)分裂標(biāo)準(zhǔn)。
SLIQ算法由于采用了上述兩種技術(shù),使得該算法能夠處理比C4.5大得多的訓(xùn)練集,在一定范圍內(nèi)具有良好的隨記錄個數(shù)和屬性個數(shù)增長的可伸縮性。
然而它仍然存在如下缺點(diǎn):
1)由于需要將類別列表存放于內(nèi)存,而類別列表的元組數(shù)與訓(xùn)練集的元組數(shù)是相同的,這就一定程度上限制了可以處理的數(shù)據(jù)集的大小。
2) 由于采用了預(yù)排序技術(shù),而排序算法的復(fù)雜度本身并不是與記錄個數(shù)成線性關(guān)系,因此,使得SLIQ算法不可能達(dá)到隨記錄數(shù)目增長的線性可伸縮性。
(4) SPRINT算法
為了減少駐留于內(nèi)存的數(shù)據(jù)量,SPRINT算法進(jìn)一步改進(jìn)了決策樹算法的數(shù)據(jù)結(jié)構(gòu),去掉了在SLIQ中需要駐留于內(nèi)存的類別列表,將它的類別列合并到每個屬性列表中。這樣,在遍歷每個屬性列表尋找當(dāng)前結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時,不必參照其他信息,將對結(jié)點(diǎn)的分裂表現(xiàn)在對屬性列表的分裂,即將每個屬性列表分成兩個,分別存放屬于各個結(jié)點(diǎn)的記錄。
SPRINT算法的優(yōu)點(diǎn)是在尋找每個結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時變得更簡單。其缺點(diǎn)是對非分裂屬性的屬性列表進(jìn)行分裂變得很困難。解決的辦法是對分裂屬性進(jìn)行分裂時用哈希表記錄下每個記錄屬于哪個孩子結(jié)點(diǎn),若內(nèi)存能夠容納下整個哈希表,其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓(xùn)練集的大小成正比,當(dāng)訓(xùn)練集很大時,哈希表可能無法在內(nèi)存容納,此時分裂只能分批執(zhí)行,這使得SPRINT算法的可伸縮性仍然不是很好。
貝葉斯分類是統(tǒng)計(jì)學(xué)分類方法,它是一類利用概率統(tǒng)計(jì)知識進(jìn)行分類的算法。在許多場合,樸素貝葉斯(Na?ve Bayes,NB)分類算法可以與決策樹和神經(jīng)網(wǎng)絡(luò)分類算法相媲美,該算法能運(yùn)用到大型數(shù)據(jù)庫中,且方法簡單、分類準(zhǔn)確率高、速度快。由于貝葉斯定理假設(shè)一個屬性值對給定類的影響?yīng)毩⒂谄渌鼘傩缘闹担思僭O(shè)在實(shí)際情況中經(jīng)常是不成立的,因此其分類準(zhǔn)確率可能會下降。為此,就出現(xiàn)了許多降低獨(dú)立性假設(shè)的貝葉斯分類算法,如TAN(tree augmented Bayes network)算法。
? ? ? ?
(1) 樸素貝葉斯算法
設(shè)每個數(shù)據(jù)樣本用一個n維特征向量來描述n個屬性的值,即:X={x1,x2,…,xn},假定有m個類,分別用C1, C2,…,Cm表示。給定一個未知的數(shù)據(jù)樣本X(即沒有類標(biāo)號),若樸素貝葉斯分類法將未知的樣本X分配給類Ci,則一定是
P(Ci|X)>P(Cj|X) 1≤j≤m,j≠i
根據(jù)貝葉斯定理
由于P(X)對于所有類為常數(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ù)此方法,對一個未知類別的樣本X,可以先分別計(jì)算出X屬于每一個類別Ci的概率P(X|Ci)P(Ci),然后選擇其中概率最大的類別作為其類別。
樸素貝葉斯算法成立的前提是各屬性之間互相獨(dú)立。當(dāng)數(shù)據(jù)集滿足這種獨(dú)立性假設(shè)時,分類的準(zhǔn)確度較高,否則可能較低。另外,該算法沒有分類規(guī)則輸出。
(2) TAN算法
TAN算法通過發(fā)現(xiàn)屬性對之間的依賴關(guān)系來降低NB中任意屬性之間獨(dú)立的假設(shè)。它是在NB網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上增加屬性對之間的關(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對類別變量C的影響還取決于屬性Aj的取值。
這些增加的邊需滿足下列條件:類別變量沒有雙親結(jié)點(diǎn),每個屬性有一個類別變量雙親結(jié)點(diǎn)和最多另外一個屬性作為其雙親結(jié)點(diǎn)。
找到這組關(guān)聯(lián)邊之后,就可以計(jì)算一組隨機(jī)變量的聯(lián)合概率分布如下:
其中ΠAi代表的是Ai的雙親結(jié)點(diǎn)。由于在TAN算法中考慮了n個屬性中(n-1)個兩兩屬性之間的關(guān)聯(lián)性,該算法對屬性之間獨(dú)立性的假設(shè)有了一定程度的降低,但是屬性之間可能存
在更多其它的關(guān)聯(lián)性仍沒有考慮,因此其適用范圍仍然受到限制。
2.3 基于關(guān)聯(lián)規(guī)則的分類算法
關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的一個重要的、高度活躍的領(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)時,ARCS比C4.5稍微精確一點(diǎn)。ARCS的準(zhǔn)確性與離散化程度有關(guān)。從可伸縮性來說,不論數(shù)據(jù)庫多大,ARCS需要的存儲容量為常數(shù)。
CBA(classification based on association)是基于關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法的分類算法。該算法分兩個步驟構(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]對該過程進(jìn)行了較深入的研究,使得算法在此步驟不需要對訓(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找出滿足給定支持度和增長率閾值的EP。己經(jīng)發(fā)現(xiàn),在許多數(shù)據(jù)集上,CAEP比C4.5和基于關(guān)聯(lián)的分類更精確。一種替代的、基于跳躍的HV露模式JEP(Jnmping Emerging Pattern)是一種特殊類型的EP,項(xiàng)集的支持度由在一個數(shù)據(jù)集中的0陡峭地增長到另一個數(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ū)動為基礎(chǔ)的過度適合規(guī)則的剪枝。第一步,運(yùn)用置信度規(guī)則建立分類器。主要是采用某種置信度的單調(diào)性建立基于置信度的剪枝策略。第二步,為實(shí)現(xiàn)精確性,用關(guān)聯(lián)規(guī)則建立一種平衡于DT(Dccision Tree)歸納的精確度驅(qū)動剪枝。這樣的結(jié)果就是ADT(Association Based Decision Trec)。它聯(lián)合了大量的關(guān)聯(lián)規(guī)則和DT歸納精確性驅(qū)動剪枝技術(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)有效地存儲關(guān)聯(lián)規(guī)則?;谥眯哦取⑾嚓P(guān)性和數(shù)據(jù)庫覆蓋來剪枝。分類的具體執(zhí)行采用加權(quán)廠來分析。與CBA和C 4.5相比,CMAR性能優(yōu)異且伸縮性較好。但CMAR優(yōu)先生成的是長規(guī)則,對數(shù)據(jù)庫的覆蓋效果較差;利用加權(quán)x2統(tǒng)計(jì)量進(jìn)行分類,會造成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ī)則生成時采用貪心算法,這比產(chǎn)生所有候選項(xiàng)集的效率高;采用一種動態(tài)方法避免在規(guī)則生成時的重復(fù)計(jì)算;采用頂期精確性評價規(guī)則,并在預(yù)測時應(yīng)用最優(yōu)的規(guī)則,避免產(chǎn)生冗余的規(guī)則。另外,MSR(Minimnm Set Rule)針對基于關(guān)聯(lián)規(guī)則分類算法中產(chǎn)生的關(guān)聯(lián)規(guī)則集可能太大的問題,在分類中運(yùn)用最小關(guān)聯(lián)規(guī)則集。在此算法中,CARS并不是通過置信度首先排序,因?yàn)楦咧眯哦纫?guī)則對噪聲是很敏感的。采用早期剪枝力方法可減少關(guān)聯(lián)規(guī)則的數(shù)量,并保證在最小集中沒有不相關(guān)的規(guī)則。實(shí)驗(yàn)證實(shí),MSR比C45和CBA的錯誤率要低得多。
雖然數(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)造。簡而言之,就是在樹的每一層,為每一個屬性建立一個維表,存放各屬性的每個取值屬于各個類別的個數(shù)以及所屬的結(jié)點(diǎn)編號。根據(jù)這些信息可以為當(dāng)前結(jié)點(diǎn)計(jì)算每種分裂標(biāo)準(zhǔn)的值,選出最優(yōu)的分裂標(biāo)準(zhǔn),然后據(jù)此對結(jié)點(diǎn)進(jìn)行分裂,修改維表中結(jié)點(diǎn)編號列的值。在上述過程中,對維表的創(chuàng)建和修改需要進(jìn)行多次,若用SQL實(shí)現(xiàn),耗時很多,因此用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一般是由用戶利用高級語言實(shí)現(xiàn)的,無法使用數(shù)據(jù)庫系統(tǒng)提供的查詢處理機(jī)制,無法利用查詢優(yōu)化方法,且UDF的編寫和維護(hù)相當(dāng)復(fù)雜。此外,MIND中用SQL語句實(shí)現(xià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ù)集中各個屬性取值組合的類別分布信息,通過最小置信度和最小支持度兩個閾值找出有意義的分類規(guī)則。在該算法中,首先利用SQL語句計(jì)算每個屬性進(jìn)行類別判定的信息量,從而選擇一個最優(yōu)的分裂屬性,并且按照信息量的大小對屬性進(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ù)的取值需用戶完成等。
評論
查看更多