陳榮

（四川大學(xué)計算機學(xué)院，成都 610065）

0 引言

隨著時間推移以及科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)快速增長，為利用其背后巨大的經(jīng)濟和實際應(yīng)用價值，數(shù)據(jù)流分類是其中的關(guān)鍵環(huán)節(jié)。傳統(tǒng)分類問題，如VFDT[1]，是基于“標(biāo)準(zhǔn)數(shù)據(jù)”進行的，所謂的“標(biāo)準(zhǔn)數(shù)據(jù)”是指那些數(shù)據(jù)分布均勻不變，類別均衡的數(shù)據(jù)集。然而，現(xiàn)實問題中，這樣的“標(biāo)準(zhǔn)數(shù)據(jù)”并不常見，更多是“非標(biāo)準(zhǔn)數(shù)據(jù)”，而解決此類數(shù)據(jù)的分類問題才更有意義。

相較于傳統(tǒng)數(shù)據(jù)的靜態(tài)環(huán)境，數(shù)據(jù)流的產(chǎn)生環(huán)境是非靜態(tài)且變化的，在這樣的環(huán)境中，數(shù)據(jù)分布會隨時間發(fā)生變化，這就產(chǎn)生了“概念漂移”現(xiàn)象。處理這類問題，已有多種算法[2-3]。另外，真實數(shù)據(jù)流中越來越多的非平衡數(shù)據(jù)流，例如入侵檢測、癌癥篩查等。如Learn++.NIE[4]、Learn++.NSE[5]，都用于解決該問題。

綜上，為解決流分類中同時存在的概念漂移以及類別不平衡問題，本文設(shè)計了一種利用部分標(biāo)簽數(shù)據(jù)，使用監(jiān)督與半監(jiān)督結(jié)合的形式進行的數(shù)據(jù)流分類方法。其主要為，在檢測到概念漂移之后，根據(jù)概念漂移的類型，分別使用不同的處理算法進行模型再訓(xùn)練，以便后續(xù)數(shù)據(jù)流進行分類。與使用全標(biāo)簽數(shù)據(jù)相比，這種使用少量標(biāo)簽數(shù)據(jù)對存在概念漂移的非平衡數(shù)據(jù)流進行分類的方法，可以獲得相當(dāng)甚至更好的性能。

1 相關(guān)概念

1.1 概念漂移定義

在動態(tài)的數(shù)據(jù)產(chǎn)生環(huán)境中，隨著數(shù)據(jù)量的增加，形成了數(shù)據(jù)流。同時，數(shù)據(jù)流的分布也會隨時間或其他因素產(chǎn)生變化，因而產(chǎn)生“概念漂移”[6]。例如，垃圾郵件問題，一封郵件是否被定義為垃圾郵件，是根據(jù)特定用戶而言，并且隨時間變化，同一用戶對于垃圾郵件的定義也會有所不同，這就產(chǎn)生了概念漂移。

在概念漂移的諸多定義中，其中最為經(jīng)典的定義形式，是使用概率論中的聯(lián)合分布隨時間變化的表達。即在t0時刻，對應(yīng)的輸入變量X與目標(biāo)變量y之間的聯(lián)合分布與t1時刻的X與y之間的聯(lián)合分布之間存在差異[7]：

1.2 概念漂移的分類

基于對概念漂移的定義，結(jié)合聯(lián)合分布的公式，會造成概念漂移的因素有：類的先驗概率P(y)，類的條件概率P(X|y)，樣本的后驗概率P(y|X)隨時間發(fā)生了變化。在實際數(shù)據(jù)流環(huán)境中，觀察的重點在于是否影響了最后的分類預(yù)測[8]，所以，概念漂移可以分為以下兩類：

（1）實漂移：后驗概率P(y|X)發(fā)生了變化，P(x)可能發(fā)生了變化，也可能沒有；

（2）虛漂移：雖然P(x)發(fā)生了變化但是沒有影響到最后的分類預(yù)測P(y|X)

根據(jù)數(shù)據(jù)分布的變化形式，實漂移又可以根據(jù)目標(biāo)概念發(fā)生變化時，經(jīng)過的實例長度分為突變漂移、漸變漂移，如圖1。

圖1 概念漂移類型

1.3 非平衡數(shù)據(jù)流

在待處理的數(shù)據(jù)流中，樣本比例占多數(shù)的類別，稱為負類；樣本比例占少數(shù)的類別，稱為正類。正負類的類別數(shù)量比例懸殊，就出現(xiàn)了非平衡數(shù)據(jù)流。由于多數(shù)模型是在均衡數(shù)據(jù)上訓(xùn)練而來，因此它們在非平衡數(shù)據(jù)流上的分類效果并不理想，性能及精度都偏低。

2 基于特征樣本的監(jiān)督與半監(jiān)督的流分類算法

非平衡的概念漂移數(shù)據(jù)流在現(xiàn)實場景中越來越多。為解決此類數(shù)據(jù)流的分類問題，Elaheh Arabmakki等人的RLS-SOM框架[9]，雖然利用了部分標(biāo)記的數(shù)據(jù)進行模型的訓(xùn)練，相較于其他全標(biāo)記的算法，如UCB、SERA等，只用了10%-30%的標(biāo)記數(shù)據(jù)就達到了同等分類性能。但是，對于剩下的大部分未標(biāo)記數(shù)據(jù)并沒有使用。因此本文設(shè)計了基于特征樣本的監(jiān)督與半監(jiān)督的流分類算法，即，使用監(jiān)督與半監(jiān)督結(jié)合的方式，利用部分標(biāo)記以及大部分未標(biāo)記數(shù)據(jù)，針對非平衡的概念漂移數(shù)據(jù)流進行模型訓(xùn)練。

