各种智能算法的总结汇总
7. 聚类算法
7.1 k-means （k 均值）
7.1.1算法定义以及原理：
定义：k 均值聚类算法（k -means clustering algorithm ）是一种迭代求解的聚类分析算法，其步骤是随机选取K 个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。 原理：K -Means 算法是一种无监督分类算法，假设有无标签数据集：
()()()12...m x x X x ??
????=??
??????
该算法的任务是将数据集聚类成K 个簇12k ,,...,C C C C =，最小化损失函数为：
2
1i
k
i
i x C E x μ=∈=-∑∑ （1）
其中i μ为簇i C 的中心点：
1
i
i x C i
x
C μ∈=
∑ （2）
要找到以上问题的最优解需要遍历所有可能的簇划分，K -Means 算法使用贪心策略求得一个近似解，具体步骤如下：
（1）在样本中随机选取k 个样本点充当各个簇的中心点{}
12,,...,k μμμ。
（2）计算所有样本点与各簇中心之间的距离()
(
)
,i j dist x μ,然后把样本点划入最近的簇中
()i nearest x μ∈。
（3）根据簇中已有的样本点，重新计算簇中心
1
:i
i x C i
x C μ∈=
∑
（4）重复2，3
7.1.2 算法特点
优点：容易实现。
缺点：可能收敛到局部最小值，在大规模数据上收敛较慢。
适合数据类型：数值型数据。
7.1.3聚类过程
（1）创建k个点作为k个簇的起始质心（经常随机选择）。
（2）分别计算剩下的元素到k个簇中心的相异度（距离），将这些元素分别划归到相异度最低的簇。
（3）根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均值。
（4）将D中全部元素按照新的中心重新聚类。
（5）重复第4步，直到聚类结果不再变化。
（6）最后，输出聚类结果。
7.1.4算法实现
创建k个点作为K个簇的起始质心（经常随机选择）
当任意一个点的蔟分配结果发生变化时（初始化为True）
对数据集中的每个数据点，重新分配质心
对每个质心
计算质心到数据点之间的距离
将数据点分配到距其最近的蔟
对每个蔟，计算蔟中所有点的均值并将均值作为新的质心
7.1.5算法总结与讨论
虽然K-Means算法原理简单，但是也有自身的缺陷：
（1）首先，聚类的簇数K值需要事先给定，但在实际中这个K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。
（2）K-Means需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果，不能保证K-Means算法收敛于全局最优解。针对此问题，在K-Means的基础上提出了二分K-Means算法。该算法首先将所有点看做是一个簇，然后一分为二，找到最小SSE 的聚类质心。接着选择其中一个簇继续一分为二，此处哪一个簇需要根据划分后的SSE值来判断。
（3）对离群点敏感。
（4）结果不稳定（受输入顺序影响）。
（5）时间复杂度高O(nkt)，其中n是对象总数，k是簇数，t是迭代次数。
7.1.6确定K 个簇的初始质心的方法
（1） 选择批次距离尽可能远的K 个点
首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出K 个初始类簇中心点。
（2） 选用层次聚类或者Canopy 算法进行初始聚类，然后利用这些类簇的中心点作为K-Means 算法初始类簇中心点。
7.2模糊c-均值聚类算法
7.2.1 FCM 算法的概念
模糊c-均值聚类算法 fuzzy c-means algorithm (FCMA)或称（ FCM ）。在众多模糊聚类算法中，模糊C-均值（ FCM ） 算法应用最广泛且较成功，它通过优化目标函数得到每个样本点对所有类中心的隶属度，从而决定样本点的类属以达到自动对样本数据进行分类的目的。
7.2.2 FCM 算法原理
假定我们有数据集X ，我们要对X 中的数据进行分类，如果把这些数据划分成C 个类的话，那么对应的就有C 类中心为i C ，每个样本j x 属于某一类i C 的隶属度定为ij u ，那么定义一个FCM 目标函数及其约束条件如下：
2
11
c n
m
ij
j i i j J u
x c ===-∑∑ (3)
1
1,1,2,...,c
ij
i u
j n ===∑ (4)
目标函数(式3)由相应样本的隶属度与该样本到各类中心的距离相乘组成的，式4为约束条件，也就是一个样本属于所有类的隶属度之和要为1。式1中的m 是一个隶属度的因子，一般为2 ，
j i
x c - 表示
j
x 到中心点
i
c 的欧式距离。
ij u 的迭代公式为：
21
1
1
ij m i j C
k i k u x c x c -==
??-
? ?-??
∑
（5）
i C 的迭代公式：
11*N m i ij i j
N m i ij
u x C u
===
∑∑ （6）
我们发现ij u 和i C 是相互关联的，彼此包含对方,程序一开始会随机生成一个ij u ，只要数值满足条件即可，然后开始迭代，通过ij u 计算出i C ，有了i C 又可以计算出ij u ，反反复复，这个过程中目标函数J 一直在变化，逐渐绉向稳定。那么当J 不在变化时就认为算法收敛到一个较好的结果了。
7.2.3 FCM 算法步骤
（1）确定分类数，指数m 的值，确定迭代次数 。 （2）初始化一个隶属度U （注意条件和为1）。 （3）根据U 计算聚类中心C 。 （4）这个时候可以计算目标函数J 了。
（5）根据C 返回去计算U ，回到步骤3，一直循环直到结束。
7.3 SOM （自组织映射网络）
7.3.1 SOM 的定义
它模拟人脑中处于不同区域的神经细胞分工不同的特点，即不同区域具有不同的响应特征，而且这一过程是自动完成的。自组织映射网络通过寻找最优参考矢量集合来对输入模式集合进行分类。每个参考矢量为一输出单元对应的连接权向量。与传统的模式聚类方法相比，它所形成的聚类中心能映射到一个曲面或平面上，而保持拓扑结构不变。对于未知聚类中心的判别问题可以用自组织映射来实现。
7.3.2 SOM 的特点
自组织神经网络是神经网络最富有魅力的研究领域之一，它能够通过其输入样本学会检测其规律性和输入样本相互之间的关系，并且根据这些输入样本的信息自适应调整网络，使网络以后的响应与输入样本相适应。竞争型神经网络的神经元通过输入信息能够识别成组的相似输入向量；自组织映射神经网络通过学习同样能够识别成组的相似输入向量，使那些网络层中彼此靠得很近的神经元对相似的输入向量产生响应。与竞争型神经网络不同的是，自组织映射神经网络不但能学习输入向量的分布情况，还可以学习输入向量的拓扑结构，其单个神经元对模式分类不起决定性作用，而要靠多个神经元的协同作用才能完成模式分类。
7.3.3 SOM 的工作原理
先来了解它是如何工作的，用随机值或从输入中随机采样对连接权重进行初始化，网格中的每个神经元都被赋予一个位置。数据输入后，测量输入向量（X ）和所有神经元权向量（W ）之间的距离，与输入数据距离最小的神经元为胜者（WTU ），距离度量如下：
j d =
（7）
其中，
j
d 是神经元 j 的权重与输入X 之间的距离，最小距离的神经元是胜者。
第二步，调整获胜神经元及其邻域神经元的权重，以确保如果下一次是相同的输入，则胜者还是同一个神经元。网络采用邻域函数
()
r Λ确定哪些邻域神经元权重需要修改，通常使用
高斯墨西哥帽函数作为邻域函数，数学表达式如下：
()2
22d r e σ
Λ=- （8）
其中，σ 是随时间变化的神经元影响半径，d 是距离获胜神经元的距离。邻域函数的一个重要特性是它的半径随时间而减小，这样刚开始时较多邻域神经元权重被修改，但是随着网络的学习，最终只有少量的神经元的权重被修改（有时只有一个或没有）。权重的改变由下式计算：
()
dW X W η=Λ- （9）
按照这个方法继续处理输入，重复执行给定的迭代次数。在迭代过程中利用一个与迭代次数相关的因子来减少学习率和影响半径。
8.分类算法
8.1.k-NN （k 近邻）
8.1.1 K -NN 算法的概念
K 近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K 个实例，这K 个实例的多数属于某个类，就把该输入实例分类到这个类中。这就类似于现实生活中少数服从多数的思想。 下面通过一个简单的例子说明一下：如下图，
图8-1 样本数据图
如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。这也就是我们的目的，来了一个新的数据点，我要得到它的类别是什么？好的，下面我们根据k 近邻的思想来给绿色圆点进行分类。
如果K=3，绿色圆点的最邻近的3个点是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。如果K=5，绿色圆点的最邻近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
从上面例子我们可以看出，k 近邻的算法思想非常的简单，也非常的容易理解，那么我们是不是就到此结束了，该算法的原理我们也已经懂了，也知道怎么给新来的点如何进行归类，只要找到离它最近的k 个实例，哪个类别最多即可。
8.1.2 距离的度量
在上文中说到，k 近邻算法是在训练数据集中找到与该实例最邻近的K 个实例，这K 个实例的多数属于某个类，我们就说预测点属于哪个类。
定义中所说的最邻近是如何度量呢？我们怎么知道谁跟测试点最邻近。这里就会引出我们几种度量两个点之间距离的标准。我们可以有以下几种度量方式： 设特征空间Z 是n 维实数向量空间n
R ，,i j x x Z ∈,()()()()
(
)
123,,,...,T
n i i i i i
x x x x x =，
()()()()
(
)123,,,...,T
n j j j j j
x x x x x =,,
i j
x x 的P
L
距离定义为
()()
()
11,p
p
n l l p i j i j l L x x x x =??
=- ? ?
?
?∑ （10）
这里1p ≥，当p=2时，称为欧氏距离，即
()()
()
12
21,p
n l l i j i j l L x x x x =??
=- ? ?
?
?∑ （11）
当p=1时，称为曼哈顿距离，即
()()()
11
,n
l l i j i j l L x x x x ==-∑ （12）
当p =∞时，它是各个坐标距离的最大值，即
()()()
,max l
l
i j i j l
L x x x x ∞=- （13）
其中当p=2的时候，就是我们最常见的欧式距离，我们也一般都用欧式距离来衡量我们高维空间中俩点的距离。在实际应用中，距离函数的选择应该根据数据的特性和分析的需要而
定，一般选取p=2欧式距离表示。
8.1.3 K-NN算法
K-NN算法的思想总结如下：就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K 个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：
（1）初始化距离为最大值。
（2）计算未知样本和每个训练样本的距离dist,然后对所有的距离进行排序，选择前k个距离。
（3）得到目前K个最临近样本中的最大距离maxdist
（4）如果dist小于maxdist，则将该训练样本作为K-最近邻样本，然后在邻近样本空间中选择最多的类别。
（5）重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完
（6）统计K-最近邻样本中每个类标号出现的次数
（7）选择出现频率最大的类标号作为未知样本的类标号
8.2决策树之ID3算法
8.2.1 决策树的基本认识
决策树是一种依托决策而建立起来的一种树。在机器学习中，决策树是一种预测模型，代表的是一种对象属性与对象值之间的一种映射关系，每一个节点代表某个对象，树中的每一个分叉路径代表某个可能的属性值，而每一个叶子节点则对应从根节点到该叶子节点所经历的路径所表示的对象的值。决策树仅有单一输出，如果有多个输出，可以分别建立独立的决策树以处理不同的输出。
8.2.2 ID3算法介绍
ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。ID3算法，即Iterative Dichotomiser 3，迭代二叉树3代，是Ross Quinlan发明的一种决策树算法，这个算法的基础就是上面提到的奥卡姆剃刀原理，越是小型的决策树越优于大的决策树，尽管如此，也不总是生成最小的树型结构，而是一个启发式算法。在信息论中，期望信息越小，那么信息增益就越大，从而纯度就越高。ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。
8.2.3 信息熵与信息增益
在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。在认识信息增益之前，先来看看信息熵的定义。熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵是对不确定性的度量。在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，
一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。
假如一个随机变量X 的取值为{}12,,...,n X x x x =，每一种取到的概率分别是
{}11p ,p ,...,p n ，那么X 的熵定义为()21
log n
i i i H X p p ==-∑，这个公式的含义是一个变量的
变化情况可能越多，那么它携带的信息量就越大。对于分类系统来说，类别C 是变量，它的取值是12,,...,n C C C ，而每一个类别出现的概率分别是()()()12,,...,n P C P C P C 。而这里的n 就是类别的总数，此时分类系统的熵就可以表示为：
()()()
21
log n
i i i H C P C P C ==-∑ （14）
信息增益是针对一个一个特征而言的，就是看一个特征t ，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。接下来以天气预报的例子来说明。下面是描述天气数据表，学习目标是play 或者not play 。
图8-2 天气预报数据例子
可以看出，一共14个样例，包括9个正例和5个负例。那么当前信息的熵计算如下：
()229955
log log 0.94028614141414Entropy S =-
-= （15）
在决策树分类问题中，信息增益就是决策树在进行属性选择划分前和划分后信息的差值。假设利用属性Outlook 来分类，那么如下图：
图8-3 天气预报属性划分图
这些属性划分后，数据被分为三部分了，那么各个分支的信息熵计算如下：
()222233
n log log 0.970951
5555E tropy sunny =--= (16) ()2244
n log 0log 00
44E tropy overcast =--*= (17) ()223322
n log log 0.970951
5555E tropy rainy =--= (18)
那么划分后的信息熵为：
()545
n 0.97095100.9709510.693536141414E tropy S T =
*+*+*= (19)
()Entropy S T 代表在特征属性T 的条件下样本的条件熵。那么最终得到特征属性T 带来
的信息增益为：
()()()0.24675
IG T Entropy S Entropy S T =-= (20)
信息增益的计算公式如下：
()()()
()v
v value T S IG S T Entropy S Entropy S S
=-
∑
(21)
其中S 为全部样本集合，value(T ）是属性T 所有取值 的集合，v 是T 的其中一个属性值，v S 是S 中属性T 的值为v 的样例集合，v S 为v S 中所含样例数。
在决策树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益，选择最大信息增益的属性来划分，因为信息增益越大，区分样本的能力就越强，越具有代表性，很显然这是一种自顶向下的贪心策略。因为信息增益越大，说明有该属性与无该属性时的信息熵相差很多。信息增益是有该属性与无该属性之间的差值，信息增益越大说明该属性的信息熵越大或者说占比很大，含有信息量越大，信息还有的可能性更多，则区分样本的能力越强，易于区分样本。
8.2.4 ID3算法缺陷
（1）抗噪声性差，如果数据样本数量太少或噪声太大，就会产生过拟合的问题。 （2）样本少，其树的构成基本上就是为少数样本量身定做的树，如果噪声太大，或样本少且有噪声的话，很多树枝都是噪声拟合出来的。
（3）在选择最优特征时，很容易倾向于选择“特征值种类较多”的特征，作为分类特征。举个极端点的例子，假设有100个样本集，现在有一个特征其数值种类也是100，如果按该特征分类，就能把这个样本集分成100份，每份一个样本。在用ID3算法做决策树时，肯定会选择这个特征作为第一个最优特征，因为这个特征分出来的样本集每一个纯度都是最高。
（4）无法处理特征值为连续型数据的特征。（不过可以考虑把连续型数据转化成离散型数据），即，可以处理像性别特征、boolen 特征等离散型特征，但没法处理特征值在某个区间内可以任意取值的特征，如身高特征、年龄特征。
8.3 C4.5
8.3.1 C4.5的概念
C4.5算法是用于生成决策树的一种经典算法，是ID3算法的一种延伸和优化。C4.5算法对ID3算法主要做了一下几点改进：
（1）通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足；
（2）能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理； （3）构造决策树之后进行剪枝操作； （4）能够处理具有缺失属性值的训练数据。
C4.5算法训练的结果是一个分类模型，这个分类模型可以理解为一个决策树，分裂属性就是一个树节点，分类结果是树的结点。每个节点都有左子树和右子树，结点无左右子树。
8.3.2 C4.5与信息增益率
分裂属性选择的评判标准是决策树算法之间的根本区别。区别于ID3算法通过信息增益选择分裂属性，C4.5算法通过信息增益率选择分裂属性。 假设以属性A 作为分裂属性(分裂结点)，属性A 的“分裂信息”(split information)如下：
()2
1
log m
j j A j S S SplitInfo S S
S
==-∑
（22）
其中，训练数据集S 通过属性A 的属性值划分为m 个子数据集，j S 表示第j 个子数据集中样本数量，S 表示划分之前数据集中样本总数量。以上文中的天气预报作为示例，A 是Outlook ，则A 有三个子数集分别有5、4、5个样本。 通过属性A 分裂之后样本集的信息增益为：
()()()
,A InfoGain S A E S E S =- （23）
通过属性A 分裂之后样本集的信息增益率：
()()
()
,,A InfoGain S A InfoGainRation S A SplitInfo S =
（24）
通过C4.5算法构造决策树时，信息增益率最大的属性即为当前节点的分裂属性，随着递归计算，被计算的属性的信息增益率会变得越来越小，到后期则选择相对比较大的信息增益率的属性作为分裂属性。
8.3.3 C4.5算法流程
如下图所示：
图8-4 C4.5算法流程
8.4 随机森林
8.4.1 随机森林的基本概念
随机森林分解开来就是“随机”和“森林”。“随机”的含义我们之后讲，我们先说“森林”，森林是由很多棵树组成的，因此随机森林的结果是依赖于多棵决策树的结果，这是一种集成学习的思想。森林里新来了一只动物，森林举办森林大会，判断这到底是什么动物，每棵树都必须发表意见，票数最多的结果将是最终的结果。随机森林最终的模型见下图示：
图8-5 随机森林模型图
8.4.2 随机森林之如何构建每棵树
假设共有N个样本，M个特征。这里我们讲“随机”的含义。对于每棵树都有放回的随
N的样本作为训练集，再有放回的随机选取m个机抽取训练样本，这里抽取随机抽取2/3
=。这就是“随机”两层含义，一个是随机特征作为这棵树的分枝的依据，这里要注意m M
选取样本，一个是随机选取特征。这样就构建出了一棵树，需要注意的是这里生成的树都是完全生长的树(关于为什么是要完全生长的树，我认为的原因是便于计算每个特征的重要程度，剪枝的话将无法进行计算)。一棵树的构建方式如下图所示：
图8-6 每棵树的构建方式图
按照这种方法，可以构建出很多棵树，那么这么多棵树综合评判的结果可以作为最后的结果吗？当然不是的，随机森林真正厉害的地方不在于它通过多棵树进行综合得出最终结果，而是在于通过迭代使得森林中的树不断变得优秀(森林中的树选用更好的特征进行分枝)。上面的一个森林相当于第一次迭代得到的森林。
8.4.3 选出优秀特征的方法
随机森林的思想是构建出优秀的树，优秀的树需要优秀的特征。那我们需要知道各个特征的重要程度。对于每一棵树都有个特征，要知道某个特征在这个树中是否起到了作用，可以随机改变这个特征的值，使得“这棵树中有没有这个特征都无所谓”，之后比较改变前后的测试集误差率，误差率的差距作为该特征在该树中的重要程度，测试集即为该树抽取
2/3N 样本之后剩余的样本(袋外样本)(由袋外样本做测试集造成的误差称为袋外误差)。在
一棵树中对于m 个特征都计算一次，就可以算出m 个特征在该树中的重要程度。我们可以计算出所有树中的特征在各自树中的重要程度。但这只能代表这些特征在树中的重要程度不能代表特征在整个森林中的重要程度。那我们怎么计算各特征在森林中的重要程度呢?每个特征在多棵数中出现，取这个特征值在多棵树中的重要程度的均值即为该特征在森林中的重要程度。如下式：
()()121
1ntree
i t t t MDA A errooB errooB ntree ==-∑ （25）
其中ntree 表示特征i
A 在森林中出现的次数。
1
t errooB 表示第t 棵树中
i
A 属性值改变之
后的袋外误差，
2
err t ooB 表示第t 棵树中正常
i
A 值的袋外误差。可以用下图来表示：
图8-7 选出优秀特征的方法的图
这样就得到了所有特征在森林中的重要程度。将所有的特征按照重要程度排序，去除森林中重要程度低的部分特征，得到新的特征集。这时相当于我们回到了原点，这算是真正意义上完成了一次迭代。
8.4.4 选出最优秀的森林的方法
按照上面的步骤迭代多次，逐步去除相对较差的特征，每次都会生成新的森林，直到剩余的特征数为为止。最后再从所有迭代的森林中选出最好的森林。迭代的过程如下图所示：
图8-8 选出最优秀的森林的方法图
得到了每次迭代出的森林之后，我们需要选择出最优秀的森林(随机森林毕竟是集成学习，所以最后的森林不一定是最优的，一个诸葛亮不一定顶的上三个臭皮匠)。那么我们怎么比较这些森林的好坏呢？这时我们需要引入一个指标OOB来评价一个森林的好坏，上面的OOB用于评价套外样本在树中的误差率，这里的OOB评价套外样本在森林中的误差率。(因为都是利用套外样本，所以名字都是(out-of-bag))。
每个样本在多棵树中是套外样本，通过多棵树的预测这个样本的结果。预测方式如下图所示：
图8-9 预测方法图
预测出所有所有样本的结果之后与真实值进行比较，就可以得到这个森林的套外误差率。选择套外误差率最小的森林作为最终的随机森林模型，即本文的第一张图。
8.4.5 随机森林优缺点总结
（1）由于采用了集成算法，本身精度比大多数单个算法要好，所以准确性高。
（2）在测试集上表现良好，由于两个随机性的引入，使得随机森林不容易陷入过拟合（样本随机，特征随机）。
（3）在工业上，由于两个随机性的引入，使得随机森林具有一定的抗噪声能力，对比其他算法具有一定优势。
（4）由于树的组合，使得随机森林可以处理非线性数据，本身属于非线性分类（拟合）模型
（5）它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化
（6）训练速度快，可以运用在大规模数据集上
（7）可以处理缺省值（单独作为一类），不用额外处理
（8）由于有袋外数据（OOB），可以在模型生成过程中取得真实误差的无偏估计，且不损失训练数据量
（9）在训练过程中，能够检测到feature间的互相影响，且可以得出feature的重要性，具有一定参考意义
（10）由于每棵树可以独立、同时生成，容易做成并行化方法
（11）由于实现简单、精度高、抗过拟合能力强，当面对非线性数据时，适于作为基准模型缺点
（1）当随机森林中的决策树个数很多时，训练时需要的空间和时间会比较大
（2）随机森林中还有许多不好解释的地方，有点算是黑盒模型。
（3）在某些噪音比较大的样本集上，RF的模型容易陷入过拟合。
9．相关性分析
9.1 典型相关性分析（CAA ）*
9.1.1 典型相关分析的概念
典型相关分析（canonical corrrelatioin analysis ）就是利用综合变量对之间的相对关系来反映两组指标之间的相对关系来反映两组指标之间的整体相关性的多元统计分析方法。它的基本原理是：为了从总体上把握两组指标之间的相关关系，分别在两组变量中提取有代表性的两个综合变量
1
U 和
1
V （分别为两个变量组中各变量的线性组合），利用这两个综合变量
之间的相关关系来反映两组指标之间的整体相关性。
9.1.2 条件：
典型相关分析有助于综合地描述两组变量之间的典型的相关关系。其条件是,两组变量都是连续变量,其资料都必须服从多元正态分布。
9.1.3 相关计算
如果我们记两组变量第一组线性组合为：
'11u X α=
'11v Y
β=
()
'
111121,,...,P αααα= ()
'
111211,,...,q ββββ=
()()'
'11
1111Var u aVar X ααα===∑ ()()''11112211
Var v Var Y ββββ===∑
典型相关分析就是求
1
α和
1
β，使两者的相关系数ρ达到最大。
()()11
'',11111121
,,u v Cov u v Cov X Y ραβαβ===∑
典型相关分析希望寻求a 和b 使得ρ达到最大，单是由于随机变量乘以常数时不改变他们的相关系数，为了防止不必要的结果重复出现，最好的限制是令()1Var U =和
()1
Var V =。
（1）实测变量标准化； （2）求实测变量的相关阵R;
()1,...,P X X X = ()1,...,q Y Y Y =
()()
11
11111
11111111
1p q xx xy p pp p pq yx
yy p q q qp q qq p q p q r r r r R R r r r r XX XY R R R r r r r YX
YY r r r r +?+??
?
? ?
??
??=== ?
?
? ? ????? ?
?
???∑∑∑∑L L M M M M M M L L L L M M M M M M L L （3）求A 和B;
()()
1
1
A XX XY YY YX --=∑∑∑∑ ()
()
1
1
B YY YX XX XY --=∑∑∑∑
（4）求A 和B 的特征根及特征向量
12p λλλ≥≥≥L
A 关于i λ的特征向量()
12,,...,i i ip a a a ，求B 关于i λ的特征向量()
12,,...,p i i i b b b （5）计算i V 和i W
1122...i i i ip p V b X b X b X =+++ 1122...i i i iq q W a Y a Y a Y =+++
（6）
i V 和i W 的第i
对典型相关系数i r =应用典型相关分析的场合是：可以使用回归方法，但是两个或两个以上的因变量；特别是因变量或准则变量相互间有一定的相关性，无视它们之间相互依赖的关系而分开处理，研究 就毫无意义。另一种有效用法是检验X 变量集合和Y 变量集合间的独立性。
9.1.4典型相关系数的检验
典型相关分析是否恰当，应当取决于两组原变量之间是否相关，如果两组变量之间毫无相关性而言，则不应该作典型相关分析。用样本来估计总计的典型相关系数是否有误，需要进行检验。在原假设为真的情况下，检验的统计量为：
()()00111ln 2Q n p q ??
=---++Λ????
近似服从自由度为pq 的2
χ分布。在给定的显著性水平α下，如果()22
pq χχ≥，则拒绝
假设，认为至少第一对典型变量之间的相关性显著。
9.2 协方差分析
9.2.2 协方差的概念
协方差分析亦称“共变量（数）分析”。方差分析的引申和扩大。基本原理是将线性回归与方差分析结合起来，调整各组平均数和 F 检验的实验误差项，检验两个或多个调整平均数有无显著差异，以便控制在实验中影响实验效应（因变量）而无法人为控制的协变量（与因变量有密切回归关系的变量）在方差分析中的影响。例如，在研究某种教学方法（实验变量）对学业成绩（实验效应）的影响时，被试的原有知识基础同时影响学业成绩，但往往在实验中难以选取具备相同知识基础的被试参加实验，可用协方差分析从学业成绩的总变异中将归因于被试知识基础差异的部分划分出去，便于确切地分析教学方法对学业成绩的影响，其中被试的知识基础就是协变量。
协方差是分析是研究方差分析模型与回归模型的一种线性模型：
12e Y X X αβ=++
0Ee =
()2N D e I σ=
式中，1X α是模型的方差分析部分，设计矩阵1X 中元素一般取值0或1。
参数向量α有一定的约束条件：2X β是模型的回归部分，设计矩阵2X 中变量是连续的。因为含有两种类型因素（连续型，属性型）的混合，故称之为协方差分析模型。但是这两部分不能同等对待，主要的还是方差分析部分，而回归部分只是因某些变量完全人为地控制而不得已引入的。 第一步，由
21Y X X e βα-=+
求出α的最小二乘估计
()()1
1
112T
T X X X Y X αβ-=-
第二步，由12Y X X e αβ-=+，求出β的最小二乘估计
()()1
2221T T
X X X Y X βα-=-
由
()()()()1122112221T T T T
X X X Y X X X X Y X ααβα--?=-?
??=-?
在某些约束条件下解出的,αβ，便是协方差模型中参数向量,αβ的最小二乘估计。
9.2.4 意义
当研究者知道有些协变量会影响应变量，却不能够控制和不敢兴趣时（当研究学习时间对学习绩效的影响，学生原来的学习基础，智力学习兴趣就是协变量），可以在实验处理前予以观测，然后在统计时运用协方差分析来处理。将协变量对因变量的影响从自变量中分离出去，可以进一步提高实验精确度和统计检验灵敏度。方差是用来度量单个变量“自身变异”大小的总体参数，方差越大，该变量的变异越大；协方差是用来度量两个变量之间“协同变异”大小的总体参数，即两个变量相互影响大小的参数，协方差的绝对值越大，两个变量相互影响越大。对于仅涉及单个变量的试验资料，由于其总变异仅为“自身变异”（如单因素完全随机设计试验资料，“自身变异”是指由处理和随机误差所引起的变异），因而可以用方差分析法进行分析；对于涉及两个变量的试验资料，由于每个变量的总变异既包含“自身变异”又包含了“协同变异”（是指由另一个变量所引起的变异），须采用协方差分析法进行分析，才能得到正确结论。
9.3 相关系数分析
9.3.1 相关系数的定义
相关性分析可以用来验证两个变量间的线性关系，从相关系数r 我们可以知道两个变量是否呈现线性关系。线性关系的强弱，以及是正相关还是负相关。 其中线性相关系数的定义式：
()
,r ,Cov X Y X Y =
其中，Cov(X,Y)为X 与Y 的协方差，Var[X]为X 的方差，Var[Y]为Y 的方差。
9.3.2 适用场合
（1）当你有成对的数字数据时；
（2）当你画了一张散点图，发现数据有线性关系时； （3）当你想要用统计的方法测量数据是否落在一条线时。
9.3.3实施步骤
尽管人工可以进行相关性分析，然而计算机软件可以使计算更加简便。按照以下的介绍来使用你的软件。
（1）分别计算出相关系数r ，它介于-1到1之间。 （2）如果r 接近0则两个变量没有线性相关性。 （3）当r 接近-1或者1，说明两个变量线性关系很强；
（4）正的r 值代表当y 值很小时x 值也很小，当Y 值很大时r 值也很大； （5）负的r 值代表当y 值很大时x 值很小，反之亦然。
9.3.4 示例
下图一到图四给出了两个变量不同关系时的散点图。图一给出了一个近似完美的线性关
人工智能经典考试题目,例题
基于规则的专家系统 1.基于规则的专家系统有5个部分组成：知识库、数据库、推理引擎、____和用户界面 A.解释设备 B.外部接口 C.开发者接口 D.调试工具 2.前向（正向）推理是数据驱动的。推理从已知的数据开始，依次执行每条可执行的规则，规则所产生的新的事实被加入到数据库中，直到没有规则可以被执行为止。请根据以下的数据库和知识库推出有哪些元素被加入到数据库中 A. N X Y Z B. L X Y Z C. N L X Z
D. L N X Y 3.关于专家系统，以下说法错误的是 A.允许不精确的推理，但不能处理不完整、不确定和模糊的数据 B.当数据不完账或模糊时，有可能会出错 C.当需要新知识时，很容易实现调整。 D.提供知识与处理过程明确分离的机制 4.对于规则的专家系统的缺点，下列说法错误的是 A.规则之间的关系不明确 B.低效的搜索策略 C.没有学习能力 D.没有统一的结构 5.对于规则的专家系统的优点，下列说确的是 A.规则之间的关系透明
B.高效的搜索策略 C.处理不完整、不确定的知识 D.具备学习能力 基于规则的专家系统中的不确定性管理 6.专家系统中不确定性知识的来源一般分为4种：弱暗示、____、未知数据，以及合并不同专家观点时的困难 A.不完整的信息 B.不一致的信息 C.不确定的信息 D.不精确的语言
7.有一同学，考试成绩数学不及格的概率是0.15，语文不及格的概率是0.05，两者都不及格的概率为0.03，在一次考试中，已知他数学不及格，那么他语文不及格的概率是多少？ A.0.2 B.0.25 C.0.4 D.0.6 8.掷三枚骰子，事件A为出现的点数之和等于5的概率为 A.1/18 B.1/36 C.1/72 D.1/108 9.下列哪个符合著名的贝叶斯公式 A.P(Ai/B) = P(Ai) x P(B/Ai) /Σ(P(Aj) x P(B/Aj)) B.P(Ai/B) = P(Ai) x P(Ai/B) /Σ(P(Aj) x P(B/Aj)) C.P(Ai/B) = P(B) x P(B/Ai) /Σ(P(Aj) x P(B/Aj))
各种排序算法的总结和比较
各种排序算法的总结和比较 1 快速排序（QuickSort） 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 （1）如果不多于1个数据，直接返回。 （2）一般选择序列最左边的值作为支点数据。（3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4）对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。 2 归并排序（MergeSort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。 3 堆排序（HeapSort） 堆排序适合于数据量非常大的场合（百万数据）。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序（InsertSort） 插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。
Python学习笔记：八大排序算法!
一、插入排序 介绍 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。 算法适用于少量数据的排序，时间复杂度为O(n^2)。 插入排算法是稳定的排序方法。 步骤 ①从第一个元素开始，该元素可以认为已经被排序 ②取出下一个元素，在已经排序的元素序列中从后向前扫描 ③如果该元素（已排序）大于新元素，将该元素移到下一位置 ④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 ⑤将新元素插入到该位置中 ⑥重复步骤2 排序演示
算法实现 二、冒泡排序 介绍 冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为O(n^2)。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。原理 循环遍历列表，每次循环找出循环最大的元素排在后面； 需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。 步骤 ①比较相邻的元素。如果第一个比第二个大，就交换他们两个。 ②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 ③针对所有的元素重复以上的步骤，除了最后一个。 ④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法实现： 三、快速排序 介绍 快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。 基本思想 快速排序的基本思想是：挖坑填数+ 分治法。 首先选出一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 实现步骤
推荐系统的架构
本文从互联网收集并整理了推荐系统的架构，其中包括一些大公司的推荐系统框架（数据流存储、计算、模型应用），可以参考这些资料，取长补短，最后根据自己的业务需求，技术选型来设计相应的框架。后续持续更新并收集。。。 图1 界面UI那一块包含3块东西：1) 通过一定方式展示推荐物品(物品标题、缩略图、简介等)；2) 给的推荐理由；3) 数据反馈改进个性化推荐；关于用户数据的存放地方：1)数据库/缓存用来实时取数据；2) hdfs文件上面； 抽象出来的三种推荐方式 图2
图3 图3中，推荐引擎的构建来源于不同的数据源(也就是用户的特征有很多种类，例如统计的、行为的、主题的)+不同的推荐模型算法，推荐引擎的架构可以试多样化的(实时推荐的+离线推荐的)，然后融合推荐结果（人工规则+模型结果），融合方式多样的，有线性加权的或者切换式的等 图4 图4中，A模块负责用户各类型特征的收集，B模块的相关表是根据图3中的推荐引擎来生成的，B模块的输出推荐结果用来C模块的输入，中间经过过滤模块(用户已经产生行为的物品，非候选物品，业务方提供的物品黑名单等)，排名模块也根据预设定的推荐目标来制定，最后推荐解释的生成（这是可能是最容易忽视，但很关键的一环，微信的好友推荐游戏，这一解释已经胜过后台的算法作用了） HULU的推荐系统
总结：这个也就跟图3有点类似了，葫芦的推荐系统，至少在他blog中写的比较简单。更多的是对推荐系统在线部分的一种描述，离线部分我猜想也是通过分布式计算或者不同的计算方式将算法产生的数据存储进入一种介质中，供推荐系统在线部分调用。系统的整个流程是这样的，首先获取用户的行为，包括(watch、subscribe、vote)，这样行为会到后台获取show-show对应的推荐数据。同时这些行为也会产生对应的topic，系统也会根据topic 到后台获取topic-show对应的推荐数据。两种数据进行混合，然后经过fliter、explanation、ranking这一系列过程，最后生成用户看到的推荐数据。 淘宝的推荐系统(详细跟简单版)
人工智能之机器学习常见算法
人工智能之机器学习常见算法 摘要机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作中都或多或少会用到机器学习的算法。这里小编为您总结一下常见的机器学习算法，以供您在工作和学习中参考。 机器学习的算法很多。很多时候困惑人们都是，很多算法是一类算法，而有些算法又是从其他算法中延伸出来的。这里，我们从两个方面来给大家介绍，第一个方面是学习的方式，第二个方面是算法的类似性。 学习方式 根据数据类型的不同，对一个问题的建模有不同的方式。在机器学习或者人工智能领域，人们首先会考虑算法的学习方式。在机器学习领域，有几种主要的学习方式。将算法按照学习方式分类是一个不错的想法，这样可以让人们在建模和算法选择的时候考虑能根据输入数据来选择最合适的算法来获得最好的结果。 监督式学习： 在监督式学习下，输入数据被称为训练数据，每组训练数据有一个明确的标识或结果，如对防垃圾邮件系统中垃圾邮件非垃圾邮件，对手写数字识别中的1，2，3，4等。在建立预测模型的时候，监督式学习建立一个学习过程，将预测结果与训练数据的实际结果进行比较，不断的调整预测模型，直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归（LogisTIc Regression）和反向传递神经网络（Back PropagaTIon Neural Network） 非监督式学习： 在非监督式学习中，数据并不被特别标识，学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means 算法。 半监督式学习： 在此学习方式下，输入数据部分被标识，部分没有被标识，这种学习模型可以用来进行预
数据结构 各种排序算法
数据结构各种排序算法总结 2009-08-19 11:09 计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。 1. 冒泡排序 BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in swap(out, min); // swap them } // end for(out) } // end selectionSort() 效率：O(N2) 3. 插入排序 insertSort 在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。 public void insertionSort() { int in, out; for(out=1; out 算法案例 【学习目标】 1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析； 2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序； 3.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质； 4.了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换. 【要点梳理】 要点一、辗转相除法 也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数m除以较小的数n得到一个商q 0和一个余数r ； 第二步：若r 0=0，则n为m，n的最大公约数；若r ≠0，则用除数n除以余数r 得到一个 商q 1和一个余数r 1 ； 第三步：若r 1=0，则r 为m，n的最大公约数；若r 1 ≠0，则用除数r 除以余数r 1 得到一个 商q 2和一个余数r 2 ； …… 依次计算直至r n =0，此时所得到的r n－1 即为所求的最大公约数. 用辗转相除法求最大公约数的程序框图为： 程序： INPUT “m=”;m INPUT “n=”;n IF m WEND PRINT n END 要点诠释： 辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量m 表示，把较小的数用变量n 表示，这样式子 )0(n r r q n m <≤+?=就是一个反复执行的步骤，因此可以用循环结构实现算法. 要点二、更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术. 更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之. 翻译出来为： 第一步：任意给出两个正整数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数(等数)就是所求的最大公约数. 理论依据： 由r b a r b a +=→=-，得b a ,与r b ,有相同的公约数 更相减损术一般算法： 第一步，输入两个正整数)(,b a b a >； 第二步，如果b a ≠，则执行3S ，否则转到5S ； 第三步，将b a -的值赋予r ； 第四步，若r b >，则把b 赋予a ，把r 赋予b ，否则把r 赋予a ，重新执行2S ； 第五步，输出最大公约数b . 程序: INPUT “a=”，a INPUT “b=”，b WHILE a<>b 个性化推荐系统研究综述 【摘要】个性化推荐系统不仅在社会经济中具有重要的应用价值，而且也是一个非常值得研究的科学问题。给出个性化推荐系统的定义，国内外研究现状，同时阐述了推荐系统的推荐算法。最后对个性化推系统做出总结与展望。 【关键词】推荐系统；推荐算法；个性化 1.个性化推荐系统 1.1个性化推荐系统的概论 推荐系统是一种特殊形式的信息过滤系统（Information Filtering），推荐系统通过分析用户的历史兴趣和偏好信息，可以在项目空间中确定用户现在和将来可能会喜欢的项目，进而主动向用户提供相应的项目推荐服务[1]。传统推荐系统认为推荐系统通过获得用户个人兴趣，根据推荐算法，并对用户进行产品推荐。事实上，推荐系统不仅局限于单向的信息传递，还可以同时实现面向终端客户和面向企业的双向信息传递。 一个完整的推荐系统由3个部分组成：收集用户信息的行为记录模块，分析用户喜好的模型分析模块和推荐算法模块，其中推荐算法模块是推荐系统中最为核心的部分。推荐系统把用户模型中兴趣需求信息和推荐对象模型中的特征信息匹配，同时使用相应的推荐算法进行计算筛选，找到用户可能感兴趣的推荐对象，然后推荐给用户。 1.2国内外研究现状 推荐系统的研宄开始于上世纪90年代初期，推荐系统大量借鉴了相关领域的研宄成果，在推荐系统的研宄中广泛应用了认知科学、近似理论、信息检索、预测理论、管理科学以及市场建模等多个领域的知识。随着互联网的普及和电子商务的发展，推荐系统逐渐成为电子商务IT技术的一个重要研究内容，得到了越来越多研究者的关注。ACM从1999年开始每年召开一次电子商务的研讨会，其中关于电子商务推荐系统的研究文章占据了很大比重。个性化推荐研究直到20世纪90年代才被作为一个独立的概念提出来。最近的迅猛发展，来源于Web210技术的成熟。有了这个技术，用户不再是被动的网页浏览者，而是成为主动参与者[2]。 个性化推荐系统的研究内容和研究方向主要包括：（1）推荐系统的推荐精度和实时性是一对矛盾的研究；（2）推荐质量研究，例如在客户评价数据的极端稀疏性使得推荐系统无法产生有效的推荐，推荐系统的推荐质量难以保证；（3）多种数据多种技术集成性研究；（4）数据挖掘技术在个性化推荐系统中的应用问题，基于Web挖掘的推荐系统得到了越来越多研究者的关注；（5）由于推荐系统需要分析用户购买习惯和兴趣爱好，涉及到用户隐私问题，如何在提供推荐服务的 最新文件---------------- 仅供参考--------------------已改成-----------word文本 --------------------- 方便更改 一、选择题(每题1分，共15分) 1、AI的英文缩写是 A)Automatic Intelligence B)Artifical Intelligence C)Automatice Information D)Artifical Information 2、反演归结（消解）证明定理时，若当前归结式是（）时，则定理得证。 A)永真式B)包孕式（subsumed）C)空子句 3、从已知事实出发，通过规则库求得结论的产生式系统的推理方式是 A)正向推理B)反向推理C)双向推理 4、语义网络表达知识时，有向弧AKO 链、ISA 链是用来表达节点知识的（）。 A)无悖性B)可扩充性C)继承性 5、(A→B)∧A => B是 A)附加律B)拒收律C)假言推理D)US 6、命题是可以判断真假的 A)祈使句B)疑问句C)感叹句D)陈述句 7、仅个体变元被量化的谓词称为 A)一阶谓词B)原子公式C)二阶谓词D)全称量词 8、MGU是 A)最一般合一B)最一般替换C)最一般谓词D)基替换 9、1997年５月，著名的“人机大战”，最终计算机以3.5比2.5的总比分将世界国际象棋棋王卡斯帕罗夫击败，这台计算机被称为（） A）深蓝B）IBM C）深思D）蓝天 10、下列不在人工智能系统的知识包含的4个要素中 A)事实B)规则C)控制与元知识D)关系 11、谓词逻辑下，子句, C1=L∨C1‘, C2= ? L∨C2‘,若σ是互补文字的（最一般）合一置换，则其归结式C=（） A) C1’σ∨C2’σB)C1’∨C2’C)C1’σ∧C2’σD)C1’∧C2’ 12、或图通常称为 A）框架网络B)语义图C)博亦图D)状态图 13、不属于人工智能的学派是 A)符号主义B)机会主义C)行为主义D)连接主义。 14、人工智能的含义最早由一位科学家于1950年提出，并且同时提出一个机器智能的测试模型，请问这个科学家是 A)明斯基B).扎德C)图林D)冯.诺依曼 15.要想让机器具有智能，必须让机器具有知识。因此，在人工智能中有一个研究领域，主要研究计算机如何自动获取知识与技能，实现自我完善，这门研究分支学科叫（）。 A)专家系统B)机器学习C)神经网络D)模式识别 二、填空题(每空1.5分，共30分) 1、不确定性类型按性质分：，， ，。 2、在删除策略归结的过程中删除以下子句：含有的子句;含 有的子句;子句集中被别的子句的子句。 3、对证据的可信度CF（A）、CF（A1）、CF（A2）之间，规定如下关系： CF（~A）=、CF（A1∧A2 ）=、 CF（A1∨A2 ）= 4、图：指由与组成的网络。按连接同一节点的各边的逻辑关系又可分为与。 5、合一算法：求非空有限具有相同谓词名的原子公式集的 6、产生式系统的推理过程中，从可触发规则中选择一个规则来执行，被执行的规则称为。 7、P(B|A) 表示在规则中，证据A为真的作用下结论B为真的。 8、人工智能的远期目标是， 近期目标是。 数据结构-各类排序算法总结 原文转自： https://www.docsj.com/doc/fc11750799.html,/zjf280441589/article/details/38387103各类排序算法总结 一. 排序的基本概念 排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素 某个项值有序的序列。 有n 个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n 的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1，Rp2，…，Rpn}。 作为排序依据的数据项称为“排序码”，也即数据元素的关键码。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可 能不唯一。实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。 若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。 二.插入类排序 1.直接插入排序直接插入排序是最简单的插入类排序。仅有一个记录的表总是有序的，因此，对n 个记录的表，可从第二个记录开始直到第n 个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。它是利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。 【高中必修3数学算法案例总结】高中数学必修1 在高中数学必修3算法教学中，为帮助学生理解案例的数学本质,安排了算法案例一节内容，下面是小编给大家带来的高中必修3数学算法案例总结，希望对你有帮助。 高中必修3数学算法案例 高中数学学习方法 抓好基础是关键 数学习题无非就是数学概念和数学思想的组合应用，弄清数学基本概念、基本定理、基本方法是判断题目类型、知识范围的前提，是正确把握解题方法的依据。只有概念清楚，方法全面，遇到题目时，就能很快的得到解题方法，或者面对一个新的习题，就能联想到我们平时做过的习题的方法，达到迅速解答。弄清基本定理是正确、快速解答习题的前提条件，特别是在立体几何等章节的复习中，对基本定理熟悉和灵活掌握能使习题解答条理清楚、逻辑推理严密。反之，会使解题速度慢，逻辑混乱、叙述不清。 严防题海战术 做习题是为了巩固知识、提高应变能力、思维能力、计算能力。学数学要做一定量的习题，但学数学并不等于做题，在各种考试题中，有相当的习题是靠简单的知识点的堆积，利用公理化知识体系的演绎而就能解决的，这些习题是要通过做一定量的习题达到对解题方法的展移而实现的，但，随着高考的改革，高考已把考查的重点放在创造型、能力型的考查上。因此要精做习题，注意知识的理解和灵活应用，当你做完一道习题后不访自问：本题考查了什么知识点?什么方法?我们从中得到了解题的什么方法?这一类习题中有什么解题的通性?实现问题的完全解决我应用了怎样的解题策略?只有这样才会培养自己的悟性与创造性，开发其创造力。也将在遇到即将来临的期末考试和未来的高考题目中那些综合性强的题目时可以有一个科学的方法解决它。 归纳数学大思维 一、粒子群算法 粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩写为PSO，是近年来发展起来的一种新的进化算法(（Evolu2tionary Algorithm - EA）。PSO 算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的交叉(Crossover) 和变异(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。 优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题.为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度.爬山法精度较高,但是易于陷入局部极小.遗传算法属于进化算法(EvolutionaryAlgorithms)的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解.遗传算法有三个基本算子:选择、交叉和变异.但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.1995年Eberhart博士和kennedy博士提出了一种新的算法;粒子群优化(ParticalSwarmOptimization-PSO)算法.这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性. 粒子群优化(ParticalSwarmOptimization-PSO)算法是近年来发展起来的一种新的进化算法(Evolu2tionaryAlgorithm-EA).PSO算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价 人教版高中数学必修三 知识点梳理 重点题型（常考知识点）巩固练习 算法案例 【学习目标】 1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析； 2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序； 3.了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质； 4.了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换. 【要点梳理】 要点一、辗转相除法 也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0； 第二步：若r0=0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1； 第三步：若r1=0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2； …… 依次计算直至r n=0，此时所得到的r n－1即为所求的最大公约数. 用辗转相除法求最大公约数的程序框图为： 程序： INPUT “m=”;m INPUT “n=”;n IF m 一插入排序 1.1 直接插入排序 基本思想：每次将一个待排序额记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。 图解： 1.//直接顺序排序 2.void InsertSort(int r[], int n) 3.{ 4.for (int i=2; i 代码实现： [cpp]view plain copy 1.//希尔排序 2.void ShellSort(int r[], int n) 3.{ 4.int i; 5.int d; 6.int j; 7.for (d=n/2; d>=1; d=d/2) //以增量为d进行直接插入排序 8. { 9.for (i=d+1; i //1. 希尔排序, 时间复杂度：O(nlogn)~ O(n^2) // 另称：缩小增量排序(Diminishing Increment Sort) void ShellSort(int v[],int n) { int gap, i, j, temp; for(gap=n/2; gap>0; gap /= 2) /* 设置排序的步长，步长gap每次减半，直到减到1 */ { for(i=gap; i } else /* 如果中间元素比当前元素小，但前元素要插入到中间元素的右侧 */ { low = mid+1; } } /* 找到当前元素的位置，在low和high之间 */ for (j=i-1; j>high; j--)/* 元素后移 */ { a[j+1] = a[j]; } a[high+1] = temp; /* 插入 */ } } //3. 插入排序 //3.1 直接插入排序, 时间复杂度：O(n^2) void StraightInsertionSort(int input[],int len) { int i, j, temp; for (i=1; i 必修3 第一章算法初步全章小结 【知识内容结构】 割圆术 【重点知识梳理与注意事项】 『算法与程序框图』 ◆算法 算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的明确的计算序列，并且这样的步骤或序列能够解决一类问题。 描述算法可以有不同的方式。可以用自然语言和数学语言加以叙述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌。 ◆程序框图 ◇概念：通常用一些通用图形符号构成一张图来表示算法，这种图称作程序框图（简称框图）。 ◇常用图形符号： 注意：i）起、止框是任何流程不可少的； ii）输入和输出可用在算法中任何需要输入、输出的位置； iii）算法中间要处理数据或计算，可分别写在不同的处理框内； iv）当算法要求对两个不同的结果进行判断时，判断条件要写在判断框内； v）如果一个框图需要分开来画，要在断开处画上连接点，并标出连接的号码。 ◇画程序框图的规则： （1）使用标准的框图的符号； （2）框图一般按从上到下、从左到右的方向画； （3）除判断框外，其他框图符号只有一个进入点和一个退出点，判断框是具有超过一个退出点的唯一符号； （4）一种判断框是二择一形式的判断，有且仅有两个可能结果；另一种是多分支判断，可能有几种不同的结果； （5）在图形符号内描述的语言要非常简练清楚。 ◆算法的三种基本逻辑结构 ◇顺序结构：描述的是最简单的算法结构，语句与语句之间，框与框之间按从上到下的顺序进行。 例： ◇条件分支结构：是依据指定条件选择执行不同指令的控制结构。 例： ◇循环结构：根据指定条件决定是否重复执行一条或多条指令的控制结构。 【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释： for(j=2*i+1; j<=m; j=j*2+1) { if(j temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："< 第1章概述 1、重点掌握人工智能的几种定义。 2、掌握目前人工智能的三个主要学派及其认知观。 3、一般了解人工智能的主要研究范围和应用领域。 人工智能的三大学派及其认知观： (1)符号主义：认为人工智能起源于数理逻辑。 (2)连接主义：认为人工智能起源于仿生学，特别是对人脑模型的研究。 (3)行为主义：认为人工智能起源于控制论。 第2章确定性知识系统 ?重点掌握用谓词逻辑法、产生式表示、语义网络法、框架表示法来描述问题，解决 问题； ?重点掌握归结演绎推理方法 谓词逻辑法 一阶谓词逻辑表示法适于表示确定性的知识。它具有自然性、精确性、严密性及易实现等特点。 用一阶谓词逻辑法表示知识的步骤如下： （1）定义谓词及个体，确定每个谓词及个体的确切含义。 （2）根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。 （3）根据所要表达的知识的语义，用适当的连接符号将各个谓词连接起来，形成谓词公式。例1：设有下列事实性知识： 张晓辉是一名计算机系的学生，但他不喜欢编程序。 李晓鹏比他父亲长得高。 请用谓词公式表示这些知识。 （1）定义谓词及个体。 Computer(x):x是计算机系的学生。 Like(x,y):x喜欢y。 Higher(x,y):x比y长得高。 这里涉及的个体有：张晓辉(zhangxh),编程序(programming), 李晓鹏(lixp)，以及函数father(lixp)表示李晓鹏的父亲。 第二步：将这些个体代入谓词中，得到 Computer(zhangxh) ?Like(zhangxh, programming) Higher(lixp, father(lixp)) ?第三步：根据语义，用逻辑联结词将它们联结起来，就得到了表示上述知识的谓词 公式。 Computer(zhangxh)∧?Like(zhangxh, programming) Higher(lixp, father(lixp)) 例2：设有下列语句，请用相应的谓词公式把它们表示出来： （1）人人爱劳动。 （2）自然数都是大于零的整数。 （3）西安市的夏天既干燥又炎热。 （4）喜欢读《三国演义》的人必读《水浒》。 （5）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。 （6）他每天下午都去打篮球。 C/C++笔试面试题目汇总3——各种排序算法 原文:https://www.docsj.com/doc/fc11750799.html,/u/1222/showart_318070.html 排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。 我将按照算法的复杂度，从简单到难来分析算法。 第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N*N)（因为没有使用word,所以无法打出上标和下标）。 第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。 第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。 一、简单排序算法 由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。 1.冒泡法：（Gilbert：点这里有视频） 这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： #include 【精品】高中数学 必修3_算法案例_知识点讲解+巩固练习(含答案)_提高
个性化推荐系统研究综述
人工智能经典考试试题与答案(优选.)
数据结构-各类排序算法总结
【高中必修3数学算法案例总结】高中数学必修1
AI人工智能的几种常用算法概念
人教版高中数学【必修三】[知识点整理及重点题型梳理]_算法案例_基础
c语言各种排序法详细讲解
各大常用排序方法
算法初步全章总结
各种排序实验报告
人工智能复习总结讲解-共30页
C C++笔试面试题目汇总3——各种排序算法
- 推荐系统总结
- 基于协同过滤算法的电影个性化推荐系统设计与实现
- 推荐系统技术ppt课件
- 机器学习算法系列(13)：推荐系统(1)—简介
- 基于协同过滤算法的学习资源个性化推荐系统设计与实现
- 常用系统算法总结及性能比较
- 常用推荐系统算法总结及性能比较
- 推荐系统技术
- 推荐系统算法
- 推荐系统算法.ppt
- 推荐系统netflix获奖算法
- 推荐系统的常用算法原理和实现
- 智能推荐系统常用算法介绍
- 经典：基于用户的协同过滤算法的推荐系统介绍
- 基于协同过滤算法的推荐系统
- 个性化推荐系统研究综述
- 基于用户的协同过滤算法的推荐系统介绍
- 推荐系统中推荐池的聚类算法分析
- 基于协同过滤的推荐系统算法研究
- 推荐系统中常用算法 以及优点缺点对比