面向非平衡與概念漂移的數(shù)據(jù)流分類的研究

陳榮

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

0 引言

隨著時(shí)間推移以及科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)快速增長(zhǎng)，為利用其背后巨大的經(jīng)濟(jì)和實(shí)際應(yīng)用價(jià)值，數(shù)據(jù)流分類是其中的關(guān)鍵環(huán)節(jié)。傳統(tǒng)分類問題，如VFDT[1]，是基于“標(biāo)準(zhǔn)數(shù)據(jù)”進(jìn)行的，所謂的“標(biāo)準(zhǔn)數(shù)據(jù)”是指那些數(shù)據(jù)分布均勻不變，類別均衡的數(shù)據(jù)集。然而，現(xiàn)實(shí)問題中，這樣的“標(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ù)分布會(huì)隨時(shí)間發(fā)生變化，這就產(chǎn)生了“概念漂移”現(xiàn)象。處理這類問題，已有多種算法[2-3]。另外，真實(shí)數(shù)據(jù)流中越來(lái)越多的非平衡數(shù)據(jù)流，例如入侵檢測(cè)、癌癥篩查等。如Learn++.NIE[4]、Learn++.NSE[5]，都用于解決該問題。

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

1 相關(guān)概念

1.1 概念漂移定義

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

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

1.2 概念漂移的分類

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

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

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

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

圖1 概念漂移類型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

表1

3.2 實(shí)驗(yàn)結(jié)果

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

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

圖2

圖3

圖4

圖5

4 結(jié)語(yǔ)

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