模糊关系的分块合成运算 Block Composition of Fuzzy Relation

doi:10.12677/HJDM.2018.83016

Hans Journal of Data Mining
Vol.08 No.03(2018), Article ID:26126,9 pages
10.12677/HJDM.2018.83016

Block Composition of Fuzzy Relation

Ji Li, Jing Wang, Yan Wang, Changzhong Wang

●How to Cite this Article

College of Mathematics and Physics, Bohai University, Jinzhou Liaoning

Received: Jul. 6^th, 2018; accepted: Jul. 23^rd, 2018; published: Jul. 30^th, 2018

ABSTRACT

Compositional operation of fuzzy relations is an important operation, which is widely used in pattern recognition, machine learning, and data mining. In this paper, block operation of fuzzy relations is studied, and the complexity of block synthesis is analyzed. The results show that block operations can simplify the form of fuzzy relation synthesis operations, but they do not increase the complexity of the operation.

Keywords:MATLAB, Fuzzy Relationship, Compositional Operations, Block Operations

模糊关系的分块合成运算

李季，王京，王艳，王长忠

渤海大学，数理学院，辽宁锦州

收稿日期：2018年7月6日；录用日期：2018年7月23日；发布日期：2018年7月30日

摘要

模糊关系中的合成运算是一种重要的运算，在模式识别、机器学习和数据挖掘中具有广泛的应用。本文对模糊关系的合成运算进行了分块运算研究，并对分块合成运算的复杂度进行了分析。研究结果表明，分块运算可以简化模糊关系合成运算的形式，但是不会增加运算的复杂度。

关键词 :MATLAB，模糊关系，合成运算，分块运算

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

模糊关系是模糊数学中的基本概念之一。模糊关系的合成运算是模糊关系的一种重要运算 [1] ，是求解模糊等价关系的基本算法，在聚类分析、模式识别中具有重要的应用 [2] - [7] 。例如，在模糊聚类分析中，应用模糊关系合成运算求解传递闭包从而构建模糊等价关系，进行动态聚类分析；在模糊模式识别中，应用合成运算求解模糊等价关系，建立模糊粗糙决策模型。在模糊关系合成运算过程中，模糊关系常常用模糊矩阵来表示，因此，模糊关系的运算能够表示为模糊矩阵的运算 [3] - [10] 。本文将模糊关系合成运算与矩阵分块技术相结合研究了模糊关系的分块合成运算，并分别从矩阵的行分块、列分块和行列分块对分块运算做出具体的讨论，给出了模糊关系的分块合成运算的算法和相应的MATLAB的程序代码，分析了分块合成运算的复杂度。研究表明，模糊关系的分块合成运算可以简化计算形式，但是不会增加运算的复杂度。

2. 模糊关系的分块合成运算

由于模糊关系可以由模糊矩阵来表示，因此在本文讨论中，直接用模糊矩阵来代替模糊关系。下面，首先引入模糊矩阵的合成运算。

定义1： [1] 设模糊矩阵 $A = {(a_{i j})}_{m \times s}$ ， $B = {(b_{i j})}_{s \times n}$ ，称模糊矩阵 $A \circ B = {(c_{i j})}_{m \times n}$ 为A与B的合成，其中 $c_{i j} = \lor_{k = 1}^{s} (a_{i k} \land b_{k j})$ 。

可见，与普通矩阵乘法一样，只有当A的列数与B的行数相等时，模糊矩阵的合成运算 $A \circ B$ 才能成立。

性质1：对于 $A = {(a_{i j})}_{m \times s}$ ， $B = {(b_{i j})}_{s \times n}$ ，可以证明：模糊矩阵的合成运算的计算复杂度为。

模糊关系合成运算的MATLAB程序代码(Max_Min)见附录1。

例1：设 $A = [\begin{matrix} 0.4 & 0.7 & 0 \\ 1 & 0.8 & 0.5 \end{matrix}]$ ， $B = [\begin{matrix} 1 & 0.7 \\ 0.4 & 0.6 \\ 0 & 0.3 \end{matrix}]$ ，计算 $A \circ B$ 。

解：通常的算法为：

$A \circ B = [\begin{matrix} (0.4 \land 1) \lor (0.7 \land 0.4) \lor (0 \land 0) & (0.4 \land 0.7) \lor (0.7 \land 0.6) \lor (0 \land 0.3) \\ (1 \land 1) \lor (0.8 \land 0.4) \lor (0.5 \land 0) & (1 \land 0.7) \lor (0.8 \land 0.6) \lor (0.5 \land 0.3) \end{matrix}] = [\begin{matrix} 0.4 & 0.6 \\ 1 & 0.7 \end{matrix}]$

