基于語義的文本數據流概念漂移檢測算法

儲 光,胡學鋼,張玉紅

(合肥工業大學 計算機與信息學院,合肥 230009)

0 概述

網絡社交媒體在現實生活中被廣泛應用,例如網絡聊天、購物評論和在線新聞等,由此產生了大量的文本數據流。這些數據流的主題會隨著時間隨機變化,這種變化被稱為概念漂移[1-2]。概念漂移檢測是數據流分類中的重要問題。

根據數據流是否含有標記信息,可將現有的概念漂移檢測算法分為監督、無監督和半監督3類。監督方法適用于有標記數據,依據衡量數據流分類過程中的錯誤率變化程度進行概念漂移檢測,衡量模型包括伯努利分布[3-5]、決策樹[6-8]和Bayes模型[9]等。無監督方法適用于無標記數據,主要分為2種:一種是借助聚類等方法,通過比較聚類簇的變化程度進行概念漂移檢測[10];另一種是借助特征向量化和特征提取的方法,通過比較提取出的特征集合或是依據特征計算出的信息熵的變化程度進行概念漂移檢測[11]。半監督方法適用于部分標記數據,概念漂移檢測方法大多與無監督方法一致[12]。上述方法都基于某種信息量的變化程度進行概念漂移檢測,其中監督方法效果直接取決于基分類器的性能,無監督或半監督方法效果直接取決于聚類或者特征提取效果,在一定條件下可以有效地實現概念漂移檢測。

然而在實際應用中,由于信息的傳播速度快、交流范圍廣,導致文本數據流中的概念通常會隨著時間頻繁變化。例如在奧運會期間,體育新聞的內容會隨著項目不同而不停更新,從球類到游泳,從田徑到射擊,項目最密集時這種更新甚至會以分鐘為單位。這種頻繁的概念漂移一方面降低了分類器的適用性,另一方面使得用于區分不同數據分布的樣本數量不足,難以累積充分的樣本來評估數據塊之間的變化程度。

針對上述問題,本文考慮文本數據流隱含的語義信息,提出一種新的概念漂移檢測算法。通過引入潛在狄利克雷分布(Latent Dirichlet Allocation,LDA)模型[13]計算語義相似度,并基于相鄰數據塊共有詞比例和相似主題比例,在頻繁漂移情況下實現有效的概念漂移檢測。

1 相關研究

本節主要介紹已有關于概念漂移檢測的研究,分監督概念漂移檢測算法和無監督或半監督概念漂移檢測算法2類進行介紹。

1)監督概念漂移檢測算法

文獻[1]對監督類的概念漂移檢測方法進行了全面綜述;文獻[2]提出一種基于分類器與數據集中概念相似度錯誤方差的方法來判斷概念是否發生漂移;文獻[3-4]提出基于伯努利數據分布設置閾值以區分概念漂移與噪音的方法DDM;文獻[5]采用分類錯誤率替換錯誤分類實例的機制改進了DDM方法,提出了一種更適用于檢測突變式概念漂移的方法EDDM;文獻[6]提出一種使用隨機決策樹構建集成分類器,并采用雙層閾值來區分噪音和漂移的方法CDRDT;文獻[7-8]提出一種依據窗口中原始數據分布變化來檢測概念漂移的方法SWCDS,以及利用雙層窗口機制跟蹤概念漂移以提高適應性的方法DWCDS;文獻[9]提出基于決策樹和Bayes混合模型的集成分類方法 WE-DTB,利用Hoeffding邊界和μ檢驗實現了數據流環境下概念漂移的檢測和分類。

在實際應用中,多數算法采用不同的錯誤率評估方法來降低概念漂移檢測過程中噪音的干擾,例如Hoeffding邊界[10,14-16]、μ檢驗[8]等。這些算法對含噪音數據流效果顯著,但本質上是通過分類錯誤率進行概念漂移檢測,性能主要受限于標簽信息和分類器性能。

2)無監督或半監督概念漂移檢測算法

