魏玲，王振，祁建軍，任睿思

1.西北大學(xué) 數(shù)學(xué)學(xué)院， 西安 710127； 2.西安電子科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 西安 710071；3.西北大學(xué) 概念、 認(rèn)知與智能研究中心， 西安 710127

形式概念分析(Formal concept analysis， FCA)作為有效的、 極具潛力的知識(shí)發(fā)現(xiàn)工具， 于1982年由德國(guó)數(shù)學(xué)家Wille 首次提出， 用于概念的發(fā)現(xiàn)、 排序和顯示[1-2]． Wille將數(shù)據(jù)描述為形式背景， 并定義了一對(duì)導(dǎo)出算子， 由此生成形為(外延， 內(nèi)涵)二元對(duì)的形式概念， 繼而生成作為該理論核心數(shù)據(jù)結(jié)構(gòu)的概念格． 概念格是根據(jù)形式背景中對(duì)象與屬性之間的二元關(guān)系建立的一種概念層次結(jié)構(gòu)， 生動(dòng)簡(jiǎn)潔地體現(xiàn)了概念之間的泛化與特化關(guān)系． 目前FCA的主要研究方向有屬性約簡(jiǎn)[3-7]、 規(guī)則獲取[5，8]以及向三支概念分析[9-11]、 三元概念分析[12-14]的拓廣等． 同時(shí)該理論還在港口危險(xiǎn)品管理、 智慧城市等領(lǐng)域得到了成功的應(yīng)用[15-17]．

三支概念分析(Three-way concept analysis， 3WCA)是將三支決策理論(Three-way decision， 3WD)[18]中的三分思想應(yīng)用于FCA而新產(chǎn)生的一種進(jìn)行知識(shí)發(fā)現(xiàn)的理論[9-10]． 與形式概念一樣， 三支概念也表現(xiàn)為(外延， 內(nèi)涵)二元對(duì)的形式， 但區(qū)別于形式概念， 三支概念的內(nèi)涵/外延為一個(gè)正交對(duì)[19]， 用于刻畫(huà)屬性集/對(duì)象集的三分． 因此3WCA既具有FCA的基本表現(xiàn)形式和具體研究?jī)?nèi)容， 也體現(xiàn)了3WD的“三分而治”思想． 自 2014 年提出以來(lái)， 其思想逐漸為知識(shí)發(fā)現(xiàn)研究領(lǐng)域的研究人員所接受， 研究主題與理論成果也越來(lái)越多， 如： 三支概念格屬性約簡(jiǎn)[20-21]、 三支概念格構(gòu)建[22-24]、 三支規(guī)則獲取[25]、 三支概念學(xué)習(xí)[26]、 三支概念格的特征分析[27]以及三支概念格之間的關(guān)系研究[28]等．

三支概念從共性這一角度， 同時(shí)考慮對(duì)象與屬性之間“共同具有”以及“共同不具有”正、 負(fù)兩方面的信息． 但在某些實(shí)際問(wèn)題中， 共性信息可能不那么重要， 比如在團(tuán)隊(duì)合作問(wèn)題中， 我們不僅需要知道一個(gè)團(tuán)隊(duì)可以合作完成哪些任務(wù)， 還需要關(guān)注哪些任務(wù)僅可由該團(tuán)隊(duì)的成員完成， 這就需要其他模態(tài)算子為我們提供的諸如必然信息等其他視角的信息， 因此結(jié)合不同的模態(tài)算子來(lái)實(shí)現(xiàn)信息的多視角刻畫(huà)就十分有意義． 其次， 三支概念的外延與內(nèi)涵存在著較為嚴(yán)苛的雙向?qū)?yīng)， 故三支概念的獲取也較為復(fù)雜， 因此將FCA中半概念[29-30]的單向?qū)?yīng)思想引入3WCA也顯得十分有意義． 基于此， 本文結(jié)合必然算子與可能算子， 利用區(qū)間集[31]提出必然-可能三支算子， 并定義必然-可能半三支概念， 進(jìn)而生成必然-可能半三支概念格．

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

本節(jié)給出正交對(duì)、 區(qū)間集以及3WCA的一些基本概念與性質(zhì)．

對(duì)于任意非空論域U，U的冪集記為P(U)，U的冪集的笛卡爾積記為DP(U)， 即

DP(U)=P(U)×P(U)

對(duì)于任意的(A1，B1)，(A2，B2)∈DP(U)， DP(U)上的包含、 并、 交分別定義為

