改进K-means算法在B2C电子商务客户细分中的应用

时红军，韩兵

0 引言

在激烈竞争的网络商业时代，电子商务企业必须留住老顾客，发展新顾客并锁定利润最高的客户，预测客户客户未来的购买趋势，制定相应的营销策略和客户管理策略。为了实现这个目标，企业就需要尽可能地了解客户的行为，尽可能收集顾客的信息，借助各种分析方法，透过无序的、表层的信息挖掘出内在的知识和规律。利用聚类算法分析出具有相似浏览或购买行为的客户群，并分析客户的共同特征，进而对客户进行细分，帮助电子商务企业了解自己的客户，为客户聚类群体提供更合适、更全面的个性化服务，选择最有开发价值的目标客户群体，发现潜在客户，集中企业优势，制定有效的营销策略[1]。

1 K-means聚类算法

聚类分析是数据挖掘领域的一个重要分支。聚类分析是依据样本间相关联的度量标准，将其自动分成几个群组，且使同一群组内的样本相似，而属于不同群组的样本相异的一组方法[2]。

聚类分析能从客户基本库中发现不同的客户群，并且用购买模式来刻画每个客户群的特征。在电子商务应用中，聚类分析分为对客户群体的聚类和对 Web页面的聚类。客户群体的聚类是Web使用挖掘模式识别阶段应用较多的算法，它主要是按现有客户对站点访问的历史行为进行划分,将具有一定相似度的客户进行聚类，得到聚类的结果模型，抽象出一个特殊客户代表这个客户聚类群体的特征。对于一个新来的客户，运用这个模型将新客户归入相应的类别中。根据各个类别的特征有目的地进行商品推荐，并跟踪推荐效果。聚类算法在电子商务个性化服务的应用中起着重要的作用。

为了实现对数据对象的分类，人们提出了许多不同的算法。目前，常用的聚类算法主要有以下几种类型：划分方法、层次方法、密度方法、模型方法和基于网格的方法。K-means算法是一种基于划分的聚类方法，目的是通过在完备数据空间的不完全搜索，使得目标函数取得极小值。但是该算法是一种局部搜索的聚类算法，算法的结果取决于初始聚类中心，而且该算法只能保证收敛到不动点，不能保证函数收敛到目标函数的极小值点。为了确定 K-means算法的初始聚类中心，提出多种不同的解决办法，Adil M. Bagirov[3]借助辅助函数选取初始点，Fuyuan Gao[4]等利用邻域方法选择初始聚类中心，Wei Li[5]也提出一种利用最大最小距离的方法选取初始距离中心。这些方法在一定程度上提高了K-means算法的性能，但在聚类准确率都有待提高。文中提出了一种新的初始聚类中心的选取规则，使得初始聚类中心的分布尽可能体现数据的实际分布，提高了聚类质量。

2 相关工作

K-means聚类[6]经过反复迭代将数据集划分成K个部分,K为希望得到的类数,需预先指定.具体算法如下：设数据集：

X=个聚类中心为p1，p2，…，pk。数据点间的距离定义为：

目标函数定义为：

算法流程如下：

输入：数据集、聚类数目K

输出：满足目标函数值最小的K个聚类

流程：

(1)从数据集中随机选择K个对象,每一个对象作为一个类的“中心” ,分别代表要分成的K个类；

(2)根据距离中心最近的原则,寻找与各对象最为相近的类,将其他对象分配到各个相应的类中；

(3)针对每一个类,计算其所有对象的平均值，作为该类的新的“中心”；

(4)根据距离“中心”最近的原则,重新进行所有对象到各个相应类的分配；

(5)返回(3) ，直到目标函数没有变化为止。

“前景理论”自提出以来，被广泛用来解释各类风险决策行为。但是，在解释“失地农民再就业培训参与决策行为”上，单靠前景理论还不能给予更为具体的解释。比如，在“编辑”阶段，究竟编辑了哪些信息？在“评价”阶段，究竟评价了哪些选项结果？诸如此类问题，“前景理论”还不能单独解释。而上述实质理论的提出，可以深化前景理论对这些问题的解释，从而使得对“失地农民再就业培训参与决策行为”的解决更为有效。

该算法存在两个缺点：（1）对于不同初始值的选取可能导致不同的结果；(2) 该算法是基于目标函数的算法，通常采用梯度法求解极值，由于梯度法的搜索方向是沿着能量减小的方向进行，使得算法很容易陷入局部极值[7]。文中针对第一个缺点进行改进，提出了一种新的确定初始值的方法。

3 改进的K-means算法

3.1 划分的基本思想

如图1所示（k＝3），以xi为中心，将整个区域按照同心圆的方式划分，分别统计第一个圆内密度（距离xiε范围内的个体数目ni）最大的点记为Z1，第二个环形区域内的密度最大点记为Z2，依次类推，找到第k个区域内的密度最大点Zk。

图1 区域划分示例

3.2 初始聚类中心的修正

为了保证初始聚类中心的有效性，对初始密度有一个阈值，这也和自然情况相似，作为一个群体的中心，必然要有足够的吸引力，密度要有一个最低值，不然很有可能是异常点。当聚类中心的密度低于阈值时，所对应的区域增大，只到找到满足条件的初始聚类中心。

3.3 改进的K-means算法

输入：数据集、聚类数目K、距离阈值ε

