（管理科学与工程专业论文）数据流频繁模式和分类挖掘算法研究.pdf

数据流频繁模式和分类挖掘算法研究 数据流频繁模式和分类挖掘算法研究 摘要 近年来，数据流广泛出现在多种应用领域中，如传感器网络、股 票分析、网络故障监测等，与传统数据不同，数据流具有大量、快速 连续到达、要求快速响应、一次扫描等特点，因此传统的数据挖掘技 术不能直接应用到数据流上。利用有限系统资源对数据流进行快速处 理以获取有用信息，为数据挖掘及其应用研究带来了新的机遇和挑 战。本文主要对滑动窗口模型下的数据流中频繁模式和分类挖掘算法 进行了研究。 首先，对传统的数据挖掘相关理论和经典算法进行了深入分析， 尤其是频繁模式挖掘算法a p r i o r i 、f p g r o w t h 算法和决策树分类i d 3 算法，并取其之长运用到数据流相关任务的挖掘上，并一一编程实现， 深化对算法的认识。 然后，对数据流的特点及其三种模型进行系统研究，其中滑动窗 口模型最符合真实应用，并在静态挖掘算法的基础上加以吸收创新， 设计并实现滑动窗口模型下适合数据流的单遍扫描算法一频繁模式 挖掘算法s o a 、s f p 和分类算法s d t 、s f p c 。 最后，本文设计并实现b s 结构的挖掘平台，在这个平台上对以 上几种封装后的算法进行测试，实验表明各算法都具有较高的准确性 数据流频繁模式和分类挖掘算法研究 和时间效率。此外，本文还分别分析了频繁模式和分类挖掘在网络监 控中的实际应用问题。 关键词：数据挖掘，数据流，频繁模式，分类，滑动窗口 数据流频繁模式和分类挖掘算法研究 r e s e a r c h o fm i n i n gf r e q u e n tp a t t e r n sa n d c l a s s i f i c a t i o no nd a t as t r a e m s a b s t r a c t i nr e c e n ty e a r s , d a t as t r e a m sw e r eg e n e r a t e di nav a r i e t yo f a p p l i c a t i o n s , s u c ha s s e n s o rn e t w o a s , s t o c ka n a l y s i s ，n e t w o r km o n i t o r i n g d i f f e r e n tf r o mt r a d i t i o n a ld a t a , t h ed a t as t r e a mi sa b o u n d e d ，r a p i d , a n dc o n t i n u o u s t r a d i t i o n a ld a t am i n i n g t e c h n i q u e sc a nn o tb ea p p l i e dd h 陪c t t yt ot h ed a t as t r e a m u s i n gt h el i m i t e ds t o r a g e s p a c et oh a n d l ed a t as t r e a mf o rr a p i da c c e s st ou s e f u li n f o r m a t i o nb r i n go u tn e w o p p o m m i t i e sa n dc h a l l e n g e st or e s e a r c h e so nd a t am i n i n ga n di t sa p p l i c a t i o n s t h i s p a p e ra i m e d a tf r e q u e n t p a t t e r nm i n i n ga n dc l a s s i f i c a t i o na l g o r i t h m s f o rt h e h i g h - s p e e dd a t as t r e a m f i r s t , w es t u d i e dt h et r a d m o n a lt h e o r ya n dt h ec l a s s i c a ld a t am i n i n ga l g o r i t h n m , i n c l u d i n gf r e q u e n tp a t t e r n sm i n i n ga l g o r i t h ma p r i o r i , f p g r o w t ha n dc l a s s i f i c a t i o n a l g o r i t h mi d 3 s e c o n d ，w el e a m e dt h ec h a r a c t e r i s t i c so f t h eo a t s t r e a ma n di t sm o d e l si nw h i c h t h es l i d i n gw i n d o wm o d e li st h eb e s tt ot h er e a la p p l i c a t i o n s t h c r c f o r e ，b a s e do i lt h e t r a d i t i o n a ls t a t i c a l g o r i t h m s , w ep r o p o s e d a n di m p l e m e n t e ds o 雠s i n g l e - p a s s a l g o r i t h m si n c l u d i n gf r e q u e n tp a t t e mm i n i n ga l g o r i t h m ss o a ，s f pa n dc l a s s i f i c a t i o n a l g o r i t h m ss d t , s f p cu n d e r t h es l i d i n gw i n d o wm o d e l f i n a l l y ，w ed e s i g n e da n di m p l e m e n t e dt h em i n i n gp l a t f o r ms m i n e rw i t hb s s t r u c t u r ew h e r et h ea l g o r i t h m sp r o p o s e da b o v ew e r et e s t e d , a n dt h ee x p e r i m e n t ss h o w t h a tt h e yh a v eah i g l ll e v e lo f a c c u r a c ya n dt i m ee f f i c i e n c y i na d d i t i o n , t h i sp a p e ra l s o 数据流频繁模式和分类挖掘算法研究 a n a l y z e dt h ea p p l i c a t i o n so ff r e q u e n tp a t t e r nm i n i n ga n dc l a s s i f i c a t i o ni nn e t w o r k m o n i t o r i n g k e y w o r d s ：d a t am i n i n g ，d a t as t r e a m , f r e q u e n tp a t t e r n , c l a s s i f i c a t i o n , s l i d i n g w i n d o w 数据流频繁模式和分类挖掘算法研究 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得浙江工商大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 签名：日期：年月 e t 数据流频繁模式和分类挖掘算法研究 第一章绪论 1 1 课题的背景和意义 近年在传感器网络、网络监控、w e b 日志管理、股票波动跟踪、网页点击流 管理、电话呼叫记录管理等大量应用领域中产生了一种新型数据一数据流，数据 流中蕴含了大量的有用信息，从数据流中挖掘出未知的、有价值的模式或规律对 网络安全、企业决策等将产生积极影响。数据流挖掘技术的潜在应用十分广泛， 在政府管理决策、商业经营决策和信息安全等很多领域都可以找到数据流挖掘技 术的应用。 数据流具有连续、快速频繁的变化、大量甚至无限、要求快速响应、一次扫 描等特点，尽管传统的数据挖掘已经取得相当多的成果，但是它们是基于静态的、 不经常进行更新的数据库，存在一些问题： ( 1 ) 需多次扫描，无法满足数据流算法单遍扫描韵需要； ( 2 ) 效率较低，不能与数据流的速度同步； ( 3 ) 占用资源过多，需要大量内存空间及i 0 开销。 因此，传统的数据挖掘算法不能直接应用于数据流挖掘，必须改造原有的算 法或者设计新的数据挖掘算法来适应数据流模型。 1 2 国内外研究现状 数据流挖掘成为近几年研究的热点，国外成立了很多研究小组，在分类方面 已经取得了很多成果。d o m in g o s 提出了基于h o e f f d i n g 树的快速决策树学习算法 v f d t 0 】。h u l t e n 在v f d t 基础上，提出了挖掘数据流的决策树算法c v f d t 【2 】，在 保持当前决策树的同时生成可选子树，必要时用子树替代当前决策树，大大提高 了效率，且保证了准确度。h a i x u nw a n g 等人提出了数据流上的多分类器构造算 法【3 】。 相比之下，频繁模式挖掘的研究却比较困难。g s m a n k u 等给出了两个算法 s t i c k ys a m p l i n g 和l o s s yc o u n t i n g 【4 】，在设定支持度m 值和错误因子阀值下，给出 了求解单个有效项的有效算法。v i t t e r j s 提出以结果稳定性为依据，适当推迟 数据流频繁模式和分类挖掘算法研究 更新时机，增量式挖掘最大频繁项目集的z i g z a g 算法1 5 】。s c h l i m e r 提出的u l i 算法是较旱增量挖掘算法t 6 t 。u t g o f f 提出了最有代表性的运用移动窗口法和抽样 法在数据流上计算超过用户给定阀值的频率统计数的算法1 7 j 。h o e f f d i n gw 提出了 一种在倾斜时问窗口框架下采用一种与f p t r e e 相似的数据结构存储模式维护频 繁模式的方法【引。p e ij 提出了频繁闭模式挖掘的c l o s e t 算法1 9 1 。一些研究者们 也提出了利用关联规则来进行分类的方法1 1 ，1 2 1 。 在国内，这方面的研究刚刚起步，文献资料也比较少，有些学校和研究所正 在对数据流进行研究。王鹏等提出了一种数据流上的基于频繁模式的分类算法一 c a p e t 】，c a p e 通过数据流中的频繁模式进行分类，在压缩数据的同时保存了数 据中的分类信息。张昕等提出一种改进的字典树结构一i l t r e e 【l4 1 ，并在其基础 上提出一种新的启发式算法f p i l - s t r e a m ，在更新模式和生成新模式的过程中， 可以快速定位历史模式。复旦的周傲英等提出了一种基于散列的算法h c o u n t 和改 进后h c o u n t 木 1 5 l ，算法能在允许项插入、删除的动态数据流环境下维护超过阀 值的频繁项集，该方法不需要预知数据的范围，耗费内存量较少。宋国杰等提出 了一个启发式分段求解方法i ”j ，将数据流分成不同的段，利用h o e f d i nb o u n d 估 算满足求解精度的段长度，通过逐段的迭代进行频繁模式的评估，最后估算出所 有的模式。徐利军等提出m g r d s 算法利用频繁集的产生集表达方式来挖掘基于整 个数据流的频繁集1 1 7 】。 1 3 研究内容及主要成果 数据流挖掘算法的研究是一项迫切的任务，早期的增量式数据挖掘算法可以 说是数据流挖掘算法的基础。增量式使已经建立好的数据模型可以重复使用，这 样就使挖掘数据流成为可能。本文在充分应用静态挖掘算法的有用成果基础上， 研究数据流模型特点，设计出数据流挖掘中一些关键算法，为数据流的分析提供 有力工具。 首先，研究数据流与传统数据的不同特点，对数据流模型的特点及其适用范 围进行分析。主要包括三种模型：界标模型、衰减模型、滑动窗口模型。由于滑 动窗口模型更接近于真实应用，本文主要对此模型展开研究，在有限的中央处理 2 数据流频繁模式和分类挖掘算法研究 器资源、内存与外存资源约束下，对数据流的扫描方法、存贮表达机制、更新方 式进行研究，提出数据流挖掘的形式化描述。 其次，对传统静态数据挖掘中的经典算法进行研究。本文特指挖掘频繁模式 的a p r i o r i 和f p - g r o w t h 算法和决策树分类i d 3 算法。 然后，在静态算法的基础上改进数据结构，提出了动态数据流中频繁模式挖 掘算法s o a 、s f p 和分类算法s d t 、s f p c ，并编程实现算法且进行实验性能分析。 再次，分析了动态数据流中频繁模式挖掘和分类算法在网络检测中的实际应 用问题。 最后，设计b s 结构的挖掘平台并实现软件。 1 4 本文的组织结构 本文共分为七章。 第一章是绪论部分。 第二章主要介绍式据挖掘相关理论。 第三章提出滑动窗口模型下基于f p - g r o w t h 和a p r i o r i 的式据流频繁模式挖 掘算法s f p 和s o a 。 第四章提出传统的决策树分类算法i d 3 应用到动态数据流中的s d t 算法和基 于s f p 数据流分类算法s f p c 。 第五章介绍数据流挖掘系统平台的设计与实现。 第流章分析频繁模式挖掘和分类在网络检测中的应用。 第七章总结与展望。 3 数据流频繁模式和分类挖掘算法研究 第二章数据挖掘相关理论 2 1 1 数据挖掘产生 2 1 数据挖掘 随着计算机与信息技术的飞速发展，人们面临着快速扩张的数据海洋，如何 有效利用这一丰富数据海洋的宝藏为人类服务，已经成为广大信息技术工作者所 关注的焦点之一。与f 1 趋成熟的数据管理技术与软件工具相比，人们所依赖的数 据分析工具功能，却无法有效地为决策者提供其决策支持所需要的相关知识，从 而形成了一种独特的现象“丰富的数据，贫乏的知识”。为有效解决这一问题，自 二十世纪8 0 年代开始，数据挖掘技术逐步发展起来。 2 1 2 数据挖掘定义 数据挖掘( d a t am i n i n g ，简称d m ) t t g l ，又称数据库中的知识发现( 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 ) ，就是从大量的、不完全的、有噪声的、模糊的、随机的 实际应用数据中，提取隐含在其中的、人们事先不知道的、但又潜在有用的信息 和知识的过程。数据挖掘的全过程定义描述如图所示。 数据挖掘仝过程 图2 1 数据挖掘全过程 4 数据流频繁模式和分类挖掘算法研究 如图所示，整个知识挖掘( k d d ) 过程是由若干挖掘步骤组成，而数据挖 掘仅是其中的一个主要步骤。整个知识挖掘的主要步骤有： 数据清洗，消除噪声或不一致数据； 数据集成，将多中数据源中的相关数据组合到一起； 数据选择，从数据库中检索与分析任五相关的数据； 数据转换，将数据转换或统一成适合挖掘的形式； 数据挖掘，知识挖掘的一个基本步骤，其作用就是利用智能方法挖掘数据 模式或规律知识； 模式评估，根据一定评估标准，识别表示知识的真正有意义的模式知识； 知识表示，利用可视化和知识表达技术，相用户展示所挖掘出的相关知识。 尽管数据挖掘仅仅是整个知识挖掘过程中的一个重要步骤，但“数据挖掘” 一词已被广泛使用并被普遍接受，因此本文也广义地使用“数据挖掘”一词来表示 整个知识挖掘过程，即数据挖掘就是一个从数据库、数据仓库或其它信息资源库 的大量数据中发掘出有用的知识。 2 1 3 数据挖掘功能 利用数据挖掘技术可以获得决策所需的多种知识，数据挖掘功能以及所能够 挖掘的模式类型说明描述如下： 概念与描述：特征化和区分 特征化是目标类数据的一般特征或特性的总汇。区分是将目标对象的一般特 征与一个或多个对比类对象的一般性比较。例如可以研究销售增加2 0 的产品的 特征。 关联分析 关联分析发现关联规则，这些规则展示属性值频繁的在给定数据集中一起 出现的条件。例如：可以通过对数据的分析得出啤酒 尿布的关联规则，即买 啤酒的人往往会买尿布。 分类与预测 分类是这样的过程，它找出描述并区分数据类或概念的模型，以便能使用模 型预测类标记未知的对象类。当被预测的值是数值数据时，通常称为预测。 5 数据流频繁模式和分类挖掘算法研究 聚类分析 聚类分析数据对象，而不考虑已知的类标记。 孤立点分析 孤立点分析也称作孤立点挖掘，挖掘数据库中那些与数据的义般行为或模型 不义致的数据对象。 演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。如对 股票交易数据的演变分析可以识别整个股票时常和特定公司的股票演变规律。这 种规律可以帮助预测股票市场价格的未来走向，帮助对股票投资作出决策。 数据挖掘在金融业、零售业和电信业等将得到广泛的应用。 在金融领域，管理者可以通过对客户偿还能力以及信用的分析，进行分类， 评出等级。从而可减少放贷的麻木性，提高资金的使用效率。同时还可发现在偿 还中起决定作用的主导因素，从而制定相应的金融政策。更值得一提的是通过对 数据的分析还可发现洗黑钱以及其他的犯罪活动。 在零售业，数据挖掘可有助于识别顾客购买行为、发现顾客购买模式和趋势， 改进服务质量，取得更好的顾客保持力和满意程度，提高货品销量比率，设计更 好的货品运输与分销策略，减少商业成本。 电信业已经迅速地从单纯的提供市话和长话服务演变为综合电信服务，如语 音、传真、寻呼、移动电话、图像、电子邮件、计算机和w e b 数据传输以及其 他的数据通信服务。电信、计算机网络、因特网和各种其他方式的通信和计算的 融合是目前的大势所趋。而且随着许多国家对电信业的开放和新兴计算与通信技 术的发展，电信市场正在迅速扩张并越发竞争激烈。因此，利用数据挖掘技术来 帮助理解商业行为、确定电信模式、捕捉盗用行为、更好地利用资源和提高服务 质量是非常有必要的。分析人员可以对呼叫源、呼叫目标、呼叫量和每天使用模 式等信息进行分析还可以通过挖掘进行盗用模式分析和异常模式识别，从而可尽 早的发现盗用，为公司减少损失。 6 数据流频繁模式和分类挖掘算法研究 2 2 1 关联规则概述 2 2 关联规则挖掘 关联规则是数据挖掘技术所能发现的非常重要的一类规则，它首先由 a g r a w a l i m i e l i s k i 和s w a m i u 于1 9 9 3 年提出【1 9 1 ，用于发现大量数据中数据项之间 的有趣联系。从大量的商务事务中发现有趣的关联联系，可以帮助许多商务决策 的制定。 挖掘关联规则的一个典型应用就是市场购物篮分析。该过程通过发现顾客放 入购物蓝中不同商品( 项) 之间的关系，从而找出顾客购买商品的行为模式，帮助 商家制定针对性的市场营销策略，进而把它应用于商品货架设计、货存安排以及 根据购买模式对用户进行分类等。 2 2 2 关联规则基本术语和相关概念 定义2 - 1 设i - i l ，i 2 i 3 ，i 。) 是数据项的集合，与任务相关的数据集合d 是数据库事务集合，其中的每个事务t 是一个数据项子集，即t i ，每个事务 均有唯一一个标志符记作t i d 。设x 是一个项集，事务t 包含x 当且仅当x c _ t 。 一个关联规则是形如x j y 的蕴涵式，其中x c i ，y d ，并且x n y = o 。 定义2 - 2 规则x 辛y 在事务数据库d 成立，具有支持度s ( s u p p o r t ) ，其中 s 是事务集中包含x 和y 的事务数与所有事务数之比，记为s u p p o r t ( x j v ) ，即 s u p p o r t ( x j y ) = p ( xu 规则支持度越高，说明出现的次数越多。 定义2 - 3 规则x j y 在事务集中具有黄信度c ( c o n f i d e n c e ) 是指包含x 和 y 的事务数与包含x 的事务数之比，记为c o n f i d e n c e ( x j y ) ，即 c o n f i d e n c e ( x j y ) ：p ( x m 置信度越高，说明这条规则越可靠。 给定一个事务集d ，挖掘关联规则问题就是寻找支持度和可信度分别大于用 户给定的最小支持度( m i n s u p ) 和最小可信度( f ) 的关联规则，同时满足小小支 持度和最小置信读的规则成为强规则。 数据流频繁模式和分类挖掘算法研究 项的集合称为项集( i t e m s e t ) 。包含k 个项的集合称为k 一项集。项集的出现频 率是包含项集的事务数，简称项的频率、支持数或计数。如果项集的频率大于或 者等于m i n s 。与d 中事务总数的乘积，则满足最小支持度，称它为频繁项集 ( f i e q u e n ti t e m s e t ) ，频繁k - 项集通常记为l k 。 关联规则的挖掘过程包含两步： 1 根据最小的支持度，在大量事务中找出所有的频繁项集。 2 根据最小的置信度，由频繁项集产生强关联规则。这一步比较容易，一般 经过第一步的筛寻后，频繁项集都不会很多，通过子集产生法就可以产生关 联规则，步骤如下： ( 1 ) 对于每个频繁项集l ，产生l 的所有非空子集； ( 2 ) 对于1 的每个非空子集s ，若s u p p o r t ( ! ) s u p p o r t ( s ) m i n 。f 则输出规则 s = ，( 1 一s ) 。 2 2 3 关联规则挖掘a p r i o f i 算法 r a k e s ha g r a w a l 等1 9 9 4 年提出了经典的a p r i o r ig 法i 2 0 j ，它是最有影响的挖 掘布尔关联规则频繁项集的算法，本算法的频繁项集查找使用一种逐层迭代的方 法，每层查找分为项集的连接和剪枝两个步骤。连接步骤是为了找k 项频繁项集 l k ，通过k - 1 项频繁项集l k 1 与自己连接产生候寻k - 项集的集合c k ；剪枝步骤 是扫描事务数据集，去掉那些支持度小于指定最小支持度的项集。 具体步骤：首先找出频繁l - 项集，记为l l ；l l 与l l 自身连接产生c 2 ，然后 对c 2 的所有事务项根据最小支持度进行剪枝后，产生k ；由此，不断迭代，直 到最后l k 为空集。 1 a p r i o r i 算法的主要步骤： ( 1 ) 扫描事务数据库中的每个事务，产生侯寻1 项集的集合c l ； ( 2 ) 根据最小支持度m 氓。，由侯寻l - 项集的集合c l ，产生频繁1 项集的集 合l l ； ( 3 ) 对k = l ； ( 4 ) 由l k 执行连接( l k o o l k ) 和剪枝操作，产生侯寻( k + 1 ) 项集的集合c k + l ； 8 数据流频繁模式和分类挖掘算法研究 ( 5 ) 根据最小支持度m i n , 。，由侯选( k + i ) - 项集的集合c k + t 产生频繁( k + i ) 项 集的集合l k + l ； ( 6 ) 若l k + l g ，则k 咄+ 1 ，跳往步骤( 4 ) ；否则，跳往步骤( 7 ) ； ( 7 ) 根据最小置信度m i n 。f ，由频繁项集产生强关联规则，结束。 2 下面是引用参考文献例中的a p r i o d 算法伪代码参考。 算法a p d o d 使用逐层迭代找出频繁项集 输入：事务数据库d ；最小支持度阈值。 输出：d 中的频繁项集l 。 方法： 1 1l z = f i n d _ 丘e q u e n t1i t e m s e t s ( d ) ； 2 ) f o r ( k = 2 ；l k - , o ；k + + ) 3 )c k = a p r o i r i g e n ( l k t , m i n _ s u p ) ； 4 1f o re a c ht r a n s a c t i o nt e d s c a ndf o rc o u n t 5 ) c t = s u b s e t ( c k ，d ； g e ts u b s e t so f tt h a ta r e c a n d i d a t e s 6 ) f o re a c hc a n d i d a t ec c t 7 ) c c o u n 什+ ； 8 ) 9 )h ； c c kic c o u n t m i n _ s u p ) 1 0 ) ) 1 1 ) r e t u r n l 2 u k h ； p r o c e d u r ea p r i o r i _ g e n ( l k 1 ：f r e q u e n t ( k - 1 ) - i t e m s e t ；m i n _ s u p ：s u p p o r t ) 1 ) f o re a c hi t e m s e the l k i 2 1f o re a c hi t e m s e t1 2 e l k - i 3 )i f ( 1 l 1 】= 1 2 1 】) ( 1 l k - 2 = 1 2 【i ( - 2 】) “h k - q 2 k - 2 ) t h e n 4 )c = l lo 。1 2 ；j o i ns t e p ：g e n e r a t ec a n d i d a t e s 5 ) i f h a s _ i n f r e q u e n t s u b s e t ( c ，l k - 1 ) t h e n 6)delete c ；p r u n es t e p ：r e m o v eu n f r e q u e n t c a d i d a t e g 数据流频繁模式和分类挖掘算法研究 ne l s e a d dc t o c k ； 8 ) 9 、r e t u r nc k ； p r o c e d u r eh a s _ i n f r e q u e n ts u b s e t ( c ：c a n d i d a t ek - i t e m s e t ；lk t ：f r e q u e n t ( k - 1 ) - i t e m s e t ) u s ep r i o r ik n o w l e d g e 1 ) f o re a c h ( k - 1 ) - s u b s e tso f c 劲 i f c 诺l k - it h e n 3 1 r e t u r nt r u e ； 4 1r e t u r nf a l s e ； 3 例子 e l e c t e c h 公司是一个跨国公司，它的一个事务数据库d 以及由a p r i o d 算法 产生频繁项集的过程如图2 2 所示。( 假设最小事务支持计数为2 ，即m i n s u p = 2 11 2 18 2 1 墁集 i 翼集 项集 项集计教 1 d 0 1a b d c l a b )a b )妇。b ) 5 t 0 0 2a b c d 顶壤 汁敦 l 1 a c a c 伯c ) 5 t 0 0 3 a 9项集计数 t 0 0 4a b c n * t b 8 a ) a m a ，町 ( a d )3 汁蠡 f c )7 捧琏 ( b 硅接 a e ) t a 耐 扫插t d 日 1 。0 0 5a ，c d 身挂 计啦 a ，e )2 - - 1 1 , , f b c + b ，c ) 伽。c )3 t a b d e d 3 讨 1 ：7a b e )2 田 ( b mb d ，伽d 2 b e ) t b e 伽e ) 2 t 0 0 8a c r 册 1 e f c 棚c m( c ，d ) 1 t m 佃 1 t 0 1 0b c c ，e ) ( c e c e 1 d ，e ) d 耐 d 时 1 1 u 1 c 口 c 3 l 2 项集 项集 计赣 伯由c a f b )5 a b ，maal 3 t a c )5 a b ，耐 项集 目# t i 项集 计敦l 项集i 计教f f j 贾集 剪杖c + 连接 剪桂 2 仁刮l a b d 脚 a d 3 a c d t a b c ) l 与卜b m 2i 啼硅 a b c ) - l a b ，町：2 广 a b 。m a e )2 a ，c 时 a ，b 。m b c 3 a d e t a b ，e ) a b 时 b d 2 b ，c m 伯e )2 i b ，c e ) 佃d e 图2 2a p d o f i 算法产生频繁项集过程 1 0 数据流频繁模式和分类挖掘算法研究 2 2 4 关联规则挖掘f p - g r o w t h 算法 在许多情况下，a 研o r i 算法大幅度压缩了侯选项集的大小，并产生很好的性 能。虽然进行了优化，a 研耐算法仍然无法克服它的一些固有缺陷： ( 1 ) 可能产生大量的侯选项集。若频繁1 项集的个数为1 0 0 0 0 ，则侯选2 项集 的个数将超过1 0 m ；若要发现长度为1 0 0 的频繁项集，则必将产生多达2 1 0 1 0 3 0 个侯选项集； ( 2 ) 无法对稀疏数据进行分析。对小于最小支持度m i i l s 。的事务无法进行处理， 若m i l l s i i 。设置过低，则算法效率又成了一个问题； ( 3 ) 需要多次重复扫描数据库。扫描的次数随着要发现的频繁项集长度的增加 而增加。 频繁模式增长( f r e q u e n t - p a t t e r ng r o w t h ) ，简称f p 增长，是由h a n , p e i 和y i n 于2 0 0 0 年提f l j 2 1 的，能够在不产生侯选项集的情况下产生所有的频繁项集。 采取一个两步骤分而治之的策略：第一遍扫描首先将数据库压缩为一棵频繁模式 树( f p t r e e ) ，同时保留项集的相关信息；然后，将压缩后的数据库分成一组条件 数据库( 一种特殊类型的投影数据库) ，每个条件数据库关联一个频繁项，再分 别对每个数据库挖掘。 1 生成频繁模式树 ( 1 ) 频繁模式树的生成步骤： ( a ) 扫描事务数据库d 一次，收集频繁项的集合f 和它们的支持度。对f 按 支持度降序排序，结果为频繁项表l 。 ( b ) 创建f p 树的根结点，以n u l l 标记它。对于t d b 中的每个事务t ，执行： 选择t 中的频繁项，并按l 中的次序排序。设排序后的频繁项表为【p 旧，其 中p 是第一个元素，而p 是剩余元素的表。调用i n s e r t _ t r e e ( p l p ，t ) ，该过程的 执行情况如下：如果t 有子女n 使得n i t e m n a m e = p i t e m n a l n e ，则n 的计数 增加1 ；否则创建一个新结点n ，将其计数设置为1 ，链接到它的父结点t ，并 且通过结点链结构将其链接到具有相同i t e m n a l t l e 的结点。如果p 非空，递归地 调用i i l s e n _ t r e e ( p ，。 ( 2 ) 生成频繁模式树的例子 数据流频繁模式和分类挖掘算法研究 仍采用上面a p f i o f i 算法中应用的e l e e t e c h 公司的例子，通过f p - 树的生成 算法得到的事务数据库d 的频繁模式树如图2 3 所示。( 假设最小事务支持计数 为2 ，即m i i l s 。p = 2 11 = 1 8 2 ) 项计数* a t 9 7 b8 d 3 2 图2 3 存放压缩的频繁模式信息的f p - 树 2 挖掘频繁项集 ( 1 ) 频繁项集的生成步骤： 对f p 树进行挖掘将生成所需的全部频繁项集，采用的是自下而上的策 略，挖掘过程由长度为1 的频繁模式( 初始后缀模式) 开始，通过构造它的条 件模式基( 一个“予数据库”，由f p - 树中一起出现的前缀路径集组成) 。然后 构造它的( 条件) f p - 树，并递归地在该f p - 树上进行挖掘。模式增长通过后缀 模式与条件f p 树产生的频繁模式连接实现。f p 树的挖掘过程通过调用过 程f p _ g r o w t h ( f p t r e e n u l l ) 实现。 下面是对过程f p _ g r o w t h 的伪码描述。 p r o c e d u r ef p _ g r o w t h ( t r e e ， i f t r e e 含单个路径pt h e n f o r 路径p 中结点的每个组合( 记作b ) 产生模式b u a ，其支持度s u p p o r t = - p 中结点的最小支持度； e l s e f o r e a c h 在t r e e 的头部 产生一个模式p ；u 旺，其支持度s u p p o r t - - 0 4 s u p p o rt ； 构造p 的条件模式基，然后构造b 的条件f p - 树t r e e p ； i f t r c e p f _ at h e n 调用f p _ g r o w t h ( t r e e p ，p ) ； 1 2 数据流频繁模式和分类挖掘算法研究 ( 2 ) 生成频繁项集的例子 对于图所示的频繁模式树，调用过程f p - g r o w t h ( f p t r e e ，n u l l ) 对其进行挖掘 的结果如表2 1 所示，这一结果与用a p r i o r i 算法产生的频繁项集相同。 表2 - 1 挖掘f p 树产生频繁项集的结果 i t e m条件模式基条件f p 一树产生的频繁项集 e ( a 。b 。d ：1 ) 。( a b b ：1 ) a 。e ：2 ， b ，e ：2 ， a 。b 。e ：2 ) d ( a ，b ：2 ) ，( a ，c ：1 ) a ，d ：3 ， b 。d ：2 。 a 。b ，d ：2 b ( a ：3 ) ，( a ，c ：2 ) ，( c ：1 ) a 。b ：5 ， b ，c ：3 a ，b ，c ：2 c ( a ：5 ) ) a 。c ：5 2 3 1 分类的概念和技术 2 3 分类挖掘 数据分类( d a t ac l a s s i f i c a t i o n ) 在数据挖掘中是一项非常重要的任务，目前在商 业上应用最多。分类的目的是找出一个分类函数或分类模型( 也常称作分类器) ， 以便能够使用该模型预测数据库中类标记未知的对象类，如可以建立一个分类模 型，对银行贷款的安全或风险进行分类。 数据分类( d a t ac l a s s i f i c a t i o n ) 可分为两步进行( 如图2 4 ) 。第一步，建立一个模 型，描述预定的数据类集或概念集。通过分析由属性描述的数据库元组来构造模 型。假定每个元组属于一个预定义的类，有一个类标号属性( c l a s sl a b e la t t r i b u t e ) 的属性确定。对于分类，数据元组也称为样本、实例或对象。为建立模型而被分 析的数据元组形成训练数据集。训练数据集中的单个元组称为训练样本，并随机 的由样本集中选取。由于预先知道每个训练样本的类标号，这个建立模型的学习 过程属于有指导的学习( 即模型的学习在知道每个训练样本属于哪个类的指导下 进行) 。这不同于无指导的学习( 例如聚类) ，无指导的学习中的每个训练样本的类 标号事先是未知的，要学习的类集合或数量也可能事先不知道，整个学习的过程 是在无指导的情况下进行的。 通常，通过第一步的学习建立的模型用分类规则、决策树或数据公式的形式 表示。例如：给定一个顾客信用信息的数据库，通过分类算法学习得出分类规则， 根据这些规则，决定顾客的信誉的好坏( 如图a ) 。即这些规则就是分类模型，可 数据流频繁模式和分类挖掘算法研究 以利用这个模型为其他数据样本进行分类，同时也能对数据库的内容提供更好的 理解。 第二步( 如图b ) ，使用这些规则进行分类。首先要评估模型的预测准确率。 最常用的一种方法是保持( h o l d o u t ) 方法，该方法使用类标号样本测试集，这些样 本随机选取，并独立于训练样本集，即测试样本集完全不同于训练样本集。模型 在测试样本集上的准确率是指正确被模型分类的测试样本的百分比。对于每个测 试样本，按照分类模型学习得出的预测类与已知的类标号比较：如果相同，则表 示分类成功；不相同，则表示分类不成功。之所以使用完全不同于训练样本集的 测试样本集，是因为学习模型倾向于过分适合数据，即是学习模型可能并入训练 数据中某些特别的异常，而这些异常不出现在总体样本集中。如果仍使用训练数 据评估分类模型，则可能评估总是乐观的。 如果认为模型的准确率可以接受，就可以利用这个模型对类标号未知的数据 元组或对象进行分类( 这种数据在机器学习的文献中也称为“未知的”或“先前未 见到的”数据) 。如在通过分析现有顾客数据学习得到的分类规则可以预测新的顾 客的信誉的好坏( 如图2 4 示) 。 、 一训练数据l 一一 顾客i d年龄 收入水x l z 信誉度 n o 12 3 0低一般 n 0 2 3 14 0 高优良 n o 3“0 由 般 n 0 4h o 由 般 n o 53 1 4 0高 优良 分类算法 i f # 龄一“3 1 4 0 ” a n d 收入水平一“高” t 1 1 e 1 1 倌誉度一“优良” ( a ) 在训练数据上用分类算法学习，学习模型用分类规则的形式表示 ( b ) 在测试数据i ：评 i 分类规则的正确率，如果准确率可以接受， 则分类规则可用于新的数据的分类 图2 4 数据分类过程 分类具有广泛的应用，包括信誉证实、医疗诊断、性能预测和选择购物等。 数据流频繁模式和分类挖掘算法研究 分类一直都是机器学习、模式识别和数理统计的研究对象。因此有多种分类 方法，常见的分类方法有贝叶斯分类( b a y e s ) ，神经网络( n e u r a ln e t w o r k s ) ，遗传 算法( g e n e t i ca l g o r i c h m s ) 和决策树分类( d e c i s i o nt r e e s ) 等，在这些分类方法中， 决策树分类在大规模的数据挖掘环境中己经得到广泛的应用瞄2 3 , 2 4 1 。 2 3 2 决策树分类算法 所谓决策树就是一个类似流程图的树型结构，其中树的每个内部结点代表对 一个属性( 取值) 的测试，其分支就代表测试的每个结果，而树的每个叶结点就 代表一个类别。树的最高层结点就是根结点。如图2 5 所示，就是一个决策树示 意描述，该决策树描述了一个购买电脑的分类模型，利用它可以对一个学生是否 会在本商场购买电脑进行分类预测。决策树的中间结点通常用矩形表示；而叶子 结点常用椭圆表示。 决策树示意描述 图2 5 决策树结构描述 为了对未知数据对象进行分类识别，可以根据决策树的结构对数据集中的属 性值进行测试，从决策树的根结点到叶结点的一条路径就形成了对相应对象的类 别预测。决策树可以很容易转换为分类规则。 判定树归纳的基本算法是贪心算法，它以自顶向下递归的各个击破方式构造 判定树。著名的i d 3 算法【2 5 1 是q i l i l a i l 于1 9 8 6 年提出的。 i d 3 算法从树的根节点处的所有训练样本开始，选取一个属性来区分这些样 本，属性的每一个值产生一个分支。将分支属性值的相应样本子集移到新生成的 子节点上。这个算法递归地应用于每个子节点，直到一个节点上的所有样本都区 分到某个类中。 数据流频繁模式和分类挖掘算法研究 i d 3 算法属性选择采用信息增益( i n f o r m a t i o ng a i n ) 的方法来确定。选择具有最 高信息增益( 熵减少的程度最大) 的属性作为当前结点的测试属性，这样保证所产 生的决策树最为简单，工作量最小。 设s 为一个包含了s 个数据样本的集合。假定类别属性可以取m 个不同的值， 定义i n 个不同类 c l ，c 2 ，c 。，。假设s i 为类别c i 中的样本个数，则对一个给定 数据对象进行分类所需要的信息量为： i ( s l ，s 2 ，s m ) 2 一_ , p i l 0 9 2 ( p i ) ( 2 一1 ) 其中p i = s i s 。 设一个属性a 取v 个不同的值 a l ，a 2 ，a v ) ，利用属性a 将s 划分为v 个子集 s i ，s 2 ，s 。 ，设s o 为子集s j 中属于c i 类别的样本数。那么利用属性a 划分当 前样本集合所需要的信息( 熵一信息和通信理论中一个非常重要的概念，用来描 述数据集合的不确定性) ，可以按如下公