機器學習與知識發(fā)現(xiàn)實驗

1、Using chemical analysis determine the origin of wines趙啟杰 SC11011063摘要采用較簡單的決策樹歸納算法根據(jù)紅酒的成分對其進行分類，劃分度量采用的是Gini 指標，所有數(shù)據(jù)都看做是連續(xù)屬性，進行二元劃分，最后得到的是一棵二叉決策樹。最后采 用二折交叉驗證的方式，進行評估，得到的分類準確度在85%左右。為了簡單，沒有考慮噪聲的干擾，沒有考慮模型的過分擬合問題，沒有考慮泛化誤差。相關(guān)工作算法的實現(xiàn)參考數(shù)據(jù)挖掘?qū)д撍惴?.1的決策樹歸納算法的框架。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的一個可能的輸出for 每個 v in V doEv =elroot.test_cond(e)=v 并且 e in Echild=TreeGrowth(Ev，F(xiàn))將child作為root的派生節(jié)點添加到樹中，并將邊(root-child)標記為v end forend ifruturn root其中E是訓練記錄集，F(xiàn)是屬性集。涉及到的主要類：Tup

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

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

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

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

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

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

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

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