紀(jì)　勇

（安徽創(chuàng)世科技股份有限公司，安徽　合肥　230088）

基于頻繁模式的KPI異常檢測(cè)研究

紀(jì)勇

（安徽創(chuàng)世科技股份有限公司，安徽合肥230088）

文章針對(duì)TD-SCDMA現(xiàn)網(wǎng)采集的網(wǎng)絡(luò)關(guān)鍵績(jī)效指標(biāo)（Key Performance Indicator，KPI），，利用頻繁模式挖掘的方法，重點(diǎn)分析掉話率、無線接通率、擁塞率等之間的關(guān)聯(lián)性。將頻繁模式項(xiàng)定義為正常模式，以此進(jìn)行異常模式檢測(cè)。這樣的方式不僅有效地檢測(cè)了網(wǎng)絡(luò)存在的異常組合，也反映了參數(shù)之間的關(guān)聯(lián)性，對(duì)快速在線檢測(cè)起到了有效的指導(dǎo)作用。

頻繁模式；異常檢測(cè)；數(shù)據(jù)挖掘；KPI

1　移動(dòng)通信的發(fā)展概況

移動(dòng)通信網(wǎng)中的網(wǎng)絡(luò)異常檢測(cè)一直以來都是一個(gè)火熱的話題。通過有效地提升網(wǎng)絡(luò)的性能，能夠從本質(zhì)上提升用戶的體驗(yàn)。在實(shí)際網(wǎng)絡(luò)中，KPI是網(wǎng)絡(luò)性能監(jiān)測(cè)的重要參數(shù)，運(yùn)營(yíng)商按照一定的時(shí)間粒度，獲取相應(yīng)的KPI參數(shù)。根據(jù)網(wǎng)絡(luò)參數(shù)表現(xiàn)出來的特性，按照經(jīng)驗(yàn)分析網(wǎng)絡(luò)可能存在的問題，從而定位異常產(chǎn)生的原因。

隨著4G時(shí)代的逐漸深入以及5G時(shí)代的即將來臨，很多流行應(yīng)用包括上網(wǎng)、視頻、音樂、社交等都從固網(wǎng)轉(zhuǎn)換到移動(dòng)通信網(wǎng)中，加上移動(dòng)物聯(lián)網(wǎng)的逐步形成，移動(dòng)通信數(shù)據(jù)呈現(xiàn)爆炸式增長(zhǎng)。思科在2015年發(fā)布的關(guān)于流量的預(yù)測(cè)報(bào)告顯示，直至2020年，移動(dòng)通信網(wǎng)的每月數(shù)據(jù)流量將會(huì)增加到30.6 EByte，相比于2016年的6.2 EByte翻了接近5倍［1］。在這樣的形式下，網(wǎng)絡(luò)的復(fù)雜構(gòu)成造成了網(wǎng)絡(luò)異常成因的復(fù)雜性以及多樣性。單純地按照經(jīng)驗(yàn)進(jìn)行網(wǎng)絡(luò)異常的判定存在一定的局限性。

除此之外，通信數(shù)據(jù)的極速增長(zhǎng)不僅僅增加了網(wǎng)路的復(fù)雜性，同時(shí)也引領(lǐng)了移動(dòng)通信大數(shù)據(jù)時(shí)代的到來。網(wǎng)絡(luò)的成因考慮的不再是因果關(guān)系，而是參數(shù)之間的關(guān)聯(lián)。因此，運(yùn)用大數(shù)據(jù)的手段分析網(wǎng)絡(luò)參數(shù)之間的關(guān)聯(lián)性成為一種新型有效的方式。

