视频监控与视频分析-第九章 分类算法解析.ppt

* * * * * * * * * * ③K-Means分类算法 * KNN,K最近邻算法 右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。 K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。 KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。 ④朴素贝叶斯定理 * A AB B P(A|B)=P(AB)/P(B) P(AB)=P(A|B)P(B) =P(B|A)P(A) P(A|B)=P(AB)/P(B) =P(A)P(B|A)/P(B) 贝叶斯公式 先验概率P(cj) P( cj|x) = P(x|cj)P(cj) P(x) 联合概率P(x|cj) 后验概率P(cj|x) * 贝叶斯决策 朴素贝叶斯分类器一 设x = a1,a2…am，为一个有m个属性的样例 = max P(a1,a2…am|cj)P(cj) P(a1,a2…am) = max P(a1,a2…am|cj)P(cj) (1) P(cMAP|x)= max P(cj|x) j∈(1,|C|) = max P(cj|a1,a2…am) 朴素贝叶斯分类器基于一个简单的假定：在给定目标值时属性值之间相互条件独立。换言之，该假定说明给定实例的目标值情况下，观察到联合的a1,a2…am的概率正好是对每个单独属性的概率乘积 朴素贝叶斯分类器二 (2) 将(2) 式其代入(1)式中，可得到朴素贝叶斯分类器，如下 朴素贝叶斯分类器三 概括地讲，朴素贝叶斯学习方法需要估计不同的P(cj)和P(ai|cj)项，也就是它们在训练数据上的频率。然后使用公式(3)来分类新实例。 CNB=argmax P(cj) （3） 其中CNB表示朴素贝叶斯分类器输出的目标值。注意在朴素贝叶斯分类器中，须从训练数据中估计的不同P(ai|cj)项的数量只是不同的属性值数量乘以不同目标值数量——这比要估计P(a1,a2…am|cj)项所需的量小得多 * 美联储主席本.伯南克昨天告诉媒体7000亿美金的救助资金将借给上百家银行、保险公司和汽车公司 贝叶斯估计在语言中的应用 本.伯南克美联储主席昨天7000亿美金的救助资金告诉媒体将借给上百家银行、保险公司和汽车公司 联主美储席本.伯南克诉体将借天的昨70救助资金00亿美金告银行、保险媒给上百家公司和汽车公司 第一个句子概率：10-20，第二个10-25，第三个10-70 在字符识别 字符输入 有广泛的应用 ⑤EM最大期望算法 * ⑥线性区分（Linear Discriminate) * * Sw Sb: within class matrix and between class matrix * 隐藏变量和混合高斯模型 将z引入后 最终得到 再看简化的问题 前面说过，在简化问题中我们观察到的是{X,Z}，因此根据以下两个式子 可以得到 其中znk表示xn属于第k个高斯分布 两个问题的比较 简化问题的计算1 简化问题的计算2 计算单一高斯分布的参数 多变量正态分布 简化问题参数结果 实际问题 至此我们已经解决了简化问题的参数求解。但是，实际上我们往往不知道znk，即Z往往是隐藏变量，怎么也能运用前面简化问题的算法 虽然不知道znk，但是我们可以用它的期望E[znk]去估计znk Znk的期望估计 是p(zk=1)的先验 是观察到样本之后的后验 简化问题——实际问题 EM for Gaussian Mixtures 1.初始化均值uk,协方差∑k和混合系数πk 2.E step (计算znk的期望值) 3.M step (重新计算参数值) EM for Gaussian Mixtures 4.测试是否达到停止条件，如果停止条件不满足返回到第2步 例子 Logistic Regression Classification Machine Learning * Binary Classification Email: Spam / Not Spam? Online Transac