齊 文，朱曦源，宋 杰

1(遼東學(xué)院 工程技術(shù)學(xué)院，遼寧 丹東 118001) 2(東北大學(xué) 軟件學(xué)院，沈陽 110819)

1 引 言

隨著信息化建設(shè)，互聯(lián)網(wǎng)行業(yè)的發(fā)展，各種信息設(shè)備在運行和通信中，會產(chǎn)生大量的網(wǎng)絡(luò)日志數(shù)據(jù).日志數(shù)據(jù)的來源很多，如網(wǎng)絡(luò)、文件和計算服務(wù)器，網(wǎng)絡(luò)日志數(shù)據(jù)對于商業(yè)規(guī)則、統(tǒng)計分析、網(wǎng)絡(luò)廣告、推薦系統(tǒng)等都很有用[1].因此，能夠合理處理并分析體量龐大的網(wǎng)絡(luò)日志數(shù)據(jù)是有實際意義的.

當前的研究提出了許多使用Hadoop[2]和MapReduce的網(wǎng)絡(luò)日志分析聚類優(yōu)化算法[3].然而這種使用MapReduce的網(wǎng)絡(luò)日志處理方法都存在計算速度慢，磁盤I/O開銷大，尤其在實時處理在線式的網(wǎng)絡(luò)日志數(shù)據(jù)方面性能較低.也有研究提出了使用Spark的聚類處理方法[4]，但是這些方法，而既不提供數(shù)據(jù)分析，也不提供對RDD內(nèi)容的查詢機制.這種缺乏對捕獲、存儲和查詢出處的支持，是在數(shù)據(jù)處理過程中和之后充分利用詳細分析的瓶頸.以及存在諸如沒有去除冗余數(shù)據(jù)，以及沒有考慮以最小的空間要求實現(xiàn)高精度的預(yù)處理的問題，以及輸出不適合對數(shù)據(jù)的進一步處理，比如聚類或是分類等.針對上述問題，網(wǎng)絡(luò)日志的聚類算法可以進一步改進.

本文提出了一種網(wǎng)絡(luò)日志處理方法，實現(xiàn)了高精度的預(yù)處理以及實現(xiàn)了數(shù)據(jù)的高效進一步聚類處理.該方法以提高聚類性能為目標，以最少的時間處理和分析網(wǎng)絡(luò)日志，并能獲得較高的準確率和靈敏度.本文提出的特征轉(zhuǎn)移概率是指特征向量向一特定聚類中心轉(zhuǎn)移的概率，基于此，分布式并行處理方法能夠分析完整的網(wǎng)絡(luò)日志數(shù)據(jù)集并提取有用的信息，在集群上進行并行處理完成聚類算法.

本文提出的基于特征轉(zhuǎn)移概率的聚類方法首先要對網(wǎng)絡(luò)日志數(shù)據(jù)集進行數(shù)據(jù)預(yù)處理，生成特征向量再用分布式優(yōu)化的K-means聚類方法基于特征轉(zhuǎn)移概率進行聚類，為了獲得更好的并行效率和速度，本文采用了Apache Spark[5]以及彈性分布式數(shù)據(jù)集.實驗與其他優(yōu)化的聚類算法進行比較，本文分布式改進的網(wǎng)絡(luò)日志處理技術(shù)實際實驗中選擇的特征能夠在高準度下提高聚類速度，保持了與現(xiàn)有的聚類方法接近的收斂靈敏度和準確度，并將執(zhí)行時間降低到了75.97%.

本文第2節(jié)介紹了一些關(guān)于聚類算法的預(yù)備知識.第3節(jié)介紹了預(yù)處理的方法，并進行了舉例演示.第4節(jié)介紹了特征轉(zhuǎn)移概率與相關(guān)的公式以及本文提出的基于特征轉(zhuǎn)移概率的算法實現(xiàn).第5節(jié)介紹了實驗，實驗測試在不同約束條件如聚類精度和數(shù)據(jù)量規(guī)模下進行.

2 預(yù)備知識

數(shù)據(jù)聚類的目的是確定數(shù)據(jù)值的分組或發(fā)現(xiàn)數(shù)據(jù)中的模式.聚類算法根據(jù)一些相似性度量將n個對象分成k個組.相似性度量可以從維度或模式集合生成.一個理想的集群將n個數(shù)據(jù)的一部分放入一個與其他組隔離的緊湊組中.聚類通常被認為是一項無監(jiān)督的任務(wù)，因為沒有提供具有特定標簽的訓(xùn)練.聚類過程包括4個步驟:特征提取、模式接近度確定(即建立對之間的距離值)、聚類(即分組)和抽象(例如，從聚類中選擇一個小的子樣本統(tǒng)計表示完整的數(shù)據(jù)集).

