曾利程，張祖平，鄒力耕

中南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410012

1 引言

在20世紀(jì)80年代，科學(xué)家Wille就提出了FCA（formal concept analysis），在過去的30多年里，F(xiàn)CA被廣泛應(yīng)用[1]。FCA是概念格的核心數(shù)據(jù)結(jié)構(gòu)，該理論強(qiáng)調(diào)以人的認(rèn)知為中心，提出了一種不同于傳統(tǒng)的知識(shí)表示以及數(shù)據(jù)分析的方法，在信息檢索、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域得到了廣泛而深遠(yuǎn)的影響[2-3]。如何快速構(gòu)建或更新概念格成為了當(dāng)今學(xué)術(shù)界的一個(gè)熱點(diǎn)。對(duì)概念格進(jìn)行更新的一個(gè)隱含前提是必須要有已經(jīng)構(gòu)造好的概念格。構(gòu)造一個(gè)概念格可以看成是把所有的對(duì)象或是屬性一個(gè)個(gè)添加到空概念格的過程，因而向概念格中添加對(duì)象或是屬性的更新算法有著比其他更新算法更加獨(dú)特的地方[4-6]。概念格作為數(shù)據(jù)分析的有效工具，被應(yīng)用到很多的領(lǐng)域，吸引了廣大研究者的長(zhǎng)期關(guān)注[7-12]。概念格中的每一個(gè)節(jié)點(diǎn)都是一個(gè)形式概念，所有的形式概念都由兩部分組成：外延和內(nèi)涵。外延是被這個(gè)概念覆蓋的例子，就是所有屬于這個(gè)概念的對(duì)象的集合；內(nèi)涵，也就是概念的描述，用來表述這個(gè)例子在這個(gè)概念下的共同特征[7,13]。形式概念分析利用了對(duì)象與屬性之間的二元關(guān)系構(gòu)建概念之間的層次結(jié)構(gòu)。概念格架構(gòu)從本質(zhì)上描述的是對(duì)象和屬性之間的關(guān)系，在哲學(xué)的意義上實(shí)現(xiàn)概念的規(guī)范化[4]。

概念格的形成是一個(gè)概念聚類的過程。自從概念格被提出來，從形式背景下構(gòu)建概念格在概念分析研究領(lǐng)域成為重點(diǎn)。在應(yīng)用概念格的過程中，由于將要被運(yùn)行的數(shù)據(jù)在大多數(shù)情況下是非常大的，因此如何有效地構(gòu)建概念格是人們最關(guān)注的問題[14]。目前存在的概念格的構(gòu)造算法大體上分為兩類：增量式算法[15-16]和批處理算法[17-19]。批處理算法計(jì)算概念格通常采用從上至下（top-down）或者由下至上（bottom-up）的方式，而增量式算法則是采用把形式背景中的對(duì)象（或是屬性）一個(gè)接一個(gè)地添加到概念格中的方式來構(gòu)建。增量式構(gòu)建算法的一個(gè)顯著特點(diǎn)就是尚未處理的對(duì)象（或?qū)傩裕┘捌湎嚓P(guān)信息對(duì)于算法來說都是未知的。因此增量式算法能夠適應(yīng)形式背景的動(dòng)態(tài)變化，避免重新構(gòu)造概念格。

