第4章 模糊关系与聚类分析 2017/3/1.

Presentation on theme: "第4章 模糊关系与聚类分析 2017/3/1."— Presentation transcript:

1 第4章 模糊关系与聚类分析 2017/3/1

2 本章内容 4.1 模糊关系 4.2 模糊等价关系 4.3 聚类分析 分类是事先有类，来了一个新的元素，判断它应该属于哪个类。这是类似于模式识别的范畴。 聚类是事先没有类，只有若干元素以及其对应的数据信息，要求按照彼此的关系将其分成若干类。 2017/3/1

3 模糊关系的三个性质 自反性 对称性 传递性 2017/3/1

4 自反性 若模糊关系R满足R(u,u)=1或I⊆R，则称R具有自反性 模糊自反矩阵 rii = 1 例如： 2017/3/1

5 自反矩阵的定理 定理. 设模糊矩阵 A ∈Mn×n是自反矩阵，则有 I ⊆ A⊆A2 ⊆ A3 ⊆…⊆ An-1 ⊆An⊆… 证明:
2017/3/1

6 对称性 若模糊关系R满足R(u,v)=R(v,u)，则称R具有对称性 模糊对称矩阵 rij = rji 例如： 2017/3/1

7 传递性 若模糊关系R满足RоR⊆R，则称R具有传递性 模糊传递矩阵 2017/3/1

8 模糊传递矩阵——例 2017/3/1

9 模糊传递矩阵的定理 定理. 设模糊矩阵 Q ∈Mn×n是传递矩阵，则有 Q ⊇Q2 ⊇ Q3 ⊇… ⊇Qn-1 ⊇Qn ⊇… 证明:
2017/3/1

10 模糊等价关系 定义. 模糊关系R∈F(U×U) , 满足 （1）自反性：R (u,u)=1; （2）对称性：R(u,v)=R(v,u);
（3）传递性：R2 ⊆R 则称R为模糊等价关系 2017/3/1

11 模糊等价矩阵 模糊等价矩阵 自反性 rii = 1 对称性 rij = rji 传递性
若论域U是有限论域，则U上的模糊等价关系R可表示为模糊等价矩阵 模糊等价矩阵 自反性 rii = 1 对称性 rij = rji 传递性 2017/3/1

12 R是否为模糊等价矩阵？ 2017/3/1

13 等价布尔关系 一个布尔矩阵具有如下特性，则称其为等价的布尔矩阵，对应一个普通的等价关系 自反性 对称性 传递性 2017/3/1

14 模糊等价矩阵的性质 若R为模糊等价矩阵，则 R= R2 = R3 = … = Rn-1 = Rn 证明：
意味着无论合成多少次，都没有变化 2017/3/1

15 模糊等价矩阵的定理1 定理1. R是模糊等价矩阵⇔ 对于任何λ∈[0,1]，Rλ是等价布尔矩阵。 证明： 对称性、自反性显然 传递性
给出证明 2017/3/1

16 定理1的意义 模糊等价矩阵普通等价矩阵 普通等价矩阵⇔普通等价关系 普通等价关系可以分类
当λ在[0,1]上变动时，得到不同的Rλ, 从而得到不同的分类 2017/3/1

17 模糊等价矩阵分类——例 设X={x1, x2, x3 ,x4, x5 } 求当λ ＝1, 0.8, 0.6, 0.5, 0.4时的聚类结果。
2017/3/1

18 λ ＝1 利用λ ＝1时的截关系，将X分成5个等价类： {x1}, {x2}, {x3}, {x4}, {x5} 2017/3/1

19 λ ＝0.8 利用λ ＝0.8时的截关系，将X分成4个等价类： {x1, x3}, {x2}, {x4}, {x5} 2017/3/1

20 λ ＝0.6 利用λ ＝0.6时的截关系，将X分成3个等价类： {x1, x3}, {x2}, {x4, x5} 2017/3/1

21 λ ＝0.5 利用λ ＝0.5时的截关系，将X分成2个等价类： {x1, x3, x4, x5}, {x2} 2017/3/1

22 λ ＝0.4 利用λ ＝0.4时的截关系，将X分成1个等价类： {x1, x2, x3, x4, x5} 2017/3/1

