基于背景間運算的部分已知概念構造

田雪 任睿思

摘要 概念是利用形式概念分析進行知識獲取的基礎。在不完備形式背景中，為了表達“一定具有”以及“可能具有”的關系，概念的外延或內涵通常以區間集的形式表達，稱這樣的概念為部分已知概念。由部分已知概念的定義可知，其本質與不完備背景的最小和最大完備化有關，因而考慮對最小和最大完備化背景進行運算來尋找部分已知概念。通過將不完備形式背景的最小完備化與最大完備化分別進行并置和疊置構造兩個新背景，其概念格分別同構于SE-ISI概念格和ISE-SI概念格，從而提出了構建SE-ISI概念格和ISE-SI概念格的新方法。對于ISE-ISI概念，使用不完備形式背景的最小與最大完備化的直和運算構造了新的形式背景，基于此背景提出了尋找ISE-ISI概念的方法。

關鍵詞 不完備形式背景;部分已知概念;并置;疊置;直和

Construction of partially-known formal concepts basedon operations of formal contexts

Abstract Concepts are the foundation for knowledge acquisition through formal concept analysis. In incomplete formal contexts， in order to express “jointly must possessing （possessed）” and “jointly might possessing （possessed）”relationships， the extent or intent of concepts is usually expressed in the form of interval set. We refer to such concepts as partially-known formal concepts. From the definition of partially-known formal concepts， it can be seen that their essence is related to the least and greatest completions of incomplete formal contexts. Therefore， we consider performing operations on the least and greatest completions of incomplete formal contexts to find partially-known formal concepts. We construct two new formal contexts based on the apposition and subposition of the least and greatest completions. Their concept lattices are isomorphic to the SE-ISI concept lattice and the ISE-SI concept lattice， respectively. Therefore， the new methods for constructing SE-ISI concept lattice and ISE-SI concept lattice are proposed. For the ISE-ISI concept， we use direct sum operation of the least and greatest completions to construct a new formal context， and propose a method to search for the ISE-ISI concepts.

Keywords incomplete formal context; partially-known formal concept; apposition; subposition; direct sum

德國數學家Wille提出的形式概念分析（formal concept analysis， FCA）［1］是進行數據庫知識發現的重要工具。通過在背景上獲取概念及其對應的概念格結構，可以進行屬性約簡［2-3］，規則獲?。?］等研究，從而獲取有用的知識。近年來，FCA與其他理論的融合研究［5-8］為基于形式概念的知識獲取提供了更加豐富的理論支撐。

經典的形式背景包含了原始數據的所有信息，其上的知識是確定且完備的，在此基礎上容易建立結構清晰的概念格，研究知識獲取問題相對容易，但在數據不完整的情況下，研究相應問題就比較困難了。在不完備形式背景中，任一對象和屬性間的關系有3種可能的情況：確定具有、確定不具有和不確定是否具有。因此，不完備背景中概念的定義、表達方式與完備背景中的概念有很大差異。

形式背景是一種理想狀態下的數據表現，但在現實生活中由于數據獲取較困難、記錄不當等原因，往往存在數據缺失的情況，部分對象和屬性之間的關系無法確定，從而導致形式背景的不完備性。在這種情況下，若簡單地將缺失信息進行刪除或補全，勢必會導致知識獲取的不確定性。因此，從不完備背景本身出發，對區間集形式的部分已知概念進行研究是有意義的。

Burmeister和Holzer受可能世界理論的啟發提出了不完備形式背景，并且將模態算子引入不完備形式背景中［9］。Djouadi等從不完備背景的最小和最大完備化出發，提出了ill-known形式概念［10］。Li等提出了近似概念，其外延是一個對象集，內涵是一對屬性集，并證明了一個不完備背景的所有近似概念形成一個完備格［11］。Li和Wang將三支決策應用到不完備背景中，并研究了屬性約簡問題［12］。Yao將區間集理論引入到不完備形式背景中，定義了3類部分已知概念：SE-ISI概念、ISE-SI概念和ISE-ISI概念［13］。Ren等進一步研究了部分已知概念的結構［14］。Zhi等考慮了不具有關系，對部分已知概念進行了擴展［15］。對于部分已知概念的研究目前主要集中在對其定義、性質以及結構的討論，并未探討其構造問題，本文通過考慮背景間的運算研究了部分已知概念的構造。

