id3算法.java

id3算法

    			leafNode.nodeName =3D getLeafNodeName(pickArray);
    			leafNode.childNodes =3D new TreeNode[0];
    			parentNode.childNodes[i] =3D leafNode;
    		}
    	}

    }
   =20
    public void printDTree(TreeNode node){
    	System.out.println(node.nodeName);

    	TreeNode[] childs =3D node.childNodes;
    	for(int i=3D0;i<childs.length;i++){
    		if(childs[i]!=3Dnull){
    			System.out.println(childs[i].parentArrtibute);
    			printDTree(childs[i]);
    		}
    	}
    }
 =20
    /**     =20
     * @param dataArray =E5=8E=9F=E5=A7=8B=E6=95=B0=E7=BB=84 D    =20
     * @param criterion =E6=A0=87=E5=87=86=E5=80=BC     =20
     * @return double     =20
     */    =20
    public void init(Object[] dataArray,int index) {
    	this.index =3D index;
        //=E6=95=B0=E6=8D=AE=E5=88=9D=E5=A7=8B=E5=8C=96  =20
        visable =3D new boolean[((String[])dataArray[0]).length];     =20
        for(int i=3D0;i<visable.length;i++) {   =20
            if(i =3D=3D index){  =20
                visable[i] =3D true;   =20
            }else {  =20
                visable[i] =3D false;   =20
            }  =20
        }  =20
    }  =20
   =20
    public Object[] pickUpAndCreateArray(Object[] array,String =
arrtibute,int index){
    	List<String[]> list =3D new ArrayList<String[]>();
    	for(int i=3D0;i<array.length;i++){
    		String[] strs =3D (String[])array[i];
    		if(strs[index].equals(arrtibute)){
    			list.add(strs);
    		}
    	}
    	return list.toArray();
    }
 =20
    /**   =20
     * Entropy(S)   =20
     * @param array   =20
     * @return double    =20
     */    =20
    public double gain(Object[] array,int index) {     =20
        String[] playBalls =3D getArrtibutes(this.index);  =20
        int[] counts =3D new int[playBalls.length];     =20
        for(int i=3D0;i<counts.length;i++) {  =20
            counts[i] =3D 0;     =20
        }  =20
        for(int i=3D0;i<array.length;i++) {  =20
            String[] strs =3D (String[])array[i];  =20
            for(int j=3D0;j<playBalls.length;j++) {  =20
                if(strs[this.index].equals(playBalls[j])) {  =20
                    counts[j]++;  =20
                }  =20
            }  =20
        }  =20
        /** =20
         * Entropy(S) =3D S -p(I) log2 p(I) =20
         */ =20
        double entropyS =3D 0;  =20
        for(int i=3D0;i<counts.length;i++) {     =20
            entropyS +=3D DTreeUtil.sigma(counts[i],array.length);     =20
        }  =20
        String[] arrtibutes =3D getArrtibutes(index);  =20
        /** =20
         * total ((|Sv| / |S|) * Entropy(Sv))  =20
         */ =20
        double sv_total =3D 0;  =20
        for(int i=3D0;i<arrtibutes.length;i++){  =20
            sv_total +=3D entropySv(array, =
index,arrtibutes[i],array.length);  =20
        }  =20
        return entropyS-sv_total;  =20
    }  =20
      =20
    /** =20
     * ((|Sv| / |S|) * Entropy(Sv)) =20
     * @param array =20
     * @param index =20
     * @param arrtibute =20
     * @param allTotal =20
     * @return =20
     */ =20
    public double entropySv(Object[] array,int index,String =
arrtibute,int allTotal) {  =20
        String[] playBalls =3D getArrtibutes(this.index);  =20
        int[] counts =3D new int[playBalls.length];  =20
        for(int i=3D0;i<counts.length;i++) {  =20
            counts[i] =3D 0;     =20
        }  =20
 =20
        for (int i =3D 0; i < array.length; i++) {  =20
            String[] strs =3D (String[]) array[i];  =20
            if (strs[index].equals(arrtibute)) {  =20
                for (int k =3D 0; k < playBalls.length; k++) {  =20
                    if (strs[this.index].equals(playBalls[k])) {  =20
                        counts[k]++;  =20
                    }  =20
                }  =20
            }  =20
        }  =20
 =20
        int total =3D 0;  =20
        double entropySv =3D 0;   =20
        for(int i=3D0;i<counts.length;i++){  =20
            total +=3D counts[i];  =20
        }  =20
        for(int i=3D0;i<counts.length;i++){  =20
            entropySv +=3D DTreeUtil.sigma(counts[i],total);   =20
        }   =20
        return DTreeUtil.getPi(total, allTotal)*entropySv;  =20
    }  =20
         =20
    @SuppressWarnings("unchecked")  =20
    public String[] getArrtibutes(int index) {     =20
        TreeSet<String> set =3D new TreeSet<String>(new =
SequenceComparator());     =20
        for (int i =3D 0; i < array.length; i++) {     =20
            String[] strs =3D (String[]) array[i];     =20
            set.add(strs[index]);     =20
        }     =20
        String[] result =3D new String[set.size()];     =20
        return set.toArray(result);     =20
    }  =20
         =20
    public String getNodeName(int index) {   =20
    	String[] strs =3D new =
String[]{"Outlook","Temperature","Humidity","Wind","Play ball"};
    	for(int i=3D0;i<strs.length;i++){
    		if(i =3D=3D index){
    			return strs[i];
    		}
    	}
    	return null;   =20
    }
   =20
    public String getLeafNodeName(Object[] array){
    	if(array!=3Dnull && array.length>0){
    		String[] strs =3D (String[])array[0];
    		return strs[index];
    	}
    	return null;	=09
    }
   =20
    public int getNodeIndex(String name) { =20
    	String[] strs =3D new =
String[]{"Outlook","Temperature","Humidity","Wind","Play ball"};
    	for(int i=3D0;i<strs.length;i++){
    		if(name.equals(strs[i])){
    			return i;
    		}
    	}
        return -1;   =20
    }=20
}     =20

