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

張呈玲，李進(jìn)金，林藝東，2

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

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

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

上述大家熟悉的模型均是二支模型，然而，在實(shí)際應(yīng)用中并非如此。姚一豫等[14]于2009年提出了以“三分而治”思想為主的三支決策理論，即依據(jù)對象特征將論域劃分為正域、負(fù)域、邊界域，并對這三個(gè)區(qū)域的對象采取適當(dāng)?shù)牟呗浴ａ槍υ摾碚摚罱ㄜ姷萚15]引入形式概念分析，給出了三支概念的定義，即對象導(dǎo)出三支概念和屬性導(dǎo)出三支概念。任睿思等[16]從格結(jié)構(gòu)、不可約元、粒計(jì)算角度討論了三支概念格的屬性約簡問題。接著，文獻(xiàn)[17]和[18]從粒計(jì)算角度，分別討論了對象導(dǎo)出三支概念格的形式背景和決策形式背景的三支粒約簡，且提出了其與二支概念格粒約簡的聯(lián)系。但針對三支概念格，目前較少利用矩陣?yán)碚撗芯咳Ц拍罡竦膶傩约s簡。

因此，本文受文獻(xiàn)[10]的啟發(fā)，在文獻(xiàn)[17-18]的約簡框架下，針對對象導(dǎo)出三支概念格的形式背景，借助矩陣?yán)碚撗芯科鋵傩约s簡問題。首先，提出OE-對象粒矩陣。其次，基于此矩陣，刻畫屬性之間的相似度，進(jìn)而給出屬性的重要度，進(jìn)一步設(shè)計(jì)啟發(fā)式屬性約簡的矩陣方法。接著，通過對象導(dǎo)出三支概念格的決策形式背景的引入，從規(guī)則提取的角度說明約簡集對應(yīng)的三支規(guī)則集更加簡潔。

1 預(yù)備知識

1.1 三支概念分析

1.2 布爾矩陣?yán)碚?/h3>

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

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

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

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

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

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

定義12[19]設(shè)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是對象導(dǎo)出的三支正決策規(guī)則；同時(shí)，notB→ notD是對象導(dǎo)出的三支負(fù)決策規(guī)則。并記所有三支正規(guī)則的集合為PR(S)，所以三支負(fù)規(guī)則集合記為NR(S)。其全體三支規(guī)則集合用OE(S)。

設(shè)S是對象三支協(xié)調(diào)的，若兩個(gè)三支正決策規(guī)則A→B和A′→B′滿足條件A?A′，B?B′，稱A→B蘊(yùn)含A′→B′；同樣地，若兩個(gè)負(fù)決策規(guī)則notC→not和notC′→notD′滿足條件C?C′，D?D′，稱notC→notD蘊(yùn)含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 對象導(dǎo)出三支概念格OEL(U,A,I)Fig.1 OE three-way concept lattice OEL(U,A,I)

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

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

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

由表3 和表4 的分析可知，在OEG 粒約簡集red={a3,a6} 對應(yīng)的決策形式背景Sred=(U,Ared,Ired,D,J) 的三支規(guī)則集蘊(yùn)含原決策形式背景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 實(shí)驗(yàn)分析

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

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

設(shè)K1、K2為兩個(gè)形式背景，稱[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相應(yīng)的組合、串聯(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í)驗(yàn)數(shù)據(jù)Table 7 Experimental data

5.2 實(shí)驗(yàn)比較

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

表8 實(shí)驗(yàn)結(jié)果比較Table 8 Comparison of experimental results

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

6 結(jié)束語

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