同批處理算法相比，增量式算法的這些特點(diǎn)使得這類算法顯然更適合應(yīng)用在動(dòng)態(tài)數(shù)據(jù)集的處理上。增量式構(gòu)造算法中最具代表性的兩種算法分別是AddIntent算法[16]和Godin算法[20]。Valtchev等人[21]采用了Godin算法一個(gè)變體，并將其整合進(jìn)了一個(gè)十分高效的增量式避頻繁項(xiàng)集挖掘框架中。Lv等人提出了一個(gè)改進(jìn)的AddIntent算法版本，該版本中的每個(gè)概念都增加了兩個(gè)字段用來快速定位已經(jīng)生成的新概念[14]。實(shí)驗(yàn)結(jié)果表明，當(dāng)形式背景中的對(duì)象數(shù)量沒有遠(yuǎn)遠(yuǎn)超過屬性時(shí)，Lv等人提出的改進(jìn)版本在時(shí)間上相比AddIntent會(huì)有微弱的優(yōu)勢(shì)[14]。這些增量式構(gòu)造算法的基本思想都是在一個(gè)已有的概念格L1的基礎(chǔ)上，向形式背景插入新增對(duì)象g（或者是屬性m），并根據(jù)g擁有的屬性集（m擁有的對(duì)象集）來更新L1從而得到新的概念格L2。根據(jù)已有的研究結(jié)果，在插入新增對(duì)象g（新增屬性m）后，可以把L2中的概念分為三大類：新概念（new concepts）、舊概念（old concepts）、修正概念（modified concepts）。其中，舊概念又可以細(xì)分為普通舊概念（general old concepts）和生成器概念（generator concepts）。這些概念類別的完整定義由定義2給出，而各概念之間的關(guān)系由圖1展示。

2 概念格構(gòu)建的基礎(chǔ)

這個(gè)模塊主要解決一些關(guān)于概念格的基礎(chǔ)概念，這些概念在文獻(xiàn)[7]都有詳細(xì)介紹。

Fig.1 Correspondences between concepts inL1andL2圖1 L1與L2中各類概念的對(duì)應(yīng)關(guān)系

在形式概念分析中，形式背景由三元組K=(G,M,I)展現(xiàn)出來，其中G是對(duì)象的集合，M是屬性的集合，而I表示的是G和M之間的二元關(guān)系。對(duì)于任意的g∈G，任意的m∈M，如果gIm則可以說明對(duì)象g擁有屬性m（(g,m)∈I）。

在對(duì)象集合A∈G以及B∈M中定義兩種映射關(guān)系，G和M都是形式背景下的對(duì)象集合和屬性集合，映射關(guān)系如下：

在形式背景中，如果一個(gè)二元組滿足C=(O,D)，并且f(O)=D以及g(D)=O，則稱C=(O,D)為一個(gè)形式概念。這里O是形式背景G中的子集，是一些對(duì)象集合，被稱為形式概念的外延；D是形式背景M中的子集，是一些屬性的集合，被稱為形式概念的內(nèi)涵。

形式背景K下的所有形式概念集合用CS(K)表示。給定概念C1=(A1,B1)和概念C2=(A2,B2)，如果A1?A2，則稱C1是C2的子概念，而C2稱為C1的超概念，另外這種關(guān)系可以表示為(A1,B1)≦(A2,B2)。如果這里不存在C3=(A3,B3)，使得 (A1,B1)＜(A3,B3)＜(A2,B2)，則稱C1為孩子概念，而C2為父親概念。關(guān)系“≦”稱為概念的序，(G,M,I)上所有的概念用這種序組成的集合，稱為背景(G,M,I)上的概念格。

父親概念將置于孩子概念的上方，通過獲得哈斯圖的方式得到概念格，將概念格可視化。這種哈斯圖是在父親和孩子概念之間畫一條直線或者是曲線來表示他們之間的父親-孩子關(guān)系的。

接下來，主要介紹一些關(guān)于增量構(gòu)造算法基礎(chǔ)的定義和理論。

Mi為前i個(gè)屬性的集合，Ii為集合G與前i個(gè)屬性之間的二元關(guān)系，“×”為笛卡爾積。使Mi={m1,m2,…,mi}?M，Ii=I?(G×Mi)，Mi+1=Mi?{m′}，Ii+1=I?(G×Mi+1)，其m′是新增屬性。對(duì)于形式背景K=(G,M,I)，給定一個(gè)形式背景Ki=(G,Mi,Ii)，與之相對(duì)應(yīng)的概念格為L(zhǎng)(Ki)。而通過屬性增量算法將會(huì)構(gòu)建概念格L(Ki+1)，相對(duì)應(yīng)的形式背景為Ki+1=(G,Mi+1,Ii+1)。

