陳麗芳，王云

?

基于信息量的動(dòng)態(tài)屬性約簡(jiǎn)算法仿真實(shí)現(xiàn)

陳麗芳*，王云

華北理工大學(xué)理學(xué)院，河北省唐山市郵編：063009

基于信息量的動(dòng)態(tài)約簡(jiǎn)算法充分利用了原信息系統(tǒng)的約簡(jiǎn)結(jié)果，從約簡(jiǎn)效率上，比靜態(tài)算法有很大的提高。但在實(shí)際應(yīng)用中，該算法的計(jì)算工作量令許多非數(shù)學(xué)專(zhuān)業(yè)的科技人員感到力不從心。鑒于這種情況，本文針對(duì)基于信息量的動(dòng)態(tài)屬性約簡(jiǎn)算法，編程仿真了整個(gè)計(jì)算過(guò)程。對(duì)該算法進(jìn)行設(shè)計(jì)并用C語(yǔ)言編寫(xiě)了源代碼，使計(jì)算過(guò)程簡(jiǎn)單化，輸入待解決問(wèn)題的數(shù)據(jù)和新增動(dòng)態(tài)數(shù)據(jù)即可計(jì)算得出相應(yīng)的約簡(jiǎn)結(jié)果。該仿真實(shí)現(xiàn)有利于動(dòng)態(tài)約簡(jiǎn)算法的進(jìn)一步推廣和應(yīng)用。

信息量；動(dòng)態(tài)屬性約簡(jiǎn)；粗糙集；屬性重要度；靜態(tài)屬性約簡(jiǎn)

引言

基于信息量的屬性約簡(jiǎn)算法，是由梁吉業(yè)等[1]于2001年提出的。文中首次將信息量的概念引入到信息系統(tǒng)中，通過(guò)知識(shí)的信息量定義了屬性的重要性。信息量是刻畫(huà)知識(shí)分類(lèi)的有效數(shù)量化方法，信息系統(tǒng)屬性約簡(jiǎn)的計(jì)算問(wèn)題可以轉(zhuǎn)化為對(duì)信息量的計(jì)算。約簡(jiǎn)是粗糙集理論中的重要概念之一。所謂約簡(jiǎn)是求原始屬性集的一個(gè)最小子集，并且這個(gè)子集和整個(gè)屬性集的分類(lèi)能力是一樣的。目前，很多學(xué)者都對(duì)靜態(tài)約簡(jiǎn)進(jìn)行了深入的研究[2]，但在實(shí)際應(yīng)用中，很多數(shù)據(jù)庫(kù)一開(kāi)始并沒(méi)有足夠的知識(shí)供提取屬性間精確的關(guān)系，往往是隨著時(shí)間的推移逐步建成的。因此，動(dòng)態(tài)屬性約簡(jiǎn)算法[3]的研究意義遠(yuǎn)遠(yuǎn)大于靜態(tài)約簡(jiǎn)。

因此，在彭黎黎、劉山等人[4]提出的“基于信息量的動(dòng)態(tài)屬性約簡(jiǎn)算法”基礎(chǔ)上，為了能夠進(jìn)一步推廣算法的使用，為非計(jì)算機(jī)專(zhuān)業(yè)的科技人員提供一個(gè)方便快捷的計(jì)算平臺(tái)，作者將整個(gè)算法過(guò)程進(jìn)行了模塊分解設(shè)計(jì)，并用C語(yǔ)言編程實(shí)現(xiàn)了仿真計(jì)算，該仿真能夠解決復(fù)雜計(jì)算的黑箱性，只要用戶(hù)輸入原始數(shù)據(jù)和新增數(shù)據(jù)集，即可獲得動(dòng)態(tài)約簡(jiǎn)結(jié)果?；谛畔⒘康膭?dòng)態(tài)屬性約簡(jiǎn)算法，充分利用了原信息系統(tǒng)的靜態(tài)約簡(jiǎn)結(jié)果，避免了因數(shù)據(jù)集的增減重新從原始數(shù)據(jù)集開(kāi)始計(jì)算的缺陷，大大提高了算法效率，本文的仿真設(shè)計(jì)與實(shí)現(xiàn)，為算法的推廣應(yīng)用奠定了基礎(chǔ)。

1 算法描述

輸出：新信息系統(tǒng)的約簡(jiǎn)。

（2）

其中，

（3）

