SOM+K-means兩階段聚類算法及其應用

摘 要:在眾多聚類算法中，K-means和自組織神經網絡(SOM)是較為經典的2個。在分析2種算法優缺點的基礎上，提出基于SOM的K-means兩階段聚類算法，該算法根據SOM算法自動聚類的優點得到初步聚類數目和各類中心點，以此作為K-means算法的初始輸入進一步聚類，從而得到精確的聚類信息。最后，應用該算法對某地區電信家庭客戶數據進行分析，結果表明該算法有較好的聚類效果。關鍵詞:聚類; 自組織神經網絡; K-means; 細分

中圖分類號:TN911-34文獻標識碼:A

文章編號:1004-373X(2010)16-0113-04

SOM+K-means Two-phase Clustering Algorithm and Its Application

ZHOU Huan， LI Guang-ming， ZHANG Gao-yu

(School of Information Management， Shanghai Finance University， Shanghai 201209， China)

Abstract: K-means and SOM network are two classical algorithms among many clustering ones. A new SOM-based K-means two-phase clustering algorithm is proposed based on the analysis of the advantages and shortcomings of the two algorithms. The quantity of the preliminary clustering and the central point of each cluster were acquired with K-means algorithm， by means of the auto-clustering advantages of SOM algorithm. Taking the results as the initial input of the K-means algorithm to make the further clustering， the accurate clustering results are gained. The data of the telecom family customers in a district is analyzed with the algorithm. The results confirm that the algorithm is better than SOM network and K-means algorithms when they are separately used.

Keywords: clustering; SOM network; K-means; partition

0 引 言

聚類分析[1]是一種探查數據結構的工具，其核心是聚類，即將對象劃分為簇，使得同一個簇的對象相似，而不同簇的對象相異。對象可以通過某些度量(如屬性/特征)或與其他對象的關系(例如，逐對距離、相似性)來描述。聚類屬于非監督學習技術。在商業社會，急需對急劇增長的數據加以組織并從數據中學習有價值信息，這使得聚類成為一個非常活躍的研究領域，是數據挖掘中、也是實踐中應用得最多的分析方法。

在聚類分析中，用得比較廣泛的一種聚類算法就是K-means算法[2]，該算法具有簡單、容易理解、計算方便、速度快以及能夠有效處理大型數據庫的優點而成為聚類分析中的經典算法。但K-means算法存在著固有的缺點[3-6]:如初始值對聚類結果影響較大、容易陷入局部最優、依賴經驗判斷最優類的個數以及對“噪音”和孤立點數據比較敏感，這些缺陷大大限制了它的應用范圍和效果。和K-means算法相比，SOM[7-8](self organizing mapping)神經網絡是一個無監督的學習模式，它能夠將數據從高維空間映射到低維空間上，通過降維尋找多維數據的主要統計特征，并根據數據間的相似性自動將數據分成不同的類別，從而達到增強客戶有用信息，降低噪聲的影響。兩者相比，SOM網絡不能提供分類后精確的聚類信息[9]，而K-means在已知聚類數目和中心點的情況下有著很高的精確性[10]。結合這2種算法的優缺點，在此提出SOM+K-means兩階段聚類算法，將其引入電信家庭客戶細分中，并給出具體的應用過程。

1 算法描述

1.1 SOM算法

SOM網絡能模擬大腦神經系統自組織特征映射的功能，是一種競爭式學習網絡，自適應學習能力和魯棒性強，能無監督地進行自組織學習。其結構如圖1所示。

它由輸入層和輸出層(競爭層)組成，對于輸入模式的畸變和噪聲的容差大。在該網絡中，輸出節點與領域其他節點廣泛相連，并互相激勵。輸入節點與輸出節點通過強度Wji(t)相連，通過某種規則，不斷地調整Wji(t)，使得在穩定時，每一領域的所有節點對某種輸入具有類似的輸出，并且這種聚類的概率分布與輸入模式的概率分布相接近。通過這種無監督的學習，穩定后的網絡輸出就對輸入模式生成自然的特征映射，從而達到自動聚類的目的。

圖1 SOM神經網絡結構

1.2 K-means算法

K-means算法以K為參數，把n個對象分為K類，以使類內具有較高的相似度，而類間的相似度較低。它的算法描述如下:

