一種面向缺失數(shù)據(jù)的信息熵和知識粒度

黃衛(wèi)華

(1.文山學(xué)院 數(shù)學(xué)學(xué)院,云南 文山 663099;2.山西大學(xué) 計算智能與中文信息處理教育部重點實驗室,山西 太原 030006)

一種面向缺失數(shù)據(jù)的信息熵和知識粒度

黃衛(wèi)華1,2

(1.文山學(xué)院 數(shù)學(xué)學(xué)院,云南 文山 663099;2.山西大學(xué) 計算智能與中文信息處理教育部重點實驗室,山西 太原 030006)

針對含有缺失數(shù)據(jù)的數(shù)據(jù)集的不確定性度量問題,分別給出了信息熵和知識粒度的公理化定義,并提出了該環(huán)境下的粗糙集的兩種不確定性度量,證明了精度是一種信息熵,粗糙度是一種知識粒度,并得出了幾個較好的性質(zhì),進(jìn)一步克服了已有缺失數(shù)據(jù)集不確定性度量的部分局限性,實例驗證了不確定性度量的有效性,且適合度量含缺失數(shù)據(jù)的粗糙集的模糊性和精確性。關(guān)鍵詞：非完備信息系統(tǒng);信息熵;知識粒度

0 引言

在許多實際問題中,數(shù)據(jù)取值缺失的現(xiàn)象廣泛存在,造成數(shù)據(jù)缺失的原因主要有以下幾個方面:一是某些信息暫時無法獲取,如病人的某項醫(yī)療診斷結(jié)果;二是由于數(shù)據(jù)采集設(shè)備、存儲介質(zhì)、傳輸媒體或人為因素等原因造成數(shù)據(jù)遺漏;三是某些對象的某個或某些屬性是不可用的,如未成年人的固定收入情況、未婚者的配偶信息等;四是獲取某些信息的代價太大。所有這些不能或不便及時獲取的信息一般用*表示。

1948年由香農(nóng)[1]定義的信息熵給出了對信息系統(tǒng)內(nèi)部結(jié)構(gòu)離散型隨機(jī)變量的不確定性度量,其優(yōu)點是便于描述各種模式中的信息量且可以應(yīng)用于許多不同的領(lǐng)域。在粗糙集理論中,關(guān)于物質(zhì)世界的知識可以利用某一確定的粒度來表示,這個粒度可以通過劃分或等價關(guān)系被精確的描述。但是現(xiàn)有的粗糙集的不確定性度量并沒有考慮由等價關(guān)系引起劃分的粒度,不能很好地描述粗糙集的不確定性,使得粗糙集在某些領(lǐng)域的應(yīng)用受到限制。信息熵和知識粒度是信息系統(tǒng)中關(guān)于不確定性度量的兩種主要方法,一些研究者利用香農(nóng)熵和改進(jìn)的香農(nóng)熵去度量粗糙集的不確定性。Wierman[2]介紹了一種不確定性度量——粒度度量及其公理化推導(dǎo),理論表明它與香農(nóng)熵具有較強(qiáng)的聯(lián)系;Hartley[3]的不確定性度量對Wierman的粒度度量提供了強(qiáng)有力的支持;苗奪謙等[4]研究了粗糙集中信息熵和知識粗糙性之間的關(guān)系, 表明可以利用信息熵度量粗糙性; Yao[5]基于粗糙集理論研究了知識粒度和概念近似的關(guān)系, 指出知識粒度是一種處理不確定性信息和概念近似的有效且實際的解決方法;王國胤等[6]從信息論觀點和代數(shù)觀點出發(fā),對Rough集理論進(jìn)行了比較分析,并把條件信息熵作為屬性重要性度量,提出了一種決策表的啟發(fā)式約簡算法;文獻(xiàn)[7]給出了粗糙集理論中模糊性和不確定性度量的新方法;文獻(xiàn)[8-9]建立了完備信息系統(tǒng)的信息熵、粗糙熵和知識粒度之間的關(guān)系;文獻(xiàn)[10]基于香農(nóng)熵解決了完備信息系統(tǒng)中粗糙集的不確定性度量和粗糙關(guān)系數(shù)據(jù)庫;文獻(xiàn)[11]給出了粗糙集的一個改進(jìn)的不確定性度量,該度量利用過剩熵度量粗糙集的不確定性。

