鄧斌濤,徐勝超
(廣州華商學院數(shù)據科學學院,廣東 廣州 511300)
隨著云計算及大數(shù)據技術的發(fā)展,近年來因特網上的數(shù)據量急劇增加,基于機器學習方法的數(shù)據挖掘技術也隨之發(fā)展用來處理這些海量的大數(shù)據。聚類算法可以針對樣本或者個體的數(shù)據完成數(shù)據的分類,是數(shù)據挖掘中的一個大類分支。
聚類分析按照功能劃分包括分區(qū)聚類、層次聚類、基于網格的聚類等[1-4]。經典的聚類算法針對無標簽的數(shù)據可以很好地分類,但是針對大規(guī)模的海量數(shù)據處理效率低、耗時,已經不能滿足近年來實時數(shù)據平臺的要求。
用實現(xiàn)方式劃分,聚類算法又可以分為K最近鄰聚類算法KNN clustering、K均值聚類算法K-means clustering、K中心點聚類算法K-medoids clustering等。相關研究表明,K最近鄰聚類算法和K均值聚類算法在處理小規(guī)模的數(shù)據時效率比較高[5-6];K中心點聚類算法比較適合于大規(guī)模的數(shù)據。因此本文選擇K中心點聚類算法完成大數(shù)據處理。但K中心點聚類仍然存在可擴展性差、收斂速度慢、容易陷入局部最優(yōu)解的不足。
差分進化(Differential Evolution, DE)是一個簡單和高效的算法,它經常用來解決真實變量的最優(yōu)化問題,特別是在非線性問題最優(yōu)化問題上,它擁有強健的全局最優(yōu)能力,可以很好地提高聚類算法的精確度,是近年來數(shù)據挖掘領域比較有前景的算法。例如文獻[7]提出了基于差分進化的模糊聚類算法,解決了錯誤診斷問題。近年來有很多文獻對差分進化進行了改進,克服了差分進化算法的一些不足[8-10]。
針對上述問題,為了改善聚類算法的處理速度和分類精確度問題,本文首先結合差分進化算法和K中心點聚類算法;其次,采用動態(tài)雙子種群(Dynamic Gemini Population, DGP)模式來解決在維持種群密度的時候避免陷入局部最優(yōu)的問題;最后,本文以網絡入侵檢測這種大規(guī)模的大數(shù)據處理問題為案例,通過配置云計算下的Hapdoop平臺來并行處理基于動態(tài)雙子種群的差分進化的K中心點聚類算法DGP-DE-K-mediods。實驗結果表明,與現(xiàn)在常見的聚類算法比較起來,并行化的差分進化的K中心點聚類具有更好的分類精度和更少的運行時間。
差分進化算法是一個基于群智能的新型啟發(fā)式算法,它具有很強的全局最優(yōu)解的尋找能力[8]。
假設X為初始種群,N為種群的尺寸,Xi(t)(t=1,2,…,N)是當前種群條件下的進化種群序列。t為算法進化過程的迭代次數(shù)。種群的個體交叉操作的處理過程如公式(1)[11]:
Vi(t)=(vi1(t),vi2(t),…,viD(t))
=Xp1(t)+F(Xp2(t)-Xp3(t))
(1)
其中,Xp1(t)、Xp2(t)、Xp3(t)是隨機從當前的進化種群中選擇出來的3個不同的個體。F是一個規(guī)模參數(shù)。
D表示種群中個體的維度,這就是說交叉的個體是由D個不同的部分組成。進化的個體Xi(t)和Vi(t)是在當前的種群完成交叉操作來競爭的個體Ui(t)=(ui1(t),ui2(t),…,uiD(t))的時候產生,Ui(t)由D個不同的部分組成。
在競爭的個體Ui(t)的第j個組成部分可以按照公式(2)完成計算[9]。
(2)
其中,z是一個隨機的整數(shù),CR∈[0,1]是交叉操作的概率。針對種群的更新,可以按照下面的公式(3)來完成。
(3)
其中,f(Ui(t))是個體Ui(t)的適應度函數(shù),f(Xi(t))是個體Xi(t)的適應度函數(shù)。對于每個個體,Xi(t+1)要好于或持平于Xi(t),通過變異、交叉,選擇達到全部最優(yōu)。
K中心點聚類算法是一個常見的聚類數(shù)據挖掘算法[12]。很多聚類算法的模型都起源于該原始算法。它的運行流程如下:
步驟1 待處理的樣本數(shù)據被清洗和標準化;
步驟2 在所有數(shù)據集合中,選擇K個點作為各個聚類的中心點;
步驟3 計算其余所有樣本點到K個中心點的距離;
步驟4 用最小的距離來完成針對訓練樣本的分類;
步驟5 在每個類型目錄中,從每個樣本點中計算出絕對最小誤差距離,并將其設置為新的中心點;
步驟6 判斷該新的中心點是否與原始的中心點一致,如果它們不一致,返回到步驟3繼續(xù)執(zhí)行;
步驟7 達到循環(huán)結束條件后停止,輸出分類的結果。
在劃分聚類后,每個樣本點都需要與所有的分類目錄計算距離遠近并判斷,與此同時,也需要完成所有分類目錄的所有點的距離計算然后進行比較;也需要在聚類中的所有點完成一個實例操作。因此,該聚類算法的聚類時間是十分長的。為了提高計算速度,使用前面提到的基于差分進化技術的K中心點聚類算法可解決這個問題。下面是關于聚類算法的分類過程的數(shù)學描述:假設有n個d維的數(shù)據樣本x(x1,x2,…,xd),它的聚類特征CF通過公式(4)表示:
CF=〈n,LS,SS〉
(4)
關于LS和SS的計算公式如公式(5)和公式(6):
(5)
(6)
那么聚類算法的聚集中心x0通過公式(7)完成計算:
(7)
根據公式(7),從聚集的所有點到聚集的中心點的平均距離通過公式(8)進行計算:
(8)
除了聚集的所有點到聚集的中心點的平均距離外任何2點之間的平均距離按照公式(9)計算:
(9)
假設參數(shù)α和β分別描述在聚類中心的樣本點的屬性度和聚集度,則差分進化算法的適應度可以描述為公式(10):
(10)
其中,xid表示第i個樣本在第j個維度上的屬性,利用差分進化算法的規(guī)則來尋找函數(shù)g(x)的最大值:
G(Xb)=Max(g(x))
(11)
G(Xb)值的獲取是從差分進化算法尋找最優(yōu)解的過程中得到的,最后聚類算法的最終結果就完成了。
在DGP-DE-K-mediods聚類算法中,為了改善DE算法容易陷入局部最優(yōu)解的問題,本節(jié)還采用動態(tài)的雙子種群策略,這樣操作后種群的多樣性可以保持,同時種群的進化速度可以加快。
在每一代種群開始的時候,種群中的個體都按照其適應度值(fitness value)從小到大進行排序,在排序操作完成后,種群中具有比較高的個體數(shù)量的,就具有更加高的適應度函數(shù)值。在這個時候,種群個體的第一個λ將建立帶精英組合的局部最優(yōu)解,剩余的個體將組成普通的帶一般組合的局部最優(yōu)解。
在每一代種群的個體進化過程中,λ按照公式(12)進行更新:
λ=λmin+rand·(λmax-λmin)
(12)
其中,λmax和λmin分別表示參數(shù)λ的最大值和最小值;在精英的局部最優(yōu)解的每個個體中,使用公式(13)交叉策略來完成:
Vi,G=Xi,G+Fi,G·(Xr1,G-Xr2,G)+Fi,G·(Xr3,G-Xr4,G)
(13)
其中,F(xiàn)i,G表示針對其相應的個體Xi,G的規(guī)模參數(shù),r1、r2、r3、r4這些下標分別表示不同的隨機整數(shù)變量,并且它們與區(qū)間[0,1]的參數(shù)i不相等,N表示種群的尺寸。在局部種群中采用公式(14)的策略來完成個體交叉操作:
Vi,G=Xi,G+Fi,G·(λbest-Xi,G)+Fi,G·(Xr5,G-Xr6,G)
(14)
其中,參數(shù)λbest表示一個個體,它由局部種群中的精英個體來選擇產生。r5、r6這些下標分別表示不同的隨機整數(shù)變量,并且它們與區(qū)間[0,1]的參數(shù)i不相等。Xr5,G和Xr6,G分別表示適應度函數(shù)值,Xr5,G的值優(yōu)于Xr6,G。
本文的DGP-DE-K-mediods聚類算法的實現(xiàn)采用云計算平臺,這樣可以并行處理基于動態(tài)雙子種群的差分進化聚類算法,更進一步地提高大數(shù)據分類的速度與效率[13]。
Hadoop是一種開源并行大數(shù)據處理的總體支撐平臺,它由HDFS分布式文件系統(tǒng)、Hbase分布式數(shù)據庫、MapReduce并行模型等模塊組成[14-18]。Hadoop中最關鍵的是MapReduce。DGP-DE-K-mediods聚類算法中采用了6個步驟來表示MapReduce任務流Job stream,如圖1所示。
圖1 基于MapReduce的大數(shù)據聚類任務流
Map操作和Reduce操作是MapReduce并行編程模型的關鍵操作,所有的任務流必須經過這2個階段。每個任務流都表示為一系列的Map任務或者Reduce任務,DGP-DE-K-mediods聚類算法作為一個應用程序,其包括的所有子任務組成了一個有向無環(huán)圖,因特網上有很多關于Hadoop的文獻,由于篇幅原因這里不再贅述。這6個具體步驟如下[19]:
1)對輸入的大數(shù)據的樣本數(shù)據集文件進行設置與切片;
2)主節(jié)點(Master)調度從屬節(jié)點(Worker)執(zhí)行Map子任務;
3)從屬節(jié)點讀取輸入源片段;
4)從屬節(jié)點執(zhí)行Map子任務,并將臨時結果文件保存在本地;
5)主節(jié)點調度從節(jié)點執(zhí)行Reduce子任務,Reduce階段的從屬節(jié)點讀取Map子任務的輸出文件;
6)執(zhí)行Reduce子任務,將最后的結果保存到HDFS分布式文件系統(tǒng)中。
有了這6個步驟,K中心點聚類的編程人員就可以擺脫本身分布式計算的編程細節(jié),能夠在很短的時間內使用高級語言完成大規(guī)模的K中心點聚類。
本節(jié)主要描述DGP-DE-K-mediods聚類算法的實現(xiàn),采用MapReduce可以使數(shù)據分布式存儲和并行計算,MapReduce編程容易,程序員沒必要有MPI或者OpenMP等早期的并行編程的專業(yè)知識。
在使用Hadoop來完成大數(shù)據處理的時候,文件里的每行代碼都可以作為一個交易記錄來對待,每行代碼的入口都被一個空格字符分離開來。
在用戶提交了數(shù)據文件到HDFS中后,文件中的數(shù)據將被劃分為一系列的數(shù)據塊,這些數(shù)據塊的默認大小為64 MB。
在每次循環(huán)和迭代不停執(zhí)行Map操作和Reduce操作的過程中,每個Map節(jié)點都同時處理多個數(shù)據塊并輸出一個臨時的中間結果,該結果可能是差分進化算法等的局部最優(yōu)解的臨時解。Map操作的偽代碼如下:
Map_Class{
1. map(key,value){
2. Sort=0;
3.Dis=Max_Value;
4. for(inti=1;i 5. RecordsDis=dis(i, pointer); 6. if(RecordsDis 7. Sort=i; 8. minDis=RecordsDis; 9. } 10. } 11. produce<"Sort", value>; 12. } 13. } Reduce任務繼續(xù)處理從Map任務中輸出的中間數(shù)據,通過歸約和比較所有具有相同的關鍵值的key-value對,并最終獲得支持數(shù)據項集的完整結果數(shù)據。MapReduce采用主-從模式的結構編程模式,即Master-Slave結構模式。主控Master節(jié)點負責收集與匯總,從節(jié)點Slave負責完成臨時數(shù)據的聚類處理。Reduce任務的偽代碼如下: Reduce_Class{ 1. reduce(key,value){ 2.D1=0; 3. Sort=k; 4. Temps=new int[D1]; 5. for(inti=0;i 6. for(intD1=0;D1 7.D1++){ 8. Temps[i]=value[D1][i]; 9. } 10. } 11. for(intj=0;j 12. pointer+=Temps[j]; 13. } 14. produce 15. } 16. } 有了上面的代碼例程和MapReduce的專業(yè)知識,本文基于動態(tài)雙子種群的差分進化K中心點聚類DGP-DE-K-mediods就可以高效地、并行地、快速地處理和適應現(xiàn)代大數(shù)據技術容量海量增加的需求。 DGP-DE-K-mediods聚類算法的測試條件如下:6臺高檔PC機,Intel的i7 3.2 GHz主頻處理器、8 GB內存,所有節(jié)點之間的通信經過1 GB/s帶寬的雙網卡。采用Hadoop2.2版的平臺,Java環(huán)境的JDK版本為1.8.0。共有6臺物理主機,其中一臺配置Jobtracker,其他5臺配置Tasktracker,在局域網內的IP地址配置如表1所示。 表1 Hadoop云平臺的物理主機的配置 本節(jié)分析在差分進化算法和動態(tài)雙子種群模式中各個參數(shù)的設置。有經驗顯示,當規(guī)模因子F=0.6的時候差分進化算法運行比較好[11],所以設置規(guī)模因子F=0.6。有文獻研究顯示,交叉操作概率變量的選擇在設置到[0.3,0.9]之間性能比較優(yōu)異[9],所以本文將交叉概率變量設置為CR=0.5,規(guī)則更新參數(shù)λmax=0.5,λmin=0.3。種群大小N=30;種群大小主要反映算法中種群信息量的大小,進化次數(shù)值越大種群信息包含得越豐富,但是帶來的后果就是計算量變大,不利于求解。反之進化次數(shù)較小,使種群多樣性受到限制,不利于算法求得全局最優(yōu)解,甚至會導致搜索停滯。所以本文將進化次數(shù)的最大值設置為Tmax=1500。 為了驗證本文的DGP-DE-K-mediods聚類算法的高效性和高性能,使用大數(shù)據處理的案例數(shù)據,UCI機器學習的Iris數(shù)據庫http://archive.ics.uci.edu/ml/datasets/和人工的KDS1數(shù)據庫來做仿真實驗。UCI機器學習數(shù)據是由加州大學提供的,當前具有335個數(shù)據集[20]。把K-mediods[12]算法、DE-K-means[13]算法、PSO-K-means[18]算法和本文的DGP-DE-K-mediods算法作為性能比較對象。Iris和KDS1這2個數(shù)據集的參數(shù)設置如表2所示。 表2 聚類算法的數(shù)據設置 由于聚類算法的索引會影響到聚類算法的應用性,所以本文把聚類算法針對大數(shù)據的分類精確度作為性能指標之一,精確度的計算公式如下: (15) 其中,Ni表示數(shù)據集中類的所有樣本數(shù),Nia表示數(shù)據集中所有被正確分類后的數(shù)量,K表示聚類算法的種類數(shù),也是中心點的數(shù)量。通過上面搭建的Hadoop云平臺完成MapReduce編程與大數(shù)據處理,實驗后得到DGP-DE-K-mediods聚類算法的結果如表3所示。 表3 4個聚類算法的分類精確度結果比較 從表3的實驗結果可以看出,DGP-DE-K-mediods聚類算法的分類精確度比其他3個算法的分類精確度更高,最高分別可以在Iris數(shù)據集上達到89.5%和在KDS1數(shù)據集上達到94.2%。因此可以看出,本文的DGP-DE-K-mediods可以獲得分類算法的全局最優(yōu)性能,在智能優(yōu)化的過程中離最優(yōu)解最接近。 3.4.1 網絡入侵檢測環(huán)境設置 為了更好地體現(xiàn)DGP-DE-K-mediods聚類算法大數(shù)據應用的優(yōu)勢,本節(jié)選擇網絡入侵檢測這種大數(shù)據應用,網絡入侵檢測是網絡安全中的一種主動防御行為,它主要靠通過發(fā)送TCP RST消息包來與入侵行為進行判斷[21-23]。基于中心點聚類的K-mediods方法的網絡入侵檢測系統(tǒng)的處理流程如圖2所示。 圖2 基于K-mediods的網絡入侵檢測流程 K-mediods網絡入侵檢測覆蓋的數(shù)據源包括許多類型:日志信息、異常的目錄與文件變化、網絡信息、程序執(zhí)行異常行為、主機的入侵行為等。本文的DGP-DE-K-mediods聚類分析方法可以很好地處理這些網絡入侵檢測的數(shù)據分析[23],網絡攻擊的數(shù)據包設置如表4所示,軟硬件測試環(huán)境還是按照表1的Hadoop集群的配置方式。 表4 K-mediods網絡入侵檢測的分類測試數(shù)據 3.4.2 精確度比較 公式(16)很好地體現(xiàn)了網絡入侵檢測系統(tǒng)的錯誤檢測率(Error Detection Rate, EDR)[12]。 (16) 其中,MP表示丟棄的攻擊包的數(shù)量,DP表示網絡入侵中的所有攻擊包的數(shù)量。本文的DGP-DE-K-mediods聚類算法完成網絡入侵檢測的結果如表5所示。 表5 網絡入侵檢測結果性能比較 從表5的結果可以看出,相對于K-mediods的網絡入侵檢測,基于DGP-DE-K-mediods的網絡入侵檢測具有更高的檢測精度,這是因為K中心點算法能夠聚集到入侵檢測模型的結構,當數(shù)據規(guī)則擴大的時候,這樣就克服了早期的入侵檢測模型過于依賴于檢測規(guī)則的不足,同時,K中心點聚類算法可以檢測和處理新型的攻擊行為。DGP-DE-K-mediods基于動態(tài)雙子種群的差分進化方法可以改善局部最優(yōu)解的問題,在種群多樣化更新的時候可以更好地改進分類的精度。 3.4.3 運行時間分析 K-mediods的入侵檢測和基于云計算的并行DGP-DE-K-mediods聚類算法的運行時間分析如表6所示。從實驗結果可以看出,當數(shù)據容量比較小的時候,DGP-DE-K-mediods聚類算法運行時間的減少還不明顯,甚至運行時間還多于K-mediods的網絡入侵檢測算法。 表6 DGP-DE-K-mediods聚類算法執(zhí)行時間 但是隨著它處理的數(shù)量容量增加,DGP-DE-K-mediods聚類算法顯示出它明顯的速度優(yōu)勢。特別是在數(shù)據容量規(guī)模特別大的時候,DGP-DE-K-mediods聚類算法速度提高特別快,這表示大數(shù)據聚類可以通過Hadoop云計算并行處理很好地提高效率。 表5和表6的結果也表明,當處理大數(shù)據聚類應用的時候,需要處理數(shù)據的容量將十分影響整體計算速度,通過云計算、智能算法的優(yōu)化都可以改進數(shù)據挖掘的速度與效果。 本文提出了云環(huán)境下基于動態(tài)雙子種群的差分進化K中心點聚類算法DGP-DE-K-mediods,利用典型的大數(shù)據分類的案例數(shù)據和網絡入侵檢測這種大數(shù)據應用來仿真算法的效果。實驗結果表明,DGP-DE-K-mediods算法比K-mediods聚類算法有更好的分類精度和更少的運行時間。盡管這樣,Hadoop是一個比較低版本的開源的云平臺,下一步的工作是將DGP-DE-K-mediods算法移植到更加高級別的云計算平臺,進一步提高大數(shù)據聚類算法的速度與效率。3 仿真實驗與性能分析
3.1 仿真軟硬件環(huán)境
3.2 參數(shù)設置與數(shù)據選取
3.3 聚類算法精確度分析
3.4 網絡入侵檢測性能分析
4 結束語