基于层次聚类算法的烟草违法区域划分研究

汤妙佳 沙建

（安徽省烟草公司淮南市公司信息中心 安徽省淮南市 232033）

近些年，随着互联网的发展，中国物流行业得到了飞速发展，它给人们生活提供了便利，也成为了不法分子从事涉烟非法交易活动的主要渠道。由于监管力度不足，不法分子通过物流寄递将假烟销售到全部各地，这不仅严重影响烟草市场秩序，对国家税收造成巨大的损失，还使消费者的利益受到了侵害。为进一步加强物流寄递运输监管，国家有关部门在2016年实施了物流寄递实名制要求，烟草行业也加大了物流寄递涉烟非法活动的监管力度，从而积累了大量涉烟非法交易活动数据。但由于缺少大数据处理手段以挖掘出数据的内在价值，目前对涉烟非法交易活动的监督仍是以“人工经验”为主，这不仅浪费了大量的人力资源，也没有发挥出数据应有的价值。如何利用这些非法交易数据，从而科学、系统的挖掘涉烟非法交易的线索，深入加强物流寄递涉烟非法活动的监管，从而实现新时期烟草专卖市场监管的高质量发展，以成为当前迫切需要解决的问题。

数据挖掘是从大量数据中找出隐含的具有潜在价值信息的一个过程，作为一种数据分析的手段，当前已经运用在各行各业中，如商务管理、市场分析、顾客行为预测等，同时也在公安部门的侦查破案中发挥着巨大的作用。因此，采用数据挖掘的手段对涉烟非法交易活动数据进行深入研究，以获得不法分子的物流寄递规律、寄递地址等潜在信息，帮助烟草主管部门在烟非法交易活动中有效的打击违法行为，让历史交易数据发挥出更大的价值。本文基于数据挖掘中的层次聚类算法，针对物流寄递涉烟非法交易活动中的寄递地址信息，实现数字化分类，以帮助烟草主管部门迅速了解和掌握管辖区域的涉烟非法交易活动的高发区域，精准打击违法区域，全面推动涉烟非法交易监管从“人工经验”向“数字分析”转变。

1 层次聚类算法概述

1.1 聚类算法

聚类算法是一种常见的数据挖掘手段，其本质是将一组数据按照给定的标准划分成若干个簇，其中标准的设定取决于聚类的目的以及数据的类型。目前常见的聚类算法主要有划分法（K-Means）、层次法、基于密度的方法、基于网格的方法、基于模型的方法、等，本文主要基于层次聚类算法进行烟草违法区域的划分研究。

1.2 层次聚类算法

层次聚类算法是聚类算法中使用最广泛的算法之一，其方法具有简单、效率高、容易实现的特点，实现方法主要分有凝聚和分裂两种方法。层次聚类算法是以距离为评价指标，所构成的簇是以距离相距相近的点组成，其中基于凝聚方法的层次聚类算法主要分为4个步骤。

步骤1：将数据集中的每个数据看作成一个点，计算各个点之间的距离；

步骤2：将距离最近的若干个点合并成一个簇；

步骤3：将各个簇看作成一个点，重新计算各个点之间的距离；

步骤4：重复步骤2和步骤3，直至满足终止条件后停止。

与凝聚方法相反，基于分裂方法的层次聚类算法是将整个数据集看作成一个点，然后计算点中各个簇的距离，并将最远的字集分裂开，从而实现聚类。本文的目的是对烟草违法区域进行精确划份，划份成的区域越小，则表示精度越高，故选用凝聚方法作为层次聚类算法的实现方法。

在计算过程中，距离的计算方法有很多，如欧氏距离、曼哈顿距离、余弦距离、等。其中，欧氏距离，又称欧几里得距离，是目前使用最为广泛的一种距离计算方式，故本文选用欧氏距离为判别各个点之间的距离方式。其计算公式如下：

其中，(x,y)和(x,y)表示两个点，ρ表示两点之间的欧式距离。

层次聚类算法的优点是距离容易被定义、限制条件少，同时还可以发现簇之间的层次关系，缺点是计算复杂度很高，容易受到噪声的影响。

1.3 簇间度量方式

