基于粗糙集改进的Apriori算法在公用经费支出中的应用

毕浩田

（中北大学信息与通信工程学院 山西 太原 030051）

0 引言

公用经费支出是财政预算支出的重要组成部分，合理安排好公用经费的支出对于财政活动有重要意义。通过数据挖掘算法为基础，对公用经费支出科目进行分析，能够发现支出科目之间的特定联系，根据支出科目之间联系，制定适用的公用经费支出标准，可以有效减少财政支出，从而使经费支出结构更加合理。

目前已有多人将数据挖掘算法应用到财政领域，陈夭元等[1]提出了基于数据挖掘的部门决算数据研究，运用关联规则算法建立部门决算数据挖掘系统。黄振国等[2]将改进时态的算法应用到绩效评价中，但关联算法的参数值确定不够科学，需要继续对该算法进行改进。叶席军[3]等对财政大数据审计技术研究及实践对Apriori 算法进行可改进，利用回归模型对财政数据进行预测，但是没有详细介绍Apriori 算法的应用。李龙等[4]研究了数据挖掘技术在部门预算系统中的应用，明确财政部门与各项费用之间的关联关系，但是没有对算法的性能进行分析研究。

本文提出了基于粗糙集的Apriori 算法，利用属性依赖中的核心属性数据[5]对数据进行约简，采用计算候选集频数优化策略提升算法运行速度。最后，将改进的算法应用到公用经费支出分析中，发现影响公用经费支出中的主要因素。

1 基于粗糙集改进的apriori算法

1.1 传统的Apriori 算法

Apriori 算法是典型的关联算法，该算法已很成熟被广泛地应用到各行各业。一般是结合实际对Apriori 算法进行适度改进，使其满足适用情况。Apriori 算法流程如图1所示。

图1 Apriori 算法流程图

Apriori 算法主要通过逐层迭代的方法来确定频繁项，即由生成的频繁K 项集确定频繁K+1 项集。其主要步骤是：第一步，扫描所需的数据库D，得到所需的候选集C1，根据已设定的支持度确定符合要求的频繁项集L1；第二步，通过自带的连接算法由L1产生候选集C2，然后第二次扫描数据库，根据所设定的支持度阈值确定频繁集L2；第三步，重复步骤二，直到最后不再产生候选集Ck+1，就可以根据支持度确定出频繁集Lk；第四步，分别计算频繁项集间的置信度，根据所设定的置信度阈值输出所对应的规则。

由上可以知道Aprioi 算法的主要缺点为：需要对数据库进行重复扫描，会浪费大量时间；候选项集项产生过多，在项集长度不断增大的情况下，该算法运算速度会随着集合长度的增加而越来越慢，增大内存运行的负担。

1.2 基于粗糙集改进的apriori 算法

针对算法存在的不足，设计了一种基于粗糙集改进的apriori 算法。本节以Apriori 算法为基础，利用粗糙集对数据进行约减，减少数据规模，同时，采用计算候选集频数策略减少扫描数据的次数，从以上两方面对Apriori算法进行改进。改进后的算法流程如图2所示。

图2 基于粗糙集改进的apriori 算法流程图

改进后的算法步骤具体如下：

（1）对原始数据进行离散化处理，有效地降低复杂度，方便数据的存储。

（2）利用粗糙集算法原理构建信息系统[6]，使数据规模得以减少，同时生成相应的布尔矩阵DM。

（3）计算出布尔矩阵DM 中每列值为1 的总数即CC 值，若某列的CC 值小于最小支持度阈值，则将该列删除就可以得到频繁项L1。计算出布尔矩阵DM 中每行值为1 的总数即RC 值，若该行的RC 值小2 则将该行删除。最后将矩阵的行和列按降序的方式排序，得到矩阵DM1。

（4）扫描DM1生成IFP-Tree，将每个节点的标记值flag_i=(x，y)添加到相应的节点处。

（5）根据计算候选集频数优化策略，通过对L1进行预剪枝得到L1′，由L′自连接生成C2，在FP-Tree树状图中找到对应的分支，由此得到该项集的支持度计数，而后将C2进行剪枝即将小于最小支持度阈值的项集删除，得到频繁二项集L2。重复该步骤，直至不再产生频繁项集。

（6）根据置信度输出关联规则。

1.2.1 粗糙集算法设计

在粗糙集理论方法中，属性（知识）约简是对多属性决策表或信息表进行数据挖掘的主要手段[7]。通过对原始数据的分析比较，属性约简能从纷繁复杂的数据结构中有效地提炼出用户最为感兴趣的数据。其中数据的独立性反映了数据之间的依赖程度，所以依赖度是数据约简的最重要的概念[8]。

其实现步骤可总结如下：

（1）在数据中找到所需的条件属性和决策属性，并用适当的符号将条件属性按决策属性表示出来。

（2）对不符合决策属性的条件属性进行删除，将剩余的条件属性按重要程度进行重新排序，完成核的求解，实现数据的约简。其主要代码如下：

#决策属性基本集

y_basic_set=sorted([vfork,vinbasic_set(y_data).items()])

num=Euclidean(x_data)

#print(num)

x_basic_set=[vfork,vinkey_basic(num,t1).items()]

#γC(D)

pos=[]

foriinx_basic_set:

forjiny_basic_set:

ifset(i).issubset(j):

pos.append(i)

#pos.sort()#排序

r_x_y=len(pos)/len(data)#也许可以写一个card 函数

print('依赖度r_x_(y):',r_x_y)