為處理不完全標記數據流中重現概念漂移問題,針對連續屬性數據流,文獻[10]采用K-Means算法在增量式構建決策樹的葉子節點標記無標簽示例,提出基于聚類簇差異度量的概念漂移檢測方法,即采用存儲歷史概念簇的機制,同時更新概念漂移檢測條件的算法REDLLA;針對多數算法忽略特征空間和樣本空間分布特點的現狀,文獻[11]利用特征選擇和加權,構建基于特征項分布的信息熵及特征動態加權概念漂移檢測模型。該模型根據特種特征和樣本空間的擬合性,使用特征信息熵捕捉概念漂移,同時利用改進的LDA模型特征動態加權算法解決了特征權重的取值問題;文獻[12]提出一種基于KNN模型和增量Bayes的概念漂移檢測算法KnnM-IB,使用增量Bayes算法分類難處理的樣本,同時利用可變的滑動窗口對少量標記信息進行主動學習,以此進行概念漂移檢測。

無監督或半監督概念漂移檢測算法通過聚類或特征提取等方法,利用聚類簇或特征集合的分布變化衡量原始數據分布變化進行概念漂移檢測。這些算法適用于半標記或未標記數據,但本質上是通過數據分布變化進行概念漂移檢測,性能直接取決于能否擁有足夠的訓練樣本用于區分數據分布的差異。

2 基于語義的概念漂移檢測方法

本文針對頻繁漂移數據流提出一種無監督基于語義的概念漂移檢測算法,首先給出算法框架,如圖1所示,本文算法框架綜合考慮了單詞和主題2個層面的語義相似度檢測概念漂移。

圖1 本文算法框架

1)共有詞比例計算

文本數據流中語義的直接表現形式是單詞,因此,共有詞比例一定程度上可以體現2個數據塊的語義相似度,且計算方法簡單、效率高。例如在線購物評論數據中消費者關注的商品從書籍變化為電器時,雖然2個類別會有一些共有詞,例如“price”“quality”等,但2個數據塊中主要用于描述商品名稱的單詞會發生較大的變化,例如從“book,comic,novel,…”變化到“dvd,television,fridge,…”。

當共有詞比例較大時,一般認為對應的相鄰數據塊語義相似度較高,因此,本文認為共有詞比例較大時無概念漂移。當共有詞比例較小時,可能存在概念漂移,有待于進一步檢測。

2)相似主題比例計算

基于共有詞比例的檢測方法沒有考慮單詞的語義權重,當比例較小的共有詞擁有較大的語義權重時,僅使用該方法會造成誤檢。例如20-Newsgroups數據中屬于“hockey”概念的2個數據塊,由于“match”“hockey”“League”等高頻詞語的數量較少,而“Canada”“CBC”“NHL”等低頻詞語的數量較低,因此此時基于共有詞比例的檢測方法反而會誤判發生概念漂移。為防止此類誤檢發生,本文引入LDA模型中的主題概念進行檢測。若相鄰兩數據塊主題較為相似,則認為未發生概念漂移,否則認為發生概念漂移。

下面簡要介紹LDA模型。LDA是一種基于語義的文檔主題生成模型,能提取出文檔-主題-詞概率矩陣,其中主題-詞的概率矩陣可用于表示主題空間。在本文中視每個數據塊為一個文檔并為其建立LDA模型,并由此得到相鄰數據塊的主題空間。對于數據塊Di,可以得到其主題集合Zi={z1,z2,…,zh}以及文檔-主題的概率分布θDi={P(z1|Di),P(z2|Di),…,P(zh|Di)};而對于主題zi∈Zi,可以得到其主題-單詞的概率分布φzi={P(w1|zi),P(w2|zi),…,P(wm|zi)},其中P(wl|zi)表示單詞wl屬于主題zi的概率,即wl在zi中的語義權重。本文通過比較單詞在不同主題中的語義權重來衡量主題相似度,并根據數據塊之間的相似主題比例來衡量數據塊的語義相似度,從而實現概念漂移的檢測,彌補了共有詞比例難以體現語義權重的不足。

