第一篇：机器学习算法优缺点改进总结

Lecture 1 Introduction to Supervised Learning（1）Expectatin Maximization(EM)Algorithm(期望值最大)（2）Linear Regression Algorithm(线性回归)（3）Local Weighted Regression(局部加权回归)（4）k-Nearest Neighbor Algorithm for Regression(回归k近邻)（5）Linear Classifier(线性分类)（6）Perceptron Algorithm(线性分类)（7）Fisher Discriminant Analysis or Linear Discriminant Analysis(LDA)（8）k-NN Algorithm for Classifier(分类k近邻)（9）Bayesian Decision Method(贝叶斯决策方法)Lecture 2 Feed-forward Neural Networks and BP Algorithm（1）Multilayer Perceptron(多层感知器)（2）BP Algorithm

Lecture 3 Rudiments of Support Vector Machine（1）Support Vector Machine(支持向量机)（此算法是重点，必考题）此处有一道必考题

Lecture 4 Introduction to Decision Rule Mining（1）Decision Tree Algorithm（2）ID3 Algorithm（3）C4.5 Algorithm（4）粗糙集……

Lecture 5 Classifier Assessment and Ensemble Methods（1）Bagging（2）Booting（3）Adaboosting Lecture 6 Introduction to Association Rule Mining（1）Apriori Algorithms（2）FP-tree Algorithms Lecture 7 Introduction to Custering Analysis（1）k-means Algorithms（2）fuzzy c-means Algorithms（3）k-mode Algorithms（4）DBSCAN Algorithms Lecture 8 Basics of Feature Selection（1）Relief Algorithms（2）ReliefF Algorithms（3）mRMR Algorithms最小冗余最大相关算法（4）attribute reduction Algorithms

比较了几种分类算法性质。（以下两个表格来自两篇该领域经典论文）

Lecture 1 Introduction to Supervised Learning（1）Expectatin Maximization(EM)Algorithm(期望值最大)①算法思想：

EM算法又称期望最大化算法，是对参数极大似然估计的一种迭代优化策略，它是一种可以从非完整的数据集中对参数进行极大似然估计的算法,应用于缺损数据，截尾数据，带有噪声的非完整数据。

最大期望算法经过两个步骤交替进行计算：

第一步计算期望（E）：也就是将隐藏的变量对象能够观察到的一样包含在内，从而计算最大似然的期望值；

另外一步是最大化（M），也就是最大化在E步上找到的最大似然期望值，从而计算参数的似然估计。M步上找到的参数然后用于另一个E步计算。

重复上面2步直至收敛。

②优点：1）Ｍ步仅涉及完全数据极大似然，通常计算比较简单

2）收敛是稳定的，因为每次迭代的似然函数是不断增加的。

③缺点：1）表现在对缺失数据较多或是多维高斯分布的情形下，计算量大，收敛速度较慢。

2）对于某些特殊的模型，要计算算法中的M步，即完成对似然函数的估计是比较困难的。

3）在某些情况下，要获得EM算法中E步的期望显式是非常困难的。

4）EM算法的收敛速度，非常依赖初始值的设置，设置不当，计算代价相当大。

5）EM算法中的M-Step依然是采用求导函数的方法,所以它找到的是极值点,即局

部最优解,而不一定是全局最优解。④改进：针对1）改进：扩大参数空间来加快收敛

针对2）改进：ECM算法，该算法通过在Ｍ步构建计算比较简单的小循环对EM

算法进行了改进，从而使期望函数极大化更加容易和有效，从而解决这一问题。

针对3）改进：MCEM算法，将E步积分求期望用蒙特卡洛模拟方法来实现，使

得E步求期望更容易实现。

针对4）初始值的获取可以通过k-means算法，层次聚类算法或是数据数据进行随

机分割，然后重复EM效果进行初始点选择。

针对5）结合遗传算法的全局搜索能力，扩大EM算法的搜索空间，有效降低EM

算法对初始值的依赖度，改善局部最优值的缺陷。

（2）Linear Regression Algorithm(线性回归)①算法思想：

线性回归(Linear Regression)是利用称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。这种函数是一个或多个称为回归系数的模型参数的线性组合。只有一个自变量的情况称为简单回归,大于一个自变量情况的叫做多元回归。

回归模型：

i

其中 和C是未知参数，对于每个训练样本(xi，yi)可得到h(xi)，用来预测真实值y。损失函数：

即误差值的平方。

1：对于训练集，求取θ，使得损失函数最小。（使用最小二乘法，梯度下降法）2：对于新输入x，其预测输出为θTx ②优点：结果易于理解，实现简单，计算简单

③缺点：1）对于非线性的数据拟合效果不好（原因：因为线性回归将数据视为线性的，可能出现欠拟合现象，导致结果不能取得最好的预测效果）

2）如果训练数据如果有些数据偏差特别大，这回造成最后训练的模型可能对整体

具备很好的准确性

④改进：针对2）改进 ：局部加权回归

数据都不（3）Local Weighted Regression(局部加权回归)①算法思想：

给每个待预测点周围的点赋予一定的权重,越近的点权重越高,以此来选出该预测点对应的数据子集,然后在此数据子集上基于最小均方差进行普通的回归.局部加权回归实质上是对于需要预测的点，只是根据其附近的点进行训练，其他的没有改变。

对于局部线性加权算法：

1：对于输入x，找到训练集中与x邻域的训练样本

2：对于其邻域的训练样本，求取θ，使得其

∈x的邻域）最小。其中w(i)为权重值。

3.预测输出为θTx

4.对于新输入，重复1-3过程。

其中

τ 为带宽(bandwidth)常量，距离输入越远，权重越小，反之越大。

②优点：1）局部加权回归还是对训练数据拟合的比较好

2）不太依赖特征的选择，而且只需要用线性模型就能够训练出不错的拟合模型、③缺点：1）计算量较大。（因为局部加权回归的损失数随着预测值的不同而不同，这样θ

就无法事先确定，每次预测时都需要扫描所有的数据并重新计算θ）

2）局部加权回归容易出现过拟合现象，过拟合现象很明显

3）关注局部的训练数据，忽略了全局数据，如果预测点在出现偏差的训练数据附

近，那么预测值会偏差很大。

④改进：

（4）k-Nearest Neighbor Algorithm for Regression(回归k近邻)①算法思想：

通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。②优点：

1）简单、有效。

2）重新训练的代价较低（类别体系的变化和训练集的变化，在Web环境和电子商务应用中是很常见的）。3）计算时间和空间线性于训练集的规模（在一些场合不算太大）。

4）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

5）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。③缺点：

（1）KNN在对属性较多的训练样本进行分类时，由于计算量大而使其效率大大降低，效果不是很理想。

（2）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。

（3）对数据的局部结构比较敏感。如果查询点是位于训练集较密集的区域，那预测相对比其他稀疏集来说更准确。（4）对k值敏感。

（5）维数灾难：临近距离可能被不相干属性主导（因此特征选择问题）④改进：

