張曉燕,王佳一

(西南大學(xué)人工智能學(xué)院,重慶 400715)

1 引言

形式概念分析[1]是一種以形式背景為研究對(duì)象的理論,是一種以概念格相關(guān)理論為核心概念的數(shù)學(xué)工具,常用于進(jìn)行數(shù)據(jù)分析。概念格展示了概念之間的偏序關(guān)系,刻畫對(duì)象和屬性的內(nèi)在關(guān)系[2]。然而,基本的概念格因其只研究了“共同(被)具有”關(guān)系的問題,忽略了“共同不(被)具有”關(guān)系的問題而存在局限性[3,4],且這種局限性也導(dǎo)致該理論在實(shí)際應(yīng)用中受到限制[5]。

2014年,Qi[6]提出了新的理論以彌補(bǔ)經(jīng)典概念格理論的局限性,即三支概念分析。三支概念分析提出了對(duì)象誘導(dǎo)的三支概念格與屬性誘導(dǎo)的三支概念格,2種三支概念格均同時(shí)研究了“共同(被)具有”和“共同不(被)具有”的問題。其所獲得的三支概念格相較于以往經(jīng)典概念格研究范圍更加全面,也會(huì)使概念識(shí)別在實(shí)際應(yīng)用過程中更加精確。

在三支概念正式提出后,許多學(xué)者對(duì)此進(jìn)行了擴(kuò)展和深入研究。Qian等[7]利用形式背景的疊置與并置,提出了三支概念格的構(gòu)造方法,仿照對(duì)象誘導(dǎo)概念格與屬性誘導(dǎo)概念格提出了對(duì)象誘導(dǎo)的三支面向?qū)ο蟾拍罡窈蛯傩哉T導(dǎo)的三支面向?qū)傩愿拍罡竦亩x,并分析4種概念之間的異同。蘇新等[8]進(jìn)行了基于對(duì)象和基于屬性的三支概念格合并方法比較。Wei等[9]立足于三支概念格,在三支協(xié)調(diào)的意義下研究了決策背景的規(guī)則獲取問題,并與強(qiáng)協(xié)調(diào)決策背景所獲得的一般決策規(guī)則進(jìn)行了詳細(xì)的比較研究。

除對(duì)三支概念本身的擴(kuò)展和推廣,學(xué)科交叉融合研究也為豐富三支概念體系做出了極大的貢獻(xiàn)。Li等[10]將多粒度與三支概念融合,提出了基于多粒度的三支認(rèn)知概念學(xué)習(xí)。龍柄翰等[11]提出模糊三支概念分析,將模糊集理論與三支概念分析相結(jié)合,考慮模糊背景中“共同具有的程度”與“共同不具有的程度”2方面不確定的共性信息極大地提高了三支概念在生產(chǎn)力方面的意義。

多粒度研究方面,知識(shí)?；痆12]、屬性?；痆13,14]和屬性聚類[15]等概念的提出將多粒度與概念認(rèn)知聯(lián)系起來[16],為了緩解龐大的概念個(gè)數(shù),在約束寬松的情況下減少工作量提供了解決方案,并且為獲取數(shù)據(jù)的多層次概念知識(shí)表示與處理方法上提供了新的方法。多粒度方面的研究包括研究對(duì)象的粗化與細(xì)化,在屬性?；芯恐?其主要研究方向包括屬性的吸收,即粗化,以及屬性的分解,即細(xì)化。在屬性的粗化與細(xì)化之中,概念也會(huì)隨之轉(zhuǎn)化,可以獲得在不同粒度上的概念分析。Belohlavek等[17]提出了給予屬性?；男问礁拍罘治龇椒?該理論中進(jìn)行了屬性?；?生成不同粒度層次的形式背景的工具主要是粒度樹與剪枝。

在三支概念格背景下,對(duì)屬性?；难芯可星也蛔?且現(xiàn)在無法通過有效手段度量屬性?；?嚴(yán)重降低了概念區(qū)分與細(xì)化的速度,需要大量冗余的計(jì)算[18]。針對(duì)此種情況,本文提出以三支概念格為背景的屬性?；识攘糠椒?嘗試探討對(duì)解決此類問題的方法。

