機(jī)器學(xué)習(xí)與知識(shí)發(fā)現(xiàn)實(shí)驗(yàn)

1、Using chemical analysis determine the origin of wines趙啟杰 SC11011063摘要采用較簡(jiǎn)單的決策樹(shù)歸納算法根據(jù)紅酒的成分對(duì)其進(jìn)行分類(lèi)，劃分度量采用的是Gini 指標(biāo)，所有數(shù)據(jù)都看做是連續(xù)屬性，進(jìn)行二元?jiǎng)澐郑詈蟮玫降氖且豢枚鏇Q策樹(shù)。最后采 用二折交叉驗(yàn)證的方式，進(jìn)行評(píng)估，得到的分類(lèi)準(zhǔn)確度在85%左右。為了簡(jiǎn)單，沒(méi)有考慮噪聲的干擾，沒(méi)有考慮模型的過(guò)分?jǐn)M合問(wèn)題，沒(méi)有考慮泛化誤差。相關(guān)工作算法的實(shí)現(xiàn)參考數(shù)據(jù)挖掘?qū)д撍惴?.1的決策樹(shù)歸納算法的框架。TreeGrowth(E,F)if Stopping_cond(E,F)=true thenl

2、eaf=creatNode()leaf.label=Classify(E)return leafelseroot=creatNode()root.test_cond=find_best_split(E, F)令V=v|v是root.test_cond的一個(gè)可能的輸出for 每個(gè) v in V doEv =elroot.test_cond(e)=v 并且 e in Echild=TreeGrowth(Ev，F(xiàn))將child作為root的派生節(jié)點(diǎn)添加到樹(shù)中，并將邊(root-child)標(biāo)記為v end forend ifruturn root其中E是訓(xùn)練記錄集，F(xiàn)是屬性集。涉及到的主要類(lèi)：Tup

3、le：數(shù)據(jù)集的一條記錄，這里把記錄的所有屬性都當(dāng)成浮點(diǎn)型數(shù)據(jù)處理。TupleTable：整個(gè)數(shù)據(jù)集。其中iClassNum代表總共的類(lèi)數(shù)，iTableLen代表記錄數(shù)， iTupleSize代表記錄的屬性數(shù)，rgStrClasses保存所有的類(lèi)，rgStrAttribute保存所有的屬性， rgTuples保存所有的記錄。DecisionNode :決策樹(shù)中的一個(gè)節(jié)點(diǎn)。TestCond：決策樹(shù)非葉子節(jié)點(diǎn)中保存的測(cè)試條件。涉及到的主要方法：TupleTable：: InitTableFromFile從數(shù)據(jù)文件獲取數(shù)據(jù)，初始化數(shù)據(jù)集。數(shù)據(jù)文件格式需要做適當(dāng)修改。TupleTable：: Tuple

4、lndexs從數(shù)據(jù)集導(dǎo)出一個(gè)數(shù)據(jù)集的索引，即一個(gè)由Tuple指針組成的數(shù)組，該數(shù)組中的每一個(gè) 元素指向TupleTable中的一個(gè)Tuple。可以通過(guò)比較Tuple的值對(duì)索引中的指針進(jìn)行排序。Stopping_cond通過(guò)檢查是否所有的記錄都屬于同一個(gè)類(lèi)，或者都具有相同的屬性值，決定是否終止決 策樹(shù)的增長(zhǎng)，或者檢查記錄數(shù)是否小于某一個(gè)最小閾值(_BOUNDARY_RECORD_)。通過(guò) 調(diào)整閾值可以在一定范圍內(nèi)改變分類(lèi)器的準(zhǔn)確率。CreateNode為決策樹(shù)建立新節(jié)點(diǎn)，決策樹(shù)的節(jié)點(diǎn)或者是一個(gè)測(cè)試條件，即一 個(gè)testcond對(duì)象，或者 是一個(gè)類(lèi)標(biāo)號(hào)。Find_best_split確定應(yīng)當(dāng)選擇哪