如何從含有缺失數(shù)據(jù)的非完備信息系統(tǒng)中獲得有用的知識,已成為一個重要的研究方向[12]。GU等[13-14]分別給出了相容和不相容多粒度決策系統(tǒng)中的知識獲取算法。文獻(xiàn)[15]利用矩陣?yán)碚摻o出了易于實現(xiàn)的模糊性度量和粗糙性度量的矩陣算法。文獻(xiàn)[16]研究了幾種知識的不確定性度量之間的關(guān)系,文獻(xiàn)[17]提出了一種基于一般二元關(guān)系的加權(quán)不確定性度量,統(tǒng)一了完備信息系統(tǒng)和非完備信息系統(tǒng)中的知識不確定性度量。吳偉志等[18]研究了多粒度標(biāo)記下的非完備信息系統(tǒng)中的知識獲取問題。另外,針對含有缺失數(shù)據(jù)的數(shù)據(jù)集的特征選擇問題現(xiàn)已成為數(shù)據(jù)挖掘領(lǐng)域的研究熱點，許多學(xué)者已經(jīng)開展了深入的研究,并取得了可喜的研究成果[19-22]。

從完備信息系統(tǒng)到非完備信息系統(tǒng)某些結(jié)果的推廣還是很困難的。為了度量非完備信息系統(tǒng)中粗糙集的不確定性,文獻(xiàn)[23]定義了一種非完備信息系統(tǒng)中粗糙集的不確定性度量。本文給出了信息熵和知識粒度的公理化定義,并提出了兩種新的不確定性度量,該度量克服了現(xiàn)有不確定性度量的局限性,能夠度量非完備信息系統(tǒng)中粗糙集的模糊性和精確性,舉例驗證了新的度量的有效性,并導(dǎo)出了該定義的一些重要性質(zhì)。

1 基本概念[11,24]

一個信息系統(tǒng)是一個有序數(shù)組S=(U,A),其中U表示所有對象的非空有限集合,稱為論域;A表示所有特征的非空有限集合,稱為屬性集;?a∈A,存在一個映射a,a∶U→Va,其中Va是a的值域。

對于任一給定信息系統(tǒng)S=(U,A),設(shè)P?A,定義U上由P誘導(dǎo)的相容關(guān)系如下:

SIM(P)={(u,v)∈U×U|?a∈P,a(u)=a(v)∨a(u)=*∨a(v)=*}.

令SP(u)={v∈U|(u,v)∈SIM(P)},表示論域U中與u可能不可區(qū)分的對象的最大集合,叫作對象u關(guān)于屬性P的相容類。

在非完備信息系統(tǒng)中,特別地,ω(U)={{x}|x∈U}稱為恒等關(guān)系;δ(U)={U}稱為全域關(guān)系,在不引起混淆的情況下,簡記作ω和δ.

令S=(U,A)表示一個非完備的信息系統(tǒng),P?A,?≠X?U,定義U中X的下近似和上近似如下:

注:本節(jié)所有概念是在粗糙集理論意義下的。

2 現(xiàn)有知識粒度及其局限性

下面我們通過一個例子說明Pawlak定義的精度和粗糙度在某些情況下區(qū)分度不明顯,存在一定的局限性。

例1 考慮表1中幾個小汽車的描述。

