智慧來

河南理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，河南焦作 454000

基于形式概念分析理論的完全格存儲模型

智慧來

河南理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，河南焦作 454000

1 引言

格描述了對象之間的偏序關(guān)系，便于對象的聚類和層次結(jié)構(gòu)的分析。近年來格論，特別是完全格理論在GPS中的坐標變換[1]、模糊故障檢測[2]、機器人集群[3]、不確定性數(shù)據(jù)表示[4]等領(lǐng)域都有應(yīng)用。在這些應(yīng)用中，都需要進行格的存儲與檢索操作。在理論研究時，通常使用的格結(jié)構(gòu)比較簡單，使用鄰接矩陣來存儲格是完全可行的。然而，在實際應(yīng)用中由于描述的對象十分復(fù)雜，構(gòu)造的格結(jié)點數(shù)目眾多，格結(jié)點之間的關(guān)系也更加復(fù)雜，仍舊采用鄰接矩陣來存儲格將耗費大量存儲空間，不利于格的檢索和同構(gòu)判定。格的存儲不再是一個無關(guān)緊要的問題，而是一個有實際應(yīng)用價值的關(guān)鍵理論問題。

形式概念分析理論與格論有天然的聯(lián)系。形式概念分析是R.Wille[5]提出的，以序論和格論為基礎(chǔ)建立起來的，它的核心數(shù)據(jù)結(jié)構(gòu)概念格是對概念以及概念之間關(guān)系的描述，由于它便于概念結(jié)構(gòu)的開發(fā)和討論，在某種意義上，概念格已經(jīng)變成了一種外部認知的手段，并在人工智能領(lǐng)域有廣泛而成熟的應(yīng)用[6]。鑒于形式概念分析理論在數(shù)據(jù)分析與表示中的獨特優(yōu)勢，本文將利用這一理論提出一個基于概念格模型的完全格存儲模型。

2 基本概念

下面的基本概念均出自于Ganter B的著作“Formal Concept Analysis”[5]。

定義1一個集合M及其上的偏序關(guān)系≤形成的有序二元組(M,≤)稱為半序集。

定義2令(M,≤)是一個半序集，A是M的子集，若M中的元素s滿足?a∈A都有s≤a，則稱s是A的一個下界。對偶地，若M中的元素s滿足?a∈A都有s≥a，則稱s是A的一個上界。如果A的所有下界組成的集合中有最大元素，則稱這個元素為A的下確界，記infA或∧A。對偶地，上界集合的最小元素稱為A的上確界，記supA或∨A。

定義3一個半序集(V,≤)，如果V中任意兩個元素x,y的上確界及下確界都存在，則稱V是一個格。如果V的任何子集的上確界及下確界都存在，則稱V是一個完全格。

定義4對于完全格V的一個元素v，定義vl=∨{x∈V|x＜v}，vu=∧{x∈V|v＜x}，如果v≠vl即v不是嚴格小于它的那些元素的上確界，則稱v是上確界不可約的，或者稱v是上確界不可約元；如果v≠vu，即v不是嚴格大于它的那些元素的下確界，則稱v是下確界不可約的，或者稱v是下確界不可約元。在不區(qū)分上確界不可約元和下確界不可約元的情況下，它們統(tǒng)稱為不可約元。

定義5a稱為b的下近鄰，當a＜b且沒有c滿足a＜c＜b，這時也稱b是a的上近鄰，并且記做a?b。

定義6一個形式背景K=(G,M,I)是由兩個集合G和M以及G與M之間的關(guān)系I組成。G的元素稱為對象，M的元素稱為屬性。(g,m)∈I或gIm表示對象g具有屬性m。

定義7設(shè)A是對象集合G的一個子集，定義f(A)= {m∈M|g∈A,gIm}，相應(yīng)地設(shè)B是屬性集合M的一個子集，g(B)={g∈G|m∈B,gIm}。如果A、B滿足條件f(A)=B且g(B)=A，則稱序?qū)?A,B)為形式背景K的一個概念，A稱為概念(A,B)的外延，B稱為概念(A,B)的內(nèi)涵。

定義8若(A1,B1)、(A2,B2)是某個形式背景的兩個概念，而且A1?A2（等價于B2?B1），則稱(A1,B1)是(A2,B2)的子概念，(A2,B2)是(A1,B1)的父概念，并記做(A1,B1)≤(A2,B2)，關(guān)系≤稱為是概念的“層次序”。(G,M,I)的所有概念用這種序組成的集合稱為概念格，記做B(G,M,I)。

定義9在一個概念格中，如果一個概念具有形式(g(f(g)),f(g))且g∈G，則稱這個概念是一個對象概念；如果一個概念具有形式(g(m),f(g(m)))且m∈M，則稱這個概念是一個屬性概念。

定理1（概念格基本定理）概念格B(G,M,I)是一個完全格，其上確界和下確界分別是：

3 基于形式概念分析理論的完全格存儲模式

定義10對于形式背景(G,M,I)，每一個屬性子集P?M決定了一個二元不可區(qū)分關(guān)系IND(P)={(x,y)∈G×G|?a∈P,I(x,a)=I(y,a)}[7]。

