基于改進預(yù)測強度的大數(shù)據(jù)K—均值聚類方法

蔡洪山 許峰

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

關(guān)鍵詞：大數(shù)據(jù)；K-均值聚類；預(yù)測強度；網(wǎng)站欄目關(guān)注度

DOIDOI：10.11907/rjdk.161106

中圖分類號：TP301

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

0 引言

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

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

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

1 基于BIC準則的模型分析

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

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

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

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

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

2.2 改進的預(yù)測強度

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

2.3 基于預(yù)測強度的模型分析結(jié)果

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

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

3 聚類結(jié)果及分析

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

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

4 結(jié)語

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

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

參考文獻：

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

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

[3]沈詩嫫.文本數(shù)據(jù)聚類算法的若干關(guān)鍵技術(shù)及應(yīng)用研究[D].南寧：廣西大學(xué)，2013.

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

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

[6]李雄.面向大數(shù)據(jù)的數(shù)據(jù)挖掘算法研究[D].南京：南京郵電大學(xué)，2014.

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

（責(zé)任編輯：孫 娟）

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