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

1.南昌大學 信息工程學院，南昌330031

2.南昌大學 軟件學院，南昌330047

3.同濟大學 電子與信息工程學院，上海201804

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

人在認知過程中，把所感覺到的具有共同特點的事物抽取出來，加以概括，稱之為概念?；谶@個哲學中對“概念”的描述，德國數(shù)學家Wille 提出形式概念分析（formal concept analysis，F(xiàn)CA）[1-2]。將哲學中的概念數(shù)學化、形式化，進而構(gòu)造能夠可視化表達的概念格。

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

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

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

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

1 基礎知識

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

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

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

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

定義2（概念格）用L(G,M,I) 表示形式背景(G,M,I)的全體概念，若(X1,B1)和(X2,B2)是形式概念，則將兩個形式概念上的偏序關系定義為(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,M,I)，其中對象集是G={1,2,3,4}，屬性集是M={a,b,c,d}，如果(g,m)∈I，則在表中記為1；如果(g,m)?I，則在表中記為0。表2 是表1 形式背景(G,M,I)所對應的形式概念，其概念格如圖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 的形式背景所對應的形式概念

Fig.1 Concept lattice corresponding to formal context in table 1圖1 表1 形式背景對應的概念格

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

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

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

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

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

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

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

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

2.2 符號約定

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

T+1 時刻，流入滑動窗口的對象表示為，流出滑動窗口的對象表示為。基于滑動窗口方法的概念格漂移計算研究，就是求滑動窗口中T+1 時刻的概念格L(t+1)=(G(t+1),M(t+1),I(t+1))。

2.3 滑動窗口中動態(tài)概念的變化機理

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

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

下面在表3 中進行總結(jié)，在表格中列出了T+1時刻時，滑動窗口中對象的變化。

Table 3 Change of object in sliding window at time T+1表3 T+1 時刻滑動窗口中對象的變化

例2T+1 時刻，向例1 形式背景下的滑動窗口中流入對象3、4、5，流出對象1、2、3。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定理4設(A,B)為概念格的節(jié)點，(O,P)為概念格L(t)的節(jié)點。當節(jié)點(A,B)與節(jié)點(O,P)相等時，(A?O,B)∈L(t+1)，(O,P)?L(t+1)，(A,B)?L(t+1)。

證明設(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)。

同時由于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 可知，文獻[1]中將X*和B*分別定義為X的所有對象共同擁有的屬性的集合，與所有擁有屬性B的對象的集合。因此對于定理4 能夠很好地理解，新添加的概念中，由于對象擁有該節(jié)點的屬性，因此能夠直接將對象添加進去。

定理5設(A,B) 為的節(jié)點，(O,P)為概念格L(t)的節(jié)點。當(O,P)為流入-不變節(jié)點時，則(O,P)∈L(t+1)，(A,B)∈L(t+1)。

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

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

證明設(O,P)∈L(t)，且(A,B)為節(jié)點(O,P)的上層節(jié)點，則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)。

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

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

證明設(O,P)∈L(t)，且(A,B)為節(jié)點(O,P)的下層節(jié)點，則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)。

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

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

證明設(O,P)∈L(t)，當(O,P)為生成新概念節(jié)點，則存在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)。同時仍然存在，O*=P，P*=O，A*=B，B*=A，因此(A,B)∈L(t+1)，(O,P)∈L(t+1)。

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

根據(jù)定義3～5 可知，流出-不變節(jié)點有(?,M)，刪除 節(jié)點有(1,abd)、(124,ab)，更新節(jié)點有(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,?)。流出對象后的概念格如圖2所示。

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

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

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

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

4 基于滑動窗口的概念格漂移計算算法

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

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

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

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

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

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

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

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

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

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

5 實例與分析

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

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

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

Table 5 Formal concept corresponding to formal context in table 4表5 表4 的形式背景所對應的形式概念

由于形式概念存在一定的偏序關系，因此可以用Hasse 圖表示出來，該形式背景所對應的概念格如圖4 所示。

Fig.4 Concept lattice corresponding to formal context in table 4圖4 表4 形式背景對應的概念格

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

5.1 CLD_SW 計算實例

按照第4 章中的基于滑動窗口的概念格漂移計算算法對概念格進行更新。

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

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

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

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

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

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

然后，由于ace?ae，abe?ae，根據(jù)定義9 可知，(6,ace)，(7,abe) 為(5,ae) 的下層節(jié)點。根據(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é)點。將(46,c)，(47,b)添加進概念格中。更新后的概念格如圖6所示。

Fig.6 Concept lattice in sliding window at time T+1圖6 T+1 時刻滑動窗口中的概念格

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

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