該算法是針對(duì)數(shù)據(jù)庫(kù)中樣本增加或減少的情形而提出的。同時(shí)給出動(dòng)態(tài)計(jì)算信息量的方法，使得在每次約簡(jiǎn)時(shí)利用上一次得到的結(jié)果，這樣同樣的比較運(yùn)算不會(huì)重復(fù)進(jìn)行。又因?yàn)槊看渭s簡(jiǎn)都是在上一次的結(jié)果上進(jìn)行操作，所以可以使得屬性組合的數(shù)目大大減少，提高運(yùn)算效率。

但是，考慮到在應(yīng)用該算法時(shí)的計(jì)算工作量，很多非數(shù)學(xué)專(zhuān)業(yè)的人員往往感到力不從心?？紤]到這種情況，筆者對(duì)該算法進(jìn)行了設(shè)計(jì)并用C語(yǔ)言編寫(xiě)了源代碼，使計(jì)算過(guò)程簡(jiǎn)單化，利于工程技術(shù)人員在實(shí)際工作和科學(xué)研究中進(jìn)一步推廣和應(yīng)用。

2 模塊分解

基于信息量的動(dòng)態(tài)屬性約簡(jiǎn)，主要是利用靜態(tài)約簡(jiǎn)的結(jié)果，對(duì)新增數(shù)據(jù)進(jìn)行分類(lèi)。因此，需要做的首先是靜態(tài)約簡(jiǎn)仿真實(shí)現(xiàn)，然后利用輸出的靜態(tài)約簡(jiǎn)結(jié)果；計(jì)算新增數(shù)據(jù)的動(dòng)態(tài)約簡(jiǎn)過(guò)程，并得到最終的動(dòng)態(tài)約簡(jiǎn)結(jié)果。整體模塊分解流程如圖1所示，靜態(tài)約簡(jiǎn)模塊分解流程如圖2所示，動(dòng)態(tài)約簡(jiǎn)模塊按算法描述中的step1~step6流程分解模塊。

圖1 整體模塊分解流程

圖2 靜態(tài)約簡(jiǎn)模塊分解

3 技術(shù)難點(diǎn)

3.1 靜態(tài)屬性約簡(jiǎn)

靜態(tài)屬性約簡(jiǎn)是編程模塊的第一步。靜態(tài)約簡(jiǎn)中，如何實(shí)現(xiàn)對(duì)象及區(qū)分矩陣的存儲(chǔ)是整個(gè)編程的技術(shù)關(guān)鍵，涉及到后面數(shù)據(jù)處理的方式和計(jì)算技巧。考慮到數(shù)據(jù)樣本數(shù)量具有不確定性，其屬性值數(shù)也不確定的特點(diǎn)，顯然用數(shù)組實(shí)現(xiàn)不適合問(wèn)題求解。因此，經(jīng)過(guò)反復(fù)推敲，最終確定使用結(jié)構(gòu)體實(shí)現(xiàn)數(shù)據(jù)樣本的存儲(chǔ)。定義結(jié)構(gòu)體來(lái)存儲(chǔ)對(duì)象及區(qū)分矩陣，如：

typedef struct {

int a,b,c,d;

}unit;

unit是用來(lái)存儲(chǔ)一個(gè)對(duì)象的數(shù)據(jù)類(lèi)型，它包括四個(gè)屬性：a,b,c,d。如果問(wèn)題涉及屬性較多時(shí)，可增加分量來(lái)實(shí)現(xiàn)。使用時(shí)，用unit數(shù)據(jù)類(lèi)型定義數(shù)組，數(shù)組元素?cái)?shù)就是樣本數(shù)，這樣即可實(shí)現(xiàn)樣本所有屬性的存儲(chǔ)。

typedef struct{

int lei;

int num;

}LEI;

LEI用來(lái)存儲(chǔ)等價(jià)類(lèi)的劃分結(jié)果，其中分量lei存儲(chǔ)劃分后的類(lèi)編號(hào)；分量num用來(lái)存儲(chǔ)每類(lèi)中包含的樣本數(shù)。使用時(shí)，用LEI定義數(shù)組，下標(biāo)為0的元素存儲(chǔ)第一類(lèi)；下標(biāo)為1的元素存儲(chǔ)第二類(lèi)，依此類(lèi)推。

3.2 動(dòng)態(tài)屬性約簡(jiǎn)

根據(jù)靜態(tài)屬性約簡(jiǎn)設(shè)計(jì)，獲得了動(dòng)態(tài)約簡(jiǎn)的輸入信息表，要輸出新增記錄后動(dòng)態(tài)約簡(jiǎn)的結(jié)果需要計(jì)算機(jī)仿真實(shí)現(xiàn)，以便推廣動(dòng)態(tài)約簡(jiǎn)算法。

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不屬于任何類(lèi) ");