定義1（修正概念更新過程）對(duì)于一個(gè)概念C=(A,B)，如果A=g(m′)，則C概念將會(huì)被定義為一個(gè)修正概念，如果C是一個(gè)修正概念，則概念在概念格L(Ki+1)將會(huì)被更新為(A,B?{m′})。

定義2（四大基本概念）L1和L2分別表示新屬性m插入前后形式背景所對(duì)應(yīng)的概念格。m所具有的對(duì)象集g(m′)。(A,B)是L2中的一個(gè)形式概念，則：

如果A不是L1中任何概念的外延，那么稱(A,B)為新概念[4]；

如果A?g(m′)，且A是L1中某個(gè)概念的外延，那么稱(A,B)為修正概念[4]；

如果(A,B)也是概念L1中的形式概念，那么稱(A,B)為舊概念[4]。

設(shè)(X,Y)是新概念，而(A,B)為舊概念，如果A?g(m′)=X≠A，那么稱 (A,B)為 (X,Y)的生成器；反之，(A,B)就稱為普通舊概念[4]。

命題1如果(A1,B1)是新概念(A2,B2)的一個(gè)標(biāo)準(zhǔn)生成器，與此同時(shí)，(A3,B3)是新概念(A2,B2)的一個(gè)非標(biāo)準(zhǔn)生成器，在A1?A3的情況下，如果A?A3并且A?A1，概念(A,B)既不是修正概念也不是任何新概念的標(biāo)準(zhǔn)生成器[13]。

命題2如果(A3,B3)是一個(gè)舊概念并且A3?g(m′)=A1，并且 (A1,B1)∈L(Ki+1)是一個(gè)修正概念的情況下，如果A?A3并且，概念(A,B)既不是修正概念也不是任何新概念的標(biāo)準(zhǔn)生成器[13]。

3 改進(jìn)的AddExtent算法：FastAddExtent算法

3.1 AddExtent算法分析

根據(jù)第1章的分析，最經(jīng)典的概念格增加算法為AddExtent算法（AddIntent算法的變形），AddExtent算法概述如下：為了增加一個(gè)屬性m（m屬性對(duì)應(yīng)的對(duì)象集合Extent），從概念格的最大上界開始遞歸地查找新概念和修正概念。在遞歸函數(shù)中，不斷尋找這個(gè)命名為MaximalConcept的普通概念，這個(gè)普通概念的外延值包含Extent。如果查找結(jié)果返回的MaximalConcept的外延值等于當(dāng)前傳入AddExtent的Extent，則這個(gè)MaximalConcept將會(huì)作為所有修正概念和包含外延Extent的新概念的最大上界。與之相反的是，如果查找結(jié)果返回的MaximalConcept的外延值不等于當(dāng)前傳入AddExtent的Extent，那么這個(gè)MaximalConcept一定是一個(gè)標(biāo)準(zhǔn)生成器，而這個(gè)標(biāo)準(zhǔn)生成器能夠產(chǎn)生一個(gè)命名為NewConcept的新概念。同樣，MaximalConcept將會(huì)作為所有修訂概念和包含外延Extent的新概念的最大上界。把MaximalConcept的所有孩子節(jié)點(diǎn)作為最原始的GeneratorConcept以及MaximalConcept.Extent?Extent作為新對(duì)象集合Extent，把這兩個(gè)參數(shù)傳入到AddExtent中遞歸查找新的生成概念和修正概念。接下來分別建立NewConcept和父親節(jié)點(diǎn)以及孩子節(jié)點(diǎn)之間的關(guān)系。根據(jù)命題1以及命題2，任何比MaximalConcept小的概念不可能是生成器也不可能是修正概念。修正概念和新概念的標(biāo)準(zhǔn)生成器一定是MaximalConcept。因此，通過查找MaximalConcept，AddExtent算法能夠在每一次遞歸時(shí)快速找到標(biāo)準(zhǔn)生成器或者是修正概念。為了能夠找到其他標(biāo)準(zhǔn)生成器或者修正概念，AddExtent對(duì)每一個(gè)MaximalConcept的孩子節(jié)點(diǎn)進(jìn)行遞歸調(diào)用。因?yàn)楦倪M(jìn)算法FastAddExtent避免了很大一部分的無用比較，這個(gè)算法具有更高的效率。相比AddExtent算法，運(yùn)行時(shí)間大大縮減。