K-means聚類算法[6]是最經(jīng)典的聚類算法之一，該算法以距離作為評價的相似度指數(shù)，即兩個對象之間的距離越近，相似度越大.對于給定的樣本集，計算任意兩個樣本之間的距離，根據(jù)樣本之間的距離將樣本集劃分為k個聚類，它實現(xiàn)起來比較簡單，可以擴展到大型數(shù)據(jù)集，并且保證收斂性.實現(xiàn)的算法如算法1所示.

算法1.K-means聚類算法

步驟1.隨機選擇k個集群中心點.

步驟2.聚類分配.在這一步，將數(shù)據(jù)集中的每個數(shù)據(jù)點分配給一個中心點，選擇與數(shù)據(jù)點最接近的中心點.

步驟3.中心點移動.對于每個中心點，計算分配給每個中心點的所有數(shù)據(jù)點的平均值.這個計算出來的平均值就是這個特定中心點的新值.

步驟4.計算每個中心點從之前的值中移動的距離平方的總和，重復(fù)步驟2和3，直到這個值不小于或等于閾值(通常是0.01)或迭代次數(shù)達到指定的最大迭代次數(shù).

然而，傳統(tǒng)的串行K-means聚類算法還是難以高效、準確地對海量運行狀態(tài)監(jiān)測進行聚類分析.接下來本文將討論這個算法在不同平臺上的實現(xiàn)細節(jié)，以深入了解這種迭代算法如何被修改以適應(yīng)不同的數(shù)據(jù)集.

2.1 在MapReduce上的K-means分析

MapReduce的工作原理是將處理過程分成兩個階段:map階段和reduce階段.每個階段都有鍵值對作為輸入和輸出.輸入的網(wǎng)絡(luò)日志文件通常駐留在Hadoop分布式文件系統(tǒng)(HDFS)中，Hadoop會提供一個包含要讀取的文件的路徑，讀取這個目錄中的所有網(wǎng)絡(luò)日志.然后，它將這些網(wǎng)絡(luò)日志分成一個或多個塊.一個MapReduce作業(yè)無非是一個應(yīng)用于數(shù)據(jù)集的程序，由若干個任務(wù)組成的.在完成第一個map任務(wù)后，各節(jié)點仍然各自再執(zhí)行幾個map任務(wù).但是他們也開始將一個map任務(wù)的中間輸出交換到另一個reducers需要的地方，shuffling是將數(shù)據(jù)從mappers轉(zhuǎn)移到reducers的過程，從而使得reducers獲得輸入，不同子集分區(qū)的鍵空間被分配給每個reduce節(jié)點;這些子集分區(qū)是reduce任務(wù)的輸入.它決定了映射階段輸出的一個鍵值對，將被送到哪個reducer中去.partitioner類可以找到一個給定的鍵值對將被送到哪個分區(qū).默認的partitioner會對鍵的哈希值進行操作，并根據(jù)這個結(jié)果分配分區(qū).單個節(jié)點上的中間鍵集合在交付給Reducer之前，會被Hadoop自動排序.當排序后的輸入數(shù)據(jù)中的下一個鍵與前一個鍵不同時，它就會啟動新的reduce任務(wù).Hadoop框架對排序順序中的每一個唯一的鍵都會調(diào)用一次Reduce().Reduce可以遍歷與該鍵相關(guān)的值，并產(chǎn)生零個或多個輸出值.輸出值需要與輸入值的類型相同，輸入鍵也不需要改變.通過調(diào)用到方法OutputCollector.collect(Object，Object)來收集輸出對.Reducer還接收OutputCollector和Reporter對象作為參數(shù)，其使用方式與map()方法相同.RecordWriter將mapreduce作業(yè)的輸出鍵值對寫入一個輸出文件.RecordWriter實現(xiàn)將作業(yè)輸出寫到HDFS中.然后，Reducers寫入的輸出文件存在HDFS中.MapReduce的網(wǎng)絡(luò)日志處理方法結(jié)束.這里Hadoop的特點是把計算移到數(shù)據(jù)上，而不是把數(shù)據(jù)移到計算上，數(shù)據(jù)以塊的方式存儲在集群中的多個節(jié)點上，從而相對于傳統(tǒng)的串行處理方法，這種基于Hadoop和MapReduce的分布式并行處理方法，取得了不錯的效果，并且成功地處理了大規(guī)模網(wǎng)絡(luò)日志數(shù)據(jù)集.

