改進(jìn)K-means算法在B2C電子商務(wù)客戶細(xì)分中的應(yīng)用

時(shí)紅軍，韓兵

0 引言

在激烈競(jìng)爭(zhēng)的網(wǎng)絡(luò)商業(yè)時(shí)代，電子商務(wù)企業(yè)必須留住老顧客，發(fā)展新顧客并鎖定利潤(rùn)最高的客戶，預(yù)測(cè)客戶客戶未來的購買趨勢(shì)，制定相應(yīng)的營(yíng)銷策略和客戶管理策略。為了實(shí)現(xiàn)這個(gè)目標(biāo)，企業(yè)就需要盡可能地了解客戶的行為，盡可能收集顧客的信息，借助各種分析方法，透過無序的、表層的信息挖掘出內(nèi)在的知識(shí)和規(guī)律。利用聚類算法分析出具有相似瀏覽或購買行為的客戶群，并分析客戶的共同特征，進(jìn)而對(duì)客戶進(jìn)行細(xì)分，幫助電子商務(wù)企業(yè)了解自己的客戶，為客戶聚類群體提供更合適、更全面的個(gè)性化服務(wù)，選擇最有開發(fā)價(jià)值的目標(biāo)客戶群體，發(fā)現(xiàn)潛在客戶，集中企業(yè)優(yōu)勢(shì)，制定有效的營(yíng)銷策略[1]。

1 K-means聚類算法

聚類分析是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要分支。聚類分析是依據(jù)樣本間相關(guān)聯(lián)的度量標(biāo)準(zhǔn)，將其自動(dòng)分成幾個(gè)群組，且使同一群組內(nèi)的樣本相似，而屬于不同群組的樣本相異的一組方法[2]。

聚類分析能從客戶基本庫中發(fā)現(xiàn)不同的客戶群，并且用購買模式來刻畫每個(gè)客戶群的特征。在電子商務(wù)應(yīng)用中，聚類分析分為對(duì)客戶群體的聚類和對(duì) Web頁面的聚類。客戶群體的聚類是Web使用挖掘模式識(shí)別階段應(yīng)用較多的算法，它主要是按現(xiàn)有客戶對(duì)站點(diǎn)訪問的歷史行為進(jìn)行劃分,將具有一定相似度的客戶進(jìn)行聚類，得到聚類的結(jié)果模型，抽象出一個(gè)特殊客戶代表這個(gè)客戶聚類群體的特征。對(duì)于一個(gè)新來的客戶，運(yùn)用這個(gè)模型將新客戶歸入相應(yīng)的類別中。根據(jù)各個(gè)類別的特征有目的地進(jìn)行商品推薦，并跟蹤推薦效果。聚類算法在電子商務(wù)個(gè)性化服務(wù)的應(yīng)用中起著重要的作用。

為了實(shí)現(xiàn)對(duì)數(shù)據(jù)對(duì)象的分類，人們提出了許多不同的算法。目前，常用的聚類算法主要有以下幾種類型：劃分方法、層次方法、密度方法、模型方法和基于網(wǎng)格的方法。K-means算法是一種基于劃分的聚類方法，目的是通過在完備數(shù)據(jù)空間的不完全搜索，使得目標(biāo)函數(shù)取得極小值。但是該算法是一種局部搜索的聚類算法，算法的結(jié)果取決于初始聚類中心，而且該算法只能保證收斂到不動(dòng)點(diǎn)，不能保證函數(shù)收斂到目標(biāo)函數(shù)的極小值點(diǎn)。為了確定 K-means算法的初始聚類中心，提出多種不同的解決辦法，Adil M. Bagirov[3]借助輔助函數(shù)選取初始點(diǎn)，F(xiàn)uyuan Gao[4]等利用鄰域方法選擇初始聚類中心，Wei Li[5]也提出一種利用最大最小距離的方法選取初始距離中心。這些方法在一定程度上提高了K-means算法的性能，但在聚類準(zhǔn)確率都有待提高。文中提出了一種新的初始聚類中心的選取規(guī)則，使得初始聚類中心的分布盡可能體現(xiàn)數(shù)據(jù)的實(shí)際分布，提高了聚類質(zhì)量。

