概念格在不完備形式背景中的知識(shí)獲取模型

王雯，康向平，武燕

（1. 太原工業(yè)學(xué)院 自動(dòng)化系，山西 太原 030008; 2. 太原理工大學(xué) 信息工程學(xué)院，山西 太原 030024; 3. 同濟(jì)大學(xué)嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室，上海 201804; 4. 同濟(jì)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，上海 201804）

通過模擬人類的概念認(rèn)知思維，Wille[1]教授于1982年在格論基礎(chǔ)上發(fā)展了面向概念建模的概念格理論。作為格論的重要應(yīng)用分支，概念格具有堅(jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)，其中概念、格代數(shù)結(jié)構(gòu)、對(duì)偶伽羅瓦連接等是核心要素。近年來，伴隨著概念格自身理論發(fā)展以及與粗糙集[2-3]、模糊集等的深度融合，其理論體系日趨成熟，應(yīng)用范圍也得到了極大的拓展。

粗糙集無需借助先驗(yàn)知識(shí)，且符合人類的近似思維，易于理解，因此受到了國內(nèi)外學(xué)者的廣泛關(guān)注[4]。近年來，對(duì)于不完備信息的處理，粗糙集已經(jīng)取得了大量的研究成果。把缺失值理解為任何可能值，Kryszkiewicz[5-6]提出了基于容差關(guān)系的拓展粗糙集模型，其中容差關(guān)系滿足自反性和對(duì)稱性，隨后，將缺失值視為不存在或是不允許比較的未知值，Stefanowski[7]提出了基于不對(duì)稱相似關(guān)系(滿足自反性和傳遞性)的粗糙集拓展模型，結(jié)合上述2種模型的優(yōu)點(diǎn)，王國胤[4]進(jìn)一步提出了基于限制容差關(guān)系(滿足自反性和對(duì)稱性)的擴(kuò)充模型，該模型相對(duì)以往模型更加符合實(shí)際，Leung等[8]將極大相容類視為一個(gè)粒，探討了不完備信息系統(tǒng)中的知識(shí)獲取，張文修[9]將不完備信息系統(tǒng)理解為一個(gè)集值信息系統(tǒng)，并探討了面向集值的相容關(guān)系。

目前，關(guān)于不完備信息系統(tǒng)已有大量的研究成果，然而對(duì)于不完備形式背景的分析處理尚處于起步階段[10-16]。從研究對(duì)象來講，形式背景本質(zhì)上是一種特殊的信息系統(tǒng)，它們之間存在著天然聯(lián)系，具有較強(qiáng)的相容性，這也意味著面向不完備信息系統(tǒng)的知識(shí)獲取方法對(duì)于不完備形式背景的處理具有一定的借鑒作用。事實(shí)上，將不完備信息系統(tǒng)中的方法推廣到不完備形式背景中，也是一項(xiàng)非常有意義的研究工作，其不僅能為不完備形式背景的分析處理提供必要的支撐，而且也有助于概念格與粗糙集的理論融合。

考慮到不完備形式背景的普遍性以及經(jīng)典概念格的局限性，在概念格框架體系中，本文融入了粗糙集中的粒化思維，探討了概念格視角下的信息粒化，提出了基于等價(jià)類和基于極大相容類的知識(shí)獲取方法。這些方法一方面有助于概念格與粗糙集的融合，另一方面也為探索不完備形式背景的分析處理機(jī)制提供了有益思路。

1 概念格基本知識(shí)

表1 一個(gè)典型的不完備形式背景Table 1 A typical incomplete formal context

2 概念格與?；治?/h2>

等價(jià)類、極大相容類等是粗糙集中的基本粒。在粒內(nèi)部，不同對(duì)象往往擁有相同的特征和相近的特征值，這就意味著粒內(nèi)部不同對(duì)象之間的特征值是可以相互借鑒的。據(jù)此，本文嘗試在概念格理論框架內(nèi)探討基于二元關(guān)系的信息?；?。

二元關(guān)系與形式背景存在著天然聯(lián)系，它們之間可以相互表示。通常，二元關(guān)系有2種不同的類型，即內(nèi)部二元關(guān)系和外部二元關(guān)系。其中，內(nèi)部二元關(guān)系存在于單個(gè)集合的內(nèi)部，例如，偏序集中的序關(guān)系”即是一種內(nèi)部二元關(guān)系；外部二元關(guān)系是指存在于集合之間的關(guān)系，例如，中的序關(guān)系“”即是一種外部二元關(guān)系。

推論1 內(nèi)部二元關(guān)系是一種特殊的外部二元關(guān)系。例如，雖然與在形式上存在一定差異，但本質(zhì)上卻是相同的。

推論2 內(nèi)部二元關(guān)系與外部二元關(guān)系均可以表示為形式背景。在下文中，無論是內(nèi)部還是外部二元關(guān)系均統(tǒng)一表示為形式背景。

在?；季S下，對(duì)于數(shù)據(jù)集的分析和處理，人們通常注重的是集合，而非單個(gè)元素；注重的是集合之間的關(guān)系，而非單個(gè)元素之間的關(guān)系。

