基于FP-Growth改进算法的轮胎质量数据分析

李敏波 丁 铎 易 泳

1.复旦大学软件学院, 上海，200433 2.复旦大学上海市数据科学重点实验室, 上海，200433

0 引言

随着工业化与信息化的深度融合，信息技术渗透到工业企业产业链的各个环节，条形码/二维码、RFID、工业传感器、工业自动控制系统、ERP、MES、CAD/CAM/CAE/CAI 等技术广泛应用于制造业，尤其是随着互联网、移动互联网、工业物联网等新一代信息技术在工业领域的应用，制造企业所拥有的数据日益丰富。由工业设备所产生、生产过程采集和处理的数据量远大于企业中计算机和人工产生的数据，企业已经进入“工业大数据”时代，其数据的多样性和复杂性正以创纪录的速度迅速增长[1]。

工业大数据是指在工业领域信息化应用中所产生的海量数据，是为决策问题服务的大数据集、大数据技术和大数据应用的总称。由于缺少有效的分析工具以及高效的计算技术来提取有用信息，工业大数据价值还未被充分利用。对于大多数制造企业，大数据应用仍以内部数据为主，多数停留在扩大数据来源与增加数量的初级阶段，将生产数据、设备运行数据、质量检验数据实时采集并存档，提供数据的统计查询，仅在需要时进行数据恢复与分析，而不是像亚马逊、谷歌、阿里巴巴等互联网公司将历史数据视为数据资产而用于运营与决策过程中。

随着智能制造的应用推广，越来越多的工业企业开始重视工业大数据的价值，围绕产品研发创新、生产线监测与预警、设备故障诊断与维护、供应链优化管理、质量监测预测等方面开展工业大数据集成应用。工业大数据面临的挑战在于挖掘历史大数据中蕴含的知识，但知识不是直接呈现在数据中，而是呈现在用于揭示数据的模型中[2]。YAN等[3]提出了工业大数据问题的一种框架， 并介绍了智能制造、工业大数据带来的挑战，如可靠性与安全性。张洁等[4]提出了一种大数据驱动的“关联+预测+调控”决策模式，帮助企业深层次地挖掘工业生产规律，提供精准决策。针对制造企业质量异常数据分析，可以采用ADTree决策树、FP-Growth[5]等算法。

本文选取轮胎行业制造大数据作为研究背景，通过整合轮胎企业各个生产环节的多源数据，构建结构化的质量分析数据集。对质量分析数据集进行关联分析挖掘，可以帮助轮胎企业发现产品制造过程中的质量异常及其影响因素，不仅能够精确定位质量问题, 而且能帮助企业改善工艺流程参数。传统的FP-Growth算法存在频繁项树构建效率低的不足，本文改进了FP-Growth算法的频繁项树建树策略，提升了其性能，使其适用于轮胎行业质量大数据分析。

1 轮胎质量数据分析

对轮胎企业来说，其产品质量控制是非常关键的。在轮胎制造过程中，企业积累了大量轮胎生产数据与轮胎检测数据。在大数据时代，如何利用工业大数据的挖掘技术，从海量时间序列生产制造数据中寻找质量传递的规律，实现产品质量的有效控制与改善，是轮胎企业面临的新难题，由此，质量数据分析成为工业大数据的重要需求。针对采集到的轮胎生产过程数据，利用传统概率统计方法以及数据挖掘算法来构建完整的、有针对性的分析模型，可通过关联分析找出影响轮胎质量的关键因素，为后续的质量改进、生产工艺改进提供合理的数据支持。

1.1 轮胎质量相关数据的获取与整合

轮胎制造过程数据是产品在生产过程中产生的相关数据，包括制造过程中产生的中间状态，如温度、压力等信息，操作工位的工位/设备编号，使用工装或夹具的编码信息，工位/设备报警类信息，合格、不合格产品信息，工序加工时间，质量检测数据与产品物料追溯信息。

