第一篇：斯坦福大学机器学习梯度算法总结
斯坦福大学机器学习梯度下降算法学习心得和相关概念介绍。
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
第三篇：机器学习算法优缺点改进总结
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等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN(weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。
（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.xiexiebang.com/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函数将非线性相关转为线性相关 ④改进： CS229 Lecture notes Andrew Ng 监督式学习 让我们开始先讨论几个关于监督式学习的问题。假设我们有一组数据集是波特兰，俄勒冈州的47所房子的面积以及对应的价格 我们可以在坐标图中画出这些数据： 给出这些数据，怎么样我们才能用一个关于房子面积的函数预测出其他波特兰的房子的价格。 为了将来使用的方便，我们使用x表示“输入变量”（在这个例子中就是房子的面积），也叫做“输入特征”，y表示“输出变量”也叫做“目标变量”就是我们要预测的那个变量（这个例子中就是价格）。一对（x,y）叫做一组训练样本，并且我们用来学习的---一列训练样本｛（x,y）；i=1，„，m｝--叫做一个训练集。注意：这个上标“（i）”在这个符号iiiiii表示法中就是训练集中的索引项，并不是表示次幂的概念。我们会使用χ表示输入变量的定义域，使用表示输出变量的值域。在这个例子中χ=Y=R 为了更正式的描述我们这个预测问题，我们的目标是给出一个训练集，去学习产生一个函数h：X→ Y 因此h(x)是一个好的预测对于近似的y。由于历史性的原因，这个函数h被叫做“假设”。预测过程的顺序图示如下： 当我们预测的目标变量是连续的，就像在我们例子中的房子的价格，我们叫这一类的学习问题为“回归问题”，当我们预测的目标变量仅仅只能取到一部分的离散的值（就像如果给出一个居住面积，让你去预测这个是房子还是公寓，等等），我们叫这一类的问题是“分类问题” PART I Linear Reression 为了使我们的房子问题更加有趣，我们假设我们知道每个房子中有几间卧室： 在这里，x是一个二维的向量属于R。例如，x1i就是训练集中第i个房子的居住面积，i是训练集中第i个房子的卧室数量。（通常情况下，当设计一个学习问题的时候，这些输x22入变量是由你决定去选择哪些，因此如果你是在Portland收集房子的数据，你可能会决定包含其他的特征，比如房子是否带有壁炉，这个洗澡间的数量等等。我们以后可能会涉及到更多变量的问题，现在我们先按照给定的变量的讲解。） 为了完成监督是学习，我们必须决定怎么样去描述我们的函数/假设 h 在计算机中。有一个最初的选择，我们把y近似的看成是x的一个线性函数：hx01x12x2 在这里，θ(i)是参数（也叫做权重）是y关于x的线性函数之间的参数。当y与x之间没有其他影响因素的时候我们将会舍弃下标θ，通常写为h(x)。为了简化我们的标注，我们习惯上令x0=1（这个是截距），因此可以写成 右边的θ和x都是向量并且这里n是输入的变量的个数（不是计算x0的个数）。 现在给定一个训练集，我们怎么选择、学习、计算权重θ？一个合理的方法类似与让hx尽可能的接近于y，至少对于我们所训练的数据都是适合的。使这个近似形式化，我们定义一个测量函数去记录对于每一个θ，h(x(i))有多接近于y(i)。我们定义一个代价函数 如果你以前了解过线性回归，你会认出这个和最小二乘法比较近似。不管你以前是否看过他，让我们继续，并且我们最终会证明这个知识众多的算法大家庭中的一个特例而已。LMS algorithm(Least Mean Square 最小均方差算法)我们想去选择一个θ使得J(θ)取的最小值。为了这样做，我们用一个寻找算法给θ赋一个初值（随机的），然后不断的重复改变θ的大小以便是J(θ)更小，直到我们找到一个θ是的J(θ)达到我们期望的最小值。特别的，我们考虑“梯度下降算法”，用下面这个公式寻找θ。 （这个更新过程同时的对所有的j=0…n执行）α表示“学习速率”。这是一个自然算法，反复的对J在减小的方向上迈出一大步直到最小。 为了执行这个算法，我们需要做的工作就是计算出等号右边的偏导数。首先我们计算出一组（x，y）样本的偏导数，这是我们可以先忽略掉对J的求和。（运用求导定律很容易就能求出导数） 对于单一的训练样本，这里给出了更新的规则： 这个规则就叫做LMS更新规则（LMS是least mean squares的缩写）也被叫做Widrow-Hoff（就是Widrow和Hoff这两位大仙发明的这个算法。参考链接：http://baike.baidu.com/link?url=bmZNDF9xV8GMtSE_rk9eV_9UbE9wGrnAdYqyf876U3Lf4IKfkRZVCoACvxF2dm1zmRDu1UUYzW9nQs-8oPWhu_）学习规则。这个算法有几个自然的和直观的特性。例如，更新的量级正比于误差项 (y(i)− h_(x(i)))；因此，当我们遇到一组训练样本的预测值非常接近他的真实值的时候，我们会发现在更新过程中权重项基本不变；相反的这个权重项会有一个大的变化当我们的预测值hθ(x(i))有大的误差的时候（例如预测值和真实值y(i)差别非常大的时候） 我们推断出了当有一个训练样本是的LMS算法。我们有两种方法可以让这个算法去适应多于一个训练样本的例子。第一种是用下面这种算法替换: 可以很容易的证明上述的更新规则算法的运算量仅仅是 J()（对J的初始化定义）。j因此这是一个简单的梯度下降算法对于原始成本函数J。这个方法注重每一个训练样本在训练过程中的每一步，所以也被叫做“批量梯度下降”。注意，梯度下降算法容易受到局部最小值的影响，这个优化问题我们对于线性回归算法只有一个目标就是找到最合适的，因此梯度下降算法总是收敛于全局最小值。（将设学习率α不是很大）实际上，J是一个凸函数。这里我们有一个梯度下降算法的例子，是使这个二次函数取得最小值。 B 这些椭圆表示了这个二次函数的等高线。这个紫色的线条表示的是取得最小值的轨迹，T初始化（48，30）。这个X标识出来在图中在梯度下降算法计算出的每个θ值，并且用实线连接起来。 当我们运行批量梯度算法去计算θ在我们以前的数据集去估计房子的价格使用房子的价格和房子面积的函数，我们得到0=71.27，1=0.1345.如果我们把 h(x)当作x（面积）的函数，使用训练样本中的数据，我们能得到下面这张图： 如果卧室数量也被当作一组输入变量，我们得到0=89.60，1=0.1392，2=-8.738.上面这些结果都是我们使用批量梯度算法得到的。对于批量梯度算法算法可以有其他的选择使他更好的预测。考虑一下下面这个算法： 在这个算法中，我们重复的使用梯度下降算法在训练样本中，并且每一次我们遇到一个训练样本，我们更新这个权重仅仅根据每一次对训练样本训练的梯度误差。这种算法叫做“随机梯度下降法”（也叫做增量梯度下降法。）然而批量梯度下降法必须要扫描全部的训练集在进行每一步之前----一个多余的操作如果m特别大的话----随即梯度下降算法可以随时开始，并且可以继续进行下一步在他跟踪的样本上。一般情况下，随即梯度下降算法会比批量梯度算法更快的使的θ“接近”最小值。（注意虽然根本不可能收敛到最小值，并且这个权重θ会一直震荡在使的J(θ)取得最小值的θ的附近；但是实际上大多数在最小值附近的值已经可以取了，已经可以近似的使函数取得最小值了）。更多的原因，特别是当这个训练集很大的时候，随即梯度下降算法通常是优先选择相对于批量梯度算法。The normal equations 梯度下降法给出了一种方法最小化J。让我们讨论另一种方法最小化J，这个算法明确的求解最小化并且不依赖于迭代算法。使用这种方法，我们通过计算J的导数来最小化J并且使他们等于0。为了不在运算过程中写过多的代数和大量的矩阵，这里对使用的计算矩阵的符号做一些介绍。 2.1 Matrix derivatives、定义一个函数，从m*n的矩阵到实数的映射，（f：Rm*nR）定义f关于矩阵A的导数： 因此梯度Af(A)本身就是 A112f一个m*n维的矩阵，对于（i,j）的元素就是。举个例子，假设A=AijA212*2维的矩阵，并且函数f：R2*2A12是一个A22R 已给定为：f(A)32A115A12A21A22 2这里Aij表示矩阵 A中（i,j）维的元素。我们得到： 这里介绍一下迹算子记作“tr”。对于一个n*n维的矩阵A，A的迹就是矩阵主对角线上元素 的和trAAi1nii。如果a是一个实数（例如a是一个1*1维的矩阵），tra=a。（如果你以前么有见到过这个运算符号，你可以矩阵A的迹看作tr（A）或者对矩阵A求他的迹。） 迹运算同样适用于两个矩阵A和B因此AB如果都是方阵，我们可以得到 tr(AB)=tr(BA)。下面是这个公式的一些推论，我们有如下： 下面对于迹的操作的一些公式也很同意证明。这里A和B都是方阵，并且a是一个实数 我们下面给出一些矩阵导数的迹推论并不进行证明（本节中不会用到）。等式（4）仅仅适用于非奇异方阵A，|A|表示A的行列式。 为了使我们的矩阵符号更具体，让我们现在详细解释第一类方程的意义。假设我们有一些固定的矩阵B∈Rn*m.我们可以定义一个函数f：Rn*mn*m→R根据F（a）= tr(AB)。注意，这个定义是有意义的，因为如果AR确实是从Rn*m，然后AB是一个方阵，我们可以将其应用到它，因此f到R的映射。我们可以运用我们的定义矩阵导数找到Af(A)，m*n矩阵。 T方程（1）在上述情况下，该矩阵的输入（i，j）的值可以由B给出或者等价于Bji。方程的证明（1-3）是相当简单的，留下作为给读者的练习。方程（4）可以使用伴随矩阵和矩阵的逆来推导。2.2 Least squares revisited 随着矩阵导数，我们开始继续在封闭的模型中寻找θ使的J（θ）取得最小值，开始先把J重新写入向量矩阵中。 给定一个训练集，定义m*n维的矩阵X（实际上是m*（n+1）维的，如果算上偏置项）在矩阵中包含给定的训练集的输入值在 同时，定义y为一个一维的列向量，值为所有的目标值 现在，从我们可以很容易证明： 运用定理 可以得到 最后，为了最小化J，我们寻找J(θ)关于θ的导数。结合式子（2）和（3），我们发现 因此有： AT,BBTXXT 在第三步中，我们使用了实数的迹就是实数本身这个定理；第四步我们使用了在第五步中我们对式5使用AT,BBTXXT和C=I和公式1.为了最tr(A)tr(AT)，小化J，我们使他的导数等于0可以得到如下等式： 因此，使的J(θ)最小的θ的值就可以有下式得到： Probabilistic interpretation 当得到一个回归问题时，什么时候使用线性回归，什么时候选择最小二乘算法去计算价值函数J？本节中，我们会给出一系列的假设来描述什么情况下使用最小二乘算法最合适。 假设我们的目标变量和输入变量的关系是： xix i表示误差项（就像我们预测房价例子中有很多其他因素比如地理位置，房屋年龄等这些我们考虑外的对房价有影响的因素我们没有计算进去），或者随机噪声。我们进一步假定i是分散的IID(independently and identically distributed)根据高斯分布（也叫正态分布）均值为0方差为2。我们可以写出这个i的定义iN(0,2)。也就是说i的概率密度是给定的 这表明： 说明yi的分布是由xi和θ控制的。注意，我们不能单独以θ为的条件，因为θ不是一个随机值。我们也能把这个式子写成另外一种形式： 给定X（设定好的矩阵包含所有的输入变量xi）和θ，如何求的yi的分布呢？这个可能的值就是。这个值代表y（或者X）的一个关于θ的函数。当我们明确 的理解这个函数之后，我们给他起一个名字叫做似然函数： 注意由于这个偏差项i的独立性（同样的y和xi之间）这个式子也可以写成 i 现在给定这个概率模型关于y和xi，怎么去选择最合理的方法去最好的求解我们想 i要得到的参数θ？这个极大似然函数使的我们能尽可能的取得最好的θ。我们应该选择θ使的L(θ)最大。 最大化L(θ)，我们可以最大化任意的单调递增函数L(θ)。特别的，求他的派生物（这里表示的是对数）的最大值回事比较简单的方法 ： 因此，最大化相当于最小化 我们认出了这个J(θ)就是我们的最小二乘法函数。 小结：在前面的概率模型计算中，使用最小二乘算法去寻找θ使得极大似然函数取得最大值。这个是一种比较合理的方法使用最小二乘法算法求解问题。（注意虽然这个方法是合理的和比较好的但是一定还有更加合适的方法去使用这个方法） 注意，在我们前面的讨论中，我们最终的选择θ并没有使用到偏差项，而且也是因为即使偏差项我们不知道，计算的结果仍然是一样的。这个结论我们会在后续讨论指数族和广义线性模型的时候用到。Locally weighted linear regression（局部加权线性回归） 考虑这个问题从x属于R预测 y。这个最左边的模型显示出这个预测得到的结果函数。我们看到这个数据并没有全部落到这个线上，所以说这个预测结果并不是很。 相反的，如果我们给这个函数加上一个额外的变量x2，预测函数则为，然后我们得到一个比刚才那个更适给定数据的预测函数（中间这幅图）。看起来好像我们加上去的变量越多这个模型越好。然而，加上太多的模型也是危险的对于我们的预测来说：右边这个模型是一个使用了五个自变量的预测模型。我们可以看到这个模型完美的适和我们给定的数据，我们不能期待这个是一个好的预测模型对于使用房子的面积去预测房子的价格。在没有正式定义这些模型之前，我们可以看到左边这个模型是低拟合度的例子-----给定训练集中的数据离我们给出的预测函数相差太多----右边这个模型是过拟合度的例子。（本节课的后面，我们会给出这些定义的概念，并且给更加详细的定义去判断一个预测模型是好还是坏） 正如前面讨论的和在上面例子中展示的，特征变量的选择直接决定了一个学习模型的好坏。（当我们讨论模型选择时候，我们会看到模型会自动选择特征变量。）在这部分，我们来讨论一下局部加权线性回归算法（LWR）假设有足够的训练数据，特征变量未鉴定。这个方法是聪明的，你会得到机会去发现这个算法的一些优异之处在你的作业中。 在经典线性回归算法中，我们在一个点x做出预测我们将会： 1、寻找使 2、输出Tx 相反的在局部加权线性回归算法中我们会这样做： 最小化的θ 1、寻找使T2、输出x 最小的θ 在这里是一些非负的权值。更直接的如果是一个非常大的特殊值关于i的，之后 更小。如果 很小，之在选择θ的过程中，我们会尽最大努力去使后计算过程中的误差项可以直接被忽略在寻找的过程中。 一个公平的标准选着权值的公式是： i注意那些我们将要预测x并且对特别点x有依赖的权值。特别的是如果|xx|很小，这个 i权值就会接近1；并且如果|xx|很大，这个权值就会很小。因此，θ被选来作为更高的“权重”去减小误差使的取得最合适的值在x偏差较大的点上。（注意，而权重公式外观类似于高斯分布的密度，形成W是不直接跟高斯有任何联系，和特别是W不是随机变量，正态分布或其他参数τ控制。）如何快速的训练样本的重量脱落的x距离从查询点X；τ叫做带宽参数，而且也是你会在你的家庭作业见到的东西。 局部加权线性回归是我们看到的非参数化算法的第一个例子。（未加权）线性回归算法，我们前面看到的是一个众所周知的参数学习算法，因为它有一个固定的，有限数量的参数（θ），这是适合这个数据的。一旦我们适应θ并且储存了他，我们不再需要保持训练数据进行未来预测。相反，使用局部加权线性回归预测，我们需要整个训练集。术语“非参数化”（粗略）指的是，我们需要保持的东西的量，以表示的假设小时增长线性的训练集的大小。 Part II Classification and logistic Regression(分类和线性回归) 现在让我们来分析分类问题。这就和回归问题一样，除了我们现在要预测的值y仅仅是一些小的离散的值之外。现在开始，我们将会把目光放在二元分类问题上，也就是y只能去两个值 0 和 1。（我们在这说的简单的形式可以推广到更加复杂的形式）。例如，如果我们想要建立一个垃圾邮件分类系统，x是邮件的特征，y是1代表是垃圾邮件，是0则代表不是。0也叫做否定类，1也叫做肯定类，一些情况下也用“+、-”来表示。给定x，y也被叫做训练集的标签。Logistic regression 我们可以解决分类问题不论y是否是离散值，并且用以前的线性回归算法去试着预测我们给定x的y值。然而，非常容易证明这个方法是不足的。更直观的是，他对于h(x)没有什么意义当值大于1或者小于0的时候当我们界定y{0,1}。 为了解决这个问题，我们改变这个假设函数h(x)。我们选择 逻辑函数，下面是他的函数图像 注意g(z)趋近1当z趋近于，并且g(z)趋近于0当z趋近于-。另外g(z)和h(x)的值域都是[0,1]。我们约定x01，因此 从现在开始，我们都假定g是已知的。其他函数如果是0—1之间的连续函数也是可以使用的，但是有两个原因我们将会看到（当我们讨论GLMs是，还有讨论生成学习算法的时候）选择他做回归函数是最合适的。在开始下一节千，这里有一个重要的推论关于sigmoid函数的导数： 因此，给定这个逻辑回归模型，怎么去找一个适合的θ？接下来我们将会使用最小二乘法和极大似然估计相结合来求出。将会结合概率和极大似然函数来球权重参数。 我们假设： 注意这个也可以简单的写为 假定给定的m个样本之间都是相互独立的，我们可以得到如下极大似然函数： 像以前一样很容易对这个似然函数的对数求最大值： 怎么样去最大化这个似然函数呢？像在线性回归里面所做的一样，我们可以使用梯度上升法。写成向量的形式，更新式子是 （注意这个公式中的正负号还有我们是要求的是最大值而不是最小值）。首先在一个训练样本（x，y）上使用这个公式，并且对他的对数求导： 我们使用公式 。求出来的就是随即梯度更新规则： 如果我们拿这个和LMS更新规则比较，我们会发现这两个是完全一样的；但是这是不一样的算法得到的，因为h(xi)现在是有非线性的函数Txi定义的。尽管如此，我们还是很好奇为什么不一样的算法和不一样的学习方法会得到同样的结果。这是偶然吗？或者有更深层次的原因在里面，我们将会解答这个问题在GLM模型中。6 Digression: The perceptron learning algorithm（感知学习算法） 我们现在额外的增加一个算法由于一些历史爱好，我们将会回归到整体之后讨论学习理论的时候。试着想一下改变这个逻辑回归模型去要求他去预测一个值是0或1或者其他。为了达到目的自然而然的从新定义g为一个阀值函数 如果我们使用 在前面作为我们的预测函数，其他都不变我们更新规则如：我们叫新的算法为感知学习算法。 在19世纪60年代，这个“感知”被认为是一个粗陋的模型对于人脑中工作的单个神经元。考虑到这个算法比较简单并且作为一个开始对于我们下节理论讨论做一个开头来讲一下。注意虽然这个感知学习算法看起来和我们其他的学习算法一样，实际上他是一个不同于逻辑回归和最小二乘回归类型的算法，特别的是，他很难赋予感知算法概率的应用，或者使用最大似然估计算法去求解。Another algorithm for maximizing ℓ(θ)回到逻辑回归算法g(z)使用sigmoid函数，我们接下来讲解一种不一样的算法来最小化l()开始之前，我们先看一下牛顿的方法去寻找一个函数的零点。特别的，假设我们有一系列的函数f：R—>R，并且我们想找到一个值使的f(θ)=0。这里θ输入R是一个实数。牛顿的方法如下：。这个方法我们可以这样理解，选定一个值做自变量的垂线过函数上这点做函数的切线与函数轴交与一点，再过这点做垂线，再过这点做函数的切下知道找到切线斜率为零的点。下面是一副图表示牛顿法的过程 在左边这张图中我们看到函数f画了一条直线在y=0处。我们希望找到的θ使得f(θ)=0;这个θ的值大约是1.3。假设我们初始化这个算法定义θ=4.5.牛顿的方法是通过函数上这点做f的切线，并且评估这条线的值是否为0.这给我们下一个猜想的对于θ，大约是2.8.最右边的图指出了这个最后一次迭代的结果，这时候更新的θ大约是1.8.一阵迭代之后我们能很快的接近θ=1.3.牛顿的方法给出了一种使f(θ)=0的方法。我们怎么把这个应用到我们求解l函数中？这个函数的最大值相当于去求他的一阶导数等于0的点。因此令f(θ)=l`(θ),我们能使用相同的算法去是L最大，我们得到这个更新规则： （需要考虑的问题：如果我们想要求一个函数的最小值而不是最大值这个算法应该如何改进？） 最后，在我们的逻辑回归设定中，θ是一个向量，因此我们需要推广牛顿法到向量级别。这个推广的方法是把牛顿法应用到多维中（也叫做牛顿—拉普森方法） 这里()是()对θ的偏导数，H是一个n*n的矩阵（实际上是n+1*n+1维的，我们带上截距项）叫做Hessian，是由下面的式子给定： 牛顿法更加快速的收敛到最小值比着梯度下降法，并且需要更少的迭代次数接近最小值。一次牛顿迭代会花费更大的代价比着梯度下降算法，当他要求找到和反相一个海森矩阵的时候，但是如果n不是很大的时候，牛顿算法通常是更快的。当牛顿算法应用到求逻辑回归极大似然函数的最大值的时候，这个求解方法也被叫做Fisher scoring。 Part III Generalized Linear Models（广义线性模型） 至今为止，我们已经看来一个回归分析的例子和一个分类分析的例子。在两个例子中都有一些近似的函数，2回归分析的例子中我们有yx;N(,)，在分类的例子中有yx;Bernoulli() 本节我们将会展示出这些都是广义线性模型中的一部分。我们也会推到一些其他的适用于回归和分类问题中的广义线性模型。The exponential family 为了引出GLMS，我们先说一下指数分布。我们定义一个分布是指数分布如果他可以被写为如下形式： 叫做特性参数（也叫做典型参数）；T(y)是充分统计量（通常情况下T(y)=y），a()是对数划分函数。分量ea()作用是归一化参数，确保p(y;η)的和是大于1的。 T一个复杂的选择，a和b定义一个分布族关于参数η；当我们改变η的值时，我们会得到不同的分布在这个分布族里面。 现在看到的Bernoulli和Gaussian分布都是指数分布的一个例子。Bernoulli分布均值为υ写为Bernoulli（υ），指定一个分布y∈｛0，1｝，写成p（y=1；υ）=Φ；p（y=0；υ）=1-υ h(x) 当我们改变υ的值，我们得到不同均值的Bernoulli分布。现在我们证明这一类的Bernoulli分布，在例子中选择T，a和b所以式子（6）是Bernoulli分布。我们把Bernoulli分布写为： 因此，特性参数由log1给出。有意思的是，当我们使用η表示υ的时候我们会得到υ=1/（1+e^（-η））。这个看起来是不是和sigmoid函数很像。这将会再次被提到当我们把逻辑回归分析看作GLM时。为了完成Bernoulli分布是指数分布的一种的猜想，我们进一步有： 这表明选择适当的T，a和b的时候，Bernoulli分布可以被写成式（6）的形式。我们进一步来讨论Gaussian分布。回想一下，当我们推导线性回归时，的值对我们最终选择的θ和 2h(x)没有任何影响。因此我们可以选择任意值作为2而不去改变他的值。为了简化式子我们定义=1.我们可以得到： 2 因此我们看到高斯分布也在指数分布族里面，当 有许多其他分布指数的家人:多项分布(我们稍后将看到),在泊松分布(造型计数数据;也看到问题集);伽玛和指数(造型连续、非负随机变量,如时间间隔),β和狄利克雷(对概率分布),和许多更多。在下一节中,我们将描述构建模型的一般“食谱”,y(x和θ)来自这些发行版。Constructing GLMs 假设您想要构建一个模型来估计客户来到你的商店的数量y(或您的网站上的页面浏览量数量)在任何给定时刻,基于某些特性x等商店促销,最近的广告、天气、读写等。我们知道,泊松分布通常提供了一个好的模型数量的游客。知道了这一点,我们怎么能想出一个模型问题?幸运的是,泊松是一个指数族分布,所以我们可以应用一个广义线性模型(GLM)。我们将在本节中,我们将描述一个方法构建全球语言监测模型,诸如此类的问题。 更为普遍的是,考虑这样一个分类或回归问题,我们想要预测一些随机变量的值y作为x的函数。获得一个漠视这个问题,我们将进行以下三个假设条件分布的y x和关于我们的模型: 1、y | x;θ∼ExponentialFamily(η)。即。鉴于x和θ,y的分布遵循一些指数族分布,参数η。 2、鉴于x,我们的目标是预测T的预期值x(y)。在我们的大多数示例中,我们将T(y)= y,所以这意味着我们想预测h(x)的输出由我们学习假说h满足h(x)= E[y | x]。(注意,这个假设是选择满足h(x)逻辑回归和线性回归。例如,在逻辑回归,我们有h(x)= p(y = 1 | x;θ)= 0·p(y = 0 | x;θ)+ 1·p(y = 1 | x;θ)= E[y | x;θ]。) 3、η的自然参数和输入x相关线性:η=θT x。(或者,如果η量值,那么ηi =θTi x)。第三的这些假设似乎是最合理的,而且它可能是更好的认为是一种“设计选择”在我们的配方设计的漠视,而不是作为一个假设本身。这三个假设/设计的选择将使我们能够获得一个非常优雅的classof学习算法,即全球语言监测机构,有很多可取的属性,如易于学习。此外,生成的模型往往是非常有效的模拟不同类型的分布在y;例如,我们不久将表明,逻辑回归和普通最小二乘法都可以派生的漠视。9.1 Ordinary Least Squares 表明普通最小二乘法是一种特殊的GLM的家庭模型,考虑设置目标变量y(也称为响应变量在GLM术语)是连续的,而且我们模型x y给定的条件分布为高斯N(μ,σ2)。(在这里,μ可能取决于x)。所以,我们让ExponentialFamily(η)分布是高斯分布。正如我们之前看到的,配方的高斯指数族分布,我们有μ=η。所以,我们有 上面的第一个假设2,平等;第二个平等的合集y | x;θ∼N(μ,σ2),所以其预期值等于μ;第三个平等从假设1(和我们先前推导表明,μ=η配方的高斯指数族分布),和最后一个平等遵循从假设3。 9.2 Logistic Regression 我们现在考虑逻辑回归。我们感兴趣的是二进制分类,因此y∈{ 0,1 }。鉴于y binary-valued,因此自然选择的伯努利家族分布模型的条件分布x y。在我们制定的伯努利分布指数族分布,我们有υ= 1 /(1 + e−)。此外,请注意,如果x,y |θ∼伯努利(υ),然后E x y |,θ=υ。similarderivation后,作为一个普通的最小二乘法,我们得到: 所以,这给了我们假设函数形式的h(x)= 1 /(1 + e−T x)。如果你以前想知道我们想出了物流功能的形式1 /(1 + e−z),这给了一个答案:一旦我们假设x y条件是伯努利,它产生的后果的漠视和指数族分布的定义。引入更多的术语中,该函数g给分配的平均作为自然参数的函数(g(η)= E(T(y);η))被称为规范响应函数。其逆,g−1,称为规范化链接功能。因此,规范响应函数为高斯家庭只是识别功能,和规范化是伯努利响应函数 9.3 Softmax Regression 让我们看看一个GLM的例子。考虑一个分类问题的反应变量y可以承担任何一个k值,因此y∈{ 1 2,。、k}。例如,而不是电子邮件分类到两类垃圾邮件或非垃圾邮件，将是一个二元分类问题,我们可能需要分类成三个类,如垃圾邮件、个人邮件,与工作相关的邮件。响应变量仍然是离散的,但现在能超过两个值。我们将因此分布式根据多项分布模型。 允许派生的GLM造型这种类型的多项数据。这样做,我们将首先表达了多项指数族分布。参数化一个多项式在k可能的结果,可以使用υ1 k参数,。,υk指定每个结果的概率。然而,这些参数将是多余的,或者更正式,他们不会独立(因为知道任何k−1υi独特的决定 最后一个,因为他们必须满足Pkiυi = 1 = 1)。所以,我们将参数化多项式只有k−1参数,υ1,。,υk−1,υi = p(y =我;υ)和p(y = k;υ)= 1−Pk−1 i = 1υi。记数的便利,我们还将让υk = 1−Pk−1 i = 1υi,但我们应该记住,这不是一个参数,而且它完全υ1规定,。,υk−1。 表达多项指数族分布,我们将定义T(y)∈R^k−1如下: 与我们之前的例子,在这里我们没有T(y)= y;此外,T(y)现在是一个k−1维向量,而不是一个实数。我们将编写(T(y))我表示的第i个元素的向量T(y)。我们介绍一个非常有用的符号。一个指标函数1 {·}就值1如果它的参数是正确的,和0(1 {真正} = 1,1 {假} = 0)。例如,1 { 2 = 3 } = 0和1 { 3 =5−2 } = 1。所以,我们还可以写T之间的关系(y)和y(T(y)){ y =我} i = 1。(继续阅读之前,请确保你明白为什么这是真的!)进一步,我们有E[(T(y))我]= P(y =我)=υi。 现在,我们可以证明这个多项式指数家族的一员，有如下： 至此我们制定的多项指数族分布。 链接函数给出了for i= 1,„,k) 为了方便起见,我们也定义ηk=log(υk /υk)= 0 =。逆函数并获得响应函数的联系,因此,我们有 这意味着υk = 1 / Pki = 1 ei,可代替回方程(7)给响应函数 这个函数映射η的υ的叫做将softmax功能。 完成我们的模型,我们使用假设3,鉴于ηi的早些时候,x的线性相关。所以,ηi =θTi x(因为我= 1,。θ1,k−1),。,θk−1∈Rn + 1是我们的模型的参数。记数的方便,我们还可以定义θk = 0,以便ηk =θT k x = 0,鉴于之前。因此,我们的模型假设的条件分布ygiven x等于 这个模型,这也适用于分类问题y∈{ 1,„k },叫做softmax回归。这是一个逻辑回归的概括。 我们的假设将输出 换句话说,我们的假设将输出概率估计p(y =我| x;θ),为每一个值的我= 1,。k。(尽管h(x)如上定义只是k−1维,显然p(y = x k |;θ)可以获得1−Pk−1 i = 1υi)。最后,让我们讨论参数拟合。类似于我们最初派生的普通最小二乘法和逻辑回归,如果我们有一个训练集m的例子{(x(i),y(i));i= 1,„,m },愿学习的参数θi这个模型中,我们将首先写下log-likelihood 获得第二行以上,我们定义用于p(y | x;θ)给出了方程(8)。我们现在可以获得的最大似然估计的参数通过最大化ℓ(θ)θ,使用梯度上升或牛顿法等方法。 机器学习总结报告 刘皓冰 大部分人错误地以为机器学习是计算机像人一样去学习。事实上，计算机是死的，怎么可能像人类一样“学习”呢，机器学习依靠的是数学，更确切地说是靠统计。 如果我们让计算机工作，是给它一串指令，然后计算机会遵照这个指令一步步执行下去，有因有果，非常明确。但这种方式在机器学习中是行不通的。机器学习是不会接受你输入的指令的，它接受的是你输入的数据。也就是说，机器学习是一种让计算机利用数据而不是指令来进行各种工作的方法。这听起来非常不可思议，但结果上却是非常可行的。“统计”思想将在你学习“机器学习”相关理念时无时无刻不伴随，相关而不是因果的概念将是支撑机器学习能够工作的核心概念。 依据数据所做的判断跟机器学习的思想根本上是一致的。机器学习方法是计算机利用已有的数据(输入)，得出了某种模型，并利用此模型预测未来(输出)的一种方法。从数据中学得模型的过程称为“学习”（learning）或“训练”（training），这个过程通过执行某个学习算法来完成。训练过程中使用的数据成为“训练数据”（training data），其中每个样本称为一个“训练样本”（training sample），训练样本组成的集合称为“训练集“（training set）。学得模型对应了关于数据的某种潜在的规律，因此亦称”假设“（hypothesis）；这种潜在规律自身，则称为”真相“或”真实“（ground-truth），学习过程就是为了找出或逼近真相。模型有时也被称为”学习器“（learner），可看作学习算法在给定数据和参数空间上的实例化。 若欲预测的是离散值则此类学习任务被称为“分类”；若欲预测的是连续值则此类学习任务称为“回归”；对只涉及两个类别的“二分类”任务，通常称其中一个类为“正类”，另一个类为“反类”；涉及多个类别时，则称为“多分类”任务。 模型是否准确依赖与数据。如果我的数据越多，我的模型就越能够考虑到越多的情况，由此对于新情况的预测效果可能就越好。这是机器学习界“数据为王”思想的一个体现。一般来说(不是绝对)，数据越多，最后机器学习生成的模型预测的效果越好。 机器学习里面有非常多的经典算法，每种算法都能形成一个模型。下面在简要介绍一下机器学习中的经典代表方法。重点介绍的是这些方法内涵的思想。 1、回归算法 在大部分机器学习课程中，回归算法都是介绍的第一个算法。原因有两个：一.回归算法比较简单，介绍它可以让人平滑地从统计学迁移到机器学习中。二.回归算法是后面若干强大算法的基石，如果不理解回归算法，无法学习那些强大的算法。回归算法有两个重要的子类：即线性回归和逻辑回归。 线性回归一般使用“最小二乘法”来求解。“最小二乘法”的思想是这样的，假设我们拟合出的直线代表数据的真实值，而观测到的数据代表拥有误差的值。为了尽可能减小误差的影响，需要求解一条直线使所有误差的平方和最小。最小二乘法将最优问题转化为求函数极值问题。函数极值在数学上我们一般会采用求导数为0的方法。但这种做法并不适合计算机，可能求解不出来，也可能计算量太大。计算机科学界专门有一个学科叫“数值计算”，专门用来提升计算机进行各类计算时的准确性和效率问题。例如，著名的“梯度下降”以及“牛顿法”就是数值计算中的经典算法，也非常适合来处理求解函数极值的问题。梯度下降法是解决回归模型中最简单且有效的方法之一。 逻辑回归是一种与线性回归非常类似的算法，但是，从本质上讲，线型回归处理的问题类型与逻辑回归不一致。线性回归处理的是数值问题，也就是最后预测出的结果是数字，例如预测一所房子大约可以买多少钱。而逻辑回归属于分类算法，也就是说，逻辑回归预测结果是离散的分类，例如判断肿瘤是恶性还是良性等等。实现方面的话，逻辑回归只是对对线性回归的计算结果加上了一个Sigmoid函数，将数值结果转化为了0到1之间的概率(Sigmoid函数的图像一般来说并不直观，你只需要理解对数值越大，函数越逼近1，数值越小，函数越逼近0)，接着我们根据这个概率可以做预测，例如概率大于0.5，肿瘤就是恶性的等等。 2、神经网络 神经网络(也称之为人工神经网络，ANN)算法是80年代机器学习界非常流行的算法，不过在90年代中途衰落。现在，携着“深度学习”之势，神经网络重装归来，重新成为最强大的机器学习算法之一。 神经网络的诞生起源于对大脑工作机理的研究。早期生物界学者们使用神经网络来模拟大脑。机器学习的学者们使用神经网络进行机器学习的实验，发现在视觉与语音的识别上效果都相当好。在BP算法(加速神经网络训练过程的数值算法)诞生以后，神经网络的发展进入了一个热潮。 下图是一个简单的神经网络的逻辑架构。在这个网络中，分成输入层，隐藏层，和输出层。输入层负责接收信号，隐藏层负责对数据的分解与处理，最后的结果被整合到输出层。每层中的一个圆代表一个处理单元，可以认为是模拟了一个神经元，若干个处理单元组成了一个层，若干个层再组成了一个网络，也就是”神经网络”。 图神经网络的逻辑架构 在神经网络中，每个处理单元事实上就是一个逻辑回归模型，逻辑回归模型接收上层的输入，把模型的预测结果作为输出传输到下一个层次。通过这样的过程，神经网络可以完成非常复杂的非线性分类。 进入90年代，神经网络的发展进入了一个瓶颈期。其主要原因是尽管有BP算法的加速，神经网络的训练过程仍然很困难。因此90年代后期支持向量机(SVM)算法取代了神经网络的地位。 3、SVM（支持向量机） 支持向量机算法是诞生于统计学习界，同时在机器学习界大放光彩的经典算法。 支持向量机算法从某种意义上来说是逻辑回归算法的强化：通过给予逻辑回归算法更严格的优化条件，支持向量机算法可以获得比逻辑回归更好的分类界线。但是如果没有某类函数技术，则支持向量机算法最多算是一种更好的线性分类技术。 但是，通过跟高斯“核”的结合，支持向量机可以表达出非常复杂的分类界线，从而达成很好的的分类效果。“核”事实上就是一种特殊的函数，最典型的特征就是可以将低维的空间映射到高维的空间。 上述机器学习算法均为监督学习算法。监督学习，就是人们常说的分类回归，通过已有的训练样本（即已知数据以及其对应的输出）去训练得到一个最优模型（这个模型属于某个函数的集合，最优则表示在某个评价准则下是最佳的），再利用这个模型将所有的输入映射为相应的输出。在人对事物的认识中，我们从孩子开始就被大人们教授这是猫啊、那是狗啊、那是桌子啊，等等。我们所见到的景物就是输入数据，而大人们对这些景物的判断结果（是房子还是鸟啊）就是相应的输出。当我们见识多了以后，脑子里就慢慢地得到了一些泛化的模型，这就是训练得到的那个（或者那些）函数，从而不需要大人在旁边指点的时候，我们也能分辨的出来哪些是猫，哪些是狗。无监督学习则是另一种研究的比较多的学习方法，它与监督学习的不同之处，在于我们事先没有任何训练样本，而需要直接对数据进行建模。这听起来似乎有点不可思议，但是在我们自身认识世界的过程中很多处都用到了无监督学习。比如我们去参观一个画展，我们完全对艺术一无所知，但是欣赏完多幅作品之后，我们也能把它们分成不同的派别（比如哪些更朦胧一点，哪些更写实一些，即使我们不知道什么叫做朦胧派，什么叫做写实派，但是至少我们能把他们分为两个类）。无监督学习里典型的例子就是聚类了。聚类的目的在于把相似的东西聚在一起，而我们并不关心这一类是什么。因此，一个聚类算法通常只需要知道如何计算相似度就可以开始工作了。 那么，什么时候应该采用监督学习，什么时候应该采用非监督学习呢？一种非常简单的回答就是从定义入手，如果我们在分类的过程中有训练样本，则可以考虑用监督学习的方法；如果没有训练样本，则不可能用监督学习的方法。但是事实上，我们在针对一个现实问题进行解答的过程中，即使我们没有现成的训练样本，我们也能够凭借自己的双眼，从待分类的数据中人工标注一些样本，并把他们作为训练样本，这样的话就可以把条件改善，用监督学习的方法来做。然而对于不同的场景，正负样本的分布如果会存在偏移（可能是大的偏移，也可能偏移比较小），这样的话用监督学习的效果可能就不如用非监督学习了。 今天，在计算机科学的诸多分支学科领域中，都能找到机器学习技术的身影，尤其是在计算机视觉、语音识别、模式识别、自然语言处理等“计算机应用技术”领域，机器学习已成为最重要的技术进步源泉之一。此外，机器学习还为许多交叉学科提供了重要的技术支撑比如说“生物信息学”。 可以说“计算机视觉=图像处理+机器学习“。图像处理技术用于将图像处理为适合进入机器学习模型中的输入，机器学习则负责从图像中识别出相关的模式。计算机视觉相关的应用非常的多，例如百度识图、手写字符识别、车牌识别等等应用。这个领域是应用前景非常火热的，同时也是研究的热门方向。随着机器学习的新领域深度学习的发展，大大促进了计算机图像识别的效果，因此未来计算机视觉界的发展前景不可估量。 如果说“计算机视觉=图像处理+机器学习“，那么”语音识别=语音处理+机器学习“。语音识别就是音频处理技术与机器学习的结合。语音识别技术一般不会单独使用，一般会结合自然语言处理的相关技术。目前的相关应用有苹果语音助手siri、微软小娜等。 “自然语言处理=文本处理+机器学习“。自然语言处理技术主要是让机器理解人类的语言的一门领域。在自然语言处理技术中，大量使用了编译原理相关的技术，例如词法分析，语法分析等等，除此之外，在理解这个层面，则使用了语义理解，机器学习等技术。作为唯一由人类自身创造的符号，自然语言处理一直是机器学习界不断研究的方向。按照百度机器学习专家余凯的说法“听与看，说白了就是阿猫和阿狗都会的，而只有语言才是人类独有的”。如何利用机器学习技术进行自然语言的的深度理解，一直是工业和学术界关注的焦点。 谈到对数据进行分析利用，很多人会想到“数据挖掘”（data mining）。数据挖掘领域在二十世纪九十年代形成，它受到很多学科领域的影响，其中数据库、机器学习、统计学无疑影响最大。数据挖掘是从海量数据中发掘知识，这就必然涉及对“海量数据”的管理和分析。大体来说，“数据挖掘=机器学习+数据库“——数据库领域的研究为数据挖掘提供数据管理技术，而机器学习和统计学的研究为数据挖掘提供数据分析技术。由于统计学往往醉心于理论的优美而忽视实际的效用，因此，统计学界提供的很多技术通常都要在机器学习界进一步研究，变成有效的机器学习算法之后才能再进入数据挖掘领域。从这个意义上说，统计学主要是通过机器学习来对数据挖掘发挥影响，而机器学习和数据库则是数据挖掘的两大支撑技术。从数据分析的角度来看，绝大多数数据挖掘技术都来自机器学习领域，但机器学习研究往往并不把海量数据作为处理对象，因此，数据挖掘要对算法进行改造，使得算法性能和空间占用达到实用的地步。同时，数据挖掘还有自身独特的内容，即关联分析。 通过上面的介绍，可以看出机器学习是多么的重要，应用是多么的广泛。现随着大数据（big data）概念的兴起，机器学习大量的应用都与大数据高度耦合，几乎可以认为大数据是机器学习应用的最佳场景。例如经典的Google利用大数据预测了H1N1在美国某小镇的爆发、百度预测2014年世界杯结果从淘汰赛到决赛全部正确。这实在太神奇了，那么究竟是什么原因导致大数据具有这些魔力的呢？简单来说，就是机器学习技术。正是基于机器学习技术的应用，数据才能发挥其魔力。 大数据的核心是利用数据的价值，机器学习是利用数据价值的关键技术，对于大数据而言，机器学习是不可或缺的。相反，对于机器学习而言，越多的数据会越可能提升模型的精确性，同时，复杂的机器学习算法的计算时间也迫切需要分布式计算与内存计算这样的关键技术。因此，机器学习的兴盛也离不开大数据的帮助。大数据与机器学习两者是互相促进，相依相存的关系。 机器学习与大数据紧密联系。但是，必须清醒的认识到，大数据并不等同于机器学习，同理，机器学习也不等同于大数据。大数据中包含有分布式计算、内存数据库、多维分析等等多种技术。单从分析方法来看，大数据也包含以下四种分析方法： 1.大数据，小分析：即数据仓库领域的OLAP分析思路，也就是多维分析思想。2.大数据，大分析：这个代表的就是数据挖掘与机器学习分析法。3.流式分析：这个主要指的是事件驱动架构。4.查询分析：经典代表是NoSQL数据库。 也就是说，机器学习仅仅是大数据分析中的一种而已。尽管机器学习的一些结果具有很大的魔力，在某种场合下是大数据价值最好的说明。但这并不代表机器学习是大数据下的唯一的分析方法。第四篇：斯坦福大学公开课 ：机器学习课程note1翻译
第五篇：机器学习报告
点击咨询 