對于K-means聚類等迭代算法，MapReduce并不是一個理想的選擇.基本上，映射器從磁盤上讀取數(shù)據(jù)和中心點.磁盤上的數(shù)據(jù)和中心點.然后這些映射器將數(shù)據(jù)實例分配給集群.一旦每個映射器完成了他們的操作，還原器通過計算每個簇中存在的數(shù)據(jù)點的平均數(shù)來計算新的中心點.每個集群中存在的數(shù)據(jù)點的平均值.現(xiàn)在，這些新的中心點被寫入到磁盤上.然后，這些中心點由映射器在下一次迭代中讀取，整個過程不斷重復(fù)，直到算法結(jié)束.整個過程不斷重復(fù)，直到算法收斂.算法2給出了在MapReduce上的K-means的偽代碼.算法3和算法4給出了K-means聚類的映射器和化簡器函數(shù)的偽代碼.

算法2.在MapReduce上的K-means

輸入:數(shù)據(jù)點D，聚類數(shù)k.

步驟1.隨機初始化k個聚類中心.

步驟2.將D中的每個數(shù)據(jù)點與最近的聚類中心聯(lián)系起來，把數(shù)據(jù)點分成k個集群.

步驟3.重新計算聚類中心的位置.重復(fù)第2步和第3步，直到數(shù)據(jù)點的成員資格不再有變化.

輸出:是集群成員的數(shù)據(jù)點.

算法3.Map映射器.

輸入:數(shù)據(jù)點D，聚類數(shù)k和聚類中心.

步驟1.對于每個數(shù)據(jù)點d∈D.

步驟2.將d分配給最接近的聚類中心.

輸出:帶有相關(guān)數(shù)據(jù)點的聚類中心.

算法4.Reduce化簡器.

輸入:帶有相關(guān)數(shù)據(jù)點的聚類中心.

步驟1.計算集群中數(shù)據(jù)點的平均值計算新的聚類中心.

步驟2.將全局中心寫到磁盤上.

輸出:新的聚類中心.

2.2 在Spark上的K-means分析

與基于Map-Reduce的Hadoop模型相比，Apache Spark具有很多優(yōu)勢.Spark提供的內(nèi)存計算在大規(guī)模分析中非常有用.內(nèi)存計算主要有兩個優(yōu)勢.第一，由于數(shù)據(jù)存儲在內(nèi)存中，所以迭代作業(yè)不需要重復(fù)的磁盤訪問.第二，交互式作業(yè)不需要每次查詢都訪問磁盤，相反，Spark可以用來將數(shù)據(jù)庫存儲在內(nèi)存中并頻繁查詢.

由于日志數(shù)據(jù)是非結(jié)構(gòu)化的，本文從每一行中解析并創(chuàng)建一個結(jié)構(gòu)，在分析時，這個結(jié)構(gòu)又會成為每一行.之后創(chuàng)建Spark Context、SQL Context、DataFrame.然后，Spark可以從文本文件中加載數(shù)據(jù)作為RDD，然后它可以處理這些數(shù)據(jù).給定一個日志行的RDD，使用map函數(shù)將每一行轉(zhuǎn)化為Apache Access Log對象.Apache Access Log RDD會被緩存在內(nèi)存中，因為會對其進行多次轉(zhuǎn)換和操作.通過映射變換提取出內(nèi)容大小，然后調(diào)用不同的操作(reduce、count、min和max)來輸出各種統(tǒng)計數(shù)據(jù).

Spark上的K-means實現(xiàn)與在MapReduce上的K-means實現(xiàn)類似.節(jié)中描述的基于MapReduce的K-means.全局中心點不是寫在磁盤上，而是寫在內(nèi)存中.這樣可以加快處理速度并減少 磁盤I/O的開銷.此外，數(shù)據(jù)將被加載到系統(tǒng)內(nèi)存中，以提供更快的訪問.以便提供更快的訪問.CPU上的K-均值聚類涉及多線程每個線程將一個數(shù)據(jù)向量與一個中心點聯(lián)系起來，最后中心點被重新計算，用于下一次迭代.最后為下一次迭代重新計算.

Spark允許本文對大量的輸入數(shù)據(jù)進行流處理.由于Spark基于內(nèi)存計算的良好性能，降低了時間要求，并保證了一定的準確度.

由于Spark對于迭代計算的性能良好，故本文選擇Spark的K-means為基礎(chǔ)進行優(yōu)化，提出了基于特征轉(zhuǎn)移概率的K-means聚類算法.具體實現(xiàn)在下節(jié)開始討論.

3 預(yù)處理與聚類特征

