PD病症的综述课件

模式识别中的聚类分析

姓名：赵伟强学号：1212122947PD病症的综述与模式识别相关的学科统计学概率论线性代数（矩阵计算）形式语言机器学习人工智能图像处理计算机视觉…PD病症的综述教材/参考文献R.Duda,P.Hart,D.Stork,PatternClassification,secondedition,2000（有中译本）.边肇祺，模式识别（第二版），清华大学出版社，2000。蔡元龙，模式识别，西北电讯工程学院出版社，1986。PD病症的综述机构、会议、刊物1973年IEEE发起了第一次关于模式识别的国际会议“ICPR”（此后两年一次），成立了国际模式识别协会---“IAPR”1977年IEEE成立PAMI委员会，创立IEEETrans.onPAMI，并支持ICCV,CVPR两个会议其他刊物PatternRecognition(PR)PatternRecognitionLetters(PRL)PatternAnalysisandApplication(PAA)InternationalJournalofPatternRecognitionandArtificialIntelligence(IJPRAI)PD病症的综述第一章模式识别概论PD病症的综述什么是模式？广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。模式的直观特性:可观察性可区分性相似性PD病症的综述模式识别的概念模式识别–直观，无所不在，“人以类聚，物以群分”周围物体的认知：桌子、椅子人的识别：张三、李四声音的辨别：汽车、火车，狗叫、人语气味的分辨：炸带鱼、红烧肉人和动物的模式识别能力是极其平常的，但对计算机来说却是非常困难的。PD病症的综述模式识别的研究目的：利用计算机对物理对象进行分类，在错误概率最小的条件下，使识别的结果尽量与客观物体相符合。Y=F(X)X的定义域取自特征集Y的值域为类别的标号集F是模式识别的判别方法PD病症的综述模式识别简史1929年G.Tauschek发明阅读机，能够阅读0-9的数字。30年代Fisher提出统计分类理论，奠定了统计模式识别的基础。50年代NoamChemsky提出形式语言理论——傅京荪提出句法结构模式识别。60年代L.A.Zadeh提出了模糊集理论，模糊模式识别方法得以发展和应用。80年代以Hopfield网、BP网为代表的神经网络模型导致人工神经元网络复活，并在模式识别得到较广泛的应用。90年代小样本学习理论，支持向量机也受到了很大的重视。PD病症的综述模式识别的应用（举例）生物学自动细胞学、染色体特性研究、遗传研究天文学天文望远镜图像分析、自动光谱学经济学股票交易预测、企业行为分析医学心电图分析、脑电图分析、医学图像分析PD病症的综述模式识别的应用（举例）工程产品缺陷检测、特征识别、语音识别、自动导航系统、污染分析军事航空摄像分析、雷达和声纳信号检测和分类、自动目标识别安全指纹识别、人脸识别、监视和报警系统PD病症的综述模式识别方法模式识别系统的目标：在特征空间和解释空间之间找到一种映射关系，这种映射也称之为假说。特征空间：从模式得到的对分类有用的度量、属性或基元构成的空间。解释空间：将c个类别表示为 其中为所属类别的集合，称为解释空间。PD病症的综述假说的两种获得方法监督学习、概念驱动或归纳假说：在特征空间中找到一个与解释空间的结构相对应的假说。在给定模式下假定一个解决方案，任何在训练集中接近目标的假说也都必须在“未知”的样本上得到近似的结果。依靠已知所属类别的的训练样本集，按它们特征向量的分布来确定假说（通常为一个判别函数），只有在判别函数确定之后才能用它对未知的模式进行分类；对分类的模式要有足够的先验知识，通常需要采集足够数量的具有典型性的样本进行训练。PD病症的综述假说的两种获得方法（续）非监督学习、数据驱动或演绎假说：在解释空间中找到一个与特征空间的结构相对应的假说。这种方法试图找到一种只以特征空间中的相似关系为基础的有效假说。在没有先验知识的情况下，通常采用聚类分析方法，基于“物以类聚”的观点，用数学方法分析各特征向量之间的距离及分散情况；如果特征向量集聚集若干个群，可按群间距离远近把它们划分成类；这种按各类之间的亲疏程度的划分，若事先能知道应划分成几类，则可获得更好的分类结果。PD病症的综述模式分类的主要方法数据聚类统计分类结构模式识别神经网络PD病症的综述第二章聚类分析2.1聚类分析的相关概念2.2模式相似性的测度和聚类准则2.3基于试探的聚类搜索算法2.4系统聚类法2.5动态聚类法2.6聚类结果的评价PD病症的综述2.1聚类分析的相关概念定义 对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。PD病症的综述2.1聚类分析的相关概念模式相似/分类的依据 把整个模式样本集的特征向量看成是分布在特征空间中的一些点，点与点之间的距离即可作为模式相似性的测量依据。