5、個(gè)屬性作為劃分訓(xùn)練記錄的測(cè)試條件。使用的不純性度量是Gini指標(biāo)。 首先對(duì)索引按第j個(gè)屬性進(jìn)行排序，如果索引中第i個(gè)記錄和第i+1個(gè)記錄不是同一個(gè)類(lèi)， 則將第i個(gè)記錄和第i+1個(gè)記錄的屬性j的中間值作為劃分點(diǎn)，計(jì)算Gini指標(biāo)。循環(huán)計(jì)算所 有可能的Gini指標(biāo)，找出其中的最小值，保存屬性名和屬性值，作為當(dāng)前最優(yōu)測(cè)試條件。GetGini獲取某個(gè)訓(xùn)練數(shù)據(jù)子集的Gini指標(biāo)。Gini(t) = 1 一 *1 p (i 11 )2i=0其中p(i|t)表示節(jié)點(diǎn)t中屬于類(lèi)i的記錄所占比例。Classify為節(jié)點(diǎn)確定類(lèi)標(biāo)號(hào)，對(duì)于節(jié)點(diǎn)t，統(tǒng)計(jì)分配到該節(jié)點(diǎn)的所有記錄中類(lèi)i的記錄數(shù)0iiClassNum，則節(jié)點(diǎn)

6、的類(lèi)標(biāo)號(hào)為maxi。Sort_record對(duì)記錄子集的索引按照某個(gè)屬性從小到大進(jìn)行排序，為了簡(jiǎn)單，使用了冒泡。TreeGrowth遞歸創(chuàng)建決策樹(shù)。創(chuàng)建決策時(shí)之前需要對(duì)作為輸入的數(shù)據(jù)集文件做適當(dāng)修改：屬性個(gè)數(shù)n屬性名1屬性名n類(lèi)個(gè)數(shù)m類(lèi)名1.類(lèi)名m記錄數(shù)k類(lèi)名，屬性1,.,屬性n類(lèi)名，屬性1,.,屬性n由于分類(lèi)器的性能評(píng)估并不是實(shí)驗(yàn)的主要內(nèi)容，因此這里只是簡(jiǎn)單的做了一下二折交叉 驗(yàn)證，將數(shù)據(jù)集隨機(jī)分成兩個(gè)子集，其中一個(gè)作為訓(xùn)練集，另一個(gè)作為檢驗(yàn)集，然后互換集 合再做一次，最后得到的準(zhǔn)確率在85%左右。優(yōu)劣分析:1決策樹(shù)歸納是一種構(gòu)建分類(lèi)模型的非參數(shù)方法。換言之，它不要求任何先驗(yàn)假設(shè)， 不假定類(lèi)和

7、其他屬性服從一定的概率分布(如Logistic回歸)；2找到最優(yōu)決策樹(shù)是NP完全問(wèn)題，許多決策樹(shù)算法都采取啟發(fā)式方法指導(dǎo)對(duì)假設(shè)空 間的搜索，如采用貪心的、自頂向下的遞歸劃分策略建立決策樹(shù)；3不需要昂貴的計(jì)算代價(jià)，即使訓(xùn)練集非常大，也可以快速建立模型。此外，決策樹(shù) 一旦建立，未知樣本分類(lèi)也非?？欤顗那闆r下的時(shí)間復(fù)雜度為O(w)，其中w是樹(shù)的最大 深度；4決策樹(shù)相對(duì)容易解釋，特別是小型決策樹(shù)；在很多簡(jiǎn)單的數(shù)據(jù)集上，決策樹(shù)的準(zhǔn)確 率也可以與其他分類(lèi)算法想媲美；5決策樹(shù)算法對(duì)于噪聲的干擾具有相當(dāng)好的魯棒性，采用避免過(guò)分?jǐn)M合的方法之后尤 其如此；6冗余屬性不會(huì)對(duì)決策樹(shù)的準(zhǔn)確率造成不利影響。如果一個(gè)屬性