轮胎质量检测分为成品胎外观检测、X射线扫描、动平衡检测与均匀性检测以及产品抽样性能试验，这些检测数据由企业MES系统管理。轮胎动平衡检测数据包括产品编号、各个检测项目和检测结果，动平衡检测结果较为重要的3个检测指标为BAL_RANK(上面不平衡量)、RO_RANK(静不平衡量)与UFM_RANK(偶不平衡量)，每个指标值对应在1～5之间取值，只要这3个指标中至少有一个指标为4或5，则产品为不合格品。

质量检测数据定义如下：

insp_Data=product_id,insp_items,insp_result

式中，product_id为轮胎编号；insp_items为轮胎检验项目；insp_result为轮胎检测结果。

制造数据是轮胎生产过程中产生的相关数据，单工序的制造数据定义如下：

product_Data=(product_id,equip_id,proc_time,

shift,operator,proc_parameters)

其中，product_id是产品编号；equip_id是设备编号；proc_time是生产时间；shift是班组编号；operator是操作人员编号；proc_parameters是该工序的工艺参数集。

以上两种数据可以用product_id关联起来，形成结构化的质量分析数据集。

1.2 轮胎质量数据分析方法

轮胎生产制造过程中产生的各种数据存储在企业的MES、ERP、质量检测等不同系统中，这些多源异构数据需要集中获取并整合为结构化数据，从而用于数据挖掘。首先使用数据采集系统将这些数据存储在关系型数据库中；然后利用Sqoop开源工具配置关系型数据库与HDFS Hive数据仓库之间的数据连接，以增量导入的方式获取所有质量相关数据，构建轮胎生产制造数据仓库，实现数据集中管理。使用Hive数据仓库建立质量检测数据与制造过程数据多表合并的结构化质量分析数据集Quality_DataSet，该数据集将应用于后续的质量数据关联分析。

质量数据的分析流程见图1，数据分析流程包括数据获取与整合、数据预处理、质量分析和分析结果整理4个阶段。根据质量分析的主题和产品对象SKU，使用Hive SQL查询语句由Hive质量分析数据集中生成某产品SKU质量分析数据子集Quality_SubDataSet。数据预处理负责重复数据的剔除、异常数据的删除、缺失数据的补全或去除处理等。

针对轮胎检测不合格品的质量异常，要从轮胎生产制造过程的“人、机、料、法、环”5个方面分析产品质量的影响因素。造成轮胎质量异常的影响因素数据(包括轮胎成形与硫化过程温度、压力等属性)均是一系列时序数据，对这些属性进一步细化，抽取其统计指标作为辅助性特征，这些统计特征包括平均值、方差、最大值、最小值、极差等，然后添加到质量异常数据追溯分析数据集中，作为后续关联分析的输入。

质量分析分为单因素分析与多因素分析，单因素分析就是使用统计的方式，通过执行Hive SQL查询语句，得到单个因素(操作人员、班组、加工设备、工艺控制参数等)与产品不合格率的关系。对山东某轮胎公司千万数量级的轮胎质量数据进行单因素分析，可以得到以下初步结论：不同物料编码的轮胎不合格率差异十分明显，其中，21种物料编码的轮胎占产品总数的0.7%，却产生了13.3%的不合格品。单因素分析同样能排除一些影响因素，例如，轮胎硫化班组分早、中、晚班，容易想到晚班的工人是否会因为精力不济导致不合格率增加，但是统计结果表明，3个班组的平均合格率几乎相同。

