# -*- coding: utf-8 -*-
__author__ = 'zhihua_oba'

import operator
from numpy import *
from math import log

#文件讀取
def file2matrix(filename, attribute_num): #傳入?yún)?shù)：文件名，屬性個(gè)數(shù)
 fr = open(filename)
 arrayOLines = fr.readlines()
 numberOfLines = len(arrayOLines) #統(tǒng)計(jì)數(shù)據(jù)集行數(shù)（樣本個(gè)數(shù)）
 dataMat = zeros((numberOfLines, attribute_num))
 classLabelVector = [] #分類(lèi)標(biāo)簽
 index = 0
 for line in arrayOLines:
  line = line.strip() #strip() 刪除字符串中的'\n'
  listFromLine = line.split() #將一個(gè)字符串分裂成多個(gè)字符串組成的列表，不帶參數(shù)時(shí)以空格進(jìn)行分割，當(dāng)代參數(shù)時(shí)，以該參數(shù)進(jìn)行分割
  dataMat[index, : ] = listFromLine[0:attribute_num] #讀取數(shù)據(jù)對(duì)象屬性值
  classLabelVector.append(listFromLine[-1]) #讀取分類(lèi)信息
  index += 1
 dataSet = [] #數(shù)組轉(zhuǎn)化成列表
 index = 0
 for index in range(0, numberOfLines):
  temp = list(dataMat[index, :])
  temp.append(classLabelVector[index])
  dataSet.append(temp)
 return dataSet

#劃分?jǐn)?shù)據(jù)集
def splitDataSet(dataSet, axis, value):
 retDataSet = []
 for featvec in dataSet: #每行
  if featvec[axis] == value: #每行中第axis個(gè)元素和value相等 #刪除對(duì)應(yīng)的元素，并將此行，加入到rerDataSet
   reducedFeatVec = featvec[:axis]
   reducedFeatVec.extend(featvec[axis+1:])
   retDataSet.append(reducedFeatVec)
 return retDataSet

#計(jì)算香農(nóng)熵 #計(jì)算數(shù)據(jù)集的香農(nóng)熵 == 計(jì)算數(shù)據(jù)集類(lèi)標(biāo)簽的香農(nóng)熵
def calcShannonEnt(dataSet):
 numEntries = len(dataSet) #數(shù)據(jù)集樣本點(diǎn)個(gè)數(shù)
 labelCounts = {} #類(lèi)標(biāo)簽
 for featVec in dataSet: #統(tǒng)計(jì)數(shù)據(jù)集類(lèi)標(biāo)簽的個(gè)數(shù)，字典形式
  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

#根據(jù)香農(nóng)熵，選擇最優(yōu)的劃分方式 #根據(jù)某一屬性劃分后，類(lèi)標(biāo)簽香農(nóng)熵越低，效果越好
def chooseBestFeatureToSplit(dataSet):
 baseEntropy = calcShannonEnt(dataSet) #計(jì)算數(shù)據(jù)集的香農(nóng)熵
 numFeatures = len(dataSet[0])-1
 bestInfoGain = 0.0 #最大信息增益
 bestFeature = 0 #最優(yōu)特征
 for i in range(0, numFeatures):
  featList = [example[i] for example in dataSet] #所有子列表（每行）的第i個(gè)元素，組成一個(gè)新的列表
  uniqueVals = set(featList)
  newEntorpy = 0.0
  for value in uniqueVals: #數(shù)據(jù)集根據(jù)第i個(gè)屬性進(jìn)行劃分，計(jì)算劃分后數(shù)據(jù)集的香農(nóng)熵
   subDataSet = splitDataSet(dataSet, i, value)
   prob = len(subDataSet)/float(len(dataSet))
   newEntorpy += prob*calcShannonEnt(subDataSet)
  infoGain = baseEntropy-newEntorpy #劃分后的數(shù)據(jù)集，香農(nóng)熵越小越好，即信息增益越大越好
  if(infoGain > bestInfoGain):
   bestInfoGain = infoGain
   bestFeature = i
 return bestFeature

#如果數(shù)據(jù)集已經(jīng)處理了所有屬性，但葉子結(jié)點(diǎn)中類(lèi)標(biāo)簽依然不是唯一的，此時(shí)需要決定如何定義該葉子結(jié)點(diǎn)。這種情況下，采用多數(shù)表決方法，對(duì)該葉子結(jié)點(diǎn)進(jìn)行分類(lèi)
def majorityCnt(classList): #傳入?yún)?shù)：葉子結(jié)點(diǎn)中的類(lèi)標(biāo)簽
 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]

#創(chuàng)建樹(shù)
def createTree(dataSet, labels): #傳入?yún)?shù)：數(shù)據(jù)集，屬性標(biāo)簽（屬性標(biāo)簽作用：在輸出結(jié)果時(shí)，決策樹(shù)的構(gòu)建更加清晰）
 classList = [example[-1] for example in dataSet] #數(shù)據(jù)集樣本的類(lèi)標(biāo)簽
 if classList.count(classList[0]) == len(classList): #如果數(shù)據(jù)集樣本屬于同一類(lèi)，說(shuō)明該葉子結(jié)點(diǎn)劃分完畢
  return classList[0]
 if len(dataSet[0]) == 1: #如果數(shù)據(jù)集樣本只有一列（該列是類(lèi)標(biāo)簽），說(shuō)明所有屬性都劃分完畢，則根據(jù)多數(shù)表決方法，對(duì)該葉子結(jié)點(diǎn)進(jìn)行分類(lèi)
  return majorityCnt(classList)
 bestFeat = chooseBestFeatureToSplit(dataSet) #根據(jù)香農(nóng)熵，選擇最優(yōu)的劃分方式
 bestFeatLabel = labels[bestFeat] #記錄該屬性標(biāo)簽
 myTree = {bestFeatLabel:{}} #樹(shù)
 del(labels[bestFeat]) #在屬性標(biāo)簽中刪除該屬性
 #根據(jù)最優(yōu)屬性構(gòu)建樹(shù)
 featValues = [example[bestFeat] for example in dataSet]
 uniqueVals = set(featValues)
 for value in uniqueVals:
  subLabels = labels[:]
  subDataSet = splitDataSet(dataSet, bestFeat, value)
  myTree[bestFeatLabel][value] = createTree(subDataSet, subLabels)
 return myTree

#測(cè)試算法：使用決策樹(shù)，對(duì)待分類(lèi)樣本進(jìn)行分類(lèi)
def classify(inputTree, featLabels, testVec): #傳入?yún)?shù)：決策樹(shù)，屬性標(biāo)簽，待分類(lèi)樣本
 firstStr = inputTree.keys()[0] #樹(shù)根代表的屬性
 secondDict = inputTree[firstStr]
 featIndex = featLabels.index(firstStr) #樹(shù)根代表的屬性，所在屬性標(biāo)簽中的位置，即第幾個(gè)屬性
 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 main():
 dataSet = file2matrix('test_sample.txt', 4)
 labels = ['attr01', 'attr02', 'attr03', 'attr04']
 labelsForCreateTree = labels[:]
 Tree = createTree(dataSet, labelsForCreateTree )
 testvec = [2, 3, 2, 3]
 print classify(Tree, labels, testvec)
if __name__ == '__main__':
  main()