形式背景同構(gòu)判定算法研究及其應(yīng)用.pdf

1、構(gòu)造概念格是FCA(FormalConceptAnalysis)理論中的一個(gè)重要問(wèn)題。傳統(tǒng)的構(gòu)造算法均是對(duì)于一個(gè)給定的形式背景從頭構(gòu)造概念格，而不能利用已有的概念格。針對(duì)該問(wèn)題，課題組提出了概念格的同構(gòu)生成方法，所涉及到的一個(gè)基本問(wèn)題是如何判定兩個(gè)形式背景是否同構(gòu)。這也是本文工作的中心任務(wù)。 形式背景同構(gòu)判定與圖同構(gòu)判定屬于同一類問(wèn)題，但不盡相同，因?yàn)樵谠旄襁^(guò)程中不僅需要得出形式背景是否同構(gòu)的結(jié)論，而且如果存在同構(gòu)還需要求出具體

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

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

4、式背景運(yùn)用直觀算法進(jìn)行判定。 經(jīng)過(guò)實(shí)驗(yàn)證明，等價(jià)類算法在時(shí)間復(fù)雜性和空間復(fù)雜性上都優(yōu)于直觀算法，有效地提高了同構(gòu)判定的效率，尤其是當(dāng)形式背景的對(duì)象數(shù)和屬性數(shù)增加時(shí)，等價(jià)類算法的優(yōu)越性更加明顯。再結(jié)合形式背景的分解和約簡(jiǎn)等手段，為概念格的構(gòu)造提供了一種有實(shí)用價(jià)值的方法，我們將這種方法稱為是基于格同構(gòu)的生成方法?；诟裢瑯?gòu)的生成方法的實(shí)用價(jià)值和性能在IsoFCA(IsomorphismFormalConceptAnalysis)系統(tǒng)

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