游戏AI的创造思路-技术基础-决策树（1）

信息增益（Information Gain）公式
$[ Gain(D, A) = Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v) ]$
其中， $(Ent(D))$ 是数据集 $D$ 的信息熵， $(D^v)$ 是特征 $A$ 上取值为 $v$ 的样本子集。
Python 实现信息增益

import numpy as np  

def entropy(y):  
    n = len(y)  
    labels_count = {}  
    for label in y:  
        if label not in labels_count:  
            labels_count[label] = 0  
        labels_count[label] += 1  
    ent = 0.0  
    for label in labels_count:  
        p = labels_count[label] / n  
        ent -= p * np.log2(p)  
    return ent  

def info_gain(X, y, feature):  
    n = len(y)  
    ent_before = entropy(y)  
    total_gain = 0.0  
    feature_values = np.unique(X[:, feature])  
    for value in feature_values:  
        sub_X = X[X[:, feature] == value]  
        sub_y = y[X[:, feature] == value]  
        prob = len(sub_X) / n  
        total_gain += prob * entropy(sub_y)  
    return ent_before - total_gain

3.2. 信息增益比（Gain Ratio）

决策树使用信息增益比（Gain Ratio）作为划分标准时，其公式是基于信息增益的，但增加了一个分裂信息（Split Information）的项来规范化信息增益，从而避免偏向于选择取值较多的特征。

信息增益比公式

信息增益（Information Gain）：
$[ Gain(D, A) = Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v) ]$
分裂信息（Split Information）：
$[ SplitInfo(D, A) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|} ]$
信息增益比（Gain Ratio）：
$[ GainRatio(D, A) = \frac{Gain(D, A)}{SplitInfo(D, A)} ]$

Python实现代码

以下是使用Python实现信息增益比的代码：

import numpy as np  
  
def entropy(y):  
    """计算信息熵"""  
    n = len(y)  
    labels_count = {}  
    for label in y:  
        if label not in labels_count:  
            labels_count[label] = 0  
        labels_count[label] += 1  
    ent = 0.0  
    for label in labels_count:  
        p = labels_count[label] / n  
        ent -= p * np.log2(p)  
    return ent  
  
def split_info(X, feature):  
    """计算分裂信息"""  
    n = len(X)  
    feature_values = np.unique(X[:, feature])  
    split_info = 0.0  
    for value in feature_values:  
        sub_X = X[X[:, feature] == value]  
        prob = len(sub_X) / n  
        split_info -= prob * np.log2(prob)  
    return split_info  
  
def info_gain(X, y, feature):  
    """计算信息增益"""  
    n = len(y)  
    ent_before = entropy(y)  
    total_gain = 0.0  
    feature_values = np.unique(X[:, feature])  
    for value in feature_values:  
        sub_X = X[X[:, feature] == value]  
        sub_y = y[X[:, feature] == value]  
        prob = len(sub_X) / n  
        total_gain += prob * entropy(sub_y)  
    return ent_before - total_gain  
  
def gain_ratio(X, y, feature):  
    """计算信息增益比"""  
    gain = info_gain(X, y, feature)  
    split_info = split_info(X, feature)  
    if split_info == 0:  # 避免除以0的情况  
        return 0  
    return gain / split_info  
  
# 示例数据  
X = np.array([[1, 0], [1, 1], [0, 0], [0, 1]])  
y = np.array([0, 0, 1, 1])  
  
# 计算特征0和特征1的信息增益比  
print("Gain Ratio for feature 0:", gain_ratio(X, y, 0))  
print("Gain Ratio for feature 1:", gain_ratio(X, y, 1))

这段代码定义了计算信息熵、分裂信息、信息增益和信息增益比的函数，然后在示例数据上计算了特征0和特征1的信息增益比。

3.3. 基尼指数（Gini Index）

决策树使用基尼指数（Gini index）作为划分标准时，其公式主要用于衡量数据集或数据子集的不纯度。基尼指数越小，表示数据集或数据子集的纯度越高，即选定的特征越好。

基尼指数公式

对于给定的数据集 D，其基尼指数 Gini(D) 可以通过以下公式计算：

$[ Gini(D) = 1 - \sum_{k=1}{J} p_k2 ]$

其中，pk 是数据集 D 中选择第 k 类的概率，J 是类的总数。