在三支概念分析領域，Qian等提出了基于背景的并置和疊置構造三支概念格的新方法［16］。受此啟發，本文將其應用到不完備背景中尋找部分已知概念。由于不完備形式背景可以被等價刻畫為一個下界和上界分別為最小完備化以及最大完備化的區間集，而部分已知概念的獲取算子與最小完備化和最大完備化上的經典導出算子之間具有一致性，所以通過對最小完備化與最大完備化使用不同的放置方式構造新的形式背景，在新背景上構造經典形式概念，即可獲取部分已知概念。

本文首先給出了不完備背景上部分已知概念的基礎知識，然后通過將不完備背景的最小完備化與最大完備化進行并置和疊置構造新的背景，并證明了此背景下的經典形式概念格分別與SE-ISI概念格和ISE-SI概念格同構，從而提出了構建SE-ISI概念格和ISE-SI概念格的方法。對于ISE-ISI概念，通過將不完備背景的最小和最大完備化進行直和運算構造了新的形式背景，基于此背景提出了構造ISE-ISI概念的方法。最后，總結了文章的內容并提出了未來可以進一步研究的問題與方向。

1 預備知識

本節給出形式概念分析、不完備形式背景及其上部分已知概念的基礎知識。

定義1［17］ 稱K=（OB，AT，I）為一個形式背景。其中：OB={o1，o2，…，op}為對象集，每個oi （i≤p）稱為一個對象；AT={a1，a2，…，aq}為屬性集，每個aj （j≤q）稱為一個屬性；I為OB和AT之間的二元關系，IOB×AT。若（o，a）∈I，則表示對象o具有屬性a，記為oIa。

其中：σ（O）表示O中所有對象共同具有的屬性集合；τ（A）表示共同具有A中所有屬性的對象集合。如果一個二元組（O，A）滿足σ（O）=A，且τ（A）=O，則稱（O，A）是一個形式概念，簡稱概念。O和A分別稱為概念（O，A）的外延和內涵。

在形式背景K=（OB，AT，I）的所有概念構成的集合上定義偏序關系和上、下確界就可以形成一個完備格，稱之為形式背景K的概念格，記為L（K）。

（o，a，+）∈J表示對象o具有屬性a；

（o，a，-）∈J表示對象o不具有屬性a；

（o，a，？）∈J表示不確定對象o是否具有屬性a。

一個完備的形式背景可以看作不完備背景的特殊情況，即完備背景中不含有“？”關系。

例1 表1為一個不完備形式背景IK=（OB，AT，{+，？，-}，J）。其中：OB={1，2，3，4}為對象集；AT={a，b，c，d，e}表示屬性集。表中（1，a）處的“+”表示對象1具有屬性a；（1，b）位置上的“-”表示對象1不具有屬性b；（1，c）處的“？”表示不確定對象1是否具有屬性c。若將其中的“？”全部替換為“+”或“-”，表1就變成了一個完備背景。

在不完備背景中，無法通過常規導出算子實現對象集和屬性集之間的推導，于是有了上界導出算子和下界導出算子的定義。

定義4［9］ 設IK=（OB，AT，{+，？，-}，J）是一個不完備背景，K=（OB，AT，I）是一個完備背景，若I滿足下列條件：

則稱K為IK的一個完備化。

