徐霽琳，徐健鋒,,3+，劉 龍，吳方文

1.南昌大學(xué) 信息工程學(xué)院，南昌330031

2.南昌大學(xué) 軟件學(xué)院，南昌330047

3.同濟(jì)大學(xué) 電子與信息工程學(xué)院，上海201804

+通信作者E-mail:jianfeng_x@ncu.edu.cn

人在認(rèn)知過(guò)程中，把所感覺(jué)到的具有共同特點(diǎn)的事物抽取出來(lái)，加以概括，稱之為概念。基于這個(gè)哲學(xué)中對(duì)“概念”的描述，德國(guó)數(shù)學(xué)家Wille 提出形式概念分析（formal concept analysis，F(xiàn)CA）[1-2]。將哲學(xué)中的概念數(shù)學(xué)化、形式化，進(jìn)而構(gòu)造能夠可視化表達(dá)的概念格。

概念格本質(zhì)上是通過(guò)一對(duì)誘導(dǎo)算子導(dǎo)出的二元層次概念結(jié)構(gòu)，體現(xiàn)了概念的外延和內(nèi)涵的統(tǒng)一。同時(shí)，概念格所蘊(yùn)含的偏序關(guān)系，不僅能夠反映對(duì)象和屬性的關(guān)聯(lián)，而且還包含了概念間的泛化和例化關(guān)系。因此，概念格成為了一種數(shù)據(jù)分析和規(guī)則獲取的有效工具，在知識(shí)發(fā)現(xiàn)、數(shù)據(jù)挖掘、信息檢索、軟件工程、語(yǔ)義Web、本體研究等很多領(lǐng)域得到廣泛應(yīng)用。

從1982 年形式概念分析提出到現(xiàn)在，概念格作為形式概念分析的熱點(diǎn)，得到了學(xué)術(shù)界的廣泛關(guān)注。概念格的主要研究方向有構(gòu)造、約簡(jiǎn)、規(guī)則提取等[3-10]，其中動(dòng)態(tài)概念格的構(gòu)造是概念格理論研究的重要研究任務(wù)。在動(dòng)態(tài)概念格的構(gòu)造研究領(lǐng)域中，曾利程等人[11]提出的FastAddExtent 算法通過(guò)增加四個(gè)字段有效地避免了概念之間不必要的比較，通過(guò)Hash 查找快速定位概念，從而使構(gòu)建概念格的效率隨著概念數(shù)量的增加有了突破性的進(jìn)展。王春月等人[12]提出將節(jié)點(diǎn)細(xì)分成四類，并根據(jù)分類對(duì)概念格進(jìn)行更新。張磊等人[13]分析了原概念格和新概念格中節(jié)點(diǎn)間的映射關(guān)系以及變化規(guī)律，提出了自頂向下和自底向上兩種漸進(jìn)式的概念格屬性漸減算法。姜琴等人[14]分析當(dāng)前節(jié)點(diǎn)類型以做相應(yīng)處理，新概念格中的節(jié)點(diǎn)是由原有概念格中的節(jié)點(diǎn)直接修改而來(lái)，并不產(chǎn)生新的概念。馬垣等人[15]研究了減少多個(gè)屬性的一次性漸減式算法，與單屬性的漸減式算法相比，在減少多個(gè)屬性時(shí)該算法只需執(zhí)行一次。

隨著計(jì)算機(jī)、網(wǎng)絡(luò)和通信技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)信息資源呈爆炸式增長(zhǎng)。高速、海量和動(dòng)態(tài)的流數(shù)據(jù)成為了大數(shù)據(jù)的重要組成部分，但是隨著時(shí)間的推移，流數(shù)據(jù)常常以不可預(yù)知的方式發(fā)生變化。這種現(xiàn)象被稱之為概念漂移（concept drift，CD）。在動(dòng)態(tài)流數(shù)據(jù)環(huán)境中的概念格計(jì)算也可能存在概念漂移，即由于時(shí)間的變化和數(shù)據(jù)的不斷產(chǎn)生，從概念格中提取的規(guī)則可能不再適用于當(dāng)前數(shù)據(jù)。例如，圖書(shū)信息概念格中的關(guān)聯(lián)規(guī)則，將書(shū)名與關(guān)鍵詞等信息緊密聯(lián)系起來(lái)，但隨著時(shí)間的變化，一些書(shū)籍的關(guān)鍵詞也會(huì)發(fā)生變化，此時(shí)用最新的關(guān)鍵詞信息來(lái)尋找書(shū)籍將導(dǎo)致搜索錯(cuò)誤。流數(shù)據(jù)知識(shí)挖掘中普遍存在的概念漂移已經(jīng)成為近年來(lái)的機(jī)器學(xué)習(xí)領(lǐng)域的熱點(diǎn)問(wèn)題，但是采用滑動(dòng)窗口方法解決概念格漂移問(wèn)題的文章，目前尚無(wú)文獻(xiàn)報(bào)道。

