写在前面

今天上午写完了以人事招聘为例的误差反向传播算法，下午要写的是“基于传递闭包的模糊聚类”。青春易逝，时间珍贵，要抓紧写完代码，这样就可以没有后顾之忧的和npy出去玩了。2021.12.2

实验题目

基于传递闭包的模糊聚类

背景知识

计算智能课程设计-基于传递闭包的模糊聚类

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import numpy as np

np.set_printoptions(precision=2)  # 设置矩阵输出精度,保留两位小数

def MaxNormalization(a):
    """
    采用最大值规格化法将数据规格化为
    """
    c = np.zeros_like(a, dtype=float)
    for j in range(c.shape[1]):  # 遍历c的列
        for i in range(c.shape[0]):  # 遍历c的列
            c[i, j] = a[i, j]/np.max(a[:, j])
    return c

def FuzzySimilarMatrix(a):
    """
    用最大最小法构造得到模糊相似矩阵
    """
    a = MaxNormalization(a)  # 用标准化后的数据
    c = np.zeros((a.shape[0], a.shape[0]), dtype=float)
    mmax = []
    mmin = []
    for i in range(c.shape[0]):  # 遍历c的行
        for j in range(c.shape[0]):  # 遍历c的行
            mmax.extend([np.fmax(a[i, :], a[j, :])])  # 取i和和j行的最大值,即求i行和j行的并
            mmin.extend([np.fmin(a[i, :], a[j, :])])  # 取i和和j行的最大值,即求i行和j行的交
    for i in range(len(mmax)):
        mmax[i] = np.sum(mmax[i])  # 求并的和
        mmin[i] = np.sum(mmin[i])  # 求交的和
    mmax = np.array(mmax).reshape(c.shape[0], c.shape[1])  # 变换为与c同型的矩阵
    mmin = np.array(mmin).reshape(c.shape[0], c.shape[1])  # 变换为与c同型的矩阵
    for i in range(c.shape[0]):  # 遍历c的行
        for j in range(c.shape[1]):  # 遍历c的列
            c[i, j] = mmin[i, j]/mmax[i, j]  # 赋值相似度
    return c

def MatrixComposition(a, b):
    """
    合成模糊矩阵a和模糊矩阵b
    """
    a, b = np.array(a), np.array(b)
    c = np.zeros_like(a.dot(b))
    for i in range(a.shape[0]):  # 遍历a的行元素
        for j in range(b.shape[1]):  # 遍历b的列元素
            empty = []
            for k in range(a.shape[1]):
                empty.append(min(a[i, k], b[k, j]))  # 行列元素比小
            c[i, j] = max(empty)  # 比小结果取大
    return c

def TransitiveClosure(a):
    """
    平方法合成传递闭包
    """
    a = FuzzySimilarMatrix(a)  # 用模糊相似矩阵
    c = a
    while True:
        m = c
        c = MatrixComposition(MatrixComposition(a, c), MatrixComposition(a, c))
        if (c == m).all():  # 闭包条件
            return np.around(c, decimals=2)  # 返回传递闭包,四舍五入,保留两位小数
            break
        else:
            continue

def CutSet(a):
    """
    水平截集
    """
    a = TransitiveClosure(a)  # 用传递闭包

    return np.sort(np.unique(a).reshape(-1))[::-1]

def get_classes(temp_pairs):
    lists = []

    for item1 in temp_pairs:
        temp_list = []
        for item2 in temp_pairs:
            if item1[0] == item2[1]:
                temp_list.append(item2[0])
        lists.append(list(set(temp_list)))

    return(list(np.unique(lists)))

def Result(a):
    """
    模糊聚类结果
    """
    lambdas = CutSet(a)
    a = TransitiveClosure(a)

    classes = []

    for lam in lambdas:
        if lam == lambdas[0]:
            classes.append([[a] for a in range(len(a))])
        else:
            pairs = np.argwhere(a >= lam)
            classes.append(get_classes(pairs))
    return classes

