Apriori算法改进及其在资产管理中的应用

郑 斌

(福建江夏学院电子信息科学学院， 福州 350108)

企业资产管理工作涉及多种资产项目和资产数据，应用数据挖掘技术挖掘资产数据之间的关联规则，从而为管理决策提供反映企业资产运营实际的数据信息，有助于企业实行科学决策，提高资产利用率，节约企业经费，提升企业经济效益。本次研究，结合轨道交通工程建设单位资产数据关联规则挖掘的需要，对Apriori算法进行了优化。

1 关于数据挖掘的关联算法

1.1 Apriori算法简介

Apriori算法是关联规则挖掘中的经典算法，为基于两阶段频集思想的递推算法。该算法的基本思想是：首先，应用描述的方法找出所有的频繁项集(即所有支持度大于最小支持度的项集，这些项集出现的频繁性至少和预定义的最小支持度一样)，由频繁项集产生强关联规则；然后，应用关联规则挖掘出频繁项集中每个大于等于最小可信度的项集。

Apriori算法的实现过程是：首先对数据库进行全集扫描，将包含所有项为n阶的项集作为初始值；然后在此项集中进行i阶迭代，直至项集为空，得到i阶的候选项集Ci；接下来继续在数据库中扫描，获得相对应的支持数，找到Ci中大于等于最小支持数的i阶项集[4]。该算法的伪代码如下：

输入：数据集D以及最小的支持度min_up

输出：最大的频繁项集Ii，事务t0=D

1)I1=D

2)for(i=2;Ii-1≠φ;i++)

3)Ci=Apriori(Ii-1)

4)while(t∈D)

5)Ct=subset(Ci,t)

6)while(C∈Ct)

7)C.sup++

8)Ii={C∈Ck|C.sup≥min.up}

Apriori算法的优势是：在支持度较低的情况下，扫描数据库的次数较少，空间复杂度较低。它的缺点是：会产生大量的候选集，需要多次迭代扫描数据库，从而导致搜索速度降低，占用过多的内存空间。

1.2 Apriori算法的改进

针对Apriori算法的不足对其进行改进。首先将数据挖掘的研究对象划分为n个数据规模的部分，然后将挖掘得到的结果进行合并。基本流程为：

1)将要挖掘的数据划分为n个部分；

2)对每一个模块部分都进行频繁项目集，存储在一个频繁项目集中；

3)将存储的频繁项目集进行合并，形成全局候选的频繁项目集；

4)针对全局的频繁项目集扫描数据库，计算该频繁项目集的实际支持度，从而实现对频繁项的确定。

改进后的算法具有如下特点：

第一，在第一次扫描数据库的时候就生成一组频繁项目集。以这些可能的频繁项目集为基础来确定数据库的实际支持度，进而得到所需的最终频繁项目集数目，并获取最可能存在的关联规则。

第二，将数据库中的划分为n个部分，首先将每个部分都产生一个频繁项目集，然后再将这些频繁项目集合并为一个全局候选频繁项目集。这种方式在信息量增加迅速的情况下，能够尽可能地降低频繁项数量对数据挖掘效率的影响，但不能降低对数据库扫描的次数，即当频繁项目集的最大值长度为K，则需要对数据库扫描K次。

第三，把要挖掘的数据划分为n个部分(子模块)，对各部分的每个事务都添加一个属性，并记录该事务所包含的项目数。

2 资产管理中的数据挖掘

资产管理数据往往来自多个部门，数量庞大而繁杂。比如城市轨道交通工程建设单位，其资产管理涉及的资产数据包含：设备采购与管理部门购买和维护设备的有关数据，土建部门组织各种施工产生的相关数据，拆迁部门开展各种拆迁项目产生的有关数据，运营移交部门在各个阶段进行资产移交产生的数据[1]，等等。要给管理和决策层提供可靠的数据信息，就需要对资产数据进行挖掘分析。

2.1 资产数据库设计

根据轨道交通工程建设单位对资产数据分析的需要，设计资产数据库时，确定资产、用户、资金共3个主题域维度，并以资产主题为核心。考虑到随着轨道交通行业的快速发展，对资产数据分析的需求也在不断变化，且资产数据量也会逐步增加，设计了2级粒度数据层次，即详细数据和高度综合数据[2]。详细数据包括单位各部门每天的数据流动和明细；高度综合数据包括各部门每月、每年的资产数据集合，以统计数据报表的形式长期存储。

