ID3
    image.png
    CSDN包含代码、可视化等:https://blog.csdn.net/asialee_bird/article/details/81118245?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165577243116781432948069%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165577243116781432948069&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-81118245-null-null.142^v18^rank_v32,157^v15^new_3&utm_term=ID3&spm=1018.2226.3001.4187
    image.png

    1. from math import log
    2. import operator
    4. def calcShannonEnt(dataSet):  # 计算数据的熵(entropy)
    5.     numEntries=len(dataSet)  # 数据条数
    6.     labelCounts={}
    7.     for featVec in dataSet:
    8.         currentLabel=featVec[-1] # 每行数据的最后一个字（类别）
    9.         if currentLabel not in labelCounts.keys():
    10.             labelCounts[currentLabel]=0
    11.         labelCounts[currentLabel]+=1  # 统计有多少个类以及每个类的数量
    12.     shannonEnt=0
    13.     for key in labelCounts:
    14.         prob=float(labelCounts[key])/numEntries # 计算单个类的熵值
    15.         shannonEnt-=prob*log(prob,2) # 累加每个类的熵值
    16.     return shannonEnt
    18. def createDataSet1():    # 创造示例数据
    19.     dataSet = [['长', '粗', '男'],
    20.                ['短', '粗', '男'],
    21.                ['短', '粗', '男'],
    22.                ['长', '细', '女'],
    23.                ['短', '细', '女'],
    24.                ['短', '粗', '女'],
    25.                ['长', '粗', '女'],
    26.                ['长', '粗', '女']]
    27.     labels = ['头发','声音']  #两个特征
    28.     return dataSet,labels
    30. def splitDataSet(dataSet,axis,value): # 按某个特征分类后的数据
    31.     retDataSet=[]
    32.     for featVec in dataSet:
    33.         if featVec[axis]==value:
    34.             reducedFeatVec =featVec[:axis]
    35.             reducedFeatVec.extend(featVec[axis+1:])
    36.             retDataSet.append(reducedFeatVec)
    37.     return retDataSet
    39. def chooseBestFeatureToSplit(dataSet):  # 选择最优的分类特征
    40.     numFeatures = len(dataSet[0])-1
    41.     baseEntropy = calcShannonEnt(dataSet)  # 原始的熵
    42.     bestInfoGain = 0
    43.     bestFeature = -1
    44.     for i in range(numFeatures):
    45.         featList = [example[i] for example in dataSet]
    46.         uniqueVals = set(featList)
    47.         newEntropy = 0
    48.         for value in uniqueVals:
    49.             subDataSet = splitDataSet(dataSet,i,value)
    50.             prob =len(subDataSet)/float(len(dataSet))
    51.             newEntropy +=prob*calcShannonEnt(subDataSet)  # 按特征分类后的熵
    52.         infoGain = baseEntropy - newEntropy  # 原始熵与按特征分类后的熵的差值
    53.         if (infoGain>bestInfoGain):   # 若按某特征划分后，熵值减少的最大，则次特征为最优分类特征
    54.             bestInfoGain=infoGain
    55.             bestFeature = i
    56.     return bestFeature
    58. def majorityCnt(classList):    #按分类后类别数量排序，比如：最后分类为2男1女，则判定为男；
    59.     classCount={}
    60.     for vote in classList:
    61.         if vote not in classCount.keys():
    62.             classCount[vote]=0
    63.         classCount[vote]+=1
    64.     sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    65.     return sortedClassCount[0][0]
    67. def createTree(dataSet,labels):
    68.     classList=[example[-1] for example in dataSet]  # 类别：男或女
    69.     if classList.count(classList[0])==len(classList):
    70.         return classList[0]
    71.     if len(dataSet[0])==1:
    72.         return majorityCnt(classList)
    73.     bestFeat=chooseBestFeatureToSplit(dataSet) #选择最优特征
    74.     bestFeatLabel=labels[bestFeat]
    75.     myTree={bestFeatLabel:{}} #分类结果以字典形式保存
    76.     del(labels[bestFeat])
    77.     featValues=[example[bestFeat] for example in dataSet]
    78.     uniqueVals=set(featValues)
    79.     for value in uniqueVals:
    80.         subLabels=labels[:]
    81.         myTree[bestFeatLabel][value]=createTree(splitDataSet\
    82.                             (dataSet,bestFeat,value),subLabels)
    83.     return myTree
    86. if __name__=='__main__':
    87.     dataSet, labels=createDataSet1()  # 创造示列数据
    88.     print(createTree(dataSet, labels))  # 输出决策树模型结果