利用粗糙集进行西瓜分类（上）

最近在学习粗糙集，但是其抽象的概念令我学习异常吃力。我使用的是周炜编著的《粗糙集理论及应用》，这本书概念居多，很多数学符号我没有见过，又不知道怎么查，so，说多了都是泪。为了更好的理解粗糙集的基本理论和概念，我使用西瓜书中对西瓜分类的例子辅助理解粗糙集在分类中的应用。本篇的目的是记录一些概念名词，并且利用python实现部分粗糙集的工作。
首先贴出西瓜书中的数据集。这个数据集是西瓜书中的西瓜数据集2.0，具体位置在76页的表4.1。粗糙集和决策树的对比我也很感兴趣，但是粗糙集我现在实在没怎么懂 (_, ) ，留在后面吧。

ID,色泽,根蒂,敲声,纹理,脐部,触感,好瓜
1,青绿,蜷缩,浊响,清晰,凹陷,硬滑,好瓜
2,乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,好瓜
3,乌黑,蜷缩,浊响,清晰,凹陷,硬滑,好瓜
4,青绿,蜷缩,沉闷,清晰,凹陷,硬滑,好瓜
5,浅白,蜷缩,浊响,清晰,凹陷,硬滑,好瓜
6,青绿,稍蜷,浊响,清晰,稍凹,软粘,好瓜
7,乌黑,稍蜷,浊响,稍糊,稍凹,软粘,好瓜
8,乌黑,稍蜷,浊响,清晰,稍凹,硬滑,好瓜
9,乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,坏瓜
10,青绿,硬挺,清脆,清晰,平坦,软粘,坏瓜
11,浅白,硬挺,清脆,模糊,平坦,硬滑,坏瓜
12,浅白,蜷缩,浊响,模糊,平坦,软粘,坏瓜
13,青绿,稍蜷,浊响,稍糊,凹陷,硬滑,坏瓜
14,浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,坏瓜
15,乌黑,稍蜷,浊响,清晰,稍凹,软粘,坏瓜
16,浅白,蜷缩,浊响,模糊,平坦,硬滑,坏瓜
17,青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,坏瓜

数据集可以直接复制下来保存为CSV文件。第一行西瓜属性的集合书中称为知识库。在信息系统中也称为属性集合。在决策表中[色泽,根蒂,敲声,纹理,脐部,触感]称为条件属性集合，最后一个属性称为决策属性集合，在机器学习中也成为label。在粗糙集的学习中感觉一个难点是名词都比较陌生。
一：知识约简和核
在学习中我认为上近似，下近似，正域，负域和边界域还是比较好理解的。从知识约简开始就不太好理解了。书中对约简的定义如下（原书中65页定义3.11）。

设Ω是论域U上的一个知识库，Δ是Ω的一个非空子族。若Δ是独立的且ind（Δ）=ind（Ω），则称Δ为Ω的一个约简。

其中ind（）是难区分关系的意思。（没学离散数学就学粗糙集就是一个大坑）。具体到西瓜数据集中。假设Δ={色泽}，Ω={色泽，根蒂}。在整个论域U中，Δ等价类就是所有色泽相同的样本组成的集合的集合。详细点说有三个颜色分别是青绿，乌黑和浅白。每个颜色相同的样本组成一个集合也就是：乌黑：{2, 3, 7, 8, 9, 15}, 浅白：{5, 11, 12, 14, 16}, 青绿：{1, 4, 6, 10, 13, 17}。那么U/Δ，也称商集为{{2, 3, 7, 8, 9, 15}, {5, 11, 12, 14, 16}, {1, 4, 6, 10, 13, 17}}。而对于多个属性而言U/Ω，就是属性的等价类求交集，注意具体实现是属性a的每个分类，对属性b的所有分类求交集。代码实现如下所示。

def liang_zu_guan_xi_de_deng_jia_lei(list_a,list_b):
    answer = []
    for A in list_a:
        for B in list_b:
            tmp = A&B
            if tmp != set():
                answer.append(tmp)
    return answer

list_a和list_b即为两个属性，可以理解为为{色泽}和{根蒂}，或者是{色泽}和{根蒂，敲声}。python中使用set实现。为了操作方便我是用了list代替部分set的表达。注意两者互转有限制，如果重构代码建议均使用set。
好说回知识约简。不考虑严苛的数学限制条件，（数学不好的学计算机伤心啊）如果U/A == U/Ω，那么Ω就是A的一个约简。A是所有条件属性的集合（暂时不考虑决策属性）。代码显示如下：

    for level in range(2,equivalence_class_count+2):#因为是二元关系，所以二元关系对的层数是总数减一
#        如果leve为2代表U/{a,b},如果level为3代表U/{a,b,c}
        for class_combination in itertools.combinations(range(equivalence_class_count), level):
#            枚举不重复的等价类组合。例如：('A', 'B') ('A', 'C') ('A', 'D') ('B', 'C') ('B', 'D') ('C', 'D')
            combination_id = "".join([str(o) for o in class_combination])
            previous_equivalence_class_id = combination_id[:-1]
            latter_equivalence_class_id = combination_id[-1]
            conditional_attribute_set[combination_id] = \
            liang_zu_guan_xi_de_deng_jia_lei(\
                                             conditional_attribute_set[previous_equivalence_class_id],\
                                             conditional_attribute_set[latter_equivalence_class_id])