一些公開的網(wǎng)絡(luò)服務(wù)器日志數(shù)據(jù)集，如Calgary-HTTP，ClarkNet-HTTP，NASA-HTTP和 Saskatchewan-HTTP的數(shù)據(jù)集都是優(yōu)質(zhì)的數(shù)據(jù)集.本文通過這些數(shù)據(jù)集來熟悉處理Web服務(wù)器日志.由于這些網(wǎng)絡(luò)日志數(shù)據(jù)具有非結(jié)構(gòu)化數(shù)據(jù)的特點，含有大量的噪聲數(shù)據(jù)，必須消除這些不相關(guān)的數(shù)據(jù)，所以需要對網(wǎng)絡(luò)日志進行預(yù)處理.表1描述了一個樣本的entry headers.

表1 對網(wǎng)絡(luò)日志條目頭的簡要描述Table 1 Brief description of the weblog entry headers

預(yù)處理使用了整個網(wǎng)絡(luò)日志數(shù)據(jù)集的解析技術(shù)[7].在本次實驗，首先將網(wǎng)絡(luò)日志數(shù)據(jù)按照以下方式進行拆分到其屬性.特征選擇作為一個預(yù)處理步驟，需要通過消除冗余和不相關(guān)的特征，只選取信息豐富和簡潔的特征來增強分類過程.在應(yīng)用這一原則后，分類過程中由于過度擬合而導(dǎo)致的問題就被消除了.為了加強這一任務(wù)，通常采用特征選擇算法來選擇信息量最大的屬性，從而減少特征空間.

對于較大的數(shù)據(jù)集，有多種技術(shù)可以確保計算、存儲和數(shù)據(jù)工作流程得到優(yōu)化，并且可以實現(xiàn)潛在的更大規(guī)模建模的可擴展性.這些計算擴展技術(shù)如MapReduce，它將數(shù)據(jù)分割為單元進行并行處理.然后，被處理的單元被重新映射回更大的數(shù)據(jù)集，以便進一步分析或處理.Apache Hadoop計算平臺旨在通過提供包括大量存儲、分布式文件系統(tǒng)和先進的處理能力在內(nèi)的高性能計算環(huán)境來利用MapReduce的概念.Spark是一個開源的HPC框架的實現(xiàn)，在需要進行大數(shù)據(jù)分析時，對R、Python和Java的使用進行了優(yōu)化.Spark使用更復(fù)雜的分布式聚類模型，數(shù)據(jù)被一次性加載到內(nèi)存中，可以對其進行大量操作.當Spark應(yīng)用程序提交時，在主節(jié)點上創(chuàng)建SparkContext對象，從HDFS讀取數(shù)據(jù)以創(chuàng)建RDD對象.它從HDFS讀取數(shù)據(jù)以創(chuàng)建RDD對象，并向集群資源管理器請求資源 向集群資源管理器請求資源.集群資源管理器將資源分配給每個工作節(jié)點的一個或多個執(zhí)行器進程.每個工作節(jié)點有一個或多個執(zhí)行器進程，每個工作節(jié)點向集群資源管理器報告資源使用和任務(wù)運行狀態(tài).每個工作節(jié)點使用心跳機制來向集群資源管理器報告資源使用情況和任務(wù)運行狀態(tài).SparkContext對象根據(jù)多個RDD之間的依賴關(guān)系構(gòu)建一個有向無環(huán)圖(DAG)，并將該DAG提交給DAG調(diào)度器以確定多個RDD之間的依賴關(guān)系.

提交給DAG調(diào)度器 DAG調(diào)度器將DAG解析為多個任務(wù)集，提交給任務(wù)調(diào)度器.任務(wù)調(diào)度器將任務(wù)分配給執(zhí)行進程，當一個執(zhí)行進程收到一個任務(wù)時，會從執(zhí)行進程的線程池中抽取一個線程來執(zhí)行該任務(wù).

3.1 預(yù)處理方法

在這個實驗中，本文使用了彈性分布式數(shù)據(jù)集和Spark，用于運行和操作在多個節(jié)點在一個集群上做并行處理并有效地獲得所需信息.Spark不僅支持映射和還原操作，還提供了過濾、按鍵還原、按鍵分組等操作.Spark提供了彈性分布式數(shù)據(jù)集(RDD)的抽象，它提供了一個只讀的對象集合，在一組機器上進行分區(qū).RDD通過線程實現(xiàn)容錯.每當RDD的任何一個分區(qū)丟失時，RDD都有足夠的信息來重建丟失的分區(qū).

