基于企业应用的K-means算法的实现与改进

    罗俊

    

    

    

    摘要：K-Means算法，也称为K-均值，是数据挖掘研究中是一种最基本的算法，也是应用最广泛的聚类算法。在电子商务、入侵检测、CRM等领域有较多的应用实例。它是一种cluster analysis的算法，其实现主要通过不断循环迭代地选取离种子点最近均值的过程。本文结合企业实际应用阐述k-means的实现过程、具体的改进思路以及应用价值，聚类模型的建立对企业具有较强的实际意义。

    关键词：电子商务;聚类;算法改进;K-means算法

    中图分类号：TP311? ? ? 文献标识码：A

    文章编号：1009-3044（2021）18-0029-03

    开放科学（资源服务）标识码（OSID）：

    当今关于大数据、云的研究愈发深入，可是如何用好这些数据，发现这些数据背后隐藏的信息却成为更具实际价值的工作，这也就是数据挖掘的概念。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐藏其中人们事先不知道的、但又是潜在有用的信息和知识的过程。其与数据分析最大的区别在于未知性，当前数据挖掘的实际价值已经应用社会的各行各业，例如：百货连锁、电子商务、生产制造、金融等。

    本文从企业实际应用出发，结合企业日常经营过程产生的业务数据，并结合k-means算法挖掘海量数据中可能潜在的分类规则与分布情况，并结合企业实际应用情况提出K-means算法的改进思路，通过大量的业务数据进行对比实验。从而更加快速有效地帮助企业分析顾客的消费情况，建立聚类模型，从而优化企业营销策略和顾客关系维护方案，一定程度上提高营销的针对性、有效性。

    1 基于k-means算法的聚类模型

    1.1 K-means算法概述

    K-means作为经典的聚类算法， 它将各个聚类子集中的所有数据样本的均值作为该聚类的代表点，使用误差平方和准则函数来评价聚类性能，给定数据集X，假设X中包含K个聚类子集C1、C2、…、Ck，各聚类子集的样本数为N1、N2、…、Nk，各聚类子集的中心点（均值）分别为M1、M2、…、Mk（Xi），则误差平方和准则函数公式如下：

    1.2算法伪代码描述

    K-means的伪代码描述如下：

    输入：类的数目k和包含n个对象的数据集。

    输出：k个类，使平方误差准则最小。

    （1） Assign initial value for means;

    //任意分配到K个对象作为簇的平均值

    （2）Repeat;

    （3）For j=1 to n DO assign each Xj to the closest clusters;

    （4）For i=1 to K DO? ? ? ? ? ? ? ? ? ? ?//更新簇平均值

    （5）Compare? ? ? ? ? ? ? ? ? ? ? ? ? ? //計算准则函数

    （6）Until E不再变化;

    1.3 算法优化思路

    K-means算法有两个明显的缺点，这两点均与初始值相关：

    其一是聚类的数量K需要事先设定，而通常情况下，我们是无法预知数据集应该被分为多少类别;

    其二是初始随机点的选择，算法的开销和性能直接取决于随机点，不同的初始随机点的选择带来的算法运行结果也不尽相同。

    此外，从算法的执行过程可以看出，需要不断调整样本分类，重复计算样本数据与类中心的距离，在数据样本集较大的情况下，算法的时间开销是需要引起注意的。

    K-means算法的时间复杂性：O（nkt），其中n=|S|，k为聚类的数量，t为迭代的次数。每次迭代均要计算S中的每个样本同每个中心点的距离，然后将其归类为最小距离的中心点。结合实际应用情况设定合适的K值，此外，对于簇中心初始值的设定，我们选择首先将数据集进行排序操作，然后取四分位数进行赋值，四分位数是将数列等分成四个部分的数，一个数列有三个四分位数，设下四分位数、中位数和上四分位数分别为Q1、Q2、Q3，则：Q1、Q2、Q3的位置可由下述公式确定：

    式中n表示资料的项数，以减少t的值来缩短算法运行时间。

    K-means改进算法的伪代码描述如下：

    （1）设定K=3;

    //结合实际应用情况设定分类数

    （2）对数据进行排序，取上四分位数、中位数、上四分位数为簇中心初始值;

    （3）Repeat;

    （4）For j=1 to n DO assign each Xj to the closest clusters;

    （5）For i=1 to K DO? ? ? ? ? ? ? ? ? ? ?//更新簇平均值

    （6）Compare? ? ? ? ? ? ? ? ? ? ? ? ? ? //计算准则函数

    （7）Until E不再变化;

    K-means算法改进后的流程图描述如下：

    2? 模型实验与结果分析

    2.1 数据准备

    实验数据为某大型百货商场2011、2012、2013三年内的交易数据，使用k-means算法对顾客会员证交易积分进行分类，通过季度累计积分值的合理分类确定合适的营销手段。积分汇总值的实际情况分布复杂，对于商场的营销可定义以下三种类型：

    活跃型：消费活动频繁，购买欲强，积分值高;

    稳定型：消费活动不规律，有一定的购买欲望，营销需要关注对象;

    停滞型：消费活动少，购买欲望弱。

    由此可设置分类数K=3，季度积分累计汇总数据集的获取主要经过以下三个步骤：

    1）通过sql语句查询数据库获取初始数据集，每张会员证的积分依据季度进行汇总，卡号进行分组。查询语句如下：

    Select mbrid，

    （select sum（itg） from mbrsaldtl where mbrid=a.mbrid and trddtm between '201201000000' and '201204000000'） as first，

    （select sum（itg） from mbrsaldtl where mbrid=a.mbrid and trddtm between '201204000000' and '201207000000'） as second，

    （select sum（itg） from mbrsaldtl where mbrid=a.mbrid and trddtm between '201207000000' and '201210000000'） as third，

    （select sum（itg） from mbrsaldtl where mbrid=a.mbrid and trddtm between '201210000000' and '201301000000'） as last

    from mbrsaldtl a

    where trddtm like '2012%'

    group by mbrid

    order by mbrid;

    查询结果数据截图如下：

    2）将以上查询结果导出为xls表格數据，分布对如下两种情况进行数据清洗：

    （1）季度积分值不全的数据进行清洗（即连续三个月未发生任何交易），这部分数据具有不稳定性，对无交易积分值进行补0处理，以免流失重要数据;

    （2）积分数值为负值的数据（即只进行退货，或者退货返还积分值大于本季度交易获得积分值），因为退货每个月都可能发生，季度汇总最终的积分值可能是消费交易产生的，也可能是冲抵部分退货后净得的，所以对于负值积分也进行补0处理，如果要再进行退货原因等情况的分析则需要重新规划数据组成;

    3）每张会员卡取一年四个季度积分汇总值作为一行数据，最终保存为txt文本文件数据集，数据项之间以“，”进行分割，供算法程序运行时读取。这样可以避免数据库网络连接及sql语句执行等因素对算法执行时间的影响。以下为最终数据集前20行的截图：

    2.2 聚类模型建立

    通过在Eclipse中进行txt文件数据集的读取，然后运行k-means算法的java实现程序，并将最终分类结果写入cluster_result.txt文件中。输出结果显示算法运行耗时为47ms。程序控制台输出结果截图如下：

    此外，还可以通过程序进行算法运行结果的图像输出显示，从而更加直观地显示数据聚类的分布情况，程序图形输出结果截图如下：

    2.3 改进算法对比

    通过对初始种子点值的设置，有效地减少了迭代的次数，算法运行耗时为16ms，由此可见初始种子点的值对算法的影响是至关重要的，后输出截图如下：

    3 结束语

    本文结合企业实际应用对k-means算法应用提出一种改进思路，并用企业实际销售产生的交易数据进行对比实验，证明优化是切实有效的。并通过建立聚类模型，划分会员证类型，从而开展有针对性的营销，一定程度上增强了企业的营销的针对性，如果再进行深层次的挖掘，则可以依据商场的商品大类对会员证的消费习惯进行细分，例如：百货、服装、鞋帽、家电、超市等，而对于某一具体的商品大类又可细分为几个小类，例如服装，可划分为男装、女装、运动装等，这样在季节新品的宣城方面就可以进行更加有针对性的宣传与推广，这样对于提高商场的销售业绩无疑是有重大意义的。

    k-means算法的改进有很多方面，例如中心点调整及重复的距离计算、确定收敛性的规则等，结合企业实际应用，从某个方面着手能够有效提高算法的实用性。后续可能还会开展网络安全、电子商务、CRM等方面的深入研究，以期建立更多具有实际指导意义的应用模型及相关算法的改进思路。

    参考文献：

    [1] Jiawei Han，Micheline Kamber，Jian Pei.范明，孟小峰译.数据挖掘：概念与技术 concepts and techniques[M].北京：机械工业出版社，2012.

    [2] 韩家炜，孟小峰，王静，等.Web挖掘研究[J].计算机研究与发展，2001，38（4）：405-414.

    [3] Bing Liu.俞勇，薛贵荣，韩定一译.Web数据挖掘[M].北京：清华大学出版社，2009.

    [4] 周炜奔，石跃祥.基于密度的K-means聚类中心选取的优化算法[J].计算机应用研究，2012，29（5）：1726-1728.

    [5] 赖玉霞，刘建平.K-means算法的初始聚类中心的优化[J].计算机工程与应用，2008，44（10）：147-149.

    【通联编辑：李雅琪】