王文珂，文雅玫，蔡 喆

(1.國防科學(xué)技術(shù)大學(xué)計算機(jī)學(xué)院，湖南 長沙 410073;2.湖南省煙草專賣局(公司)經(jīng)濟(jì)信息中心，湖南 長沙 410004)

基于條件隨機(jī)場模型的數(shù)據(jù)異常檢測算法*

王文珂1，文雅玫2，蔡 喆2

(1.國防科學(xué)技術(shù)大學(xué)計算機(jī)學(xué)院，湖南 長沙 410073;2.湖南省煙草專賣局(公司)經(jīng)濟(jì)信息中心，湖南 長沙 410004)

企業(yè)數(shù)據(jù)中心作為輔助決策的重要工具，保證其數(shù)據(jù)的及時性、準(zhǔn)確性和科學(xué)性是最基本的要求和最核心的原則。對于數(shù)據(jù)異常的情況，若僅依靠人為的經(jīng)驗在海量數(shù)據(jù)中進(jìn)行判斷是很困難的，也是不科學(xué)且低效的。針對企業(yè)購銷存數(shù)據(jù)的準(zhǔn)確性問題，研究了基于機(jī)器學(xué)習(xí)的數(shù)據(jù)異常檢測算法。由于購銷存數(shù)據(jù)是由一組相對固定的數(shù)據(jù)項組成，可以看作是一個結(jié)構(gòu)化數(shù)據(jù)序列，因此選擇了解決結(jié)構(gòu)化序列預(yù)測問題最為有效的條件隨機(jī)場模型CRFs。通過對大量歷史數(shù)據(jù)進(jìn)行學(xué)習(xí)，分析出數(shù)據(jù)的自身規(guī)律以及關(guān)聯(lián)關(guān)系，使計算機(jī)具備自動檢測異常的能力。實驗結(jié)果表明了該算法的有效性。

數(shù)據(jù)中心；機(jī)器學(xué)習(xí)；數(shù)據(jù)異常檢測；條件隨機(jī)場模型

1 引言

湖南煙草商業(yè)企業(yè)的數(shù)據(jù)中心建設(shè)，從全局視角整合了企業(yè)經(jīng)營和運(yùn)行的數(shù)據(jù)資源，形成了包含卷煙營銷、煙葉、專賣、財務(wù)、宏觀經(jīng)濟(jì)數(shù)據(jù)和工業(yè)協(xié)同等綜合性數(shù)據(jù)信息的企業(yè)級數(shù)據(jù)倉庫，成為企業(yè)管理的標(biāo)準(zhǔn)數(shù)據(jù)源。在此基礎(chǔ)上，通過數(shù)理分析，形成各層級人員需要的統(tǒng)計分析報表，為戰(zhàn)略監(jiān)控、業(yè)務(wù)運(yùn)營和職能管理提供參考依據(jù)，初步實現(xiàn)了企業(yè)管理規(guī)范化，決策科學(xué)化[1]。

然而，由于數(shù)據(jù)中心本身不產(chǎn)生數(shù)據(jù)，其數(shù)據(jù)源來自于省公司自建的營銷系統(tǒng)、行業(yè)統(tǒng)一建設(shè)的打掃碼系統(tǒng)等多個一線業(yè)務(wù)系統(tǒng)，中間涉及全省14個地州市公司以及近百個縣公司的數(shù)據(jù)統(tǒng)計環(huán)節(jié)，任何一個環(huán)節(jié)出現(xiàn)問題，都會使得最終匯集到數(shù)據(jù)中心的數(shù)據(jù)與實際銷量產(chǎn)生偏差。對于這種與實際銷售數(shù)據(jù)不符的、有偏差的數(shù)據(jù)，我們稱之為異常數(shù)據(jù)。通常，有經(jīng)驗的企業(yè)領(lǐng)導(dǎo)和業(yè)務(wù)人員通過經(jīng)驗，可判斷出報表數(shù)據(jù)存在偏差及異常，但這嚴(yán)重影響了工作效率，也降低了數(shù)據(jù)中心的權(quán)威性。為了提高數(shù)據(jù)質(zhì)量，我們通過經(jīng)驗積累，嘗試建立了一系列的數(shù)據(jù)檢測規(guī)則，例如：庫存數(shù)應(yīng)是正數(shù)等。但是，無法枚舉出所有規(guī)則，也無法科學(xué)地找出數(shù)據(jù)中存在的客觀規(guī)律。尋求合適的異常數(shù)據(jù)檢測方法、提升數(shù)據(jù)質(zhì)量，是我們亟需解決的問題。

