机器学习笔记（三）决策树分类

本文将介绍使用决策树完成字母数据集的分类任务，并且手写决策树完成鸢尾花的分类

一.简介

决策树是一种基于规则的方法，它用一组嵌套的规则进行预测。在书的每个决策节点处，根据判断结果进入一个分支，反复执行这种操作直至达到叶子节点，得到预测结果，这些规则是通过训练得到的，而不是人工制定的。决策树是分段线性函数，具有非线性建模的能力。                                 ——摘自《机器学习与应用》雷明著
本文将介绍决策树的原理及应用，用到的数据集为字母灰度图数据集，鸢尾花数据集： 数据集链接戳这里.

二.先看一个简单的例子

这里我们用决策树对字母灰度图进行分类

import pandas as pd
import numpy as np
import os
import shutil
import zipfile
from PIL import Image,ImageOps
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

if not os.path.exists('work/recognise'):
    os.makedirs('work/recognise')
extracting = zipfile.ZipFile('/home/aistudio/data/data32588/letters.zip')
extracting.extractall('work/')

folders = os.listdir('work/letters')
#文件夹重命名为字母
for folder in folders:
    i = int(folder[-3:])
    if i<=36:
        os.rename('work/letters/%s'%folder,'work/letters/%s'%chr(54+i))
    else:
        os.rename('work/letters/%s'%folder,'work/letters/%s'%chr(60+i))
print(os.listdir('work/letters'))

#图片重命名为数字
for path in os.listdir('work/letters'):
    path = 'work/letters/%s'%path
    count = 0
    for f in os.listdir(path):
        file_path = '%s%s'%(path,'/')
        if f[-3:]=='png':
            os.rename('%s%s'%(file_path,f),'%s%s%s'%(file_path,str(count),'.png'))
            count+=1
        else:
            os.remove('%s%s'%(file_path,f))
            print(f)

for folder in os.listdir('work/letters'):
    os.makedirs('work/recognise/%s' % folder)
    for i in range(916,1016):
        shutil.move('work/letters/%s/%s.png' % (folder,str(i)),'work/recognise/%s/%s.png' % (folder,str(i-916)))

def train_data(quantity): # 训练样本，quantity为每类样本数量
    data = [] #特征向量
    labels = [] #标签
    for folder in os.listdir('work/letters'):
        file_list = os.listdir('work/letters/%s'%folder)
        for i in range(quantity):
            im = Image.open("work/letters/%s/%s.png" % (folder,str(i))).convert('L')
            im = im.resize((16, 16), Image.ANTIALIAS)               
            im = np.array(im).reshape(256).astype(np.float64)
            data.append(im)
            labels.append(folder)
    data = np.array(data)
    data_T = data.T
    skip = [] #需要舍弃的特征分量
    for i in range(len(data_T)):
        #如果在95%以上的样本中，该特征分量取相同值，则该特征分量对于分类的参考意义不大，舍弃
        if pd.value_counts(data_T[i]).max() >= 26*2*quantity*0.95:
            skip.append(i)
    data = np.delete(data,skip,axis = 1) #删去需舍弃的分量
    data = pd.DataFrame(data)
    data['labels'] = labels
    data = data.reindex(np.random.permutation(data.index)) #打乱数据
    return data[list(range(256-len(skip)))],data[['labels']],skip

def test_data(skip,quantity): # 测试样本
    data = []
    labels = []
    for label in os.listdir('work/recognise'):
        for i in range(quantity):
            im = Image.open("work/recognise/%s/%s.png" % (label,str(i))).convert('L')
            im = im.resize((16, 16), Image.ANTIALIAS)               
            im = np.array(im).reshape(256).astype(np.float64)
            data.append(im)
            labels.append(label)
    data = np.array(data)
    labels = np.array(labels)
    data = np.delete(data,skip,axis = 1)
    return data,labels
train_x,train_y,skip = train_data(900)
test_x,test_y = test_data(skip,100)

clf = DecisionTreeClassifier(random_state=0) #决策树分类器
clf.fit(train_x, train_y) #训练
pred = clf.predict(test_x) #预测结果
accuracy = accuracy_score(test_y,pred)
print('准确度: %.6f'%accuracy)

输出结果为：

准确度: 0.769615

