赵海建 向俊宇 杨迎镭

摘  要： 烟草零售环节积累了大量交易数据，但其中隐藏的有价值的信息还未被有效挖掘。本文针对某省烟草零售户卷烟进销存流水数据进行数据挖掘研究。在原始数据清洗和预处理之后，对于零售户分类中遇到的噪声数据，运用K-means算法进行聚类。对聚类中的噪声干扰，提出了离群点消除方法，将离群点划分到另外的Voronoi单元中，增强正常数据点的聚类有效性。该系统在营销实践过程中得以应用，证明了方法的有效性。

關键词： 零售数据； 数据挖掘； K-means； 离群点检测； Voronoi单元

中图分类号：TP391          文献标识码：A     文章编号：1006-8228（2023）09-120-05

Research on retail data mining and clustering noise elimination method

Zhao Haijian， Xiang Junyu， Yang Yinglei

（Chongqing China Tobacco Industry Co.， Ltd.， Chongqing 400060， China）

Abstract： A large amount of transaction data has been collected in the tobacco retail segment， but the hidden valuable information has not been effectively mined. In this paper， a series of data mining research is carried out for the transaction data of tobacco retailers in a province. After the original data cleaning and preprocessing， the K-means algorithm is applied to cluster the noisy data encountered in the classification of retailers. For the noise interference in clustering， an outlier elimination method is proposed to divide the outliers into other Voronoi units to enhance the clustering effectiveness of normal data points. The system is applied in the process of marketing practice， which proves its effectiveness.

Key words： retail data; data mining; K-means; outlier detection; Voronoi Unit

0 引言

烟草零售是烟草销售的重要组成部分，其零售网络经过多年建设，已经取得较大成效，大量交易数据被记录下来。但这些数据处于分散割裂状态，往往不能有效传递到供应链上其他环节，由于数据的零散、异构、数据缺失、噪声多等原因，也难以开展有针对性的分析挖掘，成为烟草供应链决策的薄弱环节。

反观我国电商平台之所以能成功，不仅仅因为其将交易的场所从线下转到了线上，更在于其借助互联网巨大的优势，融合大数据等技术实现“智慧零售”[1]。如果能合理运用数据挖掘技术，深入挖掘其中蕴藏的潜在价值信息，将为企业货源投放、市场调控、品牌营销、风险评估和预警等方面提供数据支持，为企业提供有针对性的决策意见或建议，有助于零售环节的创新发展。

1 研究现状

1.1 烟草零售的发展现状和创新思路

经过多年的烟草零售网络建设，烟草零售环节已积累了大量的经营数据，目前缺乏有效、合适的手段发挥其作用，其中潜在的商业价值未能充分挖掘，现有的一些研究，如：按照客户价值进行分类聚类，实现客户细分，从而可以为不同类别的零售户提供有针对性的个性化服务。闫磊等[2]从客户价值评价指标的维度对零售客户进行了聚类，将大量指标按照分成贡献度、影响度、支持度、成长度和规范度几类，从客户当前价值以及潜在价值的角度进行量化分析和聚类。刘坤达等[3]突出了品牌特征，选用少量指标进行K-means聚类分析。张键等[4]基于客户画像构建了一套监管模型，有效提升了市场监管成效。

1.2 K-means聚类方法的研究

K-means是常用的数据分析技术，它简单直观，速度较快，并可调整它的许多参数以适配实际问题。Moodleya等[5]为了更好地开展零售业务营销，提出了一种有针对性的促销算法，利用模糊C-means聚类和Apriori关联规则挖掘算法等，有效识别商品的最佳目标客户。刘潇、王路遥、Hossain等也分别利用K-means方法对零售户开展分类的特征提取[6-8]。

K-means算法有一个重要的缺陷，它无法处理数据中的噪音。许多技术如DBSCAN已经被提出并被广泛研究。然而，这些方法只是将K-means作为初始的一个步骤，而较少考虑如何进行改进以使其适应噪声数据集。其中，Chawla等[9]提出了一种改进K-means方法，但要求将离群点的数量作为参数进行设置。Gan等[10]提出了KMOR算法，它要求输入两个额外的参数，其中一个是最大的离群值。ODC算法[11]将离群点和真实数据点之间的“差异”作为一个参数，而Neo-K-means[12]则要求输入两个参数α和β，它们与数据点在聚类中的分配有关，也就是离群点的数量。