3.2 FastAddExtent算法的思路

在一次遞歸的過程中，MaximalConcept的所有孩子節(jié)點(diǎn)的子孫節(jié)點(diǎn)有可能是相同的概念。因此，一個(gè)概念有可能會(huì)被比較幾次，由此將會(huì)造成時(shí)間上的消耗；在查找MaximalConcept的函數(shù)中，使用的也是遞歸調(diào)用的方式，這種方式耗時(shí)較大，為了能夠減少遞歸的次數(shù)，增加了字段，減少了遞歸調(diào)用的次數(shù)，對(duì)減少運(yùn)行時(shí)間上也起到了一定的效果；GetClosure-Concept函數(shù)使用遞歸調(diào)用，如果以某個(gè)外延值為外延的概念在概念格中本身就存在，在原始的AddExtent算法中，函數(shù)也會(huì)進(jìn)行遞歸調(diào)用直至找到該概念，耗時(shí)較大。為了能夠快速找到并返回該概念，這里通過Hash查找的方式（L.Find(extent)）迅速找到已經(jīng)存在概念格的概念，極大減少了運(yùn)行時(shí)間。

本文中提出的改進(jìn)后的FastAddExtent算法和原始的AddExtent算法一樣，都使用了遞歸的方式構(gòu)造概念格。不同的是，F(xiàn)astAddExtent為每個(gè)概念增加了四個(gè)字段：visited、NewConcept、doExtent、MaximalConcept。visited是一個(gè)存儲(chǔ)整型數(shù)字的字段，在每一次增加一個(gè)新的屬性時(shí)，都會(huì)將該屬性值的id傳入到FastAdd-Extent中，如果某次調(diào)用FastAddExtent，在比較visited時(shí)，發(fā)現(xiàn)某個(gè)概念的visited值等于此輪新增屬性的id值，則表示該概念已經(jīng)訪問過。NewConcept字段存儲(chǔ)的是由candidate傳入FastAddExtent函數(shù)之后返回的新概念，一次增加一次屬性的過程中，某個(gè)概念已經(jīng)被訪問過，則把該候選子節(jié)點(diǎn)的NewConcept指向的概念賦給candidate，減少了不必要的遞歸調(diào)用以及不必要的比較。doExtent字段存儲(chǔ)的是傳入FastAddExtent的extent值，使得傳入FastAddExtent的generatorConcept的doExtent字段等于extent，通過GetClosureConcept函數(shù)，將會(huì)得到一個(gè)標(biāo)準(zhǔn)生成器或者是一個(gè)修訂概念。將該標(biāo)準(zhǔn)生成器或者是修訂概念存儲(chǔ)在generatorConcept的MaximalConcept字段，因?yàn)樵谶f歸調(diào)用的過程中需要傳入candidate值，如果傳入的candidate越靠近ClosureConcept，則遞歸查找標(biāo)準(zhǔn)生成器的次數(shù)就會(huì)越少，增加doExtent字段和MaximalConcept字段，就是為了使傳入FastAddExtent的generatorConcept更加接近ClosureConcept。

3.3 FastAddExtent算法描述與分析

FastAddExtent算法主要由三個(gè)函數(shù)組成，分別是 FastAddExtent、GetClosureConcept、CreateLattice-Incrementally，下面將對(duì)每個(gè)函數(shù)的修改部分進(jìn)行詳細(xì)的描述。

