基于模糊三支區(qū)間集半概念知識(shí)提取方法研究

毛 華, 牛振華, 馬經(jīng)澤, 張植明, 楊蘭珍

(1.河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河北 保定 071002; 2.河北省機(jī)器學(xué)習(xí)與計(jì)算機(jī)智能重點(diǎn)實(shí)驗(yàn)室 河北 保定 071002)

0 引言

Yao[1]提出的三支決策模型,是對(duì)二支決策的一個(gè)推廣,是在原有的接受和拒絕二支決策的模型上添加了不承諾這一延遲決策[2-3]。概念格是一種基于形式背景進(jìn)行數(shù)據(jù)處理的數(shù)學(xué)工具[4]。形式背景是其數(shù)據(jù)的載體,概念是其知識(shí)的表達(dá)形式,整個(gè)知識(shí)構(gòu)成格結(jié)構(gòu),為形式概念分析的核心內(nèi)容,廣泛應(yīng)用于人工智能和知識(shí)提取等[5-7]領(lǐng)域。在實(shí)際問題中,有些知識(shí)只需要考慮對(duì)象所擁有的屬性或者屬性所具有的對(duì)象。因此,作為形式概念分析的提升,Vormbrock等[8]提出經(jīng)典半概念,并且建立了經(jīng)典半概念理論。

因三支決策更符合人類認(rèn)知,Ren等[9]將三支決策與概念格結(jié)合,提出了三支概念格的屬性約簡(jiǎn);Mao等[10-11]將三支決策思想與經(jīng)典半概念理論相結(jié)合,提出了兩種形式的半概念和三支粗糙半概念;康凱等[12]提出了基于三支聚類的協(xié)同過濾推薦方法。另外,在實(shí)際問題中,知識(shí)載體也經(jīng)常具有不確定性關(guān)系,模糊形式背景具有描述這種不確定性和確定性的二元關(guān)系。毛華等[13]將三支半概念和模糊集理論相結(jié)合,提出了面向?qū)ο蟮哪：О敫拍睢?/p>

在許多實(shí)際問題中,有些知識(shí)往往不能被精確定義,假設(shè)一個(gè)實(shí)體是否是概念的實(shí)例僅有兩種可能,即是或非,由于信息不完全,并不能對(duì)所有實(shí)體都作出這種明確的判斷,這個(gè)概念稱為部分已知的。為了描述這種部分已知概念,Yao[14]提出了有限域上一種新的集合概念:區(qū)間集。區(qū)間集是由一對(duì)上界和下界所表示的閉區(qū)間,下界表示所有確定屬于該概念的實(shí)體,上界表示所有可能屬于該概念的實(shí)體。錢婷等[15]介紹了完備形式背景上區(qū)間集概念格的構(gòu)造方法,劉營營等[16]提出了三支區(qū)間集概念格。

目前對(duì)于區(qū)間集概念格的研究中,仍然束縛在經(jīng)典概念格和二支決策的理論中。為解決不確定二元關(guān)系的實(shí)際問題,模糊形式背景具有描述知識(shí)載體不確定性的二元關(guān)系,三支決策是知識(shí)提取與發(fā)現(xiàn)的工具,本文將區(qū)間集概念格與三支決策、經(jīng)典半概念和模糊集結(jié)合,提出了模糊形式背景下的面向?qū)傩缘娜^(qū)間集半概念,證明其格性質(zhì),并且給出了模糊三支區(qū)間集半概念算法,通過實(shí)例驗(yàn)證了算法的有效性。由于研究目的是解決實(shí)際問題,而實(shí)際情況均為有限,故本文討論的內(nèi)容均為有限。

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

本節(jié)首先介紹了經(jīng)典半概念和模糊AE-半概念,接著介紹了三支區(qū)間集概念格,更詳細(xì)內(nèi)容見參考文獻(xiàn)[8,14,16-17]。

定義1[8]給定一個(gè)形式背景K=(U,V,R),非空集合U為對(duì)象集,非空集合V為屬性集,R為U與合V之間的一個(gè)二元關(guān)系,若x∈U,a∈V,對(duì)象x具有屬性a當(dāng)且僅當(dāng)(x,a)∈R或xRa。

算子*:2V→2U定義為

A*={x|x∈U,?a∈V,aRx},(A∈2V)。

對(duì)于X∈U,A∈V,若A*=X,則稱(X,A)為∪半概念,X為(X,A)的外延,A為(X,A)的內(nèi)涵。