這是一個含有缺失數(shù)據(jù)的非完備信息系統(tǒng),其中U={u1,u2,u3,u4,u5,u6},A={a1,a2,a3,a4},a1,a2,a3,a4分別表示Price,Size,Engine和Max-speed.易得U/SIM(A)={SA(u1),SA(u2),SA(u3),SA(u4),SA(u5),SA(u6)},

其中SA(u1)={u1},SA(u2)={u2,u6},SA(u3)={u3},SA(u4)={u4,u5},SA(u5)={u4,u5,u6},SA(u6)={u2,u5,u6}.

表1 關(guān)于小汽車的信息系統(tǒng)

令P={a2,a4},則U/SIM(P)={SP(u1),SP(u2),SP(u3),SP(u4),SP(u5),SP(u6)},其中SP(u1)={u1,u2,u6},SP(u2)={u1,u2,u6},SP(u3)={u3},SP(u4)={u4,u5,u6},SP(u5)={u4,u5,u6},SP(u6)={u1,u2,u4,u5,u6}.

顯然U/SIM(A)?U/SIM(P),所以AP.

注意,由上例可知,兩個知識表達(dá)系統(tǒng)U/SIM(A)和U/SIM(P)之間存在包含關(guān)系,但文獻(xiàn)[8]定義的集合的精度和粗糙度相等。因此,我們有必要重新定義一個粗糙集的精度更高的不確定性度量。

3 信息熵和知識粒度

知識粒度是論域中對知識粒的平均度量,是對論域劃分的一種較易理解的描述,也代表分類的能力。1979年,Zaded[16]提出了模糊集和信息粒的問題,梁吉業(yè)[10]等討論了信息系統(tǒng)中與粒計算有關(guān)的幾個度量,粒度度量、信息熵、粗糙熵、知識粒度以及它們之間的關(guān)系,但對信息熵沒有統(tǒng)一的描述。下文給出了信息熵的公理化定義,證明了以上知識度量是公理化的特例。

定義2 設(shè)S=(U,A)是一個非完備的信息系統(tǒng),?P?A,若存在實數(shù)GE(P)與之對應(yīng),且滿足:

(2)?P,Q?A,若P≈Q,有GE(P)=GE(Q)(不變性);

(3)?P,Q?A,若PQ,有GE(P)>GE(Q)(嚴(yán)格單調(diào)性)。

則稱GE(P)為非完備信息系統(tǒng)S=(U,A)上的信息熵。

定義3 令S=(U,A)表示一個非完備的信息系統(tǒng),?≠X?U,R?A,X關(guān)于R的精度定義為:

定理1 定義3中的ACR(X)是定義2意義下的一個信息熵。

(2)令P,Q?A,則K(P)={SP(u1),SP(u2),…,SP(u|U|)},K(Q)={SQ(u1),SQ(u2),…,SQ(u|U|)},如果P≈Q,則對任意?i∈{1,2,…,|U|},都有SP(ui)=SQ(ui),則|SP(ui)|=|SQ(ui)|,因此有

(3)令P,Q?A,則K(P)={SP(u1),SP(u2),…,SP(u|U|)},K(Q)={SQ(u1),SQ(u2),…,SQ(u|U|)},如果PQ,則對任意?ui∈U,都有SP(ui)?SQ(ui),則|SP(ui)|≤|SQ(ui)|,且存在某個u0∈U,使得SP(u0)?SQ(u0),所以

那么αP(X)>αQ(X),所以ACP(X)>ACQ(X),滿足嚴(yán)格單調(diào)性。

由此可得,定義3中的ACR(X)是定義2意義下的一個信息熵。

在新的定義中,已經(jīng)考慮了由等價關(guān)系導(dǎo)致的劃分的粒度。顯然由定理1的證明可以看出,新的精度具有以下性質(zhì)。

性質(zhì)1 (等價性)設(shè)S=(U,A)表示一個非完備的信息系統(tǒng),??X?U,P,Q?A, 若U/SIM(P)=U/SIM(Q),則ACP(X)=ACQ(X).

