基于信息量的动态属性约简算法仿真实现

陈丽芳，王云



基于信息量的动态属性约简算法仿真实现

陈丽芳*，王云

华北理工大学理学院，河北省唐山市邮编：063009

基于信息量的动态约简算法充分利用了原信息系统的约简结果，从约简效率上，比静态算法有很大的提高。但在实际应用中，该算法的计算工作量令许多非数学专业的科技人员感到力不从心。鉴于这种情况，本文针对基于信息量的动态属性约简算法，编程仿真了整个计算过程。对该算法进行设计并用C语言编写了源代码，使计算过程简单化，输入待解决问题的数据和新增动态数据即可计算得出相应的约简结果。该仿真实现有利于动态约简算法的进一步推广和应用。

信息量；动态属性约简；粗糙集；属性重要度；静态属性约简

引言

基于信息量的属性约简算法，是由梁吉业等[1]于2001年提出的。文中首次将信息量的概念引入到信息系统中，通过知识的信息量定义了属性的重要性。信息量是刻画知识分类的有效数量化方法，信息系统属性约简的计算问题可以转化为对信息量的计算。约简是粗糙集理论中的重要概念之一。所谓约简是求原始属性集的一个最小子集，并且这个子集和整个属性集的分类能力是一样的。目前，很多学者都对静态约简进行了深入的研究[2]，但在实际应用中，很多数据库一开始并没有足够的知识供提取属性间精确的关系，往往是随着时间的推移逐步建成的。因此，动态属性约简算法[3]的研究意义远远大于静态约简。

因此，在彭黎黎、刘山等人[4]提出的“基于信息量的动态属性约简算法”基础上，为了能够进一步推广算法的使用，为非计算机专业的科技人员提供一个方便快捷的计算平台，作者将整个算法过程进行了模块分解设计，并用C语言编程实现了仿真计算，该仿真能够解决复杂计算的黑箱性，只要用户输入原始数据和新增数据集，即可获得动态约简结果。基于信息量的动态属性约简算法，充分利用了原信息系统的静态约简结果，避免了因数据集的增减重新从原始数据集开始计算的缺陷，大大提高了算法效率，本文的仿真设计与实现，为算法的推广应用奠定了基础。

1 算法描述

输出：新信息系统的约简。

（2）

其中，

（3）

该算法是针对数据库中样本增加或减少的情形而提出的。同时给出动态计算信息量的方法，使得在每次约简时利用上一次得到的结果，这样同样的比较运算不会重复进行。又因为每次约简都是在上一次的结果上进行操作，所以可以使得属性组合的数目大大减少，提高运算效率。

但是，考虑到在应用该算法时的计算工作量，很多非数学专业的人员往往感到力不从心。考虑到这种情况，笔者对该算法进行了设计并用C语言编写了源代码，使计算过程简单化，利于工程技术人员在实际工作和科学研究中进一步推广和应用。

2 模块分解

基于信息量的动态属性约简，主要是利用静态约简的结果，对新增数据进行分类。因此，需要做的首先是静态约简仿真实现，然后利用输出的静态约简结果；计算新增数据的动态约简过程，并得到最终的动态约简结果。整体模块分解流程如图1所示，静态约简模块分解流程如图2所示，动态约简模块按算法描述中的step1~step6流程分解模块。

图1 整体模块分解流程

图2 静态约简模块分解

3 技术难点

3.1 静态属性约简

静态属性约简是编程模块的第一步。静态约简中，如何实现对象及区分矩阵的存储是整个编程的技术关键，涉及到后面数据处理的方式和计算技巧。考虑到数据样本数量具有不确定性，其属性值数也不确定的特点，显然用数组实现不适合问题求解。因此，经过反复推敲，最终确定使用结构体实现数据样本的存储。定义结构体来存储对象及区分矩阵，如：

typedef struct {

int a,b,c,d;

}unit;

unit是用来存储一个对象的数据类型，它包括四个属性：a,b,c,d。如果问题涉及属性较多时，可增加分量来实现。使用时，用unit数据类型定义数组，数组元素数就是样本数，这样即可实现样本所有属性的存储。

typedef struct{

int lei;

int num;

}LEI;

LEI用来存储等价类的划分结果，其中分量lei存储划分后的类编号；分量num用来存储每类中包含的样本数。使用时，用LEI定义数组，下标为0的元素存储第一类；下标为1的元素存储第二类，依此类推。

3.2 动态属性约简

根据静态属性约简设计，获得了动态约简的输入信息表，要输出新增记录后动态约简的结果需要计算机仿真实现，以便推广动态约简算法。

for (i = 0; i < N; i++){

if (X.a == obj[i].a && X.b == obj[i].b && X.c == obj[i].c && X.d == obj[i].d){

printf("X属于U[%d] ",i);

flag=1;

m=i;

}

if(flag!=1){

printf("X不属于任何类 ");

U[N].lei=N;

}

}

根据上一步骤的计算结果，如果新增记录不属于任何类，则按公式（1）计算IA的值；否则按公式（2）计算IA的值。

//若新增记录不属于任何类，则按下列代码计算IA

for (i=0;i

if(U[i].lei!=-1)

sum1+=(U[i].num)*(U[i].num);

IA=1-1.0/(N*N)*sum1;

printf("IA=%f ",IA);

IAm=2*1.0/(N+1)*(1-1.0/(N+1))+(1-1.0/(N+1))*(1-1.0/(N +1))*IA;

printf("IAm=%f ",IAm);}

//若新增记录属于原有的某一类，则按下列代码计算IA