為保證表述的準確性,本文定義了相關變量,如表1所示。

表1 變量定義

本文算法詳細步驟如下:

步驟1計算共有詞比例rw

通過計算共有詞比例rw來進行概念漂移檢測,如圖2所示,求得Di和Di+1中單詞集合交集即可計算量數據塊共有詞所占比例。

圖2 共有詞比例計算示意圖

對于文本數據流D={D1,D2,…},使用|WDi|表示數據塊Di的單詞個數。利用相鄰數據塊共有詞比例衡量其語義相似度,計算公式如式(1)所示。

(1)

由于此步驟用于快速排除相鄰數據塊語義相似度較高的情況,其余情況可以由后續步驟進行檢測,因此當rw大于閾值α時,判定未發生概念漂移,否則需要執行步驟2。

步驟2計算相似主題比例rz

引入LDA模型,通過計算相似主題比例rz進行概念漂移檢測,如圖3所示。

圖3 相似主題比例計算示意圖

LDA模型可以計算出文檔-主題-單詞的三層概率分布,本文算法引入LDA模型,主要利用主題-單詞的概率P(wl|zi)計算相似主題比例,實現概念漂移檢測。

(2)

(3)

將相似主題比例視為相鄰數據塊的語義相似度,上述計算可用于概念漂移的檢測。計算過程如式(4)所示。

(4)

其中,h為LDA模型在數據流D上劃分的主題個數。

與共有詞比例類似,當rz大于閾值α時,可以判定這2個數據塊語義相似度較高,未發生概念漂移,否則發生概念漂移。

經過以上各步驟,本文算法利用隱含的語義彌補頻繁漂移情況下訓練數據的有限性,通過計算共有詞比例和相似主題比例,實現了概念漂移檢測。

本文算法由共有詞比例計算和深入語義權重的相似主題比例計算2個步驟組成,挖掘了數據隱含的語義信息,彌補了頻繁漂移情況下單個概念數據量不足的缺陷,減少了概念漂移檢測的漏檢。算法具體如下:

算法基于語義的無監督文本數據流概念漂移檢測算法

輸入數據流D,數據塊中的主題個數h,閾值α、β

輸出發生的概念漂移次數n

1.While D not end,read chunks Di,Di+1from the stream D;

2. Count|WDi|,|WDi+1| and |WDi∩WDi+1| to calculate rw;

3. If(rw>α)

4. Then no drift and break;

5. Use LDA to get Zi,Zi+1and each j for topics by h;

7. For zi∈Zi,i=1 to h

9. Then lz′j=1 and break;

10. Sum lz′jto calculate rz;

11. If(rz>α)

12. Then no drift and break;

13. Else drift and n++;

14.Return n;

3 實驗與結果分析

本節探討了算法的閾值選取,并通過同基準算法的對比,從算法在多種頻繁漂移文本數據流上的普適性和不同漂移頻繁程度對算法的影響2個方面評估本文算法。

3.1 基準數據集、基準算法及評價指標

由于網絡中存在的真實文本數據流分布較為隨機,不能保證包含所有種類的概念漂移,用于評估概念漂移檢測算法性能時不夠嚴謹,缺乏說服力,而且包含大量的噪音,需要經過復雜的預處理,因此實驗選取常用于評估算法性能的3個基準文本數據集,通過不同的組合方式模擬真實情況下的文本數據流,3個數據集分別是亞馬遜網站購物數據(Amazon)、路透社新聞數據(Reuters)以及20新聞組數據(20-Newsgroups),具體信息如表2所示,其中亞馬遜網站購物數據是由多種商品的購物評論組成,而路透社新聞數據和20新聞組數據則是由多個領域中的多篇新聞報道組成。

表2 數據集信息

