（计算机应用技术专业论文）面向中观审计的规则发现算法研究.pdf

摘要 目前，我国政府部门为了规范市场经济秩序，防范各类经济风险，十分重视并积极开展 各类审计工作。提出了对重点资金、重点领域、重点项目的审计监督。但是，从庞大的数据 库系统中迅速地提取出有用的审计信息成为当前审计工作面临的严峻挑战，这就更加要求从 多个层面探索更有效的审计思路、新方法和新技术。本论文研究工作就是试图将中观审计理 论与数据挖掘等计算技术相结合，从行业中各个单位的数据库系统中提取出中观( 行业) 审 计假设与关联模式，用以指导中观审计工作的深入开展，并在此基础上积极探索审计智能化、 自动化的理论与技术。 本文的研究工作的创新性主要体现在以下几个方面： ( 1 ) 从中观审计检测的实际需要出发，提出了非对等结构的分布式数据库环境下关联 规则挖掘的原型系统a u d i t m i n e r 体系结构，即由局部站点和全局站点协同完成关联规则的 挖掘任务。 ( 2 ) 提出了面向中观审计的基于二进制形式的候选频繁项目集生成和相应的计算支持 数算法b - g e n ，用以降低生成频繁项集的实现难度，将该算法与a p r i o r i 、p u p 、f d m 等算 法相结合，提出了b a p r i o r i 、b r j p 和f d m 等算法，可以显著提高关联规则的生成效率。 ( 3 ) 鉴于大数据集环境下的关联规则发现日益受到重视，分布式关联规则发现是解决 这一问题的有效方法。针对非对等结构分布式数据库环境，本文提出了相应的算法g f d a ， 算法可以高效地对分布环境下的数据进行关联规则发现。 ( 4 ) 在中观审计检测中大量遇到规则增量更新问题。本文在肼c h e u n g 等人提出的f u p 算法的基础上，引入候选支持度、次频繁项集和支持数上界等概念，提出了增量式关联规则 发现算法i f u p ；进一步针对分布式环境下的关联规则的增量更新问题，提出更新算法l u d a 和g u d a 以及更新算法l u d a 2 和g u d a 2 。这些更新算法能够充分利用已挖掘的结果，产生较 少数量韵候选频繁项目集，通信代价低，算法效率较高。 ( 5 ) 将b e n f o r d 法则应用于发现异常交易，引入差异度概念与全局关联规则进行比对 获取异常模式。可以有效提高规则的审计兴趣度。 ( 6 ) 研制以海关为审计主体的、面向中观审计检测的、分布式审计关联规则挖掘原型 系统a u d i t m i n e r ，用以验证论文中提出的各算法的适用性和有效性。 关键词：中观审计，数据挖掘，关联规则，频繁项集，分布式关联规则，关联规则更新 a b s t r a c t r e c e n t l y , o u rg o v e r n m e n t s8 1 t a e hi m p o r t a n c et oa u d i ta n da s kt h ed e p a r l r n e n to fa u d i tt o s t r e n g t h e nt o $ u p e r v i t h ei m p o r t a n ts t a t ec a p i t a l sf o rp r e v e n t i n gt h er i s k so fe c o n o m i c i ti s a g r e a tc h a l l e n g e , h o w e v e r , t or a p i d l ym i n et h eu s e f u li n f o r m a t i o no l la u d i tf r o mav a r yl a r g e d a t a b s s es y s t e m i te n f o r c e su st of i n dm o l l ：e f f e c t i v ea u d i t i n gt h e o r i e s ，m e t h o d sa n dt e c h n o l o g i e s w ea t t e m p tt oc o m b i n et h et h e o r yo fi n d u s t r ya u d i ta n dt h et e e h n o l 0 9 3 , o fd a t am i n i n gt om i n e a s s o c i a t i o np a t t e r na n di n d u s t r ya u d i t8 略s u m p t i o n sf r o mt h ed a t a b a s e so fe n t e r p r i s e si nt h es a m e i n d u s t r y , a n dt h e n t of i n do u tt h ea u d i tr i s k sb e h i n dd a t a s o ，t h ep a p e ri sm o r eu s e f u li nr e s e a r c h a n da p p l i c a t i o n t h em a i nc o n l r i b u t i o no f t h ep a p e ra r cl i s t e da sf o l l o w s ： ( 1 ) , e e o r d i n gt ot h ed e m a n do fi n d u s t r ya u d i t , t h ep a p e rp r e s e n t st h ea r c l a j t e c t u r eo fad a t a m i n i n gs y s t e m a u d i t m i n e r b a s e d o n d i s t r i b u t e d d a t a b s s e e n v i r o n m e n t , i n w h i c h t h e t a s k o f m i n i n g a s s o c i a t i o nr u l e si sc o m p l e t e dt o g e t h e rb yg l o b a ls i t ea n dl o c a ls i t e s ( 2 ) p r o p o s e d b i n a r ys y s t e mb a s e dm e t h o db - g c nt og e n e r a t ee m d i d a t ef r e q u e n ti t e m s e t s a n dc o r r e s p o n d i n gs u p p o r d n gc o u n t se f t i e i e n t l y , w h i c hn e e d so n l ys o m co p e r a t i o n ss u c h 鹳 “a n d ， o ，a n d x o r a p p l y i n gt h i si d e ai nt h ee x i s t e da s s o c i a t i o nm i n i n ga l g o r i t h ma p r i o r i ，f 【j p a n df d m ，t h ec o r r e s p o n d i n gi m p r o v e da l g o r i t h mb a p r i o r i , b f u pa n db f d mi sp r o p o s e d t h e t h e o r e t i c a la n a l y s i sa n de x p e r i m e n tt e s t i f y6 a a tt h e ya e f f e c t i v ea n de t f i e i e n t ( 3 ) c o n s i d e r i n gt h a tn l o r ea n dn l o r l 。a t t e n t i o nh a v eb e e np a y e dt ot h ep r o b l e mo f a s s o c i a t i o n r u l em i n i n gi nl a r g ed a t as e t , d i s t r i b u t e da s s o c i a t i o nm i n i n gi sae f f e c t i v em e t h o dt os o v et h i s p r o b l e m t h ep a p e rp r o p o s e s 船a l g o r i t h mo fd i s t r i b u t e da s s o c i a t i o nm i n i n ga l g o r i t h m ( 3 f d a b a s e do nt h ed i s t r i b u t e da r c h i t e c t u r eo f t h ed a t a ( 4 ) b a s e do nt h ef u pa l g o r i t h m ，t h ep a p e rp r o p o s e ss e v e r a lc o n c e p t i o n si n c l u d i n gb a e l c u p s u p p o r tt h r e s h o l d ，m i n o rf r e q u e n te a n d i d a t e ss e ta n du p p e rb o u n do fs u p p o r tc o u n t , t h e np r e s e n t s i m p r o v e da l g o r i t h mi f u p f u r t h e r m o r e i n c r e m e n t a la s s o c i a t i o nr u l em i n i n gi nd i s t r i b u t e d e n v i r o n m e n ta l ec o n s i d e r e d ，a l g o r i t h m sl u d a ，( 3 u d a ，l i d a 2a n dg u d a 2a ”p r o p o s e dt o s o l v et h i sp r o b l e m ( 5 ) p r o p o s e a l g o r i t h mt om i n i n ga b n o r m a ll ， a n s a e t i o n sb yb e n f o r dl a w p r e s e n tac o l l c e p t o f d i f f e r e n c et oc o m p a r ea s s o c i a t i o nf r o ma b n o r m a lt r a n s a c t i o n sw i t hg l o b a la s s o c i a t i o nr u l e sf o r e x t r a c t i n gm o l ei n t e r e s t i n gr u l e sf r o mg l o b a la s s o c i a t i o nr u l e s ( 6 ) d e v e l o pap r o t o t y p es y s t e ma u d i t m i n e rf o rm i n i n gd i s t r i b u t e da s s o c i a t i o nr u l e sf r o mt h e c u s t o m s d a t a b a s es y s t e mb yi n d u s t r ya u d i t t h ea l g o r i t h m sp r e s e n t e di nt h ep a p e ra r et e s t e dt ob e e f f e c t i v ea n de f f i e i e n t k e y w o r d s ：i n d u s t r ya u d i t , d a t am i n i n g ，a s s o c i a t i o nr u l e ，d i s t r i b u t e da s s o c i a t i o nr u l e , a s s o c i a t i o n r u l e su p d a t i n g 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：垒亟导师签名：2 二墨兰茧期：研究生签名： 堡堕导师签名：兰至! 日期： 第一章引言 第一章引言 1 1 课题研究的背景与意义 随着计算机和数据库技术的广泛应用，特别是最近十几年来互联网的普及，目前各类 应用的数据库系统中存储的数据量急剧增加。例如，销售网点遍布全球的美国w a l - v a r t 公司，其数据库中每天都会新增加大约2 亿笔交易数据。无论考虑时间开销还是空间开销， 传统的数据分析手段都难以应付这些“堆积如山”的数据，人们无法有效地理解并使用这 些数据，造成大量数据资源的浪费。传统的数据分析方法( 例如统计方法) ，只能获得这些 数据的表层信息，很难对数据进行深层次的处理，而且不能获得数据属性之间的内在关联 和隐含的规则，即不能获得重要的有价值的知识，导致了所谓“数据爆炸但知识贫乏”的 现象。因此，面对各行各业数字化系统中的信息与数据的急剧增加，并且由于人的参与使 数据与信息中的不确定因素更加显著，信息与数据中的关系更加复杂，如何从这种大量的， 杂乱无序的、有噪声的数据中“智能地”和“自动地”挖掘出潜在的、有价值的知识。以 使花费大量财力与物力收集与整理到的数据资源得以充分利用显得至关重要。由此引发了 一个新的研究方向：数据库中的知识发现( k 叩：k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 的 理论与技术研究 k d d 包括数据预处理、数据挖掘、知识评价等处理过程数据挖掘( d a t am i n i n g ) 是 k d d 过程中的关键步骤，是指从大型数据库或数据仓库等数据源中提取人们感兴趣的知识 这些知识是隐含的、事先未知的、潜在有用信息，提取的知识一般可表示为概念( c o n c e p t s ) 、 规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式“1 用数据库管理系统 来存储数据，用机器学习和统计学等学科研究相关的方法来分析数据，挖掘大量数据所隐 含的知识，这两者的结合促成了数据挖掘技术的产生通过十多年的研究，人们已经认识 到数据挖掘是- - f l 交叉性研究学科，涉及到机器学习、神经网络、模式识别、归纳推理、 统计学、数据库、数据可视化、高性能并行计算等多个学科与领域 数据挖掘技术在科学研究方面具有重要意义。在数据量极为庞大的天文、气象、生物 技术等领域中。大量的实验和观测数据靠传统的数据分析工具难以进行有效地分析处理， 借助数据挖掘技术，可以有效地提升研究人员发现潜在知识的能力和效率目前在此方面 已获得一些重要的应用成果i l 捌。例如，美国加州理工学院喷气推进实验室与天文学家合作 开发的s k l c a t 系统通过对几百万个天体进行分类，帮助天文学家发现了1 6 个新的类星体； 专家系统d e n d r a l 根据质谱仪给出的数据，能够发现已知或未知的高分子化合物分子结 构；机器学习系统b a c o n 根据已有实验和观测数据，能够重新发现欧姆定律、凯普勒定律 等。 数据挖掘可为决策者提供重要并有价值的信息和知识，产生不可估量的收益，故基于 数据挖掘技术的产品市场需求日益增长在零售业，金融投资分析，保险行业的风险评估 等方面都取得了令人瞩目的成果如s g i 公司的h i n e s e t 系统提供的分类器就可以预测投 保人在将来的索赔概率。a c k n o s o f t 公司开发的c a s s i o p e e 系统已用于诊断和预测在波音 飞机制造过程中可能出现的问题。芬兰h e l s i n k i 大学开发了一个基于通信网络中警报数据 东南大学博士学位论文 库的知识发现系统t a s a ，用来寻找通信网络中警报序列规则，从而进行故障预测。美国哥 伦比亚大学开发的j a m 系统可以从各个独立金融机构的数据库中挖掘出关于诈骗的知识模 式等 正是基于数据挖掘的上述特征与发展，我们认为数据挖掘在审计领域也具有重要的理 论研究价值和现实应用前景 首先，审计作为国家或部门的一种独立性的经济监督活动，对被审计单位相关经济活 动具有特有的制约和促进作用。最近几年不断刮起的“审计风暴”证明了审计在经济发展 中的重要地位，审计越来越受到政府的重视和社会的关注审计被公认为是建立一个廉洁 政府的有力工具。其次，随着经济建设的发展和计算机网络技术的日益普及，企事业单位 和经济管理部门利用计算机技术的程度越来越高，业已建立并运行着数据量达g b 甚至t b 级的应用数据库，并积累了大量的历史业务数据。如海关、银行等行业审计人员面对的 不再是以往的纸质账簿和数据，在每一个被审计单位的计算机应用系统中存储着大量的电 子数据。如何利用数据挖掘技术智能地、自动地从这些海量的数据中寻找到有价值的审计 信息，同样成为审计工作面临的巨大挑战。 审计在执行的过程中，需要特定的审计假设，它是审计理论和实务发展的前提。审计 假设是通过客观正常情况或发展趋势分析所获得的经济活动中各种因素的相关性、判断和 说明应用这种由推理而得到的结论可以指导审计实施，提高审计质量与效率，减少或避 免审计风险国家审计署顾问、审计专家王会金教授等首先提出建立中观审计模型，即运 用科学系统的程序和方法，以行业为研究对象，形成中观( 行业) 审计假设模型，从而指 导对企事业单位的审计我们课题组与王会金教授经过多次讨论，一致认为这种审计假设 是可以从企业的数据库中提取出来的。由于数据挖掘与审计在本质特征上是基本一致的， 都是为了寻找出隐藏在大量数据背后的信息，因此，数据挖掘技术可以进一步丰富中观审 计理论，为中观审计开拓新的研究方向，为审计自动化研究提供理论基础 目前，我国各级政府部门为了适应加入w t o 的要求，正大力规范市场经济秩序。为防 范经济上的各类风险，近年来，政府十分重视并积极开展各类审计工作，进一步加强了对 重点资金，重点领域、重点项目的审计监督，加大对重大违法违纪问题和经济案件的查处 力度。但是，如何从庞大的数据库系统中迅速地提取有用的审计信息成为当前审计工作面 临的严峻挑战，这就更加要求从多层面探索有效的审计新思路、新方法和新技术。中观审 计理论被看成是这方面积极探索的成果之一。我们试图将中观审计理论与数据挖掘技术相 结合。从行业中各个单位的数据库系统中提取出中观( 行业) 审计假设与关联模式，再运 用这些假设与关联模式发现隐藏在数据背后的审计风险积极探索审计智能化、自动化的 理论与技术因此这一研究具有较高的理论价值和应用价值 本文的研究课题及其内容就是在上述背景下提出来的。同时，本文的研究还结合了所 申请的国家自然科学基金项目“基于数据挖掘技术的中观审计风险研究( 7 0 3 7 1 0 1 5 ) ”以及 由审计署牵头的国家8 6 3 计划信息技术( 8 6 3 - 1 0 0 ) 领域软件重大专项“计算机审计数据采 集与处理技术”项目的研究( 编号：2 0 0 3 a a i z 2 3 3 0 ) 在这些项目的支持下，充分利用已有 的研究成果，结合审计的特点，提出数据库系统中的审计假设关联模式的挖掘算法，研究 一个基于大型分布式数据库系统的面向中观审计的规则发现的整体方案和实现技术 国家审计署在( 2 0 0 4 年至2 0 0 7 年审计信息化发展规划中明确要求：“到2 0 0 7 年， 审计署要初步建成联网审计系统，开展对中央部门级预算单位以及财政、海关、国税、 金融等部门的联网审计省级和中心城市审计机关要开展以一级预算单位以及地税、社会 保障等部门和会计结算中心为重点的联网审计”目前，国家重点扶持的金审工程建设使 2 第一章引言 得全国的计算机审计网络架构已初步形成。与海关总署、中国农业银行、中国工商银行以 及建设银行等开展了网络环境下的联网审计试点，这为本文的研究工作提供了良好的实验 环境 1 2 国内外研究现状 我们从关联规则研究、计算机审计的应用与研究、中观审计理论研究和等三方面阐述 “面向中观审计的规则发现”这一研究领域的现状 1 2 1 关联规则挖掘算法研究现状 数据挖掘的研究内容主要包括关联规则( a s s o c i a t i o nr u l eo ra s s o c i a t i o np a m e m ) 3 挖掘， 分类( c l a s s i f i c a t i o n ) 挖掘、聚类( c l u s t e r i n g ) 分析、离群数据( o u t l i e r ) 挖掘、预测( p r e d i c t i o n ) 、 序列模式分析、特征规则挖掘、趋势分析、偏差分析、回归分析、序列模式分析等u j i 其 中，由于关联规则深刻地反映了知识的本质特征，成为数据挖掘的一个重要的研究领域。 1 9 9 3 年由r a k e s ha g r a w a l 等人首次提出布尔型关联规则挖掘问题及相应的a 嘶耐算法以 来p j ，数据挖掘领域的研究者在关联规则挖掘上做了大量的工作，a 耐o r i 算法已经成为关 联规则挖掘中的经典算法之一。 关联规则挖掘的研究工作主要包括：单机环境下的关联规则挖掘算法改进、并行及 分布关联规则挖掘| 9 - 2 4 | 、无候选项集( 非a 研嘶框架) 的关联规则挖掘1 2 5 - 3 2 1 ，关联规则 增量式更新与维护 3 3 - 4 2 1 、数量关联规则挖掘| 4 3 - 4 9 、约束性关联规则挖掘l ”删、对关联规则 各种阈值的讨论i “9 1 以及最大频繁项集的挖掘1 2 ”日等方面。研究者还对数据挖掘的理论 进行了有益的探索，将概念格和粗糙集应用于关联规则挖掘中”1 0 7 1 ，获得了显著的效果 总之，关联规则的研究已经取得了令人瞩目的成果，但是这些研究工作主要聚焦于技术本 身以及相关的一些理论研究，因此有一定的局限性。与某些特定的应用( 需求) 相结合， 将成为关联规则研究今后的发展方向，目前，国内外学者已将之用于分类规则挖掘 s s - 9 ”和 网络入侵检测p + ”1 等方面的研究，取得了很好的效果，但是总的来说，这些研究工作目前 还处在起步阶段。如关联规则更新维护，关联规则评价指标，以及分布式关联规则挖掘等 方面还远远不能满足实际的需要。针对这些问题，追切需要根据特定要求( 如中观审计的 应用需求) ，在算法及系统实现等方面进行深入研究 到目前为止，关联规则的挖掘已经取得了多方面的进展。主要包括： ( 1 ) 单机环境下的关联规则挖掘算法研究“”“ 由h g r a w a l ”1 等人提出的a p r i o r i 算法最为著名。a p r i o r i 算法的基本思想是通过频 繁k 一项集得到候选频繁( k + 1 ) 一项集。丈部分的算法都是在a p r i o r i 算法的架构之上进行改 进，如d l i p 算法采用h a s h 技术。s a v a s e r e “等人提出的p a r t i t i o n s 算法将数据库进行 分割，t o i v o n e n “提出的抽样算法s a m p l i n g ，其核心思想是对数据库进行抽样，以减少 数据量从而提高挖掘效率h a nj - 等人”“提出的基于频繁模式树( f p - t r e e ) 的关联规 则挖掘算法f p - g r o w t h 则与a p r i o r i 算法有本质区别，它不产生候选项集，而是将提供频 繁项集的数据库压缩到一棵频繁模式树( f p - t r e e ) ，从而把频繁模式的挖掘问题转换成挖 掘f p t r e e 问题，因此，它比a p r i o r i 快一个数量级，但是当数据库很大时，构造基于内 存的f p t r e e 的时空开销很大目前的研究基本围绕a p r i o r i 框架和f p t r e e 框架展开， 3 东南大学博士学位论文 研究方向有两个，一是通过剪枝减少搜索空间，二是分割数据库，实现分布式挖掘，从而 大大提高算法的效率 ( 2 ) 分布式环境中的关联规则挖掘算法研究1 9 - 2 4 1 最早的分布式挖掘关联规则的算法是由a g r a w a l 例等人提出的c d ( c o u n t d i s t r i b u t i o n ) ，c a d ( c a n d i d a t ed i s t r i b u t i o n ) ，d d ( d a md i s t r i b u t i o n ) ，p a r k 和c h e n 等人 提出的并行算法p d m i “l 是基于并行环境的d h p 算法的一个扩展，c h e u n g 等人提出的基于 分布式数据库的挖掘算法d m a l ”j 和f d m f ”l ( f a s td i s t r i b m e am i n i n go f a s s o c i a t i o nr u l e s ) ， 以及f p m l l 4 1 、d d d m ”l 、格方法1 1 6 1 、散列方法1 1 7 1 及并行f p - g r o w t h 算法【”1 等。算法c d 具有速度快、容易实现、要求计算机之间同步次数少等优点，但是它具有通信量大、候选 频繁项集大等缺点算法c a d 。d d 和p d m 的执行效果不如c d ，算法d m a 克服了c d 的一些弱点，但是它要求计算机之间的同步次数比较多由于c h e t m g 等人对分布环境下 的关联规则挖掘算法的深入研究，使得f d m 算法成为该领域比较著名的算法之一。对于 分布式环境的定义般指异地同构数据库，该问题等价于对数据库进行水平分割问题目 前为止，对分布关联规则的挖掘研究主要集中在非布尔型【1 9 j ，或进一步提高挖掘效率【2 等，但是对分布环境没有提出新的结构 ( 3 ) 关联规则的维护与更新研究p 3 4 2 1 由c h e u n 9 1 3 3 1 等人最早提出维护更新的概念维护更新分为两类：在最小支持度和 最小置信度不变时，数据库d b 被添加、删除或修改的情况下，关联规则所发生的变化； d b 保持不变，最小支持度和最小置信度发生变化时，关联规则产生的变化一种最直接的 方法就是对更新后的数据集重新运行一遍原算法，但是这种方法没有充分利用已发现的频 繁项集的信息，存在效率低下的缺陷如何充分利用已发现的信息来高效地生成更新后的 关联规则就成为解决问题的关键。因此，维护更新算法的高效性体现在如何减少对数据库 的扫描次数和生成较小的候选项集。对于第一类维护更新问题，可以利用f l i p ( f a s tu p d a t e ) 算法1 3 ”、f u p 2 算法p 4 1 来解决，f l i p 算法仅仅考虑向数据集增加数据的情况；f u p 2 算法 不仅考虑向数据集增加数据的情况，还考虑了向数据集中删除和修改数据的情况；对于第二 类问题，可以利用i u a ( i n c r e m e n t a lu p d a t i n ga l g o r i t h m ) 算法p q 和e i u a 算法1 3 ”来解决。由于 最小置信度发生变化时和最小支持度变大时的关联规则的维护更新问题比较直观，i l i a 算 法 3 6 1 主要考虑的是最小支持度变小时关联规则的高效更新问题。针对i u a 算法存在的不 足，提出了一种改进的增量式关联规则的维护算法e i u a 瞄】。由于数据挖掘的过程是交互的， 为了发现满意的模式。用户需要不断调整最小支持度和置信度与此同时，数据库是不断进 行更新和维护的p q 。现有的算法在一定程度上解决了关联规则的维护更新问题，但是在分布 式数据库环境下的维护更新问题研究不多。 ( 4 ) 基于约束条件的关联规则挖掘o “ 基于约束条件的关联规则挖掘的主要目的是发现更有趣、更实用、更特别的关联规则。 目前对于关联规则的度量主要分为主观指标和客观指标，客观指标是根据数据库中数据来 确定的，1 l a g r a w a l t l l 9 1 提出的支持度置信度框架，p i a t e s k 既- s h a p i r o t “提出的事件独立性 p ( a ，b ) p ( a ) p ) ，s y m t h 提出了j m e a s u r e 函数，t o i v o n e n i ”6 1 提出了根据规则的后件， 对挖掘出的关联规则集合进行分组的覆盖集合( c o v e rr u l e s ) 作为感兴趣的规则。这些方法共 同不足反映在：只是利用规则前件和后件的客观关联来评价对规则的感兴趣程度，忽视了 背景知识和用户的参与。而关联规则最终的目的给提供给决策者使用的，因此主观指标参 与关联规则的发现应当受到研究者的重视。 4 第一章引言 ( 5 ) 非布尔型关联规则挖掘一1 关联规则可分为布尔型关联规则和多值属性关联规则。多值属性又可分为数量关联规则和 类别关联规则数量关联规则是指同时包含布尔属性和连续属性的关联规则目前提出了 基于支持度的部分k 度完全方法、等深度划分方法以及数量关联规则的挖掘中的聚类方法 类别属性关联规则的挖掘算法大多是将类别属性关联规则挖掘问题转化为布尔型关联规则 挖掘问题 1 2 2 计算机审计的应用与研究现状 审计是面向相关企事业部门的，而每个部门的信息系统又是千差万别的因此，在审 计领域应用计算机受到两方面的制约。首先，计算机审计的发展直接依赖于各行业部门计 算机信息系统的建立和发展；其次，面对相关企业部门各式各样的计算机软硬件环境，数 据采集的复杂性成为阻碍计算机审计发展的瓶颈。因此，国内外计算机审计的起步都比较 晚但是，由于计算机审计需求的迫切性以及计算机和网络技术的发展，极大地加速了计 算机审计的发展速度 2 0 0 4 年8 月在南京召开了第二届国际i t 审计研讨会。从对会议的论文”。分析可以 看出，计算机审计主要集中在基于数据仓库技术的计算机审计研究和基于o l p 技术的实时 审计控制等方面。如英国采用数据仓库技术定期检查被审计对象的数据库”1 ，意大利采用 类似木马的技术”“，在被审计对象的信息系统中设置监控软件，对满足某种条件的业务数 据定期反馈给审计部门，香港采用o l a p 技术实时监控被审计单位的数据库”1 ，但是，将 关联规则等数据挖掘技术有效应用于审计行业的例子未见报道。 2 0 0 0 年开始实施的金审工程。极大地推动了我国计算机审计工作的发展相继开发出 一系列的单机环境下的审计辅助软件“，2 0 0 3 年开始的中央一级预算单位的计算机联网 工作，采用数据仓库技术进行在线审计工作，信息技术：会计核算软件数据接口 ( g b t 1 9 5 8 1 2 0 0 4 ) 国家标准也于2 0 0 5 年1 月1 日起生效”1 ，进一步从法律规范上和技术 手段上为计算机在审计中的应用奠定了基础。2 0 0 4 年由审计署、清华大学等1 0 多家单位 参加的“计算机审计数据采集与处理技术”( 8 6 3 计划) 正式立项“在该项目的申请书 中提出要把数据挖掘技术应用于审计中。其中，“基于数据挖掘技术的计算机审计处理核心 技术研究”委托东南大学计算机系和南京审计学院共同承担，我们课题组的研究工作是这 一项目中的一部分。在一定程度上说，我们所进行的面向中观审计的规则发现研究，具有 一定的创新意义 1 2 3 中观审计研究现状 中观审计的概念最旱由审计专家王会金”等人提出，按“中观经济学”的理论对中观 审计的基本依据、客体范围、审计目标及其法律性、协调性和可行性等方面作了系统的分 析和深入的研究近几年，随着国外审计风险研究的兴起，王会金”1 等人又围绕审计风 险研究，提出了较为完整的中观审计理论体系，得到了审计界有关专家的认同其主要思 想是在我国特有的经济活动条件下。以相应的被审计单位为对象，以法律规范为依据，运 用科学系统的方法，对中观( 行业或地区) 的审计行为模式、审计风险及形成机制以及在 此基础上所采取的审计对策、实施结果等进行的研究。 从国外研究来看，已由传统的对被审计单位经济活动的审查。向经济计划和社会规划 5 东南大学博士学位论文 的经济活动审查发展”1 如美国审计理论界强调政策审计。表明了现代审计发展趋势，这 说明王会金等人的中观审计理论是符合现代审计科学发展趋势的 中观审计理论虽然对审计工作具有指导作用，但是，由于受到统计能力的限制，对行 业审计行为模式的分析仍停留在定性层面”1 随着研究的进一步深入，迫切需要用数学 理论和计算技术对行业审计行为模式及行业审计风险形成机制和控制等进行定量研究，课 题组与王会金等专家通过深入研讨一致认为，数据挖掘技术，特别是关联规则的挖掘方式 可以定量描述中观审计模型，发现企业在中观层面的审计行为模式，并且通过这种模式有 效地指导对每个企业的审计工作，提高审计的质量目前，利用数据挖掘技术对现有的大 量的审计数据库进行分析以支持上述研究国内外尚无研究的先例 我们认为把中观审计的理论应用于数据挖掘领域，强调审计人员的“心智”与计算机的 “智能”相结合，追求的是人与计算机相结合的知识系统，从体系上讲，审计专家作为一个 成员，综合到整个系统中去，利用并发挥人和计算机各自的长处。把人和计算机结合起来 形成新的体系这将带来一系列在中观审计的理论研究方向及方法上的变革 1 3 本文主要研究内容 论文研究工作主要针对国内外审计软件在规则发现方面的不足，结合王会金教授等人 提出的中观审计理论，研究面向中观审计的单机环境和分布环境下相关的关联规则挖掘与 更新问题：并且根据我国审计工作的实际需要，研制以海关为审计对象的、面向中观审计 的、基于分布式数据库环境下的关联规则挖掘原型系统。论文主要研究内容包括以下几个 方面： 1 研究面向中观审计的规则发现的挖掘系统的体系框架 从计算机审计的本质特征出发，研究计算机审计的数学函义，并结合海关行业，分析海 关信息系统的结构和流程，进而提出海关行业计算机审计需求的数据模式。论文从中观审 计的理论和海关审计的实际出发，提出了非对等站点结构的分布式数据库环境下的数据挖 掘原型系统a u d i t m i n e r 的体系结构，作成本文研究课题有关算法研究的基础。 2 研究单机环境下的面向中观审计的关联规则挖掘算法 单机环境下的关联规则挖掘算法是所有关联规则挖掘算法研究的基础，也是面向中观 审计的规则发现算法研究的基础，论文对此进行了深入的研究我们发现关联规则算法的 运算量主要体现在：如何确定候选频繁项集和计算候选频繁项集的支持数；如何减 少候选项集的个数和扫描交易数据库的次数对于第个问题，目前已提出了许多很好的 解决办法。但对于第个问题，仍然沿用a p r i o r i 算法的思想，即使用s e l e c t 语句进行合 并和构造哈希树计算支持数必须首先将交易t 的所有k 维子集存储在哈希表中，然后使 用相同的哈希函数来求候选项集的支持数，并且要多次构造哈希树，该次数为最大频繁项 集中项目的个数。运算量是较大的，当支持度较低时，情况将严重恶化因此，如何确定 候选项集和计算支持数亦是a p r i o r i 类算法中的关键技术。目前国内外有关此方面的深入 研究尚不多见为此，本文首次提出了一种基于二进制编码的候选频繁项集生成和相应的 计算支持数算法。可以显著降低算法的实现难度，大大提高算法的执行效率 3 研究分布环境下的面向中观审计的关联规则挖掘算法 现有的分布式关联规则挖掘算法是针对对等结构的分布式数据库环境提出的。本文从 中观审计的实际需要出发，提出非对等站点结构分布式数据库环境下的关联规则挖掘算法 6 第一章引言 采用f d m 算法的思想，利用本文提出的二进制编码技术，提出相应的算法g f d a 。由于 g f d a 算法采用一台机器专门挖掘全局关联规则。从而可以降低通讯开销，因此，g f d a 算法 的性能优于d 姒算法。 4 研究面向中观审的关联规则挖掘更新算法 在中观审计中必须解决关联规则增量更新问题关联规则维护更新算法高效的关键在 于如何减少对数据库的扫描次数和生成较小的候选项集本文提出候选支持度、次频繁项 集和支持数上界等概念，对d w c h e u n g 等人提出的f u p 算法进行了分析，指出其不足之 处，提出了改进的办法。 进一步针对分布式环境下的全局关联规则挖掘的更新问题，本文分两种情况对基于 a u d i t g i n e r 的分布式环境中的布尔关联规则更新问题进行了探讨。 5 研究面向中观审计的规则发现 分析性复核方法在审计中的重要性日益得到重视，开发和应用新的分析性复核方法有 重要意义。b e n _ f o r d 法则作为一种分析性复核方法，目前是国外审计理论界研究的热点之 一基于b e n f o r d 法则的审计方法能够直接分析明细业务数据，并能够定位到具体异常交 易。首先，我们结合海关数据库，验证了b e n f o r d 法则的有效性。然后，利用b c n f o r d 法 则发现了部分异常交易，从而得到这些异常交易的属性集，并且与全局关联规则进行比对， 获得审计感兴趣的规则( 知识) 6 研制以海关为审计对象的、面向中观审计的数据挖掘原型系统a u d i t m i n e r 实现 了本文提出的算法，既验证各个算法的本身的正确性和性能，又验证了这些算法在审计中 的有效性和适用性。 1 4 本文主要研究成果 本文的主要研究成果体现在以下几个方面： ( 1 ) 提出了面向中观审计规则发现的分布式环境结构 本文从中观审计的理论和海关审计的实际出发，提出了不同于d w c h e t m g 的分布式 环境结构。即把站点分为若干个局部站点和一个全局站点，局部站点的任务是挖掘局部频 繁项集，全局站点的任务是挖掘全局频繁项集。这样既满足了审计的需要，也使得通讯代 价由o ( n 2 ) 下降到o ( n ) 。非对等站点结构的分布式环境成为原型系统a u d i t m i n e r 的体系结 构，也是相关算法研究的基础 把中观审计的理论应用于数据挖掘领域，也带来一系列在中观审计的理论研究方向及 方法上的变革 ( 2 ) 提出面向中观审计的基于二进制编码的b a p r i o r i 算法、b f u p 算法和f d m 算 法 关联规则挖掘算法中，其运算量及技术难点主要表现在以下两个方面：如何确定 候选频繁项集和计算候选频繁项集的支持数；如何减少候选项集的个数和扫描交易数 据库的次数。针对其中的第个问题，本文首次提出了一种基于二进制编码的候选频繁项 集生成和相应的计算支持数算法。显著降低了算法的实现难度将该算法与现有a p r i o r i 算法或其改进算法相结合，可以进一步提高算法的执行效率。我们在a p r i o f i 算法、n j p 算法、f d m 算法的基础之上，提出了b a p h o r j 算法、b f u p 算法和f d m 算法等，理论分 析和实验证明这些算法是可行的和有效的关于上列第个问题，由于目前已经提出 许多有效的改进算法，本文对此不再作说明。 7 东南大学博士学位论文 ( 3 ) 提出了面向中观审计的分布式关联规则挖掘算法g f d a 关联规则发现是数据挖掘的重要研究内容，随着数据库中数据的不断积累，大数据集 环境下的关联规则发现日益受到重视，分布式关联规则发现是解决这一问题的有效方法。 针对非对等结构的分布式环境下的规则挖掘原型系统a u d i t m i n e r 的体系结构根据f d m 算法的思想，利用本文首次提出的二进制编码技术，提出了相应的算法g f d a 理论分析 和实验结果表明，g f d a 算法的性能优于d m a 算法同时，对于中观审计来说，算法是有效 可行的 ( 4 ) 提出了面向中观审计的关联规则维护更新算法i f u p 在中观审计检测中大量遇到关联规则挖掘增量更新问题，如何更好地利用原来挖掘的 结果来高效地生成更新后的关联规则就成为各种维护算法讨论的焦点。关联规则维护更新 算法高效的关键在于如何减少对数据库的扫描次数和生成较小的候选项集本文对 d w c h e u n g 等人提出的f u p 算法进行了分析，指出其不足之处，在此基础上，引入候选 支持度、次频繁项集和支持数上界等概念，提出了改进算法i f u p 。实验表明该算法比f u p 算法在性能上有一定的改善。 ( 5 ) 提出面向中观审计的分布式关联规则更新算法g u d a 算法、l u d a 算法、g u d a 2 算法、