定義2[17]設(shè)K～=(U,V,R～)是一個(gè)模糊形式背景,U為所有對(duì)象構(gòu)成的集合,V為所有屬性構(gòu)成的集合,R～為一個(gè)定義在U×V上的模糊集。若(x,a)∈R～,μ(x,a)稱為對(duì)象x關(guān)于屬性a的隸屬度,則有0≤μ(x,a)≤1。

定義3[17]設(shè)K～=(U,V,R～)是一個(gè)模糊形式背景,給定一個(gè)閾值ε,X?U,A?V,則定義模糊三支算子?:2V→2U×2U,

定義模糊正算子*ε:2V→2U為

A*ε={x|x∈U,?a∈V,μ(x,a)≥ε},A∈2V。

對(duì)偶得到模糊三支算子?:2U→2V×2V,

其中:X*ε={a|a∈V,?x∈U,μ(x,a)≥ε};

引理1[12]設(shè)K～=(U,V,R～)是一個(gè)模糊形式背景,給定一個(gè)閾值ε,對(duì)于任意的屬性子集A,B?V,則有A?B?A??B?。

4)X=[U,U]-[Xl,Xu];

2 模糊AE-區(qū)間集半概念

本節(jié)首先引入模糊AE-區(qū)間集半算子,接著定義模糊AE-區(qū)間集半概念,其次討論模糊AE-區(qū)間集半概念的格結(jié)構(gòu),并在此基礎(chǔ)上給出尋找模糊AE-區(qū)間集半概念全體的算法。

2.1 定義

用實(shí)例解釋模糊AE-區(qū)間集半概念。

例1對(duì)大學(xué)某班的三名文娛委員紅紅、明明、聰聰進(jìn)行調(diào)查,各自對(duì)三項(xiàng)活動(dòng)的擅長程度進(jìn)行打分(滿分為1分),得到一個(gè)信息調(diào)查表,見表1。

表1 信息調(diào)查表Table 1 Schedule of information survey

現(xiàn)在設(shè)K=(U,V,R～)是一個(gè)模糊形式背景,U={1,2,3}代表對(duì)象集,其中:1代表紅紅;2代表明明;3代表聰聰。V={a,b,c}代表屬性集,其中:a代表是否擅長唱歌;b代表是否擅長跳舞;c代表是否擅長雜技。R～表示對(duì)象集和屬性集之間的二元關(guān)系,取閾值ε=0.6,當(dāng)μ(x,a)≥0.6時(shí),可認(rèn)為該同學(xué)擅長某項(xiàng)活動(dòng),那么表1的形式背景如表2所示。

表2 形式背景K=(U,V,R～)Table 2 Formal context K=(U,V,R～)

由此反映出1號(hào)同學(xué)擅長唱歌、跳舞,可以推薦1號(hào)同學(xué)去參加學(xué)校組織的歌唱活動(dòng),2號(hào)同學(xué)只擅長唱歌,當(dāng)1號(hào)同學(xué)有什么緊急情況不能去參加學(xué)校組織的歌唱活動(dòng)時(shí),2號(hào)同學(xué)可作為備選人員參加,3號(hào)同學(xué)既不擅長唱歌也不擅長跳舞,那么這次活動(dòng)不推薦3號(hào)同學(xué)。由定義8可知(([1,12],[3,3]),[a,ab])是模糊AE-區(qū)間集半概念。

2.2 性質(zhì)

形式概念分析的核心是格結(jié)構(gòu),格是知識(shí)提取的依據(jù),接下來討論模糊AE-區(qū)間集半概念的格結(jié)構(gòu)。為此,由格的定義,先討論它的偏序性質(zhì)。

定理1設(shè)K～=(U,V,R～)是一個(gè)模糊形式背景,則(FISSCLAE,≤)在定義9給出的關(guān)系中構(gòu)成一個(gè)偏序集。

得≤為偏序關(guān)系,(FISSCLAE,≤)是偏序集。

(FISSCLAE,∨,∧)是一個(gè)完備格,稱之為模糊AE-區(qū)間集半概念格。

證明(FISSCLAE,∨,∧)是一個(gè)格。

綜上可證(FISSCLAE,∨,∧)是一個(gè)格。

接下來對(duì)模糊半概念(X,A)、模糊AE-半概念((M,N),B)和模糊AE-區(qū)間集半概念(([Ml,Mu],[Nl,Nu]),[Bl,Bu])進(jìn)行對(duì)比。