針對(duì)這些研究現(xiàn)狀，基于上述研究成果，本文提出面向滑動(dòng)窗口方法的概念格漂移計(jì)算研究。主要研究?jī)?nèi)容包括：首先，采用滑動(dòng)窗口策略來(lái)保留最新數(shù)據(jù)以適應(yīng)概念漂移現(xiàn)象；然后對(duì)滑動(dòng)窗口中的形式概念變化機(jī)理進(jìn)行討論，以解決動(dòng)態(tài)概念格構(gòu)造問(wèn)題；最后基于上述理論基礎(chǔ)，總結(jié)出面向滑動(dòng)窗口法的動(dòng)態(tài)概念格構(gòu)造算法，并用實(shí)例說(shuō)明該算法的有效性和高效性。

1 基礎(chǔ)知識(shí)

假設(shè)(G,M,I)是形式背景，其中G為對(duì)象集，M為屬性集，I為G與M之間的二元關(guān)系，I?G×M。若(g,m)∈I，則表示對(duì)象g擁有屬性m。若(g,m)?I，則表示對(duì)象g不擁有屬性m。

為了更好地描述概念，德國(guó)數(shù)學(xué)家Wille 在文獻(xiàn)[1]中提出，可以引入兩個(gè)誘導(dǎo)算子：對(duì)于任意的X?G，B?M，有X*={m|m∈M,?g∈X,(g,m)∈I}，B*={g|g∈G,?m∈B,(g,m)∈I}。

X*表示X中所有對(duì)象共同擁有的屬性的集合，B*表示共同擁有B中所有屬性的對(duì)象的集合。

定義1（形式概念）如果有一個(gè)二元組(X,B)，滿足X*=B，并且B*=X，則稱(X,B)是一個(gè)形式概念，簡(jiǎn)稱概念。其中X稱為概念的外延，B稱為概念的內(nèi)涵。

定義2（概念格）用L(G,M,I) 表示形式背景(G,M,I)的全體概念，若(X1,B1)和(X2,B2)是形式概念，則將兩個(gè)形式概念上的偏序關(guān)系定義為(X1,B1)≤(X2,B2)?X1?X2(?B1?B2)。并且將(X1,B1)和(X2,B2)下確界定義為(X1,B1)∧(X2,B2)=(X1?X2,(B1?B2)**)，上確界定義為(X1,B1)∨(X2,B2)=((X1?X2)**,B1?B2)，二者都是概念。從而L(G,M,I) 是完備格，稱為形式背景(G,M,I)的概念格。

例1表1 是一個(gè)形式背景(G,M,I)，其中對(duì)象集是G={1,2,3,4}，屬性集是M={a,b,c,d}，如果(g,m)∈I，則在表中記為1；如果(g,m)?I，則在表中記為0。表2 是表1 形式背景(G,M,I)所對(duì)應(yīng)的形式概念，其概念格如圖1 所示。

Table 1 Formal context(G,M,I)表1 形式背景(G,M,I)

Table 2 Formal concept corresponding to formal context in table 1表2 表1 的形式背景所對(duì)應(yīng)的形式概念

Fig.1 Concept lattice corresponding to formal context in table 1圖1 表1 形式背景對(duì)應(yīng)的概念格

2 滑動(dòng)窗口中動(dòng)態(tài)概念的更新

本章主要討論滑動(dòng)窗口中動(dòng)態(tài)概念的變化機(jī)理，為后續(xù)動(dòng)態(tài)概念格的更新做好準(zhǔn)備。

2.1 滑動(dòng)窗口中數(shù)據(jù)的變化形態(tài)分析

根據(jù)數(shù)據(jù)的動(dòng)態(tài)特征，滑動(dòng)窗口中的數(shù)據(jù)一般有三種變化形態(tài)。

形態(tài)1簡(jiǎn)單形態(tài)。在該形態(tài)下相鄰兩次的計(jì)算時(shí)間間隔長(zhǎng)，每次計(jì)算的時(shí)候，在滑動(dòng)窗口中只有新的數(shù)據(jù)，沒(méi)有上次計(jì)算使用的舊數(shù)據(jù)。

形態(tài)2單一對(duì)象形態(tài)。在該形態(tài)下相鄰兩次的計(jì)算時(shí)間間隔極小，因此，在滑動(dòng)窗口中的計(jì)算對(duì)象只增加一條新數(shù)據(jù)，同時(shí)只減少了一條上次計(jì)算使用的舊數(shù)據(jù)。

形態(tài)3批量對(duì)象形態(tài)。在該形態(tài)下相鄰兩次的計(jì)算時(shí)間間隙稍大，滑動(dòng)窗口中的數(shù)據(jù)，都是在上次計(jì)算遺留數(shù)據(jù)的基礎(chǔ)上，增加一小批新數(shù)據(jù)，同時(shí)減少等量的一小批上次計(jì)算使用的舊數(shù)據(jù)。

