基于K-Means 算法的Web 日志用戶聚類研究*

陳 洲 陸 南

（江蘇科技大學電子信息學院 鎮江 212003）

1 引言

國際數據公司（IDC）曾經發布報告稱［1］，數字世界（digital universe）項目統計得出全球數據總量預測在2020 年達到44ZB。大數據時代，為了良好的用戶體驗及網絡站點優化，需要對Web服務站點的日志文件進行挖掘，分析元數據規律，從中發現有用知識。

用戶聚類是在對元數據進行預處理的基礎上，對具有相同行為模式的用戶進行聚類［2］。為了將具有相同瀏覽行為的用戶分成一組，田園［3］等在通過對數據文本的預處理后，得到用戶會話序列矩陣集合，然后對樣本進行聚類分析。

劉琦［4］等通過建立Web 頁面的用戶訪問矩陣，此會話矩陣是通過日志記錄中用戶對頁面的訪問情況為依據而建立，然后運用最大樹算法將構造的模糊相似矩陣進行聚類，此方法適用于處理高維數據，簡單快速。

K-Means 算法作為無監督學習算法，在商業、人工智能等領域異?；钴S，隨著Web 挖掘的發展，在數據挖掘領域也被廣泛應用，雖然K-Means算法簡單，但還存在著許多不足，其中最為嚴重的是初始中心點的隨機選取，對此，韓凌波［5］等提出了一種改進的基于密度的尋找初始聚類中心的改進算法，該算法引入密度參數的概念，把Iris數據集的聚類測試結果提高到了83.33%。

后來，基于旋轉算法的思想，崔丹丹［6］提出坐標旋轉算法來尋找初始中心點，即通過找到的第一個初始中心點，根據所劃分的類簇數目，通過坐標旋轉的方式找到下一個中心點，該算法在一定程度上降低了噪聲數據點的影響。

隨著數據量的不斷增加，基于K-Means的Web日志挖掘研究形勢更加嚴峻，以上幾種方法一定程度上提高了算法聚類精確度，但并沒有解決在構建用戶會話矩陣后存在的孤立點的問題，在分析大數據量的文本時也有一定的缺陷。

本文提出的ICKM 算法利用密度參數最大的對象作為第一中心點，利用KCR 算法尋找下一個中心點；為了提高大數據環境下的計算速度，算法與Hadoop的MapReduce計算框架［7］相結合，通過框架承載數據的計算壓力；同時，該算法也充分考慮用戶聚類過程中建立的會話矩陣孤立點的影響，在一定程度上提高了運算速度與準確度。

2 數據挖掘與K-Means算法

2.1 Web日志挖掘

Web 日志挖掘的目的是從大量的服務器日志文件中，通過各種挖掘算法，最終得到用戶所需要的知識［8］。這個過程大概分成三部分，本文只涉及其中的數據清洗，即對日志數據進行用戶訪問日志的數據清洗從而建立用戶會話矩陣［9］。

2.2 算法原理

K-Means算法簡單，為聚類問題提供了一種解決方案：把數據集合中的n 個樣本點（實例）劃分到k 個集群中，使每一個點都屬于離它最近的均值對應的集群中，使每個集群中的點（實例）存在高關聯度，使每個集群之間的對象存在低關聯度［10］。

算法開始之前，首先確定將數據集合劃分為幾個集群，然后確定初始中心點，而中心點是從數據集合中隨機選取，隨后再根據相似性度量函數計算集合中其他點到K 個初始聚類中心點的距離，將數據對象放到距離最近的集群中，其中常用的度量函數為歐式距離［11］：

其中xi，xj代表集群中任意兩個樣本，接著更新每個集群的中心點：

不斷重復，直到誤差平方和（SSE）準則函數收斂，即

其中，P表示給定的數據樣本點，m是第i個集群Ci的均值。

2.3 基于K-Means的用戶聚類

用戶聚類實質上是根據用戶訪問頁面、服務器的行為，將相同行為的用戶聚合為一類，進而分析討論該類用戶所具有的特點。而要實現用戶聚類，首先通過數據預處理對Web日志進行相應操作，進而生成＜用戶集合，頁面集合＞的相關矩陣［12］，然后將其轉化為用戶序列矩陣并采用K-Means 算法進行分析。