初始化，每个簇只有一个点，故计算欧氏距离只需要计算两个点之间的距离，但后续的每个簇中都有若干个点，此时计算欧式距离就需要事先给定点的位置。目前常见的确定点的方式有4中，分别是Ward方法、Complete linkage方法、Average linkage方法和Single linkage方法。

Ward方法计算的是最小化成对聚类间的平方差总和，即两个簇合并后增加的内离差平方和最小。这种方法的优点是不容易受到噪声的影响，缺点是对球状簇数据集的处理存在偏差。

Complete linkage方法计算的是最小化成对聚类间最远两点的距离，即两个簇中最远的两个点的欧氏距离，并将其作为两个簇之间的距离。这种方法的优点是不容易受到噪声的影响，在数据集非常大的情况下经常使用，缺点是对球状簇数据集的处理存在偏差。

Average linkage方法计算的是最小化成对聚类间平均两点的距离，即两个簇中每个点之间的欧氏距离的平均值，并将其作为两个簇之间的距离。这种方法的优点是不容易受到噪声的影响，缺点是对球状簇数据集的处理存在偏差。

Single linkage方法计算的是最小化成对聚类间最近两点的距离，即两个簇中最近的两个点的欧氏距离，并将其作为两个簇之间的距离。这种方法的优点是可以处理非椭圆形的数据集，缺点是容易受到噪声的影响。

1.4 评价指标

层次聚类算法中退出循环的终止条件是最终生成的簇个数，一般由人为主动设置。簇的个数不同，则最终生成的结果也不同，故需要一个评价指标来表示最佳的簇个数。常用的评价指标有聚类纯度（Purity）、兰德指数（Rand Index,RI）、F值（F-score）和调整后的兰德指数（Adjusted Rand Index, ARI）。

聚类纯度的思想是用聚类后的点数量除以总的点数量，故又被称为聚类的准确度。一般来说聚类纯度越高则聚类效果越好，但这个指标跟最终聚类后的实际簇个数无关，而本文最终结果需要的是簇个数的最佳值。

兰德指数和F值是聚类算法中非常重要的评价指标。假设a为两个同类点在同一个簇的情况数量；b为两个非同类点在同一个簇的情况数量；c为两个非同类点分别在两个簇的情况数量；d为两个同类点分别在两个簇的情况数量。

此时兰德指数的计算公式为：

其中兰德指数在0-1之间，值越大，表示聚类结果越好。

F值的计算公式为：

其中F值在0-1之间，值越大，表示聚类结果越好。

调整后的兰德指数是兰德指数的改进，其目的是为了去掉随机数对兰德指数的影响，其计算公式为：

其中，E(RI)表示兰德指数RI的期望值，ARI的实质是去均值归一化的结果。相对于RI而言，ARI对聚类结果的评价更加准确，故选用调整后的兰德指数作为评价聚类结果的评价依据。

2 实验仿真

以上内容详细阐述了层次聚类算法的原理，为了进一步验证上述理论在实际烟草违规区域划分中的运用情况，以X市的900起真实涉烟非法活动数据为数据集进行仿真实验，如表1所示为一起违法活动的相关数据（由于涉密原因，已略去部分无关字段）。

根据表1可以看出，针对每一次的涉烟违法活动，都存有其收发地址的经纬度信息，根据这个信息就可以唯一确定其实际地址。经脱敏处理后，获得部分收件地址数据的经纬度如表2所示。

表1：涉烟非法活动重要相关数据

表2：脱敏后的部分收件地址数据的经纬度统计表

使用Python语言结合Matplotlib绘图库，将脱敏后的经纬度坐标进行标准化处理，从而构建出用于层次聚类分析的数据集，绘制出的散点图如图1所示。

图1：X市900起物流寄递涉烟非法交易案件收件地址示意图

图1中，每个点表示一起案件的收件地址，下面对其进行层次聚类分析。

假设簇的个数为7，即终止条件为7，针对图1的数据，4种簇间度量方式的实验结果如图2所示。

图2：4种簇间度量方式的实验结果

图2中，每种颜色表示最终合并的一个簇。图2(a)针对左下角的聚类存在偏差；图2(b)针对左上角的聚类存在偏差；图2(c)针对左上角的聚类存在偏差，可以明显的看出左上角区域块的右下角2个点各自分成了一类；图2(d)相对来说是最恰当的聚类结果了，故选用Average linkage方法作为簇间度量方式。