在本文中，流入和流出對(duì)象后，滑動(dòng)窗口中有三種變化形態(tài)。在第一種形態(tài)下，滑動(dòng)窗口中沒(méi)有舊的對(duì)象，只有新的對(duì)象，對(duì)于動(dòng)態(tài)概念格構(gòu)造的研究意義不大，因此不予討論。第二種形態(tài)是第三種形態(tài)的極端特殊形態(tài)，因此這篇文章將動(dòng)態(tài)概念的第三種變化形態(tài)作為研究對(duì)象，進(jìn)行面向滑動(dòng)窗口方法的概念格漂移計(jì)算研究。

2.2 符號(hào)約定

假設(shè)在T時(shí)刻的滑動(dòng)窗口中，形式背景表示為K(t)=(G(t),M(t),I(t))，概念格表示為L(zhǎng)(t)=(G(t),M(t),I(t))，(O,P)為概念格L(t)的節(jié)點(diǎn)；那么在T+1 時(shí)刻的滑動(dòng)窗口中，形式背景表示為K(t+1)=(G(t+1),M(t+1),I(t+1))，概念格表示為L(zhǎng)(t+1)=(G(t+1),M(t+1),I(t+1))。

T+1 時(shí)刻，流入滑動(dòng)窗口的對(duì)象表示為，流出滑動(dòng)窗口的對(duì)象表示為?；诨瑒?dòng)窗口方法的概念格漂移計(jì)算研究，就是求滑動(dòng)窗口中T+1 時(shí)刻的概念格L(t+1)=(G(t+1),M(t+1),I(t+1))。

2.3 滑動(dòng)窗口中動(dòng)態(tài)概念的變化機(jī)理

滑動(dòng)窗口中的動(dòng)態(tài)概念變化情況一共有五種，分別是流入流出概念相同、流入流出概念不同、流入流出概念部分相交、流入概念包含流出概念和流出概念包含流入概念。接下來(lái)針對(duì)這五種變化現(xiàn)象進(jìn)行討論。

最后，還要考慮到流入滑動(dòng)窗口的對(duì)象中，是否有部分對(duì)象已經(jīng)存在于T時(shí)刻的滑動(dòng)窗口中，如果有，因?yàn)檫@些已經(jīng)存在的對(duì)象流入概念格不會(huì)對(duì)其產(chǎn)生影響，所以計(jì)算的時(shí)候還要減去這一已經(jīng)存在的部分，即

下面在表3 中進(jìn)行總結(jié)，在表格中列出了T+1時(shí)刻時(shí)，滑動(dòng)窗口中對(duì)象的變化。

Table 3 Change of object in sliding window at time T+1表3 T+1 時(shí)刻滑動(dòng)窗口中對(duì)象的變化

例2T+1 時(shí)刻，向例1 形式背景下的滑動(dòng)窗口中流入對(duì)象3、4、5，流出對(duì)象1、2、3。

由表3 可知，在概念格更新時(shí)，只需要計(jì)算T時(shí)刻的概念格增加對(duì)象5，刪除對(duì)象1、2 后的概念格。與現(xiàn)有的概念格更新算法相比，減少了更新步驟，提高了算法的效率，減少了時(shí)間復(fù)雜度。

3 滑動(dòng)窗口中動(dòng)態(tài)概念格的更新

本章主要介紹T+1 時(shí)刻，更新滑動(dòng)窗口中動(dòng)態(tài)概念的概念格所需要的相關(guān)定義及定理。

第2 章已經(jīng)討論了滑動(dòng)窗口中動(dòng)態(tài)概念的變化機(jī)理，通過(guò)最后得到的結(jié)論，可以很輕易地得到滑動(dòng)窗口中實(shí)際上流入和流出的對(duì)象

在動(dòng)態(tài)概念格更新的過(guò)程中，增加對(duì)象和刪除對(duì)象的前后順序?qū)r(shí)間復(fù)雜度影響不大，因此對(duì)于更新先后順序不做要求。在這篇論文中，采取先刪除對(duì)象后增加對(duì)象的順序。

定義3（流出-不變節(jié)點(diǎn)）若，則節(jié)點(diǎn)(O,P)為流出-不變節(jié)點(diǎn)。

定義4（刪除節(jié)點(diǎn)）若，并且節(jié)點(diǎn)(O,P) 的某一子節(jié)點(diǎn)的外延等于O-H，那么稱(O,P)為刪除節(jié)點(diǎn)。

定義5（更新節(jié)點(diǎn)）若，并且節(jié)點(diǎn)(O,P)的任意子節(jié)點(diǎn)的外延都不等于O-H，那么稱(O,P)為更新節(jié)點(diǎn)。

根據(jù)定義將T時(shí)刻的概念格L(t)中的節(jié)點(diǎn)分類，然后分別對(duì)這些節(jié)點(diǎn)進(jìn)行更新。

定理1若節(jié)點(diǎn)(O,P)為流出-不變節(jié)點(diǎn)，則(O,P)∈L(t+1)。

證明設(shè)(O,P)∈L(t)，且為流出-不變節(jié)點(diǎn)，則。由于(O,P)∈L(t)，根據(jù)定義1 可知，O*=P且P*=O。由于，并且在L(t)與L(t+1)中，O與P的關(guān)系I不發(fā)生變化，因此在T+1時(shí)刻，仍然存在O*=P，且P*=O，(O,P)∈L(t+1)。