根據用戶在一段時間內對頁面、服務器的訪問次數，構建會話矩陣即分析用戶ci對頁面pi的偏好程度，構造原始數據會話矩陣如下：

其中v表示一個會話記錄，可以看到，在利用算法對矩陣進行分析時，孤立點的影響對分析結果有消極影響甚至是無用的，而在尋找初始中心點時，由于孤立點（噪聲點）的存在，會使得尋找的初始中心點和真正的聚類中心點偏離較大。

3 改進的K-均值聚類算法

盡管K-Means具有很多優點，但算法需要隨機選取初始中心點，初始點的選擇不當、遠離數據集的孤立點都可能會影響聚類結果，使結果陷入局部最優解［13］。為了解決以上問題，韓凌波等提出了基于密度參數的尋找初始聚類中心的改進算法，該算法引入密度參數的概念，可此算法并未考慮稀疏數據點及孤立點的影響，本文將坐標旋轉算法與之結合，使中心點的選取不通過均值來選取，減少噪聲點的影響。

算法解決的問題：通過ICKM 確定初始中心點，將數據樣本點集合x{x1，x2，…，xn}劃分到k個集合中，使得誤差平方和最小且不再變化［14］。

定義1數據對象xi和xj之間的距離可表示為

其中，S為樣本協方差矩陣。

定義2以空間中任意一點xi為中心，半徑為r畫圓，此區域稱為點xi的鄰域，在空間點xi的鄰域內點的個數稱為點xi基于距離r的密度參數，記dins(xi，r)。

ICKM將馬氏距離作為衡量數據對象間相似度的函數，空間內任意一點的密度參數越大，說明此點所在區域點數越多，選取此點作為中心點誤差函數越容易收斂。

定義3誤差平方和函數［15］：

定義4準確率：

其中m為準確放到指定集合中對象的個數，N為集合中對象的總數。

利用ICKM 完成初始中心點的選取并進行聚類的步驟如下：

輸入：數據集x{x1，x2，…，xn}，聚類數目k

輸出：完成聚類后的k個類簇及誤差

Step1：初始中心點的選取

1）利用式（1），計算兩對象之間的距離，記為d(xi，xj)。

2）計算每個對象的密度參數dins(xi，r)，從小到大排列，記為集合D。

3）取集合D中最大密度參數對應的對象作為第一個中心點C1。

4）取距離C1最大且密度值較大的對象C2。

5）計算C1到C2的距離R12，并計算兩點的中心點C12，以C12為圓心，R122 為半徑，C1（C2）為起始點，順時針旋轉2π/k得到新的坐標點Cnew，取距離點Cnew最近的數據點作為第二個聚類中心。

6）判斷聚類中心數是否等于k，等于則執行7），少于則以Cnew為參照點，執行5）。

Step2：執行K-Means算法

1）以這k個中心點作為初始簇中心，計算所有數據到簇中心的距離。

2）將數據對象分配到距離最近（相似度最高）的簇。

3）計算各簇內數據的平均值，更新簇中心。

4）不斷重復，直到準則函數收斂，算法結束。

由算法原理可以看出，為了彌補制約坐標旋轉算法的稀疏數據區域及孤立點的影響，ICKM 利用密度、距離相結合的方式確定第一個聚類中心，同時改進了旋轉算法由最大距離點選取圓心的做法，該算法考慮到孤立點與中心點的相對距離，又充分考慮孤立點分布上的稀疏性，同時用馬氏距離代替傳統歐氏距離，保證同類簇數據間的相似度。

4 仿真實驗

4.1 實驗描述

用戶聚類實際上是對拿到的服務器日志文件進行數據預處理，然后將處理過的數據運用聚類算法分析，最后得出結論。雖然數據預處理部分的數據噪音也會對結果產生一定的影響，本文為了證明ICKM算法的有效性，采用統一的數據集進行測試。

實驗樣本采用UCI 數據庫中Iris 數據集，該數據集包含150 條記錄，對應數據集的每行數據，Iris數據集是一個150 行5 列的二維表，為了保證實驗的正確性，修改此數據集每行數據包含每個樣本的兩個個特征和樣本的類別信息。

