🚀 go-pugleaf

�������ļ���һ�°���

--
�ս����һ��վ�㣬������ͬ��Ȥ�����Ѽ��ˣ�
http://www.javaphp.com/



"jardeng" <jardeng.bbs@bbs.sjtu.edu.cn> д����Ϣ����
:49DJR3$AeQ@bbs.sjtu.edu.cn...
> ������ڴ��ˡ�������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]