聚類算法在客戶細分中的應用研究

鄭 華

（廣西工商職業技術學院，南寧 530003）

0 引言

經濟的快速發展，企業的相互競爭，市場分析理論認為，20%的客戶帶來約80%的利潤，通常情況下，只有少部分高價值的客戶才能夠為企業帶來大部分利潤。企業借助基于對客戶價值的評估，同時按照企業內部各個營運小組對公司的財務貢獻完成對客戶的細分。通常情況下，少部分高價值的客戶能夠為公司帶來大部分利潤。進行客戶細分后，公司可以為這部分客戶提供足夠的技術和人力資源的支持，以滿足這些高價值客戶對公司客戶服務的期望。

對客戶進行有效細分的基礎是通過公司所掌握的客戶數據全面地了解客戶。這種通過數據推動客戶細分的方法，涉及到數據庫技術以及可以有效訪問、分析客戶信息的營銷自動化應用。目前，許多公司都采用了復雜的數據挖掘工具，以便非技術型的用戶也能利用大量的事務處理級數據來進行有效的客戶細分。

1 聚類算法的概述

聚類是數據挖掘中的一種主要技術。將一組對象的集合分組成為由類似的對象組成的多個類的過程稱為聚類。分組后得到的相同類中的對象相似，而不同類中的對象相異。聚類分析已經廣泛地應用于許多領域，包括模式識別、數據分析、圖像處理和市場研究。在商務上，聚類可以通過顧客數據將顧客信息分組，并對顧客的購買模式進行描述。同時，聚類分析常常作為數據挖掘的第一步，對數據進行預處理，然后用其他算法對得到的類進行進一步分析。聚類算法可以被分為劃分方法、層次方法、基于密度方法、基于網格方法和基于模型方法。

1）劃分方法（PAM： PArtitioning method）。首先創建k個劃分，k為要創建的劃分個數；然后利用一個循環定位技術通過將對象從一個劃分移到另一個劃分來幫助改善劃分質量。典型的劃分方法包括：k-means,k-medoids，CLARA(Clustering LARge Application)，CLARANS(Clustering Large Application based upon RANdomized Search)。

2）層次方法（hierarchical method）。創建一個層次以分解給定的數據集。該方法可以分為自上而下（分解）和自下而上（合并）兩種操作方式。

3）基于密度方法，根據密度完成對象的聚類。它根據對象周圍的密度（如DBSCAN）不斷增長聚類。

4）基于網格方法，首先將對象空間劃分為有限個單元以構成網格結構；然后利用網格結構完成聚類。

5）基于模型方法，它假設每個聚類的模型并發現適合相應模型的數據。

2 K-平均算法的基本思想

K均值聚類，即眾所周知的C均值聚類，已經應用到各種領域。它的核心思想如下：算法把n個向量xj(1,2…,n)分為c個組Gi(i=1,2,…,c)，并求每組的聚類中心，使得非相似性（或距離）指標的價值函數（或目標函數）達到最小。當選擇歐幾里德距離為組j中向量xk與相應聚類中心ci間的非相似性指標時，價值函數可定義為：

一般來說，可用一個通用距離函數d(xk,ci)代替組I中的向量xk，則相應的總價值函數可表示為：

為簡單起見，這里用歐幾里德距離作為向量的非相似性指標，且總的價值函數表示為式(1)。

劃分過的組一般用一個c×n的二維隸屬矩陣U來定義。如果第j個數據點xj屬于組i，則U中的元素uij為1；否則，該元素取0。一旦確定聚類中心ci，可導出如下使式(1)最小uij：

重申一點，如果ci是xj的最近的聚類中心，那么xj屬于組i。由于一個給定數據只能屬于一個組，所以隸屬矩陣U具有如下性質：

另一方面，如果固定uij則使式(1)式最小的最佳聚類中心就是組I中所有向量的均值：

為便于批模式運行，這里給出數據集xi(1,2…,n)的K均值算法；該算法重復使用下列步驟，確定聚類中心ci和隸屬矩陣U：

