C45算法建立決策樹JAVA練習(xí)(DOC)

1、【決策樹】一C4.5算法建立決策樹JAVA練習(xí)以下程序是我練習(xí)寫的，不一定正確也沒做存儲優(yōu)化。有問題請留言交流。轉(zhuǎn)載請掛連接。當(dāng)前的屬性為：age in come stude nt credit_rat ing當(dāng)前的數(shù)據(jù)集為( 取后列疋TARGET_VALUE)youthhighnofairnoyouthhighnoexcelle ntnomiddle_agedhighnofairyesseniorlowyesfairyesseniorlowyesexcelle ntnomiddle_agedlowyesexcelle ntyesyouthmediumnofairnoyouthlowyesfa

2、iryesseniormediumyesfairyesyouthmediumyesexcelle ntyesmiddle_agedhighyesfairyesseniormediumnoexcelle ntnoC4.5建立樹類package C45Test;import java.util.ArrayList; import java.util.List;import java.util.Map;public class Decisi on Tree public TreeNode createDT(ListArrayList attributeList)System.out.println(

3、”當(dāng)前的 DATA 為);for (int i=O;idata.size();i+)ArrayList temp = data.get(i);for (int j=0;jtemp.size();j+) System.out.pri nt(temp.get(j)+);System.out.pri ntl n();data,ListSystem.out.println(”-);System.out.println(”當(dāng)前的 ATTR 為)；for (int i=O;iattributeList.size();i+)System.out.pri nt(attributeList.get(i)+ );