本文從對于多種頻繁漂移文本數據流的普適性和漂移頻繁程度不同對算法性能的影響2個方面考察算法,設置了2個系列的實驗數據,其中本文算法使用單詞形式的文本數據流,而對比算法使用經過特征向量化、詞頻篩選處理后的文本數據流。

由于基準數據中包含多個不同的領域,來自不同領域的數據之間概念不同,通過從不同的領域中選取數據組成數據塊并拼接構成實驗數據流的方式,可以模擬真實數據流中的概念漂移情況,具體構造方法如下:

1)多種頻繁漂移文本數據流

為考察算法的普適性,本文選取3個來自不同基準數據集的實驗數據與基準算法進行對比實驗。

(1)Amazon數據集:數據共有4個概念,對每個概念重復取樣獲得8個數據塊,并將其組成共32個數據塊的實驗數據,其中每個數據塊由200條數據構成。數據經過特征向量化、詞頻篩選后維度為256,其中設定3次概念漂移,多次重復實驗取平均值作為最終實驗結果。

(2)Reuters數據集:數據共有5個概念,對每個概念重復取樣獲得2個數據塊,并將其組成共10個數據塊的實驗數據,其中每個數據塊由200條數據構成。數據經過特征向量化、詞頻篩選后維度為224,其中設定4次概念漂移,多次重復實驗取平均值作為最終實驗結果。

(3)20-Newsgroups數據集:數據共有4個領域,每個大類包含3個～5個概念,從每個領域中隨機選取一個概念,對每個概念重復取樣獲得3個數據塊,并將其組成12個數據塊的實驗數據,其中每個數據塊由200條數據構成。數據經過特征向量化、詞頻篩選后維度為201,其中設定3次概念漂移,多次重復實驗取平均值作為最終實驗結果。

2)Amazon實驗數據序列

為考察漂移頻繁程度不同對算法性能影響,本文從亞馬遜網站購物數據中抽取數據,構建了漂移頻繁程度不同的多組實驗數據。對Amazon原始數據的4個概念分別重復取樣各獲得8個數據塊,共32個數據塊、6 400條數據,再將獲得的數據塊按照8種不同的順序進行排列以獲得8組漂移頻繁程度不同的實驗數據,其中漂移次數最多的有31次,最少的有3次。

本文選取5種概念漂移檢測算法作為基準算法,其中監督概念漂移檢測的算法有DDM[3-4]、CDRDT[6]、DWCDS[7-8]和HDDM-W-Test[16]算法,而無監督或半監督概念漂移檢測的算法則為REDLLA[10]算法。由于基于監督概念漂移檢測的算法受分類器性能影響,選擇決

策樹(DT)和樸素Bayes(NB)分類器作為對比,并在此基礎上進行分類性能的對比,分類過程運用集成分類的方法,窗口大小為4個數據塊。

評價指標:概念漂移檢測的結果需要提供有意義的、可以量化描述的結論,根據概念漂移檢測的特點,通常采用誤檢數和漏檢數作為評價指標[17]。

為了在保證精度的同時提高時間效率,設定LDA模型內部迭代次數為1 000,數據流劃分的主題數目為10,主題的關鍵詞集合大小為20。

3.2 閾值選取

本節主要說明閾值a和b的取值。由于a用于快速剔除語義相似度高的相鄰數據塊,因此本文根據經驗值設置其值為0.5;b用于衡量主題的語義相似度,需要根據實驗決定,具體實驗結果如圖4所示。

圖4 閾值b取值實驗結果

根據閾值不同取值的實驗結果,可以看出閾值越小漏檢次數越多,閾值越大誤檢次數越多。經過多次重復試驗,本文選取0.2作為主題相似度閾值b的取值。

3.3 算法普適性分析

使用多種頻繁漂移文本數據流進行實驗,具體結果如表3所示,該表顯示了本文算法與對比算法在誤報次數、漏報次數方面的概念漂移檢測性能。

表3 概念漂移檢測結果