% 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)

0.4000 0.6000

1.0000 0.7000

定义2：一般地说，设模糊矩阵 $A = {(a_{i k})}_{s n}$ ， $B = {(b_{k j})}_{n m}$ ，把A，B分成一些小矩阵，

$\begin{array}{l} \begin{matrix} n_{1} & n_{2} & \dots & n_{l} \end{matrix} \\ A = \begin{matrix} s_{1} \\ s_{2} \\ ⋮ \\ s_{t} \end{matrix} [\begin{matrix} A_{11} & A_{12} & \dots & A_{1 l} \\ A_{21} & A_{22} & \dots & A_{2 l} \\ ⋮ & ⋮ & ⋮ \\ A_{t 1} & A_{t 2} & \dots & A_{t l} \end{matrix}] \end{array}$ ， $\begin{array}{l} \begin{matrix} m_{1} & m_{2} & \dots & m_{r} \end{matrix} \\ B = \begin{matrix} n_{1} \\ n_{2} \\ ⋮ \\ n_{l} \end{matrix} [\begin{matrix} B_{11} & B_{12} & \dots & B_{1 r} \\ B_{21} & B_{22} & \dots & B_{2 r} \\ ⋮ & ⋮ & ⋮ \\ B_{l 1} & B_{l 2} & \dots & B_{l r} \end{matrix}] \end{array}$

其中，每个 $A_{i j}$ 是 $s_{i} \times n_{j}$ 小矩阵，每个 $B_{i j}$ 是 $n_{i} \times m_{j}$ 小矩阵，令

$\begin{array}{l} \begin{matrix} m_{1} & m_{2} & \dots & m_{r} \end{matrix} \\ C = A \circ B = \begin{matrix} s_{1} \\ s_{2} \\ ⋮ \\ s_{t} \end{matrix} [\begin{matrix} C_{11} & C_{12} & \dots & C_{1 r} \\ C_{21} & C_{22} & \dots & C_{2 r} \\ ⋮ & ⋮ & ⋮ \\ C_{t 1} & C_{t 2} & \dots & C_{t r} \end{matrix}] \end{array}$

其中， $C_{p q} = A_{p 1} \circ B_{1 q} \cup A_{p 2} \circ B_{2 q} \cup \dots \cup A_{p l} \circ B_{l q}$ ， $(p = 1, 2, \dots, t; q = 1, 2, \dots, r)$ 。

应注意在分块A，B中，矩阵A的列的分法必须与矩阵B的行的分法一致。

性质2：模糊关系的分块合成运算的计算复杂度为 $m s n$ 。

证明：由性质1知， $A_{p k} \circ B_{k q}$ 的复杂度为 $s_{p} n_{k} m_{q}$ 。由于

$C_{p q} = A_{p 1} \circ B_{1 q} \cup A_{p 2} \circ B_{2 q} \cup \dots \cup A_{p l} \circ B_{l q}$ ， $(p = 1, 2, \dots, t; q = 1, 2, \dots, r)$ ，

因此，可以得到 $C_{p q}$ 的复杂度为：

$s_{p} n_{1} m_{q} + s_{p} n_{2} m_{q} + \dots + s_{p} n_{l} m_{q} = s_{p} m_{q} n$ .

从而可以计算 $A \circ B$ 的第 $s_{i}$ 行的复杂度为：

$s_{i} m_{1} n + s_{i} m_{2} n + \dots + s_{i} m_{r} n = s_{i} m n$ .

考虑 $A \circ B$ 的所有行，可计算 $A \circ B$ 复杂度为： $s_{1} m n + s_{2} m n + \dots + s_{t} m n = s m n$ ，因此，可以得到 $A \circ B$ 的复杂度为 $s m n$ 。

下面分别从模糊矩阵的列分块、行分块和行列分块对分块运算做出具体的讨论，给出了模糊矩阵的分块合成运算的算法，并给出了相应的MATLAB的程序代码，分析分块合成运算的复杂度。

2.1. 列分块合成运算

在模糊矩阵 $A \circ B$ 的合成计算当中，可以把模糊矩阵A按照列分块，而矩阵B保持不变，即：

$A = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}] = (α_{1}, α_{2}, \dots, α_{n})$ ， $B = [\begin{matrix} b_{11} & b_{12} & \dots & b_{1 n} \\ b_{21} & b_{22} & \dots & b_{2 n} \\ ⋮ & ⋮ & ⋮ \\ b_{n 1} & b_{n 2} & \dots & b_{n n} \end{matrix}]$ ，

