多粒度形式概念分析的介粒度標(biāo)記方法

李金海 李玉斐 米允龍 吳偉志

1(昆明理工大學(xué)數(shù)據(jù)科學(xué)研究中心 昆明 650500)2(昆明理工大學(xué)理學(xué)院 昆明 650500)3(中國科學(xué)院大學(xué)計(jì)算機(jī)與控制學(xué)院 北京 100190)4(浙江海洋大學(xué)數(shù)理與信息學(xué)院 浙江舟山 316022)5(浙江省海洋大數(shù)據(jù)挖掘與應(yīng)用重點(diǎn)實(shí)驗(yàn)室(浙江海洋大學(xué)) 浙江舟山 316022)

粒計(jì)算以信息?；喕瘡?fù)雜問題獲得滿意解而著稱.目前，典型的粒計(jì)算方法包括模糊信息?；痆1]、熵空間法[2]、三支決策[3]等.近年來，粒計(jì)算被視作大數(shù)據(jù)分析與處理的有效工具[4-6]，應(yīng)用于各個(gè)前沿領(lǐng)域，更多討論見文獻(xiàn)[7-12].

眾所周知，形式概念分析[13]與粗糙集[14]是2種重要的粒計(jì)算方法.前者通過樣本?；⑻卣髁；?、概念知識(shí)?；确绞襟w現(xiàn)粒計(jì)算思想[15-19]，后者則是利用信息?；?、空間粒化、多粒度結(jié)構(gòu)等實(shí)現(xiàn)粒計(jì)算功能的知識(shí)發(fā)現(xiàn)[20-27].實(shí)際上，如果撇開上述2種理論在體系結(jié)構(gòu)上的差異，僅從實(shí)際需求出發(fā)，那么形式概念分析與粗糙集研究的諸多問題均存在共性，比如?；瘻?zhǔn)則、近似空間、屬性冗余、規(guī)則挖掘等.另外，基于相同數(shù)據(jù)結(jié)構(gòu)比較這2種理論的優(yōu)劣也是一種增強(qiáng)互補(bǔ)性分析的重要方式.鑒于此，一些學(xué)者在討論有關(guān)問題時(shí)頻繁表現(xiàn)出研究內(nèi)容上的互通性.也就是，從事形式概念分析研究的學(xué)者很自然會(huì)想到這一問題的粗糙集解決方法；反之，利用粗糙集討論某一問題時(shí)，人們也會(huì)習(xí)慣性地聯(lián)想到形式概念分析處理該問題的具體實(shí)效[28-29].

不僅如此，人們還從多粒度標(biāo)記(或多尺度)角度基于形式概念分析和粗糙集建立了多種廣義粒計(jì)算模型[22-23,27].需要指出的是，無論是形式概念分析還是粗糙集，多粒度標(biāo)記數(shù)據(jù)的相關(guān)工作主要集中于粒度標(biāo)記信息?；?、最優(yōu)粒度選擇和規(guī)則挖掘等研究方向[24-26,30-32].實(shí)際上，多粒度標(biāo)記或多尺度思想的實(shí)際來源較為廣泛.比如，類別等級(jí)意義下的數(shù)據(jù)表示[22]、尺度放縮環(huán)境下的數(shù)據(jù)采集[31]，以及屬性特征值的合并與分解[33]等.目前，基于粗糙集的多粒度標(biāo)記理論的研究已相對(duì)成熟，但針對(duì)形式概念分析的多粒度標(biāo)記理論才剛建立，仍有一些富有挑戰(zhàn)性的問題有待探討，更多論述見文獻(xiàn)[34].

為此，本文關(guān)注形式概念分析的多粒度標(biāo)記理論框架的完善與擴(kuò)展.具體地，在文獻(xiàn)[34]建立的多粒度標(biāo)記形式背景的基礎(chǔ)上，進(jìn)一步提出介粒度標(biāo)記形式背景的概念，以滿足多層次知識(shí)發(fā)現(xiàn)的需求.該問題可大致描述為：現(xiàn)有的多粒度標(biāo)記形式背景均假設(shè)所有屬性的粒度標(biāo)記個(gè)數(shù)兩兩相同，它簡單地將所有屬性的粒度標(biāo)記值通過多個(gè)單粒度標(biāo)記形式背景的并置予以表示.這種表示方法延續(xù)了粗糙集理論中多粒度標(biāo)記信息系統(tǒng)的慣用做法，因此一些共性問題依然會(huì)出現(xiàn)，即容易導(dǎo)致后續(xù)相關(guān)研究以單粒度標(biāo)記數(shù)據(jù)為最小單位討論相關(guān)問題，不利于多粒度標(biāo)記數(shù)據(jù)進(jìn)行多層次知識(shí)發(fā)現(xiàn).然而，根據(jù)粗糙集理論中多粒度標(biāo)記信息系統(tǒng)的研究經(jīng)驗(yàn)，可以對(duì)單粒度標(biāo)記數(shù)據(jù)的屬性粒度標(biāo)記值進(jìn)行重組以獲得重構(gòu)數(shù)據(jù)結(jié)構(gòu)，進(jìn)而得到可行的解決方法.本文將采用完備格的擴(kuò)充方式實(shí)現(xiàn)多層次知識(shí)發(fā)現(xiàn).具體地，重構(gòu)單粒度標(biāo)記形式背景的屬性粒度標(biāo)記值，通過數(shù)據(jù)重構(gòu)研究介粒度標(biāo)記形式背景，包括介粒度標(biāo)記形式背景的定義、語義解釋、泛化、特化，以及介粒度標(biāo)記決策形式背景的知識(shí)發(fā)現(xiàn)等.此外，實(shí)驗(yàn)分析說明了介粒度標(biāo)記方法的一些優(yōu)勢(shì)，這為將來深入探討多粒度形式概念分析的多層次知識(shí)發(fā)現(xiàn)、表示與處理奠定了基礎(chǔ).

