2024年3月15日发(作者：)

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所示。

它由输入层和输出层(竞争层)组成,对于输入模式的畸变

和噪声的容差大。在该网络中,输出节点与领域其他节点广泛

相连,并互相激励。输入节点与输出节点通过强度Wji(t)相连,

通过某种规则,不断地调整Wji(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?Э柯?,学习方程

为:

Δwij=η(t)|xki-wij|, wij=wij+Δwij

式中:?Е?(t)为第t次的学习率,随训练次数的增加而

递减;xki为第K个样本数据的第i个输入节点的输入;wij为

第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.