（应用数学专业论文）关联规则挖掘算法的研究与改进.pdf

武汉理工大学硕士学位论文 摘要 随着数据库技术的日益成熟和管理信息系统的广泛普及，人类积累的数据量 正在以指数级的速度增长。面临浩渺无际的数据，人们渴望得到从数据中来一 个去粗存精、去伪存真的技术。数据挖掘便应运而生了。数据挖掘是从数据中 析取、识别和发现潜在正确和有用、前所未知的、最终可理解的知识( 规则或 模型) 的过程。 关联规则挖掘是数据挖掘中最活跃的研究方法之一。它是由a g r a w a l 于1 9 9 3 年提出的。关联规则挖掘用于发现交易数据库中不同项目集之间的关系。关联 规则的算法可按照需不需要产生候选项集的做法分为两类，以f p ( 频繁模式) 树法与类a 研。一方法为代表。此二者最主要的差异在于，f p 树法并不产生候选 项集，后者是需要产生候选项集的方法。 本文在数据挖掘研究的基础上深入研究了关联规则挖掘，着重对经典关联 规则算法中的a 研o r i 算法进行了深入研究，对它的性能进行了分析，根据它的 不足之处提出了两个新的改进算法。论文的主要内容如下： 1 ) 对数据挖掘的定义、过程、技术分类以及发展趋势进行了综述。 2 ) 对关联规则挖掘的定义，性质、挖掘过程、挖掘算法以及研究现状进行 了综述。 3 ) 对经典的关联规则算法a p f i o r i 算法进行了详细的介绍，并分析了它的特 点，同时还介绍了该算法的一些改进算法。 4 ) 根据o p a 研o r i 算法的特点，提出了o m a p r i o r i 算法；根据m a p r i o r i 算法的特点，提出了s m a p r i o r i 算法。 本文的主要创新点如下： 1 ) 根据o p a p 订o d 算法的特点，提出了o m a p r i o f i 算法，用m a t 算法来改 进0 p a p r i o r i 算法中前两项频繁项集的生成，用文献 3 4 中的方法来改进 k ( k 3 ) 一频繁项目集的生成，o m a p f i o r i 算法使得算法的效率进一步提高。 2 ) 根据m a p r i o r i 算法的特点，提出了s m a p r i o r i 算法，该算法利用不是所 有的项和事务都对产生频繁项集有帮助的性质来缩小布尔矩阵的方法，使得算 法的时间复杂度和空间复杂度都有所减少，从而提高了算法的效率。 关键词：数据挖掘，关联规则，a 研o r i 算法，时间复杂性，空间复杂性 武汉理工大学硕士学位论文 a b s t r a c t a st h e g r o w i n gu po fd a t a b a s e st e c h n i q u ea n dp r e v a l e n to fa d m i n i s t r a t o r i n f o r m a t i o ns y s t e m ，t h en u m b e ro fu n u s e dd a t ah a sb e e ni n c r e a s i n ga tt h er a t eo f e x p o n e n t i nf r o n to fl a r g en u m b e ro fd a t a ，p e o p l eo f t e ne x p e c tf o rat e c h n o l o g y w h i c he l i m i n a t e st h ef a l s en u m b e r sb u tr e t a i nt h et r u ev a l u e s s od a t am i n i n gh a s b e e np r o p o s e d ，w h i c hi st h ec o r eo fk n o w l e d g e d i s c o v e r yi nd a t a b a s e s d a t am i n i n gi st h ep r o c e s so fe x t r a c t i n g ，i d e n t i f y i n ga n dd i s c o v e r i n gp o t e n t i a l l y v a l i d ，u s e f u l ，p r e v i o u s l yu n k n o w n ，a n du l t i m a t e l yu n d e r s t a n d a b l ek n o w l e d g e ( r u l e so r p a t t e r n s ) t h em i n i n go fa s s o c i a t i o nr u l e si so n eo ft h em o s ta c t i v er e s e a r c h e si nd a t am i n i n g i tw a sp r o p o s e db ya g a w a li n19 9 3 t h em i n i n go fa s s o c i a t i o nr u l e si su s e df o r d i s c o v e r i n gt h er e l a t i o no fd i f f e r e n ti t e m s e t si nd a t a b a s e s t h ea l g o r i t h m so f a s s o c i a t i o nr u l e sf a l li n t ot w oc a t e g o r i e sa c c o r d i n gt ot h en e e d so fp r o d u c i n g c a n d i d a t ei t e m 。s e t s ，m a i n l yf r e q u e n tp a t t e r nt r e ea n da p r i o r i _ l i k ea l g o r i t h m s t h e m a i nd i f f e r e n c ei st h a tf r e q u e n tp a t t e r nt r e ed o e sn o tp r o d u c ec a n d i d a t ei t e m s e t s t h el a t t e ri st h ea l g o r i t h mn e e d st op r o d u c e c a n d i d a t ei t e m s e t s b eb a s e do nr e s e a r c h i n go fd a t am i n i n g ，w ed os o m e d e e pr e s e a r c ho nt h em i n i n g o fa s s o c i a t i o nr u l e s ，e m p h a s i z eo na p r i o r ia l g o r i t h m ，w h i c hi sac l a s s i c a la l g o r i t h mo f a s s o c i a t i o nr u l e sm i n i n g w ea n a l y z ei t ，b r i n gf o r w a r di t ss h o r t a g ea n dp r o p o s et w o i m p r o v e m e n ta l g o r i t h m s t h em a i nc o n t e n ta r ea sf o l l o w s ： 1 ) w ed oas u m m a r yt od e f i n i t i o n 、p r o c e s s 、t e c h n i q u ec l a s s e sa n dt r e n do fd a t a m i n i n g 2 ) w ed oas u m m a r yt od e f i n i t i o n 、p r o p e r t y 、m i n i n gp r o c e s s 、m i n i n ga l g o r i t h m sa n d p r e s e n tr e s e a r c ho f a s s o c i a t i o nr u l e sm i n i n g 3 ) w ei n t r o d u c et h ec l a s s i c a la s s o c i a t i o nr u l ea l g o r i t l l i 】卜以p r i o r ii nd e t a i l ，d os o m e a n a l y s i so ni t sp r o p e r t y , a tt h es a m et i m e ，i n t r o d u c es o m ei m p r o v e da l g o r i t h m sb a s e d o n i t 4 ) w ep r e s e n to m - a p r i o r ia l g o r i t h ma c c o r d i n gt o o p a p r i o r i ，a n dp r e s e n t i i 武汉理工大学硕士学位论文 s m a p r i o r ia l g o r i t h ma c c o r d i n g t om a p r i o r i t h em a i ni n n o v a t i o np o i n t so ft h i sp a p e i a r ea sf o l l o w s ： 1 ) w ep r e s e n to m a p r i o r ia l g o r i t h ma c c o r d i n gt ot h ep r o p e r t i e so fo p a p r i o r i ， w h i c hi m p r o v et h ep r o c e s so ft h ef i r s tt w of r e q u e n ti t e m - s e t sb ym a ta l g o r i t h m ， i m p r o v et h ep r o c e s so fkf r e q u e n ti t e m s e t sb yt h em e t h o di nl i t e r a t u r e 【3 4 ，w h e r e k 3 ；o m a p r i o r ia l g o r i t h mi m p r o v ea p r i o r ia l g o r i t h mf u r t h e r 2 ) w ep r e s e n ts m a p r i o r ia l g o r i t h ma c c o r d i n g t ot h ep r o p e r t i e so fm a p r i o r i ，w h i c h m a k eu s eo ft h ep r o p e r t yo ft h a tn o ta l li t e m sa n da f f a i r sa r eu s e f u lf o rp r o d u c i n g f r e q u e n ti t e m - s e t st os h r i n kt h em a t r i x ，s m a p r i o r ia l g o r i t h mi m p r o v e t h em a p r i o r i a l g o r i t h mo nt i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t y k e yw 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 ，a p r i o r ia l g o r i t h m ，t i m ec o m p l e x i t y , s p a c ec o m p l e x i t y i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特另t j d i l 以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或 部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：卫卫皇l 笼导师签名：半日期： 武汉理工大学硕士学位论文 1 1 研究背景 第1 章绪论 科技的进步，特别是信息产业的发展，把我们带入了一个崭新的信息时代。 随着计算机应用的普及和数据库技术的不断发展，数据库管理系统的应用领域 越来越广泛。条形码和信用卡的普及和使用，进一步加速了商业、金融、保险 等领域的信息化进程。人们已经利用计算机取代了绝大部分手工操作。超级市 场中的交易数据，加油站里的油料购买数据，旅行社中的旅行信息数据等均是 数据库系统的信息来源。最近十几年数据库中存储的数据量急剧增大。例如， n a s a 轨道卫星上的地球观测系统e o s 每小时会向地面发回5 0 g b 左右的图像数 据；世界上最大的数据仓库之一，美国零售系统w a l - m a r t 每天会产生2 亿左右 的交易数据；人类基因组数据库项目已经搜集了数以g b 计的人类基因编码数据 等。如此多领域的数据各自存放在相应的数据库中，致使数据库的规模日益扩 大，已经达到数十兆字节，有的甚至更大。与此同时，大容量、高速度、低价 格的存储设备也相继问世，管理大量数据的数据库管理系统以及各类数据仓库 已经能够支持存储、检索如此规模的数据。但目前数据库系统所能做到的只是 对数据库中已有的数据进行存取，通过这些数据获得的信息量只占整个数据库 信息量的一小部分，因为用来对这些数据进行分析处理的工具很少，而且有局 限性。在信息时代，大量信息在给人们带来方便的同时，也带来了一系列问题， 比如，信息量过大，超过了人们掌握、消化的能力；一些信息真伪难辨，给信 息的正确运用带来困难；网络上的信息安全难以保障；信息组织形式的不一致 性，增加了对信息进行有效统一处理的难度等。另一方面，人们意识到隐藏在 这些数据之后的更能深层次、更重要的信息能够描述数据的整体特征，可以预 测发展趋势，这些信息在决策生产过程中具有重要的参考价值。面对海量数据 库和大量繁杂信息，如何才能从中提取出有价值的知识，进一步提高信息的利 用率，由此引发了一个新的研究方向：基于数据库的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 及相关的数据挖掘( d a t am i n i n g ) 理论和技术的研 究。 武汉理工大学硕士学位论文 数据挖掘是一个多学科交叉研究领域，它融合了数据库技术、人工智能 ( a r t i f i c i a le n g i n e e r i n g ) 、机器学习( m a c h i n el e a r n i n g ) 、统计学 ( s t a t i s t i c s ) 、知识工程( k n o w l e d g ee n g i n e e r i n g ) 、面向对象方法 ( o b j e c t o r i e n t e dm e t h o d ) 、信息检索( i n f o r m a t i o nr e t r i e v a l ) 、高性能计 算( h i 曲一p e r f o r m a n c ec o m p u t i n g ) 以及数据可视化( d a t av i s u a l i z a t i o n ) 等最新技术的研究成果。经过几十年的研究，产生了许多新概念和新方法。特 别是近几年，一些基本概念和方法趋于清晰，它的研究正向着更深入的方向发 展。【i 】 特别需要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面 向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏 观的统计、分析、综合和推理。这里所说的知识发现，不是要求发现放之四海 而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式。所有发现 的知识都是相对的，是面向特定领域的，同时还要能够易于被用户理解。i l l 关联规则挖掘是数据挖掘中的主要技术之一，也是在无指导学习系统中挖 掘本地模式的最普遍形式。它也是大多数人在试图了解数据挖掘的过程时，所 想到的最接近于该过程的形式；关联规则反映一个事物与其他事物之间的相互 依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其 中一个事物就能够通过其他事物预测到。 2 1 1 2 数据挖掘综述 1 2 1 数据挖掘的定义 数据挖掘的概念包含丰富的内涵，是一个多学科交叉研究领域。理解数据 挖掘的概念不是简单地下个定义就能解决的问题。下面我们就从k d d 和d a t a m i n i n g 的关系的不同观点中了解数据挖掘的含义【i 】。 ( 1 ) k d d 看成数据挖掘的一个特例 既然数据挖掘系统可以在关系型数据库、事务数据库、数据仓库、空间数 据库、文本数据以及诸如w e b 等多种数据组织形式中挖掘知识，那么数据库中 的知识发现只是数据挖掘的一个方面。这是早期比较流行的观点，因此从这个 意义上说，数据挖掘是从数据库、数据仓库以及其他数据存储方式中挖掘有用 2 武汉理工大学硕士学位论文 知识的过程。这种描述强调了数据挖掘在源数据形式上的多样性。 ( 2 ) 数据挖掘是k d d 过程的一个步骤 为了统一认识，在1 9 9 6 年出版的权威论文集知识发现与数据进展中， f a y y d ，p i a t a t s k y s h a p r i r o 和s m y t h 给出了k d d 和数据挖掘的最新定义，将二 者加以区分。 k d d 是从数据中辨别有效的、新颖的、潜在有用的、最终可以理解的模式的 过程。 数据挖掘是k d d 中通过特定的算法在可接受的计算效率限制内生成特定模 式的一个步骤。 这种观点得到很多人的认同，有一定的合理性。虽然我们可以从数据仓库、 w e b 等源数据中挖掘知识，但是这些数据源都是和数据库技术相关的。因此k d d 是一个更广泛的范畴，它包括数据清洗、数据集成、数据选择、数据转换、数 据挖掘、模式生成及评估等一系列步骤。这样可以把k d d 看成是一些基本功能 构成的系统化协同工作系统，而数据挖掘是这个系统中的一个关键部分。 ( 3 ) k d d 与数据挖掘含义相同 现在更多人认同，k d d 和数据挖掘只是叫法不一样，它们的含义基本是相同 的。在本文中我们也对二者不加以区分。 所以，数据挖掘定义有广义和狭义之分。从广义的观点，数据挖掘是从大 型数据集( 可能是不完全的、有噪声的、不确定性的、各种存储形式的) 中， 挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的过程。从这种狭 义的观点上，我们可以定义数据挖掘是从特定形式的数据集中提炼知识的过程。 其中： 数据：一个有关事实的集合，它是用来描述事物有关方面的信息，是我们 进一步发现知识的原材料。 事先未知的：也就是前面说的新颖的。 对决策有用的：就是提取出来的模式或知识必须是有意义的。 1 2 2 数据挖掘的过程 从源数据中发现有用知识或模式是一个系统化的工作，首先必须对可以利 用的源数据进行分析，确定合适的挖掘目标。然后才能着手系统的设计和开发。 3 武汉理工大学硕士学位论文 本文介绍的数据挖掘过程是指在业务需求已经清楚的前提下，设计一个知识或 模式发现系统一般应具有的关键步骤。 完成从大型源数据中发现有价值知识或模式的过程可以简单地概括为：首 先从数据源中抽取感兴趣的数据，并把它组织成适合挖掘的数据组织形式；然 后，调用相应的算法生成所需的知识或模式；最后对生成的知识模式进行评估， 并把有价值的知识集成到企业的智能系统中。 一般地说，数据挖掘是一个多步骤的处理过程，分为问题定义、数据抽取、 数据预处理、建立模型以及模型评估等基本阶段。 1 问题定义 数据挖掘是用于在大量数据中发现有用的令人感兴趣的信息，因此发现何 种知识就成为整个过程中第一个也是最重要的一个阶段。在问题定义过程中， 数据挖掘人员必须和领域专家以及最终用户紧密协作，一方面了解相关领域的 有关情况，熟悉背景知识，弄清用户要求，确定挖掘的目标等要求；另一方面 通过各种学习算法的对比进而确定可用的学习算法。后续的学习算法选择和数 据集准备都是在此基础上进行的。 2 数据抽取 数据抽取的目的是选取相应的源数据库，并根据要求从数据库中提取相关 的数据。源数据库的选取以及从中提取数据的原则和具体规则必须依据系统的 任务来界定。在弄清楚源数据的信息和结构的基础上，首先要准确地界定所选 取的数据源和抽取原则，将多数据库运行环境中的数据进行合并处理达到数据 集成的目的，然后设计存储新数据的结构和准确定义它与源数据的转换和装载 机制，以便正确地从每个数据源中抽取所需的数据。这些结构和转换信息应该 作为元数据被存储起来。在数据抽取过程中，必须要全面掌握源数据的结构特 点，任何疏忽都可能导致数据抽取的失败。在抽取多个异构数据源的过程中， 可能需要将不同的源数据格式转换成一种中间模式，再把它们集成起来。应用 领域的分析数据通常来自多个数据源，所以必须进行数据集成。来自不同源的 数据可能有模式定义上的差异，也可能存在因数据冗余而无法确定有效数据的 情形。此外，还要考虑数据库系统本身可能存在不兼容的情况。 3 数据预处理 数据预处理主要是对前一阶段抽取的数据进行再加工，检查数据的完整性 及数据的一致性。包括消除噪声、推导计算缺值数据、消除重复记录、完成数 4 武汉理t 大学硕士学位论文 据类型转换( 如把连续值数据转换为离散型的数据，以便于符号归纳，或是把 离散型的转换成连续值型的，以便应用于神经网络) 等。当数据挖掘的对象是 数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成了。但是，当 源数据来自于多数据源时，它就成为一个重要的方面。因为源数据结构的异构 ( 关系表、w e b 网页、不同文件等) 或属性差异( 名字不同、含义不同、数据类 型不同等) ，在抽取过程中产生的噪声数据就不可忽略。数据预处理是数据挖 据的重要阶段，而且可能花费很大。有一种“3 ：7 ”的说法就是指数据抽取和 预处理工作一般可能占到整个数据挖据过程的7 0 左右。 如前所述，在开始一个知识发现项目之前必须清晰地定义挖掘目标。虽然 挖掘的最后结果是不可预测的，但是要解决或探索的问题应该是可预见的。盲 目性地挖掘是没有任何意义的。在弄清业务问题后就可以进行数据的准备。数 据预处理是进行数据分析和挖掘的基础，如果所集成的数据不正确，数据挖掘 算法输出的结果也必然不正确，这样形成的决策支持是不可靠的。因此，要提 高挖掘结果的准确率，数据预处理是不可忽略的一步。对数据进行预处理，一 般需要对源数据进行再加工，检查数据的完整性及数据的一致性，对其中的噪 音数据进行平滑化，对丢失的数据进行填补，消除“脏”数据，消除重复记录 等。常见的数据预处理方法有：数据清洗、数据变换和数据规约等。 数据清洗是指去除或修补源数据中的不完整、不一致、含噪声的数据。在 源数据中，可能由于疏忽、懒惰、甚至为了保密使系统设计人员无法得到某些 数据项的数据。假如这个数据项正是知识系统所关心的，那么这类不完整的数 据就需要修补。常见的不完整数据的修补办法有：( 1 ) 使用一个全局值来填充； ( 2 ) 统计该属性的所有非空值，并用平均值来填充缺项；( 3 ) 只使用同类对象 的属性平均值填充；( 4 ) 利用回归或工具预测最可能的值，用它来填充。 数据不一致性可能是由于源数据库中对同样属性所使用的数据类型、度量 单位等不同而导致的。因此需要定义它们的转换规则，并在挖掘前统一成一个 形式。噪音数据是指那些明显不符合逻辑的偏差数据( 如某雇员2 0 0 岁) ，这些 不符合逻辑的数据往往影响挖据结果的正确性。目前讨论最多的处理噪音数据 的方法是数据平滑( d a t as m o o t h i n g ) 技术。1 9 9 9 年，p y l e 系统地归纳了利用 数据平滑技术消除噪音数据的方法，主要有：( 1 ) 利用分箱( b i n i n g ) 方法检 测周围相应属性的值来进行局部数据平滑；( 2 ) 利用聚类技术检测孤立点数据， 对它们进行修正；( 3 ) 利用回归函数探测和修正噪声数据。 5 武汉理工大学硕士学位论文 利用数据变换或规约可以将数据整理成适合进一步挖掘的数据格式。数据 变换可以根据需要构造出新的属性以帮助理解分析数据的特点，或者将数据规 范化，使之落在一个特定的数据区间中。数据规约则是在尽可能保证数据完整 性的基础上，将数据以其他方式进行表示，以减少数据存储空间，使挖据过程 更有效。常见的规约策略有：数据立方体聚集、维规约、数据压缩、数值压缩 和离散化等。 4 建立模型 经过数据清洗、抽取、选择和整理后，就可以进入建立模型阶段了，并通 过实施对应的算法来完成知识的形成。当然，现在有许多工具可以帮助完成数 据挖掘工作，这些工具许多都提供如关联规则、分类、聚类、决策树等多种模 型和算法。但是，不论是自己建立模型还是选取或改进已有模型都必须要进行 验证。这种验证最常用的方法是样本学习。先用一部分数据建立模型，然后再 用剩下的数据来测试和验证这个模型。测试数据集可以按一定比例从被挖掘的 数据集中提取，也可以使用交叉验证的方法，把训练集和测试集交换验证。数 据挖掘是一个反复的过程，通过反复的交互式执行和验证才能找到解决问题的 最好途径。通过不断地产生、筛选和验证，才能把有意义的知识集成到企业的 知识库或商业智能系统中去。 5 模型评估 建立模型中发现的模式，经过评估，可能存在冗余或无关的模式，这时需 要将其剔除；也有可能模式不满足用户要求，这时则需要整个过程回退到前续 阶段，如重新选取数据、采用新的数据变换方法、设定新的参数值，甚至换一 种算法等等。另外，数据挖掘由于最终是面向人类用户的，因此可能要对发现 的模式进行可视化，或者把结果转换为用户易懂的另一种表示。所以知识评估 阶段是数据挖掘的一个重要的必不可少的阶段，它不仅担负着将数据挖掘系统 发现的知识以用户能了解的方式呈现，而且根据需要进行知识评价，如果用户 的挖掘目标不一致需要返回前面相应的步骤进行螺旋式处理以最终获得可用的 知识。 1 2 3 数据挖掘的技术分类及知识表示模式 数据挖掘涉及的学科领域和方法很多，有多种分类方法。与数据挖掘相关 6 武汉理工大学硕士学位论文 的理论和技术可以分别按挖掘任务、挖掘对象和挖掘方法来分类。 按挖掘任务分类：包括分类或预测模型知识发现，数据总结，数据聚类， 关联规则发现，时序模式发现，依赖关系或依赖模型发现，异常和趋势发现等。 按挖掘对象来分：包括关系数据库，面向对象数据库，空间数据库，事态数 据库，文本数据库，多媒体数据库，异构数据库，数据仓库，演绎数据库和w e b 数据库等。 按挖掘方法分类：包括统计方法，机器学习方法，神经网络方法和数据库方 法。统计方法又可细分为回归分析( 多元分析、自回归分析等) ，判别分析( 贝 叶斯判别、费歇尔判别、非参数判别等) ，聚类分析( 系统聚类、动态聚类等) ， 探索性分析( 主成分分析、相关分析等) 等。机器学习方法可以细分为归纳学 习方法( 决策树、规则归纳等) ，基于规范学习，遗传算法等。神经网络方法 可以进一步分为前向神经网络( b p 算法等) ，自组织神经网络( 自组织特征映 射、竞争学习等) 。数据库方法主要是多维数据分析和o l a p 技术，此外还有面 向属性的归纳方法。 数据挖掘的目的是发现知识，知识要通过一定的模式给出。可用于数据挖 掘系统的知识表示模式是丰富的，通过对数据挖掘中知识表示模式及其所采用 方法的分析，可以更清楚地了解数据挖掘系统的特点。 1 广义知识挖掘 广义知识挖掘( g e n e r a l a t i o n ) 是指描述类别特征的概括性知识。我们知道， 在源数据中存放的一般是细节性数据，而人们有时希望能从较高层次的上试图 处理或观察这些数据，通过数据进行不同层次上的泛化来寻找数据所蕴含的概 念或逻辑，以适应数据分析的要求。数据挖掘的目的之一就是根据这些数据的 微观特性发现有普遍性的、更高层次概念的中观和宏观的知识。因此，这类数 据挖掘系统是对数据的所蕴含的概念特征信息、汇总信息和比较信息等的概括、 精炼和抽象的过程。被挖掘出的广义知识可以结合可视化技术以直观的图表( 如 饼图、柱状图、曲线图、立方体等) 形式展示给用户，也可以作为其他应用( 如 分类、预测) 的基础知识。 2 关联规则挖掘 关联规则反映一个事件和其他事件之间的依赖或关联。数据库中的数据关 联是现实世界中事物联系的表现。数据库作为一种结构化的数据组织形式，利 用其依附的数据模型可能刻画了数据问的关联( 如关系型数据库的主键和外 7 武汉理工大学硕士学位论文 键) 。但是，数据之间的关联是复杂的，不仅是上面说的依附在数据模型中的关 联，大部分是蕴藏的。关联规则挖掘的目的就是找出数据库中隐藏的关联信息。 关联可分为简单关联、因果关联、数量关联等。这些关联并不是事先知道的， 而是通过数据库中数据的关联分析获得的，因此对商业决策具有新价值。例如， 由于条形码技术的发展，零售部门可以利用前端收款机交易数据，并把这些数 据存储在后台海量数据库中。如果对这些历史数据进行分析，从中获得顾客购 买行为特征，对商家来说是极有价值的信息。这些信息有助于规划市场、合理 安排货架等。所谓关联规则是指在数据集中支持度和信任度分别满足给定阈值 的规则。 3 类知识挖掘 类知识( c l a s s ) 刻画了一类事物，这类事物具有某种意义上的共同特征， 并明显和不同类事物相区别，这里的类知识是指分类和聚类两类数据挖掘应用 所对应的知识。 ( 1 ) 分类 分类是数据挖掘中的一个重要的目标和任务，目前的研究在商业上应用很 多。分类的目的是学会一个分类模型( 称作分类器) ，该模型能把数据库中的数 据项映射到给定类别中。要构造分类器，需要有一个训练样本数据集作为输入。 由于数据挖掘是从源数据集中挖掘知识的过程，这种类知识也必须来自于源数 据，应该是对源数据的过滤、抽取( 抽样) 、压缩以及概念提取等。从机器学习 的观点，分类技术是一种有指导的学习( s u p e r v i s e dl e a r n i n g ) ，即每个训练样 本的数据对象已经有类标识，通过学习可以形成表达数据对象与类知识之间对 应的知识。从这个意义上讲，数据挖掘的目标就是根据样本数据形成的类知识 并对源数据进行分类、进而也可以预测未来数据的归类。用于分类的类知识可 以用分类规则、概念树，也可能以一种学习后的分类网络等形式表示出来。 ( 2 ) 聚类【2 】 聚类( c l u s t e r i n g ) 是将物理或抽象的对象集合分成多个组的过程，聚类生 成的组称为簇( c l u s t e r ) ，即簇是数据对象的集合。聚类就是要让生成的簇内部 的任意两个对象之间具有较高的相似度，而属于不同簇的两个对象间具有较高 的相异度。数据挖掘的目标之一就是进行聚类分析。通过聚类技术可以对源数 据库中的记录划分为一系列的有意义的子集，进而实现对数据的分析。例如， 一个商业销售企业，可能关心哪类顾客对指定的促销策略更感兴趣。聚类和分 8 武汉理工大学硕士学位论文 类技术不同，前者总是在特定的类标识下寻求新元素属于哪个类，而后者则是 通过对数据的分析比较生成新的类标识。聚类分析生成的类标识( 可能以某种 容易理解的形式展示给用户) 刻画了数据所蕴含的类知识。当然，数据挖掘中 的分类和聚类技术都是在已有的技术基础上发展起来的，它们互相交叉和补充。 数据挖掘关心聚类算法的如下特性：处理不同类型属性的能力、对大型数 据集的可扩展性、处理高维数据的能力、发现任意形状簇的能力、处理孤立点 或“噪声”数据的能力、对数据顺序的不敏感性、对先验知识和用户自定义参 数的依赖性、聚类结果的可解释性和实用性、基于约束的聚类等。 主要的数据挖掘聚类方法有：划分的方法、层次的方法、基于密度的方法、 基于网格的方法、基于模型的方法。 基于划分的聚类算法有k 平均算法以及它的一些改进算法，如k a u f m a n 等 的k 一中心点算法p a m 和c l a r e 算法；h u a n g 等提出的k 模和k 原型算法等，其 他有代表性的算法有e m 算法、c l a r a n s 算法等。 基于层次的聚类算法是通过对源数据库中的数据进行层次分解，达到目标 簇的逐步生成。有两种基本的算法：凝聚( a g g l o m e r a t i o n ) 和分裂( d i v i s i o n ) 。 基于密度的聚类算法是通过度量区域所包含的对象数目来形成最终目标 的。如果一个区域的密度超过指定的值，那么它就需要进一步分解成更细的组， 直到所有的分组满足用户的要求。比较有代表性的算法有d b s c a n 方法、基于 密度分布函数的d e n c l u e 聚类算法以及o p t i c s 聚类排序方法。 基于网格的方法是把对象空间离散化成有限的网格单元，聚类工作在这种 网格结构上进行。主要有s t r i n g 方法、w a v e c l u s t e r 和把基于网格和密度高度结 合的高维数据聚类算法c l i q u e 等。 基于模型的聚类方法为每一个簇假定一个模型，寻找数据对给定的模型的 最佳拟和。目前研究主要集中在利用概率统计模型进行概念聚类和利用神经网 络进行自组织聚类等方面。 4 预测型知识挖掘 预测型知识( p r e d i c t i o n ) 是指由历史的和当前的数据产生的并能推测未来 数据趋势的知识。这类知识被认为是以时间为关键性的关联知识，因此上面介 绍的关联知识挖掘方法可以应用到以时间为关键属性的源数据挖掘中。从预测 的主要功能上看，主要是对未来数据的概念分类和趋势输出。上面介绍的分类 技术可以用于产生对未来数据进行归类的预测型知识。 9 武汉理工大学硕士学位论文 5 特异型知识挖掘 特异型知识( e x c e p t i o n ) 是源数据中所蕴涵的极端特例或明显区别于其他 数据的知识描述，它揭示了事物偏离常规的异常规律。数据库中的数据常有一 些异常记录，从数据库中检测出这些数据所蕴涵的特异知识是很有意义的。例 如，在w e b 站点发现那些区别于正常登录行为的用户特点可以防止非法入侵。 特异型知识可以和其他数据挖掘技术结合起来，在挖掘普通知识的同时进一步 获得特异知识。例如，分类中的反常实例、不满足普通规则的特例、观测结果 与模型预测值的偏差、数据聚类外的离散值等。 1 2 4 数据挖掘研究的发展趋势 经过几十年的研究与实践，数据挖掘技术已经吸收了许多学科的最新研究 成果而形成独具特色的研究分支。毋庸置疑，数据挖掘研究和应用具有很大的 挑战性。像其他新技术的发展历程一样，数据挖掘也必须经过概念提出、概念 接受、广泛研究和探索、逐步应用和大量应用等阶段。分析目前的研究和应用 现状，数据挖掘在如下几个方面需要重点开展工作：数据挖掘技术与特定商业 逻辑的平滑集成问题；数据挖掘技术与特定数据存储类型的适应问题；大型数 据的选择与规格化问题；数据挖掘系统的构架与交互式挖掘技术；数据挖掘语 言与系统的可视化问题和数据挖掘理论与算法研究。 1 3 本文的研究内容、研究方法 近年来，数据挖掘研究领域已经成为热点，其中关联规则数据挖掘算法尤 为引人注目。关联规则反映一个事物与其他事物之间的相互依存性和关联性。 如两个或者多个事物之间的相互依存性和关联性。诸多的研究人员对关联规则 的挖掘问题进行了大量的研究。他们的工作涉及关联规则的挖掘理论探索、原 有算法的改进和新算法的设计、并行关联规则挖掘以及数量关联规则挖掘等问 题。 本文在前人研究的基础上，对关联规则挖掘的经典算法a p r i o r i 算法的步 骤、性能进行了详细的分析和研究，并提出了两种新的改进算法，将新算法的 性能从时间复杂度和空间复杂度来与旧算法进行比较来说明新算法的优越性。 并通过具体的例子来分析说明新算法在性能方法确实好于前人提出的算法。 1 0 武汉理工大学硕士学位论文 1 4 本文的组织结构 本文共分五章内容来对关联规则挖掘以及经典算法和一些改进算法进行了 阐述。 第l 章：简介了课题的研究背景、研究内容，背景主要是数据挖掘的定义、 数据挖掘的过程、数据挖掘的分类以及数据挖掘研究的发展趋势。 第2 章：对数据挖掘中的关联规则挖掘的定义、挖掘步骤、算法分类和研究 现状及发展趋势做了比较详细的综述和拓展。 第3 章：对最经典的关联规则算法- a p r i o r i 算法进行了详细描述，并用实 例进行说明，分析了该算法的特点和存在的问题，并介绍一些已有的a p r i o r i 改进算法。 第4 章：提出了a p r i o r i 的改进算法一o m - a p r i o r i 算法，并对它的性能进行 分析，以及将新算法的性能与原有的算法进行比较。 第5 章：提出了a p r i o r i 的改进算法一s m a p r i o r i 算法，并对它的性能进行 分析，以及将新算法的性能与原有的算法进行比较。 第6 章：总结和展望。总结全文的主要创新点，指出存在的不足，并指出今 后工作的方向。 1 5 小结 本章对本文的研究背景即数据挖掘的相关背景、主要研究内容、研究方法 及论文的结构安排做了概述。主要介绍了一下数据挖掘的相关知识，包括数据 挖掘的定义理解，数据挖掘的挖掘过程，数据挖掘的技术分类及知识表示模式 以及数据挖掘的发展趋势。 武汉理- t 大学硕士学位论文 第2 章关联规则挖掘概述 2 1 关联规则的定义及性质 关联规则挖据是本文研究的重点，为了使后面的算法描述更清晰、准确， 先将关联规则挖掘中涉及到的概念、名词、以及一些定理和结论进行介绍。 一个事物数据库中的关联规则挖掘可以描述如下【1 1 ： 事务数据库中的每一个属性称为一个项目( i t e m ) ，事务数据库中的每个项 目由，乞，。来表示。设i = p 。，i ：，f 。) 是一个项目集合，事物数据库 d = t ，f 2 ，j 。) 是一系列具有惟一标识t i d 的事务组成，每个事务t ，o = 1 , 2 ，n ) 都对应，上的一个子集。i i l _ 坍，其中m 为事务数据库中所含项目的总数。i d i 为 数据库的大小。d 是由多个事务组成的集合，每个事务是由一些项目组成的集 合，它表示本事务所包含的项目。此处所说的集合和一般意义下的集合概念有 所区别，一般概念中的集合只能用来说明元素在集合中出现还是不出现，而集 合中某个元素所对应的实例( 即事务) 的数量却无法表示，也就是一般集合理 论不能处理集合中的元素有多个实例的情况。在事务数据库中通常存在两个或 两个以上的事务包含完全相同的项目的情况。于是为了统计这些事务出现的次 数需要给事务数据库中的每个事务指定一个惟一的事务标识符。 定义2 1 1 由，中的一些项目所组成的集合x 称为项集( i t e m s e t ) ，包含k 个项的项集称之为k 项集，显而易见x 。 设x 为，中的一个项集，对给定的事务r ：如果有关系x ，成立，则事务 r 包含项集x 或x 包含于丁。 定义2 1 2 事务数据库d 中包含项集x 的事务数量，称为项集x 在d 中的 支持数，记为x c o u n t 。 定义2 1 3 设。，项目集在数据集d 上的支持度( s u p p o r t ) 是包含 i i 的事务在d 中所占的百分比，且1 s u p p o r t ( i ，) ：i | f d i 厶牝” i r 定义2 1 4 对项目集和事务数据库d ，r 中所有满足用户指定的最小支 持度( m i n s u p p o r t ) 的项目集，即大于或等于m i n s u p p o r t 的，的非空子集，称为 1 2 武汉理工大学硕士学位论文 频繁项目集( f r e q u e n ti t e m s e t s ) 或者大项目集( l a r g ei t e m s e t s ) 。在频繁 项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集 ( m a x i m u mf r e q u e n ti t e m s e t s ) 或最大大项目集( m a x i m u ml a r g ei t e m s e t s ) 定义2 1 5 关联规则( a s s o c i a t i o nr u l e ) 是形如厶j1 2 的逻辑蕴含式，其 中厶，1 2 i ，且，ir 、1 2 = 矽。 定义2 1 6 一个定义在，和j d 上的形如i ，ji ：的关联规则通过满足一定的 可信度、信任度或置信度( c o n f id e n c e ) 来给出。所谓规则的可信度是指包含， 和 ，的事务数与包含，的事务数之比，即 c o n f i d e ，z c e ( i lj ，2 ) = s u p p o r t ( 1 lv i p 即形( 其中k j 2ci ，i ln ，2 = 矽。 定义2 1 7d 在，上满足最小支持度和最小信任度( m i n c o n f i d e n c e ) 的关 联规则称为强关联规则( s t r o n ga s s o c i a t i o nr u l e ) 。 通常我们所说的关