（计算机应用技术专业论文）数据挖掘中的关联规则算法的研究.pdf

武汉理工大学硕士学位论文 摘要 随着信息时代的来临，人们要面对越来越庞大的数据，当数据量极度增长时 人们感到面对信息海洋像大海捞针一样束手无策，因此，需要一种从大量数据中 去粗存精、去伪存真的技术，数据挖掘技术就是人们长期对数据库技术进行研究 和开发的结果，是信息技术自然演化的结果。它从大量的数据中，抽取出潜在的、 有价值的知识、模型或规则的过程。 论文所研究的关联规则算法是数据挖掘中的重要内容之一。数据挖掘主要 的算法有分类模式、关联规则、决策树、序列模式、聚类模式分析、神经网络 算法等等。关联规则是数据挖掘领域中的一个非常重要的研究课题，广泛应用于 各个领域，既可以检验行业内长期形成的知识模式，也能够发现隐藏的新规律。 有效地发现、理解、运用关联规则是完成数据挖掘任务的重要手段，因此对关联 规则的研究具有重要的理论价值和现实意义。 论文主要分析比较了各种成熟的关联规则算法的优劣，总结了关联算法的 改进策略，并说明了数据挖掘中关联算法的相关应用，最后展望了关联规则的 前沿研究问题和未来的发展趋势。 关键词：数据挖掘关联规则算法研究 武汉理工大学硕士学位论文 a b s t r a c t w i t ht h ec o m i n go fi n f o r m a t i o na g e ，p e o p l ew i l lb ec o n f r o n t e dw i t hm o r ea n d m o r ed a t a a st h ea m o u n to fd a t ai se x t r e m e l y g r o w i n g ，p e o p l ef e e la tal o s sw h e n f a c i n gt h ei n f o r m a t i o ns e aj u s tl i k el o o k i n gf o ran e e d l ei nah a y s t a l k s o ，a t e c h n o l o g yt h a tc a l ld i s c a r dt h ed r o s sa n ds t o r ei t sq u a i n t n e s s ，e l i m i n a t et h ef a l s ea n d r e t a i nt h et r u ei sn e e d e d d a t am i n i n gt e c h n o l o g yr e s u l t e df r o mt h el o n gr e s e a r c h a n dd e v e l o p m e n to fd a t at e c h n o l o g y ，t h en a t u r a le v o l u t i o no fi n f o r m a t i o n t e c h n o l o g y i tc a nd r a wp o t e n t i a l ，v a l u a b l ek n o w l e d g ea n dm o d e l so rt h ep r o c e s so f t h er u l e sf r o mal a r g ea m o u n to fd a t a t h er e l a t e da l g o r i t h ms t a t e di nt h i st h e s i si sa ni m p o r t a n tc o n t e n td a t am i n i n g , w h o s em a i na l g o r i t h mi n c l u d e dc l a s s i f i e dm o d e ，r e l a t e dr u l e ，s t r a t e g i ct r e e ，a r r a y m o d e ，c l u s t e r sm o d ea n a l y s i s ，n e r v en e t w o r ka l g o r i t h ma n ds oo n t h er e l a t e dr u l e i sav e r yi m p o r t a n tr e s e a r c ht a s ki nt h ef i e l do fd a t am i n i n g , w i d e l yu s e di na l lk i n d s o ff i e l d s t oe x a m i n et h ek n o w l e d g em o d ed e v e l o p i n gf o ral o n gt i m ei n s i d et h e p r o f e s s i o na sw e l la sd i s c o v e rt h eh i d d e nn e wr e g u l a t i o n e f f e c t i v e l yd i s c o v e r i n g , u n d e r s t a n d i n g , a n du s i n gt h er e l a t e dr u l ei sav e r yi m p o r t a n tm e a n so ff i n i s h i n g d a t a m i n i n gt a s k t h e r e f o r e ，t h er e s e a r c ho nt h er e l a t e dr u l eh a s as i g n i f i c a n tt h e o r yv a l u e a n dr e a l i s t i cm e a n i n g t h i st h e s i sw a sm a i n l ya i m e dt om a k ea na n a l y s i sa n dc o m p a r i s o no nt h e r e l a t e dr u l e ss u p e r i o r i t ya sw e l la si n f e r i o r i t y ；m a k eac o n c l u s i o no ft h es t r a t e g y i m p r o v i n gt h er u l e ；m a k eas t a t e m e n to ft h er e l a t e da p p l i c a t i o nt ot h er e l a t e dr u l ei n d a t am i n i n g ；a tl a s t ，m a k ea p r o s p e c to f t h er e s e a r c hp r o b l e mi nt h ef r o n ta n d t h e d e v e l o p m e n tt r e n di nt h ef u t u r ea b o u tt h er e l a t e dr u l e f 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 l g o r i t h mr e s e a r c h i l 武汉理工大学硕士学位论文 第1 章引言 1 1 论文研究的目的及意义 随着信息时代的来临，人们要面对越来越庞大的数据，当数据量极度增长时， 人们感到面对信息海洋像大海捞针一样束手无策，因此，需要一种从大量数据中 去粗存精、去伪存真的技术，数据挖掘技术就是人们长期对数据库技术进行研究 和开发的结果，是信息技术自然演化的结果。它从大量的数据中，抽取出潜在的、 有价值的知识、模型或规则的过程。经过十几年的研究和发展，数据挖掘技术进 人了一个更高级的阶段，数据挖掘算法也已基本成熟、稳定。如今数据挖掘研究 正蓬勃开展，在今后还会掀起更大的波澜，这门新兴的学科会有更加广阔的前景。 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据 挖掘中是一个重要的课题，最近几年已被业界所广泛研究。 关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交 易数据库中不同商品( 项) 之间的联系，找出顾客购买行为模式，如购买了某 一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排 以及根据购买模式对用户进行分类。 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则 问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的 工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算 法挖掘规则的效率；对关联规则的应用进行推广。 最近也有独立于a g r a w a l 的频集方法的工作，以避免频集方法的一些缺陷， 探索挖掘关联规则的新方法。也有一些工作注重于对挖掘到的模式的价值进行 评估，他们提出的模型建议了一些值得考虑的研究方向。 1 2 国内外研究现状 数据挖掘是从大量数据中挖掘隐含的、未知的、对决策有潜在价值的知 武汉理工大学硕士学位论文 识，为市场策划，企业管理，决策支持提供了理论依据。数据挖掘的过程就是知 识发现的过程。它是涉及数据库，人工智能，机械学，统计学，人工神经网络等的 交叉学科，是目前国际上数据库和决策支持领域的最前沿的研究方向之一。 所谓关联规则挖掘是从大量的、有噪声的、模糊的、随机的实际数据中， 抽取隐含在其中的、人们事先不知道的、但又是潜在有用的关联信息和知识的 过程。自从a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关 联规则问题以来，很多研究人员对关联规则的挖掘问题进行了研究，从不同角 度提出了数十种关联规则挖掘算法，主要有a p r i o r l 、a i s 、s e t m 、p a r t i t i o n 、 m l _ t 2 l 1 等数据挖掘算法，而其中以a g r a w a l 等人提出的a p r i o r i 算法最为著 名，其后的数据挖掘算法大多建立在a p r i o r i 算法基础之上，或改进，或衍生变 种。如a p r i o r i 算法和等人提出的算法等。t i d p a r kd h p a g r a w a l 等，于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规 则问题，其核心力一法是基于频集理论的递推方法。以后许多研究人员对原有 的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效 率：提出各种变体，如泛化的关联规则，对关联规则的应用进行推广。 然后a g r a w a l 等在1 9 9 3 年设计了一个基本算法，提出了挖掘关联规则的一 个重要方法，这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设 计分解为两个子问题： ( 1 ) 找到所有支持度大于最小支持度的项集( i t e m s e t ) ，这些项集称为频集 ( f r e q u e n ti t e m s e t ) 。 ( 2 ) 使用第1 步找到的频集产生期望的规则。 这里的第2 步相对简单点。如给定了一个频集y = 1 11 2 i k ，k 2 ，( i ，产 生只包含集合 1 1 ，1 2 ，【忡的项的所有规则( 最多k 条) ，其中每一条规则 的右部只有一项，( 即形如【y 一瑚一皿v l i k 。一旦这些规则被生成，那么只 有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使 用了递推的力一法。其核心思想为： 首先产生频繁1 项集l ，然后是频繁2 项集l z ，直到有某个r 值使得 2 武汉理工大学硕士学位论文 h 为空，这时算法停止。这里在第k 次循环中，过程先产生候选k 项集的集合 c k ，c k 中的每一个项集是对两个只有一个项不同的属于u 【的频集做一个( k - 2 ) 连接来产生的。c k 中的项集是用来产生频集的候选集，最后的频集u 【登须是 c k 的一个子集。c k 中的每个元素需在交易数据库中进行验证来决定其是否加 入u 【，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很 大的交易数据库，这将增加很大的i 0 负载。 a g r a w a l 等后来引入了修剪技术( p r u n m g ) 来减小候选集c k 的大小，这样， 可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样 个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果c k 中某 个候选项集有一个取1 ) 子集不属于l k 1 ，则这个项集可以被修剪掉不再被 考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。 目前，数据挖掘中产生关联规则的方法以及它的应用已渐渐成熟，一些研 究成果已被集成在一些系统中，如m m 的q u e s t 项目、s i m o n f a r s e 大学的 d b m i n e r 等。关联规则挖掘算法可归纳为两大类，一是产生频繁项集候选项的 算法，二是不产生候选项的算法。在今后几年内，就关联规则的挖掘可以在下 面一些问题上做进一步的研究：将o l a p 和关联规则相结合的问题；在处理 极大量的数据时，如何提高算法效率的问题；生成结果的可视化及对非结构化 数据的挖掘。 1 3 论文研究的主要内容 首先介绍了关联规则的研究情况，提出了关联规则的分类及各种关联算法。 通过对典型关联算法进行分析，给出了对关联算法进行优化的思想，然后列举 了几个关联算法的应用，最后展望了关联规则数据挖掘的未来方向。 3 武汉理工大学硕士学位论文 第2 章数据挖掘技术 今天的人们已经拥有了大量的数据，这些以难以想象的高速度收集的数据 被存贮在超大规模的数据库中，远远超出了人们能理解它的能力，造成“数据 丰富而信息贫乏”。结果是数据库往往变成了“数据的坟墓”，很少被人访问， 决策更多地不是依赖信息，而是依赖决策者的直觉。因此，人们迫切希望改善 “数据丰富而信息贫乏”的情况，将这些数据转化为有用的知识和信息。在这 样的背景下产生了数据挖掘这个新兴学科并迅速成为信息科学中的热门研究领 域，受到广泛的关注。 数据挖掘( d a t am i n i n g ) 又被称作从数据库中发现知识k d d ( 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 研究逐步走向深入，数据挖掘和知识发现的研究已经形 成了三项强大的技术支柱：数据库、人工智能和数理统计。k d d 大会程序委员 会曾经由这三个学科的权威人物同时来任主席。目前k d d 的主要研究内容包括 基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表示 方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以及 网上数据挖掘等。 许多学者认为数据挖掘和k d d 是等价的概念，人工智能领域习惯称为k d d ， 而数据库领域习惯称呼为数据挖掘；也有学者把k d d 看作是发现知识的完整过 程，而将数据挖掘视为其中的一个基本步骤。图2 一l 示意了知识发现的主要过 4 武汉理工大学硕士学位论文 程，这里我们将数据挖掘作为知识发现的一个重要步裂矧。 图2 1 数据挖掘视为知识发现过程的一个步骤 知识发现过程包括数据清理、数据集成、数据选择、数据变换、数据挖掘、 模式评估和知识表示。数据清理就是消除噪声或不一致数据；数据集成是把多 种数据源组合在一起；数据选择是从数据库中检索与分析任务相关的数据；数 据变换是数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作：数据挖 掘是使用智能方法提取数据模式；模式评估是根据某种兴趣度度量，识别表示 知识的真正有趣的模式；知识表示是使用可视化的知识表示技术，向用户提供 挖掘的知识。我们可以将前4 个步骤统称为数据预处理过程( d a t a p r e p r o c e s s i o n ) 。 2 1 数据挖掘的知识 数据挖掘所发现的知识晟常见的有以下五类 2 1 1 广义知识( g e n e r a iiz a t i o n ) 广义知识指类别特征的概括性描述知识。根据数据的微观特性发现其表征 的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同 性质，是对数据的概括、精炼和抽象。 5 武汉理_ 上大学硕士学位论文 广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的归约 等。数据立方体还有其他一些别名，如“多维数据库”、“实现视图”、“o l a p ” 等。该方法的基本思想是实现某些常用的代价较高的聚集函数的计算，诸如计 数、求和、平均、最大值等，并将这些实现视图储存在多维数据库中。既然很 多聚集函数需经常重复计算，那么在多维数据立方体中存放预先计算好的结果 将能保证快速响应，并可灵活地提供不同角度和不同抽象层次上的数据视图。 另一种广义知识发现方法是加拿大s i m o n f r a s e r 大学提出的面向属性的归约方 法。这种方法以类s q l 语言表示数据挖掘查询，收集数据库中的相关数据集， 然后在相关数据集上应用一系列数据推广技术进行数据推广，包括属性删除、 概念树提升、属性阈值控制、计数及其他聚集函数传播等。 2 1 2 关联知识( a s s o c i a t l o n ) 它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性 之间存在关联，那么其中项的属性值就可以依据其他属性值进行预测。最为 著名的关联规则发现方法是r a g r a w a l 提出的a p r i o r i 算法。 2 1 3 分类知识( c i a s s i f i c a t i o n & c i u s t e r l n g ) 它反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知 识。最为典型的分类方法是基于决策树的分类方法。它是从实例集中构造决策 树，是一种有指导的学习方法。该方法先根据训练子集( 又称为窗口) 形成决 策树。如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到窗 e l 中，重复该过程一直到形成正确的决策集。最终结果是一棵树，其叶结点是 类名，中间结点是带有分枝的属性，该分枝对应该属性的某一可能值。最为典 型的决策树学习算法是i d 3 ，它采用自顶向下不回溯策略，能保证找到一个简 单的树。算法c 4 5 和c 5 0 都是i d 3 的扩展，它们将分类领域从类别属性扩展 到数值型属性。 数据分类还有统计、粗糙集( r o u g hs e t ) 等方法。线性回归和线性辨别分 6 武汉理工大学硕士学位论文 析是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。 最近也有人研究使用神经网络方法在数据库中进行分类和规则提取。 2 1 4 预测型知识( p r e d i c t i o n ) 它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也可 以认为是以时间为关键属性的关联知识。 目前，时间序列预测方法有经典的统计方法、神经网络和机器学习等。1 9 6 8 年b o x 和j e n k i n s 提出了一套比较完善的时间序列建模理论和分析方法。这些 经典的数学方法通过建立随机模型，如自回归模型、自回归滑动平均模型、求 和自回归滑动平均模型和季节调整模型等，进行时间序列的预测。由于大量的 时间序列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化，因 此，仅仅通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法 完成准确的预测任务。为此，人们提出了基于统计学和基于精确性的再训练方 法，当发现现存预测模型不再适用于当前数据时，对模型进行重新训练，获得 新的权重参数，建立新的模型。也有许多系统借助并行算法的计算优势进行时 间序列预测。 2 1 5 偏差型知识( d e v i a t i o n ) 偏差型知识( d e v i a t i o n ) 是对差异和极端特例的描述，揭示事物偏离常规的 异常现象，如标准类外的特例，数据聚类外的离群值等。 所有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升， 从微观到中观、到宏观，以满足不同用户不同层次决策的需要。 2 2 数据挖掘的主要流程 数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的、 有效的、可实用的信息，并使用这些信息做出决策或丰富知识。 数据挖掘环境可如下图2 2 所示： 武汉理工大学硕士学位论文 用户 图2 - 2 数据挖掘环境 数据挖掘主要包括以下步骤，如图3 3 所示【州，其中各步骤的大体内容为： 1 确定业务对象 清晰地定义出业务问题。认清数据挖掘的目的是数据挖掘的重要一步。挖 掘的最后结构是不可预测的，但要探索的问题应是有预见的。 2 数据准备 ( 1 ) 数据的选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数 据挖掘应用的数据。 ( 2 ) 数据的预处理 研究数据的质量，为进一步的分析做准备，并确定将要进行的挖掘操作的类 型。 ( 3 ) 数据的转换 将数据转换成一个分析模型。这个分析模型是针对挖掘算法建立的。建立 一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 3 数据挖掘 对所得到的经过转换的数据进行挖掘。除了选择合适的挖掘算法外，其余 一切工作都能自动地完成。 4 结果分析 解释并评估结果。其使用的分析方法一般应以数据挖掘操作而定，通常会 用到可视化技术。 5 知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 8 武汉理工大学硕士学位论文 数据集成、选择预处理转换 挖掘结果表示和解释 数据源i 舅堡塑一j 蓼咎墨j 燮一j 一蔓篓曼墼塑i 堕j 知识 图2 - 3 数据挖掘主要流程 2 3 常见数据挖掘分析方法 目前数据挖掘技术在网络安全领域的主要应用有：对安全检测对象的海量 审计数据的分析，例如网络连接流量的分析，主机日志分析等等；对安全检测 对象的行为数据分析，例如基于用户命令序列的行为分析，对用户邮件模式的 行为分析等 对安全系统报警事件的数据分析等。在特定的问题中，数据挖掘 的分析方法有一定的区别，这主要取决于数据的类型和规模，以及求解的目标。 目前数据挖掘分析方法中常用的有：关联分析、序列分析、分类分析、聚类分 析。 2 3 1 关联分析( a s s o c ia t i o na n a i y s is ) 关联分析就是要发现关联规则，找出给定数据集中数据项之间的联系。也 就是给定一组i t e m 和一个记录集合，通过分析记录集合，推导出i t e m 间的相 关性。关联规则是形式如下的一种规则“在购买面包和黄油的顾客中，有9 0 的人同时也买了牛奶”( 面包+ 黄油= 牛奶) 。用于关联规则发现的主要对象是事 务数据库( t r a n s a c t i o n a ld a t a b a s e s ) 。一般用信任度( c o n f i d e n 鳓和支持度( s u p p o r t ) 来描述关联规则的属性。关联分析的目的是从己知的事务集w 中产生数据项集 之间的关联规则，即同一条审计记录中不同字段之间存在的关系，同时保证规则 的支持度和信任度大于用户预先指定的最小支持度和最小信任度。发现关联规则 要经过以下三个步骤：连接数据，做数据准备；给定最小支持度和最小信任度， 利用数据挖掘工具提供的算法发现关联规则；可视化显示、理解、评估关联规则。 9 武汉理工大学硕士学位论文 设i = i l ，i 2 ，i 。 为数据项集合，d 为与任务相关的数据集合，也就是 一个事务数据库，其中的每个事务t 是一个数据项子集，即t i ：每个事务均 包含一个识别编号t i d 。设a 为一个数据项集合，当且仅当a c t 时，称事务 t 包含a 。一个关联规则就是具有“a b ”形式的蕴含式；其中有a c i ，b c i ， 且a n b = g 。如果a b 在事务数据集d 中成立，且具有s 支持度和c 信任度。 这就意味着事务数据集d 中有s 比例的事务t 包含a u b 数据项；且事务数据 集d 中有c 比例的事务t 满足“若包含a 就包含b 条件”。【2 7 】具体描述是： s u p p o r t ( a b ) = p ( a u t 3 ) c o n f i d e n c e ( a b ) = p0 3 l g ) 如果不考虑关联规则的支持度和信任度，那么在事务数据库中存在无穷多 的关联规则。事实上，人们一般只对满足一定的支持度和信任度的关联规则感 兴趣。一般称满足一定要求的( 如较大的支持度和信任度) 的规则为强规则。因 此，为了发现出有意义的关联规则，需要给定两个阀值：最小支持度( m i n _ s u p ) 和最小信任度( m i nc o n f ) 。前者即用户规定的关联规则必须满足的最小支持度， 它表示了一组项目集在统计意义上的需满足的最低程度；后者即用户规定的关 联规则必须满足的最小信任度，它反应了关联规则的最低可靠度。 关联规则的发现可分为两步。第一步是迭代识别所有的频繁项目集，要求 频繁项目集的支持度不低于用户设定的最低值；第二步是从频繁项目集中构造 信任度不低于用户设定的最低值的规则。识别或发现所有频繁项目集是关联规 则发现算法的核心，也是计算量最大的部分。常用的算法有a p r i o r i ，s t e m ，a i s ， d h p 。 2 3 2 序列分析( f r e q u e n te p i s o d ea n a i y s is ) 序列模式与关联模式相仿，不同的是它处理不同记录之间属性集的关联关 系，把数据之间的关联性与时间联系起来。为了发现序列模式，不仅需要知道 事件是否发生，而且需要确定事件发生的时间。序列模式分析的侧重点在于分 析数据间的前后序列关系。序列分析描述的问题是：在给定交易序列数据库中， 1 0 武汉理工大学硕士学位论文 每个序列按照交易时间排列成一组交易集，挖掘序列函数作用在这个交易序列 数据库上，返回出现的高频序列。例如入侵行为发生的先后关系常常有一定的 规律，黑客在入侵前先进行端口扫描然后再进行猜测密码的攻击的过程就可以 用序列模式来描述。序列模式数据分析有以下几种形式： 1 趋势分析 假设数据由系统性模式( 可辨识的成分集合) 和使模式难以辨识的随机噪声 构成。序列模式分析技术通常包括某种形式的噪声滤波以使模式更突出。趋势 分析通常包括某种形式的局部平均运算( 1 0 c a la v c r a g i n g ) ，最常用的是移动平均 值，用相邻的n 个值的简单或加权平均值代替均值，目的是减少奇异点的影响。 奇异点存在时，对于相同宽度平滑窗口，可以得到更光滑和更可靠的曲线。主 要缺点是不存在明显的奇异点时曲线更锯齿化。 2 周期分析 周期性依赖形式的定义为序列中每个元素i 和第i - k 个元素之间的k 阶相关 性依赖，以自相关( 该两项之间的相关) 来衡量，k 称为延迟。测量误差不是很大 时，周期性直观地表现为序列遵循每k 个元素重复的模式。时间序列的周期性 可能是不清晰的。 3 子序列分析 在序列模式数据中查找相似的子序列。将序列分到若干窗口中，通过离散 傅立叶变换的系数抽取特征。 4 相继模式分析 发现序列之间的关联规则，如“a 股票股价上升后的两个交易日内b 股票 价格也上升”。 挖掘序列模式通常分为以下五个步骤：( 1 ) 排序阶段，以事务的主题为主 键，事务时间为次键，对原始数据库进行排序，将其转换为主体序列的数据库。 ( 2 ) 大数据项阶段，找出所有的大数据项集l ，并把大数据项集映射为一组相 邻的整数，每个大数据项对应一个整数。( 3 ) 转换阶段，将数据库中主体序列 的每一次事务用该事物包含的大数据项集i t e m s e t s 代替。( 4 ) 序列阶段，利用 武汉理工大学硕士学位论文 大数据项集发掘序列模式。( 5 ) 序列最高化阶段，找出所有序列模式的最高序 列集。 其中，序列阶段是序列分析的关键阶段，按照技术方式的不同，序列挖掘 算法分为以下两大类：( 1 ) c o u n t - m l 算法，通过对所有的大序列进行计数来 计算支持度，包括非最高序列，代表算法是a p r i o r i a l l 。( 2 ) c o u n t s o m e 算法， 通过避免或减少对那些被更长序列所包含的序列进行计数来提高系统性能，代 表算法是a p f i o r i s o m e 和d y u a m i c s o m e 。【孤3 5 j 2 3 3 分类分析( c l a s s i f i c a t i o na n a i y s j s ) 分类在数据挖掘中是一项非常重要的任务，目前在商业中应用最多。分类 的目的就是要建立一个能够将数据库中的数据项映射到给定类别的分类器或分 类模型。分类和回归都可用于预测。预测的目的是从历史数据记录中自动推导 出对给定数据的推广描述，从而能对未来数据进行预测。和回归方法不同的是， 分类的输出是离散的类别值，而回归的输出则是连续数值。 学习分类器之前，首先要提供一个训练数据集( t r a i n i n gd a t as e t ) 作为分类 算法的输入。训练数据集中每一条数据记录都有己知的类型标识与之相关联， 而且训练数据集中的数据记录与实际数据集中的数据记录具有相同的数据项。 分类算法对训练数据集进行分析，提取数据记录的特征属性，为每一种类型标 识生成精确的分类规则描述。分类规则在测试数据集( t e s td a t as e t ) 上进行预测 精度评估后，才能用于对实际数据集中的数据记录进行分类。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计 方法包括贝叶斯法和非参数法( 近邻学习或基于事例学习) ，对应的知识表示 则为判别函数和原型事例：机器学习方法包括决策树法和规则归纳法，前者对 应的表示为决策树或判别树，后者则一般为产生式规则；神经网络方法主要是 b p 算法，它的模型表示是前向反馈神经网络模型( 由代表神经元的节点和代表 连接权值的边组成的一种体系结构) ，b p 算法本质上是一种非线性判别函数。 另外，最近又兴起了一种新的方法：粗糙集( t o u g hs e t ) ，其表示是产生式规则。 武汉理工大学硕士学位论文 不同的分类器有不同的特点。有三种分类器评价或比较尺度：预测准确度、 计算复杂度、模型描述的简洁度。预测准确度是用得最多的一种比较尺度，特 别是对于预测型分类任务。计算复杂度依赖于具体的实现缅节和硬件环境。在 k d d 中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非 常重要的一环节。对于描述型的分类任务，模型描述越简洁越受欢迎，例如，采 用规则表示的分类器构造法就更有用，而神经网络方法产生的结果就难以理解。 分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺值，有的 分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的是连续值或 混和式的。目前普遍认为不存在某种方法能适合于各种特点的数据。 数据分类的应用很广泛，算法也很多，常用的主要有：r i p p e r ，1 d 3 ，c 4 5 ， c a r t 等。 2 3 4 聚类分析( c l u s t e r i n ga n a l y s i s ) 当挖掘任务面临缺少领域知识或领域知识不完整的数据集合时，采用聚类 分析技术，可以将无标识数据对象自动划分为不同的类，并且可以不受人的先 验知识的约束和干扰，从而获取属于数据集合中原本存在的信息。 聚类( c l u s t e r i n g ) 是一个将数据集划分为若干组( c l a s s ) 或类( c l u s t e r ) 的过程，并使得同一组内的数据对象具有较高的相似度，而不同组中的数据对 象则是不相似的【矧。相似或不相似的度量是基于数据对象描述属性的取值来确 定的，通常就是利用( 各对象间) 距离来进行描述的。在机器学习中。聚类分 析属于一种无监督的学习方法。与分类学习不同，无监督学习不依赖事先确定 的数据类别，以及标有数据类别的学习训练样本集合。正因为如此，聚类分析 又是一种通过观察学习( 1 e a r n i n gb yo b s e r v a t i o n ) ，而不是示例学习( 1 e a r n i n gb y e x a m p l e ) 的方法。聚类分析的基本指导思想是最大程度地实现类中对象相似度 最大，类问对象相似度最小。 传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、 有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较 武汉理工大学硕士学位论文 的聚类，它需要考察所有的个体才能决定类的划分，因此它要求所有的数据必 须预先给定，而不能动态增加新的数据对象。聚类分析方法不具有线性的计算 复杂度，难以适用于数据库非常大的情况。 在很多人工智能文献中，聚类也称概念聚类，因为这里的距离不再是统计 方法中的几何距离，而是根据概念的描述来确定的。在概念聚类方法中，仅当 一组对象可以由一个概念所描述时，这些对象方才能构成一个类。这与基于几 何距离表示相似程度并进行聚类的传统聚类方法有所不同。概念聚类方法主要 包含两部分内容：一是发现适当的类，二是根据每个类形成相应的特征描述， 这与在分类学习中的方法类似。追求较高类内相似度和较低类间相似度的指导 原则同样适用于概念聚类。通过聚类人们可以识别密集的和稀疏的区域，从而 发现全局的分布模式，以及数据属性之间的有趣的相互关系。 主要的聚类方法有以下几大类： 1 划分方法 给定一个包含n 个对象的数据集，划分方法将数据集划分为k 个子集。其 中每个子集均代表一个聚类( k s n ) 。也就是说，将数据分为k 组，这些组满 足以下要求：( 1 ) 每组至少包含一个对象； ( 2 ) 每个对象必须只能属于某一 组。需要注意的是后一个要求在一些模糊划分方法中可以放宽。 给定需要划分的个数k ，一个划分方法创建一个初始划分，然后利用循环 再定位技术，即通过移动不同划分( 组) 中的对象来改变划分内容。为获得基 于划分聚类分析的全局最优结果就需要穷举所有可能的对象划分。为此大多数 应用采用两种常用启发方法： ( 1 ) k - m e a n s 算法，该算法中的每一个聚类均用 相应聚类中对象的均值来表示；( 2 ) k - m e d o i d s 算法，该算法中的每一个聚类 均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小 规模数据集以发现圆形或球状聚类时工作得很好。而在k - m e d o i d s 上进行扩展 的c i a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o nr a n d o m i z e ds e a r c h ) 算 法则能够分析处理大规模数据集。它采用基于随机抽样技术来确定可能的聚类， 以减少数据的处理量。 2 层次方法 1 4 武汉理工大学硕士学位论文 层次方法就是通过分解所给定的数据对象集来创建个层次。根据层次分 解形成的方式，可以将层次方法分为自下而上和自上而下两种类型。自下而上 的层次方法从每个对象均为一个( 单独的) 组开始，逐步将这些( 对象) 组进 行合并，直到组合并到了层次顶端或满足终止条件为止。自上而下层次方法从 所有对象均属于一个组开始，每一次循环将其( 组) 分解为更小的组，直到每 个对象构成一组或满足终止条件为止。 b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 方法 就是一个集成的层次聚类方法。它采用一种聚类特征树技术。聚类特征是有关 对象子集概要信息的一个三元组，是对给定子聚类统计信息的总结。b i r c h 方 法利用多阶段处理方式，努力在现有资源条件下产生最好的聚类。 3 基于密度方法 大多数划分方法是基于对象问距离进行聚类的。这类方法仅能发现圆形或 球状的聚类而较难发现具有任何形状的聚类。而基于密度概念的聚类方法实际 上就是不断增长所获得的聚类直到“邻近”( 数据对象或点) 密度小于一定阀 值( 如：一个聚类中的点数，或一个给定半径内必须至少包含的点数) 为止。 这种方法可以用于消除数据中的噪声，以及帮助发现任意形状的聚类。 d b s c a n ( d e n s i t y - b a s e ds p a t i a lc l u s t e r i n go fa p p l i c a t i o nw i t hn o i s e ) 就是 一个典型的基于密度方法，该方法根据密度阀值不断增长聚类。o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) 也是一个基于密度方法， 该方法提供聚类增长顺序以便进行自动或交互式数据分析。 4 基于网格方法 基于网格方法将对象空间划分为有限数目的单元以形成网格结构。所有聚 类操作均是在这一网格结构上进行的。这种方法主要优点就是处理时间由于与 数据对象个数无关而仅与划分对象空间的网格数相关，从而显得相对较快。 s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 就是一个典型的基于网格的方法，它利 用网格多分辨率来完成聚类分析。 5 基于模型方法 武汉理工大学硕士学位论文 基于模型方法就是为每个聚类假设一个模型，再去发现符合相应模型的数 据对象。一个基于模型的算法可以通过构造一个描述数据点空间分布的密度函 数来确定具体聚类。它根据标准统计方法并考虑到“噪声”或异常数据，可以 自动确定聚类个数。基于模型的聚类方法主要有两种：统计方法和神经网络方 法。 2 4 本章小结 本章以数据挖掘为主线，首先介绍了数据挖掘的一些基本概念，再具体阐 述了数据挖掘中的知识类型和挖掘的主要流程，最后重点介绍了常见的四种数 据挖掘分析方法：关联分析、序列分析、分类分析和聚类分析，为在入侵检测 系统中引入数据挖掘技术提供了理论基础。 1 6 武汉理工大学硕士学位论文 第3 章关联规则算法分析 数据挖掘是指从大型数据库或数据仓库中提取隐含的、先前未知的、对决 策有潜在价值的知识和规则。它是人工智能和数据库发展相结合的产物，是国际 上数据库和信息决策系统最前沿的研究方向之一。数据挖掘主要的算法有分类 模式、关联规则、决策树、序列模式、聚类模式分析、神经网络算法等等。关 联规则是数据挖掘领域中的一个非常重要的研究课题，广泛应用于各个领域，既 可以检验行业内长期形成的知识模式，也能够发现隐藏的新规律。有效地发现、 理解、运用关联规则是完成数据挖掘任务的重要手段，因此对关联规则的研究具 有重要的理论价值和现实意义。 r a g r a w a l 等人于1 9 9 3 年首先提出了挖掘颞客交易数据库中项集问的关联 规则问题，其核心方法是基于频集理论的递推方法。此后人们对关联规则的挖掘 问题进行了大量研究，包括对a p r i o r i 算法优化、多层次关联规则算法、多值属 性关联规则算法、其他关联规则算法等，以提高算法挖掘规则的效率。 3 1 关联规则基本原理 设i = i1 ，i2 ，im ) 是m 个不同的项目组成的集合，给定一个事务数据库 d ，其中的每一个事务t 是由i 中的一些项目组成的集合，即t c i , t 有一个唯一 的标志符t i d 。若项集x ci 且x c t ，则事务集t 包含项集x 。一条关联规则就 是形如x y 的蕴涵式，其中x c l ，y c i ，x f 3 y = 。关联规则x y 成立的条件：a 它具有支持度s ，即事务数据库d 中至少有s 的事务包含xuy 。b 它具有置信 度c ，即在事务数据库d 中包含x 的事务至少有c 同时也包含y 。关联规则挖 掘问题就是在事务数据库d 中找出具有用户给定的最小支持度m i n s u p 和最小 置信度m i n c o n f 的关联规则。关联规则挖掘问题可以分解为以下2 个子问题 【1 ，2 】。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 ) 利用强项 1 7 武汉理工大学硕士学位论文 集生成关联规则。对于每个强项集a ，若ba ，b ，且s u p p o r t ( a ) s u p p o r t ( b ) i m in c o n f ，则有关联规则b ( a b ) 。 3 2 典型关联规则算法分析 r a g r a w a l 等提出了关联规则挖掘问题以后，一批有效的挖掘关联规则的 算法在过去几年中得到了长足的发展。到目前为止，其主要研究方向有：基于规 则中涉及到的数据维数的挖掘算法，基于规则中数据的抽象层次的挖掘算法，基 于规则中处理变量类别的挖掘算法，其他关联规则算法等。 3 2 1 基于规则中涉及到的数据维数的挖掘算法 按照关联规则中涉及到的变量数目可以把关联规则分为单维关联规则和多 维关联规则。单维