合取型集值序信息系統(tǒng)組合熵和組合粒度研究?

李 燃 王青海

（青海師范大學(xué)計(jì)算機(jī)學(xué)院 西寧 810000）

1 引言

1982年，波蘭數(shù)學(xué)家Pawlak提出了粗糙集理論，它是一種在實(shí)際應(yīng)用中能解決數(shù)據(jù)屬性約簡(jiǎn)和規(guī)則挖掘問(wèn)題的數(shù)學(xué)工具［1～2］，其應(yīng)用核心基礎(chǔ)是從近似空間導(dǎo)出一對(duì)近似算子，即上近似集和下近似集［3］，并在很多方面都有成功的應(yīng)用［4～5］。但由于經(jīng)典粗糙集是基于論域上的等價(jià)關(guān)系，而現(xiàn)實(shí)世界的實(shí)際問(wèn)題中等價(jià)關(guān)系并不多見(jiàn)，為此很多學(xué)者對(duì)其進(jìn)行了擴(kuò)展研究［6～7］。

在現(xiàn)實(shí)問(wèn)題中，人們常會(huì)遇到諸如區(qū)域經(jīng)濟(jì)分析、市場(chǎng)占有率、從業(yè)行業(yè)分析等屬性具有偏好關(guān)系的一類信息系統(tǒng)，這類信息系統(tǒng)往往是不完備的信息系統(tǒng)，即某些屬性的取值是不確定的，可能是一個(gè)集合里面的不同值［8］。張文修、梁怡等把這樣的不完備的信息系統(tǒng)稱為集值信息系統(tǒng)［9］，在不完備信息系統(tǒng)中，分別提出了樂(lè)觀與悲觀兩種形式的多代價(jià)決策粗糙集方法［10］。文獻(xiàn)［11］討論了在集值信息系統(tǒng)中屬性值為區(qū)間的集值信息系統(tǒng)，將區(qū)間集值信息系統(tǒng)分為析取型和合取型集值信息系統(tǒng)，而且建立了兩者的優(yōu)勢(shì)關(guān)系，基于優(yōu)勢(shì)關(guān)系在粗糙集上進(jìn)行了研究。文獻(xiàn)［12］在合取型和析取型集值信息系統(tǒng)的基礎(chǔ)上，針對(duì)兩種集值序信息系統(tǒng)對(duì)決策規(guī)則和屬性約簡(jiǎn)進(jìn)行了研究。文獻(xiàn)［13］提出一種特殊的屬性偏好關(guān)系，這種偏好關(guān)系能夠解決一類屬性偏好既不是遞增有序也不是遞減有序，而是屬性值趨向于標(biāo)準(zhǔn)屬性值的問(wèn)題，稱之為屬性集中有序。

信息系統(tǒng)的不確定性度量是從信息視角研究其信息結(jié)構(gòu)的一種重要度量，包括從信息熵、粗糙熵、信息粒度、知識(shí)粒度等角度進(jìn)行闡明。根據(jù)經(jīng)典粗糙集近似空間中粒度的大小關(guān)系，不同信息系統(tǒng)中的關(guān)系有不同粗細(xì)程度，很多學(xué)者采用上述度量對(duì)信息系統(tǒng)進(jìn)行了不確定性研究。文獻(xiàn)［14］通過(guò)粒計(jì)算中知識(shí)的不確定性問(wèn)題，分析了粗糙集、模糊集以及熵空間等理論模型，對(duì)各種理論模型進(jìn)行討論，對(duì)知識(shí)粒度進(jìn)行了統(tǒng)一的描述，提出了知識(shí)不確定性與變化的知識(shí)粒度之間的聯(lián)系。文獻(xiàn)［15］中對(duì)信息系統(tǒng)分類能力的雙論域粗糙集的不確定性進(jìn)行研究，主要包括粗糙集的信息熵和信息粒度的定義及推廣。文獻(xiàn)［16］基于相容關(guān)系的粗糙集模型，提出了覆蓋的組合熵和組合粒度的概念，研究了他們之間的性質(zhì)與規(guī)律。文獻(xiàn)［17］針對(duì)粗糙集理論中不完備信息系統(tǒng)，提出了一種知識(shí)粒度的定義，并研究了知識(shí)粒度與信息熵的關(guān)系，為知識(shí)的度量和知識(shí)的評(píng)價(jià)提供了一種可行的方法。文獻(xiàn)［18］針對(duì)析取型集值序信息系統(tǒng)優(yōu)勢(shì)關(guān)系過(guò)于寬松的情況，引入了優(yōu)勢(shì)程度的參數(shù)問(wèn)題，對(duì)信息熵和知識(shí)粒度不確定性進(jìn)行了討論。而組合熵與組合粒度是度量信息系統(tǒng)不確定性的有效方法，其優(yōu)點(diǎn)在于具有對(duì)信息增益的易理解性。本文對(duì)合取型集值序信息系統(tǒng)采用組合熵和組合粒度進(jìn)行不確定性度量研究。

