from math import log
import pandas as pd
import numpy as np
from matplotlib.font_manager import FontProperties

'''
函数说明：计算信息熵函数
输入：data,计算列名
输出：信息熵
'''
def compute_infoentropy(Dataframe,columns_name):
    data = Dataframe[columns_name]
    data_classify = []
    length = len(data)
    for singledata in data:
        if len(data_classify) == 0:
            data_classify.append([singledata,1])
        else:
            exist = 0
            for i in range(len(data_classify)):
                if data_classify[i][0] == singledata:
                    data_classify[i][1] = data_classify[i][1]+1
                    exist = 1
            if exist == 0:
                data_classify.append([singledata,1])
    infoentropy = 0
    for data_classfy1 in data_classify:
        infoentropy += data_classfy1[1] / length * log(data_classfy1[1] / length,2)
    infoentropy = -infoentropy
    return infoentropy

'''
函数说明：将数据依照某种类型分类
输入：数据，数据分类类型
输出：分类数据
'''

def my_classify(Dataframe,columns_name):
    data = Dataframe[columns_name]
    classify = []
    for singledata in data:
        if singledata not in classify:
            classify.append(singledata)
    return classify

'''
函数说明：计算各类别的信息增益（information gain），并选择信息增益最大的类别，进行相应划分
输入:数据，类别
输出:最大类别
'''
def choose_bestfeature(Dataframe):
    #获取columns_names
    columns_names = list(Dataframe)
    key_name = columns_names[-1]
    columns_names = columns_names[:-1]
    data_count = Dataframe[key_name].count()
    gain_list=[]
    #计算各属性信息增益值
    key_infoentropy = compute_infoentropy(Dataframe,key_name)
    for singlename in columns_names:
        classify = my_classify(Dataframe,singlename)
        dflist = []
        for edata in classify:
            dflist.append(Dataframe[Dataframe[singlename] == edata])
        sum_infoentropy = 0
        for dflist1 in dflist:
            sum_infoentropy += dflist1[key_name].count()/data_count*compute_infoentropy(dflist1,key_name)
        gain_list.append([singlename,key_infoentropy-sum_infoentropy])
    max_gain = ['',0]
    for gain in gain_list:
        if gain[1]>max_gain[1]:
            max_gain=gain
    return max_gain[0]

'''
函数说明：获取当前最大分类的属性
输入：data
输出：特征属性数量占多数的属性
'''
def get_maxproperty(Dataframe):
    my_property = []
    clnname=list(Dataframe)
    for data in Dataframe[clnname[0]]:
        exist = 0
        for i in range(len(my_property)):
            if my_property[i][0] == data:
                my_property[i][1] += 1
                exist = 1
        if exist == 0:
            my_property.append([data,1])
    max_p=['',0]
    for my_property1 in my_property:
        if my_property1[1]>max_p[1]:
            max_p[0]=my_property1[0]
    return max_p[0]

'''
函数说明：决策树主函数
输入：数据集
输出：字典形式的决策树
'''
def mydescion_tree(Dataframe,feature):
    key_featlist = Dataframe.iloc[:,-1]
    if key_featlist.loc[key_featlist == key_featlist.iloc[0]].count() == key_featlist.count():         #如果分类相同，则取该分类，iloc很重要，去掉iloc即为index索引，是不对的
        return key_featlist.iloc[0]
    if Dataframe.shape[1] == 1:                                                                        #如果只剩下一列数据（即分到了最后一类特征），那么取分类占多数的分类
        return get_maxproperty(Dataframe)
    bestfeature = choose_bestfeature(Dataframe)                                                        #找出当前最佳特征
    feature.append(bestfeature)
    tree = {bestfeature : {}}                                                                          #创建节点用的
    classify = my_classify(Dataframe,bestfeature)                                                      #找出当前最佳特征共有几种属性
    for classify1 in classify:                                                                         #遍历当前特征的属性
        # 递归，后面dataframe是获取特征等于当前属性的dataframe后并删除当前最佳特征，因为已经分过类了，进入递归。
        tree[bestfeature][classify1] = mydescion_tree(Dataframe[Dataframe[bestfeature]==classify1].drop([bestfeature],axis=1),feature)
    return tree










#测试数据
df1 = pd.read_excel('西瓜数据.xlsx',engine='openpyxl')
df1 = df1.iloc[:,1:]
tree = mydescion_tree(df1,feature=[])
print(tree)