机器学习技法实现------决策树

写在前面

决策树博客

ID3 实现

因为决策树的创建是递归的形式 所以整个创建过程符合传统递归算法的套路 即 递归返回条件 递归切分条件 递归过程
首先递归返回条件：

1. 当输入训练样本的label完全属于同一类时 返回树的叶子节点，返回值为该类别值
2. 当输入样本的特征均已被遍历过一次（每次生成树的时候选取一个信息增益最大的特征 按照该特征不同取值将 训练样本分为不同是subsamples，每遍历一个特征 在生成的subsamples中将该特征去除）则返回树的叶子节点，返回值为数据中类别占比最大的类别
3. 当所有特征中最大信息增益值小于设定的最小信息增益的时候 返回树的叶子节点 返回值为数据中类别占比最大的类别

递归切分条件
遍历训练样本所有的特征，选择信息增益最大的特征A_g 对于该特征每一种可能的取值 a_j 分别取A=a_j 将训练样本划分为j个子集 。其中ID3使用信息增益 C4.5使用信息增益率（因为信息增益对于某一个特征 当特征的取值越多 信息增益倾向于越大 例如 如果每一个特征取值都只有唯一的数据，那么经验条件熵等于0 信息增益很大 但是如果按照这样划分显然是不合理的） 信息增益率和信息增益相比 多除以该特征的熵（这样如果特征取值较多 该特征的熵也会相对较大）

递归过程
以subsmaples为训练集 以A-{A_g}为特征集递归建树

切分依据：
1 熵 H(Y)=-∑ _i p_ilog p_i
2 条件熵 H(Y|X) = ∑ _i p_i H(Y|X=x_i) 其中 p_i = P(X=x_i)
3 信息增益 g（D,A）=H(D) -H(D|A)

ID3 问题：

1. 处理的特征值只能是离散型数据 不能是连续型数据
2. 在相同的不确定程度上 对于取值类别多的特征其信息增益会变大 所以分割点会倾向于分割特征取值多的
3. 没有对缺失值进行处理

# 加载数据集 使用李航书数据进行预测
dataSet = [
        ['青年', '没工作', '没房子','一般', '否'],
        ['青年', '没工作', '没房子','好', '否'],
        ['青年', '有工作', '没房子','好', '是'],
        ['青年', '有工作', '有房子','一般', '是'],
        ['青年', '没工作', '没房子','一般', '否'],

        ['中年', '没工作', '没房子','一般', '否'],
        ['中年', '没工作', '没房子','好', '否'],
        ['中年', '有工作', '有房子','好', '是'],
        ['中年', '没工作', '有房子','非常好', '是'],
        ['中年', '没工作', '有房子','非常好', '是'],

        ['老年', '没工作', '有房子','非常好', '是'],
        ['老年', '没工作', '有房子','好', '是'],
        ['老年', '有工作', '没房子','好', '是'],
        ['老年', '有工作', '没房子','非常好', '是'],
        ['老年', '没工作', '没房子','一般', '否']
    ]
def getTrainData(data=dataSet):
    trainData=np.array(data)
    return trainData
   
    
# 1.经验熵公式
def empiricalEntropy(trainLabelArray):
    H_D=0
    labelCategories=set(trainLabelArray)
    for i in labelCategories:
        i_ratio=trainLabelArray[trainLabelArray==i].size/trainLabelArray.size
        H_D+=-1*i_ratio*np.log2(i_ratio)
    return H_D

# 2.条件经验熵公式
def conditional_enpiricalEntropy(featureArray,trainLabelArray):
    C_H_D=0
    featureCategories=set(featureArray)
    for i in featureCategories:
        i_ratio=featureArray[featureArray==i].size/featureArray.size
        C_H_D+=i_ratio*empiricalEntropy(trainLabelArray[featureArray==i])
    return C_H_D

# 3.计算信息增益最大的特征
def cal_largest_information_gain_feature(trainData):
    trainfeatureArray=trainData[:,0:-1]
    trainLabelArray=trainData[:,-1]
    n_feature=trainfeatureArray.shape[1]
    information_gain=-1
    max_information_gain=-1
    H_D=empiricalEntropy(trainLabelArray)
    print('H_D is',H_D)
    max_featture=-1
    for i in range(n_feature):
        n_featureArray=trainfeatureArray[:,i]
        C_H_D=conditional_enpiricalEntropy(n_featureArray,trainLabelArray)
        information_gain=H_D-C_H_D
        print('i is',i)
        print('C_H_D is',C_H_D)
        print('information_gain is',information_gain)
        if information_gain>max_information_gain:
            max_information_gain=information_gain
            max_featture=i
    return max_featture,max_information_gain

