Spark平臺下綜合屬性權(quán)重離群點(diǎn)挖掘算法研究*

馬 晶 劉建華

（1.西安郵電大學(xué) 西安 710061）（2.西安郵電大學(xué)信息中心 西安 710121）

1 引言

現(xiàn)有的入侵檢測系統(tǒng)存在許多不足［1］，當(dāng)前面臨的主要問題：IDS主動防御能力不足、高速網(wǎng)絡(luò)環(huán)境的性能差［2］。將數(shù)據(jù)挖掘中離群點(diǎn)檢測方法運(yùn)用到入侵檢測中可一定程度改善現(xiàn)狀。離群點(diǎn)檢測是用來確定小部分?jǐn)?shù)據(jù)對象與剩余的大部分?jǐn)?shù)據(jù)明顯不同或者不一致的問題［3］。離群點(diǎn)檢測除了可應(yīng)用在入侵檢測系統(tǒng)中外，也被廣泛應(yīng)用于醫(yī)療處理、信用卡詐騙、保險詐騙和內(nèi)幕交易［4］、工業(yè)損毀檢測、圖像處理、傳感器/視頻網(wǎng)絡(luò)監(jiān)視［5］。

目前，很多離群點(diǎn)挖掘算法被應(yīng)用于入侵檢測，其中基于K-means、DBSCAN的離群點(diǎn)挖掘算法中聚類個數(shù)k、閾值的選取和基于Apriori的離群點(diǎn)挖掘算法k頻繁項(xiàng)集的選取直接影響到離群點(diǎn)的產(chǎn)生，需要經(jīng)過大量的實(shí)驗(yàn)找出合適的k值和閾值；傳統(tǒng)的LOF算法［6］未能考慮數(shù)據(jù)對象屬性的權(quán)重問題；主觀賦權(quán)法在根據(jù)屬性本身含義確定權(quán)重方面具有優(yōu)勢，但客觀性較差；而客觀賦權(quán)法在不考慮屬性實(shí)際含義的情況下，確定權(quán)重具有優(yōu)勢，但不能體現(xiàn)決策者對不同屬性的重視程度，有時會出現(xiàn)確定的權(quán)重與屬性的實(shí)際重要程度相悖的情況；文獻(xiàn)［7］提出基于的HLOF算法只考慮屬性的客觀權(quán)值，未考慮其主觀權(quán)值，不能有效地挖掘出離群點(diǎn)。

然而，隨著網(wǎng)絡(luò)數(shù)據(jù)的爆炸式增長，使用一個CPU節(jié)點(diǎn)來進(jìn)行計(jì)算，很難勝任對這些海量數(shù)據(jù)的分析任務(wù)。當(dāng)今行之有效的解決方案則是在云計(jì)算的分布式方法的幫助下增強(qiáng)計(jì)算資源的能力，利用通過網(wǎng)絡(luò)連接的多個節(jié)點(diǎn)來共同承擔(dān)對計(jì)算資源需求量較高的復(fù)雜計(jì)算［2］。目前Hadoop和Spark是兩個主流的分布式平臺，相比 MapReduce［8］，Spark速度快，開發(fā)簡單，并且能同時兼顧批處理和實(shí)時數(shù)據(jù)分析［9］，其中Spark streaming是Spark計(jì)算框架中來做實(shí)時流處理的模塊。因?yàn)槿肭謾z測系統(tǒng)的實(shí)時性要求，所以，選擇Spark平臺來做算法的并行化。目前在國內(nèi)外，已經(jīng)有很多公司在實(shí)際生產(chǎn)環(huán)境中廣泛使用Spark，比如國外的谷歌、亞馬遜，易貝、雅虎等公司和國內(nèi)的淘寶、百度、華為、優(yōu)酷、土豆等公司［10］。因此，本文提出綜合權(quán)重離群點(diǎn)挖掘（Comprehensive attribute weight outliermining，CAWOM）算法，并將其在Spark云計(jì)算平臺對其并行化來解決以上問題。

2 CAWOM算法

CAWOM算法首先根據(jù)層次分析法和均方差賦權(quán)法計(jì)算出數(shù)據(jù)對象屬性的綜合權(quán)重，得到數(shù)據(jù)的屬性加權(quán)距離，進(jìn)而求出數(shù)據(jù)對象的偏離系數(shù)和數(shù)據(jù)集的平均偏離系數(shù)，然后對二者進(jìn)行比較，最終找出離群點(diǎn)。

做如下規(guī)定，數(shù)據(jù)集D=｛X1，X2，X3，…，Xm｝表示m個待檢測的數(shù)據(jù)，其中每個對象Xi由k個屬性構(gòu)成，可表示為 Xi=（Xi1，Xi2，Xi3，…，Xik），每個對象 Xi各個屬性的綜合權(quán)重為（CW1，CW2，CW3，…，CWk）。

2.1 綜合權(quán)重

為了能夠兼顧每個獨(dú)立網(wǎng)絡(luò)環(huán)境的特殊性，使用綜合權(quán)值法來對屬性賦權(quán)。利用AHP和均方差法計(jì)算出各屬性的主觀權(quán)值和客觀權(quán)值，然后采用“乘法”集成法構(gòu)造綜合權(quán)值，進(jìn)而能夠綜合、全面地考慮屬性對離群系數(shù)的影響。