由于數(shù)據(jù)中心存在大量的歷史數(shù)據(jù)，這些數(shù)據(jù)可用于對計算機(jī)進(jìn)行訓(xùn)練，從而獲取其內(nèi)在規(guī)律。當(dāng)出現(xiàn)異常時，經(jīng)過訓(xùn)練的“智能化”計算機(jī)則可自動檢測并發(fā)出異常警告。本文的主要工作是，以企業(yè)購銷存相關(guān)數(shù)據(jù)為例，借鑒機(jī)器學(xué)習(xí)的方法，研究數(shù)據(jù)異常的自動檢測方法。由于企業(yè)購銷存數(shù)據(jù)之間存在一定的關(guān)聯(lián)關(guān)系，屬于結(jié)構(gòu)化數(shù)據(jù)序列，充分考慮數(shù)據(jù)項之間的關(guān)系，而不是單獨(dú)對每個數(shù)據(jù)項進(jìn)行局部檢測，能提高檢測質(zhì)量，獲得全局最優(yōu)結(jié)果。因此，其異常檢測問題可看作是結(jié)構(gòu)化數(shù)據(jù)序列的預(yù)測問題。本文選擇了解決結(jié)構(gòu)化序列預(yù)測問題最為有效方法之一的條件隨機(jī)場CRFs(Conditional Random Fields)模型。條件隨機(jī)場模型最早由Lafferty J等[2]提出，是一個廣泛應(yīng)用于結(jié)構(gòu)化序列預(yù)測問題的概率模型。該模型不但可以自動綜合多種數(shù)據(jù)特征，還可以有效利用數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系。相比獨(dú)立預(yù)測的方式，該模型可以更好地獲取全局最優(yōu)解。

條件隨機(jī)場模型是一個圖結(jié)構(gòu)模型，本文首先根據(jù)企業(yè)購銷存數(shù)據(jù)的特性定義了一種圖結(jié)構(gòu)。然后，基于該無向圖，詳細(xì)介紹了如何利用條件隨機(jī)場模型進(jìn)行數(shù)據(jù)異常檢測。

本文內(nèi)容的組織如下：第2節(jié)簡要介紹了條件隨機(jī)場模型的相關(guān)概念；第3節(jié)詳細(xì)描述了基于條件隨機(jī)場模型的企業(yè)購銷存數(shù)據(jù)異常檢測算法；第4節(jié)給出了算法的實驗結(jié)果；最后，第5節(jié)總結(jié)了本文工作并展望了下一步研究方向。

2 條件隨機(jī)場模型

條件隨機(jī)場模型對結(jié)構(gòu)化數(shù)據(jù)預(yù)測問題提供了一套非常有效的表示方法和推理框架，且已經(jīng)成功應(yīng)用于計算機(jī)視覺[3]、自然語言處理[4]、互聯(lián)網(wǎng)數(shù)據(jù)挖掘[5]和計算機(jī)輔助設(shè)計[6]等多個領(lǐng)域。

Figure 1 Structure of the linear conditional random fields model

圖1給出了線性條件隨機(jī)場模型的結(jié)構(gòu)示意圖。圖V=X∪Y中包含有兩種類型的節(jié)點：X是輸入節(jié)點集合，表示可觀測到的信息；Y是輸出節(jié)點集合，表示需要被預(yù)測的標(biāo)注信息?；谠搱D結(jié)構(gòu)，條件隨機(jī)場模型的定義如下[7]:

(1)

其中Z(x) 是一個正則化函數(shù)，使得所有的條件分布和為1，滿足概率意義：

參數(shù)λk是特征函數(shù)fk的權(quán)值，需要通過訓(xùn)練數(shù)據(jù)集來估計該參數(shù)值。

