from numpy import *
from scipy import *
from math import log
import operator

#計算給定數據的香濃熵：
def calcShannonEnt(dataSet):
 numEntries = len(dataSet) 
 labelCounts = {} #類別字典（類別的名稱為鍵，該類別的個數為值）
 for featVec in dataSet:
  currentLabel = featVec[-1] 
  if currentLabel not in labelCounts.keys(): #還沒添加到字典里的類型
   labelCounts[currentLabel] = 0;
  labelCounts[currentLabel] += 1;
 shannonEnt = 0.0 
 for key in labelCounts: #求出每種類型的熵
  prob = float(labelCounts[key])/numEntries #每種類型個數占所有的比值
  shannonEnt -= prob * log(prob, 2)
 return shannonEnt; #返回熵

#按照給定的特征劃分數據集
def splitDataSet(dataSet, axis, value):
 retDataSet = [] 
 for featVec in dataSet: #按dataSet矩陣中的第axis列的值等于value的分數據集
  if featVec[axis] == value:  #值等于value的，每一行為新的列表（去除第axis個數據）
   reducedFeatVec = featVec[:axis]
   reducedFeatVec.extend(featVec[axis+1:]) 
   retDataSet.append(reducedFeatVec) 
 return retDataSet #返回分類后的新矩陣

#選擇最好的數據集劃分方式
def chooseBestFeatureToSplit(dataSet): 
 numFeatures = len(dataSet[0])-1 #求屬性的個數
 baseEntropy = calcShannonEnt(dataSet)
 bestInfoGain = 0.0; bestFeature = -1 
 for i in range(numFeatures): #求所有屬性的信息增益
  featList = [example[i] for example in dataSet] 
  uniqueVals = set(featList) #第i列屬性的取值（不同值）數集合
  newEntropy = 0.0 
  splitInfo = 0.0;
  for value in uniqueVals: #求第i列屬性每個不同值的熵*他們的概率
   subDataSet = splitDataSet(dataSet, i , value) 
   prob = len(subDataSet)/float(len(dataSet)) #求出該值在i列屬性中的概率
   newEntropy += prob * calcShannonEnt(subDataSet) #求i列屬性各值對于的熵求和
   splitInfo -= prob * log(prob, 2);
  infoGain = (baseEntropy - newEntropy) / splitInfo; #求出第i列屬性的信息增益率
  print infoGain; 
  if(infoGain > bestInfoGain): #保存信息增益率最大的信息增益率值以及所在的下表（列值i）
   bestInfoGain = infoGain 
   bestFeature = i 
 return bestFeature 

#找出出現次數最多的分類名稱
def majorityCnt(classList): 
 classCount = {} 
 for vote in classList: 
  if vote not in classCount.keys(): classCount[vote] = 0 
  classCount[vote] += 1 
 sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse=True)
 return sortedClassCount[0][0] 

#創建樹
def createTree(dataSet, labels): 
 classList = [example[-1] for example in dataSet]; #創建需要創建樹的訓練數據的結果列表（例如最外層的列表是[N, N, Y, Y, Y, N, Y]）
 if classList.count(classList[0]) == len(classList): #如果所有的訓練數據都是屬于一個類別，則返回該類別
  return classList[0]; 
 if (len(dataSet[0]) == 1): #訓練數據只給出類別數據（沒給任何屬性值數據），返回出現次數最多的分類名稱
  return majorityCnt(classList);

 bestFeat = chooseBestFeatureToSplit(dataSet); #選擇信息增益最大的屬性進行分（返回值是屬性類型列表的下標）
 bestFeatLabel = labels[bestFeat] #根據下表找屬性名稱當樹的根節點
 myTree = {bestFeatLabel:{}} #以bestFeatLabel為根節點建一個空樹
 del(labels[bestFeat]) #從屬性列表中刪掉已經被選出來當根節點的屬性
 featValues = [example[bestFeat] for example in dataSet] #找出該屬性所有訓練數據的值（創建列表）
 uniqueVals = set(featValues) #求出該屬性的所有值得集合（集合的元素不能重復）
 for value in uniqueVals: #根據該屬性的值求樹的各個分支
  subLabels = labels[:] 
  myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) #根據各個分支遞歸創建樹
 return myTree #生成的樹

#實用決策樹進行分類
def classify(inputTree, featLabels, testVec): 
 firstStr = inputTree.keys()[0] 
 secondDict = inputTree[firstStr] 
 featIndex = featLabels.index(firstStr) 
 for key in secondDict.keys(): 
  if testVec[featIndex] == key: 
   if type(secondDict[key]).__name__ == 'dict': 
    classLabel = classify(secondDict[key], featLabels, testVec) 
   else: classLabel = secondDict[key] 
 return classLabel 

#讀取數據文檔中的訓練數據（生成二維列表）
def createTrainData():
 lines_set = open('../data/ID3/Dataset.txt').readlines()
 labelLine = lines_set[2];
 labels = labelLine.strip().split()
 lines_set = lines_set[4:11]
 dataSet = [];
 for line in lines_set:
  data = line.split();
  dataSet.append(data);
 return dataSet, labels


#讀取數據文檔中的測試數據（生成二維列表）
def createTestData():
 lines_set = open('../data/ID3/Dataset.txt').readlines()
 lines_set = lines_set[15:22]
 dataSet = [];
 for line in lines_set:
  data = line.strip().split();
  dataSet.append(data);
 return dataSet

myDat, labels = createTrainData() 
myTree = createTree(myDat,labels) 
print myTree
bootList = ['outlook','temperature', 'humidity', 'windy'];
testList = createTestData();
for testData in testList:
 dic = classify(myTree, bootList, testData)
 print dic
          

            
訓練集:

 outlook temperature humidity windy 
 ---------------------------------------------------------
 sunny  hot    high   false   N
 sunny  hot    high   true   N
 overcast hot    high   false   Y
 rain  mild   high   false   Y
 rain  cool   normal  false   Y
 rain  cool   normal  true   N
 overcast cool   normal  true   Y

測試集
 outlook temperature humidity windy 
 -----------------------------------------------  
 sunny  mild   high   false   
 sunny  cool   normal  false   
 rain   mild   normal  false  
 sunny  mild   normal  true   
 overcast mild   high   true   
 overcast hot    normal  false   
 rain   mild   high   true