實驗首先確定將此數據集分成的類簇數目，我們規定將此數據集分成3 個種類，運用傳統算法及改進ICKM 算法進行共4 次實驗，提取每個實驗的樣本初始中心點、SSE、迭代次數以及算法的準確率，以此作為算法有效性的標準。

為了驗證大數據環境下ICKM 的計算能力，本文將 ICKM 算法和 MapReduce 計算框架相結合［16］，共同承載計算壓力，為了驗證其有效性，實驗采用不同大小規格的數據文件，對兩種算法進行測試，提取聚類分析所需要的時間。

本文的實驗性能參數主要有4 個：SSE、迭代次數、準確率以及大數據環境下得出結果所用的時間。

SSE：集合中心不再變化時，每個樣本群的數據誤差。

迭代次數：聚類結束時，集合樣本所循環的次數，根據此參數，可有效判斷算法性能。

準確率：能夠正確到相應集合中的樣本所占比數。

時間：聚類所需時間。

4.2 實驗結果及分析

將150 個數據樣本點作為傳統算法的輸入，將此劃分為3個類簇，所得出的結果如表1所示。

表1 KM算法對Iris數據集實驗結果詳情

由上表可以看出，針對傳統聚類算法，在進行的3 次重復實驗中，所需要的初始中心點都是隨機生成，而誤差最高達到3.84，聚類準確率較高，可達到88.6%，可得出此聚類結果卻進行了9 次迭代過程，可以想象在大數據環境下此傳統方法存在的計算速度缺陷。

以上實驗，初始中心點都是隨機選取，現將數據樣本作為ICKM 算法的輸入，同樣劃分為3 個類簇，所得出的結果如表2所示。

表2 ICKM算法對Iris數據集實驗結果詳情

由表可知，針對同樣的數據集，改進的算法正確率高達90.1%；使用改進算法進行聚類的4 次迭代次數遠遠小于傳統算法的9 次；改進的算法誤差SSE 與傳統算法的最小誤差平齊，以上結果可得出，ICKM 算法在算法準確率及迭代次數上比傳統算法理想，結合誤差，改進后的ICKM 算法在效率及準確率上相對較好。

算法實現并行化的基本思路是［17］：每一次迭代啟動一個計算過程，文件內數據按行存儲，也可以按行分片，聚類分析的樣本距離計算和數據歸類步驟分別由Map、Reduce執行。

為了檢驗ICKM 的MapReduce 并行化即大數據處理能力，實驗增加樣本數量，采用了不同大小的數據文件，對ICKM 及傳統聚類算發分別進行測試，最終提取得到聚類結果時所需要的時間，聚類結果的準確性，本實驗暫不考慮，實驗結果如表3所示。

由表可知，實驗用不同大小的樣本文件測試在大數據環境下不同算法的計算能力，可以看到，實現了 MapReduce 并行化［18］的 ICKM 算法在計算能力、計算速度上明顯加快。

表3 大數據下算法處理能力實驗結果詳情

5 結語

本文針對K-Means 算法在選取初始中心點上存在的問題，以及在用戶構建會話矩陣后存在的孤立點的問題，提出了密度參數與坐標旋轉算法相結合的ICKM 算法，該算法利用密度參數最大的對象作為第一中心點，利用KCR 算法尋找下一個中心點，在一定程度上避免了孤立點對數據樣本的影響，充分考慮用戶聚類過程中建立的會話矩陣孤立點的影響的同時運用馬氏距離改進了類簇內數據的相似程度。

為了提高大數據環境下的計算速度，通過借助MapReduce 計算模型實現算法的并行計算，通過框架承載數據的計算壓力在一定程度上提高運算速度與準確度［19］。通過實驗分析，改進后的算法較傳統聚類算法有較高的準確性與穩定性。

本文利用密度參數和坐標旋轉的思路，在一定程度上降低了孤立點對初始中心點選取的影響，但并未充分考慮算法處理高維數據的能力，再加上數據量的增加，可能存在大數據高緯度處理速度緩慢的問題，下一步工作中，可借助最大數算法［20］及在大數據環境下借助hive、spark等計算框架［21］進行優化，增加其大數據處理能力。