(1) 選擇一個K值，用以確定簇的總數;

(2) 在數據集中，任意選擇K個實例，它們是初始的簇中心;

(3) 應用歐式距離將剩余實例賦給距離它們最近的簇中心;

(4) 使用每個簇中的實例來計算每個簇新的平均值;

(5) 如果新的平均值等于上次迭代的平均值，終止該過程。否則，用新的平均值作為簇中心并重復步驟(3)~(5)。

1.3 SOM+K-means兩階段聚類算法

基于SOM的K-means聚類算法屬于兩階段計算方法:在第一階段的初聚類中，SOM對海量數據樣本進行初聚類，具有相近特征的特征向量視為屬于同一類，樣本數據從而聚成不同的類別，并得出類別數目和各個類的中心點;在第二階段，K-means利用第一階段的結果作為初始值輸入，并進一步聚類，形成最終的聚類結果。基于SOM的K-means算法描述如下:

第一階段，由SOM初聚類，得出聚類數目和各類中心點。

(1) 權值初始化:設Wj(j=1，2，…，p)為連接輸入節點到第j個輸出節點的權值向量，對其賦予隨機數，設初始循環次數t=1。

(2) 對于每個輸入模式XK(K=1，2，…，m):

① 求Wj中與XK距離最小的連接權值向量Wg，有:

[XK-Wg]=∑pj=1‖XK-Wj‖

此處距離為歐式距離，任意2個n維向量E和F的歐式距離由下式求出:

‖E-F‖=∑ni=1(ei-fK)2

② 定義單元g為優勝者，定義Ng(t)為優勝者的鄰域。將鄰域中各個單元對應的連接權值向量與Xi靠攏，學習方程為:

Δwij=η(t)|xki-wij|， wij=wij+Δwij

式中:η(t)為第t次的學習率，隨訓練次數的增加而遞減;xki為第K個樣本數據的第i個輸入節點的輸入;wij為第i個輸入節點與第j個輸出節點之間的連接權值，其中j∈Ng(t)。

③ 對于不同的訓練次數t，重復步驟②。當網絡權值穩定時視為收斂。

④ 網絡收斂后，根據輸出節點的響應，完成樣本的初始聚類。

(3) 輸出聚類數目K和聚類中心Z=(Z1，Z2，…，Zk)

第二階段，將第一階段的輸出結果(聚類數K和聚類中心Z)，作為K-means算法的初始輸入，進行迭代。

(4) 選擇收斂條件，以步驟(3)的輸出結果作為K-means算法的初始輸入值進行迭代計算，直至收斂。

(5) 輸出聚類信息。

2 應用分析

客戶細分是企業在明確的戰略業務模式和專注市場中根據客戶的價值、需求和偏好等綜合因素對客戶進行細分，對不同的客戶群提供具有針對性的產品、服務和營銷模式。作為營銷管理的基礎，細分與目標市場的思想始終貫穿于營銷管理的全過程。當前電信運營商越來越重視客戶細分，但主要集中在大客戶，即政企客戶，很少涉及到家庭客戶。鑒于家庭客戶所占人數眾多，市場潛力巨大，需要對該客戶群的深入分析，了解他們的消費行為，制定針對性營銷策略，實現營銷的精細化。SOM+K-means算法在客戶細分中的應用遵從數據挖掘流程，主要包括細分變量選擇、數據準備、細分模型構建、客戶特征描述和營銷策略制定5個步驟。本文的研究對象為某地區2006年9月前在網的城市家庭客戶，共9 984個觀測對象。

2.1 變量選擇

通過因子分析以及專家探討，確定出較為關心的各個指標，選定模型中用來進行細分的指標體系，包括:在網時長(月)，平均通話時長(秒/次)，主叫次數(次/月)，本地呼叫次數(次/月)，IP時長占比(占長途時長百分比)，國內長途呼叫次數(次/月)，平均收入(ARPU，分/月)，語音收入(分/月)，長途占語音消費比例(%)，寬帶收入(分/月)，增值收入(分/月)。

2.2 數據準備

數據的準備包括數據清洗、數據整合、數據篩選等工作，主要解決將多個異種數據整合成一個整體，并處理數據中存在的噪聲、錯誤、缺失、不相關等問題。