首先,實驗結果表明在頻繁漂移情況下,監督概念漂移檢測方法普遍漏檢嚴重,尤其是對于Reuters數據,對比算法的正確檢測數量都為0,這是由于頻繁漂移情況下訓練樣本的缺少導致分類器性能低下,漂移發生時分類錯誤率的變化不夠明顯。同時選取的2種基分類器實驗結果類似,證明了這種情況的普遍性。

其次,無監督或半監督概念漂移檢測方法的效果也較差,尤其是REDLLA算法,在3組實驗數據集上均有較多漏檢和誤檢。漏檢較多是由于頻繁漂移情況下,算法獲取的樣本數量不足以區分不同概念的數據分布;誤檢較多則是由于文本數據流本身數據塊之間分布差異較大,且無監督或半監督算法不使用標記信息。

在3個基準數據集上的實驗結果表明,與對比算法相比,本文算法的概念漂移檢測結果均優于對比算法,尤其在漏檢指標上大幅度優于對比算法。這是由于本文算法考慮了文本數據隱含的語義信息,使用相鄰數據塊的語義信息增強了概念的區分度,彌補了頻繁漂移情況下數據量有限的不足,能夠進行有效的概念漂移檢測。

表4考察了本文算法與對比算法在分類錯誤率上的差異,表中數據為所有數據塊的平均分類錯誤率。由于本文算法僅進行概念漂移檢測,因此在考察分類精度時計算了2種分類方法的結果。由表4可見,實驗結果平均分類錯誤率較大,原因在于采取了未進行降噪等預處理的原始數據,而且設定的漂移較為頻繁,概念變化速度較快。此外,該算法在Amazon和 20-Newsgroups數據集上的分類錯誤率高于基準算法,這是由于基準算法頻繁漂移情況下漏檢較多,漏檢時訓練集不會更新導致其中出現概念重現問題,概念的重現使得基準算法在漏檢較多時反而具有較低的分類錯誤率。由于本文算法僅考慮概念漂移檢測,因此集成分類器機制帶來的概念重現問題不做進一步討論。

表4 分類錯誤率 %

綜合所有分類錯誤率結果則可以證明,在大部分情況下,本文概念漂移檢測算法得到的檢測結果在相同的分類機制下能獲得相當的分類精度。

3.4 不同漂移頻繁程度下的算法性能分析

本節對比本文算法與3種基準算法在不同頻繁程度下在Amazon實驗數據序列上的實驗結果,基分類器選取NB方法,結果如表5所示,其中,N表示漂移次數。可以看出,隨著漂移頻繁程度的增加,漏檢數也會上升,而本文算法漏檢數上升幅度明顯小于對比算法。DDM算法在頻繁程度較高時漏檢次數較高,這是由于頻繁發生概念漂移時,分類精度一直較低,變化程度不明顯。REDLLA算法在頻繁程度低時誤檢較多,在頻繁程度較高時漏檢較多,前者是由于文本數據塊本身數據分布差異程度較大,不使用標簽信息時會造成較多的誤檢,后者則是由于頻繁漂移時同一概念的數據樣本過少,難以區分不同概念的數據分布。而本文算法利用語義信息彌補樣本數量有限的不足,在漂移頻繁程度較低時效果與對比算法相當,而在頻繁漂移程度較大時大幅度減少了漏檢數量。

表5 漂移頻繁程度對算法性能的影響

4 結束語

概念漂移檢測是數據流分類研究的難點,尤其對于頻繁漂移數據流。監督概念漂移檢測方法通常基于分類錯誤率,過度依賴于分類器的性能,且需要在分類結束后才能進行概念漂移檢測;無監督或半監督的分類算法利用聚類或者特征提取的方法計算相鄰數據塊的差異程度以檢測漂移,在樣本數量不足時效果不理想。而本文算法利用了數據隱含的語義信息,基于語義相似度進行概念漂移檢測,效果不受基分類器性能影響,且受樣本數量影響度較小。然而該算法性能對相似閾值敏感,因此,發現閾值與數據分布間的內在關系以提升算法普適性將是未來工作重點。此外,本文僅關注了文本數據流的概念漂移問題,如何面向其他實際應用領域包括煤礦典型動力災害數據流、電信通話數據流、天氣預報數據流等實現概念漂移的檢測,也將是下一步的研究方向。

