基于ID3算法的卷烟产品零售客户分类研究

张伟丰

（湖北汽车工业学院 经济管理学院，湖北 十堰442002）

随着计算机数据库管理和MIS在烟草行业的广泛应用，数据库中存储了大量的行业数据，这些数据记录中隐藏着潜在有用的重要信息，使用一定的数据挖掘技术找寻出这些信息和知识，可以为烟草公司制定营销策略提供决策支持。目前，国家实行烟草专卖制度，每一地区的烟草公司实行统一的货源采购与分配，然后由零售客户进行销售。卷烟产品的销售额和烟草公司的利润取决于合理的采购与分配计划，为此，需要对零售客户进行分类，针对不同的卷烟品种，将零售客户划分为某一个类别，进行有针对性的货源分配，从而提高销售量。

要从这些数据中挖掘出具有实际意义的信息，选择合适的数据挖掘算法至关重要，当前运用比较多的有基于关联规则的APriori算法，基于智能计算的分类算法（如进化计算、神经网络等），以及贝叶斯分类、决策树分类算法等。在这种大数据量的情况下，APriori算法需要多趟扫描数据库，运行过程中生成大规模的候选集和频繁集，有相当大的计算量，而智能计算的分类方法具有较高的计算复杂性，计算搜索时间过长，挖掘结果往往也不可靠。ID3算法可以快速的对数据集进行划分而得出分类规则，数据量大的时候也具有很好的实时性，根据数据特点和要挖掘的目的，从实用的角度出发，本文应用ID3算法来对烟草销售系统中的客户资料信息进行分析，构造客户类别的分类器，得到分类规则，进而以此为依据来改进烟草公司现行的货源采购和分配。

1 决策树ID3算法概述

决策树分类算法是运用信息熵的理论，选择当前样本集中具有最大信息增益值的属性作为根节点，依据测试属性的取值将样本集划分为几个子样本集，对每个子样本集采用递归计算的方法重复前述过程继续进行划分，直到无剩余属性或者样本属于同一个类时结束，从而生成一棵决策树。

1.1 基本概念

ID3算法采用信息论中的概念，用信息增益作为属性分类能力的度量，进行属性节点的选择，熵表示样本集的纯度。

设S是n个数据样本的集合，将样本划分为c个不同的类，每个类含样本数ni，S划分为c个类的信息熵按式（1）计算：

假设以属性X作为决策树的根节点，属性X具有m个不同取值，将S划分为m个子集{S1，S2，…，Sm}，根据属性X划分成的子集熵按式（2）计算：

熵值越小，子集划分的纯度越高，根据属性X划分的信息增益按式（3）计算：

其它属性信息增益计算过程同理。

1.2 基本步骤和算法描述

ID3算法的核心是构造精度高、规模小的决策树，主要分为2个步骤：决策树的生成，即由训练样本集生成一棵决策树；决策树的剪枝，即对上一过程生成的决策树进行检验和校正，剪除影响预测准确性的分支。定义 ID3 算法 ID3（TreeNode，data)，具体过程描述如下：

1）对于训练样本集data，根据决策属性取值，按式（1）计算 E（S）。

2）对各条件属性Xk，根据其属性取值，按式（2）计算 E（Xk，S）。

3）对各条件属性Xk，按式（3）计算按各条件属性取值划分的信息增益Gain（Xk，S），选择信息增益最大的属性Xmax作为节点TreeNode。

4）按属性Xmax取值将样本集划分为子集｛data1，data2，…，datam｝，对每个子集 datai按式（1）计算 E（Si），如果 E（Si）等于 0，则此属性取值分支为叶节点，否则递归调用 ID3（TreeNode，datai），继续生成决策树分支。

5）当所有子集划分完时生成了一棵决策树（TreeNode集合），按一定规则剪枝后，沿着树路径读取分类规则。

2 ID3算法在卷烟产品零售客户分类上的应用

将ID3算法用于零售客户分类挖掘，需要建立训练样本数据，本文以烟草销售系统中的零售客户数据和销售历史数据为基础，经过一定的计算处理后转变成适于ID3算法处理的数据形式，然后用ID3算法构造一个分类器，得出具有一定意义的零售客户分类信息。

2.1 数据选择和预处理

根据数据挖掘的目的，对数据库基本表中的数据进行一定的选择、清理和转换，进行挖掘所需数据从3个数据表中获取：

1）烟草产品零售客户基本信息表 用于公司所属的各个地区零售客户的基本信息，数据表主要字段如表1所示。

