基于粗糙集改進(jìn)的Apriori算法在公用經(jīng)費(fèi)支出中的應(yīng)用

畢浩田

（中北大學(xué)信息與通信工程學(xué)院 山西 太原 030051）

0 引言

公用經(jīng)費(fèi)支出是財(cái)政預(yù)算支出的重要組成部分，合理安排好公用經(jīng)費(fèi)的支出對(duì)于財(cái)政活動(dòng)有重要意義。通過數(shù)據(jù)挖掘算法為基礎(chǔ)，對(duì)公用經(jīng)費(fèi)支出科目進(jìn)行分析，能夠發(fā)現(xiàn)支出科目之間的特定聯(lián)系，根據(jù)支出科目之間聯(lián)系，制定適用的公用經(jīng)費(fèi)支出標(biāo)準(zhǔn)，可以有效減少財(cái)政支出，從而使經(jīng)費(fèi)支出結(jié)構(gòu)更加合理。

目前已有多人將數(shù)據(jù)挖掘算法應(yīng)用到財(cái)政領(lǐng)域，陳夭元等[1]提出了基于數(shù)據(jù)挖掘的部門決算數(shù)據(jù)研究，運(yùn)用關(guān)聯(lián)規(guī)則算法建立部門決算數(shù)據(jù)挖掘系統(tǒng)。黃振國(guó)等[2]將改進(jìn)時(shí)態(tài)的算法應(yīng)用到績(jī)效評(píng)價(jià)中，但關(guān)聯(lián)算法的參數(shù)值確定不夠科學(xué)，需要繼續(xù)對(duì)該算法進(jìn)行改進(jìn)。葉席軍[3]等對(duì)財(cái)政大數(shù)據(jù)審計(jì)技術(shù)研究及實(shí)踐對(duì)Apriori 算法進(jìn)行可改進(jìn)，利用回歸模型對(duì)財(cái)政數(shù)據(jù)進(jìn)行預(yù)測(cè)，但是沒有詳細(xì)介紹Apriori 算法的應(yīng)用。李龍等[4]研究了數(shù)據(jù)挖掘技術(shù)在部門預(yù)算系統(tǒng)中的應(yīng)用，明確財(cái)政部門與各項(xiàng)費(fèi)用之間的關(guān)聯(lián)關(guān)系，但是沒有對(duì)算法的性能進(jìn)行分析研究。

本文提出了基于粗糙集的Apriori 算法，利用屬性依賴中的核心屬性數(shù)據(jù)[5]對(duì)數(shù)據(jù)進(jìn)行約簡(jiǎn)，采用計(jì)算候選集頻數(shù)優(yōu)化策略提升算法運(yùn)行速度。最后，將改進(jìn)的算法應(yīng)用到公用經(jīng)費(fèi)支出分析中，發(fā)現(xiàn)影響公用經(jīng)費(fèi)支出中的主要因素。

1 基于粗糙集改進(jìn)的apriori算法

1.1 傳統(tǒng)的Apriori 算法

Apriori 算法是典型的關(guān)聯(lián)算法，該算法已很成熟被廣泛地應(yīng)用到各行各業(yè)。一般是結(jié)合實(shí)際對(duì)Apriori 算法進(jìn)行適度改進(jìn)，使其滿足適用情況。Apriori 算法流程如圖1所示。

圖1 Apriori 算法流程圖

Apriori 算法主要通過逐層迭代的方法來確定頻繁項(xiàng)，即由生成的頻繁K 項(xiàng)集確定頻繁K+1 項(xiàng)集。其主要步驟是：第一步，掃描所需的數(shù)據(jù)庫D，得到所需的候選集C1，根據(jù)已設(shè)定的支持度確定符合要求的頻繁項(xiàng)集L1；第二步，通過自帶的連接算法由L1產(chǎn)生候選集C2，然后第二次掃描數(shù)據(jù)庫，根據(jù)所設(shè)定的支持度閾值確定頻繁集L2；第三步，重復(fù)步驟二，直到最后不再產(chǎn)生候選集Ck+1，就可以根據(jù)支持度確定出頻繁集Lk；第四步，分別計(jì)算頻繁項(xiàng)集間的置信度，根據(jù)所設(shè)定的置信度閾值輸出所對(duì)應(yīng)的規(guī)則。

