1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
from math import log


def calcShannonEnt(dataSet):
    '''
    计算给定数据集的熵
    :param dataSet:
    :return:
    '''
    # 1、根据频率计算概率：先计算数据集中每个类别出现的次数，存在字典中
    num = len(dataSet)
    dataDict = {}
    for data in dataSet:
        label = data[-1]
        if label not in dataDict.keys():
            dataDict[label] = 0
        dataDict[label] += 1
    # 2、根据上面计算的频率，计算熵
    shannonEnt = 0.0
    for key in dataDict.keys():
        p = dataDict[key] / float(num)
        shannonEnt += p * log(p, 2)
    return -shannonEnt


def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels


def splitDataSet(dataSet, axis, value):
    '''
    根据axis=value划分数据集，将axis=value的数据划分出来返回。
    :param dataSet:
    :param axis:
    :param value:
    :return:
    '''
    retDataSet = []
    for data in dataSet:
        if data[axis] == value:
            reducedata = data[:axis]
            reducedata.extend(data[axis + 1:])
            retDataSet.append(reducedata)
    return retDataSet


def chooseBestFeatureTopSplit(dataSet):
    '''
    选择最好的数据集划分方法，
    先使用每个特征和特征取值进行划分，然后计算每个划分的熵
    :param dataSet:
    :return:
    '''
    numfeature = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestFeature = -1
    bestInfoGain = 0.0
    for i in range(numfeature):
        # 1、要获取每个特征的取值
        featureList = [line[i] for line in dataSet]
        featureList = list(set(featureList))
        # 2、对每个特征的每个取值进行划分数据集然后分别计算熵，然后保留与原始熵差最大的，--特征以及其取值进行返回
        for feaValue in featureList:
            # 划分数据集
            dataSetSplit = splitDataSet(dataSet, i, feaValue)
            # 计算新的熵
            entropy = calcShannonEnt(dataSetSplit)
            if bestInfoGain < (baseEntropy - entropy):
                bestInfoGain = baseEntropy - entropy
                bestFeature = i
        return bestFeature


def maxClassNum(classList):
    '''
    计算当前划分后的数据集的类别标签中各个类别的数目，返回最大类别数目的
    :param classList:
    :return: 类别数最多的类别的数目
    '''
    classDict = {}
    for i in classList:
        if i not in classDict.keys():
            classDict[i] = 0
        classDict[i] += 1
    sortedclassDict = sorted(classDict.items(), lambda x: x[1], reverse=True)
    return sortedclassDict[0][0]


def createTree(dataSet, labels):
    '''
    构建决策树,递归函数
    :param dataSet:
    :param labels: 数据集中所有特征的标签
    :return:
    '''
    # 1、首先判断递归是否结束
    classList = [temp[-1] for temp in dataSet]
    # 递归结束条件1：划分后的数据集的所有类别都一致
    if classList.count(classList[0]) == len(classList): return classList[0]
    # 递归结束条件2：所有的特征都用完了，这时虽然没有划分结束，但是也只能返回数目组多的类别作为此时的叶子结点
    if len(dataSet[0]) == 1: return maxClassNum(classList)

    # 2、递归没有结束就继续划分
    # 找到最优划分的特征
    bestFeature = chooseBestFeatureTopSplit(dataSet)
    bestFeatureLabel = labels[bestFeature]
    # 根据最优划分特征将数据集进行划分
    tree = {bestFeatureLabel: {}}
    del (labels[bestFeature])
    feaValue = list(set([line[bestFeature] for line in dataSet]))
    for fea in feaValue:
        subLabel = labels[:]
        tree[bestFeatureLabel][fea] = createTree(splitDataSet(dataSet, bestFeature, fea), subLabel)
    return tree


def classfity(traintree, labelList, testVec):
    '''
    使用在训练集上构造的决策树对测试数据进行分类，思想就是根据测试数据的特征取值沿着决策树向下走，直到走到叶子结点
    :param traintree:
    :param labelList:
    :param testVec:
    :return:
    '''
    firstnode = list(traintree.keys())[0]
    print(labelList)
    labelindex = labelList.index(firstnode)
    sideDict = traintree[firstnode].keys()
    for side in sideDict:
        if testVec[labelindex] == side:
            if type(traintree[firstnode][side]).__name__ == 'dict':
                classResult = classfity(traintree[firstnode][side], labelList, testVec)
            else:
                classResult = traintree[firstnode][side]
    return classResult


def storeTree(tree,filename):
    # 将生成的决策树进行序列化，存储到文件中
    import pickle
    fw = open(filename, 'wb')
    pickle.dump(tree, fw)
    return fw.close()


def readTree(filename):
    # 将磁盘上存储的决策树进行反序列化
    import pickle
    fr = open(filename, 'rb')
    pickle.load(fr)


# 按间距中的绿色按钮以运行脚本。
if __name__ == '__main__':
    dataSet, labels = createDataSet()
    print(dataSet)
    print(labels)
    shannonEnt = calcShannonEnt(dataSet)
    print("数据集的熵为", shannonEnt)

    # 测试划分数据集的函数
    # splitdata = splitDataSet(dataSet, 1, 1)
    # print(dataSet)
    # print(splitdata)

    # 测试chooseBestFeatureTopSplit方法
    # bestFeature = chooseBestFeatureTopSplit(dataSet)
    # print('最好的数据集划分特征：', bestFeature)
    # # 计算划分之后的熵
    # dataSetSplit=splitDataSet(dataSet,bestFeature,0)
    # entroySplit=calcShannonEnt(dataSetSplit)
    # print("划分之后的熵为：",entroySplit)

    tree = createTree(dataSet, labels)
    print(tree)
    # 测试分类函数
    dataSet, labels = createDataSet()
    classres = classfity(tree, labels, [0, 0])
    print(classres)

    # 将决策树进行序列化
    filename='./decisionTree.txt'
    # storeTree(tree,filename)

    # 将磁盘中存储的决策树进行反序列化，
    tree_read=readTree(filename)
    classres = classfity(tree, labels, [0, 0])
    print(classres)