粗糙集理论属性约简算法
2018-10-06 本文已影响0人
麦穗_4feb
大创项目，基于粗糙集理论的高校学生实践能力培养研究。进行了一段时间，有了点小成果，再此总结一下。
首先了解一下什么是粗糙集理论，它是处理不确定信息的一种方法。可以从不完备的信息中得出现有的规律，并从中提取出一些规则。
百度百科：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
