基于改進預測強度的大數據K—均值聚類方法

蔡洪山 許峰

摘要：為了降低偶然因素的影響，提出了一種基于改進預測強度的大數據K-均值聚類方法，其基本思想是：首先將數據集若干等分，每一等分輪流作為測試集，取其平均預測強度，然后根據預測強度確定聚類數和聚類變量，再用K-均值聚類方法對數據集進行聚類。用上述方法研究了訪客在某網站各欄目的平均停留時間，結果表明，基于預測強度的聚類方法較常規聚類方法更適宜于大數據的聚類分析。

關鍵詞：大數據；K-均值聚類；預測強度；網站欄目關注度

DOIDOI：10.11907/rjdk.161106

中圖分類號：TP301

文獻標識碼：A 文章編號：1672-7800（2016）005-0004-03

0 引言

聚類是數據挖掘中的重要問題，也是大數據分析的核心問題之一。K-均值聚類算法是一種應用非常廣泛的聚類方法，由于此算法并不需要計算點之間的距離，因而對于大數據，K-均值聚類算法往往可以得到比其它聚類算法更快的收斂速度。但K-均值聚類算法有兩個缺陷，一是需要事先確定聚類數，二是受初始聚類中心的影響較大。

近年來，許多學者從不同的角度對大數據K-均值聚類算法進行了研究。卞亦文[1]提出了一種基于黃金分割法的K-means聚類算法，該算法可在一定程度上自動確定聚類個數；陳麗敏等[2]提出了一種基于加速迭代的大數據集譜聚類算法；沈詩嫫[3]研究了初始聚類中心的選擇問題，提出了一種基于小世界網絡選取初始聚類中心的K-means聚類方法；陳思慧[4]提出了一種基于層次劃分的大數據聚類算法；古凌嵐[5]提出了一種基于數據集劃分的大數據聚類方法；李雄[6]提出了一種并行化加權AP聚類算法，降低了算法的時間復雜度。

本文利用數據集等分思想，對基于預測強度的大數據K-均值聚類算法進行了改進，并通過實例對改進算法進行了性能測試。

1 基于BIC準則的模型分析

本文進行聚類分析的數據為某網站的后臺數據，共有2 861行，15個變量。每一行代表一位網站訪客，15個變量代表訪客在網站的15個欄目上的平均停留時間。為方便起見，將15個欄目記為e1～e15。圖1給出了訪客在e1欄目上平均停留時間的頻率直方圖。

在進行聚類時，有許多聚類變量供選擇，如何選擇聚類變量稱為模型的選擇。選擇模型時的準則通常有AIC準則（Akaike Information Criterion）、BIC準則（Bayesian Information Criterion）和HQ準則（Hannan-Quinn Criterion）。本文采用BIC準則，BIC隨變量數即模型和聚類數變化曲線如圖2所示。

從圖2中可以看出：①隨著聚類數的增加，BIC單調上升，并沒有明顯的單峰現象，這表明在本問題中，BIC準則對于聚類數的選擇沒有作用；②當聚類數大于4時，BIC增加得較為平穩，即聚類數的增加已經對模型的解釋沒有更大的貢獻，這表明最優聚類數應該接近于4，但此方法并不能給出精確的取值。

預測強度計算過程如下：①將待聚類原始數據隨機分成訓練集和測試集；②取聚類數為k，對上述兩個子集進行聚類，聚類結果記為I型聚類；③用訓練集的聚類結果對測試集進行判別，結果記為II型聚類；④在測試集自身聚成的每個類中，考查任一對樣本點i和i′是否在II型聚類中被錯分在不同的類，并記錄被正確劃分的比例；⑤在上述k個比例構成中，最小者即為當前聚類數k下的預測強度。

顯然，預測強度的直觀含義是當前聚類結果能正確預測新樣本點的能力。在實際中，可以預測強度為目標函數，以聚類數和變量子集為影響預測強度的因素，通過選擇適當的聚類數和變量子集，使預測強度最大化。