（1）分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。（2）分类效果：采用权值的方法（和该样本距离小的邻居权值大）来改进，Han等人于202_年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN(weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于202_年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。

（3）该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。（4）K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。

（5）该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

（5）Linear Classifier(线性分类器)①算法思想：线性分类器使用线性判别函数，实现线性判别函数分类的方法有感知器算法、LMSE分类算法和Fisher分类。

在分类问题中，因变量Y可以看做是数据的label，属于分类变量。所谓分类问题，就是能够在数据的自变量X空间内找到一些决策边界，把label不同的数据分开，如果某种方法所找出的这些决策边界在自变量X空间内是线性的，这时就说这种方法是一种线性分类器。

C1和C2是要区分的两个类别，在二维平面中它们的样本如上图所示。中间的直线就是一个分类函数，它可以将两类样本完全分开。

线性分类器在数学上被理解为线性判别函数(Linear Discriminant Functions)，在几何上可以理解为决策超平面(Decision Hyperplanes)。②优点：算法简单

③缺点：只能处理线性问题

④改进：要处理其他非线性问题，可以向高维转化，例如用SVM方法。线性分类器是分类方法，不是具体算法。

（6）Perceptron Algorithm(感知器算法)①算法思想：

感知机（Perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。②优点：

（1）感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。算法简单且易于实现；

（2）它提出了自组织自学习的思想。对能够解决的问题有一个收敛的算法，并从数学上给出了严格的证明。（3）当样本线性可分情况下，学习率 合适时，算法具有收敛性。③缺点：

（1）即感知机无法找到一个线性模型对异或问题进行划分。

（2）其实不光感知机无法处理异或问题，所有的线性分类模型都无法处理异或分类问题。（3）收敛速度慢；当样本线性不可分情况下，算法不收敛，且无法判断样本是否线性可分。

④改进：单个感知器虽然无法解决异或问题，但却可以通过将多个感知器组合，实现复杂空间的分割。（7）线性判别分析（LDA，Linear Discriminant Analysis）①基础概念

（1）判别分析概念

根据已知对象的某些观测指标和所属类别来判断未知对象所属类别的统计方法。利用已知类别的样本信息求判别函数，根据判别函数对未知样本所属类别进行判别。（2）判别分析分类

按判别组数来分，有两组判别分析和多组判别分析

按数学模型（函数形式）来分，有线性判别分析和非线性判别分析

按判别方法来分，有Fisher判别分析、Bayes判别分析和距离判别（K-NN）注:线性判别分析就是一般化的Fisher判别分析（3）Fisher判别分析与Bayes判别分析优缺点比较

Fisher判别方法对总体分布没有特殊要求，但是Fisher判别法未考虑各总体出现概率的大小，不能给出后验概率以及错判造成的损失。

Bayes判别法可以给出后验概率以及错判造成的损失。但是要求即各种变量必须服从多元正态分布、各组协方差矩阵必须相等、各组变量均值均有显著性差异。②LDA缺点

LDA有两个突出缺点:（1）处理高维图像时容易产生“小样本问题”, 即样本维数大大超过训练图像个数的问题；（2）由此引发的边缘类主导特征空间分解的问题。（3）LDA的其余缺点（限制）：

LDA至多可生成C-1维子空间。

LDA不适合对非高斯分布的样本进行降维。

LDA在样本分类信息依赖方差而不是均值时，效果不好。

LDA可能过度拟合数据。

③针对“小样本问题”的改进方法

可以利用本文设计的改进PCA 算法与LDA 算法相结合来解决小样本问题，即将结合了基于标准差和局部均值的图像增强处理算法的PCA 算法与LDA 算法相结合。具体的应用过程即为: 先采用改进的PCA 算法对样本进行降维处理，以便确保样本的类内离散度矩阵为非奇异的，利用改进的PCA 算法将原始样本图像往一个特征子空间中投影，从而使得样本的类内离散度矩阵是非奇异的。再利用LDA 算法在次特征子空间中求得最优变换。

LDA与PCA的比较

两者都是为了在对原始数据降维之后进行分类。PCA（Principal Component Analysis，主成分分析）是无监督的方式，它没有分类标签，降维之后需要采用K-Means或自组织映射网络等无监督的算法进行分类。LDA是有监督的方式，它先对训练数据进行降维，然后找出一个线性判别函数。（8）k-NN(k-Nearest Neighbor for classifier,分类最近邻估计)①算法思想：（1）k-NN介绍

如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。（2）k-NN概念

k-NN算法通常以“欧氏距离(Euclidean Distance)”为其分类模型, 欧氏距离公式的定义如下: 设在n 维空间中有两个点X =(x1,x2,„,xn)和Y =(y1,y2,„,yn), 它们之间的欧氏距离定义为:

其中, n是维数, Xi和Yi分别是X和Y的第k个属性值。②优点

（1）简单，易于理解，易于实现，无需估计参数，无需训练

（2）适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型）

（3）特别适合于多分类问题(multi-modal,对象具有多个类别标签)，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好.③缺点

（1）计算量大，由于要逐个计算到每条记录的欧氏距离, 对于海量数据, 该算法时间效率非常低。它在对每一个查询实例(Query Instance)进行分类时, 都需要搜索整个训练集来寻找最近邻, 所以它的运算开销巨大, 时间代价高昂, 这导致了它的运行速度非常低下。

（2）可解释性较差，无法给出决策树那样的规则。

（3）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。（4）由于所有属性均等地参与计算, 没有突出属性的重要程度, 分类结果易受单个属性的影响;④改进

缺点1：目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。缺点4：利用信息增益来衡量属性的重要程度(即属性权重系数),将属性划分为关键属性、次要属性及无关属性, 解决属性均等用力的问题;缺点3，可考虑从K值设定回答

1、k值设定为多大？

k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响）

k值通常是采用交叉检验来确定（以k=1为基准）经验规则：k一般低于训练样本数的平方根

补充去年相关习题：

请阐述 kNN近邻分类算法的基本思想，并分析它的主要优缺点。关于 k 的取值，你有什么合理的建议（至少 1 条）。优点

(1)简单，易于理解，易于实现，无需估计参数，无需训练

(2)适合对稀有事件进行分类（例如当流失率很低时，比如低于0.5%，构造流失预测模型）(3)特别适合于多分类问题，例如根据基因特征来判断其功能分类，kNN比SVM的表现要好 缺点

(1)懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢

(2)当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有 可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数；

(3)可解释性较差，无法给出决策树那样的规则。k值设定

k值选择过小，得到的近邻数过少，会降低分类精度，同时也会放大噪声数据的干扰；而如果k值选择过大，并且待分类样本属于训练集中包含数据数较少的类，那么在选择k个近邻的时候，实际上并不相似的数据亦被包含进来，造成噪声增加而导致分类效果的降低。

k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响）K值设定的建议

k值通常是采用交叉检验来确定（以k=1为基准）k一般低于训练样本数的平方根

（9）贝叶斯决策方法（Bayesian Decision Method）①贝叶斯决策概念

贝叶斯决策（Bayesian Decision Theory）就是在不完全情报下，对部分未知的状态用主观概率估计，然后用贝叶斯公式对发生概率进行修正，最后再利用期望值和修正概率做出最优决策。贝叶斯决策属于风险型决策，决策者虽不能控制客观因素的变化，但却掌握其变化的可能状况及各状况的分布概率，并利用期望值即未来可能出现的平均状况作为决策准则。

贝叶斯决策理论方法是统计模型决策中的一个基本方法，其基本思想是：

已知类条件概率密度参数表达式和先验概率。

利用贝叶斯公式转换成后验概率。

根据后验概率大小进行决策分类。②贝叶斯决策方法优缺点 优点：

贝叶斯决策能对信息的价值或是否需要采集新的信息做出科学的判断

它能对调查结果的可能性加以数量化的评价,而不是像一般的决策方法那样,对调查结果或者是完全相信,或者是 完全不相信

如果说任何调查结果都不可能完全准确,先验知识或主观概率也不是完全可以相信的,那么贝叶斯决策则巧妙地将这两种信息有机地结合起来了

它可以在决策过程中根据具体情况下不断地使用,使决策逐步完善和更加科学 缺点：

它需要的数据多,分析计算比较复杂,特别在解决复杂问题时,这个矛盾就更为突出

有些数据必须使用主观概率,有些人不太相信,这也妨碍了贝叶斯决策方法的推广使用 ③贝叶斯决策改进方法

将决策问题转化成收益矩阵,通过对收益矩阵的分析,得出各行动方案的期望值,按照一定的准则选出最优方案。

以各状况下最大收益值或效用值为基础,求出MaxE(x),以此作为完全确定情况下的收益值,用该值减去最优方案的期望值得出完全信息价值(EVPⅠ),根据完全信息期望值判断是否需要补充信息量。

在第2步得到肯定回答后,首先在预先后验分析中从理论上把各种可能的抽样方案及结果列举出来,计算各种抽样方案的抽样信息期望值EVSI=EVPI-R(n),其中R(n)为抽样风险,其大小是样本大小的函数。

以EVSI-C(其中C为抽样成本)作为标准选取最大值对应的抽样方案为最优抽样方案。

按照理论上得出的最优抽样方案进行抽样,然后,根据贝叶斯理论公式推导出后验概率分布的数字描述,最后,以此为依据按照贝叶斯决策准则选出最优方案。补充朴素贝叶斯

朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。

同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。

补充朴素贝叶斯优点：

1）朴素贝叶斯算法是基于贝叶斯理论，逻辑清楚明了

2）本算法进行分类是，时间快，在内存上需要的也不大

3）本算法鲁棒性高，即使数据包含的噪声点，无关属性和缺失值的属性，分类性能不好又 太大的变化，健壮性好

补充朴素贝叶斯算法缺点：

1）朴素贝叶斯算法要求样本各属性直接是独立的，而真实的数据符合这个条件很少。

2）当样本数据少时，分类器可能会无法正确分类

Lecture 2 Feed-forward Neural Networks and BP Algorithm（1）Multilayer Perceptron(多层感知器)①算法思想

多层感知器（Multilayer Perceptron,缩写MLP）是一种前向结构的人工神经网络。MLP算法一般包括三层，分别是一个输入层，一个输出层和一个或多个隐藏层的神经网络组成。一个“神经元”的输出就可以是另一个“神经元”的输入。MLP可以被看作是一个有向图，由多个的节点层所组成，每一层都全连接到下一层。除了输入节点，每个神经元都有几个输入和输出神经元，每个神经元通过输入权重加上偏置计算输出值，并选择一种激活函数进行转换。一种被称为反向传播算法(BP)的监督学习方法常被用来训练MLP。MLP是感知器的推广，克服了感知器不能对线性不可分数据进行识别的弱点。

激活函数

若每个神经元的激活函数都是线性函数，那么，任意层数的MLP都可被约简成一个等价的单层感知器。实际上，MLP本身可以使用任何形式的激活函数，但为了使用反向传播算法进行有效学习，激活函数必须限制为可微函数。由于具有良好可微性，很多乙形函数，尤其是双曲正切函数（Hyperbolic tangent）及逻辑乙形函数（logistic sigmoid function），被采用为激活函数。激活函数常见的有三种，分别是恒等函数，Sigmoid函数和高斯函数。

②优点：

（1）高度的并行性

人工神经网络是由许多相同的简单处理单元并联组合而成，虽然每个单元的功能简单，但大量简单单元的并行活动，使其对信息的处理能力与效果惊人。（2）高度的非线性全局作用

神经网络系统是由大量简单神经元构成的，每个神经元接受大量其他神经元的输入，通过非线性输入、输出关系，产生输出影响其它神经元。网络就是这样互相制约相互影响，实现从输入状态空间到输出状态空间非线性映射的。网络的演化遵从全局性作用原则，从输入状态演化到终态而输出。从全局观点来看，网络整体性能不是网络局部性能的简单迭加，而表现某种集体性行为；而电脑遵从串行式局域性操作原则，每一步计算与上一步计算紧密相关，并对下一步产生影响，问题是通过算法逐步进行处理的。（3）良好的容错性与联想记忆功能

人工神经网络通过自身的网络结构能够实现对信息的记忆，而所记忆的信息是存储在神经元之间的权值中。从单个权值中看不出所储存的信息内容，因而是分布式的存储方式。这使得网络具有良好的容错性，并能进行聚类分析、特征提取、缺损模式复原等模式信息处理工作。

（4）十分强的自适应、自学习功能人工神经网络可以通过训练和学习来获得网络的权值与结构，呈现出很强的自学习能力和对环境的自适应能力。③缺点

（1）网络的隐含节点个数选取问题至今仍是一个 世界难题；

（2）停止阈值、学习率、动量常数需要采用”trial-and-error”法，极其耗时（动手实验）；（3）学习速度慢；

（4）容易陷入局部极值，学习不够充分。④改进

（1）改进BP算法（见bp）（2）权值初始化

在初始化权值的时候，我们一般需要它们在0附近，要足够小（在激活函数的近似线性区域可以获得最大的梯度）。另一个特性，尤其对深度网络而言，是可以减小层与层之间的激活函数的方差和反向传导梯度的方差。这就可以让信息更好的向下和向上的传导，减少层间差异。（3）学习率

随着时间的推移减小学习速率有时候也是一个好主意。一个简单的方法是使用这个公式：u/(1+d*t)，u是初始速率（可以使用上面讲的网格搜索选择），d是减小常量，用以控制学习速率，可以设为0.001或者更小，t是迭代次数或者时间。可以基于分类错误率自适应的选择学习率。（4）隐藏节点数 这个参数是非常基于数据集的。模糊的来说就是，输入分布越复杂，去模拟它的网络就需要更大的容量，那么隐藏单元的数目就要更大。（5）正则化参数

典型的方法是使用L1/L2正则化。

L2正则化就是在代价函数后面再加上一个正则化项：

C0代表原始的代价函数，后面那一项就是L2正则化项，它是这样来的：所有参数w的平方的和，除以训练集的样本大小n。λ就是正则项系数，权衡正则项与C0项的比重。另外还有一个系数1/2，1/2经常会看到，主要是为了后面求导的结果方便，后面那一项求导会产生一个2，与1/2相乘刚好凑整。

过拟合，就是拟合函数需要顾忌每一个点，最终形成的拟合函数波动很大。在某些很小的区间里，函数值的变化很剧烈。这就意味着函数在某些小区间里的导数值（绝对值）非常大，由于自变量值可大可小，所以只有系数足够大，才能保证导数值很大。而正则化是通过约束参数的范数使其不要太大，所以可以在一定程度上减少过拟合情况。

L1正则化项就是在原始的代价函数后面加上一个正则化项，即所有权重w的绝对值的和，乘以λ/n（这里不像L2正则化项那样）：

比原始的更新规则多出了η * λ * sgn(w)/n这一项。当w为正时，更新后的w变小。当w为负时，更新后的w变大——因此它的效果就是让w往0靠，使网络中的权重尽可能为0，也就相当于减小了网络复杂度，防止过拟合。

（2）BP Algorithm ①算法思想

BP算法是一种有监督式的学习算法，其主要思想是：输入学习样本，使用反向传播算法对网络的权值和偏差进行反复的调整训练，使输出的向量与期望向量尽可能地接近，当网络输出层的误差平方和小于指定的误差时训练完成，保存网络的权值和偏差。②优点：

（1）网络实质上实现了一个从输入到输出的映射功能，而数学理论已证明它具有实现任何复杂非线性映射的功能。这使得它特别适合于求解内部机制复杂的问题；

（2）网络能通过学习带正确答案的实例集自动提取“合理的”求解规则，即具有自学习能力；（3）网络具有一定的推广、概括能力。③缺点

主要包括以下几个方面的问题。

（1）由于学习速率是固定的，因此网络的收敛速度慢，需要较长的训练时间。对于一些复杂问题，BP算法需要的训练时间可能非常长，这主要是由于学习速率太小造成的。

（2）BP算法可以使权值收敛到某个值，但并不保证其为误差平面的全局最小值，这是因为采用梯度下降法可能产生一个局部最小值

（3）网络隐含层的层数和单元数的选择尚无理论上的指导，一般是根据经验或者通过反复实验确定。因此，网络往往存在很大的冗余性，在一定程度上也增加了网络学习的负担。

（4）网络的学习和记忆具有不稳定性。也就是说，如果增加了学习样本，训练好的网络就需要从头开始训练，对于以前的权值和阈值是没有记忆的。但是可以将预测、分类或聚类做的比较好的权值保存。

（5）网络的预测能力（也称泛化能力、推广能力）与训练能力（也称逼近能力、学习能力）的矛盾。一般情况下，训练能力差时，预测能力也差，并且一定程度上，随训练能力地提高，预测能力也提高。但这种趋势有一个极限，当达到此极限时，随训练能力的提高，预测能力反而下降，即出现所谓“过拟合”现象。此时，网络学习了过多的样本细节，而不能反映样本内含的规律。（6）网络训练失败的可能性较大，其原因有：

a 从数学角度看，BP算法为一种局部搜索的优化方法，但它要解决的问题为求解复杂非线性函数的全局极值，因此，算法很有可能陷入局部极值，使训练失败；

b 网络的逼近、推广能力同学习样本的典型性密切相关，而从问题中选取典型样本实例组成训练集是一个很困难的问题。④改进.变步长法

BP算法的有效性和收敛性在很大程度上取决于学习步长η的值。采用一般的固定长梯度下降法求解时,起码可能导致两个主要问题:局部极小解;收敛速度慢。所以,一般要求是,当训练到误差曲面的平坦区时,梯度较小,为加快收敛应使η增大;当训练到深而窄的误差曲面时,应使η减小,以免因步长过大而出现振荡现象。为加快收敛,应使η合理化,可采用变步长算法。变步长算法的基本思想是,先设一个初始步长η,若一次迭代后误差增大,则将步长乘以β(<1),沿原方向重新计算该迭代点;若一次迭代后误差减小,则将步长乘以α(>1),计算下一个迭代点,以缩短学习时间。2.加动量项法

为了加速BP算法的收敛,可考虑在权值调整算式中加入动量项,即

式中,α为动量因子,一般取0.1～0.8。这时权值修正量加上了有关上一时刻权值修改方向的记忆,加速了网络的收敛。加动量项法的具体原理:若相邻两次迭代点处的梯度方向是一致的,引入动量项可使权值的调整量增大,从而加速收敛;若相邻两次迭代点处的梯度方向相反,引入动量项可使权值的调整量减小,避免了来回振荡,加快了收敛。3.串连法

BP算法的收敛速度主要取决于输入-输出模式间非线性映射的复杂程度。显然,这种非线性映射关系越复杂,收敛时间越长。因此,对那些高度复杂的非线性问题,用两个串连的BP网络代替一个BP网络,能够有效地缩短训练时间。4.利用遗传算法优化BP算法

BP算法的优点是寻优具有精确性,但它易陷入局部极小、收敛速度慢,而遗传算法(GeneticAlgorithm,GA)是基于自然选择和遗传规律的全局优化搜索算法,具有很强的宏观搜索能力和寻优全局性。因此,在BP神经网络理论中引入遗传算法的思想,则可以很好地达到全局寻优和快速高效的目的。

Lecture 3 Rudiments of Support Vector Machine（1）Support Vector Machine(支持向量机)（此算法是重点，必考题）

①算法思想

SVM的主要思想是针对两类分类问题，寻找一个超平面作为两类训练样本点的分割，以保证最小的分类错误率。在线性可分的情况下，存在一个或多个超平面使得训练样本完全分开，SVM的目标是找到其中的最优超平面，最优超平面是使得每一类数据与超平面距离最近的向量与超平面之间的距离最大的这样的平面，对于线性不可分的情况，通过使用核函数（一种非线性映射算法）将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分。②优点

（1）小样本，并不是说样本的绝对数量少（实际上，对任何算法来说，更多的样本几乎总是能带来更好的效果），而是说与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。

（2）非线性，是指SVM擅长应付样本数据线性不可分的情况，主要通过松弛变量（也有人叫惩罚变量）和核函数技术来实现，（3）高维模式识别是指样本维数很高，例如文本的向量表示，如果没有经过降维处理，出现几万维的情况很正常，其他算法基本就没有能力应付了，SVM却可以，主要是因为SVM 产生的分类器很简洁，用到的样本信息很少（仅仅用到那些称之为“支持向量”的样本，此为后话），使得即使样本维数很高，也不会给存储和计算带来大麻烦（相对照而言，kNN算法在分类时就要用到所有样本，样本数巨大，每个样本维数再一高，这日子就没法过了„„）。③缺点

（1）SVM算法对大规模训练样本难以实施 由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。（2）用SVM解决多分类问题存在困难 ④改进：

经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有

一对多组合模式、一对一组合模式和SVM决策树； 再就是通过构造多个分类器的组合来解决。

主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：

与粗集理论结合，形成一种优势互补的多类问题的组合分类器。此处有一道必考题

Lecture 4 Introduction to Decision Rule Mining（1）ID3 Algorithm ①算法思想：

补充：

ID3算法（Iterative Dichotomiser 3 迭代二叉树3代）是一个由Ross Quinlan发明的用于决策树的算法。这个算法便是：

从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。

所以，ID3的思想便是：

自顶向下的贪婪搜索遍历可能的决策树空间构造决策树(此方法是ID3算法和C4.5算法的基础)； 从“哪一个属性将在树的根节点被测试”开始；

使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试(如何定义或者评判一个属性是分类能力最好的呢？这便是下文将要介绍的信息增益，or 信息增益率)。

然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。

②优点：

（1）分类精度高；

（2）实现比较简单，产生的规则如果用图表示出来的话，清晰易懂；

优点补充：

（4）ID3算法的假设空间包含了所有的决策树，不存在无解风险

（5）ID3算法非常适合处理离散样本数据，利用属性结果提取分类规则，且容易理解（6）引进了信息论的中的熵，使得算法得到结点最少的决策树 ③缺点：

（1）ID3算法往往偏向于选择取值较多的属性，而在很多情况下取值较多的属性并不总是最重要的属性，即按照使熵值最小的原则被ID3算法列为应该首先判断的属性在现实情况中却并不一定非常重要。例如：在银行客户分析中，姓名属性取值多，却不能从中得到任何信息。（简略写：由于使用信息增益，会在属性选择时偏向选择取值多的属性）

（2）ID3算法对于噪声数据敏感，ID3算法不能处理具有连续值的属性，也不能处理具有缺失数据的属性。

（3）用互信息作为选择属性的标准存在一个假设，即训练子集中的正、反例的比例应与实际问题领域中正、反例的比例一致。一般情况很难保证这两者的比例一致，这样计算训练集的互信息就会存在偏差。

（4）在建造决策树时，每个结点仅含一个属性，是一种单变元的算法，致使生成的决策树结点之间的相关性不够强。虽然在一棵树上连在一起，但联系还是松散的。

（5）ID3算法虽然理论清晰，但计算比较复杂，在学习和训练数据集的过程中机器内存占用率比较大，耗费资源。（计算复杂，有很多对数计算）

（6）ID3不够健壮，当有一个项数据有改变时，整棵树的结构可能改变很大。

改进：用R-C4.5的思想，在进行测试属性选择时，合并分类贡献小的分支，避免出现过细的分枝，提高树的健壮性。补充：

（7）当训练集增加或减少的时候，决策树都会随之改变，对渐进学习不方便。

④改进：（1）对决策树进行剪枝。可以采用交叉验证法和加入正则化的方法。

（2）使用基于决策树的combination算法，如bagging算法，randomforest算法，可以解决过拟合的问题（3）引入用户兴趣度

给定a(0≤a≤1)为用户对不确定知识的兴趣度，a的大小由决策者根据先验知识或领域知识来确定。它是一个模糊的概念，通常指关于某一事务的先验知识，包括领域知识和专家建议，具体到决策树学习中则是指在决策树训练过程中除了用于生成和修改决策树的实例集之外的所有影响决策树规则生成和选择的因素。

（2）C4.5 Algorithm 补充：

既然说C4.5算法是ID3的改进算法，那么C4.5相比于ID3改进的地方有哪些呢？

用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵(entropy，熵是一种不纯度度量准则),也就是熵的变化值，而C4.5用的是信息增益率。对，区别就在于一个是信息增益，一个是信息增益率。（因此，C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。）在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致overfitting。对非离散数据也能处理。能够对不完整数据进行处理 ①算法思想：

②优点：

（1）产生的分类规则易于理解，准确率较高。（2）对非离散数据也能处理。

C4.5既可以处理离散型描述属性，也可以处理连续性描述属性。在选择某节点上的分枝属性时，对于离散型描述属性，C4.5的处理方法与ID3相同，按照该属性本身的取值个数进行计算；对于某个连续性描述属性Ac，假设在某个结点上的数据集的样本数量为total，C4.5将作以下处理。

1）将该结点上的所有数据样本按照连续型描述属性的具体数值，由小到大进行排序，得到属性值的取值序列{A1c，A2c，„„Atotalc}。

2）在取值序列中生成total-1个分割点。第i（0

3）从total-1个分割点中选择最佳分割点。对于每一个分割点划分数据集的方式，C4.5计算它的信息增益比，并且从中选择信息增益比最大的分割点来划分数据集。（3）能够对不完整数据进行处理。

在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x，c(x)〉是样本集S中的一个训练实例，但是其属 性A的值A(x)未知。处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。这些片断样例（fractional examples）的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。C4.5就是使用这种方法处理缺少的属性值。（4）克服了用信息增益来选择属性时偏向选择值多的属性的不足。（5）采用了一种后剪枝方法

避免树的高度无节制的增长，避免过度拟合数据，该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下：

其中N是实例的数量，f=E/N为观察到的误差率（其中E为N个实例中分类错误的个数），q为真实的误差率，c为置信度（C4.5算法的一个输入参数，默认值为0.25），z为对应于置信度c的标准差，其值可根据c的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个悲观的估计：

通过判断剪枝前后e的大小，从而决定是否需要剪枝。

树剪枝

在决策树的创建时，由于数据中的噪声和离群点，许多分枝反映的是训练数据中的异常。剪枝方法是用来处理这种过分拟合数据的问题。通常剪枝方法都是使用统计度量，剪去最不可靠的分枝。

剪枝一般分两种方法：先剪枝和后剪枝。

先剪枝方法中通过提前停止树的构造（比如决定在某个节点不再分裂或划分训练元组的子集）而对树剪枝。一旦停止，这个节点就变成树叶，该树叶可能取它持有的子集最频繁的类作为自己的类。先剪枝有很多方法，比如（1）当决策树达到一定的高度就停止决策树的生长；（2）到达此节点的实例具有相同的特征向量，而不必一定属于同一类，也可以停止生长（3）到达此节点的实例个数小于某个阈值的时候也可以停止树的生长，不足之处是不能处理那些数据量比较小的特殊情况（4）计算每次扩展对系统性能的增益，如果小于某个阈值就可以让它停止生长。先剪枝有个缺点就是视野效果问题，也就是说在相同的标准下，也许当前扩展不能满足要求，但更进一步扩展又能满足要求。这样会过早停止决策树的生长。

另一种更常用的方法是后剪枝，它由完全成长的树剪去子树而形成。通过删除节点的分枝并用树叶来替换它。树叶一般用子树中最频繁的类别来标记。

C4.5采用悲观剪枝法，它使用训练集生成决策树又用它来进行剪枝，不需要独立的剪枝集。

悲观剪枝法的基本思路是：设训练集生成的决策树是T，用T来分类训练集中的N的元组，设K为到达某个叶子节点的元组个数，其中分类错误地个数为J。由于树T是由训练集生成的，是适合训练集的，因此J/K不能可信地估计错误率。所以用(J+0.5)/K来表示。设S为T的子树，其叶节点个数为L(s)，个数总和，为到达此子树的叶节点的元组 为此子树中被错误分类的元组个数之和。在分类新的元组时，则其错误分类个数为，其标准错误表示为：。当用此树分类训练集时，设E为分类错误个数，当下面的式子成立时，则删掉子树S，用叶节点代替，且S的子树不必再计算。

③缺点：

（1）构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

（2）C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。（3）在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。④改进：

（1）SLIQ算法

SLIQ算法对C4.5决策树分类算法的实现方法进行了改进，在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。

1)预排序。对于连续属性在每个内部结点寻找其最优分裂标准时，都需要对训练集按照该属性的取值进行排序，而排序是很浪费时间的操作。为此，SLIQ算法 采用了预排序技术。所谓预排序，就是针对每个属性的取值，把所有的记录按照从小到大的顺序进行排序，以消除在决策树的每个结点对数据集进行的排序。具体实 现时，需要为训练数据集的每个属性创建一个属性列表，为类别属性创建一个类别列表。

