基于改進K-means算法的商業(yè)用戶聚類分析

孫曄，孫潔

(1.凌拓(上海)商貿(mào)有限公司 北京分公司，北京 100020; 2.華北理工大學(xué) 電氣工程學(xué)院，河北 唐山 063000)

?

基于改進K-means算法的商業(yè)用戶聚類分析

孫曄1，孫潔2

(1.凌拓(上海)商貿(mào)有限公司 北京分公司，北京 100020; 2.華北理工大學(xué) 電氣工程學(xué)院，河北 唐山 063000)

K-means聚類算法；云計算；商業(yè)用戶；網(wǎng)絡(luò)存儲資源

在競爭激烈的市場環(huán)境下，為了更好分析商業(yè)用戶信息，贏得更多的商業(yè)用戶，需要進行海量大數(shù)據(jù)分析。本文針對傳統(tǒng)K-means算法自身初始聚類選取的缺陷和單機串行聚類算法的局限性，提出了一種改進的K-means聚類算法。結(jié)合當(dāng)前主流的開源云計算平臺Hadoop，把改進的算法并行化，克服了傳統(tǒng)串行聚類算法在海量數(shù)據(jù)處理時的不足，以某大型網(wǎng)絡(luò)存儲服務(wù)企業(yè)每日商業(yè)用戶網(wǎng)絡(luò)存儲資源使用量為實驗數(shù)據(jù)，驗證了算法的高效性和可行性。

0 引言

隨著改革開放力度的進一步加大，大量外資企業(yè)的引入，使得國內(nèi)商業(yè)競爭力急劇加大，商業(yè)用戶成為了競爭的焦點，誰擁有更多的客戶，就擁有更大的競爭力，隨著信息化時代的到來，人們已經(jīng)生活在數(shù)據(jù)的海洋中，在日常眾多商業(yè)行為中，涌現(xiàn)出了大量的商業(yè)用戶數(shù)據(jù)，如何分析這些數(shù)據(jù)，挖掘出隱藏在這些數(shù)據(jù)背后的信息，從而制定出更好的營銷商業(yè)策略來贏得更多的商業(yè)用戶，成為了當(dāng)前較熱門的研究重點[1]。

以往的商業(yè)用戶分析往往依靠簡單經(jīng)驗和統(tǒng)計方法，顯然已經(jīng)無法滿足當(dāng)前的需求，數(shù)據(jù)挖掘是利用某種數(shù)學(xué)算法來發(fā)現(xiàn)隱藏在數(shù)據(jù)背后的價值，完成從知識到價值的轉(zhuǎn)變，同時隨著數(shù)據(jù)量的增多，許多算法在海量數(shù)據(jù)處理時都遇到了瓶頸，云計算的出現(xiàn)又帶來了新的曙光，越來越多的學(xué)者采用云計算和數(shù)據(jù)挖掘相結(jié)合的形式處理當(dāng)前海量數(shù)據(jù)[2-4]。

聚類分析為數(shù)據(jù)挖掘中最常用的方法，聚類分析就是利用數(shù)學(xué)的方法達到分類的效果，把相似度大的分為一類而相似度小的分為一類，本文使用聚類分析和云計算相結(jié)合的方法達到商業(yè)用戶聚類分析的目的。

1 改進K-means聚類算法

K-means是一種以距離作為標(biāo)準(zhǔn)的聚類算法，該算法收斂快，可擴展且效率高，但存在原始簇心難選取，容易陷入局部最優(yōu)，同時傳統(tǒng)聚類算法都是針對單機串行聚類分析，很難應(yīng)對當(dāng)前海量商業(yè)用戶的聚類分析請求，針對這些缺陷，本文首先提出了初始簇心的選取方法，克服了K-means算法本身的缺陷，同時結(jié)合當(dāng)前主流的開源云計算平臺Hadoop，把提出的算法并行化，使其在海量數(shù)據(jù)面前變得游刃有余。

1.1 傳統(tǒng)K-means聚類算法

傳統(tǒng)K-means聚類算法的流程為：設(shè)共有K個簇，任意取K個數(shù)據(jù)為原始簇心，計算除原始簇心以外數(shù)據(jù)的距離，把數(shù)據(jù)分給到離簇心最近的聚類，然后以所有歸到各個類中樣本平均值作為新的簇心，重新計算距離，更新聚類，直到平方誤差函數(shù)小于給定的閥值[5]。

設(shè)集合A={x1,x2,...,xm}，xi={xi1,xi2,...,xin}，則有歐式距離dij：