1 相關(guān)工作

本文統(tǒng)一用U表示論域，即非空有限對(duì)象集.信息系統(tǒng)的非空有限屬性集用C表示；形式背景的非空有限屬性集用A表示.

定義1[14].一個(gè)經(jīng)典的信息系統(tǒng)可表示成序?qū)?U,C)，其中U={u1,u2,…,un}，C={a1,a2,…,am}.

定義2[22].若一個(gè)信息系統(tǒng)(U,C)的屬性集

(1)

在p個(gè)粒度空間下取值，且每個(gè)屬性粒度值相對(duì)于粒度粗細(xì)關(guān)系形成全序，則稱(U,C)為多粒度標(biāo)記信息系統(tǒng).

需要指出的是，不宜將在p個(gè)粒度空間下取值簡單理解為p個(gè)不同值，因?yàn)閺拇罅康膶?shí)例中發(fā)現(xiàn)，有些不同值可能來源于對(duì)某一取值的語義進(jìn)行各種轉(zhuǎn)化得到，即僅僅只是描述形式上的不同，實(shí)際上指的是同一個(gè)值.

定義3[13].一個(gè)形式背景可表示為三元組(U,A,I)，其中I是布爾關(guān)系，即任意u∈U，a∈A，要么uIa，要么uIa，其中表示邏輯非運(yùn)算.

為了使規(guī)則推理非平凡，本文僅討論正則形式背景[35].

定義4[13].設(shè)(U,A,I)為形式背景，對(duì)于X?U，B?A，記

X*={a∈A|?u∈X,uIa},

(2)

B*={u∈U|?a∈B,uIa},

(3)

稱映射序?qū)?*,*)的不動(dòng)點(diǎn)(X,B)(即X*=B，B*=X)為形式概念，該不動(dòng)點(diǎn)的2個(gè)分量分別為外延和內(nèi)涵.

依據(jù)上述定義，易得下列性質(zhì).

性質(zhì)1[13].對(duì)于形式背景(U,A,I)的2個(gè)概念(Xs,Bs)和(Xt,Bt)(s,t∈T，T是指標(biāo)集)，定義

(Xs,Bs)≤(Xt,Bt)?Xs?Xt,

(4)

(Xs,Bs)∨(Xt,Bt)=((Xs∪Xt)**,Bs∩Bt),

(5)

(Xs,Bs)∧(Xt,Bt)=(Xs∩Xt,(Bs∪Bt)**),

(6)

則(U,A,I)的所有概念構(gòu)成一個(gè)完備格，稱為概念格.

定義5[35].稱屬性不相交的2個(gè)形式背景(U,A,I)和(U,D,J)的并置為決策形式背景，記為(U,A,I,D,J).

注意，文獻(xiàn)[36]也給出了與決策形式背景(U,A,I,D,J)相類似的數(shù)據(jù)結(jié)構(gòu)，但命名為訓(xùn)練形式背景.盡管命名不同，但是通常均稱A為條件屬性集，D為決策屬性集.

為了避免混淆，不妨用(·)*A與(·)*D表示算子(·)*作用于不同的形式背景(U,A,I)和(U,D,J).

定義6[37].對(duì)于(U,A,I,D,J)的條件屬性子集E?A和決策屬性子集F?D.若E*A?F*D，則稱E→F為決策蘊(yùn)涵，其中E為前件，F(xiàn)為結(jié)論.

2 多粒度標(biāo)記形式背景及其語義解釋

盡管文獻(xiàn)[34]已給出多粒度標(biāo)記形式背景的概念，但目前尚未就該概念進(jìn)行語義解釋，所以理解起來較為晦澀.為此，本節(jié)嘗試從非交并集、非交融合屬性、非交融合形式背景等多個(gè)角度對(duì)多粒度標(biāo)記形式背景的語義作出解釋，并結(jié)合一個(gè)實(shí)例輔助理解，便于第3節(jié)進(jìn)一步引入介粒度標(biāo)記形式背景并闡明其研究意義做好鋪墊.

首先，介紹形式背景的反向尺度化方法，其核心思想是將(U,A,I)的若干布爾屬性視作a∈C的取值，從而產(chǎn)生(U,C)[34].下面介紹形式背景的m可反向尺度化問題.

定義7[34].如果一個(gè)形式背景(U,A,I)經(jīng)過反向尺度化得到具有m個(gè)屬性的(U,C)，那么稱其是m可反向尺度化的.

注意，是否能夠反向尺度化與形式背景(U,A,I)的屬性分塊密切相關(guān)，即到底把(U,A,I)的哪幾個(gè)屬性視作(U,C)中某一屬性的取值，直接關(guān)系到(U,A,I)能否成功反向尺度化到(U,C).

下面通過非交并集討論屬性和數(shù)據(jù)集的非交融合問題.雖然與文獻(xiàn)[34]借助于布爾向量的敘述方式類似，但是非交并集的語義更加簡潔直觀.

