概念格

概念格，也稱為Cralois格，又叫做形式概念分析，由Wille R於1982年首先提出，它提供了一種支持數據分析的有效工具。概念格的每個節點是一個形式概念，由兩部分組成:外延，即概念所覆蓋的實例;內涵，即概念的描述，該概念覆蓋實例的共同特徵。另外，概念格通過Hasse圖生動和簡潔地體現了這些概念之間的泛化和特化關係。因此，概念格被認為是進行數據分析的有力工具。從數據集中(概念格中稱為形式背景)中生成概念格的過程實質上是一種概念聚類過程;然而，概念格可以用於許多機器學習的任務。目前，已經有了一些建造概念格的算法，並且概念格在信息檢索、數字圖書館、軟件工程和知識發現等方面得到應用。 ^[2] 

形式背景（formal context）可以表示為三元組T=(O，D，R)，其中O是事例（對象）集合，D是描述符（屬性）集合，R是O和D之間的一個二元關係，則存在唯一的一個偏序集與之對應，並且這個偏序集產生一種格結構，這種由背景（O，D，R）所誘導的格L稱為概念格。格L中的每個節點是一個序偶(稱為概念)，記為(X，Y)，其中

稱為概念的外延；

稱為概念的內涵。每一個序偶關於關係R是完備的，即有性質：

1）

2）

在概念格節點間能夠建立起一種偏序關係。具體地，給定概念

=(

，

) 和

=(

，

)，則

<

<==>

⊂

，領先次序意味着

是

的父節點或稱直接泛化。根據偏序關係可生成格的Hasse圖：如果

<

並且不存在另一個元素

使得

<

<

，則從

到

就存在一條邊。 ^[2] 

表1給出一個形式背景，其對應的概念格如圖1所示。

概念格的基本定理表明上述方式定義的概念和偏序關係是一個完全格。其中任意一組概念的上下確界是:

上述定義實際上對原始概念格的定義有所擴充。在經典定義中，形式背景是二值的。即每個屬性的值為1時代表該屬性在該對象中出現，為0時代表不出現。上述定義將其擴展成多值形式背景。實際上它們是等價的，很容易將多值形式背景轉變成二值形式背景。值得注意的是，多值形式背景中的屬性值對對應於二值形式背景中的屬性。對於多值的形式背景，也可以通過概念縮放(concept scaling)來將其轉換成二值的形式背景。

近年來，國內外學者又相繼提出了不完備決策形式背景，實值決策形式背景 ^[3]  ，模糊決策形式背景 ^[3]  ，等等。這些廣義形式背景上得到的格稱為廣義概念格，大部分廣義概念格具有經典概念格的基本性質。 ^[3] 

概念格主要圍繞格快速構造，節點刪減，數據壓縮，模型推廣等展開，下面一一介紹。

概念格快速構造自FCA提出以來，已研究30多年。據不完全統計，各種格快速構造算法不下幾十種，有興趣的讀者可參考相關文獻。這裏，僅僅給出一種經典的增量算法：

Concept lattice constuction algorithm for formal context (U, A, I)

(1) 初始化

(2)

，其中

表示對象

所擁有的全部屬性，並設

(3) 令

(4) 從

中任意選出一個概念

(5) 如果

，則

，

，並轉步驟（7）；否則轉步驟（6）

(6) 如果對任意的

，

均不包含於

，則

(7) 如果

，則

，並返回步驟（4）

(8) 如果對任意的

，

均不包含於

，則

(9) 如果

，

，並返回步驟（3）

(10) 如果

，則

(11) 輸出

需要指出的是，概念格的構造需要指數時間複雜度，所以任何快速算法只有相對的意義 ^[4]  。另外，近幾年，概念格的並行構造問題得到學界的廣泛重視。

概念格約簡是一個非常熱門的話題，研究熱度不亞於概念格構造。最早可以追溯到形式背景的淨化，淨化形式背景可以簡化概念內涵。而從格同構角度研究屬性約簡，則歸功於文獻《概念格的屬性約簡理論與方法》 ^[5]  。實際上，如果不考慮屬性重複問題，概念格的約簡是唯一的，此時計算概念格約簡只需多項式時間，因為它等價於淨化形式背景。

概念格約簡的方式方法多種多樣，除了基於格同構的思路，還有基於粒計算 ^[6-7]  ，不可約元 ^[8]  ，協調性 ^[9]  ，決策規則，等等。

截至目前，已有學者提出眾多概念格模型，包括：面向對象概念格，面向屬性概念格，近似概念格，冪概念格 ^[10]  ，單調概念格 ^[11]  ，AFS概念格 ^[12]  ，三支概念格 ^[13]  ，實值概念格 ^[3]  ，等等。需要説明的是，格快速構造和屬性約簡依然是這些廣義概念格的重點研究內容。

概念格主要用於認知計算、機器學習、模式識別、專家系統、決策分析、網頁搜索等領域 ^[4]  。近年來，概念格應用研究出現一些新領域，比如認知概念學習 ^[6]  ，規則提取，三支決策 ^[13]  ，等等。

在知識發現領域，概念格可以從關係數據中構造出來，然後從概念格上可以提取各種類型的知識，如藴含規則、關聯規則、分類規則等等;在軟件工程領域，概念格可以從類庫的規範説明上構造，從而對類庫結構的可視化以及類庫的重構和優化提供支持;在知識工程領域，概念格可以用於知識庫的重新結構化;在信息檢索方面，概念格可以實現對信息的有機組織並過慮掉無用的信息。而且，有人指出概念格將會在生物和生命科學領域有重大應用。 ^[14]