基于模糊三支區間集半概念知識提取方法研究

毛 華, 牛振華, 馬經澤, 張植明, 楊蘭珍

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

0 引言

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

因三支決策更符合人類認知,Ren等[9]將三支決策與概念格結合,提出了三支概念格的屬性約簡;Mao等[10-11]將三支決策思想與經典半概念理論相結合,提出了兩種形式的半概念和三支粗糙半概念;康凱等[12]提出了基于三支聚類的協同過濾推薦方法。另外,在實際問題中,知識載體也經常具有不確定性關系,模糊形式背景具有描述這種不確定性和確定性的二元關系。毛華等[13]將三支半概念和模糊集理論相結合,提出了面向對象的模糊三支半概念。

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

目前對于區間集概念格的研究中,仍然束縛在經典概念格和二支決策的理論中。為解決不確定二元關系的實際問題,模糊形式背景具有描述知識載體不確定性的二元關系,三支決策是知識提取與發現的工具,本文將區間集概念格與三支決策、經典半概念和模糊集結合,提出了模糊形式背景下的面向屬性的三支區間集半概念,證明其格性質,并且給出了模糊三支區間集半概念算法,通過實例驗證了算法的有效性。由于研究目的是解決實際問題,而實際情況均為有限,故本文討論的內容均為有限。

1 預備知識

本節首先介紹了經典半概念和模糊AE-半概念,接著介紹了三支區間集概念格,更詳細內容見參考文獻[8,14,16-17]。

定義1[8]給定一個形式背景K=(U,V,R),非空集合U為對象集,非空集合V為屬性集,R為U與合V之間的一個二元關系,若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)的內涵。

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

定義3[17]設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]設K～=(U,V,R～)是一個模糊形式背景,給定一個閾值ε,對于任意的屬性子集A,B?V,則有A?B?A??B?。

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

2 模糊AE-區間集半概念

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

2.1 定義

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

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

表1 信息調查表Table 1 Schedule of information survey

現在設K=(U,V,R～)是一個模糊形式背景,U={1,2,3}代表對象集,其中:1代表紅紅;2代表明明;3代表聰聰。V={a,b,c}代表屬性集,其中:a代表是否擅長唱歌;b代表是否擅長跳舞;c代表是否擅長雜技。R～表示對象集和屬性集之間的二元關系,取閾值ε=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-區間集半概念。

2.2 性質

形式概念分析的核心是格結構,格是知識提取的依據,接下來討論模糊AE-區間集半概念的格結構。為此,由格的定義,先討論它的偏序性質。

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

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

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

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

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

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

從形式上進行對比。

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

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

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

從結構上進行對比。

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

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

2.3 算法

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

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

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

輸出:FISSCLAE。

1: LETFISSCLAE=?

5: END IF

6: ENF FOR

7: GENERATEFISSCLAE

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

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

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

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

3 模糊OE-區間集半概念

由于模糊AE-區間集半概念與模糊OE-區間集半概念具有對偶性,從而對偶地,可得到有關模糊OE-區間集半概念性質的證明。

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

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

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

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

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

輸出:FISSCLOE。

LETFISSCLOE=?

END IF

ENF FOR

GENERATEFISSCLOE

4 結論

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