基于K?均值與AGNES聚類算法的校園網行為分析系統研究

茆漢國

摘 要： 校園網中的服務器存有海量的用戶訪問日志文件，記錄了校園網用戶的訪問信息。鑒于此，提出了一種基于聚類算法的校園網用戶行為分析技術，設計和實現了數據預處理系統，對日志數據進行一系列的清理、合并，標準化等預處理，使其更好地適應后續的聚類操作。將預處理后的數據作為輸入數據，分別實現了三種常用的聚類算法對日志數據進行聚類，然后從聚類準確率和聚類速度兩個角度對現有算法進行優化。為了提高聚類準確率，提出了用K?均值算法結合AGNES算法的方法；為了提高聚類速度，在MPICH2平臺上設計和實現了并行K?均值算法，實現多機并行分析，最后簡單介紹了校園網行為分析系統的應用。

關鍵詞： 校園網； 行為分析； 聚類算法； MPICH2

中圖分類號： TN98?34； TM417 文獻標識碼： A 文章編號： 1004?373X（2016）23?0116?05

Research on campus network user behavior analysis system

based on K?means and AGNES clustering algorithm

MAO Hanguo

（Information Construction and Management Office， Nanjing Institute of Technology， Nanjing 211167， China）

Abstract： The server in campus network has massive user access log files， and records the access information of the campus network users. In view of this issue， a campus network user behavior analysis technology based on clustering algorithm is proposed. The data preprocessing system was designed and implemented. The log data is conducted with a series of cleaning， merging， standardization and preprocessing to suit for the subsequent clustering operation. The preprocessed data is taken as the input data to cluster the log data by means of 3 commonly?used clustering algorithms respectively， and then， the available algorithms are optimized in the aspects of clustering accuracy and clustering speed. In order to improve the clustering accuracy， a method of combining AGNES algorithm with K?means algorithm is proposed. In order to improve the clustering speed， the parallel K?means algorithm was designed and implemented on MPICH2 platform to realize the multimachine parallel analysis. The application of the campus network user behavior analysis system is introduced simply.

Keywords： campus network； behavior analysis； clustering algorithm； MPICH2

0 引 言

當前，為了更好地管理校園網，各個高校會在校園網中安裝各種硬件設備，記錄校園網用戶的訪問信息。日積月累，校園網中就積累了大量的用戶訪問記錄[1]。但是，這些硬件設備自帶的軟件只能用來記錄訪問信息，但卻無法進一步挖掘存在于這些數據中的潛在關系，無法以現有數據預測未來的發展趨勢，無法將隱藏在數據背后的知識挖掘出來。同時，校園網上存在的不良信息、系統漏洞、病毒等問題對校園網系統產生了巨大的威脅[2]。

當前的網絡環境迫使管理者對校園網的安全性、穩定性和服務質量提出更高的要求，在校園網提供優質的網絡服務的同時，還要能夠保護網絡和用戶系統的安全[3]。因此，為了保障校園網能通暢運行，必須建立一種有效的校園網分析機制，從不同角度分析校園網的運行狀態，然后根據實際情況進行調整。Web日志中記錄了用戶的訪問信息，保存有大量用戶的訪問規律。通過設計一種Web日志分析軟件，分析Web日志中的數據，了解校園網用戶的訪問特點和規律，然后根據分析的結果調整和優化校園網結構，更好地為校園網用戶進行服務。

1 校園網行為分析系統的總體設計

根據數據挖掘技術的操作流程，系統分為以下幾個部分：數據采集，數據預處理，數據挖掘，結果分析。系統的結構如圖1所示。

圖1 校園網行為分析系統的結構

2 數據預處理的設計與實現

2.1 數據采集

校園網用戶行為分析系統的數據來自于某大學公網訪問流量控制服務器，其位置處于校園網和公網出口路由之間。流控服務器上的訪問日志有：RPT_PUR，RPT_LUR，RPT_TR，RPT_MALUR，RPT_MEDIA等文件，其中RPT_TR為主日志文件，記錄了全部的公網訪問信息，所以將該日志作為本系統的原始數據源[4]。