for (i=0;i

if(U[i].lei!=-1 && U[i].lei!=m)

sum2+=(U[i].num)*(U[i].num);

IA=1-1.0/((N-U[i].num)*(N-U[i].num))*sum2;

printf("IA=%f ",IA);

IAm=2.0*(U[m].num+1)/(N+1)*(1-(double)(U[m].num+1)/(N+1))+(1-(double)(U[m].num+1)/(N+1))*(1-(double)(U[m].num+1)/(N+1))*IA;

printf("IAm=%f ",IAm);

//去掉a属性后的分类

for(i = 0; i < N; i++){

if (obja[i].b!=-1 && obja[i].c!=-1 && obja[i].d!=-1)

Sa[i].lei=i;

for (j = i+1; j <= N; j++)

if (obja[i].b==obja[j].b && obja[i].c==obja[j].c && obja[i].d==obja[j].d){

obja[j].b=obja[j].c=obja[j].d=-1;

Sa[i].num++;

}

}

printf("去掉a属性后信息表可分为以下几类： ");

printf("类别 记录数 ");

for (i = 0; i <= N; i++)

if (Sa[i].lei!=-1)

printf("%d %d ",Sa[i].lei,Sa[i].num);

//计算IA_a

sum1=0.0;

for (i = 0; i <= N; i++)

if(Sa[i].lei!=-1)

sum1+=(Sa[i].num)*(Sa[i].num);

IA_a=1-1.0/((N+1)*(N+1))*sum1;

printf("IA_a=%f ",IA_a);

sgfa=IAm-IA_a;

printf("sgfa=%f ",sgfa);

其他的算法与此实现过程类似。

//step6 只考虑约简后的属性分类

该部分考虑的几种情况中，内容是重复性的，因此用函数的形式实现，在函数调用时传不同的属性即可。若a是新增属性，计算IB；若b是新增属性，计算IB，……。

4 应用实例

表1 教师状况表

图3 新增记录后运行结果

(a)

(b)

图4 算法实现过程

5 结语

如果信息系统的数据量非常庞大，用静态约简算法时每次增加记录都需要对所有的数据进行重新分类。而利用上述的动态约简算法，只需要检查新增记录是否属于已有的分类即可，时间复杂度降低。由于该算法每次约简时都能充分利用上一次的约简结果，这样使得同样的比较运算不会重复进行。另一方面，由于每一次约简都是在上一次的结果上进行操作的，所以属性组合的数目大大减少。通过应用实例的仿真验证，证明了算法是正确有效的。用C语言实现该算法的仿真设计，大大简化了工程技术人员和科技工作者的计算量，有利于该算法的进一步推广使用。

[1] Liang J Y, Qu K S, Xu Z B. Attributes reduction of information system [J]. Systems engineering theory and practice, 2001 (12):1-5（梁吉业,曲开社,徐宗本.信息系统的属性约简[J],系统工程理论与实践,2001(12): 1-5）

[2] Zhang W Y, Jia R. Data mining and rough set methods [M]. Xi 'an: xi 'an university of electronic science and technology press, 2007: 25-29.（张文宇,贾嵘.数据挖掘与粗糙集方法[M].西安：西安电子科技大学出版社,2007: 25-29）

[3] Liu Z H, Liu S Y, Wang Y. An attribute reduction algorithm based on information [J]. Journal of xi 'an university of electronic science and technology, 2003, and practices: 835-838.(刘振华,刘三阳,王珏. 基于信息量的一种属性约简算法[J]. 西安电子科技大学学报,2003,06:835-838.)

[4] Peng L L, Liu S. Dynamic attribute reduction based on information [J]. Computer engineering, 2005, S1: + 109 104-105(彭黎黎,刘山. 基于信息量的动态属性约简[J]. 计算机工程,2005,S1:104-105+109.)

[5] Sun L Y, Peng X G, Leng M. Attribute reduction algorithm based on dynamic discernibility matrix [J]. Computer engineering, 2008, 24:216-217 + 220(孙凌宇,彭宣戈,冷明. 基于动态区分矩阵的属性约简算法[J]. 计算机工程,2008,24:216-217+220.)

[6] Zeng J H, Ding Y H. Clear matrix of attribute reduction method application [J]. Computer and modernization, 2004 (12): 6-8(曾纪汉,丁银花.属性约简的分明矩阵方法程序实现[J].计算机与现代化, 2004(12): 6-8).

[7] Wang X Y, Yang S C. Based on an array of incremental attribute reduction study [J]. Computer application research, 2011, 12:1728-1730.(汪小燕,杨思春. 基于数组的增量式属性约简研究[J]. 计算机应用研究,2011,05:1728-1730.)

Simulation of Dynamic Attribute Reduction Algorithm Based on Information Content

CHEN Lifang*, WANG Yun

（College of Science, North China University of Science and Technology, Tangshan Hebei 063009,China)

The dynamic reduction algorithm based on information content make full use of the reduction result of the original information system, the reduction efficiency has greatly improved than the static algorithm. But in actual application, non-math majors of science and technology personnel felt run out of puff to the computation of the algorithm. Considering this situation, we programmed simulation calculating process aimed at the dynamic attribute reduction algorithm based on the information content, the algorithm source code is designed using C language, and simplify calculation process. The user input the data sample to be solved and the new added data, the reduction results can be calculated immediately. The simulation will conducive to the further promotion and application of dynamic reduction algorithm.

information content; dynamic attribute reduction; rough set;importance of attributes; static attribute reduction

1672-9129(2016)01-0044-04

TP301.6，O29

A

2016-06-14；

2016-06-25。

河北省自然科学基金面上项目（F2014209086）。

陈丽芳(1973-)，女，河北玉田，教授，博士，主要研究方向：人工智能；机器学习；智能计算；王云(1990-)，女，河北保定，硕士研究生，主要研究方向：应用数学；最优化计算。

(*通信作者电子邮箱：hblg_clf@163.com)