定義11在一個信息系統(tǒng)中a∈M，如果IND(M-{a})=IND(M)，則稱屬性a在M中是不必要的，否則，稱a在M中是必要的。如果每個屬性a∈M在M中都是必要的，則稱屬性集M是獨立的，否則，稱M是相依的。對于相依的屬性集來說，其中包含有多余屬性，可以對其約簡[7]。

定義12設(shè)P?M，如果IND(P)=IND(M)，并且P是獨立的，則稱P是M的一個約簡[7]。

定義13一個信息系統(tǒng)所有屬性約簡的交集稱為核，核中的屬性稱為是核心屬性。不屬于任何約簡的屬性稱為不必要屬性，屬于某些約簡但不屬于核的屬性稱為相對必要屬性。核心屬性與相對必要屬性統(tǒng)稱必要屬性[8]。

根據(jù)形式背景的對偶性，可以直接得到對象純化形式背景的概念，這里不再贅述。

定義14若形式背景(G,M,I)既是對象純化的，又是屬性純化的，則稱形式背景(G,M,I)是純化的形式背景，簡稱形式背景(G,M,I)是純化的[9]。

命題1有限格的一個元素是上確界不可約的，當且僅當它有且僅有一個下近鄰；一個元素是下確界不可約的，當且僅當它有且僅有一個上近鄰。

定理2在純化形式背景中，對象概念是上確界不可約元，上確界不可約元一定是對象概念；屬性概念是下確界不可約元，下確界不可約元一定是屬性概念。

證明先證明定理前半部分。反證法，假設(shè)對象概念(A,B)不是上確界不可約元，即對象概念有兩個或兩個以上的下近鄰，其中的兩個下近鄰記做(At,Bt)，t為指標集，t∈T。由于(A,B)是對象概念，因此存在對象g∈A使得f(g)=B。根據(jù)概念格基本定理，有B=∩Bt(t∈T)，又因為f(At)=Bt(t∈T)，則有f(g)=∩f(At)(t∈T)，因此g是可約簡的，與純化形式背景的前提矛盾，故定理成立。根據(jù)概念格的對偶原理，可知定理的后半部分成立。

定義15若完全格V的每個元素都是X(X?V)的某個子集的上確界，則X稱為在V中是上確界稠密的。對偶地，若完全格V的每個元素都是X(X?V)的某個子集的下確界，則X稱為在V中是下確界稠密的。

定理3若V是一個完全格，G和M是兩個集合，則存在兩個映射γ:G→V和μ:M→V，并且γ(G)是上確界稠密的，μ(M)是下確界稠密的。對任意的g∈G和m∈M定義關(guān)系I，gIm?γ(G)≤μ(M)，那么V和概念格B(G,M,I)同構(gòu)[10]。

定義γ(g):=(g(f(g)),f(g))（對象概念），μ(m):=(g(m)，f(g(m)))（屬性概念），則有g(shù)Im?g∈g(m)?g(f(g))?g(f(g(m)))=g(m)?γ(g)≤μ(m)，因此gIm?γ(G)≤μ(M)成立，可知函數(shù)γ(g)和μ(m)滿足定理3。

根據(jù)上面的論述，可以從完全格V，使用映射γ、μ得到與其同構(gòu)的概念格的形式背景K，并使用矩陣存儲此形式背景，從而實現(xiàn)對完全格的存儲。

算法1計算完全格的形式背景

輸入完全格V；

輸出形式背景K

步驟1從完全格V最小元開始向上遍歷，若一個格結(jié)點只有一個上近鄰，則從字母表{a,b,c,…}中取一個字母標注，標注后將這個字母從字母表中刪除。

步驟2從完全格V最大元開始向下遍歷，若一個格結(jié)點只有一個下近鄰，則從數(shù)字表{1,2,3,…}中取一個數(shù)字標注，標注后將這個數(shù)字從數(shù)字表中刪除。

步驟3若一共使用了m個數(shù)字和n個字母，則建立m行n列的形式背景K，每一個數(shù)字對應(yīng)一行，每一個字母對應(yīng)一列。

步驟4在完全格V中，對于每個用數(shù)字標注的格結(jié)點（假定標注的數(shù)字為i），搜索其上近鄰直到最大元，若在這一過程中遇到用字母標注的格結(jié)點（假定標注的字母為j），則將K中i行j列交叉處的值修改為*。

步驟5返回K，算法結(jié)束。

應(yīng)用算法1，可以將存儲一個完全格轉(zhuǎn)化為存儲一個形式背景。存儲形式背景實際上就是存儲一個矩陣。

例1對于圖1中的完全格V，使用算法1（標注了不可約元的完全格見圖2），可以得到5行5列的形式背景K（見表1），并依據(jù)形式背景建立5×5的存儲矩陣

圖2 標注不可約元的完全格V

圖1 完全格V

表1 形式背景K

若使用鄰接矩陣存儲完全格V，根據(jù)結(jié)點之間的鄰接關(guān)系建立一個9×9的鄰接矩陣為：