定理2若節(jié)點(diǎn)(O,P) 為刪除節(jié)點(diǎn)，那么(O,P)?L(t+1)。

證明設(shè)(O,P)∈L(t)，且為刪除節(jié)點(diǎn)，則存在H=-G′?O，使得節(jié)點(diǎn)(O,P) 的某一子節(jié)點(diǎn)的外延等于O-H，因此在L(t)中，存在節(jié)點(diǎn)(O,P)和節(jié)點(diǎn)(O-H,Q)。根據(jù)定義1 可知，O*=P，(O-H)*=Q。由于H∈O，T+1 時(shí)刻，刪除對(duì)象H后，在L(t+1)中(O,P) 更新為(O-H,P)，但(O-H)*=Q，因此根據(jù)定義1可知，(O-H,P)不是形式概念，(O,P)?L(t+1)。

定理3若節(jié)點(diǎn)(O,P)為更新節(jié)點(diǎn)，則P)∈L(t+1)。

證明設(shè)(O,P)∈L(t)，且為更新節(jié)點(diǎn)，則存在H=-G′?O，使得節(jié)點(diǎn)(O,P)的任意子節(jié)點(diǎn)的外延都不等于O-H。根據(jù)定義1 可知，O*=P且P*=O。由于H∈O，根據(jù)形式概念的定義可知，當(dāng)概念的外延減少時(shí)，內(nèi)涵增加，因此H*?P，(O-H)*?P。

假設(shè)(O-H)*≠P，那么(O-H)*?P。同時(shí)((OH)*-P)?H*≠?，該等式等價(jià)于(O-H)*?H*-P?H*≠?。由于H*?P，因此(O-H)*?H*-P≠?，根據(jù)定義可知(O-H)*?H*=P，故上述等式不成立，假設(shè)也不成立。

因此(O-H)*=P，根據(jù)定義1 可知，(O-H,P)是形式概念，

根據(jù)上述定義定理將流出對(duì)象后的概念格進(jìn)行更新，然后再考慮添加對(duì)象后概念格的更新。從表3可以得到實(shí)際上添加的對(duì)象，如果將這些對(duì)象分別與L(t)中的節(jié)點(diǎn)進(jìn)行對(duì)比之后再更新，步驟多，而且時(shí)間復(fù)雜度大。

比如，當(dāng)實(shí)際上添加的對(duì)象為(1,ab)和(2,ab)時(shí)，按照之前的方法，需要將(1,ab)與(2,ab)分別和L(t)中的節(jié)點(diǎn)進(jìn)行對(duì)比。但是如果將為(1,ab)和(2,ab)構(gòu)造概念格-L′，那么此時(shí)概念格-L′中只有(12,ab)，因此只需要對(duì)比1次。因此時(shí)間復(fù)雜度會(huì)比前一種方法小。

因此，先將實(shí)際上添加的對(duì)象-G′單獨(dú)構(gòu)造概念格，能夠進(jìn)一步減少時(shí)間復(fù)雜度，提高算法的效率。

定義6（相等）若B=P，則稱(A,B)與節(jié)點(diǎn)(O,P)相等。

定義7（流入-不變節(jié)點(diǎn)）若B?P=?，則節(jié)點(diǎn)(O,P)稱為流入-不變節(jié)點(diǎn)。

定義8（上層節(jié)點(diǎn)）若B?P，則稱(A,B)為節(jié)點(diǎn)(O,P)的上層節(jié)點(diǎn)。

定義9（下層節(jié)點(diǎn)）若P?B，則稱(A,B)為節(jié)點(diǎn)(O,P)的下層節(jié)點(diǎn)。

定義10（生成新概念節(jié)點(diǎn)）若H=B?P≠?，且滿足以下條件：（1）H與(A,B)和L(t)中的任一節(jié)點(diǎn)的內(nèi)涵都不相等；（2）H與(A,B)和L(t)中的任一節(jié)點(diǎn)的交集不等于H，則稱節(jié)點(diǎn)(O,P)為生成新概念節(jié)點(diǎn)。

通過(guò)這些定義，可以將L(t)中的節(jié)點(diǎn)分類，然后根據(jù)不同的分類，采取不同的定理對(duì)概念格進(jìn)行更新。

定理4設(shè)(A,B)為概念格的節(jié)點(diǎn)，(O,P)為概念格L(t)的節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)(A,B)與節(jié)點(diǎn)(O,P)相等時(shí)，(A?O,B)∈L(t+1)，(O,P)?L(t+1)，(A,B)?L(t+1)。

證明設(shè)(O,P)∈L(t)，且(A,B)與(O,P)相等，因此B=P。根據(jù)定義1 可知，O*=P，P*=O，A*=B，B*=A。由于A?O=?，B=P，那么(A?O)*=B=P，(A?O,B)∈L(t+1)。