4、System.out.pri ntl n();System.out.println(”-);TreeNode node = n ewTreeNode();Stri ng result = In foGai n.lsPure(l nfoGai n.getTarget(data);if (result != null )n ode.setNodeName(leafNode);no de.setTargetF unV alue(result);retur n no de;if (attributeList.size() = 0)no de.setTargetF unV alue(result);re

5、tur n no de; else In foGai n gai n =n ewI nfoGai n(data,attributeList);double maxGai n = 0.0;int attrIndex = -1;for (int i=0;iattributeList.size();i+) double tempGai n =gain. getGa in Ratio(i); if (maxGain tempGain)maxGa in = tempGa in;attrI ndex = i;System.out.pri ntln (”選擇出的最大增益率屬性為:attributeList.

6、get(attrI ndex);no de.setAttributeValue(attributeList.get(attrI ndex);ListArrayList resultData =null ;Map attrvalueMap =gai n.getAttributeValue(attrI ndex);for (Map.EntryvString, Long entry :attrvalue Map .e ntrySet()resultData = gain. getData4Value(e ntry.getKey(),attrI ndex);TreeNode leafNode =Sys

7、tem.out.pri ntl n(”+attributeList.get(attrIndex)+null ;當(dāng)前為的+e ntry.getKey()+分支。);if (resultData.size() = 0)leafNode =newTreeNode();leafNode.setNodeName(attributeList.get(attrl ndex); leafNode.setTargetF unValue(result); leafNode.setAttributeValue(e ntry.getKey();else for ( int j = 0; j resultAttr =n

8、ewArrayListvStri ng(attributeList);resultAttr.remove(attrI ndex);leafNode = createDT(resultData,resultAttr);n ode.getChildTreeNode().add(leafNode);no de.getPathName().add(e ntry.getKey();return no de;class TreeNodeprivate Stri ng attributeValue;private List childTreeNode;private List pathName;privat

9、e Stri ng targetF unV alue;private Stri ng no deName;public TreeNode(String nodeName)this .no deName = no deName;this .childTreeNode = newArrayList(); this .pathName= newArrayList();public TreeNode()this .childTreeNode = newArrayList(); this .pathName= newArrayList();public String getAttributeValue(

10、) return attributeValue;public void setAttributeValue(String attributevalue) this .attributeValue = attributeValue;public List getChildTreeNode() return childTreeNode;public void setChildTreeNode(List childTreeNode) this .childTreeNode = childTreeNode;public String getTargetFunValue() return targetF

11、unValue;public void setTargetFunValue(String targetFunValue) this .targetFunValue = targetFunValue;public String getNodeName() retur n no deName;public void setNodeName(Stri ng no deName) this .no deName = nodeName;public List getPathName() return pathName;public void setPathName(List pathName) this

12、 .pathName =pathName;Ql增益率計算類（取log的時候底用的是e,沒用2）package C45Test;import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;import java.util.List;import java.util.Map;import java.util.Set;/C 4.5 實現(xiàn)public class InfoGain private ListArrayList data;private List

13、 attribute;public InfoGain(ListArrayList data,List attributethis .data =newArrayListArrayList();for (int i=O;idata.size();i+)List temp = data.get(i);ArrayList t =n ewArrayList();for (int j=0;jtemp.size();j+) t.add(temp.get(j);this .data.add(t);this .attribute =newArrayList();for (int k=0;kattribute.

14、size();k+) this .attribute.add(attribute.get(k);/*this.data = data;this.attribute = attribute;*/獲得熵public double getE ntropy()Map targetValueMap = getTargetValue();Set targetkey = targetValueMap.keySet();double en tropy = 0.0;for (String key : targetkey)double p = MathUtils.div( double )targetValueM

15、ap.get(key),(double )data.size();en tropy += (-1) * p * Math.log(p);return entropy;/ 獲得 InfoApublic double getl nfoAttribute( int attribute In dex)MapvStri ng,L ong attributeValueMap = getAttributeValue(attributeI ndex);double infoA = 0.0;for (Map.EntryvString, Long entry :attributeValueM ap.e ntryS

16、et()int size = data.size();double attributeP = MathUtils.div( double )entry.getValue()(double) size);Map targetValueMap = getAttributeValueTargetValue(entry.getKey(),attributeI ndex);long totalCount = 0L;for (Map.EntryvString, Longen tryValue :targetValue Map .e ntrySet()totalCo unt += en tryValue.g

17、etValue();double valueSum = 0.0;for (Map.EntryvString, Long entryTargetValue :targetValueMap.e ntrySet()double p =MathUtils.div( double )e ntryTargetValue.getValue(),(double )totalCou nt);valueSum += Math.log(p) * p;infoA += (-1) * attributeP * valueSum;return infoA;/得到屬性值在決策空間的比例public MapvString,L

18、ong getAttributeValueTargetValue(StringattributeName, int attribute In dex)MapvStri ng,L ong targetValueMap =newHashMapvString,Long();lteratorArrayList iterator = data.iterator();while (iterator.hasNext()List tempList = iterator. next();if (attributeName.equalsIgnoreCase(tempList.get(attributeIndex)

19、int size = tempList.size();Stri ng key = tempList.get(size - 1);Long value = targetValueMap.get(key);targetValueMap.put(key, value !=return targetValueMap;null ? +value :1L);/得到屬性在決策空間上的數(shù)量public Map getAttributeValue(int attributelndex)Map attributeValueMap =HashMap();for (ArrayList note : data) Str

20、ing key = no te.get(attributel ndex); Longvalue = attributeValueMap.get(key);attributeValueMap.put(key, value !=return attributeValueMap;newnull ? +value :1L);public ListArrayList getData4Value(String attrValue,intattrl ndex)ListArrayList resultData =newArrayListArrayList();IteratorArrayList iterato

21、r = data.iterator();for (;iterator.hasNext();)ArrayList templist = iterator. next();if(templist.get(attrlndex).equalslgnoreCase(attrValue) ArrayList temp = (ArrayList) templist.clo ne();resultData.add(temp);return resultData;/獲得增益率public double getGa in Ratio( int attribute In dex)return MathUtils.d

22、iv(getGain(attributeIndex), getSplitI nfo(attributelndex);/獲得增益量public double getGa in( int attribute In dex)return getEntropy() - getInfoAttribute(attributelndex);/得到懲罰因子public double getSplitI nfo( int attribute In dex)MapvStri ng,L ong attributeValueMap =getAttributeValue(attributel ndex);double

23、splitA = 0.0;for (Map.EntryvString, Long entry :attributeValueM ap.e ntrySet()int size = data.size();double attributeP = MathUtils.div( double )entry.getValue()(double) size);splitA += attributeP * Math.log(attributeP) * (-1);return splitA;/得到目標(biāo)函數(shù)在當(dāng)前集合范圍內(nèi)的離散的值public Map getTargetValue()Map targetVal

24、ueMap =n ewHashMapvStri ng,L ong();IteratorArrayList iterator = data.iterator();while (iterator.hasNext()List tempList = iterator. next();Stri ng key = tempList.get(tempList.size() - 1);Long value = targetValueMap.get(key);targetValueMap.put(key, value !=null ? +value : 1L);return targetValueMap;/獲得

25、 TARGE 值public static ListvStringgetTarget(ListArrayListListvStri ng list =n ewArrayList();for (ArrayList temp : data) int index = temp.size() -1;Stri ng value = temp.get(i ndex); list.add(value);return list;/判斷當(dāng)前純度是否 100%public static Stri ng lsPure(List list)Set set =n ewHashSet();for (String name

26、 :list)set.add( name);if (set.size() 1) return null ;IteratorvString iterator = set.iterator(); return iterator.next();測試類，數(shù)據(jù)集讀取以上的分別放到2個List中。package C45Test;import java.util.ArrayList;import java.util.List;import C45Test.DecisionTree.TreeNode;public class MainC45 private staticfinal ListArrayList

27、dataList =ArrayListArrayList();private staticfinal ListvStri ng attributeList =newArrayList();data)newpublic static void main(String args)Decisi on Tree dt =new Decisi on Tree();TreeNode node = dt.createDT(configData(),configAttribute();System.out.pri ntl n();大數(shù)運算工具類package C45Test;import java.math.

28、BigDecimal;public abstract class MathUtils 默認(rèn)余數(shù)長度private static final int DIV_SCALE = 10;/受限于 DOUBL 長度public static double add( double value1, double value2)BigDecimal big1 =n ewBigDecimal(Stri ng.valueOf(value1);BigDecimal big2 =n ewBigDecimal(Stri ng.valueOf(value2);return big1.add(big2).doubleValue();/大數(shù)加法public static double add(Stri ng value1,Stri ng value2)BigDecima