（工商管理专业论文）基于关联规则的海关审单商品分组研究.pdf

大连理工大学专业学位硕士学位论文 摘要 海关对报关单的审核通常是建立在了解商品属性的基础上，但审单关员不可能对所 有商品都有所了解，因此必须对审单商品进行分组审核。一份报关单往往含有多项商品， 涉及多个类别，这就需由不同类别的审单专家分别进行审核，这在无形中降低了报关单 的流转速度，增加了审单关员的工作强度，制约了通关效率。如何对审单商品进行科学 合理分组，已经成为海关当前研究的重要课题。 关联规则是数据挖掘研究中的一个重要分支，是对数据库中某些特定事件同时发生 的概率的简单陈述。关联规则挖掘使用特定方法发现数据库中潜藏的关联规则，其在商 业等领域的成功应用，使它成为数据挖掘中最要的研究内容，但关联规则在海关审单商 品分组中的应用还是空白。 本文分析了现行海关人工审单商品分组方法的缺陷，提出了一个以商品关联规则为 依托、辅以专业知识调整的全新的海关人工审单商品分组方法。最后结合a p r i o r i 算法， 以大连海关2 0 0 5 年进出口报关单数据库为原始数据源，以从商品编码中发现频繁项集 为分组基础，进行了实例验证。基于关联规则的分组方法较原方法相比，极大减少了报 关单电子数据的流转次数，提高了海关通关效率。 关键词：关联规则；商品分组；a p r i o r i 算法；海关 基于关联规则的海关审单商品分组研究 a r m - b a s e dr e s e a r c ho nc o m m o d i t yg r o u p i n gf o rc u s t o m sd o c u m e n t s c h e c k i n g a b s t r a c t n o r m a l l y ，t h ec u s t o m sd o c u m e n t sc h e c k i n gi sb a s e do nt h eu n d e r s t a n d i n go f as p e c i f i c c o m m o d i t y ，h o w e v e r ，i ti si m p o s s i b l ef o rac u s t o m so f f i c i a lt ou n d e r s t a n da l lk i n d so ft h e c o m m o d i t i e s f o rb e t t e rd o c u m e n t a r yc h e c k i n g ，i ti s n e c e s s a r yt oc l a s s i f yt h ec o m m o d i t y i t e m s as p e c i f i cd e c l a r a t i o ni n c l u d el o t so fi t e m si nm a n yc l a s s i f i c a t i o n s t h i sn e e d sd i f k r e n t s p e c i a l i s t st om a k et h e i rr e s p e c t i v em a n u a ld o c u m e n t sc h e e k i n g i nt h i sp r o c e s st h ec i r c l i n g t i m eo fd e c l a r a t i o ni sd e c r e a s e d ，t h ew o r k i n gi n t e n s i t yo fc t l s t o m so f f i c i a l si si n c r e a s e da n d t h ee f f i c i e n c yo fc u s t o m sa l e a r i n gi sr e s t r i c t e d n o w a d a y s ，t os c i e n t i f i c a l l y g r o u pt h e c o m m o d i t yi t e m si nd o c u m e n t sc h e c k i n gi sb e c o m i n gt h ei m p o r t a n tr e s e a r c hq u e s t i o ni n s i d e t h ec u s t o m s a s s o c i a t i o nr u l e si sa ni m p o r t a n tb r a n c hi nt h er e s e a r c ho fd a t am i n i n g i ti st h es h o r t d e s c r i p t i o no f t h ep r o b a b i l i t yt h a ts o m es p e c i a la f f a i r sm t h ed a t a b a s eh a p p e ns i m u l t a n e o u s l y m i n i n ga s s o c i a t i o nr u l e si st h ec o u r s eo fu s i n gs p e c i a lm e t h o d st of i n dt h ea s s o c i a t i o nr u l e h i d d e ni nad a t a b a s e i t ss u c c e s s f u la p p l i c a t i o n ，w h i c hh a sb e e na p p r o v e di nc o m m e r c i a lf i e l d ， h a sm a d ei tt h em o s ti m p o r t a n tr e s e a r c hc o n t e n ti nd a t am i n i n g h o w e v e r ，i t sa p p l i c a t i o ni n t h ef i e l do fc u s t o m sc o m m o d i t yg r o u p i n gi ss t i l lb l a n k t h i sp a p e ra n a l y z e st h es h o r t a g e so fc o m m o d i t yg r o u p i n gm e t h o do fo n g o i n gc u s t o m s m a n u a ld o c u m e n t sc h e c k i n g m e a n w h i l et h ep a p e ro f f e r saw h o l l yf r e s hc o m m o d i t yg r o u p i n g m e t h o do fc u s t o m sm a n u a ld o c u m e n t sc h e c k i n g ，w h i c hi sb a s e do nc o m m o d i t ya s s o c i a t i o n r u l ea n ds u p p l e m e n t e dw i t hp r o f e s s i o n a lk n o w l e d g ea d j u s t m e n t s f i n a l l y ，b yu s i n ga p r i o r i a l g o r i t h m ，t h i sp a p e rt r e a t st h ei m p o r t e x p o r td e c l a r a t i o nd a t a b a s eo fy e a r2 0 0 5o fd a l i a n c u s t o m sa so r i g i n a ls o u r c eo fd a t a ，a n db a s e do nl a r g ei t e m s e t si nt h ec o m m o d i t yh sc o d eo f d i f f e r e n td e c l a r a t i o n s ，t h i sp a p e rt e s t i f yt h et r u ed a t u ma sa ne x a m p l e b yc o m p a r i s o nt h e o r i g i n a lm e t h o da n dt h ec o m m o d i t yg r o u p i n gm e t h o do fa s s o c i a t i o nr u l e ，t h ec i r c l i n gt i m ea n d f r e q u e n c yo fd e c l a r a t i o nd i g i t a id a t a i nt h ec o u r s eo fm a n u a ld o c u m e n t sc h e c k i n gi s d i m i n i s h e d ，a n dh i g h e rc u s t o m sc l e a r i n ge f f i c i e n c yi sr e a c h e d k e yw o r d s ：a s s o c i a t i o nr u l e s ；c o m m o d i t yg r o u p i n g ；a p r i o r ia l g o r i t h m ；c u s t o m s 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 大连理工大学专业学位硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 习侵 奠t 旦生年止月丝日 大连理工大学专业学位硕士学位论文 1 绪论 1 1 研究背景与选题意义 当前，随着经济全球化和区域一体化的纵深发展，贸易自由化和全球物流正在深刻 地影响着区域经济的发展，也对海关的传统管理带来了全新的要求和挑战。一方面，进 出口贸易量连年大幅攀升，海关的管理资源特别是人力资源捉襟见肘，跟不上业务量的 飞速增长，海关业务量快速增长和人力资源短缺的矛盾十分突出。另一方面，以市场为 纽带，物流方式正朝着现代化和多元化的趋势发展。“零库存”( z e r oi n v e n t o r y ) 、“及 时生产模式”( j u s t i n t i m e ，简称j i t ) 、“供应商管理库存”( v e n d o r m a n a g e d i n v e n t o r y ， 简称v m i ) 等现代物流理念，第三方物流甚至第四方、第五方物流等现代物流运作方式 正不断得以运用。贸易环境、物流成本正越来越成为企业竞争力的重要组成部分，深刻 地影响着本地区的产业发展，乃至整个地区经济发展的轨迹，而这些也直接影响着海关 的监管，对海关促进现代物流的运作、便利国际贸易的发展、推进区域一体化的进程， 都提出了新的要求。海关作为国家的进出境监督管理机关在严密监管和高效运作两方面 都面临着新的挑战和压力。 为在管理资源相对有限的情况下实现对进出口货物的有效监管，近年来海关实行了 以“集约化、信息化、规范化、专业化”为目标的海关通关作业改革，建立起了“电子 审单”+ “人工审单”的报关单电子数据审核作业系统。企业申报后，报关单电子数据 发送至海关，由计算机根据通道决策参数自动进行逻辑审核( 即电子审单) ，电子审单 判定风险值较低的进入“绿色通道”或“f 通道”，企业直接到现场办理相关手续；达 到一定风险值的进入“红色通道”，由审单处对该报关单实行专业化审单。专业化审单， 又称人工审单，是以商品分组为基础，依靠各职能部门提供的支持和自身的专业化优势， 借助信息化作业平台，对经电子审单环节分拨到审单中心和审单中心自主决定审核的报 关单电子数据进行入工专业化审核的作业过程。人工审单部门负责按照各有关业务职能 处室的管理规定和要求，对进入红色通道进出口货物报关单电子数据进行实时专业化集 中审核，确保其完整性、合法性、合理性。在海关监管中，相当一部分的逃证、偷漏税、 走私情事是在人工审单环节发现的。客观地说，专业化人工审单在海关对报关单的综合 逻辑审核中是必不可少的，但人工审单在很大程度上延缓了报关单的流转速度，严密监 管与高效运作在此构成了二律背反关系。 通常，海关对进出口报关单的综合逻辑审核是建立在了解商品属性的基础上，但由 于人的认知能力所限，作为审单关员的个体不可能对所有进出口商品都有所了解，因此 基于关联规则的海关审单商品分组研究 必须对审单商品进行分组审核，对每类商品设一个专家小组进行审核。我国海关目前分 组的基本原则是按照世界海关组织制定的商品名称及编码协调制度( 简称h s ) 中 的编码序列将人工审单商品分为食品纺织、化工五矿、机电等三个大类，由审单处的三 个审单科室进行人工审核，每个科室的审单关员由相应的专家小组组成，在平均各科室 工作量的前提下对类内审单商品进行微调。 一份报关单往往含有多项商品，涉及多个类别，这就需要在一个类别的审单专家审 完本类商品后再转入其他类专家小组进行审核。同时，海关的专业化人工审单要求不仅 仅审核商品，还要审核报关单数据的合理性与规范性，各项数据之间及审证提示信息与 报关单数据项之间的逻辑对应关系等诸多内容。每一次转单，这些审核都要根据所审商 品重新复查，这在无形中增加了报关单流转次数和审单关员的工作量，延误了通关时间。 以大连海关为例，审单一科负责迸出口动植物产品、食品、化工品、纺织及杂项商品的 审核；审单二科负责进出口贱金属、矿产品及塑料橡胶的审核；审单三科负责进出口机 电仪产品、运输设备的审核。2 0 0 5 年大连海关共人工审核进口报关单2 1 7 8 2 9 份，其中 内部转单4 8 5 9 8 份，占进口审单总量的2 2 3 1 ：共人工审核出口报关单1 6 7 6 6 7 份，其 中内部转单1 4 5 7 0 份，占出口审单总量的8 6 9 。海关总署目前正在实施的区域通关改 革的重要举措之一就是要建立“大关区”概念下的虚拟审单中心，推动人工审单作业由 “关区集中审单”转向“区域集中审单”。届时会产生大量的内部转单、重复审单作业， 必将严重制约通关速度的大幅提升。为了减少转单次数，加快在人工审单环节中报关单 电子数据的流转、提高通关效率，如何对进出1 2 审单商品进行科学合理分组，已经成为 海关当前研究的重要课题。 1 。2 国内外研究发展状况 关联规则挖掘是近几年研究较多的数据挖掘方法【l i ，在数据挖掘的各种方法中应用 得也最为广泛。关联规则的概念由a g r a w a l 、t m i e l i n s k i 和s w a m i 提出，是数据挖掘中 种简单但很实用的规则。关联规则通常用于发现交易数据库中不同商品( 项) 之间的联 系，通过这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。 发现关联规则的算法属于一种无监督学习的方法，用来自行发现隐藏在事物之间的潜在 联系。 目前，与经典的关联规则挖掘研究相比，其具有以下的发展趋势：一是从单一概念 层次关联规则的发现发展到多概念层次的关联规则的发现。也就是说在很多具体应用 中，挖掘规则可以作用到数据库不同的层面上。例如，在分析超市销售事务数据库过程 中，若单单从数据库中的原始字段，如面包、牛奶等等进行规则采掘，可能难以发现令 大连理工大学专业学位硕士学位论文 人感兴趣的规则。这时如果把一些抽象层次的概念也考虑进去，如比面包和牛奶更抽象 的概念：食品，则有可能发现新的更为抽象的规则。所以在数据库中不同的抽象层次上 挖掘规则和元规则是数据挖掘的新的研究内容。二是提高算法效率。显然在挖掘规则过 程中，需要处理大量的数据库记录，并且可能对数据库进行多次扫描，所以，如何提高 算法的效率是非常重要的。现有三种提高效率的思路：一种技术是减少数据库扫描次数， 这种技术对效率会有巨大的提高：另一种是利用采样技术，对要采掘的数据集合进行选 择，这在一些效率更为重要的应用中是非常有效的：最后是采用并行数据挖掘，这是因 为大规模莳数据库经常分布在若干网络节点上，运用并行挖掘技术显然能提高效率，这 对于在i n t e r n e t 上的海量数据挖掘研究具有重要的意义。此外，对获取的关联规则总规 模的控制：如何选择和进一步处理所获得的关联规则；模糊关联规则的获取和发现等也 是关联规则要研究的关键性课题。从挖掘的对象上看，由仅在关系数据库中进行挖掘扩 充到在文本和w e b 数据中进行关联规则的发现等课题也是未来关联规则挖掘要深入研 究和解决的问题。 专业化审单已经成为国内外海关人工审核报关单电子数据的主流模式，但对专业化 审单商品的分组还没有形成科学系统的方法，在海关管理中还没有发现基于进出口商品 的相关性进行分组研究的案例。目前国内海关均以h s 的序列为基础进行条块物理分割， 将9 8 个章的进出口商品按照商品涉及的专业性进行简单分组，大致划分三到四个大类， 此种分组方法简单，易于掌握。但是进出口企业如果存在跨类申报商品，则需对同一报 关单进行多次审核，这对海关和进出口企业形成了双向资源浪费。中国加入w t o 以来， 企业要求对外贸易通关便利化的呼声日益高涨，在这种新的形势下，海关在通关审单环 节加快电子数据流转、提高通关效率已经成为当前研究的重要课题。 1 3 研究方法和组织结构 我国海关h 2 0 0 0 通关管理系统的基础数据库为我们提供了丰富的数据源，使数据挖 掘有了必要保证。本文在现代海关管理模式框架下，从海关人工审单业务的实际需求出 发，指出现行海关进出口商品审单分组方法的缺陷。借鉴数据挖掘的相关理论，结合本 人工作经历，力图提出基于关联性的商品审单分组建议。采用关联规则挖掘的方法，结 合商品审核的专业性、经验性，对海关人工审单商品进行合理分组。尽可能减少同一报 关单跨类审核的可能性，减少在人工审单过程中报关单电子数据的流转时间和次数，节 省人力资源消耗，提高海关通关效率。以下是各章内容概括： 第一章主要对本论文的研究背景、选题意义以及国内外研究发展状况进行了阐述。 基于关联规则的海关审单商品分组研究 第二章对本文将要使用到的相关理论进行了概述，分别介绍了关联规则的概念、种 类及相关算法。 第三章在分析了基于关联规则分组的可行性的基础上，提出了海关审单商品分组的 新方法。阐明了使用a p f i o f i 算法进行关联规则挖掘，实现基于关联规则的海关审单商 品分组过程。 第四章对基于关联规则的海关审单商品分组方法进行了实例验证。最后结合实例进 行了总结。 一4 一 大连理工大学专业学位硕士学位论文 2 关联规则的理论基础 2 1 关联规则的概念 关联规则是数据挖掘研究中的一个重要分支，是对数据库中某些特定事件同时发生 的概率的简单陈述。关联规则挖掘的主要对象是事务数据库，主要针对的应用是售货数 据，也称为货篮数据( b a s k e td a t a ) ，如在超级市场的前端收款机中就收集存储了大量的数 据【1 1 。 在事务数据库中，存在一些涉及到多个物品的事务( t r a n s a c t i o n ) ：事务1 中出现了物 品甲，事务2 中出现了物品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙 在事务中的出现相互之间是否有规律可循呢? 在数据库的知识发现中。关联规则就是描 述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过 量化的数字描述物品甲的出现对物品乙的出现有多大的影响。这些数据中常常隐含着如 下形式的关联规则：在购买面包的顾客当中，有7 0 的人同时购买了黄油。这些关联规 则具有一定的商业价值。商场管理人员可以根据这些关联规则更好地规划商场，如把面 包和黄油这样的商品摆放在一起，以促进销售。 有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但其本质 上仍然可以像对售货数据一样处理。比如人寿保险，一份保单就是一个事务。保险公司 在接受保险前，往往需要记录投保人详尽的信息，有时还要到医院做身体检查。保单上 记录有投保人的年龄、性别、健康状况、工作单位、工资水平等。这些投保人的个人信 息就可以看作事务中的物品。通过分析这些数据，可以得到类似以下这样的关联规则： 年龄在4 0 岁以上，工作在a 区的投保人当中，有4 5 的入曾经向保险公司索赔过。在 这条规则中，“年龄在4 0 岁以下”是物品甲，“工作在a 区”是物品乙，“向保险公 司索赔过”则是物品丙。可以看出来a 区可能污染比较严重，环境比较差导致工作 在该区的人健康状况不好，索赔率也相对比较高。 设i - i ，f ：，毛，f 4 乇) 是一组物品集，w 是一组事务集。w 中的每个事务t 是一 组物品，t c i 。假设有一个物品集a ，一个事务t ，如果a c t ，则称事务t 支持物品 集a ，关联规则是如下形式的种蕴含；a b ，其中a 、b 是两组物品，a c i b c i ， 且a n b = 。一般可以采用四个参数来描述一个关联规则的属性： ( 1 ) 可信度( c o n f i d e n c e ) 设w 中支持物品集a 的事务中，有c 的事务同时也支持 物品集b ，c 称为关联规则a b 的可信度。简单地说，可信度就是指在出现了物品集 a 的事务t 中，物品集b 也同时出现的概率有多大。如上面所举的面包和黄油的例子， 基于关联规则的海关审单商品分组研究 该关联规则的可信度就回答了这样一个问题：如果一个顾客购买了面包那么他也购买 黄油的可能性有多大呢? 在上述例子中，购头面包的顾客中有7 0 的人购买了黄油，所 以可信度是7 0 。 ( 2 ) 支持度( s u p p o r t ) 设w 中有s 的事务同时支持物品集a 和b 。s 称为关联规 则a - - b 的支持度。支持度描述了a 和b 这两个物品集的并集c 在所有的事务中出现的 概率有多大。如果某天共有1 0 0 0 个顾客到商场购买物品，具中有1 0 0 个顾客同时购买 了面包和黄油，那么上述的关联规则的支持度就是1 0 ( 1 0 0 1 0 0 0 ) 。 ( 3 ) 期望可信疫( e x p e c t e dc o n f i d e n c e ) 设w 中有e 的事务支持物品集b ，g 称为 关联规则a b 的期望可信度。期望可信度描述了在没有任何条件影响时，物品集b 在 所有事务中出现的概率有多大。如果某天共有1 0 0 0 个顾客到商场购买物品，其中有2 0 0 个顾客购买了黄油，则上述的关联规则的期望可信度就是2 0 。 ( 4 ) 作用度( 1 i f i ) 作用度是可信度与期望可信度的比值。作用度描述物品集a 的出 现对物品集b 的出现有多大的影响。因为物品集b 在所有事务中出现的概率是期望可 信度；而物品集b 在有物品集a 出现的事务中出现的概率是可信度，通过可信度对期 望可信度的比值反映了在加入“物品集a 出现”的这个条件后，物品集b 的出现概率 发生了多大的变化。在上例中作用度就是7 0 ，2 0 = 3 5 。 用p ( a ) 表示事务中出现物品集a 的概率，p ( b i a ) 表示在出现物品集a 的事务中， 出现物品集b 的概率，则以上四个参数可用公式表示，如表2 1 所示。 表2 1 四个参数的计算公式 t a b 2 1c a l c u l a t i n gf o r m u l a so f f o u rp a r a m e t e r s 可信度是对关联规则的准确度的衡量，支持度是对关联规则重要性( 或适用范围) 的衡量。支持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联 规则越重要，应用越广泛。有些关联规则可信度虽然很高，但支持度却很低，说明改关 联规则实用的机会很小，因此也不重要。 期望可信度描述了在没有物品集a 的作用下，物品集b 本身的支持度；作用度描 述了物品集a 对物品集b 的影响力的大小。作用度越大，说明物品集b 受物品集a 的 大连理工大学专业学位硕士学位论文 影响越大。一般情况，有用的关联规则的作用度都应该大于1 ，只有关联规则的可信度 大于期望可信度，才说明a 的出现对b 的出现有促进作用，也说明了它们之间某种程 度的相关性；如果作用度不大于l ，则此关联规则也就没有意义了。应该指出，在这四 种度量中，最常用的是可信度和支持度。 2 2 关联规则的种类 关联规则可按所处理数据的不同方面进行分类： ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型 关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值型关联 规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态 的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。 例如：小明= “学生”j 等级= “优秀”：等级= “优秀”成绩= “9 5 ”，涉 及的成绩是数值类型，所以是一个数值型关联规则。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单 层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的。在多层 关联规则中，对数据的多层性已经进行了充分的考虑。 例如：百年牌面包好合牌牛奶，是一个细节数据上的单层关联规则；面包好 合牌牛奶，是一个较高层次合细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单 维关联规则中，我们只涉及到数据的一个维，如用户购买的物品。在多维关联规则中， 要处理的数据将会涉及多个维。 例如；面包；牛奶，这条规则只涉及到用户购买的物品；小明= “学生”等等级 = “优秀”，这条规则就涉及到两个字段的信息，是两维关联规则。 2 3 关联规则挖掘算法概述 关联规则的挖掘问题主要就是在事务数据库d 中找出具有用户给定的最小支持度 ( m i n s u p ) 和最小可信度( m i n e o n o 的关联规则。因此，挖掘关联规则问题可以分解为以下 两个子问题【l j ： ( 1 ) 找出存在于事务数据库中的所有大物品集( 常用物品集或频繁集) 。物品集 x 的支持度s u p p o r t ( x ) 不小于用户给定的量小支持度m i n s u p ，则称x 为大物品集 ( 1 a r g e i t e m s e t ) ( 2 ) 利用得到的大项集生成关联规则。对于每个大项集a ，若b c a ，b 面，且 c o n f i d e n c e ( ba b ) ) m i n e o n f , 则构成关联规则b j ( a b ) 。 基于关联规则的海关审单商品分组研究 第二个子问题比较容易。目前大多数研究集中在第一个子问题上。r a g r a w a l 等人 提出了关联规则的挖掘问题以后，该问题的研究得到了长足地发展，形成了针对不同类 型问题的诸多算法 4 1 。 ( 1 ) 多循环方式的挖掘算法 此类算法包括a g r a w a l 等人提出的a i s ，a p r i o r i 、a p r i o r i t i d 和a p f i o r i h y b r i d 、p a r k 等人提出d h p ，s a v a s e r e 等人的p a r t i t i o n 以及t o i v o n e n 提出的抽样算法s a m p l i n g 等等。其中最有效和有影响的算法为：a p r i o r i 、d h p 和p a r t i t i o n 。 在算法a i s 中，候选大项集是在扫描数据库的过程中产生的。具体地说，在对数据 库进行第k 次扫描时，候选大项集( 其中每一个元素的元素个数不一定是k 个，可以大 于k ) 是由第k ，1 次扫描所产生的边界集( f r o n t i e rs e 0 通过增加当前事务中的项得到。同 时计算候选大项集中的元素的支持数，直到某一次扫描所产生的边界集为空时停止运 算。应该注意的是，第k 次扫描所产生的边界集要大于本次扫描生成的大项集。本算法 的缺点在于生成的候选大项集太大。 算法a p r i o r i 和a p r i o r i t i d 利用“在给定的事务数据库d 中任意大项集的子集都是 大项集；任意弱项集的超集都是弱项集”这一原理对事务数据库进行多遍扫描，第一次 扫描得出大1 项集厶，第k ( 妨1 ) 次扫描前先利用第k - 1 次扫描的结果( 即大k - 1 项集l ) 和函数a p r i o r ig e n 产生候选大k 项集q ，然后在扫描过程中确定c t 中每一元素的支持 数，最后在每一遍扫描结束时计算出大k 项集k ，算法在当候选大项集c t 为空时结束。 由于充分利用的上述原理，这两个算法所产生的候选大项集要比算法a i s 小得多，从而 提高了算法的效率。算法a p r i o r i t i d 还有另外一个特点，即仅在第一次扫描时用事务数 据库d 计算候选大项集的支持数，其它各次扫播用其上一次扫攒生成的候选事务数据库 d 来计算候选大项集的支持数。在最后的几次扫描中，d 的大小要远远小于d ，减少 了f o 操作时间，提高了算法的效率。算法a p r i o r i h y b r i d 是算法a p r i o r i 与算法a p f i o r i t i d 的结合，当候选事务数据库d 7 不能完全容纳到内存时用算法a p r i o r i ，当内存能够完全 容纳候选事务数据库d ，时，则用算法a p r i o r i t i d 。 算法d h p 利用哈希( h a s h i n g ) 技术有效地改进了候选大项集的生成过程，产生了比 前述算法更小的候选大项集( 对大2 候选集尤为明显) ，同时也缩减了事务数据库的大小， 减小了i o 操作时间，其效率比算法a p r i o r i 有明显提高。 算法p a r t i t o n 分为两个部分。在第一部分中，算法首先将要在其中发现关联规 则的事务数据库d 分为n 个互不相交的事务数据库d i ，d 2 ，d 4 ( i = l ，2 ， n ) 的大小要求能够容纳在内存之中，然后将每一个分事务数据库d ( i = l ，2 ，n ) 一8 一 大连理工大学专业学位硕士学位论文 读入内存并发现其中的大项集f ，最后在第一部分结束时将所有分事务数据库的大项集 合并成为一个在事务数据库d 中的潜在大项集p l = y 笛r ；算法第二部分计算潜在大项 集p l 在事务数据库d 中的支持数，并得出大项集l 。该算法只对事务数据库d 扫描两 次，大大减少了i o 操作，从而提高了算法的效率。 算法s a m p l i n g 设计思想为：对事务数据库d 进行随机抽样得到抽样事务数据库d ， 先以小于用户给定的最小支持度的支持度发现存在于d ，中大项集三，再在剩下的数据 库d d ，中继续计算中各元素的支持数，最后以用户给定的最小支持度计算出大项集 l 。在大部分情况下，可以用此方法发现正确的大项集，但有时可能会漏掉一些大项集， 这时可以对d 进行第二次扫描以得出漏掉的大项集。此算法在大部分情况下可以只对d 进行一次扫描就得出大项集，最坏的情况对d 进行两次扫描，因而算法效率较高。 ( 2 ) 增量式更新算法 关联规则的增量式更新问题主要有两个：第一，在给定的最小支持度和最小置信度 下，当一个新的事物数据集d b 添加到旧的事物数据库d b 中时，如何生成d byd b 中 的关联规则；第二，给定事物数据库d b ，在最小支持度和最小可信度发生变化时，如 何生成数据库d b 中的关联规则。 算法f u p 的基本思想为：对任意一个k ( k 1 ) 项集，若其在d b 和d b 中都是大项集， 则其一定是大项集；若其在d b 和d b 中都是弱项集，则其一定是弱项集；若其仅在d b ( d b ) 中是大项集，则其支持数应加上其d b ( d b ) 中的支持数以确定它是否为大项集。算法f 【伊 假设在d b 中发现的大项集l = y 笛厶( n 为中最大元素的元素个数) 已被保存下来。它 需要对d b 和d b 进行多次扫描，在第1 次扫描中，算法先扫描d b ，将中的元素仍为 d b y d b 中的大项集的元素记入上l 中。在第k o 【 1 ) 次扫描前，先对工女一l 用a p r i o r i _ g e n 函数生成候选大k 项集c t ，并除去k 中的元素，即q = c t - l k ，对k 进行剪枝，即 对于x e l t ，若存在y a l t l 川，则x 肯定不会是曲y d b 中的大k 项集，应将其 在缸中删除；然后扫描d b ，将丘中的元素仍为d b y d b 中的大项集的元素，记入乩中。 算法在k 和c t 均为空时结束。由于利用了对d b 进行挖掘的结果，本算法的效率比再 一次利用算法a p r i o r i 或d h p 对d byd b 进行挖掘的效率要高得多。 算法i u a 采用了一个独特的候选大项集生成算法i u ag e n ，在每一次对数据库d b 扫描之前生成较小的候选大项集，从而提高了算法的效率。它也要求上一次对数据库 d b 进行挖掘时发现的大项集l - y 譬f ( n 为l 中最大元素的元素个数) ，在本次挖掘时 基于关联规则的海关审单商品分组研究 是可得到的。因为人们在发现关联规则时，常常需要不断地调整最小支持度和最小可信 度来聚集到那些真正令其感兴趣的关联规则上，因而本算法具有很重要的意义。 ( 3 ) 并行发现算法 目前己经提出的并行采掘关联规则的算法有：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 ) 、d d ( d a t ad 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 ) ，p a r 等人提出的p d m ， c h u e n g 等人提出的算法d m a 和f d m 。虽然是基于分步式数据库的挖掘算法，但也可 适用于并行挖掘。 算法c d 具有速度较快、容易实现、要求各计算机间同步次数较少等优点，但它有 通信量大和候选大项集大等缺点。算法c a d 、d d 及p d m 的执行效果都不如c d 。算法 d m a 虽克服了算法c d 的一些弱点，但它要求各计算机间同步次数较多。算法f d m 与 算法d m a 基本一致，区别在于f d m 中增加了全局剪枝技术。 这些算法都是基于无共享体系结构，即并行计算的n 台计算机之间除了用网络连接 起来以外，其它都是完全独立的。每台计算机尸。( i - l ，2 ，n ) 上都有自己的分事 务数据库d b 。，总的事务数据库d b = y n 矧d b 。 算法c d 是算法a p r i o r i 在并行环境下的应用，它要求计算机( i - l ，2 ，n ) 对d b 进行多遍扫描。在第k 次扫描，当k l 时，计算机( i = l ，2 ，n ) 首先利 用第k 1 次扫描所得的大项集t 。从和a p r i o 垣g e n 函数生成候选大项集q ，当k = l 时， 计算机p 先扫描d b 。，得出其中的大1 项集再与其它计算机得到的大1 项集进行 交换并进行合并，从而生成候选大l 项集c ；然后扫描d b 。计算g 中的元素在d b 中的 支持数，计算机j p 广播q 中元素的支持数，并接收从其它计算机p j 0 0 i ) 传来的e 中 元素的支持数，并对这些支持数进行累加，得出c 中元素的全局支持数；最后计算出大 k 项集丘，若厶中元素个数为1 ，则算法结束。 算法d m a 是基于“若项集x 在d b 中是大项集，则其必在某一个d b 。也是大项集” 的原理进行设计。算法中采用局部剪枝技术( l o c a lp r u n i n g ) ，使其生成的候选大项集比 算法c d 要小。算法各个站点进行支持数交换时采用轮询站点技术( p o i l i n gs i t e ) ，使每一 个项集x 的通讯代价由算法c d 的o ( n 2 ) 降为o ( n ) ，其中n 为站点个数。 ( 4 ) 采掘一般或多层关联规则 在研究挖掘关联规则的过程中，许多学者发现在一些实际应用中，由于数据比较少， 要想在原始的概念层次上发现强的( s t r o n g ) 和有趣的( i n t e r e s t i n g ) 关联规则是比较困难的， 因为好多项集往往没有足够的支持数。由于概念层次在要挖掘的数据库中经常是存在 大连理工大学专业学位硕士学位论文 的，比如在一个连锁店会存在这样概念层次：旭日牌牛奶是牛奶，牛奶是食品等，我们 称高层次的项是低层次项的父项，这种概念层次关系通常用一个有向非循环图( d a g ) 来 表示。于是我们就可以在较高的概念层次上发现关联规则。基于要挖掘的数据库中的概 念层次和发现单一概念层次中的关联规则的算法，主要有：h a r t 等人的m l _ t 2 l 1 及其 变种m lt 1 l a 、m lt m l i 、m lt 2 l a 和r s r i k a n t 等人的c u m u l a t e 、s t r a t i f y 及其变 种e s t i m a t e 、e s t m e r g e 、m l _ a r 等。 算法m lt 2 l 1 的基本思想是首先根据要发现的任务从原事务数据库生成一个根据 概念层次信息进行编码的事务数据库，利用这个具有概念层次信息的新生成的数据库， 自顶向下逐层递进地在不同层次发现相应的关联规则。它实际上是算法a p r i o r i 在多概 念层次环境中的扩展。根据对在发现高层关联规则过程中所用的数据结构和所生成的中 间结果共享方式的不同，算法m l t 2 l 1 有三个变种；m l t 1 l a 、m l _ t m l l 、m l _ t 2 l a 。 算法c u m u l a t e 的基本思想与a p r i o r i 完全一样，只是在扫描到事务数据库某一事务 时，将此事务中所有项的父项加入到本事务中，并加入三个优化：对加入到事务中的父 项进行过滤；预先计算概念关系t 中的每一个项的父项，得到项集与其父项的对照表 t + ：对既包含项集x 又包含x 的父项的项集进行剪枝。 算法s t r a t i f y 基于“若项集x 的父项不是大项集，则x 肯定不会是大项集”的事实 进行设计。其基本思想为：在概念层次有向非循环图中，定义没有父项的项集x 的深度 d e p t h ( x ) = 0 ，其它项集的深度为：( m a x d e p t h ( x ) i x + 是x 的父项 卜1 ) 。算法要对事务数 据库进行多遍扫描，第k ( k 0 ) 次扫描计算深度为k ( k o ) 的所有项集c 的支持数，并得 出深度为k ( k o ) 的大项集丘，在第k ( k 1 ) 次扫描之前，对g 进行剪枝，即删除g 中 那些父项包含在g - l - 丘一，中的元素。围绕着怎样及早决定某些深度较大的项集是否是大 项集问题，用抽样技术对算法s t r a t i f y 进行扩展，形成算法e s t i m a t e 和e s t m e r g e 。 ( 5 ) 挖掘多值属性关联规则 关联规则可分为布尔型关联规则和多值属性关联。多值属性又可分为数量属性和类 别属性。目前提出的挖掘多值属性关联规则的算法大多是将多值属性关联规则挖掘问题 转化为布尔型关联规则挖掘问题，即将多值属性的值划分为多个区间，每个区间算作一 个属性，将类别属性的每一个类别当作一个属性。 属性划分方法不能很好地表示数据的分布，尤其是属性值分布不均匀的时候，于是 提出了一个聚类算法，根据数据库中数据的分布情况决定属性值如何划分区段，并可将 相关的区段进行合并。在此基础上发现的多值关联规则更具有效性和可理解性。 ( 6 ) 基于约束的关联规则挖掘 基于关联规则的海关审单商品分组研究 基于约束的关联规则挖掘的主要目的是发现更有趣的，更实用的和更特别的关联规 则。 在提供布尔表达式约束情况下的关联规则发现问题。这种布尔表达式约束允许用户 指定他所感兴趣的关联规则的集合，这种约束不仅可以用来对事务数据库进行预加工， 而且可以把它集成在挖掘算法内部，从而提高算法的执行效率，根据这种集成方式的不 同给出了三种不同的算法：m u l t i p l e j o i i l s 、r e o r d e r 、d i r e c t 。 关联规则挖掘算法c a p 。提出并分析了用户所给出的约束的两个对发现算法的剪枝 步骤非常重要的属性：反单调性( a 1 1 t i m o n o t o i l i c i 劝和简洁性( s u c c i n c t n e s s ) 。 另一种类型的基于约束的关联规则挖掘方法是元模式制导的关联规则挖掘算法。这 种类型的发现算法首先由用户给定要发现的关联规则的元模式或模板，然后根据这些模 板在数据库中发现与模板相适应的实际存在的关联规则。基于这种模式两个相应的算法 是：大谓词增长算法( 1 a r g ep r e d i c a t e g r o w i n g )