# 监督学习在Aliens游戏中的探究尝试
**摘要**:?? 监督学习是指：利用一组已知类别的样本调整的，使其达到所要求性能的过程，也称为训练或有教师学习。
关键词: 特征提取、监督学习、朴素贝叶斯、逻辑斯蒂、随机森林
# 一、基于现有特征提取方法的实验
## 1.1 现有特征提取的理解
Recorder.java提供了特征提取的入口。其中invoke为记录函数，它调用featureExtract函数来生成当前状态的观测，并在末尾追加当前做出的动作，以此形成一条完整记录，用filewriter写入文件。FeatureExtract函数是特征提取的重点，目前我们提取的特征有：32*14=448个格子中的物体，4个游戏相关属性，1个动作，总共453个值。其中448个格子记录物体的编号，是一个int类型，4个游戏相关属性直接调用obsversation的4个get个方法得到（需要注意的是源代码里给448赋值了4次，实际上只存了AvatarType，其他的都被取代了）。
在invoke函数中对于4个动作的整数化表示如下：
## 1.2 不同模型的介绍与训练结果分析
为了充分比较不同监督学习模型的游戏性能，这里直接选择了最高难度的游戏，并且控制变量，使用相同的训练数据与训练轮数，只改变训练模型。
### 1.2.1 朴素贝叶斯
**简介**：
朴素贝叶斯算法是一种基于概率的分类方法，它的主要依据是如下图的 条件概率公式，即假定给定目标值时属性之间相互条件独立，在X=Xi的情况下将输入样本分类到某一类的概率可以由这一类出现的概率乘此类中输入为Xi出现的条件概率再除以X=Xi的概率得出。以此种方法计算不同分类的概率，并返回最大值所指向的分类，就完成了朴素贝叶斯分类。需要注意的是，P(X=Xi)可以通过全概率公式得出，也可以直接统计计算。
朴素贝叶斯分类器(Naive Bayes Classifier 或 NBC)发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。[4]
朴素贝叶斯算法的优点是，对小规模的数据表现很好，适合多分类任务，适合增量式训练。同时它的缺点在于，对输入数据的表达形式很敏感（离散、连续，值极大极小之类的）。[3]
**训练结果**：
训练数据显示总的分类准确率为40%左右，相对较低。
分析详细准确性数据，可以发现NIL的精确率很高，但是召回率非常低，可以预见agent将比人类进行更少的停滞动作。USE两项均很低，可以想见agent将不太倾向于发射子弹，且正确发射的概率也相应较低。而left和right两项虽然虽然精确率不高但是召回率较高，因而agent将进行比人类更多的左右移动动作。
再看混淆矩阵，各项被分到正确类的概率还是最高的，同时错误分类到其他3项的概率大致相当且较高。因而agent的行为没有特别明显的偏好特征，但总的来说错误的比例是较高的，预计结果不会特别好。
游戏结果来看，在test的一开始，表现十分正常，命中率较高，很快就把外星人的数量减少到减少到5个以下，但在仅剩一个外星人的时候开始一动不动，最终失败。
**小结**：
个人认为，在我们的特征数据提取所提供的X向量其维数相当大，而相对来说总的记录数量相对较小，这导致了统计X=Xi的概率始终处在一个非常小的值附近，而难以产生有价值的判断依据，甚至常常需要进行拉普拉斯平滑。因而朴素贝叶斯算法在这里不太容易产生良好的测试效果。
### 1.2.2 逻辑斯蒂回归
**简介**：
逻辑斯蒂回归的本质是极大似然估计，其分类方法是对输入样本高维空间用超平面进行分割。
经典的逻辑斯蒂回归模型是一种二分类模型，在进行多分类时，通过累次进行二分类（p与除p以外的类）来达到效果。实际操作中，不同类别对应的logistic函数实际上表示的是分为此类的概率，最终返回概率最大的类别，以此来实现多分类的目标。
简单看一下二分类逻辑斯蒂回归的算法，期中调参拟合的过程由weka实现，这里只叙述分类部分。
基本的线性回归形式为：
Sigmoid函数：，可以把输入规范化到0，1之间。
将线性回归表达式套上sigmoid函数，得到：这样就把线性回归表达式的实值输出结果压缩成了一个0-1之间。但这样还是没有实现分类的效果，我们需要加一个“门槛“，若输出值大于这个门槛，那么就将其结果判断为1，反之判断为0，一般这个“门槛“都是0.5。
可以看出，逻辑斯蒂回归的输出其实表征的是当前测试样本被分到1类的概率，即[5]
虽然逻辑回归能够用于分类，不过其本质还是线性回归。它仅在线性回归的基础上，在特征到结果的映射中加入了一层sigmoid函数（非线性）映射，即先把特征线性求和，然后使用sigmoid函数来预测。然而，正是这个简单的逻辑函数，使得逻辑回归模型成为了机器学习领域一颗耀眼的明星。
这主要是由于线性回归在整个实数域内敏感度一致，而分类范围，只需要在[0,1]之内。而逻辑回归就是一种减小预测范围，将预测值限定为[0,1]间的一种回归模型。逻辑曲线在z=0时，十分敏感，在z>>0或z<<0处，都不敏感，将预测值限定为[0,1]。[6]
**训练结果**：
总体来看准确率达到了62%，相比朴素贝叶斯有了较大提升。
具体来看准确性，可以发现NIL的精确率与召回率均较高，推测agent学习人类停止动作的学习效果应当不错。而USE在精确率与召回率方面都较低，推测agent正确发射子弹可能会有困难。
再看混淆矩阵，反映了同样的情况，USE被误判为NIL的概率相当大，几乎和正确判断相当，可以预见agent将比人类玩家停止更多时间，同时发射更少的子弹。而左右平移表现相对正常。
从游戏测试来看，虽然从一开始就频繁发射，但发射命中率始终较低，从最开始就miss了一堆外星人，长时间未能有效减少外星人数量，最终碰到炸弹失败。
### 1.2.3 随机森林
**简介**：
随机森林即多棵决策树组成的森林，进行分类问题的时候依据多棵决策树的输出结果的众数进行判决，类似于我们常说的“投票”。其实从直观角度来解释，每棵决策树都是一个分类器（假设现在针对的是分类问题），那么对于一个输入样本，N棵树会有N个分类结果。而随机森林集成了所有的分类投票结果，将投票次数最多的类别指定为最终的输出，这就是一种最简单的 Bagging 思想。
每棵树的按照如下规则生成：
1. 如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本（这种采样方式称为bootstrap sample方法），作为该树的训练集；从这里我们可以知道：每棵树的训练集都是不同的，而且里面包含重复的训练样本。如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；
2. 如果每个样本的特征维度为M，指定一个常数m<<M，随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；
3. 每棵树都尽最大程度的生长，并且没有剪枝过程。
一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力。[7]
最后总结一下随机森林的优缺点：
**优点**：
- 对于大部分的数据，它的分类效果比较好。
- 能处理高维特征，不容易产生过拟合，模型训练速度比较快，特别是对于大数据而言。
- 在决定类别时，它可以评估变数的重要性。
- 对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。
**缺点**：
- 对少量数据集和低维数据集的分类不一定可以得到很好的效果。
- 计算速度比单个的决策树慢。
- 当我们需要推断超出范围的独立变量或非独立变量，随机森林做得并不好。[8]
**训练结果**：
总体来看准确率将近75%，是截止到目前效果最好的分类模型。
再说具体准确性，NIL的精确率和召回率均较高，可见agent已经较好地学习人类玩家的停止动作。而USE的精确率与召回率都不算很高，两项平均大概50%，推测agent的射击行为可能与人类玩家有一定差异，并未学习的非常好。与前两种分类算法不同的是，在这里可以发现left和right的精确率差不多，但是left的召回率明显更高，可见agent学习人类向左移动的效果相比向右移动要更好。
从混淆矩阵来看，除了NIL仍旧是一枝独秀，其余三中动作被分类到nil的比例都是相对较大的，甚至right动作分类到自身的比例都不如分类到NIL的大，而Left则相对较好。推测agent的行为可能有相当多的时间处在一动不动的状态，并且更倾向于向左移动。
从游戏结果来看，一开始在相当短的时间内agent就准确发射并快速减少了外星人的数量。在最后几个外星人时agent花费了较多的时间左右移动但是并未发射，最终成功完成游戏。
### 1.2.4 SimpleCast
**简介**：
CART算法（classification and regression tree）分类和回归算法，是一种应用广泛的决策树学习方法，既然是一种决策树学习方法，必然也满足决策树的几大步骤，即：1特征的选择 2决策树的生成 3 决策树的剪枝 三大步骤，CART算法既可以用于分类还可以用于回归。
CART是在给定输入随机变量X的条件下输出随机变量Y的条件概率分布的学习方法，CART 有个特性就是其假设决策树全部是二叉树，也就是说其结点只有两种选择，‘是’和‘否’，说专业点就是决策树递归的二分每个特征，最终得到决策树，通过不断的划分，将特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。
设结点的训练数据集为D，计算现有特征对该数据集的Gini系数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或 “否”将D分割成D1和D2两部分，计算A=a时的Gini系数。在分类问题中，假设有K个类，样本点属于第k类的概率为Pk，则概率分布的gini指数的定义为：
如果样本集合D根据某个特征A被分割为D1，D2两个部分，那么在特征A的条件下，集合D的gini指数的定义为：
gini指数Gini(D,A)表示特征A不同分组的数据集D的不确定性。gini指数值越大，样本集合的不确定性也就越大，这一点与熵的概念比较类似。
所以在此，基于以上的理论，我们可以通过gini指数来确定某个特征的最优切分点(也即只需要确保切分后某点的gini指数值最小)，这就是决策树CART算法中类别变量切分的关键所在。[9]
**性能分析**：
总体正确分类率达到74%，极差较小但方差较大。
细节准确率来看NIL的精确与回归都相当高，USE均低于五成，而引人注意的是LEFT和RIGHT的判别回归率都相当低，这在之前的分类算法中是没有出现的。因而推断agent可能不能很好地模仿人类射击的动作，同时左右移动规避子弹的能力也较低。
再看混淆矩阵，发现left项被识别为nil的概率比识别为自身的概率都大，这可能会对正常的左右移动产生较大影响。
从游戏结果来看agent移动到屏幕中间后开始射击，不再左右平移，很快被炸弹击中而失败，与预期结果相近。
# 二、特征提取方法的改进
## 2.1 总的思路
旧版的特征提取中直接使用了448个方格内的物体属性作为特征来进行学习。这样做虽然最大化了特征的完整性，但是过于具体，缺乏抽象性，可能不具备良好的学习性质。同时游戏状态是不会重复的，因而收集到的特征参数也不尽相同，这样的朴素知识获取方法，近一步降低了训练模型的抽象性与泛化能力，非常容易出现过拟合情况。
因而我们特征提取方法的改进就是，通过人为方法提取一些更加“抽象”同时自认为“有用”的特征，让机器根据这些我们人类组织出来的经验进行学习，以期望获得更好的学习成果。
## 2.2 特征改进
首先解决开头的疑惑，将4个属性分别写入4个不同的位置。进行几次train后，通过直接阅读artf文件，发现除了gametick会变之外，其他三个始终是一个定值，对他们每次分别记录是毫无意义的！
所以我们为了增加空间利用率，直接移除原449，450，451属性值，并在原位存放后续的三个我们自定义的特征。
经过测试 itype: 0-empty 2-wall 5-bomb 6-alien，同时惊讶的发现，原来竟然完全没有记录Avatar的位置，真是荒唐啊荒唐。
首先，联想到自己玩塔防游戏的经验，防御塔可以设置属性“第一个”“最强的”“最近的”“最后一个”等等攻击优先度，我们的Avatar也可以发射子弹所以应当有类似的想法—攻击优先级。因为我们知道当第一个外星人下到最后一行的时候我们就已经输了，所以优先解决第一个外星人是理所应当的，于是有了第一个特征：第一个外星人与Avatar的相对位置（左负右正）。修改双重循环的顺序，使其从后向前检索，在遍历的同时直接就把最后一个alien的位置给找出来，不浪费时间。
其次，我们的Avatar不可以碰到炸弹，而“碰到”的含义在于Avatar先离炸弹很近，接着或是主动接近，或是被动接近，导致炸弹离我们越来越近，最后碰到一起，然后你就gg了。而这中间，尤以本来就最靠近Avatar的炸弹最为凶险，所以我们专门记录它和Avatar之间的距离，因而有了第二个特征值：最近炸弹与Avatar的相对位置（左负右正）。
第三，我在train的时候发现，由于Avatar的射击有攻击间隔，因而一旦在某一位置停下来射击，只要空了一发，往往后面的连续射击也“恰好”都会空枪。这时候就需要我们进行移动，或者稍作停顿后再次射击。这给了我们一个启发，即Avatar的行动前后是有关联的，并不是简单地单纯依据游戏状态（有点类似于时序逻辑电路的感觉），所以很自然地想到，可以把先前的动作作为下一次动作的判别依据，于是有了第三个特征：上一个动作的值。
## 2.3 性能评估
**Nave-bayse：**
一开始直接走到最右边开始站桩输出，但是在一段时间之后，忽然开始返回屏幕中间位置，并不断走A，行动模式与人类玩家非常相似。不过遗憾的是在外星人数量又一次降到较低值时，不再能准确击中外星人，最终被碰撞而亡。
**Logistic:**
起初的表现十分良好，可以正确移动与发射子弹，同时移动速度非常迅速异于人类，可以看到明显的规避炸弹动作。但是在仅剩一个外星人的时候，不会发射子弹，而是频繁的左右平移，最终失败。
**Random-forest:**
起初不断走A，在外形人数量少于5个时忽然开始站撸，在外星人循环两行之后获胜。
**Simple-Cast:**
始终在屏幕最左侧站桩输出，但是射击精准，直接获胜。
总体来看，4中算法在改进特征提取后均获得了不同程度的提升。尤其是其模仿人类的能力大大增强了。仍然存在较多问题，可能的原因是数据收集过少（只有一轮游戏），以及特征提取太杂且不够优化。
# 三、结束语
采用监督学习分类模式来玩游戏的目标是模仿人类玩家的行为，可以无限模仿但是难以有本质上的超越，不过在解决许多问题上仍旧是十分有帮助的。这其中涉及到的特征提取与分类算法这两块都大有门道，值得深入探究与进一步开发。《塔希里亚故事集》里有一句话说的好，“没有低级的法术，只有低级的法师”，熟练运用监督学习，不管是对于数据分析结果预测，还是在诸如开发符合人类行为模式的游戏agent方面，都是大有裨益的。
致谢 特别感谢王宸旭同学提醒我需要认真研读混淆矩阵来书写性能评估。
### References:
Wikipedia, supervised learning, https://en.wikipedia.org/wiki/Supervised_learning
### 附中文参考文献:
1. 监督学习，https://baike.baidu.com/item/%E7%9B%91%E7%9D%A3%E5%AD%A6%E4%B9%A0
2. 朴素贝叶斯，https://blog.csdn.net/sinat_30353259/article/details/80932111#_158
3. 朴素贝叶斯算法详解https://baike.baidu.com/item/%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF/4925905?fr=aladdin#reference-[3]-992724-wrap
4. 逻辑斯蒂回归（Logistic Regression），https://blog.csdn.net/zhaojc1995/article/details/81592567
5. 【机器学习】逻辑斯蒂回归（Logistic Regression）详解，https://blog.csdn.net/qq_32742009/article/details/81516140
6. 【机器学习】 随机森林（Random Forest），https://blog.csdn.net/qq_34106574/article/details/82016442
7. Python机器学习笔记——随机森林算法！最详细的笔记没有之一，http://www.sohu.com/a/297967370_729271
8. CART树算法详解，https://blog.csdn.net/e15273/article/details/79648502
?
# 监督学习在Aliens游戏中的探究尝试
**摘要**:?? 监督学习是指：利用一组已知类别的样本调整的，使其达到所要求性能的过程，也称为训练或有教师学习。
关键词: 特征提取、监督学习、朴素贝叶斯、逻辑斯蒂、随机森林
# 一、基于现有特征提取方法的实验
## 1.1 现有特征提取的理解
Recorder.java提供了特征提取的入口。其中invoke为记录函数，它调用featureExtract函数来生成当前状态的观测，并在末尾追加当前做出的动作，以此形成一条完整记录，用filewriter写入文件。FeatureExtract函数是特征提取的重点，目前我们提取的特征有：32*14=448个格子中的物体，4个游戏相关属性，1个动作，总共453个值。其中448个格子记录物体的编号，是一个int类型，4个游戏相关属性直接调用obsversation的4个get个方法得到（需要注意的是源代码里给448赋值了4次，实际上只存了AvatarType，其他的都被取代了）。
在invoke函数中对于4个动作的整数化表示如下：
## 1.2 不同模型的介绍与训练结果分析
为了充分比较不同监督学习模型的游戏性能，这里直接选择了最高难度的游戏，并且控制变量，使用相同的训练数据与训练轮数，只改变训练模型。
### 1.2.1 朴素贝叶斯
**简介**：
朴素贝叶斯算法是一种基于概率的分类方法，它的主要依据是如下图的 条件概率公式，即假定给定目标值时属性之间相互条件独立，在X=Xi的情况下将输入样本分类到某一类的概率可以由这一类出现的概率乘此类中输入为Xi出现的条件概率再除以X=Xi的概率得出。以此种方法计算不同分类的概率，并返回最大值所指向的分类，就完成了朴素贝叶斯分类。需要注意的是，P(X=Xi)可以通过全概率公式得出，也可以直接统计计算。
朴素贝叶斯分类器(Naive Bayes Classifier 或 NBC)发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。[4]
朴素贝叶斯算法的优点是，对小规模的数据表现很好，适合多分类任务，适合增量式训练。同时它的缺点在于，对输入数据的表达形式很敏感（离散、连续，值极大极小之类的）。[3]
**训练结果**：
训练数据显示总的分类准确率为40%左右，相对较低。
分析详细准确性数据，可以发现NIL的精确率很高，但是召回率非常低，可以预见agent将比人类进行更少的停滞动作。USE两项均很低，可以想见agent将不太倾向于发射子弹，且正确发射的概率也相应较低。而left和right两项虽然虽然精确率不高但是召回率较高，因而agent将进行比人类更多的左右移动动作。
再看混淆矩阵，各项被分到正确类的概率还是最高的，同时错误分类到其他3项的概率大致相当且较高。因而agent的行为没有特别明显的偏好特征，但总的来说错误的比例是较高的，预计结果不会特别好。
游戏结果来看，在test的一开始，表现十分正常，命中率较高，很快就把外星人的数量减少到减少到5个以下，但在仅剩一个外星人的时候开始一动不动，最终失败。
**小结**：
个人认为，在我们的特征数据提取所提供的X向量其维数相当大，而相对来说总的记录数量相对较小，这导致了统计X=Xi的概率始终处在一个非常小的值附近，而难以产生有价值的判断依据，甚至常常需要进行拉普拉斯平滑。因而朴素贝叶斯算法在这里不太容易产生良好的测试效果。
### 1.2.2 逻辑斯蒂回归
**简介**：
逻辑斯蒂回归的本质是极大似然估计，其分类方法是对输入样本高维空间用超平面进行分割。
经典的逻辑斯蒂回归模型是一种二分类模型，在进行多分类时，通过累次进行二分类（p与除p以外的类）来达到效果。实际操作中，不同类别对应的logistic函数实际上表示的是分为此类的概率，最终返回概率最大的类别，以此来实现多分类的目标。
简单看一下二分类逻辑斯蒂回归的算法，期中调参拟合的过程由weka实现，这里只叙述分类部分。
基本的线性回归形式为：
Sigmoid函数：，可以把输入规范化到0，1之间。
将线性回归表达式套上sigmoid函数，得到：这样就把线性回归表达式的实值输出结果压缩成了一个0-1之间。但这样还是没有实现分类的效果，我们需要加一个“门槛“，若输出值大于这个门槛，那么就将其结果判断为1，反之判断为0，一般这个“门槛“都是0.5。
可以看出，逻辑斯蒂回归的输出其实表征的是当前测试样本被分到1类的概率，即[5]
虽然逻辑回归能够用于分类，不过其本质还是线性回归。它仅在线性回归的基础上，在特征到结果的映射中加入了一层sigmoid函数（非线性）映射，即先把特征线性求和，然后使用sigmoid函数来预测。然而，正是这个简单的逻辑函数，使得逻辑回归模型成为了机器学习领域一颗耀眼的明星。
这主要是由于线性回归在整个实数域内敏感度一致，而分类范围，只需要在[0,1]之内。而逻辑回归就是一种减小预测范围，将预测值限定为[0,1]间的一种回归模型。逻辑曲线在z=0时，十分敏感，在z>>0或z<<0处，都不敏感，将预测值限定为[0,1]。[6]
**训练结果**：
总体来看准确率达到了62%，相比朴素贝叶斯有了较大提升。
具体来看准确性，可以发现NIL的精确率与召回率均较高，推测agent学习人类停止动作的学习效果应当不错。而USE在精确率与召回率方面都较低，推测agent正确发射子弹可能会有困难。
再看混淆矩阵，反映了同样的情况，USE被误判为NIL的概率相当大，几乎和正确判断相当，可以预见agent将比人类玩家停止更多时间，同时发射更少的子弹。而左右平移表现相对正常。
从游戏测试来看，虽然从一开始就频繁发射，但发射命中率始终较低，从最开始就miss了一堆外星人，长时间未能有效减少外星人数量，最终碰到炸弹失败。
### 1.2.3 随机森林
**简介**：
随机森林即多棵决策树组成的森林，进行分类问题的时候依据多棵决策树的输出结果的众数进行判决，类似于我们常说的“投票”。其实从直观角度来解释，每棵决策树都是一个分类器（假设现在针对的是分类问题），那么对于一个输入样本，N棵树会有N个分类结果。而随机森林集成了所有的分类投票结果，将投票次数最多的类别指定为最终的输出，这就是一种最简单的 Bagging 思想。
每棵树的按照如下规则生成：
1. 如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本（这种采样方式称为bootstrap sample方法），作为该树的训练集；从这里我们可以知道：每棵树的训练集都是不同的，而且里面包含重复的训练样本。如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；
2. 如果每个样本的特征维度为M，指定一个常数m<<M，随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；
3. 每棵树都尽最大程度的生长，并且没有剪枝过程。
一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力。[7]
最后总结一下随机森林的优缺点：
**优点**：
- 对于大部分的数据，它的分类效果比较好。
- 能处理高维特征，不容易产生过拟合，模型训练速度比较快，特别是对于大数据而言。
- 在决定类别时，它可以评估变数的重要性。
- 对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。
**缺点**：
- 对少量数据集和低维数据集的分类不一定可以得到很好的效果。
- 计算速度比单个的决策树慢。
- 当我们需要推断超出范围的独立变量或非独立变量，随机森林做得并不好。[8]
**训练结果**：
总体来看准确率将近75%，是截止到目前效果最好的分类模型。
再说具体准确性，NIL的精确率和召回率均较高，可见agent已经较好地学习人类玩家的停止动作。而USE的精确率与召回率都不算很高，两项平均大概50%，推测agent的射击行为可能与人类玩家有一定差异，并未学习的非常好。与前两种分类算法不同的是，在这里可以发现left和right的精确率差不多，但是left的召回率明显更高，可见agent学习人类向左移动的效果相比向右移动要更好。
从混淆矩阵来看，除了NIL仍旧是一枝独秀，其余三中动作被分类到nil的比例都是相对较大的，甚至right动作分类到自身的比例都不如分类到NIL的大，而Left则相对较好。推测agent的行为可能有相当多的时间处在一动不动的状态，并且更倾向于向左移动。
从游戏结果来看，一开始在相当短的时间内agent就准确发射并快速减少了外星人的数量。在最后几个外星人时agent花费了较多的时间左右移动但是并未发射，最终成功完成游戏。
### 1.2.4 SimpleCast
**简介**：
CART算法（classification and regression tree）分类和回归算法，是一种应用广泛的决策树学习方法，既然是一种决策树学习方法，必然也满足决策树的几大步骤，即：1特征的选择 2决策树的生成 3 决策树的剪枝 三大步骤，CART算法既可以用于分类还可以用于回归。
CART是在给定输入随机变量X的条件下输出随机变量Y的条件概率分布的学习方法，CART 有个特性就是其假设决策树全部是二叉树，也就是说其结点只有两种选择，‘是’和‘否’，说专业点就是决策树递归的二分每个特征，最终得到决策树，通过不断的划分，将特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。
设结点的训练数据集为D，计算现有特征对该数据集的Gini系数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或 “否”将D分割成D1和D2两部分，计算A=a时的Gini系数。在分类问题中，假设有K个类，样本点属于第k类的概率为Pk，则概率分布的gini指数的定义为：
如果样本集合D根据某个特征A被分割为D1，D2两个部分，那么在特征A的条件下，集合D的gini指数的定义为：
gini指数Gini(D,A)表示特征A不同分组的数据集D的不确定性。gini指数值越大，样本集合的不确定性也就越大，这一点与熵的概念比较类似。
所以在此，基于以上的理论，我们可以通过gini指数来确定某个特征的最优切分点(也即只需要确保切分后某点的gini指数值最小)，这就是决策树CART算法中类别变量切分的关键所在。[9]
**性能分析**：
总体正确分类率达到74%，极差较小但方差较大。
细节准确率来看NIL的精确与回归都相当高，USE均低于五成，而引人注意的是LEFT和RIGHT的判别回归率都相当低，这在之前的分类算法中是没有出现的。因而推断agent可能不能很好地模仿人类射击的动作，同时左右移动规避子弹的能力也较低。
再看混淆矩阵，发现left项被识别为nil的概率比识别为自身的概率都大，这可能会对正常的左右移动产生较大影响。
从游戏结果来看agent移动到屏幕中间后开始射击，不再左右平移，很快被炸弹击中而失败，与预期结果相近。
# 二、特征提取方法的改进
## 2.1 总的思路
旧版的特征提取中直接使用了448个方格内的物体属性作为特征来进行学习。这样做虽然最大化了特征的完整性，但是过于具体，缺乏抽象性，可能不具备良好的学习性质。同时游戏状态是不会重复的，因而收集到的特征参数也不尽相同，这样的朴素知识获取方法，近一步降低了训练模型的抽象性与泛化能力，非常容易出现过拟合情况。
因而我们特征提取方法的改进就是，通过人为方法提取一些更加“抽象”同时自认为“有用”的特征，让机器根据这些我们人类组织出来的经验进行学习，以期望获得更好的学习成果。
## 2.2 特征改进
首先解决开头的疑惑，将4个属性分别写入4个不同的位置。进行几次train后，通过直接阅读artf文件，发现除了gametick会变之外，其他三个始终是一个定值，对他们每次分别记录是毫无意义的！
所以我们为了增加空间利用率，直接移除原449，450，451属性值，并在原位存放后续的三个我们自定义的特征。
经过测试 itype: 0-empty 2-wall 5-bomb 6-alien，同时惊讶的发现，原来竟然完全没有记录Avatar的位置，真是荒唐啊荒唐。
首先，联想到自己玩塔防游戏的经验，防御塔可以设置属性“第一个”“最强的”“最近的”“最后一个”等等攻击优先度，我们的Avatar也可以发射子弹所以应当有类似的想法—攻击优先级。因为我们知道当第一个外星人下到最后一行的时候我们就已经输了，所以优先解决第一个外星人是理所应当的，于是有了第一个特征：第一个外星人与Avatar的相对位置（左负右正）。修改双重循环的顺序，使其从后向前检索，在遍历的同时直接就把最后一个alien的位置给找出来，不浪费时间。
其次，我们的Avatar不可以碰到炸弹，而“碰到”的含义在于Avatar先离炸弹很近，接着或是主动接近，或是被动接近，导致炸弹离我们越来越近，最后碰到一起，然后你就gg了。而这中间，尤以本来就最靠近Avatar的炸弹最为凶险，所以我们专门记录它和Avatar之间的距离，因而有了第二个特征值：最近炸弹与Avatar的相对位置（左负右正）。
第三，我在train的时候发现，由于Avatar的射击有攻击间隔，因而一旦在某一位置停下来射击，只要空了一发，往往后面的连续射击也“恰好”都会空枪。这时候就需要我们进行移动，或者稍作停顿后再次射击。这给了我们一个启发，即Avatar的行动前后是有关联的，并不是简单地单纯依据游戏状态（有点类似于时序逻辑电路的感觉），所以很自然地想到，可以把先前的动作作为下一次动作的判别依据，于是有了第三个特征：上一个动作的值。
## 2.3 性能评估
**Nave-bayse：**
一开始直接走到最右边开始站桩输出，但是在一段时间之后，忽然开始返回屏幕中间位置，并不断走A，行动模式与人类玩家非常相似。不过遗憾的是在外星人数量又一次降到较低值时，不再能准确击中外星人，最终被碰撞而亡。
**Logistic:**
起初的表现十分良好，可以正确移动与发射子弹，同时移动速度非常迅速异于人类，可以看到明显的规避炸弹动作。但是在仅剩一个外星人的时候，不会发射子弹，而是频繁的左右平移，最终失败。
**Random-forest:**
起初不断走A，在外形人数量少于5个时忽然开始站撸，在外星人循环两行之后获胜。
**Simple-Cast:**
始终在屏幕最左侧站桩输出，但是射击精准，直接获胜。
总体来看，4中算法在改进特征提取后均获得了不同程度的提升。尤其是其模仿人类的能力大大增强了。仍然存在较多问题，可能的原因是数据收集过少（只有一轮游戏），以及特征提取太杂且不够优化。
# 三、结束语
采用监督学习分类模式来玩游戏的目标是模仿人类玩家的行为，可以无限模仿但是难以有本质上的超越，不过在解决许多问题上仍旧是十分有帮助的。这其中涉及到的特征提取与分类算法这两块都大有门道，值得深入探究与进一步开发。《塔希里亚故事集》里有一句话说的好，“没有低级的法术，只有低级的法师”，熟练运用监督学习，不管是对于数据分析结果预测，还是在诸如开发符合人类行为模式的游戏agent方面，都是大有裨益的。
致谢 特别感谢王宸旭同学提醒我需要认真研读混淆矩阵来书写性能评估。
### References:
Wikipedia, supervised learning, https://en.wikipedia.org/wiki/Supervised_learning
### 附中文参考文献:
1. 监督学习，https://baike.baidu.com/item/%E7%9B%91%E7%9D%A3%E5%AD%A6%E4%B9%A0
2. 朴素贝叶斯，https://blog.csdn.net/sinat_30353259/article/details/80932111#_158
3. 朴素贝叶斯算法详解https://baike.baidu.com/item/%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF/4925905?fr=aladdin#reference-[3]-992724-wrap
4. 逻辑斯蒂回归（Logistic Regression），https://blog.csdn.net/zhaojc1995/article/details/81592567
5. 【机器学习】逻辑斯蒂回归（Logistic Regression）详解，https://blog.csdn.net/qq_32742009/article/details/81516140
6. 【机器学习】 随机森林（Random Forest），https://blog.csdn.net/qq_34106574/article/details/82016442
7. Python机器学习笔记——随机森林算法！最详细的笔记没有之一，http://www.sohu.com/a/297967370_729271
8. CART树算法详解，https://blog.csdn.net/e15273/article/details/79648502
?