🚀 go-pugleaf

������ڴ��ˡ�������2����ʾ˵NullPointerException.
�����Ϻ�����ĸ���ͬѧ��ô���˰�������ô���أ�
�Ѿ����˺ü�����ѧ�ˡ�ϣ���Ϻ������и��ˡ�
import java.util.*;
import java.io.*;
    class SS
    {
        String[] sif;
        int [] iif;
        int num;
        int column;
        
        public SS()
        {
            sif=null;
            iif=null;
            num=0;
            column=1;
            }
        public void init(String [][] s,int m,int column)
        {  //s��ʾһ��2ά�ַ����飬m��ʾԪ�����column��ʾ���Ե�����
            int i,j;
            this.column=column;
            String[] tmp=new String[m];
            
            for(i=0;i<m;i++)
                tmp[i]=s[i][column-1];//���Ƶ�column�е�����ֵ��tmp�ַ�����
            Vector v1=new Vector(4);
            v1.add(tmp[0]);
            for(i=1;i<m;i++)//ɨ��tmp���޳���ͬ��ֵ
            {
                boolean found=false;
                for(int k=0;k<i;k++)//k<i����ֻ��ɨ��i֮ǰ��ֵû���ظ�
                    if(tmp[k].equals(tmp[i]))  {found=true;break;}
                if (!found) v1.add(tmp[i]);//���ҵ��IJ��ظ���ֵ����Vector v1
��
            }   
                
            sif=new String[v1.size()];//��ʼ��v1ʵ�ʴ�С���ַ�����
            v1.copyInto(sif);//��v1�е���ֵ���Ƶ�sif�ַ�����
            iif=new int[v1.size()];//iif�Ƕ�Ӧsif��ÿ��ֵ�ĸ���
            num=v1.size();
            for(i=0;i<sif.length;i++)
                for(j=0;j<m;j++)
                    if (sif[i].equals(tmp[j])) iif[i]++;    
        }
        
        public int getNum()
        {
            return num;
        }
        
        public int getColumn()
        {
            return column;
        }
        
        public String getSif(int i)
        {
            return sif[i];
        }
        
        public int getIif(int i)
        {
            return iif[i];
        }
        
        public void print()
        {
            System.out.println(num);
            for(int i=0;i<num;i++)
                System.out.println(sif[i]+" "+iif[i]);
        }
    }       
    class PracticeData
    {
        private String value[][]=null;
        private int m=0;
        private int n=0;
        private String att[]=null;
        private SS sc=null;
        
        public PracticeData(){}
        
        public PracticeData(String[][] s,String[] attr)
        {
            value=s;
            m=s.length;
            n=s[0].length;
            att=attr;
            sc=new SS();
            sc.init(s,m,n);
        }
        
        public String[][] getArray()
        {
            return value;
        }
        
        public int getM()
        {
            return m;
        }
        
        public int getN()
        {
            return n;
        }
        
        public SS getSc()
        {
            return sc;
        }
        
        public String[] getAttributeList()
        {
            return att;
        }
        
        public void getValue(String[][] s,String[] attr)
        {
            value=s;
            att=attr;
            m=s.length;
            n=s[0].length;
            sc=new SS();
            sc.init(s,m,n);
        }
        
        public void getValue(String filename)
        {
                try
            {
                BufferedReader in=new BufferedReader(new 
FileReader(filename));
                n=Integer.parseInt(in.readLine());
                
                att=new String[n];
                String attribute=in.readLine();
                StringTokenizer t1=new StringTokenizer(attribute,"|");
                for(int i=0;i<n;i++) att[i]=t1.nextToken();
                
                m=Integer.parseInt(in.readLine());
                
                if (m>0)
                {
                    value=new String[m][n];
                    for(int i=0;i<m;i++)
                    {
                        String tmp=in.readLine();
                        StringTokenizer t2=new StringTokenizer(tmp,"|");
                        for(int j=0;j<n;j++)
                            value[i][j]=t2.nextToken();
                    }
                
                    for(int i=0;i<m;i++)
                    {
                        for(int j=0;j<n;j++)
                            System.out.print(value[i][j]+" ");
                        System.out.println();
                    }   
                }
            }
            catch(IOException e)
            {
                System.out.print("Error"+e);
                System.exit(1);
            }
            sc=new SS();
            sc.init(value,m,n);
        }   
            
        public int[][] getNums(String value[][],SS sc,SS sj)    
        {//��Ӧp191������
            int row=sc.getNum();
            int col=sj.getNum();
            int[][] nums=new int[row][col];
            
            for(int i=0;i<row;i++)
                for(int j=0;j<col;j++)
                    nums[i][j]=0;//��ʼ��
                    
            String v1=null;
            String v2=null;
            for(int k=0;k<m;k++)
            {
                v1=value[k][sc.getColumn()-1];
                v2=value[k][sj.getColumn()-1];
                System.out.println(k+" "+v1+" "+v2);
                
                int r1=find(sc,v1);
                int c1=find(sj,v2);
                
                nums[r1][c1]++;
            }
            return nums;
        }
        
        public double E(int[][] s,SS sc,SS sj)
        {//����sj�������Ե��ص�����ѹ��
            int row=sc.getNum();
            int col=sj.getNum();
            System.out.println("row="+row+" col="+col);
            double sum2=0.0;
            
            for(int j=0;j<col;j++)
            {
                double tmp=0.0;
                for(int k=0;k<row;k++)
                    tmp+=s[k][j];
                double sum1=0.0;
                for(int i=0;i<row;i++)
                {
                    double p=s[i][j]/tmp;
                    double tp=0.0;
                    if(p!=0.0)
                        tp=((Math.log(p))/Math.log(2));
                    sum1+=(p*tp);
                }
                sum1=-sum1;     
                double tt=getM();
                sum2+=((sj.getIif(j)/tt)*sum1);
            }
            double sum3=0.0;
            for(int i=0;i<sc.getNum();i++)
            {
                double t=getM();
                double p0=sc.getIif(i)/t;
                double p1=0.0;
                if (p0!=0.0)
                    p1=(Math.log(p0))/Math.log(2);  
                sum3+=(p0*p1);
            }
            sum3=-sum3;
            double result=sum3-sum2;
            return result;
        }   
                
        public int find(SS s,String str)
        {//���Ҹ��str��ֵ������SS���sif���������
            int back=0;
            for(int i=0;i<s.getNum();i++)
                if (s.getSif(i).equals(str)) {back=i;break;}
            return back;        
        }
    }       
    
    class TreeNode
    {
        private boolean leaf;
        private String attribute;
        private String classname;
        private String[][] table;
        private String[] attrList;
        private Vector v;
        
        public TreeNode(boolean l)
        {
            leaf=l;
            attribute=null;
            classname=null;
            v=null;
            table=null;
            attrList=null;
        }
        
        public TreeNode(boolean l,String[][] s,String[] al)
        {
            leaf=l;
            table=s;
            attrList=al;
            attribute=null;
            classname=null;
            v=null;
        }
        
        public void setVector(int n)
        {
            v=new Vector(n);
        }
        
        public void addBranch(TreeNode t)
        {
            v.add(t);
        }
        
        public void setAttribute(String attr)
        {
            attribute=attr;
        }
        
        public void setClassname(String name)
        {
            classname=name;
        }
        
        public void changeToBranch()
        {
            leaf=false;
        }
        
        public void setTable(String[][] t)
        {
            table=t;
        }
        
        public void setAttrList(String[] al)
        {
            attrList=al;
        }
        
        public int getTableLength()
        {
            return table.length;
        }
        
        public int getTableWidth()
        {
            return table[0].length;
        }
    }
    
    class GenerateTree
    {
        private PracticeData pd;
        private SS sc;
        //private TreeNode decisionTree;
        
        public PracticeData getPracticeData()
        {
            return pd;  
        }
        public GenerateTree()
        {
            pd=null;
            sc=null;
        //  decisionTrdd=null;
        }
        
        public void initPracticeData(String filename)
        {
            pd=new PracticeData();
            pd.getValue(filename);
        }
        
        public String getCommonClass(SS s)//ȡsamples������ͨ���࣬
        {                               //�������s��ʾ������
            int i=0;
            int num=s.getNum();
            for (int j=0;j<num-1;j++)
                if (s.getIif(j+1)>s.getIif(j))
                    i=j+1;
            return s.getSif(i);
        }       
        
        public  TreeNode Generate_decision_tree(String[][] s,String[] list)
        {
            TreeNode tn=new TreeNode(true,s,list);//�����ڵ�N����Ӧ����(1)
            int cols=tn.getTableWidth();
            int rows=tn.getTableLength();
            boolean b=true;//�ж���s�Ƿ���ͬһ�����ԣ���Ӧ�㷨����(2)
            for(int i=1;i<rows;i++)
            {   if (!(s[i][cols-1].equals(s[0][cols-1])))//���������
                    b=false;
            }
            
            if (b==true)
            {
                tn.setClassname(s[0][cols-1]);
                tn.setAttribute(null);
                return tn;//���s��ͬһ�����ԣ����Ϊ�����ԣ���Ӧ����(3)
            }
            
            if (list==null)//�б�Ϊ�գ���Ӧ�㷨���裨4��
            {
                tn.setClassname(getCommonClass(sc));//��÷���������ͨ����
                tn.setAttribute(null);
                return tn;//���Ϊ����ͨ����󷵻أ���Ӧ���裨5��
            }
            
            double maxInformationGain=0.0;//��������棬��Ӧ�㷨���裨6��
            SS stmp=new SS();
            String[] newlist=null;
            int index=0;
            for(int i=0;i<list.length;i++)
            {
                SS sj=new SS();
                sj.init(s,rows,i+1);
                SS scc=new SS();
                scc.init(s,rows,cols);
                PracticeData ppd=new PracticeData(s,list);
                double tt=ppd.E(ppd.getNums(s,scc,sj),scc,sj);
                if (tt>=maxInformationGain)
                {
                        stmp=sj;
                        tn.setAttribute(list[i]);//����������,��Ӧ�㷨����
��7��
                        index=i;
                        maxInformationGain=tt;
                }       
            }
            
            newlist=new String[list.length-1];
            int r=0;
            for(int l=0;l<list.length;l++)
            {
                if(l!=index) {
                                newlist[r]=list[l];
                                r++;
                             }
            
            }
            
            for(int i=0;i<stmp.getNum();i++)//����������������Խ��л��֣�
��Ӧ���裨
8��
            {
                TreeNode node=new TreeNode(true);
                node.setClassname(stmp.getSif(i));//��������ֵΪai�ķ�֦,��Ӧ
���裨9��
                String[][] tmps;
                tmps=split(s,stmp.getColumn(),stmp.getSif(i));//si������
��ֵΪai�Ļ�
��
                node.setTable(tmps);                        //��Ӧ���裨10��
                node.setVector(stmp.getNum());
                node.changeToBranch();
                if(tmps==null)//�ж�si�Ƿ�Ϊ�գ���Ӧ���裨11��
                {   node.setClassname(getCommonClass(stmp));//���si��
                    tn.addBranch(node);//����ϱ��Ϊsamples������ͨ���һ��
��Ҷ
                    return tn;
                }                     //��Ӧ���裨12��  
                else
                {
                    tn.addBranch(Generate_decision_tree(tmps,newlist));//���
�����
                    return tn;
                }
                
            }//������si���գ���siΪ�µ����ά�?�ԡ�list-���εݹ��������
���������
��Ϊ�µ�list
            return null;
        }   //�ݹ����Generate_decision_tree������������Ӧ���裨13��    
            
        public String[][] split(String[][] s,int column,String value)
        {
            int row=s.length;
            int col=s[0].length;
            int newrow=0;
            for(int i=0;i<row;i++)
                if (s[i][column-1].equals(value))
                    newrow++;
            if (newrow==0)      return null;
            String[][] news =new String[newrow][col-1];
            for(int i=0;i<row;i++)
            {
                int k=0;
                if (s[i][column-1].equals(value))
                {
                    for(int j=0;j<col;j++)
                    {
                        int u=0;
                        if(j!=column-1)
                            {
                                news[k][u]=s[i][j];
                                u++;
                            }
                    }
                    k++;
                }
            }
            return news;
        }
    }                   
                
    public class FirstTree
    {
        public static void main(String[] agrs)
        {
            GenerateTree tree=new GenerateTree();
            tree.initPracticeData("prectice.dat");
            TreeNode node=new TreeNode(true);
            
node=tree.Generate_decision_tree(tree.getPracticeData().getArray(),tree.g
etPracticeData().getAttributeList());
        }       
    }
            
 
--
�� ��Դ:����ˮ˼Դ bbs.sjtu.edu.cn��[FROM: 202.117.223.38]