其中 $α_{i}$ 为A的第i列 $(i = 1, 2, \dots, n)$ ，因此可以得到：

$\begin{matrix} A \circ B = (α_{1}, α_{2}, \dots, α_{n}) \circ [\begin{matrix} b_{11} & b_{12} & \dots & b_{1 n} \\ b_{21} & b_{22} & \dots & b_{2 n} \\ ⋮ & ⋮ & ⋮ \\ b_{n 1} & b_{n 2} & \dots & b_{n n} \end{matrix}] \\ = (α_{1} \circ b_{11} \cup α_{2} \circ b_{21} \cup \dots \cup α_{n} \circ b_{n 1}, α_{1} \circ b_{12} \cup α_{2} \circ b_{22} \cup \dots \cup α_{n} \circ b_{n 2}, \\ \dots, α_{1} \circ b_{1 n} \cup α_{2} \circ b_{2 n} \cup \dots \cup α_{n} \circ b_{n n}) \\ = (β_{1}, β_{2}, \dots, β_{n}) \end{matrix}$

其中， $β_{j} = α_{1} \circ b_{1 j} \cup α_{2} \circ b_{2 j} \cup \dots \cup α_{n} \circ b_{n j}$ 。

续例1：用列分块方法计算 $A \circ B$ 。

解：记 $α_{1} = [\begin{matrix} 0.4 \\ 1 \end{matrix}]$ ， $α_{2} = [\begin{matrix} 0.7 \\ 0.8 \end{matrix}]$ ， $α_{3} = [\begin{matrix} 0 \\ 0.5 \end{matrix}]$

则有：

$\begin{matrix} A \circ B = (α_{1}, α_{2}, α_{3}) \circ [\begin{matrix} 1 & 0.7 \\ 0.4 & 0.6 \\ 0 & 0.3 \end{matrix}] = (α_{1} \circ 1 \cup α_{2} \circ 0.4 \cup α_{3} \circ 0, α_{1} \circ 0.7 \cup α_{2} \circ 0.6 \cup α_{3} \circ 0.3) \\ = [[\begin{matrix} 0.4 \\ 1 \end{matrix}] \circ [1] \cup [\begin{matrix} 0.7 \\ 0.8 \end{matrix}] \circ [0.4] \cup [\begin{matrix} 0 \\ 0.5 \end{matrix}] \circ [0], [\begin{matrix} 0.4 \\ 1 \end{matrix}] \circ [0.7] \cup [\begin{matrix} 0.7 \\ 0.8 \end{matrix}] \circ [0.6] \cup [\begin{matrix} 0 \\ 0.5 \end{matrix}] \circ [0.3]] \\ = [[\begin{matrix} 0.4 \\ 1 \end{matrix}] \cup [\begin{matrix} 0.4 \\ 0.4 \end{matrix}] \cup [\begin{matrix} 0 \\ 0 \end{matrix}], [\begin{matrix} 0.4 \\ 0.7 \end{matrix}] \cup [\begin{matrix} 0.6 \\ 0.6 \end{matrix}] \cup [\begin{matrix} 0 \\ 0.3 \end{matrix}]] = [\begin{matrix} 0.4 & 0.6 \\ 1 & 0.7 \end{matrix}] \end{matrix}$

列分块合成运算的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)

0.4000 0.6000

1.0000 0.7000

2.2. 行分块合成运算

在模糊矩阵的合成计算当中，可以保持A不变，模糊矩阵B按照行分块，即：

$A = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}]$ ， $B = [\begin{matrix} b_{11} & b_{12} & \dots & b_{1 n} \\ b_{21} & b_{22} & \dots & b_{2 n} \\ ⋮ & ⋮ & ⋮ \\ b_{n 1} & b_{n 2} & \dots & b_{n n} \end{matrix}] = [\begin{matrix} β_{1} \\ β_{2} \\ ⋮ \\ β_{n} \end{matrix}]$ ，

其中， $β_{i}$ 为B的第i行 $(i = 1, 2, \dots, n)$ 。因此可以得到：

$A \circ B = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}] \circ [\begin{matrix} β_{1} \\ β_{2} \\ ⋮ \\ β_{n} \end{matrix}] = [\begin{matrix} a_{11} \circ β_{1} \cup a_{12} \circ β_{2} \cup \dots \cup a_{1 n} \circ β_{n} \\ a_{21} \circ β_{1} \cup a_{22} \circ β_{2} \cup \dots \cup a_{2 n} \circ β_{n} \\ ⋮ \\ a_{n 1} \circ β_{1} \cup a_{n 2} \circ β_{2} \cup \dots \cup a_{n n} \circ β_{n} \end{matrix}]$ .

