基于粗糙集改進的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 算法進行改進，通過計算候選集頻數減少掃描數據庫的次數，采用多種方式對冗余規則進行篩選，提升運算效率。以某市的財政預算支出數據為核心，對財政預算支出數據進行預處理后，利用改進的算法重點挖掘公用經費支出較大時支出科目之間的關系，形成公用經費支出分析規則庫，通過減少某一經費的預算支出，達到縮減預算支出的目的。