2 基礎(chǔ)知識(shí)

2.1 概念格

設(shè)有形式背景K=(G,M,I),其中,G為對(duì)象集,M為屬性集,I為G和M之間的二元關(guān)系。在經(jīng)典形式背景中,I的取值只有0或者1這2種可能。對(duì)于x∈G,m∈M,當(dāng)I(x,m)=1時(shí),表示對(duì)象x和屬性m存在關(guān)系I;當(dāng)I(x,m)=0時(shí),表示對(duì)象x和屬性m不存在關(guān)系I。

為研究對(duì)象子集和屬性子集之間的關(guān)系,對(duì)于X?G,A?M,現(xiàn)定義如下2個(gè)分別作用于屬性子集和對(duì)象子集的導(dǎo)出算子X*和A*:

X*={m:m∈M,?x∈X,I(x,m)=1}

A*={x:x∈G,?m∈A,I(x,m)=1}

特別地,當(dāng)對(duì)象子集或?qū)傩宰蛹袃H有一個(gè)元素時(shí),記{x}*為x*,記{m}*為m*。

設(shè)有形式背景K=(G,M,I),若對(duì)于X?G,A?M,有X*=A且A*=X,則(X,A)稱為一個(gè)形式概念,其中概念的外延為X,概念的內(nèi)涵為A。形式背景K=(G,M,I)下的所有形式概念的集合為L(K),L(K)即為概念格[20]。

本節(jié)內(nèi)容詳見文獻(xiàn)[2]中有關(guān)于概念格的理論敘述。

2.2 三支概念格

如果說概念格研究的是“共同具有”的關(guān)系,那么三支概念格就是同時(shí)研究“共同具有”和“共同不具有”2種關(guān)系。在應(yīng)用中,只研究單方面往往會(huì)使研究結(jié)果具有片面性,從而在利用概念尋找對(duì)象和屬性的過程中出現(xiàn)錯(cuò)誤,而從正反2方面研究則會(huì)使研究結(jié)果更加精準(zhǔn),提高尋找結(jié)果的正確率。

為了研究“共同不具有”的關(guān)系,在這里定義2.1節(jié)導(dǎo)出算子的負(fù)算子。對(duì)于子集X?G,A?M,有:

顯然,在負(fù)算子作用下,“共同不具有”這一關(guān)系可以被研究。但是,如果需要同時(shí)研究具有和不具有的關(guān)系,還需要定義一對(duì)算子。特別需要說明的一點(diǎn)是,單個(gè)對(duì)象子集在運(yùn)算后會(huì)得到2個(gè)屬性子集,即“共同具有的屬性”和“共同不具有的屬性”。同理,由于出發(fā)點(diǎn)不同,單個(gè)屬性子集在運(yùn)算后會(huì)得到2個(gè)對(duì)象子集,從而可以得出2種概念。

對(duì)于X?G和A,B?M:

若XO=(A,B)且(A,B)O=X,則(X,(A,B))為對(duì)象誘導(dǎo)的三支概念,簡稱OE概念,其中,X為OE概念的外延,(A,B)為OE概念的內(nèi)涵。

對(duì)于X,Y?G和A?M:

若AA=(X,Y)且(X,Y)A=A,則((X,Y),A)為屬性誘導(dǎo)的三支概念,簡稱AE概念,其中,(X,Y)為AE概念的外延,A為AE概念的內(nèi)涵[21]。

本節(jié)內(nèi)容詳見文獻(xiàn)[8]中有關(guān)三支概念格定義的敘述。

2.3 屬性粒化

屬性?；且环N由舊的屬性集構(gòu)建新的屬性集的方式,其構(gòu)建方法是根據(jù)不同屬性的內(nèi)在聯(lián)系,通過粒度樹與剪枝的構(gòu)造得到不同的屬性集。相對(duì)于純代數(shù)構(gòu)造方法,通過粒度樹這一工具的屬性粒化顯然要求屬性之間存在某種關(guān)聯(lián),至少是人為規(guī)定的聯(lián)系。

