分类学习笔记课件

主成分分析 Fisher线性分类器 支持向量机 基于支持向量机的目标跟踪,主要内容,PCA(principal component analysis) 主成分分析,关于PCA的基本问题 PCA数学模型 主成分的解出 PCA的计算步骤 实例,一、关于PCA的基本问题,1、什么是PCA？ PCA，即主成分分析是在保证数据信息丢失最少原则下，对高维数据进行降维处理的方法。 2、为什么要进行降维？ a、“维数灾难”问题，计算量巨大 b、维数大，处理结果不理想,3、数据降维的目的？ a、数据压缩，减少存储量 b、提取特征以便进行分类 c、去除噪声的影响,4、PCA算法基本思想？ 待处理的变量之间往往具有相关性，其基本思想是设法将原来众多的具有一定相关性的指标，重新组合成一组较少个数的互不相关的综合指标来取代原来的指标。,5、PCA的优点和缺点？,优点： a、消除了各变量之间的相关影响，减少了计算的工作量 b、主成分包含了主要的信息量，特征明显 c、此法的计算比较规范，便于在计算机上实现，还可以利用专 门的软件 缺点： a、应保证所提取的前几个主成分的累计贡献率较高 b、因为减少了数据量，所以降维后的变量不如原始变量描述的 那么确切,二、主成分分析数学模型,目的：在空间中找到一个主方向u1， u1包含了数据的大部分信息，我们将空间中的样本点投影到该向量中去，使xi投影后分散的最开。,投影表示：,这里要求u1为单位向量,为什么呢？,解释u1为单位向量：,投影到,由于有一个平方，计算起来比较麻烦，所以我们取,即u是一个单位向量,表示：,评价投影后分散程度的指标：方差 方差表示：,X投影到u1上，要求方差最大，可以写为：,表示n个样本为X=x1,x2,xn的均值：,其中,进一步推导：,其中,这里的S即为样本X的协方差矩阵。,至此，要求投影后样本分散的最开的评价转化为表达式：,下面就是求出满足此等式的u1,三、主成分求解,求解方法：利用拉格朗日方程,求解过程：,因为,列出拉格朗日方程,四、求解主成分的步骤,1、 计算协方差矩阵和其特征根 2、计算协方差矩阵特征根对应的特征向量 3、计算累积贡献率，给出恰当的主成分个数。 4、计算所选出的k个主成分的得分。将原始数据的中心化值: 代入前k个主成分的表达式，分别计算出各样本k个主成分的得分。 5、取这k个特征值对应的特征向量，得到主元。,应用举例：PCA在图像压缩的应用,基本思路： (1)将图像分块，每个块代表一个样本 (2)求块之间的协方差矩阵 (3)求的协方差矩阵的特征值和特征向量 (4)取最大的M个特征值对应的特征向量作为主元，将 图像块投影到M个单位特征向量上(M的值小于块数),Fisher线性分类器,关于Fisher的基本问题 线性分类器的数学表达式 推导过程 计算步骤,一、关于Fisher的基本问题,1、什么是Fisher？ fisher(Fisher Linear Discriminant)线性分类器，顾名思义，就是对数据进行线性分类，把不同类别的数据区分开。比如在智能交通中进行人车分类。,2、fisher基本思想？,如图所示，fisher基本思想是将n类据集尽可能地投影到一个方向（一条直线），使得类与类之间尽可能地分开。,投影原则：数据的类间距离最大，类内距离最小。,3、我们要做什么？ 找到直线的方向，使样本投影到该直线上能最容易分开。 如何找到最好的直线方向，如何实现向最好方向投影的变换，是Fisher要解决的基本问题。这个投影变换就是我们寻求的解向量 。,二、fisher算法的数学表达式,直接给出Fisher准则函数的数学表达式：,其中：,是原d维特征空间里的样本类内离散度矩阵，表示两类均,越大越容易区分。,值向量之间的离散度大小，因此，,而,称为原d维维特征空间里，样本“类内离散度”矩阵，所以,是样本的“类内总离散度”矩阵。,三、求解步骤,效果演示,人脸识别,分类,支持向量机,支持向量机简介 基本原理 优缺点 应用前景 基于支持向量机的目标跟踪,支持向量机,支持向量机SVM(Support Vector Machine)是统计机器学习的一类重要算法,它是根据统计学习理论，以结构风险最小化原则为理论基础的一种新的机器学习方法，能有效地解决高维数和非线性等问题，有效地进行分类、回归等。,线性可分：如果一个线性函数能够将样本完全正确分开，就称这些数据是线性可分的，否则成为非线性可分。 线性函数：在一维空间是一个点；二维空间是一条直线；三 维空间是一个平面，若不关注维数，这种线性函数还有一个统一的名称-超平面(Hyper Plane),SVM基本原理线性可分型,问题：找到一条直线将白点与黑点分隔开,SVM基本原理,SVM基本原理,SVM基本原理,图上的所有直线都能满足我们的要求，但是哪一个是最好的呢？,SVM基本原理,具有最大间隔的线性分类器叫做最大间隔线性分类器。 其就是一种最简单的支持向量机(SVM) (称为线性支持向量机，即LSVM),线性支持向量机,支持向量(Support Vectors) :是那些距离超平面最近的点。,量化原则：分隔的间隙越大越好，把两个类别的点分得越开越好，通常使用“分类间隔”作为指标。 在SVM中，这种最大的分隔间隙称为Maximum Marginal，是SVM的一个理论基础。,SVM基本原理,我们令黑点 = -1， 白点 = +1，直线g(x) = w x + b，这里的w、x是向量。 这种形式也等价于g(x) = w1x1 + w2x2 + wnxn + b 当向量x的维度n=2的时候，g(x) 表示二维空间中的一条直线； 当x的维度n=3的时候，g(x) 表示3维空间中的一个平面； 当x的维度n 3的时候，g(x)表示n维空间中的n-1维超平面。 当有一个新的点x需要预测属于哪个分类的时候， 我们用sgn(g(x)，就可以预测了 这里sgn表示符号函数 当g(x) 0时，sgn(g(x) = +1 当g(x) < 0时，sgn(g(x) = 1,SVM基本原理,最优分类超平面,分类超平面： 判决函数： 定义某个样本点到超平面的间隔： 几何间隔： 最大间隔问题： 通常做法为固定间隔为1， 寻求最小的 。,几何间隔：如图，H是分类面，H1和H2平行于H，且过离H最近的两类样本的直线，H1与H之间的距离，H2与H之间的距离为几何间隔。,SVM基本原理,优化问题： s.t.意为subject to，即在后面这个限制条件下的意思，这个词在svm的论文里面出现的频率很高。 这其实是一个带约束的二次规划(quadratic programming, QP)问题，是一个凸问题。 凸问题指的不会有局部最优解，可以想象一个漏斗，不管我们开始的时候将一个小球放在漏斗的什么位置，这个小球最终一定可以掉出漏斗，也就是得到全局最优解。s.t.后面的限制条件可以看做是一个凸多面体，我们要做的就是在这个凸多面体中找到最优解。,SVM基本原理,原问题最优解： 决策函数：,问题求解：（Lagrange乘子法）得出对偶问题：,SVM基本原理,SVM基本原理线性不可分型,引子：世界上本来没有两个完全一样的物体，对于所有的两个物体，我们可以通过增加维度来让他们最终有所区别，比如说两本书，从(颜色，内容)两个维度来说，可能是一样的，我们可以加上作者这个维度，实在不行我们还可以加入页码，可以加入拥有者，可以加入购买地点，可以加入笔记内容等等来使它们变得不同。,所以，当线性不可分时，我们可以让空间从原本的线性空间变成一个更高维的空间，在这个高维的线性空间下，再用一个超平面进行划分。当维度增加到无限维的时候，一定可以让任意的两个物体可分了。,举一个简单的例子 二维平面中分类曲线为椭圆（线性不可分）,SVM基本原理,两维向三维的映射： 三维空间中线性可分 分类面： 根据支持向量机求得决策函数为：,SVM基本原理,的内积计算： 令 ，称为核函数 高维空间中内积计算可以通过计算低维空间的内积得 到，核函数就是连接低维与高维之间的桥梁。,SVM基本原理,高维空间中支持向量机得出的决策函数可改写成： 因此得出一般的情形： 对于线性不可分的样本，作一个低维到高维的映射，使之在高维的空间中线性可分，在高维空间中采用最大间隔标准得出决策函数，由于巧妙的选取核函数，决策函数中在计算内积时只需换成核函数即可。 优点：由于核函数的特性，只需计算低维空间内积，而无需计算高维空间的内积，因此计算量与样本维数无关，只与样本数有关。,SVM基本原理,常用核函数： 多项式核： 径向基核： Sigmoid核：,SVM基本原理,投到高维空间仍不可分怎么办？,考虑将这些离群的点作为噪声，把这些噪声造成的损失加入到目标函数里。需要一个惩罚因子C，（cost，又叫松弛变量）原来的优化问题就变成了：,说明：1、并非所有的样本点都有一个松弛变量与其相对应，事实上，只有“离群点”才有，或者说没离群的点松弛变量等于0。 2、惩罚因子C决定了你有多重视离群点带来的损失，C越大，对目标函数的损失也越大，此时就暗示着你非常不愿意放弃这些离群点。 3、惩罚因子C不是一个变量，是一个必须事先指定的值。 4、尽管加了松弛变量，整个问题仍是一个优化问题。,有坚实的理论基础; 基于结构风险最小化，克服了传统方法的过学习的问题，具有很强的泛化能力； 采用核函数方法，向高维空间映射时不增加计算的复杂性，又克服了维数灾难。,支持向量机的优点,样本数目增多时，训练速度变慢； SVM解决的是两分类问题，因此需要多分类问题的改进； 核函数的选择：没有统一的指导标准。,支持向量机的缺点,支持向量机的应用,近年来SVM 方法已经在图像识别、信号处理和基因图谱识别等方面得到了成功的应用,显示了它的优势。 SVM 通过核函数实现到高维空间的非线性映射,所以适合于解决本质上非线性的分类、回归和密度函数估计等问题。 支持向量方法也为样本分析、因子筛选、信息压缩、知识挖掘和数据修复等提供了新工具。,基于支持向量机的目标跟踪,基于支持向量机的目标跟踪,基于特征的目标跟踪主要包括特征提取和特征匹配两个方面： （1）特征提取 特征提取是指从景物的原始图像中提取图像的描绘特征 ，理想的图像特征应具备的特点是 ： a ) 特征应具有直观意义，符合人们的视觉特性； b ) 特征应具备较好的分类能力，能够区分不同的图像内容； e ) 特征计算应该相对简单，以便于快速识别； d ) 特征应具备图像平移、旋转、尺度变化等不变性。 目标跟踪中常用的运动目标的特征主要包括颜色、纹 理、边缘、块特征、光流特征、周长、面积、质心、角点等。提取对尺度伸缩、形变和亮度变化不敏感的有效特征至今仍是图像处理研究领域中一个比较活跃的方面。,( 2 ) 特征匹配 特征提取的目的是进行帧间目标特征的匹配，并以最优匹配来跟踪目标。常见的基于特征匹配的跟踪算法有基于二值化目标图像匹配的跟踪、基于边缘特征匹配或角点特征匹配的跟踪、基于目标灰度特征匹配的跟踪、基于目标颜色特征匹配的跟踪等 。 优点： a) 在于对运动目标的尺度、形变和亮度等变化不敏感，即使目标的某一部分被遮挡，只要还有一部分特征可以被看到，就可以完成跟踪任务； b)这种方法与