王雯，康向平，武燕

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

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

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

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

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

1 概念格基本知識

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

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

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

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

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

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

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

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

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

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

表2 一個模糊相似關系矩陣Table 2 A fuzzy similarity relation matrix

表3 一個模糊等價關系矩陣Table 3 A fuzzy equivalence relation matrix

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

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

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

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

圖1 基于準則1從表1導出的概念格結構Fig. 1 Concept lattice structure derived from table 1 based on criterion 1

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

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

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

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

圖2 基于準則2從表5導出的概念格結構Fig. 2 Concept lattice structure derived from Table 5 based on Criterion 2

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

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

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

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

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

圖3 基于準則3從表5導出的概念格結構Fig. 3 Concept lattice structure derived from Table 5 based on Criterion 3

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

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

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

5 實例分析

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

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

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

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

事實性規(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)涵和蘊涵規(guī)則都占有極其重要的地位。本文認為，無論間接處理模型，還是直接處理模型，它們都應該得到相同的內(nèi)涵集和蘊涵規(guī)則集(內(nèi)涵集和蘊涵規(guī)則集是相互唯一決定的)。據(jù)此，本文提出了如下有效性判定準則：

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

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

總體來看，準則1和準則2需要引入閾值參數(shù)，屬于間接處理模型；而準則3則無需引入閾值，屬于直接處理模型。在實際應用中，如果數(shù)據(jù)缺失量大，本文傾向于選用直接處理模型，因為先選擇間接模型可能會導致原始數(shù)據(jù)集失真；如果數(shù)據(jù)缺失量少，則無論是直接模型還是間接模型，都可以選用。

6 結束語

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