基于K?均值與AGNES聚類(lèi)算法的校園網(wǎng)行為分析系統(tǒng)研究

茆漢國(guó)

摘 要： 校園網(wǎng)中的服務(wù)器存有海量的用戶訪問(wèn)日志文件，記錄了校園網(wǎng)用戶的訪問(wèn)信息。鑒于此，提出了一種基于聚類(lèi)算法的校園網(wǎng)用戶行為分析技術(shù)，設(shè)計(jì)和實(shí)現(xiàn)了數(shù)據(jù)預(yù)處理系統(tǒng)，對(duì)日志數(shù)據(jù)進(jìn)行一系列的清理、合并，標(biāo)準(zhǔn)化等預(yù)處理，使其更好地適應(yīng)后續(xù)的聚類(lèi)操作。將預(yù)處理后的數(shù)據(jù)作為輸入數(shù)據(jù)，分別實(shí)現(xiàn)了三種常用的聚類(lèi)算法對(duì)日志數(shù)據(jù)進(jìn)行聚類(lèi)，然后從聚類(lèi)準(zhǔn)確率和聚類(lèi)速度兩個(gè)角度對(duì)現(xiàn)有算法進(jìn)行優(yōu)化。為了提高聚類(lèi)準(zhǔn)確率，提出了用K?均值算法結(jié)合AGNES算法的方法；為了提高聚類(lèi)速度，在MPICH2平臺(tái)上設(shè)計(jì)和實(shí)現(xiàn)了并行K?均值算法，實(shí)現(xiàn)多機(jī)并行分析，最后簡(jiǎn)單介紹了校園網(wǎng)行為分析系統(tǒng)的應(yīng)用。

關(guān)鍵詞： 校園網(wǎng)； 行為分析； 聚類(lèi)算法； MPICH2

中圖分類(lèi)號(hào)： TN98?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

當(dāng)前，為了更好地管理校園網(wǎng)，各個(gè)高校會(huì)在校園網(wǎng)中安裝各種硬件設(shè)備，記錄校園網(wǎng)用戶的訪問(wèn)信息。日積月累，校園網(wǎng)中就積累了大量的用戶訪問(wèn)記錄[1]。但是，這些硬件設(shè)備自帶的軟件只能用來(lái)記錄訪問(wèn)信息，但卻無(wú)法進(jìn)一步挖掘存在于這些數(shù)據(jù)中的潛在關(guān)系，無(wú)法以現(xiàn)有數(shù)據(jù)預(yù)測(cè)未來(lái)的發(fā)展趨勢(shì)，無(wú)法將隱藏在數(shù)據(jù)背后的知識(shí)挖掘出來(lái)。同時(shí)，校園網(wǎng)上存在的不良信息、系統(tǒng)漏洞、病毒等問(wèn)題對(duì)校園網(wǎng)系統(tǒng)產(chǎn)生了巨大的威脅[2]。

當(dāng)前的網(wǎng)絡(luò)環(huán)境迫使管理者對(duì)校園網(wǎng)的安全性、穩(wěn)定性和服務(wù)質(zhì)量提出更高的要求，在校園網(wǎng)提供優(yōu)質(zhì)的網(wǎng)絡(luò)服務(wù)的同時(shí)，還要能夠保護(hù)網(wǎng)絡(luò)和用戶系統(tǒng)的安全[3]。因此，為了保障校園網(wǎng)能通暢運(yùn)行，必須建立一種有效的校園網(wǎng)分析機(jī)制，從不同角度分析校園網(wǎng)的運(yùn)行狀態(tài)，然后根據(jù)實(shí)際情況進(jìn)行調(diào)整。Web日志中記錄了用戶的訪問(wèn)信息，保存有大量用戶的訪問(wèn)規(guī)律。通過(guò)設(shè)計(jì)一種Web日志分析軟件，分析Web日志中的數(shù)據(jù)，了解校園網(wǎng)用戶的訪問(wèn)特點(diǎn)和規(guī)律，然后根據(jù)分析的結(jié)果調(diào)整和優(yōu)化校園網(wǎng)結(jié)構(gòu)，更好地為校園網(wǎng)用戶進(jìn)行服務(wù)。