顯然,當(dāng)S=(U,A)表示一個非完備的信息系統(tǒng)時,對于A的任意子集R,0≤ACR(X)≤1.

定義4 設(shè)S=(U,A)是一個非完備的信息系統(tǒng),?P?A,若存在實數(shù)G(P)與之對應(yīng),且滿足:

(2)?P,Q?A,若P≈Q,有G(P)=G(Q)(不變性);

(3)?P,Q?A,若PQ,有G(P)

則稱G(P)為非完備信息系統(tǒng)S=(U,A)上的知識粒度。

定義5 令S=(U,A)表示一個非完備的信息系統(tǒng),??X?U,R?A,X關(guān)于R的粗糙度定義為:

定理2 定義5中的RNR(X)是定義4意義下的一個知識粒度。

(2)令P,Q?A,則K(P)={SP(u1),SP(u2),…,SP(u|U|)},K(Q)={SQ(u1),SQ(u2),…,SQ(u|U|)},如果P≈Q,則對任意?i∈{1,2,…,|U|},都有SP(ui)=SQ(ui),則|SP(ui)|=|SQ(ui)|,因此有

所以ACP(X)=ACQ(X),則RNP(X)=RNQ(X) .

(3)令P,Q?A,則K(P)={SP(u1),SP(u2),…,SP(u|U|)},K(Q)={SQ(u1),SQ(u2),…,SQ(u|U|)},如果PQ,則對任意?ui∈U,都有SP(ui)?SQ(ui),則|SP(ui)|≤|SQ(ui)|,且存在某個u0∈U,使得SP(u0)?SQ(u0),所以

由此可得,定義5中的RNR(X)是定義4意義下的一個知識粒度。

從定理2的證明可知,粗糙度具有等價性、有界性和單調(diào)性。

例2 (上接例1)設(shè)X={u1,u2,u4,u6},計算αA(X)=αP(X)=0.4;E(A)=0.667,E(P)=0.5,所以X關(guān)于A和P精度分別為ACA(X)=0.267,ACP(X)=0.2,粗糙度分別為RNA(X)=0.733,RNP(X)=0.8.

顯然,X關(guān)于R的精度隨著R的加細(xì)而增加,粗糙度隨著R的加細(xì)在減小。

4 實驗

利用本文給出的方法,考慮關(guān)于網(wǎng)球規(guī)劃的信息系統(tǒng)(見表2),其中U={u1,u2,…,u24},A={a1,a2,a3,a4},a1=Outlook,a2=Temperature,a3=Humidity,a4=Windy.令P={a2,a4},X1={u1,u4,u6,u8,u9,u15,u17,u21,u24},X2={u3,u4,u5,u6,u10,u11,u12,u15,u16,u19,u21,u22,u23},X3={u1,u2,u3,u4,u6,u10,u11,u13,u14,u15,u16,u19,u20,u21},X4={u3,u7,u9,u16,u18,u19,u24},X5={u1,u2,u10,u11,u12,u13,u14,u20,u21},X6={u1,u2,u3,u4,u5,u6,u7,u8,u9,u12,u13,u14,u15,u16,u17,u18,u19,u22,u23,u24}.表3為兩種知識表達(dá)系統(tǒng)中元素的對照表。

表2 關(guān)于規(guī)劃網(wǎng)球的信息系統(tǒng)

幾種已有的知識粒度見表4,這些集合關(guān)于A和P有相同的上、下近似,也有相同的α(X),因此經(jīng)典粗糙集的粗糙度不能區(qū)分兩種知識表達(dá)系統(tǒng),文獻(xiàn)[5,25,26]定義的知識粒度可以區(qū)分出來。表5為兩種粗糙集的上、下近似對照表。

利用定義1計算得:E(A)=0.745,E(P)=0.462.再根據(jù)定義3和定義5,計算本文和文獻(xiàn)[23]定義的兩種知識表達(dá)系統(tǒng)下的精度見表6。