产品质量的多因素分析可使用数据挖掘的方法来找到造成不良品的影响因素。本文使用FP Growth关联分析作为轮胎质量分析的算法，例如把轮胎生产过程中的硫化工序工艺参数特征值(内温,内压,模温,板温的最大值、最小值、平均值、方差)、硫化操作人员编号(CUR_ZJS_ID)、成形操作人员编号(ZJS_ID)、各生产设备编号(POT_ID,EQUIP_ID,EQUIP_CODE)、生产班次编号(CLASS)、生产车间编号(WORK_SHOP_CODE)、生产模具编号(MOLD_ID)、生产批次编号(CUR_BATCH_ID)等属性作为FP-Growth算法的输入，并将qualified字段设为标记字段,该字段为1代表产品合格, 为2则代表产品不合格。FP-Growth算法将输出一系列满足支持度与置信度要求的关联规则作为挖掘结果， 由于传统的FP-Growth算法建树效率较低，在轮胎质量数据关联分析中存在性能提升空间，故本文对FP-Growth算法进行改进。

1.3 轮胎质量大数据分析平台

轮胎制造大数据分析平台的系统架构见图2，制造大数据平台的数据来源于ERP、MES、SCADA系统中产品与工艺数据、制造过程数据、设备运行数据以及质量检测数据和图像数据。大数据平台通过集成Sqoop框架和自定义开发的数据转化接口API实现多源异构数据获取并将其整合存储至分布式数据文件系统HDFS。轮胎制造大数据平台提供关系型数据库、NoSQL数据库、Hive数据仓库等多种数据存储。

大数据平台使用实时流式计算Storm、并行计算Spark工具进行大数据分析算法的并行计算。平台集成Spark MLlib中的关联分析、时间序列预测、分类、聚类、统计分析等大数据分析算法以实现制造过程的决策分析与预测。使用数理统计方法对提取到的质量关键变量进行标准化、归一化处理，构建多源数据融合的质量大数据模型。利用过程监控方法及多变量统计控制图技术判断失控变量，发现生产过程质量问题分布规律。对质量缺陷问题进行缺陷问题分类和聚类处理。使用K-means聚类算法将连续型属性离散化，使用FP-Growth关联算法加载关联分析的数据集，得到关联规则集。

图2 大数据分析平台架构Fig.2 The architecture of big data analysis platform

2 FP-Growth改进算法

2.1 FP-Growth关联算法

关联分析常被用来从数据中发现事物、特征间频繁出现的相互依赖和关联关系。被发现的关系可以是事先不知道、通过数据的关联分析才获得的。通过对轮胎制造数据与轮胎检测不良率数据之间的关联分析，找出不良率较高的轮胎生产过程影响因素，进而整理出轮胎质量异常的主要影响因素关联规则集。

在执行关联分析前，需要对数据集的连续型属性进行离散化处理。首先使用K-means聚类算法对连续型属性进行必要的聚类，然后基于属性取值的内在结构确定每个划分簇的划分边界，最后按照这样的划分边界对连续型属性进行离散化处理。K-means的目标函数设置为

(1)

式中，xi为第i个样本的坐标；μci为第i个样本在聚类簇中的聚类中心。

通过基于聚类结果抽取出来的离散化策略将所有连续型属性离散化之后，数据集已经符合多因素关联分析的输入规范，便可以作为输入参数进行关联分析。调用Spark MLlib的FP-Growth关联算法，加载关联分析的数据集，得到关联规则集。分析关联规则集，结合轮胎质量故障诊断知识和工艺知识，总结和整理出轮胎质量影响的主要因素以及工艺参数优化规则，为产品质量改进和工艺优化提供数据支持。

数据的关联分析能从大规模数据中分析并挖掘出有价值的关联性知识，主要通过关联规则的挖掘来实现，它可以分为两大步骤：频繁项集的生成和关联规则的产生，其中，最关键的就是频繁项集的生成，该步骤占据了关联规则挖掘全过程的主要花销。常用的频繁项集挖掘算法有Apriori算法、FP-Growth算法等。Apriori算法由AGRAWAL等[6]提出，该算法特点是先生成候选项集，再由候选项集生成频繁项集，这一过程会多次扫描数据库，故该算法效率较低。随后出现了很多Apriori改进算法，如AprioriTid算法[7]；还有基于AprioriTid算法的AprioriTidList算法[8]，它使用链式结构，取得了更好的效果。然而，候选集的生成仍是该算法本质上难以克服的瓶颈。FP-Growth算法是HAN等[9]提出的一种具有较好性能和伸缩性的频繁项集挖掘算法，其特点是不需要产生候选项集，并且只需扫描2次数据库。也有一些基于FP-Growth算法的改进算法，如凌绪雄等[10]提出的无项头表的FP-Growth算法在时间效率上略有提高。余彪等[11]提出了一种MFP-tree算法，采用分块挖掘的方式处理数据，效率也有一定的提升。在并行化方面，AISSATOU等[12]提出了基于Spark的S-FPG算法，该算法能够更好地挖掘大数据规模下的关联规则；ZHOU等[13]提出了一种基于MapReduce框架的FP-Growth算法的并行化改进算法。

