基于頻繁模式的KPI異常檢測研究

紀　勇

（安徽創世科技股份有限公司，安徽　合肥　230088）

基于頻繁模式的KPI異常檢測研究

紀勇

（安徽創世科技股份有限公司，安徽合肥230088）

文章針對TD-SCDMA現網采集的網絡關鍵績效指標（Key Performance Indicator，KPI），，利用頻繁模式挖掘的方法，重點分析掉話率、無線接通率、擁塞率等之間的關聯性。將頻繁模式項定義為正常模式，以此進行異常模式檢測。這樣的方式不僅有效地檢測了網絡存在的異常組合，也反映了參數之間的關聯性，對快速在線檢測起到了有效的指導作用。

頻繁模式；異常檢測；數據挖掘；KPI

1　移動通信的發展概況

移動通信網中的網絡異常檢測一直以來都是一個火熱的話題。通過有效地提升網絡的性能，能夠從本質上提升用戶的體驗。在實際網絡中，KPI是網絡性能監測的重要參數，運營商按照一定的時間粒度，獲取相應的KPI參數。根據網絡參數表現出來的特性，按照經驗分析網絡可能存在的問題，從而定位異常產生的原因。

隨著4G時代的逐漸深入以及5G時代的即將來臨，很多流行應用包括上網、視頻、音樂、社交等都從固網轉換到移動通信網中，加上移動物聯網的逐步形成，移動通信數據呈現爆炸式增長。思科在2015年發布的關于流量的預測報告顯示，直至2020年，移動通信網的每月數據流量將會增加到30.6 EByte，相比于2016年的6.2 EByte翻了接近5倍［1］。在這樣的形式下，網絡的復雜構成造成了網絡異常成因的復雜性以及多樣性。單純地按照經驗進行網絡異常的判定存在一定的局限性。

除此之外，通信數據的極速增長不僅僅增加了網路的復雜性，同時也引領了移動通信大數據時代的到來。網絡的成因考慮的不再是因果關系，而是參數之間的關聯。因此，運用大數據的手段分析網絡參數之間的關聯性成為一種新型有效的方式。

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

2　相關研究

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

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

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

本文針對網絡性能參數KPI，利用頻繁模式挖掘的方法得到具有頻繁項的多維KPI組成形式，以此作為正常點的模型，進行異常檢測時，將組合與正常點模型進行匹配，具有較大偏差的組合被認為是異常形式。將整體數據凝聚成不同頻繁模式的方法可以有效地減小匹配數據的大小，從而在進行在線異常檢測時具有極高的效率。

3　FP-Growth算法基本原理

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

3.1FP-tree生成

FP-Growth算法的核心部分使用了一種基本數據結構，該結構包含一棵頻繁模式樹（frequent pattern tree，FP-tree）和一個表頭項，每個項通過一個節點鏈接指向它在樹中出現的位置。

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

圖1　FP-tree的形成過程

3.2FP-tree子集分割

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

圖2　條件FP-tree形成過程

通過這樣的方式最終得到關于P的頻繁項，在這過程中涉及幾個基本概念：

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

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

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

表1　算法偽代碼

根據上述介紹的FP-Growth算法進行頻繁模式挖掘。

4　案例分析

4.1數據來源

本案例數據集來源于現網采集的中國移動TD-SCDMA的一個省的部分數據。數據從2015年12月1日00:00到2015年12月31日24:00，總共持續了接近1個月。數據采集的范圍包含243個小區，時間粒度為1個小時，包含64個KPI數據。表2給出了進行案例分析的數據來源。

表2　案例分析的數據來源

4.2數據預處理

分析KPI數據，發現部分為位置信息，部分為不是極其關注的值，最終抽取出其中的21個特征作為分析維度，如表3所示。

表3　網絡KPI參數

將所有數據按照N=10進行量化，從而形成所有數據特征都在［1，10］之間的整數集合。假設數據為K維，則對應的數據點為X=（x1， x2，…，xK），xk∈｛1，2，3，…，10｝。

將每個小區的每個時刻點看成一個數據點，總共有42235個數據點，設定最小支持度為500，得到18個頻繁模式，以這18個頻繁模式作為正常模型，進行異常檢測。

4.3異常檢測

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

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

TCH擁塞率：單獨出現為處于2等級，支持度為11，聯合出現為<無線接入性處于9等級，TCH擁塞率處于2等級>，支持度為10，根據關聯規則｛ TCH擁塞率處于2等級=>無線接入性處于9等級｝的置信度為90.91%。說明擁塞率高時，對應的無線接入性已經降到90%以下，按照考核的98%的標準，該小區出現了無線接入性較低的問題。根據接入性的定義，需要分析其對應的獨立專用控制信道（Stand-Alone Dedicated Control Channel，SDCCH）接通率和TCH接通率。

TCH擁塞率的范圍為［0，61.82%］，進行Q=10的量化，得到處于2的擁塞范圍為［6.17%，12.36%］，這個范圍的下限高于平常考核時使用的5%的閾值。總共獲取11個異常項，其對應的實際數據為如表4所示。

表4　TCH擁塞率異常的點

通過表格中的數據發現，這些點出現的異常基本都屬于忙時高峰期，對應的出現比較嚴重的擁塞。根據無線接入性的值為［0，100%］，進行10等級量化取得9等級的值為［82.86%，93.22%］。顯然與表中的異常數據一致。

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

第三行和第十行數據：該部分數據雖然也存在比較嚴重的擁塞，但其業務并不屬于忙時高峰期，同時該小區中數據量極少。0.02對應的可能是由于中間設定的TA值較大，接收了很多干擾請求，從而導致性能降低。0.08對應的可能是信道完整率低，SDCCH信道過少，資源不足。

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

5　結語

本文通過對網絡KPI參數使用頻繁模式挖掘的方式，得到網絡的正常模式組合，利用正常模式組合作為正常模型進行異常檢測，最終得到異常組合。為了更加深入地分析異常組合中維度之間的關聯性，需要進一步對異常組合進行頻繁模式挖掘，得到最可能出現的異常原因，以此作為網絡優化的指導方案。同時使用模式匹配的方法能更加快速有效地進行在線異常檢測。

［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

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