《數(shù)據(jù)挖掘》數(shù)據(jù)挖掘分類算法綜述專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專學(xué) 號(hào)：S指導(dǎo)教師：時(shí) 間：2011年08月21日數(shù)據(jù)挖掘分類算法綜述2080(KDD，KnowledgeDiscoveryinDatabase)(Data有噪聲的、模糊的、隨機(jī)的、實(shí)際應(yīng)用的數(shù)據(jù)中提取隱含在其中的、人們不知道的但又有用的信息和知識(shí)的過程。定類別中的一種技術(shù)。分類的基本步驟數(shù)據(jù)分類過程主要包含兩個(gè)步驟：1(被稱為類別屬性)。分類學(xué)習(xí)方法所使用的數(shù)據(jù)集稱為訓(xùn)練樣本集合，因此分類學(xué)習(xí)又可以稱為有指導(dǎo)學(xué)習(xí)(learningbyexample)而無指導(dǎo)學(xué)習(xí)則是在訓(xùn)練樣本的類別與類別個(gè)數(shù)均未知的情況下進(jìn)行的。分類算法訓(xùn)練數(shù)據(jù)分類規(guī)則Ifage=“31-40”andincome=highThencredit_rating=excellent分類算法訓(xùn)練數(shù)據(jù)分類規(guī)則Ifage=“31-40”andincome=highThencredit_rating=excellentnameageincomeCredit_ratingSandyJones30lowfairBilllee30lowexcellentCourtneyfox31~40highexcellentSusanlake>40medfairClairephips>40medfairAndrebeau31~40highexcellent…………圖1數(shù)據(jù)分類過程中的學(xué)習(xí)建模例如使用保持(holdout)方法。如果一個(gè)學(xué)習(xí)所獲模型的準(zhǔn)確率經(jīng)測(cè)試被認(rèn)為是可以接受的，那么就可以使用這一模型對(duì)未來數(shù)據(jù)行或?qū)ο?其類別未知)進(jìn)行分類。例如，在圖2中利用學(xué)習(xí)獲得的分類規(guī)則(模型)。對(duì)已知測(cè)試數(shù)據(jù)進(jìn)行模型準(zhǔn)確率的評(píng)估，以及對(duì)未知類別的新數(shù)據(jù)進(jìn)行分類預(yù)測(cè)。測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)分類算法分類規(guī)則nameage incomeCredit_ratingSandyJonesBilllee CourtneyfoxSusanlake >40Clairephips>40Andrebeau31~40lowlowhighmedmedhigh…fairexcellentexcellentfairfairexcellent…新數(shù)據(jù)……JohnHenri30~41 high圖2數(shù)據(jù)分類過程中的分類測(cè)試T(Training條條的數(shù)據(jù)庫(kù)記錄(Record)組成的，T的每一條記錄包含若干條屬性(Attribute)成一個(gè)特征向量，用矢量X(x,x1 2

,...,xn

xi

(1in)對(duì)應(yīng)各非類別屬性，可以有不同的值域，當(dāng)一屬性的值域?yàn)檫B續(xù)域時(shí)，該屬性為連續(xù)屬性(NumericalAttribute)，否則為離散屬性(DiscreteAttribute)，用c表示類別屬性c(c,c1

,...,ck

)，即數(shù)據(jù)集有k個(gè)不同的類別，那么，T就隱含了一個(gè)從矢量X到H:fXc分類數(shù)據(jù)的預(yù)處理進(jìn)行預(yù)處理，包括以下幾方面：數(shù)據(jù)清理以各種形式和排列方式出現(xiàn)，對(duì)噪聲數(shù)據(jù)通常關(guān)心的問題如下：①發(fā)現(xiàn)重復(fù)記錄。②查找錯(cuò)誤的屬性值。在分類數(shù)據(jù)中尋找錯(cuò)誤是大型數(shù)據(jù)集所面臨的一個(gè)問題。一些數(shù)據(jù)挖掘工具提供了頻率值或分類屬性的預(yù)測(cè)能力值的匯總，可以認(rèn)為預(yù)測(cè)能力值接近于0的屬性值可能是錯(cuò)誤的。③數(shù)據(jù)平滑。數(shù)據(jù)平滑是一個(gè)數(shù)據(jù)清理和數(shù)據(jù)轉(zhuǎn)換的過程。一些數(shù)據(jù)平滑技術(shù)努力減少數(shù)值屬性值的維數(shù)。一些分類器，如神經(jīng)網(wǎng)絡(luò)，有在分類過程中用函數(shù)完成數(shù)據(jù)平滑的功能。當(dāng)數(shù)據(jù)平滑在分類過程中完成時(shí)，則稱為是內(nèi)部數(shù)據(jù)平滑。外部數(shù)據(jù)平滑是在分類以前進(jìn)行的，舍入和計(jì)算平均值是兩種簡(jiǎn)單的外部數(shù)據(jù)平滑技術(shù)。當(dāng)我們想使用不支持?jǐn)?shù)值數(shù)據(jù)的分類器，并想保留數(shù)值屬性值的原始信息時(shí)，用平均值平滑就很合適。在這種情況下，所有的數(shù)值屬性值被相應(yīng)的中值所替代。法。①忽略缺失數(shù)據(jù)。一些數(shù)據(jù)挖掘算法，包括神經(jīng)網(wǎng)絡(luò)和貝葉斯分類器采用了這種方法。②丟棄含有缺失值的記錄。當(dāng)記錄只有一小部分缺失數(shù)據(jù)并且我們可以確定缺失值表示信息丟失時(shí)，應(yīng)用這種方法非常合適。③對(duì)于實(shí)值數(shù)據(jù)，用中值代替缺失值。在大多數(shù)情況下這是處理數(shù)值屬性的一種理想的方法。④對(duì)缺失數(shù)據(jù)給定一個(gè)假設(shè)的值，這可能需要使用某種方法預(yù)測(cè)這個(gè)值是什么。⑤用其它相似樣本中的屬性值代替某個(gè)樣本缺失的屬性值。相關(guān)性分析可能誤導(dǎo)學(xué)習(xí)過程。相關(guān)性分析的目的就是刪除這些不相關(guān)或冗余的屬性。數(shù)據(jù)變換數(shù)據(jù)可以概化到較高層概念。比如，連續(xù)值屬性“收入”的數(shù)值可以概化為離散值：低、中、高。此外數(shù)據(jù)也可以規(guī)范化，規(guī)范化將給定屬性的值按比例縮放落入較小的區(qū)間，比如[0，1]等。分類算法離的KNN算法、基于歸納的決策樹算法、基于統(tǒng)計(jì)的貝葉斯算法等等，本文主要介紹以下幾種經(jīng)典分類算法。決策樹分類統(tǒng)，它采用自頂向下不回溯策略，能保證找到一個(gè)簡(jiǎn)單的樹。基本思想決策樹方法是挖掘分類規(guī)則的有效方法，通常包括兩個(gè)部分：①樹的生成同的測(cè)試屬性遞歸進(jìn)行數(shù)據(jù)分割。②樹的修剪ID3C4.策樹生長(zhǎng)的快慢及決策樹的結(jié)構(gòu)，從而可尋找到規(guī)則信息的優(yōu)劣。且使產(chǎn)生的決策樹分支過細(xì)、結(jié)構(gòu)差，從而難以發(fā)現(xiàn)有用的規(guī)則信息。隨著訓(xùn)練樣本集中樣本個(gè)數(shù)的不斷增多(即樣本集規(guī)模不斷擴(kuò)大)實(shí)現(xiàn)過程samplesattribute_list輸出：一棵決策樹。①創(chuàng)建結(jié)點(diǎn)N；//根結(jié)點(diǎn)②IFsamplesCTHENN作為葉結(jié)點(diǎn)，以類C標(biāo)記；③IFattribute_listTHENNsamples通的類；④選擇attribute_list中具有最高信息增益的屬性test_attribute；⑤標(biāo)記結(jié)點(diǎn)N為test_attribute；//選取具有最高信息增益的屬性作為根結(jié)點(diǎn)⑥FOReachtest_attribute中的已知值ai由結(jié)點(diǎn)N長(zhǎng)出一個(gè)條件為test_attribute=ai分支；⑦設(shè)si是samples中test_attribute=ai的樣本的集合；//一個(gè)劃分⑧IFsi為空THEN 加上一個(gè)樹葉，標(biāo)記為samples中最普通的類；⑨ELSEGenerate_decision_tree(siattribute_list-test_attribute)返回的結(jié)點(diǎn)；基于距離的分類算法思想類來實(shí)現(xiàn)分類。給定一個(gè)數(shù)據(jù)庫(kù)D={t1，t2，…，t