對(duì)于形式背景K=(G,M,I),任意屬性m∈M,屬性m的粒度樹Tm是滿足以下全部條件的含有根節(jié)點(diǎn)的樹:

該樹中的任意一個(gè)節(jié)點(diǎn)都代表一個(gè)屬性,且都有確定且唯一的名稱來標(biāo)記。樹的根節(jié)點(diǎn)為m。

對(duì)于每一個(gè)節(jié)點(diǎn),此處記為z,均有一對(duì)象集合z*∈G,該對(duì)象集由具有屬性z的集合構(gòu)成。

剪枝C是粒度樹Tm上滿足如下條件的節(jié)點(diǎn)集:對(duì)于每一個(gè)葉節(jié)點(diǎn)u而言,在從u到根節(jié)點(diǎn)m的路徑上存在唯一的節(jié)點(diǎn)存在于該剪枝。給定形式背景K=(G,M,I),如表1所示,其中,G={a,b,c,d,e}為對(duì)象集,M={Color, Black, Red, Blue, Light blue, Dark blue}為屬性集,I為G和M之間的二元關(guān)系。

Table 1 Formal background K=(G,M,I)

表1中基于屬性集的粒度樹如圖1所示。

Figure 1 Granularity tree corresponding to attribute set in table 1

{Red,Light blue,Dark blue}不是剪枝,因?yàn)槠涞礁?jié)點(diǎn)Color的路徑上還有Black這一子節(jié)點(diǎn)。{Blue,Red,Light blue,Dark blue}是剪枝。

對(duì)于X?G,A?MC,有:

X*C={m:m∈MC,?x∈X,IC(x,m)=1}

A*C={x:x∈G,?m∈A,IC(x,m)=1}

得到粒度樹后,可以通過從粒度樹上獲取不同的剪枝得到不同的粒度層次,有些粒度層次之間存在偏序關(guān)系,而有些粒度層次之間不存在偏序關(guān)系。本文將對(duì)這2種情況分別進(jìn)行討論。

本節(jié)內(nèi)容詳見文獻(xiàn)[15]中關(guān)于粒度樹、剪枝及屬性?；臄⑹?。

2.4 獲取概念格

引理1設(shè)K=(G,M,I)是一個(gè)形式背景,對(duì)于X,X0?G和A?M,下面性質(zhì)成立:

(2)若X*=A和X?A*,那么(A*,A)是一個(gè)概念。

引理1是Next Clousure算法的基礎(chǔ),利用此概念可以獲得所有概念,所有的概念組成概念格L(K)。Next Clousure算法如算法1所示。

算法1 Next Clousure算法輸入:形式背景K=(G,M,I)。輸出:全部概念集合C。步驟1 初始化C=?;重命名全部對(duì)象為1:i;步驟2 令C=C∪{?**,?*};/*為對(duì)象子集和屬性子集導(dǎo)出算子,**是*的二次運(yùn)算,即復(fù)合運(yùn)算*/D=sort(G,DESC);/*將對(duì)象集元素進(jìn)行分類并按降序排序*/步驟3 S=?*; while S≠?**do J=D-S; foreach i in Jdo F=(S∩{1,…,i-1}∪{i})*; T=F*; U=T∩{1,…,i-1}; if i∈T-S and S∩{1,…,i-1}=U then C=C∪{T,F}; S=T; break; endif endfor endwhile步驟4 return C

利用Next Clousure算法同樣可以得到反概念。反概念是相對(duì)概念而言的,反概念可以看作是原形式背景的補(bǔ)背景下的概念。對(duì)于一個(gè)形式背景,所有反概念組成該形式背景下的反概念格。

3 存在偏序關(guān)系的不同粒度層次

3.1 屬性粒化前后三支概念

屬性?；昂?形式概念背景中的屬性集也隨之進(jìn)行了粗細(xì)轉(zhuǎn)化,在由粗屬性集到細(xì)屬性集的轉(zhuǎn)化中,對(duì)于相同對(duì)象集,新屬性可能部分出現(xiàn)在與之對(duì)應(yīng)的屬性集中,也有可能全部不出現(xiàn)在對(duì)應(yīng)的屬性集中。

