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

《機(jī)器學(xué)習(xí)與知識發(fā)現(xiàn)實(shí)驗(yàn)—酒分類》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、Usingchemicalanalysisdeterminetheoriginofwines趙啟杰SC11011063摘要采用較簡單的決策樹歸納算法根據(jù)紅酒的成分對其進(jìn)行分類，劃分度量采用的是Gini指標(biāo)，所有數(shù)據(jù)都看做是連續(xù)屬性，進(jìn)行二元劃分，最后得到的是一棵二叉決策樹。最后采用二折交叉驗(yàn)證的方式，進(jìn)行評估，得到的分類準(zhǔn)確度在85%左右。為了簡單，沒有考慮噪聲的干擾，沒有考慮模型的過分?jǐn)M合問題，沒有考慮泛化誤差。相關(guān)工作算法的實(shí)現(xiàn)參考《數(shù)據(jù)挖掘?qū)д摗匪惴?.1的決策樹歸納算法的框架。TreeGr

2、owth(E,F)ifStopping_cond(E,F)=truethenleaf=creatNode()leaf.label=Classify(E)returnleafelseroot=creatNode()root.test_cond=find_best_split(E,F)令V={v

3、v是root.test_cond的一個可能的輸出}for每個vinVdoEv={e

4、root.test_cond(e)=v并且einE}child=TreeGrowth(Ev,F)將child作為root的派

5、生節(jié)點(diǎn)添加到樹中，并將邊(root-->child)標(biāo)記為vendforendifruturnroot其中E是訓(xùn)練記錄集，F(xiàn)是屬性集。涉及到的主要類：Tuple：數(shù)據(jù)集的一條記錄，這里把記錄的所有屬性都當(dāng)成浮點(diǎn)型數(shù)據(jù)處理。TupleTable：整個數(shù)據(jù)集。其中iClassNum代表總共的類數(shù)，iTableLen代表記錄數(shù)，iTupleSize代表記錄的屬性數(shù)，rgStrClasses保存所有的類，rgStrAttribute保存所有的屬性，rgTuples保存所有的記錄。DecisionNode：

6、決策樹中的一個節(jié)點(diǎn)。TestCond：決策樹非葉子節(jié)點(diǎn)中保存的測試條件。涉及到的主要方法：TupleTable：：InitTableFromFile從數(shù)據(jù)文件獲取數(shù)據(jù)，初始化數(shù)據(jù)集。數(shù)據(jù)文件格式需要做適當(dāng)修改。TupleTable：：TupleIndexs從數(shù)據(jù)集導(dǎo)出一個數(shù)據(jù)集的索引，即一個由Tuple指針組成的數(shù)組，該數(shù)組中的每一個元素指向TupleTable中的一個Tuple?？梢酝ㄟ^比較Tuple的值對索引中的指針進(jìn)行排序。Stopping_cond通過檢查是否所有的記錄都屬于同一個類，或者

7、都具有相同的屬性值，決定是否終止決策樹的增長，或者檢查記錄數(shù)是否小于某一個最小閾值（_BOUNDARY_RECORD_）。通過調(diào)整閾值可以在一定范圍內(nèi)改變分類器的準(zhǔn)確率。CreateNode為決策樹建立新節(jié)點(diǎn)，決策樹的節(jié)點(diǎn)或者是一個測試條件，即一個testcond對象，或者是一個類標(biāo)號。Find_best_split確定應(yīng)當(dāng)選擇哪個屬性作為劃分訓(xùn)練記錄的測試條件。使用的不純性度量是Gini指標(biāo)。首先對索引按第j個屬性進(jìn)行排序，如果索引中第i個記錄和第i+1個記錄不是同一個類，則將第i個記錄和第i+

8、1個記錄的屬性j的中間值作為劃分點(diǎn)，計(jì)算Gini指標(biāo)。循環(huán)計(jì)算所有可能的Gini指標(biāo)，找出其中的最小值，保存屬性名和屬性值，作為當(dāng)前最優(yōu)測試條件。GetGini獲取某個訓(xùn)練數(shù)據(jù)子集的Gini指標(biāo)。其中p(i

9、t)表示節(jié)點(diǎn)t中屬于類i的記錄所占比例。Classify為節(jié)點(diǎn)確定類標(biāo)號，對于節(jié)點(diǎn)t，統(tǒng)計(jì)分配到該節(jié)點(diǎn)的所有記錄中類i的記錄數(shù)0

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

11、一定的概率分布（如Logistic回歸）；2〉找到最優(yōu)決策樹是NP完全問題，許多決策樹算法都采取啟發(fā)式方法指導(dǎo)對假設(shè)空間的搜索，如采用貪心的、自頂向下的遞歸劃分策略建立決策樹；3〉不需要昂貴的計(jì)算代價，即使訓(xùn)練集非常大，也可以快速建立模型。此外，決策樹一旦建立，未知樣本分類也非常快，最壞情況下的時間復(fù)雜度為O(w)，其中w是樹的最大深度；4〉決策樹相對容易解釋，特別是小型決策樹；在很多簡單的數(shù)據(jù)集上，決策樹的準(zhǔn)確率也可以與其他分類算法想媲美；5〉決策樹算法對于噪聲的干擾具有相當(dāng)好的