Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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


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

Similar presentations


Ads by Google