由定義4可知，完備化背景中的二元關系I可以通過將不完備背景中的每個“？”替換為“+”或“-”得到。一個不完備形式背景具有多種完備化結果，可以用COMP（IK）表示不完備背景IK的所有完備化的集合。在不完備背景的多種完備化背景中，有兩個背景較為特殊，下面給出了最小和最大完備化的定義。

定義5［10］ 給定一個不完備形式背景IK=（OB，AT，{+，？，-}，J），其最小完備化和最大完備化分別定義如下：

K*=（OB，AT，I* ）；K*=（OB，AT，I* ）。

其中：I*={（o，a）|（o，a，+）∈J}；I*={（o，a）|（o，a，+）∈J}∪{（o，a）|（o，a，？）∈J}。

例2 表2和表3分別是表1所示背景對應的最小完備化K*與最大完備化K*?？梢钥闯?，二元關系I*實際上是將所有“？”替換為“-”得到的，I*是將所有“？”換為“+”得到的。

令UP={（o，a）|（o， a， ？）∈J}表示不完

下面的定理給出了不完備形式背景中的上、下界導出算子與最小完備化和最大完備化中的導出算子之間的關系。

定理1［13］ 在不完備背景中，有

其中：（σK*，τK*）是最小完備化K*=（OB，AT，I*）上的導出算子對;（σK*，τK*）是最大完備化K*=（OB，AT，I*）上的導出算子對。

該定理表明，下界導出算子和上界導出算子分別是最小完備化和最大完備化上的導出算子。因此，上、下界導出算子具有常規導出算子的所有性質。

使用上述兩個算子可以實現從集合到區間集的轉換，即將對象集映射為屬性區間集，將屬性集映射為對象區間集。而下面定義的兩個算子可以將一個對象區間集映射為一個屬性集，將一個屬性區間集映射為一個對象集。

則被稱為具有外延區間集和內涵集的部分已知形式概念，簡稱為部分已知ISE-SI形式概念。

在給出部分已知概念格的偏序關系及其上、下確界的定義之前，先說明區間集中偏序關系和交、并運算是如何定義的。給定兩個區間集［A，B］和［C，D］，偏序關系定義為

交運算和并運算分別定義為

［A，B］∩［C，D］=［A∩C，B∩D］，

［A，B］∪［C，D］=［A∪C，B∪D］。

記IK上所有的SE-ISI概念形成的偏序集為LSE-ISI（IK），是一個完備格，其中偏序關系定義為

下確界和上確界分別定義為

記IK上所有的ISE-SI概念形成的偏序集為LISE-SI（IK），它是一個完備格，其中偏序關系定義為

下確界和上確界分別定義為

（［X1，X2］，Y）∧（［U1，U2］，V）=

（［X1，X2］∩［U1，U2］，

定理3［10］ 在不完備形式背景中，如果一對對象區間集和屬性區間集（［O*，O*］，［A*，A*］）滿足如下條件：

2） （O*，A*）是K*=（OB，AT，I*）中的一個形式概念，即σK*（O*）=A*，τK*（A*）=O*；

3） （O*，A*）是K*=（OB，AT，I*）中的一個形式概念，即σK*（O*）=A*，τK*（A*）=O*，

則稱（［O*，O*］，［A*，A*］）為一個部分已知ISE-ISI概念。

該定理是對ISE-ISI概念的構造性解釋，即一個ISE-ISI概念由兩個形式概念組成，這兩個概念分別來自最小完備化K*和最大完備化K*。

記IK上所有的ISE-ISI概念形成的偏序集為LISE-ISI（IK）是一個完備格，其中偏序關系定義為

下確界和上確界分別定義為

例3 （續例1）對于表1表示的不完備形式背景IK，可以根據定義7和定理3尋找其上的3類部分已知概念。如令O=｛1，3｝，則

故（13，［a，ac］）是一個SE-ISI概念。

類似地，取A=｛a，c｝，則

故（［3，13］，ac）是一個ISE-SI概念。

2 基于背景的并置構造SE-ISI概念格