2 基礎(chǔ)部分

2.1 集值序信息系統(tǒng)

定義1［9］（信息系統(tǒng)）設(shè)一個(gè)信息系統(tǒng) S=（U，AT ，V，f），其中U={x1,x2…,xn}是一個(gè)非空有限的對(duì)象集，每個(gè)xi（i≤n）為其中一個(gè)對(duì)象，AT={a1,a2…,am}是信息系統(tǒng)里非空有限的屬性集，每個(gè)aj（j≤m）為其中一個(gè)屬性，V是信息系統(tǒng)屬性值的集合，f是U×AT到V的冪集P（V）的一個(gè)映射，即對(duì)?x∈U,a∈AT,f(x,a)∈P(V)。

根據(jù)集值信息系統(tǒng)的定義，把集值信息系統(tǒng)中元素之間是合取關(guān)系或析取關(guān)系的集值信息系統(tǒng)稱為合取型集值信息系統(tǒng)或析取型集值信息系統(tǒng)。若在集值信息系統(tǒng)某些屬性值上建立優(yōu)勢(shì)關(guān)系，則把屬性歸為一種準(zhǔn)則，把集值信息系統(tǒng)稱為集值序信息系統(tǒng)，將合取型集值信息系統(tǒng)或析取型集值信息系統(tǒng)稱為合取型集值序信息系統(tǒng)或析取型集值序值信息系統(tǒng)。本文僅介紹合取型集值序信息系統(tǒng)。

2.2 合取型集值序信息系統(tǒng)

例1 表1為一個(gè)合取型集值序信息系統(tǒng)，表示為學(xué)生學(xué)習(xí)能力的統(tǒng)計(jì)信息，其中U={x1,x2,x3,x4,x5,x6}表示6個(gè)不同的學(xué)生，AT={a1,a2,a3,a4}=｛理論能力，實(shí)踐能力，應(yīng)用能力，創(chuàng)新能力｝，V={a,b,c,d}=｛C語(yǔ)言，數(shù)據(jù)庫(kù)設(shè)計(jì)，計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用，數(shù)據(jù)結(jié)構(gòu)｝。

表1 一個(gè)合取型集值序信息系統(tǒng)

如表中x1(a2)=表示學(xué)生x1至少掌握數(shù)據(jù)庫(kù)設(shè)計(jì)，至多同時(shí)掌握數(shù)據(jù)庫(kù)設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)，在合取型集值序信息系統(tǒng)中，集合元素之間的關(guān)系是合取關(guān)系，也即“且”關(guān)系，針對(duì)合取型集值序信息系統(tǒng)，定義如下優(yōu)勢(shì)關(guān)系。