特別地， 對(duì)于(A，B)∈DP(U)， 如果A∩B=?， 那么稱(chēng)(A，B)為一個(gè)正交對(duì)．

U上的區(qū)間集為

3WCA的數(shù)據(jù)基礎(chǔ)是形式背景．

定義1[2]稱(chēng)三元組(G，M，I)為一個(gè)形式背景， 其中G={g1，g2， …，gp}為對(duì)象集， 每個(gè)gi(i≤p)稱(chēng)為一個(gè)對(duì)象；M={m1，m2， …，mq}為屬性集， 每個(gè)mj(j≤q)稱(chēng)為一個(gè)屬性．I?G×M為G和M之間的二元關(guān)系， 若(g，m)∈I， 則稱(chēng)對(duì)象g具有屬性m．

其中c表示集合的補(bǔ)集， 即Ic=G×M-I．

特別地， 對(duì)于任意的g∈G，m∈M， 記{g}*為g*， {m}*為m*．

若X<·=(A，B)且(A，B)·>=X同時(shí)成立， 則(X， (A，B))稱(chēng)為(G，M，I)的一個(gè)對(duì)象導(dǎo)出三支概念， 簡(jiǎn)稱(chēng)為OE-概念， 其中X稱(chēng)為OE-概念的外延， (A，B)稱(chēng)為OE-概念的內(nèi)涵．

((X，Y)，A))稱(chēng)為(G，M，I)的一個(gè)屬性導(dǎo)出三支概念， 即AE-概念， 當(dāng)且僅當(dāng)(X，Y)·>=A與A<·=(X，Y)同時(shí)成立． (X，Y)稱(chēng)為AE-概念的外延，A稱(chēng)為AE-概念的內(nèi)涵．

所有OE-概念組成的集合OEL(G，M，I)可形成一個(gè)完備格， 稱(chēng)之為對(duì)象導(dǎo)出三支概念格(簡(jiǎn)稱(chēng)OE-概念格)． 對(duì)偶地， 所有AE-概念形成的完備格稱(chēng)為屬性導(dǎo)出三支概念格AEL(G，M，I)(簡(jiǎn)稱(chēng)AE-概念格)． OE-概念格及AE-概念格上的偏序關(guān)系及上、 下確界具體可參見(jiàn)文獻(xiàn)[9-10]．

例1表1為形式背景(G，M，I)， 其中對(duì)象集G={1， 2， 3， 4}為4名學(xué)生的集合， 屬性集M= {a，b，c，d}為4個(gè)問(wèn)題的集合． 表1中“1”表示學(xué)生能解決該問(wèn)題， “0”則表示不能， 如： 學(xué)生1能解決問(wèn)題a，c，d， 不能解決問(wèn)題b． 表1形式背景的OE-概念格、 AE-概念格分別如圖1、 圖2所示．

表1 形式背景(G， M， I)

圖1 表1的OE-概念格

圖2 表1的AE-概念格

下面以(13， (c，b))為例解釋OE-概念的語(yǔ)義． 該概念表明： 學(xué)生1與3都可以解決的問(wèn)題是c， 都不能解決的問(wèn)題是b， 而能解決c且不能解決問(wèn)題b的學(xué)生也恰為1與3． {c}∪ 的補(bǔ)集中的問(wèn)題a，d則是學(xué)生1與3具有差異的問(wèn)題． 所以O(shè)E-概念清晰、 完整、 準(zhǔn)確地反映了一個(gè)對(duì)象子集的正、 負(fù)兩種共性與差異性．

AE-概念的解釋與OE-概念類(lèi)似， 只不過(guò)是從屬性角度出發(fā)， 考慮一個(gè)屬性子集被對(duì)象子集共同具有以及共同不具有的情況．

此外， 一些研究人員從模態(tài)邏輯的角度， 將*算子稱(chēng)為充分算子， 并陸續(xù)提出必然算子、 可能算子以及對(duì)偶充分算子等概念[29-30]．

給定形式背景(G，M，I)， 對(duì)于任意X?G，A?M， 必然算子□定義為

X□={m∈M|m*?X}

A□={g∈G|g*?A}

可能算子◇定義為

X◇={m∈M|m*∩X≠?}

A◇={g∈G|g*∩A≠?}

以例1中的對(duì)象子集{1， 2}為例， {1， 2}□=syggg00表明： 能解決問(wèn)題d的學(xué)生一定在學(xué)生1與2之中， {1， 2}◇=M表明： 學(xué)生1和2能解決所有問(wèn)題．

必然算子與可能算子的性質(zhì)如下：