本節將通過不完備背景的最小完備化與最大完備化的并置構造具有與SE-ISI概念格同構的概念格的形式背景，進而使用構造概念格的經典方法構造SE-ISI概念格。

定義8［17］ ?設K=（OB，AT，I），K1=（OB1，AT1，I1），K2=（OB2，AT2，I2）是形式背景。記OB′j=｛j｝×OBj，AT′j=｛j｝×ATj及I′j=｛（（j，o），（j，a））|（o，a）∈Ij｝。其中，j∈｛1，2｝。若OB=OB1=OB2，則K1|K2=（OB，AT′1 ∪AT′2，I′1 ∪I′2 ）稱為K1與K2的并置。一般地，若OB=OB1=OB2，且AT1∩AT2=，則K1|K2=（OB，AT1∪AT2，I1∪I2）也稱為K1與K2的并置。

下面將K*和K*并置構造一個新的形式背景，基于新的形式背景建立SE-ISI概念格。

設不完備背景IK=（OB，AT，｛+，？，-｝，J）的最小和最大完備化分別為K*=（OB，AT，I*）和K*=（OB，AT，I*），為了區分兩個背景上的屬性，現對K*和K*中的屬性集分別添加標簽｛1｝和標簽｛2｝，定義兩個新的形式背景。

定理4 假設K*和K*分別為不完備形式背

證明 對任意（O，A）∈L（K0），定義φ（O，A）=（O，［A1，A2］）。其中：A1=｛x|（1，x）∈A｝；A2=｛x|（2，x）∈A｝。下證φ是L（K0）與LSE-ISI（IK）間的同構映射。

1）證明φ是一個映射，即證對任意的（O，A）∈L（K0），都有φ（O，A）=（O，［A1，A2］）∈LSE-ISI（IK）。

綜上可知，（O，［A1，A2］）∈LSE-ISI（IK），即φ：L（K0）→LSE-ISI（IK）是映射。

2）證明φ是雙射，即證φ既是單射又是滿射。首先，對于任意的（X，Y），（U，V）∈L（K0）且（X，Y）≠（U，V），有X≠U，Y≠V。因而（X，［Y1，Y2］）≠（U，［V1，V2］），即φ（X，Y）≠φ（U，V），因此，φ是單射。其次，證明φ是滿射。即對任意的（O，［A1，A2］）∈LSE-ISI（IK），定義A=（｛1｝×A1）∪（｛2｝×A2），有（O，A）∈L（K0），且φ（O，A）=（O，［A1，A2］）。對于任意（m，n）∈A，分兩種情況討論。

a） （m，n）∈｛1｝×A1，即m=1，n∈A1。因為（O，［A1，A2］）∈LSE-ISI（IK），故OI*=A1，OI*=A2，且O=AI*1 ∩AI*2，從而n∈OI*。因而對任意的o∈O，n∈oI*，由～的定義可知o～（1，n），由o的任意性可知（1，n）∈O～。

a） （m，n）=（1，n），由～的定義知n∈oI*，由o的任意性知n∈OI*，又因為OI*=A1，故n∈A1，因而（m，n）=（1，n）∈｛1｝×A1A。

b） （m，n）=（2，n），同理有（2，n）∈A。

綜上所述，L（K0）與LSE-ISI（IK）同構。

由定理4可以得到定理5，該定理提出了一種尋找SE-ISI部分已知概念的方法。

例4 表1所示不完備形式背景所對應的最小完備化K*，最大完備化K*，帶屬性標簽的最小完備化*，帶屬性標簽的最大完備化*， 以及其并置K0， 分別如表2～6所示，圖1為K0的概念格。 以概念C∈L（K0）為例來解釋定理5， 由于C=（13，｛（1，a），（2，a），（2，c）｝）∈L（K0），所以有O=｛1，3｝，A1=｛a｝，A2=｛a，c｝，于是概念C所對應的SE-ISI概念為（13，［a，ac］）。通過對L（K0）中所有概念進行轉換，就可以得到不完備背景IK的SE-ISI概念格，如圖2所示。

