（管理科学与工程专业论文）联系发现挖掘方法及应用研究.pdf

联系发现挖掘方法及应用研究 摘要 联系发现是数据挖掘中较新的研究领域。它的目的是从大型的、异构的数 据集中自动识别已知的、复杂的、多关系的模式，更重要的是发现未知的但具 有重要联系的模式，这些模式指示出潜在的异常的、威胁性的活动。联系发现 主要是针对反恐提出的，但随着联系发现技术的深入研究与发展，目前联系发 现技术已经被应用到社会生活的各个领域中，如法律诉讼调查、反欺诈侦察、 社会网络分析以及电信通讯等。目前对于联系发现的研究主要集中在对联系发 现方法、联系发现系统设计、联系发现的数据处理、联系发现的可信度、联系 发现方法的性能评估以及联系发现的应用等方面。 本文在广泛深入地查阅了国内外文献的基础上，对联系发现的方法和应用 进行了深入地研究，主要内容如下： 本文首先详细介绍了数据挖掘发展的历史，并由此分析了联系发现这个新 的研究领域产生的必然性与必要性。然后对联系发现的基本理论、方法、系统 以及应用情况进行了详尽地介绍。 接着对经典的无监督联系发现方法中的新颖节点发现问题进行了全面的分 析。由于在原方法中使用基于距离的k 近邻算法求解异常点，而这种算法使用 的是全局阈值，因此在处理含有不同密度区域的数据集时具有一定的局限性。 此外，原方法没有考虑到每个特征的权重，把所有特征都同样看待，在实际应 用中会使结果产生很大的偏差。针对上述问题，本文提出了基于密度的无监督 联系发现方法，给出了算法的具体步骤，并进行了实验与分析。 然后将基于密度的无监督联系发现方法应用于反洗钱领域中。针对目前洗 钱行为的复杂性以及传统的数据挖掘技术在反洗钱应用时的局限性，本文利用 联系的分析方法，寻找可疑对象，有效地提高侦破效率。并在此基础上提出了 基于联系发现数据挖掘技术的反洗钱系统模型，详细分析了系统模块功能。 本文围绕联系发现问题，在现有成果的基础上，提出了新的联系发现方法， 并将其应用于反洗钱领域中。以上研究为联系发现方法的研究提供了一种新的 思路，也为反洗钱应用提供了一种有效的工具。 关键词：联系发现：链接挖掘；无监督联系发现；反洗钱；基于密度 r e s e a r c ho nt h ea l g o r i t h ma n da p p l i c a t i o no f l i nk d i s c o v e r y a b s t r a c t l i n kd i s c o v e r y ( l d ) i san e wr e s e a r c hf i e l di nd a t am i n i n g i ti sa i m e da t i d e n t i f y i n gk n o w n ，c o m p l e x ，a n dm u l t i - r e l a t i o n sp a t t e r n sa u t o m a t i c a l l yf r o m l a r g e s c a l ea n dh e t e r o g e n e o u sd a t a s e t s m o r ei m p o r t a n t l y , i ti st of i n du n k n o w nb u t v e r yu s e f u ll i n k sw h i c hi n d i c a t et h ep o t e n t i a lt h r e a t e n i n ga c t i v i t i e s l i n kd i s c o v e r y i sp r o p o s e df o ra n t i - t e r r o r i s mm a i n l y n o wl i n kd i s c o v e r yh a sb e e na p p l i e di n t oa w i d er a n g eo fr e s e a r c ht o p i c s ，i n c l u d i n gl a wi n v e s t i g a t i o n ，f r a u dd e t e c t i o n ，n e t w o r k a n a l y s i s ，t e l e c o m m u n i c a t i o n ，a n ds oo n 。r e c e n t l yt h er e s e a r c ho fl i n kd i s c o v e r yi s c o n c e r n i n ga b o u tt h em e t h o d s ，s y s t e md e s i g n ，a p p l i c a t i o n s ，c o n f i d e n c ei n t e r v a l s a n dp e r f o r m a n c ev a l u a t i o no fl i n kd i s c o v e r y t h ed i s s e r t a t i o nm a i n l yf o c u s e so nt h em e t h o d sa n da p p l i c a t i o n so fl i n kd i s e o v e r yo nt h eb a s i so ft h er e v i e wo fr e c e n tw o r k s t h em a i nc o n t e n t sa r ed e s c r i b e d a sf o l l o w s ： f i r s t l y ，t h eh i s t o r yo ft h ed e v e l o p m e n to fd a t am i n i n gi sd e s c r i b e di nd e t a i l 。 t h e nt h ed i s s e r t a t i o nd i s c u s s e sa b o u tt h en e c e s s i t ya n di n e v i t a b i l i t yo ft h ea p p e a r - a n c eo ft h en e wf i e l do fl i n kd i s c o v e r y t h et h e s i sa l s od i s c u s s e sa b o u tt h eb a s i c t h e o r ya n da p p l i c a t i o n so fl i n kd i s c o v e r y ( l d ) ，a n da n a l y z e st h em a i nm e t h o d s ， c l a s s i c a ls y s t e m s s e c o n d l y ，t h et h e s i sa n a l y z e st h ep r o b l e m so ft h ec l a s s i c a ln o v e ln o d ed i s c o v - c r yi nt h eu n s u p e r v i s e dl i n kd i s c o v e r yi n d e t a i l t h ep r o b l e mi ss o l v e db y k - n e i g h b o r ( k n n ) m e t h o db a s e do nt h ed i s t a n c et of i n dt h ea b n o r m a ld a t a ，b u td u e t ot h eg l o b a lt h r e s h o l d ，k n ni sw e a ki nd e a l i n gw i t ht h ed a t a s e tw h i c hc o n t a i n s d i f f e r e n td e n s i t y f u r t h e r ，k n ni sn o tc o n s i d e r i n ga b o u tt h ew e i g h to f e a c hc h a r a c t e r , a n dw i l lh a v eab a di n f l u e n c ei nt h ea p p l i c a t i o n o nt h i sb a s i s ，t h ed i s s e r t a - t i o ns u g g e s t san e wm e t h o do fu n s u p e r v i s e dl i n kd i s c o v e r yb a s e do nt h er e l a t i v e d e n s i t y t h ed e t a i l e ds t e p so ft h ea l g o r i t h ma r eg i v e na n dt h ee x p e r i m e n t sa r ea l s o p r o p o s e d 。 t h i r d l y , t h en e wm e t h o do fu n s u p e r v i s e dl i n kd i s c o v e r yh a sb e e na p p l i e di n t o t h ef i e l do fa n t i m o n e yl a u n d e r i n g a c c o r d i n gt ot h ec o m p l e x i t yo fm o n e yl a u n - d e r i n ga c t i v i t ya n dt h el i m i t a t i o no ft h et r a d i t i o n a ld a t am i n i n gm e t h o d s ，t h et h e s i s u s e st h ep r o p o s e dn e wm e t h o dt of i n dt h ed o u b t f u la c c o u n ts oa st oi m p r o v et h e e f f i c i e n c yo fi n v e s t i g a t i o n o nt h i sb a s i s ，af r a m e w o r ko fa na n t i m o n e yl a u n d e r i n g s y s t e mb a s e do nl i n kd i s c o v e r ym i n i n gt e c h n i q u eh a sb e e np r o p o s e d ，a n dt h ef u n c 一 l 差 t i o n so ft h es y s t e mm o d u l e sh a v ea l s ob e e nd i s c u s s e d t h ed i s s e r t a t i o np r o p o s e san e wm e t h o do fl i n kd i s c o v e r ya c c o r d i n gt oi t s p r o b l e m so nt h eb a s i so ft h ec u r r e n tw o r k s ，a n da l s ou s e st h en e wm e t h o dt os o l v e t h ep r o b l e mo fa n t i m o n e yl a u n d e r i n g t h i sr e s e a r c hh a sb r o u g h tan e wt h i n k i n gt o l i n kd i s c o v e r y ，a n da ne f f e c t i v et o o lt oa n t i m o n e yl a u n d e r i n g k e y w o r d s ：l i n kd i s c o v e r y ；l i n km i n i n g ；u n s u p e r v i s e d l i n kd i s c o v e r y ；a n t i m o n e yl a u n d e r i n g ，d e n s i t yb a s e d i i i 插图清单 1 1 高级数据挖掘分类2 1 2 联系发现方法与应用3 1 3 论文组织结构图6 2 1 一个神经元网络9 2 2 一颗简单的决策树9 2 3 链接挖掘任务图1 2 2 4l d c a 方法的三个基本步骤18 2 5 文献引用关系网络图1 9 2 6c a d r e 系统结构图1 9 2 7k o j a k 系统结构图2 0 3 1 点簇图2 6 3 2 算法流程图2 8 3 3 文献关系网络图3 0 4 1 资金交易网络图3 7 4 2 基于联系发现数据挖掘技术的反洗钱系统构架4 0 图图图图图图图图图图图图图图图 表3 1 表3 2 表3 3 表4 1 表4 2 表格清单 文章清单3 0 异常贡献度矩阵3 1 求解结果3 1 异常贡献度矩阵3 7 求解结果3 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 金月曼王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位澈作者魏炙讨 签字隗_ 年 肜日 学位论文版权使用授权书 本学位论文作者完全了解佥目垦王些太堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金旦墨王些盔堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 炙拂 j 签字日期：叫年4 月扣日 学位论文作者毕业后去向： 工作单位： 通讯地址： ：降研 签字日期：沙7 年护月尹日 致谢 值此论文完成之际，我谨向所有关心和帮助过我的老师、同学、朋友以及 家人致以最真诚的谢意。 首先，我要深深地感谢我的导师倪志伟教授。本人在学习、论文写作以及 平时的生活中，自始至终得到了倪老师的悉心指导。无论从课程学习、论文选 题，还是到资料收集、论文修改定稿，无不渗透着倪老师的智慧和心血。倪老 师渊博的知识、严谨的治学作风以及富于创新的学术思想，让我在学业上受益 匪浅，同时也培养了我踏踏实实研究学问的态度，这些都将使我终身受益，并 激励我不断前进。 感谢智能管理研究所的所有同学，正是通过与你们的互相交流、互相帮助， 我才得以不断提高。特别要感谢王丽红、梁敏君、郑盈盈、高雅卓、杨葛钟啸、 罗义钦、胡汤磊在学习和生活上的帮助，衷心地祝各位前程似锦! 感谢合肥工 业大学计算机与信息学院罗贺同学，感谢他一直以来对我的关心、帮助、鼓励 和支持。 感谢合肥工业大学管理学院2 0 0 6 级研究生2 7 班的全体同学。他们在近三 年的学习和生活中给了我帮助和鼓励。 同时，研究生阶段学习和生活中，我得到了许多朋友的关心，特别要感谢 我的室友包海飞和程业嫒，感谢你们的支持与关怀! 感谢各位评审专家在百忙之中抽出时间对论文进行了仔细的评阅! 借此机会，感谢我的父母家人，是他们二十多年来的呵护、关心、支持和 鼓励，使我得以顺利完成学业。感谢他们给我健康的身体、上进的思想! 作者：吴姗 2 0 0 9 年3 月 第一章绪论 联系发现( l i n kd i s c o v e r y ，l d ) ，是数据挖掘中较新的研究领域，它综合 了计算机科学、社会学等多个领域的知识，被认为是关系数据挖掘中的挑战之 一。联系发现最早由美国国防部高级研究计划局( d e f e n s ea d v a n c e dr e s e a r c h p r o j e c t sa g e n c y ，d a p p a ) 提出，经过数十年的发展，目前已经在诸多领域中 得到了广泛的应用。本章介绍了联系发现的研究背景和意义，分析了联系发现 的研究现状，并给出了论文的主要研究内容和结构。 1 1 联系发现研究背景和意义 随着计算机网络技术、通讯技术、数据库技术等信息技术的迅速发展和广 泛应用，各种数据正以惊人的速度堆积。虽然人们搜集数据的能力大幅度提高， 但是数据处理的能力却远远不及数据获得的能力。正是由于数据的产生和传输 能力与处理能力之间的不平衡性，人们希望借助各种技术提高数据的分析能力， 更好地为决策服务。因此，数据挖掘( d a t am i n i n g ，d m ) 技术应运而生，不 断发展，并在实际应用中逐渐显示出其强大的生命力。 数据挖掘被描述为从大型数据库的数据中提取隐含的、事先未知的、潜 在的有用信息，获取人们感兴趣的知识。这些知识可以表示为概念( 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 ) 等形式【】。 由于现代数据搜集、高级数据库系统和万维网技术的飞速发展，数据的实 时性、联系性、复杂性的不断加大，各种复杂形式的数据( 例如，半结构化与 非结构化数据、空间和时态数据、超文本与多媒体数据) 都有了爆发性增长。 越来越多行业需要借助数据挖掘技术来提高数据的利用率，为决策提供支持。 随着数据挖掘技术不断地扩展到更多的领域，出现了一些新的研究任务，包括 w e b 数据挖掘、时间序列挖掘、空间数据挖掘、流数据挖掘、链接挖掘等新的 研究方向。目前，这些任务被视为是数据挖掘中的高级主题。这些新的任务给 数据挖掘技术带来了新的发展，也提出了巨大的挑战【lj 。 链接挖掘( l i n km i n i n g ，l m ) 【18 】是数据挖掘高级主题中一个十分重要的 组成部分。链接挖掘是针对数据间具有复杂联系的数据而言的，因此在链接挖 掘的过程中必须要考虑数据之间的链接关系。链接挖掘研究内容很多，主要有 基于链接的对象排序【3 1 、基于链接的对象分类 4 1 、基于链接的聚类”】、联系发现 】、子图挖掘【7j 等。本文研究的联系发现是链接挖掘的一个子方向，联系发现 的提出是由于在对数据进行处理的过程中，发现许多应用领域出现了海量的、 复杂联系数据，数据之间的联系不再是两个实体间的简单联系，而是由多个联 系组合而成的复杂联系。在这样的复杂联系中往往蕴含着很多有用的信息。 图1 1 高级数据挖掘分类 联系发现的目的就是从海量的、异构的数据集合中，自动识别出异常的和 危险的活动。“9 11 事件 就是一个典型的拥有许多零散情报信息的实例，由于 没有及时把这些信息联系起来进行分析，导致未能提前预防恐怖事件的发生， 给社会带来了重大的损失。 联系发现词最早出现在美国的官方文件中。1 9 9 8 年6 月，在自动学习和发 现中心( a u t o m a t e dl e a r n i n ga n dd i s c o v e r y ，a l d ) 开放后，美国国防部高级研 究计划局( d a r p a ) 在卡内基梅隆大学举行一次预备计划会议上首次提出了联 系发现的概念，并建立了一项“证据提取与链接发现 ( e v i d e n c ee x t r a c t i o na n d l i n kd i s c o v e r y ，e e l d ) 的研究计划【9 】。“9 1 1 事件 以后，利用计算机信息处 理技术帮助情报机构提早发现和防止恐怖主义逐渐成为了全世界共同关注的焦 点。为此，美国国防部也试图借“证据提取与链接发现”研究计划来解决这个 问题。 联系发现是对大量的关系型数据进行分析，识别其中可能存在的威胁活动 的模式，并利用模式匹配机制在大量的数据中发现满足模式的实例【l7 1 。因此这 种方法只能发现已知模式的实例，然而在海量的、多关系数据挖掘中，模式信 息往往是复杂的，多关系的，甚至是难以学习的。因此s e n a t o r 将联系发现定义 为不仅要发现已知模式的证据，更重要的是发现未知的但可能是很重要的联系 【9 】 o 联系发现的研究涉及到多个研究领域的方法和技术，例如离散数学( 图论) 、 社会学( 社会网络分析) 和计算机科学、图挖掘、超文本和w e b 挖掘等方面。 因此联系发现研究的范围也很广，包括社会关系分析、欺骗调查、图理论、模 式分析和联系分析等。目前，对于联系发现的研究主要集中在联系发现方法研 究、联系发现系统设计、联系发现方法评估、联系发现数据处理、联系发现应 用这几方面。随着联系发现的深入研究，联系发现己经被广泛应用于许多社会 领域，例如法律诉讼调查、反欺诈侦察、社会网络分析以及电信通讯等。其中 对联系发现的研究主要还是集中在防止恐怖主义等异常威胁性的活动上。 图1 2 联系发现方法与应用 可见，研究联系发现具有重要的理论和现实意义。目前，经过数十年的研 究，联系发现虽然有了一定的发展，但还不完善，处于初级阶段，还有很多问 题需要进一步深入的研究。 1 2 联系发现研究现状 美国“9 11 事件”以后，美国国防部高级研究计划局试图借“证据提取与 联系发现”研究计划【9 】帮助情报机构提早发现和防止恐怖主义。这个计划的目 的是大力发展能够在海量分类的、非分类的数据源中自动发现、抽取和链接稀 少证据的技术和工具，以达到帮助情报机构提早发现危险性活动的目的。“证据 抽取与联系发现【4 1 】 【2 4 】 【4 2 】项目主要涉及三个方面的子任务 9 】：证据抽取 ( e v i d e n c ee x t r a c t i o n ) 、联系发现( l i n kd i s c o v e r y ) 、模式学习( p a t t e r n l e a r n i n g ) 。证据抽取的任务是从非结构的自然语言文档中抽取获得结构化的证 据。联系发现是对大量的关系型数据进行分析，从中识别出潜在威胁性活动的 已知的、复杂的、多关系的模式。联系发现的数据一部分来自于证据抽取，其 它的来自于已有的关系型数据库。模式学习的目的是自动学习潜在威胁性活动 的新关系模式。此后，联系发现又成为数据挖掘领域顶级会议知识发现与数据 挖掘( k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ，k d d ) 的研究焦点，k d d 会议于 2 0 0 5 举行l i n kd i s c o v e r y 专题会议。会议上t e ds e n a t o r 提出了联系发现研究的重 要性以及联系发现的研究难点等问题。， 联系发现的目的就是从海量的异构数据集合中，自动识别出异常的和危险 的活动。基于联系发现挖掘的现状，对联系发现的研究主要集中在以下几个方 面【1 9 ： ( 1 ) 联系发现方法研究 针对联系发现数据的特点，研究高效挖掘算法，从而在大量的、复杂数据 中自动识别和推断出异常复合联系，进而发现异常或危险性的活动。在对联系 发现方法进行设计时要考虑到不同领域数据的特点，需要全面考虑算法的效率、 有效性和正确性【2 引。 由于在传统的数据挖掘中数据被表示成特征向量的形式，这种数据表示方 式不适合多关系型数据，m o o n y 认为归纳逻辑程序( i n d u c t i v el o g i cp r o g r a m m i n g ，i l p ) 是一种用一阶谓词表示数据和规则的学习方法，这种数据表示方 法很适合于多关系型的数据。因此将归纳逻辑程序技术运用到联系发现中【1 7 j ， 提出了基于归纳逻辑程序的联系发现方法。z h a n g 等人使用相关性度量的方法 考察两个数据项的模式相似程度，并以此度量来判断两者强弱，并在此基础上 提出了基于相关性分析的联系发现方法【2 叭。这种方法主要通过联系假设、联系 产生、联系确定三个阶段来确定具有紧密联系的子图，此联系就是我们所要寻 找的潜在联系。大多的联系发现只是在海量数据中发现已知模式的对应实例。 l i n 认为联系发现不仅仅要从大量数据中识别已知的模式，更重要的是在海量 的、复杂数据中识别出未知的但具有价值的联系。针对这个问题，他提出了无 监督的联系发现方法，又被称为新颖联系发现【8 】( n o v e ll i n kd i s c o v e r y ) 。在这 种方法中，实体及实体间的关系被表示成复杂网络的形式。在这种复杂网络图 中，点表示不同类型的实体，边表示实体间的关系，不同类型的关系用不同语 义的谓词表示。并且使用稀有度来度量人们对路径的兴趣度，从而在稀有度的 基础上发现异常实体及联系。 ( 2 ) 联系发现系统设计 在联系发现的系统设计方面，主要有c a d r e 和k o j a k 等联系发现系统。 c a d r e ( c o n t i n u o u sa n a l y s i sa n dd i s c o v e r yf r o mr e l a t i o n a le v i d e n c e ) 系统主 要分为假设产生和建设评估两个阶段。系统中使用反演推理方法来为观察到的 事实给出最佳解释【2 1 1 。系统在假设产生阶段主要采用自底向上的规则触发推理 和自顶向下的反演假设相结合的方法。针对数据的不完整和稀疏性，系统采用 一种基于限制的分层模式的表示方法。k o j a k 联系发现系统【2 2 j 的目标是从大型 数据库中找出隐藏的组队及其成员，是一种从不完整和有噪声的现实证据中， 找出组织或者实体间隐藏关系的系统。k o j a k 系统结合了诸如统计聚类技术、 知识表示以及数据挖掘领域的多种分析技术。 ( 3 ) 联系发现的数据处理 由于联系发现数据的异构性以及联系性，使得联系发现数据的处理成为联 系发现中的一个难点问题。不同组织和无组织的数据、“连接灾难”问题、噪声 数据、海量的、异构的分布数据都是联系发现领域中所要解决的数据处理问题。 ( 4 ) 联系发现的可信度和联系发现方法的性能评估【2 5 】 由于在实际应用中，数据是从数据群体中随机抽样的，并没有准确地反映 整个群体的概率性质。而大多联系发现的算法是确定的，构造的假设没有概率 限定。发现的知识和蕴含的假设实际上有概率的，因此其不确定性需要度量； 并且需要考察联系发现算法的信任度问题。a d i b i 等人提出了采用引导重抽样方 法( b o o t s t r a pr e s a m p l i n gm e t h o d ) c 2 4 j 来度量这些假设的置信区间。m a f z a lu p a l 对联系发现系统的性能评估做了一定研究。他分析了传统的监督分类问题和联 系发现系统评估问题的异同点，将联系发现系统评估问题定义为一个广义范畴 的分类问题【2 4 】。在联系发现系统评估问题中，他重新定义了查准率和查全率， 并用这两个度量来衡量联系发现系统的性能。 ( 5 ) 联系发现的应用研究 联系发现己被广泛应用于如法律诉讼调查、反欺诈侦察、社会网络分析以 及电信通讯等诸多社会领域。但对联系发现应用较多的领域还是在对恐怖主义 等异常威胁性的活动发现上。z h a n g 把基于相关分析的联系发现方法( l d c a ) 方法应用于洗钱犯罪调查中。在联系假设阶段首先使用聚类方法对金融事物进 行分析，随后在联系产生阶段，引入基于分层结构的方法考察实体间的相关性： 并在假设产生阶段使用图分割的方法进行子图发现，从而达到发现异常犯罪活 动的目的。l i n 把无监督联系发现方法应用在书目检索系统中，他使用这种方法 可以很容易的发现在复杂引用关系网络中的异常联系以及与给定节点具有异常 联系的实体。 目前，国内对于联系发现的研究较少。其中南京大学对联系发现这一新的 研究领域进行了综述性地研究；华中科技大学把联系发现技术运用到了金融监 管中。 数据挖掘领域已从传统的结构数据挖掘课题扩展到w e b 数据挖掘c 1 2 j 、时间 序列数据挖掘3 1 、文本挖掘f 12 1 、网络挖掘1 4 】，( 1 5 1 等高级课题。相信随着联系发 现方法和技术的不断发展，将进一步提高人们对数据的处理能力，并且联系发 现将会应用到更多的社会领域之中，更好地为决策做支持。 1 3 论文主要内容与结构 论文的整体架构图如图3 所示。全文共分五章，各章主要内容分述如下： 第一章是绪论。说明了本论文的选题背景、意义、依据，对联系发现的国 内外研究现状进行了概述，并给出全文的整体架构图和各章的研究内容。 第二章是链接挖掘和联系发现。首先对数据挖掘的基本概念进行介绍，进 而对链接挖掘进行简单概述，介绍了链接挖掘定义、链接挖掘的任务、链接挖 掘的挑战：然后详细介绍联系发现的基本概念，包括联系发现的定义、联系发 现的特点以及联系发现的应用情况；最后介绍了目前联系发现的几种主要方法 和两个典型系统。 第三章是基于密度的无监督联系发现方法。首先简述无监督联系发现方法， 在此基础上，针对新颖节点发现子问题的缺点及不足，提出了加权距离和相对 密度的概念，采用基于加权距离的相对密度来度量对象离群程度，并求解异常 点。提出了一种基于密度的无监督联系发现方法。 第四章是联系发现方法在反洗钱犯罪中的应用。主要针对洗钱活动的日益 复杂的特点，分析了传统数据挖掘技术的局限性，进而阐述了联系发现技术的 优点，主要对联系发现方法在反洗钱犯罪中的应用进行研究。首先研究了反洗 钱问题的背景与研究意义，在此基础上把本文提出的基于密度的无监督联系发 现方法运用于反洗钱中，用于发现异常洗钱对象。本章最后提出基于联系发现 数据挖掘技术的反洗钱系统框架，并详细介绍了每个模块的具体功能。 第五章是总结与展望。首先阐述联系方法的发展以及研究状况。接着对联 系发现的研究方向和未来趋势进行介绍。最后对本文所做的工作进行了展望。 联系发现数据挖掘方法与应用 窖；l ；：巍li 基委案褰要雾萋督ll 联系发翠磊量誊钱犯罪li 总结与展望与联系发现li联系发现方法ji中的应用ll 。“2 州腓| i | | j 圉引圈国腓怍 萋蓁ll蓁蓁ll蓁l委ll蓁ll囊l蓁ll萎l l蓁ll耋 图1 3 论文组织结构图 模块功能介绍 数据表示问题分析 第二章链接挖掘与联系发现 近年来，随着互联网技术的广泛应用，电子商务、网上银行等领域有了迅 速地发展，与此同时在这些领域中逐渐出现了一些更为复杂的数据形式。这些 数据具有异构的、多关系和半结构化的特征，利用传统的数据挖掘模式已经无 法对具有这类特征的数据进行分析，亟待使用更为有效的数据挖掘方法来解决 这类问题。链接挖掘和联系发现就是一类可以解决这种问题的新方法。本章首 先简单介绍了数据挖掘的定义、发展历史以及常用技术；接着对链接挖掘进行 了概述，介绍了链接挖掘的定义、主要任务以及挑战，然后给出了联系发现的 定义，分析了联系发现的特点以及联系发现的应用情况，最后介绍了联系发现 中常用的几种方法以及两个典型的系统。 2 1 数据挖掘 2 1 1 数据挖掘定义 数据挖掘简单地说就是从大量数据中提取或“挖掘”知识，但从不同的角 度有着不同的定义，以下分别从商业和技术角度对数据挖掘进行定义： ( 1 ) 商业角度定义 数据挖掘的主要特点是对商业数据库中的大量业务数据进行抽取、转换、 分析等其他模型化处理，从中提取辅助商业决策的关键性知识。它是一种新的 商业信息处理技术。 数据挖掘简单地说即是一种深层次的数据分析方法，数据分析虽已有多年 历史，但过去的主要目的仅限于科学研究，且当时的计算能力有限，对于大数 据量的复杂数据进行分析的方法具有很大的限制。如今收集数据是由于纯机会 的商业运作而产生，不再仅仅为了分析，并且数据分析更主要是为商业决策提 供真正有价值的信息，进而获得更高利润。但所有企业对于数据的处理均面临 同一个问题：企业具有海量的数据量，然而其中真正有价值的信息却很少，因 此需要对大量的数据进行深层次分析，获得有利于商业运作、提高竞争力的知 识，这一过程如同矿石中淘金一般，数据挖掘因而得名。 因此，从商业的角度，我们可以把数据挖掘表述为：根据企业的既定业务 目标，对大量的企业数据进行处理和分析，揭示隐藏的、未知的或验证已知的 规律性，并进一步将其模型化的先进有效的方法【3 引。 ( 2 ) 技术角度定义 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用 数据中，提取隐含在其中的、事先不为人知的，但又是潜在有用的信息和知识 的过程【lj 。此定义具有以下几层含义：第一，数据源具有真实的、大量的、含 噪声的特点；第二，发现的知识要可接受、可理解、可运用的，并且应是所需 要的知识；第三，所发现的知识并不要求具有普遍性，仅支持特定的问题即可。 知识的表现形式很多，从广义上理解，如数据、信息等，但一般我们更倾 向于把知识看作是概念、规则、模式、规律和约束等【lj 。原始数据的形式多样， 如关系数据库中的结构化的数据；也可以是如文本、图形和图像数据似的半结 构化的数据；甚至可以是分布在网络上的异构型数据。发现知识的方法可以是 演绎的，也可以是归纳的，可以是数学的，也可以是非数学的；发现的知识的 用途很多，如被用于信息管理、决策支持、查询优化和过程控制，也可以用于 数据自身的维护。综上所述，数据挖掘是一门把对数据的应用从低层次的简单 查询，提升到从数据中挖掘知识，提供决策支持的交叉学科。 2 1 2 数据挖掘研究现状 1 9 8 9 年举行的第十一届国际联合人工智能学术会议上首次出现从数据库 中发现知识( k d d ) 的概念。到目前为止，由美国人工智能协会主办的k d d 国际 研讨会已召开多次，规模和研究重点都有了重要的变化，规模由原来的专题讨 论会发展到国际学术大会，研究重点也逐渐从单纯的发现方法研究转向系统应 用研究，并且对于数据挖掘的研究更注重多种学科之间的相互渗透、多种发现 策略和技术的集成等策略。随着数据挖掘研究的不断深入，数据挖掘被列入多 个专刊的专题内容，1 9 9 3 年i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率 先出版了k d d 技术专刊。接着计算机网络、并行计算、信息工程等其他领域的 国际学会、学刊也把数据挖掘和知识发现( d m k d ) 列为专题和专刊讨论。随着 网络技术和高级数据库技术的不断发展，各种复杂性的数据爆炸性地增长，传 统的针对简单和结构化的数据挖掘方法已经具有很大的局限，因此数据挖掘面 j 临一些日趋重要的高级课题，如流数据挖掘、链接挖掘、联系发现、图挖掘、 w e b 挖掘等。 数据挖掘技术的不断发展，主要是由于应用价值的推动。因此目前数据挖 掘技术已经被广泛应用于金融、零售、电信、生物、入侵检测等领域，同时也 出现了很多商业化的数据挖掘系统。数据挖掘在网络中的应用目前也已经成为 一个热点问题。如在电子商务方面，对服务器以及浏览器端的日志记录数据进 行挖掘，从中发现隐藏于数据中的模式信息，从而了解系统的访问模式以及用 户的行为模式，做出预测性分析；在搜索引擎的方面，可以对网页信息采用链 接挖掘的方法，对网页的内容和li n k 进行分析，实现网络信息的分类浏览与检 索，从而改善检索效果。 与国外相比，国内对数据挖掘的研究稍晚，但也已具有一定的研究成果。 1 9 9 3 年国家自然科学基金首次支持对该领域的研究项目。至今，国内的许多科 研单位和高校竞相开展数据挖掘的基础理论及其应用研究。如北京大学对数据 立方体代数开展研究，北京系统工程研究所集中子对模糊方法在知识发现中的 应用研究，此外，复旦大学、华中理工大学、浙江大学、中科院数学研究所、 中国科技大学、吉林大学等单位开展了对关联规则算法的优化和改造研究；南 京大学、四川联合大学和上海交通大学等单位的研究重点主要集中在非结构化 数据的知识发现以及w e b 数据挖掘上。 输入 ： 图2 1 i i 膏古层i 输出 一个神经元网络 2 1 3 数据挖掘的主要方法 ( 1 ) 人工神经网络 人工神经网络是模拟人类的形象直觉思维，是在生物神经网络研究的基础 上，根据生物神经元和神经网络的特点，通过简化、归纳、提炼总结出来的一 类并行处理网络。神经网络是解决复杂问题的一种比较有效的方法，对于具有 上百个参数的问题神经网络的优点体现的更甚，常用于分类和回归这两大类问 题【33 1 。 高负债 高风险高风险 低风险 图2 2 一颗简单的决策树 神经网络在结构上可划分为输入层、输出层和隐含层三个层次，如图2 1 所示。输入层的每个节点对应一个预测变量，输出层的节点表示目标变量，可 有多个。输入层和输出层之间便是隐含层，隐含层的层数和每层节点的个数决 定了神经网络的复杂度。 神经网络具有易于在并行计算机上实现的优点，因此可将节点分配到不同 的c p u 上并行计算。 在神经网络中除了输入层的节点外的所有节点都与其前的很多节点连接在 一起，每个连接对应一个权重眠，此节点的值通过对应所有输入节点的值与 对应连接权重乘积的和作为一个函数的输入而得到，该函数称为活动函数或挤 压函数。 ( 2 ) 决策树 决策树提供一种规则方法，可形象地展示出在何种条件下会得到何种值的 情况【3 3 1 。例如在贷款申请中对申请的风险大小做出判断，为解决这个问题而建 立的一棵决策树如下图2 2 ，由图可见决策树是由决策节点、分支和叶子基本 组成部分组成的。 决策树中最上面的节点是根节点，是整个决策树的开始。每个节点子节点 的个数与决策树所使用的算法有关。每个分支或是一个新的决策节点，或是树 的结尾，称为叶子。在决策树从上到下遍历的过程中，对问题的不同回答导致 不同的分支，最后会到达一个叶子节点。此过程即为利用决策树进行分类的过 程。 决策树可用于分析数据、预测，是数据挖掘中的一种常用技术，常用算法 有i d 3 、c h a i d 、c a r t 、q u e s t 、c 4 5 和c 5 0 等。 ( 3 ) 聚类法 聚类算法把具有相似特征的数据归于一类。通过聚类，在同一类类集中的 数据具有相似的变量值，不同类之间数据的变量值不具有相似性。区分不同的 类是属于数据挖掘过程的一部分，这些类是通过聚类算法采用全自动方式获得 的，而不是事先定义好的。 ( 4 ) 其他技术方法 机器学习方法：从特殊的训练样本中归纳出通用函数。这种方法主要运 用于分类、聚类和预测中。 机器学习可以分为基于范例学习、归纳学习、遗传算法等。遗传算法是基 于进化理论，并采用遗传结合、遗传变异、以及自然选择等设计方法的优化技 术。 近邻算法：通过k 个与选定记录最相近的记录的组合来判别新纪录，该 算法主要运用于偏差分析、聚类分析等。 规则推导：从统计意义上对数据中的“i f t h e n ”规则进行寻找和推导。 很多专门的分析工具中都己运用了上述技术，并且发展了近十年，但数据 量的处理还相对较小。随着技术的不断成熟，在很多大型的工业标准的数据仓 库和联机分析系统中也已集成了上述多种技术，这将推动数据挖掘技术在海量、 复杂数据处理中的应用。 2 2 链接挖掘 链接挖掘在社会网络、联系发现、超文本和w e b 挖掘、图挖掘、关系学 习和归纳逻辑规划中研究的融合。它通过考虑联系( 对象间的关系) ，试图挖掘 出更多的有用信息，它的挖掘过程表现了描述性和预测性建模。链接挖掘的任 务包括基于链接的对象排序、基于链接的对象分类、对象聚类、对象鉴定、链 接预测、子图发现、图分类、图生成模型等。与传统数据挖掘方法相比，对象 间的联系带来了链接挖掘这一新任务的同时，也带来了许多的挑战。 2 2 1 链接挖掘定义 由于互联网和社会网络等领域中的数据不断增多，逐渐涌现出了许多大规 模的异构化联系数据，这些数据对象往往属于不同的类型，并且对象之间又存 在着复杂的联系。如果用网络或者图来表示这种数据，那么反映到图中的就是 一个包含不同类型的节点以及不同类型的边的复杂网络。一般地，传统的数据 挖掘方法( 例如，关联规则挖掘、购物篮、聚类分析等) 是对单一关系的，具有 相互独立的实例进行分析，得到某种模型。该模型与利用经典的统计推断方法 对具有独立同分布( i n d e p e n d e n t ，i d e n t i c a l l y ，d i s t r i b u t e d ，i i d ) 特性的样 本数据进行分析所建立的模型是相吻合的。但是如果依然使用这些经典方法对 上述异构化的并且具有复杂联系的数据进行分析，就会忽略了复杂网络中的链 接信息，得到一些不切实际的结论，因此我们必须要关注这些数据之间潜在的 各种联系。链接挖掘就是针对数据之间的联系，挖掘其中可能被利用的知识信 息，从而提高数据挖掘的可靠性，它强调了实体之间的相互作用对数据挖掘结 果的影响，并扩展了传统数据挖掘中的分类、聚类等任务【l 引。 近年来已经有很多著名的国际会议在关注链接挖掘的研究。其中，1 9 9 8 年 的a a a i ( a r t i f ic i a li n t e l li g e n c ea n