一種新的不完備信息系統(tǒng)中極大相容塊的構(gòu)造算法

趙乃剛

(山西大同大學數(shù)學與計算機科學學院，山西大同037009)

一種新的不完備信息系統(tǒng)中極大相容塊的構(gòu)造算法

趙乃剛

(山西大同大學數(shù)學與計算機科學學院，山西大同037009)

在不完備信息系統(tǒng)中以分層遞階的方式求取極大相容塊的構(gòu)造算法，簡化了不完備信息系統(tǒng)中極大相容塊的求取過程.然而，該算法有一定不足之處，在求取極大相容塊的中間過程中，沒有進行非極大相容塊的去除，從而增加了算法的空間復雜度，所以該算法僅適用于小規(guī)模不完備信息系統(tǒng).基于這個缺點，提出了改進的極大相容塊求取算法,從而可以在較大規(guī)模的不完備信息系統(tǒng)中進行極大相容塊的求取.

粗糙集 非完備信息系統(tǒng) 極大相容塊 空間復雜度

文獻[1]提出的粗糙集理論模型對相容關(guān)系的結(jié)構(gòu)進行深入分析，證明了極大相容塊是不完備信息系統(tǒng)中的最小知識顆粒，這就意味著，它可以為知識獲取提供更有效的計算，特別是對于大規(guī)模不完備信息系統(tǒng)而言.文獻[2]提出了在不完備信息系統(tǒng)中以分層遞階的方式求取極大相容塊的構(gòu)造算法，從而簡化了極大相容塊的求取過程.然而，該算法有一定不足之處，在求取極大相容塊的中間過程中，沒有進行非極大相容塊的去除，從而增加了算法的空間復雜度，所以該算法不適用于較大規(guī)模不完備信息系統(tǒng)中極大相容塊的求取.基于這個缺點，本文提出了改進的極大相容塊求取算法，實現(xiàn)了在較大規(guī)模不完備信息系統(tǒng)中進行極大相容塊的求取.

1 相關(guān)基本概念

我們知道,一個信息系統(tǒng)是一個有序三元組S= (U,AT,f)，這里U是由對象組成的有限非空集，AT是由屬性組成的有限非空集，對于任意的a∈AT，fa∶U→Va，其中，Va被稱為屬性a的值域.這里，假定一個對象x∈U在一個屬性a下只取一個值，如果屬性a的值缺失，則用“*”表示該缺失值.對于一個信息系統(tǒng)，如果對于任意的對象x∈U沒有缺失的屬性值，則稱這個信息系統(tǒng)是完備的，否則它被稱為是不完備的.

定義1[1]設(shè)S=(U,AT,f)是不完備信息系統(tǒng)，P?AT是一個屬性子集，X?U是一個對象子集，稱X關(guān)于P是相容的，如果對任意的x,y∈X有(x, y)∈SIM(P).如果不存在一個對象子集Y?U使得X?Y且Y關(guān)于P是相容的，則稱X為一個極大相容子集或極大相容塊.

為了方便起見，以C(P)記由屬性集P?AT所決定的所有極大相容塊構(gòu)成的集合.

性質(zhì)1[2]不完備信息系統(tǒng)S=(U,AT,f)中，a∈ AT，則

這條性質(zhì)是針對不完備信息系統(tǒng)在單個屬性作用下對極大相容塊的求取.將原對象集合進行細化，細化后的集合內(nèi)部，各個對象完全滿足基本的容差關(guān)系.

性質(zhì)2[2]不完備信息系統(tǒng)S=(U,AT,f)中，P?AT，任意的x∈C(P)，則存在Y∈C(P{a})，使得X∈CY({a}).其中X∈CY({a})表示Y為論域下屬性集{a}決定的極大相容塊集.

該性質(zhì)為利用分層遞階方式求取極大相容塊提供了方法.先求出屬性集P{a}決定的極大相容塊集C(P{a})={K1,K2,…,Km}，然后對于每個極大相容塊Ki，用屬性a提供的信息求更細的不可區(qū)分單元集C

Ki({a})，而且必有下式成立:.這樣，我們可以結(jié)合性質(zhì)1，在求由N個屬性組成的屬性集P決定的極大相容塊時，完全可以利用分層遞階的思想進行.先求出由第一個屬性a1決定的極大相容塊，將這些相容塊作為論域，再求由屬性a2決定的極大相容塊，如此反復，最后得到屬性集P決定的極大相容塊.

當然，在此迭代過程中，不可區(qū)分單元集({a})是相容塊，但不一定是極大相容塊，因為可能存在Xm∈CKi(a)，Xn∈CKj(a),有Xm?Xn，則Xm不符合定義1而不能是極大相容塊.針對這種情況，我們可以這樣處理：對前一步生成的極大相容塊利用后面所加屬性進一步分解后，所產(chǎn)生的相容塊中，還要比較判斷各塊是否是當前屬性下的極大相容塊.如果在同一層次上，有集合X的超集存在，則不是極大相容塊，應(yīng)該去除之.

2 極大相容塊的求取算法

給定不完備信息系統(tǒng)S=(U,AT)，若U′?U，AT′?AT,稱S′=(U′,AT′)為原信息系統(tǒng)S的局部子系統(tǒng).局部子系統(tǒng)中，在屬性集P下的極大相容塊是局部極大相容塊，而在原系統(tǒng)下的極大相容塊是全局極大相容塊.

算法1：求屬性集P決定的極大相容塊C(P).

輸入：不完備信息系統(tǒng)

輸出：C(P).

