''''' 
Created on Jan 30, 2015 
 
@author: 史帥 
''' 
 
from math import log 
import operator 
import re 
 
def fileToDataSet(fileName): 
  ''''' 
  此方法功能是:從文件中讀取樣本集數(shù)據(jù),樣本數(shù)據(jù)的格式為:數(shù)據(jù)以空白字符分割,最后一列為類標簽 
     
    參數(shù): 
      fileName:存放樣本集數(shù)據(jù)的文件路徑 
     
    返回值: 
      dataSet:樣本集數(shù)據(jù)組成的二維數(shù)組 
  ''' 
  file=open(fileName, mode='r') 
  lines=file.readlines() 
  dataSet=[] 
  index=0 
  p=re.compile(r"\s+") 
  for line in lines: 
    line=p.split(line.strip()) 
    dataSet.append(line) 
    index+=1 
  return dataSet 
 
def calculateShannonEntropy(dataSet): 
  ''''' 
  此方法功能是:計算樣本集數(shù)據(jù)類別的信息熵,樣本數(shù)據(jù)的格式為二維數(shù)組 
     
    參數(shù): 
      dataSet:樣本集數(shù)據(jù)組成的二維數(shù)組 
     
    返回值: 
      shannonEntropy:樣本集數(shù)據(jù)類別的信息熵 
  ''' 
  dataCount=len(dataSet) 
  classCountDic={} 
  for data in dataSet: 
    label=data[-1] 
    if label not in classCountDic.keys(): 
      classCountDic[label]=0 
    classCountDic[label]+=1 
  shannonEntropy=0.0 
  for key in classCountDic: 
    prob=float(classCountDic[key])/dataCount 
    shannonEntropy-=prob*log(prob,2) 
  return shannonEntropy 
 
def splitDataSet(dataSet,axis,value): 
  ''''' 
  此方法功能是:對樣本集數(shù)據(jù)按照某一特征進行分割,使得分割后的數(shù)據(jù)集中該特征的值全部等于同一個值,并且將分割后的數(shù)據(jù)中該特征列去除 
   
    參數(shù): 
      dataSet:待分割的樣本集數(shù)據(jù),二維數(shù)組 
      axis:特征所在樣本集數(shù)據(jù)列中的位置 
      value:樣本集數(shù)據(jù)分割后該特征的值 
       
    返回值: 
      splitedDataSet:按照所在位置為axis的特征進行分割,并且該特征值為value的樣本集數(shù)據(jù)的子集 
  ''' 
  splitedDataSet=[] 
  for data in dataSet: 
    if data[axis]==value: 
      splitedData=data[:axis] 
      splitedData.extend(data[axis+1:]) 
      splitedDataSet.append(splitedData) 
  return splitedDataSet 
 
def chooseBestFeatureToSlipt(dataSet): 
  ''''' 
  此方法功能是:分別計算整個樣本集數(shù)據(jù)的信息熵與按照各個特征分割后的數(shù)據(jù)集的信息熵之差,得到使差值最大的分割方案,得到該分割方案的特征 
   
    參數(shù): 
      dataSet:待分割的樣本集數(shù)據(jù),二維數(shù)組 
       
    返回值: 
      bestFeature:按照分割前后信息熵差值最大的分割方案得到的特征，返回此特征所在樣本集數(shù)據(jù)列中的位置 
  ''' 
  bestFeature=-1 
  dataSetShannonEntropy=calculateShannonEntropy(dataSet) 
  infoGain=0 
  featureCount=len(dataSet[0])-1 
  for i in range(featureCount): 
    featureList=[example[i] for example in dataSet] 
    featureSet=set(featureList) 
    splitedDataSetShannonEntropy=0 
    for feature in featureSet: 
      splitedDataSet=splitDataSet(dataSet,i,feature) 
      splitedDataSetShannonEntropy+=float(len(splitedDataSet))/len(dataSet)*calculateShannonEntropy(splitedDataSet) 
    if dataSetShannonEntropy-splitedDataSetShannonEntropy>infoGain: 
      infoGain=dataSetShannonEntropy-splitedDataSetShannonEntropy 
      bestFeature=i 
  return bestFeature 
 
def majorityClass(classList): 
  ''''' 
  此方法功能是:從類別列表中得到個數(shù)最多的類別 
   
    參數(shù): 
      classList:類別列表,一維數(shù)組 
       
    返回值: 
      類別列表中個數(shù)最多的類別 
  ''' 
  classCountDic={} 
  for label in classList: 
    if label not in classCountDic.keys(): 
      classCountDic[label]=0 
    classCountDic[label]+=1 
  classCountDic=sorted(classCountDic.item(),key=operator.itemgetter(1),reverse=True) 
  return classCountDic[0][0] 
 
 
def createTree(dataSet,features): 
  ''''' 
  此方法功能是:根據(jù)訓練樣本集數(shù)據(jù)創(chuàng)建對分類最有效的決策樹 
   
    參數(shù): 
      dataSet:訓練樣本集數(shù)據(jù),二維數(shù)組 
      features:與訓練樣本集數(shù)據(jù)中各列的特征值相對應的特征名稱集合,一維數(shù)組 
     
    返回值: 
      tree:根據(jù)訓練樣本集數(shù)據(jù)所創(chuàng)建的，對分類最有效的決策樹 
  ''' 
  subFeatures=features[:] 
  classList=[example[-1] for example in dataSet] 
  if classList.count(classList[0])==len(classList): 
    return classList[0] 
  if len(dataSet[0])==1: 
    return majorityClass(classList) 
  bestFeature=chooseBestFeatureToSlipt(dataSet) 
  label=subFeatures[bestFeature] 
  tree={label:{}} 
  del(subFeatures[bestFeature]) 
  featureList=[example[bestFeature] for example in dataSet] 
  featureSet=set(featureList) 
  for feature in featureSet: 
    splitedDataSet=splitDataSet(dataSet,bestFeature,feature) 
    tree[label][feature]=createTree(splitedDataSet, subFeatures) 
  return tree 
   
def classify(inX,tree,features): 
  ''''' 
  此方法功能是:根據(jù)創(chuàng)建好的決策樹,對特定的數(shù)據(jù)進行分類 
   
    參數(shù): 
      inX:待分類的數(shù)據(jù),特征值向量,一維數(shù)組 
      tree:根據(jù)決策樹算法創(chuàng)建好的最有效的決策樹 
      features:與訓練樣本集數(shù)據(jù)中各列的特征值相對應的特征名稱集合,一維數(shù)組 
       
    返回值: 
      label:待分類的數(shù)據(jù)通過決策樹分類之后的類別 
  ''' 
  feature=list(tree.keys())[0] 
  featureIndex=features.index(feature) 
  secondTree=tree[feature][inX[featureIndex]] 
  if type(secondTree).__name__=="dict": 
    label=classify(inX,secondTree,features) 
  else: 
    label=secondTree 
  return label