基于Ｋ－ｍｅａｎｓ算法的校園網用戶行為聚類分析

摘要:在給出K-means算法流程的基礎上，以校園網認證計費系統日志為研究對象，實現一個基于K-means算法的校園網用戶行為聚類分析，得到不同特征的用戶組，為今后進一步了解用戶行為特征#65380;更好制定校園網絡策略奠定基礎#65377;

關鍵詞:K-means; 聚類分析;用戶行為

中圖分類號:TP311文獻標識碼:A

1引言

“用戶行為分析”作為一種有效的管理和決策支持方法，可以定性地分析用戶的群體構成和各自的愛好，對于提高網絡服務的效率和個性化程度極為重要#65377;如何分析用戶行為，改善校園網絡的性能，提高用戶使用網絡的效率已成為校園網絡管理的一個重要課題#65377;

本文以廣西大學校園網認證計費系統日志為研究對象，利用數據挖掘方法中的K-means算法對校園網用戶校園網用戶行為進行聚類分析#65377;

2聚類分析和K-means算法

K-means算法屬于聚類方法中的一種劃分方法，該算法具有較好的可伸縮性和很高的效率，適合處理大文檔集#65377;

該算法形式描述為[1]:已知d維空間Rd，在Rd中定義一個評價函數E∶{p∶pC}→R+，給每個聚類一個量化的評價，輸入Rd中的對象集合C和一個整數，k要求輸出C的一個劃分:C1，C2，…，Ck，這個劃分使得評價函數E最小化#65377;不同的評價函數將產生不同的聚類結果，本文采用均方差作為評價函數，定義如下:式中，E為數據庫中所有對象的平方誤差的總和，p為Rd空間的點，表示給定的數據對象，mi為簇Ci的平均值(p和mi都是多維的)，|p-mi|2表示數據對象與聚類中心之間的距離#65377;

此評價函數使所獲得的k個聚類具有以下特點:各聚類本身盡可能緊湊，而各聚類之間盡可能分開#65377;

以下是K-means算法的流程:

第一步:首先輸入K-means算法的聚類個數k，以及包含n個數據對象的數據庫;第二步:從n個數據對象任意選擇k個對象作為初始聚類中心;第三步:而對于所剩下其它對象，則根據它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類;第四步:重新計算每個(有變化)聚類的均值(中心對象)，根據新的每個聚類對象的均值(中心對象)，計算每個對象與這些新聚類中心對象的距離，并根據最小距離重新對相應對象進行劃分;第五步:循環第四步直到每個聚類不再發生變化為止，即方差評價函數開始收斂為止#65377;輸出滿足方差最小標準的k個聚類#65377;

例如[2]，當k=3時，即需要將數據對象C聚類為3個簇，根據算法描述，任意選擇3個對象作為3個初始簇中心，簇中心在圖中用“+”來標注，根據與簇中心的距離，每個對象被分配給最近的一個簇，這樣的分布形成了圖1(a)中虛線所描繪的的圖形#65377;這樣的分組會改變聚類中心，也就是說，每個聚類的平均值會根據類中的對象重新計算#65377;依據這些新的聚類中心，對象被重新分配到各個類中，這樣的重新分配形成了圖1(b)中虛線所描繪的輪廓#65377;重復以上的過程，產生圖1(c)的情況，最后，當沒有對象的重新分配發生時處理過程結束，聚類的結果被返回#65377;

圖1基于k-means算法的一組對象的聚類

3K-means算法的實現

根據K-means算法的流程，本文采用C++語言實現的K-means算法的主函數如下:其中System::LoadPatterns(char *fname)為數據輸入函數，用于從文本文件中讀入聚類樣本數據#65380;樣本維數以及聚類個數k，并保存在動態生成的數組#65377;

System::KMeans()是實現K-means算法的主要函數，實現了K-means算法流程的第二步到第五步#65377;程序描述如下:

日志文件記錄了用戶登錄網絡的用戶名#65380;上網時間等信息#65377;

根據實際需要從日志文件提取上網時間#65380;下網時間#65380;上行流量#65380;使用網絡時間#65380;源IP地址#65380;下行流量#65380;國際流量#65380;國內流量#65380;國際下載流量#65380;國內下載流量這10個信息作為聚類分析的特征值#65377;在日志文件中有很多記錄的國際流量或國內流量小于1M，它們屬于不活躍的記錄，數據預處理時應去掉這部分記錄#65377;為更好的找出用戶在一天里上網的規律，只取時分不取日期#65377;另外，由于校內用戶的IP地址前兩個字節相同，故只取IP地址的后兩個字節作為有效輸入#65377;將2005年12月至2006年7月的日志進行預處理完成后得到66079條有效記錄，聚類輸入文件格式如下:

輸入文件的第一行表示此數據文件的記錄數，即k-means算法中的樣本數據個數n;第二行表示每條記錄的特征項，即k-means算法中的樣本維數d;第三行表示k-means算法中的聚類個數k #65377;從第四行開始就是d維的n個樣本數據#65377;

4.2聚類結果

經過15次聚類后收斂，結果如表1所示#65377;

從表1中可以看出，當把校園網用戶分為4類時可以得出較為明顯的4組:

第一類所占比例最大，他們使用網絡的時間大約為80分鐘左右，通常上網時間是每天傍晚18:37左右，國際國內的流量不大，可以推測出上網的活動多為瀏覽網頁#65380;查找資料等動作，屬于普通活動#65377;

第二類上網時間跨度最大，國際國內流量很大，屬于上網時經常下載東西的一類#65377;

第三類的上網時間在夜間，國內下載流量最大，但這類活動所占比例最小#65377;

第四類所占比例僅次于第一類，上網時間集中在下午15:00左右#65377;

表1聚類結果

5小結

將k-means聚類算法應用于校園網用戶行為分析是一種嘗試，它的聚類結果可以給網絡管理人員對用戶的行為有所了解從而考慮制定相應的網絡策略#65377;但k-means算法只適用于均值有意義的情況，因此在進行數據預處理時，應盡可能多的選擇樣本特征項，即增加樣本的維數，并過濾異常#65380;無效的數據，因為k-means算法對這類數據很敏感，它們可能會影響到各聚類的均值#65377;k-means算法還有一個缺點就是用戶還必須事先指定聚類個數，如果聚類個數定義不準確將會使聚類結果不合理#65377;

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。