1 校園網(wǎng)行為分析系統(tǒng)的總體設(shè)計(jì)

根據(jù)數(shù)據(jù)挖掘技術(shù)的操作流程，系統(tǒng)分為以下幾個(gè)部分：數(shù)據(jù)采集，數(shù)據(jù)預(yù)處理，數(shù)據(jù)挖掘，結(jié)果分析。系統(tǒng)的結(jié)構(gòu)如圖1所示。

圖1 校園網(wǎng)行為分析系統(tǒng)的結(jié)構(gòu)

2 數(shù)據(jù)預(yù)處理的設(shè)計(jì)與實(shí)現(xiàn)

2.1 數(shù)據(jù)采集

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

2.2 數(shù)據(jù)預(yù)處理

2.2.1 清理臟數(shù)據(jù)

對(duì)于行為分析系統(tǒng)來(lái)說(shuō)，并不需要關(guān)心日志文件中的所有字段，而只需要對(duì)其中一部分進(jìn)行處理。因此，只需要提取以下幾個(gè)字段：“客戶端IP”、“請(qǐng)求訪問(wèn)時(shí)間”、“網(wǎng)站域名”、“上行流量”、下行流量等這些字段[5]。另外，對(duì)于字段不完整的數(shù)據(jù)條目，予以舍棄。

2.2.2 數(shù)據(jù)歸并

根據(jù)校園網(wǎng)日志文件做用戶的行為分析時(shí)，有兩個(gè)數(shù)據(jù)是至關(guān)重要的。第一個(gè)就是某個(gè)網(wǎng)站的訪問(wèn)次數(shù)，另一個(gè)是該網(wǎng)站的訪問(wèn)流量。其中訪問(wèn)流量還包括上行流量和下行流量?jī)刹糠?。由于不分別考慮上行流量和下行流量，可將二者相加，并將其統(tǒng)一命名為流量[6]。然后將相同網(wǎng)站進(jìn)行歸并，這樣根據(jù)數(shù)據(jù)條目的多少和每個(gè)數(shù)據(jù)條目中的訪問(wèn)流量，可以得到每個(gè)網(wǎng)站的總訪問(wèn)次數(shù)和訪問(wèn)流量。

2.2.3 數(shù)據(jù)的標(biāo)準(zhǔn)化

數(shù)據(jù)標(biāo)準(zhǔn)化的形式有很多，根據(jù)整理后的校園網(wǎng)日志文件的特點(diǎn)，采用極差歸一化方法。由于相同字段中，數(shù)據(jù)之間的數(shù)量級(jí)差異比較大，如果單純的使用極差歸一化方法，會(huì)出現(xiàn)很多接近0的數(shù)據(jù)，這樣會(huì)降低后續(xù)聚類(lèi)操作的準(zhǔn)確率[7]。所以需要根據(jù)實(shí)際情況對(duì)現(xiàn)有的極差歸一化方法進(jìn)行改進(jìn)，對(duì)數(shù)量級(jí)差進(jìn)行級(jí)放大，具體的操作過(guò)程如下：

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

（2） 比較[xmaxi]每個(gè)值的數(shù)量級(jí)，選擇數(shù)量級(jí)最小的值分別記為[xmaxs；]

（3） 對(duì)各個(gè)字段使用極差歸一化的方法對(duì)數(shù)據(jù)集進(jìn)行標(biāo)準(zhǔn)化，但在計(jì)算每個(gè)值[xi]與最小值[xmin]的差時(shí)，都乘以[xmaxs]對(duì)應(yīng)的數(shù)量級(jí)[Os]，即：

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

經(jīng)過(guò)極差的級(jí)放大后，得到的數(shù)據(jù)處于同一個(gè)數(shù)量級(jí)，這為后續(xù)的聚類(lèi)操作的準(zhǔn)確性提供了保障。

2.2.4 處理效果評(píng)價(jià)

