谈模式识别方法在林业管理问题中的应用 报告人:管理工程系 马宁 报告地点:学研B107 报告时间:2016年5月18日(周三),13:30-15:30
模式识别 人们在观察事物或现象的时候,常常要寻找它与其他事物或现象的不同之处,并根据一定的目的把各个相似的但又不完全相同的事物或现象组成一类。 字符识别就是一个典型的例子。例如数字“4”可以有各种写法,但都属于同一类别。更为重要的是,即使对于某种写法的“4”,以前虽未见过,也能把它分到“4”所属的这一类别。人脑的这种思维能力就构成了“模式”的概念。 “模式”是一种抽象化的概念,如“房屋”等都是“模式”,而把具体的对象,如人民大会堂,叫作“房屋”这类模式中的一个样本。
模式识别的应用 模式识别与统计学、心理学、语言学、 计算机科学 、生物学、控制论等都有关系。它与 人工智能 、 图像处理 的研究有交叉关系。 模式识别与统计学、心理学、语言学、 计算机科学 、生物学、控制论等都有关系。它与 人工智能 、 图像处理 的研究有交叉关系。 例如自适应或自组织的模式识别系统包含了人工智能的学习机制;人工智能研究的景物理解、自然语言理解也包含模式识别问题。又如模式识别中的预处理和特征抽取环节应用图像处理的技术;图像处理中的图像分析也应用模式识别的技术。 模式识别可应用于文字识别、语音识别、指纹识别、遥感、医学诊断等。
举例:喝酒与练瑜伽的区别 喝酒与练瑜伽的作用是否相同是长期争论不休的一个问题,为此需要统计分析。 这是一个假设检验问题: H0 :喝酒= 练瑜伽 H1: 喝酒≠ 练瑜伽 现取5个样本进行检验。
喝酒2两=练瑜伽半年
喝酒5两=练瑜伽一年
喝酒1斤=练瑜伽5年
喝酒1近半=练瑜伽10年
喝酒2斤=瑜伽大师
结论: P值很大,无理由拒绝原假设。
Statistics are used much like a drunk uses a lamppost: for support, not illumination.
Pattern Classification Statistical Approach Non-Statistical Approach Supervised Unsupervised Decision-tree Basic concepts: Baysian decision rule (MPP, LR, Discri.) Basic concepts: Distance Agglomerative method Syntactic approach Parameter estimate (ML, BL) K-means Non-Parametric learning (kNN) Winner-take-all LDF (Perceptron) Kohonen maps NN (BP, Hopfield, DL) Support Vector Machine Dimensionality Reduction FLD, PCA Performance Evaluation ROC curve (TP, TN, FN, FP) cross validation Stochastic Methods local opt (GD) global opt (SA, GA) Classifier Fusion majority voting NB, BKS
什么是贝叶斯法则 统计学中有一个基本的工具叫贝叶斯法则、也称为贝叶斯公式。 如果你看到一个人总是做一些好事,则那个人多半会是一个好人。这就是说,当你不能准确知悉一个事物的本质时,你可以依靠与事物特定本质相关的事件出现的多少去判断其本质属性的概率。 用数学语言表达就是:支持某项属性的事件发生得愈多,则该属性成立的可能性就愈大。
应用一:S VM分类 支持向量机本身是一种监督式学习的方法,它广泛的应用于统计分类以及回归分析中。 通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,即支持向量机的学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。
线性分类 这里我们考虑的是一个两类的分类问题,数据点用 x 来表示,这是一个 n 维向量,w^T中的T代表转置,而类别用 y 来表示,可以取 1 或者 -1 ,分别代表两个不同的类。一个线性分类器的学习目标就是要在 n 维的数据空间中找到一个分类超平面,其方程可以表示为: 下面举个简单的例子,一个二维平面(一个超平面,在二维空间中的例子就是一条直线),如下图所示,平面上有两种不同的点,一种为红颜色的点,另一种则为蓝颜色的点,红颜色的线表示一个可行的超平面。
线性分类图示 从图中我们可以看出,这条红颜色的线把红颜色的点和蓝颜色的点分开来了。而这条红颜色的线就是我们上面所说的超平面。 超平面把这两种不同颜色的数据点分隔开来,在超平面一边的数据点所对应的 y 全是 -1 ,而在另一边全是 1 。
最大间隔分类器 对一个数据点进行分类,当它的 margin 越大的时候,分类的 confidence 越大。 对于一个包含 n 个点的数据集,为了使得分类的 confidence 高,我们希望所选择的超平面hyper plane 能够最大化这个 margin 值。
支持向量 由于这些 supporting vector 刚好在边界上,所以满足: 而对于所有不是支持向量的点,也就是在“阵地后方”的点,则有:
SVM原理 在线性不可分的情况下,支持向量机通过某种非线性映射(核函数)将输入变量映射到一个高维特征空间,在这个空间中构造最优分类超平面。 通过映射到高维特征空间,平面上不好分的非线性数据分开了。
核函数 通常人们会从一些常用的核函数中选择:多项式核、高斯核、线性核等。如下图所示,高斯核函数将低维线性不可分的数据映射到了高维空间。
举例 假设现在你是一个农场主,圈养了一批羊群,但为预防狼群袭击羊群,你需要搭建一个篱笆来把羊群围起来。但是篱笆应该建在哪里呢?你很可能需要依据牛群和狼群的位置建立一个“分类器”,比较下图这几种不同的分类器,我们可以看到SVM完成了一个很完美的解决方案。
SVM Packages Download: http://www.csie.ntu.edu.tw/~cjlin/libsvm/ Installation (Three choices) On Unix systems, type `make' to build the `svm-train' and `svm-predict‘ programs. On other systems, consult `Makefile' to build them Use the pre-built binaries (Windows binaries are in the directory ‘windows'). More details pls refer to the README file
林业管理问题应用举例 Research on the influential factors of forest farmers’ information technology adoption
Pattern Classification Statistical Approach Non-Statistical Approach Supervised Unsupervised Decision-tree Basic concepts: Baysian decision rule (MPP, LR, Discri.) Basic concepts: Distance Agglomerative method Syntactic approach Parameter estimate (ML, BL) K-means Non-Parametric learning (kNN) Winner-take-all LDF (Perceptron) Kohonen maps NN (BP, Hopfield, DL) Support Vector Machine Dimensionality Reduction FLD, PCA Performance Evaluation ROC curve (TP, TN, FN, FP) cross validation Stochastic Methods local opt (GD) global opt (SA, GA) Classifier Fusion majority voting NB, BKS
应用二:K-means聚类 与分类不同,聚类是把相似的东西分到一组。 对于一个 classifier ,通常需要你告诉它“这个东西被分为某某类”的一些例子,理想情况下,一个 classifier 会从它得到的训练集中进行“学习”,从而具备对未知数据进行分类的能力,这种提供训练数据的过程通常叫做 supervised learning (监督学习)。 而在聚类的时候,我们并不关心某一类是什么,我们需要实现的目标只是把相似的东西聚到一起,因此,一个聚类算法通常只需要知道如何计算相似度就可以了,因此 clustering 通常并不需要使用训练数据进行学习,这在 machine Learning 中被称作 unsupervised learning (无监督学习)。
K-means原理 A,B,C,D,E是五个待聚类的点,假设K=2,则随机在图中取2个种子点(灰色的点),以用来寻找点群。
Distance from Point to Cluster Euclidean distance(欧氏距离) Mahalanobis distance (马氏距离)
k-means聚类的弱点 The number of cluster, K, must be determined before hand. When the numbers of data are not so many, initial grouping will determine the cluster significantly. We never know which attribute contributes more to the grouping process since we assume that each attribute has the same weight. 。。。。。。
层次聚类 层次聚类,是一种很直观的算法。顾名思义就是要一层一层地进行聚类,可以从下而上地把小的cluster合并聚集,也可以从上而下地将大的cluster进行分割,用得比较多的是从下而上地聚集。 所谓从下而上地合并cluster,具体而言,就是每次找到距离最短的两个cluster,然后进行合并成一个大的cluster,直到全部合并为一个cluster。
层次聚类图示
Distance between Clusters Nearest neighbor measure Furthest neighbor measure
举例 dmin dmax A B C A B C
举例 1st col: three data sets 2nd col: dmin 3rd col: dmax
层次聚类+K-means聚类 先用层次聚类,然后用K-means聚类,是一种常见的聚类算法,其基本原理在于,用层次聚类算法得到初始化信息,比如可以分成多少个簇,中心点的位置信息等等,这样接下来可以利用这些信息来做K-means聚类。 这样的好处是可以解决K-means算法初始中心位置的随机性而且可以减少运算量,因为层次聚类的算法运算量太大无法运用于大规模数据。
林业管理问题应用举例 Forestry Farmers’ Information Demand Characteristics and Classification-Some Practical Views in Fujian Province of China
Pattern Classification Statistical Approach Non-Statistical Approach Supervised Unsupervised Decision-tree Basic concepts: Baysian decision rule (MPP, LR, Discri.) Basic concepts: Distance Agglomerative method Syntactic approach Parameter estimate (ML, BL) K-means Non-Parametric learning (kNN) Winner-take-all LDF (Perceptron) Kohonen maps NN (BP, Hopfield, DL) Support Vector Machine Dimensionality Reduction FLD, PCA Performance Evaluation ROC curve (TP, TN, FN, FP) cross validation Stochastic Methods local opt (GD) global opt (SA, GA) Classifier Fusion majority voting NB, BKS
应用三:FSM建模 有限状态自动机(FSM "finite state machine" 或者FSA "finite state automaton" )是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态,每个状态可以迁移到零个或多个状态,输入字串决定执行哪个状态的迁移。 有限状态自动机可以表示为一个有向图。有限状态自动机可以分为: 确定的有限状态自动机(DFA) 不确定的有限状态自动机(NFA)
有限状态系统实例 指针式钟表共有12*60*60个状态,每过一秒,钟表就从一种状态到另一种状态。 围棋共有3361个状态,每走一步棋就从一个状态到另一个状态。 电视开 电视关 打开 关闭
淘宝网上购物 顾客、店家和支付宝网三方之间的交互限于以下几种事件: 1、顾客告诉店家购买某种物品,决定预付款购物。 并将钱款转入支付宝。 2、店家送货给顾客。 3、顾客收到货后,可以选择: (1)确认付款(2)退货(3)换货 4、交易成功,支付宝将这笔钱转帐给店家的帐号。 以上的事件以及事件间在一定条件下转化的情况,可以表示成有限状态系统。
选物品 预付款 已购物 送货 已收货 换货 更换物品 选物品 已购物 确认付款 认可物品 转帐 交易结束 不认可物品 取消 选物品 预付款 已购物 确认付款 认可物品 退货 不认可物品 换货 取消
模型介绍 有限状态自动机(finite automaton,FA)是一个五元组: M=(Q,∑, q0,δ,F) Q——状态的非空有限集合。q∈Q,q为M的一个状态。 ∑——输入字母表。输入字符串都是∑上的字符串。 q0——q0∈Q,是M的开始状态(初始状态或者启动状态)。 δ——状态转移函数(转换函数或移动函数), δ:Q×∑Q,对(q,a)∈Q×∑,δ(q,a)=p表示:M在状态q读入字符a,将状态变成p,并将读头指向输入字符串的下一个字符。 F——FQ,是M的终止状态集合。 q∈F,q称M的终止状态(接受状态)。
M1=({q0,q1,q2},{0},δ1,q0,{q2}) 举例 有限状态自动机 M1=({q0,q1,q2},{0},δ1,q0,{q2}) 其中 :δ1(q0,0)= q1 δ1(q1,0)= q2, δ1(q2,0)= q1 S q0 q1 q2 识别 {(00)n|n>=1}
确定的有限自动机 对于任意的q∈Q, a∈∑,δ(q,a)均有确定的值,这种FA称为确定的有限状态自动机(deterministic finite automaton,DFA) 例:构造一个DFA,它接受的语言为{x000|x∈{0,1}*}。
不确定有限自动机 非确定的有限自动机(Nondeterministic Finite Automata)简记为NFA,是一个五元组 M=(Q,∑,δ,q0 , F),其中Q、∑、q0和F与确定的有限自动机的含意相同,只是转移函数δ不同,它是从Q×∑到2Q(Q的一切子集的集合)上的映射。 例:希望是接受{x|x∈{0,1}*,且x含有子串00或11}的FA。
NFA与DFA的区别 “NFA”与前面定义的DFA,的区别在于: ⑴ 并不是对于所有的(q,a)∈∑×Q,δ(q,a)都有一个状态与它对应;
林业管理问题应用举例 Research on the Implementation Strategy of Forest Insurance in China Based on Multi-agent Simulation
汇报完毕,请批评指正!