FCM算法理论及其Python实现

ゝ一纸荒年。 2022-03-12 04:00 525阅读 0赞

## FCM算法 ##

全名为Fuzzy C-Means，是一种聚类算法。

> Fuzzy c-means (FCM) is a method of clustering which allows one piece of data to belong to two or more clusters. This method (developed by Dunn in 1973 and improved by Bezdek in 1981) is frequently used in pattern recognition. It is based on minimization of the following objective function:  
> FCM是一种聚类的方法，可以允许一个数据属于两个或以上的类。这种方法（由Dunn在1973年提出，由Bezdek在1981年改进。）被频繁地用于模式识别。
> 
>  *  J. C. Dunn (1973): “A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters”, Journal of Cybernetics 3: 32-57
>  *  J. C. Bezdek (1981): “Pattern Recognition with Fuzzy Objective Function Algoritms”, Plenum Press, New York

基于最小化下面的目标函数:

J m = ∑ i = 1 N ∑ j = 1 C u i j m ∣ ∣ x i − c j ∣ ∣ 2 J\_m = \\sum^\{N\}\_\{i=1\}\{\\sum^\{C\}\_\{j=1\}\{u\_\{ij\}^m||x\_i-c\_j||^2\}\} Jm=i=1∑Nj=1∑Cuijm∣∣xi−cj∣∣2

*  m是任何大于1的实数
 *   u i j u\_\{ij\} uij是 x i x\_i xi在类j上隶属度
 *  其中 x i x\_i xi是第i个d维测量向量
 *   c j c\_j cj是一个d维的类中心

FCM主要通过迭代更新u和c来得到最终的解。

迭代终点一般选取两个：

*  当u变化的无穷范数小于某个值时
 *  当迭代次数达到某个极限时候

这个过程可能会收敛到局部最小值或者是鞍点上

## 算法流程 ##

1.  初始化矩阵U （描述每个点在不同的类中的概率）
2.  通过U算类中心  
     C j = ∑ i = 1 N u i j m ∗ x i ∑ i = 1 N u i j m C\_j=\\frac\{\\sum^\{N\}\_\{i=1\}\{u\_\{ij\}^m \* x\_i\}\}\{\\sum^\{N\}\_\{i=1\}\{u\_\{ij\}^m\}\} Cj=∑i=1Nuijm∑i=1Nuijm∗xi
3.  更新U，通过之前算出来的类中心  
     u i j = 1 ∑ k = 1 C ( ∣ ∣ x i − c j ∣ ∣ ∣ ∣ x i − c k ∣ ∣ ) 2 m − 1 u\_\{ij\} = \\frac\{1\}\{\\sum^\{C\}\_\{k=1\}\{(\\frac\{||x\_i-c\_j||\}\{||x\_i-c\_k||\})^\{\\frac\{2\}\{m-1\}\}\}\} uij=∑k=1C(∣∣xi−ck∣∣∣∣xi−cj∣∣)m−121
4.  如果u变化的无穷范小于某个值的时候，就停下来，否者就转到第2步

其实看到这里，一般来说直接公式来做，就可以把算法实现了。

**但我偷了个懒，找了一份代码，原始的代码有些问题，我做了修改后，然后写上了备注（部分备注我写的是英文的~）**

## Python代码实现 ##

*  accuracy函数是用来验证的
 *  其他函数都是实现fcm的部分
 *  数据文件我放到后面，大家复制之后另存为“SPECTF\_New.csv”即可

