决策树案例理解
小王是一家著名高爾夫俱樂部的經理。但是他被雇員數量問題搞得心情十分不好。某些天好像所有人都來玩高爾夫，以至于所有員工都忙的團團轉還是應付不過來，而有些天不知道什么原因卻一個人也不來，俱樂部為雇員數量浪費了不少資金。
小王的目的是通過下周天氣預報尋找什么時候人們會打高爾夫，以適時調整雇員數量。因此首先他必須了解人們決定是否打球的原因。
在2周時間內我們得到以下記錄:
天氣狀況有晴，云和雨；氣溫用華氏溫度表示；相對濕度用百分比；還有有無風。當然還有顧客是不是在這些日子光顧俱樂部。最終他得到了14列5行的數據表格。
決策樹模型就被建起來用于解決問題。
決策樹是一個有向無環圖。根結點代表所有數據。分類樹算法可以通過變量outlook，找出最好地解釋非獨立變量play（打高爾夫的人）的方法。變量outlook的范疇被劃分為以下三個組：
晴天，多云天和雨天。
我們得出第一個結論: 如果天氣是多云，人們總是選擇玩高爾夫，而只有少數很著迷的甚至在雨天也會玩。
接下來我們把晴天組的分為兩部分，我們發現顧客不喜歡濕度高于70%的天氣。最終我們還發現，如果雨天還有風的話，就不會有人打了。
這就通過分類樹給出了一個解決方案。 David（老板）在晴天，潮濕的天氣或者刮風的雨天解雇了大部分員工，因為這種天氣不會有人打高爾夫。而其他的天氣會有很多人打高爾夫，因此可以雇用一些臨時員工來工作。
結論是決策樹幫助我們把復雜的數據表示轉換成相對簡單的直觀的結構。
公式
熵
算法ID3?,?C4.5?和C5.0生成樹算法使用熵。這一度量是給予信息學理論中熵的概念。
相對于其他數據挖掘算法，決策樹在以下幾個方面擁有優勢：
- 決策樹易于理解和實現.?人們在通過解釋后都有能力去理解決策樹所表達的意義。
- 對于決策樹，數據的準備往往是簡單或者是不必要的 .?其他的技術往往要求先把數據一般化，比如去掉多余的或者空白的屬性。
- 能夠同時處理數據型和常規型屬性。?其他的技術往往要求數據屬性的單一。
- 是一個白盒模型?如果給定一個觀察的模型，那么根據所產生的決策樹很容易推出相應的邏輯表達式。
- 易于通過靜態測試來對模型進行評測。?表示有可能測量該模型的可信度。
- 在相對短的時間內能夠對大型數據源做出可行且效果良好的結果。
由決策樹擴展為決策圖
在決策樹中所有從根到葉節點的路徑都是通過“與”（AND）運算連接。在決策圖中可以使用“或”來連接多于一個的路徑。
決策樹算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納算法生成可讀的規則和決策樹，然后使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用于數據分析處理的數據集。第二步，決策樹的剪枝：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡準確性的分枝剪除。
java實現代碼如下：
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 | packagedemo; importjava.util.HashMap; importjava.util.LinkedList; importjava.util.List; importjava.util.Map; importjava.util.Map.Entry; importjava.util.Set; publicclass DicisionTree { ??publicstatic void main(String[] args) throwsException { ????System.out.print("腳本之家測試結果："); ????String[] attrNames = newString[] { "AGE","INCOME","STUDENT", ????????"CREDIT_RATING"}; ????// 讀取樣本集 ????Map<Object, List<Sample>> samples = readSamples(attrNames); ????// 生成決策樹 ????Object decisionTree = generateDecisionTree(samples, attrNames); ????// 輸出決策樹 ????outputDecisionTree(decisionTree,0,null); ??} ??/** ???* 讀取已分類的樣本集，返回Map：分類 -> 屬于該分類的樣本的列表 ???*/ ??staticMap<Object, List<Sample>> readSamples(String[] attrNames) { ????// 樣本屬性及其所屬分類（數組中的最后一個元素為樣本所屬分類） ????Object[][] rawData = newObject[][] { ????????{"<30 ","High ","No ","Fair?? ","0"}, ????????{"<30 ","High ","No ","Excellent","0"}, ????????{"30-40","High ","No ","Fair?? ","1"}, ????????{">40 ","Medium","No ","Fair?? ","1"}, ????????{">40 ","Low? ","Yes","Fair?? ","1"}, ????????{">40 ","Low? ","Yes","Excellent","0"}, ????????{"30-40","Low? ","Yes","Excellent","1"}, ????????{"<30 ","Medium","No ","Fair?? ","0"}, ????????{"<30 ","Low? ","Yes","Fair?? ","1"}, ????????{">40 ","Medium","Yes","Fair?? ","1"}, ????????{"<30 ","Medium","Yes","Excellent","1"}, ????????{"30-40","Medium","No ","Excellent","1"}, ????????{"30-40","High ","Yes","Fair?? ","1"}, ????????{">40 ","Medium","No ","Excellent","0"} }; ????// 讀取樣本屬性及其所屬分類，構造表示樣本的Sample對象，并按分類劃分樣本集 ????Map<Object, List<Sample>> ret = newHashMap<Object, List<Sample>>(); ????for(Object[] row : rawData) { ??????Sample sample = newSample(); ??????inti = 0; ??????for(intn = row.length - 1; i < n; i++) ????????sample.setAttribute(attrNames[i], row[i]); ??????sample.setCategory(row[i]); ??????List<Sample> samples = ret.get(row[i]); ??????if(samples == null) { ????????samples = newLinkedList<Sample>(); ????????ret.put(row[i], samples); ??????} ??????samples.add(sample); ????} ????returnret; ??} ??/** ???* 構造決策樹 ???*/ ??staticObject generateDecisionTree( ??????Map<Object, List<Sample>> categoryToSamples, String[] attrNames) { ????// 如果只有一個樣本，將該樣本所屬分類作為新樣本的分類 ????if(categoryToSamples.size() == 1) ??????returncategoryToSamples.keySet().iterator().next(); ????// 如果沒有供決策的屬性，則將樣本集中具有最多樣本的分類作為新樣本的分類，即投票選舉出分類 ????if(attrNames.length == 0) { ??????intmax = 0; ??????Object maxCategory = null; ??????for(Entry<Object, List<Sample>> entry : categoryToSamples ??????????.entrySet()) { ????????intcur = entry.getValue().size(); ????????if(cur > max) { ??????????max = cur; ??????????maxCategory = entry.getKey(); ????????} ??????} ??????returnmaxCategory; ????} ????// 選取測試屬性 ????Object[] rst = chooseBestTestAttribute(categoryToSamples, attrNames); ????// 決策樹根結點，分支屬性為選取的測試屬性 ????Tree tree = newTree(attrNames[(Integer) rst[0]]); ????// 已用過的測試屬性不應再次被選為測試屬性 ????String[] subA = newString[attrNames.length - 1]; ????for(inti = 0, j = 0; i < attrNames.length; i++) ??????if(i != (Integer) rst[0]) ????????subA[j++] = attrNames[i]; ????// 根據分支屬性生成分支 ????@SuppressWarnings("unchecked") ????Map<Object, Map<Object, List<Sample>>> splits = ????/* NEW LINE */(Map<Object, Map<Object, List<Sample>>>) rst[2]; ????for (Entry<Object, Map<Object, List<Sample>>> entry : splits.entrySet()) { ??????Object attrValue = entry.getKey(); ??????Map<Object, List<Sample>> split = entry.getValue(); ??????Object child = generateDecisionTree(split, subA); ??????tree.setChild(attrValue, child); ????} ????return tree; ??} ??/** ???* 選取最優測試屬性。最優是指如果根據選取的測試屬性分支，則從各分支確定新樣本 ???* 的分類需要的信息量之和最小，這等價于確定新樣本的測試屬性獲得的信息增益最大 ???* 返回數組：選取的屬性下標、信息量之和、Map(屬性值->(分類->樣本列表)) ???*/ ??static Object[] chooseBestTestAttribute( ??????Map<Object, List<Sample>> categoryToSamples, String[] attrNames) { ????int minIndex = -1; // 最優屬性下標 ????double minValue = Double.MAX_VALUE; // 最小信息量 ????Map<Object, Map<Object, List<Sample>>> minSplits = null; // 最優分支方案 ????// 對每一個屬性，計算將其作為測試屬性的情況下在各分支確定新樣本的分類需要的信息量之和，選取最小為最優 ????for (int attrIndex = 0; attrIndex < attrNames.length; attrIndex++) { ??????int allCount = 0; // 統計樣本總數的計數器 ??????// 按當前屬性構建Map：屬性值->(分類->樣本列表) ??????Map<Object, Map<Object, List<Sample>>> curSplits = ??????/* NEW LINE */new HashMap<Object, Map<Object, List<Sample>>>(); ??????for (Entry<Object, List<Sample>> entry : categoryToSamples ??????????.entrySet()) { ????????Object category = entry.getKey(); ????????List<Sample> samples = entry.getValue(); ????????for (Sample sample : samples) { ??????????Object attrValue = sample ??????????????.getAttribute(attrNames[attrIndex]); ??????????Map<Object, List<Sample>> split = curSplits.get(attrValue); ??????????if (split == null) { ????????????split = new HashMap<Object, List<Sample>>(); ????????????curSplits.put(attrValue, split); ??????????} ??????????List<Sample> splitSamples = split.get(category); ??????????if (splitSamples == null) { ????????????splitSamples = new LinkedList<Sample>(); ????????????split.put(category, splitSamples); ??????????} ??????????splitSamples.add(sample); ????????} ????????allCount += samples.size(); ??????} ??????// 計算將當前屬性作為測試屬性的情況下在各分支確定新樣本的分類需要的信息量之和 ??????double curValue = 0.0; // 計數器：累加各分支 ??????for (Map<Object, List<Sample>> splits : curSplits.values()) { ????????double perSplitCount = 0; ????????for (List<Sample> list : splits.values()) ??????????perSplitCount += list.size(); // 累計當前分支樣本數 ????????double perSplitValue = 0.0; // 計數器：當前分支 ????????for (List<Sample> list : splits.values()) { ??????????double p = list.size() / perSplitCount; ??????????perSplitValue -= p * (Math.log(p) / Math.log(2)); ????????} ????????curValue += (perSplitCount / allCount) * perSplitValue; ??????} ??????// 選取最小為最優 ??????if (minValue > curValue) { ????????minIndex = attrIndex; ????????minValue = curValue; ????????minSplits = curSplits; ??????} ????} ????return new Object[] { minIndex, minValue, minSplits }; ??} ??/** ???* 將決策樹輸出到標準輸出 ???*/ ??static void outputDecisionTree(Object obj, int level, Object from) { ????for (int i = 0; i < level; i++) ??????System.out.print("|-----"); ????if (from != null) ??????System.out.printf("(%s):", from); ????if (obj instanceof Tree) { ??????Tree tree = (Tree) obj; ??????String attrName = tree.getAttribute(); ??????System.out.printf("[%s = ?]\n", attrName); ??????for (Object attrValue : tree.getAttributeValues()) { ????????Object child = tree.getChild(attrValue); ????????outputDecisionTree(child, level + 1, attrName + " = " ????????????+ attrValue); ??????} ????} else { ??????System.out.printf("[CATEGORY = %s]\n", obj); ????} ??} ??/** ???* 樣本，包含多個屬性和一個指明樣本所屬分類的分類值 ???*/ ??static class Sample { ????private Map<String, Object> attributes = new HashMap<String, Object>(); ????private Object category; ????public Object getAttribute(String name) { ??????return attributes.get(name); ????} ????public void setAttribute(String name, Object value) { ??????attributes.put(name, value); ????} ????public Object getCategory() { ??????return category; ????} ????public void setCategory(Object category) { ??????this.category = category; ????} ????public String toString() { ??????return attributes.toString(); ????} ??} ??/** ???* 決策樹（非葉結點），決策樹中的每個非葉結點都引導了一棵決策樹 ???* 每個非葉結點包含一個分支屬性和多個分支，分支屬性的每個值對應一個分支，該分支引導了一棵子決策樹 ???*/ ??staticclass Tree { ????privateString attribute; ????privateMap<Object, Object> children = newHashMap<Object, Object>(); ????publicTree(String attribute) { ??????this.attribute = attribute; ????} ????publicString getAttribute() { ??????returnattribute; ????} ????publicObject getChild(Object attrValue) { ??????returnchildren.get(attrValue); ????} ????publicvoid setChild(Object attrValue, Object child) { ??????children.put(attrValue, child); ????} ????publicSet<Object> getAttributeValues() { ??????returnchildren.keySet(); ????} ??} } |
運行結果：
總結
- 上一篇： SVM分类算法的基本理论问题
- 下一篇： 聚类、K-Means、例子、细节