首先加載數(shù)據(jù)集，將文件的每一行轉(zhuǎn)換成 RDD 中的元素.接下來，本文使用map將解析函數(shù)應(yīng)用于RDD中的日志文件中每個元素.然后要進行數(shù)據(jù)清理，驗證一下原始數(shù)據(jù)集中是否有空行.分割樣本，生成m條數(shù)據(jù)，再創(chuàng)建一個RDD，包含n個分區(qū)，每個RDD分區(qū)包含m/n個數(shù)據(jù).對于第s個RDD分區(qū)，每l個數(shù)據(jù)被劃分到一個樣本，完成樣本劃分后，將得到m/l個新樣本RDD.對于樣本RDD的第s個RDD分區(qū)，其中每條數(shù)據(jù)都將按max-min算法[8]進行歸一化.樣本中包含的一條數(shù)據(jù)，從某條屬性來考慮.max代表數(shù)據(jù)的最大值，min代表最小值.

在所有樣本被歸一化后，得到一個新的RDD，并在此基礎(chǔ)上操作進行樣本分解形成特征向量.每個特征向量可以由不同的屬性構(gòu)建.最后，在對所有樣本進行分解后，得到m/l個特征向量.

3.2 預(yù)處理舉例

本文使用了NASA-HTTP數(shù)據(jù)集來進行一個演示，預(yù)處理算法提取了不同的結(jié)果，如主機、請求路徑、請求內(nèi)容的字節(jié)數(shù)等.在本文第4節(jié)的實驗中以NASA-HTTP為例，表2顯示了一個包含部分屬性的預(yù)處理網(wǎng)絡(luò)日志樣本.對于解析日志文件中host這一元素.如果想要提取排行前10的host.首先，本文使用lambda函數(shù)中的和map函數(shù)如txt_.map(lambdax:(x，x.split(′1′))).filter(lambday:y[0].startswith(′host′))從RDD中提取主機字段，創(chuàng)建一個新的RDD，使用由主機和1組成的元組，讓本文計算特定主機的請求創(chuàng)建了多少記錄.使用新的RDD，本文用Lambda函數(shù)執(zhí)行一個reduce函數(shù)，將兩個值相加.然后，本文根據(jù)每個主機的訪問次數(shù)(每對主機的第2個元素)大于10來過濾結(jié)果.

表2 數(shù)據(jù)集預(yù)處理之后的部分結(jié)果Table 2 Partial results of the dataset after pre-processing

在Spark環(huán)境下，預(yù)處理的步驟可簡述為:輸入網(wǎng)絡(luò)日志數(shù)據(jù)集，對數(shù)據(jù)集中所需的屬性應(yīng)用上文的解析技術(shù)，設(shè)置數(shù)據(jù)集的正則表達式，應(yīng)用并檢查日志解析的輸出，如果解析成功，則將內(nèi)容存儲起來，否則，應(yīng)用新的解析規(guī)則，添加新舊兩個規(guī)則，用于解析日志.將不同的正則表達式進行分組，解析日志，輸出主機、HTTP請求和響應(yīng)的數(shù)量以及數(shù)據(jù)的特征.

為了舉例，這里做了一個可視化展示，本文從產(chǎn)生的RDD中提取10個元素，輸出結(jié)果(來自170455條網(wǎng)絡(luò)日志記錄的主機數(shù)量)如圖1所示.

圖1 預(yù)處理輸出的前10主機展示Fig.1 Preprocessed output of the top 10 hosts

4 基于特征轉(zhuǎn)移概率的聚類算法

基于Spark的K-means算法需要一個用戶定義的參數(shù).這也是大多數(shù)聚類方法的情況.一個缺點是難以確定最佳的聚類數(shù)量.有多種技術(shù)可以做出這種決定，其中大多數(shù)是基于找到k的值，以平衡最小化集群內(nèi)距離和最大化集群間距離的搜索.然而，對于 "最佳 "技術(shù)并沒有達成共識.k的選擇也可能經(jīng)常依賴于研究人員的專家意見，以及對不同位置誤差和空間分布誤差的擬合度的解釋.在本文中聚類的數(shù)量是通過最大化平均輪廓系數(shù)來確定的，而不是試錯的學(xué)習方法.輪廓系數(shù)是一個簇中所有點之間的平均距離，與一個點與它與最近簇的距離之間的平均距離之比.K-means算法隨機選擇k個觀測值作為群組的中心，然后計算每個觀測值與所有群組中心之間在特征空間中的歐幾里得距離.接下來，它根據(jù)歐氏距離最近的聚類中心給每個觀測值分配一個組，即k.中心被反復(fù)更新，直到達到一定數(shù)量的群組，所有的觀測值被分配到一個獨特的群組.由于K-means由于計算量過大而無法處理大型數(shù)據(jù)集，本文采用了基于Spark的K-means-標準K-means算法的高級版本，以減少計算負擔.基于Spark的K-means對所有數(shù)據(jù)對的距離進行并行計算，同時需要一個通過平均輪廓系數(shù)確定的參數(shù)k，將數(shù)據(jù)分成k個聚類.這種方法適合于探索無法存儲在計算機存儲器中的大規(guī)模數(shù)據(jù)集.與基本的K-means算法相比，基于Spark的K-means的計算速度更快.