在本文中，用y(或者yt、y′)表示某一觀測節(jié)點對應(yīng)的標(biāo)注變量。例如，在圖1 中有六個標(biāo)注變量y1,y2,…,y6。Y則表示所有觀測節(jié)點的標(biāo)注集合。例如，在圖1中，Y={y1,y2,…,y6}表示所有標(biāo)注變量的集合。同理，X表示觀測變量的集合，x表示某一觀測變量。從公式(1)中可以看出，條件隨機(jī)場模型是同時考慮所有標(biāo)注變量來獲得全局最優(yōu)結(jié)果，而不是只考慮一個標(biāo)注變量的局部最優(yōu)結(jié)果，這也是條件隨機(jī)場模型的優(yōu)勢之一。

3 基于條件隨機(jī)場模型的企業(yè)購銷存數(shù)據(jù)異常檢測算法

應(yīng)用條件隨機(jī)場模型解決企業(yè)購銷存數(shù)據(jù)異常檢測問題，主要包括以下三個步驟：(1)由于條件隨機(jī)場模型是一個圖結(jié)構(gòu)模型，因此需要將企業(yè)購銷存數(shù)據(jù)的關(guān)系以圖結(jié)構(gòu)表示。(2)由于條件隨機(jī)場模型是通過自動綜合多種數(shù)據(jù)特征對異常情況進(jìn)行預(yù)測，因此需要定義有效的特征函數(shù)。(3)需要定義如何評估參數(shù)值θ={λk}。并且，對于新的數(shù)據(jù)，如何預(yù)測標(biāo)簽Y。對于以上三個步驟，將分別在下面三個小節(jié)中進(jìn)行詳細(xì)說明。

3.1 圖結(jié)構(gòu)

這一步，將根據(jù)數(shù)據(jù)的關(guān)聯(lián)關(guān)系，構(gòu)造數(shù)據(jù)關(guān)系圖。通常，經(jīng)營簡報中關(guān)于月度企業(yè)購銷存數(shù)據(jù)的描述如下：

“某月份，全省系統(tǒng)購進(jìn)卷煙a萬箱，其中省產(chǎn)卷煙b萬箱、省外卷煙c萬箱；全省系統(tǒng)銷售卷煙d萬箱，同比增長e，其中省產(chǎn)卷煙f萬箱、省外卷煙g萬箱，省外煙銷量累計占比h；某月末，全省系統(tǒng)卷煙庫存為s萬箱，存銷比l?！?/p>

根據(jù)數(shù)據(jù)間的關(guān)聯(lián)關(guān)系，可構(gòu)造月度企業(yè)購銷存數(shù)據(jù)關(guān)系圖。

定義2月度企業(yè)購銷存數(shù)據(jù)關(guān)系圖MDG={L,E}是一個用于表示各數(shù)據(jù)項之間關(guān)聯(lián)關(guān)系的無向圖，其中L是節(jié)點集合，E表示邊集合。集合L中的節(jié)點與數(shù)據(jù)項一一對應(yīng)，集合E中的邊則表示相連兩數(shù)據(jù)項間的關(guān)系。

圖2給出了根據(jù)上述描述構(gòu)造的月度企業(yè)購銷存數(shù)據(jù)關(guān)系圖。

Figure 2 Constructed MDG

3.2 特征集

條件隨機(jī)場模型的一大優(yōu)勢在于可以自動綜合多種特征函數(shù)，從而挖掘出數(shù)據(jù)潛在的規(guī)律性。本節(jié)將詳細(xì)介紹用于機(jī)器學(xué)習(xí)的特征集。

表1 列出了數(shù)據(jù)異常檢測用到的特征集，其中定義了兩類特征：一類是數(shù)據(jù)關(guān)系圖中節(jié)點的屬性特征；另一類是數(shù)據(jù)關(guān)系圖中邊上的關(guān)聯(lián)特征。目前，定義了三種屬性特征和四種關(guān)聯(lián)特征。數(shù)據(jù)項的屬性特征包括：數(shù)據(jù)項是否為正數(shù)、數(shù)據(jù)項是否為小數(shù)、數(shù)據(jù)項的位數(shù)。關(guān)聯(lián)特征則描述了數(shù)據(jù)項之間的邏輯關(guān)系。