n 1}和一組類C={C，…n 1

}。假定每個(gè)mti={ti1，ti2，…，tik}，每個(gè)類也包含數(shù)值性屬性值：Cj={Cj1，Cj2，…，Cjk}，則分類問題是要分配每個(gè)ti到滿足如下條件的類Cj：sim(ti，Cj)>=sim(ti，Cl)，Cl∈C，Cl≠Cj，（2-1）其中，sim(ti，Cj)表示相似性。在實(shí)際的計(jì)算中，往往用距離來表征，距離越近，相似性越大，距離越大，相似性越小。進(jìn)行比較。實(shí)現(xiàn)過程C1，…，Cmtc。①距離初始化②FORi:=1tomDO③IFdis(ci，t)<distTHENBEGIN④c←i；⑤dist←dist(ci，t)；⑥END.規(guī)則歸納規(guī)則歸納的策略規(guī)則歸納有四種策略：減法、加法，先加后減、先減后加。條件（屬性值）或減除合取項(xiàng)（廣，使推廣后的例子或規(guī)則不覆蓋任何反例。②加法策略：起始假設(shè)規(guī)則的條件部分為空（永真規(guī)則），如果該規(guī)則覆蓋了反例，則不停地向規(guī)則增加條件或合取項(xiàng)，直到該規(guī)則不再覆蓋反例。③先加后減策略：由于屬性間存在相關(guān)性，因此可能某個(gè)條件的加入會(huì)導(dǎo)致前面加入的條件沒什么作用，因此需要減除前面的條件。④先減后加策略：道理同先加后減，也是為了處理屬性間的相關(guān)性。規(guī)則歸納算