23 动态聚类图 λ由1变到0，Rλ的分类由细到粗 x1 x2 x3 x4 x5 λ =1 λ =0.8 λ =0.6 λ =0.5 λ =0.4
这里要说明一下，所谓λ=0.4，是指在[0,0.4]上 2017/3/1

24 模糊等价矩阵的定理2 定理2. R ∈ μn×n是模糊等价矩阵，则对于任何λ,μ ∈[0,1]，且λ<μ，Rμ所决定的分类中的每个类都是Rλ所决定的分类中的某个类的子类。 说明什么？ λ越大，分类越细 2017/3/1

25 动态聚类图 λ由1变到0的过程，是Rλ的分类由细到粗的过程，从而形成了一个动态的聚类图。 x1 x2 x3 x4 x5 λ =1
λ =0.8 λ =0.4 λ =0.6 λ =0.5 这里要说明一下，所谓λ=0.4，是指在[0,0.4]上 2017/3/1

26 模糊相似关系 2017/3/1

27 模糊相似关系的定义 设R∈F(U×U)，若R具有自反性和对称性，则称R为U上的一个模糊相似关系 例如：模糊关系“彼此熟悉”、“朋友”等
模糊相似关系vs.模糊等价关系 没有了传递性的要求 2017/3/1

28 为何研究模糊相似关系？ 实际应用中，通常只能得到自反和对称矩阵（相似矩阵），模糊等价矩阵较为少见 Questions.
对具有相似关系的元素如何分类？ 相似矩阵可否改造为等价矩阵？ 2017/3/1

29 概念——传递闭包 设A, Â, B∈F(U×U)，若Â为包含A的传递关系(即A⊆Â且Â2⊆ Â)，且对于任何包含A的传递关系B，都有Â⊆B，则称Â为A的传递闭包，记为t(A)= Â . 之前讲过对称闭包 R的传递闭包t(R)是包含R的最小的传递关系 2017/3/1

30 传递闭包的定理1 定理1. 设模糊矩阵 A ∈ μn×n ，则A的传递闭包t(A)是 2017/3/1

31 传递闭包定理1证明 1) 包含 2)传递性 3) 最小 2017/3/1

32 传递闭包的定理2 定理2. 设模糊矩阵 A ∈ μn×n ，则 其中，t(A)是传递闭包。 定理2说明，至多做n次并操作，就可以得到传递闭包
2017/3/1

33 定理2的意义 定理2说明，当R是n阶方阵时，至多用n次并运算，就可以得到R的传递闭包 定理2极大地简化了传递闭包的计算 2017/3/1

34 传递闭包的定理3 定理3. 相似矩阵R∈μn×n 的传递闭包是等价矩阵，且t(R)=Rn 证明：只需证明自反性和对称性
1) R自反⇒ I ⊆ R⊆R2 ⊆ … ⊆Rn ⇒t(R)=∪k=1n Rk= Rn是自反的 2) 对称性。R= RT⇒(Rn)T= (RT)n = (Rn) 2017/3/1

35 传递闭包的定理4 定理4. 设R∈μn×n 为相似矩阵。则对于任意自然数m≥n, 都有t(R)=Rm
证明： R自反=> I ⊆ R⊆R2 ⊆… ⊆Rn t(R)=Rn ⊆Rm ⊆ ∪k=1∞ Rk=t(R) 2017/3/1

36 模糊相似矩阵模糊等价矩阵 将相似矩阵改造成等价矩阵 只需求相似矩阵的传递闭包 2017/3/1

37 传递闭包的定理5 定理5. 设R∈μn×n 是模糊相似矩阵，则存在一个最小自然数k (k≤n)，使得传递闭包t(R)=Rk，对于任何自然数b≥k，都有Rb=Rk，此时，t(R)是模糊等价矩阵。 2017/3/1

38 平方法求传递闭包 从模糊相似矩阵R出发，依次求平 方： 当第一次出现Rk ◦Rk =Rk时， Rk就是 所求的传递闭包t(R)
问：这里至多求多少步，可以得到传递闭包？ 2017/3/1

39 时间复杂度 如果超出n了，说明一定到了，都无需再做下一步 2017/3/1