2)广度优先策略。在C4.5算法中，树的构造是按照深度优先策略完成的，需要对每个属性列表在每个结点处都进行一遍扫描，费时很多，为此，SLIQ采用 广度优先策略构造决策树，即在决策树的每一层只需对每个属性列表扫描一次，就可以为当前决策树中每个叶子结点找到最优分裂标准。

SLIQ算法由于采用了上述两种技术，使得该算法能够处理比C4.5大得多的训练集，在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。

然而它仍然存在如下缺点：

1)由于需要将类别列表存放于内存,而类别列表的元组数与训练集的元组数是相同的,这就一定程度上限制了可以处理的数据集的大小。

2)由于采用了预排序技术，而排序算法的复杂度本身并不是与记录个数成线性关系，因此，使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。（2）SPRINT算法

为了减少驻留于内存的数据量，SPRINT算法进一步改进了决策树算法的数据结构，去掉了在SLIQ中需要驻留于内存的类别列表，将它的类别列合并到每个 属性列表中。这样，在遍历每个属性列表寻找当前结点的最优分裂标准时，不必参照其他信息，将对结点的分裂表现在对属性列表的分裂，即将每个属性列表分成两 个，分别存放属于各个结点的记录。

SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进行分 裂时用哈希表记录下每个记录属于哪个孩子结点，若内存能够容纳下整个哈希表，其他属性列表的分裂只需参照该哈希表即可。由于哈希表的大小与训练集的大小成 正比，当训练集很大时，哈希表可能无法在内存容纳，此时分裂只能分批执行，这使得SPRINT算法的可伸缩性仍然不是很好。