三.决策树分类原理

1.分类过程概述

以二叉决策树为例，决策树的决策过程从根节点开始，在每个决策节点处做判断，根据特征向量的某个分量做出判断，将特征向量归为为左子树或右子树，依次进行下去，直至到达叶子节点，叶子节点对应的标签即为分类结果。如下图所示，将一组四维特征向量分为三类的过程。

2.训练过程

（1）递归分裂

模型训练的过程就是决策树生长的过程。决策树的建立是一个递归的过程，基本流程为，利用样本集$D$D创建根节点，找到一个划分标准，将样本集划分为$D_1$D1​,$D_2$D2​，利用$D_1$D1​,$D_2$D2​分别建立左子节点，右子节点，依次类推，递归地建立整棵树。当不能再分裂时，该节点作为叶子节点，同时确定叶子节点的标签。

（2）最佳分裂及分裂条件

在训练时，我们需要确定一个合适的方法将样本分裂为两部分。
我们的期望是，使分类之后的两部分样本尽可能得“纯”，即同一样本集中的中样本尽可能多得属于同一类。在这里引进信息熵的概念：
$E(D)=- \sum_ip_ilog_2p_i\tag{1}$E(D)=−i∑​pi​log2​pi​(1)
$p_i= \frac{N_i}N$pi​=NNi​​，$N_i$Ni​为第$i$i类的样本数，$N$N为总样本数
$E(D)$E(D)越大，说明样本信息量越大，即样本越均匀得分布于不同类，即越不纯。我们的期望是找到一个分裂条件，使分类后的信息熵尽可能得减小。另一常用指标还有Gini
指数：
$G(D)=1-\sum_i p_i^2=1- \frac{\sum_i N_i^2}{N^2}\tag{2}$G(D)=1−i∑​pi2​=1−N2∑i​Ni2​​(2)
Gini指数的意义表述与信息熵类似，计算过程复杂度较信息熵小。下面我们将以Gini指数为例。
对于分裂之后的Gini指数，计算公式为：
$G=\frac{N_L}NG(D_L)+\frac{N_R}NG(D_R)\tag{3}$G=NNL​​G(DL​)+NNR​​G(DR​)(3)
$N_L$NL​为左子树样本数，$N_R$NR​为右子树样本数，$N$N为总样本数，$G(D_L)$G(DL​)为左子样本的Gini指数，$G(D_R)$G(DR​)为右子样本的Gini指数。联立(2)、(3)式，可得求分裂后Gini指数的以下公式：
$G=1-\frac{1}N(\frac{\sum_iN_L^2}{N_L} +\frac{\sum_iN_R^2}{N_R})\tag{4}$G=1−N1​(NL​∑i​NL2​​+NR​∑i​NR2​​)(4)
假设特征向量$X=(x_1,x_2,...,x_i,...,x_n)$X=(x1​,x2​,...,xi​,...,xn​)，从$x_1$x1​开始遍历每个分量，对于其中一个特定的分量，依次用训练样本中每个$x_1$x1​的取值作为阈值，将样本分为左右两部分，得到Gini指数最小时对应的阈值即为最佳阈值，如此可获得本节点最佳分裂所根据的分量及其最佳阈值。如此递归进行，建立决策树。

（3）叶子节点的标签

我们可以设定某些条件，如果某节点输入的样本满足这些条件，则判定不能再分裂，已经到达叶子节点(在后面剪枝以约束树的大小还会再提到)。取这些样本中众数的标签作为叶子节点的标签。

（4）终止分裂

我们需要终止分裂的条件，同时，如果树的结构过于冗杂，则会出现过拟合问题，需要通过一定的方法约束树的大小。剪枝分为预剪枝和后剪枝。预剪枝为在数生成过程中根据某些条件终止分裂，后剪枝为再构造出整棵树后将某些决策节点更改为叶子节点以缩小树的规模。
终止分裂的条件一般有样本数量小于设定最小值，树的深度大于设定最大值，信息增益(样本分列前后Gini指数之差)小于设定值等等。

四.手写鸢尾花分类

1. 数据集介绍

鸢尾花数据集大小为150行×5列，前四列为花的四个特征，第五列为花的种类，一共三种。

2. 实现过程

（1）数据预处理