40 课堂作业 2017/3/1

41 课堂作业4-1 设 请问至多几次平方可以到达传递闭包？ 请给出传递闭包t(R) 2017/3/1

42 课堂作业4-2 证明：若Q,R是传递的，则Q∩R也是传递的. 2017/3/1

43 本章内容 4.1 模糊关系 4.2 模糊等价关系 4.3 聚类分析 分类是事先有类，来了一个新的元素，判断它应该属于哪个类。这是类似于模式识别的范畴。 聚类是事先没有类，只有若干元素以及其对应的数据信息，要求按照彼此的关系将其分成若干类。 2017/3/1

44 4-3 聚类分析 2017/3/1

45 聚类分析 聚类分析是把对象自动划分成多个类簇，使得同类簇内对象相近、异类簇间对象相异；
聚类分析对于发现数据的隐含模式、获取知识、预测数据的功能或行为等，具有十分重要的意义。 移动通信网客户聚类 蛋白质聚类 图像像素点聚类 A person dies of rabies almost every 10 minutes. 2017/3/1 45

46 聚类分析与模式分类的区别： 模式分类是已知若干模式，要求我们正确判断当前的新样本属于哪个模式；
聚类分析所讨论的对象是一大批样本，事先没有给定任何模式供参考，要求我们按样本各自的属性值加以分类。 从机器学习的角度来看，分类是有监督学习，聚类是无监督学习。 2017/3/1

47 聚类分析方法 （1）层次聚类算法：通过数据的分裂或聚合，以形成层次类簇。适用于小规模数据集。
简单说，聚类分析就是用数学方法对事物进行分类。通过适当聚类，事物便于研究，事物的内部规律容易为人类所掌握。现有方法主要有： （1）层次聚类算法：通过数据的分裂或聚合，以形成层次类簇。适用于小规模数据集。 （2）划分式聚类：事先指定类簇数或类簇中心，通过反复迭代，逐步降低目标函数的值。当目标函数收敛时，得到最终类簇。 （3）基于密度和网格的聚类：通过密度或网格发现类簇。适用于大规模数据集。 2017/3/1

48 模糊聚类分析 模糊数学产生之前，聚类分析是数理统计多元分析的一个分支。
现实分类问题往往具有模糊性，例如“环境污染分类”、“临床症状资料分类”、“岩石分类”等等，因此，用模糊数学语言进行模糊聚类分析更为自然。 2017/3/1

49 基于模糊等价矩阵的聚类分析方法 2017/3/1

50 基于模糊等价矩阵的聚类分析步骤 第一步：建立模糊矩阵 ； 第二步：建立模糊等价矩阵； 第三步：聚类（求动态聚类图） 2017/3/1

51 第一步：建立模糊矩阵 设U ={u1, u2, …, un }为待分类的全体对象，其中每个待分类对象由一组数据表征如下：
问题转化为：如何建立对象ui与uj之间的相似关系 2017/3/1

52 例1——环境污染 例如，要对一些环境单元进行聚类，判断它们的污染程度 每个环境单元包括四个要素：空气、水分、土壤、作物
环境单元的污染状况由污染物在四个要素中含量的超限度来描述 2017/3/1

53 现有5个污染单元， U={Ⅰ,Ⅱ,Ⅲ,Ⅳ,Ⅴ} 它们的污染数据如下: Ⅰ=(5,5,3,2),Ⅱ=(2,3,4,5),
Ⅲ=(5,5,2,3),Ⅳ=(1,5,3,1), Ⅴ=(2,4,5,1) 最大绝对值差做和得到的是9，因此c=0.1没问题 2017/3/1

54 建立模糊矩阵 如何建立对象ui与uj之间的相似关系？
有许多方法，应用时根据实际情况，选择一种方法来求ui与uj的相似关系R(ui, uj)=rij 在“环境污染”的例子中，如何给出模糊相似矩阵？ 2017/3/1

55 建立模糊相似矩阵 建立模糊相似矩阵的注意事项： rij∈[0,1] 自反 对称 “环境”例中，采用“绝对值减数法”
问：得到的相似矩阵的维数是多少？ 问： 2017/3/1

56 模糊相似矩阵 2017/3/1

