決策形式背景基于OE-協調性的屬性約簡

常麗娜 魏玲 彭超林

摘要 屬性約簡作為形式概念分析中非常重要的一個研究分支，在三支概念分析中也同樣重要?；趯ο髮С鋈Ц拍罡?，提出了保持決策形式背景OE-協調性的屬性約簡理論，豐富了三支概念分析的約簡理論。首先，定義了決策形式背景的OE-協調集和OE-約簡，并將屬性按其特征分為3類。其次，指出OE-約簡的本質就是極小OE-協調集，給出了OE-協調集的幾個判定定理，通過研究OE-協調集的充要條件，獲取OE-約簡的判定定理。最后，給出OE-差別矩陣和OE-差別函數的定義，并給出了利用OE-差別矩陣和OE-差別函數計算OE-約簡的方法。

關鍵詞 三支概念分析;屬性約簡;OE-協調性;決策形式背景;對象導出三支概念格

Attribute reduction in formal decision contextsbased on OE-consistency

Abstract Attribute reduction， as a very important branch of formal concept analysis， is equally important in the three-way concept analysis. Based on object-induced concept lattices， attribute reduction theory which preserve OE-consistency of formal decision contexts is proposed， which enriches the reduction theory of three-way concept analysis. Firstly， OE-consistent set and OE-reduct of formal decision contexts are defined， and the attributes are classified into three categories according to their characteristics. Then， it is pointed out the essence of OE-reduct is minimal OE-consistent set， and several judgement theorems of OE-consistent set are given. By studying the necessary and sufficient conditions of OE-consistent set， judgement theorem of OE-reduct is obtained. Finally， the definition of OE-discernibility matrix and OE-discernibility function are given， and the method of calculating OE-reduct by using OE-discernibility matrix and OE-discernibility function is given.

Keywords three-way concept analysis; attribute reduction; OE-consistency; formal decision contexts; object-induced three-way concept lattices

形式概念分析［1-2］（formal concept analysis， FCA）作為數據分析與知識發現的有力工具， 是由德國數學家Wille于1982年提出的， 并被廣泛應用于機器學習、沖突分析等很多領域［3］。

在經典形式概念分析的基礎上， Qi等結合三支決策理論［4］（three-way decision， 3WD）于2014年提出了三支概念分析［5-6］（three-way concept analysis， 3WCA）， 既體現了三支決策的思想和應用價值， 也是經典形式概念分析的一種擴展， 能同時反映“共同具有”和“共同不具有”兩種信息。目前， 三支概念分析已經得到了很多學者的關注和認可， 研究成果也越來越豐富。Ren等研究了兩類三支概念格的4種屬性約簡問題， 并討論了它們之間的關系［7］。Yu等通過考慮三支概念格（三支粗概念格）的原子、不可約元和補的性質， 研究了三支概念格（三支粗概念格）的性質，在具有這些特殊性質的完備格與三支概念格（三支粗概念格）之間建立了一個同構映射［8］。Zhi等提出了三支對偶概念格， 探討了三支對偶概念格與經典對偶概念格的關系， 研究了三支概念格、三支對偶概念格、三支面向對象概念格和三支面向屬性概念格4種類型的三支概念分析模型之間的關系［9］。Yang等引入一對組合算子， 提出了一種構造屬性誘導三支概念格和對象誘導三支概念格的新方法［10］。Zhao等對三支算子的性質重新表述，研究了不同類型的三支概念格之間的關系［11］。