#计算每一个γ(C-a)(D)

#获取条件属性个数为总下标存入集合

#收集属性重要性

imp_attr=[]

columns_num=list(range(len(x_data.columns)))

foriincolumns_num:

c=columns_num.copy()

c.remove(i)

u=data.iloc[:,c]

num=Euclidean(u)

u=sorted([vfork,vinkey_basic(num,t1).items()])

#γC(D)

pos_va=[]

forkinu:forjiny_basic_set:

ifset(k).issubset(j):

pos_va.append(k)

r_x_y_2=len(pos_va)/len(data)

r_diff=round((r_x_y-r_x_y_2),4)

imp_attr.append(r_diff)

dict_imp={}

foro,pinenumerate(imp_attr):

dict_imp[data.columns[o]]=p

result=dict_imp

#print(imp_attr)

Return result

（3）将约简后的数据生成布尔矩阵

1.2.2 计算候选集频数优化策略

在Apriori 算法中，为了确定支持度需要多次扫描数据库才造成Apriori 算法运行缓慢。本次提出来一种计算候选集频数优化策略来提升Apriori 算法的运行速度。

首先利用矩阵式运算获得频繁项C1，对C1进行预剪枝得到L1，然后利用Apriori 算法的自连接性质，通过L1自主生成候选二项集C2。之后，第二次扫描数据库，利用fp-tree 中的生长树形成树结构，并在每个节点处添加标记flagitem=（i,j）。根据L1明确IX和Iy中的最小项，在计算候选项集C2的支持度时，只需要扫描特定分支即含有最小项事务结点链[9]避免扫描整个数据库，并结合该节点处标记[10]flagitem=（i,j）中j 中的数值，即可得到C2的计数，最后根据设定的最小支持度得到频繁二项集。对获得的频繁二项集做上述第二步同样的操作就可以快速计算出C3支持度计数，重复以上步骤就可以得来最终的结果。使用计算候选集频数优化策略可以有效节省空间和时间资源，提升算法运行效率。

defapriori(D,minSupport):

flag=1

C1=createC1()#生成C1 候选项集

L1,supportData=scanD(D,C1,minSupport)#扫描数据集，生成L1 频繁项集

L=[L1]

k=2

scan=1

while(len(L[k-2])>0):#频繁项集不为空

Ck=aprioriGen(L[k-2],k)#调用候选集生成算法

Lk,supK=scanD(D,Ck,minSupport)#调用计算候选集频数算法生成Lk 频繁项集

L.append(Lk);supportData.update(supK)#添加新频繁项集和他们的支持度

k+=1

returnL,supportData

defscanD(dataSet,Ck,minSupport):#计算候选集频数算法

ssCnt={}#记录每个候选项的个数

foriteminTree.children:

forcaninCk:

ifcan.issubset(tid):

ssCnt[can]=flagitem.get（’j’）#计算每一个项集出现的频率

numItems=float(len(dataSet))

retList=[]

supportData={}

forkeyinssCnt:

support=ssCnt[key]/numItems

ifsupport>=minSupport:

retList.insert(0,key)#将频繁项集插入返回列表的首部

supportData[key]=support

returnretList,supportData#retList 为在Ck 中找出的频繁项集

2 实验与结果

为确定本次算法改进的合理性，将本次改进的算法与其他三种基于Apriori 改进的算法进行对比，主要从算法的运行时间和冗余规则数进行分析来比较该算法的优越性。本次实验所采用的数据为某市财政部门公用经费支出数据，数据规模为3 000 条。设置关联规则算法的支持度均为0.2，最小置信度均为0.4，提升度阈值均为1.4、兴趣度阈值均为0.1。不同算法的实验结果如表1所示。由表1可以看出本文提出的改进的Apriori 算法可以大大降低冗余规则条数，算法运行时间也得到缩短，提高了预警规则的挖掘效率。

表1 算法运行时间对比表

本文提出的改进的Apriori 算法在剔除掉无关的967条冗余规则后，共挖掘到有效规则300 条。部分规则如表2所示。

表2 公用经费支出关联规则表

表2中第1～7 条规则，前列都为T29，说明在职人员数是决定公用经费支出多少的关键因素，在职人员数越多，T1办公费、T2印刷费、T5邮电费、T7差旅费、T11会议费T25下乡人员经费、T27福利费、T28公务交通补贴支出越多；T1⇒T2，T1⇒T3说明办公费越高，印刷费和邮电费就越高；T11⇒T1，T11⇒T2，T11⇒T5说明会议费越多，办公费，邮电费，印刷费就越多；T28⇒T29说明公务交通补贴越高，在职人员越多。通过数据挖掘形成的规则，在编制公用经费预算时要参照在职人员数，当在职人员数增长时，T1办公费、T2印刷费、T5邮电费、T7差旅费、T11会议费T25下乡人员经费、T27福利费、T28公务交通补贴都应该相应增加；可以适当减少会议的次数，会使办公费、邮电费、印刷费用减少。

3 结论

本文针对Apriori 算法的缺陷，提出了基于粗糙集改进的Apriori 算法，首先利用粗糙集对原始数据进行约减，然后对Apriori 算法进行改进，通过计算候选集频数减少扫描数据库的次数，采用多种方式对冗余规则进行筛选，提升运算效率。以某市的财政预算支出数据为核心，对财政预算支出数据进行预处理后，利用改进的算法重点挖掘公用经费支出较大时支出科目之间的关系，形成公用经费支出分析规则库，通过减少某一经费的预算支出，达到缩减预算支出的目的。