57 步骤2：相似关系等价关系 步骤1得到的矩阵一般满足自反性和对称性 将模糊相似矩阵改造成模糊等价矩阵 平方法 求传递闭包 2017/3/1

58 至多计算多少次？ 模糊相似矩阵5×5 k=[log25]+1=2+1=3 最坏情况下，RR2R4R8，计算到R8 2017/3/1

59 2017/3/1

60 模糊等价矩阵 观察该矩阵，一共只有0.4,0.5,0.6,0.8,1，我们以0.5为例，可以发现5个环境单元共分成2类，1345在一类，2自成一类 2017/3/1

61 步骤3：聚类 R的传递闭包t(R)=R4 对于t(R)，依次取截关系 2017/3/1

62 λ ＝1 利用λ ＝1时的截关系，将X分成5个等价类： {x1}, {x2}, {x3}, {x4}, {x5} 2017/3/1

63 λ ＝0.8 利用λ ＝0.8时的截关系，将X分成4个等价类： {x1, x3}, {x2}, {x4}, {x5} 2017/3/1

64 λ ＝0.6 利用λ ＝0.6时的截关系，将X分成3个等价类： {x1, x3}, {x2}, {x4, x5} 2017/3/1

65 λ ＝0.5 利用λ ＝0.5时的截关系，将X分成2个等价类： {x1, x3, x4, x5}, {x2} 2017/3/1

66 λ ＝0.4 利用λ ＝0.4时的截关系，将X分成1个等价类： {x1, x2, x3, x4, x5} 2017/3/1

67 动态聚类图 λ由1变到0，Rλ的分类由细到粗 x1 x2 x3 x4 x5 λ =1 λ =0.8 λ =0.6 λ =0.5 λ =0.4
这里要说明一下，所谓λ=0.4，是指在[0,0.4]上 2017/3/1

68 讨论 2017/3/1

69 讨论1：建立相似矩阵的其他方法 非常多！主要分为3类 相似系数法 距离法（绝对值减数法就是距离法之一） 主观法 在后面给出 2017/3/1

70 讨论2：直接基于相似矩阵聚类？？ 建立模糊相似矩阵R后，求其传递闭包t(R)计算量较大。 若直接从R出发，进行聚类，会怎么样？
2017/3/1

71 取λ=1(最大值)，对每个xi，确定其相似类[xi]1
将满足rij =1的xi和xj放在一类，构成相似类 {x1}, {x2}, {x3}, {x4}, {x5} 2017/3/1

72 取λ=0.8(次大值)，对每个xi,确定其相似类[xi]R
{x1, x3}, {x2}, {x4}, {x5} 2017/3/1

73 依次取λ=0.6、0.4等，确定其相似类。 {x1, x3}, {x2}, {x4, x5}
当λ=0.5时，相似类有公共元素 {x1, x3 ,x4 }, {x2 , x5}, {x1, x3 },{x1, x4 ,x5},{x2 , x4, x5} 2017/3/1

74 相似矩阵直接聚类vs.等价矩阵聚类 对于一个固定的λ，等价矩阵聚类得到的等价类没有公共元素！
相似矩阵聚类得到的相似类则有公共元素，这是因为不具有“传递性” 2017/3/1

75 讨论3：如何选取λ？？ 在实际应用中，需要选择适当的λ，从而给出一个较明确的分类。
1）由具有丰富经验的领域专家结合领域知识确定λ，从而得到λ水平上的等价分类。 2）用统计学中的F检验方法，刷掉不合格的类，使分类变得较清晰。 2017/3/1

76 最佳阈值确定——F统计量 F统计量： 分子表示类间平均距离，分母表示类内样本间的距离，F值越大，表示类与类间的差异越大，分类越好。
2017/3/1

77 讨论1:模糊相似矩阵的建立 2017/3/1

78 1、数据预处理——数据标准化 设论域U ={x1, x2, …, xn }为待聚类对象， 每个对象由m个指标表示其性状：
将原始数据矩阵中的元素通过适当的变换 压缩到[0,1]上。 2017/3/1

