K-means算法首先随机从数据集中选取K个点作为初始聚类中心,然后计算各个样本到聚类中心的距离,把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类簇的数据对象的平均值来得到新的聚类中心,如果相邻两次的聚类中心没有产生任何变化,说明划分过程结束,聚类准则函数P己经收敛^{[ 5]}。从上面的算法思想不难看出,K个初始聚类中心点的选取对聚类结果具有较大的影响,如果有先验知识做依据选取具有代表性的点,就可以提高算法的准确性。K-means算法主要存在以下两个问题:

(1)算法中K需要事先给定,而这个K值的选定是很难估计的。关于K-means算法中聚类数目K值的确定,孙才志等根据方差分析理论,应用混合F统计量来确定最佳分类数,并应用模糊划分熵来验证最佳分类数的正确性^{[ 6]}。在文献[7]中,使用了一种结合全协方差矩阵的RPCL算法,逐步删除那些只包含少量样本数据的类。文献[8]使用的是一种称为次胜者受罚的竞争学习规则,自动决定类的适当数目。

(2)K-means算法中常采用误差平方和准则函数作为聚类准则函数。在运用这一函数测度聚类效果时,最佳聚类结果对应于目标函数的极值点,由于目标函数存在多个局部极小点,而算法的每一步都是沿着目标函数减小的方向进行,若初始化落在一个局部极小点附近,就会造成算法在局部极小处即收敛^{[ 9]}。

本文针对这两个缺陷提出一种改进的聚类算法。

K-means算法是所有聚类算法中速度最快的一种算法,得到了广泛的应用。然而,算法本身的原理存在两大缺陷,限制了它的使用。本文充分利用了K-means的运算快速这一优点,结合两种方法对以上两个缺陷进行改进,提出一种较好的基于K-means的聚类方案。

(1)对于K值的选取问题,使用相对度量指标中的有效性度量指标。在进行聚类之前,用样本数据对应于不同的K进行初步K-means聚类,使用有效性指标进行比较,选取最优的K值,以保证聚类使用的是最好的K值。由于K-means算法的速度相当快,所以,先进行聚类选取K值,再进行聚类优化,在实际应用中是可行的。

(2)在聚类初始点选取上,使用了PSO算法。PSO算法是1995年由Kennedy和Eberhart在鸟群、鱼群和人类社会的行为规律的启发下提出的一种基于群智能的演化计算技术^{[ 4]}。在PSO中,粒子群中的每个粒子相当于鸟群中的鸟,它们都追踪当前的最优粒子(相当于离食物最近位置的鸟),在解空间搜索,它们不断更新自己的位置和速度,通过不断的迭代,以求得最优解(如同鸟找到食物)。PSO是一种基于迭代的优化工具,首先初始化一群随机粒子(随机候选解),然后通过迭代找到最优解。粒子在每一次迭代中,通过跟踪两个“极值”来更新自己。第一个极值是粒子本身所找到的最优解,这个解称为个体极值(pBest);另一个极值就是整个种群中所有粒子目前找到的最优解,称为全局极值(gBest)。在找到两个最优解后,粒子根据更新公式来更新自己的速度和位置,从而能在较少的迭代次数内找到最优解^{[ 4]}。

这种算法在实际优化问题中表现出很好的性能,基于此,一些学者已经验证过PSO算法对神经网络的训练要好于遗传算法等群智能算法^{[ 10, 11]}。本文使用PSO方法选取K-means聚类的初始点,选取出最好的初始点后使用K-means进行聚类优化。

本文提出的结合算法建立在K-means算法高效聚类的基础上,算法首先使用K-means方法对数据进行多次聚类,再使用有效性指标对每次聚类的效果进行评价,选取出最优聚类的K值,代入到PSO算法中对数据进行K个初始点的选取,最后再次使用K-means进行聚类。在最优K和最优初始点的基础上,在最后一次K-means的应用时保证了聚类的较好效果。算法的流程如图1所示:

图1

	Figure Option ViewDownloadNew Window
	图1 结合算法流程图

结合算法中引入了有效性指标这一聚类质量的评价标准,使用了两次K-means聚类,一次粒子群优化,在PSO算法中适应度的计算方法也是基于K-means聚类中划分的思想。下面对有效性指标进行简单的介绍。

有效性指标的定义如下:SD(C)=a×Scat(C)+Dis(C)^{[ 3]}。α是加权项,用于平衡簇的平聚分散度Scat(C)和簇间总体分离度Dis(C)之间的相对重要性,公式中的其他部分定义如下:

(1)

(2)

其中,{Invalid MML}表示C中簇的最大和最小距离的比例;σ(C)表示数据项与其分配的簇中心的标准偏差;σ(C_k)表示簇C_k的标准偏差;N_k表示分配到簇C_k的数据项的数量。

从有效性指标的定义来看,Scat(C)表示簇间的紧密程度,值越小,簇内的紧密程度越高,随着簇内的分散度越高,它的值也越大;Dis(C)表示簇间的分离度,它受簇的聚类中心影响并随着簇的数量增加而增大;这两项不在一个数量级上,因此需要参数a来调整,α是一个未知项,事先无法给它赋予一个固定的值。在已有的文献中,有人将α定义在[0.5,3.0]的区间范围内,令α=0.5、1.0、1.5、2.0、2.5、3.0,根据上述分散度及分离度公式计算K=4、5、6、7、8的聚类有效性指标值,得出结论:α=0.5时,不论K取何值,有效性指标都是最小的,可见,有效性指标为0.5是最佳选择。本文将这一α值代入有效性指标函数,以聚类结果的具体值来精确衡量哪一个K值是最好的选择。

为解决时间复杂度过高的问题,粒子群采用的是实数编码,每个粒子的编码对应着求解问题的一个可行解。在与K-means结合的算法中,一个粒子的编码对应着一种分类候选方案。本文采用基于聚类中心的编码方式,即每个粒子以K个聚类中心的坐标向量为基础进行编码。另外,粒子除了位置之外,还有速度、适应值两个参数。综上所述,粒子的编码结构如下:

Z₁₁Z₁₂…Z_1dZ₂₁…Z_2d…Z_3d…Z_k1…Z_kd|V₁V₂…V_k*d|f(X)

其中,Z_kd表示粒子的位置,V_k*d表示粒子的速度,f(X)表示粒子的适应度值^{[ 12]}。

在这种结合算法中,粒子的适应度的计算是很耗时的部分,需要多步迭代计算。适应度的计算参考了K-means划分的基本思想,对每个粒子的计算都要求对所有样本按照最近邻法则进行初步聚类划分,再根据这种聚类划分计算适应度。

最近邻法则表示如下:

若X_i、j满足‖X_i-Z_j‖=min‖X_i-Z_k‖ ,则X_i属于第j类。最常用的适应度函数如下^{[ 13]}:

(3)

该适应度函数代表了所有类的类内距离之和,是非常典型的一个适应度计算公式。然而,虽然聚类的结果类内距离与类间距离具有一定的关系,但这种关系是不确定的,导致这种聚类结果的评价策略不充分。本文选择刘向东等提出的以下适应度函数^{[ 10]}:

d_min(z_i)=min{d(c_il,c_ip)}(∀l,p,l≠p) (4)

其中,w₁和w₂为给定的正常数, },|C_ij|为聚类C_ij中元素的个数,{Invalid MML}(z_i)代表z_i对应分类的最大的类内平均距离,d_min(z_i)=min{d(c_il,c_ip)}(∀l,p,l≠p)代表z_i对应分类的最小类间距离。这样,f的最小值就可以使分类方案同时满足类内距离小和类间距离大这两个准则^{[ 10]}。

改进的聚类算法描述如下:

输入:样本数据集X,K-means迭代次数R,设置粒子群体大小N,粒子群算法最大迭代次数M

输出:聚类数为K的数据集合

Procedure SD()

Begin

初始化运行参数

for k=3 to 10 do

随机选定k个点作为k个聚类集合的中心点

for m

以c₁,c₂,…,c_k为中心点对{x₁,x₂,x₃,…,x_n}进行集合划分, 根据分类集合G₁,G₂,…,G_k中的点计算新的中心点{Invalid MML},{Invalid MML},…,{Invalid MML}

If {Invalid MML}!=c_i,i=1,2,…,k

当前的中心点为聚类划分的结果

break

end if

else

{Invalid MML}=c_i

end for

根据返回的聚类中心点计算聚类的有效性指标SD_k(C)

end for

return SD_k(C)最小时k的值

End

Procedure PSO()

Begin

初始化群体p(i),调用在SD算法中得到的k值

for t = 0 to M-1 do

对每个粒子p(i),计算待分类集合到该粒子对应聚类中心的距离,根据距离将粒子分类

计算粒子群体P(t) 中每个个体的适应度

if 粒子适应度> P_id的适应值

更新P_id

end if

if 粒子适应度> P_gd的适应值

更新P_gd

end if

根据粒子群算法的速度V_i(t)和位置X_i(t)公式调整粒子群的速度和位置

if V_i(t)=V_i(t+1) and X_i(t)=X_i(t+1)

Break

end if

end for

return 适应度最优的粒子

根据返回的最优粒子对聚类数据进行K-means分类

End

数据预处理过程涵盖4方面的内容:数据的导入、数据清洗、模型指标的计算及数据变换。选取国内某知名证券公司在上海的一个营业部的数据,数据预处理的数据库平台采用SQL Server 2005。

为了提高聚类分析的准确性,对原始表中的数据进行清理,主要是删除不合理或空值的记录。处理过程如下:

(1)在客户基本信息表中删除已销户的客户。

(2)本例只研究人民币账户,所以,从客户基本信息表中删除币种为美元或港币的客户资料。

(3)在客户基本信息表中删除小额休眠账户,即资金账户中证券账户余额为零和资金账户余额小于100元且连续三年以上无交易的账户。这些资金往往是结算产生的资金,而不是交易资金,这样的客户共有705个。

(4)建立一个临时统计表,统计出客户在统计期间内交易的次数。107个客户在这一年间没有进行过任何交易,甚至资金也没有注入,当前价值和潜在价值都为零,将这些客户删除。

(5)在客户基本信息表中删除开户未满一个月的账户。这些客户由于开户时间比较短,现有数据还不足以形成一种规律,不适合分析研究。

(6)在各源数据表中,删除客户基本信息表中已经被删除的账户数据。

统计剩余账户数为5 629个。将客户资金账号作为唯一标识,即将Cust_Analysis表中的cust_no字段作为主键。需要从客户基本信息表中将资金账号、客户姓名、客户类型和开户日期等字段值输入到Cust_Analysis对应的字段中。

对经过预处理的客户数据进一步处理,参照表1中的指标结构和各指标的计算方法,计算出各项细分业务指标的具体值,记录到Cust_Analysis数据表中对应的资金账号的各项字段。

表1

表1

表1 客户细分的业务指标 细分角度 业务指标 现有价值 佣金收入+利息收入 潜在价值 资产规模×投资收益率 忠诚度 开放天数 资金流动频率 成交笔数 客户活跃度(资金周转率) 总成交金额/平均资产

表1 客户细分的业务指标

采用参数如下:有效性指标α=0.5,粒子个数取为100,惯性因子ω=0.9,适应度函数w1=0.5,w2=0.5,学习因子c1=c2=1.49,速度阈值取Vmax=0.4。

(1)将程序中经过标准化的数据集的存储路径连接到ODBC接口并将K-means的最大迭代次数设为1 000次,有效性指标公式中的α设为0.5,运行第一段程序,返回SD最小的聚类数存于K中。程序运行整个过程中K取值从3到10得到不同的有效性指标值,如表2所示:

表2

表2

表2 K值与有效性指标SD值的对应关系 K 3 4 5 6 7 8 9 10 SD 6.273 6.946 5.254 4.296 4.98 6.739 7.219 8.017

表2 K值与有效性指标SD值的对应关系

(2)再次将程序中经过标准化的数据集的存储路径连接到第二段程序的ODBC接口,将粒子个数的参数N设为100、最大迭代次数设为100并将K-means的最大迭代次数设为1 000,运行第二段程序。这一过程中得到最优粒子即最优的6个中心点为:

C₁(0.298,2.057,0.407,0,266,-0.092,0.025)

C₂(-0.129,0.087,-0.178,-0.063,0.11,-0.151)

C₃(2.347,0.566,2.25,0.575,-0.07,0.239)

C₄(-0.446,-1.142,-0.486,-0.416,-0.116,-0.207)

C₅(0.604,0.679,0.362,0.129,0.478,5.592)

C₆(1.011,0.656,0.842,6.324,-0.117,-0.212)

(3)对最优粒子进行K-means优化,返回K个数据集。

通过算法执行,得出满足有效性指标最好的K值为6,即将本案例中的客户聚为6个簇。以下就对这6个簇中指标的特征进行分析。

(1)各簇之间的距离

聚类就是将对象划分成若干个类,使得同一类中的对象尽可能地相似,不同类中的对象尽可能地相异。为了产生分离效果较好的簇,期望聚类生成的簇间距离尽可能的大,因为簇间距离小就意味着两个簇之间的相似程度高。由聚类结果可以算出簇间距离如表3所示:

表3

表3

表3 各簇之间的最终距离 Cluster 1 2 3 4 5 6 1 4.591 5.567 4.408 4.914 4.426 2 4.591 3.929 3.139 3.893 3.015 3 5.567 3.929 4.839 5.582 4.297 4 4.408 3.139 4.839 1.356 2.16 5 4.914 3.893 5.582 1.356 3.512 6 4.426 3.015 4.297 2.16 3.512

表3 各簇之间的最终距离

根据已有研究,设定聚类的簇间距离阈值为3.0,簇间距离大于设定阈值的簇为分离较好的,否则分离较差。观察表3可以发现,簇间距离大于3.0的占80%,总体来说,各簇之间的距离相对比较合理,没有明显的离群点数据。