输出：满足目标函数值最小的K个聚类

（1）计算每个对象的密度参数ni(xi ,ε)；

（2）计算以x1为中心，其他数据对象到x1的距离d(x1,x2)；

（3）以x1为中心，将空间划为K等分，以同心圆的形式划分，每份的距离间隔为每份内的数据集合记为Di；

（5）修正聚类中心，若Zi对应的ni(xi ,ε)满足最小个数，则作为初始的聚类中心；如果不满足，其对应的空间扩大，返回（4）；

（6）从这k个聚类中心出发，应用K-means聚类算法，得到聚类结果。

4 实验验证及应用研究

4.1 实验的描述

为验证上述算法，选用 UCI数据库上的 Iris，Balance_scale，Wine 3组数据作为测试数据，数据测试前对数据进行处理，算法中用到距离，防止多维数据中某一数据占绝对地位，将测试数据中的变为同量级的数据。UCI数据库是一个专门用于测试机器学习、数据挖掘算法的数据库，库中的数据都有确定的分类，因此可以用准确率直观地表示聚类的质量。由于Wine数据集中，有些属性的值与其他属性的值相差很大，需要处理下。表1的数据都是在Matlab7.1下运行的结果。

表1 数据集合描述

4.2 实验的结果

用随机选取初始聚类中心的传统的 K-means算法和本文提出的改进的K-means算法，得到表2的结果。其中准确率

表格 2 改进的k-means算法与传统K-means算法

4.3 实验的分析

由表2可以看出，在Iris, Balance-scale和Wine数据集中，K-means算法随初始聚类中心的不同，准确率变化很大，其中最大的相差40%，即使相对误差最小的也有10%。应用改进后的算法后，准确率都极大改善，且准确率非常接近十次运行的最好结果。但Balance-scale的数据集的准确率相对其他两个准确率较低，这可能数据集本生的分布有关。

4.4 应用研究

文章的方法也能够应用在实际电子商务客户细分中。对客户进行细分，需要确定客户的购买兴趣及浏览习惯。在Web服务器环境下，这种客户兴趣度可以根据客户访问某个页面的频率即访问该页面的次数，通过 Web使用挖掘自动获得。如果客户经常购买或浏览某一商品或某一类商品的网页，我们就认为客户对该类商品感兴趣，这一类商品购买的越多，那么他对该类商品的兴趣度就越高，这里采用第二个指标来衡量客户的兴趣度。

设网站共有n类商品构成集合:,有m个客户 ,则构成客户集合由客户订购和浏览商品可以得到客户的购买信息 ,客户购买行为被映射成为向量,其中表示客户Ui购买或浏览c1…cn商品的量级。

表3的数据来源于国内某专业 B2C电子商务平台 ,其日平均点击率近万次，我们通过筛选处理 ,抽取了其在2008年平 5月份的 10名客户U1,……U10订购或浏览 3种商品C1, C2, C3的记录如表 1 (选客户 U1作为参照 ) : 即经过 Web使用挖掘数据预处理后 ,得到数据集 S10={s1，s2，…，s10}：s1=(0, 0, 0) s2=(5, 3, 5) s3=(7, 5, 4) s4= (5, 4, 5)s5=(3,8, 6) s6=(4,8,7) s7=(6,4,6) s8=(1,1,3) s9=(6,3,4) s10=(2,2,4)。

表格3 客户数据描述

应用改进的 K-means算法对上面的数据进行处理，初始聚类中心为s2、s7、s8，得到与文献[1] 的聚类结果相比，本文的聚类质量要好，将s10与s1、s8归为一类，这也与表中的情况相符合。s10显然是购买比较少的客户，在聚类中心的选择上，本文的方法也比文献[1] 的方法好，避免将异常点选为聚类的中心。

5 结束语

K-means算法是一种广泛应用的聚类算法，但聚类的结果在很大程度取决于初始聚类中心的选取，本文依此为出发点，综合考虑距离和密度，提出一种选择 K-means初始聚类中心的算法。实验结果表明，改进后的 K-means算法，能够消除对初始聚类中心的敏感性，且极大改善聚类结果。应用结果也表明，改进后的 K-means算法能更好的应用于实际问题。

[1] 郭媛香.聚类算法在 B2C电子商务客户细分中的应用[J] .忻州师范学院学报,2009,25(2):27-29.

[2] 闪四清,陈茵等.数据挖掘[M] .北京:清华大学出版社,2003:101-102.

[3] Fuyuan Cao, Jiye Liang, Guang Jiang. An initialization method for the K-Means algorithm using neighborhood model[J] . Computers and Mathematics with Applications,2009, 58: 474-483.

[4] Adil M. Bagirov. Modified global k-means algorithm for minimum sum-of-squares clustering problem[J] s. Pattern Recognition 41 (2008) 3192-3199.

[5] Wei Li. Modif i ed K-means clustering algorithm[C] .Image and Signal Processing, 2008.Volume 4, 27-30 May 2008 Page(s):618 - 621

[6] 王洪春,彭宏.基于模糊 C-均值的增量式聚类算法[J] .微电子学与计算机,2007,24 (6) :156 - 158.

[7] 黄光球,王西邓.基于网格划分策略的改进人工鱼群算法[J] .微电子学与计算机,2007,24(7):83 - 86.