3.3.1 函數(shù)FastAddExtent描述

輸入：新建概念的外延extent，新建概念格的初始生成器generatorConcept，已建好的概念格L，添加屬性的id值n。

輸出：新概念newConcept。

步驟1對(duì)初始生成器的doExtent以及Maximal-Concept字段進(jìn)行標(biāo)記。

步驟2通過GetClosureConcept函數(shù)獲得外延值包含于該概念的最小的概念并賦值給generator-Concept，判斷該外延值是否等于extent，如果是，則返回該概念；否則繼續(xù)步驟3。

步驟3獲得該generatorConcept的所有孩子節(jié)點(diǎn)，這些孩子節(jié)點(diǎn)作為newConcept的候選孩子節(jié)點(diǎn)candidate。

步驟4對(duì)每一個(gè)候選孩子節(jié)點(diǎn)candidate，如果外延值與extent值存在包含關(guān)系，則為修改概念；否則需要新建概念，繼續(xù)步驟5。

步驟5如果該candidate在添加屬性過程中已經(jīng)被訪問過，則直接將候選孩子節(jié)點(diǎn)賦值為以該候選節(jié)點(diǎn)為生成器生成的新概念；否則以extent與候選節(jié)點(diǎn)的外延值的交集、候選節(jié)點(diǎn)candidate、已建好的概念格L、n值傳入，進(jìn)入步驟1，將返回的新概念賦值于candidate的NewConcept，并對(duì)該概念進(jìn)行被訪問標(biāo)記，此時(shí)的候選節(jié)點(diǎn)candidate變?yōu)樾律傻男赂拍睢?/p>

步驟6對(duì)newConcept中每一個(gè)孩子節(jié)點(diǎn)進(jìn)行判斷，如果該candidate外延值包含于孩子節(jié)點(diǎn)，則跳出循環(huán)；如果該child外延值包含于候選孩子節(jié)點(diǎn)的外延值，則刪除該child，將候選孩子節(jié)點(diǎn)加入到正式孩子節(jié)點(diǎn)中。完成步驟4。

步驟7將newConcept與每一個(gè)孩子節(jié)點(diǎn)建立關(guān)系，同時(shí)刪除每一個(gè)孩子節(jié)點(diǎn)與生成器generatorConcept之間的聯(lián)系。建立生成器與newConcept的聯(lián)系。

步驟8返回newConcept。

在接下來的段落里，將會(huì)主要介紹FastAddExtent算法相對(duì)AddExtent算法修改部分。至于AddExtent算法的不做修改部分以及使用不變的函數(shù)，可以查閱文獻(xiàn)[11]。

3.3.2 函數(shù)GetClosureConcept描述

輸入：外延值extent，查找最小概念的起點(diǎn)generator-Concept，已生成的概念格。

輸出：標(biāo)準(zhǔn)生成器generatorConcept。

步驟1在Hash表中查找是否存在以extent為外延值的概念。如果存在，則返回該概念；否則步驟2。

步驟2對(duì)已建好的概念格L中，以generator-Concept為起點(diǎn)，從上往下查找，找到外延值包含extent的最小概念。

步驟3返回generatorConcept。

3.3.3 函數(shù)CreateLatticeIncrementally描述

輸入：形式背景G、M、I。

輸出：概念格L。

步驟1讀取形式背景的信息，新建第一個(gè)概念topConcept(G, ? )。

步驟2對(duì)形式背景中的M的每一個(gè)屬性，調(diào)用FastAddExtent，添加屬性至概念格。并將屬性添加至修改概念中。

步驟3返回概念格L。

3.4 FastAddExtent算法案例分析

下面用一個(gè)案例來分析FastAddExtent算法是如何減少運(yùn)行時(shí)間的。表1、表2為增加屬性前后的形式背景，圖2、圖3為增加屬性前后的概念格。

Table 1 Example of formal context before adding attributee表1 增加屬性e之前的背景

