模式识别绪论


模式识别 12-13学年第1学期 东南大学计算机科学工程学院 第一个模式 • 耿新 • Email: • xgeng@seu.edu.cn • URL:URL: • http://cse.seu.edu.cn/people/xgeng/index.htm 东南大学计算机科学与工程学院 第二个模式 • 名称:模式识别 • 学分:2 • 学时 36• 学时:36 • 上课周次:1-12周 • 推荐教材 • 《Pattern Classification 2nd Edition》,机械工业出版《Pattern Classification, 2 Edition》,机械工业出版 社,Richard O. Duda, Peter E. Hart, David G. Stork, 2004 • 《Pattern Recognition, 4th Edition》,机械工业出版社, S. Theodoridis,K. Koutroumbas,2009 东南大学计算机科学与工程学院 考核方式 • 平时成绩:40% • 课堂表现+出勤率:10% • 期中大作业 30%• 期中大作业:30% • 期末考试:60% • 加分:5% 期中作业优秀者就其作业内容做报告 可获此加分期中作业优秀者就其作业内容做报告,可获此加分 东南大学计算机科学与工程学院 广告 • 模式识别有什么用? • 微软、Google、IBM的共同兴趣 • 计算机科学最热门的研究领域之一• 计算机科学最热门的研究领域之一 • 人类智能的核心问题之一 • 因此。。。 • 找最Cool的工作找最Cool的工作 • 做研究 出国• 出国 东南大学计算机科学与工程学院 Ch 01. 模式识别绪论 "To understand is to perceive patterns" – Isaiah Berlin 什么是模式 •“A pattern is the opposite of a chaos; it is an p pp entity vaguely defined, that could be given a name.” – Satoshi Watanabe 东南大学计算机科学与工程学院 什么是识别 • “Identification of a pattern as a member of a p category we already know, or we are familiar with” – Anil K. Jain • 分类 (已知类别) • 聚类 (创建新类别)• 聚类 (创建新类别) 分类 聚类 东南大学计算机科学与工程学院 分类 聚类 什么是模式识别 • 对表征事物或现象的各种形式的(数值的,文字征事 现象 各种 式 数值 字 的和逻辑关系的)信息进行处理和分析,以对事 物或现象进行描述、辨认、分类和解释的过程, 是信息科学和人工智能的重要组成部分。 • “The real power of human thinking is based on• The real power of human thinking is based on recognizing patterns. The better computers get at pattern recognition the more humanlike theyat pattern recognition, the more humanlike they will become”. – Ray Kurzweil NY Times Nov 24 2003– Ray Kurzweil, NY Times, Nov 24, 2003 东南大学计算机科学与工程学院 什么是模式识别 • It is the study of how machines cany • observe the environment • learn to distinguish patterns of interest from their• learn to distinguish patterns of interest from their background make sound and reasonable decisions about the• make sound and reasonable decisions about the categories of the patterns. 东南大学计算机科学与工程学院 模式识别应用(1) • 字符识别 • 输入 • 输出:Earham encourag 东南大学计算机科学与工程学院 模式识别应用(2) • 语音识别 • 输入:声波信号 • 输出:语音内容 东南大学计算机科学与工程学院 模式识别应用(3) • 指纹识别 • 输入:指纹图像 • 输出:身份 东南大学计算机科学与工程学院 模式识别应用(4) • 签名验证 • 输入:签名点序列 • 输出:签名人身份 东南大学计算机科学与工程学院 模式识别应用(5) • 人脸检测 • 输入:图像 • 输出:人脸在图像中的位置 东南大学计算机科学与工程学院 模式识别应用(6) • 文档分类 • 输入:HTML文件 • 输出:文档类别 东南大学计算机科学与工程学院 模式识别应用(7) • 财务预测 • 输入:股票价格时间序列 • 输出:牛?熊? 东南大学计算机科学与工程学院 其他应用 ProblemProblem InputInput OutputOutput NonNon--destructive testingdestructive testing Ultrasound, eddy current, Ultrasound, eddy current, acoustic emission waveformsacoustic emission waveforms Presence/absence of flaw, Presence/absence of flaw, type of flawtype of flawacoustic emission waveformsacoustic emission waveforms type of flawtype of flaw Detection and diagnosis of Detection and diagnosis of diseasedisease EKG, EEG waveformsEKG, EEG waveforms Types of cardiac Types of cardiac conditions, classes of brain conditions, classes of brain conditionsconditionsconditionsconditions Natural resource Natural resource identificationidentification Multispectral imagesMultispectral images Terrain forms, vegetation Terrain forms, vegetation covercover Aerial reconnaissanceAerial reconnaissance Visual infrared radar imagesVisual infrared radar images Tanks airfieldsTanks airfieldsAerial reconnaissanceAerial reconnaissance Visual, infrared, radar imagesVisual, infrared, radar images Tanks, airfieldsTanks, airfields Character recognition Character recognition (page readers, zip code, (page readers, zip code, license plate)license plate) Optical scanned imageOptical scanned image Alphanumeric charactersAlphanumeric characters license plate)license plate) Identification and counting Identification and counting of cellsof cells Slides of blood samples, microSlides of blood samples, micro-- sections of tissuessections of tissues Type of cellsType of cells Inspection (PC boards ICInspection (PC boards IC Scanned image (visibleScanned image (visible Acceptable/unacceptableAcceptable/unacceptableInspection (PC boards, IC Inspection (PC boards, IC masks, textiles)masks, textiles) Scanned image (visible, Scanned image (visible, infrared)infrared) Acceptable/unacceptableAcceptable/unacceptable ManufacturingManufacturing 33--D images (structured light, D images (structured light, laser stereo)laser stereo) Identify objects, pose, Identify objects, pose, assemblyassembly 东南大学计算机科学与工程学院 laser, stereo)laser, stereo) assemblyassembly Web searchWeb search Key words specified by a userKey words specified by a user Text relevant to the userText relevant to the user 目前已知最好的模式识别系统 • 人类大脑! 东南大学计算机科学与工程学院 基本概念 • 模型(Model) 可以用数学形式表达的不同特征的描述 样本(Sl)• 样本(Sample) 分类的基本对象,模式的实例 • 训练集(Training Set) 用于训练分类器的样本集合用于训练分类器的样本集合 • 测试集(Test Set) 用于测试分类器的样本集合,通常应与训练集无交集 基本概念 • 特征(Feature) 可用于分类的样本属性 特征向量(Ft Vt)• 特征向量(Feature Vector) 由一组特征组成的向量,通常表示为列向量 • 特征空间(Feature Space) 由所有可能的特征向量组成的数据空间 如 3Rx由所有可能的特征向量组成的数据空间,如 • 散布图(Scatterplot) 3Rx 将每个样本表示为特征空 间中的一个点 基本概念 • 决策边界\面\曲线(Decision Boundary)y 特征空间中区别各类的边界 线性决策曲线 二次决策曲线 复杂决策曲线 一个详细的例子 东南大学计算机科学与工程学院 一个详细的例子 • 预处理 • 调整光照 • 去除噪声 • 增强对比度 •… • 分割 • 将鱼的图像同背景分离开来将鱼的图像同背景分离开来 • 特征提取 • 从鱼的图像中提取用于分类的特征• 从鱼的图像中提取用于分类的特征 • 分类 鲑鱼?鲈鱼?• 鲑鱼?鲈鱼? 一个详细的例子 • 选择用于分类的特征 训练集的直方图 长度 光泽度 东南大学计算机科学与工程学院 一个详细的例子 • 决策边界与代价(cost) 鲑鱼比鲈鱼值钱!鲑鱼 鲈鱼值钱 等代价 消费者 奸商消费者 奸商 东南大学计算机科学与工程学院 一个详细的例子 • 使用两个特征:光泽度x1和宽度x21 2 一个样本的特征向量:[x1, x2]T 线性决策边界: f(x1,x2)=ax1+bx2+c=0 f(x x )<0 鲑鱼f(x1,x2)<0:鲑鱼 f(x1,x2)>0:鲈鱼 东南大学计算机科学与工程学院 一个详细的例子 • 那个判决曲线更好? 东南大学计算机科学与工程学院 泛化能力 • “推广能力”/“泛化能力”(Generalization) • 设计分类器的中心目标是能够对新样本做出正确的反应 ,而不是对训练样本的完美分类。,而不是对训练样本的完美分类 • 分类模型对训练样本的过分匹配是一种应当努力避免的 现象:过配(Overfitting)现象:过配(Overfitting) • 避免过配的方法 避免过于复杂的决策面避免过于复杂的决策面 • 两难 复杂的决策面复杂的决策面? 简单的决策面? 根据具体应用设计 专门的分类器 东南大学计算机科学与工程学院 相关领域 • 假设检验(Hypothesis testing) •H0 vs. H1 • 图像处理(Image processing) • 图像 图像 • 回归(Regression) 为输入数据找到合适的函数表示• 为输入数据找到合适的函数表示 • 插值(Interpolation) 已知 定范围内的输入数据对应的函数值 求输入点之间的数据点对应的• 已知一定范围内的输入数据对应的函数值,求输入点之间的数据点对应的 函数值 • 概率密度估计(Density estimation) • 估计产生给定样本集的概率密度函数 东南大学计算机科学与工程学院 模式识别系统 后处理决策 分类 特征提取 预处理 分割 输入 传感器 预处理 输入 传感器 模式识别系统设计 开始 采集数据 开始 选择特征 选择模型 先验知识 训练分类器 评价分类器 结束 模式识别中的重要问题 • 噪声 • 模型选择 • 分割 数据采集 模择 • 过配 • 数据采集 • 领域知识 • 上下文 • 分类器集成领域知识 • 特征抽取 分类器集成 • 代价与风险 • 模式表示 • 缺失特征 • 计算复杂度 • 缺失特征 东南大学计算机科学与工程学院 噪声(noise) • Various types of noise (e.g., shadows, conveyor belt might shake, etc.) • Noise can reduce the reliability of the feature values measured. • Knowledge of the noise process can help improve g performance. 东南大学计算机科学与工程学院 分割(Segmentation) • Individual patterns have to be segmented. • How can we segment without having categorized them first ? • How can we categorize them without having segmented them first ? • How do we "group" together the proper number of l?elements ? 东南大学计算机科学与工程学院 数据采集(Data Collection) • How do we know that we have collected an adequately large and representative set of examples for training/testing the system? • The cost of data collection could be prohibitively high 东南大学计算机科学与工程学院 领域知识(Domain Knowledge) • When there is not sufficient training data, incorporate domain knowledge: • Model how each pattern is generated - this is difficult !! (e.g., illtfhi)recognize all types of chairs). • Incorporate some knowledge about the pattern generation method (e gthe pattern generation method. (e.g., optical character recognition (OCR) assuming characters are sequences of strokes)of strokes) 东南大学计算机科学与工程学院 特征抽取(Feature Extraction) • It is a domain-specific problem which influences classifier's performance. • Which features are most promising ? • Are there ways to automatically learn which features are best ? • How many should we use ? • Choose features that are robust• Choose features that are robust to noise. • Favor features that lead to simpler• Favor features that lead to simpler decision regions. 东南大学计算机科学与工程学院 模式表示(Pattern Representation) • Similar patterns should have similar representations. • Patterns from different classes should have dissimilar representations. • Pattern representations should be invariant to transformations such as: t l ti t ti i fl ti iiddf ti• translations, rotations, resize, reflections, non-rigid deformations • Small intra-class variation, large inter class variationlarge inter-class variation. 东南大学计算机科学与工程学院 缺失特征(Missing Features) • Certain features might be missing (e.g., due to occlusion). • How should the classifier make the best decision with missing features? • How should we train the classifier with missing features ?g 东南大学计算机科学与工程学院 模型选择(Model Selection) • How do we know when to reject a class of models and try another one ? • Is the model selection process just a trial and error process ? • Can we automate this process ? 东南大学计算机科学与工程学院 过配(Overfitting) • Models complexer than necessary lead to overfitting (i.e., good performance on the training data but poor performance on novel data). • How can we adjust the complexity of the model? (not very complex or simple). • Are there principled methods for finding the best complexity? 东南大学计算机科学与工程学院 上下文(Context) • The same pattern within different context might pg have different meanings • Context is very helpful!• Context is very helpful! How m ch info mation iiare y u mi sing 东南大学计算机科学与工程学院 分类器集成(Classifier Ensemble) • Performance can be improved using multiple pgp classifiers. • How should we combine multiple classifiers?• How should we combine multiple classifiers? 东南大学计算机科学与工程学院 代价与风险(Costs and Risks) • Each classification is associated with a cost or risk (e.g., classification error). • How can we incorporate knowledge about such risks? • Can we estimate the lowest possible risk of any classifier? 东南大学计算机科学与工程学院 计算复杂度 (Computational Complexity)(Computational Complexity) • How does an algorithm scale with • the number of feature dimensions • number of patterns • number of categories • Brute-force approaches might lead to perfect l ifi ti lt b t ll h i ti l ticlassifications results but usually have impractical time and memory requirements. • What is the tradeoff between computational ease and performance? 东南大学计算机科学与工程学院 计算复杂度 (Computational Complexity)(Computational Complexity) • “万能”图像识别器 • 将100*100的灰度图像所有像素值的可能组合都进行标 记记 • 拿到新图像,只需用“查找表”法,在所有做过标记的 图像库中查找一样的图像,就可以得到其类别图像库中查找 样的图像,就可以得到其类别 • 计算复杂度无法接受 100 100256  • 实际应用中必须考虑计算复杂度 设计模式识别系统的广义目标 • Humans have the ability to switch rapidly and ypy seamlessly between different pattern recognition tasks • It is very difficult to design a device that is capable of performing a variety of classificationcapable of performing a variety of classification tasks Diff d i i k i diff f• Different decision tasks may require different features. • Different features might yield different solutions. • Different tradeoffs (e.g., classification error) exist for different tasks. 东南大学计算机科学与工程学院 设计模式识别系统的广义目标 • 模式识别的根本目的在于重建产生模式的内在模型 • 每种模式识别技术都依赖于某种假设模型 • 每个模式识别问题都隐含着某种内在模型每个模式识别问题都隐含着某种内在模型 • 有没有“最佳方法”? 某种模式识别技术在某个问题上的有效性取决于该技术的假设模• 某种模式识别技术在某个问题上的有效性取决于该技术的假设模 型与该问题的内在模型的契合程度 • 不存在适用于所有问题的模式识别技术不存在适用于所有问题的模式识别技术 不存在广泛意义上的“最佳方法”,但是对某个问题有可能 找到解决它的“最佳方法”找到解决它的 最佳方法 东南大学计算机科学与工程学院 设计模式识别系统的基本手段 • 基于已知的知识 • 对于某些特定的模式,人类已知的知识就可以将其很好 的分类、识别。在这种情况下,直接根据已知知识就可的分类、识别。在这种情况下,直接根据已知知识就可 以设计很好的分类器。 • 这种情况比较少见这种情况比较少见 • 基于“从样本中学习”的算法 • 给定一定数量的目标模式的样本集合,称为训练样本集 • 应用某种学习算法从这些样本中学习得到分类器 给定一般的模型或分类器形式,利用训练样本学习或估计模型或 分类器中的未知参数 • 多数情况,也是模式识别研究的主要课题 东南大学计算机科学与工程学院 设计模式识别系统的基本手段 • 学习范式 • 有监督学习(Supervised Learning) • 无监督学习(Unsupervised Learning)• 无监督学习(Unsupervised Learning) • 半监督学习(Semi-supervised Learning) • 强化学习(Reinforcement Learning) • 增量学习(Incremental Learning)g •… 机器学习机器学习 小结 • 重要性 • 可行性 挑战性• 挑战性
还剩52页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

eis3

贡献于2012-10-18

下载需要 3 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf