模糊語言屬性偏序結(jié)構(gòu)圖的逐層屬性約簡(jiǎn)算法

龐 闊 周 愛 楊鑫冉 李 楠 鄒 麗 魯明羽

形式概念分析(Formal Concept Analysis， FCA)理論，也稱概念格理論[1]，是知識(shí)表示與發(fā)現(xiàn)的一種有效數(shù)學(xué)工具.FCA的輸入是一個(gè)二元表，其中,行表示對(duì)象，列表示屬性，稱為形式背景.主要輸出是在形式背景中挖掘的對(duì)象與屬性的特定集群與其層次結(jié)構(gòu)，稱為概念格.目前，F(xiàn)CA被廣泛應(yīng)用于機(jī)器學(xué)習(xí)[2-5]、專家系統(tǒng)[6]、推薦系統(tǒng)[7-9]及數(shù)據(jù)挖掘[10-12]等領(lǐng)域.

在現(xiàn)實(shí)生活中，人們常通過模糊語言值描述定性的信息.如何利用人類認(rèn)知對(duì)模糊語言值數(shù)據(jù)進(jìn)行分析和可視化，從模糊語言值數(shù)據(jù)中獲取有價(jià)值的模糊語言偏好知識(shí)，已成為當(dāng)前FCA研究的熱點(diǎn).學(xué)者們對(duì)使用概念格處理模糊語言值數(shù)據(jù)進(jìn)行深入研究,并取得重要成果.Zou等[11,13-14]基于語言術(shù)語集和語言值格蘊(yùn)涵代數(shù)構(gòu)造相應(yīng)的語言概念格，并完成規(guī)則提取、屬性約簡(jiǎn)和不確定性推理等任務(wù).Pei等[15]基于 FCA 探索模糊語言值集的層次結(jié)構(gòu)，并通過模糊語言值刻畫對(duì)象的適用性，進(jìn)一步研究模糊語言值的推理.

在現(xiàn)實(shí)世界中，概念往往不滿足嚴(yán)格數(shù)學(xué)意義下的內(nèi)涵與外延的充要關(guān)系.偏序形式結(jié)構(gòu)分析(Partial Order Formal Structure Analysis， POFSA)[16]是從FCA理論基礎(chǔ)上發(fā)展而來，從認(rèn)知事物的角度出發(fā)，挖掘形式背景中對(duì)象、屬性及屬性與對(duì)象之間的關(guān)系，構(gòu)建一種以發(fā)掘?qū)傩蚤g關(guān)系和區(qū)分對(duì)象為基本目的的數(shù)學(xué)結(jié)構(gòu).在POFSA中存在2種知識(shí)結(jié)構(gòu)：屬性偏序結(jié)構(gòu)(Attribute Partial Ordered Structure， APOS)[17]與對(duì)象偏序結(jié)構(gòu)(Object Partial Ordered Structure， OPOS)[18].APOS與OPOS的可視化結(jié)構(gòu)圖分別稱為屬性偏序結(jié)構(gòu)圖(APOS Diagram， AP-OSD)與對(duì)象偏序結(jié)構(gòu)圖(OPOS Diagram， OPOSD).目前APOSD在中醫(yī)藥數(shù)據(jù)挖掘、中醫(yī)診斷的模式識(shí)別分類及自然語言處理等相關(guān)研究中取得較好的應(yīng)用效果[19-22].由于APOSD的構(gòu)建效率高于概念格，并且相比概念格，APOSD層次分明，可讀性較強(qiáng)，在進(jìn)行下游任務(wù)時(shí)，選擇APOSD不僅可提高構(gòu)建效率，還能提高結(jié)果的可解釋性.然而，目前還未發(fā)現(xiàn)將模糊語言值數(shù)據(jù)嵌入APOSD的方法.因此，如何將模糊語言值嵌入APOSD中是一個(gè)值得研究的問題.

近年來，隨著詞計(jì)算(Computing with Words， CW)[23-25]的不斷發(fā)展，學(xué)者們?cè)谀：Z言值信息處理方面也取得較大成就.目前，模糊語言值表示的工作主要集中于模糊集[26-27]、語言項(xiàng)集[28-29]和語言真值格蘊(yùn)涵代數(shù)[30-31].語言真值格蘊(yùn)涵代數(shù)可處理模糊語言值間的可比性和不可比性，豐富的蘊(yùn)涵操作更適合計(jì)算機(jī)利用模糊語言進(jìn)行不同的下游任務(wù).

概念格約簡(jiǎn)是概念格理論研究中的核心問題之一.概念格約簡(jiǎn)是在保持特定信息不變的前提下避免對(duì)象、屬性或概念的冗余.概念格約簡(jiǎn)主要分為對(duì)象約簡(jiǎn)、屬性約簡(jiǎn)和概念約簡(jiǎn).概念格中的屬性約簡(jiǎn)是一個(gè)保持形式背景或概念格某種特性不發(fā)生改變以計(jì)算極小屬性子集的過程[32].學(xué)者們?cè)谶@一方面進(jìn)行深入研究，張文修等[33]系統(tǒng)研究保持概念格結(jié)構(gòu)不變的屬性約簡(jiǎn)理論與方法，引入可辨識(shí)屬性矩陣實(shí)現(xiàn)屬性約簡(jiǎn)，并進(jìn)一步研究概念格屬性特征.Wei等[34]利用圖論結(jié)合概念格與有向圖，對(duì)屬性進(jìn)行約簡(jiǎn).Dias等[35]給出不同特性的概念格約簡(jiǎn)方法,同時(shí)有效去除系統(tǒng)中不相關(guān)的屬性信息.

在形式概念分析約簡(jiǎn)理論中，大多數(shù)屬性約簡(jiǎn)方法屬于保持概念格結(jié)構(gòu)不變的屬性約簡(jiǎn)[36-39].此后，學(xué)者們擴(kuò)展經(jīng)典概念格的屬性約簡(jiǎn)方法，研究其它不同類型的概念格屬性約簡(jiǎn)問題.Wang等[40]提出4種基于不同準(zhǔn)則的近似概念格屬性約簡(jiǎn)方法，并討論4種屬性約簡(jiǎn)之間的關(guān)系.Lin等[41]基于粒度矩陣，通過粒度協(xié)調(diào)集，提出模糊形式背景的知識(shí)約簡(jiǎn)方法.模糊語言值作為人們定性表達(dá)的工具，在屬性約簡(jiǎn)的過程中考慮模糊語言值可避免數(shù)值轉(zhuǎn)化為語言值造成的信息損失，更貼近人類的思維模式.針對(duì)含有模糊語言值信息的形式背景，通過APOSD適當(dāng)弱化概念，從而保持某種特定要求不變的屬性約簡(jiǎn)方法也是一個(gè)有意義的研究問題.