表3 兩種知識表達(dá)系統(tǒng)的元素

續(xù)表3 兩種知識表達(dá)系統(tǒng)的元素

表4 幾種知識粒度的比較

表5 兩種粗糙集的上、下近似

表6 不同對象集下幾種信息熵的比較

從表6可以看出這些集合關(guān)于A和P有相同的上、下近似,也有相同的α(X),但AC(X)不同,原因是A和P的知識粒度不同。因此,新的信息熵對關(guān)于不同等價關(guān)系的不確定性被很好地描述,表明本文的方法是有效的。

5 結(jié)論

本文給出了信息熵和知識粒度的公理化定義,證明了本文定義的精度和粗糙度是公理化定義的特殊形式,并推導(dǎo)了新度量的幾個較好的性質(zhì),驗證了新度量能夠克服現(xiàn)有不確定性度量的有限性,并且可以用來度量非完備信息系統(tǒng)中粗糙集的精度和粗糙度。

[1] Shannon C E.The Mathematical Theory of Communication[J].TheBellSystemTechnicalJournal,1948,27(3-4):373-423.

[2] Wierman M J.Measuring Uncertainty in Rough Set Theory[J].InternationalJournalofGeneralSystems,1999,28(4):283-297.

[3] Hartley R V L.Transmission of Information[J].TheBellSystemsTechnicalJournal,1928,7(3):535-563.

[4] 苗奪謙,王玨.粗糙集理論中概念與運算的信息表示[J].軟件學(xué)報,1999,10(2):113-116.

[5] Yao Y Y.Information Granulation and Rough Set Approximation[J].InternationJournalofIntelligentSystems,2001,16(1):87-104.DOI:10.1002/1098-111X.

[6] 王國胤,于洪,楊大春.基于條件信息熵的決策表約簡[J].計算機(jī)學(xué)報,2002,25(7):759-766.

[7] Liang J Y,Chin K S,Dang C Y,etal.A New Method for Measuring Uncertainty and Fuzziness in Rough Set Rheory[J].InternationalJournalofGeneralSystems,2002,31(4):331-342.DOI:http:∥dx.doi.org/10.108010308107021000013635.

[8] Liang J Y,Shi Z Z.The Information Entropy,Rough Entropy and Knowledge Granulation in Rough Set Theory[J].InternationalJournalofUncertainty,FuzzinessandKnowledge-BasedSystems,2004,12(1):37-46.DOI:10.1142/S0218488504002631.

[9] Liang J Y,Li D Y.Uncertainty and Knowledge Acquisition in Information System[M].Beijing:Science Press (in Chinese),2005.

[10] Beaubouef T,Petry F E,Arora G.Information-theoretic Measures of Uncertainty for Rough Sets and Rough Relational Databases[J].InformationSciences,1998,109(48):185-195.

[11] Pawlak Z.Rough Sets[J].InternationalJournalofComputerandInformationSciences,1982,11(5):341-356.

[12] 梁吉業(yè),李德玉.信息系統(tǒng)中的不確定性與知識獲取[M].北京:科學(xué)出版社,2005.

[13] GU S M,WU W Z.Knowledge Acquisition in Inconsistent Multi-scale Decision Systems[C]∥YAO J T,RAMANNA S,WANG G Y,etal.eds.Lecture Notes in Computer Science.Berlin,Germany:Springer,2011,6954:669-678.DOI:10.1007/978-3-642-24425-4_84.

[14] GU S M,WU W Z.On Knowledge Acquisition in Multi-scale Decision Systems[J].InternationalJournalofMachineLearningandCybernetics,2013,4(5):477-486.DOI:10.1007/s13042-012-0115-7.

[15] 解濱,米據(jù)生,張軍鵬.粗糙集不確定性度量的矩陣運算[J].計算機(jī)工程與應(yīng)用,2011,47(29):42-45.

