第6章 非监督学习方法

第6章非监督学习方法（聚类分析）基本概念分级聚类法C均值聚类法实验介绍6.1基本概念监督学习(SupervisedClassification)利用已知类别的样本进行训练非监督学习(NonsupervisedClassification)所用样本没有类别标志（本章主要研究）聚类分析按照物以类聚的思想，对未知类别的样本集根据样本之间的相似程度分类，相似的归为一类。6.1基本概念什么叫两个样本相似？模式的相似性测度相似到什么程度归为一类？聚类准则，聚类准则不同，分类结果也不同羊，狗金鱼，青蛙以胎生为准则聚类羊，狗金鱼青蛙以生存环境为准则聚类6.1基本概念模式相似性测度度量同一类样本间的类似性和不属于同一类样本间的差异性。1、距离度量欧氏距离：设为两个样本，则,ijxx1/221(,)()dijijijkkkDxxxxxx1(,)dijijkkkDxxxx街坊距离：6.1基本概念欧氏距离欧氏距离在使用中反映各特征分量的样本个数应均衡。例如，取5个样本，其中有4个反映对分类有意义的特征A，只有1个对分类有意义的特征B，欧氏距离的计算结果，则主要体现特征A。马氏距离马氏距离排除了不同特征之间相关性的影响。6.1基本概念距离测度的优缺点以距离作为测度具有平移不变性和旋转不变性，但不具尺度不变性。平移不变旋转不变6.1基本概念距离测度的优缺点不具有尺度不变性6.1基本概念2、角度测度cosScosTijijTTijijijijijxxxxxxxxxxxxxx由内积公式可定义，6.1基本概念角度测度具有尺度不变性和旋转不变性，不具有平移不变性。缺点：此时发生归为一类的错误6.2分级聚类法（系统聚类）非迭代的分级聚类算法聚类算法分类迭代的动态聚类算法聚类分析是把N个没有类别标志的样本分成若干类1NNN个样本分成类两种极端情况划分序列个样本分成类6.2分级聚类法（系统聚类）1x2x3x4x5x6x第一级第二级第三级第四级第五级第六级1020304080类间距离突然增大在此处停止聚类较合理缺陷：某一样本若在某级划分中归入了某一类，则在后面的划分中，它永远属于该类。6.2分级聚类法（系统聚类）分级聚类需要解决的两个问题聚类停止的两个可选条件如何定义类间距离？何时停止聚类？设定聚类类别数，达到则停止—类别数已知情况类间距离超过预定的阈值—类别数未知情况6.2分级聚类法（系统聚类）类间距离定义（区别于样本间距离）（1）最近距离(,)min(,)ijijxRyRRRDxyiRjR1x2x6.2分级聚类法（系统聚类）类间距离定义（区别于样本间距离）（2）最远距离（3）均值距离(,)max(,)ijijxRyRRRDxy(,)(,)ijijRRDmm选择不同的距离，可得到不同的聚类的结果，用不同的方法试一下，选一个合理的距离定义。6.2分级聚类法（系统聚类）,,1,2,,|(,)min(,)(3),(4)(2)jjjikjlikikiRjIINRjIRRRRRRRRRiIICCx(1)初始时，设置(2)在集合中找到一对满足条件的聚类和把并入去掉把从指标集中删除，若的基数等于，算法终止，否则转对应于聚为类的情况6.2分级聚类法（系统聚类）例：给出六个五维模式样本如下，按最小距离准则进行系统聚类分类并画出聚类过程树。最小距离准则指类间距离采用最小距离定义。1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,0x6.2分级聚类法（系统聚类）解：1.将每个样本看成一类，则有六类模式样本，即(0)(0)(0)(0)(0)(0)123456(0)1*(0)2(0)3(0)4(0)5(0)6003061501356076811041181421GGGGGGGGGGGG6.2分级聚类法（系统聚类）2.上表最小距离为，是与之间距离，合为一类，得(1)(1)(1)(1)(1)12345(1)1(1)2(1)3(1)4*(1)5060513086701481140GGGGGGGGGG3(0)1G(0)2G(1)12(1)3121323,,min(,)15,(,)6GxxGxxxxx6.2分级聚类法（系统聚类）3.上表最小距离为，合并与，得4(2)(2)(3)(4)1234(2)1(2)2*(2)3(2)406051308670GGGGGGGG(1)4G(1)5G6.2分级聚类法（系统聚类）4.上表最小距离，合并与，得(3)(3)(3)123(3)1*(3)2*(3)3060760GGGGGG系统聚类树5(2)1G(2)3G6.2C均值算法（动态聚类法）系统聚类缺陷系统聚类中如样本被划入某一类，则在以后各级划分中，样本始终属于该类，动态聚类可动态调整类属，是普遍采用的方法。动态聚类流程6.2C均值算法（动态聚类法）初始化聚类中心(1)根据具体问题，凭经验从样本集中选出C个比较合适的样本作为初始聚类中心。(2)用前C个样本作为初始聚类中心(3)将全部样本随机地分成C类，计算每类的样本均值，将样本均值作为初始聚类中心。6.2C均值算法（动态聚类法）初始聚类(1)按就近原则将样本归入各聚类中心所代表的类中。(2)取一样本，将其归入与其最近的聚类中心的那一类中，重新计算样本均值，更新聚类中心。然后取下一样本，重复操作，直至所有样本归入相应类中。6.2C均值算法（动态聚类法）聚类准则函数误差平方和准则函数211iiceiiiiJmNxxxmx最小方差划分算法步骤：已知样本集为（1）给定类别数C和允许误差Emax,k←1（2）初始化聚类中心（3）修正（4）修正聚类中心（5）计算误差，如eEmax，结束，否则转（3）6.2C均值算法（动态聚类法）(),1,2,,ikicm22()min()10=1,2,,;1,2,,jjilljikkdicjNxmxm其它11(1)/NNjijijijjkddmx21(1)()ciiiekkmm6.2C均值算法（动态聚类法）聚类结果单样本改进每调整一个样本的类别就重新计算一次各类的聚类中心1,jjiidx若22()min()10=1,2,,jjilljikkdicxmxm其它只调整一个样本6.2C均值算法（动态聚类法）聚类类别数的确定实验方法确定类别数如无拐点，此法失效根据知识判断（人为判断）本章小结分级聚类法C均值聚类法小结：非监督识别比监督识别存在更大不确定性，因训练样本类别未知，甚至聚类数也未知，可用信息大大减少，因此应注意利用专门领域的知识。K均值聚类算法（C均值）一、实验目的将模式识别方法与图像处理技术相结合，掌握利用K均值聚类算法进行图像分类的基本方法，通过实验加深对基本概念的理解。二、实验仪器设备及软件HPD538、MATLAB、WIT三、实验原理参照C均值动态聚类课堂笔记K均值聚类算法（C均值）四、实验步骤及程序理解K均值算法基本原理，编写程序实现对自选图像的分类，并将所得结果与WIT处理结果进行对比。实验程序附于实验报告。五、实验结果与分析以MATLAB和WIT分别实现K均值图像聚类算法，写明聚类类别数、聚类中心、迭代次数、运行时间，附原始图像和分类结果图像，并做实验分析。WIT简介WIT是一个图形编程环境，用于进行机器视觉应用的快速原型开发。WIT简介—开发方式图形化编程方式WIT简介—检测结果直线检测结果WIT简介—特性综合性图像处理库灵活的相机接口WIT引擎一种用作DLL和ActiveX组件的执行引擎，允许使用VB、VC定制GUI。多CPU执行：针对拥有多CPU的PCeWit：在联网PC上执行应用程序，分布式计算C代码生成算子开发工具WIT简介—图像处理库标准库滤波：低通、Sobel……形态分析：腐蚀、膨胀、骨架化、中值滤波……分割：阈值分割、C均值聚类、分水岭……几何分析：图像大小调整、旋转……颜色空间处理：RGB/HSV/YUV转换、通道拆分与合并……测量：点到线的距离、线与线的夹角……WIT简介—图像处理库标准库变换：FFT、DCT、Hough……统计：直方图计算、区域平均……边缘：边缘检测查找：模版匹配金字塔：Gauss金字塔、Burt金字塔……图像采集：搭配采集卡对象：访问各种元素控制：if-elseWIT简介—图像处理库Smart库搜索：高效匹配OCR：光学字符识别矩阵：一、二维条码测量：视觉测量、工业测量颜色分类：颜色识别线扫描：线扫描相机处理WIT程序设计方法启动WIT后按F2弹出算子选择窗口，输入算子名称或从列表中选择，双击将其放入工作区。WIT程序设计方法所有程序均以start算子开始WIT程序设计方法调入readImage算子以读取图像，以鼠标连接start算子与readImage算子。WIT程序设计方法右键单击readImage算子，弹出属性框，可选择图像。基于WIT的Kmeans算法基于WIT的Kmeans算法可利用直方图确定聚类类别数基于WIT的Kmeans算法属性中可选择初始聚类中心、聚类类别数、最大迭代次数。WIT在实验中的应用实验中使用DEMO版本，不能存储工程Kmeans算法程序事例位于wit\demo\Operators\Segmentation\kmeans.igrWIT程序结果用于与所设计程序进行对比