在初始化階段，得到初始分類模型以及由特征向量SV1和正類樣本PS（Positive Samples）組成的代表性樣本 RS（Representative Samples）。在之后的訓(xùn)練階段，計算后續(xù)數(shù)據(jù)流中的數(shù)據(jù)塊di(i=2,3,…,n)，與RS的歐氏距離：

選取最短距離K個樣本SDK（Shortest Distance K），請求其標(biāo)簽。若SDK包含正負類樣本且分類準(zhǔn)確率變化超過閾值α，則判定發(fā)生了條件漂移，本文使用基于特征樣本的監(jiān)督式流分類算法。若SDK中不包含正類，則判定發(fā)生了特征漂移，本文提出基于特征樣本的多閾值SOM非隨機半監(jiān)督式流分類算法。

2.1 基于特征樣本的監(jiān)督式流分類算法

在發(fā)生條件漂移后，由于分類邊界只發(fā)生了輕微漂移，SDK還能夠代表當(dāng)前數(shù)據(jù)的特征，所以此時的FS（Feature Samples）就是SDK中的樣本，所以，利用FS使用監(jiān)督式的方式，例如DT（Dession Tree）等，重新訓(xùn)練并更新模型，并且更新RS。然后，進入下一輪的分類與漂移判定流程。

2.2 基于特征樣本的多閾值SOM非隨機半監(jiān)督式流分類算法

在發(fā)生特征漂移后，由于SDK中沒有包含正類，由此可知，分類邊界發(fā)生了重大漂移，此時，需要在當(dāng)前數(shù)據(jù)快上，重新尋找新的FS用于訓(xùn)練新模型。在本文中使用基于SOM多閾值樣本搜索法尋找FS。算法如下：

在獲取到當(dāng)前數(shù)據(jù)塊di的FS及其標(biāo)簽后，結(jié)合剩下的無標(biāo)簽樣本，使用半監(jiān)督的方式訓(xùn)練新的模型。在已有的基于度量聚類假設(shè)的權(quán)重學(xué)習(xí)算法的基礎(chǔ)上[10]，本文提出使用基于特征樣本的非隨機半監(jiān)督聚類算法，通過SOM多閾值樣本搜索法獲得的特征樣本作為初始聚類中的標(biāo)簽樣本。算法如下：

其中，以“信息熵”為基礎(chǔ)，本文使用“樣本熵”來衡量簇的規(guī)則性CR(Ci)，這里的H表示di的樣本熵，H(Ci)表示簇Ci上的樣本熵。

當(dāng)數(shù)據(jù)塊di+1到來之后，其中數(shù)據(jù)樣本x的樣本則以如下公式得出。

最后，獲得了di+1的全部標(biāo)簽數(shù)據(jù)，接著使用該獲得完全標(biāo)記的數(shù)據(jù)塊，重新訓(xùn)練并更新模型，并且更新RS。然后，進入下一輪的分類與漂移判定流程。

3 實驗分析

3.1 實驗數(shù)據(jù)集

實驗數(shù)據(jù)集主要為UCI的森林覆蓋數(shù)據(jù)集。完整樣本有581012個樣本，7個類型，54維屬性。為了產(chǎn)生非平衡的環(huán)境，選取了其中4組2類進行實驗。

表1

3.2 實驗結(jié)果

本實驗通過與在同樣環(huán)境下的簡單分類器進行分類準(zhǔn)確率對比，簡單分類器在檢測到概念漂移后，均使用全標(biāo)記的監(jiān)督式訓(xùn)練新的分類器。在不同數(shù)據(jù)集上，改變每次處理的窗口大小，得到準(zhǔn)確率變化如圖2-圖5。其中橫坐標(biāo)表示窗口的大小，縱坐標(biāo)表示判定分類性能的指標(biāo)Acc。

由此可見，本論文實驗?zāi)Ｐ驮诎l(fā)生概念漂移之后，只選取部分標(biāo)記數(shù)據(jù)作為特征樣本重新得到的分類模型在分類性能上基本能達到和普通利用全標(biāo)記數(shù)據(jù)訓(xùn)練得到的模型一樣的水平，甚至在某些特定情況下，性能更好。

圖2

圖3

圖4

圖5

4 結(jié)語

相對單純概念漂移數(shù)據(jù)流分類來說，針對同時存在概念漂移以及類別不平衡分布的特定數(shù)據(jù)流分類的研究還較少。如何在二者皆存的情況下，及時對發(fā)生漂移的數(shù)據(jù)重新訓(xùn)練有效分類模型，顯得至關(guān)重要。本文提出的，針對不同漂移類型，使用不同的模型再建方法，不僅對有標(biāo)簽數(shù)據(jù)的數(shù)量要求有降低，同時還利用了無標(biāo)簽的數(shù)據(jù)，并且還取得了不錯的性能。