在理想情況下，屬性約簡(jiǎn)集中的每個(gè)屬性及屬性組合都能起到區(qū)分對(duì)象的作用.結(jié)合模糊語言屬性偏序圖為每個(gè)結(jié)點(diǎn)都向底層結(jié)點(diǎn)建立邊,基于語言真值格蘊(yùn)涵代數(shù)與模糊語言值形式背景，提出模糊語言屬性偏序結(jié)構(gòu)圖的逐層屬性約簡(jiǎn)算法(Layer-by-Layer Attribute Reduction Algorithm for Fuzzy Linguistic APOSD， LLAR).在屬性約簡(jiǎn)過程中嵌入模糊語言值數(shù)據(jù)的同時(shí)，還得到保持屬性偏序結(jié)構(gòu)圖區(qū)分能力不變的最小屬性子集，并以層次化視圖顯示簡(jiǎn)明區(qū)分對(duì)象的過程，可加強(qiáng)用戶與數(shù)據(jù)的交互，減輕大數(shù)據(jù)情況下用戶的認(rèn)知過載問題.本文提出模糊語言屬性偏序結(jié)構(gòu)圖(Fuzzy Linguistic APOSD， FL-APOSD)，逐層分析模糊語言屬性偏序圖中未向底層結(jié)點(diǎn)建立邊的結(jié)點(diǎn)及其子結(jié)點(diǎn)對(duì)應(yīng)的屬性，根據(jù)定義在模糊語言屬性偏序圖中的類等價(jià)，判斷屬性是否可約，把屬性約簡(jiǎn)問題轉(zhuǎn)化為在模糊語言屬性偏序圖中的搜索問題.對(duì)比實(shí)驗(yàn)表明本文算法的有效性.

1 預(yù)備知識(shí)

1.1 形式概念分析

定義1[1]稱K=(U,A,I)為一個(gè)形式背景，其中，U為對(duì)象集，A為屬性集，I為U和A之間的二元關(guān)系，I?U×A.若x∈U,a∈A,(x,a)∈I，說明對(duì)象x具有屬性a，記為xIa.

定義2[1]在形式背景K=(U,A,I)中,對(duì)?X?U，B?A，定義

f(X)={a∈A|?x∈X,(x,a)∈I}，

g(B)={x∈U|?a∈B,(x,a)∈I},

其中，f(X)表示X中所有對(duì)象共同擁有的屬性組成的集合，g(B)表示B中所有屬性的對(duì)象組成的集合.

對(duì)于形式背景(U,A,I)，對(duì)于?X?U，B?A，若滿足f(X)=B且g(B)=X，稱(X,B)為一個(gè)概念，其中，X稱為概念的外延，B稱為概念的內(nèi)涵.

所有概念的集合形成一個(gè)完備格，稱為(U,A,I)的概念格，表示為L(zhǎng)(U,A,I).

在各種下游任務(wù)中,概念往往不能滿足嚴(yán)格意義上的內(nèi)涵與外延的協(xié)調(diào)統(tǒng)一.因此，在弱化概念的前提下，Hong等[16]提出近似概念的定義.

定義3[16]設(shè)K=(U,A,I)為一個(gè)形式背景，(X,B)為K上的一個(gè)概念.假設(shè)存在(X1,B1)，滿足X1?X或B1?B，稱(X1,B1)為(X,B)的一個(gè)近似概念，其中，X1為近似概念的外延，B1為近似概念的內(nèi)涵.

定義4[16]假設(shè)(X1,B1)、(X2,B2)為形式背景(U,A,I)上2個(gè)近似概念，滿足X1?X2,稱(X1,B1)為(X2,B2)的子概念，(X2,B2)為(X1,B1)的超概念,記作(X1,B1)≤(X2,B2).關(guān)系≤表示概念間基于屬性的序.形式背景(U,A,I)所有近似概念用這種序組成的集合表示為R(U,A,I)，稱為形式背景(U,A,I)上的屬性偏序結(jié)構(gòu)圖.

定義5[16]在形式背景K=(U,A,I)中，若屬性a∈A滿足g(a)=U，則稱屬性a為形式背景K的最大共有屬性.

定義6[16]在形式背景K=(U,A,I)中，若屬性a0∈A,a1∈A,…,ak∈A滿足

g(at)?g(a0),t=1,2,…,k,k≥2，

則稱在形式背景K中，屬性a0為屬性集合{a1,a2,…,ak}的共有屬性.

定義7[16]在形式背景K=(U,A,I)中，若屬性a∈A滿足|g(a)|=1，則稱屬性a為形式背景K的獨(dú)有屬性，其中|g(a)|表示具有集合g(a)的基數(shù).

最大共有屬性、共有屬性和獨(dú)有屬性及其關(guān)系是構(gòu)造屬性偏序結(jié)構(gòu)圖的關(guān)鍵，基于這3種基本屬性特征和基本關(guān)系類型的屬性偏序結(jié)構(gòu)圖構(gòu)建方法在文獻(xiàn)[16]中有詳細(xì)介紹.下面通過例1直觀說明屬性偏序結(jié)構(gòu)圖.

例1表1為一個(gè)形式背景(U,A,I)，其中，對(duì)象集U={1,2,…,6}，屬性集

A={a,b,c,d,e,f,g}，

表中×表示對(duì)象具有某屬性.根據(jù)表1，構(gòu)建屬性偏序結(jié)構(gòu)圖R(U，A，I)，如圖1所示，生成的概念格L(U，A，I)如圖2所示.

對(duì)比圖1與圖2可知，概念格與APOSD都屬于偏序結(jié)構(gòu)，都是從FCA發(fā)展而來.不同之處在于概念格是以概念的外延偏序由大到小建立的偏序結(jié)構(gòu)，而APOSD是以屬性覆蓋概念的程度為偏序.在同一形式背景中，概念格一般會(huì)有邊的交叉，而APOSD中邊與邊之間不交叉.由于兩種圖形依據(jù)的原理和節(jié)點(diǎn)定義不同，在不同的應(yīng)用問題上具有各自的優(yōu)勢(shì).相比在概念格下進(jìn)行屬性約簡(jiǎn)任務(wù)，在APOSD下進(jìn)行屬性約簡(jiǎn)任務(wù)不僅可提高構(gòu)建效率，而且可在每個(gè)屬性約簡(jiǎn)步驟中提供約簡(jiǎn)圖，從而提高屬性約簡(jiǎn)方法的可解釋性.

表1 形式背景(U，A，I)Table 1 formal context(U，A，I)

圖1 屬性偏序結(jié)構(gòu)圖R(U，A，I)Fig.1 Attribute partial order structure diagram R(U，A，I)

圖2 概念格L(U，A，I)Fig.2 Concept lattice L(U，A，I)

1.2 模糊語言值分層概念格

定義8[30]設(shè)一個(gè)帶有逆序?qū)瓦\(yùn)算“′”的有界格(L,∨,∧,O,I)，L的最大元為I，最小元為O，若存在

1)x→(y→z)=y→(x→z)；

2)x→x=I；

3)x→y=y′→x′；

4)如果x→y=y→x=I,那么x=y；

5)(x→y)→y=(y→x)→x；

6)(x∨y)→z=(x→z)∨(y→z)；

7)(x∧y)→z=(x→z)∧(y→z)；

那么有界格(L,∨,∧,′,→,O,I)稱為一個(gè)格蘊(yùn)涵代數(shù).

定義9[30]設(shè)ADn={h1,h2,…,hn}為含有n個(gè)語氣算子的集合,h1

LV(n×2)=ADn×MT，

則稱

LV(n×2)=(LV(n×2),∧,∨,′,→,(hn,c1),(hn,c2))

為由ADn和MT生成的語言真值格蘊(yùn)涵代數(shù).LV(n×2)哈斯圖如圖3所示.