由上可以知道Aprioi 算法的主要缺點(diǎn)為：需要對(duì)數(shù)據(jù)庫進(jìn)行重復(fù)掃描，會(huì)浪費(fèi)大量時(shí)間；候選項(xiàng)集項(xiàng)產(chǎn)生過多，在項(xiàng)集長(zhǎng)度不斷增大的情況下，該算法運(yùn)算速度會(huì)隨著集合長(zhǎng)度的增加而越來越慢，增大內(nèi)存運(yùn)行的負(fù)擔(dān)。

1.2 基于粗糙集改進(jìn)的apriori 算法

針對(duì)算法存在的不足，設(shè)計(jì)了一種基于粗糙集改進(jìn)的apriori 算法。本節(jié)以Apriori 算法為基礎(chǔ)，利用粗糙集對(duì)數(shù)據(jù)進(jìn)行約減，減少數(shù)據(jù)規(guī)模，同時(shí)，采用計(jì)算候選集頻數(shù)策略減少掃描數(shù)據(jù)的次數(shù)，從以上兩方面對(duì)Apriori算法進(jìn)行改進(jìn)。改進(jìn)后的算法流程如圖2所示。

圖2 基于粗糙集改進(jìn)的apriori 算法流程圖

改進(jìn)后的算法步驟具體如下：

（1）對(duì)原始數(shù)據(jù)進(jìn)行離散化處理，有效地降低復(fù)雜度，方便數(shù)據(jù)的存儲(chǔ)。

（2）利用粗糙集算法原理構(gòu)建信息系統(tǒng)[6]，使數(shù)據(jù)規(guī)模得以減少，同時(shí)生成相應(yīng)的布爾矩陣DM。

（3）計(jì)算出布爾矩陣DM 中每列值為1 的總數(shù)即CC 值，若某列的CC 值小于最小支持度閾值，則將該列刪除就可以得到頻繁項(xiàng)L1。計(jì)算出布爾矩陣DM 中每行值為1 的總數(shù)即RC 值，若該行的RC 值小2 則將該行刪除。最后將矩陣的行和列按降序的方式排序，得到矩陣DM1。

（4）掃描DM1生成IFP-Tree，將每個(gè)節(jié)點(diǎn)的標(biāo)記值flag_i=(x，y)添加到相應(yīng)的節(jié)點(diǎn)處。

（5）根據(jù)計(jì)算候選集頻數(shù)優(yōu)化策略，通過對(duì)L1進(jìn)行預(yù)剪枝得到L1′，由L′自連接生成C2，在FP-Tree樹狀圖中找到對(duì)應(yīng)的分支，由此得到該項(xiàng)集的支持度計(jì)數(shù)，而后將C2進(jìn)行剪枝即將小于最小支持度閾值的項(xiàng)集刪除，得到頻繁二項(xiàng)集L2。重復(fù)該步驟，直至不再產(chǎn)生頻繁項(xiàng)集。

（6）根據(jù)置信度輸出關(guān)聯(lián)規(guī)則。

1.2.1 粗糙集算法設(shè)計(jì)

在粗糙集理論方法中，屬性（知識(shí)）約簡(jiǎn)是對(duì)多屬性決策表或信息表進(jìn)行數(shù)據(jù)挖掘的主要手段[7]。通過對(duì)原始數(shù)據(jù)的分析比較，屬性約簡(jiǎn)能從紛繁復(fù)雜的數(shù)據(jù)結(jié)構(gòu)中有效地提煉出用戶最為感興趣的數(shù)據(jù)。其中數(shù)據(jù)的獨(dú)立性反映了數(shù)據(jù)之間的依賴程度，所以依賴度是數(shù)據(jù)約簡(jiǎn)的最重要的概念[8]。

其實(shí)現(xiàn)步驟可總結(jié)如下：

（1）在數(shù)據(jù)中找到所需的條件屬性和決策屬性，并用適當(dāng)?shù)姆?hào)將條件屬性按決策屬性表示出來。