2.2 數據預處理

2.2.1 清理臟數據

對于行為分析系統來說，并不需要關心日志文件中的所有字段，而只需要對其中一部分進行處理。因此，只需要提取以下幾個字段：“客戶端IP”、“請求訪問時間”、“網站域名”、“上行流量”、下行流量等這些字段[5]。另外，對于字段不完整的數據條目，予以舍棄。

2.2.2 數據歸并

根據校園網日志文件做用戶的行為分析時，有兩個數據是至關重要的。第一個就是某個網站的訪問次數，另一個是該網站的訪問流量。其中訪問流量還包括上行流量和下行流量兩部分。由于不分別考慮上行流量和下行流量，可將二者相加，并將其統一命名為流量[6]。然后將相同網站進行歸并，這樣根據數據條目的多少和每個數據條目中的訪問流量，可以得到每個網站的總訪問次數和訪問流量。

2.2.3 數據的標準化

數據標準化的形式有很多，根據整理后的校園網日志文件的特點，采用極差歸一化方法。由于相同字段中，數據之間的數量級差異比較大，如果單純的使用極差歸一化方法，會出現很多接近0的數據，這樣會降低后續聚類操作的準確率[7]。所以需要根據實際情況對現有的極差歸一化方法進行改進，對數量級差進行級放大，具體的操作過程如下：

（1） 設數據集中需要計算的字段數量為[n，]首先獲取每個字段的最大值，分別記為[xmaxi（i=1，2，…，n）；]

（2） 比較[xmaxi]每個值的數量級，選擇數量級最小的值分別記為[xmaxs；]

（3） 對各個字段使用極差歸一化的方法對數據集進行標準化，但在計算每個值[xi]與最小值[xmin]的差時，都乘以[xmaxs]對應的數量級[Os]，即：

[xinew=（xi-xmin）×Osxmax-xmin] （1）

經過極差的級放大后，得到的數據處于同一個數量級，這為后續的聚類操作的準確性提供了保障。

2.2.4 處理效果評價

在校園網日志文件經過清理臟數據、數據歸并和數據標準化之后，原始數據集數量由原來的7 000萬條變為現在的85萬條，并且數據形式也更符合后續聚類操作的要求。數據預處理工作有效地縮減了原始數據規模，并為后續聚類操作做了鋪墊。

3 聚類算法的設計

3.1 算法的選擇

聚類算法的形式有很多種，不同的聚類算法適合不同的原始數據集。例如K?均值法適合大數據集，K?中心點算法適合小數據集，BIRCH算法適用于數據分布呈凸形及球形的數據集等。根據校園網日志數據的情況，分別選擇K?均值算法，AGNES算法和DBScan算法對數據集進行分析，并對比三種算法的執行效率。

3.2 K?均值算法的實現

3.2.1 算法的輸入

算法的執行過程如下：首先，隨機從原始數據中選出[k]個對象，設置為[k]個簇，每個簇的平均值就是這個對象的值，把這個平均值又叫做質心或中心。對于剩余的對象，根據每個對象與每個簇中心的距離大小，把他們分到最近的簇中，這個過程完成后重新計算各個簇的平均值[8]。此過程需不斷重復，直至準則函數收斂，或達到指定的迭代次數為止。通常采用平方誤差準則函數，即：

[Je=i=1kx∈CiX-mi2] （2）

式中：[Je]是數據集中所有數據對象的平方誤差的總和；[X]代表數據對象；[mi]代表簇[Ci]的平均值。

對于兩個數據對象之間的相似度，可以通過他們間的相異性來定義和描述。一般而言，在計算兩個對象之間的相異性時，采用兩個對象之間的距離來計算。在計算簇中的個體對象與簇中心的距離時，通常采用歐式距離，其計算公式為：