圖3 哈斯圖LV(n×2)Fig.3 Hasse diagram of LV(n×2)

定義10[11]稱(U,A,ILV(n×2))為一個(gè)模糊語言值形式背景，其中，U為對(duì)象集，A為屬性集,ILV(n×2)為U和A之間的模糊語言值關(guān)系，即ILV(n×2)?U×A.對(duì)于?xi∈U，ai∈A，存在

ILV(n×2)(xi,ai)=(hi,cj)，

其中(hi,cj)∈LV(n×2).

定義11[11]設(shè)(U,A,ILV(n×2))為一個(gè)模糊語言值形式背景，λ∈ILV(n×2)為模糊語言值信任度,對(duì)于?Y?U，C?A，定義

{a∈A|?x∈U,ILV(n×2)(x,a)≥λorILV(n×2)(x,a)‖λ}，

{x∈U|?a∈A,ILV(n×2)(x,a)≥λorILV(n×2)(x,a)‖λ},

其中ILV(n×2)(x,a)‖λ表示ILV(n×2)(x,a)與λ在LV(n×2)中不可比.

注λ所取的模糊語言值(hi,cj)與決策者的風(fēng)險(xiǎn)偏好有關(guān).

所有模糊語言值分層概念的集合形成一個(gè)完備格，稱為(U,A,ILV(n×2))的概念格,表示為L(zhǎng)VLLλ(U,A,ILV(n×2)).

2 模糊語言屬性偏序結(jié)構(gòu)圖

由于人們?cè)趯?duì)客觀事物進(jìn)行評(píng)價(jià)或決策時(shí)往往存在主觀不確定性.對(duì)于評(píng)價(jià)結(jié)果,人們往往通過模糊語言值描述.因此,有必要對(duì)APOSD中的模糊語言值數(shù)據(jù)進(jìn)行處理.本節(jié)根據(jù)粒計(jì)算(Granular Computing， GrC)的思想,從模糊語言值粒度的角度研究模糊語言屬性偏序結(jié)構(gòu)圖的構(gòu)造方法.

定義12設(shè)(U,A,ILV(n×2))為一個(gè)模糊語言值形式背景，λ為模糊語言值信任度.對(duì)于a0∈A,a1∈A,…,ak∈A，這些屬性可分為如下3類.

1)模糊語言值λ下的最大共有屬性am：

2)模糊語言值λ下的共有屬性an：

3)模糊語言值λ下的獨(dú)有屬性ao:

am、an、ao統(tǒng)稱為模糊語言值約束下的屬性特征.在模糊語言值約束下的特征屬性的基礎(chǔ)上，模糊語言屬性偏序結(jié)構(gòu)圖(FL-APOSD)的構(gòu)建模型如下.

1)初始化語言真值格蘊(yùn)涵代數(shù)LV(n×2)與模糊語言值形式背景(U,A,ILV(n×2)),選擇模糊語言值λ.

2)計(jì)算模糊語言值λ下的最大共有屬性am與其對(duì)應(yīng)的節(jié)點(diǎn)N0.若不存在am，則增加(?,U)作為頂節(jié)點(diǎn).

3)在am的約束下計(jì)算模糊語言值λ下的特征屬性集{a11,a12,…,a1k}與其對(duì)應(yīng)的節(jié)點(diǎn){N11,N12,…,N1k},再建立與N0連接的邊.

若節(jié)點(diǎn)間的關(guān)系滿足

(1)

轉(zhuǎn)至4).當(dāng)不滿足式(1)，在最底層節(jié)點(diǎn)與N0間建立l條邊：

4)在上層每個(gè)模糊語言值λ下的共有屬性{Nl1,Nl2,…,Nlr}下，計(jì)算模糊語言值λ下的共有屬性和獨(dú)有屬性集

{a(l+1)1,a(l+1)2,…,a(l+1)q}

與其對(duì)應(yīng)的節(jié)點(diǎn)

{N(l+1)1,N(l+1)2,…,N(l+1)q}.

若其上層節(jié)點(diǎn){Nl1,Nl2,…,Nlr}與模糊語言值λ下的共有屬性和獨(dú)有屬性節(jié)點(diǎn)滿足

(2)

其中Ext(Nlj)表示第l層第j個(gè)節(jié)點(diǎn)的對(duì)象集，轉(zhuǎn)至5).若不滿足式(2),在最底層節(jié)點(diǎn)與Nlj節(jié)點(diǎn)間建立L條邊：

5)當(dāng)模糊語言值λ下的共同屬性或獨(dú)有屬性下無法生成新節(jié)點(diǎn)時(shí)停止，否則轉(zhuǎn)3).

相比屬性偏序結(jié)構(gòu)圖，從如下3個(gè)角度說明FL-APOSD的優(yōu)勢(shì).

1)出發(fā)點(diǎn).屬性偏序結(jié)構(gòu)圖的出發(fā)點(diǎn)為形式背景，而FL-APOSD的出發(fā)點(diǎn)為模糊語言值形式背景.相比形式背景，模糊語言值形式背景直接描述對(duì)象與屬性間的模糊語言值關(guān)系，減少由模糊語言值轉(zhuǎn)化為數(shù)值造成的信息損失.

2)構(gòu)造方法.屬性偏序結(jié)構(gòu)圖直接根據(jù)特征屬性的計(jì)算或論域劃分生成，而FL-APOSD從粒度的角度，通過選取不同的模糊語言值信任度λ生成不同的FL-APOSD，滿足不同決策者的不同需要，隨著模糊語言值信任度λ的增大，構(gòu)建速度也會(huì)加快.

3)背景知識(shí).屬性偏序結(jié)構(gòu)圖直接通過對(duì)象與屬性間的布爾關(guān)系進(jìn)行構(gòu)造，而FL-APOSD需要引入語言真值格蘊(yùn)涵代數(shù)，得到模糊語言值間的序關(guān)系與不可比關(guān)系.

例2表2表示一個(gè)模糊語言值形式背景(U,A,ILV(n×2))，對(duì)象集U={1,2,…,5}，屬性集A={a,b,c,d,e}.

表2 模糊語言值形式背景(U,A,ILV(n×2))Table 2 Fuzzy linguistic-valued formal context(U,A,ILV(n×2))

設(shè)語氣算子的集合

AD3={h1=有點(diǎn),h2=一般,h3=極}，

元語言真值集

MT={c1=壞,c2=好}.

可得到模糊語言值集

LV(3×2)={(h1,c1),(h2,c1),(h3,c1),(h1,c2), (h2,c2),(h3,c2)}，

由定義9可容易得到一個(gè)六元語言真值格蘊(yùn)涵代數(shù)：

LV(3×2)=(LV(3×2),∨,∧,′,→,(h3,f),(h3,t))，

哈斯圖如圖4所示.

由圖4可容易獲得模糊語言值的序關(guān)系與不可比關(guān)系：

(h3,c1)<(h1,c2)<(h2,c2)<(h3,c2)，

(h2,c1)<(h2,c2), (h1,c1)<(h3,c2)，

(h3,c1)<(h2,c1)<(h1,c1)，

(h1,c1)‖(h2,c2)， (h2,c1)‖(h1,c2)， (h1,c1)‖(h1,c2).

圖4 哈斯圖LV(3×2)Fig.4 Hasse diagram of LV(3×2)