證明當(dāng)時(shí)，由定義1可知，對(duì)于任意和任意，有成立，這就意味著和是關(guān)聯(lián)的。假設(shè)和不是極大關(guān)聯(lián)的，即存在滿足。在此情形下，必然有且成立，或且成立，而非且成立，由此即得，顯然，該結(jié)論與已知條件是相互矛盾的。故當(dāng)時(shí)，和是極大關(guān)聯(lián)的。證畢。

證明當(dāng)成立時(shí)，由定理1得和是極大關(guān)聯(lián)的，這也意味著將滿足下述條件：

3 基于等價(jià)類的數(shù)據(jù)分析模型

表2 一個(gè)模糊相似關(guān)系矩陣Table 2 A fuzzy similarity relation matrix

表3 一個(gè)模糊等價(jià)關(guān)系矩陣Table 3 A fuzzy equivalence relation matrix

為避免單一粒度認(rèn)知的片面性，對(duì)于任意缺失值的估計(jì)，用戶可以設(shè)置多個(gè)閾值參數(shù)，進(jìn)而結(jié)合多個(gè)粒度下的分類結(jié)果去分析和求解問題。定義6 設(shè)是-階模糊等價(jià)關(guān)系矩陣，稱是邊界值，若不存在滿足且。

基于上述判定準(zhǔn)則，用戶可以對(duì)不完備形式背景進(jìn)行預(yù)處理，從而得到一個(gè)完備的形式背景。接上例，對(duì)于，依據(jù)準(zhǔn)則1及下述計(jì)算結(jié)果，即得。

類似地，用戶也可以判定其它缺失值，相應(yīng)的判定結(jié)果如表4所示。在此基礎(chǔ)上，復(fù)用經(jīng)典概念格生成算法，用戶可以從表4生成一個(gè)格代數(shù)結(jié)構(gòu)，如圖1所示。

表4 表1的一個(gè)完備化形式背景Table 4 A complete formal context from table 1

圖1 基于準(zhǔn)則1從表1導(dǎo)出的概念格結(jié)構(gòu)Fig. 1 Concept lattice structure derived from table 1 based on criterion 1

4 基于極大相容類的數(shù)據(jù)分析模型

表5 一個(gè)不完備形式背景Table 5 A incomplete formal context

類似地，用戶也可以判定其它缺失值，相應(yīng)的判定結(jié)果如表6所示。在此基礎(chǔ)上，復(fù)用經(jīng)典概念格生成算法，用戶可以從表6生成一個(gè)格代數(shù)結(jié)構(gòu)，如圖2所示。

表6 表5的一個(gè)完備化形式背景Table 6 Complete formal context generated from table 5

圖2 基于準(zhǔn)則2從表5導(dǎo)出的概念格結(jié)構(gòu)Fig. 2 Concept lattice structure derived from Table 5 based on Criterion 2

基于準(zhǔn)則1和準(zhǔn)則2的模型本質(zhì)上都屬于間接處理模型，即需要對(duì)原始數(shù)據(jù)集進(jìn)行預(yù)處理，給出缺失數(shù)據(jù)的估算值，進(jìn)而復(fù)用經(jīng)典理論對(duì)完備形式背景進(jìn)行分析處理。

準(zhǔn)則3 在任一極大相容類中，不同對(duì)象在同一屬性下應(yīng)具有相同的屬性值。在此情形下，一個(gè)極大相容類在屬性下的值域只可能有以下 4種情況，即{1}、{0}、{1, *}、{0, *}，而不可能是{0, 1, *}。

與定義1中的經(jīng)典算子相類似，從上述算子出發(fā)同樣可以導(dǎo)出一個(gè)格代數(shù)結(jié)構(gòu)，相關(guān)證明過程與經(jīng)典算子類似，在此不再詳述。

例如，在表5中，從定理2和定義7出發(fā)，可判定{1}、{2}、{3, 4}、{5}、{6}、{7, 8}、{7, 9}是極大相容類，如表7所示，進(jìn)而基于定義7中的算子生成圖3所示的格代數(shù)結(jié)構(gòu)。除(79, abce)之外，圖3、圖2中的其他結(jié)點(diǎn)均一致，這也從側(cè)面反映了這樣一個(gè)事實(shí)，即無論是基于準(zhǔn)則2，還是基于準(zhǔn)則3，所構(gòu)造的模型可能會(huì)得到相似的結(jié)論。

表7 表5的一個(gè)?；问奖尘癟able 7 A granular formal context from table 5

圖3 基于準(zhǔn)則3從表5導(dǎo)出的概念格結(jié)構(gòu)Fig. 3 Concept lattice structure derived from Table 5 based on Criterion 3

基于準(zhǔn)則3的知識(shí)獲取模型，其本質(zhì)是將分析尺度放大，以極大相容類為研究對(duì)象，而非單個(gè)對(duì)象。在準(zhǔn)則3下，任意在屬性的取值是確定的，即要么成立，要么成立，這就意味著，不完備形式背景可以轉(zhuǎn)化為一個(gè)完備的?；问奖尘?。事實(shí)上，在準(zhǔn)則3下，無論是基于定義7，還是定義8，得到的格代數(shù)結(jié)構(gòu)本質(zhì)上是相同的，僅僅在外延表示形式上存在略微差異。