8、在數(shù)據(jù)集中與另一個(gè) 屬性是強(qiáng)相關(guān)的，則該屬性是冗余的。在兩個(gè)冗余屬性中，如果已經(jīng)選擇其中一個(gè)作為用于 劃分的屬性，則另一個(gè)屬性將被忽略；另一方面，如果數(shù)據(jù)集中含有很多與目標(biāo)變量不相關(guān) 的屬性，則某些屬性可能在樹(shù)的構(gòu)造過(guò)程中偶然被選中，導(dǎo)致決策樹(shù)過(guò)于龐大。在預(yù)處理階 段，特征選擇技術(shù)能夠幫助找出并刪除不相關(guān)屬性，以幫助提高決策樹(shù)的準(zhǔn)確率；7數(shù)據(jù)碎片(data fragmentation)問(wèn)題。由于大多數(shù)的決策樹(shù)算法采用自頂向下的遞歸 劃分方法。因此沿著樹(shù)向下，記錄會(huì)越來(lái)越少，在葉子結(jié)點(diǎn)記錄數(shù)量可能太少，以致對(duì)于葉 子結(jié)點(diǎn)代表的類(lèi)的判決不具有統(tǒng)計(jì)顯著性。解決這一問(wèn)題的方法是當(dāng)樣本數(shù)小于某個(gè)特定閥

9、值時(shí)停止分裂；8由于大多數(shù)決策樹(shù)算法采用分治劃分策略，因此屬性空間的不同部分可能使用相同 的測(cè)試條件，從而導(dǎo)致子樹(shù)在決策書(shū)中重復(fù)出現(xiàn)多次，這使得決策樹(shù)過(guò)于復(fù)雜，并且可能更難于解釋;9決策樹(shù)是學(xué)習(xí)離散值函數(shù)的典型代表，然而，它不能很好的推廣到某些特定的布爾 問(wèn)題。如對(duì)于奇偶函數(shù)來(lái)說(shuō)，當(dāng)奇數(shù)偶數(shù)個(gè)布爾屬性為真時(shí)其值為0/1，對(duì)這樣的函數(shù)準(zhǔn)確 建模需要一棵具有2的d次方個(gè)節(jié)點(diǎn)的滿決策樹(shù)（d為布爾屬性的個(gè)數(shù)）。10對(duì)于測(cè)試條件只涉及一個(gè)屬性的決策樹(shù)，可以將決策樹(shù)的成長(zhǎng)過(guò)程看成劃分屬性空 間為不相交的區(qū)域的過(guò)程，直到每個(gè)區(qū)域都只包含同一記錄，兩個(gè)不同類(lèi)的相鄰區(qū)域之間的 邊界稱作決策邊界（Decision

10、 Boundary）0由于測(cè)試屬性只涉及單個(gè)屬性，因此決策邊界是 平行于坐標(biāo)軸的直線，這就限制了決策樹(shù)對(duì)連續(xù)屬性之間復(fù)雜關(guān)系建模的表達(dá)能力。斜決策 樹(shù)（Oblique Decision Tree）是克服以上局限的方法之一，它允許測(cè)試條件涉及多個(gè)屬性（如 x+y1），當(dāng)然，這一技術(shù)在賦予決策樹(shù)更強(qiáng)表達(dá)能力的同時(shí)，為給定結(jié)點(diǎn)找出最佳的測(cè)試 條件的計(jì)算復(fù)雜度也是昂貴的。另一種將屬性空間劃分為非矩形區(qū)域的方法是構(gòu)造歸納（Constructive Induction），即創(chuàng)建復(fù)合屬性用于代表已有屬性的算術(shù)/邏輯組合，該方法不需 要昂貴的計(jì)算花費(fèi)；11研究表明大部分不純性度量方法的結(jié)果是指一致的，因此不純性度量方法的選擇對(duì) 決策樹(shù)算法的性能影響很小。樹(shù)