為了方便，記Tc為與參數(shù)c相關(guān)的一個(gè)指標(biāo)集.

定義9.給定形式背景(U,Ai,Ii)和(U,Aj,Ij)，c∈Aj，若存在br∈Ai(r∈Tc)滿足

(7)

那么稱c可由{br|r∈Tc}非交融合得到.

非交融合的語義可解釋為將形式背景不相交的幾列合并產(chǎn)生新的一列.顯然，通過該合并方式可以由一個(gè)形式背景產(chǎn)生另一個(gè)形式背景.

定義10.給定形式背景(U,Ai,Ii)和(U,Aj,Ij)，若Aj的每一個(gè)屬性c均可由Ai的若干屬性{br|r∈Tc}通過非交融合得到，且

(8)

那么稱(U,Aj,Ij)可由(U,Ai,Ii)非交融合得到，簡記為(U,Ai,Ii)(U,Aj,Ij).

不難發(fā)現(xiàn)，由(U,Ai,Ii)出發(fā)，可以產(chǎn)生一系列非交融合形式背景(U,Aj,Ij)(j∈T，T是指標(biāo)集).換言之，非交融合形式背景(U,Aj,Ij)的具體表現(xiàn)形式完全取決于非交融合方法所采取的特定融合模式.另外，(U,Ai,Ii)(U,Aj,Ij)也從側(cè)面表明(U,Aj,Ij)的粒度標(biāo)記值比(U,Ai,Ii)的更粗.也就是，原來分開細(xì)化各自表述的內(nèi)容，被合并后使用更粗的標(biāo)記值進(jìn)行統(tǒng)一描述.注意，在此過程中原來可以區(qū)分的內(nèi)容，現(xiàn)在可能變得無法區(qū)分.

定義11[34].設(shè)形式背景(U,Ak,Ik)(k=1,2,…,p)均m可反向尺度化，不妨令每個(gè)屬性集Ak都可拆分為兩兩不相交的非空子集序列Ak1,Ak2,…,Akm，且每個(gè)屬性塊Akj所擁有的對(duì)象集構(gòu)成U的劃分.若對(duì)于1≤s

(U,Asj,Isj)(U,Atj,Itj),j=1,2,…,m,

(9)

容易驗(yàn)證，多粒度標(biāo)記形式背景的屬性塊Ak1,Ak2,…,Akm(k=1,2,…,p)一共有p×m個(gè)，每個(gè)屬性塊均描述了一個(gè)完整的屬性特征(相當(dāng)于經(jīng)典信息系統(tǒng)的某一屬性)，它們通過固定變量k的方式成批鑲嵌于單粒度標(biāo)記形式背景(U,Ak,Ik)中(即每個(gè)單粒度標(biāo)記形式背景均可固定m個(gè)屬性塊)，但是這種表示方式很可能導(dǎo)致后續(xù)相關(guān)研究以單粒度標(biāo)記形式背景(U,Ak,Ik)(k=1,2,…,p)為最小單位.實(shí)際上，這極大限制了數(shù)據(jù)的知識(shí)發(fā)現(xiàn)進(jìn)一步延伸到更深層次，第3節(jié)將會(huì)給出詳細(xì)解釋.

例1.表1是一個(gè)形式背景(U,A1,I1)，其中對(duì)象集U={u1,u2,u3,u4,u5,u6,u7}代表7個(gè)時(shí)裝模特，屬性集A1={a1,a2,a3,a4,a5,a6,a7,a8}代表時(shí)裝模特走秀時(shí)可能的著裝搭配，具體語義是a1為黑點(diǎn)狀裙子，a2為黑條紋裙子，a3為藍(lán)點(diǎn)狀裙子，a4為藍(lán)條紋裙子，a5為白點(diǎn)狀上衣，a6為白條紋上衣，a7為紅點(diǎn)狀上衣，a8為紅條紋上衣.表2是另一個(gè)形式背景(U,A2,I2)，它的對(duì)象集與表1完全相同，但屬性集不同，A2={b1,b2,b3,b4,b5,b6}，具體語義是b1為黑裙子，b2為藍(lán)裙子，b3為白點(diǎn)狀上衣，b4為白條紋上衣，b5為紅點(diǎn)狀上衣，b6為紅條紋上衣.表3也是一個(gè)形式背景(U,A3,I3)，它的對(duì)象集也與表1完全相同，但屬性集不同，A3={c1,c2,c3,c4}，具體語義是c1為黑裙子，c2為藍(lán)裙子，c3為白上衣，c4為紅上衣.

Table 1 The Formal Context (U,A1,I1)表1 形式背景(U,A1,I1)

Table 2 The Formal Context (U,A2,I2)表2 形式背景(U,A2,I2)

Table 3 The Formal Context (U,A3,I3)表3 形式背景(U,A3,I3)

下面根據(jù)定義11判斷表1、表2和表3的數(shù)據(jù)能否聯(lián)合產(chǎn)生多粒度標(biāo)記背景.依據(jù)表1、表2可得：

令A(yù)11={a1,a2,a3,a4}，A12={a5,a6,a7,a8}，A21={b1,b2}，A22={b3,b4,b5,b6}，那么(U,A21,I21)可由(U,A11,I11)通過非交融合得到，且(U,A22,I22)可由(U,A12,I12)通過非交融合得到.也就是，(U,A11,I11)(U,A21,I21)和(U,A12,I12)(U,A22,I22)均成立.

類似地，依據(jù)表2、表3可得：