為了能更好地了解KPI參數(shù)之間的關(guān)聯(lián)性以及網(wǎng)絡(luò)可能存在的異常KPI組合，文章針對(duì)現(xiàn)網(wǎng)采集的TD-SCDMA網(wǎng)絡(luò)KPI參數(shù)進(jìn)行分析。利用頻繁模式挖掘的手段，著重分析掉話率、無線接入性，擁塞率等常用網(wǎng)絡(luò)監(jiān)測(cè)參數(shù)之間的頻繁模式，并以此作為網(wǎng)絡(luò)KPI正常模式來檢測(cè)網(wǎng)絡(luò)的異常模式。這樣的方式為在線檢測(cè)提供了快速匹配的碼本模式，同時(shí)也能很好地分析網(wǎng)絡(luò)KPI 參數(shù)之間的關(guān)聯(lián)性，從而更快地定位到異常產(chǎn)生的原因。

2　相關(guān)研究

移動(dòng)通信網(wǎng)的網(wǎng)絡(luò)異常檢測(cè)一直是運(yùn)營(yíng)商亟待解決的重要問題。針對(duì)這一問題，很多學(xué)者圍繞兩個(gè)方面展開研究：（1）網(wǎng)絡(luò)性能參數(shù)，即上下行數(shù)據(jù)量、數(shù)據(jù)速率、擁塞率等；（2）端到端的服務(wù)質(zhì)量（Quality of Service，QoS）或者用戶體驗(yàn)（Quality of Experience，QoE），即延遲、抖動(dòng)或者M(jìn)OS（Mean Opinion Score）。對(duì)于運(yùn)營(yíng)商而言，QoS和QoE都屬于端到端的特性，更多的是反映終端用戶的直接體驗(yàn)，不能直接反映網(wǎng)絡(luò)的性能。除此之外，端到端的參數(shù)提取需要消耗大量的人力物力，性價(jià)比較低。同時(shí)QoE由于涉及用戶的體驗(yàn)，更多時(shí)候摻雜了用戶的主觀意愿，不具有一般性，因此，文章研究的重點(diǎn)在網(wǎng)絡(luò)性能參數(shù)KPI上。

在大多數(shù)KPI參數(shù)研究中，單閾值分析是一個(gè)廣泛使用的統(tǒng)計(jì)方法。單變量與多變量閾值異常檢測(cè)方式是當(dāng)前網(wǎng)絡(luò)運(yùn)營(yíng)商部署采用的方案。這一方法將新到達(dá)的KPI參數(shù)與訓(xùn)練數(shù)據(jù)的均值進(jìn)行比較，當(dāng)偏差超過設(shè)定的閾值是，認(rèn)為是異常點(diǎn)。文獻(xiàn)［2—3］中，作者使用其他單變量統(tǒng)計(jì)結(jié)果，比如：累積分布函數(shù)（Cumulative Distribution Function，CDF），差分自回歸移動(dòng)平均模型（AutoRegressive Integrated Moving Average，ARIMA）等，對(duì)KPI特性進(jìn)行建模，并檢測(cè)測(cè)試數(shù)據(jù)是否能與模型很好地?cái)M合。針對(duì)用戶域名系統(tǒng)（Domain Name System，DNS）請(qǐng)求次數(shù)，文獻(xiàn)［4—6］利用相對(duì)熵（Kullback-Leibler，KL）-divergence作為指標(biāo)參數(shù)來分析檢測(cè)分布與參考分布之間的距離，從而判定檢測(cè)分布是否為異常。相似地，文獻(xiàn)［7—8］采用基于熵的方法分析流量的變化情況判別流量的異常突變。上述提及的所有統(tǒng)計(jì)方法本質(zhì)上利用的都是新數(shù)據(jù)與訓(xùn)練數(shù)據(jù)統(tǒng)計(jì)模型之間的偏差關(guān)系。統(tǒng)計(jì)模型完全依賴于訓(xùn)練數(shù)據(jù)，當(dāng)異常點(diǎn)出現(xiàn)在訓(xùn)練數(shù)據(jù)中時(shí)，統(tǒng)計(jì)模型（比如：均值、方差等）的精確度就會(huì)顯著降低。反之，當(dāng)訓(xùn)練數(shù)據(jù)都正常時(shí)，統(tǒng)計(jì)模型可以代表正常點(diǎn)模型。除此之外，這些模型大多針對(duì)單獨(dú)的維度進(jìn)行處理，忽略了維度之間可能存在的關(guān)聯(lián)性。

