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

畢浩田

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

0 引言

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

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

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

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

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

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

圖1 Apriori 算法流程圖

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

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

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

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

圖2 基于粗糙集改進的apriori 算法流程圖

改進后的算法步驟具體如下：

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

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

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

（4）掃描DM1生成IFP-Tree，將每個節(jié)點的標記值flag_i=(x，y)添加到相應的節(jié)點處。

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

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

1.2.1 粗糙集算法設計

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

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

（1）在數(shù)據(jù)中找到所需的條件屬性和決策屬性，并用適當?shù)姆枌l件屬性按決策屬性表示出來。

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

#決策屬性基本集

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 函數(shù)

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

#計算每一個γ(C-a)(D)

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

#收集屬性重要性

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

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

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

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

defapriori(D,minSupport):

flag=1

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

L1,supportData=scanD(D,C1,minSupport)#掃描數(shù)據(jù)集，生成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)#調用計算候選集頻數(shù)算法生成Lk 頻繁項集

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

k+=1

returnL,supportData

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

ssCnt={}#記錄每個候選項的個數(shù)

foriteminTree.children:

forcaninCk:

ifcan.issubset(tid):

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

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 改進的算法進行對比，主要從算法的運行時間和冗余規(guī)則數(shù)進行分析來比較該算法的優(yōu)越性。本次實驗所采用的數(shù)據(jù)為某市財政部門公用經(jīng)費支出數(shù)據(jù)，數(shù)據(jù)規(guī)模為3 000 條。設置關聯(lián)規(guī)則算法的支持度均為0.2，最小置信度均為0.4，提升度閾值均為1.4、興趣度閾值均為0.1。不同算法的實驗結果如表1所示。由表1可以看出本文提出的改進的Apriori 算法可以大大降低冗余規(guī)則條數(shù)，算法運行時間也得到縮短，提高了預警規(guī)則的挖掘效率。

表1 算法運行時間對比表

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

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

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

3 結論

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