景波，劉瑩，陳耿

南京審計學(xué)院信息科學(xué)學(xué)院，南京 210029

結(jié)合SOM的關(guān)聯(lián)規(guī)則挖掘研究

景波，劉瑩，陳耿

南京審計學(xué)院信息科學(xué)學(xué)院，南京 210029

1 引言

隨著數(shù)據(jù)庫應(yīng)用技術(shù)的快速發(fā)展，許多企事業(yè)單位積累了海量的、以不同形式存儲的數(shù)據(jù)資源，因此與之相應(yīng)的審計活動對信息化水平的要求也在不斷提高。目前，聯(lián)網(wǎng)實時審計已成為審計信息化發(fā)展的重點，在聯(lián)網(wǎng)審計的海量數(shù)據(jù)環(huán)境下，如何根據(jù)需要智能和自動地找出有用的信息并發(fā)現(xiàn)審計線索，是聯(lián)網(wǎng)實時審計中迫切需要解決的問題[1]。審計署從2004年開始收集并整理審計專家經(jīng)驗庫，經(jīng)過近十年的建設(shè)，其內(nèi)容涉及領(lǐng)域廣泛、審計方法全面詳實，通過對它進行多維分析和數(shù)據(jù)挖掘等技術(shù)手段，可以提取出大量有價值的規(guī)則。這些規(guī)則可以成為聯(lián)網(wǎng)審計活動中進行自動化評價及預(yù)測的基礎(chǔ)和依據(jù)。

筆者參加的“某集團工程聯(lián)網(wǎng)審計”項目中，海量數(shù)據(jù)間的關(guān)系錯綜復(fù)雜，審計線索難以發(fā)現(xiàn)。筆者思索通過數(shù)據(jù)挖掘?qū)Ρ粚弳挝粩?shù)據(jù)和審計專家經(jīng)驗庫進行關(guān)聯(lián)規(guī)則快速提??；再利用自組織神經(jīng)網(wǎng)絡(luò)相似聚類方法對審計專家經(jīng)驗庫抽取的規(guī)則劃分出相似規(guī)則群；通過對被審單位關(guān)聯(lián)規(guī)則集合和專家經(jīng)驗的相似規(guī)則群進行相對強弱、趨近率和價值率的比較最終得到審計線索集合，其流程如圖1。

2 算法思想

關(guān)聯(lián)規(guī)則挖掘用于發(fā)現(xiàn)大量數(shù)據(jù)間的相互關(guān)系，它和自組織神經(jīng)網(wǎng)絡(luò)都屬于典型的無監(jiān)督學(xué)習(xí)模式[2]。在經(jīng)典的關(guān)聯(lián)規(guī)則Apriori算法中，首先搜尋數(shù)據(jù)中所有符合最小支持度（Support）的最大項目集（Itemset），再利用此最大項目集產(chǎn)生相關(guān)規(guī)則[3-4]。算法缺點是對數(shù)據(jù)庫I/O訪問過頻繁，產(chǎn)生過多的候選項目集。后期Park等提出的DHP算法由于哈希方式會產(chǎn)生碰撞，實際掃描次數(shù)與Apriori算法相近；Brin等提出DIC算法，算法中區(qū)段大小的劃分成為執(zhí)行效率的瓶頸；Savasere等提出Partition算法，其分塊大小要配合主存儲器的大小。本文提出以分解法為基礎(chǔ)的快速匹配關(guān)聯(lián)規(guī)則挖掘算法（FMA），算法目標不是尋找最大項目集，而是尋找最適當?shù)捻椖考?，即k＜n[5]。

圖1 審計線索智能發(fā)現(xiàn)流程圖