近年來，大數(shù)據(jù)已經(jīng)逐步深入到各行各業(yè)中，數(shù)據(jù)挖掘的方法也隨之被廣泛應(yīng)用。其中，聚類、頻繁模式挖掘成為最主要的異常檢測(cè)方法［9—10］。異常的定義是指遠(yuǎn)離其他觀測(cè)點(diǎn)的點(diǎn)［11—12］，基于這樣的定義，可以使用聚類或者頻繁模式挖掘的方法得到正常的點(diǎn)簇或者模式，以此作為正常模型。基于密度聚類的聚類算法（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）［13］是典型的利用密度較大的區(qū)域作為正常簇，而密度較小的點(diǎn)作為異常點(diǎn)的聚類算法，并在此基礎(chǔ)上進(jìn)行了一系列的改進(jìn)［14］。這樣的非監(jiān)督聚類、頻繁模式獲取正常點(diǎn)模型的方法對(duì)異常點(diǎn)的敏感性比較低，當(dāng)訓(xùn)練數(shù)據(jù)中存在異常點(diǎn)時(shí)，得到的模型不會(huì)受到異常點(diǎn)的影響，從而使得這樣得到的模型比使用統(tǒng)計(jì)方法得到的模型具有更高的魯棒性。

本文針對(duì)網(wǎng)絡(luò)性能參數(shù)KPI，利用頻繁模式挖掘的方法得到具有頻繁項(xiàng)的多維KPI組成形式，以此作為正常點(diǎn)的模型，進(jìn)行異常檢測(cè)時(shí)，將組合與正常點(diǎn)模型進(jìn)行匹配，具有較大偏差的組合被認(rèn)為是異常形式。將整體數(shù)據(jù)凝聚成不同頻繁模式的方法可以有效地減小匹配數(shù)據(jù)的大小，從而在進(jìn)行在線異常檢測(cè)時(shí)具有極高的效率。

3　FP-Growth算法基本原理

FP-Growth 算法是文獻(xiàn)［15］中提出的一種快速頻繁模式挖掘算法。該算法能在不生成候選項(xiàng)，且只掃描一次數(shù)據(jù)庫的情況下，完成Apriori算法的功能，從而有效地解決海量數(shù)據(jù)下，Apriori算法的時(shí)空復(fù)雜度。本文使用的算法是FPGrowth算法，在處理數(shù)據(jù)時(shí)極大地提升了處理的速度。在分析實(shí)際數(shù)據(jù)前簡(jiǎn)單介紹一下FP-Growth算法的基本原理，主要包括以下幾個(gè)部分：

3.1FP-tree生成

FP-Growth算法的核心部分使用了一種基本數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)包含一棵頻繁模式樹（frequent pattern tree，F(xiàn)P-tree）和一個(gè)表頭項(xiàng)，每個(gè)項(xiàng)通過一個(gè)節(jié)點(diǎn)鏈接指向它在樹中出現(xiàn)的位置。

圖1給出了一個(gè)FP-Tree形成過程的案例。首先掃描一遍數(shù)據(jù)庫，得到每個(gè)Item的頻數(shù)，去除支持度較低的項(xiàng)（min_ support=3），得到1-頻繁項(xiàng)集。根據(jù)支持度對(duì)頻繁項(xiàng)進(jìn)行排序，將支持度高的項(xiàng)排在前面，使得生成的FP-tree中，出現(xiàn)的頻繁項(xiàng)更可能被共享，從而有效地節(jié)省算法運(yùn)行所需要的空間。

圖1　FP-tree的形成過程

3.2FP-tree子集分割