import pandas as pd
    import numpy as np
    import random
    import operator
    import math
    
    df_full = pd.read_csv("SPECTF_New.csv")
    columns = list(df_full.columns)
    features = columns[:len(columns) - 1]
    class_labels = list(df_full[columns[-1]])
    df = df_full[features]
    
    # Number of Attributes
    num_attr = len(df.columns) - 1
    
    # Number of Clusters
    k = 2
    
    # Maximum number of iterations
    MAX_ITER = 100
    
    # Number of data points
    n = len(df)
    
    # Fuzzy parameter
    m = 2.00
    
    
    def accuracy(cluster_labels, class_labels):
        county = [0, 0]
        countn = [0, 0]
        tp = [0, 0]
        tn = [0, 0]
        fp = [0, 0]
        fn = [0, 0]
    
        for i in range(len(df)):
            # Yes = 1, No = 0
            if cluster_labels[i] == 1 and class_labels[i] == 'Yes':
                tp[0] = tp[0] + 1
            if cluster_labels[i] == 0 and class_labels[i] == 'No':
                tn[0] = tn[0] + 1
            if cluster_labels[i] == 1 and class_labels[i] == 'No':
                fp[0] = fp[0] + 1
            if cluster_labels[i] == 0 and class_labels[i] == 'Yes':
                fn[0] = fn[0] + 1
    
        for i in range(len(df)):
            # Yes = 0, No = 1
            if cluster_labels[i] == 0 and class_labels[i] == 'Yes':
                tp[1] = tp[1] + 1
            if cluster_labels[i] == 1 and class_labels[i] == 'No':
                tn[1] = tn[1] + 1
            if cluster_labels[i] == 0 and class_labels[i] == 'No':
                fp[1] = fp[1] + 1
            if cluster_labels[i] == 1 and class_labels[i] == 'Yes':
                fn[1] = fn[1] + 1
    
        a0 = float((tp[0] + tn[0])) / (tp[0] + tn[0] + fn[0] + fp[0])
        a1 = float((tp[1] + tn[1])) / (tp[1] + tn[1] + fn[1] + fp[1])
        p0 = float(tp[0]) / (tp[0] + fp[0])
        p1 = float(tp[1]) / (tp[1] + fp[1])
        r0 = float(tp[0]) / (tp[0] + fn[0])
        r1 = float(tp[1]) / (tp[1] + fn[1])
    
        accuracy = [a0 * 100, a1 * 100]
        precision = [p0 * 100, p1 * 100]
        recall = [r0 * 100, r1 * 100]
    
        return accuracy, precision, recall
    
    
    # 返回的矩阵是每个点属于不同的集群的概率（隶属度）
    # 随机生成
    def initializeMembershipMatrix():
        membership_mat = list()
        for i in range(n):
            random_num_list = [random.random() for i in range(k)]
            summation = sum(random_num_list)
            temp_list = [x / summation for x in random_num_list]
            membership_mat.append(temp_list)
        return membership_mat
    
    
    def calculateClusterCenter(membership_mat):
        cluster_mem_val = list(zip(*membership_mat))
        # cluster_mem_val 's shape is (k, n)
        cluster_centers = list()
        for j in range(k):  # 选定一个类别
            x = cluster_mem_val[j]
            xraised = [e ** m for e in x]  # m is a Fuzzy parameter
            denominator = sum(xraised)  # 求和
    
            # 将对应点向量乘上它在该类别上的概率 得到概率向量
            temp_num = list()
            for i in range(n):
                data_point = list(df.iloc[i])
                prod = [xraised[i] * val for val in data_point]
                temp_num.append(prod)
    
            # 将所有点在对应特征下的概率累积求和
            numerator = map(sum, zip(*temp_num))
            center = [z / denominator for z in numerator]
            # the shape of center is (num_attr,) , which is the number of the features.
            # 本质上做的是加权平均，关于不同的特征，在不同的点上做加权。权重即为初始概率
            cluster_centers.append(center)
        return cluster_centers
    
    
    def updateMembershipValue(membership_mat, cluster_centers):
        # m is the Fuzzy parameter.
        p = float(2 / (m - 1))
        # cluster_centers : (k, num_attr)
        for i in range(n):
            x = list(df.iloc[i])
            # 算和两个中心的距离，这里采用的是二范数
            distances = [np.linalg.norm(list(map(operator.sub, x, cluster_centers[j]))) for j in range(k)]
            # 更新概率矩阵
            for j in range(k):
                den = sum([math.pow(float(distances[j] / distances[c]), p) for c in range(k)])
                membership_mat[i][j] = float(1 / den)
        return membership_mat
    
    
    def getClusters(membership_mat):
        cluster_labels = list()
        for i in range(n):
            max_val, idx = max((val, idx) for (idx, val) in enumerate(membership_mat[i]))
            cluster_labels.append(idx)
        return cluster_labels
    
    
    def fuzzyCMeansClustering():
        # Membership Matrix
        membership_mat = initializeMembershipMatrix()
        curr = 0
        while curr <= MAX_ITER:
            cluster_centers = calculateClusterCenter(membership_mat)
            # cluster_centers: (k, num_attr). k means k clusters. And num_attr means num_attr features.
            # 更新 membership_mat 矩阵
            membership_mat = updateMembershipValue(membership_mat, cluster_centers)
            cluster_labels = getClusters(membership_mat)
            curr += 1
        # print(membership_mat)
        return cluster_labels, cluster_centers
    
    
    labels, centers = fuzzyCMeansClustering()
    print(labels)
    print(len(labels))
    # a, p, r = accuracy(labels, class_labels)
    #
    # print("Accuracy = " + str(a))
    # print("Precision = " + str(p))
    # print("Recall = " + str(r))

