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

(1.河北大學 數(shù)學與信息科學學院 河北 保定 071002; 2.河北省機器學習與計算機智能重點實驗室 河北 保定 071002)

0 引言

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

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

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

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

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

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

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

引理1[12]設(shè)K～=(U,V,R～)是一個模糊形式背景,給定一個閾值ε,對于任意的屬性子集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 定義

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

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

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

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

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

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

2.2 性質(zhì)

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

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

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

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

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

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

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

從形式上進行對比。

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

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

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

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

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

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

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 的時間復(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ū)間集半概念具有對偶性,從而對偶地,可得到有關(guān)模糊OE-區(qū)間集半概念性質(zhì)的證明。

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

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

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

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

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

輸出:FISSCLOE。

LETFISSCLOE=?

END IF

ENF FOR

GENERATEFISSCLOE

4 結(jié)論

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