代码的功能是枚举出所有的A的子集，并求出所有子集相应的U/Ω。依此进行对比。此外实现的过程中有一点问题，由于python中list和set不能实现无缝转换。详细说就是如果list中均为set那么这个list不能直接转换为set。所以U/A == U/Ω不方便直接对比，这里我是用list部分代替set，但是list是有序的。所以list（a）！=list（b）不等价于set（a）！=set（b）。这里我的处理方法较为笨拙，使用先验证两个集合的长度是否一致，再相互测试包含关系进行对比。不建议这么使用。代码为：

        if len(conditional_attribute_set[key]) == len(conditional_attribute_set["".join([str(o) for o in range(equivalence_class_count)])]):
            set_equ_flag = True
            for a in conditional_attribute_set[key]:
                if a not in conditional_attribute_set["".join([str(o) for o in range(equivalence_class_count)])]:
                    set_equ_flag = False
                    break
            for a in conditional_attribute_set["".join([str(o) for o in range(equivalence_class_count)])]:
                if a not in conditional_attribute_set[key]:
                    set_equ_flag = False
                    break
            if set_equ_flag:
                print(key)

总体代码如下，需要使用pandas读取csv文件。

# -*- coding: utf-8 -*-
"""
Created on Fri Jul 12 10:24:42 2019

@author: BHN
"""
import pandas as pd
import itertools

def Deal_data():
#    pandas分为Series和DataFrame两种数据形式。Series可以视为一维数组，DataFrame与array
#    的区别是其数据类型可以是不相同的
    df=pd.read_csv('data//watermelon.csv', encoding='gb18030')
#    print(df.columns)#打印pandas的标签
#    df.drop(df.columns[0],axis=1,inplace=True)#删除某一列
    answer = {}
    for class_num,a in enumerate(list(df.columns[1:-1])): #删除第一列的序数和最后一列的决策属性
        one_class_label = list(set(df[a].values))#DataFrame对应转成numpy的是to_numpy()
#        这行的功能是查看这一个属性中有几种独立的label
        single_class_conditional_attribute_set = []
        for b in one_class_label:
            single_class_conditional_attribute_set.append(set(df[df[a] == b].ID.values))
        answer[str(class_num)]=single_class_conditional_attribute_set
    
    answer_decision = {}
    one_class_label = list(set(df[df.columns[-1]].values))
    single_class_conditional_attribute_set = []
    for b in one_class_label:
        single_class_conditional_attribute_set.append(set(df[df[df.columns[-1]] == b].ID.values))
    answer_decision['0']=single_class_conditional_attribute_set
    return answer,answer_decision
        
def liang_zu_guan_xi_de_deng_jia_lei(list_a,list_b):
    answer = []
    for A in list_a:
        for B in list_b:
            tmp = A&B
            if tmp != set():
                answer.append(tmp)
    return answer

def Pos_2_attributes(C,D):
    answer = []
    for A in C:
        for B in D:
            if A.issubset(B):
                answer.append(A)
    if answer != []:
        union = answer[0]
        for a in answer:
            union = union|a
    else:
        union = set()
    return union
        
    
if __name__ =='__main__':
    conditional_attribute_set,decision_attribute_set = Deal_data()
    equivalence_class_count = len(conditional_attribute_set)
    for level in range(2,equivalence_class_count+2):#因为是二元关系，所以二元关系对的层数是总数减一
#        如果leve为2代表U/{a,b},如果level为3代表U/{a,b,c}
        for class_combination in itertools.combinations(range(equivalence_class_count), level):
#            枚举不重复的等价类组合。例如：('A', 'B') ('A', 'C') ('A', 'D') ('B', 'C') ('B', 'D') ('C', 'D')
            combination_id = "".join([str(o) for o in class_combination])
            previous_equivalence_class_id = combination_id[:-1]
            latter_equivalence_class_id = combination_id[-1]
            conditional_attribute_set[combination_id] = \
            liang_zu_guan_xi_de_deng_jia_lei(\
                                             conditional_attribute_set[previous_equivalence_class_id],\
                                             conditional_attribute_set[latter_equivalence_class_id])
    print(conditional_attribute_set)
    for key in conditional_attribute_set:
#        验证每一个商集是否与所有条件属性的商集相同
        if len(conditional_attribute_set[key]) == len(conditional_attribute_set["".join([str(o) for o in range(equivalence_class_count)])]):
            set_equ_flag = True
            for a in conditional_attribute_set[key]:
                if a not in conditional_attribute_set["".join([str(o) for o in range(equivalence_class_count)])]:
                    set_equ_flag = False
                    break
            for a in conditional_attribute_set["".join([str(o) for o in range(equivalence_class_count)])]:
                if a not in conditional_attribute_set[key]:
                    set_equ_flag = False
                    break
            if set_equ_flag:
                print(key)

可以观察到约简的结果。再西瓜数据集中可以观察到约简结果为01235
02345
也就是{色泽,根蒂,敲声,纹理,触感}和{色泽,敲声,纹理,脐部,触感}。
我除了对怎么吃西瓜优点了解，这个约简结果对不对页不知道，反正现在也很难挑到生瓜了吧。