FP-Growth算法的具体执行流程如下。

(1)先扫描一遍数据集，得到项目集中每个项目出现的次数，定义最小支持度(项目出现最少次数)，删除那些小于最小支持度的项目，然后将原始数据集中的条目按项目集中降序进行排列。

(2)第2次扫描，创建频繁项头表(从上往下降序)以及FP树。

(3)对于每个项目(可以按照从下往上的顺序)找到其条件模式基(conditional pattern base，CPB)，递归调用树结构，删除小于最小支持度的项。如果最终呈现单一路径的树结构，则直接列举所有组合；非单一路径的则继续调用树结构，直到形成单一路径即可。

FP-Growth算法分为构造树与挖掘树两个部分，算法伪代码分别如下。

FP树的构造算法：

输入：原始数据库D，最小支持度minsup

输出：数据库D的FP树

扫描数据库D，收集频繁项的集合F和它们的支持度。对F按照支持度降序排序，结果为频繁项头表H;创建FP-树的根节点R，标记为null;

对D中每个事务Trans：

选择 Trans 中的频繁项，并按H中的次序排序。设排序后的频繁项表为[p | P]，p是第一个元素，P是剩余元素的表。调用insert_tree([p|P], R)。

函数insert_tree([p|P], T)：

如果T有子节点N使得N.item-name = p.item-name，则N 的计数增加1;

否则创建一个新节点N将其计数设置为1，链接到它的父节点T，并且在与它同名的频繁项头表中遍历到最后一个节点，添加此新节点N;

如果P非空，递归地调用函数insert_tree(P, N);

FP树的挖掘算法：

输入：FP树和最小支持度minsup

输出：频繁模式集合

通过调用FP_growth(FP_tree, null)实现

if(树含单个路径P) then

对P中节点的每个组合β：

产生模式β∪α，支持度support=β中节点的最小支持度;

Else{

对树头部的每一个ai：

生成模式β=ai∪α，支持度support=ai.support;

构造β的条件模式基和β的条件FP树Treeβ

if Treeβ≠ ∅ then调用 FP_Growth (Treeβ, β)}

2.2 FP-Growth算法的改进

在传统FP-Growth算法中，需要利用FP-Tree构造算法生成一个包含完整频繁项信息的FP树， 其中，FP树的频繁项头表具有2个属性：item-Name(项名称)和next_Node。next_Node是一个指针，指向FP树中具有相同 item-Name 的第1个节点。在此过程中，要循环调用insert_tree( )算法插入新的树节点，其中，有一个步骤就会用到频繁项头表这一数据结构，把FP树中的每个与项头表具有相同名称的项进行连接。每次执行上述过程时都需要回到项头表的同名头节点，然后从头节点开始遍历，直至最后一个同名节点的域，再把新的节点插入最后一个节点后，进入项头表结构中。可以看出，项头表这一数据结构的模型会直接影响 FP-Growth 算法的性能，在数据量较大的情况下，每次都从头节点遍历到尾端然后插入，这种方法的执行效率明显不好，有待改进。