證明由定義7和定義8即得。證畢。

與準(zhǔn)則1和準(zhǔn)則2最大的不同是，基于準(zhǔn)則3的知識(shí)獲取模型無需對(duì)缺失信息進(jìn)行預(yù)判定并給出估算值，而是直接在原始不完備形式背景上建立知識(shí)獲取模型。

5 實(shí)例分析

表8是一個(gè)以醫(yī)院病例為原型而得到的不完備形式背景，其中Pi(i=)表示患者代碼；(H, yes)、(H, no)、(M, yes)等表示身體癥狀特征，其中 H、M、T、F依次表示 Headache、Muscle-pain、Temperature、Flu；若某患者具有某種癥狀，則在表 8 中用“1”來表示，反之用“0”來表示；若某診斷結(jié)論存在缺失，則用“*”來表示。

表8 一個(gè)不完備形式背景Table 8 A incomplete formal context

表9 表8的一個(gè)完備化形式背景Table 9 Complete formal context generated from table 8

事實(shí)上，表9中的完備化結(jié)果與下述事實(shí)性規(guī)則是吻合的，這也在一定程度上反應(yīng)了準(zhǔn)則1和準(zhǔn)則2的合理性和有效性。例如，當(dāng)患者體溫是“very high”時(shí)，則其體溫一定也是“high”；當(dāng)患者體溫“normal”時(shí)，則其體溫一定不是“high”和“very high”；當(dāng)患者“Flu, yes”時(shí)，則一定不是“Flu, no”等。

事實(shí)性規(guī)則：(T, very high)→(T, high)、(T, normal)(T, high)、(T, normal)(T, very high)、(H,yes)(H, no)、(H, no)(H, yes)、(F, no)(F, yes)、(F, yes)(F, no)。

在概念格經(jīng)典理論中，概念內(nèi)涵和蘊(yùn)涵規(guī)則都占有極其重要的地位。本文認(rèn)為，無論間接處理模型，還是直接處理模型，它們都應(yīng)該得到相同的內(nèi)涵集和蘊(yùn)涵規(guī)則集(內(nèi)涵集和蘊(yùn)涵規(guī)則集是相互唯一決定的)。據(jù)此，本文提出了如下有效性判定準(zhǔn)則：

有效性判定準(zhǔn)則對(duì)于同一個(gè)不完備形式背景，若多個(gè)不同模型得到的蘊(yùn)涵規(guī)則集合或內(nèi)涵集合是相同的，則本文認(rèn)為這些模型在一定程度上是有效的，得到的結(jié)果在一定程度上也是可信的。

準(zhǔn)則3相對(duì)應(yīng)的極大相容類有{1}、{2, 7, 8}、{3}、{4, 9}、{5, 8}、{6}。在此基礎(chǔ)上，基于定義7或定義8，用戶可得到相應(yīng)的格代數(shù)結(jié)構(gòu)。經(jīng)驗(yàn)證明，基于準(zhǔn)則3直接從表8得到的概念內(nèi)涵集與基于準(zhǔn)則1或準(zhǔn)則2間接從表8中得到的概念內(nèi)涵集是相同的。顯然，在這種情形下，依據(jù)有效性判定準(zhǔn)則給出的判定原理，可以在一定程度認(rèn)為基于準(zhǔn)則1、準(zhǔn)則2或準(zhǔn)則3構(gòu)建的模型是合理的，相應(yīng)的求解結(jié)果也是可信的。

總體來看，準(zhǔn)則1和準(zhǔn)則2需要引入閾值參數(shù)，屬于間接處理模型；而準(zhǔn)則3則無需引入閾值，屬于直接處理模型。在實(shí)際應(yīng)用中，如果數(shù)據(jù)缺失量大，本文傾向于選用直接處理模型，因?yàn)橄冗x擇間接模型可能會(huì)導(dǎo)致原始數(shù)據(jù)集失真；如果數(shù)據(jù)缺失量少，則無論是直接模型還是間接模型，都可以選用。

6 結(jié)束語

為消除不完備信息帶來的影響，使概念格模型具有更強(qiáng)的數(shù)據(jù)處理能力與更廣的應(yīng)用領(lǐng)域，本文嘗試將經(jīng)典形式背景中的知識(shí)獲取方法進(jìn)一步拓展到不完備形式背景中，依次探討了基于等價(jià)類的分析模型和基于極大相容類的分析模型。在實(shí)際應(yīng)用中，用戶既可以選擇基于準(zhǔn)則1或準(zhǔn)則2的間接處理模型，也可以選擇基于準(zhǔn)則3的直接處理模型。此外，對(duì)于模型的機(jī)制有效性和結(jié)果可信性，本文也嘗試性的進(jìn)行了探討，并提出了一些初步的驗(yàn)證方法。相信本文所做的工作能為下一步相關(guān)研究提供一些有益的思路。