游戏设计中几种常用机器学习算法合集

当今机器学习算法已经广泛应用于我们的日常生活之中，每天我们需要处理的数据也在不断增加。理解数据背后的真实含义，能够帮助人们认识事物本质，提高生产效率。机器学习算法主要用于分类、回归和聚类，常用的几种算法如下所示：

• 监督分类算法

• K-邻近算法

• 决策树(ID3算法)

• 朴素叶倍斯分类器

• Logistic回归

• 支持向量机(SVM)

• AdaBoost元算法

• 回归预测

• 线性回归

• 树回归

• 无监督聚类

• K-均值聚类

• 关联分析

• Apriori算法

• FP-growth算法

• 优化技术

• 降维：PCA算法

• 降维：SVD算法

• 大数据：MapReduce

该文作为《机器学习实战》(Peter Harrington)的读后感，列举常用的机器学习算法，单看几篇文章不可能充分理解机器学习，但可以作为一个索引，知道某种算法适合解决某一类问题，需要时再仔细研究。

K-邻近算法

一种分类数据最简单有效的算法，优点是容易实现，缺点在于效率低。原理是选择与样本数据中前K个最相似的数据，将k个最相似数据中出现最多的分类，作为新数据的分类。

如下图所示是几部电影里的打斗镜头与接吻镜头所出现次数的数据，现在要计算最后一部电影的类型。

可以算出未知电影与各个电影的距离

若选择K=3，最近的两个电影是He's Not Really into Dudes，Beautiful Woman和California Man，这三部电影全是爱情片，因此判断未知电影也是爱情片。

决策树ID3算法

决策树是依照数据的不同特征做分类的方法，输出结果易于理解，容易看出各个特征的内在联系，但有可能出现过度匹配的问题。

在构造决策树时，需要解决的第一个问题是，当前数据集上哪个特征在划分数据类型时起决定性作用。为了找到决定性特征，我们必须评估每个特征。 ID3算法是一种用来构造决策树的算法，它以信息熵的下降速度为选取测试属性的标准。即在每个节点选取还尚未被用来划分的具有最高信息增益（根据  游戏设计中几种常用机器学习算法合集 计算）的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。

如下图显示的是动物的几种特征和是否属于鱼类的数据，先测试以“不浮出水面是否可以生存”和“是否有脚蹼”作为分类后信息熵大小，计算后选取分类后信息熵较大的“不浮出水面是否可以生存”分类，接着再递归剩余的特征，直到被完全分类。

朴素叶倍斯分类器

朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。假设一个数据集由N类组成，如果p(类型c|x,y)?>?p(其他类型|x,y)，那么类别为c。

假如要对留言板的留言分类，屏蔽带有侮辱性的留言。样本如下，留言已经去除了标点符号并统一大小写。

对每个类（带有侮辱性、不带侮辱性）计算 （c是分类，w是词组向量），比较大小即可得出新留言的分类。根据朴素贝叶斯假设，将w展开为一个个独立特征，那么p(w)=p(w1)*p(w2)*...p(wn)，p(w|ci)= = 。接下来只要统计各个词在样本中的出现频率，就能够解出上述式子。

Logistic回归

根据现有数据对分类边界建立回归公式，以此进行分类。线性方程 ，即 。只要确定参数w，既可计算出回归公式，进而分类。

图：逻辑回归的思想是用一个超平面将数据集分为两部分，这两部分分别位于超平面的两边，且属于两个不同类别。

梯度上升（下降）算法，是一种计算方程参数的算法。它的思想是：要找到某函数的最大值，最好的方法是沿着该函数的梯度方向搜寻。

由此对 进行多次迭代，即可找出方程参数。

支持向量机(SVM)

支持向量机会将问题当做一个“求两个类的边界距离”的最优化问题来解决。

假设你的数据点分为两类，支持向量机试图寻找最优的一条线（超平面），使得两类数据与该线的距离最大。在离边界较近的点（如下图Gap内）称为支持向量，它们对超平面有较大影响，应给予较高权重。

如果数据并非线性可分数据，可以通过核函数将数据映射成高维线性可分的数据，比如径向核函数 映射数据，如下图所示：

可以通过迭代计算SMO，其中Platt的SMO算法通过每次只优化两个alpha值来加快SVM训练速度。

AdaBoost元算法

元算法也叫集成方法，通过将其他算法进行组合而形成更优的算法，组合方式包括：不同算法的集成，数据集不同部分采用不同算法分类后的集成或者同一算法在不同设置下的集成。

Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。它给每个训练数据一个权重以达 到优化分类器的目的。每一个训练样本最开始时都被赋予相同的权重，接下来，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就 被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。

判断分类器的效果，除了使用错误率（正确率） 之外，ROC曲线也是一种分类器的评价方法。比如将“正常邮件分类成垃圾邮件”的后果要比“将垃圾邮件分类成正常邮件”严重，由此需要选择低TN值的模型。

ROC曲线是显示模型真正率和假正率之间折中的一种图形化方法。 它引入了真正率、假正率等概念。

• 真正（True Positive , TP）被模型预测为正的正样本；

• 假负（False Negative , FN）被模型预测为负的正样本；

• 假正（False Positive , FP）被模型预测为正的负样本；

• 真负（True Negative , TN）被模型预测为负的负样本。