性質(zhì)1[33-34]設(shè)(G，M，I)為一個(gè)形式背景， 對(duì)于任意X，X1，X2?G，A，A1，A2?M， 有：

(i)X□?X◇，A□?A◇；

2 對(duì)象導(dǎo)出必然可能半三支概念

3WCA從正、 負(fù)兩方面同時(shí)考慮共性， 利用正交對(duì)實(shí)現(xiàn)對(duì)象集屬性集的三分． 事實(shí)上， 不同的模態(tài)算子從不同的角度刻畫(huà)不同的信息， 并且不同模態(tài)算子之間也存在著內(nèi)在關(guān)系， 如： 必然算子與可能算子間的包含關(guān)系， 使得我們可以結(jié)合兩種不同的模態(tài)算子， 利用區(qū)間集等工具， 定義新的三支算子來(lái)獲取多視角信息， 并實(shí)現(xiàn)對(duì)象集屬性集的三分．

2.1 對(duì)象導(dǎo)出必然可能三支算子

結(jié)合必然算子□與可能算子◇， 從對(duì)象子集三分屬性集的角度， 定義對(duì)象導(dǎo)出必然-可能三支算子如下：

ONPE-算子具有如下性質(zhì)：

性質(zhì)2設(shè)(G，M，I)為一個(gè)形式背景， 對(duì)于任意X1，X2∈P(G)， 我們有：

(ii) 由性質(zhì)1(d)，(e)， 可知

(iii) 由性質(zhì)1(f)，(g)， 我們有

2.2 對(duì)象導(dǎo)出必然可能半三支概念

形式概念分析中， 稱(chēng)形如(X，X*)，(A*，A)的二元對(duì)為形式背景(G，M，I)的半概念， 其中X?G是任意的對(duì)象子集，A?M是任意的屬性子集． 不難看出， 半概念僅考慮對(duì)象子集與屬性子集間的單向?qū)?yīng)， 而不再?gòu)?qiáng)調(diào)苛刻的雙向?qū)?yīng)． 基于這種思想， 我們利用ONPE-算子， 定義對(duì)象導(dǎo)出必然-可能半三支概念為：

對(duì)于對(duì)象子集X?G， 區(qū)別于OE-算子獲取的共有屬性， ONPE-算子可以同時(shí)獲取必然屬性X□與可能屬性X◇， 并形成屬性集M上的一個(gè)區(qū)間集[X□，X◇]， 這個(gè)區(qū)間集可將M分為3部分： 正域POSX=X□、 負(fù)域NEGX=M-X◇以及中間域BNDX=X◇-X□． 并且POSX，NEGX和BNDX兩兩互不相交， 形成M的一個(gè)弱三劃分．

例2表1形式背景下所有的ONPSE-概念如表2所示．

表2 表1的ONPSE-概念

以(12， [d，M])， (14， [d，M])為例解釋ONPSE-概念的語(yǔ)義． 概念(12， [d，M])表明： 能解決問(wèn)題d的學(xué)生在學(xué)生1與學(xué)生2當(dāng)中， 學(xué)生1和學(xué)生2可以合作解決所有的問(wèn)題． 類(lèi)似地， 概念(14， [d，M])表明： 能解決問(wèn)題d的學(xué)生在學(xué)生1與學(xué)生4當(dāng)中， 學(xué)生1和學(xué)生4可以合作解決所有的問(wèn)題． 結(jié)合兩個(gè)ONPSE-概念， 我們進(jìn)一步可知， 能解決問(wèn)題d的學(xué)生是學(xué)生1， 符合概念(1， [d，acd])所反映的信息．

稱(chēng)ONPSEL(G，M，I)為(G，M，I)的對(duì)象導(dǎo)出必然-可能半三支概念格， 簡(jiǎn)稱(chēng)為ONPSE-概念格． 定理1給出其上、 下確界， 并證明其是一個(gè)完備格．

定理1ONPSEL(G，M，I)是一個(gè)完備格， 其上、 下確界分別為：

則X1?X且X2?X， 故X1∪X2?X， 因此

例3表1的ONPSE-概念格如圖3所示．

圖3 表1的ONPSE-概念格

定理2ONPSEL(G，M，I)?P(G)， 其中P(G)為G的冪集格．

3 屬性導(dǎo)出必然-可能半三支概念

3.1 屬性導(dǎo)出必然-可能三支算子