1）初始化聚類中心ci,i=1,…,c。典型的做法是從所有數據點中任取c個點。

2）用式(3)確定隸屬矩陣U。

3）根據式(1)計算價值函數。如果它小于某個確定的閥值，或它相對上次價值函數質的改變量小于某個閥值，則算法停止。

4）根據式(4)修正聚類中心。返回2）。

該算法本身是迭代的，且不能確保它收斂于最優解。K均值算法的性能依賴于聚類中心的初始位置。所以，為了使它可取，要么用一些前端方法求好的初始聚類中心；要么每次用不同的初始聚類中心，將該算法運行多次。此外，上述算法僅僅是一種具有代表性的方法；我們還可以先初始化一個任意的隸屬矩陣，然后再執行迭代過程。

K均值算法也可以在線方式運行。這時，通過時間平均，導出相應的聚類中心和相應的組。即對于給定的數據點x，該算法求最近的聚類中心ci，并用下面公式進行修正：

3 聚類算法的改進

聚類是一個富有挑戰的研究領域，它的潛在應用提出了各自特殊的要求。K-平均算法處理不同類型屬性的能力取決于距離的計算方法，及對不同類型數據的處理，但該算法還是有以下不足之處：

1）孤立點是數據庫中與數據的一般模式不一致的數據的對象。在K-平均算法中，孤立點的存在對算法結果的影響是很大的，因為迭代后的中心點是數據的平均值，如果有距離較遠的孤立點，會將整個族的中心拉遠，從而導致結果的偏差。

2）K-平均算法需要人工輸入聚類的數目，加重了用戶的負擔，也使使用更為復雜化了。

通過對聚類方法的總結與比較，可以發現在已有的聚類算法中，一大類都是基于“距離”的概念，例如：傳統的基于歐氏幾何距離的聚類算法，常見的有K-MEANS, K-MEDIODS算法，這類算法的缺點在于處理大數據集和高維數據集時效果不好，另一方面它能發現的聚類個數常常依賴于用戶參數的指定，而這對用戶來說經常是很困難的。而另一類是要人們確定一些參數或者函數的，這在高維空間的數據來說是很難確定的，這類方法包括了基于密度和模型的方法。至于基于網格的方法，它的缺點就是聚類質量較差。這里我們采取一種新的思路，將基于網格和密度的方法結合起來。它的優點在于，一方面，能夠自動發現包含你感興趣知識的子空間，并將里面存在的所有聚類挖掘出來；另一方面，它能很好地處理高維數據和大數據集的數據表格。針對這種思想，人們也曾提出過一些算法，如CLIQUE，DBCA，m IGDCA等。

CLIQUE算法是一種典型的基于密度(關系)和網格(變換)的聚類方法，它利用了關聯規則挖掘中的先驗性質:如果一個k維單元是密集的，那么它的k-1維空間上的投影也是密集的。它的基本思想是把可k維的數據空間分成互不覆蓋的矩形單元。如果一個單元中的數據點的個數大于一個閡值傭戶的輸入參數，則稱該單元是密集的。一個cluster是指連接的密集單元的最大集合。該算法具有網格類算法效率高的優點，對數據輸入順序不敏感，可以處理高維的數據，但需要用戶輸入數據聚類空間等間隔距離和密度閉值參數。由于方法簡化，聚類結果的精確可能降低。

受CLIQUE算法的啟發，并在此算法的基礎上對其進行了改進和完善。既保留了其基于網格算法的運行速度快的特點，又通過細化技術彌補了該類算法精度不高的弱點。滿足了覆蓋的條件，集合r中的最大區域的個數不再減少。

3.1 問題的描述

設R={Rl，R2,…，Rn}是n維立方體，其中Rl,R2…，Rn分別表示n維空間中的一個維。