其中有12個非零元素。兩種方法的存儲效率對比見表2。

另一方面，本文的方法有利于提高判定完全格同構(gòu)的效率。完全格同構(gòu)的判定可以轉(zhuǎn)化為圖同構(gòu)的判定，多數(shù)學(xué)者認為圖的同構(gòu)判定問題屬于NP-完全問題[11]。利用存儲矩陣通過行交換和列交換，如果能夠得到相同的矩陣則可以判斷是同構(gòu)的。在最壞情況下交換的總次數(shù)將達到r!×c!（r為背景的行數(shù)，c為背景的列數(shù)），復(fù)雜性遠遠大于指數(shù)時間復(fù)雜性[12]。本文的方法降低了存儲矩陣的行、列數(shù)，因此有利于實現(xiàn)完全格同構(gòu)的判定。

表2 存儲效率對比

4 結(jié)束語

格結(jié)構(gòu)在理論研究和實際應(yīng)用中廣泛存在，本文利用形式概念分析的理論研究完全格的存儲。本文的方法只存儲不可約元及不可約元間關(guān)系的信息，并不存儲其他信息，與采用鄰接矩陣的存儲方式相比提高了存儲效率，為復(fù)雜格結(jié)構(gòu)的應(yīng)用提供技術(shù)上的支持。

[1]Wu Chih-Hung，Su Weihan.Lattice-based clustering and genetic programming for coordinate transformation in GPS applications[J].Computers and Geosciences，2013，52：85-94.

[2]Li Bing，Liu Pengyuan，Hu Renxi，et al.Fuzzy lattice classifier and its application to bearing fault diagnosis[J].Applied Soft Computing Journal，2012，12（6）：1708-1719.

[3]XuQingzheng，WangLei.Lattice-basedartificial endocrine system model and its application in robotic swarms[J].Science China Information Sciences，2011，54：1-17.

[4]Denoeux T，Younes Z，Abdallah F.Representing uncertainty on set-valued variables using belief functions[J].Artificial Intelligence，2010，174：479-499.

[5]Ganter B，Wille R.Formal concept analysis：mathematical foundation[M].New York：Springer-Verlag，1999.

[6]Scaife M，Rogers Y.External cognition：how do graphical representations work[J].International Journal of Human Computer Studies，1996，45：185-213.

[7]梁吉業(yè)，曲開社，徐宗本.信息系統(tǒng)的屬性約簡[J].系統(tǒng)工程理論與實踐，2001（12）：76-80.

[8]Pawlak Z.Rough sets—theoretical aspects of reasoning about data[M].Dordrecht：Kluwer Academic Publisher，1991.

[9]智慧來，智東杰.純化形式背景及其性質(zhì)研究[J].計算機工程與應(yīng)用，2011，47（35）：61-62.

[10]Davey B A，Priestley H A.Introduction to lattice and order[M]. New York：Cambridge University Press，2002.

[11]Karp R M.Reducibility among combinatorial problems[M]. New York：Plenum Press，1972.

[12]李鋒，李曉燕.圖的同構(gòu)判定算法：關(guān)聯(lián)度序列法及其應(yīng)用[J].復(fù)旦學(xué)報：自然科學(xué)版，2001，40（3）：318-325.

ZHI Huilai

School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China

The storage of complete lattice is an important issue in various types of applications.The theory of formal concept analysis is adopted in the storage of complete lattice.For a given complete lattice,when it is stored by using a matrix,irreducible elements are identified.This paper marks the upper and lower irreducible elements separately by using different types of signs,i.e. object labels and attribute labels,and lets them indicate rows and columns of the matrix.It ascertains the element of the matrix according to the relationship between the upper and lower irreducible elements.Compared with using adjacent matrix,this method is more efficient and suitable for application.

formal concept analysis;complete lattice;irreducible elements;storage model;concept lattice

完全格的存儲是一個有實際應(yīng)用價值的關(guān)鍵問題。在利用矩陣存儲完全格時，識別完全格中的不可約元；分別對上確界不可約元和下確界不可約元用對象標簽和屬性標簽進行標注，使得對象標簽和屬性標簽分別對應(yīng)矩陣的行和列；根據(jù)不可約元之間的關(guān)系確定矩陣中元素的值。與采用鄰接矩陣存儲完全格相比，該方法只存儲不可約元的相關(guān)信息，能夠提高存儲的效率。

形式概念分析；完全格；不可約元；存儲模型；概念格

A

TP18

10.3778/j.issn.1002-8331.1308-0020

ZHI Huilai.Storage model of complete lattice based on theory of formal concept analysis.Computer Engineering and Applications,2013,49（24）：1-3.

國家自然科學(xué)基金（No.60975033）；河南理工大學(xué)博士基金（No.B2011-102）。

智慧來（1981—），男，博士，講師，研究領(lǐng)域：粗糙集合、本體、形式概念分析等。E-mail：zhihuilai@126.com

2013-08-05

2013-09-16

1002-8331（2013）24-0001-03

CNKI出版日期：2013-09-26http://www.cnki.net/kcms/detail/11.2127.TP.20130926.1644.001.html