用Python实现一个决策树算法函数

决策树是一种基本的分类和回归方法，其本质是一种树形结构，其中每个内部节点表示一个特征或属性，每个分支代表该特征的一个取值，每个叶节点表示一个类别。决策树学习的本质是构建一个树形结构的分类器或回归器。在构建决策树时，算法会选择最优的特征来作为节点，然后将数据集划分为不同的子集，使得每个子集尽量纯净，即同一个子集中的样本尽量属于同一个类别。构建决策树的过程可以使用递归的方式来实现。本文将使用Python实现一个基本的决策树算法函数。

我们将使用Iris数据集作为分类的例子。Iris数据集是一个标准的机器学习数据集，其中包含了三个类别的花卉，分别是山鸢尾（Iris Setosa）、变色鸢尾（Iris Versicolour）和维吉尼亚鸢尾（Iris Virginica）。数据集中包含了150个样本，每个样本有四个特征，分别是花瓣长度、花瓣宽度、花萼长度和花萼宽度。我们的目标是根据这四个特征来预测花卉的类别。

数据集下载链接：https://archive.ics.uci.edu/ml/datasets/iris

首先，我们需要将数据集读入程序中，并将其拆分为训练集和测试集。代码如下：

import csv
import random
import math
 
# 读取数据集
def loadDataset(filename, split, trainingset=[], testset=[]):
    with open(filename, 'rt') as csvfile:
        lines = csv.reader(csvfile)
        dataset = list(lines)
        for x in range(len(dataset)-1):
            for y in range(4):
                dataset[x][y] = float(dataset[x][y])
            if random.random() < split:
                trainingset.append(dataset[x])
            else:
                testset.append(dataset[x])

接下来，我们需要实现一个函数来计算数据集的熵。熵是衡量样本集合的"纯度"的指标，可以用来选择最优的特征来作为节点。如果一个样本集合中包含的样本属于同一个类别，那么这个样本集合的熵为0；如果样本集合中包含的样本属于不同的类别，那么这个样本集合的熵越大，表示其"纯度"越低。代码如下：

# 计算数据集的熵
def entropy(dataset):
    n = len(dataset)
    classes = {}
    for sample in dataset:
        c = sample[-1]
        if c not in classes:
            classes[c] = 0
        classes[c] += 1
    e = 0
    for c in classes:
        p = classes[c] / n
        e -= p * math.log2(p)
    return e

然后，我们需要实现一个函数来选择最优的特征来作为节点。我们使用信息增益来衡量特征对样本集合的分类的"贡献度"，信息增益越大，表示该特征对分类的影响越大，应该选择该特征作为节点。代码如下：

# 选择最优的特征
def selectFeature(dataset):
    n = len(dataset[0]) - 1
    avgE = entropy(dataset)
    maxGain = 0
    bestFeature = -1
    for f in range(n):
        classes = {}
        for sample in dataset:
            c = sample[f]
            if c not in classes:
                classes[c] = []
            classes[c].append(sample)
        e = 0
        for c in classes:
            p = len(classes[c]) / len(dataset)
            e += p * entropy(classes[c])
        gain = avgE - e
        if gain > maxGain:
            maxGain = gain
            bestFeature = f
    return bestFeature

下一步是构建决策树。我们使用递归的方式来实现。在构建决策树时，算法会选择最优的特征来作为节点，然后将数据集划分为不同的子集，使得每个子集尽量纯净，即同一个子集中的样本尽量属于同一个类别。代码如下：

# 构建决策树
def decisionTree(dataset, features):
    classes = [sample[-1] for sample in dataset]
    if len(set(classes)) == 1:
        return classes[0]
    if len(dataset[0]) == 1:
        return max(set(classes), key=classes.count)
    bestFeature = selectFeature(dataset)
    node = features[bestFeature]
    tree = {node:{}}
    del(features[bestFeature])
    classes = {}
    for sample in dataset:
        c = sample[bestFeature]
        if c not in classes:
            classes[c] = []
        classes[c].append(sample)
    for c in classes:
        subtree = decisionTree(classes[c], features)
        tree[node][c] = subtree
    return tree

最后，我们需要实现一个函数来测试决策树的性能。代码如下：

# 测试决策树的准确率
def testTree(tree, testset):
    n = len(testset)
    correct = 0
    for sample in testset:
        c = classify(tree, sample)
        if c == sample[-1]:
            correct += 1
    return correct / n
 
# 使用决策树进行分类
def classify(tree, sample):
    if type(tree) != dict:
        return tree
    node = list(tree.keys())[0]
    value = sample[features.index(node)]
    subtree = tree[node][value]
    return classify(subtree, sample)

完整代码如下：

`python

import csv

import random

import math

# 读取数据集

def loadDataset(filename, split, trainingset=[], testset=[]):

with open(filename, 'rt') as csvfile:

lines = csv.reader(csvfile)

dataset = list(lines)

for x in range(len(dataset)-1):

for y in range(4):

dataset[x][y] = float(dataset[x][y])

if random.random() < split:

trainingset.append(dataset[x])

else:

testset.append(dataset[x])

# 计算数据集的熵

def entropy(dataset):

n = len(dataset)

classes = {}

for sample in dataset:

c = sample[-1]

if c not in classes:

classes[c] = 0

classes[c] += 1

e = 0

for c in classes:

p = classes[c] / n

e -= p * math.log2(p)

return e

# 选择最优的特征

def selectFeature(dataset):

n = len(dataset[0]) - 1

avgE = entropy(dataset)

maxGain = 0

bestFeature = -1

for f in range(n):

classes = {}

for sample in dataset:

c = sample[f]

if c not in classes:

classes[c] = []

classes[c].append(sample)

e = 0

for c in classes:

p = len(classes[c]) / len(dataset)

e += p * entropy(classes[c])

gain = avgE - e

if gain > maxGain:

maxGain = gain

bestFeature = f

return bestFeature

# 构建决策树

def decisionTree(dataset, features):

classes = [sample[-1] for sample in dataset]

if len(set(classes)) == 1:

return classes[0]

if len(dataset[0]) == 1:

return max(set(classes), key=classes.count)

bestFeature = selectFeature(dataset)

node = features[bestFeature]

tree = {node:{}}

del(features[bestFeature])

classes = {}

for sample in dataset:

c = sample[bestFeature]

if c not in classes:

classes[c] = []

classes[c].append