（2）對(duì)不符合決策屬性的條件屬性進(jìn)行刪除，將剩余的條件屬性按重要程度進(jìn)行重新排序，完成核的求解，實(shí)現(xiàn)數(shù)據(jù)的約簡(jiǎn)。其主要代碼如下：

#決策屬性基本集

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)#也許可以寫一個(gè)card 函數(shù)

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

#計(jì)算每一個(gè)γ(C-a)(D)

#獲取條件屬性個(gè)數(shù)為總下標(biāo)存入集合

#收集屬性重要性

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）將約簡(jiǎn)后的數(shù)據(jù)生成布爾矩陣

1.2.2 計(jì)算候選集頻數(shù)優(yōu)化策略

在Apriori 算法中，為了確定支持度需要多次掃描數(shù)據(jù)庫才造成Apriori 算法運(yùn)行緩慢。本次提出來一種計(jì)算候選集頻數(shù)優(yōu)化策略來提升Apriori 算法的運(yùn)行速度。

首先利用矩陣式運(yùn)算獲得頻繁項(xiàng)C1，對(duì)C1進(jìn)行預(yù)剪枝得到L1，然后利用Apriori 算法的自連接性質(zhì)，通過L1自主生成候選二項(xiàng)集C2。之后，第二次掃描數(shù)據(jù)庫，利用fp-tree 中的生長(zhǎng)樹形成樹結(jié)構(gòu)，并在每個(gè)節(jié)點(diǎn)處添加標(biāo)記flagitem=（i,j）。根據(jù)L1明確IX和Iy中的最小項(xiàng)，在計(jì)算候選項(xiàng)集C2的支持度時(shí)，只需要掃描特定分支即含有最小項(xiàng)事務(wù)結(jié)點(diǎn)鏈[9]避免掃描整個(gè)數(shù)據(jù)庫，并結(jié)合該節(jié)點(diǎn)處標(biāo)記[10]flagitem=（i,j）中j 中的數(shù)值，即可得到C2的計(jì)數(shù)，最后根據(jù)設(shè)定的最小支持度得到頻繁二項(xiàng)集。對(duì)獲得的頻繁二項(xiàng)集做上述第二步同樣的操作就可以快速計(jì)算出C3支持度計(jì)數(shù)，重復(fù)以上步驟就可以得來最終的結(jié)果。使用計(jì)算候選集頻數(shù)優(yōu)化策略可以有效節(jié)省空間和時(shí)間資源，提升算法運(yùn)行效率。

defapriori(D,minSupport):

flag=1

C1=createC1()#生成C1 候選項(xiàng)集

L1,supportData=scanD(D,C1,minSupport)#掃描數(shù)據(jù)集，生成L1 頻繁項(xiàng)集

L=[L1]

k=2

scan=1

while(len(L[k-2])>0):#頻繁項(xiàng)集不為空

Ck=aprioriGen(L[k-2],k)#調(diào)用候選集生成算法

Lk,supK=scanD(D,Ck,minSupport)#調(diào)用計(jì)算候選集頻數(shù)算法生成Lk 頻繁項(xiàng)集

L.append(Lk);supportData.update(supK)#添加新頻繁項(xiàng)集和他們的支持度

k+=1

returnL,supportData

defscanD(dataSet,Ck,minSupport):#計(jì)算候選集頻數(shù)算法

ssCnt={}#記錄每個(gè)候選項(xiàng)的個(gè)數(shù)

foriteminTree.children:

forcaninCk:

ifcan.issubset(tid):

ssCnt[can]=flagitem.get（’j’）#計(jì)算每一個(gè)項(xiàng)集出現(xiàn)的頻率

numItems=float(len(dataSet))

retList=[]

supportData={}

forkeyinssCnt:

support=ssCnt[key]/numItems

ifsupport>=minSupport:

retList.insert(0,key)#將頻繁項(xiàng)集插入返回列表的首部

supportData[key]=support

returnretList,supportData#retList 為在Ck 中找出的頻繁項(xiàng)集

2 實(shí)驗(yàn)與結(jié)果