在校園網(wǎng)日志文件經(jīng)過(guò)清理臟數(shù)據(jù)、數(shù)據(jù)歸并和數(shù)據(jù)標(biāo)準(zhǔn)化之后，原始數(shù)據(jù)集數(shù)量由原來(lái)的7 000萬(wàn)條變?yōu)楝F(xiàn)在的85萬(wàn)條，并且數(shù)據(jù)形式也更符合后續(xù)聚類(lèi)操作的要求。數(shù)據(jù)預(yù)處理工作有效地縮減了原始數(shù)據(jù)規(guī)模，并為后續(xù)聚類(lèi)操作做了鋪墊。

3 聚類(lèi)算法的設(shè)計(jì)

3.1 算法的選擇

聚類(lèi)算法的形式有很多種，不同的聚類(lèi)算法適合不同的原始數(shù)據(jù)集。例如K?均值法適合大數(shù)據(jù)集，K?中心點(diǎn)算法適合小數(shù)據(jù)集，BIRCH算法適用于數(shù)據(jù)分布呈凸形及球形的數(shù)據(jù)集等。根據(jù)校園網(wǎng)日志數(shù)據(jù)的情況，分別選擇K?均值算法，AGNES算法和DBScan算法對(duì)數(shù)據(jù)集進(jìn)行分析，并對(duì)比三種算法的執(zhí)行效率。

3.2 K?均值算法的實(shí)現(xiàn)

3.2.1 算法的輸入

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

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

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

對(duì)于兩個(gè)數(shù)據(jù)對(duì)象之間的相似度，可以通過(guò)他們間的相異性來(lái)定義和描述。一般而言，在計(jì)算兩個(gè)對(duì)象之間的相異性時(shí)，采用兩個(gè)對(duì)象之間的距離來(lái)計(jì)算。在計(jì)算簇中的個(gè)體對(duì)象與簇中心的距離時(shí)，通常采用歐式距離，其計(jì)算公式為：

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

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

3.2.2 算法的過(guò)程

K?均值算法的過(guò)程如下所示：

輸入：簇的數(shù)目[k，]包含[n]個(gè)對(duì)象的數(shù)據(jù)集

輸出：[k]個(gè)簇

過(guò)程：

（1） 從數(shù)據(jù)集中隨機(jī)選擇[k]個(gè)對(duì)象，將每個(gè)對(duì)象都作為一個(gè)簇的初始中心；

（2） 分配每個(gè)剩余對(duì)象到離他最近的簇中心所在的簇中；

（3） 計(jì)算每個(gè)簇中所有對(duì)象的均值向量，使其作為新的簇的中心；

（4） 重復(fù)步驟（2），步驟（3）過(guò)程，直到[k]個(gè)簇的中心不再發(fā)生變化或者準(zhǔn)則函數(shù)收斂；

（5） 返回各個(gè)聚類(lèi)的中心和成員。

K均值算法的時(shí)間復(fù)雜性為[O（tkn），t]代表迭代次數(shù)，[k]代表聚類(lèi)數(shù)，[n]代表樣本數(shù)。

3.3 AGNES算法的實(shí)現(xiàn)

3.3.1 算法的輸入

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

3.3.2 算法的過(guò)程

AGNES算法的過(guò)程如下：

輸入：簇的數(shù)目[k，]包含[n]個(gè)對(duì)象的數(shù)據(jù)集

輸出：[k]個(gè)簇

過(guò)程：

（1） 設(shè)置每個(gè)對(duì)象都作為一個(gè)初始簇；

（2） Repeat；

（3） 以兩個(gè)簇中最近的數(shù)據(jù)點(diǎn)為標(biāo)準(zhǔn)找到最近的兩個(gè)簇；

（4） 將兩個(gè)簇合并生成新的簇的集合；

（5） Until達(dá)到要求的簇的數(shù)目。

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

3.4 DBScan算法的實(shí)現(xiàn)

3.4.1 算法的輸入

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

3.4.2 算法的過(guò)程

DBScan算法的過(guò)程如下所示：