2.2 改進的預測強度

在預測強度的計算過程中，因為訓練集和測試集是隨機劃分的，所以某些偶然因素可能對預測強度的計算結果產生較大影響。為了降低偶然因素的影響，本文采用一種改進方法計算預測強度，具體做法為：首先將數據集隨機分為若干等分，將每一等分輪流作為測試集，求出各自的預測強度后，再取其平均值為這一聚類數下的預測強度。

2.3 基于預測強度的模型分析結果

不同變量數和聚類數下的預測強度變化曲線如圖3所示。

從圖3（f）中可以看出，當聚類變量的個數為3時（變量子集為{e1，e2，e4}），整條預測強度曲線都維持在一個很高的水平上。特別地，當聚類數為4時，預測強度達到了全局最大值，這表明最優聚類方案是選取e1、e2、e4為聚類變量，聚類數為4。

3 聚類結果及分析

確定最優聚類方案后，即可利用K-均值聚類方法對原始數據進行聚類。4類訪客在各欄目上的平均停留時間如圖4所示。

從圖4中可以看出，第一類訪客幾乎在所有欄目上的平均停留時間都較長，都超過其它3類，說明這類訪客屬該網站的高端忠實客戶；第二類訪客僅僅在第2、4欄目上的停留時間較長，表明這類訪客屬于專業訪客，一般只對某幾個特定欄目感興趣，關注程度較高；第三類訪客在每個欄目上的停留時間都不太長，且相差不大，表明這類訪客屬一般訪客，對欄目沒有特殊興趣；第四類幾乎在所有欄目上的停留時間都非常短，表明這類訪客屬典型的游客，對每個欄目都匆匆而過。由此可見，基于改進預測強度的K-均值聚類方法對實例中大數據的聚類結果是可信且有實際意義的。

4 結語

在K-均值聚類算法的基礎上，引入了改進的預測強度，并以此確定聚類變量和聚類數。對網站欄目平均停留時間的聚類分析表明，這種改進的大數據聚類方法的聚類結果具有較為明確的實際意義，較常規聚類方法更適宜用來進行大數據的聚類分析。

需要指出的是，大數據聚類算法的理論基礎還很薄弱，理論體系尚不完善，本文對新算法的性能研究也只能依賴于對具體實際問題的聚類分析結果，至于算法的收斂性和復雜度的理論分析則有待進一步研究。

參考文獻：

[1]卞亦文.大樣本數據聚類的改進方法[J].統計與決策，2009（1）：12-13.

[2]陳麗敏，楊靜，張健沛.一種加速迭代的大數據集譜聚類方法[J].計算機科學，2012，39（5）：172-176.

[3]沈詩嫫.文本數據聚類算法的若干關鍵技術及應用研究[D].南寧：廣西大學，2013.

[4]陳思慧.基于MIP和改進模糊K-means算法的大數據聚類設計[J].計算機測量與控制，2014，22（4）：1270-1275.

[5]古凌嵐.面向大數據集的有效聚類算法[J].計算機工程與設計，2014，35（6）：2183-2187.

[6]李雄.面向大數據的數據挖掘算法研究[D].南京：南京郵電大學，2014.

[7]ROBERT TIBSHIRANI.Cluster validation by predication strength[J].2001.http：//citeseerx.ist.psu.edu/viewdoc/summary？ Doi=10.1.1.24.2960.

（責任編輯：孫 娟）

Abstract：In order to reduce the influence of accidental factor，a large data K-means clustering method based on improved prediction strength is put forward.The basic idea of method is that first data set is divided into equal parts，and each part is set up test set in turn.The average strength prediction is computed，and clustering number is determined according to the strength prediction，then K-means clustering method is applied for data set.By means of the above method，the average residence time of the visitors in a website is studied.The results show that the clustering method based on the prediction strength is more suitable for the cluster analysis of large data.

Key Words：Big Data；K-Means Clustering；Prediction Strength；Website Column Access Analysis