为了解决上述问题，提升算法的效率，本文提出了一种优化后的项头表数据结构，在原有的项头表结构上添加一个新的属性尾节点tail，用于记录每一个数据项当前的最后一个节点。通过这种新的频繁项头表数据结构，执行insert_tree()算法并在项头表插入新节点时，就可以避免遍历当前节点的链表而导致算法效率不佳，直接通过tail属性找到表尾进行新节点的插入即可。在轮胎质量数据分析中，该改进会有更突出的效果，由于这些数据集中相同的项大量存在(如同一主机手会经手大量轮胎)，同样会出现在FP树中的各个分支，故加入新的属性尾节点tail记录数据项的最后一个节点，对轮胎质量数据分析的效率提升会起到很好的作用。

优化后的项头表数据结构见表1。具体定义如下。

表1 优化后的项头表数据结构

Public class HeadTable{

Private String item_Name;//数据项名称

Private Node next_Node;//项头表中的下一个同名节点

Private Node tail;//该项头表中的最后一个同名节点位置

}//优化后的项头表

在执行FP-Tree构造算法时，利用优化的项头表，避免了繁琐的循环遍历操作：

If (HeadTable.tail == null)

Then

HeadTable.next_Node =新节点;

HeadTable.tail =新节点;

Else

HeadTable.tail.next_Node =新节点;

HeadTable.tail =新节点;

引入优化后的频繁项头表后，新的FP-Tree构造算法如下：

FP_Tree(D, minsup)

输入：原始数据库D，最小支持度minsup

输出：数据库D的FP树

扫描数据库D，收集频繁项的集合F和它们的支持度。对F按照支持度降序排序，结果为频繁项头表H;

创建FP-树的根节点R，标记为null;

对D中每个事务Trans：

选择 Trans 中的频繁项，并按H中的次序排序。设排序后的频繁项表为[p | P]，p是第一个元素，P是剩余元素的表。调用insert_tree([p|P], R)。

函数insert_tree([p|P], T)：

如果T有子节点N使得N.item-name = p.item-name，则N 的计数增加1;

否则创建一个新节点N将其计数设置为1，链接到它的父节点T，并且在与它同名的频繁项头表的tail属性中找到当前最末节点，添加此新节点N，并设新节点N为新的tail;

如果P非空，递归地调用函数insert_tree(P, N);

现有以下数据库D，见表2，设最小支持度阈值为3。由该数据库通过算法构造得出的FP树结果见图3。

表2 数据库D

图3 根据优化后的FP-Growth算法构建的FP-TreeFig.3 The FP-Tree built based on the optimized FP-Growth algorithm

3 FP-Growth改进算法在轮胎质量大数据分析应用

3.1 FP-Growth算法改进实验

对改进后的FP-Growth算法进行以下3个实验。

实验1。不同物料编码数据集FP树构造时间对比。取轮胎质量分析数据集中物料编码为221000 994、221003 794、221003483的3组数据作为实验的数据集，数据集分别包含856526、308880、157360个事务，均有35个属性。实验环境为Intel(R) Xeon(R) CPU E5649@2.53 GHz，操作系统为3.10.0-514.26.2.el7.x86_64，4台24G内存计算机，通过JAVA调用Spark并连接HIVE进行实现。结果见表3。

表3 FP-Tree构造时间

实验2。不同数据量级的数据集FP树构造时间对比。取轮胎质量分析数据集中的百万、十万和万级别的数据集，实验环境同实验1。结果见表4。

表4 FP-Tree构造时间

实验3。优化后的FP-Growth算法与改进的BICA算法(一种ADTree算法)对比。取轮胎质量分析数据集中的百万、十万和万级别的数据集，实验环境同实验1。结果见表5。

表5 改进的FP-Growth与改进的BICA对比