接著，需要為每個特征定義對應(yīng)的特征函數(shù)。根據(jù)條件隨機(jī)場模型的定義，公式(1)中的特征函數(shù)fk(y,y′,x)也包含兩種類型：一類是狀態(tài)特征函數(shù)sk(yi,x)，用于表示標(biāo)簽yi與觀察變量x之間的關(guān)系；另一類是傳遞特征函數(shù)tk(y,y′,x)，用于表示相鄰標(biāo)簽y和y′之間的關(guān)系。傳遞特征函數(shù)tk(y,y′,x)也可依賴于觀察變量x。為了簡化該模型，本文定義的傳遞特征函數(shù)與觀察變量x無關(guān)。因此，可根據(jù)屬性特征定義狀態(tài)特征函數(shù)，根據(jù)關(guān)聯(lián)特征定義傳遞特征函數(shù)。

Table 1 Features表1 特征集

注：n表示數(shù)據(jù)關(guān)系圖中某數(shù)據(jù)項i對應(yīng)的圖節(jié)點。

對于表1 所列的特征，分別定義了相應(yīng)的離散特征函數(shù)。例如，對應(yīng)于屬性特征PN(n)的狀態(tài)特征函數(shù)定義為：

其中，y表示節(jié)點n的標(biāo)簽，x表示觀察變量。

對應(yīng)于屬性特征FN(n)的狀態(tài)特征函數(shù)定義為：

其中，y表示節(jié)點n的標(biāo)簽，x表示觀察變量。

3.3 參數(shù)估計及預(yù)測

本小節(jié)將介紹如何估計參數(shù)值和預(yù)測新樣本的最佳標(biāo)注信息。這里主要包含兩個任務(wù)：首先，對于預(yù)定義的特征函數(shù)，需要估計對應(yīng)的參數(shù)值θ={λk}，這樣才能計算公式(1)中的條件概率p(y|x)；其次，需要預(yù)測一個新樣本X的最佳標(biāo)簽結(jié)果。如果一個樣本包含n個節(jié)點，并且一共含有m種不同的標(biāo)簽類型，那么這個樣本的標(biāo)簽結(jié)果Y有mn種可能。如果窮舉所有的可能從而找到最佳結(jié)果，計算效率將會非常低。因此，需要利用一種有效的方法來找到最佳的預(yù)測結(jié)果。

利用條件隨機(jī)場模型，主要包含以下兩個步驟：訓(xùn)練(參數(shù)估計)和測試(預(yù)測)。在訓(xùn)練階段，需要利用已有的標(biāo)注數(shù)據(jù)來估計參數(shù)(特征函數(shù)的權(quán)值)θ={λk}∈Rk；在測試階段，則利用學(xué)習(xí)的模型參數(shù)來預(yù)測新樣本的標(biāo)注結(jié)果。因為本文定義的數(shù)據(jù)關(guān)系圖是一個樹形圖，因此需要一個樹形結(jié)構(gòu)的條件隨機(jī)場模型，如圖3所示。下面將主要介紹如何在樹形條件隨機(jī)場模型上進(jìn)行參數(shù)估計和預(yù)測新樣本的標(biāo)注結(jié)果。

Figure 3 Structure of the tree conditional random fields model

(2)

這里的目標(biāo)是解決如下優(yōu)化問題：

argmaxθ=λkL(θ)

為了防止過擬合，在公式(2)中加入了正則因子，避免過大的參數(shù)估計值。加入正則因子后的條件似然函數(shù)定義為：

(3)

對公式(3)求參數(shù)的偏導(dǎo)數(shù)，可得：

其中，p(y,y′|x(i))是指給定x(i)的情況下，變量y和y′的邊緣分布。

關(guān)于樹形結(jié)構(gòu)上的邊緣分布計算問題，已有多種成熟的推理算法，本節(jié)則采用了精確推理算法Sum-Product[8]。Sum-Product算法利用消息傳遞技術(shù)來迭代處理相鄰變量，是一種動態(tài)規(guī)劃算法，可以有效地計算出上式中的邊緣概率分布。