2 相關(guān)工作

K-means聚類[6]經(jīng)過反復(fù)迭代將數(shù)據(jù)集劃分成K個(gè)部分,K為希望得到的類數(shù),需預(yù)先指定.具體算法如下：設(shè)數(shù)據(jù)集：

X=個(gè)聚類中心為p1，p2，…，pk。數(shù)據(jù)點(diǎn)間的距離定義為：

目標(biāo)函數(shù)定義為：

算法流程如下：

輸入：數(shù)據(jù)集、聚類數(shù)目K

輸出：滿足目標(biāo)函數(shù)值最小的K個(gè)聚類

流程：

(1)從數(shù)據(jù)集中隨機(jī)選擇K個(gè)對(duì)象,每一個(gè)對(duì)象作為一個(gè)類的“中心” ,分別代表要分成的K個(gè)類；

(2)根據(jù)距離中心最近的原則,尋找與各對(duì)象最為相近的類,將其他對(duì)象分配到各個(gè)相應(yīng)的類中；

(3)針對(duì)每一個(gè)類,計(jì)算其所有對(duì)象的平均值，作為該類的新的“中心”；

(4)根據(jù)距離“中心”最近的原則,重新進(jìn)行所有對(duì)象到各個(gè)相應(yīng)類的分配；

(5)返回(3) ，直到目標(biāo)函數(shù)沒有變化為止。

“前景理論”自提出以來，被廣泛用來解釋各類風(fēng)險(xiǎn)決策行為。但是，在解釋“失地農(nóng)民再就業(yè)培訓(xùn)參與決策行為”上，單靠前景理論還不能給予更為具體的解釋。比如，在“編輯”階段，究竟編輯了哪些信息？在“評(píng)價(jià)”階段，究竟評(píng)價(jià)了哪些選項(xiàng)結(jié)果？諸如此類問題，“前景理論”還不能單獨(dú)解釋。而上述實(shí)質(zhì)理論的提出，可以深化前景理論對(duì)這些問題的解釋，從而使得對(duì)“失地農(nóng)民再就業(yè)培訓(xùn)參與決策行為”的解決更為有效。

該算法存在兩個(gè)缺點(diǎn)：（1）對(duì)于不同初始值的選取可能導(dǎo)致不同的結(jié)果；(2) 該算法是基于目標(biāo)函數(shù)的算法，通常采用梯度法求解極值，由于梯度法的搜索方向是沿著能量減小的方向進(jìn)行，使得算法很容易陷入局部極值[7]。文中針對(duì)第一個(gè)缺點(diǎn)進(jìn)行改進(jìn)，提出了一種新的確定初始值的方法。

3 改進(jìn)的K-means算法

3.1 劃分的基本思想

如圖1所示（k＝3），以xi為中心，將整個(gè)區(qū)域按照同心圓的方式劃分，分別統(tǒng)計(jì)第一個(gè)圓內(nèi)密度（距離xiε范圍內(nèi)的個(gè)體數(shù)目ni）最大的點(diǎn)記為Z1，第二個(gè)環(huán)形區(qū)域內(nèi)的密度最大點(diǎn)記為Z2，依次類推，找到第k個(gè)區(qū)域內(nèi)的密度最大點(diǎn)Zk。

圖1 區(qū)域劃分示例

3.2 初始聚類中心的修正

為了保證初始聚類中心的有效性，對(duì)初始密度有一個(gè)閾值，這也和自然情況相似，作為一個(gè)群體的中心，必然要有足夠的吸引力，密度要有一個(gè)最低值，不然很有可能是異常點(diǎn)。當(dāng)聚類中心的密度低于閾值時(shí)，所對(duì)應(yīng)的區(qū)域增大，只到找到滿足條件的初始聚類中心。

