必然-可能半三支概念①

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

1.西北大學 數學學院， 西安 710127； 2.西安電子科技大學 計算機科學與技術學院， 西安 710071；3.西北大學 概念、 認知與智能研究中心， 西安 710127

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

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

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

1 基礎知識

本節給出正交對、 區間集以及3WCA的一些基本概念與性質．

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

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

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

特別地， 對于(A，B)∈DP(U)， 如果A∩B=?， 那么稱(A，B)為一個正交對．

U上的區間集為

3WCA的數據基礎是形式背景．

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

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

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

若X<·=(A，B)且(A，B)·>=X同時成立， 則(X， (A，B))稱為(G，M，I)的一個對象導出三支概念， 簡稱為OE-概念， 其中X稱為OE-概念的外延， (A，B)稱為OE-概念的內涵．

((X，Y)，A))稱為(G，M，I)的一個屬性導出三支概念， 即AE-概念， 當且僅當(X，Y)·>=A與A<·=(X，Y)同時成立． (X，Y)稱為AE-概念的外延，A稱為AE-概念的內涵．

所有OE-概念組成的集合OEL(G，M，I)可形成一個完備格， 稱之為對象導出三支概念格(簡稱OE-概念格)． 對偶地， 所有AE-概念形成的完備格稱為屬性導出三支概念格AEL(G，M，I)(簡稱AE-概念格)． OE-概念格及AE-概念格上的偏序關系及上、 下確界具體可參見文獻[9-10]．

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

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

圖1 表1的OE-概念格

圖2 表1的AE-概念格

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

AE-概念的解釋與OE-概念類似， 只不過是從屬性角度出發， 考慮一個屬性子集被對象子集共同具有以及共同不具有的情況．

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

給定形式背景(G，M，I)， 對于任意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中的對象子集{1， 2}為例， {1， 2}□=g0gggggg表明： 能解決問題d的學生一定在學生1與2之中， {1， 2}◇=M表明： 學生1和2能解決所有問題．

必然算子與可能算子的性質如下：

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

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

2 對象導出必然可能半三支概念

3WCA從正、 負兩方面同時考慮共性， 利用正交對實現對象集屬性集的三分． 事實上， 不同的模態算子從不同的角度刻畫不同的信息， 并且不同模態算子之間也存在著內在關系， 如： 必然算子與可能算子間的包含關系， 使得我們可以結合兩種不同的模態算子， 利用區間集等工具， 定義新的三支算子來獲取多視角信息， 并實現對象集屬性集的三分．

2.1 對象導出必然可能三支算子

結合必然算子□與可能算子◇， 從對象子集三分屬性集的角度， 定義對象導出必然-可能三支算子如下：

ONPE-算子具有如下性質：

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

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

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

2.2 對象導出必然可能半三支概念

形式概念分析中， 稱形如(X，X*)，(A*，A)的二元對為形式背景(G，M，I)的半概念， 其中X?G是任意的對象子集，A?M是任意的屬性子集． 不難看出， 半概念僅考慮對象子集與屬性子集間的單向對應， 而不再強調苛刻的雙向對應． 基于這種思想， 我們利用ONPE-算子， 定義對象導出必然-可能半三支概念為：

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

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

表2 表1的ONPSE-概念

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

稱ONPSEL(G，M，I)為(G，M，I)的對象導出必然-可能半三支概念格， 簡稱為ONPSE-概念格． 定理1給出其上、 下確界， 并證明其是一個完備格．

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

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

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

圖3 表1的ONPSE-概念格

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

3 屬性導出必然-可能半三支概念

3.1 屬性導出必然-可能三支算子

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

ANPE-算子具有如下性質：

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

3.2 屬性導出必然-可能半三支概念

ANPE-算子可以生成屬性導出必然-可能半三支概念， 簡稱ANPSE-概念．

ONPSE-概念與ANPSE-概念統稱為必然-可能半三支概念， 簡稱為NPSE-概念．

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

稱ANPSEL(G，M，I)為(G，M，I)的屬性導出必然-可能半三支概念格， 簡稱為ANPSE-概念格．

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

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

圖4 表1的ANPSE-概念格

表3 表1的ANPSE-概念

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

由ANPSE-概念定義， 可得以下結論：

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

4 結語

本文基于多視角信息獲取這一想法， 結合必然算子與可能算子， 從對象或屬性這兩種不同的角度出發， 定義了對象導出與屬性導出必然-可能三支算子， 并結合形式概念分析中半概念的單向對應思想， 獲取了對象導出與屬性導出必然-可能半三支概念， 拓廣了三支概念的語義．

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