現(xiàn)實(shí)應(yīng)用中,屬性?；Ｓ糜诟泳_地定義概念。例如,在將“不同種類牛仔褲”進(jìn)行區(qū)分定義時(shí),某屬性可以由“藍(lán)色”到“深藍(lán)色”及“淺藍(lán)色”,再到具體色號(hào)層層細(xì)化,使定義更加細(xì)化。而在屬性?；纱值郊?xì)的過程中,隨著屬性集向更細(xì)的方向轉(zhuǎn)化,必定會(huì)有更多概念的形成。以下將對(duì)此結(jié)論進(jìn)行理論證明。

為了方便說明,對(duì)于剪枝后的形式背景KC=(G,MC,IC)形成的概念格記為L(KC)。對(duì)于概念格中的概念數(shù)量,由于概念格本質(zhì)上是集合,將其中元素的數(shù)目記為|L(KC)|。相似地,由這種概念格形成的面向?qū)ο笕Ц拍罡裼洖镺EL(KC),面向?qū)傩匀Ц拍罡裼洖锳EL(KC)。

定理1在屬性粒化的過程中,隨著屬性粒度層次的細(xì)化,屬性集中元素的增多,概念格中概念的數(shù)量不會(huì)減少。

證明在屬性粒化過程中,對(duì)于任意屬性分解過程a→{a1,a2,…,al},若該屬性分解導(dǎo)致概念格中元素減少,則為在原概念格中存在概念的內(nèi)涵B,a∈B的基礎(chǔ)上,新概念格中不存在概念的內(nèi)涵BC,令BC∩{a1,a2,…,al}≠?。

對(duì)于新屬性集中的元素?ap(1≤p≤l)∈{a1,a2,…,al},設(shè)A=(M∩MC)∪{ap},則因?yàn)?A*C)*C=A*C*C,且(A*C*C)*C=A*C*C*C=A*C,因此(A*C,A*C*C)是一個(gè)概念格,因?yàn)锳?A*C*C,所以ap∈A*C*C,則在新的概念格中存在概念內(nèi)涵A*C*C∩{a1,a2,…,al}≠?。以上假設(shè)不成立,即任意屬性分解均不會(huì)造成概念格中元素減少,原定理得證。

類似地,有如下定理:

定理2在屬性粒化的過程中,隨著屬性粒度層次的細(xì)化,屬性集中元素增多,面向?qū)ο笕Ц拍罡裰懈拍畹臄?shù)量不會(huì)減少。

定理3在屬性粒化的過程中,隨著屬性粒度層次的細(xì)化,屬性集中元素的增多,面向?qū)傩匀Ц拍罡裰懈拍畹臄?shù)量不會(huì)減少。

3.2 細(xì)化系數(shù)

為了研究屬性聚類對(duì)三支概念的影響,需要在同一對(duì)象集下,進(jìn)一步建立屬性聚類前后三支概念的聯(lián)系。對(duì)于屬性集M={m1,m2,…,m|M|},聚類后表示為MR={([m]R)1,([m]R)2,…,([m]R)k}(k≤|M|),其中,R為聚類關(guān)系,?1≤p,q≤k,且p≠q,根據(jù)等價(jià)類與集合的性質(zhì),([m]R)p∩([m]R)q=?。定義一般屬性聚類中的算子與負(fù)算子,對(duì)于X?G和A?MR:如果在定義事物的時(shí)候,選擇描述事物的關(guān)鍵詞越多,分類越細(xì)致,對(duì)于事物的定義就會(huì)越精確。相似地,概念格在不同的屬性層次移動(dòng),由粗到細(xì)的時(shí)候,概念也會(huì)由粗到細(xì),得到更加精確的概念。概念格中概念的數(shù)量也會(huì)隨之變化。根據(jù)定理1,較粗屬性層次對(duì)應(yīng)的概念格中的概念數(shù)量會(huì)大于或等于較細(xì)屬性層次對(duì)應(yīng)的概念格中概念的數(shù)量,因此可以通過比較層次移動(dòng)時(shí)概念格中概念數(shù)量的變化來比較屬性?；男Ч?。