3.3 改進(jìn)的K-means算法

輸入：數(shù)據(jù)集、聚類數(shù)目K、距離閾值ε

輸出：滿足目標(biāo)函數(shù)值最小的K個(gè)聚類

（1）計(jì)算每個(gè)對(duì)象的密度參數(shù)ni(xi ,ε)；

（2）計(jì)算以x1為中心，其他數(shù)據(jù)對(duì)象到x1的距離d(x1,x2)；

（3）以x1為中心，將空間劃為K等分，以同心圓的形式劃分，每份的距離間隔為每份內(nèi)的數(shù)據(jù)集合記為Di；

（5）修正聚類中心，若Zi對(duì)應(yīng)的ni(xi ,ε)滿足最小個(gè)數(shù)，則作為初始的聚類中心；如果不滿足，其對(duì)應(yīng)的空間擴(kuò)大，返回（4）；

（6）從這k個(gè)聚類中心出發(fā)，應(yīng)用K-means聚類算法，得到聚類結(jié)果。

4 實(shí)驗(yàn)驗(yàn)證及應(yīng)用研究

4.1 實(shí)驗(yàn)的描述

為驗(yàn)證上述算法，選用 UCI數(shù)據(jù)庫上的 Iris，Balance_scale，Wine 3組數(shù)據(jù)作為測(cè)試數(shù)據(jù)，數(shù)據(jù)測(cè)試前對(duì)數(shù)據(jù)進(jìn)行處理，算法中用到距離，防止多維數(shù)據(jù)中某一數(shù)據(jù)占絕對(duì)地位，將測(cè)試數(shù)據(jù)中的變?yōu)橥考?jí)的數(shù)據(jù)。UCI數(shù)據(jù)庫是一個(gè)專門用于測(cè)試機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘算法的數(shù)據(jù)庫，庫中的數(shù)據(jù)都有確定的分類，因此可以用準(zhǔn)確率直觀地表示聚類的質(zhì)量。由于Wine數(shù)據(jù)集中，有些屬性的值與其他屬性的值相差很大，需要處理下。表1的數(shù)據(jù)都是在Matlab7.1下運(yùn)行的結(jié)果。

表1 數(shù)據(jù)集合描述

4.2 實(shí)驗(yàn)的結(jié)果

用隨機(jī)選取初始聚類中心的傳統(tǒng)的 K-means算法和本文提出的改進(jìn)的K-means算法，得到表2的結(jié)果。其中準(zhǔn)確率

表格 2 改進(jìn)的k-means算法與傳統(tǒng)K-means算法

4.3 實(shí)驗(yàn)的分析

由表2可以看出，在Iris, Balance-scale和Wine數(shù)據(jù)集中，K-means算法隨初始聚類中心的不同，準(zhǔn)確率變化很大，其中最大的相差40%，即使相對(duì)誤差最小的也有10%。應(yīng)用改進(jìn)后的算法后，準(zhǔn)確率都極大改善，且準(zhǔn)確率非常接近十次運(yùn)行的最好結(jié)果。但Balance-scale的數(shù)據(jù)集的準(zhǔn)確率相對(duì)其他兩個(gè)準(zhǔn)確率較低，這可能數(shù)據(jù)集本生的分布有關(guān)。

4.4 應(yīng)用研究

文章的方法也能夠應(yīng)用在實(shí)際電子商務(wù)客戶細(xì)分中。對(duì)客戶進(jìn)行細(xì)分，需要確定客戶的購買興趣及瀏覽習(xí)慣。在Web服務(wù)器環(huán)境下，這種客戶興趣度可以根據(jù)客戶訪問某個(gè)頁面的頻率即訪問該頁面的次數(shù)，通過 Web使用挖掘自動(dòng)獲得。如果客戶經(jīng)常購買或?yàn)g覽某一商品或某一類商品的網(wǎng)頁，我們就認(rèn)為客戶對(duì)該類商品感興趣，這一類商品購買的越多，那么他對(duì)該類商品的興趣度就越高，這里采用第二個(gè)指標(biāo)來衡量客戶的興趣度。