選擇凸函數(shù)L(θ)作為目標(biāo)函數(shù)，這樣可以保證局部最優(yōu)值的同時也是全局最優(yōu)值。最優(yōu)化函數(shù)問題可以采用迭代的方法求解，本節(jié)采用了L-BFGS方法[9]。該方法只需要利用目標(biāo)函數(shù)的導(dǎo)數(shù)，并且已被證明是一種有效解決條件隨機(jī)場模型的方法[10]。

在完成訓(xùn)練階段估計完所有的參數(shù)值后，則可進(jìn)入測試階段預(yù)測新樣本的標(biāo)注信息。預(yù)測過程是希望能夠為新樣本找到最有可能的標(biāo)注結(jié)果：

y*=argmaxp(y|x)

為了找到最優(yōu)的y*，即需要找到使p(y|x)取值最大的y*。若通過枚舉所有可能的標(biāo)注結(jié)果來求得最優(yōu)值是不現(xiàn)實的，因為這種暴力搜索的時間復(fù)雜度是O(mn)，其中m是指標(biāo)注類別的數(shù)目，n是指樣本x包含的節(jié)點數(shù)目。因此，本文采用了一種有效的預(yù)測方法Max-Product[7]。Max-Product算法是上面所提Sum-Product算法的一種變形算法，它將Sum-Product中的求和運(yùn)算(Sum)變?yōu)榍笞畲笾?Max)。同樣，Max-Product算法也是一種有效的動態(tài)規(guī)劃算法，它可將預(yù)測的時間復(fù)雜度從O(mn)降到O(m2)。

4 實驗分析

為了驗證本文算法對異常數(shù)據(jù)的檢測效果，我們收集了2009年～2013年這五年的企業(yè)月度購銷存數(shù)據(jù)。對于60組全部正確的數(shù)據(jù)，首先，手工將其中多組數(shù)據(jù)中的單個數(shù)據(jù)項進(jìn)行修改。然后，隨機(jī)選取了其中的40組作為訓(xùn)練集，剩下的20組則作為測試集。接著，手工為數(shù)據(jù)序列中的每個數(shù)據(jù)項標(biāo)記正常/異常標(biāo)簽。在學(xué)習(xí)階段，通過對訓(xùn)練集數(shù)據(jù)進(jìn)行評估，獲得了表示特征函數(shù)相對權(quán)重的最優(yōu)參數(shù)θ={λk}。在測試階段，首先隱藏測試集數(shù)據(jù)中手工標(biāo)記的標(biāo)簽，然后采用本文基于條件隨機(jī)場模型的算法對數(shù)據(jù)序列中每個數(shù)據(jù)項的標(biāo)簽進(jìn)行預(yù)測。最后，通過比較手工標(biāo)記的標(biāo)簽和機(jī)器預(yù)測的標(biāo)簽是否一致來檢測該算法的有效性。

對于上述實驗步驟，我們重復(fù)了五次，實驗數(shù)據(jù)說明如表2所示。

由于本文算法是用于檢測新增的月度數(shù)據(jù)是否正確，異常數(shù)據(jù)只是個別現(xiàn)象，所以實驗中異常數(shù)據(jù)選擇在1～5個。此外，異常數(shù)據(jù)是由于統(tǒng)計不全面造成的，因此異常數(shù)據(jù)浮動范圍選擇在2%～30%。實驗結(jié)果表明，本文算法準(zhǔn)確識別出了手工修改的實際工作中常見的異常數(shù)據(jù)。

Table 2 Experimental data表2 實驗數(shù)據(jù)說明

5 結(jié)束語

本文針對數(shù)據(jù)中心里數(shù)據(jù)異常的問題，以成熟的機(jī)器學(xué)習(xí)方法為基礎(chǔ)，研究了基于條件隨機(jī)場模型的數(shù)據(jù)異常檢測算法。

數(shù)據(jù)異常檢測、數(shù)據(jù)預(yù)測等數(shù)據(jù)分析技術(shù)的研究在數(shù)據(jù)中心的優(yōu)化完善中具有重要的應(yīng)用價值，企業(yè)對于科學(xué)實用的數(shù)據(jù)分析技術(shù)也有著迫切的需求。然而，這方面的研究還不夠深入和全面，數(shù)據(jù)里更深層次的信息還未被充分挖掘。下一步，可以從智能化的角度出發(fā)，綜合考慮企業(yè)的實際需求，在充分挖掘數(shù)據(jù)信息、提高數(shù)據(jù)科學(xué)性及權(quán)威性等方面繼續(xù)進(jìn)行深入研究，以推動數(shù)據(jù)分析技術(shù)在數(shù)據(jù)中心的應(yīng)用。