定義1對(duì)于屬性?；瘜哟蜟1和C2,若存在偏序關(guān)系C1≤C2,即前者是后者的細(xì)化,在度量細(xì)化時(shí),定義細(xì)化系數(shù)eLC如式(1)所示:

(1)

細(xì)化系數(shù)eLC越大,表明新的屬性層次產(chǎn)生了越多的新概念,此次屬性?；接行?。

相似地,根據(jù)定理2和定理3,可以定義出與以上細(xì)化系數(shù)相同的面向?qū)ο蠹?xì)化系數(shù)和面向?qū)傩约?xì)化系數(shù)。

定義2對(duì)于屬性粒化層次C1和C2,若存在偏序關(guān)系C1≤C2,即前者是后者的細(xì)化,在度量細(xì)化時(shí),定義面向?qū)ο蠹?xì)化系數(shù)eOELC如式(2)所示:

(2)

定義3對(duì)于屬性?；瘜哟蜟1和C2,若存在偏序關(guān)系C1≤C2,即前者是后者的細(xì)化,在度量細(xì)化時(shí),定義面向?qū)傩约?xì)化系數(shù)eAELC如式(3)所示:

(3)

以下用示例說明2種細(xì)化系數(shù)的用法。

例1現(xiàn)有一購物網(wǎng)站搜索場景利用如表2所示形式背景K=(G,M,I)表示,其中,M={m1,m2,m3},MC1={m1,m2,m31,m32},MC2={m1,m2,m31,m321,m322}。對(duì)象代表4種不同的鞋品,屬性代表商品的特征,m1,m2和m3分別代表網(wǎng)面材質(zhì)、黑色和安踏品牌,且粒度樹如圖2所示。對(duì)于存在偏序關(guān)系C2

Figure 2 Granularity tree of table 2

Table 2 Formal background K=(G,M,I) for example 1

計(jì)算可得:

|OEL(K)|=8,|AEL(K)|=7,|OEL(KC1)|=11,eOELC1=11/8,|AEL(KC1)|=10,eAELC1=10/7。

同理,|OEL(KC2)|=12,eOELC2=12/11>1;|AEL(KC2)|=15,eOELC2=3/2>1。該屬性?；贑2上存在意義。

4 不存在偏序關(guān)系的不同粒度層次

在實(shí)際應(yīng)用中,經(jīng)常使用屬性?；瘜?duì)現(xiàn)有概念進(jìn)行細(xì)化,而屬性細(xì)化方向的選擇則與屬性粒化的效率息息相關(guān),細(xì)化方向選擇的不同會(huì)導(dǎo)致屬性?；实牟顒e,例如,在試圖細(xì)化“牛仔褲”這個(gè)概念的時(shí)候,存在多種細(xì)化方向,顯然,將“藍(lán)色”細(xì)化為“深藍(lán)色”和“淺藍(lán)色”相較于將“紅色”細(xì)化為“淺紅色”和“深紅色”更加有效。

例2現(xiàn)有一購物網(wǎng)站搜索場景利用如表3所示的形式背景K=(G,M,I)表示,其中,M={m1,m2,m3},MC1={m1,m2,m31,m32},MC3={m11,m12,m2,m3}。對(duì)象代表4種不同的鞋品,屬性代表商品的特征,m1,m2和m3分別代表網(wǎng)面材質(zhì)、黑色和安踏品牌,且粒度樹如圖3所示。不存在偏序關(guān)系的屬性粒化層次及生成的新形式背景KC1=(G,MC1,IC1)和KC3=(G,MC3,IC3),m11和m12分別代表全網(wǎng)面鞋和半網(wǎng)面鞋,m31和m32分別代表安踏品牌休閑系列與安踏品牌運(yùn)動(dòng)系列。

Figure 3 Granularity tree of table 3

Table 3 Formal background K=(G,M,I) for example 2

Table 4 Formal background K=(G,M,I) for example 3

計(jì)算可得:

|OEL(KC3)|=10,eOELC3=5/4

|AEL(KC3)|=10,eAELC3=10/7=eAELC1

因此,屬性粒化方向C1優(yōu)于C3。

在具體的現(xiàn)實(shí)操作中,細(xì)化方向的選擇往往更加復(fù)雜,且相較于以上實(shí)例更加抽象和不直觀,因此通過細(xì)化算子來度量不存在偏序關(guān)系的不同粒度層次的優(yōu)劣,以此來選擇粒度層次進(jìn)行進(jìn)一步細(xì)化,從而避免冗余的計(jì)算和資源的浪費(fèi),是十分有必要的。

5 算法

5.1 理論依據(jù)

以下一組定理是獲取面向?qū)ο笕Ц拍罡衽c面向?qū)傩匀Ц拍罡竦睦碚撘罁?jù)。

定理4設(shè)K=(G,M,I)是一個(gè)形式背景,若(X,A)是一個(gè)概念且(X,B)是一個(gè)反概念,那么(X,(A,B))一定是一個(gè)OE概念,記由此得到的概念集合為O1。

定理5設(shè)K=(G,M,I)是一個(gè)形式背景,若(X,A)是一個(gè)概念且(Y,B)是一個(gè)反概念,且Y為X的最小上界,X不屬于FL(K)的外延集,那么(X,(A,B))一定是一個(gè)OE概念,記由此得到的概念集合為O2。

定理6設(shè)K=(G,M,I)是一個(gè)形式背景,若(X,A)是一個(gè)概念且(Y,B)是一個(gè)反概念,且X為Y的最小上界,Y不屬于L(K)的內(nèi)涵集,那么(Y,(A,B))一定是一個(gè)OE概念,記由此得到的概念集合為O3。

定理7設(shè)K=(G,M,I)是一個(gè)形式背景,若(X,A)是一個(gè)概念且(Y,B)是一個(gè)反概念,且X,Y均為X∩Y的最小上界,X不屬于FL(K)的外延集,Y不屬于L(K)的內(nèi)涵集,那么(X∩Y,(A,B))一定是一個(gè)OE概念,記由此得到的概念集合為O4。

定理8設(shè)K=(G,M,I)是一個(gè)形式背景,則OEOL(K)=O1∪O2∪O3∪O4。

定理9設(shè)K=(G,M,I)是一個(gè)形式背景,若(X,A)是一個(gè)概念且(Y,A)是一個(gè)反概念,那么((X,Y),A)一定是一個(gè)AE概念,記由此得到的概念集合為A1。

定理10設(shè)K=(G,M,I)是一個(gè)形式背景,若(X,A)是一個(gè)概念且(Y,B)是一個(gè)反概念,且B為A的最小上界,A不屬于FL(K)的內(nèi)涵集,那么((X,Y),A)一定是一個(gè)AE概念,記由此得到的概念集合為A2。

定理11設(shè)K=(G,M,I)是一個(gè)形式背景,若(X,A)是一個(gè)概念且(Y,B)是一個(gè)反概念,且A為B的最小上界,B不屬于L(K)的內(nèi)涵集,那么((X,Y),B)一定是一個(gè)AE概念,記由此得到的概念集合為A3。

定理12設(shè)K=(G,M,I)是一個(gè)形式背景,若(X,A)是一個(gè)概念且(Y,B)是一個(gè)反概念,且A,B均為A∩B的最小上界,A不屬于FL(K)的內(nèi)涵集,B不屬于L(K)的內(nèi)涵集,那么((X,Y),A∩B)一定是一個(gè)AE概念,記由此得到的概念集合為A4。

定理13設(shè)K=(G,M,I)是一個(gè)形式背景,則AEPL(K)=A1∪A2∪A3∪A4。

5.2 獲取eOELC算法

根據(jù)以上理論可以獲取eOELC,如算法2所示。