決策形式背景［12］這一概念是由魏玲提出的， 隨之決策形式背景的知識發現成為FCA的研究熱點。決策形式背景只有在滿足一定的協調意義下， 對其的知識發現才更具合理性。Wei等定義了決策形式背景的強、弱協調性， 并在此基礎上研究了兩種協調意義下的屬性約簡［13］。Li等對決策形式背景的屬性約簡與規則獲取進行了較為系統深入的研究［14-15］。Chen等研究了大規模決策形式背景的屬性約簡問題，提出了一種計算決策形式背景差別矩陣簡單有效的方法［16］。作為形式概念分析的擴展， 決策形式背景的知識發現在三支概念分析中同樣重要。陳雪等基于AE-概念格， 研究了決策形式背景的保持非冗余規則信息不變的屬性約簡問題［17］。林洪等研究了三支粒協調決策形式背景的粒約簡問題［18］。劉琳等基于AE-概念格研究了決策背景的規則提取問題［19-20］。Wei等基于兩類三支概念格定義了決策形式背景的OE-協調性和AE-協調性， 研究了三支規則提取問題［21］。Long等基于三支概念格研究了不完備決策背景的規則獲取問題［22］。

決策形式背景在滿足一定的協調意義下，其知識發現才更具合理性和可解釋性，因此，研究決策形式背景不同的協調性，可以挖掘出一個決策背景更多的信息與細節。本文根據文獻［20］提出的決策形式背景的OE-協調性的定義， 基于對象導出三支概念格，研究決策形式背景保持OE-協調性的屬性約簡理論， 并通過實例表明協調集判定定理及約簡計算方法的有效性。

1 預備知識

1.1 形式概念分析

將形式背景（G，M，I）的概念的全體記為L（G，M，I），對于任意的（X1，A1），（X2，A2）∈L（G，M，I）， 它們的偏序關系為

進一步， 定義任意兩個概念的下確界和上確界為

則L（G，M，I）形成一個完備格，稱為概念格。

1.2 三支概念分析

下面給出三支算子的概念。

記形式背景（G，M，I）的所有OE-概念構成的集合為OEL（G，M，I），所有OE-概念外延構成的集合為OELE（G，M，I）。對于任意的（X1，（A1，B1）），（X2，（A2，B2））∈OEL（G，M，I）， 定義它們的偏序關系為

如果（X1，（A1，B1））≤（X2，（A2，B2））且（X1，（A1，B1））≠（X2，（A2，B2））， 則記為（X1，（A1，B1））<（X2，（A2，B2））。如果（X1，（A1，B1））<（X2，（A2，B2））， 且不存在OE-概念（X，（A，B））使得（X1，（A1，B1））<（X，（A，B））<（X2，（A2，B2））成立， 則稱（X1，（A1，B1））是（X2，（A2，B2））的子概念， （X2，（A2，B2））是（X1，（A1，B1））的父概念， 記作（X1，（A1，B1））（X2，（A2，B2））。其中，任意兩個OE-概念的下確界和上確界為

則OEL（G，M，I）是一個完備格，稱為對象導出三支概念格，簡記為OE-概念格。

2 決策形式背景的屬性約簡

2.1 OE-協調性與屬性約簡的相關定義

本節首先介紹決策形式背景OE-協調性的定義， 然后給出保持決策形式背景OE-協調性的協調集和約簡的定義。

定義4［20］ ?如果（G，M，I）和（G，N，J）是形式背景， M∩N=， 則稱五元組（G，M，I，N，J）為一個決策形式背景， 其中M稱為條件屬性集， N稱為決策屬性集。背景（G，M，I）的對象導出三支概念格記為OEL（G，M，I）， 背景（G，N，J）的對象導出三支概念格記為OEL（G，N，J）。如果對于任意（Y，（E，F））∈OEL（G，N，J）， 總存在（X，（A，B））∈OEL（G，M，I）， 使得X=Y，則稱OEL（G，M，I）細于OEL（G，N，J）， 記作OEL（G，M，I）≤OEL（G，N，J）， 且稱決策形式背景（G，M，I，N，J）是對象導出三支協調的， 簡稱為OE-協調的。

定義6 設OE-協調的決策形式背景（G，M，I，N，J）的所有OE-約簡為｛Di|Di是約簡，i∈τ｝（τ為一個指標集）， 則條件屬性集M中的屬性可分為以下3類：

定理1 設決策形式背景（G，M，I，N，J）是OE-協調的， 則其OE-約簡一定存在。