package graph;     =20
    =20
/**   =20
 * @author B.Chen   =20
 */    =20
public class TreeNode {     =20
    =20
    /**   =20
     * =E7=88=B6   =20
     */    =20
    TreeNode parent;   =20
    =20
    /**   =20
     * =
=E6=8C=87=E5=90=91=E7=88=B6=E7=9A=84=E5=93=AA=E4=B8=AA=E5=B1=9E=E6=80=A7 =
  =20
     */    =20
    String parentArrtibute;     =20
    =20
    /**   =20
     * =E8=8A=82=E7=82=B9=E5=90=8D   =20
     */    =20
    String nodeName;     =20
    =20
    /**   =20
     * =E5=B1=9E=E6=80=A7=E6=95=B0=E7=BB=84   =20
     */    =20
    String[] arrtibutes;   =20
   =20
    /**
     * =E8=8A=82=E7=82=B9=E6=95=B0=E7=BB=84
     */
    TreeNode[] childNodes;

}     =20

package graph;  =20
 =20
public class DTreeUtil {  =20
 =20
    /** =20
     * =E5=B1=9E=E6=80=A7=E5=80=BC=E7=86=B5=E7=9A=84=E8=AE=A1=E7=AE=97 =
Info(T)=3D(i=3D1...k)pi*log=EF=BC=882=EF=BC=89pi =20
     *  =20
     * @param x =20
     * @param total =20
     * @return double =20
     */ =20
    public static double sigma(int x, int total) {
    	if(x =3D=3D 0){
    		return 0;
    	}
        double x_pi =3D getPi(x, total);  =20
        return -(x_pi * logYBase2(x_pi));  =20
    }  =20
 =20
    /** =20
     * log2y =20
     *  =20
     * @param y =20
     * @return double =20
     */ =20
    public static double logYBase2(double y) {  =20
        return Math.log(y) / Math.log(2);  =20
    }  =20
 =20
    /** =20
     * =
pi=E6=98=AF=E5=BD=93=E5=89=8D=E8=BF=99=E4=B8=AA=E5=B1=9E=E6=80=A7=E5=87=BA=
=E7=8E=B0=E7=9A=84=E6=A6=82=E7=8E=87=EF=BC=88=3D=E5=87=BA=E7=8E=B0=E6=AC=A1=
=E6=95=B0/=E6=80=BB=E6=95=B0=EF=BC=89 =20
     *  =20
     * @param x =20
     * @param total =20
     * @return double =20
     */ =20
    public static double getPi(int x, int total) {  =20
        return x * Double.parseDouble("1.0") / total;  =20
    } =20

}  =20

package graph;

import java.util.Comparator;

public class SequenceComparator implements Comparator {

    public int compare(Object o1, Object o2) throws ClassCastException {
        String str1 =3D (String) o1;
        String str2 =3D (String) o2;
        return str1.compareTo(str2);
    }

}

</PRE></DIV>
<DIV class=3Dblog_bottom>
<UL>
  <LI>22:18 </LI>
  <LI>=E6=B5=8F=E8=A7=88 (207) </LI>
  <LI><A =
href=3D"http://leon-a.javaeye.com/blog/178585#comments">=E8=AF=84=E8=AE=BA=
</A> (0) </LI>