对于特征 $A$ ，假设它有 $V$ 个可能的取值 {a1,a2,…,aV}，如果使用特征 A 对数据集 D 进行划分，可以得到 V 个子集 {D1,D2,…,DV}，其中 Dv 包含所有在特征 A 上取值为 av 的样本。此时，特征 A 对数据集 D 的基尼指数 $Gini(D,A)$ 可以通过以下公式计算：

$[ Gini(D, A) = \frac{\sum_{v=1}^{V} |D^v| \cdot Gini(D^v)}{|D|} ]$

其中， $Gini(Dv)$ 是子集 Dv 的基尼指数，∣Dv∣ 是子集 Dv 的样本数量，∣D∣ 是数据集 D 的样本总数。

Python实现代码

以下是使用Python实现基尼指数的代码：

import numpy as np  
  
def gini_index(y):  
    """计算数据集的基尼指数"""  
    n = len(y)  
    labels_count = {}  
    for label in y:  
        if label not in labels_count:  
            labels_count[label] = 0  
        labels_count[label] += 1  
    gini = 1.0  
    for label in labels_count:  
        p = labels_count[label] / n  
        gini -= p**2  
    return gini  
  
def gini_index_feature(X, y, feature):  
    """计算特征对数据集的基尼指数"""  
    n = len(y)  
    feature_values = np.unique(X[:, feature])  
    total_gini = 0.0  
    for value in feature_values:  
        sub_X = X[X[:, feature] == value]  
        sub_y = y[X[:, feature] == value]  
        prob = len(sub_X) / n  
        total_gini += prob * gini_index(sub_y)  
    return total_gini  
  
# 示例数据  
X = np.array([[1, 0], [1, 1], [0, 0], [0, 1]])  
y = np.array([0, 0, 1, 1])  
  
# 计算特征0和特征1的基尼指数  
print("Gini index for feature 0:", gini_index_feature(X, y, 0))  
print("Gini index for feature 1:", gini_index_feature(X, y, 1))

这段代码定义了计算数据集基尼指数的函数 gini_index。

然后定义了计算特征对数据集基尼指数的函数 gini_index_feature。

最后，在示例数据上计算了特征0和特征1的基尼指数。

3.4. 三种划分标准对比

决策树在构建过程中，选择合适的划分标准至关重要，这直接影响到决策树的性能和效率。信息增益（Information Gain）、信息增益比（Gain Ratio）和基尼指数（Gini Index）是三种常用的划分标准，它们各自具有不同的优点和缺陷。

信息增益（Information Gain）

优点：

直观易懂：信息增益的计算过程简单明了，易于理解和解释。它反映了使用某个特征进行划分后，数据集纯度的提升程度。

适应性强：信息增益可以适应多个类别之间的分类问题，并可以应用于离散型和连续型的特征。

多特征值偏好：信息增益在计算时考虑了特征的不确定性程度，因此对于具有更多特征值的特征更有利，这有助于捕捉数据中的细节信息。

缺陷：

特征值偏好：信息增益倾向于选择具有更多特征值的特征作为划分特征，这可能导致决策树过于复杂，增加过拟合的风险。

忽略相关性：信息增益独立地计算每个特征的重要性，可能忽视了特征之间的相关性，而特征之间的相关性对于分类问题具有重要意义。

信息增益比（Gain Ratio）

优点：

规范化信息增益：信息增益比通过引入分裂信息（Split Information）对信息增益进行了规范化，从而减少了信息增益对具有更多特征值特征的偏好。

处理特征值偏差：在信息增益的基础上，信息增益比更好地处理了特征值分布偏差大的情况，提高了决策树的健壮性。

缺陷：

计算复杂度：由于需要计算分裂信息，信息增益比的计算复杂度略高于信息增益，特别是在处理大规模数据集时。

可能偏向取值少的特征：在某些情况下，信息增益比可能过于偏向取值数目较少的特征，这需要根据具体数据集进行权衡。

基尼指数（Gini Index）

优点：

计算效率高：基尼指数的计算方式相对简单，不涉及对数运算，因此在处理大规模数据集时具有较高的效率。

不偏向特征值：基尼指数在计算特征重要性时不考虑特征的不确定性程度，因此不会偏向于具有更多特征值的特征。

二分类友好：基尼指数特别适用于二分类问题，能够直观地反映分类的准确性。

缺陷：

不直观：基尼指数作为一个概率指标，其计算过程相对较为抽象，不如信息增益直观易懂。

多分类问题：虽然基尼指数可以应用于多分类问题，但在处理多个类别之间的分类时，其效果可能不如信息增益或信息增益比。