79 程序3：玉米螟 1:7~8月平均气温 2:上年12~2月平均气温 3: 4月份温湿系数 4: 4月份雨日数 5: 4月份日照数 6: 4月份平均风速 7: 5月上旬温湿系数8: 5月田间调查的玉米螟卵数 2017/3/1

80 数据标准化 数据标准化常用的两种变换： 平移－极差变换 平移－标准差变换 2017/3/1

81 数据标准化 平移－极差变换(变换至0-1区间)：
Ⅰ=(5,5,3,2),Ⅱ=(2,3,4,5), Ⅲ=(5,5,2,3),Ⅳ=(1,5,3,1), Ⅴ=(2,4,5,1) 请计算:Ⅰ=(5,5,3,2),Ⅱ=(2,3,4,5),Ⅲ=(5,5,2,3), Ⅳ=(1,5,3,1),Ⅴ=(2,4,5,1) 2017/3/1

82 数据标准化 平移－标准差变换(消除量纲)： 2017/3/1

83 2、模糊相似矩阵的建立 相似系数法 距离法 其它方法：主观评分法 2017/3/1

84 1)相似系数法 (1) 数量积法 |rij|∈[0,1]，若为负，要将其压缩到[0,1]，压缩方法：平移－极差变换或r’ij＝(rij+1)/2 Ⅰ=(5,5,3,2),Ⅱ=(2,3,4,5), Ⅲ=(5,5,2,3),Ⅳ=(1,5,3,1), Ⅴ=(2,4,5,1) 2017/3/1

85 1)相似系数法 (2)夹角余弦法： (3)相关系数法： 2017/3/1

86 1)相似系数法 (4)指数相似系数法： 2017/3/1

87 1)相似系数法 (5)最大最小法： (6)算数平均最小法： (7)几何平均最小法： 上述三种方法要求xij＞0，否则也要作适当变换。
2017/3/1

88 2)距离法 (1)绝对值倒数法： (2)绝对值指数法： 2017/3/1

89 2)距离法 (3)直接距离法：rij＝1-c*d(xi,xj) 海明距离： 欧式距离： 切比雪夫距离： 2017/3/1

90 3)主观评分法 专家直接给出相似度，专家数为N，rij(k)表示第k个专家给出的i与j的相似度，aij(k)为专家的自信度。
2017/3/1

91 程序演示 2017/3/1

92 程序1：环境 第4章\数据文件\编辑E.exe 打开”环境.dat” 第4章\模糊聚类E.exe 2017/3/1

93 程序1：环境 2017/3/1

94 程序1：环境 2017/3/1

95 程序2：家族 论域U = {x1, x2, x3, x4, x5}表示来自2个家族的5个人,已经利用某种方法建立了相似矩阵：
第4章\数据文件\编辑E.exe 打开”家族.dat” 用模糊聚类分析确定他们的家族关系。 第4章\模糊聚类E.exe 2017/3/1

96 程序2：家族 2017/3/1

97 程序3：玉米螟 第4章\数据文件\编辑E.exe 打开”玉米螟.dat” 用模糊聚类分析确定各年份间关系，以应用于害虫预报。
2017/3/1

98 程序3：玉米螟 2017/3/1

99 程序3：玉米螟 2017/3/1

100 程序4：土壤 第4章\数据文件\编辑E.exe 打开”土壤.dat”
21个土壤样本，每个样本9个量化指标：含氮百分比、含磷百分比、有机质、PH值、耕层厚度、持水量等。 第4章\模糊聚类E.exe 分析结果为进一步做土壤分类提供参考。 2017/3/1

101 程序4：土壤 2017/3/1

102 课后作业 2017/3/1

103 1、著名聚类的例子 日本学者Tamura给出，在模糊数学中广泛使用 有三个家庭，共16人。每个家庭人数为4-7人。
每人提供一张照片，共计16张 由若干素不相识的中学生对照片两两进行比较，按相貌相似程度进行评分，分数在[0,1]上。每对照片的相似程度由所有人对他们的评分的平均值确定。 要求：把三个家庭区分开来（即对这16个人进行聚类），可使用直接聚类法 2017/3/1

104 得到相似矩阵 2017/3/1

105 作业2 要建立下面四个对象的相似矩阵，请给出合理的建立公式，并用传递闭包法进行模糊聚类。 2017/3/1