令A(yù)31={c1,c2}，A32={c3,c4}，那么(U,A31,I31)可由(U,A21,I21)通過非交融合得到，且(U,A32,I32)可由(U,A22,I22)通過非交融合得到.也就是，(U,A21,I21)(U,A31,I31)和(U,A22,I22)(U,A32,I32)均成立.

綜上可知，表1、表2和表3的數(shù)據(jù)能夠聯(lián)合產(chǎn)生多粒度標(biāo)記背景.此外，不難發(fā)現(xiàn)，屬性塊A11，A12，A21，A22，A31，A32均描述了一個(gè)完整的屬性特征.比如，A31描述了褲子的特征，A32描述了上衣的特征.

3 介粒度標(biāo)記形式背景

第2節(jié)給出了多粒度標(biāo)記形式背景的語義解釋，它可以由p個(gè)單粒度標(biāo)記形式背景(U,A1,I1),(U,A2,I2),…,(U,Ap,Ip)組成.文獻(xiàn)[34]建議研究這些單粒度標(biāo)記形式背景的知識(shí)發(fā)現(xiàn)、表示與處理問題，以及由(U,As,Is)到(U,At,It)(1≤s

定義12.對(duì)于形式背景(U,Ak,Ik)(k=1,2,…,p)構(gòu)成的多粒度標(biāo)記形式背景S，設(shè)每個(gè)屬性集Ak均可拆分為兩兩不相交的非空子集序列Ak1,Ak2,…,Akm，且每個(gè)屬性塊Akj所擁有的對(duì)象集構(gòu)成U的劃分，稱(U,Ameso,Imeso)為介粒度標(biāo)記形式背景，其中屬性集Ameso由元素Ap11,Ap22,…,Apmm構(gòu)成，下標(biāo)滿足pj∈{1,2,…,p}(j=1,2,…,m).

為了敘述方便，記S的所有介粒度標(biāo)記形式背景組成的集合為δ(S).

根據(jù)定義12可知，介粒度標(biāo)記形式背景的屬性塊允許來自各個(gè)單粒度標(biāo)記形式背景.某種程度上，它也可以看作是屬性粒度標(biāo)記值重組產(chǎn)生的新數(shù)據(jù)結(jié)構(gòu).

性質(zhì)2.設(shè)(U,Ak,Ik)是S的某一單粒度標(biāo)記形式背景，則(U,Ak,Ik)∈δ(S).

證明. 注意到(U,Ameso,Imeso)∈δ(S)的屬性集Ameso由元素Ap11,Ap22,…,Apmm構(gòu)成，其中下標(biāo)滿足pj∈{1,2,…,p}(j=1,2,…,m).特殊地，令

p1=p2=…=pm=k(k∈{1,2,…,p}),

則(U,Ameso,Imeso)退化為形式背景(U,Ak,Ik).也就是，(U,Ak,Ik)∈δ(S).

證畢.

為了敘述方便，本文用|·|表示集合的基數(shù).

性質(zhì)3.|δ(S)|=pm.

證明. 注意到多粒度標(biāo)記形式背景S的屬性塊Ak1,Ak2,…,Akm(k=1,2,…,p)一共有p×m個(gè).對(duì)于形成介粒度標(biāo)記形式背景的屬性粒度標(biāo)記值重組問題，它實(shí)際上相當(dāng)于m個(gè)填充位置，每個(gè)位置均有p種可能的填充方式的情形，故一共有pm種填充結(jié)果，所以介粒度標(biāo)記形式背景的個(gè)數(shù)為pm.

證畢.

注意，與多粒度標(biāo)記信息系統(tǒng)中組合粒度標(biāo)記方法的語境略有不同[25]，多粒度標(biāo)記形式背景的屬性粒度個(gè)數(shù)是相同的(通過單粒度標(biāo)記形式背景予以表示)，原因是現(xiàn)實(shí)中數(shù)據(jù)采集批次一般認(rèn)為是相同的(當(dāng)然，相鄰2個(gè)單粒度標(biāo)記形式背景的部分屬性粒度標(biāo)記值允許一樣).實(shí)際上，即便屬性粒度個(gè)數(shù)不同，也可以通過復(fù)制粒度標(biāo)記值的方式將其視作屬性粒度個(gè)數(shù)相同的情形.此外，需要指出的是，本文將屬性粒度標(biāo)記值進(jìn)行重組得到的數(shù)據(jù)結(jié)構(gòu)命名為介粒度標(biāo)記形式背景，其原因是介粒度標(biāo)記形式背景的屬性集Ameso由元素Ap11,Ap22,…,Apmm構(gòu)成，縱向來看它的粒度標(biāo)記層恰好介于min{p1,p2,…,pm}和max{p1,p2,…,pm}之間，這對(duì)理解介粒度標(biāo)記形式背景的粒度標(biāo)記層所處的大致范圍是有益的.

例2.以表1、表2、表3構(gòu)成的多粒度標(biāo)記形式背景S為例.根據(jù)定義12可知，表4是一個(gè)介粒度標(biāo)記形式背景(U,Ameso,Imeso)，它的屬性粒度標(biāo)記值來源于表1的第1個(gè)屬性塊和表3的第2個(gè)屬性塊.顯然，它不屬于原始數(shù)據(jù)的任一單粒度標(biāo)記形式背景.不難發(fā)現(xiàn)，(U,Ameso,Imeso)的粒度標(biāo)記層介于第1個(gè)粒度標(biāo)記和第3個(gè)粒度標(biāo)記之間.

不難看出，介粒度標(biāo)記思想的引入使得多粒度標(biāo)記形式背景的數(shù)據(jù)分析不再局限于各個(gè)單粒度標(biāo)記形式背景，還包括原始的單粒度標(biāo)記形式背景聯(lián)合誘導(dǎo)出的數(shù)據(jù)結(jié)構(gòu).根據(jù)性質(zhì)3，新誘導(dǎo)數(shù)據(jù)結(jié)構(gòu)的規(guī)模遠(yuǎn)遠(yuǎn)大于原始的單粒度標(biāo)記形式背景，這極大拓寬了多粒度標(biāo)記形式背景進(jìn)行知識(shí)發(fā)現(xiàn)的層度和廣度.

Table 4 The Meso-granularity Labeled Formal Context(U,Ameso,Imeso)表4 介粒度標(biāo)記形式背景(U,Ameso,Imeso)

4 介粒度標(biāo)記形式背景的數(shù)據(jù)結(jié)構(gòu)

由性質(zhì)3可知，S的介粒度標(biāo)記形式背景的個(gè)數(shù)眾多，所以捋清它們之間的數(shù)據(jù)結(jié)構(gòu)關(guān)系對(duì)于繼續(xù)討論S的多層次知識(shí)發(fā)現(xiàn)是必要的.為此，下面給出介粒度標(biāo)記形式背景的泛化與特化，以揭示其數(shù)據(jù)結(jié)構(gòu)形成一個(gè)完備格.為了書寫方便，本節(jié)中的S均指

(10)

不難發(fā)現(xiàn)，介粒度標(biāo)記形式背景的泛化與特化，實(shí)際上刻畫的是屬性粒度標(biāo)記派生出的粗細(xì)關(guān)系，這種粒度粗細(xì)關(guān)系有可能不是數(shù)據(jù)采集或表示所自然形成的，而是通過屬性標(biāo)記值重構(gòu)產(chǎn)生新的數(shù)據(jù)結(jié)構(gòu)的方式，即人為誘導(dǎo)出的一種數(shù)據(jù)結(jié)構(gòu)的粗細(xì)關(guān)系.在屬性粒度標(biāo)記值重構(gòu)的過程中，它相當(dāng)于打破了原有或故有的粒度標(biāo)記層，從而有利于多層次知識(shí)發(fā)現(xiàn).

例3.以表1、表2、表3構(gòu)成的多粒度標(biāo)記形式背景S為例.對(duì)于表4的介粒度標(biāo)記形式背景(U,Ameso,Imeso)∈δ(S)，表1的形式背景(U,A1,I1)是(U,Ameso,Imeso)的一個(gè)特化，而表3的形式背景(U,A3,I3)則是(U,Ameso,Imeso)的一個(gè)泛化.

性質(zhì)4.δ(S)在關(guān)系≤下形成一個(gè)完備格.

αj=max{λj,μj},j=1,2,…,m,

βj=min{λj,μj},j=1,2,…,m.

那么

λj≤γj,μj≤γj,

證畢.

實(shí)際上，完備格結(jié)構(gòu)數(shù)據(jù)對(duì)于進(jìn)一步考慮最優(yōu)介粒度標(biāo)記形式背景的選擇(滿足用戶特定需求的前提下)是非常實(shí)用的.比如，可以利用格結(jié)構(gòu)關(guān)系，通過漸進(jìn)優(yōu)化的方式逐步搜索最優(yōu)介粒度標(biāo)記形式背景.另一方面，由于搜索空間的規(guī)模較大，如何實(shí)現(xiàn)最優(yōu)介粒度標(biāo)記形式背景的有效搜索也是一個(gè)重要的研究課題.

最后，需要指出的是，從一個(gè)介粒度標(biāo)記形式背景泛化到另一個(gè)介粒度標(biāo)記形式背景，信息通常會(huì)出現(xiàn)損失；反之，從一個(gè)介粒度標(biāo)記形式背景特化到另一個(gè)介粒度標(biāo)記形式背景，信息會(huì)增加，當(dāng)然該過程必須借助于額外信息才能完成.這是由于泛化過程是不可逆的，而特化過程是可逆的.因此，一個(gè)有趣的問題是，在介粒度標(biāo)記形式背景的泛化過程中，如何刻畫或度量信息的損失程度非常關(guān)鍵，這是傳統(tǒng)粗糙集領(lǐng)域中尚未考慮的問題.

5 帶決策信息的介粒度知識(shí)發(fā)現(xiàn)方法

(11)

文獻(xiàn)[34]針對(duì)Q討論了知識(shí)發(fā)現(xiàn)問題.然而，現(xiàn)有的知識(shí)發(fā)現(xiàn)方法僅限于原始單粒度標(biāo)記數(shù)據(jù)本身或相互之間的推理關(guān)系，不涉及屬性粒度標(biāo)記值重構(gòu)(即介粒度標(biāo)記數(shù)據(jù))的情形.換言之，現(xiàn)有方法僅僅考慮(U,Ak,Ik,D,J)(k=1,2,…,p)的知識(shí)發(fā)現(xiàn).如前所述，單粒度標(biāo)記數(shù)據(jù)或相互之間的知識(shí)發(fā)現(xiàn)的研究范圍過于狹窄，不能較好地滿足現(xiàn)實(shí)中復(fù)雜問題求解的需要，因?yàn)閺?fù)雜問題求解通常會(huì)涉及屬性粒度標(biāo)記值重構(gòu)的數(shù)據(jù).

