《第7章 模糊聚类分析.ppt》由会员分享，可在线阅读，更多相关《第7章 模糊聚类分析.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第章第章 模糊聚类分析模糊聚类分析 一、模糊聚类分析及其步骤一、模糊聚类分析及其步骤二、基于模糊等价关系的传递闭包法二、基于模糊等价关系的传递闭包法三、基于模糊相似关系的直接聚类法三、基于模糊相似关系的直接聚类法四、基于模糊四、基于模糊c-划分的模糊聚类法划分的模糊聚类法模糊聚类分析是一类应用很广泛的数学模糊聚类分析是一类应用很广泛的数学方法，就其理论来说，大致分为三种：方法，就其理论来说，大致分为三种：一是基于模糊等价关系的传递闭包法，一是基于模糊等价关系的传递闭包法，二是基于模糊相似关系的直接聚类法，二是基于模糊相似关系的直接聚类法，三是基于模糊三是基于模糊c-划分的模糊聚类法划分的模糊聚
2、类法。.1 模糊聚类分析及步骤模糊聚类分析及步骤数学上，把按一定要求和规律，对事物进行分类数学上，把按一定要求和规律，对事物进行分类数学上，把按一定要求和规律，对事物进行分类数学上，把按一定要求和规律，对事物进行分类的方法叫聚类分析，它属于数理统计多元分析的一的方法叫聚类分析，它属于数理统计多元分析的一的方法叫聚类分析，它属于数理统计多元分析的一的方法叫聚类分析，它属于数理统计多元分析的一支，是对清晰事物进行分类的一种方法，然而现实支，是对清晰事物进行分类的一种方法，然而现实支，是对清晰事物进行分类的一种方法，然而现实支，是对清晰事物进行分类的一种方法，然而现实生活中，事物间的界限往往不一定很
3、清晰，很多分生活中，事物间的界限往往不一定很清晰，很多分生活中，事物间的界限往往不一定很清晰，很多分生活中，事物间的界限往往不一定很清晰，很多分类问题，都多伴有模糊性，如天气，晴、阴、雨天类问题，都多伴有模糊性，如天气，晴、阴、雨天类问题，都多伴有模糊性，如天气，晴、阴、雨天类问题，都多伴有模糊性，如天气，晴、阴、雨天之间就无绝对的界限，普通的聚类分析对此是无能之间就无绝对的界限，普通的聚类分析对此是无能之间就无绝对的界限，普通的聚类分析对此是无能之间就无绝对的界限，普通的聚类分析对此是无能为力的；用模糊数学的语言和方法来描述和解决就为力的；用模糊数学的语言和方法来描述和解决就为力的；用模糊数
4、学的语言和方法来描述和解决就为力的；用模糊数学的语言和方法来描述和解决就成为自然和方便的了，这就产生了模糊聚类分析成为自然和方便的了，这就产生了模糊聚类分析成为自然和方便的了，这就产生了模糊聚类分析成为自然和方便的了，这就产生了模糊聚类分析模糊聚类分析的步骤：模糊聚类分析的步骤：模糊聚类分析的步骤：模糊聚类分析的步骤：一、选择统计指标一、选择统计指标一、选择统计指标一、选择统计指标根据实际问题，选择那些具有明确的意义，有较根据实际问题，选择那些具有明确的意义，有较根据实际问题，选择那些具有明确的意义，有较根据实际问题，选择那些具有明确的意义，有较强的分辨力和代表性的特征，作为分类事物的统计指强
5、的分辨力和代表性的特征，作为分类事物的统计指强的分辨力和代表性的特征，作为分类事物的统计指强的分辨力和代表性的特征，作为分类事物的统计指标，统计指标选择的如何，对分类结果有直接的影响；标，统计指标选择的如何，对分类结果有直接的影响；标，统计指标选择的如何，对分类结果有直接的影响；标，统计指标选择的如何，对分类结果有直接的影响；二、数据标准化（正规化）二、数据标准化（正规化）二、数据标准化（正规化）二、数据标准化（正规化）把代表事物各特征的统计指标的数据进行处理，使把代表事物各特征的统计指标的数据进行处理，使把代表事物各特征的统计指标的数据进行处理，使把代表事物各特征的统计指标的数据进行处理，使
6、之便于分析和比较，数据标准化可这样进行：令之便于分析和比较，数据标准化可这样进行：令之便于分析和比较，数据标准化可这样进行：令之便于分析和比较，数据标准化可这样进行：令其中其中其中其中x x原始数据，原始数据，原始数据，原始数据，为其的平均值，为其的平均值，为其的平均值，为其的平均值，为其标准差为其标准差为其标准差为其标准差三、标定三、标定三、标定三、标定所谓标定，就是根据实际情况，按一个准所谓标定，就是根据实际情况，按一个准所谓标定，就是根据实际情况，按一个准所谓标定，就是根据实际情况，按一个准或某种方法，给论域或某种方法，给论域或某种方法，给论域或某种方法，给论域 U U中的元素两两之间中
7、的元素两两之间中的元素两两之间中的元素两两之间都赋以都赋以都赋以都赋以0,10,1间的一个数，叫做相似系数，其大小表征间的一个数，叫做相似系数，其大小表征间的一个数，叫做相似系数，其大小表征间的一个数，叫做相似系数，其大小表征两个元素彼此接近或相似的程度；两个元素彼此接近或相似的程度；两个元素彼此接近或相似的程度；两个元素彼此接近或相似的程度；设设设设为待分事物的全体，为待分事物的全体，为待分事物的全体，为待分事物的全体，由一组数由一组数由一组数由一组数据据据据来表征，用来表征，用来表征，用来表征，用表示元素表示元素表示元素表示元素的相似的相似的相似的相似系数，系数，系数，系数，表示表示表示表
8、示截然不同，毫无相似截然不同，毫无相似截然不同，毫无相似截然不同，毫无相似之处；之处；之处；之处；表示表示表示表示完全相似或等同；当完全相似或等同；当完全相似或等同；当完全相似或等同；当i=ji=j时，时，时，时，就是就是就是就是和自己的相似程度，恒取和自己的相似程度，恒取和自己的相似程度，恒取和自己的相似程度，恒取1 1可据实际情况，选择下列方法之一来确定：可据实际情况，选择下列方法之一来确定：可据实际情况，选择下列方法之一来确定：可据实际情况，选择下列方法之一来确定：（1 1）数量乘积法）数量乘积法）数量乘积法）数量乘积法其中其中其中其中显然显然显然显然如果如果如果如果中出现负值，可采用下
9、面中出现负值，可采用下面中出现负值，可采用下面中出现负值，可采用下面方法将全体方法将全体方法将全体方法将全体进行调整进行调整进行调整进行调整.方法方法方法方法1.1.令令令令则则则则方法方法方法方法2.2.令令令令于是于是于是于是其中其中其中其中（2 2）夹角余弦法）夹角余弦法）夹角余弦法）夹角余弦法如果如果如果如果中出现负值，也可采用上面方法调整中出现负值，也可采用上面方法调整中出现负值，也可采用上面方法调整中出现负值，也可采用上面方法调整.（3 3）最大最小法）最大最小法）最大最小法）最大最小法（4 4）算术平均最小法）算术平均最小法）算术平均最小法）算术平均最小法（5 5）绝对值减数法）
10、绝对值减数法）绝对值减数法）绝对值减数法其中其中其中其中c c适当选取，使适当选取，使适当选取，使适当选取，使 在在在在0,10,1中且分散开中且分散开中且分散开中且分散开.后，后，后，后，其它方法请参阅教材！以上方法其它方法请参阅教材！以上方法其它方法请参阅教材！以上方法其它方法请参阅教材！以上方法究竟选哪一种，视问题实际特点而定，究竟选哪一种，视问题实际特点而定，究竟选哪一种，视问题实际特点而定，究竟选哪一种，视问题实际特点而定，通过标定求出相似系数通过标定求出相似系数通过标定求出相似系数通过标定求出相似系数可得模糊相似矩阵可得模糊相似矩阵可得模糊相似矩阵可得模糊相似矩阵四、聚类四、聚类四
11、、聚类四、聚类选择一种合适的聚类方法，便可以得到分类结果选择一种合适的聚类方法，便可以得到分类结果.2 基于模糊等价关系的传递闭包法基于模糊等价关系的传递闭包法一、传递闭包法一、传递闭包法一、传递闭包法一、传递闭包法BasicBasic idea:idea:据上面标定所得的模糊矩阵据上面标定所得的模糊矩阵R，求出其传递闭包求出其传递闭包为模糊等价矩阵，为模糊等价矩阵，然后由然后由3.4之方法，令之方法，令 从从1降到降到0，便可按需要，便可按需要对对U进行分类，这样的聚类方法，称进行分类，这样的聚类方法，称传递闭包法传递闭包法传递闭包法传递闭包法例例7.17.1 环境单元分类环境单元分类设设为
12、五个环境单元的集合，每个为五个环境单元的集合，每个环境单元有空气、水分、土壤、作物四个要素，环境环境单元有空气、水分、土壤、作物四个要素，环境单元的污染状况由污染物在四个要素中含量的超限度单元的污染状况由污染物在四个要素中含量的超限度来描述，若其污染数据为：来描述，若其污染数据为：试对试对U进进行分类行分类.解：解：解：解：（1）按）按绝对值减数绝对值减数法进行标定，如取法进行标定，如取c=0.1，则，则于是得模糊相似矩阵于是得模糊相似矩阵（2）用逐次平方法计算）用逐次平方法计算R的传递闭包的传递闭包因为因为所以传递闭包所以传递闭包然后依次取然后依次取 的截矩阵的截矩阵并按并按 将将U分成等价
13、类分成等价类.若若=1,便将便将U分为分为5类类,即即若若=0.8,便将便将U分为分为4类类,即即若若=0.6,便将便将U分为分为3类类,即即若若=0.5,便将便将U分为分为2类类,即即若若=0.4,便将便将U全归为为全归为为1类类,即即聚类图见教材聚类图见教材3.4图图3-3 二、最佳或值二、最佳或值二、最佳或值二、最佳或值 的确定的确定的确定的确定 聚类图给出各聚类图给出各聚类图给出各聚类图给出各 值对应的分类值对应的分类值对应的分类值对应的分类,形成一种动态聚形成一种动态聚形成一种动态聚形成一种动态聚类类类类,便于全面了解元素聚类便于全面了解元素聚类便于全面了解元素聚类便于全面了解元素聚
14、类,然后根据实际需要选然后根据实际需要选然后根据实际需要选然后根据实际需要选择其或值择其或值择其或值择其或值 便可确定一种分类便可确定一种分类便可确定一种分类便可确定一种分类,至于如何选择或值至于如何选择或值至于如何选择或值至于如何选择或值 ,使分类更合理使分类更合理使分类更合理使分类更合理,除了凭经验外除了凭经验外除了凭经验外除了凭经验外,还可用还可用还可用还可用F-F-统计统计统计统计量量量量来选取来选取来选取来选取.设设为待分事物的全体为待分事物的全体,为描述元素为描述元素 的第的第k个特征的数据个特征的数据,又设又设c为对应于为对应于 值的类数值的类数,为第为第i类元素的个数类元素的个
15、数,第第i类元素记为类元素记为记记为第为第i类元素第类元素第k个特征的平均值个特征的平均值,称称为第为第i 类的类的聚类中心向量聚类中心向量聚类中心向量聚类中心向量;为全体元素为全体元素的的中心向量中心向量中心向量中心向量,而而于是称于是称为为为为F-F-统计量统计量统计量统计量,其中其中为第为第i类中心类中心元素元素的距离的距离.例例7.2 气象预报中最佳或值的选取气象预报中最佳或值的选取(数据分析见教材数据分析见教材第第156页页).3 基于模糊相似关系的直接聚类法基于模糊相似关系的直接聚类法BasicBasic idea:idea:用传递闭包法分类需要先建立用传递闭包法分类需要先建立U
16、U上上的模糊等价矩阵的模糊等价矩阵,但矩阵阶数较高时但矩阵阶数较高时,计算便变得较计算便变得较困难困难.而采用相似矩阵而采用相似矩阵R R进行分类的进行分类的直接聚类法直接聚类法直接聚类法直接聚类法其计算其计算量则要小很多量则要小很多,这种方法聚类的原则是这种方法聚类的原则是:与与在在 水平上同类水平上同类在在R的图中的图中,存在一条权重存在一条权重不低于不低于 的路联结的路联结 与与直直直直接接接接聚聚聚聚类类类类法法法法最最最最大大大大树树树树法法法法编编编编网网网网法法法法画出以被分类元素为结点画出以被分类元素为结点,以相似矩阵以相似矩阵R的元的元 素素 为权重的一棵最大树为权重的一棵最
17、大树;取定取定0,1,砍断权重低于砍断权重低于 的枝的枝,得到一个得到一个不连通图不连通图,各连通分支便构成了在各连通分支便构成了在 水平上的分水平上的分类类对给定的模糊相似矩阵对给定的模糊相似矩阵R,取定水平取定水平0,1,作作截矩阵截矩阵R,在在R 主对角线上填入元素的符号主对角线上填入元素的符号,在在对角线下方以结点号对角线下方以结点号”*”代替代替1,而而”0”则略则略去不写去不写,由结点向主对角线上引经线和纬线由结点向主对角线上引经线和纬线,叫叫编网编网编网编网,由经纬线能相互连接起来的元素由经纬线能相互连接起来的元素,属于同属于同类类,从从实现了分类实现了分类.4 基于模糊基于模糊
18、c-划分的模糊聚类法划分的模糊聚类法一、一、一、一、c-c-划分划分划分划分1、普通集合上的、普通集合上的c-划分划分集合集合 上的上的c-c-划分划分划分划分是指是指U的的c个子集个子集满足：满足：记矩阵记矩阵其中其中若若(属于第属于第 i 类类);若若满足满足:(表示每个表示每个 属于且只属于某一类属于且只属于某一类)(表示每类表示每类 至少有一个元素至少有一个元素)反之反之,具有上述条件的矩阵具有上述条件的矩阵A对应着对应着U上的一个分类上的一个分类A称为集合称为集合U的一个的一个c-c-划分矩阵划分矩阵划分矩阵划分矩阵.如给定四元集如给定四元集U一一个分类结果个分类结果则对应分化矩阵为
19、则对应分化矩阵为若分类矩阵为若分类矩阵为则对应则对应U的分类的分类为为记记为为实矩阵的集合实矩阵的集合,且且称为将称为将U分成分成c类的类的分类空间分类空间分类空间分类空间.这样的分类是通这样的分类是通常意义下的分类常意义下的分类,称为称为硬分类硬分类硬分类硬分类.2、模糊、模糊c-划分划分设设一个一个模糊矩阵模糊矩阵若满足若满足:(表示每个表示每个 属于属于c个模糊子集个模糊子集 的的(表示每类表示每类 不等于不等于 或或U )的程度总和为的程度总和为1);则则A称为称为U的的模糊模糊模糊模糊c-c-划分矩阵划分矩阵划分矩阵划分矩阵,记记称为称为U U的的的的c c类软分类空间类软分类空间类
20、软分类空间类软分类空间.显然显然二、目标函数聚类法和硬二、目标函数聚类法和硬二、目标函数聚类法和硬二、目标函数聚类法和硬c-c-均值算法均值算法均值算法均值算法BasicBasic idea:idea:在目标函数法中在目标函数法中,目标函数是对给定目标函数是对给定c c的所有候选分类的所有候选分类进行度量进行度量,最优的类就是使目标函数达到局部最小的类最优的类就是使目标函数达到局部最小的类对于硬分类情形对于硬分类情形,目标函数一般选为总体组内误差平目标函数一般选为总体组内误差平方和方和.其定义如下其定义如下:其中其中 为为 中元素各特征分别取平均值后所得的聚类中元素各特征分别取平均值后所得的聚
21、类中心向量中心向量,也称也称 的聚类中心的聚类中心.类中元素向量和类中元素向量和类中元素个数类中元素个数记记V称为称为聚类中心矩阵聚类中心矩阵,若若 则则 到聚类中心到聚类中心的距离为的距离为 中全体元素到中心距离平方和为中全体元素到中心距离平方和为而而V中其它元素到其所在类中心距离平方和为中其它元素到其所在类中心距离平方和为Remark:Remark:最理想的最理想的c-c-划分应该是划分应该是J(A,V)J(A,V)取取极小的极小的A,A,寻找最小的寻找最小的A A并非易事并非易事,这是因为这是因为McMc的容量的容量虽有限但非常大虽有限但非常大,最常见的方法是最常见的方法是硬硬c-c-均
22、值算法均值算法:Step1 假设给出假设给出n n个数据点个数据点其中其中取定取定c(2cn),并并初始化初始化Step2 当迭代次数为当迭代次数为时时,计算聚类中计算聚类中心向量心向量其中其中Step3 用下式将用下式将更新为更新为其它其它和和Step4 比较比较若若(是一个非常小的常数是一个非常小的常数),则停止算法则停止算法;否则否则,令令返回返回Step2关于算法的使用说明关于算法的使用说明,见教材见教材164-165164-165页页!三、模糊三、模糊三、模糊三、模糊c-c-均值算法均值算法均值算法均值算法定义目标函数定义目标函数其中其中r1是一个加权指数是一个加权指数.BasicB
23、asic idea:idea:模糊模糊c-c-均值算法的目标在于找到均值算法的目标在于找到和和使得使得最小最小.下面的定理给出了上述最小化问题之必要条件下面的定理给出了上述最小化问题之必要条件定理定理 令令为一给定数据集为一给定数据集.设设和和假设对所有假设对所有1kn和和1ic,有有则仅则仅当当和和时时,和和才是才是的的局部最小值局部最小值.注注:模糊模糊c-c-均值算法是建立在定理必要条件均值算法是建立在定理必要条件()和和()的基础上的的基础上的,算法步骤如下算法步骤如下:Step1Step1 给定数据集给定数据集设定设定和和并初始化并初始化Step2Step2 当迭代次数为当迭代次数为
24、时时,计算聚类中计算聚类中心向量心向量Step3Step3 用下式将用下式将更新为更新为Step4Step4若若 则停止算法则停止算法;否则否则,令令返回返回Step2(是一个非常小的常数是一个非常小的常数),Remark:Remark:此算法也称为模糊此算法也称为模糊ISODATA方法方法.遇到只有一个样本的类遇到只有一个样本的类,要在聚类前先排除要在聚类前先排除,待聚待聚类类后再加上该类后再加上该类,而参数而参数r一般常取一般常取r=2.此算法要求此算法要求 ,因此取初始分类因此取初始分类 时时三、模糊划分清晰化三、模糊划分清晰化三、模糊划分清晰化三、模糊划分清晰化 实际问题中实际问题中,最后的分类结果都要求是明确的最后的分类结果都要求是明确的,因因此此,在使用模糊在使用模糊c-划分分类后划分分类后,都必须将模糊划分清都必须将模糊划分清晰化晰化,可用下述方法进行可用下述方法进行:方法方法I 对对若若则将则将归入归入类类.类类.方法方法II 对对若若归入归入则将则将关于算法的使用说明关于算法的使用说明,见教材见教材168-169168-169页页!例例7.3 模糊模糊ISODATA聚类算法的应用聚类算法的应用(教材第教材第169页页)例例7.4 应用模糊聚类分析对地下水位动态分类应用模糊聚类分析对地下水位动态分类(教材教材 第第170页页)