聚类分析是按不同对象之间的差异，根据距离函数的规律（大小）进行模式分类的。PD病症的综述2.1聚类分析的相关概念聚类分析的有效性

聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。若向量点的分布是一群一群的，同一群样本密集（距离很近），不同群样本距离很远，则很容易聚类；若样本集的向量分布聚成一团，不同群的样本混在一起，则很难分类；对具体对象做聚类分析的关键是选取合适的特征。特征选取得好，向量分布容易区分，选取得不好，向量分布很难分开。PD病症的综述2.1聚类分析的相关概念两类模式分类的实例：一摊黑白围棋子选颜色作为特征进行分类，用“1”代表白，“0”代表黑，则很容易分类；选大小作为特征进行分类，则白子和黑子的特征相同，不能分类（把白子和黑子分开）。PD病症的综述2.1聚类分析的相关概念特征选择的维数

在特征选择中往往会选择一些多余的特征，它增加了维数，从而增加了聚类分析的复杂度，但对模式分类却没有提供多少有用的信息。在这种情况下，需要去掉相关程度过高的特征（进行降维处理）。降维方法结论：若rij->1，则表明第i维特征与第j维特征所反映的特征规律接近，因此可以略去其中的一个特征，或将它们合并为一个特征，从而使维数降低一维。PD病症的综述2.1聚类分析的相关概念模式对象特征测量的数字化 计算机只能处理离散的数值，因此根据识别对象的不同，要进行不同的数据化处理。连续量的量化：用连续量来度量的特性，如长度、重量、面积等等，仅需取其量化值；量级的数量化：度量时不需要详尽的数值，而是相应地划分成一些有次序的量化等级的值。病人的病程名义尺度：指定性的指标，即特征度量时没有数量关系，也没有明显的次序关系，如黑色和白色的关系，男性和女性的关系等，都可将它们分别用“0”和“1”来表示。超过2个状态时，可用多个数值表示。PD病症的综述2.2模式相似性的测度和聚类准则2.2.1相似性测度目的：为了能将模式集划分成不同的类别，必须定义一种相似性的测度，来度量同一类样本间的类似性和不属于同一类样本间的差异性。欧氏距离量纲对分类的影响（下页图例）公式:D=||x-z||例：x=(x1,x2),z=(z1,z2)马氏距离特点：排除了模式样本之间的相关性问题：协方差矩阵在实际应用中难以计算PD病症的综述2.2模式相似性的测度和聚类准则一般化的明氏距离公式：D(x,y)=它是欧氏距离的扩展，当m=2时，即为欧氏距离。角度相似性函数特点：反映了几何上相似形的特征，对于坐标系的旋转、放大和缩小等变化是不变的。PD病症的综述量纲对分类的影响（图例）PD病症的综述2.2模式相似性的测度和聚类准则2.2.2聚类准则 有了模式的相似性测度，还需要一种基于数值的聚类准则，能将相似的模式样本分在同一类，相异的模式样本分在不同的类。试探方法聚类准则函数法PD病症的综述2.2模式相似性的测度和聚类准则2.2.2聚类准则试探方法 凭直观感觉或经验，针对实际问题定义一种相似性测度的阈值，然后按最近邻规则指定某些模式样本属于某一个聚类类别。例如对欧氏距离，它反映了样本间的近邻性，但将一个样本分到不同类别中的哪一个时，还必须规定一个距离测度的阈值作为聚类的判别准则。PD病症的综述2.2模式相似性的测度和聚类准则2.2.2聚类准则聚类准则函数法依据：由于聚类是将样本进行分类以使类别间可分离性为最大，因此聚类准则应是反映类别间相似性或分离性的函数；由于类别是由一个个样本组成的，因此一般来说类别的可分离性和样本的可分离性是直接相关的；可以定义聚类准则函数为模式样本集{x}和模式类别{Sj,j=1,2,…,c}的函数，从而使聚类分析转化为寻找准则函数极值的最优化问题。PD病症的综述2.2模式相似性的测度和聚类准则2.2.2聚类准则聚类准则函数法一种聚类准则函数J的定义c为聚类类别的数目，Sj第j个类别样本的集合mj为属于Sj集合的样本的均值向量,