例4.表5是一個(gè)形式背景(U,D,J)，其中U={u1,u2,u3,u4,u5,u6,u7}代表7個(gè)時(shí)裝模特，D={e,f}代表時(shí)裝模特走秀時(shí)的著裝效果，具體語義是e代表“裙子和上衣搭配效果不滿意”，f代表“裙子和上衣搭配效果滿意”.

Table 5 The Formal Context (U,D,J)表5 形式背景(U,D,J)

聯(lián)合表1、表2、表3和表5的數(shù)據(jù)可得：

容易驗(yàn)證，Q是多粒度標(biāo)記決策形式背景.

然而，根據(jù)現(xiàn)有的知識(shí)發(fā)現(xiàn)方法，只能從表1和表5、表2和表5，以及表3和表5組成的3個(gè)單粒度標(biāo)記決策形式背景中挖掘知識(shí)，并不能從介粒度標(biāo)記形式背景(如表4)和表5組成的決策形式背景中挖掘知識(shí).

為了討論該問題，下面引入介粒度標(biāo)記決策形式背景的概念.

定義15.對(duì)于多粒度標(biāo)記決策形式背景Q，若

(12)

則稱(U,Ameso,Imeso,D,J)是Q的介粒度標(biāo)記決策形式背景，記為(U,Ameso,Imeso,D,J)∈δ(Q).