本文提出的基于特征轉(zhuǎn)移概率的Spark-K-means聚類算法，可以充分利用集群的計算資源，高效并行處理大規(guī)模網(wǎng)絡(luò)日志數(shù)據(jù).對于特征轉(zhuǎn)移概率及其算法的實現(xiàn)步驟在4.1和4.2中介紹.

4.1 特征轉(zhuǎn)移概率

特征轉(zhuǎn)移概率的概念如定義1所示，通過計算特征轉(zhuǎn)移概率，可以得到最大過渡概率，進行比較可以得到每個特征向量及其接入點的鍵值對，確定其每次的聚類中心.

定義1.特征轉(zhuǎn)移概率(Feature Transition Probability).特征轉(zhuǎn)移概率Pik表示樣本i到第k個聚類中心的轉(zhuǎn)移概率，由公式(1)進行計算.

(1)

(2)

(3)

(4)

(5)

以上是本文算法用到的公式.其中M={μ1，μ2，…，μk}是所有聚類中心的集合.其中εik=1/εik，其中εik代表i點和k點之間的歐幾里得距離，參數(shù)σik(n)可由公式(2)來迭代計算，表示發(fā)生第i個點轉(zhuǎn)移到第n次聚類中心的歐幾里得距離.α和β是可變參數(shù).

4.2 聚類算法實現(xiàn)步驟

聚類算法實現(xiàn)如圖2所示，具體步驟見步驟1～步驟8.

圖2 聚類算法實現(xiàn)流程Fig.2 Clustering algorithm implementation process

步驟1.讀取預(yù)處理后的數(shù)據(jù)，提取為m個特征向量.創(chuàng)建RDD.創(chuàng)建一個包含n個分區(qū)的RDD特征向量RDD，每個RDD分區(qū)包含m/n個特征向量，每個工作節(jié)點將處理多個RDD分區(qū).

步驟2.隨機選取初始聚類中心.計算所有點之間的平均距離即輪廓系數(shù)，通過計算最大化平均輪廓系數(shù)來確定聚類數(shù)量.從特征向量RDD中隨機選取k個特征向量作為初始聚類中心M={μ1，μ2，…，μk}，由主節(jié)點向各工作節(jié)點廣播.

步驟5.判斷初始聚類中心是否已經(jīng)收斂.計算路徑RDD的第s個RDD分區(qū)的所有特征向量與其對應(yīng)的初始聚類中心之間的均方誤差MSE，然后將每個RDD分區(qū)得到的均方誤差從每個工作節(jié)點收集到主節(jié)點，則總均方誤差可由公式(5)來計算，判斷MSE是否小于或等于收斂閾值，如果是，則輸出全局最優(yōu)初始聚類中心，否則返回步驟3.

步驟6.將每個特征向量并行劃分到最近的聚類中.計算出每個特征向量與每個聚類中心之間的歐氏距離，并將每個特征向量分類到最近的聚類中，將一個特征向量及其對應(yīng)的最近聚類的中心點分別視為值和鍵，得到鍵值對RDD集群RDD.

步驟7.并行更新聚類中心.對于第s個RDD分區(qū){<μ?j∈[1，k]，E(s-1)m/n+1>，<μ?j∈[1，k]，E(s-1)m/n+2>，…，<μ?j∈[1，k]，Es*m/n>}的簇RDD，重新計算第s個RDD分區(qū)的k個簇的中心點，{μs1，μs2，…，μsk}，從工作節(jié)點到主節(jié)點收集簇RDD分區(qū)的k個簇的中心點，以公式(4)確定的μj作為第j個新的聚類中心，從主節(jié)點向每個工作節(jié)點廣播k個更新的聚類中心.

步驟8.判斷聚類中心是否已經(jīng)收斂或達到最大迭代次數(shù).計算集群RDD的第s個RDD分區(qū)的所有特征向量與其對應(yīng)的聚類中心之間的均方誤差MSE.其次，將每個RDD分區(qū)得到的均方誤差從每個工作節(jié)點收集到主節(jié)點，通過公式(5)計算總均方誤差.判斷MSE是否小于或等于收斂閾值或已達到最大迭代次數(shù)，如果是則輸出網(wǎng)絡(luò)日志的分析模型.如果不是則返回步驟6.

