聚類算法在客戶細(xì)分中的應(yīng)用研究

鄭 華

（廣西工商職業(yè)技術(shù)學(xué)院，南寧 530003）

0 引言

經(jīng)濟(jì)的快速發(fā)展，企業(yè)的相互競(jìng)爭(zhēng)，市場(chǎng)分析理論認(rèn)為，20%的客戶帶來約80%的利潤(rùn)，通常情況下，只有少部分高價(jià)值的客戶才能夠?yàn)槠髽I(yè)帶來大部分利潤(rùn)。企業(yè)借助基于對(duì)客戶價(jià)值的評(píng)估，同時(shí)按照企業(yè)內(nèi)部各個(gè)營(yíng)運(yùn)小組對(duì)公司的財(cái)務(wù)貢獻(xiàn)完成對(duì)客戶的細(xì)分。通常情況下，少部分高價(jià)值的客戶能夠?yàn)楣編泶蟛糠掷麧?rùn)。進(jìn)行客戶細(xì)分后，公司可以為這部分客戶提供足夠的技術(shù)和人力資源的支持，以滿足這些高價(jià)值客戶對(duì)公司客戶服務(wù)的期望。

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

1 聚類算法的概述

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

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

2）層次方法（hierarchical method）。創(chuàng)建一個(gè)層次以分解給定的數(shù)據(jù)集。該方法可以分為自上而下（分解）和自下而上（合并）兩種操作方式。

3）基于密度方法，根據(jù)密度完成對(duì)象的聚類。它根據(jù)對(duì)象周圍的密度（如DBSCAN）不斷增長(zhǎng)聚類。

4）基于網(wǎng)格方法，首先將對(duì)象空間劃分為有限個(gè)單元以構(gòu)成網(wǎng)格結(jié)構(gòu)；然后利用網(wǎng)格結(jié)構(gòu)完成聚類。

5）基于模型方法，它假設(shè)每個(gè)聚類的模型并發(fā)現(xiàn)適合相應(yīng)模型的數(shù)據(jù)。

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

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

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

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

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

重申一點(diǎn)，如果ci是xj的最近的聚類中心，那么xj屬于組i。由于一個(gè)給定數(shù)據(jù)只能屬于一個(gè)組，所以隸屬矩陣U具有如下性質(zhì)：

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

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

1）初始化聚類中心ci,i=1,…,c。典型的做法是從所有數(shù)據(jù)點(diǎn)中任取c個(gè)點(diǎn)。

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

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

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

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

K均值算法也可以在線方式運(yùn)行。這時(shí)，通過時(shí)間平均，導(dǎo)出相應(yīng)的聚類中心和相應(yīng)的組。即對(duì)于給定的數(shù)據(jù)點(diǎn)x，該算法求最近的聚類中心ci，并用下面公式進(jìn)行修正：

3 聚類算法的改進(jìn)

聚類是一個(gè)富有挑戰(zhàn)的研究領(lǐng)域，它的潛在應(yīng)用提出了各自特殊的要求。K-平均算法處理不同類型屬性的能力取決于距離的計(jì)算方法，及對(duì)不同類型數(shù)據(jù)的處理，但該算法還是有以下不足之處：

1）孤立點(diǎn)是數(shù)據(jù)庫中與數(shù)據(jù)的一般模式不一致的數(shù)據(jù)的對(duì)象。在K-平均算法中，孤立點(diǎn)的存在對(duì)算法結(jié)果的影響是很大的，因?yàn)榈蟮闹行狞c(diǎn)是數(shù)據(jù)的平均值，如果有距離較遠(yuǎn)的孤立點(diǎn)，會(huì)將整個(gè)族的中心拉遠(yuǎn)，從而導(dǎo)致結(jié)果的偏差。

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

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

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

受CLIQUE算法的啟發(fā)，并在此算法的基礎(chǔ)上對(duì)其進(jìn)行了改進(jìn)和完善。既保留了其基于網(wǎng)格算法的運(yùn)行速度快的特點(diǎn)，又通過細(xì)化技術(shù)彌補(bǔ)了該類算法精度不高的弱點(diǎn)。滿足了覆蓋的條件，集合r中的最大區(qū)域的個(gè)數(shù)不再減少。

3.1 問題的描述

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

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

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

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

s(U)=(u字空間中點(diǎn)的個(gè)數(shù))/(整個(gè)空間中點(diǎn)的總個(gè)數(shù))

對(duì)于用戶的輸入?yún)?shù)T，如果s(U)＞ T，則稱數(shù)據(jù)子空間U是密集的，反之。則是松散的。

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

3.2 算法的設(shè)計(jì)

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

3.3 算法的實(shí)現(xiàn)

給定一個(gè)數(shù)據(jù)集合，算法的目標(biāo)是找到cluster，并標(biāo)識(shí)每個(gè)數(shù)據(jù)對(duì)象所屬的cluster。該算法由以下三個(gè)步驟組成：1）把數(shù)據(jù)集合中的點(diǎn)映射到多個(gè)單元中；2）對(duì)非密集單元移動(dòng)，直到它變成密集單元或移出原來的單元范圍；3）標(biāo)識(shí)cluster。

下面具體說明每個(gè)步驟的方法。

1）數(shù)據(jù)空間的劃分和數(shù)據(jù)集合的映射。

設(shè)置閥值T及預(yù)處理，把n維空間的每一維劃分為∮個(gè)互不相交的區(qū)間，并統(tǒng)計(jì)每個(gè)區(qū)間單元格內(nèi)的點(diǎn)數(shù)，即區(qū)間的密度，得到所有非空區(qū)間信息，并按維的次序作為關(guān)鍵字排序，存儲(chǔ)區(qū)間位置、密度。

2）細(xì)化技術(shù)。

該步驟通過細(xì)化技術(shù)來發(fā)現(xiàn)新的密集區(qū)間，它的基本思想是把非密集區(qū)間向密集區(qū)間移動(dòng)，從而獲得更好的聚類效果。

部份源程序：

實(shí)驗(yàn)結(jié)果表明：改進(jìn)的算法具有更好的全局尋優(yōu)能力、更快的收斂速度，且其解的精度更高對(duì)初始聚類中心的敏感度降低。

4 結(jié)束語

企業(yè)的競(jìng)爭(zhēng)重點(diǎn)，正在經(jīng)歷著從以產(chǎn)品為中心向以客戶為中心的轉(zhuǎn)移，用改進(jìn)的聚類算法解決企業(yè)客戶聚類分析問題，是可行的。這在支持企業(yè)決策方面有著極為重要的理論參考價(jià)值和實(shí)際應(yīng)用意義，可以幫助高層管理者更好地管理企業(yè)，使企業(yè)得到更好的順利發(fā)展。

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

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

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

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