輸入：半徑[e，]包含[n]個(gè)對(duì)象的數(shù)據(jù)集，最少數(shù)目MinPts

輸出：生成達(dá)到所有密度要求的簇

過(guò)程：

（1） Repeat；

（2） 從數(shù)據(jù)集中找到一個(gè)未處理的點(diǎn)；

（3） IF找到的點(diǎn)是核心點(diǎn)，THEN找出全部從該點(diǎn)密度可達(dá)的對(duì)象，形成一個(gè)簇；

（4） ELSE找到的點(diǎn)是邊緣點(diǎn)（非核心對(duì)象），從本次循環(huán)中跳出，繼續(xù)尋找下一個(gè)點(diǎn)；

（5） UNTIL所有的點(diǎn)都被處理。

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

3.5 幾種聚類(lèi)算法執(zhí)行結(jié)果對(duì)比

3.5.1 效率對(duì)比

在樣本數(shù)達(dá)到4 000時(shí)，AGNES算法的執(zhí)行時(shí)間已經(jīng)是無(wú)窮大了，所以AGNES不適合數(shù)據(jù)量較大的聚類(lèi)。而DBScan算法和K?均值算法的執(zhí)行時(shí)間相對(duì)較快，特別是K?均值算法，在簇?cái)?shù)遠(yuǎn)小于數(shù)據(jù)集樣本個(gè)數(shù)時(shí)，K?均值算法的時(shí)間復(fù)雜性為[O（n）。]三種算法的執(zhí)行效率如圖2所示。

從圖2得出的結(jié)論：K?均值算法的執(zhí)行效率最高，遠(yuǎn)遠(yuǎn)優(yōu)于另外兩種算法。而AGNES算法的執(zhí)行效率非常低，不適合在大數(shù)據(jù)集上進(jìn)行聚類(lèi)運(yùn)算。

3.5.2 準(zhǔn)確率對(duì)比

AGNES算法和DBScan算法在聚類(lèi)準(zhǔn)確率上效果比較好，而K?均值算法的聚類(lèi)準(zhǔn)確率跟初始聚類(lèi)中心的選定有很大關(guān)系。而在實(shí)際操作中，能正確地選取聚類(lèi)中心是一件很困難的事情，因?yàn)樵诰垲?lèi)結(jié)果出來(lái)之前，很難預(yù)先確定聚類(lèi)中心的大概位置。所以，如果要在實(shí)際中使用K?均值算法，一定要解決這個(gè)問(wèn)題，讓初始聚類(lèi)中心貼近最終的聚類(lèi)中心，然后才能得到滿意的聚類(lèi)結(jié)果。

4 K?均值算法的優(yōu)化

4.1 優(yōu)化方案

因?yàn)镵?均值算法的執(zhí)行效率會(huì)比另外兩種聚類(lèi)算法高過(guò)很多，在數(shù)據(jù)量較大時(shí)這種效率優(yōu)勢(shì)會(huì)更加明顯，所以決定在K?均值算法的基礎(chǔ)上進(jìn)行優(yōu)化。設(shè)計(jì)優(yōu)化的方案有兩種，第一種是采用AGNES算法和K?均值算法結(jié)合的方式，這樣既能利用AGNES算法提高聚類(lèi)準(zhǔn)確率，又能兼顧K?均值算法的高效率。第二種優(yōu)化是利用MPICH2接口設(shè)計(jì)一種并行的K?均值算法，讓它在多機(jī)的環(huán)境下執(zhí)行，這樣可以顯著地提高執(zhí)行效率。

4.2 AGNES算法與K?均值算法的結(jié)合

使用AGNES算法和K?均值算法結(jié)合的方式，在執(zhí)行K?均值算法前，從原始數(shù)據(jù)中隨機(jī)抽出一部分?jǐn)?shù)據(jù)，并在這些抽出來(lái)的數(shù)據(jù)上運(yùn)行AGNES算法，然后將運(yùn)行結(jié)果得到的聚類(lèi)中心當(dāng)做K?均值算法的初始聚類(lèi)中心。具體過(guò)程如圖3所示。

