??? 摘? 要： 針對k-means算法在處理大數據集時間開銷較大的弊端，提出一種改進的k-means算法。在計算和比較樣本點間的距離時，借用三角形中兩邊之和大于第三邊的定律進行改進，提高了算法的執行效率。
??? 關鍵詞： k-means? 客戶關系管理? 客戶細分
?
??? 在當今信息技術時代，客戶關系管理CRM（Customer Relationship Management）的應用得到快速發展，客戶細分在CRM中擔當越來越重要的角色[1]。
??? 在大眾營銷時代，企業對客戶的劃分比較簡單，如分為大中型企業、小型企業、個人用戶等。隨著精準化營銷、一對一銷售時代的來臨，客戶細分的方法就需要多樣化，營銷活動要求對客戶進行更為細致的分層。在建立和完善以客戶為中心的營銷體系的同時，最為重要且最為緊迫的就是對客戶細分，以便對不同價值的客戶實行差別服務[2]。
??? 在客戶細分中采用的主要技術是數據挖掘中的分類和聚類技術。面對越來越龐大的客戶數據，利用傳統的k-means算法進行細分時，存在著處理大數據集時間開銷較大的不足。本文進行分析后提出對k-means算法的改進，實現了客戶快速、準確的細分方法。
1? 客戶細分模型
??? 客戶數據庫中一般采用三個主要要素作為客戶價值分析的重要指標：最近一次消費R(Recency)、消費頻率F(Frequency)和消費金額M(Monetary)[3]。
??? 最近一次消費R指客戶最近一次購買產品或服務離現在有多長時間。理論上，距離上一次消費時間越近的客戶應該是比較忠誠的；最近才購買商品或服務的消費者，是最有可能再次購買的客戶。吸引一個幾個月前才光顧的客戶，比吸引一個一年多以前來過的客戶要容易得多。
??? 消費頻率F是客戶在特定期間內購買的次數。一般認為，最常購買的客戶也是滿意度最高的客戶。增加客戶購買的次數意味著從競爭對手處搶占了更多的市場占有率。
??? 消費金額M是客戶的所有消費金額，是所有數據庫報告的支柱。
??? 按照最近一次消費R、消費頻率F、消費金額M這三要素建立RFM模型，是分析客戶價值最重要且最容易的方法，能實現對客戶間差異的準確理解。
2? k-means算法及改進
2.1 k-means算法基本思想
??? k-means是數據挖掘技術中的一種基于劃分的聚類算法，因其理論上可靠、算法簡單、收斂速度快而被廣泛使用[4]。
??? k-means算法的目標是根據輸入參數k，將數據集劃分成k個簇。算法采用迭代更新方法：在每一輪中，依據k個聚類中心將其周圍的點分別組成k個簇，而每個簇的質心(即簇中所有點的平均值，也是幾何中心)將被作為下一輪迭代的聚類中心。迭代使得選取的聚類中心越來越接近真實的簇質心，所以聚類效果越來越好。聚類過程如圖1所示。
?
??? 設將d維數據集X＝{xi|xi∈Rd，i=1，2，……，n}聚集成k個簇w1，w2，……，wk，它們的質心依次為c1，c2，……ck，其中
ni是簇wi中數據點的個數。采用誤差平方和準則函數作為目標函數來顯式地判斷算法是否結束，如公式(1)。利用誤差平方和準則函數能把真正屬于同一類的樣本聚合成一個類型的子集，而把不同類的樣本分開[5]。
??? 
??? 當準則函數Jc收斂后，算法結束。k-means算法步驟描述如下(稱為k-means_1)：
??? (1)給定大小為n的數據集X，令I=1，選取k個初始聚類中心cj(I)，j=1，2，3，……，k。
??? (2)以cj(I)為參照點對X進行劃分，計算每個樣本數據對象與聚類中心的距離。若d(xi，ck(I))=min{d(xi，cj(I))，i=1，2，……n}，其中j=1，2，……，k，i=1，2，……n，則將xi劃分到簇wk。
??? (3)令I=I+1，
計算新的聚類中心和誤差平方和準則函數的值
??? (4)若|Jc(I+1)
2.2 改進的k-means算法
??? 在上述k-means算法中，一次迭代內把每一個數據對象分到離它最近的聚類中心所在類，這個過程的時間復雜度為O(nkd)。n指的是總的數據對象的個數，k是指定的聚類數，d是數據對象的維數。新的分類產生以后需要計算新的聚類中心，這個過程的時間復雜度為O(nd)。因此，這個算法一次迭代需要的總時間復雜度為O(nkd)。如果數據量比較大，算法的時間開銷也是相當可觀的[6]。
??? 針對處理大數據量時開支大的不足，本文提出了一種借用三角形三邊不等定律的思想，即三角形兩邊之和大于第三邊的定律，減少每次迭代的計算次數的改進k-means算法。
??? 
在k-means算法的第一個循環階段，每次迭代中要計算每一個樣本數據到各個聚類中心的距離，依次比較得到與之距離最小的一個類中心，并被分配到這個類中。如果能找到一個方法，避免一些不必要的比較和距離計算，就能節省運行的時間開支。在k-means算法中采用的是歐幾里德距離，因此可以考慮借用幾何三角形中三邊關系定理：兩邊之和大于第三邊，從而簡化計算比較過程。
??? 令xi∈X，d(ck，cj)為二個聚類中心的距離，d(ck，cj)、d(xi，ck)與d(xi，cj)三邊構成了一個如圖2所示的三角形。
??? 則有d(ck，cj)≤d(xi，ck)+d(xi，cj)
??? 即：d(ck，cj)－d(xi，ck)≤d(xi，cj)
??? 如果d(ck，cj)≥2d(xi，ck)，則有：d(xi，ck)≤d(xi，cj)，即xi到中心cj的距離比到ck的距離大。因此在d(ck，cj)≥2d(xi，ck)的前提下，就不必計算d(xi，cj)了。k-means算法的演變如下所示(稱為k-means_2)：
??? (1)給定大小為n的數據集X，令I=1，選取k個初始聚類中心cj(I)，j=1，2，3，……，k。
??? (2)計算每兩個聚類中心間的距離d(ci(I),cj(I))，其中i=1，2，……，k，j=1，2，……，k。
??? (3)設xi當前所在類為wm，計算xi與wm類中心的距離d(xi，cm(I))，若d(cm(I),cj(I))≥2d((xi，cm(I))不成立，則計算d(xi，cj(I))；若d(xi,cj(I))＜d(xi，cm(I))，則暫時將xi分配到wj，返回(3)循環運行，最終將xi劃分到簇wm中。其中j=1，2，……，k，i=1，2，……n，m=1，2，……n。
??? (4)令I=I+1，
計算新的聚類中心和誤差平方和準則函數的值
??? (5)若|Jc(I+1)
??? 這里對算法k-means_1和k-means_2作一個比較。在第二個循環階段重新計算聚類中心時，這二個算法的時間復雜度是相同的。但是在第一個循環階段指定聚類簇時，改進的k-means_2算法顯然減少了計算量。先考慮一個樣本點的情況。在k-means_1算法中，計算樣本點到各中心點的距離的次數是k次，而k-means_2算法中，在最好情況下計算樣本點到各中心點的距離的次數是1次，最壞情況下計算樣本點到各中心點的距離的次數是k次。假設α為第一循環階段一次迭代時一個樣本點的平均計算次數，則有α
??? 如上所述，本文采用改進的k-means算法對某酒店的現有客戶群進行細分，建立了RFM模型。根據酒店用戶的要求，分別把R、F、M三個要素劃分為3個等級，結合這三個指標，可以把客戶分成9個等級，也就是聚類成9個簇。
??? 實現聚類算法的主要數據結構如下：
??? (1)記錄一個簇的信息
??? Public Structure clusterlist
??? ??Dim Mean As Double′簇均值
??? ??Dim ClusterNum As Integer′簇中記錄數
??? ??Dim CluserId As Integer′簇號
??? ??Dim SquareError As Double′簇中平方誤差和
??? End Structure
??? (2)記錄一個簇中所有記錄的關鍵字
??? Public Structure recordnum
??? ??Dim culsterid As Integer ′簇號
??? ??Dim recordid As ArrayList ′記錄關鍵字
??? End Structure
??? (3)記錄各個聚類中心間的距離
??? Dim mean_dist(，)as double ′用二維數組記錄中心間的兩兩距離
??? 實現聚類算法的主要函數有：
??? (1)init_mean( )：設定初始聚類中心。
??? (2)calc_mean_eucli( )：計算各中心間的歐幾里德距離。
??? (3)calc_sam_eucli( )：計算各個樣本點到中心歐幾里德距離。
??? (4)calc_euclidean( )：計算二個點間的歐幾里德距離公式。
??? (5)find_cluster( )：找到離樣本點最近距離的簇,并分配樣本點到該簇。
??? (6)calc_new_mean( )：一次劃分后計算新的聚類中心。
??? (7)calc_Jc( )：計算誤差平方和準則函數。
??? (8)kmeans( )：運行k-means算法，若不滿足算法結束條件則遞歸調用。
??? (9)show_cluster( )：展示一個簇內的客戶數據。
??? 聚類算法實現界面如圖3所示，用戶首先要輸入允許的誤差準則和聚類要生成的簇數。
?
4? 結? 論
??? K-means是一種基于劃分的聚類算法，有著廣泛的應用，但其存在著處理大數據集的時間開銷較大的不足。本文對該算法進行改進，用以提高運行效率。客戶細分是信息時代企業自身發展的需要，在當今客戶數據量越來越大的情況下，利用該k-means算法，可以對客戶數據進行分析，快速、有效地實現對客戶的細分，為企業提供準確的決策支持，提高營銷政策的針對性和有效性，提高企業的效益和競爭力。該算法的改進思想也可以為其他領域聚類分析提供參考。
參考文獻
1?? 何榮勤.CRM原理.設計.實踐.北京：電子工業出版社，2003
2?? 謝寰紅.數據挖掘在證券公司CRM客戶細分中的應用.計算機工程，2004；(30)
3?? Bult J R，Wansbeek T.Optimal selection for direct mail.Marketing Science，1997；14(4)
4?? Han J W，Kamber M.Data Mining：Concepts and Techniques.San Francisco：Morgan Kaufmann，2000
5?? 李金宗.模式識別導論.北京：高等教育出版社，1994
6?? Moore A W.The anchors hierarchy：Using the triangle inequality to survive high dimensional data.In：Proc. UAI2000：The Sixteenth Conference on Uncertainty in Artificial Intelligence，2000