面向滑動窗口法的概念格漂移計算研究

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

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

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

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

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

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

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

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

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

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

1 基礎知識

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

為了更好地描述概念，德國數學家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稱為概念的內涵。

定義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 滑動窗口中數據的變化形態(tài)分析

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

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

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

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

在本文中，流入和流出對象后，滑動窗口中有三種變化形態(tài)。在第一種形態(tài)下，滑動窗口中沒有舊的對象，只有新的對象，對于動態(tài)概念格構造的研究意義不大，因此不予討論。第二種形態(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)概念變化情況一共有五種，分別是流入流出概念相同、流入流出概念不同、流入流出概念部分相交、流入概念包含流出概念和流出概念包含流入概念。接下來針對這五種變化現象進行討論。

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

下面在表3 中進行總結，在表格中列出了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 后的概念格。與現有的概念格更新算法相比，減少了更新步驟，提高了算法的效率，減少了時間復雜度。

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

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

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

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

定義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é)點。

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

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

證明設(O,P)∈L(t)，且為流出-不變節(jié)點，則。由于(O,P)∈L(t)，根據定義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)。根據定義1 可知，O*=P，(O-H)*=Q。由于H∈O，T+1 時刻，刪除對象H后，在L(t+1)中(O,P) 更新為(O-H,P)，但(O-H)*=Q，因此根據定義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。根據定義1 可知，O*=P且P*=O。由于H∈O，根據形式概念的定義可知，當概念的外延減少時，內涵增加，因此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≠?，根據定義可知(O-H)*?H*=P，故上述等式不成立，假設也不成立。

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

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

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

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

定義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é)點的內涵都不相等；（2）H與(A,B)和L(t)中的任一節(jié)點的交集不等于H，則稱節(jié)點(O,P)為生成新概念節(jié)點。

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

定理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。根據定義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，根據定義1 可知，(A,B) 和(O,P) 不再是形式概念，因此(O,P)?L(t+1)，(A,B)?L(t+1)。

根據定義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é)點，根據定義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，并且根據定義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，根據定義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，并且根據定義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，根據定義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≠?，并且根據定義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，根據表3 可知，只需要計算增加概念(5,ab)和刪除對象12 后的概念格。

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

因此根據定理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é)點，根據定理7 將(34,?)更新為(345,?)，并將(5,ab)加入到概念格中。

然后d?ab=?，由定義7 可知，(3,d)為流入-不變節(jié)點。最后由于abc?ab，根據定義8 可知，(5,ab)為(4,abc)上層節(jié)點，根據定理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根據表3 計算T+1 時刻，實際上流入和流出的對象并計算實際流入對象所構成的概念格。

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

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

步驟4自頂向下遍歷L(t)的節(jié)點，并選取概念格中任一節(jié)點(A,B)，與其對比。根據定義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ā)生的概念漂移現象。同時基于現有的概念格更新算法，對這些算法進行改進，極大地提高了概念格更新的效率，減少了時間復雜度。

5 實例與分析

T時刻的滑動窗口中，有這樣的一些數據，已知形式背景中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，因此根據定義1 可知(1,bd)不是形式概念；對象2 擁有屬性ace，同時共同擁有屬性ace的也只有對象2，因此根據定義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，根據滑動窗口中動態(tài)概念的特征，由于滑動窗口的尺寸大小是固定不變的，因此有多少數據流入滑動窗口中，就有等量的數據流出滑動窗口，因此假定流出滑動窗口的對象為1234。

5.1 CLD_SW 計算實例

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

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

步驟2自頂向下遍歷L(t)的節(jié)點，并將流出的對象與這些節(jié)點一一對比，根據定義3～5，將這些節(jié)點分類。因此已知實際流出對象123，根據定義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é)點分類后，算法要求根據定理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)中任一概念，分別與其對比。根據定義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é)點，根據定理7 將(45,?) 更新為(4567,?)，并將(6,ace)，(7,abe)，(67,ae)加入到概念格中。

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

最后，由于bcd?abe=b，bcd?ace=c，根據定義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 算法分析與結論

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

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

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

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

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

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

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

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

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

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

6 結束語

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

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

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