[d（x，y）=k=1nwk（xk-yk）2， 1≤k≤n] （3）

式中：[x=（x1，x2，…，xn）]和[y=（y1，y2，…，yn）]是兩個[n]維的數據對象；[m=（m1，m2，…，mn）]則代表每個屬性在計算相異度時所代表的權重，不同的權重設置就會產生不同的相異度，從而影響到簇的劃分。

3.2.2 算法的過程

K?均值算法的過程如下所示：

輸入：簇的數目[k，]包含[n]個對象的數據集

輸出：[k]個簇

過程：

（1） 從數據集中隨機選擇[k]個對象，將每個對象都作為一個簇的初始中心；

（2） 分配每個剩余對象到離他最近的簇中心所在的簇中；

（3） 計算每個簇中所有對象的均值向量，使其作為新的簇的中心；

（4） 重復步驟（2），步驟（3）過程，直到[k]個簇的中心不再發生變化或者準則函數收斂；

（5） 返回各個聚類的中心和成員。

K均值算法的時間復雜性為[O（tkn），t]代表迭代次數，[k]代表聚類數，[n]代表樣本數。

3.3 AGNES算法的實現

3.3.1 算法的輸入

AGNES算法的輸入變量只有1個，就是最終簇的個數[k，]這點與K?均值算法一樣。算法最初將數據集中的每個對象都看成一個簇，通過特定的規則將這些簇逐步合并，直到簇的數目達到要求。在這里規定：在簇[A]中的一個對象和簇[B]中的一個對象之間的距離是所有屬于不同簇的對象之間最小的，將[AB]合并。按照這個規則，不斷地合并現有的簇，直到簇的個數等于變量[k]后，算法結束。

3.3.2 算法的過程

AGNES算法的過程如下：

輸入：簇的數目[k，]包含[n]個對象的數據集

輸出：[k]個簇

過程：

（1） 設置每個對象都作為一個初始簇；

（2） Repeat；

（3） 以兩個簇中最近的數據點為標準找到最近的兩個簇；

（4） 將兩個簇合并生成新的簇的集合；

（5） Until達到要求的簇的數目。

AGNES算法的時間復雜性為[O（n2），n]代表樣本數。

3.4 DBScan算法的實現

3.4.1 算法的輸入

DBScan算法是典型的基于密度的聚類方法。除了數據集，DBScan算法的輸入有兩個：半徑[e]和最少數目MinPts。DBScan算法的核心思想是，對于簇中的每一個對象，在給定的半徑[e]鄰域內，包含數據對象的個數必須大于給定的最少數目MinPts。

3.4.2 算法的過程

DBScan算法的過程如下所示：

輸入：半徑[e，]包含[n]個對象的數據集，最少數目MinPts

輸出：生成達到所有密度要求的簇

過程：

（1） Repeat；

（2） 從數據集中找到一個未處理的點；

（3） IF找到的點是核心點，THEN找出全部從該點密度可達的對象，形成一個簇；

（4） ELSE找到的點是邊緣點（非核心對象），從本次循環中跳出，繼續尋找下一個點；

（5） UNTIL所有的點都被處理。

DBScan算法的時間復雜性為O（nlog n），其中n代表樣本數。

3.5 幾種聚類算法執行結果對比

3.5.1 效率對比

在樣本數達到4 000時，AGNES算法的執行時間已經是無窮大了，所以AGNES不適合數據量較大的聚類。而DBScan算法和K?均值算法的執行時間相對較快，特別是K?均值算法，在簇數遠小于數據集樣本個數時，K?均值算法的時間復雜性為[O（n）。]三種算法的執行效率如圖2所示。

從圖2得出的結論：K?均值算法的執行效率最高，遠遠優于另外兩種算法。而AGNES算法的執行效率非常低，不適合在大數據集上進行聚類運算。

3.5.2 準確率對比