资产数据库的逻辑模型采用雪花模型[3-4]。雪花模型可以将各个维度的表格拓展为实时表，由此构成局部层次区域(见图1)。构建好的多维主题表，数据冗余度较低，可以确保数据的一致性，可以实现较好的数据粒度，规则泛化能力较强。数据库构建完成后，需要装填数据。具体流程是：首先抽取源数据，按构建的逻辑数据模型转换相关的数据；然后从物理数据模型中提取相关的资产数据变化特征，将其填补到资产数据库中；最后应用改进的Apriori算法实现数据挖掘。

图1 资产数据库的逻辑模型

2.2.1 资产指标选择

在数据挖掘过程中规约属性和分类数据，能够降低属性值，简化挖掘规则。我们通过设计属性约束方式来降低候选项集数量，提升关联规则效率[5]。轨道交通工程建设单位的资产管理涉及一系列资产，资产数据的数量庞大而繁杂。从中选择下列较有代表性的资产指标。

A. 资产建设费用。这是固定资产，包含建设资产的原始费用。

B. 资产剩余使用年率。资产使用年限反映着资产的折旧费用，这是资产管理的关键指标。

C. 资产年使用率。在使用过程中，各种资产都会由于损耗而降低价值。

D. 资产质量评估值。在资产管理过程中要对每个指标进行质量评估，以此确定资产的价值。

2.2.2 数据处理方法

(1) 数据泛化。这是对数据库中与任务相关的大量数据进行抽象概述的一个分析过程。未通过泛化的数据，通常在属性值的表达中没有规律可寻，且表述复杂，没有一个明显的特点[6]。

(2) 数据离散化。对非连续的数据，通常应用泛化技术来进行处理；对连续性数据则采用离散化处理方式。将连续的数据分成若干个合理的区间，设置一个区间线来表示各数据汇总值，并计算得到该区间范围的各个统计值，以特定的离散符号表示。步骤是先确定分割离散点，然后对分段区间进行统计[7]。

2.3 改进算法的规则生成

对资产数据进行挖掘时，在关联规则中添加约束，可以显著提升挖掘效率。为了研究资产的共性，对资产信息数据进行约束。I=。其中，tid为资产类别编号；name指资产名称；A表示购置的资产信息；purchasetiame即购买时间；categories表示不同类型的资产类别。

对于每个单项事务，T=。其中，rid是一个全局事务变量；itemsets为该事务的项目集合。

对给定的资产，定义其中两个单项事务为I1和I2。当其存在关联属性时，例如是在同一个时间段内购置的资产，则认为这两者之间存在属性连接，将共同属性作为事务标号。如此，逐步增加新事务的数量。

3 算法实验及结果分析

实验开发语言为C#语言，数据库为SQL 2008。使用联想电脑，内存为2 GB，CPU采用Intel i5，主频大小为1.6 GHz。实验数据集为某市五条地铁运营过程中购置的资产事务数据集，数据量为313 MB，包含资产记录86.2万条，属于海量数据集。

确定数据库结构后，首先规约数据属性，并根据量化规则将其转换为相同的格式，应用约束规则来预处理相同格式的数据；然后引用SQL语句统计功能来完成数据统计；最后运用改进的Apriori算法完成对候选项集的计算，由此构建强关联规则的频繁项集。

轨道交通工程建设单位的资产数据量较大，且资产属性量也较多，挖掘出来的关联规则数量比较多。为了验证算法的挖掘效率和精确性，将传统的Apriori算法在不同支持度下的挖掘时间与改进算法进行了比较，结果如图2所示。

图2 在不同支持度下新旧算法所需的挖掘时间

传统Apriori算法和改进算法都是随着支持度的上升，所消耗时间越来越少；但改进后的Apriori算法所需的时间明显少很多，它具有更好的时间效率。

在资产数据挖掘中，分别设置两种最小支持度和最小信任度，即(0.1，0.3)和(1.6，1.5)，对资产数据进行遍历处理。结果显示，改进后的Apriori算法能够快速获取到关联规则(见表1)。在支持度不同的情况下，改进算法计算频繁项的速度非常快。当选择支持度为0.1时，运用改进算法计算得到频繁项用时为45 min，约为传统算法用时的15。运用改进算法获取到的关联规则数量也较多。随着支持度的上升，关联规则数量有明显降低。最小支持度增加过大，会导致一些正确的规则数降低，从而降低不同数据之间的关联性。

表1 在不同的最小支持度和信任度下算法的效率对比

说明：提升效率=(传统算法-改进算法)÷传统算法×100%。

4 结 语

根据轨道交通工程建设单位资产管理的需要，应用数据挖掘技术挖掘资产数据之间的关联规则。联系资产数据的特点，改进Apriori算法，构建了频繁项生成优化模型，应用数据属性规约方式优化约束关联规则。实验结果表明，改进后的Apriori算法具有更好的时间效率，可适用于海量数据集。