如第3節(jié)所述，如果(U,Ameso,Imeso)不屬于任一原始的單粒度標(biāo)記形式背景，那么(U,Ameso,Imeso,D,J)的決策蘊(yùn)涵E→F(E?Ameso，F(xiàn)?D)通過現(xiàn)有的知識(shí)發(fā)現(xiàn)方法是無法直接獲得的.但是，仍然可以通過原始的單粒度標(biāo)記形式背景間接驗(yàn)證E→F是否成立，具體見算法1.

算法1.單粒度標(biāo)記方法判斷決策蘊(yùn)涵.

輸入：多粒度標(biāo)記決策形式背景Q，Qmeso=(U,Ameso,Imeso,D,J)∈δ(Q)，E?Ameso，F(xiàn)?D.

輸出：E→F是否為Qmeso的決策蘊(yùn)涵.

① 對(duì)于任意k∈{1,2,…,p}，j∈{1,2,…,m}，計(jì)算Ekj=E∩Akj.

④ 若ε?F*D，則E→F是Qmeso的決策蘊(yùn)涵；否則，E→F不是Qmeso的決策蘊(yùn)涵.

容易驗(yàn)證，上述單粒度標(biāo)記方法判斷決策蘊(yùn)涵的時(shí)間復(fù)雜度為

需要指出的是，根據(jù)定義6，也可以采用直接的方法在Qmeso=(U,Ameso,Imeso,D,J)中驗(yàn)證E→F是否為Qmeso的決策蘊(yùn)涵，其時(shí)間復(fù)雜度為

因此，介粒度標(biāo)記方法給決策蘊(yùn)涵挖掘帶來了計(jì)算上的便利，至少降低了算法的計(jì)算復(fù)雜性.第6節(jié)將通過數(shù)值實(shí)驗(yàn)進(jìn)一步評(píng)估節(jié)省計(jì)算量的實(shí)際情況.

至此，針對(duì)介粒度標(biāo)記數(shù)據(jù)，已給出直接和間接2種方法判斷決策蘊(yùn)涵.實(shí)際上，這里的“直接”與“間接”都是基于決策蘊(yùn)涵E→F是否在(U,Ameso,Imeso,D,J)∈δ(Q)中進(jìn)行驗(yàn)證做出的區(qū)分.因此，下文中統(tǒng)稱它們?yōu)橹苯优袛喾椒?，以區(qū)別于即將討論的推理演化間接方法.所謂推理演化是指隨著介粒度標(biāo)記形式背景的泛化與特化，借助于知識(shí)發(fā)現(xiàn)的演變規(guī)律間接判斷決策蘊(yùn)涵.

需要強(qiáng)調(diào)的是，與定義10不同，這里的Eμ是通過雙射ρλμ作用于Eλ得到，并不是完全合并更細(xì)的非交列產(chǎn)生.換言之，原像只是合并產(chǎn)生像的眾多非交列之一(非交列唯一的情況除外).

為了討論方便，記(U,Ameso,Imeso,D,J)的所有決策蘊(yùn)涵為Δ(U,Ameso,Imeso,D,J).

證畢.

(13)

那么

證畢.

最后，需要指出的是，決策蘊(yùn)涵只是形式概念分析進(jìn)行知識(shí)發(fā)現(xiàn)的一種方式而已.除此之外，還有決策規(guī)則[38]、推理依賴[39]、關(guān)聯(lián)規(guī)則[40]等.因此，基于這些規(guī)則深入研究隨著介粒度標(biāo)記數(shù)據(jù)的泛化與特化其知識(shí)推理的內(nèi)在機(jī)理也是有意義的.

6 實(shí)驗(yàn)與結(jié)果

本節(jié)通過數(shù)值實(shí)驗(yàn)評(píng)估算法1、介粒度標(biāo)記方法、性質(zhì)5和性質(zhì)6的性能表現(xiàn)，以表明介粒度標(biāo)記方法的有效性與優(yōu)勢(shì)所在.

