/* * To change this template, choose Tools | Templates * and open the template in the editor. */package id3;import java.io.BufferedReader;import java.io.File;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.IOException;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.ArrayList;/** * * @author Lam *//** * ID3判定樹類 * @author Lam * */class ID3Tree{	ID3Tree()	{		root=null;		attributeList=new AttributesList();		dataSet=new Matrix();		testData=new Matrix();		ruleList=new ArrayList<String>();	}		/**	 * 多數表決 	 * @param matrix 數據集	 * @return 數據集中最普通的類	 */	private String getMaxLabel(Matrix matrix)	{		if(matrix.matrix.size()==0)			return "";		ArrayList<Target> tarList=new ArrayList<Target>();		ArrayList<RowData> rows=matrix.matrix;		for(int i=0;i<rows.size();i++)		{			ArrayList<String> row=rows.get(i).rowdata;			String cLabel=row.get(row.size()-1);			int j=0;			for( ;j<tarList.size();j++)			{				if(tarList.get(j).label.equals(cLabel))				{					tarList.get(j).counts++;					break;				}			}			if(j==tarList.size())			{				Target tar=new Target();				tar.label=cLabel;				tar.counts++;				tarList.add(tar);			}		}		int maxTargetIndex=0;		int maxCounts=0;		for(int i=0;i<tarList.size();i++)		{			int count=tarList.get(i).counts;			if(count>maxCounts)			{				maxCounts=count;				maxTargetIndex=i;			}		}		String maxLabel=tarList.get(maxTargetIndex).label;		return maxLabel;	}		/**	 * 產生判定樹	 * @param attList 屬性列表	 * @param matrix  數據表	 * @param path 節點路徑(最終轉化為規則)	 * @return 判定樹節點	 */	private Node Generate_decision_tree(AttributesList attList,Matrix matrix,String path)	{		   Node t;					String label=this.theSameClass(matrix);			//在同一類中			if(label!=null)			{				t=new Node("Leave-Class"+label,path+"->"+label,1,0);							}			//attribute_list為空			else if(attList.attributes.size()==0)			{				String maxLabel=this.getMaxLabel(matrix);				t=new Node("Leave-Class"+maxLabel,path+"->"+maxLabel,1,0);			}			else			{				int maxColIndex=0;				double maxEntropy=0.0;				ArrayList<Column> cols=attList.attributes;				for(int i=0;i<cols.size();i++)				{					double gain=attList.inentropy-entropy(cols.get(i));					if(gain>maxEntropy)					{						maxEntropy=gain;						maxColIndex=i;					}				}				Column col=cols.get(maxColIndex);				int childCounts=col.attributes.size();				t=new Node("Node-"+col.label,path+col.label,-1,childCounts);				Node[] childs=t.childs;				for(int i=0;i<childs.length;i++)				{					String subAttr=this.getAttrLabel(attList, maxColIndex, i);					Matrix matr=buildMatrix(matrix,attList,maxColIndex,i);					if(matr.matrix.size()==0)					{						String maxLabel=this.getMaxLabel(matrix);												childs[i]=new Node("Leave-"+maxLabel,t.path+":"+subAttr+"->"+maxLabel,1,0);					}					else					{						AttributesList newAttrList=this.buildAttributesList(matr,attList,maxColIndex);						childs[i]=this.Generate_decision_tree(newAttrList, matr,t.path+":"+subAttr);					}				}			}				return t;			}		/**	 * 返回屬性列表中指定的某列的某個子屬性	 * @param attList 屬性列表	 * @param colIndex 屬性列位置	 * @param attIndex  子屬性位置	 * @return	 */	private String getAttrLabel(AttributesList attList,int colIndex,int attIndex)	{		ArrayList<Column> cols=attList.attributes;		Column col=cols.get(colIndex);		Attribute attr=col.attributes.get(attIndex);		return attr.label;	}		/**	 * 從指定節點產生判定樹規則	 * @param t	 */	private void genRule(Node t)	{		if(t!=null)		{			if(t.decision==1)  //屬于葉節點,記下它的路徑			{				ruleList.add(t.path);				return;			}			else //遞歸查找葉節點			{				Node[] childs=t.childs;				for(int i=0;i<childs.length;i++)				{					genRule(childs[i]);				}			}		}	}		/**	 * 將規則轉換為特定形式(類似于0:1->1)	 *	 */	private void checkRules()	{		genRule(root);		for(int i=0;i<ruleList.size();i++)		{			String s=ruleList.get(i);			s=s.substring(9);			s=s.replaceAll("Attribute", "+");			ruleList.set(i, s);		}	}		/**	 * 輸出判定樹規則的特定形式	 *	 */	public void showRules() throws IOException	{		checkRules();		System.out.println("規則列表:");		File ruleFile=new File("rule.txt");		if(ruleFile.exists())			ruleFile.delete();		FileOutputStream fout=new FileOutputStream(ruleFile);		PrintWriter pWriter=new PrintWriter(fout);		pWriter.println("ID3分類規則列表:");		for(String s:ruleList)		{			pWriter.println(s);		}		pWriter.close();		for(String s:ruleList)		{			System.out.println(s);		}                System.out.println("結果同時保存到文件\"rule.txt\"中.");	}			/**	 * 判斷所有數據是否屬于同一類	 * @param matrix 數據表	 * @return  此類的標識	 */	private String theSameClass(Matrix matrix)	{		int labelIndex=matrix.width-1;		ArrayList<RowData> rows=matrix.matrix;		String cLabel=rows.get(0).rowdata.get(labelIndex);		for(int i=0;i<rows.size();i++)		{			ArrayList<String> row=rows.get(i).rowdata;			if(!row.get(labelIndex).equals(cLabel))					return null;		}		return cLabel;	}			/**	 * 計算某個主屬性的屬性增益	 * @param col 主屬性	 * @return  屬性增益值	 */	private double entropy(Column col)	{		//TotalTarget totalTargets=new TotalTarget();		//ArrayList<Target> totalList=totalTargets.totalTargets;		ArrayList<Attribute> colAttr=col.attributes;		int totalCount=0;		//屬性增益		double EAttr=0.0;		for(int i=0;i<colAttr.size();i++)		{			Attribute attr=colAttr.get(i);			//數據總項數			totalCount+=attr.counts;		}		for(int i=0;i<colAttr.size();i++)		{			//對每個子屬性計算屬性增益			Attribute attr=colAttr.get(i);			int sC=attr.counts;			ArrayList<Target> tarList=attr.targets;			double inentropy=0.0;			for(int j=0;j<tarList.size();j++)			{				int pC=tarList.get(j).counts;				double p=(double)pC/sC;				inentropy+=p*Math.log(p)/LN2;			}			inentropy=-1*inentropy;			//sc/totalCount屬性增益權重			EAttr+=inentropy*((double)sC/totalCount);		}		return EAttr;	}			/**	 * 由指定的主屬性,篩選某個子屬性,構造新的數據Matrix	 * @param matrix 舊的數據集	 * @param attList 屬性列表	 * @param col_index 主屬性下標	 * @param attr_index 主屬性下的子屬性下標	 * @return 滿足條件的新的數據集	 */	private Matrix buildMatrix(Matrix matrix,AttributesList attList,int col_index,int attr_index)	{		//實際上是實現算法中的在一個test_attribute中取出一個分支的數據		ArrayList<Column> cols=attList.attributes;		ArrayList<Attribute> colAttr=cols.get(col_index).attributes;		Attribute attr=colAttr.get(attr_index);		String label=attr.label;		ArrayList<RowData> oldData=matrix.matrix;		Matrix newMatrix=new Matrix();		ArrayList<RowData> newRowData=newMatrix.matrix;		newMatrix.setWidth(matrix.width-1);		for(int i=0;i<oldData.size();i++)		{			ArrayList<String> row=oldData.get(i).rowdata;			RowData newrowdata=new RowData();			ArrayList<String> newrow=newrowdata.rowdata;			//只選擇具有這個屬性的行			if(row.get(col_index).equals(label))			{				for(int j=0;j<row.size();j++)				{					if(j!=col_index)						newrow.add(row.get(j));				}				newRowData.add(newrowdata);			}		}		return newMatrix;	}			/**         * 根據刪除了主屬性col_index的數據集產生新的屬性列表         * @param theMatrix 數據集         * @param oldattList 舊的屬性列表         * @param col_index 主屬性下標         * @return 新的屬性列表         */	private AttributesList buildAttributesList(Matrix theMatrix,AttributesList oldattList,int col_index)	{            //實際上是構造一個除去test_attribute的attribute_list,即attribute_list-test_attribute            //由于上一步的buildMatrix在生成滿足test_attribute的數據集theMatrix時,同時將test_attribute這一列數據刪除,            //而保持了列之間順序的不變,在這里只需使用舊的列標識從theMatrix中直接生成AttrubutesList		AttributesList attList=new AttributesList();		TotalTarget totalTargets=new TotalTarget();		ArrayList<Target> totalList=totalTargets.totalTargets;		//屬性列集合		ArrayList<Column> newCols=attList.attributes;				ArrayList<Column> oldCols=oldattList.attributes;		for(int i=0;i<oldCols.size();i++)		{			//構造新的列,保留除了要刪除的列之外的舊列的標識			if(i!=col_index)				{					Column col=new Column();					col.label=oldCols.get(i).label;					newCols.add(col);				}		}		//行數		int height=theMatrix.matrix.size();		//列數		int width=theMatrix.width;		//行數據集合		ArrayList<RowData> rows=theMatrix.matrix;		for(int i=0;i<height;i++)		{			totalTargets.totalCount++;			//行數據			ArrayList<String> row=rows.get(i).rowdata;			//類標識,鏈表最后一個元素			String cLabel=row.get(width-1);//			***統計總的類標識計數			int t=0;			for(;t<totalList.size();t++)			{				Target tar=totalList.get(t);				if(tar.label.equals(cLabel))				{					tar.counts++;					break;				}			}			if(t==totalList.size())			{				Target tar=new Target();				tar.label=cLabel;				tar.counts++;				totalList.add(tar);			}						for(int j=0;j<width-1;j++)			{								//每一個屬性列				Column col=newCols.get(j);				ArrayList<Attribute> attCol=col.attributes;				int k=0;				for(;k<attCol.size();k++)				{					Attribute attr=attCol.get(k);					if(attr.label.equals(row.get(j)))					{						attr.counts++;						break;					}				}				//此屬性尚未構造				if(k==attCol.size())				{					Attribute attrib=new Attribute();					ArrayList<Target> tarList=attrib.targets;					attrib.label=row.get(j);					attrib.counts++;					Target targ=new Target();					targ.label=cLabel;					targ.counts++;					tarList.add(targ);					attCol.add(attrib);									}				else				{					Attribute attr=attCol.get(k);					ArrayList<Target> tarList=attr.targets;					int s=0;					for(;s<tarList.size();s++)					{						Target target=tarList.get(s);						if(target.label.equals(cLabel))						{							target.counts++;							break;						}					}					//此類標識尚未構造					if(s==tarList.size())					{						Target targ=new Target();						targ.label=cLabel;						targ.counts++;						tarList.add(targ);					}				}			}		}                //計算區分整個樣本的熵		double inentropy=0.0;		int totalCounts=totalTargets.totalCount;		for(int i=0;i<totalList.size();i++)		{			Target tar=totalList.get(i);			int pCount=tar.counts; //每一類含有的行數			double p=(double)pCount/totalCounts;			inentropy+=p*Math.log(p)/LN2;		}		inentropy=-1*inentropy;		attList.inentropy=inentropy;		attList.rowcounts=theMatrix.matrix.size();				return attList;	}			/**	 * 輸出原始數據表(測試用)	 *	 */	public void showMatrix()	{				Matrix matrix=this.dataSet;		ArrayList<RowData> rowdata=matrix.matrix;						for(int i=0;i<rowdata.size();i++)		{			ArrayList<String> row=rowdata.get(i).rowdata;									for(int j=0;j<row.size();j++)			{				System.out.print(row.get(j)+" ");			}			System.out.println();					}					}			/**	 * 開始構建ID3判定樹	 * @param dataFile 訓練數據文件	 * @param classFile 訓練數據類文件	 * @throws IOException	 */	public void start(File dataFile,File classFile) throws IOException	{		dataSet=ID3.buildMatrix(dataFile,attributeList);		ID3.buildAttribute(classFile, dataSet,attributeList);		root=this.Generate_decision_tree(this.attributeList, this.dataSet, "");	}			/**	 * 從指定節點打印判定樹結構(使用前序遍歷)	 *	 */	public void printTree()	{		printTree(root);	}			/**	 * 打印判定樹結構(使用前序遍歷)	 *	 */	private void printTree(Node t)	{		if(t!=null)		{			System.out.print(t.label+" ");			Node[] childs=t.childs;			if(childs!=null)			{				for(int i=0;i<childs.length;i++)				{					printTree(childs[i]);				}			}			System.out.println();		}	}			/**	 * 由測試數據文件構造測試數據集	 * @param testFile 測試數據文件	 * @param testData 測試數據集	 * @return 測試數據集