[1] Jiang Xiao-fang. Date center,a good helperofleaders[J].China Tobacco,2012(5):1.(in Chinese)

[2] Lafferty J, McCallum A, Pereira F. Conditional random fields: Probabilistic models for segmentingand labeling sequence data [C]∥Proc of the 18th International Conference on Machine Learning,2001:282-289.

[3] Quattoni A,Collins M,Darrell T. Conditional random fields for object recognition [C]∥Proc of Advances in Neural Information Processing Systems (NIPS-17),2005:1097-1104.

[4] McCallum A. Efficiently inducing features of conditional random fields [C]∥Proc of the 19th Conference on Uncertainty in Artificial Intelligence,2003:403-410.

[5] Culotta A,Bekkerman R,McCallum A. Extracting social networks and contact information from email and the web [C]∥Proc of the 1st Conference on Email and Anti-Spam (CEAS),2004:1.

[6] Wen Ya-mei. Studies on 3D solid reconstruction from 2D engineering drawings with sectional views [D]. Beijing: Tsinghua University, 2012. (in Chinese)

[7] Sutton C, McCallum A. An introduction to conditional random fields for relational learning [M]∥Introduction to Statistical Relational Learning.Massachusetts:MIT Press,2006.

[8] Kschischang F,Frey B,Loeliger H. Factor graphs and the sum-product algorithm [J]. IEEE Transactions on Information Theory,2001,47(2):498-519.

[9] Liu D,Nocedal J. On the limited memory BFGS method for large scale optimization [J]. Mathematical Programming,1989,45(1):503-528.

[10] Sha F,Pereira F. Shallow parsing with conditional random fields [C]∥Proc of Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology-Volume (HLT-NAACL),2003:213-220.

附中文參考文獻(xiàn)：

[1] 蔣曉方.數(shù)據(jù)中心——決策的好幫手[J].中國煙草,2012(5):1.

[6] 文雅玫. 基于帶剖視工程圖的三維重建算法研究[D]. 北京：清華大學(xué),2012.

王文珂(1981-),男,山東德州人，博士，副研究員，研究方向為虛擬現(xiàn)實與科學(xué)計算可視化。E-mail:wangwenke@nudt.edu.cn

WANG Wen-ke,born in 1981,PhD,associate research fellow,his research interests include virtual reality, and scientific visualization.

Abnormal data detection algorithm based on conditional random fields model

WANG Wen-ke1,WEN Ya-mei2,CAI Zhe2

(1.College of Computer,National University of Defense Technology,Changsha 410073;2.Information Center,Hunan Tobacco,Changsha 410004,China)

Data centers are an important auxiliary tool for business leaders to make decisions, and timely, accurate and scientific data are basic requirements and key principles. It is difficult and inefficient to find out abnormal one in huge amounts of data by human experience. In this paper, we propose an algorithm for detecting abnormal data based on machine learning. Because enterprise sales data consist of a series of relatively fixed data items, they can be recognized as a structured data sequence. Conditional Random Fields (CRFs) model is efficient for structured data sequence prediction, so it can be used as the detection model. A large number of history data are learnt and their intrinsic rules and relationship are analyzed so as to enable computers to detect abnormal data automatically. Experimental result shows the effectiveness of the proposed algorithm.

data center;machine learning;detection of abnormal data;conditional randomfieldsmodel

1007-130X(2015)09-1756-05

2014-07-08;

2014-10-21基金項目：國家自然科學(xué)基金資助項目(61202335)

TP274

A

10.3969/j.issn.1007-130X.2015.09.026

通信地址：410004 湖南省長沙市煙草專賣局(公司)經(jīng)濟(jì)信息中心 文雅玫

Address:Information Center,Hunan Tobacco,Changsha 410004,Hunan,P.R.China