AGNES算法和DBScan算法在聚類準確率上效果比較好，而K?均值算法的聚類準確率跟初始聚類中心的選定有很大關系。而在實際操作中，能正確地選取聚類中心是一件很困難的事情，因為在聚類結果出來之前，很難預先確定聚類中心的大概位置。所以，如果要在實際中使用K?均值算法，一定要解決這個問題，讓初始聚類中心貼近最終的聚類中心，然后才能得到滿意的聚類結果。

4 K?均值算法的優化

4.1 優化方案

因為K?均值算法的執行效率會比另外兩種聚類算法高過很多，在數據量較大時這種效率優勢會更加明顯，所以決定在K?均值算法的基礎上進行優化。設計優化的方案有兩種，第一種是采用AGNES算法和K?均值算法結合的方式，這樣既能利用AGNES算法提高聚類準確率，又能兼顧K?均值算法的高效率。第二種優化是利用MPICH2接口設計一種并行的K?均值算法，讓它在多機的環境下執行，這樣可以顯著地提高執行效率。

4.2 AGNES算法與K?均值算法的結合

使用AGNES算法和K?均值算法結合的方式，在執行K?均值算法前，從原始數據中隨機抽出一部分數據，并在這些抽出來的數據上運行AGNES算法，然后將運行結果得到的聚類中心當做K?均值算法的初始聚類中心。具體過程如圖3所示。

4.3 K?均值算法并行實現

4.3.1 并行K?均值算法的實現

分析K?均值算法可以看出，算法中每次迭代的計算只要分為兩個步驟：

（1） 計算各個數據對象與各個類中心之間的距離；

（2） 產生新的聚類中心時，需要對每個類中所有數據求和并取平均值。

隨著數據量的增加而導致計算時間延長的處理階段主要是第一步，因此考慮并行處理這一過程來提高聚類效率，降低算法對內存的較高要求。

采取基于主從（Master/Slave）模式的數據并行策略。主程序運行在一個主節點上，負責分配數據和匯總從其他節點產生的聚類結果，生成新的聚類中心。從程序運行在其他節點上，處理主節點分配給自己的一部分數據集。主從節點之間的通信通過MPICH2平臺實現，所以寫程序時不用關注具體的并行通信細節，在很大程度上方便了編程。

首先，主節點先將數據集劃分后，連同現有的聚類中心集一并發給各個從節點，每個節點接收到的數據集大小為整個數據集的大小/從節點數。各個從節點將接收到的數據集進行聚類，并把聚類結果返還給主節點。這時主節點等待各個從節點的數據，一旦將所有從節點的聚類結果收齊后，主節點計算各個類的新的聚類中心，然后和原聚類中心通過計算誤差平方準則函數進行比較。如果原來的聚類中心和新的聚類中心之差小于給定的閾值，算法結束。否則主節點將重新劃分數據集并分配給各個從節點，開始新的一次迭代過程。

4.3.2 執行結果

把多臺配置為Intel Core i3 3.2 GHz，4 GB RAM的計算機用100M/10M自適應網卡連接起來，在系統上安裝好MPICH2構成一個機群系統。使用C++實現這個算法，在這個機群系統的基礎上完成算法的驗證實驗。通過實驗可以看出K?均值并行算法具有以下幾個特征：

（1） 當[N=100K，p=2]時，并行算法的加速比是小于1的。也就是說，由于數據量不夠大，數據分塊過多，各節點獲分配的數據量比較少，并行計算粒度過小，導致計算與通信比值下降，從而造成并行算法的執行時間不如串行算法。

（2） 當[N>100K][且2≤p≤4]時，并行算法在絕大多數情況下加速比大于1。當輸入數據規模增大，每個節點的運算量增加時，并行算法的優勢就體現出來了，這時并行算法的執行時間要優于串行算法。

（3） 當[N>100]K且[p=3]時，算法的加速比達到了最高值，即3為理想節點數。當再增加節點數目，因為各個節點之間的通信量增加，加速比開始下降，當[p=5]時，加速比開始小于1，也就意味著并行算法的效率小于串行算法。