2 K-means聚类离群点消除方法

本文提出了一种改进的K-means聚类方法，将K-means方法扩展到噪声数据集，以去除聚类结果中的离群点，而无需额外的参数。

2.1 K-means聚类方法

K-means聚类是一种划分式的聚类算法，其原理简单，算法效率高。但是，由于无法预先确定聚类的数量即k值，使用上也存在一定的局限性。

进行K-means聚类前需要进行数据预处理的准备工作，包括数据的准备、清洗、特征构建、特征标准化、确定k值等。最优k值的确定常采用手肘法和轮廓系数法。以手肘法为例，它采用SSE（误差平方和）作为评估聚类好坏的标准，如公式⑴所示，其中Ci是第i个簇，mi是Ci的聚类中心：

[SSE=i=1kp∈Cip-mi2]  ⑴

SSE随着k值的增大而减小，且刚开始会迅速下降，随着k的增大，SSE下降的速度逐步减慢，从k-SSE的图像上可以找到曲率较大一点，对应的k值可以作为最优的k值。因图像上这一点的形状向手肘，故称手肘法。

对标准化后的数据集应用K-means算法，持续将样本划分到k个样本集合（即簇）中，直到聚类中心的变化小于一定的阈值或达到设定的迭代次数，最终得到k个簇，每个簇包含一定的样本量，簇的中心也就是样本集合的特征均值，反映了这个簇的整体特征。

2.2 离群点消除

上述过程得到了k个聚类簇，但在簇中各数据点与聚类中心的距离相差较大，某些点与两个乃至多个聚类中心距离接近，只是因为微小的差距而划入其中某個簇，这样的点显然更应作为离群点被分离出去。本文提出一种方法，从上一节的聚类结果开始，探索离群点所在的区域。

由于聚类中心是由所有簇中数据点取平均得来的，因此，数据点越近中心，它被正确分类的可能性越大；反之，数据点与中心相距越远，它被错误分类或成为离群点的可能性就越大。为此，对离群点的搜索应该从离聚类中心最远的位置开始。K-means聚类簇将空间剖分为Voronoi单元，相邻Voronoi单元之间是超平面。如图1所示，在超平面的交汇处，可以找到离聚类中心最远的点，该点可记为m。

在一个[d]维的数据空间中，[d+1]个Voronoi单元能够确定这样一个交点[m]，它是数据空间中的一个点，满足[vj-m=r，j∈1，2，…，d+1]。其中[vj]是Voronoi单元的中心，即K-means方法发现的聚类中心，[r]是m与Voronoi单元中心的距离。如果其中一个Voronoi单元中心与[m]的距离不等于[r]，[m]将被分配到距离最小的Voronoi单元。

当找到这些交点时，假设这些交点的区域应被视为包含离群点。我们保留聚类的形态，在交点处新建一个Voronoi单元，但该单元中的所有数据点都被视为离群点（见图1（b））。在原有的聚类簇之外，创建这样的离群Voronoi单元有时可能是错误的，因为这样的离群Voronoi单元可能也把一些正常的数据点包含进来。为此，必须设置一个标准来决定是否需要创建这样的离群Voronoi单元。本文使用了最小描述长度（MDL）策略，它假设聚类的编码成本取决于聚类的好坏，而编码成本与聚类编码所需的内存直接相关。应用该准则，可推算新建的Voronoi单元是否保留，然后开始下一次迭代。在图1（b）中，找到了新的Voronoi单元交点，可以采取与之前相同的步骤。在此之前会更新聚类中心。这一过程迭代进行，直到找不到其他交点用于改善聚类。

2.2.1 寻找Voronoi单元交点

有几种方法可以用于搜寻Voronoi单元的交点。最直观的方法是用几何计算法找到m。但如果在d维数据空间中有k个K-means中心，在不知道这些中心的相邻关系的情况下，需要遍历所有组合以找到Voronoi单元的组合，这种方法效率较低。

本文使用Avis-Fukuda算法，它专门用于寻找Voronoi交点。Avis-Fukuda算法将每个Voronoi单元的中心作为输入，并计算这些Voronoi单元的交点，即从一个Voronoi单元的中心和约束它的其他中心开始，形成一个围绕中心的凸多面体，该凸多面体的角就是要找的交点。它用线性优化方法计算出最近的顶点，然后沿着凸多面体的边找到其他顶点。通过这种方式，可以找到凸多面体的所有角点，即所有Voronoi交点。