（3）随机森林(Random Forest)（对C4.5,ID3改进，提高准确率）

随机森林是一个最近比较火的算法，它有很多的优点： 在数据集上表现良好

在当前的很多数据集上，相对其他算法有着很大的优势

它能够处理很高维度（feature很多）的数据，并且不用做特征选择 在训练完后，它能够给出哪些feature比较重要

在创建随机森林的时候，对generlization error使用的是无偏估计 训练速度快

在训练过程中，能够检测到feature间的互相影响 容易做成并行化方法 实现比较简单

随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。在建立每一棵决策树的过程中，有两点需要注意 – 采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m << M)。之后就 是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 – 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。

按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。随机森林的过程请参考Mahout的random forest。这个页面上写的比较清楚了，其中可能不明白的就是Information Gain，可以看看之前推荐过的Moore的页面。

Lecture 5 Classifier Assessment and Ensemble Methods

1、bagging bagging是一种用来提高学习算法准确度的方法，这种方法通过构造一个预测函数系列，然后以一定的方式将它们组合成一个预测函数。• 基本思想

1.给定一个弱学习算法,和一个训练集;2.单个弱学习算法准确率不高;3.将该学习算法使用多次,得出预测函数序列,进行投票;4.最后结果准确率将得到提高.Bagging要求“不稳定”（不稳定是指数据集的小的变动能够使得分类结果的显著的变动）的分类方法。比如：决策树，神经网络算法