线性回归

线性回归是中学就学到的知识，一般使用最小二乘法求解，它通过最小化误差的平方（ ）来寻找y=wx的最佳参数w。如图是一条拟合直线。

为了达到更好的拟合效果，可以使用局部加权线性回归。该算法给预测点附近的点赋予较高权重，远离的点赋予较低权重，常见的权重公式为( )，这时线性方程变成y=w1*w2*x(w1为参数，w2为权重),如下图为局部加权回归的效果。

岭回归是一种改良的最小二乘估计法，通过放弃最小二乘法的无偏性，以损失部分信息、降低精度为代价获得回归系数更为符合实际、更可靠的回归方法，对病态数据的拟合要强于最小二乘法。

树回归

现实生活中很多问题是非线性的，不可能用全局线性模型来拟合数据。一种可行的方法是将数据集切分成很多易建模的数据，然后利用线性回归技术来进行 拟合。这种切分方式下，树结构和回归法就相当有用。分类回归树（CART）它使用二元切分来处理连续型变量，回归树的策略是：遍历所有的特征，对每个特 征，遍历这个特征里所有样例的取值，计算以这个取值作为切分时，生成的两个子数据集的平方误差，我们取子数据集平方误差最小的切分方式。

K-均值聚类

K-均值聚类算法是采用距离作为相似性的评价指标的无监督聚类算法。两个对象的距离越近，相似度越大。算法过程如下：

1）随机选取K个数据作为初始质心

2）测量数据到每个质心的距离，并归类到最近的质心的类

3）重新计算各个类的质心

4）迭代2～3步直至新的质心小于指定阈值，算法结束

k均值算法的一个缺点是如果初始质心选择不好，达到局部最优解后，不一定能达到全局最优解。二分k均值算法可以达到全局最优解，主要思想是：首先将所有点作为一个簇，然后将该簇一分为二。之后将簇划分为两个簇。以此进行下去，直到簇的数目等于用户给定的数目k为止。

Apriori算法

关联分析是一种在大规模数据集中寻找关系的人物，比如要确定商场里同时买啤酒和尿布的人多不多，做优惠的时候是否应该把这两项捆绑销售。Apriori 算法是数据挖掘中一种挖掘关联规则的频繁项集算法，其核心是基于两阶段频集思想的递推算法。

假如有0,1,2,3共4种商品，要找到经常在一起购买的组合。只要扫描所有数据，使用某一组合的总数除以交易总数，就可以得到支持度，支持度大于阀值即认为频繁购买。但是遍历2^N次太费时间，因此需要一种算法来减少计算量。

如果某个项是非频繁的，那么它的子项也是非频繁的，比如{1,3}不频繁，那么{1,3,4}一定不频繁，依据这一原理（Apriori原理）， 可以大大减少计算量。Apriori算法使用一种称作逐层搜索的迭代方法，首先，找出频繁1-项集的集合，该集合记作L1。L1用于找频繁2-项集的集合 L2，而L2用于找L3，如此迭代。

FP-growth算法

Apriori算法在产生频繁模式完全集前需要对数据进行多次扫描，同时产生大量的候选频繁集，这就使Apriori算法时间和空间复杂度较大，FP-Growth算法是一种只需遍历两次数据的计算频繁项算法。

FP-Growth算法流程的基本思路是不断地迭代FP-tree的构造和投影过程。对于每个频繁项，构造它的条件投影数据库和投影FP- tree。对每个新构建的FP-tree重复这个过程，直到构造的新FP-tree为空，或者只包含一条路径。当构造的FP-tree为空时，其前缀即为 频繁模式；当只包含一条路径时，通过枚举所有可能组合并与此树的前缀连接即可得到频繁模式。

降维：PCA算法

原始数据很多特征，但这些特征不一定是独立的，通过某些算法降低数据的特征数，摒弃不重要的特征，可以降低算法开销。

PCA（Principal Component Analysis)是最常用的线性降维方法，对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面 中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空 间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。

降维：SVD

SVD（奇异值分解）是一种强大的降维工具，我们可以利用SVD来逼近矩阵并从中提取重要特征，通过保留矩阵80%-90%的能力，就可以得到重要特征并去除噪声。

SVD给出一个与原始数据A同大小的对角矩阵S（由Σ的特征值组成），两个酉矩阵U和V，且满足= U*S*V'。若A为m×n阵，则U为m×m阵，V为n×n阵。奇异值在S的对角线上，非负且按降序排列。那么对于方阵Σ呢，就有

Σ = USV'

ΣΣ' = USV'*VS'U' = U(ΣΣ')U'

Σ'Σ = VS'U'*USV' = V(Σ'Σ)V'

U是ΣΣ'的特征向量矩阵；

V是Σ'Σ的特征向量矩阵，都是n*n的矩阵

由于方阵的SVD相当于特征值分解，所以事实上U = V, 即Σ = USU', U是特征向量组成的正交矩阵，我们的目的是，从n维降维到k维，也就是选出这n个特征中最重要的k个，也就是选出特征值最大的k个。

大数据：MapReduce

当数据大到无法使用一台机器计算时，可以使用分布式计算。一个典型的MapReduce分布式作业流程先使用map阶段并行处理数据。之后将这些数据在Reduce阶段合并。MapReduce处理大数据的过程如下。