形式背景同構判定算法研究及其應用.pdf

1、構造概念格是FCA(FormalConceptAnalysis)理論中的一個重要問題。傳統的構造算法均是對于一個給定的形式背景從頭構造概念格，而不能利用已有的概念格。針對該問題，課題組提出了概念格的同構生成方法，所涉及到的一個基本問題是如何判定兩個形式背景是否同構。這也是本文工作的中心任務。 形式背景同構判定與圖同構判定屬于同一類問題，但不盡相同，因為在造格過程中不僅需要得出形式背景是否同構的結論，而且如果存在同構還需要求出具體

2、的映射關系。由于形式背景用矩陣表示，所以我們只關心是用矩陣表示圖的一類同構判定算法。這些算法大致分為兩類，一類使用行列交換進行判定，一類利用圖的一些不變量及其它特性進行判定。形式背景同構判定可以通過行列交換進行判定，本文中實現的“直觀算法”就是使用這種思路。但這種方法時間復雜度高，效率很低。根據圖同構的第二類算法，我們也可以利用形式背景的一些不變量進行初步判斷，同時結合行列變換的方法進行判定，基于這個思路，本文提出了“等價類法”。

3、 等價類同構判定算法的基本思想為：對于形式背景K1和K2分別按照等重(weight)關系進行等重劃分，此過程包括兩部分——對象劃分和屬性劃分。對象劃分在計算每一對象(行)的重的基礎上，按照等重關系將對象集劃分為等價類，并使得對象等價類按其重的大小排序。為確定形式背景形態(tài)上的唯一性，在變換過程中，始終要保持等價類的有序性。屬性劃分類似。于是，等重劃分后的形式背景被對象等價類和屬性等價類分解為多個子形式背景，這樣只須對K1和K2對應的子形

4、式背景運用直觀算法進行判定。 經過實驗證明，等價類算法在時間復雜性和空間復雜性上都優(yōu)于直觀算法，有效地提高了同構判定的效率，尤其是當形式背景的對象數和屬性數增加時，等價類算法的優(yōu)越性更加明顯。再結合形式背景的分解和約簡等手段，為概念格的構造提供了一種有實用價值的方法，我們將這種方法稱為是基于格同構的生成方法?；诟裢瑯嫷纳煞椒ǖ膶嵱脙r值和性能在IsoFCA(IsomorphismFormalConceptAnalysis)系統

5、中得到了驗證。 本文的主要貢獻如下：(1)提出了等價類算法，并通過實驗驗證了等價類算法的高效性和正確性。 (2)提出了基于對象和屬性權重不變量的等價關系，實現對形式背景對象集和屬性集的劃分。 (3)根據圖同構行列交換判定思想，實現了形式背景同構判定的直觀算法。 (4)將等價類算法運用于IsoFCA原型系統中對n階形式背景核的構造和子形式背景同構判定。該系統的成功運行驗證了概念格同構生成方法的可行性，也驗證