同時(shí)由于B*=A?O≠A，P*=A?O≠O，根據(jù)定義1 可知，(A,B) 和(O,P) 不再是形式概念，因此(O,P)?L(t+1)，(A,B)?L(t+1)。

根據(jù)定義1 可知，文獻(xiàn)[1]中將X*和B*分別定義為X的所有對(duì)象共同擁有的屬性的集合，與所有擁有屬性B的對(duì)象的集合。因此對(duì)于定理4 能夠很好地理解，新添加的概念中，由于對(duì)象擁有該節(jié)點(diǎn)的屬性，因此能夠直接將對(duì)象添加進(jìn)去。

定理5設(shè)(A,B) 為的節(jié)點(diǎn)，(O,P)為概念格L(t)的節(jié)點(diǎn)。當(dāng)(O,P)為流入-不變節(jié)點(diǎn)時(shí)，則(O,P)∈L(t+1)，(A,B)∈L(t+1)。

證明設(shè)(O,P)∈L(t)，且為流入-不變節(jié)點(diǎn)，根據(jù)定義1 可知，O*=P，P*=O。(A,B) 為概念格的節(jié)點(diǎn)，則存在A*=B且B*=A。由于B?P=?，在形式背景K(t+1)=(G(t)?A,M(t+1),I(t+1)) 中，關(guān)系I不發(fā)生變化，因此在新的概念格中，仍然存在O*=P，P*=O，A*=B和B*=A，故(O,P)∈L(t+1)，(A,B)∈L(t+1)。

定理6設(shè)(A,B) 為的節(jié)點(diǎn)，(O,P)為概念格L(t)的節(jié)點(diǎn)。若(A,B)為節(jié)點(diǎn)(O,P)的上層節(jié)點(diǎn)，那么(A?O,B)∈L(t+1)，(O,P)∈L(t+1)，(A,B)?L(t+1)。

證明設(shè)(O,P)∈L(t)，且(A,B)為節(jié)點(diǎn)(O,P)的上層節(jié)點(diǎn)，則B?P，并且根據(jù)定義1 可知，O*=P，P*=O，A*=B，B*=A。由于A?O=?，B?P=B，那么(A?O)*=B，因此(A?O,B)∈L(t+1)。

同時(shí)仍然存在O*=P，并且P*=O，因此(O,P)∈L(t+1)。但是B*=A?O≠A，根據(jù)定義1 可知，(A,B)不再是形式概念，因此(A,B)?L(t+1)。

定理7設(shè)(A,B) 為的節(jié)點(diǎn)，(O,P)為概念格L(t)的節(jié)點(diǎn)。若節(jié)點(diǎn)(A,B)為節(jié)點(diǎn)(O,P)的下層節(jié)點(diǎn)，那么(A?O,P)∈L(t+1)，(O,P)?L(t+1)，(A,B)∈L(t+1)。

證明設(shè)(O,P)∈L(t)，且(A,B)為節(jié)點(diǎn)(O,P)的下層節(jié)點(diǎn)，則P?B，并且根據(jù)定義1 可知，O*=P，P*=O，A*=B，B*=A。由于A?O=?，B?P=P，那么(A?O)*=P，因此(A?O,P)∈L(t+1)。

同時(shí)仍然存在A*=B，并且B*=A，因此(A,B)∈L(t+1)。但是P*=A?O≠O，根據(jù)定義1 可知，(O,P)不再是形式概念，因此(O,P)?L(t+1)。

定理8設(shè)(A,B) 為 的節(jié)點(diǎn)，(O,P)為概念格L(t)的節(jié)點(diǎn)。當(dāng)(O,P)為生成新概念節(jié)點(diǎn)，則(A?O,B?P)∈L(t+1)，(O,P)∈L(t+1)，(A,B)∈L(t+1)。

證明設(shè)(O,P)∈L(t)，當(dāng)(O,P)為生成新概念節(jié)點(diǎn)，則存在H=B?P≠?，并且根據(jù)定義1 可知，O*=P，P*=O，A*=B，B*=A。由于A?O=?，B?P=H，那么(A?O)*=H，因此(A?O,H)∈L(t+1)，即(A?O,B?P)∈L(t+1)。同時(shí)仍然存在，O*=P，P*=O，A*=B，B*=A，因此(A,B)∈L(t+1)，(O,P)∈L(t+1)。

例3已知T時(shí)刻，概念格如圖1 所示，T+1 時(shí)刻，流入對(duì)象345，流出對(duì)象123，根據(jù)表3 可知，只需要計(jì)算增加概念(5,ab)和刪除對(duì)象12 后的概念格。

根據(jù)定義3～5 可知，流出-不變節(jié)點(diǎn)有(?,M)，刪除 節(jié)點(diǎn)有(1,abd)、(124,ab)，更新節(jié)點(diǎn)有(24,abc)、(13,d)、(G,?)。

因此根據(jù)定理1～3，將L(t)中(1,abd)、(124,ab)刪除，(?,M)保持不變，(24,abc)、(13,d)、(G,?)更新為(4,abc)、(3,d)、(34,?)。流出對(duì)象后的概念格如圖2所示。

