#coding :utf-8
'''
2017.6.26 author :Erin 
     function: "decesion tree" ID3
     
'''
import numpy as np
import pandas as pd
from math import log
import operator 
import random
def load_data():
  
  red = [line.strip().split(';') for line in open('e:/a/winequality-red.csv')]
  white = [line.strip().split(';') for line in open('e:/a/winequality-white.csv')]
  data=red+white
  random.shuffle(data) #打亂data
  x_train=data[:800]
  x_test=data[800:]
  
  features=['fixed','volatile','citric','residual','chlorides','free','total','density','pH','sulphates','alcohol','quality']
  return x_train,x_test,features
 
def cal_entropy(dataSet):
 
  
  numEntries = len(dataSet)
  labelCounts = {}
  for featVec in dataSet:
    label = featVec[-1]
    if label not in labelCounts.keys():
      labelCounts[label] = 0
    labelCounts[label] += 1
  entropy = 0.0
  for key in labelCounts.keys():
    p_i = float(labelCounts[key]/numEntries)
    entropy -= p_i * log(p_i,2)#log(x,10)表示以10 為底的對(duì)數(shù)
  return entropy
 
def split_data(data,feature_index,value):
  '''
  劃分?jǐn)?shù)據(jù)集
  feature_index：用于劃分特征的列數(shù)，例如“年齡”
  value:劃分后的屬性值：例如“青少年”
  '''
  data_split=[]#劃分后的數(shù)據(jù)集
  for feature in data:
    if feature[feature_index]==value:
      reFeature=feature[:feature_index]
      reFeature.extend(feature[feature_index+1:])
      data_split.append(reFeature)
  return data_split
def choose_best_to_split(data):
  
  '''
  根據(jù)每個(gè)特征的信息增益，選擇最大的劃分?jǐn)?shù)據(jù)集的索引特征
  '''
  
  count_feature=len(data[0])-1#特征個(gè)數(shù)4
  #print(count_feature)#4
  entropy=cal_entropy(data)#原數(shù)據(jù)總的信息熵
  #print(entropy)#0.9402859586706309
  
  max_info_gain=0.0#信息增益最大
  split_fea_index = -1#信息增益最大，對(duì)應(yīng)的索引號(hào)
 
  for i in range(count_feature):
    
    feature_list=[fe_index[i] for fe_index in data]#獲取該列所有特征值
    #######################################
 
    # print(feature_list)
    unqval=set(feature_list)#去除重復(fù)
    Pro_entropy=0.0#特征的熵
    for value in unqval:#遍歷改特征下的所有屬性
      sub_data=split_data(data,i,value)
      pro=len(sub_data)/float(len(data))
      Pro_entropy+=pro*cal_entropy(sub_data)
      #print(Pro_entropy)
      
    info_gain=entropy-Pro_entropy
    if(info_gain>max_info_gain):
      max_info_gain=info_gain
      split_fea_index=i
  return split_fea_index
    
    
##################################################
def most_occur_label(labels):
  #sorted_label_count[0][0] 次數(shù)最多的類(lèi)標(biāo)簽
  label_count={}
  for label in labels:
    if label not in label_count.keys():
      label_count[label]=0
    else:
      label_count[label]+=1
    sorted_label_count = sorted(label_count.items(),key = operator.itemgetter(1),reverse = True)
  return sorted_label_count[0][0]
def build_decesion_tree(dataSet,featnames):
  '''
  字典的鍵存放節(jié)點(diǎn)信息，分支及葉子節(jié)點(diǎn)存放值
  '''
  featname = featnames[:]       ################
  classlist = [featvec[-1] for featvec in dataSet] #此節(jié)點(diǎn)的分類(lèi)情況
  if classlist.count(classlist[0]) == len(classlist): #全部屬于一類(lèi)
    return classlist[0]
  if len(dataSet[0]) == 1:     #分完了,沒(méi)有屬性了
    return Vote(classlist)    #少數(shù)服從多數(shù)
  # 選擇一個(gè)最優(yōu)特征進(jìn)行劃分
  bestFeat = choose_best_to_split(dataSet)
  bestFeatname = featname[bestFeat]
  del(featname[bestFeat])   #防止下標(biāo)不準(zhǔn)
  DecisionTree = {bestFeatname:{}}
  # 創(chuàng)建分支,先找出所有屬性值,即分支數(shù)
  allvalue = [vec[bestFeat] for vec in dataSet]
  specvalue = sorted(list(set(allvalue))) #使有一定順序
  for v in specvalue:
    copyfeatname = featname[:]
    DecisionTree[bestFeatname][v] = build_decesion_tree(split_data(dataSet,bestFeat,v),copyfeatname)
  return DecisionTree
 
def classify(Tree, featnames, X):
  classLabel=''
  root = list(Tree.keys())[0]
  firstDict = Tree[root]
  featindex = featnames.index(root) #根節(jié)點(diǎn)的屬性下標(biāo)
  #classLabel='0'
  for key in firstDict.keys():  #根屬性的取值,取哪個(gè)就走往哪顆子樹(shù)
    if X[featindex] == key:
      if type(firstDict[key]) == type({}):
        classLabel = classify(firstDict[key],featnames,X)
      else:
        classLabel = firstDict[key]
  return classLabel
 
  
if __name__ == '__main__':
  x_train,x_test,features=load_data()
  split_fea_index=choose_best_to_split(x_train)
  newtree=build_decesion_tree(x_train,features)
  #print(newtree)
  #classLabel=classify(newtree, features, ['7.4','0.66','0','1.8','0.075','13','40','0.9978','3.51','0.56','9.4','5'] )
  #print(classLabel)
  
  count=0
  for test in x_test:
    label=classify(newtree, features,test)
    
    if(label==test[-1]):
      count=count+1
  acucy=float(count/len(x_test))
  print(acucy)