專家經(jīng)驗相似規(guī)則群的獲得采用SOM中的經(jīng)典CLARANS算法[6]為原型的改進算法，CLARANS算法采用隨機方式產(chǎn)生初始節(jié)點，然后不斷為當前節(jié)點尋找總代價更小的鄰近節(jié)點來改善聚類結(jié)果；隨機產(chǎn)生初始節(jié)點對總搜索次數(shù)影響較大，差的初始節(jié)點將會增加搜索鄰近節(jié)點過程中鄰近節(jié)點替換和探索的總次數(shù)[7-8]。本文改進了CLARANS算法，為優(yōu)化初始節(jié)點的選擇，增加了初始節(jié)點預(yù)聚類的方法，具體流程為：

（1）掃描數(shù)據(jù)集合，計算在數(shù)據(jù)空間中數(shù)據(jù)對象各維的分布因子，并將結(jié)果按降序進行排列。

（2）選分布因子最大的m維，并生成相應(yīng)m維的子數(shù)據(jù)空間S。

（3）將數(shù)據(jù)空間S劃分成m維的網(wǎng)格，每個網(wǎng)格稱為一個m維的網(wǎng)格對象。

（4）再次掃描數(shù)據(jù)集合，按m維的值將數(shù)據(jù)劃分到相應(yīng)的網(wǎng)格中；以網(wǎng)格中的數(shù)據(jù)對象個數(shù)作為網(wǎng)格對象權(quán)重，以數(shù)據(jù)對象的均值作為網(wǎng)格對象的值。

（5）在子數(shù)據(jù)空間S中，在所有網(wǎng)格對象上使用加權(quán)距離產(chǎn)生k個初始中心點。

（6）使用第5步中得到的k個中心點作為CLARANS算法中的初始節(jié)點。

3 算法實現(xiàn)

3.1 快速匹配關(guān)聯(lián)規(guī)則挖掘算法思路

快速匹配關(guān)聯(lián)規(guī)則挖掘算法（FMA），利用分解法將每筆交易數(shù)據(jù)分解成長度為k的項目集(k＜n)；在各長度相同的項目集里，取各項目集的項目集值（即支持度的乘積）最大值者，稱為最大項目集(max_itemse)。在每筆交易中，找出不同長度的最大項目集，再比較其包含、相等的隸屬關(guān)系，找出最大的集合；最后得到不同長度的項目集的集合。

3.2 計算相似規(guī)則群

利用自組織映射神經(jīng)網(wǎng)絡(luò)中的聚類分析的CLARANS算法的改良，來進行相似規(guī)則群的劃分。CLARANS算法即根據(jù)數(shù)據(jù)分群的原則，將數(shù)據(jù)依相近似的程度予以分群，使各群內(nèi)的數(shù)據(jù)相近似度最高，而群外的相近似度減至最低。其最主要的作用是在各群組內(nèi)建立有意義的數(shù)據(jù)分群。同時，為優(yōu)化初始節(jié)點的選擇，增加了預(yù)處理的方法。

首先，C記為T的交易向量，矩陣V記作交易向量C的集合，定義如下：

利用CLARANS改良算法將數(shù)據(jù)按照相近似度分為數(shù)個群聚，每個相似性群聚，即代表著該群聚的屬性聚集，其中的每個屬性的先后順序也代表該群聚內(nèi)各屬性的重要程度。算法描述：

至此，已經(jīng)得到了由第一階段FMA算法產(chǎn)生的關(guān)聯(lián)規(guī)則集合和第二階段相似規(guī)則群的集合，對兩個集合進行相對強弱、趨近率和價值率的比較即可得到最終目標集合。具體合并算法由于篇幅所限，不在此展開討論。

4 實驗分析

為檢驗算法效率，在IBM（IBM，2003）的數(shù)據(jù)產(chǎn)生器生成的數(shù)據(jù)環(huán)境中進行與Apriori、FP_Tree算法的比較測試。實驗主機為Pentum4-2.8 GHz，1 GB Mem，運行在Borland Jbuilder9平臺上，使用JAVA語言編寫算法。