[16] 劉財輝,苗奪謙,岳曉冬,等.知識不確定性度量及其關(guān)系研究[J].計算機(jī)科學(xué),2014,41(3):66-70.DOI:1002-137X.2014.03.013.

[17] 滕書華,盧敏,楊阿鋒,等.基于一般二元關(guān)系的粗糙集加權(quán)不確定性度量[J].計算機(jī)學(xué)報,2014,37(3):649-665.

[18] 吳偉志,陳穎,徐優(yōu)紅,等.協(xié)調(diào)的非完備多粒度標(biāo)記決策系統(tǒng)的最優(yōu)粒度選擇[J].模式識別與人工智能,2016,29(2):108-115.

[19] Zadeh L A.Fuzzy Sets and Information Granularity[J].AdvancesinFuzzySetTheoryandApplication.Amsterdam:North-Holland,1979:3-18.DOI:10.1142/9789814261302_0022.

[20] Liang J Y,Shi Z Z.Information Entropy,Rough Entropy and Knowledge Granulation in Incomplete Information Systems[J].InternationalJournalofGeneralsystems,2006,35(6):641-654.DOI:10.1080/03081070600687668.

[21] 錢宇華,梁吉業(yè),王鋒.面向非完備決策表的正向近似特征選擇加速算法[J].計算機(jī)學(xué)報,2011,34(3):435-442.DOI:10.3724/SP.J.1016.2011.00435.

[22] 王鋒,魏巍.缺失數(shù)據(jù)數(shù)據(jù)集的組增量式特征選擇[J].計算機(jī)科學(xué),2015,42(7):285-290.DOI:10.11896/j.issn.1002-137X.2015.07.061.

[23] Wang J H,Liang J Y,Qian Y H,etal.Uncertainty Measure of Rough Sets Based on Aknowledge Granulation for Incomplete Information Systems[J].InternationalJournalofUncertainty,FuzzinessandKnowledge-BasedSystems,2008,16(2):233-244.DOI:10.1142/S0218488508005157.

[24] Pawlak Z,Skowron A.Rudiments of Rough Sets[J].InformationSciences,2007,177(1):3-27.DOI:10.1016/j.ins.2006.06.003.

[25] Qian Y H,Liang J Y.Combination Entropy and Combination Granulation in Incomplete Information System[J].LectNotesArtifIntel,2006,4062:184-190.DOI:10.1007/11795131_27.

[26] Liang J Y,Xu Z B.The Algorithm on Knowledge Reduction in Incomplete Information Systems[J].IntJUncertainFuzz,2002,24(1):95-103.DOI:10.1142/S021848850200134X.

A Kind of Information Entropy and Information Granularity for Missing Data

HUANG Weihua1,2

(1.SchoolofMathematics,WenshanUniversity,Wenshan663099,China;2.KeyLaboratoryofComputationalintelligence&ChineseInformationProcessingofMOE,ShanxiUniversity,Taiyuan030006，China)

For the uncertainty measurement problem with missing data,an axiomatic definition of information entropy and knowledge granularity is given,and two ancertainty measwres ment approaehes are presented.It is proved that the precision is a kind of information entropy, and then some properties of entropy measurement are deduced.The new measurements are validated that they can overcome the limitations of existing uncertainty measurement,and they can be used to measure the accuracy and roughness of the rough set in incomplete information system.

incomplete information system;information entropy;knowledge granularity

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.01.011

2016-10-18；

2016-11-01

國家自然科學(xué)基金 (11361074);云南省教育廳科研基金(2015Y470);文山學(xué)院重點學(xué)科數(shù)學(xué)建設(shè)基金(12WSXK01)

黃衛(wèi)華(1979-),女,碩士,講師,主要從事信息代數(shù)和粗糙集理論的研究，E-mail:850755022@qq.com

TP18

A

0253-2395(2017)01-0084-08