可根據(jù)不同的模糊語言值信任度得到同個(gè)模糊語言值形式背景的不同的FL-APOSD R(U,A,ILV(n×2)),具體如圖5所示.對(duì)于同個(gè)模糊語言值形式背景，選取的模糊語言值信任度不同，模糊語言值形式背景屬性約簡(jiǎn)的結(jié)果也不相同.

由圖5可知，當(dāng)模糊語言值信任度λ1=(h2,c1)和λ2=(h1,c2)時(shí)，模糊語言值形式背景(U,A,ILV(n×2))生成的2個(gè)FL-APOSD相同.原因是在六元語言真值格蘊(yùn)涵代數(shù)LV(3×2)中，2個(gè)模糊語言值不可比，因此它們的知識(shí)分類結(jié)果也一樣.

(a)λ=(h3,c1) (b)λ=(h2,c1)

(c)λ=(h1,c1) (d)λ=(h1,c2)

(e)λ=(h2,c2) (f)λ=(h3,c2)

對(duì)于模糊語言值λ3=(h1,c1)和λ2=(h1,c2)，雖然它們之間不可比，但是存在λ3>λ1和λ1‖λ2，所以λ3=(h1,c1)和λ2=(h1,c2)對(duì)應(yīng)的FL-APOSD表示不同，即當(dāng)λ3=(h1,c1) 和λ2=(h1,c2) 時(shí)，(U,A,ILV(n×2)) 的知識(shí)分類結(jié)果不同.

3 模糊語言屬性偏序結(jié)構(gòu)圖的逐層屬性約簡(jiǎn)算法

由于模糊語言屬性偏序結(jié)構(gòu)圖構(gòu)建效率高于模糊語言值分層概念格，可反映模糊語言形式背景下屬性約簡(jiǎn)的過程,可解釋性較強(qiáng).因此，本節(jié)以模糊語言屬性偏序結(jié)構(gòu)圖為基礎(chǔ)，研究模糊語言值形式背景下的屬性約簡(jiǎn)理論.

3.1 算法理論

定義13設(shè)(U,A,ILV(n×2))為模糊語言值形式背景，λ為模糊語言值信任度，R(U,A,ILV(n×2))λ為(U,A,ILV(n×2))在λ下對(duì)應(yīng)的模糊語言屬性偏序結(jié)構(gòu)圖.R(U,A,ILV(n×2))λ中與最底層節(jié)點(diǎn)(A,?)連接的節(jié)點(diǎn)的集合記為P，定義映射：

其中,(Bm,n,Xm,n)∈P表示第m層第n個(gè)節(jié)點(diǎn)，Xm+1,n表示(Bm,n,Xm,n)第n個(gè)下層節(jié)點(diǎn)對(duì)應(yīng)的對(duì)象集合,稱映射h為R(U,A,ILV(n×2))λ的對(duì)象劃分映射.集合

U/h=

稱為R(U,A,ILV(n×2))λ的對(duì)象劃分集合,集合中每個(gè)元素表示一類對(duì)象劃分.

例3以圖5(e)中λ=(h2,c2)的屬性偏序結(jié)構(gòu)圖R(U,A,ILV(n×2))(h2,c2)為例，與最底層節(jié)點(diǎn)(A,?)連接的節(jié)點(diǎn)的集合P可表示為

P={(abce,2),(bc,12),(cd,45), (acd,4),(ae,3)}.

(bc,12)節(jié)點(diǎn)擁有2個(gè)下層節(jié)點(diǎn):(abc，2)和(A,?).(cd,45)節(jié)點(diǎn)擁有2個(gè)下層節(jié)點(diǎn):(acd,4)和(A,?).其余3個(gè)節(jié)點(diǎn)的下層節(jié)點(diǎn)都為(A,?).容易得到R(U,A,ILV(n×2))(h2,c2)的對(duì)象劃分集合：

U/h={{1},{2},{3},{4},{5}}.

定義14設(shè)

(U,A1,(ILV(n×2))1)， (U,A2,(ILV(n×2))2)

為2個(gè)模糊語言值形式背景，λ1、λ2為模糊語言值信任度，

R(U,A1,(ILV(n×2))1)λ1， R(U,A2,(ILV(n×2))2)λ2

為2個(gè)模糊語言屬性偏序結(jié)構(gòu)圖,U/h1、U/h2為其對(duì)應(yīng)的對(duì)象劃分集合.對(duì)于?X∈U/h1，總存在X∈U/h2，則稱R(U,A1,(ILV(n×2))1)λ1與

R(U,A2,(ILV(n×2))2)λ2

類等價(jià)，記作

R(U,A1,(ILV(n×2))1)λ1?H/hR(U,A2,(ILV(n×2))2)λ2.

定義15設(shè)(U,A,ILV(n×2))為模糊語言值形式背景，λ為模糊語言值信任度,如果存在屬性子集D?A，使得

R(U,D,(ILV(n×2))D)λ?H/hR(U,A,ILV(n×2))λ，

則稱D為(U,A,ILV(n×2))中λ下的簡(jiǎn)化集.若?d∈D,

R(U,D-j5i0abt0b,(ILV(n×2))D-j5i0abt0b)λ?H/hR(U,A,ILV(n×2))λ

不成立，則稱D為(U,A,ILV(n×2))中λ下的約簡(jiǎn)集，R(U,D,(ILV(n×2))D)λ為R(U,A,ILV(n×2))λ的約簡(jiǎn)圖，其中

(ILV(n×2))D=ILV(n×2)∩(U×D).

定理1在模糊語言值形式背景(U,A,ILV(n×2))中,λ為模糊語言值信任度,如果存在屬性e∈A,使得

R(U,A-{e},(ILV(n×2))A-{e})λ?H/hR(U,A,ILV(n×2))λ

成立,當(dāng)且僅當(dāng)屬性e為(U,A,ILV(n×2))中λ下的非核心屬性.

證明充分性.設(shè)R(U,A,ILV(n×2))λ對(duì)應(yīng)的對(duì)象劃分集合為U/h，

R(U,A-{e},(ILV(n×2))A-{e})λ

對(duì)應(yīng)的對(duì)象劃分集合為U/hA-{e}.若在模糊語言值形式背景(U,A,ILV(n×2))中,存在屬性e∈A,使得

R(U,A-{e},(ILV(n×2))A-{e})λ?H/hR(U,A,ILV(n×2))λ

成立，則對(duì)于?X∈U/h，總存在X∈U/hA-{e}，即對(duì)象分類不變，屬性e可約，所以e∈A-∩Di為(U,A,ILV(n×2))中λ下的非核心屬性.

必要性.若在模糊語言值形式背景(U,A,ILV(n×2))中，屬性e為(U,A,ILV(n×2))中λ下的非核心屬性,則e∈A-∩Di，其中τ為一個(gè)指標(biāo)集.由e∈A-∩Di可知，存在約簡(jiǎn)Di,使得e?Di，即Di?A-{e}.由于

R(U,Di,(ILV(n×2))Di)λ?H/hR(U,A,ILV(n×2))λ,

且Di?A-{e}，所以存在

R(U,A-{e},(ILV(n×2))A-{e})λ?H/hR(U,A,ILV(n×2))λ.

得證.