6.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)使用的具體配置如下：CPU為Intel Core i3-2120 3.30 GHz,4.00 GB內(nèi)存；JDK為jdk1.8.0_20,Eclipse使用32位的eclipse-4.2.實(shí)驗(yàn)選取的7個(gè)數(shù)據(jù)集均來源于UCI數(shù)據(jù)庫(1)http://archive.ics.uci.edu/ml/的真實(shí)數(shù)據(jù)，即zoo,BC(breast cancer),monks2,wisconsin,SHD(semeion handwritten digit),mushroom,letter數(shù)據(jù)集，詳見表6所示:

Table 6 The Data Sets for Experiments表6 實(shí)驗(yàn)數(shù)據(jù)集

在此基礎(chǔ)上，將表6中的原始數(shù)據(jù)集通過尺度變換(scaling)[13]轉(zhuǎn)化為標(biāo)準(zhǔn)形式背景格式的數(shù)據(jù)集，預(yù)處理后的屬性情況如表6最后一列所示.類似于粗糙集理論中的慣用做法[30]，這里也選擇合并相鄰布爾屬性的方式產(chǎn)生多粒度標(biāo)記形式背景.為了敘述方便，本文將用于實(shí)驗(yàn)的7個(gè)數(shù)據(jù)集均處理成4個(gè)粒度標(biāo)記層.具體如下：在尺度變換后得到的原始形式背景(記為第1粒度標(biāo)記層)的基礎(chǔ)上，依次通過屬性距d1=2，d2=5，d3=10分別產(chǎn)生第2粒度標(biāo)記層、第3粒度標(biāo)記層和第4粒度標(biāo)記層.比如，屬性距d1=2表示通過合并相鄰2個(gè)布爾屬性的方式產(chǎn)生下一層粒度標(biāo)記，其他屬性距的語義可類似進(jìn)行解釋.注意，實(shí)驗(yàn)涉及的7個(gè)數(shù)據(jù)集均將樣本類別標(biāo)簽信息視作決策屬性，從而得到實(shí)驗(yàn)所需的標(biāo)準(zhǔn)數(shù)據(jù)集.在不引起混淆時(shí)，預(yù)處理后產(chǎn)生的標(biāo)準(zhǔn)數(shù)據(jù)集依舊沿用原始數(shù)據(jù)集的命名.

6.2 實(shí)驗(yàn)結(jié)果

首先，根據(jù)定義6、定義15和算法1，對(duì)比了單粒度標(biāo)記方法(single-granularity labeled method, SLM)與介粒度標(biāo)記方法(meso-granularity labeled method, MLM)的運(yùn)行時(shí)間，以及它們?cè)诓煌瑪?shù)據(jù)集上的表現(xiàn).表7給出了在其他參數(shù)一定的情況下，決策蘊(yùn)涵的前件屬性集E與數(shù)據(jù)集類型對(duì)2種粒度標(biāo)記方法產(chǎn)生的實(shí)際影響.

Table 7 Comparison of Meso-granularity andSingle-granularity Methods表7 介粒度標(biāo)記方法與單粒度標(biāo)記方法的對(duì)比 ms

從表7不難看出: 1)對(duì)于決策蘊(yùn)涵挖掘,在不同的前件屬性集E下，介粒度標(biāo)記方法都比單粒度標(biāo)記方法更加有效；2)2種粒度標(biāo)記方法的運(yùn)行時(shí)間都隨著數(shù)據(jù)集規(guī)模的增大而變大；3)2種粒度標(biāo)記方法的運(yùn)行時(shí)間都對(duì)前件屬性集E的變化表現(xiàn)不太敏感，這很可能是由于實(shí)驗(yàn)中E的元素個(gè)數(shù)相對(duì)于屬性全集遠(yuǎn)遠(yuǎn)偏小的緣故.

其次，由性質(zhì)5和性質(zhì)6給出的2種決策蘊(yùn)涵推理方法(decision implication inference method, DIIM)，可以間接進(jìn)行跨粒度標(biāo)記數(shù)據(jù)之間的決策蘊(yùn)涵推理.為了區(qū)分性質(zhì)5和性質(zhì)6給出的決策蘊(yùn)涵推理方法，將它們分別記為DIIM5和DIIM6.表8和表9給出了前件屬性集E的元素個(gè)數(shù)為2(盡管E的元素個(gè)數(shù)與表7中的完全相同，但由于具體賦值不同，所以最終的實(shí)驗(yàn)結(jié)果基本不相同)，決策蘊(yùn)涵推理方法的間接驗(yàn)證與單粒度標(biāo)記方法和介粒度

Table 8Comparison of the First Decision Implication

Inference Method and Recalculation

表8 第1種決策蘊(yùn)涵推理方法與重新計(jì)算的對(duì)比

ms

Table 9Comparison of the Second Decision Implication

Inference Method and Recalculation

表9 第2種決策蘊(yùn)涵推理方法與重新計(jì)算的對(duì)比

標(biāo)記方法重新計(jì)算的對(duì)比結(jié)果.從表8和表9不難看出，決策蘊(yùn)涵推理方法的間接驗(yàn)證要比2種重新計(jì)算的方法更加高效.

