/*先把標題給寫了，這樣就能經常提醒自己*/
決策樹是一種容易理解的分類算法，它可以認為是if-then規則的一個集合。主要的優點是模型具有可讀性，且分類速度較快，不用進行過多的迭代訓練之類。決策樹學習通常包括3個步驟：特征選擇、決策樹的生成和決策樹的修剪。比較常用到的算法有ID3、C4.5和CART。
1. 決策樹模型
決策樹是一種樹形結構的分類模型，它由結點和有向邊組成，結點分為內部結點和葉結點，內部結點表示一個特征或屬性，葉結點表示一個類。
決策樹的分類即是從樹的根節點開始對實例的某一個特征進行判斷，通過內部結點逐步下潛到葉結點的過程。
2. 特征選擇
特征選擇在于選取對訓練數據具有分類能力的特征，通常的選擇準則是信息增益或信息增益率。為了便于說明，書中給出了一個例子
希望通過所給的訓練數據學習一個貸款申請的決策樹，當新客戶提出貸款申請時，根據申請人的特征決定是否可貸。
????? 從認知上個人覺得特征的選擇就是找出一些具有代表性，對于分類辨識度高的特征，如此能夠快速準確的為實例分類，從數學的角度上來講，就要涉及到信息論與概率統計中的熵了。在此不贅述太多，直接給出特征選擇的算法（信息增益）。
????? 輸入：訓練數據集D和特征A；
????? 輸出：特征A對訓練數據集D的信息增益
和增益率
?
（1）?? 計算數據集D的經驗熵
?
（2）?? 計算特征A的經驗條件熵
?
（3）?? 計算信息增益
?
（4）?? 信息增益率
?
????? 對于書中的例子，首先計算經驗熵
?
然后計算各特征的信息增益，分別以
表示年齡、有工作、有房子和信貸情況4個特征，則
?
?
分別計算
的信息增益，由于
的信息增益值最大，則選擇其為最優特征，當然也可以計算出信息增益率的結果作為選擇的依據。
3. 決策樹的生成
ID3和C4.5算法基本上一樣，只是在特征選擇的依據上C4.5采用了改進后的信息增益率。因為本文只介紹其中的ID3算法即可。?
ID3算法步驟
輸入：訓練數據集D，特征集A，閾值e
輸出：決策樹T
（1）?? 若D中所有實例屬于同一類Ck，則T為單結點樹，并將類Ck作為該結點的類標記，返回T；
（2）?? 若A=空，則T為單結點樹，將D中實例數最多的類Ck作為結點類標記，返回T；
（3）?? 否則，計算A中各特征對D的信息增益，選擇信息增益值最大的特征Ag；
（4）?? 如果Ag的信息增益小于閾值e，則T為單結點樹，將D中最多的類Ck作為結點類標記，返回T；
（5）?? 否則，對Ag的每一可能值ai，依Ag=ai將D分割為若干子集Di，將Di中實例數最大多的類作為類標記，構建子結點，由結點及其子結點構成樹T，返回T；
（6）?? 對于第i個子結點，以Di為訓練集，以A-Ag為特征集，遞歸調用步驟（1）~（5），得到子樹Ti，返回Ti。
?
從描述上感覺決策樹的生成還是挺簡單明了的，但是具體的實現上樹的生成是最最難的，要注意的細節很多，花了倆個晚上才搞好的，遇到了好多坑
代碼塊1：信息增益類
package
org.juefan.decisiontree;
import
java.util.ArrayList;
import
java.util.HashMap;
import
java.util.Map;
import
org.juefan.basic.FileIO;
import
org.juefan.bayes.Data;
public
class
InfoGain {
//
數據實例存儲類
class
Data {
public
ArrayList<Object>
x;
public
Object y;
/**
讀取一行數據轉化為標準格式
*/
public
Data(String content){
String[] strings
= content.split("\t| |:"
);
ArrayList
<Object> xList =
new
ArrayList<Object>
();
for
(
int
i = 1; i < strings.length; i++
){
xList.add(strings[i]);
}
this
.x =
new
ArrayList<>
();
this
.x =
xList;
this
.y = strings[0
];
}
public
Data(){
x
=
new
ArrayList<>
();
y
= 0
;
}
public
String toString(){
StringBuilder builder
=
new
StringBuilder();
builder.append(
"[ "
);
for
(
int
i = 0; i < x.size() - 1; i++
)
builder.append(x.get(i).toString()).append(
","
);
builder.append(x.get(x.size()
- 1
).toString());
builder.append(
" ]"
);
return
builder.toString();
}
}
//
返回底數為2的對數值
public
static
double
log2(
double
d){
return
Math.log(d)/Math.log(2
);
}
/**
* 計算經驗熵
*
@param
datas 當前數據集，可以為訓練數據集中的子集
*
@return
返回當前數據集的經驗熵
*/
public
double
getEntropy(ArrayList<Data>
datas){
int
counts =
datas.size();
double
entropy = 0
;
Map
<Object, Double> map =
new
HashMap<Object, Double>
();
for
(Data data: datas){
if
(map.containsKey(data.y)){
map.put(data.y, map.get(data.y)
+ 1
);
}
else
{
map.put(data.y, 1D);
}
}
for
(
double
v: map.values())
entropy
-= (v/counts * log2(v/
counts));
return
entropy;
}
/**
* 計算條件熵
*
@param
datas 當前數據集，可以為訓練數據集中的子集
*
@param
feature 待計算的特征位置
*
@return
第feature個特征的條件熵
*/
public
double
getCondiEntropy(ArrayList<Data> datas,
int
feature){
int
counts =
datas.size();
double
condiEntropy = 0
;
Map
<Object, ArrayList<Data>> tmMap =
new
HashMap<>
();
for
(Data data: datas){
if
(tmMap.containsKey(data.x.get(feature))){
tmMap.get(data.x.get(feature)).add(data);
}
else
{
ArrayList
<Data> tmDatas =
new
ArrayList<>
();
tmDatas.add(data);
tmMap.put(data.x.get(feature), tmDatas);
}
}
for
(ArrayList<Data>
datas2: tmMap.values()){
condiEntropy
+= (
double
)datas2.size()/counts *
getEntropy(datas2);
}
return
condiEntropy;
}
/**
* 計算信息增益（ID3算法）
*
@param
datas 當前數據集，可以為訓練數據集中的子集
*
@param
feature 待計算的特征位置
*
@return
第feature個特征的信息增益
*/
public
double
getInfoGain(ArrayList<Data> datas,
int
feature){
return
getEntropy(datas) -
getCondiEntropy(datas, feature);
}
/**
* 計算信息增益率（C4.5算法）
*
@param
datas 當前數據集，可以為訓練數據集中的子集
*
@param
feature 待計算的特征位置
*
@return
第feature個特征的信息增益率
*/
public
double
getInfoGainRatio(ArrayList<Data> datas,
int
feature){
return
getInfoGain(datas, feature)/
getEntropy(datas);
}
}
代碼塊2：決策樹類
package
org.juefan.decisiontree;
import
java.util.ArrayList;
import
java.util.List;
public
class
TreeNode {
private
String feature; //候選特征
private
List<TreeNode>
childTreeNode;
private
String targetFunValue; //特征對應的值
private
String nodeName; //分類的類別
public
TreeNode(String nodeName){
this
.nodeName =
nodeName;
this
.childTreeNode =
new
ArrayList<TreeNode>
();
}
public
TreeNode(){
this
.childTreeNode =
new
ArrayList<TreeNode>
();
}
public
void
printTree(){
if
(targetFunValue !=
null
)
System.out.print(
"特征值: " + targetFunValue + "\t"
);
if
(nodeName !=
null
)
System.out.print(
"類型: " + nodeName + "\t"
);
System.out.println();
for
(TreeNode treeNode: childTreeNode){
System.out.println(
"當前特征為：" +
feature);
treeNode.printTree();
}
}
public
String getAttributeValue() {
return
feature;
}
public
void
setAttributeValue(String attributeValue) {
this
.feature =
attributeValue;
}
public
List<TreeNode>
getChildTreeNode() {
return
childTreeNode;
}
public
void
setChildTreeNode(List<TreeNode>
childTreeNode) {
this
.childTreeNode =
childTreeNode;
}
public
String getTargetFunValue() {
return
targetFunValue;
}
public
void
setTargetFunValue(String targetFunValue) {
this
.targetFunValue =
targetFunValue;
}
public
String getNodeName() {
return
nodeName;
}
public
void
setNodeName(String nodeName) {
this
.nodeName =
nodeName;
}
}
代碼塊3：決策樹的生成
package
org.juefan.decisiontree;
import
java.util.ArrayList;
import
java.util.HashMap;
import
java.util.HashSet;
import
java.util.List;
import
java.util.Map;
import
java.util.Set;
import
org.juefan.basic.FileIO;
import
org.juefan.bayes.Data;
public
class
DecisionTree {
public
static
final
double
e = 0.1
;
public
InfoGain infoGain =
new
InfoGain();
public
TreeNode buildTree(ArrayList<Data> datas, ArrayList<String>
featureName){
TreeNode treeNode
=
new
TreeNode();
ArrayList
<String> feaName =
new
ArrayList<>
();
feaName
=
featureName;
if
(isSingle(datas) || getMaxInfoGain(datas) <
e){
treeNode.setNodeName(getLabel(datas).toString());
return
treeNode;
}
else
{
int
feature =
getMaxInfoGainFeature(datas);
treeNode.setAttributeValue(feaName.get(feature
+ 1
));
ArrayList
<String> tList =
new
ArrayList<>
();
tList
=
feaName;
Map
<Object, ArrayList<Data>> tMap =
new
HashMap<>
();
for
(Data data: datas){
if
(tMap.containsKey(data.x.get(feature))){
Data tData
=
new
Data();
for
(
int
i = 0; i < data.x.size(); i++
)
if
(i !=
feature)
tData.x.add(data.x.get(i));
tData.y
=
data.y;
tMap.get(data.x.get(feature)).add(tData);
}
else
{
Data tData
=
new
Data();
for
(
int
i = 0; i < data.x.size(); i++
)
if
(i !=
feature)
tData.x.add(data.x.get(i));
tData.y
=
data.y;
ArrayList
<Data> tDatas =
new
ArrayList<>
();
tDatas.add(tData);
tMap.put(data.x.get(feature),tDatas);
}
}
List
<TreeNode> treeNodes =
new
ArrayList<>
();
int
child = 0
;
for
(Object key: tMap.keySet()){
//
這一步太坑爹了，java的拷背坑真多啊，害我浪費了半天的時間
ArrayList<String> tList2 =
new
ArrayList<>
(tList);
tList2.remove(feature
+ 1
);
treeNodes.add(buildTree(tMap.get(key), tList2));
treeNodes.get(child
++
).setTargetFunValue(key.toString());
}
treeNode.setChildTreeNode(treeNodes);
feaName.remove(feature
+ 1
);
}
return
treeNode;
}
/**
* 獲取實例中的最大類
*
@param
datas 實例集
*
@return
出現次數最多的類
*/
public
Object getLabel(ArrayList<Data>
datas){
Map
<Object, Integer> map =
new
HashMap<Object, Integer>
();
Object label
=
null
;
int
max = 0
;
for
(Data data: datas){
if
(map.containsKey(data.y)){
map.put(data.y, map.get(data.y)
+ 1
);
if
(map.get(data.y) >
max){
max
=
map.get(data.y);
label
=
data.y;
}
}
else
{
map.put(data.y,
1
);
}
}
return
label;
}
/**
* 計算信息增益（率）的最大值
*
@param
datas
*
@return
最大的信息增益值
*/
public
double
getMaxInfoGain(ArrayList<Data>
datas){
double
max = 0
;
for
(
int
i = 0; i < datas.get(0).x.size(); i++
){
double
temp =
infoGain.getInfoGain(datas, i);
if
(temp >
max)
max
=
temp;
}
return
max;
}
/**
信息增益最大的特征
*/
public
int
getMaxInfoGainFeature(ArrayList<Data>
datas){
double
max = 0
;
int
feature = 0
;
for
(
int
i = 0; i < datas.get(0).x.size(); i++
){
double
temp =
infoGain.getInfoGain(datas, i);
if
(temp >
max){
max
=
temp;
feature
=
i;
}
}
return
feature;
}
/**
判斷是否只有一類
*/
public
boolean
isSingle(ArrayList<Data>
datas){
Set
<Object> set =
new
HashSet<>
();
for
(Data data: datas)
set.add(data.y);
return
set.size() == 1?
true
:
false
;
}
public
static
void
main(String[] args) {
ArrayList
<Data> datas =
new
ArrayList<>
();
FileIO fileIO
=
new
FileIO();
DecisionTree decisionTree
=
new
DecisionTree();
fileIO.setFileName(
".//file//decision.tree.txt"
);
fileIO.FileRead(
"utf-8"
);
ArrayList
<String> featureName =
new
ArrayList<>
();
//
獲取文件的標頭
for
(String string: fileIO.fileList.get(0).split("\t"
))
featureName.add(string);
for
(
int
i = 1; i < fileIO.fileList.size(); i++
){
datas.add(
new
Data(fileIO.fileList.get(i)));
}
TreeNode treeNode
=
new
TreeNode();
treeNode
=
decisionTree.buildTree(datas, featureName);
treeNode.printTree();
}
}
?運行情況：
輸入文件?".//file//decision.tree.txt" 內容為:
類型 年齡 有工作 有自己的房子 信貸情況
否 青年 否 否 一般
否 青年 否 否 好
是 青年 是 否 好
是 青年 是 是 一般
否 青年 否 否 一般
否 中年 否 否 一般
否 中年 否 否 好
是 中年 是 是 好
是 中年 否 是 非常好
是 中年 否 是 非常好
是 老年 否 是 非常好
是 老年 否 是 好
是 老年 是 否 好
是 老年 是 否 非常好
否 老年 否 否 一般
運行結果為：
當前特征為：有自己的房子
特征值: 是 類型: 是
當前特征為：有自己的房子
特征值: 否
當前特征為：有工作
特征值: 是 類型: 是
當前特征為：有工作
特征值: 否 類型: 否
對代碼有興趣的可以上本人的GitHub查看： https://github.com/JueFan/StatisticsLearningMethod/
里面也有具體的實例數據
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