2、Booting Boosting方法是一种用来提高弱分类算法准确度的方法,这种方法通过构造一个预测函数系列,然后以一定的方式将他们组合成一个预测函数。Boosting是一种提高任意给定学习算法准确度的方法。他是一种框架算法,主要是通过对样本集的操作获得样本子集,然后用弱分类算法在样本子集上训练生成一系列的基分类器。可以用来提高其他弱分类算法的识别率。

 Bagging与Boosting的区别

二者的主要区别是取样方式不同。Bagging采用均匀取样，而Boosting根据错误率来取样，因此Boosting的分类精度要优于Bagging。Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boostlng的各轮训练集的选择与前面各轮的学习结果有关；Bagging的各个预测函数没有权重，而Boosting是有权重的；Bagging的各个预测函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于象神经网络这样极为耗时的学习方法。Bagging可通过并行训练节省大量时间开销。

bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化---Overfit。

Boosting思想的一种改进型AdaBoost方法在邮件过滤、文本分类方面都有很好的性能。

3、Adaboost(Adaptive Boosting) 算法简介

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用adaboost分类器可以排除一些不必要的训练数据特征，并放在关键的训练数据上面。 算法分析

该算法其实是一个简单的弱分类算法提升过程，这个过程通过不断的训练，可以提高对数据的分类能力。整个过程如下所示：

1.先通过对N个训练样本的学习得到第一个弱分类器； 2.将分错的样本和其他的新数据一起构成一个新的N个的训练样本，通过对这个样本的学习得到第二个弱分类器 ； 3.将1和2都分错了的样本加上其他的新样本构成另一个新的N个的训练样本，通过对这个样本的学习得到第三个弱分类器；

4.最终经过提升的强分类器。即某个数据被分为哪一类要由各分类器权值决定。

 算法优点： 高精度；简单，无需做特征筛选；可以使用各种方法构建子分类器，Adaboost算法提供的是框架；当使用简单分类器时，计算出的结果是可以理解的，而且弱分类器构造极其简单；不会过度拟合。

对于boosting算法，存在两个问题：

1.如何调整训练集，使得在训练集上训练的弱分类器得以进行； 2.如何将训练得到的各个弱分类器联合起来形成强分类器。针对以上两个问题，Adaboost算法进行了调整：

1.使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上； 2.将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。

与Boosting算法不同的是，Adaboost算法不需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，并且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，这样可以深入挖掘弱分类器算法的能力。

 算法缺点： 训练时间过长，执行效果依赖于弱分类器的选择。对噪声数据和离群值敏感。 改进：限制样本权重的调整在各目标类内部进行

1、权值更新方法的改进

Allende等人提出了RADA算法，该算法是对原算法中误分类样本权值抑制的方法。算法最突出的贡献有三点：第一点是对的抑制，第二点，用当前层分类器来判断样本是否分类正

确，而非原算法中的当前弱分类器，第三点，增加 age变量记录误分类情况，并作了阈值限制，这里有效缓解了过拟合的问题。RADA 比传统 AdaBoost 算法更加稳定，有效解决了误分类样本权值偏高的问题。

2、训练方法的改进

Merler等人提出了AdaBoost的并行计算方法P-AdaBoost算法。其主要思想是，将AdaBoost训练过程分为两个阶段，第一阶段和原算法一样，经过多轮训练，获得一个较为可靠的样本分布ωi(s)，第二阶段采用并行方法提高训练效率，训练中不再对样本权值进行更新，而统一采用ωi(s)，最后输出为。

采用这种方法能大大减少训练成本，与原算法相比，多了S 轮的样本分布初始化工作，并且避免了差样本因多次分类而造成权值过大的问题。

3、多算法结合的改进