最后，分析前件屬性集E和數(shù)據(jù)集類型對(duì)決策蘊(yùn)涵推理方法(這里僅以DIIM5為例)的影響.從圖1與圖2可以看出，隨著數(shù)據(jù)集規(guī)模的增大進(jìn)行決策蘊(yùn)涵推理所需時(shí)間變長.除此之外，還顯示出前件屬性集E與決策蘊(yùn)涵推理時(shí)間呈現(xiàn)正相關(guān),其原因是前件屬性集E越大，則其進(jìn)行映射所需搜尋的范圍也會(huì)越廣.

Fig. 1 The impact of data sets and attribute set E on DIIM5圖1 數(shù)據(jù)集與屬性集E對(duì)DIIM5的影響

Fig. 2 The impact of attribute set E and data sets on DIIM5圖2 屬性集E與數(shù)據(jù)集對(duì)DIIM5的影響

需要指出的是，前件屬性集E和數(shù)據(jù)集類型對(duì)DIIM6的影響與DIIM5呈現(xiàn)的趨勢(shì)基本一致，在此不再贅述.

注意，本文的實(shí)驗(yàn)都是針對(duì)判斷一條決策蘊(yùn)涵評(píng)估其計(jì)算代價(jià)，總的運(yùn)行時(shí)間均較小，只是通過時(shí)間的相對(duì)大小表明介粒度標(biāo)記方法的有效性.現(xiàn)實(shí)中，一個(gè)數(shù)據(jù)集的決策蘊(yùn)涵的總數(shù)是相當(dāng)龐大的，因?yàn)闆Q策蘊(yùn)涵的前件屬性集E來源于屬性全集的任一子集，所以它的個(gè)數(shù)與屬性全集的冪集基本相當(dāng)，均屬于指數(shù)級(jí)別.換言之，盡管本文的實(shí)驗(yàn)都是針對(duì)判斷一條決策蘊(yùn)涵評(píng)估其計(jì)算代價(jià)，本文的方法與現(xiàn)有方法的運(yùn)行結(jié)果貌似差異不大，但是一旦把決策蘊(yùn)涵的前件屬性集E的規(guī)?？紤]進(jìn)去，那么新舊方法的差異將會(huì)是顯著的.

7 總 結(jié)

本文從實(shí)際應(yīng)用出發(fā)，提出介粒度標(biāo)記形式背景的概念，以表明重組屬性粒度標(biāo)記值呈現(xiàn)更多數(shù)據(jù)結(jié)構(gòu)思想的重要性.盡管已存在類似的研究倡議[25]，但本文仍有一些值得歸納總結(jié)的新意：1)多粒度標(biāo)記數(shù)據(jù)的粒度標(biāo)記個(gè)數(shù)兩兩相同是有現(xiàn)實(shí)背景意義的，因?yàn)楹芏鄶?shù)據(jù)的采集都是成批進(jìn)行的(假設(shè)每批數(shù)據(jù)均構(gòu)成一類單粒度標(biāo)記)；2)即使特殊時(shí)多粒度標(biāo)記數(shù)據(jù)形成的粒度標(biāo)記個(gè)數(shù)出現(xiàn)不同的情形，也可以通過擴(kuò)充的方式使得粒度標(biāo)記個(gè)數(shù)兩兩相同(允許部分屬性的粒度標(biāo)記值重復(fù)出現(xiàn)即可)；3)實(shí)際上，粒度標(biāo)記個(gè)數(shù)相同與否不是該問題的關(guān)鍵所在，數(shù)據(jù)分析與處理的實(shí)際需求才是促使人們采用介粒度標(biāo)記方法的重要因素；4)介粒度標(biāo)記形式背景進(jìn)行泛化時(shí)會(huì)導(dǎo)致信息出現(xiàn)損失，因?yàn)樵撨^程是不可逆的.

本文在經(jīng)典多粒度形式概念分析的基礎(chǔ)上，提出介粒度標(biāo)記方法以拓展現(xiàn)有的研究思路，使得數(shù)據(jù)分析與處理不再局限于數(shù)據(jù)采集或表示形成的自然粗細(xì)粒度標(biāo)記關(guān)系.換言之，自然形成的粗細(xì)粒度標(biāo)記數(shù)據(jù)結(jié)構(gòu)，是數(shù)據(jù)存儲(chǔ)表示的一種原始狀態(tài)，如果要達(dá)到多層次知識(shí)發(fā)現(xiàn)的目的，那么充分利用各個(gè)單粒度標(biāo)記數(shù)據(jù)相互交叉融合誘導(dǎo)出的介粒度標(biāo)記數(shù)據(jù)是非常必要的.

除了與經(jīng)典粗細(xì)粒度標(biāo)記形式背景有類似的研究問題之外，介粒度標(biāo)記方法有待繼續(xù)探討的課題如下：1)當(dāng)用戶提出具體的粒度標(biāo)記層約束時(shí)，如何在滿足用戶需求的情況下，選擇最優(yōu)介粒度標(biāo)記形式背景；2)由于選擇最優(yōu)介粒度標(biāo)記形式背景的搜索空間龐大，所以探討節(jié)省搜索空間的近似智能算法也是有必要的；3)介粒度標(biāo)記數(shù)據(jù)在泛化過程中存在信息損失，如何度量其大小是一個(gè)重要的課題；4)介粒度標(biāo)記方法帶來諸多優(yōu)勢(shì)的同時(shí)，如何避免不足之處以充分發(fā)揮其積極作用？比如，精度和效率與計(jì)算代價(jià)之間的綜合權(quán)衡關(guān)系.

致謝感謝昆明理工大學(xué)閆夢(mèng)宇博士對(duì)本文初稿提出的意見和建議！