U[N].lei=N;

}

}

根據(jù)上一步驟的計(jì)算結(jié)果，如果新增記錄不屬于任何類(lèi)，則按公式（1）計(jì)算IA的值；否則按公式（2）計(jì)算IA的值。

//若新增記錄不屬于任何類(lèi)，則按下列代碼計(jì)算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);}

//若新增記錄屬于原有的某一類(lèi)，則按下列代碼計(jì)算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屬性后的分類(lèi)

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屬性后信息表可分為以下幾類(lèi)： ");

printf("類(lèi)別 記錄數(shù) ");

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

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

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

//計(jì)算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);

其他的算法與此實(shí)現(xiàn)過(guò)程類(lèi)似。

//step6 只考慮約簡(jiǎn)后的屬性分類(lèi)

該部分考慮的幾種情況中，內(nèi)容是重復(fù)性的，因此用函數(shù)的形式實(shí)現(xiàn)，在函數(shù)調(diào)用時(shí)傳不同的屬性即可。若a是新增屬性，計(jì)算IB；若b是新增屬性，計(jì)算IB，……。

4 應(yīng)用實(shí)例

表1 教師狀況表

圖3 新增記錄后運(yùn)行結(jié)果

(a)

(b)

圖4 算法實(shí)現(xiàn)過(guò)程

5 結(jié)語(yǔ)

如果信息系統(tǒng)的數(shù)據(jù)量非常龐大，用靜態(tài)約簡(jiǎn)算法時(shí)每次增加記錄都需要對(duì)所有的數(shù)據(jù)進(jìn)行重新分類(lèi)。而利用上述的動(dòng)態(tài)約簡(jiǎn)算法，只需要檢查新增記錄是否屬于已有的分類(lèi)即可，時(shí)間復(fù)雜度降低。由于該算法每次約簡(jiǎn)時(shí)都能充分利用上一次的約簡(jiǎn)結(jié)果，這樣使得同樣的比較運(yùn)算不會(huì)重復(fù)進(jìn)行。另一方面，由于每一次約簡(jiǎn)都是在上一次的結(jié)果上進(jìn)行操作的，所以屬性組合的數(shù)目大大減少。通過(guò)應(yīng)用實(shí)例的仿真驗(yàn)證，證明了算法是正確有效的。用C語(yǔ)言實(shí)現(xiàn)該算法的仿真設(shè)計(jì)，大大簡(jiǎn)化了工程技術(shù)人員和科技工作者的計(jì)算量，有利于該算法的進(jìn)一步推廣使用。

[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（梁吉業(yè),曲開(kāi)社,徐宗本.信息系統(tǒng)的屬性約簡(jiǎn)[J],系統(tǒng)工程理論與實(shí)踐,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.（張文宇,賈嶸.數(shù)據(jù)挖掘與粗糙集方法[M].西安：西安電子科技大學(xué)出版社,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.(劉振華,劉三陽(yáng),王玨. 基于信息量的一種屬性約簡(jiǎn)算法[J]. 西安電子科技大學(xué)學(xué)報(bào),2003,06:835-838.)

[4] Peng L L, Liu S. Dynamic attribute reduction based on information [J]. Computer engineering, 2005, S1: + 109 104-105(彭黎黎,劉山. 基于信息量的動(dòng)態(tài)屬性約簡(jiǎn)[J]. 計(jì)算機(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(孫凌宇,彭宣戈,冷明. 基于動(dòng)態(tài)區(qū)分矩陣的屬性約簡(jiǎn)算法[J]. 計(jì)算機(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ì)漢,丁銀花.屬性約簡(jiǎn)的分明矩陣方法程序?qū)崿F(xiàn)[J].計(jì)算機(jī)與現(xiàn)代化, 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.(汪小燕,楊思春. 基于數(shù)組的增量式屬性約簡(jiǎn)研究[J]. 計(jì)算機(jī)應(yīng)用研究,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。

河北省自然科學(xué)基金面上項(xiàng)目（F2014209086）。

陳麗芳(1973-)，女，河北玉田，教授，博士，主要研究方向：人工智能；機(jī)器學(xué)習(xí)；智能計(jì)算；王云(1990-)，女，河北保定，碩士研究生，主要研究方向：應(yīng)用數(shù)學(xué)；最優(yōu)化計(jì)算。

(*通信作者電子郵箱：hblg_clf@163.com)