AHP計(jì)算屬性主觀權(quán)重：層次分析模型見圖1，其中，屬性權(quán)重為目標(biāo)層，n種攻擊方式為準(zhǔn)則層，k個屬性為方案層，通過各層次單排序權(quán)向量計(jì)算層次總排序，得出各個屬性的權(quán)值。具體步驟：根據(jù)準(zhǔn)則層中各個攻擊方式的發(fā)生頻率構(gòu)造判斷（成對比較）矩陣A，然后計(jì)算A的最大特征值λmax1及其相對應(yīng)的歸一化特征向量ω（2），λmax用來計(jì)算A的一致性指標(biāo)（n為準(zhǔn)則層因素個數(shù)）；將準(zhǔn)則層中的n個因素作為方案層各個屬性的對比標(biāo)準(zhǔn)，構(gòu)造n個k×k成對比較矩陣B，計(jì)算每個矩陣的最大特征值λi及其歸一化特征向量ωi，得 出 其 層 次 單 排 序 權(quán) 向 量 ω（3），，比較矩陣的一致性的判斷與準(zhǔn)則層相同；根據(jù)層次單排序計(jì)算層次總排序，得出 k個屬性的權(quán)值。

均方差法計(jì)算屬性客觀權(quán)重：計(jì)算各個屬性集（X1i，X2i，X3i，…，Xmi），0＜i≤k的標(biāo)準(zhǔn)差si，屬性的客觀權(quán)重公式：

采用“乘法”集成法構(gòu)造屬性的綜合權(quán)值。綜合權(quán)值公式：

2.2 偏離系數(shù)

根據(jù)屬性的綜合權(quán)值構(gòu)造數(shù)據(jù)對象Xp，Xq的加權(quán)屬性距離公式為

數(shù)據(jù)對象Xp的加權(quán)屬性距離公式：

偏離系數(shù)（Outlier Factor，OF），OF（Xi）計(jì)算公式：

平均偏離系數(shù)AOF（D）計(jì)算公式：

2.3 算法執(zhí)行過程

根據(jù)綜合權(quán)重公式，得到各個屬性的綜合權(quán)值，然后計(jì)算數(shù)據(jù)集D中每個數(shù)據(jù)對象Xi的偏離系數(shù)OF（Xi）和平均偏離系數(shù)AOF（D），若OF（Xi）＞AOF（D），則Xi為數(shù)據(jù)集D的離群數(shù)據(jù)，即離群點(diǎn)。具體算法如下：

輸入：對象集D=｛X1，X2，X3，…，Xm｝為待挖掘的數(shù)據(jù)集，屬性重要程度參數(shù)（）。

輸出：對象集中的離群點(diǎn)。

算法過程如下：

根據(jù)AHP算法確定每個屬性的主觀權(quán)重ai；

根據(jù)式（1）計(jì)算屬性的客觀權(quán)重OWi；

根據(jù)式（2）計(jì)算綜合權(quán)重CWi；

根據(jù)式（4）計(jì)算每個對象的加權(quán)屬性距離N d（Xi，CW）；

根據(jù)式（5）計(jì)算每個對象的偏離系數(shù)OF（Xi）；

根據(jù)式（6）計(jì)算數(shù)據(jù)集D的平均偏離系數(shù)AOF（D），將OF（Xi）＞AOF（D）的對象作為離群點(diǎn)輸出。

3 Spark Stream ing

Spark是一套開源的、基于內(nèi)存的，可運(yùn)行在分布式集群上的并行計(jì)算框架［11～12］。Spark的一切都基于Spark的輸入—RDD。RDD可由外部文件存儲系統(tǒng)HDFS、HBase等中的數(shù)據(jù)集創(chuàng)建。Spark平臺擴(kuò)展了5個主要的函數(shù)庫，Spark SQL、Spark Streaming、MLlib、GraphX和SparkR。

Spark Streaming［13］屬于核心 Spark API的擴(kuò)展，支持實(shí)時數(shù)據(jù)流的可擴(kuò)展、高吞吐、容錯的流處理。DStream（離散數(shù)據(jù)流）是Spark Streaming的基本抽象，由一組時間序列上連續(xù)的RDD來表示，可看作一個RDDS序列。Spark Streaming是將實(shí)時數(shù)據(jù)流根據(jù)固定的時間間隔劃分成DStream存儲在RDDs中，然后從DStream的轉(zhuǎn)換操作生成對RDDs的轉(zhuǎn)換操作，執(zhí)行產(chǎn)生的中間結(jié)果可以存儲在內(nèi)存中以進(jìn)行迭代操作。圖2是基于DStream實(shí)現(xiàn)的Spark Streaming模型。

圖2 基于DStream實(shí)現(xiàn)的Spark Streaming模型

4 Spark平臺并行化CAWOM算法

4.1 S-CAWOM算法