從形式上進(jìn)行對(duì)比。

1) 模糊半概念(X,A)為二維數(shù)據(jù);模糊AE-半概念((M,N),B)為三維數(shù)據(jù);模糊AE-區(qū)間集半概念(([Ml,Mu],[Nl,Nu]),[Bl,Bu])為三維區(qū)間集數(shù)據(jù)。

2) 對(duì)于模糊AE-區(qū)間集半概念(([Ml,Mu],[Nl,Nu]),[Bl,Bu]),Ml=Mu,Nl=Nu,Bl=Bu時(shí)為模糊AE-半概念。

3) 模糊半概念(X,A)僅考慮了屬性擁有的對(duì)象,模糊AE-區(qū)間集半概念(([Ml,Mu],[Nl,Nu]),[Bl,Bu])不僅考慮了屬性區(qū)間集共同擁有的對(duì)象區(qū)間集,也考慮了屬性區(qū)間集共同不擁有的對(duì)象區(qū)間集。因此模糊AE-區(qū)間集半概念的應(yīng)用范圍更廣泛。

從結(jié)構(gòu)上進(jìn)行對(duì)比。

1) 模糊半概念(X,A)、模糊AE-半概念((M,N),B)、模糊AE-區(qū)間集半概念(([Ml,Mu],[Nl,Nu]),[Bl,Bu])都可以構(gòu)成格。

2) 每一個(gè)概念可以看成一個(gè)知識(shí),通過建立不同的泛化-例化關(guān)系,構(gòu)成各自的格,進(jìn)而進(jìn)行知識(shí)提取。

2.3 算法

接下來根據(jù)已知模糊形式背景,給出尋找模糊AE-區(qū)間集半概念全體的算法。

算法1尋找模糊AE-區(qū)間集半概念全體

輸入:K～=(U,V,R～),閾值ε。

輸出:FISSCLAE。

1: LETFISSCLAE=?

5: END IF

6: ENF FOR

7: GENERATEFISSCLAE

現(xiàn)分析算法1 的時(shí)間復(fù)雜度,步驟2的復(fù)雜度為O(2|V|×2|V|)=O(2(2×|V|)),步驟3的復(fù)雜度為O(2×|U|),則算法1的復(fù)雜度為O(2(2×|V|)+2×|U|)。

表3 模糊AE-區(qū)間集半算子Table 3 Fuzzy AE-interval-set semioperator

根據(jù)定理2可以得到模糊AE-區(qū)間集半概念格,如圖1所示。為方便起見,在模糊AE-區(qū)間集半概念格的圖中只列出模糊AE-區(qū)間集半概念格的內(nèi)涵。該例子說明了算法1的有效性。

圖1 模糊AE-區(qū)間集半概念格Figure 1 Fuzzy AE-interval-set semiconcept lattice

3 模糊OE-區(qū)間集半概念

由于模糊AE-區(qū)間集半概念與模糊OE-區(qū)間集半概念具有對(duì)偶性,從而對(duì)偶地,可得到有關(guān)模糊OE-區(qū)間集半概念性質(zhì)的證明。

定義10設(shè)K～=(U,V,R～)是一個(gè)模糊形式背景,給定一個(gè)閾值

定理3設(shè)K～=(U,V,R～)是一個(gè)模糊形式背景,則(FISSCLOE,≤)在定義12給出的關(guān)系中構(gòu)成一個(gè)偏序集。

(FISSCLOE,∨,∧)是一個(gè)完備格,稱之為模糊OE-區(qū)間集半概念格。

算法2尋找模糊OE-區(qū)間集半概念全體

輸入:K～=(U,V,R～),閾值ε。

輸出:FISSCLOE。

LETFISSCLOE=?

END IF

ENF FOR

GENERATEFISSCLOE

4 結(jié)論

考慮實(shí)際問題,有些知識(shí)是在模糊形式背景下提取的,作為區(qū)間集概念格的拓廣,本文將區(qū)間集與三支決策和經(jīng)典半概念和模糊集理論結(jié)合起來,提出兩種形式的模糊三支區(qū)間集半概念(模糊AE-區(qū)間集半概念和模糊OE-區(qū)間集半概念),使知識(shí)提取的應(yīng)用更為廣泛。本文是在完備形式背景下研究的,不完備形式背景下的三支區(qū)間集半概念和經(jīng)典形式背景下的三支區(qū)間集半概念也值得進(jìn)行探究。