基于OE-概念格的形式背景屬性約簡

張呈玲，李進金，林藝東，2

1.閩南師范大學 數(shù)學與統(tǒng)計學院，福建 漳州 363000

2.廈門大學 數(shù)學科學學院，福建 廈門 361000

形式概念分析（Formal concept analysis）是由德國數(shù)學家Wille[1]于1982 年提出的一種建構(gòu)概念格的有力工具。它以形式背景為基礎展開討論，通過對象集和屬性集之間的關系建立一種概念層次關系。這充分體現(xiàn)了概念之間的泛化與特化的關系[2]，同時也體現(xiàn)了概念內(nèi)涵和外延的完美匹配。近年來，形式概念分析已被應用到諸多領域，如機器學習、決策分析等[3-5]。形式背景的屬性約簡理論一直是學術(shù)界的研究熱點。因為這可以獲得更加簡潔的知識。目前為止，已取得豐碩成果。張文修等[3]通過構(gòu)造辨識矩陣提出了概念格屬性約簡方法，及討論了不同類型屬性的特征。王霞等[6]借助不可約元研究了形式背景的對象和屬性約簡。接著，吳偉志等[7]從粒計算的角度提出了形式背景的粒結(jié)構(gòu)，并給出了粒約簡的方法。相較于文獻[3]，此方法無需構(gòu)造概念格可直接通過區(qū)分屬性獲得約簡。同時，形式背景是一個二元關系表，可以被認為是布爾矩陣?；诖?，通過矩陣理論解決形式背景的有關問題已經(jīng)取得了重要的成果[8-13]。李同軍等[8]將布爾矩陣理論應用于形式概念分析中，給出了布爾形式背景的概念及探討了布爾形式概念的計算。張清新等[9]針對對象子集的內(nèi)涵和屬性子集的外延提出了矩陣特征表示方法，并進一步地，利用協(xié)調(diào)集判斷矩陣可探討一個集合是否是協(xié)調(diào)集。接著，林藝東等[10]在文獻[9]的粒矩陣的基礎之上，借助屬性重要度的刻畫，給出了啟發(fā)式的約簡算法。

上述大家熟悉的模型均是二支模型，然而，在實際應用中并非如此。姚一豫等[14]于2009年提出了以“三分而治”思想為主的三支決策理論，即依據(jù)對象特征將論域劃分為正域、負域、邊界域，并對這三個區(qū)域的對象采取適當?shù)牟呗?。針對該理論，祁建軍等[15]引入形式概念分析，給出了三支概念的定義，即對象導出三支概念和屬性導出三支概念。任睿思等[16]從格結(jié)構(gòu)、不可約元、粒計算角度討論了三支概念格的屬性約簡問題。接著，文獻[17]和[18]從粒計算角度，分別討論了對象導出三支概念格的形式背景和決策形式背景的三支粒約簡，且提出了其與二支概念格粒約簡的聯(lián)系。但針對三支概念格，目前較少利用矩陣理論研究三支概念格的屬性約簡。

因此，本文受文獻[10]的啟發(fā)，在文獻[17-18]的約簡框架下，針對對象導出三支概念格的形式背景，借助矩陣理論研究其屬性約簡問題。首先，提出OE-對象粒矩陣。其次，基于此矩陣，刻畫屬性之間的相似度，進而給出屬性的重要度，進一步設計啟發(fā)式屬性約簡的矩陣方法。接著，通過對象導出三支概念格的決策形式背景的引入，從規(guī)則提取的角度說明約簡集對應的三支規(guī)則集更加簡潔。

1 預備知識

1.1 三支概念分析

1.2 布爾矩陣理論

2 基于矩陣的OE-概念格的形式背景屬性約簡

本章基于文獻[16]提出的OE-概念格的屬性約簡理論，并進一步地，探討該理論的矩陣約簡方法。

表1 形式背景K=(U,A,I)Table 1 Formal context K=(U,A,I)

3 基于矩陣的OE-概念格的決策形式背景屬性約簡

4 基于矩陣的對象導出三支概念格的決策形式背景的規(guī)則提取

本章在OE-概念格的三支協(xié)調(diào)決策形式背景下，討論其三支規(guī)則集。下面先給出規(guī)則獲取的概念。

定義12[19]設S=(U,A,I,D,J)是對象三支協(xié)調(diào)的，對于任意(X,(A,B))∈OEL(U,A,I)，若存在(Y,(C,D))∈OEL(U,D,J)(Y≠φ,U)，滿足X?Y，稱A→C是對象導出的三支正決策規(guī)則；同時，notB→ notD是對象導出的三支負決策規(guī)則。并記所有三支正規(guī)則的集合為PR(S)，所以三支負規(guī)則集合記為NR(S)。其全體三支規(guī)則集合用OE(S)。

