【参考资料】
【1】《模式识别与智能计算的MATLAB技术实现》
【2】《模糊数学方法及其应用》
【3】https://baike.baidu.com/item/Kruskal/10242089?fr=aladdin

1. 模糊关系的矩阵定义

---

模糊集定义及基础信息，参考之前笔记《模糊数学笔记-模糊集》

1.1 模糊关系

定义: 设论域U,V，称$U\times V$的一个模糊子集$\underset{\sim }{R}\in F(U\times V)$为U到V的模糊关系。其隶属函数映射为:
$U_R:U\times V\to [0,1]$ 其隶属度$\underset{\sim }{R}(x,y)$称为(x,y)关于模糊关系$\underset{\sim }{R}$的相关程度。

举例：

1.2 模糊矩阵

我们可以将上述关系用模糊矩阵来表述，有点类似马儿可夫随机过程里定义状态转移矩阵

定义矩阵$R=(r_{ij}{)}_{m\times n}$为模糊矩阵，例如：
$\left[\begin{array}{ccc}1& 0& 0.1\\ 0.5& 0.7& 0.3\end{array}\right]$，这里$r_{ij}\in [0,1]$

这里比较主要的是模糊矩阵的合成运算，如下:

定义:设$A=(a_{ij}{)}_{m\times t}$，$B=(b_{ij}{)}_{t\times n}$称模糊矩阵$A\circ B=(c_{ij}{)}_{m\times n}$

其中$ (c_{ij}) = {\lor}{t = 1}^s(a{it} \land b_{tj}) $

这里和矩阵乘法类似，只是在具体的运算中原先的元素乘元素编程取最小值，原先的乘积相加变为求最大值。 举例：

其次我们定义模糊矩阵的$\lambda$截距矩阵，这个定义比较简单，矩阵中的每个元素大于$\lambda$则为1，否则为0。举例如下:

2. 模糊关系的聚类分析

---

2.1 基于模糊矩阵的等价关系

如果模糊矩阵满足等价关系的三个要素，即：

1. 自反性：$r_{ij}=1$
2. 对称性：$r_{ij}=r_{ji}$
3. 传递性：$R\circ R\le R$即$(r_{ij})\ge {\vee }_{t=1}^s(r_{it}\wedge r_{tj})$

这里有一点不理解，为什么传递性中是小于等于而非直接等于？

举例:

2.2 基于模糊矩阵的分类

由于等价关系代表着集合上的一个分类，因此在模糊聚类中，我们对模糊矩阵取不同的$\lambda$截距，就可以取不同的分类。

3. 模糊聚类的算法步骤

---

第一步建立原始数据矩阵：

存在n个被分类对象，每个对象存在m个属性，则有：
$\left[\begin{array}{cccc}{x}_{11}& x_{12}& \cdots & x_{1m}\\ x_{21}& x_{22}& \cdots & x_{2m}\\ \cdots & \cdots & \cdots & \cdots \\ x_{n1}& x_{n2}& \cdots & x_{nm}\end{array}\right]$，同时将数据归一化到[0,1]之间。

第二步建立模糊相似矩阵：

对第一步建立的数据矩阵，其元素$x_i$和$x_j$建立一个相似矩阵。其中每一个元素$r_{ij}$代表$x_i$和$x_j$。这里的相似度可以用多种方式做，比如数量积、相关系数等。

比如数量积定义：
$r_{ij}=\{\begin{array}{ll}1,& i=j\\ \frac{1}{M}\sum _{k=1}^m{x}_{ik}.x_{jk},& i̸=j\end{array}$
这里$M=max(\sum _{k=1}^m{x}_{ik}.x_{jk})$

这里的结果也归一化到[0,1]之间

第三步聚类操作：

这里举例为最大树法。

这里用的就是最大生成树Kruskal算法

4. 程序实现

---

# -*- coding: utf-8 -*-
import numpy  as np
import sklearn.datasets as ds
import matplotlib.pyplot as plt
import random
import math
import operator

SAMPLE_NUM  = 200    #样本数量
FEATURE_NUM = 2     #每个样本的特征数量
CLASS_NUM   = 2     #分类数量


#1. 初始化测试数据
sample, y = ds.make_blobs(SAMPLE_NUM, n_features=FEATURE_NUM, centers=CLASS_NUM, random_state=3)

sim_array = [[0 for col in range(SAMPLE_NUM)] for row in range(SAMPLE_NUM)]



tree_node  = []   #选择的节点
path_node  = []   #路径
value_node = []   #存储路径对应的值


def _build_kruskal_tree():

    #kruskal每次筛选与当前已选区域联通的点，将满足要求最好的点加入已选区域

    tree_node.append(0)

    while len(tree_node) < SAMPLE_NUM :
        
        tmp_sum = 0
        tmp_set = (0,0)
        tmp_node = 0

        for node in tree_node:

            for i in range(0, SAMPLE_NUM):

                if node == i:

                    continue

                else:

                    if i in tree_node:

                        continue

                    else:



                        #计算距离
                        if sim_array[node][i] > tmp_sum:

                            tmp_sum = sim_array[node][i]

                            tmp_set = (node, i)

                            tmp_node = i

        path_node.append(tmp_set)
        tree_node.append(tmp_node)
        value_node.append((len(path_node), tmp_sum))



def _do_fuzzy_cluster():

    

    #2. 构造相似矩阵

    max = 0

    for i in range(0, SAMPLE_NUM):

        for j in range(0, SAMPLE_NUM):

            if i == j:

                sim_array[i][j] = 1

            else:

                tmp = 0

                for k in range(0, FEATURE_NUM):

                    tmp += sample[i][k] * sample[j][k]

                sim_array[i][j] = tmp

                if tmp > max:

                    max = tmp



    for i in range(0, SAMPLE_NUM):

        for j in range(0, SAMPLE_NUM):

            if i != j:

                sim_array[i][j] = sim_array[i][j]/max


    #3. 构造最大树
    _build_kruskal_tree()

    #4. 聚类划分并显示
    #根据最大生成树来进行分类
    value_node.sort(key= operator.itemgetter(1))

    gamma = value_node[int(len(value_node)/2)][1]

    #根据这个gamma值分开
    y_pre = [0 for col in range(SAMPLE_NUM)]

    for i in range(0, SAMPLE_NUM - 1):

        start = path_node[i][0]
        end   = path_node[i][1]

        if value_node[i][1] > gamma:

            y_pre[start] = 1
            y_pre[end]   = 1

        else:
            y_pre[start] = 0
            y_pre[end]   = 0

    #print(np.array(y_pre))
    #print(y)

    #显示

    plt.figure(figsize=(5, 6), facecolor='w')
    plt.subplot(211)
    plt.title('origin classfication')
    plt.scatter(sample[:, 0], sample[:, 1], c=y, s=20, edgecolors='none')

    plt.subplot(212)
    plt.title('fuzzy classfication')
    plt.scatter(sample[:, 0], sample[:, 1], c=np.array(y_pre), s=20, edgecolors='none')

    plt.show()

"""
说明：

模糊聚类的代码实现，基于最大树算法，针对笔记《模糊聚类分析》

作者：fredric

日期：2018-12-23

"""
if __name__ == "__main__":

    _do_fuzzy_cluster()