4.1.1 决策树模型和朴素贝叶斯模型的比较
在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。决策树模型通过构造树来解决分类问题。首先利用训练数据集来构造一棵决策树，一旦树建立起来，它就可为未知样本产生一个分类。在分类问题中使用决策树模型有很多的优点，决策树便于使用，而且高效；根据决策树可以很容易地构造出规则，而规则通常易于解释和理解；决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小；决策树模型的另外一大优点就是可以对有许多属性的数据集构造决策树。决策树模型也有一些缺点，比如处理缺失数据时的困难，过度拟合问题的出现，以及忽略数据集中属性之间的相关性等。
和决策树模型相比，朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。
朴素贝叶斯模型：
Vmap=arg max{P( Vj | a1,a2...an)}
Vj属于V集合，其中j=1,2,…,N，即共有N类； Vmap是给定一个example，得到的最可能的目标值；
a1...an是这个example里面的属性/特征，共有n个特征。
Vmap为目标值，就是后面计算得出的概率最大的一个，所以用max 来表示，它意味着该example应该/最可能为得到最大后验概率的那个类，这与前面讲到的贝叶斯分类器是一致的。
将贝叶斯公式应用到 P( Vj | a1,a2...an)中，可得到： Vmap= arg max{P(a1,a2...an | Vj ) P( Vj ) / P (a1,a2...an)}
又因为朴素贝叶斯分类器默认a1...an他们互相独立的，所以P(a1,a2...an)对于结果没有影响（因为所有的概率都要除同一个东西之后再比较大小）。于是可得到：
Vmap= arg max{P(a1,a2...an | Vj ) P( Vj )}
然后，朴素贝叶斯分类器基于一个简单的假定：给定目标值时属性之间相互条件独立。换言之，该假定说明给定实例的目标值情况下，观察到联合的a1,a2...an的概率正好是对每个单独属性的概率乘积：P(a1,a2...an | Vj ) = Πi P( ai| Vj )。
因此，朴素贝叶斯分类器公式为：Vnb =arg max{P( Vj )Πi P ( ai | Vj )}。
5 邻近算法（k-Nearest Neighbor algorithm，k最近邻算法）
下图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3（即实线圆内部），由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5（即虚线圆内），由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。
该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
6 回归树分类器
如果要选择在很大范围的情形下性能都好的、同时不需要应用开发者付出很多的努力并且易于被终端用户理解的分类技术的话，那么Brieman, Friedman, Olshen和Stone（1984）提出的分类树方法是一个强有力的竞争者。
6.1 分类树
在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。
6.2 递归划分
让我们用变量Y表示因变量（分类变量），用X1, X2, X3,...,Xp表示自变量。通过递归的方式把关于变量X的p维空间划分为不重叠的矩形。首先，一个自变量被选择，比如Xi和Xi的一个值xi，比方说选择xi把p维空间为两部分：一部分是p维的超矩形，其中包含的点都满足Xi<=xi，另一个p维的超矩形包含的所有点满足Xi>xi。接着，这两部分中的一个部分通过选择一个变量和该变量的划分值以相似的方式被划分。这导致了三个矩形区域。随着这个过程的持续，我们得到的矩形越来越小。这个想法是把整个X空间划分为矩形，
其中的每个小矩形都尽可能是同构的或“纯”的。“纯”的意思是（矩形）所包含的点都属于同一类。我们认为包含的点都只属于一个类（当然，这并不总是可能的，因为经常存在一些属于不同类的点，但这些点的自变量有完全相同的值）。
7 Adaboost分类器
Adaboost是adaptive boost的缩写，它是一种迭代算法。其核心思想是针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器融合起来，作为最后的决策分类器。使用Adaboost分类器可以排除一些不必要的训练数据特征，并将重点放在关键的训练数据上。
该算法其实是一个弱分类算法的提升过程，这个过程通过不断的训练，可以提高对数据的分类能力。
整个过程如下所示：
? 先通过对N个数据的训练样本的学习得到第一个弱分类器；
? 将分错的样本和其他的新数据一起构成一个新的N个数据的训练样本，通过对这
个样本的学习得到第二个弱分类器 ；
? 将1.和2.都分错了的样本加上其他的新样本构成另一个新的N个数据的训练样本，
通过对这个样本的学习得到第三个弱分类器 ；
? 最终经过提升的强分类器，即某个数据被分为哪一类要通过，……的多数表决。 对于boosting算法，存在两个问题：
? 如何调整训练集，使得在训练集上训练的弱分类器得以进行； ? 如何将训练得到的各个弱分类器联合起来形成强分类器。 针对以上两个问题，adaboost算法进行了调整：
? 使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比
较难分的训练数据样本上； ? 将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱
分类器具有较大的权重，而分类效果差的分类器具有较小的权重。 Adaboost算法是Freund和Schapire根据在线分配算法提出的，他们详细分析了Adaboost算法错误率的上界，以及为了使强分类器达到要求的错误率，算法所需要的最多迭代次数等相关问题。与Boosting算法不同的是，adaboost算法不需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，并且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，这样可以深入挖掘弱分类器算法的能力。
Adaboost算法中不同的训练集是通过调整每个样本对应的权重来实现的。开始时，每个样本对应的权重是相同的，即其中 n 为样本个数，在此样本分布下训练出一弱分类器。对于分类错误的样本，加大其对应的权重；而对于分类正确的样本，降低其权重，这样分错的样本就被突出出来，从而得到一个新的样本分布。在新的样本分布下，再次对弱分类器进行训练，得到弱分类器。依次类推，经过T次循环，得到T个弱分类器，把这T个弱分类器按一定的权重叠加（boost）起来，得到最终想要的强分类器。
8 人工神经网络（ANN, artificial neural network）
人工神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。
电脉冲输入树突细胞体信息处理形成轴突传输
突触输出图12.2 生物神经元功能模型神经网络基本模型
人工神经网络研究的局限性：
? 研究受到脑科学研究成果的限制； ? 缺少一个完整、成熟的理论体系； ? 研究带有浓厚的策略和经验色彩； ? 与传统技术的接口不成熟。
一般而言, ANN与经典计算方法相比并非优越, 只有当常规方法解决不了或效果不佳时ANN方法才能显示出其优越性。尤其对问题的机理不甚了解或不能用数学模型表示的系统,如故障诊断、特征提取和预测等问题,ANN往往是最有利的工具。另一方面, ANN对处理大量原始数据而不能用规则或公式描述的问题, 表现出极大的灵活性和自适应性。
8.1 BP网络
人工神经网络以其具有自学习、自组织、较好的容错性和优良的非线性逼近能力，受到众多领域学者的关注。在实际应用中，80%～90%的人工神经网络模型是采用误差反传算法或其变化形式的网络模型（简称BP网络），目前主要应用于函数逼近、模式识别、分类和数据压缩或数据挖掘。
（1）BP网络建模特点： ? 非线性映照能力：神经网络能以任意精度逼近任何非线性连续函数。在建模过程中
的许多问题正是具有高度的非线性。
? 并行分布处理方式：在神经网络中信息是分布储存和并行处理的，这使它具有很
强的容错性和很快的处理速度。
? 自学习和自适应能力：神经网络在训练时，能从输入、输出的数据中提取出规律
性的知识，记忆于网络的权值中，并具有泛化能力，即将这组权值应用于一般情形的能力。神经网络的学习也可以在线进行。 ? 数据融合的能力：神经网络可以同时处理定量信息和定性信息，因此它可以利用传
统的工程技术（数值运算）和人工智能技术（符号处理）。 ? 多变量系统：神经网络的输入和输出变量的数目是任意的，对单变量系统与多变量
系统提供了一种通用的描述方式，不必考虑各子系统间的解耦问题。 （2）样本数据的收集和整理分组：
采用BP神经网络方法建模的首要和前提条件是有足够多典型性好和精度高的样本。而且，为监控训练（学习）过程使之不发生“过拟合”和评价建立的网络模型的性能和泛化能力，必须将收集到的数据随机分成训练样本、检验样本（10%以上）和测试样本（10%以上）3部分。此外，数据分组时还应尽可能考虑样本模式间的平衡。
由于传统的误差反传BP算法较为成熟，且应用广泛，因此努力提高该方法的学习速度具有较高的实用价值。BP算法中有几个常用的参数，包括学习率η，动量因子α，形状因子λ及收敛误差界值E等。这些参数对训练速度的影响最为关键。
9 Fisher分类器
X空间：
WTX-W0 >0 X∈ω1 -WTX-W0 <0 X∈ω2 映射到Y空间：
Y = WTX-W0 >0 X∈ω1 Y = WTX-W0 <0 X∈ω2
把X空间各点投影到Y空间的一直线上，维数由2维降为一维。若适当选择W的方向，可以使两类分开。于是问题便转化为从数学上寻找最好的投影方向，即寻找最好的变换向量W的问题。
1在X空间上的均值为：Xi?Ni?xj?1Niji?1,2
1Ni1NiT在Y空间上的均值为：Yi?yj?Wxj?WTXi??Nij?1Nij?1i?1,2
投影样本类间的分离性用投影样本之差表示：|Y1?Y2|?|WT(X1?X2)|，要求类间的分离性越大越好。
投影样本类内离散度:
????y2ij?1Nij?Yi??Wxj?WXiTTj?1?2Ni???W2TSiW，其中，
Si??(x?Xi)(x?Xi)T。
x?1Ni投影样本总的离散度可用(?12??22)来表示，要求投影样本总的离散度越小越好。 ?12??22?WTS1W?WTS2W?WTSwW，其中，Sw?S1?S2称为类内散布矩阵。
Fisher准则函数为：J(W)?|Y?Y|，
?????12212222TT2T而(Y1?Y2)?(WX1?WX2)?WSbW，其中，Sb?X1?X2???X1?X2?T称
为类间散布矩阵。
WTSbW1所以，J(W)?T，对J(W)求极值得W?S?w?X1?X2?。这便是n维X空间
WSwW向一维Y空间的最好投影方向，它实际上是多维空间向一维空间的一种映射。
现在我们已把一个n维的问题转化为一维的问题。于是只需在一维空间中设计 Fisher分类器:
Y?WTX?W0?X??1 Y?WTX?W0?X??2
于是，问题归结为W0的选择，常用的有以下三种： 1.W0?Y1?Y2; 2N1Y2?N2Y2N1WTX1?N2WTX22.W0?; ?N1?N2N1?N2??y3.W0?Y1?(Y2?Y1)j?1N11j?Y1?N22??yj?1N1。
21j?Y1????y2j?Y2?2j?1