4.3 K?均值算法并行實(shí)現(xiàn)

4.3.1 并行K?均值算法的實(shí)現(xiàn)

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

（1） 計(jì)算各個(gè)數(shù)據(jù)對(duì)象與各個(gè)類(lèi)中心之間的距離；

（2） 產(chǎn)生新的聚類(lèi)中心時(shí)，需要對(duì)每個(gè)類(lèi)中所有數(shù)據(jù)求和并取平均值。

隨著數(shù)據(jù)量的增加而導(dǎo)致計(jì)算時(shí)間延長(zhǎng)的處理階段主要是第一步，因此考慮并行處理這一過(guò)程來(lái)提高聚類(lèi)效率，降低算法對(duì)內(nèi)存的較高要求。

采取基于主從（Master/Slave）模式的數(shù)據(jù)并行策略。主程序運(yùn)行在一個(gè)主節(jié)點(diǎn)上，負(fù)責(zé)分配數(shù)據(jù)和匯總從其他節(jié)點(diǎn)產(chǎn)生的聚類(lèi)結(jié)果，生成新的聚類(lèi)中心。從程序運(yùn)行在其他節(jié)點(diǎn)上，處理主節(jié)點(diǎn)分配給自己的一部分?jǐn)?shù)據(jù)集。主從節(jié)點(diǎn)之間的通信通過(guò)MPICH2平臺(tái)實(shí)現(xiàn)，所以寫(xiě)程序時(shí)不用關(guān)注具體的并行通信細(xì)節(jié)，在很大程度上方便了編程。

首先，主節(jié)點(diǎn)先將數(shù)據(jù)集劃分后，連同現(xiàn)有的聚類(lèi)中心集一并發(fā)給各個(gè)從節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)接收到的數(shù)據(jù)集大小為整個(gè)數(shù)據(jù)集的大小/從節(jié)點(diǎn)數(shù)。各個(gè)從節(jié)點(diǎn)將接收到的數(shù)據(jù)集進(jìn)行聚類(lèi)，并把聚類(lèi)結(jié)果返還給主節(jié)點(diǎn)。這時(shí)主節(jié)點(diǎn)等待各個(gè)從節(jié)點(diǎn)的數(shù)據(jù)，一旦將所有從節(jié)點(diǎn)的聚類(lèi)結(jié)果收齊后，主節(jié)點(diǎn)計(jì)算各個(gè)類(lèi)的新的聚類(lèi)中心，然后和原聚類(lèi)中心通過(guò)計(jì)算誤差平方準(zhǔn)則函數(shù)進(jìn)行比較。如果原來(lái)的聚類(lèi)中心和新的聚類(lèi)中心之差小于給定的閾值，算法結(jié)束。否則主節(jié)點(diǎn)將重新劃分?jǐn)?shù)據(jù)集并分配給各個(gè)從節(jié)點(diǎn)，開(kāi)始新的一次迭代過(guò)程。

4.3.2 執(zhí)行結(jié)果

把多臺(tái)配置為Intel Core i3 3.2 GHz，4 GB RAM的計(jì)算機(jī)用100M/10M自適應(yīng)網(wǎng)卡連接起來(lái)，在系統(tǒng)上安裝好MPICH2構(gòu)成一個(gè)機(jī)群系統(tǒng)。使用C++實(shí)現(xiàn)這個(gè)算法，在這個(gè)機(jī)群系統(tǒng)的基礎(chǔ)上完成算法的驗(yàn)證實(shí)驗(yàn)。通過(guò)實(shí)驗(yàn)可以看出K?均值并行算法具有以下幾個(gè)特征：

（1） 當(dāng)[N=100K，p=2]時(shí)，并行算法的加速比是小于1的。也就是說(shuō)，由于數(shù)據(jù)量不夠大，數(shù)據(jù)分塊過(guò)多，各節(jié)點(diǎn)獲分配的數(shù)據(jù)量比較少，并行計(jì)算粒度過(guò)小，導(dǎo)致計(jì)算與通信比值下降，從而造成并行算法的執(zhí)行時(shí)間不如串行算法。

