粗糙集理论属性约简算法

大创项目，基于粗糙集理论的高校学生实践能力培养研究。进行了一段时间，有了点小成果，再此总结一下。

首先了解一下什么是粗糙集理论，它是处理不确定信息的一种方法。可以从不完备的信息中得出现有的规律，并从中提取出一些规则。

百度百科：https://baike.baidu.com/item/%E7%B2%97%E7%B3%99%E9%9B%86%E7%90%86%E8%AE%BA/4047224

https://baike.baidu.com/item/%E7%B2%97%E7%B3%99%E9%9B%86/8248139?fr=aladdin

其他更详细的参考论文，我们选择的是厦门大学黄丽萍写的论文《基于粗糙集的属性约简与规则提取》。

其中我们的属性约简算法就是参考她文中的改进的CEBARKCC算法。

首先描述一下我们的项目流程：

1.设计一个可以体现大学生实践能力的问卷

2.对问卷进行处理，即将数据都转换为方便处理的离散型数据

3.对数据进行属性约简，去掉无用的属性

4.对约简后的数据进行规则提取

5.分析提取出的规则

本次主要描述我们的属性约简算法

因为需要处理的数据并不是非常巨量，所以采用了基于信息熵的属性约简算法。

信息熵简介：https://baike.baidu.com/item/%E4%BF%A1%E6%81%AF%E7%86%B5/7302318?fr=aladdin

我们将要处理的信息假如是这样：

病人 头痛 胸口痛 体温 流感

a1 是 是 正常 否

a2 是 是 高 是

a3 是 是 很高 是

a4 否 是 正常 否

a5 否 否 高 否

a6 否 是 很高 是

a7 否 否 高 是

a8 否 是 很高 否

信息熵的主要公式：

image

其中

image

U为论域，即我们数据的 a1 到 a8

Xi 和 Yj 是属性集合，是针对某一属性来说的，举个例子，“头痛”这个属性可以分为

X1集合{a1,a2,a3}

X2集合{a4,a5,a6,a7,a8}

所以P（X1）= 3/8

头痛的信息熵就为：H（P）= 3/8 * log(3/8) + 5/8 * log(5/8)

代表头痛的不确定度。

由信息熵延伸一下，得到条件信息熵：

image

我们的算法思路很简单，从全集开始，依次去掉属性。如果这个属性的缺失导致决策属性（流感）的信息熵变大了，说明这个属性对与是否流感的判断有益，是核属性！

image

得到核属性集合只是第一步，下面运用黄丽萍的改进CEBARKCC算法得到约简：

image

算法的整体思路：

计算原本的数据中，条件属性集合对于决策属性的条件信息熵作为算法的终止值，

每次对所有的属性进行重要度的计算，如果这个属性对于当前条件集合来说重要度为0，则可以删除。然后挑选最重要的属性加入当前条件集合，进行下一轮循环。直到当前条件集合的条件信息熵与原本数据的条件信息熵相等。说明当前集合可以代替原本的集合。算法结束。

代码：

#include <windows.h>
#include <iostream>
#include <string>
#include <stdio.h>
#include <tchar.h>
#include <sstream>
#include<fstream>
#include <vector>

using namespace std;

class Tuple
{
public:
    Tuple();
    ~Tuple();
    string list[50];
    int PropertyNum;//属性个数
    int LineNum;//元组个数
    void outline(int a);//输出一行,a指输出元素个数
private:
    

};


void Tuple::outline(int a) {//输出一行
    cout << list[0];
    for (int i = 1; i <= a; i++) {
        cout << "\t" << list[i];
    }
    cout << endl;
}


Tuple::Tuple()
{
}

Tuple::~Tuple()
{
}

