模式識別——決策樹算法

1、數(shù)學與計算機學院課程名稱: 模式識別 題 目: 決策樹 任課老師: 王類 年級專業(yè): 2014級應用數(shù)學 姓 名: 閆輝 時 間: 2014 年 12 月 10 日模式識別決策樹算法目 錄一 決策樹算法介紹3二 id3算法描述3三 id3算法java實現(xiàn)51 實例52 算法的java實現(xiàn)7四 id3算法性能分析141 優(yōu)勢142 弊端14五 id3算法改進14六、 附錄核心算法的主要源代碼15161617參考文獻18決策樹算法一 決策樹算法介紹決策樹是數(shù)據(jù)挖掘分類算法的一個重要方法。在各種分類算法中，決策樹是最直觀的一種。決策樹(decision tree）是在已知各種情況發(fā)生概率的基礎(chǔ)上，通

2、過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。在機器學習中，決策樹是一個預測模型，他代表的是對象屬性與對象值之間的一種映射關(guān)系。entropy = 系統(tǒng)的凌亂程度，使用算法id3,c4.5和c5.0生成樹算法使用熵。這一度量是基于信息學理論中熵的概念。決策樹是由一系列節(jié)點組成的，每一個節(jié)點代表一個特征和相應的決策規(guī)則。最上部的節(jié)點是根節(jié)點(這里的“樹”通常是倒置過來畫的，即根在頂端)，此時所有的樣本都在一起，經(jīng)過該節(jié)點后被劃分到各個子節(jié)點中。每個子節(jié)點再用新的特征

3、來進一步?jīng)Q策，直到最后的葉節(jié)點。在葉節(jié)點上，每一個節(jié)點只包含純一類的樣本，不需要再劃分。決策樹構(gòu)造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數(shù)據(jù)集是根據(jù)實際需要有歷史的、有一定綜合程度的，用于數(shù)據(jù)分析處理的數(shù)據(jù)集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數(shù)扼集（稱為測試數(shù)據(jù)集）中的數(shù)據(jù)校驗決策樹生成過程中產(chǎn)生的初步規(guī)則，將那些影響預衡準確性的分枝剪除。二 id3算法描述id3算法是由quinlan首先提出的。該算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標準，從而實現(xiàn)對數(shù)據(jù)的歸納分類

4、。 id3算法主要針對屬性選擇問題，是決策樹學習方法中最具影響和最為典型的算法。id3采用貪心方法，其中決策樹以自頂向下遞歸的分治方式構(gòu)造。大多數(shù)決策樹歸納算法都沿用這種自頂向下的方法，從訓練元組集和它們的相關(guān)聯(lián)的類標號開始構(gòu)造決策樹。隨著樹的構(gòu)建，訓練集遞歸地劃分成較小的子集。id3算法中關(guān)鍵的一步是屬性選擇度量，即選擇分裂準則。其中的三種度量方法分別是信息增益、增益率和gini指標。(示例算法選擇了第一種方法)。當獲取信息時，將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信息伴著不確定性。算法的基本策略如下：算法：generate_decision_tree。由數(shù)據(jù)劃分d的訓練元組產(chǎn)生決策樹。輸入：1

5、.數(shù)據(jù)劃分d是訓練元組和對應類標號的集合2.attribute_list，候選屬性的集合3.attribute_selection_method，一個確定“最好”地劃分數(shù)據(jù)元組為個體類的分裂準則的過程。這個準則由分裂屬性和分裂點或分裂子集組成。輸出：一棵決策樹方法：創(chuàng)建一個節(jié)點n；if d中的元組都是同一類c，then返回n作為葉節(jié)點，以類c標記；if attribute_list 為空then返回n作為葉節(jié)點，標記為d中的多數(shù)類； /多數(shù)表決使用attribute_selection_method（d，attribute_list），找出“最好”的splitting_criterion；7用