（2） 當(dāng)[N>100K][且2≤p≤4]時(shí)，并行算法在絕大多數(shù)情況下加速比大于1。當(dāng)輸入數(shù)據(jù)規(guī)模增大，每個(gè)節(jié)點(diǎn)的運(yùn)算量增加時(shí)，并行算法的優(yōu)勢(shì)就體現(xiàn)出來(lái)了，這時(shí)并行算法的執(zhí)行時(shí)間要優(yōu)于串行算法。

（3） 當(dāng)[N>100]K且[p=3]時(shí)，算法的加速比達(dá)到了最高值，即3為理想節(jié)點(diǎn)數(shù)。當(dāng)再增加節(jié)點(diǎn)數(shù)目，因?yàn)楦鱾€(gè)節(jié)點(diǎn)之間的通信量增加，加速比開(kāi)始下降，當(dāng)[p=5]時(shí)，加速比開(kāi)始小于1，也就意味著并行算法的效率小于串行算法。

4.3.3 提高并行性能的方法

通過(guò)對(duì)K?均值并行算法的設(shè)計(jì)與實(shí)現(xiàn)，發(fā)現(xiàn)在PC機(jī)群網(wǎng)絡(luò)并行的環(huán)境下，要提高并行算法的執(zhí)行效率，需要注意以下兩點(diǎn)：

（1） 計(jì)算機(jī)節(jié)點(diǎn)數(shù)人。在計(jì)算機(jī)節(jié)點(diǎn)數(shù)目較少時(shí)，增加計(jì)算機(jī)節(jié)點(diǎn)數(shù)會(huì)提高并行度，提高并行算法的執(zhí)行效率。

（2） 應(yīng)該盡量加大每個(gè)節(jié)點(diǎn)的預(yù)算量并減少節(jié)點(diǎn)間的通信，即采用粗粒度的并行算法。

5 系統(tǒng)的應(yīng)用

5.1 統(tǒng)計(jì)分析

將預(yù)處理后的日志文件以散點(diǎn)圖的形式顯示出來(lái)?？梢钥吹剑瑤缀?9%以上的數(shù)據(jù)都集中在左下角，這表明校園網(wǎng)用戶在進(jìn)行網(wǎng)絡(luò)訪問(wèn)時(shí)，對(duì)于大部分的網(wǎng)站用戶訪問(wèn)流量低且點(diǎn)擊次數(shù)少。這個(gè)統(tǒng)計(jì)結(jié)果也是符合事實(shí)的，因?yàn)槿藗兩暇W(wǎng)時(shí)，只有個(gè)別非常有名的網(wǎng)站，會(huì)讓用戶長(zhǎng)時(shí)間訪問(wèn)而造成大量的上行和下行流量，或者讓用戶頻繁地訪問(wèn)。隨著搜索引擎的普遍使用，用戶對(duì)于某些信息的搜索會(huì)查詢大量的網(wǎng)站，對(duì)于大部分網(wǎng)站來(lái)說(shuō)，用戶只會(huì)訪問(wèn)有限的幾次，甚至絕大部分網(wǎng)站用戶在很長(zhǎng)一段時(shí)間內(nèi)只會(huì)訪問(wèn)一次，說(shuō)明校園網(wǎng)用戶的訪問(wèn)呈現(xiàn)出流量少和訪問(wèn)次數(shù)少的特點(diǎn)。

校園訪問(wèn)的網(wǎng)站點(diǎn)擊流量和次數(shù)分布如圖4所示。

5.2 聚類(lèi)分析