說明：記Cb為中間過程所求單元素子論域集；Xi表示極大相容塊集合C=({a1,a2,…,ar})；Xij表示C= ({a1,a2,…,ar})中的第j個局部極大相容塊；Xi+1表示將極大相容塊集合Xi在屬性ai+1作用下求得的極大相容塊集合；Yi+1表示生成Xi+1之前，未去除非極大相容塊時的集合；Vai+1表示在屬性Vi+1下，論域中各對象值的集合.

初始化：Cb=φ；CN=1；求極大相容塊之前的初始數(shù)據(jù)集X01={1,2,…｜U｜}.

Step1：令i=0.

Step2：若i>r,則轉(zhuǎn)Step14.

Step3：令CN2=CN，然后將CN清0.

Step4：將屬性ai+1下論域中各對象值依次讀到集合 Vai+1中.

Step5：令j=1.

Step8：令j=j+1轉(zhuǎn)到步驟Step6.

Step9：判斷集合Yi+1中每一個yk，得到C″= {M∈Yi+1｜?N∈Yi+1且M∈N}.

Step10：判斷集合Yi+1C″中每一個yk，若｜yk｜=1， 則Cb=Cb∪yk.

Step11：判斷集合Yi+1中每一個yk，合成Xi+1= {yk∈Yi+1｜?(Cb∪C″)}，且得到屬性ai+1下的極大相容塊個數(shù)CN3.

Step12：令CN=CN3.

Step13：令i=i+1，然后轉(zhuǎn)到Step2.

Step14：去掉集合Cb中的重復值.

Step15：得到C(P)=X′∪Cb.

Step16：輸出C(P)，算法結(jié)束.

Step1:利用屬性ai+1對局部極大相容塊Xij中的對象按其取值進行升序排列(將“*”當作無窮小的正則值).

Step3:判斷若y1中對象值不為“*”,則令C′()，將當前CN值加上α，然后轉(zhuǎn)步驟Step7.

Step4:若α>1，則轉(zhuǎn)步驟Step5，否則轉(zhuǎn)步驟Step6.

3 實驗

我們從汽車評論網(wǎng)上下載了對某款汽車連續(xù)3個月的評論文本，共100篇.根據(jù)文本評論內(nèi)容，我們選擇了常用的65種特征，那些用來描述特征的詞匯稱為特征詞.如描述特征“動力”時，可以用“強勁”、“不足”等.每個文本可由其在所有特征下的取值，即特征詞所構(gòu)成的向量來表示，如表1所示.由于并非所有特征均在每一個文本中出現(xiàn)，所以得到的是一個非完備信息系統(tǒng)，某個文本在某特征下取值為空時，用*表示.

表1 汽車評論文本的表示(100篇)

在表1中，由于特征詞的種類太多，從而影響極大相容塊的求取.所以，我們基于領(lǐng)域知識，利用文獻[3]提供的情感詞詞表swt中規(guī)定的各特征詞的情感極性,再利用文獻[4]定義的條件屬性值映射公式，可以將表1中出現(xiàn)的特征詞映射成為兩個符號a和c，其中符號a表示該特征詞的情感傾向為正面，符號c表示該特征詞的情感傾向為負面，這樣表1便可以表示成表2的形式.

表2 將表1中情感詞映射后的結(jié)果

再利用文獻[4]提供的屬性重要性度量公式計算出所有65個特征的重要度，為了在求取極大相容塊時降低維度，選取前面最重要的25個特征進行計算.這樣，我們就可以按照上面提到的算法進行極大相容塊的求取，生成的極大相容塊數(shù)為1 023，如表3所示.

表3 對100篇文本形成的不完備信息系統(tǒng)求取極大相容塊的結(jié)果(部分)

4 結(jié)束語

本文首先將文本集表示成不完備信息系統(tǒng)的形式，然后對該系統(tǒng)進行特征詞映射等一系列預處理，進而利用改進的算法求取極大相容塊.實驗表明，該算法適合于在較大規(guī)模的不完備系統(tǒng)中進行極大相容塊的求取，然而，對于大規(guī)模的不完備信息系統(tǒng)，本算法還有待改進.

[1]Leung Y,Li D Y.Maximal consistent block technique for rule acquisition in incomplete information systems[J].Information Science, 2003,153:85-106.

[2]梁吉業(yè),王寶麗,錢宇華,等.一種不完備信息系統(tǒng)中極大相容塊的構(gòu)造算法[J].計算機科學,2006,33(11A):79-82.

[3]王素格.基于Web的評論文本情感分類問題研究[D].上海:上海大學,2008.

[4]趙乃剛，李德玉，王素格，等.一種新的不完備信息系統(tǒng)中屬性重要性度量及其應(yīng)用[J].計算機科學,2008,35(8A):251-254.

Abstract:A hierarchical algorithm for constructing Maximal Consistent Block in Incomplete Information System is proposed in [2].As a result,the process for constructing Maximal Consistent Block is greatly simplified.However,There is a weak point in the algorithm,while computing the maximal consistent block,without dislodging the Non-Maximal Consistent Block.As a result,The Space-complexity of program is proved greatly,so the algorithm used only to a small Incomplete Information System.Based the fatal shortcoming,In the present paper,A better algorithm is provided,which would be used to the major Incomplete Information System.

Key words:rough set;Incomplete Information System;maximal consistent Block；space-complexity

〔編輯 高海〕

A New Algorithm of Constructing Maximal Consistent Block in Incomplete Information System

ZHAO Nai-gang
(School of Mathematics&Computer Science,Shanxi Datong University,Datong Shanxi,037009)

TP18

A

1674-0874(2010)04-0015-03

2010-03-25

趙乃剛（1975－），男，山西應(yīng)縣人，碩士，助教，研究方向：數(shù)據(jù)挖掘.