Fig.2 Concept lattice after objects flow out in table 1圖2 表1 流出對(duì)象后的概念格

自頂向下遍歷，將(5,ab)與圖2 中各個(gè)節(jié)點(diǎn)進(jìn)行對(duì)比。首先??ab，由定義9 可知，(5,ab)為(34,?)的下層節(jié)點(diǎn)，根據(jù)定理7 將(34,?)更新為(345,?)，并將(5,ab)加入到概念格中。

然后d?ab=?，由定義7 可知，(3,d)為流入-不變節(jié)點(diǎn)。最后由于abc?ab，根據(jù)定義8 可知，(5,ab)為(4,abc)上層節(jié)點(diǎn)，根據(jù)定理6，(5,ab)更新為(45,ab)添加到概念格中。更新后的概念格如圖3 所示。

Fig.3 Concept lattice after objects flow into fig.2圖3 圖2 流入對(duì)象后的概念格

4 基于滑動(dòng)窗口的概念格漂移計(jì)算算法

基于上述模型理論推理，可以設(shè)計(jì)出面向滑動(dòng)窗口方法的概念格漂移計(jì)算算法（calculation of concept lattice drift based on sliding window method，CLD_SW），具體算法如下。

輸入：T時(shí)刻，滑動(dòng)窗口中的形式背景K(t)=(G(t),M(t),I(t))，概念格L(t)=(G(t),M(t),I(t))。T+1 時(shí)刻，流入的對(duì)象，流出的對(duì)象。

輸出：T+1時(shí)刻，概念格L(t+1)=(G(t+1),M(t+1),I(t+1))。

步驟1根據(jù)表3 計(jì)算T+1 時(shí)刻，實(shí)際上流入和流出的對(duì)象并計(jì)算實(shí)際流入對(duì)象所構(gòu)成的概念格。

步驟2自頂向下遍歷L(t)的節(jié)點(diǎn)，并將流出的對(duì)象與這些節(jié)點(diǎn)一一對(duì)比，根據(jù)定義3～5，將這些節(jié)點(diǎn)分類。

步驟3根據(jù)步驟2 中節(jié)點(diǎn)的分類，通過(guò)定理1～3，對(duì)概念格進(jìn)行更新。

步驟4自頂向下遍歷L(t)的節(jié)點(diǎn)，并選取概念格中任一節(jié)點(diǎn)(A,B)，與其對(duì)比。根據(jù)定義6～10 和定理4～8，將步驟3 更新后的概念格進(jìn)行更新。

步驟5返回步驟4，直到概念格中的節(jié)點(diǎn)對(duì)比完畢。

步驟6刪除重復(fù)冗余的節(jié)點(diǎn)后，得到T+1 時(shí)刻最終的概念格L(t+1)=(G(t+1),M(t+1),I(t+1))。

通過(guò)這個(gè)算法可以得到T+1 時(shí)刻，滑動(dòng)窗口中動(dòng)態(tài)概念的概念格。算法在最開(kāi)始的時(shí)候，對(duì)滑動(dòng)窗口的動(dòng)態(tài)概念變化的五種情況進(jìn)行討論，得到實(shí)際上動(dòng)態(tài)概念的變化，使得概念格在更新的時(shí)候，不需要對(duì)所有變化的對(duì)象進(jìn)行更新。采用滑動(dòng)窗口策略，可有效地適應(yīng)概念格中可能會(huì)發(fā)生的概念漂移現(xiàn)象。同時(shí)基于現(xiàn)有的概念格更新算法，對(duì)這些算法進(jìn)行改進(jìn)，極大地提高了概念格更新的效率，減少了時(shí)間復(fù)雜度。

5 實(shí)例與分析

T時(shí)刻的滑動(dòng)窗口中，有這樣的一些數(shù)據(jù)，已知形式背景中G={1,2,3,4,5}，M={a,b,c,d,e}。G與M的關(guān)系，如表4 形式背景中所示，當(dāng)G中的某個(gè)對(duì)象擁有M中的某個(gè)屬性時(shí)，在表中表示為1，否則表示為0。

Table 4 Formal context(G,M,I)of instance表4 實(shí)例的形式背景(G,M,I)

通過(guò)定義1 可以求出表4 形式背景所對(duì)應(yīng)的形式概念，如：對(duì)象1 擁有屬性bd，但是共同擁有屬性bd的對(duì)象有14，因此根據(jù)定義1 可知(1,bd)不是形式概念；對(duì)象2 擁有屬性ace，同時(shí)共同擁有屬性ace的也只有對(duì)象2，因此根據(jù)定義1 可知(2,ace)是形式概念。具體情況如表5 所示。

Table 5 Formal concept corresponding to formal context in table 4表5 表4 的形式背景所對(duì)應(yīng)的形式概念

由于形式概念存在一定的偏序關(guān)系，因此可以用Hasse 圖表示出來(lái)，該形式背景所對(duì)應(yīng)的概念格如圖4 所示。