如圖1所示，求以p為前綴的投影數(shù)據(jù)庫：根據(jù)頭表的指針找到FP-tree的兩個(gè)p節(jié)點(diǎn)，搜索出從這兩個(gè)節(jié)點(diǎn)到樹的根節(jié)點(diǎn)路徑節(jié)點(diǎn)信息（包含支持度）。然后累加路徑節(jié)點(diǎn)信息的支持度，刪除非頻繁項(xiàng)。對(duì)剩下的頻繁項(xiàng)按照上一節(jié)的方法構(gòu)建條件FP-tree，過程如圖2所示。

圖2　條件FP-tree形成過程

通過這樣的方式最終得到關(guān)于P的頻繁項(xiàng)，在這過程中涉及幾個(gè)基本概念：

（1）條件模式基。包含F(xiàn)P-tree中與后綴模式一起出現(xiàn)的前綴路徑的集合，即同一個(gè)頻繁項(xiàng)在FP-tree中的所有節(jié)點(diǎn)的祖先路徑的集合。比如，p在FP-tree中出現(xiàn)了2次，其祖先路徑分別為｛fcam：2（頻度為2）｝和｛cb：1｝，這2個(gè)祖先路徑的集合就是頻繁項(xiàng)p的條件模式基。

（2）條件樹。將條件模式基按照FP-tree的構(gòu)造原則形成新的FP-tree，即圖2最終形成的p-conditional FP-tree。

FP-Growth算法的基本思路：不斷地迭代FP-tree的構(gòu)造和投影過程。當(dāng)構(gòu)造的FP-tree為空時(shí)，前綴即為頻繁模式；當(dāng)只包含一條路徑時(shí)，枚舉所有可能組合并與此樹的前綴連接，即可得到頻繁模式。其算法偽代碼如表1所示。

表1　算法偽代碼

根據(jù)上述介紹的FP-Growth算法進(jìn)行頻繁模式挖掘。

4　案例分析

4.1數(shù)據(jù)來源

本案例數(shù)據(jù)集來源于現(xiàn)網(wǎng)采集的中國(guó)移動(dòng)TD-SCDMA的一個(gè)省的部分?jǐn)?shù)據(jù)。數(shù)據(jù)從2015年12月1日00:00到2015年12月31日24:00，總共持續(xù)了接近1個(gè)月。數(shù)據(jù)采集的范圍包含243個(gè)小區(qū)，時(shí)間粒度為1個(gè)小時(shí)，包含64個(gè)KPI數(shù)據(jù)。表2給出了進(jìn)行案例分析的數(shù)據(jù)來源。

表2　案例分析的數(shù)據(jù)來源

4.2數(shù)據(jù)預(yù)處理

分析KPI數(shù)據(jù)，發(fā)現(xiàn)部分為位置信息，部分為不是極其關(guān)注的值，最終抽取出其中的21個(gè)特征作為分析維度，如表3所示。

表3　網(wǎng)絡(luò)KPI參數(shù)

將所有數(shù)據(jù)按照N=10進(jìn)行量化，從而形成所有數(shù)據(jù)特征都在［1，10］之間的整數(shù)集合。假設(shè)數(shù)據(jù)為K維，則對(duì)應(yīng)的數(shù)據(jù)點(diǎn)為X=（x1， x2，…，xK），xk∈｛1，2，3，…，10｝。

將每個(gè)小區(qū)的每個(gè)時(shí)刻點(diǎn)看成一個(gè)數(shù)據(jù)點(diǎn)，總共有42235個(gè)數(shù)據(jù)點(diǎn)，設(shè)定最小支持度為500，得到18個(gè)頻繁模式，以這18個(gè)頻繁模式作為正常模型，進(jìn)行異常檢測(cè)。

4.3異常檢測(cè)

例如，異常數(shù)據(jù)x1=［10，1，10，4］，正常模式p1= ［10，1，10，1］，p2=［10，2，10，1］，p3=［10，1，9，1］，，匹配三個(gè)模式得到d1=1，d2=d3=2，則得到px1=［10，1，10，1］，y1=｛r4（4）｝。