算法的輸入是n維空間中的點集，其中r={rl，r2…，rn}表示點集中的一個點。通過輸入分割參數∮，可以將空間R的每一維分割成相同的∮個區間，從而將整個空間分成了有限個不相交的子空間，每個子空間可以表示為由n個分量組成的形式{Ul、U2…，u小其中Ui表示這一子空間中的一個維，其取值為{Ri/。/∮，Ri+1/∮}

一個子空間U的中心點UC是一個n維向量{ucl,uc2. . ..ucn} ,其中uci=(li+hi)/2。其中li和hi分別為該區間的最小值和最大值。假設一個子空間U包含k個數據點p1，p2...pk，則U的重心點PU也是一個n維向量{pul, pu2... pun}，其中PUi=(pli+P2i+...+pki)/k。

判定點r={r1，r2...rn}是否落入區間{Ul, U2,…，Un}內，主要是比較是否r的每個分量都滿足Ri/∮＜=Ri＜Ri+l/∮}。在此基礎上還要定義子空間u的選擇率s(U), s(U)表示如下：

s(U)=(u字空間中點的個數)/(整個空間中點的總個數)

對于用戶的輸入參數T，如果s(U)＞ T，則稱數據子空間U是密集的，反之。則是松散的。

一個聚類可以定義為，在n維空間中由一些連通的密集子空間組成的連通分支。一個n維中的子空間Ul, U2稱為連通的是這樣定義的：當且僅當這兩個子空間只有一個公共的面或者Ul, U2都跟另一個子空間U3連通。兩個子空間Ul={ u1, u2…uk}，U2={u'l、u'2…，u'k}有一個公共的面是指，存在k1個維度（不妨設這k1維就是1, 2,…，k1，有uj=u'j成立(j=1, 2,…，k)，并且對于第k維有uk＜＞u'k。

3.2 算法的設計

算法的目的在于要能夠從源數據空間中自動發現這樣一些子空間，使得當所有的數據記錄投影到這個子空間之后，能夠形成具有較高點集密度的區域。為了使得計算點密度的方法簡單一些，將數據空間分割成網格狀，將數據空間中的每一維劃分成相同的區間數，這就意味著每一個單元具有相同的“體積”，這樣單元中點的密度的計算可以轉換成簡單的點計數，然后將落到某個單元中的點的個數當成這個單元的密度。這時可以指定一個閥值，當某個單元格中點的個數大于該閥值時，就說這個單元格是密集的。最后，聚類也就定義為連通的所有的“密集的”單元格的集合。

3.3 算法的實現

給定一個數據集合，算法的目標是找到cluster，并標識每個數據對象所屬的cluster。該算法由以下三個步驟組成：1）把數據集合中的點映射到多個單元中；2）對非密集單元移動，直到它變成密集單元或移出原來的單元范圍；3）標識cluster。

下面具體說明每個步驟的方法。

1）數據空間的劃分和數據集合的映射。

設置閥值T及預處理，把n維空間的每一維劃分為∮個互不相交的區間，并統計每個區間單元格內的點數，即區間的密度，得到所有非空區間信息，并按維的次序作為關鍵字排序，存儲區間位置、密度。

2）細化技術。

該步驟通過細化技術來發現新的密集區間，它的基本思想是把非密集區間向密集區間移動，從而獲得更好的聚類效果。

部份源程序：

實驗結果表明：改進的算法具有更好的全局尋優能力、更快的收斂速度，且其解的精度更高對初始聚類中心的敏感度降低。

4 結束語

企業的競爭重點，正在經歷著從以產品為中心向以客戶為中心的轉移，用改進的聚類算法解決企業客戶聚類分析問題，是可行的。這在支持企業決策方面有著極為重要的理論參考價值和實際應用意義，可以幫助高層管理者更好地管理企業，使企業得到更好的順利發展。

[1] 張雷,李人厚.人工免疫c一均值聚類算法[J].西安交通大學學報,2005,39(8):836-839.

[2] 張世勇.一種新的混合粒子群優化算法[J].重慶工商大學學報:自然科學版,2007,24(3):241-245.

[3] Tang,z.h.,MaccLennan等.數據挖掘原理與應用:SQL Server 2005數據庫[M].清華大學出版社,2007,(1):215-230.

[4] 劉瑜,鄭平,劉瑩.分析型CRM中客戶細分的決策樹分類技術綜述[J].軟件導刊.2006,(3):72-75.