Fig.4 Concept lattice corresponding to formal context in table 4圖4 表4 形式背景對(duì)應(yīng)的概念格

隨著時(shí)間的變化，在T+1 時(shí)刻，已知流入滑動(dòng)窗口的對(duì)象為4567，根據(jù)滑動(dòng)窗口中動(dòng)態(tài)概念的特征，由于滑動(dòng)窗口的尺寸大小是固定不變的，因此有多少數(shù)據(jù)流入滑動(dòng)窗口中，就有等量的數(shù)據(jù)流出滑動(dòng)窗口，因此假定流出滑動(dòng)窗口的對(duì)象為1234。

5.1 CLD_SW 計(jì)算實(shí)例

按照第4 章中的基于滑動(dòng)窗口的概念格漂移計(jì)算算法對(duì)概念格進(jìn)行更新。

步驟1首先找出實(shí)際上流入和流出的對(duì)象和，并計(jì)算實(shí)際流入對(duì)象所構(gòu)成的概念格。第2 章已經(jīng)討論了滑動(dòng)窗口中的動(dòng)態(tài)概念變化機(jī)理，通過(guò)表3 可以很輕易地得知，實(shí)際上流出滑動(dòng)窗口的對(duì)象為123，流入滑動(dòng)窗口的對(duì)象為67。同時(shí)對(duì)象67與屬性的關(guān)系為(6,ace)，(7,abe)。它們所構(gòu)成的概念格節(jié)點(diǎn)分別為(6,ace)，(7,abe)，(67,ae)。

步驟2自頂向下遍歷L(t)的節(jié)點(diǎn)，并將流出的對(duì)象與這些節(jié)點(diǎn)一一對(duì)比，根據(jù)定義3～5，將這些節(jié)點(diǎn)分類。因此已知實(shí)際流出對(duì)象123，根據(jù)定義3～5可以將T時(shí)刻的概念進(jìn)行分類，流出-不變節(jié)點(diǎn)有(?,abcde)，(4,bcd)，刪除節(jié)點(diǎn)有(24,c)，(134,b)，(14,bd)，(3,abe)，(2,ace)，更新節(jié)點(diǎn)有(12345,?)，(235,ae)。

步驟3將T時(shí)刻中概念格節(jié)點(diǎn)分類后，算法要求根據(jù)定理1～3 將刪除節(jié)點(diǎn)(24,c)，(134,b)，(14,bd)，(3,abe)，(2,ace)刪除，并將更新節(jié)點(diǎn)更新為(45,?)，(5,ae)。更新后的概念格如圖5 所示。

步驟4自頂向下遍歷L(t)的節(jié)點(diǎn)，并選取(6,ace)，(7,abe)，(67,ae)中任一概念，分別與其對(duì)比。根據(jù)定義6～10 和定理4～8，將概念格進(jìn)行更新。

Fig.5 Concept lattice after objects flow out in table 4圖5 表4 流出對(duì)象后的概念格

首先，??ace，??abe，??ae，由定義9 可知，(6,ace)，(7,abe)，(67,ae)為(45,?)的下層節(jié)點(diǎn)，根據(jù)定理7 將(45,?) 更新為(4567,?)，并將(6,ace)，(7,abe)，(67,ae)加入到概念格中。

然后，由于ace?ae，abe?ae，根據(jù)定義9 可知，(6,ace)，(7,abe) 為(5,ae) 的下層節(jié)點(diǎn)。根據(jù)定理7，(5,ae)更新為(567,ae)，并將(6,ace)，(7,abe)添加到概念格中。由于ae=ae，根據(jù)定義6 可知，(567,ae)與(67,ae)相等。根據(jù)定理4，(67,ae)更新為(567,ae)。

最后，由于bcd?abe=b，bcd?ace=c，根據(jù)定義10 可知(4,bcd)為生成新概念節(jié)點(diǎn)。將(46,c)，(47,b)添加進(jìn)概念格中。更新后的概念格如圖6所示。

Fig.6 Concept lattice in sliding window at time T+1圖6 T+1 時(shí)刻滑動(dòng)窗口中的概念格

5.2 算法分析與結(jié)論

目前現(xiàn)有的概念格更新算法大致可以分為兩類：第一類算法直接將最新的數(shù)據(jù)生成一個(gè)新的概念格；另一類算法就是在現(xiàn)有的概念格基礎(chǔ)上進(jìn)行更新。

本文在流數(shù)據(jù)環(huán)境中進(jìn)行概念格的概念漂移研究。應(yīng)用第一類算法時(shí)，高速、海量和動(dòng)態(tài)的流數(shù)據(jù)將會(huì)導(dǎo)致構(gòu)造概念格出現(xiàn)NP 難問(wèn)題，時(shí)間復(fù)雜度極大，在實(shí)際的應(yīng)用中，算法將會(huì)消耗極大的時(shí)間與內(nèi)存。

至于第二類算法，目前現(xiàn)有的概念格的更新算法，只有增加對(duì)象時(shí)概念格的更新和刪除對(duì)象時(shí)概念格的更新。對(duì)于同時(shí)增減對(duì)象的概念格算法研究目前暫未展開(kāi)。