(1)

(2)

1.2 K-means初始聚類選取

由于K-means算法采用隨機方式選取簇數(shù)和簇心，很容易使其局部最優(yōu)，對于初始簇數(shù)和簇心，本文提出如下的取辦法:

(1)初始簇心的選擇

(3)

其中d(xi,xj)為按照(1)公式計算的xi和xj2個對象之間的距離，其對象xi的密度Den(xi)有：

(4)

其中若Dis(A)-d(xi,xj)>0,則σ(x)=1，否則σ(x)=0，將所有密度生成密度集合D={Den(x1),Den(x2),...,Den(xn)}，選取密度最大的作為第一個簇心，即O1=max(D)，密度第二大的作為第2個簇心，依次類推指導(dǎo)選取到Ok為止。

(2)初始簇類個數(shù)的選擇

簇內(nèi)數(shù)據(jù)越緊密，簇間距越大，聚類效果越明顯，首先假設(shè)簇數(shù)為k，使用(1)步驟的方法選取簇心，將第i個簇內(nèi)元素間平均距離作為元素的分散程度，用ei代表，更新k值重復(fù)步驟(1)，使得下式值最小k值為最佳的簇數(shù)：

(5)

1.3 改進K-means聚類算法

使用云計算平臺Hadoop主要由HDFS(分布式文件系統(tǒng))和MapReduce計算模型組成，HDFS采用了主/從構(gòu)架，HDFS集群是由一個Namenode(管理節(jié)點)和若干個Datanode(數(shù)據(jù)節(jié)點)組成，其節(jié)點均是一臺普通PC。MapReduce是一種并行編程模式，包括Map階段和Reduce階段，在Map階段，各節(jié)點服務(wù)器以已經(jīng)分割好若干個數(shù)據(jù)塊作為輸入，對每塊中每條記錄執(zhí)行map函數(shù)，生成中間結(jié)果鍵值對，在Reduce階段，把Map生成的鍵值對作為輸入，執(zhí)行Reduce函數(shù)，最后生成新的鍵值對，最終把結(jié)果寫入HDFS中[6]。

具體實現(xiàn)方式如下：

(1)以行形式存儲商業(yè)用戶數(shù)據(jù)，任務(wù)管理節(jié)點按照本節(jié)提出的方法選取初始聚類，并將初始聚類發(fā)送到M個待執(zhí)行map函數(shù)，對數(shù)據(jù)初始化形成鍵值對形式，即原始數(shù)據(jù)為<商業(yè)用戶ID，商業(yè)用戶的信息>。

(2)每個Map函數(shù)計算到每個簇心的距離，把數(shù)據(jù)歸到離簇心最近的類中，Map函數(shù)輸入為<商業(yè)用戶ID，商業(yè)用戶的信息>，輸出為<聚類類別，商業(yè)用戶信息>。

(3)Combine的函數(shù)的作用為把key值相同的數(shù)據(jù)輸送給同一Reduce函數(shù)進行處理。

(4)每個Reduce函數(shù)中得到的均為相同聚類的數(shù)據(jù)，計算他們的平均值，以數(shù)據(jù)的平均值作為新的簇心重復(fù)步驟(2)到(4)，指導(dǎo)滿足收斂條件位置。

其程序流程圖如下所示：

圖1 改進K-means聚類算法流程圖

2 實驗仿真

實驗選用了由6臺PC搭建Hadoop云平臺，6臺PC均為雙核2.4GHz，2GB內(nèi)存。采用紅帽企業(yè)版Linux 6.0作為操作系統(tǒng)，JDK版本為1.6.0，Hadoop版本為1.2.1。每臺計算機使用千兆網(wǎng)卡，通過交換機連接。

實驗數(shù)據(jù)取自某大型網(wǎng)絡(luò)存儲服務(wù)企業(yè)每日商業(yè)用戶使用的網(wǎng)絡(luò)存儲資源情況，采樣時間為24日，共收集了10 000份數(shù)據(jù)，每份數(shù)據(jù)為24維，實驗部分源數(shù)據(jù)如下表所示：

表1 實驗源數(shù)據(jù)

實驗一