def main():
    """
    特性指标矩阵
    """
    input = np.array([[17, 15, 14, 15, 16],
                      [18, 16, 13, 14, 12],
                      [18, 18, 19, 17, 18],
                      [16, 18, 16, 15, 18]])

    print("特性指标矩阵\n", input)
    print("\n采用最大值规格化法将数据规格化为\n", MaxNormalization(input))
    print("\n用最大最小法构造得到模糊相似矩阵\n", FuzzySimilarMatrix(input))
    print("\n平方法合成传递闭包\n", TransitiveClosure(input))
    print("\n水平截集为\n", CutSet(input))
    print("\n模糊聚类结果\n", Result(input))


if __name__ == "__main__":
    main()

实验内容

运行和理解示例代码，回答下列问题：

1）为什么按最大最小法得到的一定是一个方阵？且一定是自反方阵？且一定是对称方阵？

2）为什么可以根据水平截集对数据进行分类？（提示：一个等价关系唯一确定一个划分）

3）请解释代码 72 行中两个-1 的含义：

1
return np.sort(np.unique(a).reshape(-1))[::-1]

4）在平方法的代码实现中，如何判断平方后的矩阵是否满足传递性？为什么可以这么判断？

5）请修改代码，将最大最小法替换为算术平均最小法。这会改变最终的聚类结果么？

实验结果与分析

第一题

1）为什么按最大最小法得到的一定是一个方阵？且一定是自反方阵？且一定是对称方阵？

  1. 因为按照最大最小法来做，当i==j时，有：

    所以有

    故，得到的方阵一定是自反方阵

  2. 对于

    有

    故它一定是对称方阵。

第二题

2）为什么可以根据水平截集对数据进行分类？（提示：一个等价关系唯一确定一个划分）

由于模糊相似矩阵本身已经是自反的、对称的，其传递闭包又是传递的，则其传递闭包一定是模糊等价矩阵，可以决定一个划分。

第三题

3）请解释代码 72 行中两个-1 的含义：

前面的-1是自动推断行数或列数

后面的-1是逆序

1
return np.sort(np.unique(a).reshape(-1))[::-1]

第四题

4）在平方法的代码实现中，如何判断平方后的矩阵是否满足传递性？为什么可以这么判断？

判断代码如下：

1
FuzzySimilarMatrix(a)==MatrixComposition(MatrixComposition(a, c), MatrixComposition(a, c)).all

从模糊相似矩阵得到传递闭包，采用的方法是平方法，具体方法是：把一个相似矩阵，进行自乘操作，得到并且检验是否满足传递性，如果满足，则停止。

原理：

第五题

5）请修改代码，将最大最小法替换为算术平均最小法。这会改变最终的聚类结果么？

修改代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def FuzzySimilarMatrix(a):
    """
    用最大最小法构造得到模糊相似矩阵
    """
    a = MaxNormalization(a)  # 用标准化后的数据
    c = np.zeros((a.shape[0], a.shape[0]), dtype=float)
    mmax = []
    mmin = []
    for i in range(c.shape[0]):  # 遍历c的行
        for j in range(c.shape[0]):  # 遍历c的行
            ###修改处
            mmax.extend([a[i, :]+ a[j, :]])  # 取i和和j行的最大值,即求i行和j行的并
            mmin.extend([np.fmin(a[i, :], a[j, :])])  # 取i和和j行的最大值,即求i行和j行的交
    for i in range(len(mmax)):
        ###修改处
        mmax[i] = np.sum(mmax[i])/2  # 求并的和
        mmin[i] = np.sum(mmin[i])  # 求交的和
    mmax = np.array(mmax).reshape(c.shape[0], c.shape[1])  # 变换为与c同型的矩阵
    mmin = np.array(mmin).reshape(c.shape[0], c.shape[1])  # 变换为与c同型的矩阵
    for i in range(c.shape[0]):  # 遍历c的行
        for j in range(c.shape[1]):  # 遍历c的列
            c[i, j] = mmin[i, j]/mmax[i, j]  # 赋值相似度
    return c

会改变最终的聚类结果。