定義2［12］（優(yōu)勢(shì)關(guān)系）設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT ，定義的優(yōu)勢(shì)關(guān)系為={(x,y)∈U×U|||≥ ||? ||≥ |}，其中a∈A，||?代表集合的基數(shù)。

下限集合表示一名學(xué)生至少掌握的專業(yè)課，上限集合表示一名學(xué)生可能掌握的專業(yè)課，沒(méi)有定義各門(mén)專業(yè)課的重要程度，用掌握的專業(yè)課門(mén)數(shù)即基數(shù)來(lái)定義優(yōu)勢(shì)，這個(gè)優(yōu)勢(shì)關(guān)系可理解為在屬性集合A中，x優(yōu)于y當(dāng)且僅當(dāng)x下限中元素的基數(shù)大于或者等于y下限中元素的基數(shù)，同時(shí)滿足x上限中元素的基數(shù)大于或者等于y上限中元素的基數(shù)。例上表x=a3(x3)=y=a3(x4)=，為了表示方便，V的下限用表示，V的上限用表示，由于此時(shí)=,＞，所以在應(yīng)用能力方面，學(xué)生x3優(yōu)于學(xué)生x4。根據(jù)定義1，容易得出如下定理：

定理1 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT ，可得：

證明 1）

定義3（優(yōu)勢(shì)類）設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT ，設(shè)滿足屬性 a(a∈A)下優(yōu)勢(shì)關(guān)系優(yōu)勢(shì)類的集合表示為[={y∈U|(y,x)∈，論域U上所有優(yōu)勢(shì)類的集合表示為{[x∈U}。

定理2 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?M,N?AT ，可得：

3）若 xi∈[xj]，則 [xi]?[xj]，其 中 [xj]= ∪{[xi]|xi∈[xj]} 。

同理可證2）成立。

3）若存在 xi∈[xji,j∈{1,2,…n}，根據(jù)優(yōu)勢(shì)關(guān) 系 的 定 義 有 ?a∈A, 即 (xi,xj)∈則||≥ ||? ||≥ ||, f(xj,a)?f(xi,a)同 理?x∈[xif(xi,a)?f(x ,a ) ，所 以 f(xj,a)?f(x ,a ) ，有 x∈[，由定義3和定理2可得x∈[x]，[x?[x，其中 [x=∪{[x|x∈[x},ijijjiij f(xi,a)∈p(v),f(xj,a )∈p(v)。

定義4（粒度粗細(xì)）設(shè)一個(gè)合取型集值序信息系 統(tǒng) S=(U,AT,V,f),?M∈AT,?N∈AT,使 得[x]?[x]，則稱滿足優(yōu)勢(shì)關(guān)系優(yōu)勢(shì)類的集合U/細(xì)于U/R，即M比N精細(xì)，記作M?N 。

例2 根據(jù)表1所給出的合取型集值序信息系統(tǒng)，U={x1,x2,x3,x4,x5,x6}，AT={a1,a2,a3,a4}，設(shè)N={a1,a2},M={a1,a2,a3},各個(gè)優(yōu)勢(shì)類的集合為[x1]={x1,x3,x4,x6},[x2]={x1,x2,x3,x4,x6},[x3]={x3,x6},[x4]={x1,x3,x4,x6},[x5]={x1,x3,x4,x5,x6},[x6]={x3,x6},[x1]={x1,x3,x6},[x2]={x1,x2,x3,x6},[x3]={x3,x6},[x4]={x1,x3,x4,x6},[x5]={x3,x5,x6},[x6]={x3,x6}, 可得 [x]?[x]，M ? N 。

定理3 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），若 M?N ，即 [x]?[x]，則 | [x]|≤|[x]，其中 |. |代表集合的基數(shù)。

證明 由定理2可得。

3 組合熵和組合粒度

3.1 知識(shí)的組合熵

定義5（組合熵）設(shè)一個(gè)合取型集值序信息系統(tǒng)S=(U,AT,V,f),?A?AT定義知識(shí)A的組合熵為則0≤CE(A)＜1。約定：當(dāng)={[x]|x∈U}時(shí)，即優(yōu)勢(shì)關(guān)系的集合為單元素集，|=0，此時(shí)組合熵CE（A）取最大值1。由上述定義是優(yōu)勢(shì)關(guān)系上優(yōu)勢(shì)類的集合，|[ xi|表示在合取型集值序信息系統(tǒng)中優(yōu)勢(shì)關(guān)系優(yōu)勢(shì)類集合的基數(shù)。

定理4 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），若 M,N?AT ，M?N ，則CE（M）≥ CE（N）。

證明 若 M?N，由定義知，?xi∈U，使得[xi]?[xi], 即 ||[xi≤ ||[xi]，于是CE(M)=)=CE(N)，所以有 M?N ，存在CE（M）≥CE（N）。

由定理4得出，當(dāng)優(yōu)勢(shì)關(guān)系的集合越細(xì)時(shí)，組合熵的值也越大，集合越粗時(shí)，組合熵的值越小。組合熵反映了優(yōu)勢(shì)關(guān)系的分類能力，當(dāng)組合熵的值越大，表示知識(shí)的不確定性越弱，區(qū)分能力越強(qiáng)。

例3 根據(jù)例2可得CE(N)=28/45，CE(M)=7/9，CE（M）≥CE（N），結(jié)果與定理4一致。

3.2 組合粒度

定義6（組合粒度）設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT ，定義知識(shí)A的組合粒度為，則有 0＜CG(A)≤1。約定：當(dāng)U/={[x]|x∈U}時(shí)，即優(yōu)勢(shì)關(guān)系集合為單元素集，|=0，組合粒度CG（A）取最小值0。

定理5 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），若 M,N?AT ，M?N ，則CG（M）≤ CG（N）。

證明 若 M?N ，由 ?xi∈U ，使得 [xi]?[xi],則 ||[xi]≤ ||[xi]，于是 CG(M)=)=CG(N)，所以有 M?N，存在CG（M）≤ CG（N）。

例4 根據(jù)例2可得：CG(N)=17/45,CE(M)=2/9，CG（M）≤CG（N），結(jié)果與定理5一致。

結(jié)合定理4和5可以得出，當(dāng)優(yōu)勢(shì)關(guān)系下的集合越細(xì)時(shí)，組合熵的值也越大，相反組合粒度值越??；集合越粗時(shí)，組合熵的值越小，組合粒度的值反而越大。那么組合熵組合熵和組合粒度之間是否存在某種關(guān)系，下面進(jìn)行討論。

3.3 知識(shí)的組合熵和組合粒度之間的關(guān)系

定理6 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT ，知識(shí)A的組合熵和組合粒度有如下關(guān)系：CE（A）+CG（A）=1。

證明

例5 根據(jù)例3與例4的結(jié)果可得CE(N)+CG(N)=1,CE(M)+CG(M)=7/9+2/9=1,滿足定理6。

4 優(yōu)勢(shì)關(guān)系的優(yōu)化

前面在定義優(yōu)勢(shì)關(guān)系時(shí)，比較x與y上下限中集合基數(shù)的大小，例如表1中x1(a2)與x4(a2)上下限的基數(shù)的大小相等，所以x1(a2)優(yōu)于x4(a2)，同時(shí)x4(a2)也優(yōu)于x1(a2)，在實(shí)際問(wèn)題中并沒(méi)有考慮其它因素來(lái)定義優(yōu)勢(shì)關(guān)系，例各門(mén)專業(yè)課重要程度和選修的時(shí)間等?，F(xiàn)引入權(quán)值wi表示未考慮因素的重要程度，例定義C語(yǔ)言，數(shù)據(jù)庫(kù)設(shè)計(jì)，計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的權(quán)值分別為3，4，5，6。定義如下優(yōu)勢(shì)關(guān)系：

定義7（優(yōu)化后的優(yōu)勢(shì)關(guān)系）設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT,a∈A，定義優(yōu)勢(shì)關(guān)系為={(x,y)∈表示xi在屬性a的下限或上限權(quán)值的求和。

注意，定義7滿足定義2且上下限相等才存在的優(yōu)勢(shì)關(guān)系，那么這個(gè)優(yōu)勢(shì)關(guān)系可以理解為在屬性集合A中，當(dāng)x和y上下限集合基數(shù)相等，若滿足x下限中所有元素權(quán)值的求和大于或等于y下限中所有元素權(quán)值的求和，且x上限中所有元素權(quán)值的求和大于或等于y上限中所有元素權(quán)值的求和，則定義x優(yōu)于y。例如表1中 x1(a2)=x4(a2)=，得出 x1(a2)與 x4(a2)上下限的基數(shù)相等，權(quán)值=11,滿足，可得在實(shí)踐能力方面，學(xué)生x4優(yōu)于學(xué)生x1。

定理7 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT,?a?A,是上優(yōu)勢(shì)關(guān)系相等的部分，可得：

證明 略

定義8（優(yōu)化后的優(yōu)勢(shì)類）設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT,?a?A,滿足屬性a下優(yōu)化后優(yōu)勢(shì)關(guān)系的優(yōu)勢(shì)類表示為={y∈U|(y,x)∈，U上所有優(yōu)勢(shì)類的集合表示為{[x]|x∈U}。

定理8 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?I,J?AT,R∑wi是R?上優(yōu)勢(shì)關(guān)系相等的

AA部分，可得：

證明 略

例6 表2為一個(gè)合取型集值序信息系統(tǒng)，表示學(xué)生專業(yè)課能力統(tǒng)計(jì)信息，其中U={x1,x2,x3,x4,x5,x6}表示6個(gè)不同的學(xué)生，AT={a1,a2,a3,a4}=｛理論能力，實(shí)踐能力，應(yīng)用能力，創(chuàng)新能力｝，V=｛a，b，c，d｝=｛C語(yǔ)言，數(shù)據(jù)庫(kù)設(shè)計(jì)，計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用，數(shù)據(jù)結(jié)構(gòu)｝，定義C語(yǔ)言，數(shù)據(jù)庫(kù)設(shè)計(jì)，計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的權(quán)值分別為3，4，5，6。

表2 反映學(xué)生專業(yè)課能力的合取型集值序信息系統(tǒng)

定義9（優(yōu)化后的粒度粗細(xì)）設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?I∈AT,?J∈AT ，使得，則稱滿足優(yōu)勢(shì)關(guān)系優(yōu)勢(shì)類的集合U細(xì)于U，即I比J精細(xì)，記作 I?J 。

例7 根據(jù)表2所給出的合取型集值序信息系統(tǒng)，U={x1,x2,x3,x4,x5,x6}，AT={a1,a2,a3,a4}，設(shè)J={a1,a2},I={a1,a2,a3},各個(gè)優(yōu)勢(shì)類的集合為,滿足定理8，J?I?AT 則,且滿足定義9

定理9 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），若 I?J ，即|，其中 ||.代表集合的基數(shù)。

5 優(yōu)化后優(yōu)勢(shì)關(guān)系的組合熵和組合粒度

優(yōu)化后優(yōu)勢(shì)關(guān)系的組合熵與組合粒度所滿足的結(jié)論與優(yōu)化前的結(jié)論是否一致，下面對(duì)優(yōu)化后優(yōu)勢(shì)關(guān)系的組合熵和組合粒度進(jìn)行討論。

5.1 優(yōu)化后的組合熵

定義10（優(yōu)化后的組合熵）設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT 定義知識(shí)A的組合熵為0≤CE(A)＜1 。 約 定 ：當(dāng)U/={[x]|x∈U}，即優(yōu)化后優(yōu)勢(shì)關(guān)系集合為單元素集，，此時(shí)組合熵CE（A）取最大值1。

定理10 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），若 I,J?AT ，I?J ，則 CE（I）≥ CE（J）。

證明 若 I?J，由定義知，?xi∈U ，[x]?，于是 CE(I)=)=CE(J)，所以有I?J ，存在CE（I）≥ CE（J）。

比較定理4和定理10，優(yōu)化后優(yōu)勢(shì)關(guān)系組合熵與粗細(xì)程度之間關(guān)系與優(yōu)化前一致。當(dāng)優(yōu)勢(shì)關(guān)系下的集合越細(xì)時(shí)，組合熵的值也越大，集合越粗時(shí)，組合熵的值越小。

例8 根據(jù)例7可得：CE(J)=61/90，CE(I)=73/90 ，CE（I）≥ CE（J），結(jié)果與定理10一致。

5.2 優(yōu)化后的組合粒度

定義11（優(yōu)化后的組合粒度）設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），?A?AT ，定義知識(shí)A的組合粒度為，則有0＜CG(A)≤1。約定：當(dāng)U/={[x]|x∈U}時(shí)，優(yōu)化后優(yōu)勢(shì)關(guān)系集合為單元素集=0，此時(shí)組合粒度CG（A）取最小值0。

定理11 設(shè)一個(gè)合取型集值序信息系統(tǒng)S=（U，AT，V，f），若 I,J?AT ，I?J ，則 CG（I）≤ CG（J）。

證明 若 I?J，?xi∈U ，則即，于 是 CG(I)，所以有 I?J ，存在 CG(I)≤CG(J).

例9 根據(jù)例7可得：CG(J)=29/90,CG(I)=17/90 ，CG（I）≤ CG（J），結(jié)果與定理11一致。

比較定理10和11，優(yōu)化后優(yōu)勢(shì)關(guān)系的集合越細(xì)時(shí)，組合熵的值越大，相反組合粒度值越?。患显酱謺r(shí)，組合熵的值越小，組合粒度的值反而越大，與優(yōu)化前組合熵和組合粒度粗細(xì)粒度大小結(jié)論一致。

6 結(jié)語(yǔ)

集值信息系統(tǒng)是對(duì)不完備信息系統(tǒng)的一種拓展與延續(xù)，在現(xiàn)實(shí)空間中也廣泛存在這類或約束條件更多的使用實(shí)例。本文在合取型集值序信息系統(tǒng)的二元優(yōu)勢(shì)關(guān)系上，引入組合熵和組合粒度對(duì)優(yōu)勢(shì)關(guān)系粗細(xì)程度的度量進(jìn)行研究和探討，針對(duì)滿足優(yōu)勢(shì)關(guān)系但優(yōu)勢(shì)程度不同的情形進(jìn)行了改進(jìn)和優(yōu)化，從而使改進(jìn)后的優(yōu)勢(shì)關(guān)系更加符合實(shí)際情形，且在改進(jìn)后的優(yōu)勢(shì)關(guān)系中，引入組合熵與組合粒度進(jìn)行不確定性度量的研究，研究表明改進(jìn)后的優(yōu)勢(shì)關(guān)系的組合熵與組合粒度之間的結(jié)論與改進(jìn)前結(jié)論一致，即隨著優(yōu)勢(shì)關(guān)系的逐步變細(xì)，其組合熵逐步遞增，組合粒度逐步遞減。但在實(shí)際問(wèn)題中除了優(yōu)勢(shì)關(guān)系權(quán)值的不同，可能還會(huì)有其他條件的限制，如本文例子中，對(duì)計(jì)算機(jī)學(xué)院學(xué)生能力的合取型集值序信息系統(tǒng)中存在不同課程在不同時(shí)期的學(xué)習(xí)等，這都將是下一步深入研究的方向。