針對(duì)上述變化之后的數(shù)據(jù)再次進(jìn)行頻繁模式挖掘，得到最可能產(chǎn)生異常的組合以及各參數(shù)對(duì)應(yīng)的范圍。設(shè)定最小支持度為8，最終得到1441個(gè)頻繁模式，其中包括93個(gè)1-頻繁項(xiàng)集。為了分析KPI之間的關(guān)聯(lián)性，分析多項(xiàng)頻繁項(xiàng)集，經(jīng)分析比較發(fā)現(xiàn)，引起聯(lián)合異常的KPI中三大KPI較為特殊，分別為TCH擁塞率、TCH掉話率以及SD擁塞率，下面以TCH擁塞率為例分析異常的原因。

TCH擁塞率：?jiǎn)为?dú)出現(xiàn)為處于2等級(jí)，支持度為11，聯(lián)合出現(xiàn)為<無線接入性處于9等級(jí)，TCH擁塞率處于2等級(jí)>，支持度為10，根據(jù)關(guān)聯(lián)規(guī)則｛ TCH擁塞率處于2等級(jí)=>無線接入性處于9等級(jí)｝的置信度為90.91%。說明擁塞率高時(shí)，對(duì)應(yīng)的無線接入性已經(jīng)降到90%以下，按照考核的98%的標(biāo)準(zhǔn)，該小區(qū)出現(xiàn)了無線接入性較低的問題。根據(jù)接入性的定義，需要分析其對(duì)應(yīng)的獨(dú)立專用控制信道（Stand-Alone Dedicated Control Channel，SDCCH）接通率和TCH接通率。

TCH擁塞率的范圍為［0，61.82%］，進(jìn)行Q=10的量化，得到處于2的擁塞范圍為［6.17%，12.36%］，這個(gè)范圍的下限高于平?？己藭r(shí)使用的5%的閾值?？偣搏@取11個(gè)異常項(xiàng)，其對(duì)應(yīng)的實(shí)際數(shù)據(jù)為如表4所示。

表4　TCH擁塞率異常的點(diǎn)

通過表格中的數(shù)據(jù)發(fā)現(xiàn)，這些點(diǎn)出現(xiàn)的異?；径紝儆诿r(shí)高峰期，對(duì)應(yīng)的出現(xiàn)比較嚴(yán)重的擁塞。根據(jù)無線接入性的值為［0，100%］，進(jìn)行10等級(jí)量化取得9等級(jí)的值為［82.86%，93.22%］。顯然與表中的異常數(shù)據(jù)一致。

第一行數(shù)據(jù)：小概率異常，無線接入性的等級(jí)已經(jīng)降到8，可以看出此時(shí)SDCCH的接入性出現(xiàn)了比較嚴(yán)重的問題，SDCCH分配成功率下降到88.44%，表明從開始用戶就沒有接入，擁塞引起接入困難。

第三行和第十行數(shù)據(jù)：該部分?jǐn)?shù)據(jù)雖然也存在比較嚴(yán)重的擁塞，但其業(yè)務(wù)并不屬于忙時(shí)高峰期，同時(shí)該小區(qū)中數(shù)據(jù)量極少。0.02對(duì)應(yīng)的可能是由于中間設(shè)定的TA值較大，接收了很多干擾請(qǐng)求，從而導(dǎo)致性能降低。0.08對(duì)應(yīng)的可能是信道完整率低，SDCCH信道過少，資源不足。

其余數(shù)據(jù)：大概率異常，當(dāng)擁塞的等級(jí)升到2時(shí)，會(huì)引起無線接入性等級(jí)的下降，可見本身接入就存在問題，信道資源不足，引起擁塞。

5　結(jié)語

本文通過對(duì)網(wǎng)絡(luò)KPI參數(shù)使用頻繁模式挖掘的方式，得到網(wǎng)絡(luò)的正常模式組合，利用正常模式組合作為正常模型進(jìn)行異常檢測(cè)，最終得到異常組合。為了更加深入地分析異常組合中維度之間的關(guān)聯(lián)性，需要進(jìn)一步對(duì)異常組合進(jìn)行頻繁模式挖掘，得到最可能出現(xiàn)的異常原因，以此作為網(wǎng)絡(luò)優(yōu)化的指導(dǎo)方案。同時(shí)使用模式匹配的方法能更加快速有效地進(jìn)行在線異常檢測(cè)。

