模式识别原理10

nullnull单特征维特征优化 优点：验证每一特征的有效性。是次优的，识别性能 对实时特征优化很重要 缺点：一维特征排序的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，不考虑正交性 线性fisher分类比（FDR，可多维），统计排秩方法， 通过探测类间检测索引来决定特征优先级 K：类别数 P： 特征（下标） 第I类第p个特征均值 第I类第p个特征 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 类null模拟退火算法 ①初始温度 初始特征 下一个解 ， 邻域 ② 新特征 ，按可分性判据 下可多次转移 ③ 下未达平衡态，到② ④ 足够低，结束得特征 null ⑤计算新温度 ，转到② 变化足够 性能与速度折衷 遗传算法 遗传，变异，进化 群体－ 个体，解集 交叉－2个个体，以其作为双亲做基因链码交叉 （即遗传产生后代）null产生新个体（后代） 如：随机选截断点，交换后半部分 后代 变异－某个基因链码的某基因翻转： 每个基因链码 取得极大值，则 越好，越适应 null遗传算法： 1 进化代数t＝0：初始群体 ， 为其中任一个体。 2 估值 的每一个体 得最优解 。若 优于 ， 保证是搜索过了最优解 3 终止条件满足，停， 为结果，否则 群体代数超过给定值，或在一个给定代数后无最优解 4 从 中选个体交叉，变异，得 个体性能越好，被选概率大 D个特征选d位 0，1表示特征组合 null 第六章 聚类分析 聚类：学习，是分割的一种（分裂、合并） 对观察量所知甚少，尝试寻找它的结构。 类别不知，据样本相似程度来自动进行分类。 ①未标记的样本分几类？ （非监督学习） ②已标记集合分为几个子集 如字母Q：QQQQQQQQQQ 监督 类聚：按某个 原则 组织架构调整原则组织架构设计原则组织架构设置原则财政预算编制原则问卷调查设计原则 ，把各模式样本在特征空间中分成一 块一块，每块点集为一个聚类。 整个分类过程为类聚过程。 风险 ① 聚类分析代替了寻找自然的数据结构（fit for） ② 很多聚类算法允许自由地聚为N类 ③ 同一dataset和加权值，不同聚类技术有不同聚类结果。 BOSS：2*2=？ 律师：您希望它等于？ ④ 通常边界并不尖锐，渐变，旁边有其他类null为什么去聚类？ 1）对给定测量或特征值，空间中子集的可分离性不会 因为其分布的线性修正而改变。 2）用是否“自然”去衡量分类得怎样。 聚类有效性？ 测度原则： ①以距离函数作度量，不断修改阈值来探究对准则的满足情况。 欧氏距离、相似距离、其他距离。。。 类内偏差min、类间距max 如最近邻聚类 ②误差平方和准则 则 寻求使各类划分合理的最小值 每种划分对应一个J值，求 的划分null 适用类内偏差min 类间距max 的情况（紧致） 应用： 降维（特征聚类）、 数据压缩（紧密聚合类内的模式可由该类中心表示）、 多谱数据分类、 图象分割，匹配null一 、基本聚类算法 最小均方误差聚类：局部均方误差最小点 穷尽搜索、耗时； 与样本SIZE 有关，比较只在相同样本数下有意义 球形聚类 ISODATA：距离测量最近邻中心归类重新计算均值重复 分级聚类：1N 图论聚类方法:谱系图、树图。 距离、搜索路径有关（样本沿线/面分布？不规则形状） 难以了解聚类的形状 1、 基于最近邻规则的试探法（即直接推断法） N个样本， 求 到 的距离 null A. if ， ， B. if ， 为分数， ， 重算 的中心 C. if 在 之间，不定 ，如 可取1/2.null优点：可以串行处理，计算简单 类别中心迭代 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 ： 如： 缺点： ①有 时，会有一个未定区 ②与 第一个聚类中心的选取 排列样本顺序 大小 有关。null2、 基于最小最大距离算法（以上一个方法发展） 例：给定样本： 求聚类 null第一步： 计算各点欧氏距离，可构成三角形表，存于机 中待查null第二步：任选中心点（第一类） 第三步：查表，找出与 相距最远点（第二个样本）， 得 ，选 为 ，第二类中心 第四步：查表知，各点与两中心点的距离， 构成队列。 每点2个距离： 左（min距离） 右（max距离） 在左边最小列中选最大者，则独立于原类别null第五步：因为 ，所以 为 第六步： 查表，找各点到 距离 ， 又排队列 第七步：又找，直至 ， 不能成为新的一类 结论： 再用上节方法，录取其他点至此之各类别 上节方法为： 结块算法（lumping） 本节方法为： 分快算法（splitting分割法）null3、 对话式结块算法（ISODATA）算法 （iterative self-organization data analysis technique algorithm：迭代自组织数据分析技术算法） Forgy程序、C/K均值算法（已知类别数 C，K） 聚类中心通过样本均值迭代运算得来 试探性+人机交互，吸取中间结果，可一分为二或合二为一。 第一步：任设类别中心点 分别录取，令 ，去除模糊区 第二步：根据最小距离录取其他点 null 第一轮结果 第三步：重新计算类别中心点，返回第二步 据上述计算，第二轮开始的中心点位置null 再计算距离：如 重新录取，得到第二轮结果 结论：第一轮假设是对的 结束条件：若验证 相等，结束，为C，K均值法 缺点：没有考虑，类内距离和类间距null检验分类是否正确准则： 结果： 这是由于开始设的中心不恰当 第三轮：检验 的结果不合适。要重新改变中心， 调整聚类数，在 内有理由认为分为两类。 第二次重选初始中心， 有针对性地重复一遍， 合理null查表可得： 验证： 合理，结果正确，分类满足要求 初始中心选定不当时，分类出错，要验算。 null可以规定验证参量： A 允许的最大类内偏差 ，或类内距离 B 最小类间距离 C 每类最小样本数，要求各类别数目接近 D 规定希望类别数 据参量和步骤，开始可任算，中间要验算，自动类聚。 规定最大扩展参数， 最大合并类别数（超过不合并）， 最大合并距离 四、类聚的数学模型和物理模型 1、类聚过程上升到一个迭代的数学模型 类聚过程三个算子：null一、 h算子（初始化算子）－从给定样本算出用来分类的数 （测量度） 二、 g算子（描述算子）给予类聚集合以符号描述 （1）类聚（类别划分Partition） k种典型特征比较P的各类用最接近的特征命名之 （2）对应各类的k个解释符 可以是各类命名，每个A用自己的一组中心参量表征。 （g算子表示把P映射为L的过程，描述每个类别） null三、 算子（识别算子） 菜心 原来一个样本集 据特征， 描述为 再来一个新成员 据 重新描述为 接近菜心 直到特征稳定，描述稳定为止。稳定PL，P：最终的分类类聚集合 L：最终的分类解释集合 类聚的数学模型 * 首先给定解释符集合L（1） 产生类聚集合P（1） （每个类别用特征说明，解释(分类) 待分类样本 以是否 衡量，逐渐产生首次迭代的类聚集合）null新样本加入，重新确定其特征平均值新的解释符L（2） (确定时，以某个条件约束，如风险 最小 ，代价最小等。 把样本分到P（1）时风险最小， 即样本据 P（1），若 ，则 否则修正，使 按L（2）来接受新来的样本，x不断来 重复进行至得到稳定的L、P，过程结束。 开始的0阶解可任意假设， 后面动态类聚null2 、物理模型（相似吸附，物以类聚、人以群分，同声相应、同气相求） 吸附力模型，设吸附力为一非负函数 （与类聚本身有关，使同类点凝聚） 设一类别集合 ，互不连通 各类别内部吸附力 （非负） 整个集合吸附力 之间的吸附力 同一大系统吸附力 各子系统吸附力和： null定义结构函数 非负集合函数 测度子集之间的吸附力 J越大，即 愈大，类别间吸附力愈大，愈难分开。 J愈小，愈好分开 分类：使 ， 尽可能切断类别间联系 （使其易被分开） 物理模型类聚准则 ①吸附力的结块聚合成类（结块算法） ②吸附力小的集合分割出类别（分块算法）null例子： 两个二进制数列,可用相同/相异的1或0的个数来测度 其相似性程度。 null 第i、j个样本数列同一位均取1值 1）若 两物体互不相关。其出现某种取值组合的概率 等于各自取相应值的概率相乘。 2）若 取值频繁地一致，或频繁地不一致，说明两物体间有着某种关系（相似或相反），很可能结成一团。 类聚体现在：出现某种取值组合的概率大于各自取某一个值的概率的乘积。 null比如： 相关，两物体间有一定吸附力 如果设 可知 在某列第I个物体具有其特性的概率 且可知 某列不具有其特性的概率 某列一个有一个无 null结构函数可选为J： 代入展开化简 结构函数＝部分熵之和－总体熵null三、树形类聚法 据图论类聚，谱系图表示法 跨距树图表示法 1、 谱系图法（以图形表示模式、聚类及模式类别间隔） 模式样本集 ，其幂集 谱系图定义为H（Hierarchy）： ① （样本x属于这个谱系图） ② （样本集合X的具有某种性质的集合也属于这 个谱系图） ，那么 （若有某个样本属于模式样本集， 则样本也属于这个谱系图） ④ 且 ，则必有 或 （如果谱系图中的两个部分，互相之间有重叠的关系， 那么这两个部分有包含的谱系关系）null构成方法： ① 先造距离表，计算各模式样本间的距离 ② 搜索最小距离 规则 ① 先找出 的一对元素，组成新集合 ，把其中一个元 素去掉，只剩一个，以 作其组名。 （如 ，对应于 ，得一子集，去除 对应的行、列，以 代替 ，再计算其它x对 的距离） ② 在有 的距离表中又找 。 （从 引发出去，取得 的样本。 找完后，从另一 出发。照此方法找第二类的）null③ 第二轮 查表找到 ，依上法在高一层次有几类 ④ 又造第三轮距离表, * 一直进行到只剩一行一列，得谱系图 * 对该图分段、分集团，可设定门限（代表类内距离），分 类数与门限有关。 是自下而上的分级聚类方法，N个无类别标签的样本， * 极端情况下为N个集合，每类一个样本 * 第二个划分可为N－1类，N－2类，…，直至1个类。 类数 时，称划分处于 i 水平null 任2样本某个样本水平上归为同一类 同一类样本更高水平的划分时也总是处于同一类。 (如同生物：个体种－类－族，聚类类数的合理性从类间相似度决定） 2、跨距树图（spanning tree） 术语： ①线段：两个模式样本点的连线 ②路径：连接两点的线段序列 ③回路：闭合路径 ④连通图形：任两点之间有一条或一条以上路径者。 （即各点之间是连结起来的，但不一 定直接相连。） ⑤树图：没有回路的连通图形 （单线顺序相连，不闭合，不返回）null⑥跨距树图：包含模式样本集合中每一点的树图 （即连结每一个模式样本点且没有重复的连通图） ⑦线段权重（线的重要性）：可取点间距离 整个树图的权重为树图中各线段权重之和。 ⑧最小跨距树图：权重最小的跨距树图 （若以距离作权重，则各模式样本点以最小 距离连结每一样本点，且无重复） * 沿着该路线，连结相邻每点间的距离总和min * 一条路，经过最多点，代价最小。 ⑨主直径：在最小跨距树图中走过最多模式样本点的那条路径。 跨距树图：把一个类聚的各个模式用一条线段顺序相连，顺着 路径可得出类聚结果。 若 是同一类聚，则以线段 相连，得 逐渐构成跨距树图。 null最小跨距树图构成方法： ①计算距离表 ②所有距离按从小到大顺序排列 ③按距离从小到大顺序连结点对。 规则：   是最小跨距树图 从 最后，经过最多点的路径称为主直径 沿主直径走下去，代价最小。 分类时，依距离门限分为几类null3、分享共同邻域点类聚法 最大相似性树图，以共同邻点数作阈值，也作权重 邻域位置表示 统计特征空间样本点及其邻域的投影（4或8邻域） 列出最近邻表 统计共同邻点数 以共同邻点数k作类聚门限。 * 有一定的k数聚为一类， （两个样本邻域位置靠近，相同邻点多类似。） * 先连k最大的，再连次大的。 null 步骤： ①作邻域表。M个样本，每个样本本身处于0位置， 8个邻点，标上样本号。 ②作共同朋友表，标上各样本之间相同邻点的数目， ③首先连接共同朋友最多的点对，找最大数max； 再到次多的、。。。。 连结规则：不可构成回路。 特点：类聚区分清楚， 类内主直径经过最多样本点、权重最大、共同邻点数最多null四、动态类聚：反复用g及 迭代达到最佳 一般类聚算法及其与数学模型对应关系： <一> 初始化样本 ，解释符 计算测度量(h算子) <二> 类聚 if only 相当于 , 接受新成员。 <三> 检验：新样本到后，重新计算 中心，使代价最小， 修改解释符g（P）=L <四> 是否稳定。P.L是否稳定，说明 是否有新成员，是否需 要返回第二步重新计算 其中第三步中有两种方法 算法1： 每接受一个新成员，计算新的 参数（逐个样本修正法， 串行法） 算法2： 接受完所有的成员，再计算（成批样本修正法、并行）null2个样本从同一类的2个不同部分抽出，其中一个的随机 变量参数比另一个大，如： 2类，均值中心相同，各中心到其个别点的均值距离不同 （分布密度不同） 如： ①OCR问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ： 印刷质量不同的文本，样本分散程度不同。 ②不同时间收集的data，参数会分散。 ③不同光照条件下的图象 图论聚类，直觉，但结果较难解释 图论聚类：形状？难以了解聚类的形状 （样本是沿着一条线？在平面上？不规则形状？） 均方误差min的聚类：产生球形聚类 （不管自然聚类是否球形） null没有一个类聚法可以对所有数据表现得最佳： 近邻法：实际过程中受挫于链式效应，某些点因有共同相邻点 而被再次从各类中移出而归入同一聚类。 分级的类聚：序贯合并处理，仅考虑距离或类别间的不相似性， 初始状态 N个样本data，最近邻合并， 到所需类 别数或最小不相似门限时，停止 划分方法可使初始得不准确划分得到改进 *最小均方误差准则  寻找超椭球形的聚合类。但两类模式数目 相差较大时，大的聚合类进行分裂，方差会更小 *考虑：① 数据矩阵随机聚类的可能 ② 系统层次符合？ ③ 划分有效？：类内内聚，类间分离 *数据的知识，同样数据不同算法，看其结果。null关键是聚类的有效性。（因为聚类的任意性本质） 验证： 对几种聚类技术，用通常的类别来验证，而不是对个别类找有效性 五 聚类的有效性：PR重要部分，但具有一定的随意性 * 某些方法脱离真实的分布，加一个超形状给数据来聚类。 * 聚类结果受距离测量影响，尤其是对不同轴的加权 * 抽样错误：样本的代表性如何？不同时间的抽样来自 同一类或不同类？ （可以从统计检验来解决2样本是否同一分布） 不能指望找出一个单个的统计来解决所有问题的聚类有效性。 *典型聚类问题先验信息太小，即使对单一类别，其聚类有效性也牵涉很多因素（如某一度量空间中划分的点数）。 *聚类分析是对自然的探索，而且是一个发现工具。 不是终结，在假设高斯分布下的t/F检验实质是随机分布下t/F检验，聚类标示是在假设分布下某一准则的最优化模式处理） *有效性应针对几个聚类方法对普通聚类的处理null假设检验 t分布：均值为 的样本， 标准方差可能来自均值为u的 分布，比值检验   F分布：检验2个样本方差比值的有效性来决定它们是否 来自同一类。 null第七章  句法模式识别 类聚吸附力模型等涉及到类别之间，类别与整体之间的结构关系（J），这些结构间的关系需借助结构信息解决―――句法模式问题。 结构信息重要，如图片，语音。景物的识别十分复杂，要求特征量非常巨大，要把每一模式分类准确很困难，希望把一个   识别基元 子模式 复杂模式 （汉字，指纹，连续语音采用这方法已获得一定成功） 类比： 文库 句子 句子 字，字符 字 字母 文库，句子，正确与否看是否合文法null 执行模式推理，按模式文法看是否得出（识别所要求的模式) 句法PR系统：