首先選取配置一致的2臺PC，1臺以單機形式實現(xiàn)聚類算法，另一臺為集群中的1個節(jié)點，從實驗源數(shù)據(jù)中隨機算取樣本數(shù)為500、1 000、2 000、4 000、8 000共5組實驗數(shù)據(jù)，分別進行單機環(huán)境下和集群環(huán)境下的聚類分析，對執(zhí)行時間對比，結(jié)果如下圖所示，可以得出數(shù)據(jù)規(guī)模較小時，單機情況下算法的效率好于集群情況，而隨著數(shù)據(jù)量的增大，單機情況下的效率急劇下降，而集群情況卻下降緩慢，這是因為數(shù)據(jù)量較少時，集群的主要耗時花在了任務(wù)的分配和節(jié)點的啟動上，但隨著數(shù)據(jù)量的增大，這一部分耗時顯得微乎其微，集群環(huán)境表現(xiàn)出了明顯的優(yōu)勢，通過實驗可以看出，在海量數(shù)據(jù)處理方面，集群環(huán)境現(xiàn)對于單機環(huán)境具有明顯的優(yōu)勢。

圖2 效率對比實驗結(jié)果

實驗二

結(jié)合本文提出的改進算法和實驗數(shù)據(jù)，對其進行聚類分析，結(jié)果如下，可以得出實驗數(shù)據(jù)被分為了3類，并且得到了每類的資源使用規(guī)律情況，企業(yè)可以根據(jù)每類的資源使用規(guī)律調(diào)整自己的資源和制定相應(yīng)的營銷策略，在提供更好服務(wù)同時贏得更多的商業(yè)用戶。

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

3 結(jié)論

(1)提出了一種改進K-means聚類算法，通過簡單實驗驗證了其在商業(yè)用戶聚類分析方面高效、可行，但仍然有一些不足，第一，實驗樣本量較小，其維度較低，通過更多的樣本進行實驗，其推廣價值會更大；第二，如果能對連續(xù)多期的數(shù)據(jù)進行研究，同時對商業(yè)用戶未來的行為進行預(yù)測，也是商業(yè)用戶流失管理所關(guān)心的內(nèi)容之一。

(2)在商業(yè)用戶聚類分析方面提出了一種新的思路，在商業(yè)用戶聚類分析的應(yīng)用是相對有效的，對于各類商業(yè)行業(yè)具有一定的指導(dǎo)意義，在今后的研究中可以設(shè)計更多的實驗和實驗樣本更加完善研究成果。

[1]牛勝利．基于數(shù)據(jù)挖掘的商業(yè)銀行客戶關(guān)系管理研究[D].北京：財政部財政科學(xué)研究所，2013.

[2]周文,井明洋等.中國云計算產(chǎn)業(yè)結(jié)構(gòu)和商業(yè)模式[D].上海大學(xué)學(xué)報:自然科學(xué)版.2013,19(1): 26-30.

[3]瞿小寧.K均值聚類算法在商業(yè)銀行客戶分類中的應(yīng)用[J].計算機仿真.2011,28(6):357-360.

[4]郭強. 海量用電數(shù)據(jù)并行聚類分析[J].遼寧工程技術(shù)大學(xué)學(xué)報:自然科學(xué)版.2016,35(1) :76-80.

[5]謝雪蓮,李蘭友.基于云計算的并行K-means聚類算法研究[J].計算測量與控制.2014,22(5):1 510-1512.

[6]常潤梅，孟利青，劉萬軍.電信企業(yè)云計算數(shù)據(jù)中心容量管理[J].遼寧工程技術(shù)大學(xué)學(xué)報:自然科學(xué)版.2013,32(8) : 1 112-1 117.

Clustering Analysis of Commercial Users Based on Improved K-means Algorithm

SUN Ye1, SUN Jie2

(1.Beijing Branch, Netapp (Shanghai) Commercial Co. Ltd, Beijing 100020, China;2. College of Electrical Engineering, North China University of Science and Technology,Tangshan Hebei 063009,China)

K-means clustering algorithm; cloud computing; business user; network storage resource

In the highly competitive market environment, in order to better analyze the commercial user information and win more commercial users, it is necessary to carry out mass data analysis. In this paper, we propose an improved K-means clustering algorithm based on the limitations of the traditional K-means algorithm and the limitations of single machine serial clustering algorithm. Combined with the current mainstream cloud computing platform Hadoop, the improved algorithm is paralleled, which overcomes the shortcomings of the traditional serial clustering algorithm in mass data processing. Use the large network storage service enterprise daily business user network storage resource as the experimental data, the effectiveness and feasibility of the algorithm is proved.

2095-2716(2016)01-0067-05

2015-09-30

河北省自然科學(xué)基金(ZD2014077)。

TP391.4

A