決策分類樹算法之ID3，C4.5算法系列
一、引言
在最開始的時候，我本來準備學習的是C4.5算法，后來發現C4.5算法的核心還是ID3算法，所以又輾轉回到學習ID3算法了，因為C4.5是他的一個改進。至于是什么改進，在后面的描述中我會提到。
二、ID3算法
ID3算法是一種分類決策樹算法。他通過一系列的規則，將數據最后分類成決策樹的形式。分類的根據是用到了熵這個概念。熵在物理這門學科中就已經出現過，表示是一個物質的穩定度，在這里就是分類的純度的一個概念。公式為：
在ID3算法中，是采用Gain信息增益來作為一個分類的判定標準的。他的定義為：
每次選擇屬性中信息增益最大作為劃分屬性，在這里本人實現了一個java版本的ID3算法，為了模擬數據的可操作性，就把數據寫到一個input.txt文件中，作為數據源，格式如下：
[java] view plaincopyprint?
-
Day OutLook Temperature Humidity Wind PlayTennis
-
1 Sunny Hot High Weak No
-
2 Sunny Hot High Strong No
-
3 Overcast Hot High Weak Yes
-
4 Rainy Mild High Weak Yes
-
5 Rainy Cool Normal Weak Yes
-
6 Rainy Cool Normal Strong No
-
7 Overcast Cool Normal Strong Yes
-
8 Sunny Mild High Weak No
-
9 Sunny Cool Normal Weak Yes
-
10 Rainy Mild Normal Weak Yes
-
11 Sunny Mild Normal Strong Yes
-
12 Overcast Mild High Strong Yes
-
13 Overcast Hot Normal Weak Yes
-
14 Rainy Mild High Strong No
PalyTennis屬性為結構屬性，是作為類標識用的，中間的OutLool,Temperature,Humidity,Wind才是劃分屬性，通過將源數據與執行程序分類，這樣可以模擬巨大的數據量了。下面是ID3的主程序類，本人將ID3的算法進行了包裝，對外只開放了一個構建決策樹的方法，在構造函數時候，只需傳入一個數據路徑文件即可：
[java] view plaincopyprint?
-
package DataMing_ID3;
-
-
import java.io.BufferedReader;
-
import java.io.File;
-
import java.io.FileReader;
-
import java.io.IOException;
-
import java.util.ArrayList;
-
import java.util.HashMap;
-
import java.util.Iterator;
-
import java.util.Map;
-
import java.util.Map.Entry;
-
import java.util.Set;
-
-
/**
-
* ID3算法實現類
-
*
-
* @author lyq
-
*
-
*/
-
public class ID3Tool {
-
// 類標號的值類型
-
private final String YES = "Yes";
-
private final String NO = "No";
-
-
// 所有屬性的類型總數,在這里就是data源數據的列數
-
private int attrNum;
-
private String filePath;
-
// 初始源數據，用一個二維字符數組存放模仿表格數據
-
private String[][] data;
-
// 數據的屬性行的名字
-
private String[] attrNames;
-
// 每個屬性的值所有類型
-
private HashMap<String, ArrayList<String>> attrValue;
-
-
public ID3Tool(String filePath) {
-
this.filePath = filePath;
-
attrValue = new HashMap<>();
-
}
-
-
/**
-
* 從文件中讀取數據
-
*/
-
private void readDataFile() {
-
File file = new File(filePath);
-
ArrayList<String[]> dataArray = new ArrayList<String[]>();
-
-
try {
-
BufferedReader in = new BufferedReader(new FileReader(file));
-
String str;
-
String[] tempArray;
-
while ((str = in.readLine()) != null) {
-
tempArray = str.split(" ");
-
dataArray.add(tempArray);
-
}
-
in.close();
-
} catch (IOException e) {
-
e.getStackTrace();
-
}
-
-
data = new String[dataArray.size()][];
-
dataArray.toArray(data);
-
attrNum = data[0].length;
-
attrNames = data[0];
-
-
/*
-
* for(int i=0; i<data.length;i++){ for(int j=0; j<data[0].length; j++){
-
* System.out.print(" " + data[i][j]); }
-
*
-
* System.out.print("\n"); }
-
*/
-
}
-
-
/**
-
* 首先初始化每種屬性的值的所有類型，用于后面的子類熵的計算時用
-
*/
-
private void initAttrValue() {
-
ArrayList<String> tempValues;
-
-
// 按照列的方式，從左往右找
-
for (int j = 1; j < attrNum; j++) {
-
// 從一列中的上往下開始尋找值
-
tempValues = new ArrayList<>();
-
for (int i = 1; i < data.length; i++) {
-
if (!tempValues.contains(data[i][j])) {
-
// 如果這個屬性的值沒有添加過，則添加
-
tempValues.add(data[i][j]);
-
}
-
}
-
-
// 一列屬性的值已經遍歷完畢，復制到map屬性表中
-
attrValue.put(data[0][j], tempValues);
-
}
-
-
/*
-
* for(Map.Entry entry : attrValue.entrySet()){
-
* System.out.println("key:value " + entry.getKey() + ":" +
-
* entry.getValue()); }
-
*/
-
}
-
-
/**
-
* 計算數據按照不同方式劃分的熵
-
*
-
* @param remainData
-
* 剩余的數據
-
* @param attrName
-
* 待劃分的屬性，在算信息增益的時候會使用到
-
* @param attrValue
-
* 劃分的子屬性值
-
* @param isParent
-
* 是否分子屬性劃分還是原來不變的劃分
-
*/
-
private double computeEntropy(String[][] remainData, String attrName,
-
String value, boolean isParent) {
-
// 實例總數
-
int total = 0;
-
// 正實例數
-
int posNum = 0;
-
// 負實例數
-
int negNum = 0;
-
-
// 還是按列從左往右遍歷屬性
-
for (int j = 1; j < attrNames.length; j++) {
-
// 找到了指定的屬性
-
if (attrName.equals(attrNames[j])) {
-
for (int i = 1; i < remainData.length; i++) {
-
// 如果是父結點直接計算熵或者是通過子屬性劃分計算熵，這時要進行屬性值的過濾
-
if (isParent
-
|| (!isParent && remainData[i][j].equals(value))) {
-
if (remainData[i][attrNames.length - 1].equals(YES)) {
-
// 判斷此行數據是否為正實例
-
posNum++;
-
} else {
-
negNum++;
-
}
-
}
-
}
-
}
-
}
-
-
total = posNum + negNum;
-
double posProbobly = (double) posNum / total;
-
double negProbobly = (double) negNum / total;
-
-
if (posProbobly == 1 || posProbobly == 0) {
-
// 如果數據全為同種類型，則熵為0，否則帶入下面的公式會報錯
-
return 0;
-
}
-
-
double entropyValue = -posProbobly * Math.log(posProbobly)
-
/ Math.log(2.0) - negProbobly * Math.log(negProbobly)
-
/ Math.log(2.0);
-
-
// 返回計算所得熵
-
return entropyValue;
-
}
-
-
/**
-
* 為某個屬性計算信息增益
-
*
-
* @param remainData
-
* 剩余的數據
-
* @param value
-
* 待劃分的屬性名稱
-
* @return
-
*/
-
private double computeGain(String[][] remainData, String value) {
-
double gainValue = 0;
-
// 源熵的大小將會與屬性劃分后進行比較
-
double entropyOri = 0;
-
// 子劃分熵和
-
double childEntropySum = 0;
-
// 屬性子類型的個數
-
int childValueNum = 0;
-
// 屬性值的種數
-
ArrayList<String> attrTypes = attrValue.get(value);
-
// 子屬性對應的權重比
-
HashMap<String, Integer> ratioValues = new HashMap<>();
-
-
for (int i = 0; i < attrTypes.size(); i++) {
-
// 首先都統一計數為0
-
ratioValues.put(attrTypes.get(i), 0);
-
}
-
-
// 還是按照一列，從左往右遍歷
-
for (int j = 1; j < attrNames.length; j++) {
-
// 判斷是否到了劃分的屬性列
-
if (value.equals(attrNames[j])) {
-
for (int i = 1; i <= remainData.length - 1; i++) {
-
childValueNum = ratioValues.get(remainData[i][j]);
-
// 增加個數并且重新存入
-
childValueNum++;
-
ratioValues.put(remainData[i][j], childValueNum);
-
}
-
}
-
}
-
-
// 計算原熵的大小
-
entropyOri = computeEntropy(remainData, value, null, true);
-
for (int i = 0; i < attrTypes.size(); i++) {
-
double ratio = (double) ratioValues.get(attrTypes.get(i))
-
/ (remainData.length - 1);
-
childEntropySum += ratio
-
* computeEntropy(remainData, value, attrTypes.get(i), false);
-
-
// System.out.println("ratio:value: " + ratio + " " +
-
// computeEntropy(remainData, value,
-
// attrTypes.get(i), false));
-
}
-
-
// 二者熵相減就是信息增益
-
gainValue = entropyOri - childEntropySum;
-
return gainValue;
-
}
-
-
/**
-
* 計算信息增益比
-
*
-
* @param remainData
-
* 剩余數據
-
* @param value
-
* 待劃分屬性
-
* @return
-
*/
-
private double computeGainRatio(String[][] remainData, String value) {
-
double gain = 0;
-
double spiltInfo = 0;
-
int childValueNum = 0;
-
// 屬性值的種數
-
ArrayList<String> attrTypes = attrValue.get(value);
-
// 子屬性對應的權重比
-
HashMap<String, Integer> ratioValues = new HashMap<>();
-
-
for (int i = 0; i < attrTypes.size(); i++) {
-
// 首先都統一計數為0
-
ratioValues.put(attrTypes.get(i), 0);
-
}
-
-
// 還是按照一列，從左往右遍歷
-
for (int j = 1; j < attrNames.length; j++) {
-
// 判斷是否到了劃分的屬性列
-
if (value.equals(attrNames[j])) {
-
for (int i = 1; i <= remainData.length - 1; i++) {
-
childValueNum = ratioValues.get(remainData[i][j]);
-
// 增加個數并且重新存入
-
childValueNum++;
-
ratioValues.put(remainData[i][j], childValueNum);
-
}
-
}
-
}
-
-
// 計算信息增益
-
gain = computeGain(remainData, value);
-
// 計算分裂信息，分裂信息度量被定義為(分裂信息用來衡量屬性分裂數據的廣度和均勻)：
-
for (int i = 0; i < attrTypes.size(); i++) {
-
double ratio = (double) ratioValues.get(attrTypes.get(i))
-
/ (remainData.length - 1);
-
spiltInfo += -ratio * Math.log(ratio) / Math.log(2.0);
-
}
-
-
// 計算機信息增益率
-
return gain / spiltInfo;
-
}
-
-
/**
-
* 利用源數據構造決策樹
-
*/
-
private void buildDecisionTree(AttrNode node, String parentAttrValue,
-
String[][] remainData, ArrayList<String> remainAttr, boolean isID3) {
-
node.setParentAttrValue(parentAttrValue);
-
-
String attrName = "";
-
double gainValue = 0;
-
double tempValue = 0;
-
-
// 如果只有1個屬性則直接返回
-
if (remainAttr.size() == 1) {
-
System.out.println("attr null");
-
return;
-
}
-
-
// 選擇剩余屬性中信息增益最大的作為下一個分類的屬性
-
for (int i = 0; i < remainAttr.size(); i++) {
-
// 判斷是否用ID3算法還是C4.5算法
-
if (isID3) {
-
// ID3算法采用的是按照信息增益的值來比
-
tempValue = computeGain(remainData, remainAttr.get(i));
-
} else {
-
// C4.5算法進行了改進，用的是信息增益率來比,克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足
-
tempValue = computeGainRatio(remainData, remainAttr.get(i));
-
}
-
-
if (tempValue > gainValue) {
-
gainValue = tempValue;
-
attrName = remainAttr.get(i);
-
}
-
}
-
-
node.setAttrName(attrName);
-
ArrayList<String> valueTypes = attrValue.get(attrName);
-
remainAttr.remove(attrName);
-
-
AttrNode[] childNode = new AttrNode[valueTypes.size()];
-
String[][] rData;
-
for (int i = 0; i < valueTypes.size(); i++) {
-
// 移除非此值類型的數據
-
rData = removeData(remainData, attrName, valueTypes.get(i));
-
-
childNode[i] = new AttrNode();
-
boolean sameClass = true;
-
ArrayList<String> indexArray = new ArrayList<>();
-
for (int k = 1; k < rData.length; k++) {
-
indexArray.add(rData[k][0]);
-
// 判斷是否為同一類的
-
if (!rData[k][attrNames.length - 1]
-
.equals(rData[1][attrNames.length - 1])) {
-
// 只要有1個不相等，就不是同類型的
-
sameClass = false;
-
break;
-
}
-
}
-
-
if (!sameClass) {
-
// 創建新的對象屬性，對象的同個引用會出錯
-
ArrayList<String> rAttr = new ArrayList<>();
-
for (String str : remainAttr) {
-
rAttr.add(str);
-
}
-
-
buildDecisionTree(childNode[i], valueTypes.get(i), rData,
-
rAttr, isID3);
-
} else {
-
// 如果是同種類型，則直接為數據節點
-
childNode[i].setParentAttrValue(valueTypes.get(i));
-
childNode[i].setChildDataIndex(indexArray);
-
}
-
-
}
-
node.setChildAttrNode(childNode);
-
}
-
-
/**
-
* 屬性劃分完畢，進行數據的移除
-
*
-
* @param srcData
-
* 源數據
-
* @param attrName
-
* 劃分的屬性名稱
-
* @param valueType
-
* 屬性的值類型
-
*/
-
private String[][] removeData(String[][] srcData, String attrName,
-
String valueType) {
-
String[][] desDataArray;
-
ArrayList<String[]> desData = new ArrayList<>();
-
// 待刪除數據
-
ArrayList<String[]> selectData = new ArrayList<>();
-
selectData.add(attrNames);
-
-
// 數組數據轉化到列表中，方便移除
-
for (int i = 0; i < srcData.length; i++) {
-
desData.add(srcData[i]);
-
}
-
-
// 還是從左往右一列列的查找
-
for (int j = 1; j < attrNames.length; j++) {
-
if (attrNames[j].equals(attrName)) {
-
for (int i = 1; i < desData.size(); i++) {
-
if (desData.get(i)[j].equals(valueType)) {
-
// 如果匹配這個數據，則移除其他的數據
-
selectData.add(desData.get(i));
-
}
-
}
-
}
-
}
-
CDA數據分析師考試相關入口一覽（建議收藏）：
? 想報名CDA認證考試，點擊>>>
“CDA報名”
了解CDA考試詳情；
? 想學習CDA考試教材，點擊>>> “CDA教材” 了解CDA考試詳情；
? 想加入CDA考試題庫，點擊>>> “CDA題庫” 了解CDA考試詳情；
? 想了解CDA考試含金量，點擊>>> “CDA含金量” 了解CDA考試詳情；
京公網安備 11010802034615號
經營許可證編號：京B2-20210330