def data_supplier(n):
    with open('/home/aistudio/data/data5420/iris.data') as fo:
        data = [i.split(',') for i in fo.read().split('\n')]
    df = pd.DataFrame(data)[:-2] #去掉末尾的无效数据(空行)
    df = df.reindex(np.random.permutation(df.index)) #打乱数据
    train_x = np.array(df[:n][[0,1,2,3]]).astype('float32')
    train_y = np.squeeze(np.array(df[:n][[4]]))
    test_x = np.array(df[n:][[0,1,2,3]]).astype('float32')
    test_y = np.squeeze(np.array(df[n:][[4]]))
    return train_x,train_y,test_x,test_y
train_x,train_y,test_x,test_y = data_supplier(120)

（2）建立决策树

class DecisionTree: #决策树
    min_samples_split = 2 #最小分裂样本数
    dim =4 #维度
    max_depth = 5 #最大深度
    def __init__(self,vectors,labels,depth):
        #若样本数小于设定的最小值或者深度大于最大值，则停止分裂，到达叶子节点
        if len(vectors) <= self.min_samples_split or depth>=self.max_depth:
            self.kind = 'leaf'
            self.label = pd.value_counts(labels).index[0] #本叶子节点的标签
        else:
            self.G = 1-(pd.value_counts(labels)**2).sum()/len(vectors)**2 #样本的Gini指数
            self.threshold = None #分裂阈值
            vectors_T = vectors.T
            child_G = None #分裂后的Gini指数
            I = 0
            for i in range(self.dim): #变量分量，寻找最佳分裂特征
                for pos_thr in set(vectors_T[i]): # 遍历，寻找该特征下最佳分裂阈值
                    left_bools = vectors[:,i]<=pos_thr
                    right_bools = ~left_bools
                    left_vecs = vectors[left_bools] #左样本
                    right_vecs = vectors[right_bools]
                    left_labels = labels[left_bools] #左样本的标签
                    right_labels = labels[right_bools]
                    N_left = len(left_vecs)
                    N_right = len(right_vecs)
                    if N_left == 0 or N_right == 0: #一个子节点的样本数量为0
                        temp_g = self.G
                    else:
                        temp_g = 1-1/len(labels)*((pd.value_counts(left_labels)**2).sum()/N_left+
                                    (pd.value_counts(right_labels)**2).sum()/N_right) #分裂的Gini指数
                    if self.threshold == None or temp_g<child_G: #最小化Gini指数
                        child_G = temp_g
                        self.threshold = pos_thr
                        self.I = i #本节点选取的特征向量的分量
                        self.l_vecs = left_vecs #左节点样本
                        self.l_labels = left_labels
                        self.r_vecs = right_vecs #右节点样本
                        self.r_labels = right_labels
            if self.G-child_G<=0.001: #如果信息增益很小，停止分裂，则本节点判定为叶子节点
                self.kind = 'leaf'
                self.label = pd.value_counts(labels).index[0] #样本中数量最多的种类的标签
            else: #否则判定为普通节点，递归建立子树
                self.kind = 'node'
                self.l_tree = DecisionTree(self.l_vecs,self.l_labels,depth+1) #左子树
                self.r_tree = DecisionTree(self.r_vecs,self.r_labels,depth+1) #右子树
    def classify(self,vector): #分类
        if self.kind == 'leaf': #如果是叶子节点直接返回标签
            return self.label
        else: #如果不是叶子节点，根据特征进入子树
            if vector[self.I]<=self.threshold:
                return self.l_tree.classify(vector)
            else:
                return self.r_tree.classify(vector)

（3）分类

class DT_Classifier:
    def __init__(self,vectors,labels):
        self.decision_tree = DecisionTree(vectors,labels,0)
    def classify(self,test_x,test_y):
        results = []
        for i in test_x:
            res = self.decision_tree.classify(i)
            results.append(res)
        results = np.array(results)
        test_y = np.array(test_y)
        return sum(results==test_y)/len(test_y) #正确判断的数目除以总数得准确度
        
dt_classifier = DT_Classifier(train_x,train_y)
accuracy = dt_classifier.classify(test_x,test_y)
print('准确度：%.6f'%accuracy)

输出结果为

准确度：0.933333