笔者使用Clementine中的K-means直接聚类得到的簇间距离大于3.0的比例为66%,可以说此次的聚类效果是较好的,且相对单独使用K-means方法来说更有效。

(2)簇内标准差和有效性指标

为了验证两种聚类结果质量的好坏,使用簇内标准差和有效性指标来度量簇内紧密度和簇间分离度。簇内标准差衡量的是簇内对象与簇中心点的偏离程度,而有效性指标衡量的是簇内平聚分散度及簇间总体分离度。

对于同一组经过标准化的数据及同一个细分模型,使用K-means和经过改进的K-means进行两次聚类,K值使用的是经过有效性指标确定的值6,统计结果如表4所示:

表4

表4

表4 聚类的簇内标准差和有效性评价 Data 聚类算法 簇内标准差 有效性指标a=0.5 Cust_Analysis SD+PSO+K-means 24.789 4.296 K-means 51.250 19.402

表4 聚类的簇内标准差和有效性评价

一种好的聚类算法应该对应着较小的簇内标准差和较小的有效性指标值。从表4可知,在使用标准化后的证券客户数据进行聚类时,改进的K-means算法的簇内标准差为24.789,K-means算法的簇内标准差为51.250。在簇内紧密度上,改进的K-means算法比K-means算法具有更高的绩效。在有效性指标上,改进的K-means算法的有效性指标值始终比K-means算法的有效性指标值要小,也就是说,改进的K-means算法体现在有效性指标上显得比K-means算法更优一些。因此,可以得出:以簇内标准差和有效性指标为依据,对K-means算法和改进的K-means算法进行对比分析,使用真实案例证明了使用有效性指标和PSO改进K-means聚类算法具有更好的聚类绩效。

通过算法的实现得到了6个客户群,然而在数据处理时为了聚类时各指标的贡献度相同对数据做了标准化处理,在本节中对客户类别进行描述,以制定相应的营销策略。

通常情况下,客户的资产规模越大,客户创造的当前价值、潜在价值绝对值也会相应越大。为了更好地解读细分结果,消除这种由于不同客户资产规模引起的数据差异,对各个客户群进行分析时对数据进行进一步转换,使用这两个指标的平均值与资产总值作比较得出各个簇的价值贡献率,如表5所示:

表5

表5

表5 客户群的价值贡献度 客户群 规模 当前价值贡献度 潜在价值贡献度 1 3.8% 5.05% 14.02% 3 2.1% 16.67% 9.69% 2 5.6% 3.18% 3.34% 6 8.9% 10.30% 4.70% 4 54.6% 4.02% 1.93% 5 25.0% 0.94% 1.71%

表5 客户群的价值贡献度

经过客户群的价值贡献度分级,可以得到聚类的各个客户群的总体特征的描述,如表6所示:

表6

表6

表6 客户群总体特征描述 簇 规模 价值 行为分析 风险度 当前 价值 潜在 价值 忠诚度 资金 流动 交易 频率 资金 利用率 1 3.8% 中 高 中 一般 很频繁 中等风险、持仓 3 2.1% 高 高 中 一般 很频繁 高风险、持仓 2 5.6% 中 中 中 不频繁 很频繁 中等风险、持仓 6 8.9% 高 中 高 一般 很频繁 中等风险、持仓 4 54.6% 中 低 中 不频繁 一般 中等风险、持仓 5 25.0% 低 低 低 不频繁 不频繁 低风险、持仓

表6 客户群总体特征描述

通过分析表6中的数据,可以统计出当前价值和潜在价值同时在中高水平的客户占20.4%,这一比例符合经典的利润20/80原则,同时这部分客户的忠诚度也在中高水平,说明这些客户其中多数为证券公司的老客户,从资金流动、交易频率和资金利用率上也可以看出这些客户的活跃度及风险承受能力都较强;另外79.6%的客户贡献率相对较低,且忠诚度不高,另外三个指标也体现出个人投资的特点,粗略估计这部分可能以散户居多。

总体上,可以看到该营业部的结构基本上属于以中、散户为主的营业部,这与该营业部的实际情况相符。从最初聚类结果的各指标的平均值可以看出,各个簇的资产平均值相差不大,无法区分进行客户等级评价,这是因为细分模型是以挖掘高价值客户为主要目的,在进行营销策略制定的时候,需要以价值为主要依据,再次通过细分模型或者数据库查询对客户进一步细分,制定个性化的营销策略。在实际的经营中,证券公司在有限的人力、物力和财力范围内很难实现对所有客户的个性化营销,而且对于一个企业来说,这种投资收益率明显是不好的,因此,对有价值客户的识别和细分就显出了应有的价值。