應(yīng)用本文研發(fā)的系統(tǒng)對(duì)校園網(wǎng)日志文件進(jìn)行聚類(lèi)分析，然后得出校園網(wǎng)用戶的網(wǎng)絡(luò)行為。為了讓聚類(lèi)既準(zhǔn)確又快速，采用AGNES+K?均值合并算法，同時(shí)K?均值算法部分采用并行實(shí)現(xiàn)。通過(guò)分析，本系統(tǒng)可以通過(guò)分析訪問(wèn)日志而得出各類(lèi)網(wǎng)站的訪問(wèn)狀況，進(jìn)而得知校園網(wǎng)用戶的上網(wǎng)行為?？梢灾?，校園網(wǎng)用戶訪問(wèn)最多的網(wǎng)站是bit.edu.cn，而訪問(wèn)量最大的網(wǎng)站是幾個(gè)視頻網(wǎng)站。利用本系統(tǒng)對(duì)校園網(wǎng)日志文件進(jìn)行聚類(lèi)，其結(jié)果有助于分析校園網(wǎng)用戶的上網(wǎng)行為，了解他們的喜好。校園網(wǎng)管理者可以根據(jù)分析的結(jié)果對(duì)校園網(wǎng)結(jié)構(gòu)進(jìn)行調(diào)整，從而更好地為校園網(wǎng)用戶服務(wù)。

6 結(jié) 論

本文介紹了一種基于聚類(lèi)算法的校園網(wǎng)用戶行為分析技術(shù)，在分析日志文件的過(guò)程中，系統(tǒng)采用的核心算法為聚類(lèi)算法。首先設(shè)計(jì)了系統(tǒng)的總體結(jié)構(gòu)，提出了分析模型，然后設(shè)計(jì)并實(shí)現(xiàn)了對(duì)校園網(wǎng)日志數(shù)據(jù)進(jìn)行預(yù)處理的模塊，通過(guò)處理臟數(shù)據(jù)，數(shù)據(jù)歸并，數(shù)據(jù)標(biāo)準(zhǔn)化等操作篩選出有效的數(shù)據(jù)，為數(shù)據(jù)挖掘做準(zhǔn)備。進(jìn)一步，根據(jù)當(dāng)前的校園網(wǎng)實(shí)際運(yùn)行情況，提出了校園網(wǎng)行為分析系統(tǒng)的創(chuàng)建意義，然后設(shè)計(jì)并實(shí)現(xiàn)了K?均值，AGNES，DBScan幾種聚類(lèi)算法，并對(duì)K?均值算法進(jìn)行優(yōu)化。最后介紹了本系統(tǒng)的應(yīng)用方法，并根據(jù)系統(tǒng)的執(zhí)行結(jié)果分析了校園網(wǎng)用戶的上網(wǎng)行為。

參考文獻(xiàn)

[1] 丁青，周留根，朱愛(ài)兵，等.基于K?means聚類(lèi)算法的校園網(wǎng)用戶行為分析研究[J].網(wǎng)絡(luò)新媒體技術(shù)，2010，31（6）：74?80.

[2] 馬艷英.基于遺傳算法的Web文檔聚類(lèi)算法[J].現(xiàn)代電子技術(shù)，2016，39（1）：148?152.

[3] 羅軍鋒，洪丹丹.基于數(shù)據(jù)抽樣的自動(dòng)K?means聚類(lèi)算法[J].現(xiàn)代電子技術(shù)，2014，37（8）：19?21.

[4] 步媛媛，關(guān)忠仁.基于K?means聚類(lèi)算法的研究[J].西南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2009（1）：198?200.

[5] 王燕，吳灝，毛天宇.基于K?中心點(diǎn)聚類(lèi)算法的論壇信息識(shí)別技術(shù)研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（1）：210?212.

[6] 劉興光.基于云計(jì)算的大型校園互聯(lián)監(jiān)測(cè)系統(tǒng)設(shè)計(jì)[J].現(xiàn)代電子技術(shù)，2015，38（24）：90?93.

[7] 張建文，徐瓊，王強(qiáng).基于MPI環(huán)境的并行程序設(shè)計(jì)[J].東華理工學(xué)院學(xué)報(bào)，2007，30（1）：81?84.

[8] 呂元海，孫江輝，馬龍.基于OracleRAC的校園網(wǎng)數(shù)據(jù)庫(kù)集群系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2016，39（4）：72?75.