写在前面

刚开始学习机器学习，深度学习这一块，觉得有必要动手写一下，当然python里面已经有很成熟的包可以做到这些事情，我主要是了解其中的原理，参考了别人的文章https://blog.csdn.net/csqazwsxedc/article/details/65697652，例子使用也是该文章中的，主要是在写法上有一些自己的改变。
附上我的女神：

ID3算法的决策树的实现–python

几个基础的概念

• 信息熵或者熵

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个有限的离散随机变量，其概率分布为
$$P(X=x_i)=p_i,i=1,2,...,n$$

则随机变量X的熵定义
H(X)= $$-\sum _{i=1}^n(P_{i}log{P}_i)$$

接下来定义一个函数用来计算一组数据的信息熵

import math
def Entropy(data):
    #首先计算数据中的类别
    symbols = len(set(data))
    length = len(data)
    #计算单个类别的熵并进行累加
    result = 0
    for item in set(data):
        e = -(data.count(item)/length*math.log10(data.count(item)/length))
        result=result + e
    return result
        

实验一下

test_data = [1,1,1,2,2,2,2,2]
test_data2 = [1,1,1,1,1,1,1,1]
print(Entropy(test_data),Entropy(test_data2))

0.28731326376205846 0.0

用python实现一个实例

头发	声音	性别
长	粗	男
短	粗	男
短	粗	男
长	细	女
短	细	女
短	粗	女
长	粗	女
长	粗	女

• 面临的第一个问题是选择哪一个特征用作根节点，这里就要用到我们的信息熵；如果在使用某个特征进行分类后获得信息熵的增益最多，那么我们就使用哪一个特征作为根节点，针对该问题又以下两种方法

1. 以头发作为根节点（长：1男3女，短：2男2女）

2. 以声音作为根节点（粗：3男3女，细：2女）
   
   现在开始编写相应的代码

3. 创建数据

import pandas as pd
import math
#在这里将数据类型定义为padas的dataframe类型，因为这种类型对于数据的行列操作更为方便
def createDataSet1():    # 创造示例数据
    dataSet = pd.DataFrame({'头发':list("长短短长短短长长"),
                           '声音':list("粗粗粗细细粗粗粗"),
                           '性别':list("男男男女女女女女")})
    return dataSet
#做几个测试
dataSet=createDataSet1()
print(dataSet)
#数据的行数
print(len(dataSet))
#如何将某一列转为list
print(dataSet.iloc[:,-1].values.tolist())
#根据某一条件进行数据的提取 ，这里提取所有长头发的数据
print(dataSet.loc[dataSet.loc[:,"头发"].values=="长",:])
#获第一到倒数第二列，因为最后一列是我们的分类。前面的列是feature，
print(dataSet.columns.values[0:-1])
print(set(dataSet.loc[:,"头发"].values.tolist()))

      头发 声音 性别
    0  长  粗  男
    1  短  粗  男
    2  短  粗  男
    3  长  细  女
    4  短  细  女
    5  短  粗  女
    6  长  粗  女
    7  长  粗  女
    8
    ['男', '男', '男', '女', '女', '女', '女', '女']
      头发 声音 性别
    0  长  粗  男
    3  长  细  女
    6  长  粗  女
    7  长  粗  女
    ['头发' '声音']
    {'长', '短'}

2. 定义一个函数用来计算数据的熵

def calculateEntropy(dataSet):
    #获取数据的长度
    dataItems = len(dataSet)
    #获取数据的原始分类结果，默认最后一列为lable
    allLable = dataSet.iloc[:,-1].values.tolist()
    LableKinds = set(allLable)
    Entropy = 0
    for item in LableKinds:
        e = -(allLable.count(item)/dataItems*math.log10(allLable.count(item)/dataItems))
        Entropy = Entropy + e
    return Entropy
print(calculateEntropy(dataSet))

    0.28731326376205846

3. 根据某一属性值划分数据集并获取划分后的数据集

def splitDataSet(dataSet,feature,value):
    #将数据按照feature拆分，value，表示某个feature的特征
    newDataSete = dataSet.loc[dataSet.loc[:,feature].values == value,:]
    #在使用每一个feature进行分支之后，得到的新数据集中将不再包含已经被使用过的Feature
    newDataSete = newDataSete.drop(columns = feature)
    return newDataSete
newDataSete = splitDataSet(dataSet,"头发","长")
#测试一下
print(newDataSete.shape[])
print(splitDataSet(dataSet,"头发","短"))
print(splitDataSet(dataSet,"头发","长"))
print(splitDataSet(newDataSete,"声音","粗").iloc[:,-1].values.tolist())

    (4, 2)
      声音 性别
    1  粗  男
    2  粗  男
    4  细  女
    5  粗  女
      声音 性别
    0  粗  男
    3  细  女
    6  粗  女
    7  粗  女
    ['男', '女', '女']
    