得到訓(xùn)練良好的網(wǎng)絡(luò)日志分析模型后，就可以對數(shù)據(jù)進行分析.如圖2所示，首先，將待診斷的數(shù)據(jù)進行基于Spark的分解預(yù)處理，得到特征向量，存儲在HDFS[9]中.然后從HDFS中讀取所有特征向量，創(chuàng)建RDD.通過并行計算RDD的每個特征向量與日志分析模型提供的每個聚類中心之間的加權(quán)歐氏距離.最后，將每個特征向量分類到最近的聚類中心，并輸出分析結(jié)果.

5 實驗分析

5.1 實驗準備

本次實驗使用的是NASA-HTTP網(wǎng)絡(luò)服務(wù)器日志.包含IP地址、用戶名.時間戳、訪問請求、狀態(tài)碼、字節(jié)數(shù)等.在應(yīng)用所提出的算法之前必須對網(wǎng)絡(luò)日志數(shù)據(jù)進行預(yù)處理.表2顯示了一個包含部分屬性的預(yù)處理網(wǎng)絡(luò)日志樣本.

所有的實驗都是在PC上使用Apache Spark 3.1.2進行的，該集群由1個主節(jié)點和8個工作節(jié)點組成，其集群資源管理器為Spark自帶的獨立集群管理器.節(jié)點配置信息在表3列出.大小為512 GB的硬盤和Linux Ubuntu16.04操作系統(tǒng).所提出的算法采用Python和Spark應(yīng)用編程接口(API).

表3 節(jié)點信息及配置Table 3 Node information and configuration

5.2 實驗結(jié)果

圖3分別繪制了不同工作節(jié)點數(shù)和不同規(guī)模數(shù)據(jù)集(數(shù)據(jù)集A數(shù)據(jù)集B數(shù)據(jù)集C的規(guī)模大小是遞增的)下得到的并行計算速度、并行效率和部分屬性的聚類時間，從圖3可以看出，對于3種不同大小的數(shù)據(jù)集，隨著Spark集群中工作節(jié)點數(shù)量的增加，并行速度逐漸增加.隨著工作節(jié)點數(shù)的增加，得到的速度逐漸增加，接近線性增長，但并沒有達到理論值，因為工作節(jié)點數(shù)量的增加所帶來的通信成本和任務(wù)調(diào)度成本在一定程度上降低了并行的性能[10].當工作節(jié)點數(shù)為8時，用數(shù)據(jù)集A、數(shù)據(jù)集B、數(shù)據(jù)C，分別獲得了4.86×、5.25×、6.18×的提速，當工作節(jié)點數(shù)一定時，用更大的數(shù)據(jù)集進行網(wǎng)絡(luò)日志處理可以獲得更高的提速.當工作節(jié)點數(shù)固定時，隨著數(shù)據(jù)集的大小變大，所獲得的并行效率逐漸提高.因此，較大的數(shù)據(jù)集更有助于發(fā)揮并行計算的優(yōu)勢，并充分利用Spark集群的計算資源.結(jié)果表明，隨著數(shù)據(jù)集大小的增加，并行速度和效率都在逐步提高.因此，本文所提出的方法適合處理網(wǎng)絡(luò)日志這種大規(guī)模數(shù)據(jù)集.在不同規(guī)模數(shù)據(jù)集下，通過使用Apache Spark在這些數(shù)據(jù)集上執(zhí)行K-means算法，并對其執(zhí)行時間與現(xiàn)有的結(jié)果對比其他現(xiàn)有使用Spark的K-means算法，有明顯的改進.在執(zhí)行時間上，相對現(xiàn)有的使用Spark的K-means算法[11]，執(zhí)行時間大約是75.97%.如圖4所示.

圖3 不同節(jié)點數(shù)的并行速度(a)和并行效率(b)比較Fig.3 Parallel speed and parallel efficiency with different number of nodes

圖4 K-means聚類處理的執(zhí)行時間Fig.4 Execution time of K-means clustering

對每個數(shù)據(jù)集，選擇最重要的特征來代表候選解決方案集.為測試目的，用約10和100的特征數(shù)進行測試.分類器如Naive Bayes(NB)[12]、支持向量機(SVM)[13]和K-NN[14]用于評估數(shù)據(jù)集.分類器的準確度是通過十倍交叉驗證獲得的.