Yunlong提出了EAdaBoost算法，是AdaBoost结合k近邻算法的产物。AdaBoost算法具有高度拟合的特点，噪声会对训练产生很大的影响，Yunlong等人在AdaBoost算法的基础之上加入了kNN算法，对噪声样本进行了有效处理，提高了算法的精确度。EAdaBoost算法的主要过程如下：

(a)准备训练样本，对样本权值进行初始化。(b)计算训练误差，并挑选最优的弱分类器。(c)更新样本权值。

(d)用 KNN 算法排除噪声样本，将权值设为 0。

该算法中有两个非常关键的问题，什么样的样本称为噪声样本和每次要处理多少个噪声样本的问题，原文中称之为 suspect sample，算法中取的是那种难于学习、让分类器出错过多的样本。

4、综合方法的改进

Rong Xiao等人提出了Boosting Chain算法，用链表的方式来组织分类器，算法先用boosting特征快速排除 大量非人脸窗口，再用boosting chain和SVM分类器进行再判别，实验效果相比FloatBoost还要略好。

Adaboosting

Lecture 6 Introduction to Association Rule Mining（1）Apriori Algorithms ①算法思想：Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”。首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。

一、挖掘步骤：

1.依据支持度找出所有频繁项集（频度）2.依据置信度产生关联规则（强度）二、一些定义： 对于A->B ①支持度：P(A∩B)，既有A又有B的概率

②置信度：P(B|A)，在A发生的事件中同时发生B的概率p(AB)/P(A)③如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则。⑤候选集：通过向下合并得出的项集。

⑥频繁集：支持度大于等于特定的最小支持度（Minimum Support/minsup）的项集。注意，频繁集的子集一定是频繁集。核心思想：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。简单的讲，1、发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集，重复步骤（1）~（5）直到不能发现更大的频集

2、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果 P（L）/P（S）≧minsup 则输出规则“SàL-S”

注：L-S表示在项集L中除去S子集的项集

②优点： Apriori（先验的，推测的）算法应用广泛，可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。

③缺点：此算法的的应用非常广泛，但是他在运算的过程中会产生大量的侯选集，而且在匹配的时候要进行整个数据库的扫描（重复扫描），因为要做支持度计数的统计操作，在小规模的数据上操作还不会有大问题，如果是大型的数据库上呢，他的效率还是有待提高的。④改进：

方法

一、Apriori优化：Fp-tree 算法

关键点：以树形的形式来展示、表达数据的形态；可以理解为水在不同河流分支的流动过程； 生成Fp-tree的几个点： 1.扫描原始项目集； 2.排列数据；

3.创建ROOT节点；

4.按照排列的数据进行元素的流动； 5.节点+1；

方法

二、Apriori优化：垂直数据分布

关键点：相当于把原始数据进行行转列的操作，并且记录每个元素的个数 Lecture 6有5种改进方法：

1.基于哈希的项集数：小于阈值的哈希桶数的k项集不是频繁的

2.缩减事务：在子频繁集中扫描时，不包含任何k项频繁集的事务是无用的 3.划分DB：DB中的任何频繁项集在部分DB中也一定是频繁的 4.采样：用一个小的支持阈值和方法挖掘给定数据的子集

5.动态规划项集数：只有当他们的所有子集预计为频繁时才添加一个新的候选项（1）基于hash的方法。基于哈希的算法仍是将所有所有数据放入内存的方法。只要在计算的过程中能够满足算法对内存的大量需求，针对C2候选项对过大，一些算法提出用来减少C2的大小。这里我们首先考虑PCY算法，这个算法使用了在Apriori算法的第一步里大量没使用的内存。接着，我们考虑Multistage（多步哈希）算法，这个算法使用PCY的技巧，但插入了额外的步骤来更多的减少C2的大小。类似的还有Multihash。

（2）基于划分的方法。Savasere等设计了一个基于划分(partition)的算法.这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。

（3）基于采样的方法。基于前一遍扫描得到的信息，对此仔细地作组合分析，可以得到一个改进的算法，Mannila等先考虑了这一点，他们认为采样是发现规则的一个有效途径。

（2）FP-tree Algorithms ①算法思想：

参考http://blog.csdn.net/sealyao/article/details/6460578 FP-tree 在不生成候选项的情况下，完成Apriori算法的功能。通过合并一些重复路径，实现了数据的压缩，从而使得将频繁项集加载到内存中成为可能。之后以树遍历的操作，替代了 Apriori 算法中最耗费时间的事务记录遍历，从而大大提高了运算效率。算法步骤如下：

1.扫描一遍数据库，删除频率小于最小支持度的项，并降序排列。并将每个事务中的项都要按照这个顺序进行排列。处理后的数据库记录为：

2.构建 FP-Tree，把每个事务中的数据项按降序依次插入到一棵以NULL为根结点的树中，同时在每个结点处记录该结点出现的支持度。如果插入时频繁项节点已经存在了，则把该频繁项节点支持度加1；如果该节点不存在，则创建支持度为1的节点，并把该节点链接到项头表中。

3.求出每个节点的条件模式基

4.为每个节点建立FP-Tree

5.递归 调用FP-growth(Tree，null)开始进行挖掘。伪代码如下： procedure FP_growth(Tree, a)if Tree 含单个路径P then{

for 路径P中结点的每个组合（记作b）

产生模式b U a，其支持度support = b 中结点的最小支持度； } else {

for each a i 在Tree的头部(按照支持度由低到高顺序进行扫描){ 产生一个模式b = a i U a，其支持度support = a i-support；

构造b的条件模式基，然后构造b的条件FP-树Treeb； if Treeb 不为空 then 调用 FP_growth(Treeb, b)； } }

FP-growth的执行过程：

1）在FP-growth递归调用的第一层，模式前后a=NULL，得到的其实就是频繁1-项集。2）对每一个频繁1-项，进行递归调用FP-growth()获得多元频繁项集。②优点：

（ppt翻译）

1.算法结构拥有完整性：

1）没有破坏事务的长模式；

2）能保留频繁模式挖掘的完整信息。2.算法结构拥有紧凑性：

1）不相关的项被删除；

2）事务项按照频率降序排列，因为更频繁的项更可能被找到；

3）如果不计算链接和节点数目，存储空间小于原始数据库。

3.FP算法的效率比Apriori算法快一个数量级,效率快的原因有以下4个：

1）没有候选集，没有候选测试

2）有紧凑的数据结构

3）消除重复的数据库遍历

4）基础操作是计数和FP-Tree的建立 ③缺点：

（参考http://www.teniu.cc/wiki/Covariance_matrix

我们认为bi代表B的第i行，那么由协方差矩阵

推知

<>表示向量的内积，也就是每一项的积之和。⑤ 计算协方差矩阵C的特征值和特征向量

若XA=aA,其中A为一列向量，a为一实数。那么a就被称为矩阵X的特征值，而A则是特征值a对应的特征向量。

顺便扯一下，在matlab里面，求解上述A以及a，使用eig函数。如[D,V] = eig(C)，那么D就是n个列特征向量，而V是对角矩阵，对角线上的元素就是特征值。⑥ 排序

将特征值按从大到小的顺序排列，并根据特征值调整特征向量的排布。

D'=sort(D);V'=sort(V);

⑦ 计算总能量并选取其中的较大值

若V'为C的对角阵，那么总能量为对角线所有特征值之和S。

由于在步骤⑥里面已对V进行了重新排序，所以当v'前几个特征值之和大于等于S的90%时，可以认为这几个特征值可以用来“表征”当前矩阵。

假设这样的特征值有L个。⑧ 计算基向量矩阵W

实际上，W是V矩阵的前L列，所以W的大小就是 MxL。⑨ 计算z-分数（这一步可选可不选）

Z[i,j]=B[i,j]/sqrt(D[i,i])⑩ 计算降维后的新样本矩阵

W*表示W的转置的共轭矩阵，大小为 LxM , 而Z的大小为 MxN , 所以Y的大小为 LxN , 即降维为 N 个 L 维向量。

②优点： 该算法可以消除数据间的冗余，以简化数据，提高计算效率。③缺点：缺乏主成分的物理解释，也就是缺乏有效的语义解释。

PCA假设数据各主特征是分布在正交方向上，如果在非正交方向上存在几个方差较大的方向，PCA的效果就大打折扣了。

PCA技术的一个很大的优点是，它是完全无参数限制的。在PCA的计算过程中完全不需要人为的设定参数或是根据任何经验模型对计算进行干预，最后的结果只与数据相关，与用户是独立的。

但是，这一点同时也可以看作是缺点。如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高

PCA也存在一些限制，例如它可以很好的解除线性相关，但是对于高阶相关性就没有办法了，对于存在高阶相关性的数据，可以考虑Kernel PCA，通过Kernel函数将非线性相关转为线性相关