续例2：用行分块方法计算例1。

解：记 $β_{1} = [\begin{matrix} 1 & 0.7 \end{matrix}]$ ， $β_{2} = [\begin{matrix} 0.4 & 0.6 \end{matrix}]$ ， $β_{3} = [\begin{matrix} 0 & 0.3 \end{matrix}]$

$\begin{matrix} A \circ B = [\begin{matrix} 0.4 & 0.7 & 0 \\ 1 & 0.8 & 0.5 \end{matrix}] \circ [\begin{matrix} β_{1} \\ β_{2} \\ β_{3} \end{matrix}] = [\begin{matrix} 0.4 \circ β_{1} \cup 0.7 \circ β_{2} \cup 0 \circ β_{3} \\ 1 \circ β_{1} \cup 0.8 \circ β_{2} \cup 0.5 \circ β_{3} \end{matrix}] \\ = [\begin{matrix} [0.4] \circ [\begin{matrix} 1 & 0.7 \end{matrix}] \cup [0.7] \circ [\begin{matrix} 0.4 & 0.6 \end{matrix}] \cup [0] \circ [\begin{matrix} 0 & 0.3 \end{matrix}] \\ [1] \circ [\begin{matrix} 1 & 0.7 \end{matrix}] \cup [0.8] \circ [\begin{matrix} 0.4 & 0.6 \end{matrix}] \cup [0.5] \circ [\begin{matrix} 0 & 0.3 \end{matrix}] \end{matrix}] \\ = [\begin{matrix} [\begin{matrix} 0.4 & 0.4 \end{matrix}] \cup [\begin{matrix} 0.4 & 0.6 \end{matrix}] \cup [\begin{matrix} 0 & 0 \end{matrix}] \\ [\begin{matrix} 1 & 0.7 \end{matrix}] \cup [\begin{matrix} 0.4 & 0.6 \end{matrix}] \cup [\begin{matrix} 0 & 0.3 \end{matrix}] \end{matrix}] = [\begin{matrix} 0.4 & 0.6 \\ 1 & 0.7 \end{matrix}] \end{matrix}$

合成运算的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)

0.4000 0.6000

1.0000 0.7000

2.3. 行列分块合成运算

在模糊矩阵 $A \circ B$ 的合成计算当中，可以把模糊矩阵A按照列分块，模糊矩阵B按照行分块，即：

其中 $α_{i}$ 为A的第i列 $(i = 1, 2, \dots, n)$ ， $β_{i}$ 为B的第i行 $(i = 1, 2, \dots, n)$ 。

因此可以得到：

$A \circ B = [\begin{matrix} α_{1} & α_{2} & \dots & α_{n} \end{matrix}] \circ [\begin{matrix} β_{1} \\ β_{2} \\ ⋮ \\ β_{n} \end{matrix}] = α_{1} \circ β_{1} \cup α_{2} \circ β_{2} \cup \dots \cup α_{n} \circ β_{n}$ .

续例3：用行列分块方法计算例1。

解：记： $α_{1} = [\begin{matrix} 0.4 \\ 1 \end{matrix}]$ ， $α_{2} = [\begin{matrix} 0.7 \\ 0.8 \end{matrix}]$ ， $α_{3} = [\begin{matrix} 0 \\ 0.5 \end{matrix}]$ ， $β_{1} = [\begin{matrix} 1 & 0.7 \end{matrix}]$ ， $β_{2} = [\begin{matrix} 0.4 & 0.6 \end{matrix}]$ ， $β_{3} = [\begin{matrix} 0 & 0.3 \end{matrix}]$ 。则

