結合SOM的關聯規則挖掘研究

景波，劉瑩，陳耿

南京審計學院信息科學學院，南京 210029

結合SOM的關聯規則挖掘研究

景波，劉瑩，陳耿

南京審計學院信息科學學院，南京 210029

1 引言

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

筆者參加的“某集團工程聯網審計”項目中，海量數據間的關系錯綜復雜，審計線索難以發現。筆者思索通過數據挖掘對被審單位數據和審計專家經驗庫進行關聯規則快速提??；再利用自組織神經網絡相似聚類方法對審計專家經驗庫抽取的規則劃分出相似規則群；通過對被審單位關聯規則集合和專家經驗的相似規則群進行相對強弱、趨近率和價值率的比較最終得到審計線索集合，其流程如圖1。

2 算法思想

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

圖1 審計線索智能發現流程圖

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

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

（2）選分布因子最大的m維，并生成相應m維的子數據空間S。

（3）將數據空間S劃分成m維的網格，每個網格稱為一個m維的網格對象。

（4）再次掃描數據集合，按m維的值將數據劃分到相應的網格中；以網格中的數據對象個數作為網格對象權重，以數據對象的均值作為網格對象的值。

（5）在子數據空間S中，在所有網格對象上使用加權距離產生k個初始中心點。

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

3 算法實現

3.1 快速匹配關聯規則挖掘算法思路

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

3.2 計算相似規則群

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

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

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

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

4 實驗分析

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

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

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

在此實驗里，從整體來看，FMA與Apriori的比較里，最小的差距是數據為5 000，minsup為0.02時，FMA為Apriori的9.09%；最大的差距是數據為200 000，minsup為0.005時，執行時間FMA為Apriori的0.45%。在FMA與FP_Tree的執行時間里，最小的差距是數據為50 000，minsup為0.02時，執行時間FMA為FP_Tree的71.43%；最大的差距是數據為10 000，minsup為0.005時，執行時間FMA為Apriori的8.11%。

圖3 D=5 000 minsup遞減時執行時間對比

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

圖4 不同數據量下執行時間對比

圖5 不同數據量下替換總代價對比

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

5 結束語

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

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

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

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

[4]馬盈倉.挖掘關聯規則中Apriori算法的改進[J].計算機應用與軟件，2004，21（11）：82-84.

[5]景波，劉瑩，黃兵.基于審計的時態關聯規則研究[J].微計算機信息，2007（18）：176-178.

[6]田景文，高美娟.人工神經網絡算法研究及應用[M].北京：北京理工大學出版社，2006.

[7]張書春，孫秀英.基于網格結構的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]姜華，孟志青，周克江，等.一類時態近似周期關聯規則的知識發現問題[J].計算機工程與應用，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]馬春玲，李廉.基于等價關系的關聯規則的挖掘[J].蘭州大學學報：自然科學版，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

為了實現在海量數據中的審計線索的快速發現，通過數據挖掘FMA算法對被審數據和審計專家經驗庫進行關聯規則快速提?。辉倮米越M織神經網絡改良CLARANS算法對審計專家經驗庫抽取的規則劃分出相似規則群；然后通過對被審單位關聯規則集合和專家經驗的相似規則群進行相對強弱、趨近率和價值率的比較，最終得到審計線索集合。

關聯規則挖掘；自組織神經網絡；審計線索

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）；國家自然科學基金（No.70971067，No.71271117）。

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

2012-12-25

2013-02-25

1002-8331（2014）22-0154-04

CNKI網絡優先出版：2013-03-13,http://www.cnki.net/kcms/detail/11.2127.TP.20130313.0955.024.html