3 基于背景的疊置構造ISE-SI概念格

與第2節類似，本節將不完備背景的最小完備化與最大完備化進行疊置來構造具有與ISE-SI概念格同構的概念格的形式背景，基于新形式背景使用構造經典概念格的方法構造ISE-SI概念格。

下面將K*和K*進行疊置得到新的形式背景，基于新的形式背景建立ISE-SI概念格。

設不完備背景IK=（OB，AT，｛+，？，-｝，J）的最小和最大完備化分別為K*=（OB，AT，I*）和K*=（OB，AT，I*）。為了區分兩個背景上的對象，現對K*和K*中的對象集分別添加標簽｛1｝和標簽｛2｝，定義如下兩個新的形式背景。

證明 由于對象集與屬性集之間是對偶的，與第2節證明同理，此處略去。

例5 表7是不完備背景IK所對應的疊置背景K1，圖3為K1的概念格L（K1），以概念F為例解釋定理7。由于F=（｛（1，3），（2，1），（2，3）｝，ac）∈L（K1），因而O1=｛3｝，O2=｛1，3｝，A=｛a，c｝，于是可以得到概念F所對應的ISE-SI概念為（［3，13］，ac）。通過轉換L（K1）的所有概念，就可以得到IK的ISE-SI概念格，如圖4所示。

4 基于背景的直和構造ISE-ISI概念格

本節通過對不完備形式背景IK的最小完備化與最大完備化進行直和運算構造新的背景，從而獲取ISE-ISI概念。

定義10［17］ 設K=（OB， AT， I）， K1=（OB1， AT1， I1）， K2=（OB2，AT2，I2）是形式背景。記OB′j=｛j｝×OBj，AT′j=｛j｝×ATj及I′j=｛（（j，o），（j，a））|（o， a）∈Ij｝。 其中， j∈｛1， 2｝。 則稱K1+K2=（OB′1∪OB′2， AT′1∪AT′2， I′1∪I′2∪（OB′1×AT′2）∪（OB′2×AT′1））為K1與K2的直和。

定理8給出了如何利用不完備背景的最小完備化與最大完備化的直和構造新背景并獲取ISE-ISI概念。在直和運算中，為了區分K*和K*上的對象和屬性，對兩者的對象集和屬性集分別添加標簽｛1｝和標簽｛2｝。

2）類似地，可以證明A2=OI*2，O2=AI*2。

綜上所述，（［O1，O2］，［A1，A2］）是一個ISE-ISI部分已知概念。

5 結語

本文基于形式背景的并置、疊置及直和運算，提出了構造SE-ISI概念格、ISE-SI概念格以及尋找ISE-ISI概念的方法。對于一個形式背景，通過將其最小和最大完備化并置得到一個新的形式背景K0，該背景的經典概念格同構于SE-ISI概念格，對L（K0）中每個概念進行一定的轉換，就可以得到SE-ISI概念格。對偶地，通過將不完備背景的最小和最大完備化疊置，使用經典概念格的構造方法就可以得到ISE-SI概念格。對于ISE-ISI概念，使用背景的直和運算構造了新的形式背景，當該背景中的概念滿足一定條件時，它的概念就可以轉換為ISE-ISI概念。

從定義出發構造部分已知概念涉及到集合與區間集的相互轉換，構造較為復雜，但由部分已知概念的定義可知，其本質與不完備背景的最小和最大完備化有關。因此，考慮從最小和最大完備化出發，使用不同的放置方式構造新背景來獲取部分已知概念。該方法可以將不完備背景上的部分已知概念與完備背景上的形式概念聯系起來，而形式概念的構造已有很豐富的研究成果，這些成果可以指導部分已知概念的構造與獲取。本文雖然通過背景的直和運算將完備背景中的形式概念與不完備背景中的ISE-ISI概念進行了聯系，但是這兩種概念格之間并沒有建立同構映射，即通過背景直和獲取的經典概念必須在滿足一定條件的情況下才能被轉化為ISE-ISI概念。所以在未來的研究中，將繼續深入探究不完備背景下的ISE-ISI概念與經典概念之間的關系，尋找更加有效且直觀的ISE-ISI概念構造方法。