定理2在模糊語言值形式背景(U,A,ILV(n×2))中，λ為模糊語言值信任度，R(U,A,ILV(n×2))λ為(U,A,ILV(n×2))在λ下對(duì)應(yīng)的模糊語言屬性偏序結(jié)構(gòu)圖，其對(duì)應(yīng)的對(duì)象劃分集合為U/h.若存在屬性e∈A，使

R(U,A-{e},(ILV(n×2))A-{e})λ?H/hR(U,A,ILV(n×2))λ，

R(U,A-{e},(ILV(n×2))A-{e})λ?H/hR(U,A,ILV(n×2))λ

矛盾，假設(shè)不成立.

得證.

3.2 算法步驟

當(dāng)模糊語言值形式背景(U,A,ILV(n×2))有n個(gè)屬性時(shí)，最多能區(qū)分2n個(gè)屬性，即約簡(jiǎn)集中的每個(gè)屬性及不同的屬性組合都能起到區(qū)分對(duì)象的作用.根據(jù)模糊語言屬性偏序結(jié)構(gòu)圖的構(gòu)圖特點(diǎn)，該情況在模糊語言屬性偏序圖中體現(xiàn)為每個(gè)節(jié)點(diǎn)都向底層節(jié)點(diǎn)建立邊.由此分析未與底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)并加以處理，將屬性約簡(jiǎn)問題轉(zhuǎn)化為在模糊語言屬性偏序結(jié)構(gòu)圖中使盡可能多的節(jié)點(diǎn)向底層節(jié)點(diǎn)建立邊的問題.

由模糊語言屬性偏序結(jié)構(gòu)圖的構(gòu)圖步驟可知,在模糊語言值形式背景(U,A,ILV(n×2))中，給定模糊語言值信任度λ，若節(jié)點(diǎn)

Cm,n=(Am,n,Um,n)

與其子節(jié)點(diǎn)集合

Φ={Φ(j)=Cm+1, j|j=1,2,…,M}

滿足關(guān)系

節(jié)點(diǎn)Cm,n與最底層節(jié)點(diǎn)建立邊，Cm,n表示R(U,A,I)中第m層第n個(gè)節(jié)點(diǎn).若節(jié)點(diǎn)

Cm,n=(Am,n,Um,n)

未向底層節(jié)點(diǎn)建立邊，為建邊需得到

可刪除Cm,n=(Am,n,Um,n)及其子節(jié)點(diǎn)集合

Φ={Φ(j)=Cm+1, j|j=1,2,…,M}

中對(duì)應(yīng)屬性的差別屬性Am+1, j-Am,n.

因此本文的模糊語言屬性偏序結(jié)構(gòu)圖的逐層屬性約簡(jiǎn)算法(LLAR)的思想是：在保持與FL-APOSD類等價(jià)的情況下，分析刪減FL-APOSD中未向底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)

Cm,n=(Am,n,Um,n)

及其子節(jié)點(diǎn)集合

Φ={Φ(j)=Cm+1, j|j=1,2,…,M}

中對(duì)應(yīng)屬性的差別屬性Am+1, j-Am,n.簡(jiǎn)化FL-APOSD,直至刪除任意屬性后的更新圖都不與原FL-APOSD類等價(jià)，這樣保留的屬性組成的集合即為屬性約簡(jiǎn)集.

根據(jù)上述分析，LLAR步驟如算法1所示.

算法1LLAR

輸入模糊語言值形式背景(U,A,ILV(n×2))，

模糊語言值信任度λ

輸出約簡(jiǎn)圖R(U,D,(ILV(n×2))D)λ，

屬性約簡(jiǎn)集D

構(gòu)造模糊語言屬性偏序結(jié)構(gòu)圖R(U,A,ILV(n×2))λ；

按照從上到下、從左到右的順序掃描R(U,A,ILV(n×2))λ，尋找未與底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)集合

Γ={Γ(s)=Cm,n|s=1,2,…,N}；

令s= 1；

while?！?

Γ(s)=Cm,n；

A′←A-(Am+1, j-Am,n)；

R(U,A′,(ILV(n×2))A′)λ←R(U,A,ILV(n×2))λ；

ifR(U,A′,(ILV(n×2))A′)λ?U/hR(U,A,ILV(n×2))λ

根據(jù)R(U,A′,(ILV(n×2))A′)λ更新Γ和Φ；

else

ifj≤M

j++；

else

Γ(s)=? ；

endif

endif

endwhile

return R(U,D,(ILV(n×2))D)λ，D.

算法1的運(yùn)行時(shí)間主要包括如下2部分.

1)R(U,D,(ILV(n×2))D)λ的構(gòu)造.假設(shè)模糊語言值形式背景(U,A,ILV(n×2))含有m個(gè)對(duì)象和n個(gè)屬性.當(dāng)計(jì)算最大共有屬性、共有屬性和獨(dú)有屬性，需要遍歷所有屬性.因此,求解R(U,D,(ILV(n×2))D)λ需要的時(shí)間復(fù)雜度為O(n2).

2)約簡(jiǎn)圖與R(U,D,(ILV(n×2))D)λ類等價(jià)的計(jì)算.假定R(U,D,(ILV(n×2))D)λ中沒有向底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)個(gè)數(shù)為o個(gè)，子節(jié)點(diǎn)個(gè)數(shù)為p個(gè).對(duì)于未向底層節(jié)點(diǎn)建立邊的每個(gè)節(jié)點(diǎn)，在計(jì)算差別屬性時(shí)，需要遍歷所有的子節(jié)點(diǎn)，需要的時(shí)間復(fù)雜度為O(o2p).

LLAR的輸出結(jié)果為約簡(jiǎn)圖

R(U,D,(ILV(n×2))D)λ

與屬性約簡(jiǎn)集D，根據(jù)定理1，當(dāng)刪除核心屬性時(shí)，會(huì)造成R(U,D,(ILV(n×2))D)λ與原始數(shù)據(jù)產(chǎn)生的模糊語言屬性偏序結(jié)構(gòu)圖R(U,A,ILV(n×2))λ非類等價(jià)，即核心屬性可起到區(qū)分不同對(duì)象的作用，反映到R(U,A,ILV(n×2))λ中，刪除節(jié)點(diǎn)中包含的核心屬性信息會(huì)使某些節(jié)點(diǎn)不會(huì)與底層節(jié)點(diǎn)建立邊.反之，當(dāng)刪除非核心屬性時(shí)，R(U,D,(ILV(n×2))D)λ與R(U,A,ILV(n×2))λ類等價(jià)，即非核心屬性不會(huì)起到區(qū)分不同對(duì)象的作用，反映到R(U,A,ILV(n×2))λ中，刪除節(jié)點(diǎn)中包含的非核心屬性信息不會(huì)影響節(jié)點(diǎn)與底層節(jié)點(diǎn)的連邊關(guān)系.

通過上述分析可知，通過遍歷所有節(jié)點(diǎn)的屬性信息以刪除節(jié)點(diǎn)中的非核心屬性信息得到的屬性約簡(jiǎn)集是保持模糊語言屬性偏序結(jié)構(gòu)圖區(qū)分能力不變的最小屬性子集.

4 數(shù)值實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)例分析

