Fp-growth改进算法在公务用车调度系统中的研究与应用∗

陈 君肖 锋

（1.渭南师范学院网络安全与信息化学院网络安全与信息化工程技术中心 渭南 714000）（2.西安工业大学计算机科学与工程学院 西安 710032）

1 引言

我们可以通过公务用车调度管理系统对企事业单位的公务用车进行车辆调度、驾驶员管理、车辆管理等工作，能够实现管理员对公务用车的信息的添加、删除、修改、查询等，在最短时间实现公务用车的合理调度，通过使用此系统可以完善车队的管理，提高管理质量和管理效率。因此有效地对网络招聘系统中的数据进行分析挖掘，找出其中的规律已显得尤为重要。

本文利用基于项头表节点的Fp-growth改进算法，对公务用车调度管理系统中车辆类型、使用部门、用车人数、车牌号、所属部门、驾驶员、行驶里程等信息进行对比、分析，从中发现用车规律，方便车辆调度。例如：使用哪种车型的一般用车人数在多少人，哪些部门经常使用什么车型的车辆，哪些单位用车使用车辆较为频繁，行车年限在多少年的车辆使用率较高等。经过对相关数据的分析有效地帮助有关部门对车辆的调度进行更好的分配和管理，提高车辆调度效率［1］。

2 数据挖掘及关联规则概念

数据挖掘（Data Mining）是指从大量的、不完全的、模糊的、有噪声的、随机的数据中提取隐含其中的、事先不知道的、有用的知识和信息的过程［2］。数据挖掘主要包括概念描述，关联分析、分类、预测和聚类分析等内容［3］。数据挖掘技术目前已在制造业、金融业、电信业、保险业、医疗和零售业等领域得到了广泛的应用［4］。随着信息技术的快速发展，数据挖掘技术将成为商业智能、生物工程、网络服务等领域研究热点［5］。

关联规则是数据挖掘的一种，关联规则的挖掘就是产生支持度和置信度大于使用者设定的最小取值的有效性规则［6］。关联规则挖掘可分为两步：首先，找出所有频繁项集，就是找出所有出现频率至少和预定义的最小支持度一样的项集；然后，由频繁项集产生关联规则［7］。

3 FP-Growth算法

FP-growth算法是韩家炜等提出的一种基于FP-tree的频繁项集挖掘算法，此算法是将原始数据集压缩到一棵FP-tree上，在整个挖掘过程中只需要扫描原始数据集两次，并且在它的挖掘过程中不产生候选项集，挖掘效率得到了一定的提高［8～10］。

FP-Growth算法具有以下优点：首先，FP-Growth算法只需要扫描原始数据集两次，可以将一个大型的数据库有效地压缩成比原数据库小很多的高密度的数据结构，避免了对数据库的重复扫描。其次，FP-Growth算法是基于FP-tree的挖掘算法，它采取模式增长的递归性策略，提出无候选项集的挖掘方法，在进行频繁模式挖掘时有效地提高挖掘的效率［11～13］。

4 基于项头表节点的Fp-growth改进算法

4.1 基本思想及算法描述

基于项头表节点的FP-growth改进算法是指在Fp-tree中找到与头表具有一样的Node-Link时，都必须返回头表中，逐个找出最后一个Node-Link项后，将新找到的项加入，每次有一个新的项目出现时都必须从头表第一个项开始逐个寻找，直到找出最后一个，把原算法FP-tree和项头表的Node_link字段删除，将Ln当作项头表［14］。对任意频繁项ai，先找到所有FP-tree节点的Item-name与ai的项名一样的节点，针对找到的每个树节点寻找其频繁模式，找到频繁项ai的所有频繁模式［15］。改进后的算法比原算法节省1/5树的空间，它将Ln当作了项头表，所以省去了项头表空间。

4.2 改进后算法的优点

FP-growth算法在Fp-tree中查找与头表中具有一样的Node-Link时，都必须回到头表中，逐个找出最后一个Node-Link的项后，再将新找到的项加入其中，这就相当于每有一个新的项出现时都必须从头表第一个开始查找，直到找出最后一个为止，这样数据量大的时候效率就会相对较低。而改进后的基于项头表节点的Fp-growth算法先找到所有Fp-tree节点的Item-name与ai的项名一样的节点，针对找到的每个树节点找到它的频繁模式，这样也就找到了频繁项ai的所有频繁模式，可节省1/3的项头表空间和1/5树的空间。实验结果表明，基于项头表节点的FP-growth改进算法性能优于FP-growth算法。

5 基于项头表节点的FP-Growth算法的应用

本文在内存为4GB，CPU为intel2.6GHz，操作系统为Windows 10的硬件环境下，在Microsoft Vi⁃sual Studio 2015开发平台中使用C＃语言，应用FP-growth算法对公务用车调度管理系统的数据库进行数据挖掘并得出结论。

5.1 整理与转换数据

首先对公务用车调度管理系统数据库中的数据进行整理。整理出的有公务用车调度信息主要包括：车辆类型、使用部门、用车人数、车牌号、所属部门、驾驶员、行驶里程等。其中例举了一条用户的记录如表1所示，关系数据库属性值与事务数据集中的项目对应关系如表2所示，再将其进行数据转换，转换后的事务数据如表3所示。

表1 记录的字段名含义

表2 对应关系表

表3 转换后的事务数据

5.2 结果及分析

下面我们对整理和转换后的数据进行挖掘，输入数据为事务数据表、最小支持度、最小值信度，输出频繁项集。设定最小支持度为s=5%，最小置信度为c=20%。挖掘结果如表4所示。

从表4可以得出以下结论：规则A表示使用SUV车辆的一般用车人数在3到4人，规则B表示使用MPV型车辆的用车人数在5到7人，与C表示使用商务面包型车辆的用车人数在8到16人，规则D和E表示后勤和营销部分使用车辆较为频繁，规则F表示行车里程在4到8万公里，行车年限在2到5年的车辆使用率较高，规则G表示后勤部门使用MPV型车辆较多。

表4 挖掘结果

6 结语

本文将Fp-growth算法进行了改进，提高了挖掘速度，并用改进后的算法对公务用车调度管理系统中的数据进行了挖掘和分析，从中发现公务用车的使用规律，为车辆调度部门和车辆使用部门提供了有用的信息。在算法的实际应用过程中，特别是对大型事务数据库进行挖掘时，数据的准备与选择至关重要，它直接关系到数据挖掘的结果是否成功，是否具有实际效益，另在数据挖掘的过程中选取恰当的最小支持度和最小置信度也是十分重要的，如取值过小，挖掘结果就会出现大量无用规则，影响执行效率、浪费系统资源，如取值过大，可能会找不出相关规则，无法达到目的。