4. 通过计算信息熵增益选取最好的分类特征

def chooseBestFeatureTosplit(dataSet):
    #计算数据的原始Entropy
    rawEntropy = calculateEntropy(dataSet)
    #获取新的数据集
    #首先按照featue进行分类
    #获取feature
    allFeature = dataSet.columns.values[0:-1]
    if len(allFeature) == 0:
        print("warnings: allFeature=0")
    for feature in allFeature:
        #获取该feature的各个特征
        allKinds = set(dataSet.loc[:,feature].values.tolist())
        bestFeature = feature
        rawinformationGain = 0
        singelFeatureEntroy = 0
        for value in allKinds:
            #按照特征进行数据拆分
            newdataSet = splitDataSet(dataSet,feature,value)
            #计算Entropy
            ratio = len(newdataSet)/float(len(dataSet))
            En = ratio*calculateEntropy(newdataSet)
            singelFeatureEntroy +=  En
        #计算信息熵增益
        informationGain = rawEntropy - singelFeatureEntroy
        #如果新的增益大于原始增益，则最优的特征为当前特征，否则为上一次循环的特征
        if (informationGain > rawinformationGain):
            bestFeature = feature
            rawinformationGain = informationGain
    return bestFeature
print(chooseBestFeatureTosplit(dataSet))

    声音

5. 构建决策树，需要确定树的分支在什么时候停止，以及停止之后如何获得决策结果

   • 第一种情况是已经处理完了所有的feature，但是类标签依旧不是唯一的，此时一般采用多数表决法
   • 第二种情况是每个分支下的所有对象都属于相同的分类，如果所有的实例都属于相同分类，则得到一个叶子节点或者终止快。

   5.1 定义一个多数表决函数

import operator
def moremajorityVote(classList):
    classCount = {}
    for item in classList:
        if item not in classCount.keys():
            classCount[item] = 1
        else:
            classCount[item] += 1
#这里是使用sorted对字典依照其values进行排序，采用降序的方法。则第一个值为最大值
    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]
print(moremajorityVote([1,1,1,2,1,1,1,2,3,4,4,4,4,4,4,4,4]))

    4

5.2 定义一个创建决策树的递归函数

这里使用递归函数进行决策树的计算，第一次使用这种写法，绕了好一会儿，太笨了。。。

def createTree(dataSet):
    #在本函数中 每进行一次特征的迭代计算，则从原数据集中删掉该特征
    #获取数据的分类结果target，我们的分类结果是数据集的最后一列
    targets = dataSet.iloc[:,-1].values.tolist()
    #接下来设置分支停止的条件，在分支停止时，返回当前条件下的分类结果
    #第一种条件，划分后的数据全部属于一个分类
    if targets.count(targets[0]) == len(targets):
        return targets[0]
    # 此时以及是最后一个特征，也就是说此时的数据只剩下最后一列，也就是分类列，这时进行多数表决
    if dataSet.shape[1] == 1 :
        return moremajorityVote(dataSet.iloc[:,0].values.tolist())
    #创建树
    
    #获取最佳的分类特征
    BestFeatures = chooseBestFeatureTosplit(dataSet)
    print(BestFeatures)
    myTree = {BestFeatures:{}}
    #获得本次迭代中的最优分类特征后，获取本特征有几种类型
    featureValuesKind = set(dataSet.loc[:,BestFeatures].values.tolist())
    #这里使用的时一个递归函数，由于基础比较差，在这一块废了一些力气，这也是我第一次使用递归的方法
    for value in featureValuesKind:
        print(value)
        myTree[BestFeatures][value] = createTree(splitDataSet(dataSet,BestFeatures,value))
    return myTree
print(createTree(dataSet))

    1
      头发 声音 性别
    0  长  粗  男
    1  短  粗  男
    2  短  粗  男
    3  长  细  女
    4  短  细  女
    5  短  粗  女
    6  长  粗  女
    7  长  粗  女
    声音
    粗
    1
      头发 性别
    0  长  男
    1  短  男
    2  短  男
    5  短  女
    6  长  女
    7  长  女
    头发
    长
    1
      性别
    0  男
    6  女
    7  女
    短
    1
      性别
    1  男
    2  男
    5  女
    细
    1
      头发 性别
    3  长  女
    4  短  女
    {'声音': {'粗': {'头发': {'长': '女', '短': '男'}}, '细': '女'}}

女神结尾：