設(shè)網(wǎng)站共有n類商品構(gòu)成集合:,有m個(gè)客戶 ,則構(gòu)成客戶集合由客戶訂購和瀏覽商品可以得到客戶的購買信息 ,客戶購買行為被映射成為向量,其中表示客戶Ui購買或?yàn)g覽c1…cn商品的量級(jí)。

表3的數(shù)據(jù)來源于國(guó)內(nèi)某專業(yè) B2C電子商務(wù)平臺(tái) ,其日平均點(diǎn)擊率近萬次，我們通過篩選處理 ,抽取了其在2008年平 5月份的 10名客戶U1,……U10訂購或?yàn)g覽 3種商品C1, C2, C3的記錄如表 1 (選客戶 U1作為參照 ) : 即經(jīng)過 Web使用挖掘數(shù)據(jù)預(yù)處理后 ,得到數(shù)據(jù)集 S10={s1，s2，…，s10}：s1=(0, 0, 0) s2=(5, 3, 5) s3=(7, 5, 4) s4= (5, 4, 5)s5=(3,8, 6) s6=(4,8,7) s7=(6,4,6) s8=(1,1,3) s9=(6,3,4) s10=(2,2,4)。

表格3 客戶數(shù)據(jù)描述

應(yīng)用改進(jìn)的 K-means算法對(duì)上面的數(shù)據(jù)進(jìn)行處理，初始聚類中心為s2、s7、s8，得到與文獻(xiàn)[1] 的聚類結(jié)果相比，本文的聚類質(zhì)量要好，將s10與s1、s8歸為一類，這也與表中的情況相符合。s10顯然是購買比較少的客戶，在聚類中心的選擇上，本文的方法也比文獻(xiàn)[1] 的方法好，避免將異常點(diǎn)選為聚類的中心。

5 結(jié)束語

K-means算法是一種廣泛應(yīng)用的聚類算法，但聚類的結(jié)果在很大程度取決于初始聚類中心的選取，本文依此為出發(fā)點(diǎn)，綜合考慮距離和密度，提出一種選擇 K-means初始聚類中心的算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的 K-means算法，能夠消除對(duì)初始聚類中心的敏感性，且極大改善聚類結(jié)果。應(yīng)用結(jié)果也表明，改進(jìn)后的 K-means算法能更好的應(yīng)用于實(shí)際問題。

[1] 郭媛香.聚類算法在 B2C電子商務(wù)客戶細(xì)分中的應(yīng)用[J] .忻州師范學(xué)院學(xué)報(bào),2009,25(2):27-29.

[2] 閃四清,陳茵等.數(shù)據(jù)挖掘[M] .北京:清華大學(xué)出版社,2003:101-102.

[3] Fuyuan Cao, Jiye Liang, Guang Jiang. An initialization method for the K-Means algorithm using neighborhood model[J] . Computers and Mathematics with Applications,2009, 58: 474-483.

[4] Adil M. Bagirov. Modified global k-means algorithm for minimum sum-of-squares clustering problem[J] s. Pattern Recognition 41 (2008) 3192-3199.

[5] Wei Li. Modif i ed K-means clustering algorithm[C] .Image and Signal Processing, 2008.Volume 4, 27-30 May 2008 Page(s):618 - 621

[6] 王洪春,彭宏.基于模糊 C-均值的增量式聚類算法[J] .微電子學(xué)與計(jì)算機(jī),2007,24 (6) :156 - 158.

[7] 黃光球,王西鄧.基于網(wǎng)格劃分策略的改進(jìn)人工魚群算法[J] .微電子學(xué)與計(jì)算機(jī),2007,24(7):83 - 86.