證明 因為（G，M，I，N，J）是OE-協調的， 故M是OE-協調集， 若m∈M， 都有（G，M-｛m｝，IM-m，N，J）不是OE-協調的， 則M就是OE-約簡。若m∈M， 使得（G，M-｛m｝，IM-m，N，J）是OE-協調的， 令M1=M-｛m｝， 則M1是OE-協調集， 若m1∈M1， 都有（G，M1-｛m1｝，IM1-m1，N，J）不是OE-協調的， 則M1是OE-約簡;否則， 再進一步研究M1-｛m1｝。重復上述過程， 由于M是有限集， 所以至少可以找到決策形式背景（G，M，I，N，J）的一個OE-約簡， 故OE-約簡必存在。

例1 表1給出了一個決策形式背景（G，M，I，N，J）。其中對象集G=｛1，2，3，4｝， 條件屬性集為M=｛a，b，c，d，e，f｝， 決策屬性集為N=｛g，h，i｝。

背景（G，M，I）共有13個對象導出三支概念， 分別標為TCi（i=1，2，…，13）， 其對象導出三支概念格OEL（G，M，I）如圖1所示;背景（G，N，J）共有10個對象導出三支概念， 其對象導出三支概念格OEL（G，N，J）如圖2所示。

容易判斷，OEL（G，M，I）≤OEL（G，N，J）， 所以該決策形式背景是OE-協調的。它的OE-約簡共有4個， 分別是D1=｛a，b，e｝， D2=｛a，c，e｝， D3=｛b，d，e｝， D4=｛c，d，e｝。其中OE-核心屬性為e， OE-相對必要屬性為a，b，c，d， 絕對不必要屬性為f。

由例1可知OE-協調的決策形式背景的OE-約簡未必是唯一的。

利用上述定義和定理，得到以下推論。

推論1 OE-核心是OE-約簡OE-約簡唯一。

證明 。（反證法）假設若OE-核心是OE-約簡， 則OE-約簡不唯一。不妨設Dj，Dk均為OE-約簡， 且Dj≠Dk。那么OE-核心∩i∈τDiDj∩DkDj， 由于Dj是OE-約簡， 而∩i∈τDiDj， 即∩i∈τDi是Dj的真子集， 所以OE-核心∩i∈τDi不可能是OE-約簡， 與已知條件矛盾， 故假設不成立。因此， 如果OE-核心是OE-約簡， 則OE-約簡唯一。

顯然成立。

推論2 m∈M是OE-不必要屬性M-｛m｝是OE-協調集。

推論3 m∈M是OE-核心屬性M-｛m｝不是OE-協調集。

2.2 OE-協調集判定定理

因為決策形式背景上的OE-約簡D滿足以下兩個條件：首先， D是OE-協調集;其次， 對于任意的d∈D，D-｛d｝不是OE-協調集。即OE-約簡的本質就是極小OE-協調集。因此， 只要對OE-協調集的充要條件研究透徹， 就能獲得OE-約簡的判定方法。下面給出OE-協調集的幾個充要條件， 即OE-協調集判定定理。

證明 必要性。由定理2必要性的證明可得。

證明 必要性。由定理3可證。

定理5 （OE-協調集判定定理4）設（G，M，

證明 必要性。由定理2可證。

上面給出了4個關于決策形式背景（G，M，I，N，J）的OE-協調集等價命題（定理2～5）， 均可作為一個條件屬性子集D是否為決策背景的OE-協調集的判定方法。但是對于具體決策形式背景而言， 定理2、3的理論意義更強， 定理4、5的可操作性更強。由于只考慮決策屬性集N×N中的元素， 因此，實際判斷時多選用定理5。

由定理5及OE-約簡的定義易得OE-約簡的判定方法。

例2 （續例1）針對表1所示的決策形式背景（G，M，I，N，J）， 下面根據定理5對任意選取的條件屬性子集是否為OE-協調集進行判斷，若條件屬性子集為OE-協調集，進一步利用定理6判斷其是否為OE-約簡。