bool init(Tuple a[200])//初始化,定义读取的文件名
{
    LPCWSTR file = _T("输出.txt");
    DeleteFile(file);//删除现有的旧文件


    FILE *fp1 = NULL;
    FILE *fp2 = NULL;
    fp1 = fopen("实验.txt", "r");
    fp2 = fopen("输出.txt", "w");
    if (fp1 == NULL || fp2 == NULL) {//判断文件是否存在
        cout << "文件打开失败！" << endl;
        return false;
    }

    
    string st = "";
    string out;
    int i = 0;
    int j = 0;
    int k = 0;
    char s = NULL;
    s = fgetc(fp1);//读取第一个字符到s
    while (!feof(fp1)) {
        char out1[2] = { s,0 };
        out = out1;//字符转换为字符串
        cout << out;//打印字符
        //printf("%d  ",s);

        if (s == 10) {
            i++;
            j = 0;
            st = "";
        }
        else if (s == 9) {
            j++;
            st = "";
            if (j >= k)
                k = j;
        }
        else
            st = st + out;
        a[i].list[j] = st;//字符串输入元组中
        fputc(s, fp2);//写入输出文件
        s = fgetc(fp1);//取下一个字符
        //fprintf(fp2,"%c",s);
    }
    fclose(fp1);
    fclose(fp2);
    for (j = 0; j <= i; j++) {
        a[j].LineNum = i - 1;//元组个数
        a[j].PropertyNum = k;//属性个数
    }
    cout << "初始化成功！" << endl;
    return true;
}
string c2s(char a) {//单个字符转字符串
    char b[2] = {a,0};
    string s = b;
    return s;
}
string int2s(int a) {//整数转字符串
    string s;
    stringstream sstr;
    sstr << a;
    sstr >> s;
    return s;
}
int s2int(string s) {//字符串转整数
    int a;
    stringstream sstr;
    sstr << s;
    sstr >> a;
    return a;
}




float Entropymath(string a[],int b) {//信息熵的计算
    float s = 0;
    float k = 0;
    b = (float)b;
    for (int i = 1; i <= b; i++) {
        if (a[i] == "&&")
            continue;
        k = 1;
        for (int j = i+1; j <= b; j++) {
            if (a[i] == a[j]) {
                k++;
                a[j] = "&&";
            }
        }
        //cout << k << endl;
        s = s - k*log2(k / b) / b;
    }
    return s;
}


float Entropy(Tuple a[], string str2 = "all") {//计算决策属性的信息熵和关于其他属性的条件熵
    string b[200];
    string c[200];
    float x = 0;
    if (str2 == "all") {//非条件信息熵
        for (int i = 1; i <= a[0].LineNum; i++) {
            b[i] = a[i].list[a[i].PropertyNum];
        }
        x = Entropymath(b, a[0].LineNum);
        return x;
    }

    string s = "";//条件信息熵
    for (int i = 0; i <= str2.length(); i++) {
        if (str2[i] == ','|| str2[i] == 0) {//函数传递进来的参数是属性之间用“，”隔开
            int k = 1;                      //分析条件集合拼接属性值，便于比较
            for (; k <= a[0].PropertyNum; k++) {
                if (s == a[0].list[k])
                    break;
            }
            for (int j = 1; j <= a[0].LineNum; j++) {
                c[j] = c[j] + a[j].list[k];
            }
            s = "";
            continue;
        }
        s = s + c2s(str2[i]);
    }

    for (int i = 1; i <= a[0].LineNum; i++) {//比较条件集合的值，计算条件信息熵
        if (c[i] == "&&")
            continue;
        int k = 1;
        b[1] = a[i].list[a[0].PropertyNum];
        for (int j = i + 1; j <= a[0].LineNum; j++) {
            if (c[i] == c[j]) {
                k++;
                b[k] = a[j].list[a[0].PropertyNum];
                c[j] = "&&";
            }
        }
        
        x = x + float(k)*Entropymath(b, k)/a[0].LineNum;
    }
    return x;
}

string CORE(Tuple a[]) {//求核，如果去掉属性集中的某一个属性，结果对于D关于C的条件信息熵变大，则是核属性
    string core = "";
    string c = "";
    for (int i = 1; i < a[0].PropertyNum; i++) {
        c = c + a[0].list[i] + ",";
    }
    float hdc = Entropy(a,c);//D关于C的条件信息熵
    for (int i = 1; i < a[0].PropertyNum; i++) {
        for (int j = 1; j < a[0].PropertyNum; j++) {
            if (i == j)
                continue;
            c = c + a[0].list[j] + ",";
        }
        float hdca = Entropy(a, c);//D关于C-a的条件信息熵
        if (hdc < hdca) {
            core = core + a[0].list[i] + ",";
        }
    }
    return core;
}