④改进：

第二篇：斯坦福大学机器学习梯度算法总结

斯坦福大学机器学习梯度下降算法学习心得和相关概念介绍。

1基础概念和记号

线性代数对于线性方程组可以提供一种简便的表达和操作方式，例如对于如下的方程组：

4x1-5x2=13

-2x1+3x2=-9

可以简单的表示成下面的方式：

X也是一个矩阵，为(x1,x2)T，当然你可以看成一个列向量。

1.1基本记号

用A ∈表示一个矩阵A，有m行，n列，并且每一个矩阵元素都是实数。用x ∈ , 表示一个n维向量.通常是一个列向量.如果要表示一个行向量的话，通常是以列向量的转置（后面加T）来表示。

1.2向量的内积和外积

根据课内的定义，如果形式如xT y，或者yT x，则表示为内积，结果为一个实数，表示的是：，如果形式为xyT，则表示的为外积:。

1.3矩阵-向量的乘法

给定一个矩阵A ∈ Rm×n，以及一个向量x ∈ Rn，他们乘积为一个向量y = Ax ∈ Rm。也即如下的表示：

如果A为行表示的矩阵（即表示为），则y的表示为：

相对的，如果A为列表示的矩阵，则y的表示为：

即：y看成A的列的线性组合，每一列都乘以一个系数并相加，系数由x得到。

同理，yT=xT*A表示为：

yT是A的行的线性组合，每一行都乘以一个系数并相加，系数由x得到。

1.4矩阵-矩阵的乘法

同样有两种表示方式:

第一种：A表示为行，B表示为列

第二种，A表示为列，B表示为行：

本质上是一样的，只是表示方式不同罢了。

1.5矩阵的梯度运算（这是老师自定义的）

定义函数f，是从m x n矩阵到实数的一个映射，那么对于f在A上的梯度的定义如下：

这里我的理解是，f（A）=关于A中的元素的表达式，是一个实数，然后所谓的对于A的梯度即是和A同样规模的矩阵，矩阵中的每一个元素就是f(A)针对原来的元素的求导。

1.6其他概念

因为篇幅原因，所以不在这里继续赘述，其他需要的概念还有单位矩阵、对角线矩阵、矩阵转置、对称矩阵（AT=A）、反对称矩阵（A=-AT）、矩阵的迹、向量的模、线性无关、矩阵的秩、满秩矩阵、矩阵的逆（当且仅当矩阵满秩时可逆）、正交矩阵、矩阵的列空间(值域)、行列式、特征向量与特征值……

2用到的公式

在课程中用到了许多公式，罗列一下。嗯，部分公式的证明很简单，部分难的证明我也不会，也懒得去细想了，毕竟感觉上数学对于我来说更像是工具吧。

转置相关：

•(AT)T = A

•(AB)T = BT AT

•(A + B)T = AT + BT 迹相关： • For A ∈ Rn×n, trA = trAT.• For A, B ∈ Rn×n, tr(A + B)=trA + trB.• For A ∈ Rn×n, t ∈ R, tr(tA)= t trA.• For A, B such that AB issquare, trAB = trBA.• For A, B, C such that ABC issquare, trABC = trBCA = trCAB。当乘法变多时也一样，就是每次从末尾取一个矩阵放到前面去，这样的矩阵乘法所得矩阵的迹是一致的。秩相关

• For A ∈ Rm×n,rank(A)≤ min(m, n).If rank(A)= min(m, n), 则A称为满秩

• For A ∈ Rm×n,rank(A)= rank(AT).• For A ∈ Rm×n, B ∈ Rn×p,rank(AB)≤ min(rank(A), rank(B)).• For A, B ∈ Rm×n,rank(A + B)≤ rank(A)+rank(B).逆相关：

•(A−1)−1 = A

• If Ax = b, 左右都乘以A−1 得到 x = A−1b.•(AB)−1 = B−1A−1

•(A−1)T =(AT)−1.F通常表示为A−T.行列式相关：

• For A ∈ Rn×n, |A| = |AT |.• For A, B ∈ Rn×n, |AB| = |A||B|.• For A ∈ Rn×n, |A| = 0，表示矩阵A是奇异矩阵，不可逆矩阵

• For A ∈ Rn×n and A 可逆, |A|−1 = 1/|A|.梯度相关： • ∇x(f(x)+ g(x))= ∇xf(x)+ ∇xg(x).• For t ∈ R, ∇x(t f(x))= t∇xf(x).• ∇xbT x = b

• ∇xxT Ax = 2Ax(if A 对称)

• ∇2xxT Ax = 2A(if A 对称)

• ∇A|A| =(adj(A))T = |A|A−T.adj=adjoint

3梯度下降算法和正规方程组实例应用

例子用的是上节课的房价的例子，有一组数据，有房子面积和房子价格，输入格式举例：

老师定义的变量如下：

m:训练样本的数目

x：输入的变量（输入的特征，在这个例子中为房子面积，后来又加了一个房子的卧室数目）

y :输出变量（目标变量，这个例子中就是房价）

(x,y)：表示的是一个样本

：表示的第i个样本，表示为。

3.1监督学习概念

所谓的监督学习即为告诉算法每个样本的正确答案，学习后的算法对新的输入也能输入正确的答案。监督指的是在训练样本答案的监督下，h即为监督学习函数。

此例中我们假设输出目标变量是输入变量的线性组合，也就是说，我们的假设是存下如下的h（x）：

Theta表示是特征前面的参数（也称作特征权重）。也就是经过h(x)之后得到的就是预测的结果了。

如果假设x0=1，那么原来的h(x)就可以简单的表示为如下形式：，其中n为特征数目，我们为了表达简便，把theta和x都写成向量的形式。下面就是如何求出θ（向量）使得h(x)尽可能接近实际结果的,至少在训练集内接近训练集中的正确答案。

我们定义一个花费函数(costfunction)，针对每一组θ，计算出h(x)与实际值的差值。定义如下：

这也是用的最小二乘法的思想，但是之所以乘以1/2是为了简化后面的计算。针对训练集中的每一组数据。剩下的问题就是求得minJ（θ）时的θ取值，因为J(θ)是随着θ变化而变化，所以我们要求得minJ（θ）时的θ就是我们想要的θ（这个min也叫做最小花费函数)，怎么样求出这组theta呢？采用的方法就是梯度下降算法和正规方程组。我们首先来看梯度下降算法。

3.2梯度下降算法

梯度下降算法是一种搜索算法，基本思想可以这样理解：我们从山上的某一点出发，找一个最陡的坡走一步（也就是找梯度方向），到达一个点之后，再找最陡的坡，再走一步，直到我们不断的这么走，走到最“低”点（最小花费函数收敛点）。

如上图所示，x,y表示的是theta0和theta1，z方向表示的是花费函数，很明显出发点不同，最后到达的收敛点可能不一样。当然如果是碗状的，那么收敛点就应该是一样的。

算法的theta更新表示如下：

对每一个theta(j),都先求J(θ)对theta(j)的偏导(梯度方向)，然后减少α，然后将现在的theta(j)带入，求得新的theta(j)进行更新。其中α为步长，你可以理解为我们下山时走的步子的大小。步子太小了，收敛速度慢，步子太大了，可能会在收敛点附近来回摆动导致无法到达最低点。P.S.这个符号根据老师所说理解为程序中的赋值符号(=号)，如果是=号，则理解为值是相等的(编程里面的==号)。下面我们先理解下，假设现在训练集只有一组数据求关于theta(j)的偏导：

带入

可以得到关于一组数据的theta(j)的表达式，不妨，这组数据就是第i组，则表示为：

然后我们将这个更新theta(j)的方法扩充到m个训练样本中，就可以得到下面的式子：

P.S.最外面的那个xj(i)的理解为：第i组数据中的第j个特征(feature)值。

3.2.1批量梯度下降算法（batch gxxxxdxxxx algorithm）

重复执行上面的这个更新步骤，直到收敛，就可以得到这组θ的值了。就是这个过程：。

这个算法就是批量梯度下降算法，为什么叫批量梯度下降？因为注意到上式中每更新一个θj都需要计算所有的样本取值，所以当样本数目非常大的时候(例如上万条甚至数十万条的时候)，这样的更新非常慢，找θ也非常慢，所以就有了另外一种改进的梯度下降算法。

3.2.2随机梯度下降算法/增量梯度下降算法

做一个小小的改进，用一个样本做一个theta的更新，比如用样本1做theta(1)的更新，用样本2做theta(2)的更新，以此类推。这种方法的好处是速度上肯定比批量梯度下降算法快，而且样本数据越多，体现应该就越明显。劣势是得到的收敛点的值和批量梯度算法比起来也许不是最优的值。