設D=｛a，b，e，f｝， 已知N=｛g，h，i｝， 由于

其中，D滿足定理5， 所以D是OE-協調集。進一步， D1=D-｛f｝=｛a，b，e｝也是OE-協調集， 所以D不是OE-約簡。而D1的所有真子集｛a， b｝， ｛a， e｝， ｛b， e｝均不是OE-協調集， 所以D1是OE-約簡。同理， 可判定D2=｛a，c，e｝， D3=｛b，d，e｝， D4=｛c，d，e｝均為OE-約簡， 與例1所得結果一致。

定理7 （OE-協調集判定定理5）設（G，M，I，N，J）為OE-協調的決策形式背景， 則D是OE-協調集的充要條件是

所以有

故

2.3 約簡方法

下面介紹差別矩陣和差別函數的定義，通過差別矩陣和差別函數的方法可以得到OE-協調決策形式背景的OE-約簡。

定義7 設（G，M，I，N，J）為OE-協調決策形式背景， （Xi，（Ai，Bi）），（Xj，（Aj，Bj））∈OEL（G，M，I）， 稱

為（Xi，（Ai，Bi））與（Xj，（Aj，Bj））的OE-差別屬性集。稱

ΛOEL=（DISOE（（Xi，（Ai，Bi）），

（Xj，（Aj，Bj））），（Xi，（Ai，Bi）），

（Xj，（Aj，Bj））∈OEL（G，M，I）

為該OE-協調決策形式背景的OE-差別矩陣。

例3 （續例1）根據定義7， 表2給出了例1中決策形式背景（G，M，I，N，J）的OE-差別矩陣ΛOEL。其中， 矩陣第i行第j列代表的是OE-條件概念TCi與TCj的差別屬性集DISOEL（TCi， TCj）。

為敘述方便，將OE-差別矩陣中的元素稍作變換， 若DISOEL（（X，（A，B）），（Y，（C，D）））=（E，F）， 則重新記DISOEL（（X，（A，B）），（Y，（C，D）））為H=E∪F， 依然用ΛOEL來表示決策背景（G，M，I，N，J）的OE-差別矩陣。

定理8表明， OE-協調的決策形式背景的協調集與差別矩陣的每個元素相交都非空， 而約簡就是找滿足這些條件的協調集中的極小集合。

定義8 設（G，M，I，N，J）為OE-協調決策形式背景， 則其OE-差別函數為

根據∧，∨的運算律， 差別函數f可以變換為最小析取范式， 這個最小范式的所有合取式就是OE-協調的決策形式背景（G，M，I，N，J）的全部OE-約簡。

例4 （續例1）求例1中決策形式背景（G，M，I，N，J）的OE-差別函數。

決策形式背景（G，M，I，N，J）共有4個約簡，分別是D1=｛a，b，e｝，D2=｛a，c，e｝，D3=｛b，d，e｝，D4=｛c，d，e｝， 與例1所得結果相同。

3 結語

本文基于對象導出三支概念格， 在OE-協調的決策形式背景下， 首先定義了OE-協調集和OE-約簡； 其次，給出了OE-協調集的幾個判定定理和OE-約簡的判定定理； 最后，給出了利用差別矩陣和差別函數求OE-約簡的計算方法。對于OE-協調的決策形式背景， OE-約簡也是保持OE-非冗余規則信息不丟失的約簡， 所以本文提出的OE-協調集的判定定理也是保持OE-非冗余規則信息不丟失的協調集判定定理， 豐富了三支概念分析的內容。

研究決策形式背景的屬性約簡理論是十分有意義的， 在約簡后的決策背景上進行知識的更新與獲取， 既能保證知識的完整性， 也更加精煉。本文是從對象導出三支概念格出發，研究了決策形式背景保持OE-協調性的屬性約簡問題，下一步還可從屬性導出三支概念格出發來研究決策屬性背景的保持AE-協調性的約簡問題。

參考文獻