例4(續(xù)例2) 以表2作為L(zhǎng)LAR的輸入，并設(shè)置模糊語言值信任度λ=(h2,c2)，構(gòu)造模糊語言屬性偏序結(jié)構(gòu)圖R(U,A,ILV(n×2))(h2,c2)，如圖5(e)所示.

1)按照由上到下、由左到右的順序掃描

R(U,A,ILV(n×2))(h2,c2)，

發(fā)現(xiàn)首個(gè)未向底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)為(?,U)，子節(jié)點(diǎn)為(c,1245)、(a,3)，由于構(gòu)圖時(shí)屬性a、c左右位置可能不同，所以屬性集A中可刪除屬性a或c.

當(dāng)屬性集A刪除屬性a時(shí)，更新

R(U,A,ILV(n×2))(h2,c2)

為

R(U,A-{a},(ILV(n×2))A-{a})(h2,c2)，

模糊語言屬性偏序結(jié)構(gòu)圖如圖6所示.在圖中

R(U,A-{a},(ILV(n×2))A-{a})(h2,c2)

的對(duì)象劃分集合為

U/h1={{1},{2},{3},{4,5}}.

由定義14可知

R(U,A-{a},(ILV(n×2))A-{a})(h2,c2)

與R(U,A,ILV(n×2))(h2,c2)非類等價(jià).因此，屬性a不可刪除，轉(zhuǎn)為刪除屬性c.

圖6 模糊語言屬性偏序結(jié)構(gòu)圖 R(U,A-{a},(ILV(n×2))A-{a})(h2,c2)Fig.6 FL-APOSD R(U,A-{a},(ILV(n×2))A-{a})(h2,c2)

當(dāng)刪除屬性c時(shí),更新R(U,A,ILV(n×2))(h2,c2)為

R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)，

如圖7所示.在圖中,

R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)

的對(duì)象劃分集合為

U/h2={{1},{2},{3},{4},{5}},

因此，R(U,A,ILV(n×2))(h2,c2)與

R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)

類等價(jià)，確認(rèn)刪除屬性c.

圖7 模糊語言屬性偏序結(jié)構(gòu)圖 R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)Fig.7 FL-APOSD R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)

2)掃描R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)，發(fā)現(xiàn)首個(gè)未向底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)為(a，234)，刪除a，更新

R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)

為

R(U,A-{a,c},(ILV(n×2))A-{a,c})(h2,c2)，

模糊語言屬性偏序結(jié)構(gòu)圖如圖8所示.

圖8 模糊語言屬性偏序結(jié)構(gòu)圖 R(U,A-{a,c},(ILV(n×2))A-{a,c})(h2,c2)Fig.8 FL-APOSD R(U,A-{a,c},(ILV(n×2))A-{a,c})(h2,c2)

在圖8中

R(U,A-{a,c},(ILV(n×2))A-{a,c})(h2,c2)

的對(duì)象劃分集合為

U/h3={{1},{2},{3},{4,5}},

可得

R(U,A-{a,c},(ILV(n×2))A-{a,c})(h2,c2)

與R(U,A,ILV(n×2))(h2,c2)非類等價(jià)，屬性a不可刪除.繼續(xù)掃描

R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)，

發(fā)現(xiàn)節(jié)點(diǎn)(a,234)的子節(jié)點(diǎn)為(ae,23)、(ad,4),可刪除屬性為e或d.

3)當(dāng)刪除屬性e時(shí),更新

R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)

為

R(U,A-{c,e},(ILV(n×2))A-{c,e})(h2,c2)，

模糊語言屬性偏序結(jié)構(gòu)圖如圖9所示.在圖中

R(U,A-{c,e},(ILV(n×2))A-{c,e})(h2,c2)

的對(duì)象劃分集合為

U/h4={{1},{2},{3},{4},{5}},

因此，R(U,A,ILV(n×2))(h2,c2)與

R(U,A-{c,e},(ILV(n×2))A-{c,e})(h2,c2)

類等價(jià)，確認(rèn)刪除屬性e.

掃描

R(U,A-{c,e},(ILV(n×2))A-{c,e})(h2,c2)，

除頂層節(jié)點(diǎn)以外，未發(fā)現(xiàn)未向底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)，算法結(jié)束.輸出屬性約簡(jiǎn)集D1={a,b,d}，模糊語言屬性偏序結(jié)構(gòu)圖如圖9所示.

圖9 模糊語言屬性偏序結(jié)構(gòu)圖 R(U,A-{c,e},(ILV(n×2))A-{c,e})(h2,c2)Fig.9 FL-APOSD R(U,A-{c,e},(ILV(n×2))A-{c,e})(h2,c2)

當(dāng)刪除屬性d時(shí)，更新

R(U,A-{c},(ILV(n×2))A-{c})(h2,c2)

為

R(U,A-{c,d},(ILV(n×2))A-{c,d})(h2,c2)，

模糊語言屬性偏序結(jié)構(gòu)圖如圖10所示.在圖中

R(U,A-{c,d},(ILV(n×2))A-{c,d})(h2,c2)

的對(duì)象劃分集合為

U/h5={{1},{2},{3},{4},{5}},

因此，與R(U,A,ILV(n×2))(h2,c2)類等價(jià)，屬性d可刪除.掃描

R(U,A-{c,d},(ILV(n×2))A-{c,d})(h2,c2),

未發(fā)現(xiàn)未向底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)，算法結(jié)束.輸出屬性約簡(jiǎn)集D2={a,b,e}.

圖10 模糊語言屬性偏序結(jié)構(gòu)圖 R(U,A-{c,d},(ILV(n×2))A-{c,d})(h2,c2)Fig.10 FL-APOSD R(U,A-{c,d},(ILV(n×2))A-{c,d})(h2,c2)

由上述步驟可知，屬性約簡(jiǎn)集為{a,b,d}和{a,b,e}，對(duì)比

R(U,A-{c,d},(ILV(n×2))A-{c,d})(h2,c2)

和

R(U,A-{c,e},(ILV(n×2))A-{c,e})(h2,c2)

可知，屬性約簡(jiǎn)結(jié)果不同，對(duì)象的區(qū)分方式也有差異.實(shí)際上，多數(shù)情況下頂層節(jié)點(diǎn)(?,U)∈Γ，依據(jù)本文算法進(jìn)行屬性約簡(jiǎn)時(shí)會(huì)首先刪減位于第一層節(jié)點(diǎn)中的屬性.屬性所處的節(jié)點(diǎn)層越高，說明包含此屬性的對(duì)象越多，在該節(jié)點(diǎn)的基礎(chǔ)上可區(qū)分的對(duì)象類別越多.所以通常設(shè)置頂層節(jié)點(diǎn)(?,U)?Γ，以保留位于第一層節(jié)點(diǎn)中屬性，達(dá)到使用較少屬性區(qū)分較多對(duì)象類別的目的.

當(dāng)在算法中設(shè)置(?,U)?Γ時(shí)，屬性約簡(jiǎn)步驟如下.

1)按照由上到下、由左到右的順序掃描

R(U,A,ILV(n×2))(h2,c2)，

首個(gè)發(fā)現(xiàn)未向底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)為(c,1245)，其子節(jié)點(diǎn)有(bc,12),(cd,45)，可選擇刪除屬性b或d.

2)當(dāng)刪除屬性b時(shí)，更新

R(U,A,ILV(n×2))(h2,c2)

為

