人人小站(7)

相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost方法能“聚焦于”那些较难分（更富信息）的样本上。

在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器Ck。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器Ck[2]。整个训练过程如此迭代地进行下去。 

Adaboost算法的具体步骤如下：   
1. 给定训练样本集  ，其中  分别对应于正例样本和负例样本；  为训练的最大循环次数；  
2. 初始化样本权重  ，即为训练样本的初始概率分布；  
3. 第一次迭代：  
(1)  训练样本的概率分布  下，训练弱分类器：  
(2) 计算弱分类器的错误率：  
(3) 选取  ，使得  最小  
(4) 更新样本权重：  
(5) 最终得到的强分类器：  
Adaboost算法是经过调整的Boosting算法，其能够对弱学习得到的弱分类器的错误进行适应 
性调整。上述算法中迭代了次的主循环，每一次循环根据当前的权重分布对样本x定一个分 
布P，然后对这个分布下的样本使用若学习算法得到一个错误率为的弱分类器  ，对于这个算 
法定义的弱学习算法，对所有的  ，都有，而这个错误率的上限并不需要事先知道，实际上。 
每一次迭代，都要对权重进行更新。更新的规则是：减小弱分类器分类效果较好的数据的概 
率，增大弱分类器分类效果较差的数据的概率。最终的分类器是个弱分类器的加权平均。 

八、数据挖掘十大经典算法(8) kNN  

1、K最近邻(k-Nearest  Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空 
间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。 
2、KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。  KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本， 
而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。  
3、KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的 
邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。  
4、 该算法在分类时有个主要的不足是 ，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。

该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 
算法分类过程如下： 
1 首先我们事先定下k值（就是指k近邻方法的k的大小，代表对于一个待分类的数据点，我们要寻找几个它的邻居）。这边为了说明问题，我们取两个k值，分别为3和9； 
2 根据事先确定的距离度量公式（如：欧氏距离），得出待分类数据点和所有已知类别的样本点中，距离最近的k个样本。 
3 统计这k个样本点中，各个类别的数量。根据k个样本中，数量最多的样本是什么类别，我们就把这个数据点定为什么类别。 

训练样本是多维特征空间向量，其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。 在分类阶段，k是一个用户定义的常数。一个没有类别标签的向量 （查询或测试点）将被归类为最接近该点的K个样本点中最频繁使用的一类。

一般情况下，将欧氏距离作为距离度量，但是这是只适用于连续变量。在文本分类这种非连续变量情况下，

另一个度量——重叠度量（或海明距离）可以用来作为度量。

（责任编辑：晨鸿）