3.2.3梯度下降算法总结

不管是批量梯度算法还是随机梯度下降算法，他们的共同点有以下：

1.时间复杂度都是O(mn)(m为样本数目，n为特征值/影响因子数目)

2.都有梯度下降性质：接近收敛时，每次“步子”（指实际减去的数，而不是前面定义的α，α是手动设置参数，人为改变才会变）会越来越小。其原因是每次减去α乘以梯度，但是随着收敛的进行，梯度会越来越小，所以减去的值会。

3.判定收敛的方法都是如下两种:

1)两次迭代值改变量极小极小

2)J(θ)的值改变量极小极小

3.3正规方程组

写在前面：这种方法是另一种方法了，和梯度下降算法就没啥联系了！！！

首先回顾下前面定义的矩阵梯度运算：

例如:

则：

定义一个矩阵，称作设计矩阵，表示的是所有的样本的输入：

因为前面得到的结论：

（θT*x(i)和x(i)的转置*θ结果是一样），可以得到

可以写成如下的形式：

又因为对于任意向量，所以可以得到：

运用下面介绍的一系列性质：

（5）是由(2)和(3)得到的，进行下面的推导

中间加tr不变的原因是因为是一个实数(看成1x1矩阵)加迹等于他本身。

将上式设为0，得到正规方程组

求解得到

第三篇：面试备用：18大机器学习经典算法总结

学习18大经典数据挖掘算法

大概花了将近2个月的时间，自己把18大数据挖掘的经典算法进行了学习并且进行了代码实现，涉及到了决策分类，聚类，链接挖掘，关联挖掘，模式挖掘等等方面。也算是对数据挖掘领域的小小入门了吧。下面就做个小小的总结，后面都是我自己相应算法的博文链接，希望能够帮助大家学习。

1.C4.5算法。C4.5算法与ID3算法一样，都是数学分类算法，C4.5算法是ID3算法的一个改进。ID3算法采用信息增益进行决策判断，而C4.5采用的是增益率。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42395865

2.CART算法。CART算法的全称是分类回归树算法，他是一个二元分类，采用的是类似于熵的基尼指数作为分类决策，形成决策树后之后还要进行剪枝，我自己在实现整个算法的时候采用的是代价复杂度算法，详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42558235

3.KNN(K最近邻)算法。给定一些已经训练好的数据，输入一个新的测试数据点，计算包含于此测试数据点的最近的点的分类情况，哪个分类的类型占多数，则此测试点的分类与此相同，所以在这里,有的时候可以复制不同的分类点不同的权重。近的点的权重大点，远的点自然就小点。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42613011

4.Naive Bayes(朴素贝叶斯)算法。朴素贝叶斯算法是贝叶斯算法里面一种比较简单的分类算法，用到了一个比较重要的贝叶斯定理，用一句简单的话概括就是条件概率的相互转换推导。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42680161

5.SVM(支持向量机)算法。支持向量机算法是一种对线性和非线性数据进行分类的方法，非线性数据进行分类的时候可以通过核函数转为线性的情况再处理。其中的一个关键的步骤是搜索最大边缘超平面。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42780439

6.EM(期望最大化)算法。期望最大化算法，可以拆分为2个算法，1个E-Step期望化步骤,和1个M-Step最大化步骤。他是一种算法框架，在每次计算结果之后，逼近统计模型参数的最大似然或最大后验估计。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/42921789

7.Apriori算法。Apriori算法是关联规则挖掘算法，通过连接和剪枝运算挖掘出频繁项集，然后根据频繁项集得到关联规则，关联规则的导出需要满足最小置信度的要求。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43059211

8.FP-Tree(频繁模式树)算法。这个算法也有被称为FP-growth算法，这个算法克服了Apriori算法的产生过多侯选集的缺点，通过递归的产生频度模式树，然后对树进行挖掘，后面的过程与Apriori算法一致。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43234309

9.PageRank(网页重要性/排名)算法。PageRank算法最早产生于Google,核心思想是通过网页的入链数作为一个网页好快的判定标准，如果1个网页内部包含了多个指向外部的链接，则PR值将会被均分，PageRank算法也会遭到Link Span攻击。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43311943

10.HITS算法。HITS算法是另外一个链接算法，部分原理与PageRank算法是比较相似的，HITS算法引入了权威值和中心值的概念，HITS算法是受用户查询条件影响的，他一般用于小规模的数据链接分析，也更容易遭受到攻击。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43311943

11.K-Means(K均值)算法。K-Means算法是聚类算法，k在在这里指的是分类的类型数，所以在开始设定的时候非常关键，算法的原理是首先假定k个分类点，然后根据欧式距离计算分类，然后去同分类的均值作为新的聚簇中心，循环操作直到收敛。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43373159

12.BIRCH算法。BIRCH算法利用构建CF聚类特征树作为算法的核心，通过树的形式，BIRCH算法扫描数据库，在内存中建立一棵初始的CF-树，可以看做数据的多层压缩。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43532111

13.AdaBoost算法。AdaBoost算法是一种提升算法，通过对数据的多次训练得到多个互补的分类器，然后组合多个分类器，构成一个更加准确的分类器。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43635115

14.GSP算法。GSP算法是序列模式挖掘算法。GSP算法也是Apriori类算法，在算法的过程中也会进行连接和剪枝操作，不过在剪枝判断的时候还加上了一些时间上的约束等条件。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43699083

15.PreFixSpan算法。PreFixSpan算法是另一个序列模式挖掘算法，在算法的过程中不会产生候选集，给定初始前缀模式，不断的通过后缀模式中的元素转到前缀模式中，而不断的递归挖掘下去。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43766253

16.CBA(基于关联规则分类)算法。CBA算法是一种集成挖掘算法，因为他是建立在关联规则挖掘算法之上的，在已有的关联规则理论前提下，做分类判断，只是在算法的开始时对数据做处理，变成类似于事务的形式。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43818787

17.RoughSets(粗糙集)算法。粗糙集理论是一个比较新颖的数据挖掘思想。这里使用的是用粗糙集进行属性约简的算法，通过上下近似集的判断删除无效的属性，进行规制的输出。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43876001

18.gSpan算法。gSpan算法属于图挖掘算法领域。，主要用于频繁子图的挖掘，相较于其他的图算法，子图挖掘算法是他们的一个前提或基础算法。gSpan算法用到了DFS编码，和Edge五元组，最右路径子图扩展等概念，算法比较的抽象和复杂。

详细介绍链接：http://blog.csdn.net/androidlushangderen/article/details/43924273

第四篇：各种排序算法的优缺点

一、冒泡排序

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与 a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比 较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理 n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

优点：稳定；

缺点：慢，每次只能移动相邻两个数据。

二、选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟 排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

优点：移动数据的次数已知（n-1次）；

缺点：比较次数多。

三、插入排序

已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、b[2]、……b[m]，需将二者合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继续跳过，直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来 a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1的数组a）

优点：稳定，快；

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

四、缩小增量排序

由希尔在1959年提出，又称希尔排序(shell排序)。

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入 排序的效果很好。首先取一增量d(d

优点：快，数据移动少；

缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。

五、快速排序

快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x] 作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数 据a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n] 两组数据进行快速排序。

优点：极快，数据移动少；

缺点：不稳定。

六、箱排序

已知一组无序正整数数据a[1]、a[2]、……a[n]，需将其按升序排列。首先定义一个数组x[m],且m>=a[1]、a[2]、……a[n]，接着循环n次，每次x[a]++.优点：快，效率达到O(1)缺点：数据范围必须为正整数并且比较小

六、归并排序

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1)3(2)2(3)2(4)5(5)(括号中是记录的关键字)时输出的 1(1)2(3)2(4)3(2)5(5)中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.归并排序：归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。

堆排序：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。

第五篇：公开课优缺点及改进措施,文档

关于新教师朱生红汇报课的评价与改进措施 优点：

1、教学环节有新意。

2、引入运用大量古诗词，激发学生兴趣。

3、问题设计合理。

4、设计内容比较广泛。

不足：

1、教师上课放的不够开。

2、教学环节过渡不够自然。

3、朗读过程中，对每次朗读应提出不同的要求。

4、教师语言不够精炼。

5、对与多媒体课件环节的相接不够熟练。改进措施

1，多听优秀教师的的课。

2、注重基本功的训练。

3、上课前要吃透教材。

4、多看优秀视频，学习先进经验。

5、多和优秀教师交流，提高课堂效率。