通过实验1的3组实验可以明显看出，使用优化后的FP-Growth算法，FP树的构造效率有了明显提升，平均提升效率为26%；实验2对比分析了不同数量级下的FP-Growth算法执行情况，改进后的算法平均效率提升也在20%以上，并且数据集的数量级越大，算法效率提升越快；实验3选取了轮胎质量数据分析的另一个基于ADTree的优化算法进行比较，从实验结果可以看出，在算法执行的时间方面，两者的差距并不明显，但使用ADtree算法进行数据分析时，最终只能得到一个二分树，利用该二分树的每一个节点与分支进行分析，才能得出轮胎质量相关的一些结论，有时ADtree得出的二叉树并不能包含全面结果，会遗漏部分属性的影响；而FP-growth算法挖掘给出的是一条条关联规则，只要给出确定的支持度与置信度，就能得到符合要求的全部规则，没有遗漏；通过关联规则，能够更加直观与清晰地看出属性间的关联关系，进行进一步的分析也更加方便。

3.2 FP-Growth关联分析结果

通过FP-Growth算法得出的关联规则能够帮助我们进行轮胎质量异常数据的分析。以物料编码为221003 794的数据集为例，该数据集的可用样本数为308 880, 其中，质检合格数为306 471, 不合格数为2 409, 不合格率约0.78%。实验设置支持度为300，置信度为1.5%。根据FP-Growth算法的挖掘结果, 使用Hive数据库对质量数据进行回查, 查询挖掘出的关联规则中的频繁项对产品不合格率的影响。共挖掘出45个频繁项集，24条关联规则。因篇幅有限，仅给出部分结果进行展示。FP-Growth算法挖掘得出的一些频繁项集见表6。

表6 频繁项集

以下是通过关联规则进一步分析的过程：

cur_BATCH_ID=20 161 206ZJS_ID=20 070 488 952==>hege=2 380

cur_BATCH_ID=20161206 1264 ==>hege=2 401

以上两条规则说明，批次是20 161 206产出的1264件产品中，不合格的有401件，占比约31.72%，远高于平均不合格率0.78%。这1 264件产品中，经手成型主机手20 070 488的952件产品更是有380件不合格，不合格率为40%。剩余312件产品有21件不合格，不合格率约为6.73%，也远高于平均不合格率。由此得出结论：需要更加关注成型主机手20 070 488与批次20 161 206。

如该主机手与设备的关系：

POT_ID=314ZJS_ID=20070488 2582 ==>hege=2 412

POT_ID=36ZJS_ID=20070488 6151 ==>hege=2 394

以上两条规则显示，产品经手成型主机手20 070 488，并且在POT_ID为314和36的硫化蒸锅上生产时，不合格率分别约为15.96%与6.41%。

这两台硫化蒸锅的平均不合格率也被算法挖掘出来：

POT_ID=314 11690 ==>hege=2 552

POT_ID=36 21570 ==>hege=2 463

POT_ID为314的硫化蒸锅生产的产品，不合格率约4.72%，而POT_ID为36的硫化蒸锅相应的不合格率约2.15%，均比该型号产品的平均不合格率高。由于这两个硫化蒸锅生产的部分产品之前有经过成型主机手20 070 488的操作，故排除后再做分析，POT_ID为314的硫化蒸锅不合格率约1.54%，POT_ID为36的硫化蒸锅不合格率约0.45%，甚至比平均不合格率还要低，故可以排除POT_ID为36的硫化蒸锅的影响。

限于篇幅，此主机手与生产工艺参数相关的一些规则不再列出。由此可见，通过关联规则，可以很方便地对轮胎质量影响因素进行严谨的分析，从而做出合理的猜测与推论。

4 结语

针对现有频繁模式增长(FP-Growth)算法存在FP树建树性能较低的问题，本文提出了一种改进的FP-Growth算法，在原有的频繁项头表基础上新增一个tail属性，加速FP-Tree构建。实验结果表明，改进后的FP-Growth算法能够有效提高轮胎质量异常数据的关联分析效率，并且适用于大数据量的数据挖掘。通过关联分析产生的频繁项集分析，能够找出影响轮胎质量的生产制造过程重要因素，帮助企业改善工艺流程和精益生产，降低产品不良率，提升产品质量。