float SGF(Tuple a[],string s,string p) {//属性s关于p对d的属性依赖度
    float hdp = Entropy(a, p);
    p = s + "," + p;
    float sgf = Entropy(a, p);
    sgf = hdp - sgf;
    return sgf;
}


vector<string> split(const string& str, const string& delim) {
    vector<string> res;
    if ("" == str) return res;
    //先将要切割的字符串从string类型转换为char*类型
    char * strs = new char[str.length() + 1]; 
    strcpy(strs, str.c_str());

    char * d = new char[delim.length() + 1];
    strcpy(d, delim.c_str());

    char *p = strtok(strs, d);
    while (p) {
        string s = p; //分割得到的字符串转换为string类型
        res.push_back(s); //存入结果数组
        p = strtok(NULL, d);
    }

    return res;
}
string addto(string s, string p) {//向集合s中添加元素p
    std::vector<string> res = split(s, ",");
    for (int i = 0; i < res.size(); ++i) {
        if (res[i] == p)
            p = "";
    }
    if (p == "")
        return s;
    s = p + "," + s;
    return s;
}

string remove(string s,string p) {//从集合s中删去元素p
    string y = "";
    std::vector<string> res = split(s, ",");
    for (int i = 0; i < res.size(); ++i) {
        if (res[i] == p)
            continue;
        y = y + res[i] + ",";
    }
    return y;
}

string buji(string u,string s) {//全集为u，s为其子集，计算u-s
    string b = "";
    std::vector<string> resu = split(u, ",");
    std::vector<string> ress = split(s, ",");
    for (int i = 0; i < ress.size(); ++i)
        for (int j = 0; j < resu.size(); ++j) {
            if (resu[j] == ress[i])
                resu[j] = "&&";
        }
    for (int j = 0; j < resu.size(); ++j) {
        if (resu[j] == "&&")
            continue;
        b = b + resu[j] + ",";
    }
    return b;
}
string reduce(Tuple a[]) {
    string c = "";
    for (int i = 1; i < a[0].PropertyNum; i++) {
        c = c + a[0].list[i] + ",";
    }
    string core = CORE(a);
    string p = core;
    string b = buji(c,core);
    std::ofstream openfile("输出.txt", std::ios::app);
    while (Entropy(a,c)!= Entropy(a,p))
    {
        openfile <<"\n" << "H(D|C) = " << Entropy(a, c) << "\nH(D|P) = " << Entropy(a, p) << endl;
        cout << "\n";
        cout << "H(D|C) = " << Entropy(a, c) << "\nH(D|P) = " << Entropy(a, p) << endl;
        std::vector<string> resb = split(b, ",");
        int max = 0;
        float maxsgf = 0;
        for (int i = 0; i < resb.size(); ++i) {
            float sgf = SGF(a, resb[i], p);
            
            openfile<< "SGF(" << resb[i] << ",P,D) = H(D|" << p << ") - H(D|" << addto(p, resb[i]) << ") = " << sgf << endl;
            
            cout << "SGF(" << resb[i] << ",P,D) = H(D|" << p << ") - H(D|" << addto(p, resb[i]) << ") = " << sgf << endl;
            if (sgf == 0)
                b = remove(b, resb[i]);
            if (sgf>maxsgf) {
                maxsgf = sgf;
                max = i;
            }
        }
        p = addto(p, resb[max]);
        b = remove(b, resb[max]);
        cout << "\n\n";
        openfile << "\n\n";

    }
    openfile << "约简结果为：" << p << endl;
    openfile << "CORE :" << CORE(a) << endl;
    openfile.close();
    return p;
}


void main() 
{
    Tuple a[200];
    init(a);
    //a[6].outline(a[6].PropertyNum);
    
    //cout << buji("a1,a2,a5,a4,a6", "a1,a4") << endl;
    //cout << remove("a1,a2,a5,a4,a3,", "a5") << endl;
    //cout << addto("a1,a2,a6,a4,a3,", "a5") << endl;
    //cout << SGF(a, "a4", "") << endl;

    cout <<"约简结果为："<< reduce(a) << endl;
    cout << "CORE :"<<CORE(a) << endl;

    //cout << "\n" << a[4].list[5] << endl;
    //cout << Entropy(a,"")<<endl;
    getchar();
}

运行结果实例：

image