2.3 細分模型構建

對于本文所提的SOM+K-means算法，首先應用SOM對所選的細分變量進行聚類，將所得的聚類中心和類個數作為K-means算法初始值輸入，進行迭代，直至得到最終精確的細分信息。

首先，SOM將客戶數據自動分為13類不同的客戶群，表1~表3為不同算法下的運行結果(類內距離標準差)，從中可以觀察到，基于SOM+K-means兩階段算法的類內距離標準差在不同客戶群的不同屬性中表現最好。

表1 基于SOM的類內距離標準差

類別用戶數在網時長平均通話時長主叫次數本地呼叫次數IP時長占比國內長途呼叫次數平均收入語音收入長途占語音消費比例寬帶收入增值收入

1185101.294.4165.5169.638.122.12 748.93 068.923.51 072.11 646.1

2949109.381.932.231.532.72.71 233.51 062.922.21 223.5563.8

361170.868.238.738.433.73.31 224.61 070.123.01 264.7685.3

415154.764.9151.0153.738.123.03 041.42 769.724.11 933.12 309.7

51846.257.6598.7515.536.3127.77 396.611 376.425.54 309.01 976.5

63 05378.393.911.411.123.61.1997.5420.520.3208.7200.5

71 27257.670.341.042.034.84.2738.9772.723.2437.7548.6

8308111.582.878.379.837.010.61 624.81 486.323.31 352.21 623.9

940146.285.6105.4108.837.011.31 652.61 669.322.4788.51 057.1

1080461.176.866.168.037.16.81 095.31 137.422.6519.9894.0

117342.778.5295.2293.239.077.67231.08 309.325.53 424.22 629.0

122 00088.758.521.021.431.42.3558.9531.123.2567.0415.6

1315950.573.558.259.635.77.61 676.21 498.024.71 602.11 464.1

表2 基于K-means的類內距離標準差

類別用戶數在網時長平均通話時長主叫次數本地呼叫次數IP時長占比國內長途呼叫次數平均收入語音收入長途占語音消費比例寬帶收入增值收入

128186.287.7144.9148.437.616.42 296.32 623.922.5843.51 479.1

267295.468.429.329.131.92.5968.9907.022.91 153.1606.2

3618120.982.128.327.931.72.31 034.3857.321.61 149.2477.7

422553.474.6133.8136.437.415.82 570.22 369.624.92 162.62 388.0

52743.457.5506.2441.136.3124.812 092.511 314.126.03 873.91 748.2

62 65284.057.011.711.627.11.3465.2411.521.8286.0245.4

71 24265.870.348.149.435.35.0883.0938.722.9435.0648.3

8392100.383.766.667.937.76.91 420.21 273.822.51 215.21 002.6

969445.683.288.190.237.18.81 343.11 484.322.3755.11 012.7

1091750.873.55.45.211.30.5384.9200.813.1100.588.8

1111146.496.4259.6263.939.351.85779.36238.725.23 433.12 484.0

12187082.663.326.827.233.02.7613.4624.423.3415.9452.7

1328351.563.248.247.834.25.41 759.61 366.323.01 268.41 004.3

2.4 結果應用

表4是根據SOM+K-means運行后統計出的不同客戶群表現，通過對各類客戶的分析可以制定針對性的營銷策略。以第一類客戶為例，該類客戶數不多，但貢獻最大:在語音收入、寬帶收入、增值收入方面表現優異。同時，該類客戶在主叫次數、本地呼叫次數和長途呼叫次數方面都位居前列，較多的應用IP進行長途通話。該類客戶多為業務往來頻繁的個體經營戶，屬于高價值客戶，需要重點關注。該類群體有著很高的本地通話和外地通話，可見交際網很廣，對電信產品的粘性很高，不建議主動對其進行話費優惠，可通過預存話費進行優惠，也可以采用交叉銷售的方式，鼓勵其多使用增值業務(如:來電顯示、呼叫轉移等)進一步提升忠誠度。

表3 基于SOM+K-means的類內距離標準差

類別用戶數在網時長平均通話時長主叫次數本地呼叫次數IP時長占比國內長途呼叫次數平均收入語音收入長途占語音消費比例寬帶收入增值收入

123193.385.2143.2144.738.413.52 444.53197.823.3785.41 556.7