算法2 獲取eOELC輸入:概念格L(K),L(KC)與反概念格FL(K),FL(KC)。輸出:參數(shù)eOELC。步驟1 初始化O1=?,O2=?,o1=0,o2=0;步驟2 令LpG∩FqG=W;if W=LpG且W=FqG then O1=O1∪(W,(LpM,FqM)); /*LpG和LpM分別表示在L(K)中概念的外延和內(nèi)涵,FqG和FqM分別表示在FL(K)中反概念的外延和內(nèi)涵*/else if W=LpG,W≠FqG且FqG為W最小上界 then O1=O1∪(W,(LpM,FqM)); else if W≠LpG,W=FqG且LpG為W最小上界 then W1=W1∪(W,(LpM,FqM));else if W≠LpG,W≠FqG且LpG與FqG均為W最小上界 then O1=O1∪(W,(LpM,FqM));end ifo1為O1中元素的個(gè)數(shù);步驟3 令LpGC∩FqGC=V;if V=LpGC且V=FqGC then O2=O2∪(V,(LpMC,FqMC)); /*LpGC和LpMC分別表示在L(KC)中概念的外延和內(nèi)涵,FqGC和FqMC分別表示在FL(KC)中反概念的外延和內(nèi)涵*/else if V=LpGC,V≠FqGC且FqGC為V最小上界 then O2=O2∪(V,(LpMC,FqMC));else if V≠LpGC,V=FqGC且LpGC為V最小上界 then O2=O2∪(V,(LpMC,FqMC));else if V≠LpGC,V≠FqGC且LpGC與FqGC均為V最小上界 then O2=O2∪(V,(LpMC,FqMC));end if步驟4 eOELC=o2/o1;步驟5 輸出eOELC

例3現(xiàn)某購物網(wǎng)站需要對(duì)搜索機(jī)制改良,對(duì)10件短袖的標(biāo)簽進(jìn)行細(xì)分,根據(jù)最新網(wǎng)絡(luò)關(guān)鍵詞捕捉報(bào)告,近期“全棉”與“含棉混合面料”的區(qū)別引起消費(fèi)者廣泛討論,故生成如圖4所表示的粒度樹。

Figure 4 Granularity tree of commodity research

根據(jù)粒度樹與“商品-標(biāo)簽”對(duì)應(yīng)關(guān)系,有如表4所示形式背景K=(G,M,I)和KC=(G,MC,I),其中,G={α,β,…,τ},M={n1,n2,n3,n4},MC={n1,n2,n3,n41,n42}。

現(xiàn)以此例,從準(zhǔn)確性和效率性評(píng)估算法2(與直接計(jì)算作比較)。

利用直接計(jì)算方法,求得OEL(K)需要進(jìn)行算子計(jì)算(包括正算子和負(fù)算子)544次,交集運(yùn)算256次,比較運(yùn)算512次,最后得出|OEL(K)|=33;求得OEL(KC)需要進(jìn)行算子計(jì)算(包括正算子和負(fù)算子)2 112次,交集運(yùn)算1 024次,比較運(yùn)算2 048次,最后得出|OEL(KC)|=52。共計(jì)使用算子計(jì)算2 656次,交集運(yùn)算1 280次,比較運(yùn)算2 560次。最終計(jì)算得出eOELC=52/33。

利用本文的改進(jìn)算法Next Clousure算法計(jì)算概念格與反概念格。計(jì)算K的概念格使用算子運(yùn)算32次,比較運(yùn)算16次;計(jì)算KC的概念格使用算子運(yùn)算64次,比較運(yùn)算32次。利用2個(gè)計(jì)算結(jié)果進(jìn)一步計(jì)算eOELC的過程中,使用交集運(yùn)算1 280次,比較運(yùn)算256次,最終輸出eOELC=52/33。

在實(shí)驗(yàn)過程中,需要尤為注意的是,算子計(jì)算的復(fù)雜度與其他計(jì)算是不可同日而語的。以本數(shù)據(jù)集為例,一次算子計(jì)算包含4～50次的運(yùn)算;而一次比較計(jì)算至多只涉及5次對(duì)應(yīng)計(jì)算。因此,效率性的評(píng)估以算子計(jì)算的數(shù)目為主要評(píng)價(jià)指標(biāo)。