實驗數(shù)據(jù)為5 000、10 000、25 000、50 000、100 000及200 000六種，數(shù)據(jù)的交易長度平均為10，最小支持度選為0.005或0.007 5。在minsup不變，而交易量逐漸由5 000增加至200 000時，其FMA、Apriori與FP_Tree之執(zhí)行時間的對比如圖2。在交易量固定為5 000或200 000時，而minsup值從0.02逐漸減少至0.005時，其FMA、Apriori與FP_Tree之執(zhí)行時間的對比如圖3。

圖2 minsup=0.005&交易量遞增時執(zhí)行時間對比

在此實驗里，從整體來看，F(xiàn)MA與Apriori的比較里，最小的差距是數(shù)據(jù)為5 000，minsup為0.02時，F(xiàn)MA為Apriori的9.09%；最大的差距是數(shù)據(jù)為200 000，minsup為0.005時，執(zhí)行時間FMA為Apriori的0.45%。在FMA與FP_Tree的執(zhí)行時間里，最小的差距是數(shù)據(jù)為50 000，minsup為0.02時，執(zhí)行時間FMA為FP_Tree的71.43%；最大的差距是數(shù)據(jù)為10 000，minsup為0.005時，執(zhí)行時間FMA為Apriori的8.11%。

圖3 D=5 000 minsup遞減時執(zhí)行時間對比

在不同數(shù)據(jù)集規(guī)模的情況下，設(shè)目標群個數(shù)為5，局部最優(yōu)解個數(shù)為2，最大鄰居數(shù)為100，CLARANS與改良算法的平均運行時間對比如圖4，鄰居節(jié)點替換總代價的平均次數(shù)對比如圖5。

圖4 不同數(shù)據(jù)量下執(zhí)行時間對比

圖5 不同數(shù)據(jù)量下替換總代價對比

從圖中可以看出，在目標群數(shù)值固定的情況下，隨著數(shù)據(jù)量增加，CLARANS和改良算法的運行時間都會隨之增加，但改良算法的增長較緩慢，并且執(zhí)行時間僅為CLARANS算法的1/5，鄰居節(jié)點數(shù)隨數(shù)據(jù)增加變化不大，改良算法的計算量也僅為原算法的1/5。

5 結(jié)束語

本文以FMA算法將被審單位的海量數(shù)據(jù)利用數(shù)據(jù)挖掘手段，找出適當長度的項目集；同時通過自組織特征映射神經(jīng)網(wǎng)絡(luò)的CLARANS算法產(chǎn)生項目集（專家經(jīng)驗相似群）；使用相對強弱、趨近率、價值率等集合操作手段，產(chǎn)生得出審計目標線索群。實驗表明，算法能做到快速生成審計規(guī)則及形成審計線索群，符合預(yù)期設(shè)想。下一步將通過實際審計過程中的問題發(fā)現(xiàn)，做進一步的評估與驗證。

[1]劉家義.加快審計信息化建設(shè)的思考[J].中國審計，2000（9）：4-8.

[2]國家863計劃審計署課題組.計算機審計數(shù)據(jù)采集與處理技術(shù)研究報告[R].北京：清華大學(xué)出版社，2006.

[3]張懷亭，王忠民.提高關(guān)聯(lián)規(guī)則完整性和有效性的算法[J].計算機工程與應(yīng)用，2003，39（29）：208-210.

[4]馬盈倉.挖掘關(guān)聯(lián)規(guī)則中Apriori算法的改進[J].計算機應(yīng)用與軟件，2004，21（11）：82-84.

[5]景波，劉瑩，黃兵.基于審計的時態(tài)關(guān)聯(lián)規(guī)則研究[J].微計算機信息，2007（18）：176-178.

[6]田景文，高美娟.人工神經(jīng)網(wǎng)絡(luò)算法研究及應(yīng)用[M].北京：北京理工大學(xué)出版社，2006.

[7]張書春，孫秀英.基于網(wǎng)格結(jié)構(gòu)的CLARANS改進算法[J].計算機工程，2012（6）：56-59.

