(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 201911194649.0
(22)申请日 2019.11.28
(71)申请人 广西中烟工业有限责任公司
地址 530000 广西壮族自治区南宁市西乡
塘区北湖南路28号
(72)发明人 黄飞杰 郎旭明 左少燕 肖骏
尹建康 张卫东 宋红文
欧达宇 唐靖 赵黎鸣
(74)专利代理机构 北京天盾知识产权代理有限
公司 11421
代理人 卓邦荣 史炜炜
(51)Int.Cl.
G06Q 30/02(2012.01)
G06K 9/62(2006.01)
(54)发明名称
(57)摘要
本发明提供了基于聚类算法的卷烟零售客
户分类模型，拟在K -means算法的程序框架中进
行重构；由于Clara较其余算法运行稳定性更佳，
且采取抽样化思想，运行时长更短。基于以上两
点，特将Clara算法用于K -means算法初始聚类中
心的生成，在此基础上，进行K -means聚类，得到
聚类结果。本发明的算法的总体误差相比现有技
术算法更低，性能更佳，针对于烟草销售行业，采
用本发明的聚类算法对客户进行二次细分，得到
客户类别，在保证档位不变的整体公平性下，新
增了类别这一标准，实现了客户分类精准化，客
观上满足了不同客户的实际需求。权利要求书2页 说明书9页 附图11页CN 111144927 A 2020.05.12
C N 111144927
A
1.基于聚类算法的卷烟零售客户分类模型，其特征在于，算法步骤如下：
(1)、将前期预处理后的数据集导入到matlab工作区中，并进行归一化处理，得到算法输入数据集； (2)、从输入数据集中随机抽取样本集；
(4)、分别用除初始聚类中心以外的数据点替代初始聚类中心，并计算每一次替代后相应的代价和时间；
(5)、选取最小代价和时间情况下的替代方式，生成新的聚类中心；
(6)、将新的聚类中心与初始聚类中心对比，并输出最终聚类中心；
(7)、将最终聚类中心作为整个输入数据集的聚类中心，并计算当前的总误差；
(8)、循环(3)～(7)步骤，选取总误差最小情况下的聚类中心；
(9)、将总误差最小情况下的聚类中心作为K-means算法的初始聚类中心；
(10)、计算数据集中所有数据点分别到K-means算法的初始聚类中心的误差值；并分配类别；
(11)、分配类别后，获得若干类，并在每一类中，计算该类中平均值作为分类聚类中心；
(12)、判断分类聚类中心与K-means算法的初始聚类中心是否相同，
(a)若相同，则迭代终止，输出此时的聚类情况；
(b)若不同，则继续重复循环(10)、(11)步骤，直至聚类中心不再发生变化为止；
(13)、结束程序。
2.如权利要求1所述的基于聚类算法的卷烟零售客户分类模型，其特征在于，将新的聚类中心与初始聚类中心对比如下：
(1)若前后聚类中心保持不变，则输出最终聚类中心；
(2)若前后聚类中心产生变化，重复权利要求1中的(4)和(5)步骤，进行进一步聚类中心替代循环，直至聚类中心不再发生变化为止。
3.如权利要求1所述的基于聚类算法的卷烟零售客户分类模型，其特征在于，在进行归一化处理中，对于每一个属性j下，运行归一化公式：
Ni(j)代表第i个样本第j个属性归一化的数值；
min(C(j))代表所有样本第j个属性的最小值；
max(C(j))代表所有样本第j个属性的最小值；
Ci(j)代表第i第i个样本第j个属性值。
4.如权利要求1所述的基于聚类算法的卷烟零售客户分类模型，其特征在于，所述从输入数据集中随机抽取样本集；具体为，从输入数据集中随机抽取40+2K的样本集，随机抽取方法是以随机数的形式将输入数据集顺序打乱，取打乱后数据中的前40+2K个数据集作为样本。
5.如权利要求1所述的基于聚类算法的卷烟零售客户分类模型，其特征在于，所述40+ 2K为确定样本数量的经验公式；K代表聚类的类别数。
6.如权利要求1所述的基于聚类算法的卷烟零售客户分类模型，其特征在于，所述选取总误差最小情况下的聚类中心，总误差采用欧式距离进行计算，具体如下；
其中：
dist为欧氏距离；
N(j)代表第j个样本点数据；
Centers(i)代表第i个聚类中心点数据。
7.如权利要求1所述的基于聚类算法的卷烟零售客户分类模型，其特征在于，所述的分配类别是根据误差值最小原则，分配类别。
基于聚类算法的卷烟零售客户分类模型
技术领域
[0001]本发明涉及到计算机领域，具体为计算机算法模型，尤其是用于对卷烟零售客户分类计算。
背景技术
[0002]按档位投放是中国烟草在坚持和完善专卖制度前提下，努力克服销售指标等非市场因素，遵循市场经济一般规律，建立市场决定销售自下而上的货源投放模式。例如按成都市区来计，成都市约有4万个有效的烟草零售户，遍布于商业区和大小社区，因此确保和提升零售户盈利水平，是必须承担社会责任。最主要的方式是给零售户提供品类、数量适合的商品。在卷烟商品的投放上，受到“客户分档及卷烟货源供应管理办法”的限制，确保公平和公正的原则，将客户分为1～7档，在投放时采用同档同量的原则，然而随着零售客户的不断增多，同档位内部客户同样存在很大的差异性。因此有必要在保证档位这一大前提不变的情况下，对客户进行二次细分，以实现类间异质化、类中同质化的目的。
[0003]因此有必要从客户基础信息、客户经营结构、客户经营能力三大方面出发，收集聚类算法所需的聚类因子，并进行数据归一化处理，得到算法输入数据集。
[0004]截至目前聚类的传统算法领域，主要分为：基于划分、基于层次、基于网格、基于密度、基于网格的聚类等等。
[0005]基于划分思想的聚类算法主要包括：K-means算法、K-modes算法、K-medoide算法、K-mediods算法、Clara算法。以上五种算法的基本原理具体如下：
[0006]K-means算法：其聚类原理参考图1所示。
[0007]K-means算法是一种较为经典的聚类算法，运行简单快速，但其聚类效果很大程度上受初始聚类中心的选择，且对噪声点及孤立点较为敏感，很容易陷入局部最优解。K-means算法存在的一个比较大的弊端是聚类结果受初始聚类中心的选取影响，不能得到稳定的聚类情况。
[0008]根据误差最小化原则，不断将各数据点分配给对应的聚类中心，同时获取每一类中的均值，以此作为下一次迭代过程中的新聚类中心，若当前聚类中心与上一步迭代的中心点相同，则迭代终止，输出当前迭代次数及聚类结果。
[0009]K-modes算法：其原理参考图2所示。
[0010]K-modes算法在处理分类型数据中表现较好，但仅适用于无序型分类数据，对于有序型分类数据和数值型数据的聚类，往往不能达到更符合实际的聚类效果。
[0011]该算法采用汉明距离作为相似性度量标准，即：判断任意两个数据点间是否相同，相同为1，不同为0，依次计算每个数据点到聚类中心的汉明距离，得分最大，则分配到相应的类中，并在各类中计算
数据点到所有数据点的汉明距离和，得分最大的数据点，作为新的聚类中心，进行下一次迭代，直至聚类中心不再发生变化为止。
[0012]K-medoide算法：其原理参考图3所示。
[0013]K-medoide算法是在K-means算法的基础上进行二次改进的算法，其与K-means算
法的不同点在于每次迭代中的聚类中心生成方式不同，K-medoide算法是在每次迭代中，计算每类中各数据点到所有数据点的欧式距离误差和，取其中误差和最小的数据点作为新的聚类中心。但是，从根本上并未解决K-means算法本身存在的弊端。
[0014]K-mediods算法：其原理参考4所示。
[0015]在每次迭代中，对于聚类中心的每一个点，都遍历所有数据点以替换此时的聚类中心center(i)，并计算相应的替换代价，选择误差最小的数据点作为新的center(i)，得到当前比较好的聚类中心，判断新聚类中心与上一步聚类中心是否相同，不同则继续进行迭代，相同则以此聚类中心进行数据点分配，输出最终聚类情况。
[0016]Clara算法：其原理参考5所示。
[0017]Clara算法是在K-mediods算法的基础上，采用随机样本的思想进行聚类。即从数据集中随机抽取一定量的样本，调取K-mediods算法，得到一个较好的聚类中心，将此聚类中心应用于整个数据集中，并计算此时的总误差，进行多次迭代，选取总误差最小情况下的聚类结果作为最优化输出结果。
[0018]综合来看上述五种算法。在聚类中心的迭代方面，其中K-means算法是以类中平均值作为聚类中心进行迭代，其余四种均是基于样本点作为过程迭代的聚类中心；在相似度度量方面，其中K-modes算法是以汉明距离作为衡量相似性的指标，其余四种均以欧氏距离作为相似性计算标准。在数据处理对象方面，其中K-modes在处理无序分类型领域性能较好，其余四种算法在数值型数据聚类方面性能更佳。
[0019]因此，有必要基于上述五类算法解决卷烟零售客户分类计算问题。
发明内容
[0020]为了解决上述问题，本发明提供了一种基于聚类算法的卷烟零售客户分类模型(定义为Clameans改进算法)，算法步骤如下：
[0021](1)、将前期预处理后的数据集导入到matlab工作区中，并进行归一化处理，得到算法输入数据集；
[0022](2)、从输入数据集中随机抽取样本集；
[0023](3)、针对样本集随机生成一个初始聚类中心；
[0024](4)、分别用除初始聚类中心以外的数据点替代初始聚类中心，并计算每一次替代后相应的代价和时间；
[0025](5)、选取最小代价和时间情况下的替代方式，生成新的聚类中心；
[0026](6)、将新的聚类中心与初始聚类中心对比，并输出最终聚类中心；
[0027](7)、将最终聚类中心作为整个输入数据集的聚类中心，并计算当前的总误差；[0028](8)、循环(3)～(7)步骤，选取总误差最小情况下的聚类中心；
[0029](9)、将总误差最小情况下的聚类中心作为K-means算法的初始聚类中心；[0030](10)、计算数据集中所有数据点分别到K-means算法的初始聚类中心的误差值；并[0031]分配类别；
[0032](11)、分配类别后，获得若干类，并在每一类中，计算该类中平均值作为分类聚类中心；
[0033](12)、判断分类聚类中心与K-means算法的初始聚类中心是否相同，
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议