21 65490.757.116.616.930.51.9383.1465.723.1406.4322.5

31008113.880.227.827.431.82.11 252.9842.122.01 024.0500.4

428651.376.6125.4126.737.513.82 461.62 366.424.12 212.82 185.5

53046.057.0492.6432.736.1126.311 725.511 579.426.83 847.81 694.8

6171885.155.29.49.325.10.9370.6311.120.0258.1206.9

796053.969.944.745.934.94.0694.4823.122.8536.8531.0

844474.783.281.0100.736.39.91 388.81 458.122.01 073.01 158.9

967144.279.864.666.537.66.3991.41 253.522.8734.3857.0

1086550.967.45.45.29.90.5299.3200.911.977.784.5

1112152.893.0254.4257.439.446.04 929.75 353.525.13 407.42 457.1

121 26375.255.228.425.930.62.6507.9645.123.1530.2481.9

1373367.268.354.354.334.95.01417.21432.420.21671.2888.3

表4 基于SOM+K-means的客戶群表現

類別用戶數在網時長平均通話時長主叫次數本地呼叫次數IP時長占比國內長途呼叫次數平均收入語音收入長途占語音消費比例寬帶收入增值收入

123181.0195.3868.1680.837.9186.143 264.543 837.248.93 696.21 767.9

21 65492.8195.028.627.016.31.53 002.01 223.523.093.4260.4

31 00891.7176.212.912.39.60.62 079.1509.417.244.8124.3

428696.1187.529.528.117.41.37 358.91 154.119.14912.3387.1

53083.422.91.00.91.30.0150.136.22.68.220.7

61 71897.0203.746.944.322.52.74 201.91 972.724.5233.1468.7

796097.7226.8290.1272.340.817.813 780.511 678.629.1416.31 772.2

844485.9229.4436.5389.642.846.923 754.918 365.837.03 503.72 240.6

967198.3220.080.476.425.44.011 380.03 030.324.66 267.3887.6

1086595.7209.780.676.326.04.45 538.53 170.325.1178.1709.7

11121100.6239.6192.2180.136.412.016 933.87 398.030.86 459.92 031.5

12126399.4215.8120.1114.131.46.07 297.44 659.524.9294.5965.8

13733100.0223.0184.1174.533.29.69 819.66 818.526.7566.11 307.2

3 結 語

SOM+K-means聚類算法結合了2種算法的優點，聚類過程具有較強的自適應性。SOM網絡首先找出觀測數據集類別數目和各中心點，作為K-means的初始輸入，得到合適初始值輸入后可以得出滿意的聚類結果。案例分析表明，該算法在商業應用中具有較好的客戶細分效果，可為營銷策略的制定提供量化依據，提高企業開展營銷活動的針對性和有效性。

參考文獻

[1]SOMAN K P，DIWAKAR Shyam， AJAY V. 數據挖掘基礎教程[M].北京:機械工業出版社，2009.

[2]JAIN Anil K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition， 2010(31): 651-666.

[3]CAO Fu-yuan， LIANG Ji-ye， JIANG Guang. An initialization method for the K-means algorithm using neighborhood model[J]. Computers and Mathematics with Applications， 2009(58): 474-483.

[4]劉靖明，韓麗川，侯立文.基于粒子群的K均值聚類算法[J].系統工程理論與實踐，2005(6):54-58.

[5]蔣慶豐，李梓，程曉旭.K-Means聚類算法研究及圖形演示的實現[J].信息技術，2010(3):23-25.

[6]徐家寧，張立文，徐素莉，等.改進遺傳算法的K-均值聚類算法研究[J].微計算機應用，2010(4):11-15.

[7]KOHONEN T. Self-organizing maps[M]. 2nd ed. Berlin: Springer-Verlag， 1997.

[8]江波，張黎.基于多維自組織特征映射的聚類算法研究[J].計算機科學，2008(6):181-185.

[9]梁斌梅.自組織特征映射神經網絡的改進及應用研究[J]. 計算機工程與應用，2009(31):137-138.

[10]BALAKRISHNANP V， COOPER M C， JACOBV S. A study of classification capabilities of neural networks using unsupervised learning: a comparison with K-means clus-tering[J]. Psychometrika， 1994， 59(4): 509-525.