2.2.2 MDL准则

找到Voronoi单元的所有交点后，下一步要决定是否新建Voronoi离群单元。MDL假设，较低的编码成本意味着更好的聚类。因此，如果新的Voronoi噪声单元降低了总的编码成本，算法就会保留新的Voronoi噪声单元。编码成本由两部分组成。模型[LM]的编码成本和数据[LD|M]的编码成本。因此，总的编码成本可通过公式⑵计算：

[LM，D=LM+L（D|M）]

[=i=1Kj=1Cilog2NCi+i=1Kpi2log2（Ci）-i=1Kx∈Cilog2（pdf（x））] ⑵

其中，[K]是聚类[Ci]的数量；[N]是数据点[x]的数量；[pi]是参数的数量。

编码成本推导如下：只要知道聚类的大小，便可以计算模型编码成本[LM]，它跟数据点的分布有关。一般K-means假设基于正态分布，该分布在所有方向上的方差都一样。因此，基于这一假设，数据点与中心的距离就足以确定其概率。聚类的正态分布取决于两个参数，即均值和聚类方差。聚类均值就是聚类中心，基于聚类可计算方差。假设[x]是正态群中的一个随机点，聚类在每个维度都是[N0，α]的正态分布，即方差为[α]的正态分布，因此找到[α]就是方差。计算[x]到中心的距离[distx，0=i=1dαXi2]，其中[Xi]服从[N0，α]分布，因此[αXi]也是[N0，α]分布的，从而更新[distx，0]的计算方法，如公式⑶：

[distx，0=i=1d（αXi）2]

[=α2i=1d（Xi）2=αi=1dXi2] ⑶

[Y=i=1dXi2]被称为卡方分布，把它标为[pdfx]。不同的是，这里有系数[α]。如果[i=1dXi2～pdfx]，则[αi=1dXi2～1αpdfxα]，由此得到了概率分布。利用方差公式，可得概率密度函数，如公式⑷：

[pdfx=xd-1e-xd2α2xd2-1αdΓ（d2）] ⑷

其中，[Γ]是标准的伽马函数。

至于应该用哪种[pdf]来模拟噪声，一般采用均匀分布的噪声，但它可能会被异常值扭曲。为了降低异常值的影响，本方法假设噪声也服从正态分布。噪声分布的参数计算同前，即平均值是所有数据点的平均值，噪声的方差是所有数据点的方差。

3 数据分析与数据挖掘的设计与实现

烟草零售环节海量原始数据存在不完整、含噪音、不一致等问题，需要通过数据清洗、转换、归纳等手段进行预处理，从而解决数据的不规范问题。本文所使用的原始数据为2020年8月至2021年3月某省级烟草公司零售户卷烟零售的进销存流水数据，共计3357万余条。初步分析数据，存在大量重复值、缺失值和少量异常值，以及不一致的情况。为此，对于重复记录，经过谨慎清洗，共删除3.01%的数据；对于占大量的结存、销售价格缺失情形，基于前后数据进行填补；对于异常值，通过数据校验，依次消除。

随后作了多维聚合分析，以时间、产品、销售三个维度来进行：时间维度划分为日、周、月；产品维度划分为规格、品牌、制造企业；销售维度划分为零售户、县、地市、省等。将经过清洗后的流水数据作为事实表，构建星型模型，开展了OLAP数据分析国，主要的分析指标包括基础指标（购进量、销售量、售价等）、零售户指标（活跃客户数、经销客户数、净增长率等）、品牌销售指标（覆盖率、铺货率等）等类别。

本文构建了带品牌特征的聚类模型，使用客户与品牌连接的数据作为聚类样本，有效扩大了聚类特征值的多样性，增大了样本集合。选择聚类特征时，通过构建五个二级特征指标，反映样本的品牌倾向性、当前价值、潜在价值三个方面。数据集首先按照月份进行分组，分别对每月的数据进行聚类分析。针对数据的量纲不同，因此通过Z-score标准化方法进行标准化和无量纲化处理。然后采用手肘法确定聚类最优k值，通过比较每个月的k-SSE图像，并多次试验，最终确定k取5。图2以2月份为例展示k-SSE图像。