以Average linkage方法作为簇间度量方式，以调整后的兰德指数作为簇个数最佳值的评价依据，据此得到调整后的兰德指数与簇个数之间的折线图如图3所示。

从图3中，折线图随着簇个数的增加先是变大，然后变小。其中，在簇的个数为7时，调整后的兰德指数最大，故簇的最佳个数为7。

图3：调整后的兰德指数与簇个数之间的关系

簇间度量方式选用Average linkage方法，簇的个数设置为7，测得的X市900起物流寄递涉烟非法交易案件收件地址数据的聚类结果如图4所示。

图4：X市900起物流寄递涉烟非法交易案件收件地址聚类结果

图4中，每种颜色表示一个涉烟非法交易地址区域，故该市900起案件数据的案发地址大致可以划分为7个区域，即这7个区域内的非法经营者或者消费者通过物流寄递购买非法烟草的次数较高，分别是X市新城及其某公寓、X市南站、X市某村、X市某大学及周边学院、X市现代工业园区。

为验证聚类结果的准确性，对图4中的7个聚类区域，分别求取聚类簇的质心，然后将对应的脱敏数据进行同样的操作，验证质心的坐标位置是否一致，计算得到如表3所示的中心位置经纬度统计表。

表3：中心位置经纬度统计表

进而，将表3中的中心点坐标信息显示在图中，得到如图5所示。

图5：收件地址聚类结果中心位置图

从表3和图5中，可以看出聚类簇的质心和脱敏数据的中心坐标位置具有高度一致性，进而验证了聚类结果的准确率还是很高的。因此，在市场实际监管工作中，烟草主管部门主要对这7个区域进行重点走访和调查即可。

3 结果及讨论

由于近些年物流业的飞速发展，凭借其方便快捷、伪装手段多、检测方式单一等特点，越来越多的不法分子借助物流寄递进行涉烟非法交易活动。目前，X市烟草主管部门主要采取“现场人工排查”的方式，选派若干名烟草专卖执法人员进驻各物流快递集散中心，与邮政和公安的相关工作人员一起，对运达的各类包裹进行集中排查。但用于不法分子通常采用少量、多次的方式进行交易，因此存在检查量大、但实际收益小的状况。

在实际工作中，由于缺乏相应的数据分析手段，目前常见的处理方式是现场工作人员根据自身经验，对印象中物流快递的收件方进行重点关注。这种处理手段受到个人影响较大，并且容易错漏关键人员的地址信息，且不利于工作人员之间的情报共享。而且查获的大量案件数据，只能存放在数据库中，不能进行有效的运用，使含有价值的线索白白浪费。

2018年11月以来，X市烟草主管部门采用聚类算法对物流寄递涉烟非法交易活动的收件地址进行自动划分，并对每起查获的收件人纳入重点检查名单，特别是对查获次数较多的收件地址或收件人进行重点关注。同时还将划分后各区域内经营者的经营数据进行对比，从而迅速定位疑似进行涉烟非法交易活动的嫌疑人，为一线工作人员提供了精准的违法区域和高效的情报来源，为全面实现精准打击奠定了坚实的基础。2019年，X市烟草主管部门市场检查环节查获案件数量同比增长13.7%，查获假烟数量同比增长61.7%，取得了显著的成效。

4 结语

本文运用聚类算法中的层次聚类算法分析了物流寄递涉烟非法交易案件的收件地址数据，对案件地址区域进行了聚类划分。层次聚类算法具有简单高效、使用便捷的特点，对数据集的要求不高。在给定一定数量的案件数据前提下，可以快速对违法活动区域进行划分，以此不断挖掘出潜在的情报线索。该方法可以帮助烟草工作人员在大量案件数据中快速了解案情，在涉烟非法交易活动中有着广泛的应用前景，但使用前提是涉烟案件地址数据必须准确，否则运行结果将不具备指导意义。同时，该方法对孤立点较为敏感，少量孤立数据可能对最终结果产生很大的影响，因此，如何对孤立点进行额外加权评估，将是接下来需要继续研究的课题。