6、splitting_criterion標記節(jié)點n；if splitting_ attribute是離散值的并且允許多路劃分then /不限于二叉樹attribute_list attribute_list - splitting_ attribute ； /刪除劃分屬性for splitting_criterion的每個輸出j / 劃分元組并對每個劃分產(chǎn)生子樹設(shè)dj是d中滿足輸出j的數(shù)據(jù)元組的集合；/一個劃分if dj為空then加一個樹葉到節(jié)點n，標記為d中的多數(shù)類；else 加一個由generate_decision_tree（dj，attribute_list）返回的節(jié)點到節(jié)點n；end

7、 for返回n；上述算法基本策略中，用到三個參數(shù)d、attribute_list和attribute_selection_method調(diào)用該算法。其中，d為數(shù)據(jù)劃分；attribute_list是描述元組的屬性列表；attribute_selection_method指定選擇屬性的啟發(fā)式過程，所選擇的屬性按類“最好”地區(qū)分元組。該過程使用一種屬性選擇度量，如信息增益和gini指標。屬性選擇度量是一種選擇分裂準則，將給定的類標記的訓練元組的數(shù)據(jù)劃分d“最好”地分成個體類的啟發(fā)式方法。如果我們要根據(jù)分裂準則的輸出將d劃分成較小的劃分，理想地，每個劃分是“純”的，即，落在給定劃分的所有元組都屬于相同

8、的類。從概念上講，最好的劃分準則是導致最接近這種情況的劃分。本文主要介紹一種流行的屬性選擇度量信息增益。信息增益度量基于claude shannon在研究消息的值或“信息內(nèi)容”的信息論方面的先驅(qū)工作。設(shè)節(jié)點n代表或存放劃分d的元組。選擇具有最高信息增益的屬性作為節(jié)點n的分裂屬性。該屬性使結(jié)果劃分中的元組分類所需的信息量最小，并反映這些劃分中的最小隨機性或“不純性”。這種方法使對給定元組分類所需的期望測試數(shù)目最小，并確保找到一棵簡單的樹。對于d中的元組分類所需的期望信息由下式給出：（1）其中，pi是d中任意元組屬于類ci的概率，并用|ci,d|/|d|估計。使用以2為底的對數(shù)函數(shù)，因為信息用二進

9、位編碼。info(d)是識別d中的元組的類標號所需的平均信息量。這里，我們所具有的信息只是每個類的元組所占的百分比。info(d)又稱d的熵。假設(shè)按屬性a劃分d中的元組，其中屬性a根據(jù)訓練數(shù)據(jù)的觀測具有v個不同值a1,a2,av?？梢杂脤傩詀將d劃分為v個子集d1d2,dv ，其中dj包含d中的元組，它們在a上具有值aj。這些劃分將對應于從節(jié)點n生長出來的分枝。理想地，我們希望該劃分產(chǎn)生元組的準確分類，即，每個劃分都是純的。為了得到準確的分類我們還需要多少信息？這個量由下式度量： （2）項充當?shù)趈個劃分的權(quán)重。是基于按a劃分對d的元組分類所需要的期望信息。所需要的信息越小，劃分的純度越高。信息

10、增益定義為原來的信息需求（即僅基于類比例）與新的需求（即對a劃分之后得到的）之間的差。即是： （3）gain(a)告訴我們通過a的劃分我們得到了多少。選擇具有最高信息增益的屬性作為節(jié)點n的分裂屬性。這等價于按能做“最佳劃分”的屬性a劃分，使得完成元組分類還需要的信息最少。三 id3算法java實現(xiàn)1 實例假定某推銷員根據(jù)經(jīng)驗得知，學生是否會由家長接送，與學生的年齡、性別和家庭收入關(guān)系最大。于是，她收集了某一學校學生由家長接送的信息，得到了表如下的數(shù)據(jù)，這就是她的訓練樣本集，她的目標是建立能夠估學生是否會由家長接送的決策樹。這可以看作一個兩類的分類問題。顧客編號年齡性別月收入是否購買19男400

11、0否211女5000否312女3800否414女2000否58男7000否612女2500否79女2000否88女9000是914男5000是109男7000否1112女4800否126男2800否1312女4500否1412男2800是1514男4000是1615女2500否面對這些數(shù)據(jù)，她無從下手分析。有經(jīng)驗的同事告訴她，應該先把年齡和收入情況分成幾個等級。于是她查閱了有關(guān)資料，決定把年齡以10歲為門檻分成兩檔，把收入按照每月3000元以下、3000-6000元和6000元以上分為低、中、高三檔，這樣，她的數(shù)據(jù)就變成了表如下的形式。接下來的事情就是如何根據(jù)這樣的樣本數(shù)據(jù)構(gòu)造決策樹。顧客編號