小结

三种划分标准各有优缺点，选择哪种标准取决于具体问题的特点和数据集的特征。

在实际应用中，可以通过交叉验证等方法来评估不同划分标准对决策树性能的影响，从而选择最适合的划分标准。

4. 运行原理及步骤

决策树的构建过程包括选择最佳划分特征、递归地划分数据集、剪枝等步骤。

步骤
1. 选择最佳划分特征：根据信息增益、信息增益比或基尼指数选择最佳划分特征。
2. 划分数据集：根据选择的特征和特征值划分数据集。
3. 递归构建决策树：对每个子数据集重复上述步骤，直到满足停止条件（如所有样本属于同一类，或没有更多特征等）。
4. 剪枝：为了防止过拟合，通常需要对决策树进行剪枝。
Python 实现决策树构建

class DecisionTree:  
    def __init__(self, max_depth=None, min_samples_split=2):  
        self.max_depth = max_depth  
        self.min_samples_split = min_samples_split  
        self.root = None  

    def fit(self, X, y):  
        self.root = self._build_tree(X, y, 0)  

    def _build_tree(self, X, y, depth):  
        # 停止条件  
        if depth >= self.max_depth or len(np.unique(y)) == 1 or len(X) < self.min_samples_split:  
            return Node(value=np.argmax(np.bincount(y)))  

        # 选择最佳划分特征  
        best_feature, best_thresh = self._best_split(X, y)  

        # 划分数据集  
        left_idxs, right_idxs = self._split(X[:, best_feature], best_thresh)  

        # 递归构建子树  
        left = self._build_tree(X[left_idxs, :], y[left_idxs], depth + 1)  
        right = self._build_tree(X[right_idxs, :], y[right_idxs], depth + 1)  

        return Node(best_feature, best_thresh, left, right)  

    # 辅助函数：选择最佳划分特征和阈值、划分数据集等

5. 优缺点

优点
- 易于理解和实现。
- 计算效率高，对于分类问题表现良好。
- 能够处理非线性关系。
- 可以清晰地显示决策过程，便于解释。
缺点
- 容易过拟合，需要通过剪枝等技术解决。
- 对缺失值比较敏感，需要额外处理。
- 在某些复杂问题上可能不如神经网络等算法表现优异。

6. 游戏AI使用决策树算法进行NPC行为控制

在游戏开发中，NPC（非玩家角色）的行为控制是一个重要方面。

使用决策树算法可以有效地管理和控制NPC的行为，使其根据游戏环境和玩家行为做出合理的反应。

6.1. 概述

决策树是一种基于树结构的决策模型，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

6.2. 详细过程

定义行为: 确定NPC可能执行的所有行为，例如攻击、逃跑、对话等。
确定属性: 选择影响NPC行为的属性，如玩家距离、玩家状态（攻击、防御等）、NPC当前状态等。
构建决策树: 使用属性构建决策节点，每个节点根据属性做出决策，并决定下一步的行为。
实施行为: 根据决策树的结果，NPC执行相应的行为。

6.3. 实例

假设我们有一个简单的游戏，NPC可以执行两种行为：攻击和逃跑。我们考虑两个属性：玩家距离和玩家状态。

如果玩家距离小于5米且玩家处于攻击状态，NPC选择逃跑。
如果玩家距离小于5米且玩家不处于攻击状态，NPC选择对话。
如果玩家距离大于等于5米，NPC选择巡逻。

6.4. Python实现

class NPC:  
    def __init__(self, name):  
        self.name = name  
  
    def decide_action(self, player_distance, player_is_attacking):  
        # 根据玩家距离和玩家状态决定NPC的行为  
        if player_distance < 5:  
            if player_is_attacking:  
                return "逃跑"  
            else:  
                return "对话"  
        else:  
            return "巡逻"  
  
# 实例化NPC  
npc = NPC("守卫")  
  
# 调用decide_action方法决定NPC的行为，并打印结果  
action = npc.decide_action(3, True)  
print(f"{npc.name}决定{action}")

这段代码定义了一个NPC类，其中__init__方法是构造函数，用于初始化NPC的姓名。

decide_action方法根据传入的玩家距离（player_distance）和玩家是否处于攻击状态（player_is_attacking）来决定NPC应该执行的行为，并返回该行为。

最后，代码创建了一个名为“守卫”的NPC实例，并调用decide_action方法来决定其行为，然后打印出结果。