［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］ GANTER B， WILLE R. Formal concept analysis： Mathematical foundations ［M］.Berlin： Springer-Verlag， 1999.

［3］ ZHI H L， QI J J， QIAN T， et al.Conflict analysis under one-vote veto based on approximate three-way concept lattice［J］. Information Sciences， 2020， 516： 316-330.

［4］ YAO Y Y. An outline of a theory of three-way decisions ［C］∥Rough Sets and Current Trends in Computing. Berlin： Springer， 2012： 1-17.

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

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

［7］ REN R S， WEI L. The attribute reductions of three-way concept lattices ［J］.Knowledge-Based Systems， 2016， 99： 92-102.

［8］ YU H Y， LI Q G， CAI M J. Characteristics of three-way concept lattices and three-way rough concept lattices［J］.Knowledge-Based Systems， 2018， 146： 181-189.

［9］ ZHI H L， QI J J， QIAN T， et al. Three-way dual concept analysis［J］.International Journal of Approximate Reasoning， 2019， 114： 151-165.

［10］YANG S C， LU Y N， JIA X Y， et al. Constructing three-way concept lattice based on the composite of classical lattices［J］.International Journal of Approximate Reasoning， 2020， 121： 174-186.

［11］ZHAO X R， MIAO D Q， HU B Q. On relationship between three-way concept lattices［J］.Information Sciences， 2020， 538： 396-414.

［12］魏玲. 粗糙集與概念格的約簡理論與方法［D］.西安： 西安交通大學， 2005.

［13］WEI L， QI J J， ZHANG W X. Attribute reduction theory of concept lattice based on decision formal contexts ［J］.Science in China Series F： Information Sciences， 2008， 51（7）： 910-923.

［14］LI J H， MEI C L， LYU Y J. Knowledge reduction in decision formal contexts［J］.Knowledge-Based Systems， 2011， 24（5）： 709-715.

［15］LI J H， MEI C L， WANG J H， et al. Rule-preserved object compression in formal decision contexts using concept lattices ［J］.Knowledge-Based Systems， 2014， 71： 435-445.

［16］CHEN J K， MI J S， XIE B， et al. Attribute reduction in formal decision contexts and its application to finite topological spaces ［J］.International Journal of Machine Learning and Cybernetics， 2021， 12： 39-52.

［17］陳雪， 魏玲， 錢婷. 基于AE-概念格的決策形式背景屬性約簡［J］.山東大學學報（理學版）， 2017， 52（12）： 95-103.

CHEN X， WEI L， QIAN T. Attribute reduction in formal decision contexts based on AE-concept lattices ［J］.Journal of Shandong University （Natural Science）， 2017， 52（12）： 95-103.

［18］林洪， 秦克云. 決策形式背景三支粒約簡［J］.計算機科學， 2018， 45（10）： 47-50.

LIN H， QIN K Y. Three-way granular reduction for decision formal context ［J］.Computer Science， 2018， 45（10）： 47-50.

［19］劉琳， 錢婷， 魏玲. 基于屬性導出三支概念格的決策背景規則提?。跩］.西北大學學報（自然科學版）， 2016， 46（4）： 481-487.

LIU L， QIAN T， WEI L.Rules extraction in formal decision contexts based on attribute-induced three-way concept lattices ［J］. Journal of Northwest University （Natural Science Edition）， 2016， 46（4）： 481-487.

［20］劉琳， 魏玲， 錢婷. 決策形式背景中具有置信度的三支規則提?。跩］.山東大學學報（理學版）， 2017， 52（2）： 101-110.

LIU L， WEI L， QIAN T. Three-way rules extraction in formal decision contexts with confidence ［J］.Journal of Shandong University （Natural Science）， 2017， 52（2）：101-110.

［21］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.

［22］LONG B H， XU W H， ZHANG X Y. Double threshold construction method for attribute-induced three-way concept lattice in incomplete fuzzy formal context ［J］.The Journal of Engineering， 2020（13）： 549-554.