随机模式的分类方法.ppt

随机模式的分类方法 第2章 该方法基于贝叶斯决策理论 往往以某种概率的形式给出 本章首先介绍贝叶斯分类方法中的一般性的判决规则 并且抽象出随机模式的判决函数和决策面方程 给出2种分类器结构 MadeinCV PRLabofShandongUniversity 目录 2 1引言 1 2 2最小错误率判决规则 最简单的Bayes分类方法 2 2 3最小风险判决规则 3 2 4最大似然比判决规则 4 2 5Neyman Pearsen判决规则 有时不知道先验概率 仅知道类概率密度 5 2 6最小最大判决规则 先验概率是变化的 6 2 7分类器设计 6 MadeinCV PRLabofShandongUniversity 2 1引言 随机模式在可以觉察到的客观世界中 存在着大量的物体和事件 他们在基本条件不变时 具有某种不确定性 每一次观测的结果没有重复性 这种模式就是随机模式 虽然随机模式样本测量值具有不确定性 但同类抽样实验的大量样本的观测值具有某种统计特性 这个统计特性是建立各种分类方法的基本依据 先看一下确定性模式判决函数的问题 MadeinCV PRLabofShandongUniversity 2 1引言 通过判决函数 特征空间被区分界面划分成两种类型的区域A和B 由于模式样本的观测值是确定性的 经常被正确分配到类型区域A B之中 假如我们用概率的形式来表达 就是 在类型A的条件下观测模式样本x 则x位于区域A的概率为1 而位于区域B的概率为0 同样 在类型B的条件下观测模式样本x 情况正好相反 x位于区域A的概率为0 而位于区域B的概率为1 这实际上是将概率的方法引入到确定模式 对于大多数实际情况 这是非常理想的概率分布 MadeinCV PRLabofShandongUniversity 许多实际情况 即使在类型A的条件下 模式样本x位于区域A的概率也往往小于1 而位于区域B的概率也不为0 对于类型B的条件也一样 这种交错分布的样本使分类发生错误 是模式随机性的一种表现 此时 分类方法就从确定性模式转到随机模式 如何使分类错误率尽可能小 是研究各种分类方法的中心议题 2 1引言 MadeinCV PRLabofShandongUniversity Bayes决策理论是随机模式分类方法最重要的基础 其中几个重要的概念 先验概率先验概率是预先已知的或者可以估计的模式识别系统位于某种类型的概率 类 条件 概率密度它是系统位于某种类型条件下 模式样本x出现的概率密度分布函数后验概率后验概率可以根据贝叶斯公式计算出来 可直接用作分类判决的依据 2 1引言 MadeinCV PRLabofShandongUniversity 先验概率先验概率是预先已知的或者可以估计的模式识别系统位于某种类型的概率 若仍然用两个类型A和B为例 可用和表示各自的先验概率 此时满足 推广到一般的c类问题中 用表示类型 则各自的先验概率用表示 且满足 其实 在处理实际问题时 有时不得不以先验概率的大小作为判决的依据 如 有一批木材 其中桦木占70 松木占30 A 桦木 B 松木 则 如果从中任取一块木材 而又要用先验概率作出判决 那就判为桦木 先验概率不能作为判决的唯一依据 但当先验概率相当大时 它也能成为主要因素 2 1引言 MadeinCV PRLabofShandongUniversity 2 1引言 2 类 条件 概率密度它是系统位于某种类型条件下 模式样本x出现的概率密度分布函数 常用 以及来表示 先验概率密度在分类方法中起至关重要的作用 它的函数形式及主要参数或者是已知的 或者是可通过大量抽样实验估计出来 3 后验概率它是系统在某个具体的模式样本x条件下 位于某种类型的概率 常以 以及表示 后验概率可以根据贝叶斯公式计算出来 可直接用作分类判决的依据 例如 一个2类问题 w1表示诊断为无癌症 w2诊断为有癌症 P w1 表示诊断正常的概率 P w2 表示某地区的人被诊断出患上癌症的概率 该值可以通过大量的统计得到 x表示 试验反应呈阳性 那么 P x w1 表示诊断为无癌症且试验反应为阳性 P w1 x 表示试验为阳性 而且没有癌症 同样 可以有w2的类概率密度和后验概率 MadeinCV PRLabofShandongUniversity 2 2最小错误率判决规则 最简单的Bayes分类方法 分析一个 两类问题 以上一个例子为例 用w1和w2表示两种不同的类型 如w1表示诊断正常 w2表示诊断出患有癌症 用和分别表示先验概率 如 诊断正常的概率 表示某地人患癌症的概率 可通过大量的统计得到 用和表示两个类概率密度 样本x表示 试验反应阳性 则诊断为无癌症且试验反应为阳性 试验为阳性且没有癌症 根据全概率公式 模式样本x出现的全概率密度为 2 2 1 根据Bayes公式 在模式样本x出现的条件下 两个类型的后验概率为 2 2 2 MadeinCV PRLabofShandongUniversity 此时 样本归属于 后验概率较高 的那种类型 也就是 则偶然决定 或 2 2 3 则 则 根据 2 2 2 式 上述判决规则等价于 则 则 2 2 4 则偶然决定 或 上面只是给出了最小错误率贝叶斯决策规则 但没有证明按这种规则进行分类确实使错误率最小 2 2最小错误率判决规则 MadeinCV PRLabofShandongUniversity 下面用一维情况来证明最小错误率贝叶斯决策规则 其结果不难推广到多维 如下图所示 在一维特征空间里 判决门限t把空间划分为两个类型区域R1 R2 在R1中 则 在R2中 则 阴影区域是两类样本的交错分配区域 阴影面积就是这种分类方法的错误概率 2 2最小错误率判决规则 MadeinCV PRLabofShandongUniversity 总错误率有两种情况 而判为 斜线区域 而判为 所以 总错误率 纹线区域 其中 表示在整个d维特征空间上的积分 对上述两类问题 当 时 则 显然作出决策w2时 x的条件错误概率为 反之为 也就是 2 2最小错误率判决规则 MadeinCV PRLabofShandongUniversity 若令t为两类分界面 特征向量x为一维时 t为x轴上的一个点 如上图所示 也可写为 2 2最小错误率判决规则 MadeinCV PRLabofShandongUniversity 所以要使最小 判决门限应如上图所示 否则就会有多余的阴影面 而 2 2 3 2 2 4 表达的判决规则 判决门限正好如上图所示 所以称之为 最小错误概率判决规则 2 2最小错误率判决规则 MadeinCV PRLabofShandongUniversity 可以把上述两类问题导出的最小错误率判决规则一般化 推广到c类问题中 表达为 若 则 等价于 则 2 2最小错误率判决规则 例1 为了对癌症进行诊断 对一批人进行一次普查 各每个人打试验针 观察反应 然后进行统计 规律如下 这一批人中 每1000个人中有5个癌症病人 这一批人中 每100个正常人中有一个试验呈阳性反应 这一批人中 每100个癌症病人中有95人试验呈阳性反应 问 若某人 甲 呈阳性反应 甲是否正常 MadeinCV PRLabofShandongUniversity 2 2最小错误率判决规则 解 假定x表示实验反应为阳性 1 人分为两类 w1 正常人 w2 癌症患者 2 由已知条件计算概率值 先验概率 类条件概率密度 3 决策过程 由最小错误判决规则 可知 由于比大很多 所以先验概率起了较大作用 MadeinCV PRLabofShandongUniversity 2 3最小风险判决规则 最小风险判决规则也是一种Bayes分类方法 最小错误率判决规则没有考虑错误判决带来的 风险 或者说没有考虑某种判决带来的损失 同一问题中 某种判决总会有一定的损失 特别是错误判决有风险 不同的错误判决有不同的风险 如上一节的例子中 判断细胞是否为癌细胞 可能有两种错误判决 正常细胞错判为癌细胞 癌细胞错判为正常细胞 两种错误带来的风险不同 在 中 会给健康人带来不必要的精神负担 在 中 会使患者失去进一步检查 治疗的机会 造成严重后果 显然 第 种错误判决的风险大于第 种 判决风险也可以理解为判决损失 即使在正确判决的情况下 一般也会付出某种代价 也会有损失 正是由于有判决风险的存在 最小错误率判决就不够了 必须引入最小风险判决规则 MadeinCV PRLabofShandongUniversity 假定有c类问题 用 表示类型 用 表示可能作出的判决 实际应用中 判决数a和类型数c可能相等 也可能不等 即允许除c类的c个决策之外 可以采用其它决策 如 拒绝 决策 此时 对于给定的模式样本x 令 表示 而判决为 的风险 若判决 一定 对c个不同类型的 有c个不同的 2 3最小风险判决规则 MadeinCV PRLabofShandongUniversity 维风险矩阵 的c个离散值随类型的性质变化 具有很大的随机性 可看成是随机变量 另外 由于判决数目有a个 这样对于不同的判决和不同类型就有一个 一般风险矩阵 2 3最小风险判决规则 MadeinCV PRLabofShandongUniversity 假定某样本x的后验概率 已经确定 则有 对于每一种判决 可求出随机变量 的条件平均风险 也叫 条件平均损失 2 3 1 最小风险判决规则就是把样本x归属于 条件平均风险最小 的那一种判决 也就是 若 则 2 3 2 2 3最小风险判决规则 MadeinCV PRLabofShandongUniversity 实施最小风险判决规则的步骤如下 1 在给定样本x条件下 计算各类后验概率 2 按照 2 3 1 式求各种判决的条件平均风险 为此 需要知道风险矩阵 按照 2 3 2 式 比较各种判决的条件平均风险 把样本x归属于条件平均风险最小的那一种判决 2 3最小风险判决规则 MadeinCV PRLabofShandongUniversity 2 3最小风险判决规则 和 解 从风险矩阵中得到 将例1中计算出的后验概率 代入2 3 1式 根据最小风险判决规则 即试验人属于癌症病人 与例1的结论相反 例2 在例1的癌症诊断问题中 所有的化验结果可分为两类 w1 正常 w2 癌症 得到的判决也有两种 MadeinCV PRLabofShandongUniversity 2 3最小风险判决规则 注意 实际工作中 列出合适的风险矩阵很不容易 要根据研究的具问题 分析错误决策造成损失的严重程度 与有关专家共同商讨决定 上面分析了两种决策规则 下面讨论它们之间的关系 判决风险又叫判决损失 又叫损失函数 现假设正确判决损失为0 错误判决损失为1 且判决数目与类型数目相等 即有0 1损失函数 MadeinCV PRLabofShandongUniversity 2 3最小风险判决规则 代入式 2 3 1 有 结果代入式 2 3 2 中 得到 若 则 这就是最小错误率判决规则 结论 在0 1损失函数情况下 最小风险判决规则退化为最小错误率判决规则 也就是说 最小错误率判决规则是最小风险判决规则的一个特例 MadeinCV PRLabofShandongUniversity 2 4最大似然比判决规则 0 类概率密度 又称为 似然函数 两个类概率密度之比称为 似然比函数 最大似然比判决规则也是一种Bayes分类方法 描述 类型 分别与其它类型 的似然比均大于相应的门限值 分别与 的似然比均小于相应的门限值 则样本 而其它类型 1 由最小错误率判决规则引出最大似然比判决规则 2 由最小风险判决规则引出最大似然比判决规则 MadeinCV PRLabofShandongUniversity 2 4最大似然比判决规则 0 1 由最小错误率判决规则引出最大似然比判决规则 若 最小错误率判决规则 两边同时除以 有 定义类型 与 的似然比为 2 4 1 则判决门限为 2 4 2 一般先验概率已知 也就已知了 MadeinCV PRLabofShandongUniversity 2 4最大似然比判决规则 0 则 则 2 4 3 则偶然决定 或 2 由最小风险判决规则引出最大似然比判决规则 若 有 代入 有 即 所以 最小错误率判决规则 就变为 若 MadeinCV PRLabofShandongUniversity 2 4最大似然比判决规则 0 又由Bayes公式 代入上式 即 式中 2 4 4 为判决门限 总结 最小风险判决引出的最大似然比判决与最小错误率判决引出的最大似然比判决的公式相同 只是判决门限的计算公式不同 MadeinCV PRLabofShandongUniversity 2 4最大似然比判决规则 0 同样 在 2 4 4 中取0 1损失函数 即 则 2 4 4 退化为 2 4 2 在0 1损失函数情况下 最小风险判决退化为最小错误率判决 将上述讨论进一步推广 假定有c个类型 分别用 表示 定义 且 2 4 5 由最小错误率判决规则导出 0 若 则 其中 2 4 7 2 4 6 MadeinCV PRLabofShandongUniversity 2 4最大似然比判决规则 由最小风险判决规则导出 对于2 4 6式 定义为 同样在0 1损失函数的情况下 2 4 8 退化为 2 4 7 2 4 8 似然函数的性质 因此 在c类问题中 若有一个 则不可能再有另外的类型 例3 对于前面的例1 2可以用上述办法求出 满足式 2 4 6 式 满足 2 4 6 式 MadeinCV PRLabofShandongUniversity 2 5Neyman Pearsen判决规则 0 在两类别决策问题中 有犯两种错误分类的可能性 一种是在采取决策时 其实际自然状态为 另一种是在采取决策时 其实际自然状态为 在实际应用中 有时不知道先验概率 仅知道类概率密度 应如何确定判决门限呢 假定在处理过程中 先验概率保证不变 这时可以使用聂曼 皮尔逊 Neyman Pearson 判决规则 两种错误的概率分别为 和 最小错误率Bayes决策是使这两种错误之和最小 MadeinCV PRLabofShandongUniversity 2 5Neyman Pearsen判决规则 0 在两类问题中 两类的类概率密度曲线如下图所示 假定判决门限选为t 可能发生的两类分类错误与阴影区面积和成正比 聂曼 皮尔逊判决规则的基本思想是 在一种错误率不变的条件下 使另一种错误率最小 MadeinCV PRLabofShandongUniversity 2 5Neyman Pearsen判决规则 0 这是具有实际意义的 例如 在细胞的化验中 由于把异常细胞错判为正常细胞的风险较大 可以要求这种错判的错误率不大于某个指定的常数作为前提条件 使正常细胞错判为异常细胞的错误率尽可能小 以此为原则来选择判决门限t 这就是聂曼 皮尔逊判决规则的基本思想 从上图可以看出 假定不变 为某个给定的正数 令 2 5 3 MadeinCV PRLabofShandongUniversity 2 5Neyman Pearsen判决规则 0 为了使最小化 就要通过适当地选择某个正数使最小 把 2 5 4 式和 2 5 2 式代入 2 5 3 式 得到 2 5 4 2 5 5 2 5 6 把 2 5 5 式和 2 5 1 式代入 2 5 3 式 得到 2 5 7 为了使最小化 上两式中的被积函数最好为负数 从而得到聂曼 皮尔逊判决规则为 MadeinCV PRLabofShandongUniversity 2 5Neyman Pearsen判决规则 显然正数 是x的函数 根据上式 要求 为 2 5 9 为了最后确定各特征坐标上的门限值 还需要利用给定的正数 由 2 5 2 式 并参考上图 得到 式中 表示函数 的逆函数 2 5 10 例 两类的概率密度函数是正态的 两类的均值向量分别为 和 协方差矩阵相等且为单位矩阵 给定 试确定N P判决门限t MadeinCV PRLabofShandongUniversity 2 5Neyman Pearsen判决规则 0 解 根据给定的条件 很容易写出两类的类概率密度函数 即 和 而 得到 故 只是x1的函数 与x2无关 有 MadeinCV PRLabofShandongUniversity 2 5Neyman Pearsen判决规则 又 的边缘密度为 对于给定的正数 可由下式计算 MadeinCV PRLabofShandongUniversity 2 5Neyman Pearsen判决规则 0 显然 y是服从标准正态分布的随机变量 令 则 与y1具有一一对应的关系 有表可查 当 时 因此判决门限 如上图所示 分区界线是 的一条直线 对于样本 的分类判决 只需考察特征 则 否则 x属于w2 判决规则为 若