第4节 统计分类.pptx

统计分类 电子科技大学师君 统计分类分类器训练统计聚类K近邻分类 认知问题观测过程存在不确定性 测量误差 噪声 模式识别的统计模型 似然函数 likelihoodfunction 已知某事件发生 不同测量值出现的 可能性 后验概率 PosterioriProbability 已知观测值的条件下 事件发生的概率 模式识别的统计模型 已知特征向量 样本属于某一类的概率 后验概率 PosterioriProbability 错误概率 将A类样本划分到非A类的概率 分类方法与评估手段 模式识别的统计模型 统计分类策略 当某个观测结果已知时 认为 后验概率最大的事件发生 最大后验概率分类 条件概率公式 A发生且B发生 联合概率在B发生条件下 A发生的概率条件概率与联合概率的关系 贝叶斯定理 贝叶斯公式 似然函数与后验概率的关系 条件概率 联合概率 事件概率贝叶斯推理 已知似然函数和事件发生概率 当某观测发生时 对事件出现的概率推断 多观测推理 贝叶斯定理 例 已知1000人中有1人得病 进行测试 如果有病 则该测试结果为阳性的概率为0 99 无病 测试结果为阳性的概率为0 02 某人测试结果为阳性 问其得病概率为多少 贝叶斯定理 例 如果得病人数未知 假设概率相同 则有 贝叶斯定理 贝叶斯分类 等价于 贝叶斯分类 二元分类 差法 比法似然函数比 阀值 贝叶斯分类 最大后验概率分类是最小误差分类 几何解释 贝叶斯分类 引理1 证明 贝叶斯分类 引理2 证明 贝叶斯分类 二元分类器 引理1的直接结论 多元分类器 错误概率 1 正确概率 结合利用引理2 得证 贝叶斯分类 似然函数是高斯函数 贝叶斯分类器 正态分布下 贝叶斯分类属于二次分类器 正态分布贝叶斯分类 二元分类 正态分布贝叶斯分类 几何意义 贝叶斯分类 closeallclearallclcN 200 u1 0 8 0 6 u2 0 8 0 6 Cov1 0 3 0 8 0 2 0 2 8 Cov1 0 3 1 0 0 1 Cov2 0 6 1 0 0 1 Cov2 Cov1 P1 0 5 P2 1 P1 nn 1 N C 4 xx nn N 2 N C foriii 1 Nforjjj 1 Nx 1 iii N 2 N C x 2 jjj N 2 N C f1 iii jjj 1 sqrt 2 pi sqrt det Cov1 exp 1 2 x u1 inv Cov1 x u1 f2 iii jjj 1 sqrt 2 pi sqrt det Cov2 exp 1 2 x u2 inv Cov2 x u2 endendfigure mesh f1 figure mesh f2 foriii 1 Nforjjj 1 N a b max f1 iii jjj f2 iii jjj yy iii jjj a mask iii jjj b 1 endendfigure imagesc mask foriii 1 N a b max abs diff mask iii border iii 1 C iii N 2 N border iii 2 C b N 2 N endfigure contour xx xx yy 40 linewidth 2 colormap jet holdonplot border 2 border 1 r markersize 15 linewidth 3 线性分类 如果两类样本的相关矩阵相等 则有 是n维空间中的平面 正态分布贝叶斯分类 线性分类 如果相关矩阵为对角阵 则分类面与样本中心垂直 否则 不垂直 正态分布贝叶斯分类 最小代价分类 将样本 k错分为 i的代价 总代价 利用引理1 可得最优分类为 其他分类策略 二元最小代价分类 比法 其他分类策略 Neyman Pearson准则 限定一类错误率条件下 使另一类错误率为最小 即 假设各类先验信息相同 利用拉格朗日乘数法 可得 其他分类策略 等价转化为 判决函数为 其他分类策略 的计算 根据拉格朗日乘数法 有 即 选择 使得分界面满足固定概率约束 对于一维情况 则可先计算分界点t 再计算 其他分类策略 最小最大损失决策 给定先验概率利用最小代价分类如果先验概率未知 则得到与代价的函数 设计分类器 使得对于所有代价函数最小 其他分类策略 最小最大损失决策过程 选择不同 计算损失 选择最大损失 记作 则最小最大损失分类器为 其他分类策略 统计分类分类器训练统计聚类K近邻分类 统计分类需要各类的先验概率和其对应的似然函数和 先验概率 根据实际情况 或假设相等 似然函数 如果已知 则直接写出判决函数 如果未知 则需要从样本中估计似然函数 估计似然函数似然函数类型已知 参数估计似然函数类型未知 非参数化估计 分类器训练 参数估计 信号检测与估计 最大似然估计 ML 各样本相互独立 则 最大后验概率 MAP 与ML相比 MAP需要另外给定参数的概率密度函数 分类器训练 参数估计 信号检测与估计 最大熵估计 略 混合模型估计 假设样本分布函数为一组基函数 kernelfunction 的线性组合 估计线性系数 wi 解法 建立ML MAP模型 求解最优化问题 略 分类器训练 非参数化估计 有时分布函数没有解析表达式 无法参数化 此时 需要采用非参数化的估计 直方图估计 hist 统计样本出现的频率 利用频率分布逼近概率密度分布 当步长趋近于0 样本趋近于无穷时 频率逼近于概率密度分布 分类器训练 直方图 直方图函数 分类器训练 直方图估计 分类器训练 closeallclearallclcN 1000 C 10nn 1 N xx C nn N N y zeros N Nsam 500 samp randn 2 Nsam foriii 1 Nforjjj 1 Nx 1 C iii N 2 N x 2 C jjj N 2 N forkkk 1 Nsamif abs x 1 samp 1 kkk 0 5imagesc xx xx y N 1 N 50 N 500 N 2000 Parzen窗估计 矩形函数不具有连续性 因此利用一组连续函数估计概率密度函数 称为核函数 势函数 Parzen窗 一般选择独立同分布高斯函数作为核函数 分类器训练 Parzen窗估计 分类器训练 closeallclearallclcN 200 C 10nn 1 N xx C nn N N y zeros N Nsam 200 samp randn 2 Nsam foriii 1 Niiiforjjj 1 Nx 1 C iii N 2 N x 2 C jjj N 2 N forkkk 1 Nsamy iii jjj y iii jjj exp 0 5 norm x samp kkk 2 endendendfigure mesh xx xx y figure imagesc xx xx y N 200 N 10 N 1 高维空间的样本问题 朴素贝叶斯 Na veBayes 为了保证对样本空间的均匀采样 样本数按维数的增加幂级增长 如果采用各变量独立假设 则样本数按维数的增加线性增长 此假设称为朴素贝叶斯 分类器训练 采用高斯核函数 则似然函数 判决函数 分类器实现 贝叶斯分类算法伪码 初始化训练样本和测试样本 For 所有测试样本 for A类训练样本 计算样本概率PA Endfor B类训练样本 计算样本概率PB endif PA PB 将该样本放入A类结果中 Else将该样本放入B类结果中 EndEND显示 评估分类结果 分类器实现 分类结果 分类器实现 closeallclearallclcObj1 NTrain 100 Obj1 mean 0 3 3 5 Obj1 SampTrain randn 2 Obj1 NTrain kron Obj1 mean ones 1 Obj1 NTrain Obj1 NTest 100 Obj1 SampTest randn 2 Obj1 NTest kron Obj1 mean ones 1 Obj1 NTest Obj2 NTrain 100 Obj2 mean 0 3 3 5 Obj2 SampTrain randn 2 Obj2 NTrain kron Obj2 mean ones 1 Obj2 NTrain Obj2 NTest 100 Obj2 SampTest randn 2 Obj2 NTest kron Obj2 mean ones 1 Obj2 NTest EvaluationTestMatrix zeros 2 cnt c1 1 cnt c2 1 foriii 1 Obj1 NTesty1 0 y2 0 forkkk 1 Obj1 NTrainy1 y1 exp 0 5 norm Obj1 SampTest iii Obj1 SampTrain kkk 2 endforkkk 1 Obj2 NTrainy2 y2 exp 0 5 norm Obj1 SampTest iii Obj2 SampTrain kkk 2 endif y1 y2 Result c1 cnt c1 Obj1 SampTest iii cnt c1 cnt c1 1 TestMatrix 1 1 TestMatrix 1 1 1 elseResult c2 cnt c2 Obj1 SampTest iii cnt c2 cnt c2 1 TestMatrix 1 2 TestMatrix 1 2 1 endendforiii 1 Obj2 NTesty1 0 y2 0 forkkk 1 Obj1 NTrainy1 y1 exp 0 5 norm Obj2 SampTest iii Obj1 SampTrain kkk 2 endforkkk 1 Obj2 NTrainy2 y2 exp 0 5 norm Obj2 SampTest iii Obj2 SampTrain kkk 2 endif y1 y2 Result c1 cnt c1 Obj2 SampTest iii cnt c1 cnt c1 1 TestMatrix 2 1 TestMatrix 2 1 1 elseResult c2 cnt c2 Obj2 SampTest iii cnt c2 cnt c2 1 TestMatrix 2 2 TestMatrix 2 2 1 endendTestMatrix 1 TestMatrix 1 Obj1 NTest TestMatrix 2 TestMatrix 2 Obj2 NTest TestMatrixfigure plot Result c1 1 Result c1 2 ro linewidth 2 markersize 10 holdonplot Result c2 1 Result c2 2 bo linewidth 2 markersize 10 plot Obj1 SampTrain 1 Obj1 SampTrain 2 r linewidth 2 markersize 10 plot Obj2 SampTrain 1 Obj2 SampTrain 2 b linewidth 2 markersize 10 复杂样本分类 Parzen窗贝叶斯分类可构造复杂分类曲面 分类器实现 复杂样本分类 分类器实现 复杂样本分类 分类器实现 代码 分类器实现 closeallclearallclcObj1 mean 0 0 Obj1 NTrain 200 cnt1 1 foriii 1 1000 Obj1 NTrain tmp rand 2 1 0 5 10 Obj1 mean if norm tmp Obj1 mean 0 8contour xx xx yy 40 linewidth 2 colormap jet holdonplot border 1 border 2 r markersize 15 linewidth 3 贝叶斯分类应用实例 统计分类分类器训练统计聚类K近邻分类 模型 已知概率密度函数和样本序列xi 则样本序列出现的可能性为 取对数 求 使得似然函数最大 期望最大算法 例子 已知事件包含四种情况 a b c d 概率密度函数 统计197个样本 a出现125次 b出现18次 c出现20次 d出现34次 求 期望最大算法 例子 期望最大算法 symsxy 125 1 x x 38 x 2 x 34 2 x 1 x solve y double ans 例子 已知事件包含五种情况 a b c d e 概率密度函数 统计197个样本 a b出现125次 c出现18次 d出现20次 e出现34次 求 方法一 令x1 a b x2 c x3 d x4 e 构造概率密度函数 计算 0 6268 期望最大算法 方法二 EM算法 给定初始 0 得到P a 0 5 P b 0 估计样本a 125 b 0 计算 利用新计算 重新估计a b 迭代计算 得到对 的估计 计算得到 0 6268 期望最大算法 clearallcloseallclcab 125 c 18d 20e 34x 0 foriii 1 10a ab 0 5 0 5 0 25 x b ab a x b e b c d e end 已知y 求E x y 离散情况 连续情况 期望最大算法 基本步骤 1 求完全变量X条件期望 2 代入似然函数 3 求似然函数最大值 期望最大算法 标准步骤 E step 计算Q函数M step 令Q函数等于0 更新 的估计 其中 期望最大算法 收敛性讨论1 迭代过程似然函数单调增加 2 似然函数有界3 迭代序列收敛到局部最大值 4 如果分布函数为高斯函数 为凸优化 收敛到全局最大值 期望最大算法 问题 为多类混合样本x添加类标号 扩展为更高维随机变量 估计分布参数 属于非完备样本参数估计 采用EM算法 混合分解聚类 例 假设服从高斯分布 混合分解聚类 求偏导得到 其中 混合分解聚类 混合分解聚类 clearallcloseallclcK 2 N 300 P1 0 3 P2 0 7 u1 0 0 u2 3 4 b1 0 3 b2 1 Data 1 round N P1 randn 2 round N P1 b1 kron u1 ones 1 round N P1 Data round N P1 1 N randn 2 round N P2 b2 kron u2 ones 1 round N P2 figure plot Data 1 Data 2 ro PP 1 0 5 PP 2 0 5 uu 1 0 0 uu 2 5 5 bb 1 1 bb 2 3 foriii 1 20PPP zeros 1 2 uuu zeros 2 2 bbb zeros 1 2 forjjj 1 Nforkkk 1 KPxx jjj kkk 1 sqrt 2 pi bb kkk exp 1 norm Data jjj uu kkk 2 2 bb kkk bb kkk PP kkk endPxx jjj Pxx jjj sum Pxx jjj eps endforjjj 1 NPPP PPP Pxx jjj endforjjj 1 Nforkkk 1 Kuuu kkk uuu kkk Pxx jjj kkk Data jjj PPP kkk endendforjjj 1 Nforkkk 1 Kbbb kkk bbb kkk Pxx jjj kkk norm Data jjj uuu kkk 2 PPP kkk 2 endendPP PPP N uu uuu bb sqrt bbb endPPuubbxxx zeros 2 1 forxx 1 100foryy 1 100 xxx 1 xx 50 5 xxx 2 yy 50 5 z1 xx yy 1 sqrt 2 pi bb 1 exp 1 norm xxx uu 1 2 2 bb 1 bb 1 z2 xx yy 1 sqrt 2 pi bb 2 exp 1 norm xxx uu 2 2 2 bb 2 bb 2 endendholdon nn 1 100 ttt nn 50 5 contour ttt ttt z1 5 linewidth 2 contour ttt ttt z2 5 linewidth 2 统计分类分类器训练统计聚类K近邻分类 思路 对某些似然函数 待分类点到训练样本的距离越近 对应的似然函数值越大 该点越有可能位于此类 因此 可以直接以 距离 作为评判标准设计分类器 如何衡量向量的 远 近 需要引入 距离 的概念 最邻近分类 距离 度量 的公理化定义 距离的构造 利用范数构造距离 但是 距离不需要满足范数的 齐次性 可以构造其他的距离 距离 欧氏距离 Manhattan距离 契比雪夫距离 明氏 Minkowski 距离 Mahalanobis距离 Camberra Lance Willims距离 无量纲 根据所处理问题的实际情况 选择合适的距离 常用距离 正态分布贝叶斯分类 对于高斯分布 且发生概率相同 各类协方差矩阵相同 则判决函数等价于 定义mahalanobis距离 马氏距离 如果协方差矩阵为单位阵 则马氏距离等于欧式距离 明显 距离某训练样本距离越近 对应似然函数越大 所以 距离远近可作为分类标准 前提 似然函数 类高斯 最小距离分类 例 不用计算指数 降低了运算量 最小距离分类 k最邻近分类 kNN 计算待分类点到所有训练样本的距离 选出距离最短的k个训练样本统计k个样本所在的类 将待分类点分配给包含k个训练样本中数目最多的类 k最邻近分类 KNN分类算法伪码 初始化训练样本和测试样本 For 所有测试样本 for A类训练样本 计算测试样本到A训练样本的距离 Endfor B类训练样本 计算测试样本到B训练样本的距离 End距离排序 选择最近k个距离 统计所属集合数目if NA NB 将该样本放入A类结果中 Else将该样本放入B类结果中 EndEND显示 评估分类结果 k最邻近分类 k最邻近分类 决策面 closeallclearallclcObj1 mean 1 0 3 5 Obj2 mean 1 3 5 Obj3 mean 1 3 5 Obj4 mean 1 3 5 K NNInv 7 K 2 Im zeros 300 foriii 1 300forjjj 1 300 xx iii 150 150 Inv yy jjj 150 150 Inv d 1 norm Obj1 mean xx yy K d 2 norm Obj2 mean xx yy K d 3 norm Obj3 mean xx yy K d 4 norm Obj4 mean xx yy K a b min d Im iii jjj b endendxxx 1 300 xxx xxx 150 150 Inv imagesc xxx xxx Im holdonplot Obj1 mean 2 Obj1 mean 1 ro linewidth 3 markersize 15 plot Obj2 mean 2 Obj2 mean 1 ro linewidth 3 markersize 15 plot Obj3 mean 2 Obj3 mean 1 ro linewidth 3 markersize 15 plot Obj4 mean 2 Obj4 mean 1 ro linewidth 3 markersize 15 k 1Voronoi纹理 代码 k最邻近分类 closeallclearallclcObj1 NTrain 100 Obj1 mean 0 2 3 5 Obj1 SampTrain randn 2 Obj1 NTrain kron Obj1 mean ones 1 Obj1 NTrain Obj1 NTest 100 Obj1 SampTest randn 2 Obj1 NTest kron Obj1 mean ones 1 Obj1 NTest Obj2 NTrain 100 Obj2 mean 0 2 3 5 Obj2 SampTrain randn 2 Obj2 NTrain kron Obj2 mean ones 1 Obj2 NTrain Obj2 NTest 100 Obj2 SampTest randn 2 Obj2 NTest kron Obj2 mean ones 1 Obj2 NTest K NNTestMatrix zeros 2 K 11 cnt c1 1 cnt c2 1 NORM ORDER 2 foriii 1 Obj1 NTestcnt dist 1 forkkk 1 Obj1 NTrainDist cnt dist 1 norm Obj1 SampTest iii Obj1 SampTrain kkk NORM ORDER Dist cnt dist 2 1 cnt dist cnt dist 1 endforkkk 1 Obj2 NTrainDist cnt dist 1 norm Obj1 SampTest iii Obj2 SampTrain kkk NORM ORDER Dist cnt dist 2 1 cnt dist cnt dist 1 end a ID sort Dist 1 SortID Dist ID 2 if sum SortID 1 K 0 Result c1 cnt c1 Obj1 SampTest iii cnt c1 cnt c1 1 TestMatrix 1 1 TestMatrix 1 1 1 elseResult c2 cnt c1 Obj1 SampTest iii cnt c2 cnt c2 1 TestMatrix 1 2 TestMatrix 1 2 1 endendforiii 1 Obj2 NTestcnt dist 1 forkkk 1 Obj1 NTrainDist cnt dist 1 norm Obj2 SampTest iii Obj1 SampTrain kkk NORM ORDER Dist cnt dist 2 1 cnt dist cnt dist 1 endforkkk 1 Obj2 NTrainDist cnt dist 1 norm Obj2 SampTest iii Obj2 SampTrain kkk NORM ORDER Dist cnt dist 2 1 cnt dist cnt dist 1 end a ID sort Dist 1 SortID Dist ID 2 if sum SortID 1 K 0 Result c1 cnt c1 Obj2 SampTest iii cnt c1 cnt c1 1 TestMatrix 2 1 TestMatrix 2 1 1 elseResult c2 cnt c1 Obj2 SampTest iii cnt c2 cnt c2 1 TestMatrix 2 2 TestMatrix 2 2 1 endendTestMatrix 1 TestMatrix 1 Obj1 NTest TestMatrix 2 TestMatrix 2 Obj2 NTest TestMatrixfig