R(U,A-,(ILV(n×2))A-)(h2,c2)，

模糊語言屬性偏序結(jié)構(gòu)圖如圖11所示.在圖中，

R(U,A-,(ILV(n×2))A-)(h2,c2)

的對(duì)象劃分集合為

U/h1={{1},{2},{3},{4},{5}},

因此

R(U,A-,(ILV(n×2))A-)(h2,c2)

與R(U,A,ILV(n×2))(h2,c2)類同構(gòu)，確定刪除屬性b.

圖11 模糊語言屬性偏序結(jié)構(gòu)圖 R(U,A-,(ILV(n×2))A-)(h2,c2)Fig.11 FL-APOSD R(U,A-,(ILV(n×2))A-)(h2,c2)

3)掃描

R(U,A-,(ILV(n×2))A-)(h2,c2)，

首個(gè)發(fā)現(xiàn)未向底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)為(a,3)，其子節(jié)點(diǎn)為(ae,3)，可刪除屬性e，更新

R(U,A-,(ILV(n×2))A-)(h2,c2)

為

R(U,A-{b,e},(ILV(n×2))A-{b,e})(h2,c2)，

模糊語言屬性偏序結(jié)構(gòu)圖如圖12所示.在圖中

R(U,A-{b,e},(ILV(n×2))A-{b,e})(h2,c2)

的對(duì)象劃分集合為

U/h2={{1},{2},{3},{4},{5}},

R(U,A-{b,e},(ILV(n×2))A-{b,e})(h2,c2)

與R(U,A,ILV(n×2))(h2,c2)類等價(jià)，確定刪除屬性e.

圖12 模糊語言屬性偏序結(jié)構(gòu)圖 R(U,A-{b,e},(ILV(n×2))A-{b,e})(h2,c2)Fig.12 FL-APOSD R(U,A-{b,e},(ILV(n×2))A-{b,e})(h2,c2)

4)掃描

R(U,A-{b,e},(ILV(n×2))A-{b,e})(h2,c2)，

除頂層節(jié)點(diǎn)外，未發(fā)現(xiàn)未向底層節(jié)點(diǎn)建立邊的節(jié)點(diǎn)，算法結(jié)束.輸出屬性約簡(jiǎn)集D3={a,c,d}及其約簡(jiǎn)圖

R(U,D3,(ILV(n×2))D3)(h2,c2).

同理，當(dāng)刪除屬性d時(shí)，最終得到的屬性約簡(jiǎn)結(jié)果為D4={a,b,c}，模糊語言屬性偏序結(jié)構(gòu)圖如圖13所示.

圖13 模糊語言屬性偏序結(jié)構(gòu)圖 R(U,A-{d,e},(ILV(n×2))A-{d,e})(h2,c2)Fig.13 FL-APOSD R(U,A-{d,e},(ILV(n×2))A-{d,e})(h2,c2)

4.2 有效性分析

本節(jié)通過在真實(shí)數(shù)據(jù)集上實(shí)現(xiàn)模糊語言屬性偏序結(jié)構(gòu)圖在不同模糊語言值信任度λ上的構(gòu)建及屬性約簡(jiǎn)，進(jìn)而驗(yàn)證LLAR的有效性.

實(shí)驗(yàn)環(huán)境如下：CPU為Intel(R)Core(TM) i5-10400FCPU@2.90 GHz，16 GB內(nèi)存，軟件環(huán)境為Windows10下的python 3.9.

使用UCI數(shù)據(jù)集上的Iris、Glass Identification、Ionosphere、Winequality-Red這4個(gè)真實(shí)數(shù)據(jù)集評(píng)估LLAR.為了說明LLAR的有效性，將這4個(gè)數(shù)據(jù)集進(jìn)行轉(zhuǎn)置，使其屬性數(shù)量增多，更明顯表現(xiàn)LLAR的效果.具體數(shù)據(jù)集信息如表3所示.

表3 實(shí)驗(yàn)數(shù)據(jù)集Table 3 Experimental datasets

LLAR可以處理不確定性環(huán)境中的多個(gè)模糊語言值.將表3中的原始數(shù)據(jù)集通過模糊語言值信任度λ轉(zhuǎn)化為模糊語言值形式背景(U,A,ILV(3×2))，具體如表4所示，應(yīng)用六元語言真值格蘊(yùn)涵代數(shù)，即

LV(3×2)=(LV(3×2),∨,∧,′,→,(h3,c1),(h3,c2)).

表4 模糊語言值形式背景(U,A,ILV(3×2))Table 4 Fuzzy linguistic-valued formal context (U,A,ILV(3×2))

在4個(gè)不同的模糊語言值形式背景(U,A,ILV(3×2))上進(jìn)行實(shí)驗(yàn)，選取六元語言真值格蘊(yùn)涵代數(shù)中3個(gè)不同的模糊語言值作為模糊語言值信任度λ，并觀察λ的不同取值對(duì)模糊語言屬性偏序結(jié)構(gòu)圖構(gòu)造的影響.這里選取節(jié)點(diǎn)數(shù)量與運(yùn)行時(shí)間作為指標(biāo)觀察模糊語言屬性偏序結(jié)構(gòu)圖構(gòu)造的情況.

不同模糊語言值信任度λ下模糊語言屬性偏序結(jié)構(gòu)圖的指標(biāo)值變化情況如表5所示.由表可看出，在模糊語言值形式背景(U,A,ILV(3×2))中，對(duì)于語言真值格蘊(yùn)涵代數(shù)中的不同模糊語言值，模糊語言值信任度λ越大，對(duì)象與屬性之間的模糊語言值關(guān)系越粗，構(gòu)造的模糊語言屬性偏序結(jié)構(gòu)圖規(guī)模越小，即節(jié)點(diǎn)數(shù)量越少，算法運(yùn)行時(shí)間越短.反之，模糊語言值信任度λ越小，對(duì)象與屬性之間的模糊語言值關(guān)系越細(xì)，構(gòu)造的模糊語言屬性偏序結(jié)構(gòu)圖規(guī)模越大，即節(jié)點(diǎn)數(shù)量越多，算法運(yùn)行時(shí)間越長(zhǎng).

表5 不同λ對(duì)模糊語言屬性偏序結(jié)構(gòu)圖的影響Table 5 Influence of different λ on FL-APOSD

為了驗(yàn)證LLAR在屬性約簡(jiǎn)方面的有效性與實(shí)用性，在4個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并記錄不同模糊語言值信任度λ下LLAR的屬性約簡(jiǎn)數(shù)量、約簡(jiǎn)率及運(yùn)行時(shí)間，具體如表6所示.由表可看出，在不同模糊語言值形式背景(U,A,ILV(3×2))中，隨著模糊語言值信任度λ的增大，對(duì)象與屬性之間的模糊語言值關(guān)系越粗，屬性約簡(jiǎn)數(shù)量越少，運(yùn)行時(shí)間越短.

表6 不同λ對(duì)LLAR屬性約簡(jiǎn)結(jié)果的影響Table 6 Influence of different λ on LLAR attribute reduction results

4.3 實(shí)驗(yàn)結(jié)果對(duì)比

本文提出LLAR，刪除冗余屬性的同時(shí)保證

R(U,D,(ILV(3×2))D)λ?H/hR(U,A,ILV(3×2))λ，