如圖5～圖7所示，本文的聚類方法，在SVM的分類器測試下，靈敏度、特異性、準確率性能很好，其他分類器如NB、K-NN環(huán)境下，相比與其他優(yōu)化的聚類方法也并沒有降低.得到很好的聚類效果的同時，提升聚類的速度.

圖5 文獻[11]與本文聚類的特異性對比Fig.5 Sensitivity comparison between proposed algorithm and [11]

圖6 文獻[11]與本文聚類的特異性對比Fig.6 Specificity comparison between proposed algorithm and [11]

6 相關(guān)工作

目前，已經(jīng)提出了許多聚類算法來處理各種數(shù)據(jù)集.這些聚類算法大致可分為4類:分區(qū)聚類算法、分層聚類算法、基于網(wǎng)格的聚類和基于密度的聚類.對于處理Web日志這種數(shù)據(jù)集，較常見的是分層聚類的方法.

文獻[15]提出了一種分層聚類的方法，分層地分解給定的數(shù)據(jù)對象集合.根據(jù)層次分解的形成，層次方法可分為自底向上法和自頂向下法.自底向上方法先將每個對象分離為一個組，然后依次合并相似的對象或組，直到所有組合并為一個組，或者直到達到作為終止條件.自頂向下法將所有對象放入一個簇中.在這種類型的聚類中，所有觀察值都分配給一個集群，然后將單個集群分為兩個集群，并依次為每個集群進行處理，直到每個觀察都有一個集群.常用的自底向上法內(nèi)聚聚類方法有AGNES、BIRCH、ROCK和CURE[16-18]，常用的自頂向下劃分方法有DIANA等.層次方法的缺點是缺乏全局最優(yōu)函數(shù).該技術(shù)的另一個主要問題是它不能糾正錯誤的決定.此外，該算法在時間和空間上具有較高的復(fù)雜度，嚴重限制了要處理的數(shù)據(jù)集.

文獻[11]通過將K-means算法和層次算法相結(jié)合，提出了層次K-means 網(wǎng)絡(luò)日志挖掘聚類算法.K-means 算法的主要缺點是需要預(yù)先確定聚類的數(shù)量.如果系統(tǒng)在聚類用戶時沒有意識到這一點，K-means 算法將是不自適應(yīng)的.K-means算法對噪聲數(shù)據(jù)和邊界數(shù)據(jù)非常敏感，即使少量的噪聲或邊界數(shù)據(jù)也會使聚類中心發(fā)生較大程度的偏移.并且由于K-means算法對初始聚類中心敏感，必須提前給出聚類次數(shù)，這會導(dǎo)致聚類的主觀性和隨意性，影響正確的聚類結(jié)果.而內(nèi)聚層次聚類算法的優(yōu)點是通過內(nèi)聚的方法確定聚類的個數(shù)，克服了上述缺點，并降低了一定時間復(fù)雜度.

上述工作確實提高了傳統(tǒng) K-means 算法的性能.然而，在面對大規(guī)模數(shù)據(jù)集時，這些算法仍然存在效率低和對噪聲點敏感的問題.但仍然存在算法的時間空間復(fù)雜度較高的情況，運行速度較慢.本文提出的基于特征轉(zhuǎn)移概率的聚類算法對K-means算法進行了改進.通過最大化平均輪廓系數(shù)確定了聚類的個數(shù)，避免了試錯.在數(shù)據(jù)處理方面具有快速、穩(wěn)定和準確的特點.

綜上所述，本文提出的基于特征轉(zhuǎn)移概率的方法保持了內(nèi)聚層次聚類算法的優(yōu)點，同時對運行速度方面有了一定的改善，同時對并行效率也有一定提升，尤其對于數(shù)據(jù)規(guī)模較大的情況，本文方法的效果更加理想，最佳情況下，執(zhí)行時間大約是文獻[11]中K-means聚類方法的75.97%.

7 結(jié)束語

本文提出了一種基于特征轉(zhuǎn)移概率的K-means聚類算法.并對傳統(tǒng)的聚類算法進行了分析，本文提出的算法對傳統(tǒng)的聚類算法的不足之處各方面進行了彌補，主要在運行速度方面進行了較大改進.通過本文的方法，可以快速地對web服務(wù)器的各方面日志進行分析，了解所需要的信息.并行的分布式處理網(wǎng)絡(luò)日志方法節(jié)省了大量的處理時間，提高了性能，在短時間內(nèi)進行處理海量數(shù)據(jù)，給出了更高效的結(jié)果并在靈敏度、特異性、準確率等方面保持較高水平.對于Web日志挖掘等大量數(shù)據(jù)處理，本文提出的基于特征轉(zhuǎn)移概率的K-means算法具有較好的優(yōu)勢.