$\begin{matrix} A \circ B = [\begin{matrix} \begin{matrix} α_{1} \end{matrix} & \begin{matrix} α_{2} & \begin{matrix} α_{3} \end{matrix} \end{matrix} \end{matrix}] \circ [\begin{matrix} β_{1} \\ β_{2} \\ β_{n} \end{matrix}] = α_{1} \circ β_{1} \cup α_{2} \circ β_{2} \cup α_{3} \circ β_{3} \\ = [\begin{matrix} 0.4 \\ 1 \end{matrix}] \circ [\begin{matrix} 1 & 0.7 \end{matrix}] \cup [\begin{matrix} 0.7 \\ 0.8 \end{matrix}] \circ [\begin{matrix} 0.4 & 0.6 \end{matrix}] \cup [\begin{matrix} 0 \\ 0.5 \end{matrix}] \circ [\begin{matrix} 0 & 0.3 \end{matrix}] \\ = [\begin{matrix} 0.4 & 0.4 \\ 1 & 0.7 \end{matrix}] \cup [\begin{matrix} 0.4 & 0.6 \\ 0.4 & 0.6 \end{matrix}] \cup [\begin{matrix} 0 & 0 \\ 0 & 0.3 \end{matrix}] = [\begin{matrix} 0.4 & 0.6 \\ 1 & 0.7 \end{matrix}] \end{matrix}$

行列合成运算的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)

0.4000 0.6000

1.0000 0.7000

3. 结论

根据以上研究能够得到，在计算模糊关系的合成时，可以将模糊关系分块，然后进行合成运算。在形式上，模糊关系的分块合成运算可以简化运算步骤。事实上，只要模糊关系的分块合成运算能够进行，任意分块方式都可以得到正确的结果。然而，通过计算复杂度可以发现，模糊分块矩阵的合成运算既不能降低计算的复杂度，也不会提高运算的时间。但是，分块合成运算仅仅使得合成运算在计算形式上简洁明了，不会提高计算效率。

基金项目

国家自然科学基金(61572082)；辽宁省自然科学基金(No. 20170540012)；辽宁省教育厅(LZ2016003)资助。

文章引用

李季,王京,王艳,王长忠. 模糊关系的分块合成运算
Block Composition of Fuzzy Relation[J]. 数据挖掘, 2018, 08(03): 142-150. https://doi.org/10.12677/HJDM.2018.83016

参考文献

1. 谢季坚, 刘承平. 模糊数学方法及其应用[M]. 第3版. 武汉: 华中科技大学出版社, 2006.

2. 李荣钧. 模糊多准则决策理论与应用[M]. 北京: 科学出版社, 2002.

3. 王长忠, 王丽丽. 模糊关系映射的性质[J] 模糊系统与数学, 2013, 27(4): 13-18.

4. 王长忠, 陈德刚. 基于粗糙集的知识获取理论与方法[M]. 哈尔滨: 哈尔滨工业大学出版社, 2010.

5. Wang, C., Shao, M., He, Q., Qian, Y. and Qi, Y. (2016) Feature Subset Selection Based on Fuzzy Neighborhood Rough Sets. Knowledge-Based Systems, 111, 173-179. https://doi.org/10.1016/j.knosys.2016.08.009

6. Wang, C., Qi, Y., Shao, M., et al. (2016) A Fitting Model for Fea-ture Selection with Fuzzy Rough Sets. IEEE Transactions on Fuzzy Systems, 25, 741-753. https://doi.org/10.1109/TFUZZ.2016.2574918

7. Wang, C., Chen, D. and Hu, Q. (2014) Fuzzy Information Systems and their Homomorphisms. Fuzzy Sets and Systems, 249, 128-138. https://doi.org/10.1016/j.fss.2014.02.009

8. Zadeh, L.A. (1975) The Concept of a Linguistic Variable and Its Applications in Approximate Reasoning. Information Sciences, 8, 199-251. https://doi.org/10.1016/0020-0255(75)90036-5

9. Graymala-Busse, J.W. (1986) Algebraic Properties of Knowledge Repre-sentation Systems. Proceedings of the ACM SIGART International Symposium on Methodologies for Intelligent Systems, Knoxville, 22-24 October 1986, 432-440. https://doi.org/10.1145/12808.12856

10. Wang, C.Z., Chen, D.G. and Zhu, L.K. (2009) Homomorphisms between Fuzzy In-formation Systems. Applied Mathematics Letters, 22, 1045-1050. https://doi.org/10.1016/j.aml.2009.01.013

附录

1) 合成运算的MATLAB程序代码为：

function[C]=Max_Min(A,B)

[m,s]=size(A);

[s1,n]=size(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

2) 列分块合成运算的MATLAB程序代码为：

function [C,time1] = leftblock(A,B)

[m,s] = size(A);

[s1,n] = size(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

3) 合成运算的MATLAB程序代码为：

function [C,time1] = rightblock(A,B)

[m,s] = size(A);

[s1,n] = size(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

4) 行列合成运算的MATLAB程序代码为：

function [C]=leftright(A,B)

[m,s]=size(A);

[s1,n]=size(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

期刊菜单