基于信息量的動態(tài)屬性約簡算法仿真實現(xiàn)

陳麗芳，王云

?

基于信息量的動態(tài)屬性約簡算法仿真實現(xiàn)

陳麗芳*，王云

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

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

信息量；動態(tài)屬性約簡；粗糙集；屬性重要度；靜態(tài)屬性約簡

引言

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

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

1 算法描述

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

（2）

其中，

（3）

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

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

2 模塊分解

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

圖1 整體模塊分解流程

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

3 技術難點

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

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

typedef struct {

int a,b,c,d;

}unit;

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

typedef struct{

int lei;

int num;

}LEI;

LEI用來存儲等價類的劃分結果，其中分量lei存儲劃分后的類編號；分量num用來存儲每類中包含的樣本數(shù)。使用時，用LEI定義數(shù)組，下標為0的元素存儲第一類；下標為1的元素存儲第二類，依此類推。

3.2 動態(tài)屬性約簡

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

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;

}

}

根據(jù)上一步驟的計算結果，如果新增記錄不屬于任何類，則按公式（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("類別 記錄數(shù) ");

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);

其他的算法與此實現(xiàn)過程類似。

//step6 只考慮約簡后的屬性分類

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

4 應用實例

表1 教師狀況表

圖3 新增記錄后運行結果

(a)

(b)

圖4 算法實現(xiàn)過程

5 結語

如果信息系統(tǒng)的數(shù)據(jù)量非常龐大，用靜態(tài)約簡算法時每次增加記錄都需要對所有的數(shù)據(jù)進行重新分類。而利用上述的動態(tài)約簡算法，只需要檢查新增記錄是否屬于已有的分類即可，時間復雜度降低。由于該算法每次約簡時都能充分利用上一次的約簡結果，這樣使得同樣的比較運算不會重復進行。另一方面，由于每一次約簡都是在上一次的結果上進行操作的，所以屬性組合的數(shù)目大大減少。通過應用實例的仿真驗證，證明了算法是正確有效的。用C語言實現(xià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è),曲開社,徐宗本.信息系統(tǒng)的屬性約簡[J],系統(tǒng)工程理論與實踐,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].西安：西安電子科技大學出版社,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(彭黎黎,劉山. 基于信息量的動態(tài)屬性約簡[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(孫凌宇,彭宣戈,冷明. 基于動態(tài)區(qū)分矩陣的屬性約簡算法[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(曾紀漢,丁銀花.屬性約簡的分明矩陣方法程序實現(xiàn)[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ù)組的增量式屬性約簡研究[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-)，女，河北保定，碩士研究生，主要研究方向：應用數(shù)學；最優(yōu)化計算。

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