12、年齡性別月收入是否購買110女中否310女中否410女低否510女低否710女低否810男中是1010女中否1210男低否1310男低是1510男中是1610女低否這個例子中，每個屬性都是離散值的，連續(xù)的屬性已經(jīng)被離散化。對于表中數(shù)據(jù)，在不考慮任何特征時，16人中有4人需要家長接送，12人不需要家長接送，計算出此時的熵不純度為其中，info(d)表示總共16個樣本中4個為一類，12個為另一類時的熵不純度?，F(xiàn)在希望找到一個能夠最有效地劃分買車與不買車兩類的特征，也就是希望引入該特征后，能夠使不純度最有效地減少。于是，相關(guān)人員逐一考查各個特征，分別計算如果采用年齡、性別或月收入為特征把樣本劃分，劃

13、分后的熵不純度是否會減少，比較哪個特征能夠使不純度減少幅度最大。對年齡特征的計算方法和結(jié)果是：如果采用年齡作為根節(jié)點，則把所有樣本分為兩組，30歲以下組有6人，1人需要家長接送；30歲以上組有10人，3人需要家長接送。總的熵不純度是這兩組樣本上計算的不純度按照樣本比例的加權(quán)求和，即這樣，采用年齡作為根節(jié)點后，在下一級的熵不純度比上一級減少的量是稱作不純度減少量，或信息增益（information gain）。用同樣的方法，相關(guān)人員又分別計算了采用性別特征、月收入特征作為根節(jié)點所能夠帶來的信息增益相關(guān)人員發(fā)現(xiàn)，用性別作為第一個特征能夠帶來不純度最大的減小，于是決定用性別特征作為決策樹的根節(jié)點，如

14、圖(1)所示：所有16個樣本被按照性別特征分成了兩組，女性組有9個樣本，其中1人需要家長接送；男性組有7個樣本，其中3個人不。下面需要構(gòu)建決策樹的下一層節(jié)點。對于女性組合男性組，用上面的相同的方法，分別考查兩組樣本上如果再采用年齡或月收入作為特征所得的不純度減少。結(jié)果發(fā)現(xiàn)，對于男性組，采用年齡特征后不純度減少最大，為0.9852；對于女性組，則是采用月收入作為特征后不純度減少最多，為0.688。這樣就可以分別用這兩個特征構(gòu)建下一級的決策樹節(jié)點。事實上，在這個簡單的例子里，這時各個節(jié)點上已經(jīng)都是純的樣本了，因此這一級節(jié)點就是葉節(jié)點。決策樹構(gòu)建完成，如圖(2)所示。 2 算法的java實現(xiàn)impo

15、rt java包;public class id3 private arraylist attribute = new arraylist(); / 存儲屬性的名稱private arraylistarraylist attributevalue = new arraylistarraylist(); / 存儲每個屬性的取值private arraylist data = new arraylist(); / 原始數(shù)據(jù)int decatt; / 決策變量在屬性集中的索引public static final string patternstring = attribute(.*)(.*?);d

