模式识别考试题.pdf

一 监督模式识别与费监督模式识别 监督模式识别 有一个已知样本集 集合中每个样本的类别已知 作为训练样本集 并通过控制先验已知信息来指导设计分类器 这种情况下建立分类器的问题属于监督学习问 题 称作监督模式识别 非监督模式识别 没有已知类别的标签的训练数据可用 通过挖掘样本中潜在的相似性 分类 这种学习过程成为非监督模式识别 在统计中通常被称作聚类 所得到的类别也称作 聚类 由于没有类别已知的训练样本 在没有其他额外信息的情况下 在用不同的方法或不 同的假定可能会获得不同的结果 聚类结果只是数学上的划分 对应的实际问题需结合更多 的专业知识进行解释 二 聚类分析的基本思想 C 均值动态聚类算法的思想及步骤 1 聚类分析是无监督分类 1 假设 对像集客观存在着若干个自然类 每个自然类中个体的属性具有较强的相似性 2 原理 将给定模式分成若干组 每组内的模式是相似的 而组间各模式差别较大 3 方法 a 根据带分类的模式属性或特征相似程度进行分类 相似的模式归为一类 不相似的 模式划分为不同的类 将带分类的模式集分成若干个不重叠的子集 b 定义适当的准则函数 运用有关的数学工具 或利用有关的统计概念和原理进行分 类 2 C 均值法 1 条件及约定 设待分类的模式特征矢量集为 1 x n x 类的数目 C 是事先取定的 2 算法思想 该方法取定 C 个类别和选取 C 个初始聚类中心 按最小距离原则将各模式 分配到 C 类中的某一类 之后不断的计算类心和调整个模式的类别 最终使各模式到其判 属性类别中心的距离平方之和最小 3 原理步骤 a 任选 C 个模式特征矢量作为初始聚类中心 0 0 2 0 1 c zzz 令 k 0 b 将待分类的模式特征矢量集 i x 中的模式 按最小距离原则分化给 C 类中的某一类 即 如果 k il d j min k ij d i 1 2 3 N 则 1 k il x 式中 k ij d表示 i x 和 j k w的中心 k j z 的 距离 上角标表示选代次数 于是产生新聚类 1 j k w j 1 2 C c 计算重新分类后的各类心 1 k j z 1 1 k j n 1 k ji wx i x j 1 2 C 式中 1 k j n为类 1 k j w 中所含模式的个数 d 如果 1 k j z k j z j 1 2 C 则结束 否则 k k 1 转至 b 三 说明线性判别函数的正负以及数值大小在分类中的意义并证明 n 维特征空间 n x中 两类问题的线性判别界面方程为 0 w x 1 n w 0 判别函数为 d x 0 w x 1 n w 此方程表示一超平面 它有以下三个性质 意义 1 系数矢量 是该平面的法矢量 1 判别函数 d x 的绝对值正比于x 到超平面 d x 0 的距离 2 判别函数值的正负表示出特征点位于哪个半空间中 即若为正 在超平面的正侧 若为负 在超平面的负侧 证明 1 平面 的方程可以写成 0 0 w w x 0 1 w wn 设平面 的单位法矢量n 0 0 w w 等号上有小三角 上式可以写成n x 0 1 w wn 设p 是平面 中的任一点 x 是特征矢量 n x中的任一点 点x 到平面 的距离为差矢量 x p 在n 上投影的绝对值 即 x d n x p n x n p 0 0 w w x 0 0 w w p 0 0 w w x 0 1 w wn 1 0 w d x 上式表明 d x 的值 d x 正比于x 到超平面 d x 0 的距离 x d 2 两矢量n 和 x p 的数积为 n x p n x p cos n x p 0 1 0 w wxw n 当n 和 x p 夹角小于 o 90时 即x 在n 指向的那个半空间中 cos n x p 0 反之 n 和 x p 夹角大于 o 90时 x 在n 背向的那个半空间中 cos n x p 0 故n x p 和 1 0 n wxw 同号 即x 在n 指向的半空间中时 0 10 n wxw 即x 在n 背向的半空间中时 10 n wxw 22 l 12 l P 2 w x 则x 2 1 w w 其中 11 l 21 l 0 22 l 12 l 0 即 1121 2212 2 1 ll ll xwP xwP 则x 2 1 w w 决策 自然状态 1 w 2 w 1 11 l 11 wl 12 l 21 wl 2 21 l 12 wl 22 l 22 wl 由 得 若 1121 2212 22 11 ll ll wPwxP wPwxP 则x 2 1 w w 即 若 1121 2212 1 2 2 1 ll ll wP wP wxp wxp 则x 2 1 w w 可得最小风险 Bayes 决策识别规则 八 已知某一类训练样本集的每一个样本都是由独立抽样实验采集的 类条件概率密度服从 正态分布 以一维情况为例 求最大似然估计对未知参数 均值 方差 的估计过程及结果 解 由题意 单变量正态分布的形式为 P x 2 1 exp 2 1 2 x 其中均值 和方差 2 为未知参数 即要估计的参数为 TT 2 21 用于估计的样本是 x N xx 1 则似然函数 L p x 0 1 12 211 N N xxp 最大似然估计是下列方程组的解 N k k xpH 1 ln 0 又从 可得 2 1 2 2 2 1 2ln 2 1 ln k xxp 分别对两个未知参数求偏导 得 2 1 2 1 1 ln 2 1 2 22 1 2 k k k x x xp 因此最大似然估计是以下方程组的解 N k k x 1 1 2 0 1 0 1 11 2 2 2 1 2 N k N k k x 解得 N k k x N 1 1 1 2 2 2 1 k x N 九 最邻近决策和 K 近邻决策的思想是什么 最邻近决策 对于一个新样本 把它逐一与已知样本比较 找出距离最新样本最近的已知样本 以该 样本的类别作为新样本的类别 这就是最邻近法 已知样本集 N s 1 x 1 N x 1 其中 i x 是样本 i 的特征向量 i 是 它对应的类别 设有 C 个类 即 i 1 2 C 定义两个样本间的距离度量 i x j x 比如可采用欧式距离 i x j x i x j x 对未知样本x 求 N s 中与之距离最近的 样本 设为 x 对应的类别为 即 x x min 2 1 j Nj xx 则将x 决策为 类 这种决策方法称为最邻近决策 最近邻法渐进错误率 P Bayes 错误率 P C 类别数 则 P P P 2 1 p c c 即 P 最坏不会超出两倍的 P 最好有可能接近或达到 P K 近邻决策 选择前若干个离新样本最近的已知样本 用他们的类别投票来决定新样本的类别 习惯 把参加投票的近邻样本个数记作 k 称作 k 近邻法 设有 N 个已知样本属于 C 个类 i w i 1 C 考察新样本x 在这些样本的前 K 个近邻 设其中有 i k个属于 i w类 则 i w类的判别函数就是 xgi i k i 1 C 决策规则是 若 xgk max 1 xgi Ci 则x k w k 近邻法仍满足 的上界关系 但随着 k 的增加 上界将逐渐降低 当 k 趋于无穷大时 上界和下界碰到一起 k 近邻 法就达到了贝叶斯错误率 十 主成分分析方法的基本原理是什么 推导变换矩阵的组成 基本原理 1 从一组特征中计算出一组按重要性从大到小排列的新特征 他们是原有特征的线性组合 并且相互之间是互不相关的 2 记 1 x p x为 p 个原始特征 设新特征 i i 1 p 是这些原始特征的线性组合 i p j T ijij xaxa 1 为了统一 i 的尺度要求线性组合系数的模为 1 即 T i a i a 1 则 T A x 其中 是由新特征 i 组成的向量 A 是特征变换矩阵 要求解的是最优的正交变换A 它使新特征 i 的方差达到极值 变换矩阵A 的组成 1 A 1 a p a 最优的 1 a 是 的最大本征值对应的本征向量 2 a 第二大 变换矩阵A 的各个列向量是由 的正交归一的本征向量组成的 因此 T A 1 A 即A 是正交矩阵 2 1 a 第一主成分 1 p j T jij xaxa 1 1 方差最大 模为 1 方差 var 1 E 2 1 E 1 2 11 axxaE TT 11 axExaE TT T a1 1 a 其中 是x 的协方差矩阵 E 是数学期望 要在约束条件 T a1 1 a 1 下最大化 1 的方差 等价于下列拉格朗日函数的极值 1 af T a1 1 a v T a1 1 a 1 v是拉格朗日乘子 将其对 1 a 求导 并令他等于零 得 1 a 满足 1 a v 1 a 这是 的特征方程 即 1 a 一定是 的本征向量 v是对应的本征值 则 var 1 v 3 第二主成分 2 满足 与