綜上,在計(jì)算eOELC時(shí),使用本文提出的算法相較直接計(jì)算方法大幅減少了正算子及負(fù)算子的計(jì)算量,極大降低了計(jì)算復(fù)雜度。2次計(jì)算輸出的eOELC相等。算法2相比直接計(jì)算方法在保證準(zhǔn)確性的前提下,極大提升了計(jì)算效率。

5.3 獲取eAELC算法

根據(jù)以上理論可以獲取eAELC,如算法3所示。

算法3 獲取eAELC輸入:概念格L(K),L(KC),與反概念格FL(K),FL(KC)。輸出:參數(shù)eAELC。步驟1 初始化A1=?,A2=?,a1=0,a2=0;步驟2 令LpM∩FqM=N;if N=LpM且N=FqM then A1=A1∪((LpG,FqG),N); /*LpG和LpM分別表示在L(K)中概念的外延和內(nèi)涵,FqG和FqM分別表示在FL(K)中反概念的外延和內(nèi)涵*/else if N=LpM,N≠FqM且FqM為N最小上界 then A1=A1∪((LpG,FqG),N);else if N≠LpM,N=FqM且LpM為N最小上界 then A1=A1∪((LpG,FqG),N);else if N≠LpM,N≠FqM且LpM,FqM均為N最小上界 then A1=A1∪((LpG,FqG),N);end ifa1為A1中元素的個(gè)數(shù);步驟3 令LpMC∩FqMC=Q;if Q=LpMC且Q=FqMC then A2=A2∪((LpGC,FqGC),Q);else if Q=LpMC,Q≠FqMC且FqMC為Q最小上界 then A2=A2∪((LpGC,FqGC),Q);else if Q≠LpMC,Q=FqMC 且LqMC為Q最小上界 then A2=A2∪((LpGC,FqGC),Q);else if Q≠LpMC,Q≠FqMC且LpMC,FqMC均為Q最小上界 then A2=A2∪((LpGC,FqGC),Q);end ifa2為A2中元素的個(gè)數(shù);步驟4 eAELC=a2/a1;步驟5 輸出eAELC

接例3,從準(zhǔn)確性和效率性評(píng)估算法3(與直接計(jì)算作比較)。

利用直接計(jì)算方法,求得AEL(K)需要進(jìn)行算子計(jì)算64次,交集運(yùn)算16次,比較運(yùn)算32次,最后得出|AEL(K)|=12;求得AEL(KC)需要進(jìn)行算子計(jì)算(包括正算子和負(fù)算子)128次,交集運(yùn)算32次,比較運(yùn)算64次,最后得出|AEL(KC)|=17。共計(jì)使用算子計(jì)算192次,交集運(yùn)算48次,比較運(yùn)算96次。最終計(jì)算得出eAELC=17/12。

利用本文改進(jìn)算法Next Clousure算法計(jì)算概念格與反概念格。計(jì)算K的概念格使用算子運(yùn)算32次,比較運(yùn)算16次;計(jì)算KC的概念格使用算子運(yùn)算64次,比較運(yùn)算32次。利用2個(gè)計(jì)算結(jié)果進(jìn)一步計(jì)算eAELC過程中,使用交集運(yùn)算1 280次,比較運(yùn)算256次,最終輸出eAELC=17/12。2次計(jì)算輸出的eAELC相等。

綜上,在計(jì)算eAELC時(shí),使用本文提出算法相比直接計(jì)算方法減少了正算子及負(fù)算子的計(jì)算量。算法3相比直接計(jì)算方法在保證準(zhǔn)確性的前提下,極大地提升了計(jì)算效率。

6 結(jié)束語

本文對(duì)概念格、三支概念格以及屬性粒化的定義及性質(zhì)進(jìn)行了概述,并且研究了屬性?；昂笕Ц拍畹年P(guān)系,定義細(xì)化系數(shù),以此度量屬性?；男省１疚难芯拷Y(jié)果仍存在不能精確選擇、不能進(jìn)行精確性度量等問題。下一步將針對(duì)目前發(fā)現(xiàn)的問題進(jìn)行深入的研究。