因此為與本文所提出的CLD_SW 算法進(jìn)行對(duì)比，將采用傳統(tǒng)方法對(duì)概念格先進(jìn)行刪除對(duì)象的更新，再進(jìn)行增加對(duì)象的更新。

首先刪除對(duì)象，目前現(xiàn)有的刪除對(duì)象算法說(shuō)明如下，如果要?jiǎng)h除的對(duì)象不屬于L(t)的某一節(jié)點(diǎn)，則該節(jié)點(diǎn)保持不變。如果要?jiǎng)h除的對(duì)象屬于L(t)的某一節(jié)點(diǎn)，且刪除對(duì)象后，等于該節(jié)點(diǎn)的某一子節(jié)點(diǎn)的外延，則將該節(jié)點(diǎn)刪除。如果要?jiǎng)h除的對(duì)象屬于L(t)的某一節(jié)點(diǎn)，且刪除對(duì)象后，都不等于該節(jié)點(diǎn)的任意子節(jié)點(diǎn)的外延，則將該節(jié)點(diǎn)的外延直接刪除對(duì)象。

取某一個(gè)想要?jiǎng)h除的對(duì)象，根據(jù)上述刪除對(duì)象算法，遍歷原概念格所有節(jié)點(diǎn)，將該對(duì)象從中刪除。重復(fù)以上刪除對(duì)象步驟，直到所有要?jiǎng)h除的對(duì)象全部刪除完畢。

接下來(lái)增加對(duì)象，目前現(xiàn)有的概念格更新算法是將新增對(duì)象與已有概念格的所有概念節(jié)點(diǎn)的對(duì)象進(jìn)行并運(yùn)算，將所對(duì)應(yīng)的兩個(gè)屬性集進(jìn)行交運(yùn)算。直到對(duì)象添加進(jìn)概念格中。依舊重復(fù)以上增加對(duì)象步驟，直到想要添加的對(duì)象增加完畢。

將以上所描述的傳統(tǒng)算法應(yīng)用在如圖4 所描述的概念格中，流入流出與CLD_SW 計(jì)算實(shí)例所描述的相同對(duì)象后，仍然能夠得到如圖6 所示的概念格。

上述兩種算法在實(shí)例的應(yīng)用中，傳統(tǒng)的概念格更新算法需要遍歷原有的概念格8 次。而本文所提出的基于滑動(dòng)窗口法的概念格構(gòu)造算法，由于添加了預(yù)處理過(guò)程，對(duì)于流入流出的對(duì)象進(jìn)行了變化機(jī)理的討論，只需要遍歷原有概念格4 次。相較于現(xiàn)有的概念格構(gòu)造算法，減少了遍歷次數(shù)和時(shí)間復(fù)雜度，提高了概念格更新的效率。

就算法的時(shí)間復(fù)雜度而言，傳統(tǒng)的概念格算法的時(shí)間復(fù)雜度為O(n2)。而本文算法中，通過(guò)對(duì)滑動(dòng)窗口中的動(dòng)態(tài)概念變化機(jī)理的討論，可以知道，當(dāng)流入流出概念完全相同時(shí)，時(shí)間復(fù)雜度為O(1)，此時(shí)為最好的情況。當(dāng)流入流出概念完全不同時(shí)，此時(shí)為最壞的情況，時(shí)間復(fù)雜度為O(n2)。

6 結(jié)束語(yǔ)

本文提出了面向滑動(dòng)窗口方法的概念格計(jì)算算法，通過(guò)對(duì)滑動(dòng)窗口中的流入與流出概念相同、流入流出概念不同、流入流出概念部分相交、流入概念包含流出概念和流出概念包含流入概念這五種現(xiàn)象分別進(jìn)行討論，進(jìn)行滑動(dòng)窗口方法下的概念格的更新，避免概念漂移現(xiàn)象的產(chǎn)生。

與傳統(tǒng)的只能對(duì)增加概念進(jìn)行概念格更新，和只能對(duì)減少概念進(jìn)行概念格更新的算法相比，該算法能夠更加高效地利用內(nèi)存中保存的原有信息，進(jìn)行動(dòng)態(tài)概念格計(jì)算，在一定程度上，提升了概念格構(gòu)造的效率，減少了時(shí)間復(fù)雜度。

同時(shí)采用滑動(dòng)窗口方法解決概念格漂移問(wèn)題，使得算法能夠適應(yīng)流數(shù)據(jù)知識(shí)挖掘中普遍存在的概念漂移現(xiàn)象，為流數(shù)據(jù)環(huán)境中進(jìn)行概念格的概念漂移研究做出貢獻(xiàn)。上述理論分析表明，面向滑動(dòng)窗口法的概念格漂移計(jì)算是一種可行的新型動(dòng)態(tài)計(jì)算方法，在流數(shù)據(jù)環(huán)境中的動(dòng)態(tài)概念格構(gòu)造領(lǐng)域具有廣闊的前景。