经过K-means算法多轮迭代后，得到了各月的聚类结果。各簇的聚类中心如表1所示。

使用雷达图进行绘制，如图3所示，可以观察到各个簇的特征。

为每个簇确定类别的过程，如果仅参考特征排名，則存在不稳定性（如图3 SHCZ指标中G1为次高、G0为最差，但他们的值几乎接近），因此还参考了指标的相对大小的等级（简称指标等级）。指标等级指一组簇类的某一指标经min-max归一化后的值所处的范围等级，0～0.2之间表示E，0.2～0.4之间表示D，以此类推。从而将簇的特征数据转化为等级与排名的形式，以便赋予类别标签。从品牌倾向度、商户当前价值、商户潜在价值三个角度，用H、X、L分别表示高、中、低，分别根据指标等级、排名进行评估、综合与拟合后确定类别。各类的大致特征为：HHX（A类）、LHX（B类）、HLH（C类）、LLH（D类）、XLL（E类）。所刻画的五类分别为：重点客户的主销品牌、重点客户的非主销品牌、成长型客户的主销品牌、成长型客户的非主销品牌、低价值和低潜力客户。

该分类方法已在企业十余个基层销售组织中进行推广应用，在三个多月的试用过程中收集销售人员的意见与反馈，并进行统计分析。分析结果表明，本方法所分类的85%以上的产品符合销售人员的原有判断，并有所细化。其余分类有差异的主要涉及中等偏下的产品。按照本方法的分类开展相应营销工作后，销量有10%以上幅度增长，说明本方法将数据中的一些隐含信息挖掘了出来，并有效指导了营销工业的开展。

4 总结

本文针对省级烟草公司所辖零售户卷烟的进销流水数据开展了一系列数据挖掘工作。在调研销售分析相关方法的基础上，选择K-means聚类算法作为零售户分类的基础方法，在聚类成果之上进行离群点消除。在此基础上开展数据分析和数据挖掘，完成了数据清洗与预处理、多维分析处理和数据展示。本文所开发的系统已在该烟草公司应用实施，取得了良好的应用效果。

参考文献（References）：

[1] 李卫华.大数据背景下传统零售企业精准营销探析[J].商业

经济研究，2019（15）：71-74.

[2] 闫磊，刘旭，徐斌.基于客户价值的卷烟零售客户分类研究与

应用[J].价值工程，2019，38（25）：89-90.

[3] 刘坤达，宋红文，张卫东，等.品牌优先的零售客户细分研究[J].

现代商贸工业，2021，42（32）：45-46.

[4] 张健，魏生强，张瀛.精准画像提高烟草专卖监管效能——

基于粗糙集的大数据分类监管体系研究[J].海峡科学，2021（8）：69-73.

[5] Raymond Moodleya， Francisco Chiclanacb， Fabio Caraf-

finia， et al. A product-centric data mining algorithm for targeted promotions[J]. Journal of Retailing and Consumer Services，2020，54（5）：1-13.

[6] 刘潇，王效俐.基于K-means和邻域粗糙集的航空客户价值

分類研究[J].运筹与管理，2021，30（3）：104-111.

[7] 王路遥，高山，李俊，等.基于K-means聚类与空间相关性的

零售户销售行为分析[J].测绘通报，2019（9）：51-54.

[8] Hossain， M. Z.， Akhtar， M. N.， Ahmad， R. B.， et al. A

dynamic K-means clustering for data mining[J]. Indonesian Journal of Electrical Engineering and Computer Science，2019，13（2）：521-526.

[9] Sanjay Chawla， Aristides Gionis. K-means--： a unified

approach to clustering and outlier detection[C].Proceedings of the 2013 SIAM International Conference on Data Mining，2013：190-197.

[10] Guojun Gan， Michael Kwok-Po Ng.K-means clustering

with outlier removal[J]. Pattern Recognition Letters，2017，90（4）：8-14.

[11] Mohiuddin Ahmed， Abdun Naser Mahmood. A novel

approach for outlier detection and clustering improvement[A]. 2013 IEEE 8th Conference on Industrial Electronics and Applications （ICIEA）[C]. Melbourne， VIC， Australia：IEEE，2013：577-582.

[12] Joyce Jiyoung Whang， Yangyang Hou， David F. Gleich，

etc. Non-exhaustive， Overlapping Clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2019，41（11）：2644-2659.