Nj为Sj中的样本数目PD病症的综述2.2模式相似性的测度和聚类准则以均值向量mj为sj中样本的代表，用均值来代表每个样本的中心。同一类局的越紧密，函数值J就越小。J代表了属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。对于不同的聚类形式，J值是不同的。目的：求取使J值达到最小的聚类形式。PD病症的综述2.3基于试探的聚类搜索算法2.3.1按最近邻规则的简单试探法算法:给定N个分类的模式样本{x1,x2,…,xN},要求按距离阈值T，将它们分到聚类中心z1,z2,…。第一步：任取一样本x1作为一个聚焦中心的初始值，令z1=x1,计算D21=||x2-z1||,若D21>T,则确定一个新的聚类中心z2=x2;否则x2属于以z1为中心的聚类。第二步：假设已有聚类中心z1,z2,计算D31=||x3-z1||,D32=||x3-z2||,若D31>T且D32>T,则得一个新的聚类中心z3=x3,否则x3属于离z1和z2中的最近者。……如此重复下去，直至将N个模式样本分类完毕。

PD病症的综述2.3基于试探的聚类搜索算法2.3.1按最近邻规则的简单试探法讨论在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，所以这种方法在很大程度上依赖于以下因素：第一个聚类中心的位置待分类模式样本的排列次序距离阈值T的大小样本分布的几何性质PD病症的综述2.3基于试探的聚类搜索算法2.3.1按最近邻规则的简单试探法讨论距离阈值T对聚类结果的影响PD病症的综述2.3基于试探的聚类搜索算法2.3.2最大最小距离算法基本思想：以试探类间欧氏距离为最大作为预选出聚类中心的条件。PD病症的综述2.3基于试探的聚类搜索算法2.3.2最大最小距离算法算法（实例）：有10个模式识别样本点：第一步：任选一个模式样本点作为第一聚类中心，如z1=x1.第二步：选距离z1最远的点作为下一个聚类中心。经计算，||x6-z1||最大，所以z2=x6。第三步：逐个计算各模式样本{xi,i=1,2,…,N}与{z1,z2}之间的距离，即Di1=||xi-z1||,Di2=||xi-z2||并选出其中最小的距离min(Di1,Di2),i=1,2,…,NPD病症的综述2.3基于试探的聚类搜索算法第四步：在所有模式样本最小值中选出最大距离，若该最大值达到||z1-z2||的一定比例以上，则相应的基本点取为第三个聚类中心z3,即若max{min(Di1,Di2),i=1,2,…,N}>θ||z1-z2||,则z3=xr,否则，若找不到适合要求的样本作为新的聚类中心，则找聚类中心的过程结束这里，θ可用试探法取一固定分数，如1/2。在此例中，当k=7时，符合上述条件，故z3=x7。第五步：若有z3存在，则计算max{min(Di1,Di2),i=1,2,…,N}.若该值超过||z1-z2||的一定比例，则存在z4,否则找聚类中心的过程结束。在此例中，无z4满足条件。第六步：将模式样本{xi,i=1,2,…,N}按最近距离分到最近的聚类中心。最后，还可以在每一类中计算各样本的均值得到更具代表性的聚类中心。PD病症的综述2.4系统聚类法基本思想 将模式样本按距离准则逐步分类，类别由多到少，直到获得合适的分类要求为止。PD病症的综述2.4系统聚类法算法：第一步：设初始模式样本共有N个，每个样本自成一类，即建立N类，G(0)1,G(0)2,…,G(0)N,计算各类间的距离。得到一个N*N维的距离矩阵D(0).这里，标号（0）表示聚类开始运算前的状态。第二步:假设千亿布局类运算中已求得距离矩阵D(n),n为逐次聚类合并的次数，则求D(n)中的最小元素。如果他是G(n)i和G(n)j两类之间的距离，则将G(n)i和G(n)j两类合并为一类G(n+1)m,由此建立新的分类：G(n+1)1,G(n+1)2,…第三步：计算合并后新类别之间的距离，得D(n+1),计算G(n+1)m与其它没有发生合并的G(n+1)1,G(n+1)2,…之间的