因此依據(jù)LLAR輸出的集合D即為屬性約簡(jiǎn)集.

本文選擇如下屬性約簡(jiǎn)算法進(jìn)行實(shí)驗(yàn)對(duì)比：概念格約簡(jiǎn)方法(Concept Lattice Reduction Approach, CLR)[33]、SE-ISIAR(Attribute Reduction of SE-ISI Concept Lattices)[40]、DM-methods[39]、DMSRC(Reduct Construction Method Based on Discernibility Matrix Simplification)[42]、MGLCR(Multi-granularity Linguistic Concept Reduction)[13].各算法對(duì)比結(jié)果如表7所示.

本文在如下4方面上進(jìn)行對(duì)比分析.

1)出發(fā)點(diǎn).相比其它屬性約簡(jiǎn)方法，只有LLAR是以模糊語言屬性偏序結(jié)構(gòu)圖為基礎(chǔ)進(jìn)行的屬性約簡(jiǎn).存在3個(gè)模型是以概念格為基礎(chǔ)進(jìn)行的屬性約簡(jiǎn).在形式背景(U，A，I)中,構(gòu)造屬性偏序結(jié)構(gòu)圖的時(shí)間復(fù)雜度為O(|A|2)，構(gòu)造概念格的時(shí)間復(fù)雜度為O(|U||A|2),屬性偏序結(jié)構(gòu)圖的生成效率高于概念格，更適合應(yīng)用于屬性約簡(jiǎn).

SE-ISIAR在三支概念格下進(jìn)行屬性約簡(jiǎn)，可同時(shí)考慮正面信息與負(fù)面信息，但是構(gòu)建效率低于概念格.

CLR、SE-ISIAR、DM-methods、DMSRC都無法表達(dá)模糊語言值數(shù)據(jù)，MGLCR與LLAR可表達(dá)模糊語言值信息,但MGLCR使用的模糊語言值會(huì)隨著屬性數(shù)量的增多而產(chǎn)生維度爆炸的問題，并且MGLCR嵌入的模糊語言值數(shù)據(jù)是語義序關(guān)系，無法表達(dá)模糊語言值的不可比性.

LLAR使用的FL-APOSD是由模糊語言值形式背景構(gòu)建的，模糊語言值數(shù)據(jù)通過語言真值格蘊(yùn)涵代數(shù)表示，可同時(shí)處理模糊語言值的可比信息與不可比信息.此外，F(xiàn)L-APOSD的構(gòu)建效率與可解釋性都優(yōu)于語言概念格.

2)約簡(jiǎn)原理.由于LLAR是在FL-APOSD下進(jìn)行的屬性約簡(jiǎn)，因此，得到的屬性約簡(jiǎn)結(jié)果是保持對(duì)象的區(qū)別能力不變的最小屬性子集.而其它方法是在不同種類的概念格下進(jìn)行屬性約簡(jiǎn)，得到的是保持其概念結(jié)構(gòu)不變的最小屬性子集.

3)約簡(jiǎn)圖.僅有LLAR可產(chǎn)生約簡(jiǎn)圖，從而可直接觀察對(duì)象之間的區(qū)分方式，明確屬性約簡(jiǎn)結(jié)果中每個(gè)屬性的作用. 每個(gè)約簡(jiǎn)過程產(chǎn)生的約簡(jiǎn)圖方便人工糾正約簡(jiǎn)信息，提高LLAR的魯棒性.相比其它基于辨識(shí)矩陣的方法,屬性偏序結(jié)構(gòu)圖能更完整地表達(dá)信息，有利于部分對(duì)象的識(shí)別.

4)背景知識(shí).CLR、SE-ISIAR、DM-methods、DM-SRC未使用背景知識(shí).MGLCR將模糊語言值的語義序作為背景知識(shí)，指導(dǎo)語言概念格下的屬性約簡(jiǎn)工作.LLAR在約簡(jiǎn)每個(gè)屬性時(shí)都充分利用FL-APOSD的節(jié)點(diǎn)，保持與FL-APOSD類等價(jià).在模糊語言值形式背景中，使用語言真值格蘊(yùn)涵代數(shù)作為模糊語言值的表示模型，引入模糊語言值的序關(guān)系與不可比關(guān)系作為背景知識(shí).

此外，在同個(gè)模糊語言值形式背景中,選取的模糊語言值信任度λ不同，產(chǎn)生的FL-APOSD不同.因此，LLAR得到的屬性約簡(jiǎn)結(jié)果也不同.可通過選擇模糊語言值信任度滿足不同風(fēng)險(xiǎn)偏好的決策者對(duì)于同一模糊語言值形式背景屬性約簡(jiǎn)結(jié)果的不同需要.

表7 各算法結(jié)果對(duì)比Table 7 Result comparison analysis of different methods

5 結(jié) 束 語

本文利用模糊語言屬性偏序結(jié)構(gòu)圖能發(fā)掘?qū)傩蚤g關(guān)系和區(qū)分對(duì)象及嵌入模糊語言值數(shù)據(jù)的特征，提出基于模糊語言屬性偏序結(jié)構(gòu)圖的逐層屬性約簡(jiǎn)算法.對(duì)比分析和實(shí)例表明，LLAR可有效地為模糊語言值形式背景提供可解釋性屬性約簡(jiǎn)，同時(shí)動(dòng)態(tài)展示每個(gè)屬性的約簡(jiǎn)過程，魯棒性較強(qiáng).LLAR在模糊語言屬性偏序結(jié)構(gòu)圖下進(jìn)行屬性約簡(jiǎn)，不但可提高效率，而且保存搜索路徑，容易追溯約簡(jiǎn)的依據(jù)，以直觀方式展現(xiàn)屬性約簡(jiǎn)的過程，可解釋性較強(qiáng).此外，將模糊語言值數(shù)據(jù)嵌入形式背景中，可減少數(shù)值轉(zhuǎn)化為語言值造成的信息缺失，更貼近人類的思維模式.LLAR體現(xiàn)數(shù)據(jù)動(dòng)態(tài)更新過程，在處理帶有屬性偏好關(guān)系的模糊語言值形式背景屬性約簡(jiǎn)問題上具有一定優(yōu)勢(shì).可通過語言真值格蘊(yùn)涵代數(shù)表示模糊語言值信息,有效利用模糊語言值的序關(guān)系與不可比關(guān)系的背景知識(shí).

隨著語言真值格蘊(yùn)涵代數(shù)中元數(shù)的增加，F(xiàn)L-APOSD的構(gòu)建效率會(huì)逐漸降低，如何在語言真值格蘊(yùn)涵代數(shù)全局結(jié)構(gòu)下設(shè)計(jì)FL-APOSD構(gòu)造算法，并在此基礎(chǔ)上研究新的屬性約簡(jiǎn)方法是一個(gè)值得研究的方向.本文只對(duì)FL-APOSD的構(gòu)建模型與屬性約簡(jiǎn)方法進(jìn)行初步探索，今后可考慮將FL-APOSD應(yīng)用于不同領(lǐng)域的知識(shí)發(fā)現(xiàn)任務(wù)中.此外，今后也將考慮研究動(dòng)態(tài)模糊語言信息系統(tǒng)約簡(jiǎn)問題，并設(shè)計(jì)帶偏好的屬性約簡(jiǎn)算法.