（计算机软件与理论专业论文）基于矩阵的关联规则挖掘算法研究.pdf

婀i 柯上学颀 p 诊殳摘璎 基于矩阵的关联规则挖掘算法研究 计算机软件与理论专业硕士研究生李娟 指导教师张明义教授 摘要 数据挖掘是致力丁= 数据分析和理解，揭示数据内部蕴涵知识的技术，成为未来信息技术 麻h 的重要目标之一。关联规则是数据挖掘的一个重要研究分支，主要用于描述数据库中数 据项之间的潜在联系，有着极其重要的应用价值。 自r a k e s h a g r a w a l 等人1 9 9 3 年首次提出了关联规则挖掘这个研究课题以来，研究人员已 经提出了多种挖掘关联规则的算法：a l m o r i 算法、f p - g r o w t h 算法，以及基于这两种算法的多 种改进方法，但这些算法都是把数据库中各个项目按平等一致的方式加以处理的。而在实际 戍用中，各个项目在使用者心日中的重要程度往往不同，一个自然的想法就是为每个项目赋 予不同的权值，以区分它们的重要程度。鉴于此，本文对加权关联规则挖掘算法进行了研究。 另外，在关联规则的实际挖掘过程中，用户往往需要对最小支持度和晟小置信度这两个闽值 进行不断调整来寻找真正感兴趣的规则：而且数据库中的数据是不断进行添加、修改和删除 的，这是一个动态的交互过程。因此，关联规则的更新问题也很值得研究。 本文首先概述了数据挖掘的任务、方法、应用等现状，介绍了关联规则分析的基本概念、 分类及一些常见的算法思想，并着重讨论了些经典的关联规则和加权关联规则挖掘算法， 分析了算法存在的问题。在此基础上，提出了新的加权关联规则模型，并给出了挖掘加权频 繁项集的矩阵位串算法( m a t r i xb i ts t r i n ga l g o r i t h m ，简记为a m b ) 。该算法创新之处在于引 入矩阵思想，通过一次扫描交易数据库将其转化为0 1 矩阵，并在判断某个项集是否加权频繁 项集时采h j 位串做逻辑“与”运算方法，而免去了对原始交易数据库的多次扫描判断。理论分析 和实验均表明，a m b 算法比已有加权关联规则挖掘算法w m a r 的效率更高。在分析已有增 晕更新算法的基础上，给出了改进的增鼍式更新算法m f u p ，并通过实验验证了本算法的敛率。 在本文的最后对全文内容进行总结，并展望了进一步的研究方向。 关键词：数据挖掘关联规则加权关联规则频繁项集增量更新 两南j 、擘蛳f 。f j 论上a b s t r a c t r e s e a r c ho i la l g o r i t h mo f m i n i n g a s s o c i a t i o nr u l e sb a s e do nm a t r i x 。 s p e c i a l i t y ：c o m p u t e rs o f t w a r ea n dt h e o r y r e s e a r c hd i r e c t i o n ：l o g i cp r o g r a m m i n ga n d i n t e l l i g e n ts o f t w a r e author：lij u a n s u p e r v i s o r ：p r o f z h a n gm i n g y i a b s t r a c t d a t am i n i n gi sat e c h n i q u et h a ta i m st oa n a l y z ea n du n d e r s t a n dl a r g es o u r c ed a t aa n dr e v e a l k n o w l e d g eh i d d e ni nt h ed a t a i th a sb e e nv i e w e d a ni m p o r t a n te v o l u t i o nf o ri n f o r m a t i o n p r o c e s s i n g a s s o c i a t i o nr o l ei so n eo ft h ei m p o r t a n tr e s e a r c hb r a n c h e so fd a t am i n i n g ，i su s e dt o d e s c r i b et h ep o t e n t i a lc o r r e l a t i o n si nl a r g eq u a n t i t yo fd a t a ，a n dh a st h em o s ts i g n i f i c a n ta p p l i c a t i o n i nf u t u r e s i n c er a k e s ha g r a w a lc ta 1 p r o p o s e dt h e s u b j e e to fm i n i n ga s s o c i a t i o nr u l e si n1 9 9 3 r e s e a r c h e r sh a v ep u tf o r w a r dl o t so f a l g o r i t h m s ，s u c ha sa p r i o r i ，f p g r o w t h ，a n dv a r i e t yo f i m p r o v e d a l g o r i t h mb a s e do nt h e s et w oa l g o r i t h m s m o s to ft h e s ea l g o r i t h m st r e a te a c hi t e ma su n i f o r m i t y h o w e v e r , i ti sn o tt r u ei nt h er e a lw o r l dd a t a b a s e s ，i nw h i c hd i f f e r e n ti t e m su s u a l l yh a v ed i f f e r e n t i m p o r t a n c e s an a t u r a li d e ai st og i v ee a c hi t e md i f f e r e n tw e i g h t st od i s t i n g u i s ht h e i ri m p o r t a n c e s o ， t h ea l g o r i t h mo f m i n i n gw e i g h t e da s s o c i a t i o nm l e si ss t u d i e di nt h i st h e s i s i na d d i t i o n ，i nt h ea c t u a l e x c a v a t i o np r o c e s so fa s s o c i a t i o nr o l e s ，u s e r so f t e nn e e dt om o d i f yt h ev a l u eo fm i n i m u ms u p p o r t a n dm i n i m u mc o n f i d e n c et of i n dr e a li n t e r e s t e dr u l e s ；a n dt h ed a t aj l lt h ed a t a b a s ei sc o n s t a n t l yb e i n g a d d e d ，m o d i f i e do rd e l e t e d , t h i si sad y n a m i ci n t e r a c t i v ep r o c e s s t h e r e f o r e ，t h eu p d a t eo f a s s o c i a t i o nr o l ei sw o r t h yt os t u d y i nt h eb e g i n n i n go ft h i st h e s i ss i m i l eb a s i cp r i n c i p a lt h e m e s ，a p p r o a c h e sa n dp r o b l e m so fd a t a m i n i n ga r ei n t r o d u c e d ，f o l l o w e db yc o n c e p t i o n s ，c a t e g o r i e s a n dg e n e r a lt h o u g h t so fp o p u l a r a l g o r i t h m sa b o u ta s s o c i a t i o nr o l e af e wc l a s s i ca s s o c i a t i o nm l ea n dw e i g h t e da s s o c i a t i o nr u l e e x t r a c t i n ga l g o r i t h m sa r ed e e p l yd i s c u s s e d ，a n da n a l y z e dt h ep r o b l e m se x i s t i n gi nt h ea l g o r i t h m s o n t h i sb a s i s ，an e ww e i g h t e da s s o c i a t i o nr o l e sm o d e la n da ne f f e c t i v ea l g o r i t h ma m bt oh a n d l et h e p r o b l e m o f m i n i n gw e i g h t e df r e q u e n ti t e m s e t sa r ep r o p o s e di nt h i st h e s i s t h en o v e la l g o r i t h mb a s e d o nm a t r i xf o rf m d i n gf r e q u e n ti t e m s e t s i to n l yn e e d st os c a nt h et r a n s a c t i o nd a t a b a s eo n c et oc o n v e r t u 西南，、 6 f 卜学忙诊逻 a b s t r a c t i ti n t oo - 1m a t r i xa n dl e tb i ts t r i n g sd ol o g i c a l “a n d ”o p e r a t i o nt oj u d g ew h e t h e rap a r t i c u l a ri t e m s e t i sf r e q u e n t i tc a ng e tr i do fs c a n n i n gt h eo r i g i n a lt r a 唧s a c t i o nd a t a b a s er e p e a t e d l y t h e o r e t i c a l a n a l y s j sa n de x p e r i m e n t a lr e s u l t s i n d i c a t et h a tt h ei l e wa m ba l g o r i t h mi sm o r ee f f e c t i v ea n d e f f i c i e n t b a s e do nt h ea n a l y s i so fe x i s t e di n c r e m e n t a lu p d a t ea l g o r i t h m ，a l li m p r o v e di n c r e m e n t a l u p d a t ea l g o r i t h mm f u pi sp r o p o s e d e x p e r i m e n ti sc a r r i e do u tt oc o n f i r mt h ee f f i c i e n c yo ft h e a l g o r i t h mm f u e i nt h el a s tp a r to ft h et h e s i s ，t h ec o n c l u s i o na n dp r o s p e c to fr e s e a r c hd i r e c t i o ni s g i v 饥 k e y w o r d s ：d a t am i n i n g ，a s s o c i a t i o nr u l e , w e i g h t e d a s s o c i a t i o nr u l e , f r e q u e n ti t e m s e li n c r e m e n t a lu p d a t e l i i 独创性声明 学位论文题目：基王缝睦盟羞毯拯则控担簋造盟窒 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及l 阪得的研究成果。据我所知，除了文中特，j l j d l i 以标注和致谢的地 力夕h ，论文c i 不包含其他人已经发表或撰写过的研究成果，也不包含 为获得两南大学或其他教育机构的学位或证书而使用过的材料。与我 【i + j ，l 作的同志对本形f 究所做的任何贡献均已在论文中作了明确的 c _ 1 6 i 则并表示谢意。 学位论文作者： 痞询 签字日期：州年 p 月矽日 学位论文版权使用授权书 本：学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：a 不保密， 口保密期限至年月止) 。 学位论文作者签名：套响 签字日期： 岬年印月加日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期： 邮编 西南上学衙卜学伊论上第l 审弓l 苫 第1 章引言 数据挖掘( d a t a m i n i n g ) 是一个多学科领域，它融合了数据库技术、人工智能、 机器学习、神经网络、统计学、模式识别、知识库系统、知识获取、信息检索、 高性能计算和数据可视化等最新技术的研究成果。经过几十年的研究，数据挖掘 已经形成了清晰的概念和方法，并且正向着更深入的方向发展。本章主要介绍了 课题研究背景及意义，并给出了全文的结构安排。 1 1 课题研究背景及意义 近年来商业条码的推广、企业和政府事务的管理以及数据采集工具的发展， 产生了大规模的数据，在商业管理、政府部门、国防建设、科学和工业数据处理 等领域中都应用了数以百万计的数据库。超大型数据库虽然是一个巨大资源，但 是寻找隐藏在其中的有用信息则无异于大海捞针，人们感到“数据过剩”而“知识贫 乏”。随着数据和数据库的急剧增长，现有信息管理系统中的数据分析工具已无法 适应新的需求。因此，面对“数据过剩但知识贫乏”的挑战，数据挖掘技术应运而生， 并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘可以从大型数据库中的大量原始数据中提取人们感兴趣的、隐含的、 尚未被发现的有用的信息和知识。数据挖掘是一个融合数据库、机器学习、数理 统计、可视化和信息科学技术为一体的新兴的交叉学科领域【1 】。它的发展不仅可以 为商务管理、科学研究、查询优化、过程控制等领域提供决策支持，而且为相关 的计算机学科注入新的活力，从而推进计算机科学向纵深方向发展。毫无疑问， 对数据挖掘的深入研究在计算机理论和应用两个方面都具有十分重大的意义。在 数据挖掘所能发现出的众多知识种类中1 2 】，例如，关联规j j ( a s s o c i a t i o nr u l e ) 的挖 掘、分类( c l a s s i f i c a t i o n ) 、聚类( c l u s t e r i n g ) 、趋势( t r e n d ) 分析、偏差( d e v i a t i o n ) 分析、 模式( p a t e m ) 分析等，关联规则的挖掘是目前数据挖掘领域中研究最为广泛的课题 之一。 关联规则是描述数据库中数据项之间潜在关系的规则。关联规则挖掘的一般 对象是事务数据库，起初主要应用于零售业，比如超级市场的销售管理。条形码 技术的发展使得数据的收集变得更容易更完整，从而存储了大量交易资料，关联 规则就是通过辨别这些交易资料，来分析顾客的购买模式，根据关联规则提供的 信息可以用做商品销售目录设计、商品布置、针对性的市场营销等。虽然关联规 则是伴随着零售业的飞速发展而产生的一种需求，但它的应用决不仅是在零售业 上，还体现在银行业、保险业、经纪业和安全交易、计算机硬件和软件、医药、 交通、电信等多个领域，所以展开对关联规则的研究具有重大意义。 两南j f l l ；ll # 位论之 第1 帚r j i 二- 1 2 论文的研究内容 1 9 9 3 年a g r a w a lr 等人首先提出了挖掘顾客交易数据库中项集间的关联规则 问题1 3 i ，并于1 9 9 4 年提出了挖掘关联规则的经典a p r i o r i 算法【4 i 。后来有不少学者 对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有a p r i o r i 算法进 行优化，如采用基于散列【5 1 、划分、随机采样7 1 、事务i 丘缩1 4 1 1 8 1 1 们、动态项集计数 1 0 1 等的优化方法，以提高算法挖掘规则的效率。有的学者为了避免频繁项集产生 方法的些缺陷，提出了独立于a p r i o r i 算法的挖掘关联规则的新方法，如j i a w e i h a n 等人提出的不产生候选频繁项集的f p g r o w t h 方法l 。但这些算法都是把数 据库中各个项目按平等一致的方式加以处理的。 但在实际应用中，用户对每个项目的看重程度往往是不一样的，例如在一个 大型商场中，从决策者角度出发，他们一般更倾向于优先考虑利润较高的项目， 而忽略利润较低的项目。特别是当那些利润率较高的项日出现不频繁时，用普通 的挖掘算法结果可能只是挖掘到一些用户认为“近乎自然”的“平凡”的规则，而与用 户最看重、最关心项目相关的规则却挖掘不到。针对这个问题，我们可以在关联 规则中引入权重的概念，解决项目重要程度不一致的问题，由此产生的关联规则 称为“加权关联规则”。研究人员也已经提出不少挖掘加权关联规则的算法，例如文 献 1 2 】 1 3 【1 4 等，算法的核心思想都是寻找加权频繁项集，然后根据频繁项集产 生加权关联规则。 挖掘关联规则的挑战性在于数据量巨大，算法的效率是关键，因此有必要研 究出占用内存小、i ，0 操作少、执行速度快的高效算法。为此，本文提出了一种基 于矩阵和位串的加权关联规则挖掘算法( m a t r i xb i ts t r i n ga l g o r i t h m ，简记为 a m b ) ，可以较好地解决这一问题。该算法创新之处在于引入矩阵思想，通过一 次扫描交易数据库将其转化为0 - 1 矩阵，并在判断某个项集是否加权频繁项集时采 用位串做逻辑“与”运算方法，而免去了对原始交易数据库的多次扫描判断。理论分 析和实验均表明，a m b 算法比已有加权关联规则挖掘算法w m a r 的效率更高。 同时，在关联规则的实际挖掘过程中，用户往往需要对最小支持度和最小置 信度这两个阂值进行不断调整来寻找真正感兴趣的规则；而且数据库中的数据是 不断进行添加、修改和删除的，这是一个动态的交互过程。因此，怎样利用已有 的结果挖掘出新的频繁项集也是一个值得研究的问题。本文在分析已有增量更新 算法的基础上，给出了改进的增量更新算法m f u p ，实验表明，m f u p 算法比原 有f u p 算法效率更高，具有较高的实用价值。 1 3 论文的结构安排 本文的结构安排如下： 第l 章： 要介绍了论文研究的背景和意义，论文的研究内容及结构安排。 第2 章：介绍数据挖掘的一般性理论，包括概念、任务、对象、方法、应用 发展以及关联规则和加权关联规则。 第3 章：介绍了关联规则挖掘算法，包括概念、分类、挖掘步骤，详细分析 了关联规则挖掘的经典a 嘶o r i 算法及其他学者对a p r i o r i 算法的改进算法，总结了 算法存在的问题。 第4 章：介绍了加权关联规则的相关概念，分析了已有算法的不足，提出新 的加权关联规则模型、科学的设定项目权值的方法及基于矩阵和位串的加权关联 规则挖掘算法a m b ，理论上分析了该算法的时间复杂度，并通过实验比较了改进 前后的效率。 第5 章：介绍了关联规则增量更新的概念、分类，分析了已有增量更新算法 的基本思想，提出了基于矩阵的改进型增量更新算法m f u p ，实验表明该算法比 经典f l i p 算法更高效。 第6 章：总结了本文的重要工作并展望了未来的研究方向。 两南夫学研卜掌位论上 第2 帝数据挖拇髓述 2 1 数据挖掘的概念 第2 章数据挖掘概述 数据挖掘起源于从数据库中发现知识( 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 ) ，它首次出现在1 9 8 9 年8 月在底特律举行的第十一届国际联合人工智能 学术会议上。为了统一认识，在1 9 9 6 年出版的总结该领域进展的权威论文集知 识发现与数据进展【b l 中，f a y y d ，p i a t e t s k y - s h a p i r oa n ds m y t h 给出了k d d 和数 据挖掘的最新定义，将二者加以区分。 k d d 的定义为：k d d 是从数据中辨别有效的、新颖的、潜在有用的、最终可 理解的模式的过程。( 原文为：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 si st h en o n t r i v i a l p r o c e s so fi d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l e p a t t e r n si nd a t a ) 数据挖掘的定义为：数据挖掘是k d d 中通过特定的算法在可接受的计算效率 限制内生成特定模式的一个步骤。( 原文为：d a t a m i n i n g i s as t e p i n t h e k d dp r o c e s s t h a t ，u n d e ra c c e p t a b l ec o m p u t a t i o n a le f f i c i e n c yl i m i t a t i o n s ，e n u m e r a t e ss t r u c t u r e s ( p a t t e r n so rm o d e l s ) o v e r d a t a ) 由此可见，整个k d d 过程是一个以知识使用者为中心、人机交互的探索过程。 数据挖掘只是数据库中知识发现的一个步骤，但又是最重要的一步。因此，往往 可以不加区别地使用k d d 和数据挖掘。一般在研究领域被称作数据库中的知识发 现，而在工程领域则称为数据挖掘。 目前，数据挖掘还未有一致的定义，一种较为公认的定义是g p i a t e t s k ys h a p i r o 等人提出的：数据挖掘是从静态的存储于大型数据库中的结构化数据中提取人们 感兴趣的数据模式、内在联系、规律、发展趋势等知识，这些知识是隐含的、事 先不知的、潜在有用的信息，提取的知识一般可以表示为概念、规则、规律、模 式等形式。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的； 发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用。 2 2 数据挖掘系统 从知识发现的角度，可以把数据挖掘视为数据库中知识发现过程的一个基本 步骤。一般知识发现的过程由以下步骤组成： ( 1 ) 数据清理：消除噪声或不一致的数据； ( 2 ) 数据集成：多种数据源可以组合在一起； 4 两南，：学彤| 仆 z孔2 争致搬挖押碍述 ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据： ( 4 ) 数据变换：将数据转换成一个分析模型。这个分析模掣足针对挖掘算法 建立的。建蕾一个真正适合挖掘算法的分析模型是数据挖掘成功的关键； ( 5 ) 数据挖掘：基本步骤，使用智能方法提取数掘模式； ( 6 ) 模式评估：根据某种兴趣度量，识别表示知识的真正有趣的模式； ( 7 ) 知识表示：使用可视化和知识表现技术，向用户提供挖掘知识； 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户，或作为新 的知识存放在知识库中。从数据挖掘的广义观点来看，数据挖掘足从存放在数据 库、数据仓库、或其他信息库中的大量数据中挖掘有趣知识的过程。 基于这种观点，典型的数据挖掘系统具有以下主要成分( 见图2 1 ) ： 图2 - 1 典型的数据挖掘系统结构 ( 1 ) 数据库、数据仓库或其他信息库：这是一个或者一组数据库、数据仓库、 册1 罚，+ 坝i 。掌位论z第2 币剪帮皑帮楫瑾 电子表格或其他类型的信息库。可以在数据上进行数掘清理和集成。 ( 2 ) 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓 库服务器负责提取相关数据。 ( 3 ) 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这 种知识可能包括概念分层，用于将属性或属性值组成不同的抽象层。用户确信方 面的知识也可以包含在内。可以使用这种知识，根据非期望性评估模式的兴趣度。 领域知识的其他例子有兴趣度限制或阈值和元数据( 例如，描述来自多个异种数 据源的数据) 。 ( 4 ) 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成， 用于特征化、关联、分类、聚类分析以及演变和偏差分析。 ( 5 ) 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚焦在有趣的模式上。它可能使用兴趣度阈值过滤发现的模式。模式 评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。 对于有效的数据挖掘，建议尽可能深地将模式评估推进到挖掘过程之中，以便将 搜索限制在有兴趣的模式上。 ( 6 ) 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系 统交互，制定数据挖掘查询任务，提供信息、帮助搜索聚焦，根据数据挖掘中的 中间结果进行探索式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓库 模式或数据结构，评估挖掘的模式以不同的形式对模式可视化。 2 3 数据挖掘的任务 数据挖掘的任务可分为【1 6 j ：关联分析，序列模式，聚类，分类，偏差检测， 预测。 ( 1 ) 关联分析 关联分析用来发现关联规则，这些规则展示属性一值频繁地在给定数据集中 一起出现的条件。它是从数据库中发现知识( k d d ) 的一类重要方法。关联规则 挖掘是由r a k e s ha g r a w a l 等人首先提出的。两个或两个以上变量的取值之间存在 某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、可被发现的 知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是找出数据库 中隐藏的关联网。一般用支持度和可信度两个闽值来度量关联规则的相关性，还 不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。关联分析广泛 用于购物篮或事务数据分析。 ( 2 ) 序列模式 6 阳雨尺掌鲫f 字1 ，舻卫弭2 争翦舞讫拇僻述 序列模式分析和关联分析相似，其目的也是为了挖掘数据之| 玎j 的联系，但序 列模式分析的侧重点在于分析数据问的静后序列关系。它能发现数扼库中形如“在 某一段时间内，顾客购买商品a ，接着购买商品b ，而后购买商品c ，即序列 a b c 出现的频度较高”之类的知识，序列模式分析描述的j 口j 题是：在给定交易 序列数据库中，每个序列是按照交易时间排列的一组交易集，挖掘序列函数作用 在这个交易序列数据库上，返回该数据库中出现的高频序列。在进行序列模式分 析时，同样也需要由用户输入最小置信度c 和最小支持度s 。 ( 3 ) 聚类 聚类足把整个数据库分成不同的组群。它的目的是要群与群之间差别很明显， 而同一个群内的数据尽量相似。划分出来的群组具有一定的意义，我们称为类。 在同一类别中，个体之间的距离较小，而不同类别的个体之f o j 的距离较大。聚类 方法包括统计分析方法、机器学习方法和神经网络方法等。 ( 4 ) 分类 数据挖掘应用最多的任务要属分类。分类找出描述并区分数据类或概念的模 型，以便能够使用模型预测类标记未知的对象类。一般用规则或决策树模式来表 示类数掘的整体信息，即该类的内涵描述。该模式能把数据库中的元组映射到给 定类别中的某一个。 目前影响较大的分类方法有：判定树归纳的i d 3 ，c 4 5 ；基于后验概率贝叶斯 定理的朴素贝叶斯分类和贝叶斯信念网络；神经网络的后向传播算法；基于要求 的最近相邻分类法等算法。我们用预测的准确率、计算速度、强壮性、可伸缩性 和可解释性来评估分类算法的好坏。 ( 5 ) 偏差检测 所谓偏差检测就是在数据分析中发现有很多异常情况存在于数据库中，我们 根据这种异常情况可以获得很多有用的信息。比如利用偏差检测可以发现信用卡 的欺骗。通过检测一个给定账号与正常的付费相比，以付款数额特别大来发现信 用卡欺骗性使用。偏差检测可以使用统计试验检测。 ( 6 ) 预测 预测可以利用历史数据或数据分布依据一定的模型计算出数值数据或识别出 未来分布趋势等。预测建模可以分为用于分类的预测和用于回归的预测。 2 4 数据挖掘的对象 数据挖掘的对象主要是关系数据库。随着技术的发展，空问数据库、时态数 据库、文本数据库、多媒体数据库、w e b 逐渐成为数据挖掘的研究对象。文字、 7 两南j ：学坝f 学f ? 论文第2 帚致撑挖啊摒球 音频、图像、视频等多媒体数据已逐渐成为信息领域的重要表现形式。音频、视 频的数据量很大，要从千万计的多媒体数据中找出需要的数掘和信息是很困难的。 目前，对多媒体数据的处理只能是存取、编辑、集成、快进快退等基本操作，对 多媒体信息的检索仅靠文件标识、关键字等进行检索，局限性很大。目i j 兴起的 基于内容的多媒体检索，通过实例的查询方式，检索相似图像、音频、视频信息， 已成为研究的热点。基于内容的音频、视频信息的聚类、分类、相似查询等数据 挖掘技术正在兴起。 2 5 数据挖掘的方法 数据挖掘的方法主要有【1 7 】：( 1 ) 机器学习方法：其目的是通过观察和实验发现 经验规律。可细分为：归纳学习方法( 决策树、规则归纳等) 、基于范例学习、遗 传算法和贝叶斯信念网络等；( 2 ) 统计方法：对关系表中各属性进行统计分析，找 出它们之间存在的关系。可细分为：回归分析( 多元回归、自回归等) 、判别分析 ( 贝叶斯判别、费歇尔判别、非参数判别) 、聚类分析( 系统聚类、动态聚类等) 、 探索性分析( 主元分析法、相关分析法等) 、模糊集、粗糙集等；( 3 ) 神经网络方法： 利用大量的简单计算单元( 即神经元) 连成网络来实现大规模并行计算，通过学 习改变神经元之间的连接强度。可细分为：前向神经网络( b p 算法等) 、自组织 神经网络( 自组织特征映射、竞争学习等) 等；( 4 ) 数据库方法：主要是多维堆数 据分析或o l a p 方法，另外还有面向属性的归纳方法；( 5 ) 可视化技术：用比较巧 妙的方法在二维空间展示n 维空间数据，把数据、信息、知识转化为可视的表示 形式的过程，使用户能交互式地分析数据关系。可视化技术将人的观察能力和智 能融入数据挖掘系统，极大地改善了数据挖掘的速度和深度。 几种常用的数据挖掘方法介绍如下： ( 1 ) 决策树方法 利用信息论中的信息增益寻找数据库中具有最大信息量的字段，建立决策树 的一个结点，再根据字段的不同取值建立树的分枝。在每个分枝子集中重复建立 树的下层结点和分枝的过程，即可建立决策树。接下来还要对决策树进行剪枝处 理，然后把决策树转化为规则，利用这些规则可以对新事例进行分类。典型的决 策树方法有分类回归树( 如c a r t 、i d 3 、c 4 5 等【1 8 2 0 1 ) ，其中最有影响和最早的 决策树方法是q u i u l a n 提出的i d 3 方法【1 8 】，它对越大的数据库效果越好。后人在 i d 3 方法的基础上又发展了各种决策树方法。 ( 2 ) 神经网络方法 对非线性数据具有快速的建模能力，仿照生理神经网络结构的非线性预测模 两雨人7 声蛳卜7 声1 芝沦艾弭2 辛致蹙帮峨违 型，通过学习进行模式识别。其开采过程基本上足将数据聚类，然后分类计算权 值，适合非线性数据和含噪声数据，所以在市场数扼库的分析和建模方面应用广 泛1 2 1 】。 ( 3 ) 遗传算法 遗传算法模仿人工选择培育良种的思想，从一个初始规则集合( 知识基因) 开始，逐步地通过交换对象成员( 杂交、基因突变) 产生群体( 繁殖) ，评价并择 优复制( 适者生存、不适者淘汰) ，迭代积累计算，最后得到优化的知识集1 2 2 1 。 ( 4 ) 粗糙集方法 用于数据简化( 例如删除与任务无关的记录或字段) 、数据的意义评估、对象 相似或差异性分析、因果关系及范式挖掘等。粗糙集理论由z p a w l a k 在8 0 年代 提出【2 3 】，用于处理不确定性。其主要思想如下：把对象的属性分为条件属性和决 策属性，按各属性值相同分等价类。 ( 5 ) 统计分析方法 主要用于完成汇总知识和关联知识的挖掘。对关系表中各属性进行统计分析， 找到它们之间潜在的关系。关系表的属性之间一般存在以下两种关系： ( a ) 函数关系( 能用函数公式表示的确定性关系) ； ( b ) 相关关系( 不能用函数公式表示，但仍是相关确定关系) ； 对它们的分析可以采用回归分析、相关分析、主成分分析等统计分析方法【2 4 】。 ( 6 ) 模糊论方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模 糊聚类分析。模糊性足客观存在的，系统的复杂性越高，精确化能力就越低，也 就意味着模糊性越强。这是z a d e h 总结出的互克性原理【25 1 。 2 6 数据挖掘的应用 数据挖掘技术旨在发现大量数据中所隐藏的知识，以用来解决“数据丰富、知 识贫乏”的问题。近年来随着数据库和网络技术的广泛使用，加上使用先进的自动 数据生成和采集工具，人们所拥有的数据量急剧增加，使得数据挖掘技术得到广 泛的应用，如科学研究、金融投资、市场营销、保险、医疗卫生、产品制造业、 通信网络管理等行业。 l - 科学研究 在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的大量实 验和观测数据靠传统的数据分析工具己难于对付，因此对功能强大的智能化自动 分析工具要求迫切，这种需求推动了k d d 技术在科学研究领域的应用发展，并且 9 两南j 、学t “# 位论文 第2 辛嚣摧挖捧嘬述 已经获得一些重要的应用成果。 2 会融投资 在银行和会融机构中产生的会融数据通常相对比较完整，可靠和质量较高， 因此，数据挖掘在这一领域中的应用相对比较成熟，也取得较好的社会效益和经 济效益。由于金融投资的风险很大，在进行投资决策时，需要对各种投资方向的 有关数据进行分析，以选择最佳的投资方向，而数据挖掘则是通过对已有数据进 行处理，并利用学习得到的模式进行市场预测，以选择最佳的投资方向，可使金 融投资的风险降低。通过分析市场波动的因素，建立预测模型，进行投资分析和 预测，改进预测市场波动的能力，为投资决策提供科学的依据。 3 保险业 随着社会保障体系的日益健全，保险业取得了蓬勃的发展，发挥着越来越重 要的作用。保险是一项风险业务，保险公司的一个重要工作就是进行风险评估。 通过研究证明，可以利用数据挖掘技术来进行风险分析，在保险公司建立的保单 及索赔信息数据库的基础上，寻找保单中风险较大的领域，从而得出一些实用的 控制风险的规则，以指导保险公司的工作。数据挖掘技术在保险业中的应用，有 利于保险公司开展业绩评价、业务预算、市场分析、风险评估和风险预测等，大 大提高企业防范和抵抗经营风险的能力和水平，也为管理人员提供科学的决策依 据。 4 零售业 零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买习性和趋向， 对于零售商制定销售策略是至关重要的。销售分析人员运用关联规则挖掘技术对 大量的销售数据进行分析，可以发现顾客购买模式和趋势，改进服务质量，取得 更好的顾客保持力和满意程度，提高货品销售比率，设计更好的货品运输与分销 策略，减少商业成本。购物篮分析是数据挖掘技术应用在零售业中的一种有效方 式，可用于销售搭配、产品目录设计、产品定价和促销等。 5 制造业 随着现代技术越来越多地应用于制造业，产品生产己不是人们想象中的手工 劳动，而是集成了多种先进科技的流水作业。在产品的生产制造过程中常常伴随 着大量的数据，如产品的各种加工条件或控制参数，这些数据反映了每个生产环 节的状态，不仅为生产的顺利进行提供了保证，而且通过对这些数据的分析，得 到产品的质量与这些参数之间的关系。这样通过数据挖掘对这些数据的分析，可 以对改进产品质量提出针对性很强的建议，而且有可能提出新的更高效节约的控 制模式，从而为制造厂家带来极大的凹报。 6 电信业 1 0 两丽人掌埘l i 掌位论上幂2 审致据皑拶转述 电信业已经从单纯的提供市话和长话服务演变成提供综合服务电信业务，如 语音、传真、寻呼、移动电话、图像、电子邮件、计算机和w e b 数据传输，以及 其他数据通信服务。而且随着许多国家对电信业的丁f 放和新兴计算与通信技术的 发展，电信市场正在迅速扩张并越发竞争激烈。冈此，利用数据挖掘技术来帮助 理解商业行为、确定电信模式、捕捉盗用行为、更好地利用资源和提高服务质量 是非常必要的。 7 其它应用领域 医疗数据挖掘可用于病例、病人行为特征的分析，以及用于药方管理等，以 安排治疗方案、判断药方的有效性等；司法数据挖掘可用于案件调查、案例分析、 犯罪监控等，还可用于犯罪行为特征模式的分析，从而为案件的侦破提供指导， 进而为教育和改造犯罪寻求有效方法；工业部门数据挖掘技术可用于进行故障诊 断、生产过程优化等。制造业应用数据挖掘技术来进行零件故障诊断、资源优化、 生产过程分析等，通过对生产数据进行分析，可发现容易产生质量问题的工序以 及相关的故障因素等。 在网络入侵监测领域中，计算机的网络化和操作系统的同益复杂化给系统带 来的安全隐患，以及黑客的活动日益活跃，这就对网络安全工作提出了挑战。如 何从大量审计数据中发现用户的行为模式，并提取出具有代表性的系统特征模式， 从而发现异常的访问模式，是入侵监测急需解决的关键问题。数据挖掘技术是用 于从海量数据中提取用户有用的数据，将该技术用于入侵检测领域，利用数据挖 掘中的关联分析，序列模式分析等算法提取相关的用户行为特征，并根据这些特 征生成安全事件的分类模型，应用于安全事件的自动鉴别。 2 7 关联规则和加权关联规则 近年来，关联规则已经成为数据挖掘中最成熟、最主要、最活跃的研究领域。 数据挖掘领域的研究者在挖掘关联规则上做了大量的工作，主要致力于改进算法， 提高算法速度和有效性。 加权关联规则足针对在获取关联规则的过程中，将项目组的支持度进行调整， 其主要是考虑现实中的某些情况，让一些获利率高但交易不频繁的产品也能符合 最小支持度。若某产品的支持度过低，则将导致无法找出其相关的关联规则，如 此便不能了解此产品与其它产品之间的关联性。在现实的交易中，商家往往更希 望得知获利率高的产品其关联性，例如家电的交易次数一定比面包的交易次数来 的少很多，可能卖出了一百个面包才卖出一台家电，但就获利率高低束衡量，家 电的销售关联性可能是商家更想知道的，因为商家希望卖出更多高获利率的产品。 两南、7 帅| | # p - 沧义羁2 帝静据掺掘啊述 因此需要提升高获利产品的支持度权值，使其能成为频繁项目集，进而找出与其 相关的规则，以便发掘出这些产品的最佳营销组合。使得每个项目在数据库中出 现的频度( 支持度) 与各个项目在使用者心目中的重要程度( 权值) 综合起来考 虑衡量他们的重要性。 1 2 两南上绚卜f ? ，泠z第3 争篾孵w 州挖掘算法 第3 章关联规则挖掘算法 关联规贝t j ( a s s o c i a t i o nr u l e s ) 的概念首先是由r a g r a w a l 等人于1 9 9 3 年在文献 3 】中提出的，此后在文献【4 】【2 6 】【2 7 中，他们又对关联规则进行了推广。关联规则 是发现交易数据库中不同商品( 项) 之间的联系【2 ”，即寻找给定数据集中的有趣 联系。通过描述数掘库中数据项之自j 所存在的潜在关系的规则，找出满足给定支 持度和置信度阀值的多个域之自j 的依赖关系。关联规则挖掘在商业等领域的成功 应用，使它成为了数据挖掘中最成熟、最重要、最活跃的研究内容【2 9 j 1 3 0 i 。例如， 对超市销售数掘进行关联规则挖掘可以找出顾客购买行为模式，应用于商品货架 设计、存货安排以及根据购买模式对用户进行分类等；在客户关系管理中，有趣 的关联规则可以用来分析客户的行为，以帮助市场人员制定相应的促销策略来进 行客户保持和客户服务。 3 1 关联规则挖掘的基本概念 3 1 1 问题定义 为了准确地描述关联规则挖掘问题，便于问题的讨论，给出关联规则挖掘问 题的形式化定义，首先介绍关联规则挖掘中几个相关术语的定义。 定义3 1 设i = i l ，i 2 ，i m 是项( i t e m ) 的集合。设任务相关的数据是数据库事 务的集合，其中每个事务t 是项的集合，使得t i