參考文獻

［1］ WILLE R. Restructuring lattice theory： An approach based on hierarchies of concepts ［C］∥RIVAL I. Ordered Sets. Dordrecht-Boston： Reidel， 1982： 445-470.

［2］ QIN K Y， LIN H， JIANG Y T. Local attribute reductions of formal contexts［J］. International Journal of Machine Learning and Cybernetics， 2020， 11（1）： 81-93.

［3］ 張文修， 魏玲， 祁建軍. 概念格的屬性約簡理論與方法［J］. 中國科學E輯：信息科學，2005，35（6）：628-639.

ZHANG W X， WEI L， QI J J. Attribute reduction theory and approach to concept lattice［J］. Science in China Series F： Information Sciences， 2005， 48（6）： 713-726.

［4］ WEI L， LIU L， QI J J， et al. Rules acquisition of formal decision contexts based on three-way concept lattices ［J］. Information Sciences， 2020， 516： 529-544.

［5］ GUO L K， HUANG F P， LI Q G， et al. Power contexts and their concept lattices［J］. Discrete Mathematics， 2011， 311（18/19）： 2049-2063.

［6］ KENT R E. Rough concept analysis： A synthesis of rough sets and formal concept analysis［J］.Fundamenta Informaticae， 1996，27（2）：169-181.

［7］ QI J J， WEI L， YAO Y Y. Three-way formal concept analysis［C］∥Proceedings of Rough Sets and Knowledge Technology. Shanghai： Springer， 2014： 732-741.

［8］ QI J J， QIAN T， WEI L.The connections between three-way and classical concept lattices［J］. Knowledge-Based Systems， 2016， 91： 143-151.

［9］ BURMEISTER P， HOLZER R. On the treatment of incomplete knowledge in formal concept analysis［C］∥Conceptual Structures： Logical， Linguistic， and Computational Issues. Berlin： Springer-Verlag， 2000： 385-398.

［10］DJOUADI Y， DUBOIS D， PRADE H. Différentes extensions floues de l′analyse formelle de concepts［J］. Actes Renc Franc Sur la Logique Floue et ses Applications Cépadues Edn， 2009： 141-148.

［11］LI J H， MEI C L， LV Y J. Incomplete decision contexts： Approximate concept construction， rule acquisition and knowledge reduction［J］. International Journal of Approximate Reasoning， 2013， 54（1）： 149-165.

［12］LI M Z， WANG G Y. Approximate concept construction with three-way decisions and attribute reduction in incomplete contexts［J］. Knowledge-Based Systems， 2016， 91： 165-178.

［13］YAO Y Y. Interval sets and three-way concept analysis in incomplete contexts［J］. International Journal of Machine Learning and Cybernetics， 2017， 8（1）： 3-20.

［14］REN R S， WEI L， YAO Y Y. An analysis of three types of partially-known formal concepts［J］. International Journal of Machine Learning and Cybernetics， 2018， 9： 1767-1783.

［15］ZHI H L， CHAO H. Three-way concept analysis for incomplete formal contexts［J］. Mathematical Problems in Engineering， 2018， 2018：1-11.

［16］QIAN T， WEI L， QI J J. Constructing three-way concept lattices based on apposition and subposition of formal contexts［J］. Knowledge-Based Systems， 2017， 116： 39-48.

［17］GANTER B， WILLE R. Formal concept analysis： Mathematical foundations［M］.New York： Springer， 1999.