第7章-模糊聚类分析

第７章模糊聚类分析一、模糊聚类分析及其步骤二、基于模糊等价关系的传递闭包法三、基于模糊相似关系的直接聚类法四、基于模糊c-划分的模糊聚类法模糊聚类分析是一类应用很广泛的数学方法，就其理论来说，大致分为三种：一是基于模糊等价关系的传递闭包法，二是基于模糊相似关系的直接聚类法，三是基于模糊c-划分的模糊聚类法。§７.1模糊聚类分析及步骤数学上，把按一定要求和规律，对事物进行分类的方法叫聚类分析，它属于数理统计多元分析的一支，是对清晰事物进行分类的一种方法，然而现实生活中，事物间的界限往往不一定很清晰，很多分类问题，都多伴有模糊性，如天气，晴、阴、雨天之间就无绝对的界限，普通的聚类分析对此是无能为力的；用模糊数学的语言和方法来描述和解决就成为自然和方便的了，这就产生了模糊聚类分析模糊聚类分析的步骤：一、选择统计指标根据实际问题，选择那些具有明确的意义，有较强的分辨力和代表性的特征，作为分类事物的统计指标，统计指标选择的如何，对分类结果有直接的影响；二、数据标准化（正规化）把代表事物各特征的统计指标的数据进行处理，使之便于分析和比较，数据标准化可这样进行：令xxx其中x原始数据，x为其的平均值，为其标准差三、标定所谓标定，就是根据实际情况，按一个准则或某种方法，给论域U中的元素两两之间都赋以[0,1]间的一个数，叫做相似系数，其大小表征两个元素彼此接近或相似的程度；设12{,,...,}nUuuu为待分事物的全体，iu由一组数据12,,...,iiinxxx来表征，用ijr表示元素,ijuu的相似系数，01,ijr0ijr表示,ijuu截然不同，毫无相似之处；1ijr表示,ijuu完全相似或等同；当i=j时，ijr就是iu和自己的相似程度，恒取1ijr可据实际情况，选择下列方法之一来确定：（1）数量乘积法11,1,mijikjkkijrxxijM其中1max()mijjkijkMxx显然01,ijr如果ijr中出现负值，可采用下面方法将全体ijr进行调整.方法1.令1,2ijijrr则[0,1]ijr方法2.令(),ijijrmrijMm[0,1]ijrmax,ijijMr于是其中min,ijijmr（2）夹角余弦法12211mikjkkijmmikjkkkxxrxx如果ijr中出现负值，也可采用上面方法调整.（3）最大最小法11()()mikjkkijmikjkkxxrxx（4）算术平均最小法112()()mikjkkijmikjkkxxrxx（5）绝对值减数法11mijikjkkrcxx其中c适当选取，使在[0,1]中且分散开.ijr后，其它方法请参阅教材！以上方法究竟选哪一种，视问题实际特点而定，通过标定求出相似系数ijr可得模糊相似矩阵()ijRr四、聚类选择一种合适的聚类方法，便可以得到分类结果.§７.2基于模糊等价关系的传递闭包法一、传递闭包法Basicidea:据上面标定所得的模糊矩阵R，求出其传递闭包(),tR()RtR为模糊等价矩阵，然后由§3.4之方法，令从1降到0，便可按需要对U进行分类，这样的聚类方法，称传递闭包法例7.1环境单元分类设12{,,...,}nUuuu为五个环境单元的集合，每个环境单元有空气、水分、土壤、作物四个要素，环境单元的污染状况由污染物在四个要素中含量的超限度来描述，若其污染数据为：1(5,5,3,2),u2(2,3,4,5),u3(5,5,2,3),u4(1,5,3,1),u5(2,4,5,1),u试对U进行分类.解：（1）按绝对值减数法进行标定，如取c=0.1，则4110.1ijikjkkrxx于是得模糊相似矩阵10.10.80.50.30.110.10.20.40.80.110.30.10.50.20.310.60.30.40.10.61R（2）用逐次平方法计算R的传递闭包(),tRR因为210.30.80.50.50.310.20.40.40.80.210.30.10.50.40.510.60.50.40.30.61RR4210.40.80.50.50.410.40.40.40.80.410.50.50.50.40.510.60.50.40.50.61RR8410.40.80.50.50.410.40.40.40.80.410.50.50.50.40.510.60.50.40.50.61RR所以传递闭包4,RR然后依次取的截矩阵,R并按将U分成等价类.R若=1,便将U分为5类,即12345{},{},{},{},{};uuuuu若=0.8,便将U分为4类,即13245{,},{},{},{};uuuuu若=0.6,便将U分为3类,即13245{,},{},{,};uuuuu若=0.5,便将U分为2类,即12342{,,,},{};uuuuu若=0.4,便将U全归为为1类,即12345{,,,,}uuuuu聚类图见教材§3.4图3-3二、最佳阈值的确定聚类图给出各值对应的分类,形成一种动态聚类,便于全面了解元素聚类,然后根据实际需要选择其或值便可确定一种分类,至于如何选择阈值,使分类更合理,除了凭经验外,还可用F-统计量来选取.设12{,,...,}nUuuu为待分事物的全体,1(,jjux2,,),jjmjkxxx为描述元素的第k个特征的数据,ju又设c为对应于值的类数,为第i类元素的个数,in第i类元素记为1,,,iiinuu记11inikjkjixxn(1,,)km为第i类元素第k个特征的平均值,称1(,,)iiimuxx为第i类的聚类中心向量;1(,,)muxx为全体元素的中心向量,而11,nkjkjxxn1,,,km于是称22111()/()(1)()iiiinccijiiijnuunuuFcnc为F-统计量,其中21()miikkkuuxx为第i类中心,iijuu元素的距离.例7.2气象预报中最佳或值的选取(数据分析见教材第156页)§７.3基于模糊相似关系的直接聚类法Basicidea:用传递闭包法分类需要先建立U上的模糊等价矩阵,但矩阵阶数较高时,计算便变得较困难.而采用相似矩阵R进行分类的直接聚类法其计算量则要小很多,这种方法聚类的原则是:juiu与在水平上同类在R的图中,存在一条权重不低于的路联结与iuju直接聚类法最大树法编网法①画出以被分类元素为结点,以相似矩阵R的元素为权重的一棵最大树;②取定[0,1],砍断权重低于的枝,得到一个不连通图,各连通分支便构成了在水平上的分类ijr对给定的模糊相似矩阵R,取定水平[0,1],作截矩阵R,在R主对角线上填入元素的符号,在对角线下方以结点号”*”代替1,而”0”则略去不写,由结点向主对角线上引经线和纬线,叫编网,由经纬线能相互连接起来的元素,属于同类,从实现了分类§７.4基于模糊c-划分的模糊聚类法一、c-划分1、普通集合上的c-划分集合上的c-划分是指U的c个子集12{,,...,}nUuuu{:1,,}(2),iAiccn满足：①1;niiAU②ijAA()ij记矩阵12()(,,,),TijcncAaAAA其中1,ija若jiuA(属于第i类);ju0,ija若jiuA满足:⑴1,1cijija(表示每个属于且只属于某一类)ju1,0nijjian⑵(表示每类至少有一个元素)iA反之,具有上述条件的矩阵A对应着U上的一个分类A称为集合U的一个c-划分矩阵.如给定四元集U一个分类结果1234{},{,},{},uuuu则对应分化矩阵为100001100001A1u2u3u4u123若分类矩阵为10000100,0011A则对应U的分类为1234{},{},{,}.uuuu记cn为cn实矩阵的集合,且11{(),{0,1},1,0}cncijcnijijijijMAAaaaan称为将U分成c类的分类空间.这样的分类是通cM常意义下的分类,称为硬分类.2、模糊c-划分设12{,,...,},nUuuu12(,,,),jjjjmuxxx一个cn模糊矩阵11112122222212nncccncAaaaAaaaAaaaA若满足:⑴1,1cijija(表示每个属于c个模糊子集的juiA1,0nijjian⑵(表示每类不等于或U)iA的程度总和为1);则A称为U的模糊c-划分矩阵,记11{(),[0,1],1,0}cnfcijcnijijijijMAAaaaanfcM称为U的c类软分类空间.显然cfcMM二、目标函数聚类法和硬c-均值算法Basicidea:在目标函数法中,目标函数是对给定c的所有候选分类进行度量,最优的类就是使目标函数达到局部最小的类对于硬分类情形,目标函数一般选为总体组内误差平方和.其定义如下:211(,)cnijjiijJAVauv其中为中元素各特征分别取平均值后所得的聚类iviA中心向量,也称的聚类中心.iAiv11nijjjnijjaua类中元素向量和iA类中元素个数iA记11112122122212mmncccmvvvvvvvvVvvvvV称为聚类中心矩阵,若则到聚类中心,jiuAjuiv的距离为21()mijjijkikkduvxv中全体元素到中心距离平方和为iA21()nijijjad而V中其它元素到其所在类中心距离平方和为211(,)()cnijijijJAVad211cnijjiijauvRemark:最理想的c-划分应该是J(A,V)取极小的A,寻找最小的A并非易事,这是因为Mc的容量虽有限但非常大,最常见的方法是硬c-均值算法:Step1假设给出n个数据点12{,,...,},nUuuu其中12(,,,).mjjjjmuxxxR取定c(2≤c≤n),并初始化(0).cAMStep2当迭代次数为(0,1,2,)ll时,计算聚类中心向量()1()()1nlijjjlinlijjauva其中()()(),1,2,,llijaAicStep3用下式将()lA更新为(1)(1)()llijAa(1)10lija()()1min()lljijiicuvuv其它和Step4比较()lA(1),lA若(1)(1)llAA(是一个非常小的常数),则停止算法;否则,令1,ll返回Step2关于算法的使用说明,见教材164-165页!三、模糊c-均值算法定义目标函数211(,)()cnrmijjiijJAVauv其中r≥1是一个加权指数.Basicidea:模糊c-均值算法的目标在于找到()ijfcAaM和12(,,,)(),mcivvvvvR使得(,)mJAV最小.下面的定理给出了上述最小化问题之必要条件定理令12{,,...,},nUuuu12(,,,)mjjjjmuxxxR为一给定数据集.设{2,3,,1}cn和(1,),r假设对所有1≤k≤n和1≤i≤c,有0,jiuv则仅当2111,1,1ijrcjijjjaicjnuvuv和11,1nijjjinijjauvica时,()ijAa和12(,,,)cVvvv才是(,)mJAV的局部最小值.注:模糊c-均值算