表1 客户信息表

2）零售客户订单表 用于存储公司所有订单信息，订单信息由零售客户通过烟草销售系统下订单生成，操作过程如下：首先选择所要订购的卷烟产品，生成订购产品列表，然后输入各产品订购数量，确认后系统自动生成此客户的订单。存储订单信息的数据表主要字段如表2～3所示。

表2 客户订单基本信息表

表3 客户订单订购产品信息表

表2存储订单基本信息，表3存储各个订单内包含的产品详细信息，2个表通过订单号关联，系统运行过程中这2个表会积累下大量数据，对订单金额运用如下的算法进行预处理（数据离散化）：

a.对某一种卷烟产品，查询订单表，统计出所有订购此产品的零售客户；

b.对于某一零售客户，根据客户名和产品名在订单表中统计出销售这种产品的总订单金额；

c.所有零售客户对于此产品的总订单金额统计出来后，按金额大小划分为5个类别，即｛高，较高，中等，较小，小｝，然后对某一零售客户根据其订单金额大小归入某一订单金额类别。

销售品种处理方式如下：对于某一零售客户，在订单表中查询出所有订购的产品种类。根据产品种类在高中低档烟草产品中所占的比例归入｛高档为主，高低搭配，低档为主｝中的某个类别。销售区域根据零售客户详细地址划分为｛市内，市郊，农村地区｝。其它属性及取值来自于客户信息表。

通过对上述3个基本表进行数据抽取和转换，得到数据格式如表4所示。

2.2 用ID3算法对零售客户进行分类挖掘

本文是针对某一产品的客户分类，对于不同的产品，同一客户可能具有不同的类别，要挖掘出公司零售客户对于各种产品的分类信息，需要针对每一种产品进行数据的准备和挖掘，对不同的产品而言会有不同的客户分类结果。以“黄鹤楼（秋·品道硬）”这类比较高档的卷烟产品为例，运用ID3算法进行客户分类挖掘。首先针对这种产品进行数据准备：抽取近一段时间内的历史数据，按上述过程进行数据预处理，得到训练数据样本集；然后用ID3算法构建分类器，得出分类规则。算法需要输入训练数据样本；算法输出决策树、分类规则。训练数据由系统根据数据库中的客户基础数据和订单数据自动转换生成作为算法的输入项，决策树构造完成后进行剪枝处理，以获取有价值的分类规则。本文以规则支持度（支持此规则的数据在样本数据中占的比例）作为剪枝条件，分类规则按决策树路径读取，转换为“if then”格式，得到挖掘结果如图1所示。

表4 转换后的零售客户信息表

在完成分类器构造后，选择合适规则支持度对决策树进行修剪，需要反复调整参数以达到需要的挖掘结果。对于这种产品，有8124个零售客户在销售，选择支持度为0.02，从上面分类挖掘结果可得到这样的信息，对于销售“黄鹤楼（秋·品道硬）”产品的零售客户，订单金额高和销售区域在市内的客户是此产品的重要客户。而对于其它产品，则可能挖掘出另外不同的信息，如对于某类低档烟，销售区域在农村地区的客户可能是该产品的重要客户。

3 结语

将ID3算法用在烟草产品零售客户分类的挖掘中，充分利用现有的历史数据，挖掘出有用的知识来指导公司的经营决策。本文主要分析了烟草产品零售客户的分类，对不同的产品，将客户划入某一个类别，利用ID3算法发掘出针对于各类产品的重要客户，有针对性的进行货源的采购和分配，达到了库存最小、利润最大化的目的。

［1］鲁钊，陈世平.基于ID3算法的机械制造业决策应用［J］.计算机应用，2011，31（11）:3087－3090.

［2］ 刘泽，潘晖.基于ID3算法汽车变速箱故障诊断系统［J］.长春工业大学学报：自然科学版，2011，32（6）:534－537.

［3］ 段汝娇，赵伟，等.基于模糊ID3决策树的快速角点检测算法［J］.清华大学学报：自然科学版，2011，51（12）:1787－1791.

［4］ 王小巍，蒋玉明.决策树ID3算法的分析与改进［J］.计算机工程与设计，2011，32（9）:3069－3076.

［5］ 盛俊.决策树ID3算法的改进及其应用 ［J］.扬州职业大学学报，2012，15（4）:34－36.

［6］ 张琳，陈燕，等.决策树分类算法研究［J］.计算机工程，2011，37（13）:66－70.