Table 2 Example of formal context after adding attributee表2 增加屬性e之后的背景

Fig.2 Concept lattice of formal context in Table 1圖2 表1形式背景的概念格

Fig.3 Concept lattice of formal context in Table 2圖3 表2形式背景的概念格

為了方便查看對(duì)圖3中的各個(gè)概念進(jìn)行標(biāo)號(hào)，標(biāo)號(hào)情況如下：

在一次增加屬性e的過程中，C1為新概念C5的標(biāo)準(zhǔn)生成器，由于C1有兩個(gè)候選子節(jié)點(diǎn)分別對(duì)兩個(gè)候選子節(jié)點(diǎn)的外延與{1,2,3}進(jìn)行交集，此時(shí)C2.NewConcept=C6，C3.NewConcept=C7，并且C2、C3的visited值為5，假設(shè)C6概念相比C7概念先創(chuàng)建。C4是C2的候選子節(jié)點(diǎn)，并且由C4作為標(biāo)準(zhǔn)生成器生成了概念C8，并且返回C8，則C4.NewConcept=C8，C4.visited=5。當(dāng)創(chuàng)建C7概念時(shí)，C7的候選子節(jié)點(diǎn)為C4，由于C4.visited=5，C4是第二次訪問，則直接把C4.NewConcept賦給C7的候選子節(jié)點(diǎn)candidate。這一過程中，省去了一次遞歸調(diào)用和后續(xù)諸多的比較，極大減少了運(yùn)行時(shí)間。在概念格規(guī)模龐大的時(shí)候，此時(shí)的效果更加明顯。

3.5 實(shí)驗(yàn)評(píng)估及分析

為了證明文中提出的改進(jìn)算法的有效性，使用了Python語言分別實(shí)現(xiàn)了改進(jìn)的FastAddExtent和原始的AddExtent算法。所有的實(shí)驗(yàn)都是在一臺(tái)裝有64位操作系統(tǒng)，core i5 4590（3.7 GHz），8.0 GB內(nèi)存的計(jì)算機(jī)上運(yùn)行。

FastAddExtent算法雖然相比AddExtent算法在時(shí)間復(fù)雜度上并未作出改進(jìn)，時(shí)間復(fù)雜度仍是O(|L||G||M|3)[4]，但是通過增加四個(gè)字段以及改變數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，以減少不必要的比較，能夠快速定位標(biāo)準(zhǔn)生成器，大大減少運(yùn)行時(shí)間。

整個(gè)實(shí)驗(yàn)所使用的數(shù)據(jù)集均為隨機(jī)生成，這幾種數(shù)據(jù)集的填充率(|I|/|G||M|)各不相同，分別為10%、24%和40%。對(duì)象個(gè)數(shù)固定為50，但是屬性的個(gè)數(shù)則是變化的，而且每個(gè)屬性所對(duì)應(yīng)的對(duì)象個(gè)數(shù)也不一樣。

圖4展示了FastAddExtent算法和AddExtent算法在填充率為10%（低密度）的數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比。實(shí)驗(yàn)數(shù)據(jù)從100個(gè)屬性開始增加到30 000，對(duì)象個(gè)數(shù)保持在50不變，由實(shí)驗(yàn)結(jié)果得到的折線圖可知，在低密度下并且對(duì)象保持個(gè)數(shù)為50不變，屬性個(gè)數(shù)相對(duì)較少的情況下，F(xiàn)astAddExtent算法和AddExtent算法在時(shí)間上沒有明顯的差別。但是，隨著屬性個(gè)數(shù)的不斷增加，F(xiàn)astAddExtent算法相比AddExtent算法在運(yùn)行時(shí)間的優(yōu)勢(shì)明顯，并且有逐漸拉大差距的趨勢(shì)（當(dāng)|M|大約在2 500時(shí)，F(xiàn)astAddExtent算法運(yùn)行時(shí)間低于AddExtent算法）。

