使⽤Java实现的决策树
本系统实现了决策树⽣成，只要输⼊合适的数据集，系统就可以⽣成⼀棵决策树。
数据集的输⼊使⽤⼆维数组，输⼊的个数为：序号+特征+分类结果。同时要把特征名以及对应的特征值传给程序，如此⼀来系统就可以建决策树。
关于决策树的定义这⾥不再列出，CSDN上有很多类似的博客。这些博客实现的Java代码很长，⼜没有注释，我看不懂，所以⾃⼰实现了⼀遍。我这⾥不再多加赘述。使⽤Java实现决策树个⼈觉得是不太明智的做法，⽐较繁琐，建议使⽤python实现。以下是代码，⼤部分应该是有注释的，后⾯可能是调到⼼累所有有些地⽅没有，留个纪念。原理还是很好懂的。
package homework;
import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
public class DecisionTree {
LinkedList<String[]> dataList = new LinkedList<String[]>();//保存训练集的数据，结构为：序号+属性+类别
LinkedList<String> attribute = new LinkedList<String>();//存放属性个数
DecisionTree father;
String attriValue;
String attriDivide;
LinkedList<DecisionTree> child;
HashMap<String,LinkedList<String>> attributeValue = new HashMap<String,LinkedList<String>>();//存放属性及其对应的属性值
public DecisionTree(String[][] data,HashMap<String,LinkedList<String>> attributeValue,DecisionTree father,String attriDivide,String attriValue) {
this.father = father;
this.attriDivide = attriDivide;
this.attriValue = attriValue;
this.attributeValue = attributeValue;
getDataAndAttribute(data,attributeValue);
if(!detectEnd()) {//当前节点不为终叶节点，可以继续往下分
String attriRoot = bestAttri();//得到当前的划分属性
Map<String,LinkedList<String[]>> child = divideByAttribute(attriRoot);//得到划分后的所有东西
this.child = new LinkedList<DecisionTree>();//后⾯划分的节点属于当前的⼉⼦
//获得不同键值下⾯的数据集，先获取键值集
Set<String> keySet = child.keySet();
//遍历键值集
Iterator<String> keys = keySet.iterator();
while(keys.hasNext()) {
String key = ();
LinkedList<String[]> childData = (key);//获取此键值下⾯的所有数据集
HashMap<String,LinkedList<String>> newAttribute = this.attributeValue;
if(childData.size()==0)continue;
String[][] datas = new String[childData.size()][(0).length];//将child下⾯的data改为⼆维数组的形式
for(int i=0;i<childData.size();i++) {
datas[i] = (i);
}
DecisionTree childNode = new DecisionTree(datas,newAttribute,this,attriRoot,key);
this.child.add(childNode);
}
}
}
resultset 遍历public void getDataAndAttribute(String[][] data,HashMap<String,LinkedList<String>> attribute) {
for(int i=0;i<data.length;i++) {//将所有数据集压⼊类的数据集中
this.dataList.add(data[i]);
}
Set<String> keySet = attribute.keySet();
Set<String> keySet = attribute.keySet();
Iterator<String> it = keySet.iterator();//将map⾥⾯的键值写⼊到本地的attribute表中，作为属性表
while(it.hasNext()) {
String s = it.next();
this.attribute.add(s);
}
}
boolean detectEnd() {//判断当前节点是否为终叶节点
Set<String> detect = new HashSet<String>();
for(int i=0;i<dataList.size();i++) {
String[] temp = (i);
detect.add(temp[temp.length-1]);
}//当所有分类结果最终只有⼀种结果，就是终叶节点
if(detect.size()==1)return true;
else return false;
}
double calEntropy(String attribute) {
double result = 0;//所有属性值的熵值和
double totalNum = this.dataList.size();//总数据集的个数
Map<String,LinkedList<String[]>> divide = divideByAttribute(attribute);//得到按属性attribute值分类的结果  Set<String> keySet = divide.keySet();//得到所有键值
Iterator<String> iterator = keySet.iterator();//遍历所有键值
while(iterator.hasNext()) {
String key = ();
LinkedList<String[]> values = (key);//获得当前键值下所有的数据集
int count = values.size();//当前键值下的数据个数
Set<String> resultSet = new HashSet<String>();//使⽤Set来判断结果中有多少种
for(int i=0;i<count;i++) {
String[] temp = (i);
resultSet.add(temp[temp.length-1]);
}
Iterator<String> iteratorResult = resultSet.iterator();//遍历结果种数
double resultInAttribute = 0;//当前属性值下的熵值
int countI;
while(iteratorResult.hasNext()) {
countI=0;//计算不同结果各⾃有多少种
String resultI = (();//当前的结果
for(int i=0;i<count;i++) {
String[] temp = (i);//与数据集中的结果⽐较
if(temp[temp.length-1].equals(resultI))countI++;//如果数据与当前结果相同，计数加⼀
}
//计算得到当前属性值的熵
resultInAttribute = resultInAttribute - ((double)countI/count)*(Math.log((double)countI/count)/Math.log(2));  }
result = result + ((double)count/totalNum)*resultInAttribute;
}
return result;
}
public String bestAttri() {
double min = 100;
String choose = "";
for(int i=0;i<this.attribute.size();i++) {
double cal = calEntropy((i));
if(min>cal) {
min = cal;
choose = (i);
}
}
return choose;
}
Map<String,LinkedList<String[]>> divideByAttribute(String attribute){
LinkedList<String> attriValue = (attribute);//获得当前属性下的属性值
String[] content = (0);//从本类的数据中拿出第0个，为了判断当前的attribute在哪⼀列
int col=0;
for(int i=1;i<content.length-1;i++) {
ains(content[i])) {
ains(content[i])) {
col = i;//到当前attribute所在的列
break;
}
}
Map<String,LinkedList<String[]>> result = new HashMap<String,LinkedList<String[]>>();//结果集  //下⾯开始按attribute的值对dataList分类
for(int i=0;i<attriValue.size();i++) {//遍历
LinkedList<String[]> resultValue = new LinkedList<String[]>();//当前attribute[i]的值
for(int j=0;j<this.dataList.size();j++) {
String[] temp = (j);
if(temp[col].(i)))resultValue.add(temp);
}
if(resultValue.size()!=0)result.(i), resultValue);
}
return result;
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。