設S是對象三支協(xié)調(diào)的，若兩個三支正決策規(guī)則A→B和A′→B′滿足條件A?A′，B?B′，稱A→B蘊含A′→B′；同樣地，若兩個負決策規(guī)則notC→not和notC′→notD′滿足條件C?C′，D?D′，稱notC→notD蘊含notC′→notD′。

例5針對表2 中的OE-概念格決策形式背景S=(U,A,I,D,J)，借助圖1和圖2及定義12，表3給出所有的三支規(guī)則集OE(S)。

表2 決策形式背景S=(U,A,I,D,J)Table 2 Formal decision context S=(U,A,I,D,J)

圖1 對象導出三支概念格OEL(U,A,I)Fig.1 OE three-way concept lattice OEL(U,A,I)

圖2 對象導出三支概念格OEL(U,D,J)Fig.2 OE three-way concept lattice OEL(U,D,J)

結(jié)合圖2 和圖3，約簡集red={a3,a6}對應的決策形式背景Sred的三支規(guī)則集如表4所示。

圖3 對象導出三支概念格OEL(U,red,Ired)Fig.3 OE three-way concept lattice OEL(U,red,Ired)

由表3 和表4 的分析可知，在OEG 粒約簡集red={a3,a6} 對應的決策形式背景Sred=(U,Ared,Ired,D,J) 的三支規(guī)則集蘊含原決策形式背景S=(U,A,I,D,J)的三支規(guī)則集。并且，OEG 粒約簡的決策形式背景中的三支規(guī)則更加簡潔。

表3 例3的三支規(guī)則集OE(S)Table 3 Three-way decision rule of example 3 OE(S)

表4 例4的三支規(guī)則集OE(Sred)Table 4 Three-way decision rule of example 4 OE(Sred)

5 實驗分析

本章將通過仿真實驗驗證所提出方法的有效性。實驗環(huán)境是在Windows 10及Intel?Core?i5-6200UCPU@2.3 GHz，8.0 GB內(nèi)存。仿真實驗所用的軟件Matlab 9.3。

5.1 收集數(shù)據(jù)

設K1、K2為兩個形式背景，稱[K1K2] 為K1、K2的組合，為K1、K2的串聯(lián)，為K1、K2的合并[20]。

S1和S7分別是表5 和表6 的決策形式背景，如表7所示。S2是S1的90 倍串聯(lián)；S3是S1的5 倍合并、9 倍串聯(lián)；S4是S2的6 倍組合；S5是S1的7 倍組合，70 倍串聯(lián)；S6是由S3的4 倍組合與S1的5 倍串聯(lián)、20 倍組合串聯(lián)形成。由上述方法，經(jīng)S7相應的組合、串聯(lián)、合并得到S8、S9、S10、S11。

表5 決策形式背景S1=(U,A,I,D,J)Table 5 Formal decision context S1=(U,A,I,D,J)

表6 決策形式背景S7=(U,A,I,D,J)Table 6 Formal decision context S7=(U,A,I,D,J)

表7 實驗數(shù)據(jù)Table 7 Experimental data

5.2 實驗比較

通過比較算法2（HOGR）與文獻[18]約簡理論（記為OER）之間的差異。值得注意的是，文獻[18]借助辨識矩陣可以得出所有的約簡集。為了便于比較，算法OER求決策形式背景下的一個極小約簡。兩者算法的約簡個數(shù)及運行時間如表8所示。

表8 實驗結(jié)果比較Table 8 Comparison of experimental results

根據(jù)表8可知，算法HOGR和OER在每個數(shù)據(jù)集上的約簡個數(shù)相同，但是HOGR 在計算約簡集的時間比OER 的運行時間短。因此，從運行時間角度，算法HOGR比OER輸出約簡集更具優(yōu)越性。

6 結(jié)束語

本文研究了OE-概念格的形式背景的啟發(fā)式屬性約簡方法。首先根據(jù)三支算子的定義，借助矩陣理論，給出了OE-對象粒矩陣。然后，在保持OE-對象粒矩陣不變的前提下，探討屬性之間的相似性及給出內(nèi)外重要度的概念，接著設計啟發(fā)式的約簡算法。其次，將上述理論結(jié)果應用于OE-概念格的決策形式背景，給出核心屬性的判定條件，且設計了基于矩陣的啟發(fā)式算法。最后，從規(guī)則提取的角度得出了OEG 粒約簡集所對應的三支規(guī)則集將更加簡潔。未來可以在本文的基礎上進一步地研究基于屬性導出三支概念格屬性約簡的矩陣方法。