def getMaxCategory(trainfeature):
    mostCommon=Counter(trainfeature).most_common()
    return mostCommon[0][0]

def getSubSamples(trainData,ag,tag):
    n_samples=trainData.shape[0]
    subsamples=[]
    for i in range(n_samples):
        if trainData[i][ag]==tag:
            subsamples.append(list(trainData[i,0:ag])+list(trainData[i,ag+1:]))
    return np.array(subsamples)
        
    
# 生成决策树
'''
trainData
'''

def createTree(trainData,eposinao):
    if len(trainData[0])==1:
        return getMaxCategory(trainData[:,-1])
    if len(set(trainData[:,-1]))==1:
        return trainData[0][-1]
    ag,information_gain=cal_largest_information_gain_feature(trainData)
    if information_gain<eposinao:
        return getMaxCategory(trainLabel)
    tree={ag:{}}
    for i in set(trainData[:,ag]):
        tree[ag][i]=createTree(getSubSamples(trainData,ag,i),eposinao)
    return tree


def predict(testData,tree):
    print(testData)
    while True:
        (key,value),=tree.items()
        print(key)
        print(value)
        if type(tree[key]).__name__=='dict':
            result=testData[key]
            print(result)
            testData=np.delete(testData,key)
            print(testData)
            tree=value[result]
            print(tree)
            print(type(tree))
            if type(tree).__name__!='dict':
                return tree
        else:
            return value
        
def test(testDataList, testLabelList, tree):
    '''
    测试准确率
    :param testDataList:待测试数据集
    :param testLabelList: 待测试标签集
    :param tree: 训练集生成的树
    :return: 准确率
    '''
    #错误次数计数
    errorCnt = 0
    #遍历测试集中每一个测试样本
    for i in range(len(testDataList)):
        #判断预测与标签中结果是否一致
        if testLabelList[i] != predict(testDataList[i], tree):
            errorCnt += 1
    #返回准确率
    return 1 - errorCnt / len(testDataList)
          
start = time.time()
trainData=getTrainData()
testDataList=trainData[:,0:-1]
testLabelList=trainData[:,-1]
#创建决策树
print('start create tree')
tree = createTree(trainData,0.1)
print('tree is:', tree)

#测试准确率
print('start test')
accur = test(testDataList, testLabelList, tree)
print('the accur is:', accur)

#结束时间
end = time.time()
print('time span:', end - start) 

C4.5

为了解决上述问题 C4.5通过如下的方法

1. C4.5 将连续特征离散化 例如对于连续特征A m个训练样本在A特征上有m个取值 将这些取值从小到大排列 以相邻两个取值的中间值作为分割点 此时具有m-1个分割点 分别计算以这m-1个分割点作为划分的信息增益 比如取到的最大信息增益点为a_t 那么小于a_t的被划分为一类 大于a_t的被划分为一类 和离散属性不一样的地方是 该属性还会参与到后续的划分中 而不是像离散属性一样直接删除

2. 对于划分标准趋向于使用类别较多的属性这一问题 将划分的标准由信息增益更改为信息增益比
   g_r(D,A)=g(D,A)/H_A(D)
   其中 H_A(D) = -∑ _i D_i /D log₂D_i /D
   但是信息增益比倾向于寻找类别较少的属性 因此C4.5并不直接使用信息增益作为分割依据 而是采用一种启发性策略 首先寻找信息增益高于平均水平的特征 然后在这些特征中寻找信息增益比最大的

3. 对于缺失值处理
   缺失值影响主要存在于如下几个方面
   1 在属性值缺失的情况下如何进行划分属性的选择
   2 在给定划分属性的情况下 若样本在这个属性上 应该

C4.5自身存在的问题：
1 C4.5生成的树为多叉树 相比于二叉树而言 多叉树的计算效率较低
2 C4.5 只能应用于分类问题 不能应用于回归问题
3 C4.5中存在较多的对数运算 对于连续特征而言 还存在较多的排序运算 效率较低