[8]Zhang Yaping，Sun Jizhou，et al.Parallel implementation of CLARANS using PVM[C]//Proceeding of the 3rd International Conference on Machine Learning and Cybernetics，2004：26-29.

[9]姜華，孟志青，周克江，等.一類時態(tài)近似周期關(guān)聯(lián)規(guī)則的知識發(fā)現(xiàn)問題[J].計算機工程與應(yīng)用，2010，46（20）：241-244.

[10]Meng Zhi-qing.Study of temporal type and time granularityinthetemporal datamining[J].Natural Science Journal of Xiangtan University，2000，22（3）：1-4.

[11]Meng Zhiqing.Knowledge discovery for a kind of neighbor temporalassociatedrules[J].PatternRecognitionand Artificial Intelligence，2001，14（4）：458-462.

[12]Jiang Hua，Meng Zhiqing.Study of data mining for a kind of temporal approximate periodicity[J].Computer Engineering，2006，32（22）：61-63.

[13]Li Y，Ning P，Wang X S，et al.Discovering calendar-based temporal association rules[J].Data and Knowledge Engineering，2003，44（2）：193-218.

[14]Yang Jiong，Wang Wei，Yu P S.Mining asynchronous periodic patterns in time series data[J].IEEE Transactions on Knowledge and Data Engineering，2003，15（3）：613-628.

[15]馬春玲，李廉.基于等價關(guān)系的關(guān)聯(lián)規(guī)則的挖掘[J].蘭州大學(xué)學(xué)報：自然科學(xué)版，2002（4）：64-71.

JING Bo,LIU Ying,CHEN Geng

School of Information Science,Nanjing Audit University,Nanjing 210029,China

In order to achieve the audit trail of the massive data quickly found through data mining FMA algorithms to quickly extract trial data and audit expertise library association rules；re-use of self-organizing neural network improved CLARANS algorithm to extract audit expertise library divide a similar rule base rules；then by trial set of association rules and expert experience similar rules group relative strength,the approach value and the different rate of comparing the resulting set of audit trail.

association rule mining;Self-Organizing Map（SOM）;audit trail

為了實現(xiàn)在海量數(shù)據(jù)中的審計線索的快速發(fā)現(xiàn)，通過數(shù)據(jù)挖掘FMA算法對被審數(shù)據(jù)和審計專家經(jīng)驗庫進行關(guān)聯(lián)規(guī)則快速提??；再利用自組織神經(jīng)網(wǎng)絡(luò)改良CLARANS算法對審計專家經(jīng)驗庫抽取的規(guī)則劃分出相似規(guī)則群；然后通過對被審單位關(guān)聯(lián)規(guī)則集合和專家經(jīng)驗的相似規(guī)則群進行相對強弱、趨近率和價值率的比較，最終得到審計線索集合。

關(guān)聯(lián)規(guī)則挖掘；自組織神經(jīng)網(wǎng)絡(luò)；審計線索

A

TP311

10.3778/j.issn.1002-8331.1212-0298

JING Bo,LIU Ying,CHEN Geng.Research on association rule based on SOM.Computer Engineering and Applications,2014,50（22）：154-157.

江蘇省公共工程審計重點實驗室開放課題（No.20201201213）；江蘇省審計信息工程重點實驗室開放課題（No.AIE201205）；國家自然科學(xué)基金（No.70971067，No.71271117）。

景波（1975—），男，副教授，主要研究方向：IT審計，數(shù)據(jù)挖掘；劉瑩（1977—），女，講師，主要研究方向：數(shù)據(jù)挖掘，分布式計算技術(shù)；陳耿（1965—），男，教授，博士，主要研究方向：數(shù)據(jù)挖掘，審計信息化，知識工程等。E-mail：jbo@nau.edu.cn

2012-12-25

2013-02-25

1002-8331（2014）22-0154-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-03-13,http://www.cnki.net/kcms/detail/11.2127.TP.20130313.0955.024.html