1. 引言
模糊关系是模糊数学中的基本概念之一。模糊关系的合成运算是模糊关系的一种重要运算 [1] ,是求解模糊等价关系的基本算法,在聚类分析、模式识别中具有重要的应用 [2] - [7] 。例如,在模糊聚类分析中,应用模糊关系合成运算求解传递闭包从而构建模糊等价关系,进行动态聚类分析;在模糊模式识别中,应用合成运算求解模糊等价关系,建立模糊粗糙决策模型。在模糊关系合成运算过程中,模糊关系常常用模糊矩阵来表示,因此,模糊关系的运算能够表示为模糊矩阵的运算 [3] - [10] 。本文将模糊关系合成运算与矩阵分块技术相结合研究了模糊关系的分块合成运算,并分别从矩阵的行分块、列分块和行列分块对分块运算做出具体的讨论,给出了模糊关系的分块合成运算的算法和相应的MATLAB的程序代码,分析了分块合成运算的复杂度。研究表明,模糊关系的分块合成运算可以简化计算形式,但是不会增加运算的复杂度。
2. 模糊关系的分块合成运算
由于模糊关系可以由模糊矩阵来表示,因此在本文讨论中,直接用模糊矩阵来代替模糊关系。下面,首先引入模糊矩阵的合成运算。
定义1: [1] 设模糊矩阵
,
,称模糊矩阵
为A与B的合成,其中
。
可见,与普通矩阵乘法一样,只有当A的列数与B的行数相等时,模糊矩阵的合成运算
才能成立。
性质1:对于
,
,可以证明:模糊矩阵的合成运算的计算复杂度为。
模糊关系合成运算的MATLAB程序代码(Max_Min)见附录1。
例1:设
,
,计算
。
解:通常的算法为:
% command window
>> A=[0.4 0.7 0;1 0.8 0.5];
>> B=[1 0.7;0.4 0.6;0 0.3];
>> C=Max_Min(A,B)
C=
0.4000 0.6000
1.0000 0.7000
定义2:一般地说,设模糊矩阵
,
,把A,B分成一些小矩阵,
,
其中,每个
是
小矩阵,每个
是
小矩阵,令
其中,
,
。
应注意在分块A,B中,矩阵A的列的分法必须与矩阵B的行的分法一致。
性质2:模糊关系的分块合成运算的计算复杂度为
。
证明:由性质1知,
的复杂度为
。由于
,
,
因此,可以得到
的复杂度为:
.
从而可以计算
的第
行的复杂度为:
.
考虑
的所有行,可计算
复杂度为:
,因此,可以得到
的复杂度为
。
下面分别从模糊矩阵的列分块、行分块和行列分块对分块运算做出具体的讨论,给出了模糊矩阵的分块合成运算的算法,并给出了相应的MATLAB的程序代码,分析分块合成运算的复杂度。
2.1. 列分块合成运算
在模糊矩阵
的合成计算当中,可以把模糊矩阵A按照列分块,而矩阵B保持不变,即:
,
,
其中
为A的第i列
,因此可以得到:
其中,
。
续例1:用列分块方法计算
。
解:记
,
,
则有:
列分块合成运算的MATLAB程序代码(left right block)见附录2。
%command window
>> A=[0.4 0.7 0;1 0.8 0.5];
>> B=[1 0.7;0.4 0.6;0 0.3];
>> C=leftrightblock(A,B)
C=
0.4000 0.6000
1.0000 0.7000
2.2. 行分块合成运算
在模糊矩阵的合成计算当中,可以保持A不变,模糊矩阵B按照行分块,即:
,
,
其中,
为B的第i行
。因此可以得到:
.
续例2:用行分块方法计算例1。
解:记
,
,
合成运算的MATLAB程序代码(right block)见附录3。
%command window
>> A=[0.4 0.7 0;1 0.8 0.5];
>> B=[1 0.7;0.4 0.6;0 0.3];
>> C=rightblock(A,B)
C=
0.4000 0.6000
1.0000 0.7000
2.3. 行列分块合成运算
在模糊矩阵
的合成计算当中,可以把模糊矩阵A按照列分块,模糊矩阵B按照行分块,即:
,
,
其中
为A的第i列
,
为B的第i行
。
因此可以得到:
.
续例3:用行列分块方法计算例1。
解:记:
,
,
,
,
,
。则
行列合成运算的MATLAB程序代码(left right)见附录4。
%command window
>> A=[0.4 0.7 0;1 0.8 0.5];
>> B=[1 0.7;0.4 0.6;0 0.3];
>> C=leftright(A,B)
C=
0.4000 0.6000
1.0000 0.7000
3. 结论
根据以上研究能够得到,在计算模糊关系的合成时,可以将模糊关系分块,然后进行合成运算。在形式上,模糊关系的分块合成运算可以简化运算步骤。事实上,只要模糊关系的分块合成运算能够进行,任意分块方式都可以得到正确的结果。然而,通过计算复杂度可以发现,模糊分块矩阵的合成运算既不能降低计算的复杂度,也不会提高运算的时间。但是,分块合成运算仅仅使得合成运算在计算形式上简洁明了,不会提高计算效率。
基金项目
国家自然科学基金(61572082);辽宁省自然科学基金(No. 20170540012);辽宁省教育厅(LZ2016003)资助。
附录
1) 合成运算的MATLAB程序代码为:
function[C]=Max_Min(A,B)
C=[];
if (s1~=s)
return
end
for (i=1:m)
for (j=1:n)
C(i,j)=0;
for (k=1:s)
x=0;
if (A(i,k)
x=A(i,k);
else
x=B(k,j);
end
if (C(i,j)
C(i,j)=x;
end
end
end
end
2) 列分块合成运算的MATLAB程序代码为:
function [C,time1] = leftblock(A,B)
C = zeros(m,n);
if (s1 ~= s)
return
end
C = zeros(m,n);
for j = 1:n
for k = 1:s
for i = 1:m
if A(i,k) > B(k,j);
x = B(k,j);
else
x = A(i,k);
end
if C(i,j) < x
C(i,j) = x;
end
end
end
End
3) 合成运算的MATLAB程序代码为:
function [C,time1] = rightblock(A,B)
C = zeros(m,n);
if (s1 ~= s)
return
end
C = zeros(m,n);
for i = 1:m
for k = 1:s
for j = 1:n
if A(i,k) > B(k,j);
x = B(k,j);
else
x = A(i,k);
end
if C(i,j) < x
C(i,j) = x;
end
end
end
End
4) 行列合成运算的MATLAB程序代码为:
function [C]=leftright(A,B)
C=zeros(m,n);
if (s1~=s)
return
end
for i=1:s
Ai=A(:,i);
Bi=B(i,:);
Ci=Max_Min(Ai,Bi);
for j=1:m
for k=1:n
if (Ci(j,k)>C(j,k))
C(j,k)=Ci(j,k);
end
end
end
end