Fig.4 Comparison results of concept lattice construction with low density圖4 低填充率下概念格構(gòu)建結(jié)果比較

Fig.5 Comparison results of concept lattice construction with medium density圖5 中等填充率下概念格構(gòu)建結(jié)果比較

圖5顯示了FastAddExtent算法和AddExtent在填充率為24%（中等密度）的數(shù)據(jù)集上運(yùn)行時(shí)間結(jié)果的比較。實(shí)驗(yàn)從屬性個(gè)數(shù)25開始增加到10 000，實(shí)驗(yàn)期間，對(duì)象個(gè)數(shù)保持50不變。從折線圖5中可以看出，相比填充率為10%的結(jié)果圖，在中等填充率下，相同對(duì)象個(gè)數(shù)、相同屬性個(gè)數(shù)之間運(yùn)行時(shí)間差距拉大。同時(shí)，F(xiàn)astAddExtent算法在屬性個(gè)數(shù)較少的情況下也能獲得運(yùn)行時(shí)間上的較大優(yōu)勢(shì)（當(dāng)|M|大約在1 250時(shí)，F(xiàn)astAddExtent算法運(yùn)行時(shí)間低于AddExtent算法）。

圖6展示了FastAddExtent算法和AddExtent算法在填充率為40%（高密度）的隨機(jī)數(shù)據(jù)集上的運(yùn)行時(shí)間的比較結(jié)果。實(shí)驗(yàn)從屬性個(gè)數(shù)為10個(gè)開始進(jìn)行，直至增加到1 000個(gè)，期間對(duì)象個(gè)數(shù)保持50不變。由于在高密度的數(shù)據(jù)集下，產(chǎn)生的概念的個(gè)數(shù)巨大，概念格的規(guī)模龐大，對(duì)內(nèi)存資源的消耗非常迅速。于是，在現(xiàn)有的實(shí)驗(yàn)條件下，只能對(duì)屬性個(gè)數(shù)較少的部分進(jìn)行測(cè)試。從實(shí)驗(yàn)得到的折線圖可以直觀地看出，相比填充率為10%和24%的情況，F(xiàn)astAdd-Extent算法和AddExtent算法在運(yùn)行時(shí)間上都快速上升。相比圖4和圖5的實(shí)驗(yàn)顯示，相交的點(diǎn)在橫坐標(biāo)下提前了許多，并且FastAddExtent算法和AddExtent算法在交匯點(diǎn)之后的每一個(gè)測(cè)試點(diǎn)都具有明顯的優(yōu)勢(shì)（當(dāng)|M|大約在100時(shí)，F(xiàn)astAddExtent算法運(yùn)行時(shí)間低于AddExtent算法）。

Fig.6 Comparison results of concept lattice construction with high density圖6 高填充率下概念格構(gòu)建結(jié)果比較

4 結(jié)束語

向概念格中添加屬性的增量式算法可以用來構(gòu)造概念格也可以用來更新概念格。介紹了一種快速有效的增量式概念格構(gòu)造算法FastAddExtent。該算法是在已有的AddExtent算法下增加了字段，在GetClosureConcept函數(shù)下引用Hash查找函數(shù)的方法，減少了不必要的比較，從而減少了運(yùn)行時(shí)間。

FastAddExtent算法采用哈希表的方式存儲(chǔ)概念，它幾乎能在所有的測(cè)試點(diǎn)上獲得明顯的優(yōu)勢(shì)，而且即便是在屬性個(gè)數(shù)較少的稀疏數(shù)據(jù)集上也能花費(fèi)比AddExtent算法更少的時(shí)間，而且雙方之間的性能差距會(huì)隨著屬性個(gè)數(shù)的增大而增大。理論分析和性能測(cè)試都有說明，在對(duì)象個(gè)數(shù)較大的情況下應(yīng)用FCA方法時(shí)，F(xiàn)astAddExtent算法是一種相比AddExtent算法更好的選擇。