[1] WIDMER G,KUBAT M.Learning in the Presence of Concept Drift and Hidden Contexts[J].Machine Learning,1996,23(1):69-101.

[2] WANG Haixun,FAN Wei,YU P S,et al.Mining Concept-drifting Data Streams Using Ensemble Classifiers[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2003:789-802.

[3] GAMA J,MEDAS P,CASTILLO G,et al.Learning with Drift Detection[M]//BAZZAN A L C,LABIDI S.Advances in Artificial Intelligence.Berlin,Germany:Springer-Verlag,2004:286-295.

[4] GAMA J,CASTILLO G.Learning with Local Drift Detection[M]//LI Xue,ZA?ANE O R,LI Zhanhuai.Advanced Data Mining and Applications.Berlin,Germany:Springer-Verlag,2006:42-55.

[5] BAENA-GARC M,CAMPO-VILA J D,FIDALGO R,et al.Early Drift Detection Method[C]//Proceedings of the 4th International Workshop on Knowledge Discovery from Data Streams.Pittsburgh,USA:[s.n.],2006:1-10.

[6] LI Peipei,WU Xindong,HU Xuegang,et al.A Random Decision Tree Ensemble for Mining Concept Drifts from Noisy Data Streams[J].Applied Artificial Intelligence,2010,24(7):680-710.

[7] 朱 群,張玉紅,胡學鋼,等.一種基于雙層窗口的概念漂移數據流分類算法[J].自動化學報,2011,37(9):1077-1084.

[8] ZHU Qun,HU Xuegang,ZHANG Yuhong,et al.A Double-window-based Classification Algorithm for Concept Drifting Data Streams[C]//Proceedings of IEEE International Conference on Granular Computing.Washington D.C.,USA:IEEE Press,2010:639-644.

[9] 桂 林,張玉紅,胡學鋼.一種基于混合集成方法的數據流概念漂移檢測方法[J].計算機科學,2012,39(1):152-155.

[10] LI Peipei,WU Xindong,HU Xuegang.Mining Recurring Concept Drifts with Limited Labeled Streaming Data[J].ACM Transactions on Intelligent Systems and Technology,2012,3(2):241-252.

[11] 孫 雪,李昆侖,韓 蕾,等.基于特征項分布的信息熵及特征動態加權概念漂移檢測模型[J].電子學報,2015,43(7):1356-1361.

[12] 郭躬德,李 南,陳黎飛.一種基于混合模型的數據流概念漂移檢測算法[J].計算機研究與發展,2014,51(4):731-742.

[13] BLEI D M,NG A Y,JORDAN M I.Latent Dirichlet Allocation[J].Journal of Machine Learning Research,2003,3:993-1022.

[14] HOFFMAN M D,BLEI D M,BACH F R.Online Learning for Latent Dirichlet Allocation[M]//LAFFERTY J D,WILLIAMS C K I,SHAWE-TAYLOR J.Advances in Neural Information Processing Systems.[S.l.]:Neural Information Processing Systems Foundation,Inc.,2010:856-864.

[15] LI Peipei,WU Xindong,HU Xuegang,et al.Learning Concept-drifting Data Streams with Random Ensemble Decision Trees[J].Neurocomputing,2015,166(C):68-83.

[16] FRIASBLANCO I,CAMPOAVILA J D,RAMOSJIMENEZ G,et al.Online and Non-parametric Drift Detection Methods Based on Hoeffding’s Bounds[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(3):810-823.

[17] HABABOU M,CHENG A Y,FALK R.Variable Selection in the Credit Card Industry[C]//Proceedings of NESUG’06.Philadelphia,USA:SAS Institute Inc.,2006:1-5.