*  数据

Attr_1,Attr_2,Attr_3,Attr_4,Attr_5,Attr_6,Attr_7,Attr_8,Attr_9,Attr_10,Attr_11,Attr_12,Attr_13,Attr_14,Attr_15,Attr_16,Attr_17,Attr_18,Attr_19,Attr_20,Attr_21,Attr_22,Attr_23,Attr_24,Attr_25,Attr_26,Attr_27,Attr_28,Attr_29,Attr_30,Attr_31,Attr_32,Attr_33,Attr_34,Attr_35,Attr_36,Attr_37,Attr_38,Attr_39,Attr_40,Attr_41,Attr_42,Attr_43,Attr_44,Class
    57,69,68,75,69,74,73,71,57,61,72,74,73,69,61,58,60,55,71,62,79,70,77,71,65,63,69,55,61,68,75,74,63,64,63,58,69,67,79,77,72,70,61,65,Yes
    76,59,82,76,80,56,74,67,67,58,77,71,56,68,60,64,66,66,66,66,82,79,40,45,49,48,75,70,64,35,71,60,39,28,71,66,73,61,71,49,53,45,29,15,Yes
    65,62,67,68,65,67,71,71,64,56,73,72,68,69,56,57,67,62,74,66,80,76,80,78,53,47,48,36,68,65,74,73,60,60,67,63,74,63,77,79,68,70,59,56,Yes
    70,54,66,66,76,46,74,58,68,52,81,58,67,58,68,32,73,59,76,51,82,57,76,54,58,30,69,41,59,59,67,73,62,55,60,55,65,56,65,44,73,36,51,28,Yes
    64,64,70,75,70,71,74,71,59,60,62,68,70,66,69,72,69,69,61,63,56,60,62,66,69,71,62,63,67,65,62,58,52,51,67,66,61,56,64,65,71,73,57,63,Yes
    65,67,69,76,62,68,65,66,65,64,74,73,60,75,66,63,64,62,73,65,77,74,69,69,66,59,68,59,69,69,76,79,65,63,60,60,69,64,69,74,69,70,62,57,No
    68,70,69,74,65,70,72,73,71,68,73,70,68,74,63,65,65,63,70,67,74,70,69,72,62,63,63,61,66,66,74,80,70,72,69,67,60,57,69,62,66,75,50,50,No
    64,66,68,71,62,64,74,73,63,67,66,74,70,74,59,64,75,73,70,66,79,81,79,78,61,62,76,72,67,67,71,75,65,62,70,69,68,65,75,72,62,64,57,54,No
    58,63,80,71,76,70,70,71,64,63,74,78,77,75,62,61,62,56,71,52,82,71,84,85,71,71,57,47,42,39,70,70,50,70,50,46,58,60,76,73,82,77,65,66,No
    77,79,79,77,74,76,76,81,65,68,66,66,74,73,72,68,67,73,63,62,72,67,76,69,68,64,64,61,69,68,73,75,70,66,64,70,70,70,73,76,79,73,65,63,No
    54,53,73,68,77,65,65,72,60,50,69,64,73,75,74,76,69,72,66,60,74,67,68,69,69,78,56,67,69,61,76,71,67,64,73,70,55,49,70,61,73,70,61,61,Yes
    59,57,67,71,66,68,68,70,56,62,77,61,67,71,75,71,67,64,62,54,64,75,71,72,76,79,75,70,71,77,71,69,56,54,62,64,56,53,71,68,64,63,56,56,No
    68,64,74,80,76,72,78,75,67,64,75,80,78,77,66,64,67,67,70,60,78,82,70,68,63,60,64,60,54,56,70,73,59,65,55,58,50,51,73,70,69,65,42,41,No
    78,73,68,74,68,69,63,74,68,67,73,73,66,71,64,67,66,68,61,66,75,71,60,62,64,66,65,67,66,62,74,75,61,61,63,66,68,65,71,62,69,67,61,59,Yes
    64,72,70,74,63,70,73,74,61,69,65,75,61,71,65,67,73,69,72,71,74,81,69,69,65,65,78,75,67,71,66,74,54,60,64,68,64,68,69,71,65,65,56,58,Yes
    70,64,68,67,76,68,76,69,67,64,69,65,62,65,70,67,74,68,65,65,74,75,64,69,63,63,64,64,56,61,62,68,66,66,62,58,57,48,75,64,79,74,59,58,No
    71,75,78,78,68,67,75,72,67,68,72,75,74,74,67,66,66,67,66,66,78,80,73,75,67,72,67,67,67,65,77,78,61,64,63,66,51,57,77,67,78,76,60,59,No
    56,56,63,66,76,76,68,73,62,54,65,62,70,65,74,72,65,64,64,53,64,56,63,61,73,64,66,60,66,74,76,75,65,61,71,73,60,53,61,73,67,68,59,56,No
    72,66,75,67,61,59,64,63,61,67,75,76,66,48,61,56,69,68,68,68,68,75,69,67,68,71,70,68,48,47,74,79,63,75,62,62,64,67,56,52,69,83,59,73,Yes
    71,76,74,79,71,69,77,75,64,64,75,78,69,70,59,52,71,62,47,50,68,65,67,62,56,48,58,50,65,63,75,75,64,62,60,56,64,63,61,65,64,58,51,38,Yes
    68,70,66,72,63,71,77,82,61,63,61,62,61,65,65,62,72,77,69,73,72,78,74,77,69,69,77,74,64,63,66,70,58,60,65,69,75,77,77,77,69,77,65,64,No
    64,53,74,70,65,63,70,70,57,57,64,64,73,74,65,59,65,63,63,62,72,73,79,76,75,68,60,58,69,66,72,76,64,65,63,65,63,65,75,80,74,67,71,67,No
    74,73,72,79,66,61,76,66,65,64,78,74,62,57,48,36,62,50,67,63,79,70,61,57,52,36,69,49,55,65,74,73,58,60,64,62,73,69,62,67,60,56,53,46,Yes
    69,64,73,72,49,70,66,71,57,56,64,62,76,74,65,62,63,58,63,63,75,76,78,80,75,77,51,62,74,68,77,77,70,68,68,64,59,58,69,66,74,75,62,59,No
    70,75,72,72,67,71,71,78,63,67,73,76,71,74,59,61,67,64,74,71,77,77,70,72,61,61,62,58,63,69,76,75,64,65,66,67,68,70,70,71,64,67,56,54,No
    63,63,69,72,67,62,65,57,68,53,68,71,73,78,64,58,61,54,70,61,72,67,72,68,57,55,61,53,66,60,76,77,73,66,66,58,75,70,77,67,78,68,64,58,Yes
    63,58,66,55,56,58,69,74,44,48,63,60,76,67,73,73,58,66,68,63,72,74,70,72,77,75,70,71,71,67,75,73,60,59,71,70,65,62,70,69,71,70,58,61,Yes
    71,61,74,74,76,74,69,56,68,78,71,78,58,64,70,72,71,68,72,71,79,78,67,68,63,60,67,67,76,74,67,79,67,71,71,64,70,74,83,76,74,73,54,54,No
    67,57,73,78,63,68,72,73,61,59,59,76,71,72,69,66,70,68,65,77,79,68,71,75,62,66,70,78,68,69,70,76,65,65,66,67,62,72,69,72,70,68,60,59,No
    62,67,68,70,65,70,73,77,69,70,69,73,71,74,71,71,76,75,66,67,73,73,70,74,63,67,58,68,66,69,78,79,69,70,71,73,72,71,73,77,72,76,64,66,No
    70,72,65,64,71,69,75,76,65,68,69,79,65,74,62,67,73,73,53,51,72,69,74,68,49,44,52,48,65,68,64,72,57,58,66,69,64,69,76,73,66,69,50,53,Yes
    70,64,52,58,75,89,70,72,26,30,46,55,54,59,40,40,39,37,35,17,59,52,66,72,23,46,8,31,17,20,49,72,61,70,31,13,40,23,31,30,57,67,41,57,Yes
    67,65,77,74,67,66,67,70,65,64,75,78,66,74,62,60,65,65,73,72,75,76,74,81,66,65,65,63,63,67,76,80,63,64,63,64,73,72,76,75,72,74,65,64,No
    76,72,73,69,67,73,74,72,60,65,73,66,66,73,68,67,69,70,60,58,66,76,69,75,65,64,63,60,74,71,77,79,61,68,71,70,62,63,73,76,62,69,52,59,No
    61,63,58,62,56,60,67,75,61,57,64,71,56,59,66,62,73,76,71,75,83,84,69,71,69,69,69,71,49,43,59,64,56,61,64,72,70,73,69,70,65,68,65,62,Yes
    74,81,80,78,70,69,74,77,69,71,73,76,68,68,62,61,68,68,67,70,74,80,68,74,57,62,57,65,61,65,71,76,63,65,67,67,70,74,63,72,68,70,61,64,No
    75,71,54,51,53,50,68,69,46,55,11,12,43,48,61,60,73,77,46,45,68,59,65,73,54,60,55,66,54,41,53,52,58,63,72,65,33,23,64,54,36,46,45,52,Yes
    68,64,65,68,63,64,77,73,75,72,80,77,70,71,61,61,73,68,63,62,76,73,69,69,48,59,62,44,66,59,75,74,64,64,63,61,70,69,74,67,51,48,45,45,Yes
    70,72,70,70,65,69,70,65,69,72,77,78,68,71,63,70,69,71,68,74,75,74,69,65,71,68,63,64,66,68,73,75,67,67,69,65,66,71,69,65,78,75,66,63,No
    76,75,68,78,71,72,72,75,61,65,67,70,67,75,60,58,63,67,59,63,67,72,74,73,56,56,52,52,67,68,73,78,65,68,61,67,69,74,77,75,74,70,63,61,No
    69,66,62,75,67,71,72,76,69,70,66,69,71,80,66,64,71,77,65,61,72,67,71,69,65,57,69,65,68,65,76,73,63,64,69,70,72,72,69,68,70,73,63,59,Yes
    80,76,75,75,69,68,74,75,77,77,76,78,74,70,66,65,67,75,74,73,74,77,68,67,61,58,60,67,61,63,75,75,66,62,59,61,77,74,69,67,65,66,61,58,No
    72,62,69,67,78,82,74,65,69,63,70,70,72,74,70,71,72,75,66,65,73,78,74,79,74,69,69,70,71,69,72,70,62,65,65,71,63,60,69,73,67,71,56,58,Yes
    71,75,76,74,71,68,67,68,69,75,75,74,59,58,71,69,70,74,74,72,71,78,69,72,69,72,63,61,59,70,72,75,61,66,70,71,59,64,64,60,72,61,55,63,Yes
    60,51,75,60,65,45,64,55,55,61,66,74,61,50,62,41,70,63,60,62,76,69,70,54,51,47,77,80,69,48,74,59,72,57,76,68,69,63,62,53,57,31,46,30,Yes
    74,73,72,75,63,62,67,67,73,74,75,79,70,71,64,67,65,69,79,78,81,80,71,73,60,62,69,67,69,69,75,75,66,67,67,66,71,73,66,69,62,65,55,56,No
    75,75,70,77,67,75,75,75,67,66,74,73,68,72,64,70,76,70,67,63,74,75,72,68,69,68,75,69,71,74,75,76,63,70,71,69,66,63,70,73,66,68,58,59,No
    62,67,64,70,59,58,67,74,60,66,68,68,73,71,60,63,64,74,64,65,74,77,69,73,59,58,58,67,65,69,78,76,61,62,64,67,72,74,71,71,71,69,66,61,No
    61,60,60,62,64,72,68,67,74,68,76,70,74,71,76,74,74,70,75,66,69,62,65,60,66,65,68,59,64,59,72,65,55,56,66,66,66,60,60,58,60,67,49,52,Yes
    78,76,71,72,65,71,75,74,70,64,65,76,65,73,59,57,65,65,73,73,81,80,68,66,59,44,62,63,62,59,71,74,59,60,64,61,77,76,62,67,44,42,44,30,Yes
    70,66,61,66,61,58,69,69,72,68,62,71,71,71,63,59,74,75,70,69,83,77,73,70,41,37,39,40,58,46,75,73,65,66,67,69,70,66,70,64,60,55,49,41,Yes
    73,74,65,66,69,69,67,81,65,62,69,65,67,68,70,67,72,68,66,66,78,61,67,70,67,63,68,66,70,70,69,70,66,66,66,69,72,70,74,76,75,72,67,63,No
    79,78,66,63,69,62,78,70,72,71,73,78,75,65,68,62,76,71,68,68,72,71,52,48,23,26,66,59,66,66,72,74,56,58,67,63,66,69,70,74,34,33,11,12,Yes
    66,81,75,72,69,67,74,81,67,73,76,75,69,64,58,57,74,74,56,62,74,78,55,50,37,38,65,73,61,61,73,73,61,63,67,66,60,71,46,58,35,37,24,20,Yes
    76,77,69,70,64,69,76,80,50,56,70,74,61,55,54,59,65,65,53,72,76,73,51,47,43,46,66,80,73,73,71,65,60,53,69,70,54,62,64,66,51,42,28,22,Yes
    66,64,64,66,67,72,72,77,65,66,64,64,57,61,70,66,74,78,73,72,77,75,60,58,58,61,63,60,59,60,65,65,58,58,69,73,76,75,73,75,72,72,62,62,No
    72,63,68,62,72,63,79,61,57,49,76,75,55,57,43,37,54,52,57,56,78,78,57,55,35,37,57,57,41,35,67,70,75,72,53,46,63,62,53,43,38,35,32,26,Yes
    32,41,76,34,65,53,30,54,16,51,61,43,74,70,62,21,34,42,61,37,58,66,54,49,17,19,11,42,53,30,71,9,61,16,31,43,67,61,29,31,17,8,18,11,Yes
    69,78,74,76,70,67,69,73,68,75,75,76,71,77,58,61,66,70,67,72,76,72,56,62,56,61,57,62,67,73,76,74,58,63,64,68,66,76,70,72,64,68,60,56,No
    40,73,61,74,61,67,56,75,64,71,75,76,63,61,56,67,70,73,69,60,74,63,65,73,57,63,66,69,60,66,72,71,57,64,64,69,67,68,59,66,55,62,51,60,Yes
    65,66,71,72,67,75,76,83,70,74,70,76,70,68,63,71,69,76,72,73,76,80,69,68,57,59,59,56,62,68,75,73,65,61,69,73,66,70,63,65,65,67,53,42,Yes
    80,74,82,77,74,74,73,77,64,61,73,73,73,72,62,66,66,68,63,61,69,75,70,75,59,64,63,69,66,66,70,77,62,62,60,65,67,66,74,71,66,71,59,62,Yes
    67,64,73,75,77,77,74,70,65,62,74,75,65,67,68,70,66,69,67,60,74,75,62,64,66,71,62,61,64,69,73,76,64,66,61,64,65,60,68,75,74,80,67,68,No
    71,71,69,71,65,65,76,73,67,66,69,79,76,76,63,62,74,71,58,66,76,78,78,74,68,66,69,68,68,68,71,74,59,57,65,66,73,71,78,74,68,70,57,55,No
    63,61,75,72,68,71,69,70,64,56,70,75,76,73,70,72,76,73,68,68,79,76,68,76,66,73,58,68,72,75,72,75,65,61,66,67,58,57,72,72,68,71,57,58,No
    70,69,67,66,68,60,76,77,70,67,71,71,79,79,70,64,77,76,63,54,68,65,72,67,59,52,56,50,67,61,74,72,67,59,68,66,73,68,74,68,77,69,65,62,Yes
    59,75,70,76,62,70,65,74,65,67,75,76,70,73,63,61,74,67,78,69,75,73,70,68,67,64,79,68,70,75,76,77,59,63,72,69,64,64,65,72,61,61,51,55,No
    64,58,70,78,66,66,74,72,66,63,72,74,72,65,59,58,64,67,63,61,75,74,67,58,60,53,61,58,62,61,76,72,64,65,62,64,77,71,74,72,74,73,70,59,No
    59,58,69,74,71,73,70,68,57,55,64,68,76,75,67,66,66,63,72,67,77,75,80,75,73,69,65,61,71,75,71,77,65,66,66,66,61,56,74,71,72,69,62,60,No
    72,70,75,80,73,70,76,73,66,56,72,70,73,75,67,65,69,69,73,72,81,77,80,79,67,64,64,66,69,68,70,75,63,59,66,63,74,77,81,78,79,75,65,66,No
    68,59,77,69,77,64,75,71,64,53,67,63,66,74,74,62,67,65,70,61,73,66,78,75,72,67,67,53,72,64,71,77,66,60,73,73,70,58,70,59,77,71,70,63,Yes
    61,68,62,70,76,79,71,71,73,77,75,77,68,73,72,72,71,68,72,75,81,80,72,73,61,67,62,61,66,68,72,71,67,67,69,69,66,71,67,66,74,71,58,58,No
    75,73,72,77,68,67,76,73,67,65,76,78,66,74,67,62,70,69,66,64,77,74,75,73,67,69,73,69,68,68,72,74,61,61,70,67,72,71,79,75,77,75,67,71,No
    70,66,66,68,71,69,64,61,68,67,50,53,73,71,73,63,71,73,80,81,82,82,67,71,52,47,67,64,66,67,66,75,58,62,65,65,71,67,70,71,67,64,52,53,Yes
    69,68,75,74,78,72,75,72,61,57,72,71,75,72,70,68,68,62,62,66,67,67,74,78,64,68,62,62,64,63,75,77,66,67,69,65,62,63,64,59,74,75,63,67,Yes
    73,80,78,78,75,73,78,75,70,66,77,77,67,71,60,63,71,74,77,75,74,76,61,67,60,60,64,63,62,58,72,77,59,58,65,70,68,69,64,64,63,63,56,51,No
    55,66,58,75,71,77,68,73,63,69,77,78,60,69,59,60,69,69,67,70,72,80,67,72,53,60,70,58,46,67,68,84,69,79,70,74,62,71,67,66,63,61,53,60,Yes
    66,67,63,70,69,70,73,72,61,62,68,68,70,71,71,67,71,69,65,65,76,78,71,70,65,64,68,71,70,71,73,74,58,63,68,71,70,72,77,79,79,79,66,66,No
    70,69,60,62,58,60,71,77,69,69,73,68,68,70,69,65,76,75,63,64,67,74,56,60,54,44,68,69,68,68,74,73,61,59,68,67,64,68,64,76,64,61,54,49,Yes
    75,72,75,79,72,68,79,77,69,66,73,77,67,73,57,58,69,69,67,65,77,68,69,65,58,54,68,60,67,66,75,78,63,66,68,64,72,69,73,61,52,44,34,37,Yes
    61,76,71,68,77,69,77,69,64,75,71,81,75,72,71,69,70,73,61,71,69,79,64,65,62,66,61,65,71,68,67,71,59,64,66,65,60,68,74,71,69,68,63,59,No
    76,73,74,76,60,69,76,76,68,69,78,79,57,62,69,69,67,66,73,69,80,81,58,68,75,69,73,70,58,65,79,76,74,71,66,64,65,62,78,68,75,68,62,60,No
    59,62,72,74,66,66,74,76,63,67,72,76,71,74,66,64,70,69,63,66,70,72,70,76,65,69,61,66,64,65,67,72,57,63,65,71,67,69,77,78,77,76,70,70,No
    69,71,70,78,61,63,67,65,59,59,66,69,71,75,65,58,60,55,62,59,67,66,74,74,64,60,57,54,70,73,69,76,62,64,61,61,66,65,72,73,68,68,59,63,Yes
    62,66,66,68,73,76,68,71,62,62,63,68,74,75,63,68,71,68,58,58,65,66,65,76,64,70,63,60,70,72,71,77,67,69,72,71,63,63,70,72,75,79,62,59,No
    59,68,69,67,69,59,78,73,66,65,77,73,74,66,66,55,71,66,69,68,75,73,80,79,69,65,69,66,68,65,75,71,59,61,65,64,73,71,81,75,74,65,69,66,No
    70,65,65,62,68,67,77,74,62,61,66,61,69,74,64,62,71,71,74,70,77,78,69,70,67,65,67,70,49,48,73,71,65,73,73,73,75,71,73,72,73,70,65,64,Yes
    59,52,70,67,73,66,72,61,58,52,72,71,70,77,66,65,67,55,61,57,68,66,72,74,63,64,56,54,67,54,76,74,65,67,66,56,62,56,72,62,74,74,64,67,Yes
    62,56,66,57,74,75,68,59,65,59,74,66,71,65,67,69,66,66,71,72,80,74,71,63,62,72,62,66,66,61,73,68,59,59,63,62,73,73,76,67,77,71,62,58,Yes
    74,69,75,70,70,74,77,77,65,67,73,72,69,73,68,66,69,68,67,63,78,74,71,63,66,61,68,63,74,69,74,75,65,61,66,67,63,61,71,68,66,65,54,57,No
    67,66,65,77,66,70,72,72,72,67,76,72,73,76,74,71,74,73,69,61,78,70,76,73,70,70,62,51,70,68,79,77,75,68,72,71,69,63,65,61,73,73,64,67,Yes
    71,62,70,64,67,64,79,65,70,69,72,71,68,65,61,61,73,71,75,74,80,74,54,47,53,37,77,68,72,59,72,68,60,60,73,70,66,65,64,55,61,41,51,46,Yes
    64,60,71,69,71,65,66,64,68,59,63,67,68,64,73,59,73,60,72,56,77,68,69,69,66,59,57,40,55,53,69,63,71,63,66,55,66,58,65,65,75,64,61,56,Yes
    64,70,71,69,72,70,75,78,61,66,69,68,68,70,71,70,75,76,73,72,80,78,79,81,74,70,72,79,73,75,77,73,65,64,72,72,59,62,71,74,68,67,58,57,No
    72,74,67,69,69,70,74,81,66,70,73,78,69,80,65,65,70,77,69,70,73,79,64,68,56,58,67,64,68,68,69,74,62,67,66,70,73,77,74,77,71,72,63,65,No
    62,71,78,84,64,68,72,74,53,57,71,70,71,72,54,53,63,67,54,57,71,71,70,74,54,57,54,57,62,64,75,72,62,65,60,64,64,67,72,77,62,62,61,65,No
    77,61,62,68,62,58,72,68,77,71,76,77,72,75,62,57,77,74,61,58,72,76,69,68,56,53,57,54,69,70,73,79,65,70,66,68,67,66,71,67,60,60,53,57,Yes
    65,68,70,78,65,72,72,74,64,69,71,73,72,68,62,62,65,62,72,75,79,78,72,76,66,67,62,61,68,76,72,78,65,64,67,63,64,67,67,77,66,66,59,57,No
    76,69,78,73,68,67,75,70,77,70,79,73,79,75,74,71,76,68,81,79,77,78,75,76,66,76,65,67,67,57,68,75,50,62,62,59,47,49,75,65,74,70,51,48,Yes
    68,65,72,72,47,74,76,74,67,66,71,69,69,67,63,64,68,68,70,74,77,77,73,60,49,48,42,69,70,69,76,79,63,66,64,69,71,73,73,75,68,56,58,44,No
    72,61,64,66,64,59,68,66,76,66,77,75,71,72,72,62,72,68,77,78,77,81,67,67,69,68,65,68,69,64,72,73,56,56,69,64,67,71,69,68,65,73,56,52,No
    65,69,66,76,58,67,65,72,66,64,77,75,64,62,63,59,71,61,67,45,74,45,66,46,64,48,62,27,65,67,72,72,62,66,71,64,71,70,72,69,70,65,63,61,Yes
    67,51,73,65,69,56,72,63,64,56,68,67,70,62,70,58,68,62,65,59,77,69,68,59,64,55,65,60,70,60,72,65,58,51,66,59,71,62,74,60,76,65,62,56,Yes
    73,76,68,74,56,59,73,76,54,48,75,78,47,53,25,19,60,56,56,54,80,79,47,53,19,14,58,50,67,71,63,54,49,48,66,65,62,58,57,72,31,30,15,11,Yes
    59,65,53,60,72,74,67,69,64,67,64,65,71,70,68,71,72,70,70,70,75,78,72,71,71,71,67,64,67,71,71,74,62,66,72,73,57,57,64,71,70,69,53,49,No
    76,65,60,40,32,34,65,50,53,37,66,53,33,31,30,30,69,75,64,45,68,65,57,43,23,23,53,77,48,32,55,32,48,23,62,51,65,59,43,39,35,30,24,21,Yes
    70,71,71,74,68,66,72,70,66,69,74,72,70,69,64,66,73,72,75,73,81,81,76,75,71,70,74,82,69,72,76,74,60,56,66,66,64,64,73,72,66,63,54,58,No
    68,76,79,78,63,73,68,78,64,71,73,77,67,71,58,57,61,63,52,64,64,74,53,72,36,44,52,54,49,56,73,81,65,80,53,60,63,70,58,64,52,57,49,50,Yes
    64,63,62,59,60,61,70,74,68,63,66,68,64,66,67,66,72,68,63,59,75,72,67,62,63,55,66,56,65,64,70,71,61,63,67,63,69,69,77,65,74,62,60,54,Yes
    66,54,69,66,69,69,75,72,63,62,68,66,68,70,71,68,70,69,66,68,73,72,65,73,67,63,60,57,70,68,75,75,65,67,69,65,65,64,67,69,71,68,59,59,No