為確定本次算法改進(jìn)的合理性，將本次改進(jìn)的算法與其他三種基于Apriori 改進(jìn)的算法進(jìn)行對(duì)比，主要從算法的運(yùn)行時(shí)間和冗余規(guī)則數(shù)進(jìn)行分析來比較該算法的優(yōu)越性。本次實(shí)驗(yàn)所采用的數(shù)據(jù)為某市財(cái)政部門公用經(jīng)費(fèi)支出數(shù)據(jù)，數(shù)據(jù)規(guī)模為3 000 條。設(shè)置關(guān)聯(lián)規(guī)則算法的支持度均為0.2，最小置信度均為0.4，提升度閾值均為1.4、興趣度閾值均為0.1。不同算法的實(shí)驗(yàn)結(jié)果如表1所示。由表1可以看出本文提出的改進(jìn)的Apriori 算法可以大大降低冗余規(guī)則條數(shù)，算法運(yùn)行時(shí)間也得到縮短，提高了預(yù)警規(guī)則的挖掘效率。

表1 算法運(yùn)行時(shí)間對(duì)比表

本文提出的改進(jìn)的Apriori 算法在剔除掉無關(guān)的967條冗余規(guī)則后，共挖掘到有效規(guī)則300 條。部分規(guī)則如表2所示。

表2 公用經(jīng)費(fèi)支出關(guān)聯(lián)規(guī)則表

表2中第1～7 條規(guī)則，前列都為T29，說明在職人員數(shù)是決定公用經(jīng)費(fèi)支出多少的關(guān)鍵因素，在職人員數(shù)越多，T1辦公費(fèi)、T2印刷費(fèi)、T5郵電費(fèi)、T7差旅費(fèi)、T11會(huì)議費(fèi)T25下鄉(xiāng)人員經(jīng)費(fèi)、T27福利費(fèi)、T28公務(wù)交通補(bǔ)貼支出越多；T1?T2，T1?T3說明辦公費(fèi)越高，印刷費(fèi)和郵電費(fèi)就越高；T11?T1，T11?T2，T11?T5說明會(huì)議費(fèi)越多，辦公費(fèi)，郵電費(fèi)，印刷費(fèi)就越多；T28?T29說明公務(wù)交通補(bǔ)貼越高，在職人員越多。通過數(shù)據(jù)挖掘形成的規(guī)則，在編制公用經(jīng)費(fèi)預(yù)算時(shí)要參照在職人員數(shù)，當(dāng)在職人員數(shù)增長(zhǎng)時(shí)，T1辦公費(fèi)、T2印刷費(fèi)、T5郵電費(fèi)、T7差旅費(fèi)、T11會(huì)議費(fèi)T25下鄉(xiāng)人員經(jīng)費(fèi)、T27福利費(fèi)、T28公務(wù)交通補(bǔ)貼都應(yīng)該相應(yīng)增加；可以適當(dāng)減少會(huì)議的次數(shù)，會(huì)使辦公費(fèi)、郵電費(fèi)、印刷費(fèi)用減少。

3 結(jié)論

本文針對(duì)Apriori 算法的缺陷，提出了基于粗糙集改進(jìn)的Apriori 算法，首先利用粗糙集對(duì)原始數(shù)據(jù)進(jìn)行約減，然后對(duì)Apriori 算法進(jìn)行改進(jìn)，通過計(jì)算候選集頻數(shù)減少掃描數(shù)據(jù)庫的次數(shù)，采用多種方式對(duì)冗余規(guī)則進(jìn)行篩選，提升運(yùn)算效率。以某市的財(cái)政預(yù)算支出數(shù)據(jù)為核心，對(duì)財(cái)政預(yù)算支出數(shù)據(jù)進(jìn)行預(yù)處理后，利用改進(jìn)的算法重點(diǎn)挖掘公用經(jīng)費(fèi)支出較大時(shí)支出科目之間的關(guān)系，形成公用經(jīng)費(fèi)支出分析規(guī)則庫，通過減少某一經(jīng)費(fèi)的預(yù)算支出，達(dá)到縮減預(yù)算支出的目的。