結(jié)合必然算子□與可能算子◇， 從屬性子集三分對(duì)象集的角度研究屬性導(dǎo)出必然-可能半三支概念． 因與第2節(jié)類(lèi)似， 本節(jié)證明省略． 首先， 定義屬性導(dǎo)出必然-可能三支算子如下：

ANPE-算子具有如下性質(zhì)：

性質(zhì)3設(shè)(G，M，I)為一個(gè)形式背景， 對(duì)于任意A1，A2∈P(M)， 我們有：

3.2 屬性導(dǎo)出必然-可能半三支概念

ANPE-算子可以生成屬性導(dǎo)出必然-可能半三支概念， 簡(jiǎn)稱(chēng)ANPSE-概念．

ONPSE-概念與ANPSE-概念統(tǒng)稱(chēng)為必然-可能半三支概念， 簡(jiǎn)稱(chēng)為NPSE-概念．

類(lèi)似于ONPE-算子， 對(duì)于屬性子集A?M， 可以利用ANPE-算子得對(duì)象集G上的一個(gè)區(qū)間集[A□，A◇]， 這個(gè)區(qū)間集可將G分為3部分： 正域POSA=A□、 負(fù)域NEGA=G-A◇以及中間域BNDA=A◇-A□． 并且POSA，NEGA和BNDA互不相交， 形成G的一個(gè)弱三劃分．

稱(chēng)ANPSEL(G，M，I)為(G，M，I)的屬性導(dǎo)出必然-可能半三支概念格， 簡(jiǎn)稱(chēng)為ANPSE-概念格．

定理3ANPSEL(G，M，I)是一個(gè)完備格， 其上、 下確界分別為

例4表1的所有ANPSE-概念如表3所示， ANPSE-概念格如圖4所示．

圖4 表1的ANPSE-概念格

表3 表1的ANPSE-概念

以([234，G]，abc)為例解釋ANPSE-概念的語(yǔ)義． 概念([234，G]，abc)表明： 問(wèn)題a，b，c可被所有學(xué)生合作解決， 學(xué)生2，3，4能解決的問(wèn)題在a，b，c當(dāng)中． 并且G與{2， 3， 4}的差集中的學(xué)生1還能解決其他問(wèn)題， 如概念([?， 1]，d)表明： 學(xué)生1還能解決問(wèn)題d．

由ANPSE-概念定義， 可得以下結(jié)論：

定理4ANPSEL(G，M，I)?P(M)， 其中P(M)為M的冪集格．

4 結(jié)語(yǔ)

本文基于多視角信息獲取這一想法， 結(jié)合必然算子與可能算子， 從對(duì)象或?qū)傩赃@兩種不同的角度出發(fā)， 定義了對(duì)象導(dǎo)出與屬性導(dǎo)出必然-可能三支算子， 并結(jié)合形式概念分析中半概念的單向?qū)?yīng)思想， 獲取了對(duì)象導(dǎo)出與屬性導(dǎo)出必然-可能半三支概念， 拓廣了三支概念的語(yǔ)義．

事實(shí)上， 對(duì)象與屬性作為兩種不同的研究角度， 生成的兩種必然-可能半三支概念的語(yǔ)義解釋與應(yīng)用場(chǎng)景也有所不同， 如在形式概念分析與知識(shí)空間理論結(jié)合的研究[35-36]中， 從對(duì)象或?qū)傩猿霭l(fā)可分別看作是問(wèn)題驅(qū)動(dòng)或技能驅(qū)動(dòng)這兩種截然不同的研究方向， 因此如何結(jié)合上述研究成果， 對(duì)兩種必然-可能半三支概念的語(yǔ)義與應(yīng)用做進(jìn)一步研究就很有意義． 本文僅從正面結(jié)合必然算子與可能算子獲取了多視角的信息， 而負(fù)信息也很重要， 因此如何從負(fù)面結(jié)合必然算子與可能算子來(lái)獲取信息也十分有意義． 并且必然算子與可能算子與雙論域粗糙集[37-38]的下、 上近似有著緊密聯(lián)系[39]， 因此本文獲取的必然-可能半三支概念對(duì)雙論域粗糙集的知識(shí)可視化也有所幫助， 如： 我們可以從ONPSE-概念格迅速獲取雙論域粗糙集的可定義集與不可定義集， 因此如何將本文研究?jī)?nèi)容與雙論域粗糙集結(jié)合也很重要． 最后， 其他模態(tài)算子的結(jié)合研究也十分有意義， 如文獻(xiàn)[40]結(jié)合充分算子與可能算子探討了共同-可能粒描述． 這些都是我們未來(lái)的研究方向．