4.3.3 提高并行性能的方法

通過對K?均值并行算法的設計與實現，發現在PC機群網絡并行的環境下，要提高并行算法的執行效率，需要注意以下兩點：

（1） 計算機節點數人。在計算機節點數目較少時，增加計算機節點數會提高并行度，提高并行算法的執行效率。

（2） 應該盡量加大每個節點的預算量并減少節點間的通信，即采用粗粒度的并行算法。

5 系統的應用

5.1 統計分析

將預處理后的日志文件以散點圖的形式顯示出來。可以看到，幾乎99%以上的數據都集中在左下角，這表明校園網用戶在進行網絡訪問時，對于大部分的網站用戶訪問流量低且點擊次數少。這個統計結果也是符合事實的，因為人們上網時，只有個別非常有名的網站，會讓用戶長時間訪問而造成大量的上行和下行流量，或者讓用戶頻繁地訪問。隨著搜索引擎的普遍使用，用戶對于某些信息的搜索會查詢大量的網站，對于大部分網站來說，用戶只會訪問有限的幾次，甚至絕大部分網站用戶在很長一段時間內只會訪問一次，說明校園網用戶的訪問呈現出流量少和訪問次數少的特點。

校園訪問的網站點擊流量和次數分布如圖4所示。

5.2 聚類分析

應用本文研發的系統對校園網日志文件進行聚類分析，然后得出校園網用戶的網絡行為。為了讓聚類既準確又快速，采用AGNES+K?均值合并算法，同時K?均值算法部分采用并行實現。通過分析，本系統可以通過分析訪問日志而得出各類網站的訪問狀況，進而得知校園網用戶的上網行為。可以知道，校園網用戶訪問最多的網站是bit.edu.cn，而訪問量最大的網站是幾個視頻網站。利用本系統對校園網日志文件進行聚類，其結果有助于分析校園網用戶的上網行為，了解他們的喜好。校園網管理者可以根據分析的結果對校園網結構進行調整，從而更好地為校園網用戶服務。

6 結 論

本文介紹了一種基于聚類算法的校園網用戶行為分析技術，在分析日志文件的過程中，系統采用的核心算法為聚類算法。首先設計了系統的總體結構，提出了分析模型，然后設計并實現了對校園網日志數據進行預處理的模塊，通過處理臟數據，數據歸并，數據標準化等操作篩選出有效的數據，為數據挖掘做準備。進一步，根據當前的校園網實際運行情況，提出了校園網行為分析系統的創建意義，然后設計并實現了K?均值，AGNES，DBScan幾種聚類算法，并對K?均值算法進行優化。最后介紹了本系統的應用方法，并根據系統的執行結果分析了校園網用戶的上網行為。

參考文獻

[1] 丁青，周留根，朱愛兵，等.基于K?means聚類算法的校園網用戶行為分析研究[J].網絡新媒體技術，2010，31（6）：74?80.

[2] 馬艷英.基于遺傳算法的Web文檔聚類算法[J].現代電子技術，2016，39（1）：148?152.

[3] 羅軍鋒，洪丹丹.基于數據抽樣的自動K?means聚類算法[J].現代電子技術，2014，37（8）：19?21.

[4] 步媛媛，關忠仁.基于K?means聚類算法的研究[J].西南民族大學學報（自然科學版），2009（1）：198?200.

[5] 王燕，吳灝，毛天宇.基于K?中心點聚類算法的論壇信息識別技術研究[J].計算機工程與設計，2009，30（1）：210?212.

[6] 劉興光.基于云計算的大型校園互聯監測系統設計[J].現代電子技術，2015，38（24）：90?93.

[7] 張建文，徐瓊，王強.基于MPI環境的并行程序設計[J].東華理工學院學報，2007，30（1）：81?84.

[8] 呂元海，孫江輝，馬龍.基于OracleRAC的校園網數據庫集群系統設計與實現[J].現代電子技術，2016，39（4）：72?75.