［1］BARRETO G A， MOTA J C， SOUZA L G M， et al.Condition monitoring of 3g cellular networks through competitive neural models，Neural Networks， 2005（5）：1064-1075.

［2］CIOCARLIE G F， LINDQVIST U， NOVACZKI S， et al. Detecting anomalies in cellular networks using an ensemble method［J］. Network and service management， 2013（9）：171-174.

［3］CIOCARLIE G， LINDQVIST U， NITZ K， et al. On the feasibility of deploying cell anomaly detection in operational cellular networks ［J］.Network Operations and Management Symposium（NOMS）， 2014（10）：1-6.

［4］FIADINO P， DALCONZO A， SCHIIAVONE M， et al. RCATool-A Framework for Detecting and Diagnosing Anomalies in Cellular Networks［J］.Teletraffc Congress（ITC 27）， 2015（27）：194-202.

［5］FIADINO P， DALCONZO A， SCHIAVONE M， et al. Towards automatic detection and diagnosis of Internet service anomalies via DNS traffc analysis［J］.Wireless Communications and Mobile Computing Conference （IWCMC），2015（10）：373-378.

［6］FIADINO P， DALCONZO A， SCHIAVONE M， et al. Challenging Entropy-based Anomaly Detection and Diagnosis in Cellular Networks［J］.2015 ACM Conference on Special Interest Group on Data Communication. ACM， 2015（10）：87-88.

［7］LAKHINA A， CROVELLA M， DIOT C. Mining anomalies using traffic feature distributions［J］.ACM SIGCOMM Computer Communication Review. ACM， 2005（4）：217-228.

［8］NYCHIS G， SEKAR V， ANDERSEN D G， et al. An empirical evaluation of entropy-based traffic anomaly detection［J］. ACM SIGCOMM conference on Internet measurement. ACM， 2008（5）：151-156.

［9］PORTNOY L， ELEAZAR E， SALVATORE J S. Intrusion detection with unlabeled data using clustering［J］. Postgraduate Annual Research Seminar， 2001（11）：51.

［10］RAMASWAMY S， RASTOGI R， SHIM K. Effcient algorithms for mining outliers from large data sets［J］.ACM SIGMOD Record. ACM， 2000（2）：427-438.

［11］GRUBBS F E. Procedures for detecting outlying observations in samples［J］. Technometrics， 1969（1）：1-21.

［12］MADDALA G S， LAHIRI K. Introduction to econometrics［M］. New York: Macmillan， 1992.

［13］ESTER M， KIEGEL H P， et al. A density-based algorithm for discovering clusters in large spatial databases with noise［J］. International Conference on Knowledge Discovery and Data Mining， 1996（2）：226-231.

［14］MARKUS M.BREUNING， HANS-PETER KRIEGEL， et al. LOF：Identifying Density-Based Local Outliers［J］. 2000 ACM SIGMOD international conference on Management of data， 2000（14）：93-104.

［15］HAN J， PEI J， YIN Y. Mining frequent patterns without candidate generation［J］.ACM Sigmod Record. ACM， 2000（2）：1-12.

Research on anomaly detection of KPI based on frequent patterns

Ji Yong
（CREARO， Hefei 230088， China）

Aiming at the current TD-SCDMA network acquisition network key performance indicators （KPIs）， this paper used frequent pattern mining method， focused on the analysis of correlation between off rate， wireless call completion rate and congestion rate. Frequent pattern defnition was considered as the normal mode to carry out anomaly mode detection. This way not only effectively detected unusual combination of network， but also reflected the correlation between parameters， which played an effective guiding role in fast online detection.

frequent pattern； anomaly detection； data mining； KPI

紀(jì)勇（1977— ），男，四川成都，工程師；研究方向：通信信息與系統(tǒng)。