S-CAWOM算法是CAWOM算法在Spark平臺的實(shí)現(xiàn)。算法首先將數(shù)據(jù)按照1s的時間間隔分配到各個子節(jié)點(diǎn)，在各個子節(jié)點(diǎn)上根據(jù)CAWOM算法計(jì)算對象的離群系數(shù)OF（Xi）及數(shù)據(jù)集Di的平均離群系數(shù)AOF（Di）；將各個子節(jié)點(diǎn)的離群點(diǎn)匯總，比較 OF（Xi）與數(shù)據(jù)集D的平均偏離系數(shù)AOF（D）（AOF（D）為各個子節(jié)點(diǎn)的AOF（Di）的平均值），找出離群點(diǎn)。圖3是Spark平臺下算法的并行化流程圖。

圖3 并行算法流程圖

S-CAWOM算法的執(zhí)行過程：

1）集群從分布式文件系統(tǒng)HDFS上讀取數(shù)據(jù)，以1秒為時間間隔，生成DStream；

2）通過flatMap（）方法將數(shù)據(jù)格式化為向量；

3）通過map（）方法將根據(jù)CAWOM算法計(jì)算出每個節(jié)點(diǎn)的OF（Xi）與之前節(jié)點(diǎn)向量連接組成新的向量；

4）通過reduce（）方法計(jì)算各個集群的離群系數(shù) AOFi，然后通過filter（）、union（）方法得出初始離群點(diǎn)集O'；

5）通過reduce（）方法得到平均離群系數(shù)AOF，然后通過filter（）方法得出離群點(diǎn)集O。

4.2 算法偽代碼

Input：存放數(shù)據(jù)對象集地址HDFS_path，Spark集群地址master_address，屬性重要程度值向量P（pi），0＜i≤k，其中k為屬性維數(shù)。

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)環(huán)境

在2臺主機(jī)上安裝Red Hat Linux7.2操作系統(tǒng)，在每臺主機(jī)上分別創(chuàng)建3臺虛擬機(jī)。將主機(jī)1作為Master節(jié)點(diǎn)，主機(jī)2和其余6個虛擬機(jī)作為Slave節(jié)點(diǎn)，每個節(jié)點(diǎn)的配置信息均為Internet Core i7 2.7GHz CPU，2GB內(nèi)存，50GB硬盤。采用CDH平臺集成搭建Spark集群。

實(shí)驗(yàn)數(shù)據(jù)采用KDD CUP99數(shù)據(jù)集，主要包含DoS、Probe、U2R和R2L 4種攻擊。數(shù)據(jù)集為CVS格式，大小約為708MB，包含490萬個連接，每個連接占一行，包含38個屬性特征［14］。其中的類別型特征屬性采用One-hot編碼處理，Protocal-type的處理如表1，其余的類別型屬性參考Protocal-type的處理。對于連續(xù)型屬性參考文獻(xiàn)［15］中的Imp-Chi2算法處理。

表1 Protecal-type處理表

5.2 實(shí)驗(yàn)方法及結(jié)果分析

在計(jì)算主觀權(quán)重時，選取KDD CUP99 10%數(shù)據(jù)集中的攻擊比例作為AHP模型準(zhǔn)則層的參考。在spark平臺將存儲在分布式文件系統(tǒng)HDFS上的數(shù)據(jù)集按照S-CAWOM算法進(jìn)行離群檢測，找出其離群點(diǎn)集，算法進(jìn)行性能評價時，選取檢測率、誤檢率和算法執(zhí)行時間3個性能指標(biāo)與文獻(xiàn)［16］中的ACPO、EOS算法進(jìn)行比較，表2為檢測性能對比表。

表2 檢測率對比表

由表2可以看出，S-CAWOM算法的檢測效率高于ACPO和EOS算法，但誤檢率稍高于ACPO和EOS算法。

為了驗(yàn)證算法的執(zhí)行效率，在KDD CUP99數(shù)據(jù)集抽取10000、20000、50000、100000條鏈接進(jìn)行驗(yàn)證，比較三種算法的算法運(yùn)行時間。圖4為三種算法分別在10000、20000、50000、100000條鏈接的運(yùn)行時間折線圖。

圖4 算法運(yùn)行時間

根據(jù)圖4可發(fā)現(xiàn)，在當(dāng)數(shù)據(jù)集在變化時，S-CAWOM算法的運(yùn)行時間都是最少的。從整個趨勢來看，當(dāng)數(shù)據(jù)集較小時，各算法的運(yùn)行時間相差較小，當(dāng)數(shù)據(jù)集逐漸增大時，各算法執(zhí)行時間增長較快，效率減小。

6 結(jié)語

本文研究Spark平臺下綜合屬性權(quán)重離群點(diǎn)挖掘的問題，由于很多研究都未考慮屬性的綜合權(quán)重，只是從客觀屬性單方面進(jìn)行研究，使得離群點(diǎn)的檢測效率不高。本文在Spark Streaming框架的基礎(chǔ)上，提出了綜合屬性權(quán)重離群點(diǎn)挖掘算法S-CAWOM。實(shí)驗(yàn)證明，該算法的執(zhí)行效率高，檢測性能良好。