16、ocument xmldoc;element root;public id3() xmldoc = documenthelper.createdocument();root = xmldoc.addelement(root);root.addelement(decisiontree).addattribute(value, null);public static void main(string args) id3 inst = new id3();inst.readarff(new file(d:newprojectweka-3-7-1weka-3-7-1weka-3-7-1dataweat

17、her.nominal.arff);inst.setdec(play);linkedlist ll = new linkedlist();for (int i = 0; i inst.attribute.size(); i+) if (i != inst.decatt)ll.add(i);arraylist al = new arraylist();for (int i = 0; i inst.data.size(); i+) al.add(i);inst.builddt(decisiontree, null, al, ll);inst.writexml(d:newprojecttestwea

18、ther.xml);return;/ 讀取arff文件，給attribute、attributevalue、data賦值public void readarff(file file) try filereader fr = new filereader(file);bufferedreader br = new bufferedreader(fr);string line;pattern pattern = ppile(patternstring);while (line = br.readline() != null) matcher matcher = pattern.matcher(li

19、ne);if (matcher.find() attribute.add(matcher.group(1).trim();string values = matcher.group(2).split(,);arraylist al = new arraylist(values.length);for (string value : values) al.add(value.trim();attributevalue.add(al); else if (line.startswith(data) while (line = br.readline() != null) if (line = )c

20、ontinue;string row = line.split(,);data.add(row); else continue;br.close(); catch (ioexception e1) e1.printstacktrace();/ 設(shè)置決策變量public void setdec(int n) if (n = attribute.size() system.err.println(決策變量指定錯誤。);system.exit(2);decatt = n;public void setdec(string name) int n = attribute.indexof(name);s

21、etdec(n);/ 給一個樣本（數(shù)組中是各種情況的計數(shù)），計算它的熵public double getentropy(int arr) double entropy = 0.0;int sum = 0;for (int i = 0; i arr.length; i+) entropy -= arri * math.log(arri + double.min_value)/ math.log(2);sum += arri;entropy += sum * math.log(sum + double.min_value) / math.log(2);entropy /= sum;return e

22、ntropy;public boolean infopure(arraylist subset) string value = data.get(subset.get(0)decatt;for (int i = 1; i subset.size(); i+) string next = data.get(subset.get(i)decatt;/ equals表示對象內(nèi)容相同，=表示兩個對象指向的是同一片內(nèi)存if (!value.equals(next)return false;return true;/ 給定原始數(shù)據(jù)的子集(subset中存儲行號),當以第index個屬性為節(jié)點時計算它的信息

23、熵public double calnodeentropy(arraylist subset, int index) int sum = subset.size();double entropy = 0.0;int info = new intattributevalue.get(index).size();for (int i = 0; i info.length; i+)infoi = new intattributevalue.get(decatt).size();int count = new intattributevalue.get(index).size();for (int i

24、 = 0; i sum; i+) int n = subset.get(i);string nodevalue = data.get(n)index;int nodeind = attributevalue.get(index).indexof(nodevalue);countnodeind+;string decvalue = data.get(n)decatt;int decind = attributevalue.get(decatt).indexof(decvalue);infonodeinddecind+;for (int i = 0; i info.length; i+) entr

25、opy += getentropy(infoi) * counti / sum;return entropy;/ 構(gòu)建決策樹public void builddt(string name, string value, arraylist subset,linkedlist selatt) element ele = null;suppresswarnings(unchecked)list list = root.selectnodes(/ + name);iterator iter = list.iterator();while (iter.hasnext() ele = iter.next(

26、);if (ele.attributevalue(value).equals(value)break;if (infopure(subset) ele.settext(data.get(subset.get(0)decatt);return;int minindex = -1;double minentropy = double.max_value;for (int i = 0; i selatt.size(); i+) if (i = decatt)continue;double entropy = calnodeentropy(subset, selatt.get(i);if (entro

27、py minentropy) minindex = selatt.get(i);minentropy = entropy;string nodename = attribute.get(minindex);selatt.remove(new integer(minindex);arraylist attvalues = attributevalue.get(minindex);for (string val : attvalues) ele.addelement(nodename).addattribute(value, val);arraylist al = new arraylist();

28、for (int i = 0; i subset.size(); i+) if (data.get(subset.get(i)minindex.equals(val) al.add(subset.get(i);builddt(nodename, val, al, selatt);/ 把xml寫入文件public void writexml(string filename) try file file = new file(filename);if (!file.exists()file.createnewfile();filewriter fw = new filewriter(file);outputformat format = outputformat.createprettyprint(); / 美化格式xmlwriter output = new xmlwriter(fw, format);output.write(xmldoc);output.close(); catch (ioexception e) system.out.println(e.getmessage();四 id3算法性能分析1 優(yōu)勢搜索空間是完全的假設(shè)空間，目標函數(shù)必在搜索空間中，不存在無解的危險；全盤使用訓練數(shù)據(jù)，而不是像候選剪除算法一個一個地考慮訓練