齊 文，朱曦源，宋 杰

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

1 引 言

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

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

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

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

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

2 預(yù)備知識

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

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

算法1.K-means聚類算法

步驟1.隨機(jī)選擇k個(gè)集群中心點(diǎn).

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

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

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

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

2.1 在MapReduce上的K-means分析

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

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

算法2.在MapReduce上的K-means

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

步驟1.隨機(jī)初始化k個(gè)聚類中心.

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

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

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

算法3.Map映射器.

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

步驟1.對于每個(gè)數(shù)據(jù)點(diǎn)d∈D.

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

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

算法4.Reduce化簡器.

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

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

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

輸出:新的聚類中心.

2.2 在Spark上的K-means分析

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

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

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

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

由于Spark對于迭代計(jì)算的性能良好，故本文選擇Spark的K-means為基礎(chǔ)進(jìn)行優(yōu)化，提出了基于特征轉(zhuǎn)移概率的K-means聚類算法.具體實(shí)現(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ù)的特點(diǎn)，含有大量的噪聲數(shù)據(jù)，必須消除這些不相關(guān)的數(shù)據(jù)，所以需要對網(wǎng)絡(luò)日志進(jìn)行預(yù)處理.表1描述了一個(gè)樣本的entry headers.

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

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

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

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

3.1 預(yù)處理方法

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

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

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

3.2 預(yù)處理舉例

本文使用了NASA-HTTP數(shù)據(jù)集來進(jìn)行一個(gè)演示，預(yù)處理算法提取了不同的結(jié)果，如主機(jī)、請求路徑、請求內(nèi)容的字節(jié)數(shù)等.在本文第4節(jié)的實(shí)驗(yàn)中以NASA-HTTP為例，表2顯示了一個(gè)包含部分屬性的預(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中提取主機(jī)字段，創(chuàng)建一個(gè)新的RDD，使用由主機(jī)和1組成的元組，讓本文計(jì)算特定主機(jī)的請求創(chuàng)建了多少記錄.使用新的RDD，本文用Lambda函數(shù)執(zhí)行一個(gè)reduce函數(shù)，將兩個(gè)值相加.然后，本文根據(jù)每個(gè)主機(jī)的訪問次數(shù)(每對主機(jī)的第2個(gè)元素)大于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ù)集的正則表達(dá)式，應(yīng)用并檢查日志解析的輸出，如果解析成功，則將內(nèi)容存儲起來，否則，應(yīng)用新的解析規(guī)則，添加新舊兩個(gè)規(guī)則，用于解析日志.將不同的正則表達(dá)式進(jìn)行分組，解析日志，輸出主機(jī)、HTTP請求和響應(yīng)的數(shù)量以及數(shù)據(jù)的特征.

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

(5)

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

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

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

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

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

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

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

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

步驟7.并行更新聚類中心.對于第s個(gè)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，重新計(jì)算第s個(gè)RDD分區(qū)的k個(gè)簇的中心點(diǎn)，{μs1，μs2，…，μsk}，從工作節(jié)點(diǎn)到主節(jié)點(diǎn)收集簇RDD分區(qū)的k個(gè)簇的中心點(diǎn)，以公式(4)確定的μj作為第j個(gè)新的聚類中心，從主節(jié)點(diǎn)向每個(gè)工作節(jié)點(diǎn)廣播k個(gè)更新的聚類中心.

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

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

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)準(zhǔn)備

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

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

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

5.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

6 相關(guān)工作

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

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

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

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

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

7 結(jié)束語

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