机器学习实践第三篇——决策树构建

一.什么是决策树

　　决策树是一种基本的机器学习算法，其核心思想是通过对数据集进行递归的二分来构建一棵树形结构，每个节点代表一个属性测试，每个分支代表一个测试结果，每个叶子节点代表一个类别或者值。

　　决策树的关键点包括：

1. 可解释性： 决策树的模型结构直观易懂，可以被解释为一系列简单的规则，因此对于决策推理过程的可解释性较强。

2. 特征选择： 决策树的关键在于如何选择每个节点的分裂特征，常用的特征选择指标包括信息增益、信息增益比、基尼系数等。

3. 剪枝： 决策树容易出现过拟合的问题，为了提高泛化能力，需要对生成的决策树进行剪枝操作，减少决策树的复杂度。

4. 连续值和缺失值处理： 决策树算法通常需要对连续值和缺失值进行处理，C4.5算法引入了对连续值的处理和处理缺失值的能力。

5. 集成学习： 决策树也常被用于集成学习中的 Bagging、Random Forest 和 Boosting 等算法中，以提高模型的性能。

6. 适用性： 决策树适用于分类问题和回归问题，且能够处理多类别分类和多输出回归问题。

7. 优缺点： 决策树的优点包括易于理解和解释、对数据的预处理要求低、能够处理数值型和类别型数据等；缺点包括容易过拟合、对噪声敏感、不稳定性等。

二.如何构建一个决策树

　　1.准备数据集： 收集包含多个样本的数据集，每个样本包含多个特征和一个标签（类别或者值）。

　　　　首先，我们需要收集包含多个样本的数据集，每个样本包含多个特征和一个标签（类别或值）。确保数据集的质量和完整性对于构建准确的决策树模型至关重要。

　　　　鸢尾花数据集是一个经典的分类问题数据集，其中包含了三个品种的鸢尾花（山鸢尾、变色鸢尾和维吉尼亚鸢尾）的样本数据。每个样本包含四个特征：花萼长度、花萼宽度、花瓣长度和花瓣宽度，以及对应的品种标签。我们将加载鸢尾花数据集，并对数据进行预处理，包括数据清洗、特征选择等操作

　　2.选择特征： 根据问题的要求和数据集的特征，选择最适合作为分裂节点的特征。常用的特征选择指标包括信息增益、信息增益比、基尼系数等。

　　基尼指数算法实例

#在Python的scikit-learn库中，决策树模型默认就是使用基尼指数（Gini index）作为分裂属性的判断准则。以下是构建决策树模型的代码：

#1. 导入需要的库：

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn import tree
import matplotlib.pyplot as plt

#2. 加载数据集：

iris = load_iris()
X = iris.data
y = iris.target

#3. 划分训练集和测试集：

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

4. 构建基于基尼指数的决策树模型：

clf_gini = DecisionTreeClassifier(criterion='gini', max_depth=3, random_state=42)
clf_gini.fit(X_train, y_train)

#5. 评估模型：

print("Training Accuracy:", clf_gini.score(X_train, y_train))
print("Testing Accuracy:", clf_gini.score(X_test, y_test))

#6. 绘制决策树：

fig = plt.figure(figsize=(15,10))
_ = tree.plot_tree(clf_gini, 
                   feature_names=iris.feature_names,  
                   class_names=iris.target_names,
                   filled=True)

#在这段代码中，`DecisionTreeClassifier(criterion='gini', max_depth=3, random_state=42)`表示创建一个基于基尼指数的决策树模型，其中`max_depth=3`表示树的最大深度为3，`random_state=42`表示随机数种子为42，用于确保每次运行结果的一致性。

　　ID3算法实例

import numpy as np
import pandas as pd
from collections import Counter

def entropy(y):
    hist = np.bincount(y)
    ps = hist / len(y)
    return -np.sum([p * np.log2(p) for p in ps if p > 0])

class Node:

    def __init__(self, feature=None, threshold=None, left=None, right=None, *, value=None):
        self.feature = feature
        self.threshold = threshold
        self.left = left
        self.right = right
        self.value = value

    def is_leaf_node(self):
        return self.value is not None

class ID3:

    def __init__(self, min_samples_split=2, max_depth=100, n_feats=None):
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth
        self.n_feats = n_feats
        self.root = None

    def fit(self, X, y):
        self.n_feats = X.shape[1] if not self.n_feats else min(self.n_feats, X.shape[1])
        self.root = self._grow_tree(X, y)

    def predict(self, X):
        return np.array([self._traverse_tree(x, self.root) for x in X])

    def _grow_tree(self, X, y, depth=0):
        n_samples, n_features = X.shape
        n_labels = len(np.unique(y))

        # stopping criteria
        if (depth >= self.max_depth
                or n_labels == 1
                or n_samples < self.min_samples_split):
            leaf_value = self._most_common_label(y)
            return Node(value=leaf_value)

        feat_idxs = np.random.choice(n_features, self.n_feats, replace=False)

        # greedily select the best split according to information gain
        best_feat, best_thresh = self._best_criteria(X, y, feat_idxs)
        
        # grow the children that result from the split
        left_idxs, right_idxs = self._split(X[:, best_feat], best_thresh)
        left = self._grow_tree(X[left_idxs, :], y[left_idxs], depth+1)
        right = self._grow_tree(X[right_idxs, :], y[right_idxs], depth+1)
        return Node(best_feat, best_thresh, left, right)

    def _best_criteria(self, X, y, feat_idxs):
        best_gain = -1
        split_idx, split_thresh = None, None
        for feat_idx in feat_idxs:
            X_column = X[:, feat_idx]
            thresholds = np.unique(X_column)
            for threshold in thresholds:
                gain = self._information_gain(y, X_column, threshold)

                if gain > best_gain:
                    best_gain = gain
                    split_idx = feat_idx
                    split_thresh = threshold

        return split_idx, split_thresh

    def _information_gain(self, y, X_column, split_thresh):
        # parent loss
        parent_entropy = entropy(y)

        # generate split
        left_idxs, right_idxs = self._split(X_column, split_thresh)

        if len(left_idxs) == 0 or len(right_idxs) == 0:
            return 0

        # compute the weighted avg. of the loss for the children
        n = len(y)
        n_l, n_r = len(left_idxs), len(right_idxs)
        e_l, e_r = entropy(y[left_idxs]), entropy(y[right_idxs])
        child_entropy = (n_l / n) * e_l + (n_r / n) * e_r

        # information gain is difference in loss before vs. after split
        ig = parent_entropy - child_entropy
        return ig

    def _split(self, X_column, split_thresh):
        left_idxs = np.argwhere(X_column <= split_thresh).flatten()
        right_idxs = np.argwhere(X_column > split_thresh).flatten()
        return left_idxs, right_idxs

    def _traverse_tree(self, x, node):
        if node.is_leaf_node():
            return node.value

        if x[node.feature] <= node.threshold:
            return self._traverse_tree(x, node.left)
        return self._traverse_tree(x, node.right)

    def _most_common_label(self, y):
        counter = Counter(y)
        most_common = counter.most_common(1)[0][0]
        return most_common

三.总结

通过本文的实验，我们将深入了解决策树算法的构建过程，并通过实际数据集的应用来验证模型的性能。同时，我们也将探讨决策树模型的优化方法，以便读者能够更好地理解和应用决策树算法。