此文不对理论做相关阐述,仅涉及代码实现:
1.熵计算公式:
P为正例,Q为反例
Entropy(S) = -PLog2(P) - QLog2(Q);
2.信息增量计算:
Gain(S,Sv) = Entropy(S) - (|Sv|/|S|)ΣEntropy(Sv);
举例:
转化数据输入:
5 14
Outlook Sunny Sunny Overcast Rain Rain Rain Overcast Sunny Sunny Rain Sunny Overcast Overcast Rain
Temperature Hot Hot Hot Mild Cool Cool Cool Mild Cool Mild Mild Mild Hot Mild
Humidity High High High High Normal Normal Normal High Normal Normal Normal High Normal High
Wind Weak Strong Weak Weak Weak Strong Strong Weak Weak Weak Strong Strong Weak Strong
PlayTennis No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No
Outlook Temperature Humidity Wind PlayTennis
package com.qunar.data.tree; /**
* *********************************************************
* <p/>
* Author: XiJun.Gong
* Date: 2016-09-02 15:28
* Version: default 1.0.0
* Class description：
* <p>统计该类型出现的次数</p>
* <p/>
* *********************************************************
*/
public class CountMap<T> { private T key; //类型
private int value; //出现的次数 public CountMap() {
this(null, 0);
} public CountMap(T key, int value) {
this.key = key;
this.value = value;
} public T getKey() {
return key;
} public void setKey(T key) {
this.key = key;
} public int getValue() {
return value;
} public void setValue(int value) {
this.value = value;
}
}
package com.qunar.data.tree; import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Maps;
import com.google.common.collect.Multimap;
import com.google.common.collect.Sets; import java.util.*; /**
* *********************************************************
* <p/>
* Author: XiJun.Gong
* Date: 2016-09-02 14:24
* Version: default 1.0.0
* Class description：
* <p>决策树</p>
* <p/>
* *********************************************************
*/ public class DecisionTree<T, K> { private static String positiveExampleType = "Yes";
private static String counterExampleType = "No"; public double pLog2(final double p) {
if (0 == p) return 0;
return p * (Math.log(p) / Math.log(2));
} /**
* 熵计算
*
* @param positiveExample 正例个数
* @param counterExample 反例个数
* @return 熵值
*/
public double entropy(final double positiveExample, final double counterExample) { double total = positiveExample + counterExample;
double positiveP = positiveExample / total;
double counterP = counterExample / total;
return -1d * (pLog2(positiveP) + pLog2(counterP));
} /**
* @param features 特征列表
* @param results 对应结果
* @return 将信息整合成新的格式
*/
public Multimap<T, CountMap<K>> merge(final List<T> features, final List<T> results) {
//数据转化
Multimap<T, CountMap<K>> InfoMap = ArrayListMultimap.create();
Iterator result = results.iterator();
for (T feature : features) {
K res = (K) result.next();
boolean tag = false;
Collection<CountMap<K>> countMaps = InfoMap.get(feature);
for (CountMap countMap : countMaps) {
if (countMap.getKey().equals(res)) {
/*修改值*/
int num = countMap.getValue() + 1;
InfoMap.remove(feature, countMap);
InfoMap.put(feature, new CountMap<K>(res, num));
tag = true;
break;
}
}
if (!tag)
InfoMap.put(feature, new CountMap<K>(res, 1));
} return InfoMap;
} /**
* 信息增益
*
* @param infoMap 因素(Outlook,Temperature,Humidity,Wind)对应的结果
* @param dataTable 输入的数据表
* @param type 因素中的类型(Outlook{Sunny,Overcast,Rain})
* @param entropyS 总的熵值
* @param totalSize 总的样本数
* @return 信息增益
*/
public double gain(Multimap<T, CountMap<K>> infoMap,
Map<K, List<T>> dataTable,
final String type,
double entropyS,
final int totalSize) {
//去重
Set<T> subTypes = Sets.newHashSet();
subTypes.addAll(dataTable.get(type));
/*计算*/
for (T subType : subTypes) {
Collection<CountMap<K>> countMaps = infoMap.get(subType);
double subSize = 0;
double positiveExample = 0;
double counterExample = 0;
for (CountMap<K> countMap : countMaps) {
subSize += countMap.getValue();
if (positiveExampleType.equals(countMap.getKey()))
positiveExample = countMap.getValue();
else
counterExample = countMap.getValue();
}
entropyS -= (subSize / totalSize) * entropy(positiveExample, counterExample);
}
return entropyS;
} /**
* 计算
*
* @param dataTable 数据表
* @param types 因素列表{Outlook,Temperature,Humidity,Wind}
* @param resultType 结果(PlayTennis)
* @return 返回信息增益集合
*/
public Map<String, Double> calculate(Map<K, List<T>> dataTable, List<K> types, K resultType) { Map<String, Double> answer = Maps.newHashMap();
List<T> results = dataTable.get(resultType);
int totalSize = results.size();
int positiveExample = 0;
int counterExample = 0;
double entropyS = 0d;
for (T ExampleType : results) {
if (positiveExampleType.equals(ExampleType)) {
++positiveExample;
continue;
}
++counterExample;
}
/*计算总的熵*/
entropyS = entropy(positiveExample, counterExample); Multimap<T, CountMap<K>> infoMap;
for (K type : types) {
infoMap = merge(dataTable.get(type), results);
double _gain = gain(infoMap, dataTable, (String) type, entropyS, totalSize);
answer.put((String) type, _gain);
}
return answer;
} } package com.qunar.data.tree;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps; import java.util.*; /**
* *********************************************************
* <p/>
* Author: XiJun.Gong
* Date: 2016-09-02 16:43
* Version: default 1.0.0
* Class description：
* <p/>
* *********************************************************
*/
public class Main { public static void main(String args[]) { Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
DecisionTree<String, String> dt = new DecisionTree();
Map<String, List<String>> dataTable = Maps.newHashMap();
/*Map<String, List<String>> dataTable = Maps.newHashMap();*/
List<String> types = Lists.newArrayList();
String resultType;
int factorSize = scanner.nextInt();
int demoSize = scanner.nextInt();
String type; for (int i = 0; i < factorSize; i++) {
List<String> demos = Lists.newArrayList();
type = scanner.next();
for (int j = 0; j < demoSize; j++) {
demos.add(scanner.next());
}
dataTable.put(type, demos);
}
for (int i = 1; i < factorSize; i++) {
types.add(scanner.next());
}
resultType = scanner.next();
Map<String, Double> ans = dt.calculate(dataTable, types, resultType);
List<Map.Entry<String, Double>> list = new ArrayList<Map.Entry<String, Double>>(ans.entrySet());
Collections.sort(list, new Comparator<Map.Entry<String, Double>>() { @Override
public int compare(Map.Entry<String, Double> o1, Map.Entry<String, Double> o2) {
return (o2.getValue() > o1.getValue() ? 1 : -1);
}
}); for (Map.Entry<String, Double> iterator : list) {
System.out.println(iterator.getKey() + "= " + iterator.getValue());
}
}
} }
/**
*使用举例:*
5 14
Outlook Sunny Sunny Overcast Rain Rain Rain Overcast Sunny Sunny Rain Sunny Overcast Overcast Rain
Temperature Hot Hot Hot Mild Cool Cool Cool Mild Cool Mild Mild Mild Hot Mild
Humidity High High High High Normal Normal Normal High Normal Normal Normal High Normal High
Wind Weak Strong Weak Weak Weak Strong Strong Weak Weak Weak Strong Strong Weak Strong
PlayTennis No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No
Outlook Temperature Humidity Wind PlayTennis
*/
结果:
Outlook= 0.2467498197744391
Humidity= 0.15183550136234136
Wind= 0.04812703040826927
Temperature= 0.029222565658954647