（计算机应用技术专业论文）基于数据挖掘的图书馆用户借阅行为分析及书目推荐服务.pdfVIP

摘要 摘要 随着信息技术的迅速发展，图书馆自动化程度的逐步提高，图书馆具有的 知识信息传播服务功能也在不断增强，成为社会的信息枢纽和i n t e r n e t 的重要 组成部分。图书馆数字化不仅改变了传统的服务方式，而且积累了大量的数据， 为个性化服务提供了数据基础。个性化服务需要用户的兴趣、图书间的关联等 信息的支持，而这些信息能够通过对图书馆的日常业务数据分析和挖掘获得。 因此，研究数据挖掘在图书馆系统中的应用具有非常重要的现实意义。 本文重点研究了关联规则挖掘算法，在分析现有图书馆管理系统的基础上， 提出了基于数据挖掘图书馆用户借阅行为分析与书目推荐服务应用模型。本文 主要工作有： ( 1 ) 改进了a p r i o r i 算法，构造了生成频繁2 项集l 。所需的散列表和类哈希函 数；应用改进后的剪枝步算法减少了候选k 项集的大小：利用频繁项集标识字 段，减少了对事务集的扫描，提高了频繁集的生成效率。在图书馆管理系统中 应用关联规则挖掘算法实现了对借阅历史信息的挖掘。 ( 2 ) 提出了“基于数据挖掘的图书馆用户借阅行为分析与书目推荐服务 应用 模型，将数据挖掘技术与图书馆个性化服务结合在一起。通过挖掘文献借阅规 律，可以制定相应的决策以优化图书馆的馆藏布局，并且提供图书推荐服务。 关键词：数据挖掘，关联规则，图书馆，读者，借阅 a b s t r a c t a l o n gw i t l lt h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n dt h eg r a d u a l l y e n h a n c e m e n to fl i b r a r y sa u t o m a t i c i t y , t h ei n f o r m a t i o nd i s s e m i n a t i o na n dt h es e r v i c e f u n c t i o no fl i b r a r ya l es t r e n g t h e n i n gu n c e a s i n g l y ，i th a sb e c o m et h ei n f o r m a t i o nk e y p o s i t i o ni ns o c i a la n dt h ei m p o r t a n tc o n s t i t u e n to fi n t e r n e t l i b r a r yd i g i t i z a t i o nn o t o n l yc h a n g e st h et r a d i t i o n a ls e r v i c ew a y ，b u ta l s oa c c u m u l a t e sm a s s i v ed a t a , i th a s p r o v i d e dt h ed a t af o u n d a t i o nf o rt h ep e r s o n a l i z e ds e r v i c e p e r s o n a l i z e ds e r v i c en e e d s s u p p o r to fu s e r si n t e r e s ta n dt h ec o n n e c t i o ni n f o r m a t i o nb e t w e e nb o o k s w ec a n o b t a i nt h e s ei n f o r m a t i o nt h r o u g ha n a l y s i s i n ga n dm i n i n gt ol i b r a r y sd a i l yo p e r a t i o n a l d a t a s o ，t h er e s e a r c ho fd a t am i n i n g sa p p l i c a t i o ni nl i b r a r ys y s t e mh a se x t r e m e l y v i t a ls i g n i f i c a n c e t h i sa r t i c l es t u d i e sm a i n l yt h ea s s o c i a t i o nr u l e sa l g o r i t h m a na p p l i c a t i o nm o d e l w h i c hi sb a s e do nd a t am i n i n gf o ra n a l y s i s i n gl i b r a r yu s e r sb o r r o w i n gb e h a v i o ra n d p r o v i d i n gb o o k sr e c o m m e n d a t i o ns e r v i c ei sp r o p o s e d t h ep r i m et a s ki s ： ( 1 ) t h ea p r i o r ia l g o r i t h mi si m p r o v e d ah a s ht a b l ea n dah a s hf u n c t i o nf o r p r o d u c t i n gf r e q u e n t2 一i t e m s e t sa l ec o n s t r u c t e d ai m p r o v e d & p r i o r ia l g o r i t h mi su s e d t or e d u c et h es i z eo fc a n d i d a t ei t e m s e t s at a gf i e l dw h i c hi sm a r k i n gf r e q u e n t i t e m s e t st or e d u c et i m e so fs c a n n i n gf r e q u e n ti t e m s e t si su s e d t h em e t h o do fm i n i n g t ol i b r a r y sb o r r o w i n gl o gi sr e a l i z e d ( 2 ) a na p p l i c a t i o nm o d e lw h i c hi sb a s e do nd a t am i n i n gf o ra n a l y s i s i n gl i b r a r y u s e r sb o r r o w i n gb e h a v i o ra n dp r o v i d i n gb o o k sr e c o m m e n d a t i o ns e r v i c ei sp r o p o s e d w i t hm i n i n gt or u l e so fl i b r a r yb o r r o w i n gl o g , w ec a l lm a k ed e c i s i o nt o o p t i m i z e b o o kc o l l e c t i o ni nl i b r a r y ，a n dp r o v i d eb o o k sr e c o m m e n d a t i o ns e r v i c e 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 ，l i b r a r y , u s e r , b o r r o w 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 一玄指导教师而爵本揪文属于葆丽一在 年解密后适用本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明；所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章前言 第一章前言 第一节研究背景 随着信息技术的迅速发展，图书馆自动化程度的逐步提高，图书馆具有的 知识信息传播服务功能也在不断增强，成为社会的信息枢纽和i n t e r n e t 的重要 组成部分。它可以帮助读者在海量的信息中找到有用的知识，真正提高了图书 馆的工作效率，实现全社会的信息资源共享。 图书馆数字化不仅改变了传统的服务方式，而且积累了大量的数据。图书 馆面向用户的信息需求与形式越来越多样化，同时，用户对文献资料的类型需 求也越来越来广泛。因此个性化的信息服务成为了新的发展趋势。个性化服务 需要用户的兴趣、图书间的关联等信息的支持，而这些信息能够通过对图书馆 的日常业务数据分析和挖掘获得。因此，研究数据挖掘在图书馆系统中的应用 具有非常重要的实际意义。 对业务数据的挖掘应用表现在以下几方面 1 为图书馆提供决策支持 采用数据挖掘技术能够为领导层的科学决策提供有力的保障。数据挖掘能 将涉及图书馆这一信息系统的各种内部数据和外部信息汇集起来，经过处理和 转换，形成集中统一、随时可用的决策信息。利用数据仓库系统提供的o l a p 工 具可以对集成数据进行多维分析比较，对决策进行审查和验证，提高决策的可 靠度和可行性，达到合理利用有限资金，优化图书馆的资源配置的目的。数据 挖掘工具可以从历史数据中找出潜在的模式，并在模式的基础上自动作出预测， 这对启发图书馆决策者的创新思维，应对信息化社会的挑战具有重大意义。 2 获取文献利用状况，优化馆藏，提高资源配置利用率 图书馆的自动化集成管理系统中对书目的馆藏信息、文献的流通情况有着 详细的记录。利用这些信息可以使用关联挖掘等技术挖掘文献的使用规律、需 求动向，籍此指导图书馆采购，调整馆藏结构、排架布局和各图书馆分部间的 文献分布，甚至可以发掘学科间的隐性联系和学科动向嘲。例如采访部门，采访 部门职能发挥的好坏关系到图书馆资金及资源利用率的高低，如何利用有限的 资金采购高质量的书刊，保障图书馆信息资源体系的科学性和合理性，是图书 第一章前言 馆工作的重中之重。因此，准确地定位读者对象的需求就成为提高资源利用率 的一个重要因素，流通方面，频繁的倒架以及因为流通快而破损的图书也是值 得我们挖掘的一个方面，利用数据挖掘关联分析的方法对历年借阅数据进行相 关分析，相应的增长幅度较大的图书种类在上架的时候应根据预测趋势预留架 位。对于那些借阅频率较大而破损的图书以及读者多次续借的图书，应以量化 的方式反馈给采访部门以加大采购的力度。 3 获取读者需求信息，提供个性化信息服务 数据挖掘技术通过收集、加工和处理涉及读者借阅行为的大量信息，确定 特定读者群体或个体的兴趣、习惯、倾向和需求，进而推断出相应群体或个体 下一步的行为，然后以此为基础，对所识别出来的群体进行特定内容的定制服 务。这与传统的“等读者上门的被动式服务相比，不仅能使馆藏资源得到更 好的利用，而且通过个性化服务能增加读者满意度，有利于图书馆的进一步发 展。例如，当发现新的相关信息或书目数据时，及时推荐给读者：当读者访问时， 根据读者兴趣度，推介相关专题信息，并提供个性化服务界面：分析读者信息访 问过程，判断其信息检索能力，适当的通过提示或引导帮助其发现信息：读者的 兴趣可能会随着需求不断变化，采用数据挖掘技术，系统可以具备自动监测能 力，及时发现读者的最新需要。 第二节本文主要工作 本文主要研究了关联规则在图书馆自动化集成管理系统u n i c o r n 中的应用， 主要研究工作如下： 1 分析图书馆集成管理系统中的借阅历史数据，对数据进行预处理 以现有图书馆管理系统为研究对象，了解系统的组成，分析系统的业务数 据，抽取用于数据挖掘的数据集，并对数据集进行预处理。 2 关联规则挖掘研究，实现改进的a p r i o r i 算法在图书关联性中的挖掘应用 对关联规则挖掘的理论进行研究，选择a p r i o r i 算法作为主要研究对象。 在研究的基础上，提出了改进的a p r i o r t 算法，提高了产生频繁集的效率。在 v i s u a lb a s i c 环境下实现了该算法。对图书馆自动化管理系统u n i c o r n 中的借 阅历史数据，进行了关联规则的挖掘实验，并对关联规则产生的结果进行了解 2 第一章前言 释。 3 数据挖掘技术在图书馆系统中的应用模型的设计与实现 提出了在图书馆环境下的数据挖掘应用模型。系统采用基于v i s u a l b a s i c 6 0 的c s 开发环境，后台数据库为s q ls e r v e r2 0 0 5 。完成的主要功能 包括数据预处理、数据挖掘以及挖掘结果应用。其中数据挖掘模块实现了关联 规则挖掘算法，并实现了挖掘结果的可视化表示。 第三节论文结构 本文共分五章阐述了研究的主要工作。 第一章介绍数据挖掘技术的发展现状，本文的研究背景以及主要研究工作。 第二章主要介绍数据挖掘的基本概念和相关理论基础。 第三章研究了a p r i o r i 算法的基本思想、特点和不足，并对a p r i o r i 算法 进行了改进，构造了生成l 2 的类哈希函数，应用改进后的剪枝步算法生成c k ， 减少了频繁项集生成过程中对事务数据库的扫描。 、 第四章详细阐述了数据挖掘技术在图书馆系统中的应用模型的实现方案。 主要介绍了系统的体系结构设计、数据库设计、数据处理功能的实现方案、数 据挖掘功能的实现方案及结果显示、数据挖掘结果在图书馆系统中的应用。 第五章对本文的研究工作进行了总结，最后对数据挖掘技术在图书馆系统 中的应用前景进行了展望。 第二章数据挖掘技术概述 第二章数据挖掘技术概述 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识过程n 1 。数据挖掘的研究涉及机器学习、数据库、模式识别、统计学、人工智 能、管理信息系统、知识获取、数据可视化等许多领域心1 。 第一节数据挖掘任务与过程 一般地，数据挖掘任务可以分为两种描述和预测。描述性挖掘任务刻画数 据库中数据的一般特性。预测性挖掘任务在当前数据上进行推断，以进行预测。 数据挖掘 描述型 形夕下 分类回归时间序列分析预测聚类汇总关联规则序列数据挖掘 图2 1 数据挖掘任务 1 分类 分类的目的是找出一组能够描述数据集合典型牲的模型或函数，以便能够 识别未知数据的归属或类别盔1 。分类实际上就是从数据库对象中发现共性，并将 数据对象分成不同类别的一个过程。分类的目标首先是对训练数据进行分析， 使用数据的某些属性，给出每个类的准确描述，即分类规则，然后使用这些描 述，对数据库中的其他数据进行分类。分类过程包含两步：第一步，建立一个 模型，描述指定的数据集；第二步，使用模型进行分类。许多技术都可以应用 到分类应用中，如决策树、贝叶斯分类、神经网络、遗传算法与进化理论、粗 糙集、模糊集等。 2 回归 回归是最广泛使用的数值预测方法，它将数据项映射到一个实值预测变量。 回归涉及学习一个可以完成该映射的函数。回归首先假设一些已知类型的函数 可以拟合目标数据，然后利用某种误差分析确定一个与目标数据拟合程序最好 4 第二章数据挖掘技术概述 的函数。 3 时间序列分析 时间序列包含一系列数据，这些数据是来自于随时间或者其他变量的增加 而得到的数据。许多变量随着时间的改变它的值也在改变。随着时间的改变， 变量值的序列组成了一个时间序列啼】。一般地说，时间序列分析的目标有两个： ( 1 ) 时间序列建模( 即洞察产生时间序列的机制或根本因素) ，( 2 ) 时间序列预 测( 即预测时间序列变量的未来值) 。时间序列数据库由不同时间重复测量得到 的值或事件的序列组成。这些值通常是在相等时间间隔( 例如，每小时，每天， 每周) 测量n 3 。通过时间序列图可将时间序列可视化。 4 预测 预测可以看作是一种分类，它主要是基于过去和当前数据对未来数据状态 进行预测。预测应用包括水灾预报、语音识别、机器学习和模式识别等。除了 可以使用时间序列分析和回归分析对未来值进行预测外，其它的技术也可用于 预测。 5 聚类 聚类是把一组个体按照相似性归成若干类或簇，划分的原则是在同一个簇 中的对象之间具有较高的相似度，而不同簇中的对象差别较大。与分类不同的 是，聚类操作中要划分的类是事先未知的，类的形成完全是数据驱动的，属于 一种无指导的学习方法。聚类分析可以作为其它算法的预处理步骤，可以作为 一个独立的工具来获得数据的分布情况，也可以完成孤立点挖掘。比较有代表 性的聚类方法有：基于划分的聚类方法、基于层次的聚类方法、基于密度的聚 类方法、基于网格的聚类方法、基于模型的聚类方法。 6 汇总 汇总就是将数据映射到伴有简单描述的子集中。它有时也被称做特征化 ( c h a r a c t e r i z a t i o n ) 或泛化( g e n e r a li z a t i o n ) 。汇总从数据库中抽取或者得到 有价值的信息，这可以通过检索部分数据来完成，也可从数据中得到一些总结 性信息( 例如某些数值属性的平均值) 。汇总简洁地将数据的内容特征化b 1 。 第二章数据挖掘技术概述 7 关联规则 关联规则是可以识别出特殊类型的数据关联的模型。这些关联通常用于零 售业以了解哪些商品频繁地被顾客同时购买。关联规则挖掘是数据挖掘中最活 跃的研究方法之一。最早是由a g r a w a l 等人在1 9 9 3 年提出的，其目的是为了发 现事务数据库( t r a n s a c t i o nd a t a b a s e ) 中不同商品之间的联系规则，也就是 挖掘在数据中频繁出现的模式( 频繁模式) 。存在多种类型的频繁模式，包括项 集、子序列和子结构。通常，频繁项集是指频繁地在事务数据集中一起出现的 项的集合，如牛奶和面包。频繁出现的子序列是指：例如顾客倾向于先购买“商 品甲 ，再购买“商品乙 ，然后再购买“商品丙”，这样的模式是一个频繁序列 模式。子结构可能涉及不同的结构形式，如图、树或格，如果一个子结构频繁 出现，则称它是频繁结构模式。 8 序列数据挖掘 序列数据库是由有序元素或事件的序列组成的，可能不包括具体的时间概 念。许多应用都涉及序列数据。如顾客购物序列、网络点击流、生物学序列、 科学或工程以及自然和社会发展中的事件序列。序列模式挖掘是挖掘频繁出现 的有序事件或子序列。 第二节数据挖掘过程 数据挖掘的一般过程如图2 2 所示，它不是一个线性的过程，包括很多反 馈回路在内，其中的每一步都有可能回到前面的一个或几个步骤往复执行。 图2 2 数据挖掘过程 6 第二章数据挖掘技术概述 数据挖掘可分为以下几个阶段 1 确定目标 了解数据挖掘相关领域的情况，熟悉有关的背景知识，弄清楚用户的要 求，确定挖掘的总体目标和方法。了解相关源数据结构并回以分析，确定数 据选择的原则。 2 数据选择 根据用户的要求从数据库中抽取与数据挖掘目标相关的数据，这种选择 工作可以借助于数据库操作语言或专门的工具来进行。 3 数据预处理 主要是对上一阶段产生的数据进行再加工，包括消除噪声、推导计算缺 失值数据、消除重复记录、完成数据类型转换( 如把连续型数据转换为离散 型数据，把离散型数据转换为连续数据) 等。 4 数据变换 主要目的是削减数据的维，即从初始特征中找出真正有用的特征以减少数 据挖掘时要考虑的特征或变量个数。根据任务的目标，查找有用的特征来表示 数据。利用空间压缩或变换的方法来减少要考虑的有效变量数目或找到数据的 不变表示。 5 挖掘算法确定 根据上一阶段所确定的模式，选择合适的数据挖掘算法。 6 数据挖掘： 运用选定的算法，从数据中提取出用户所需要的知识。这些知识可以用 种特定的方式表示或使用一些常用的表示方式，如关联规则等等。 7 模式解释 对发现的模式进行解释。在些过程中，为了取得更为有效的知识，可能会 返回前面处理步骤中的某些步以改进结果，保证提取出的知识是有效和可用的。 8 知识评价 将发现的知识以用户能了解的方式呈现给用户。这期间也包含对知识的一 致性评价，以确保本次发现的知识不与以前发现的知识相抵触。 7 第三章对经典a p d o d 算法的改进 第三章对经典a p r io ri 算法的改进 基于数据挖掘的图书管理系统模型是建立在原有的图书馆自动化管理系统 之上，充分利用系统的数据，实现关联规则挖掘应用。对图书馆而言，其信息 服务模式与商业领域内的营销模式有许多相似之处，通过收集、加工和处理涉 及读者借阅行为的大量信息，确定读者的借阅习惯、借阅倾向和借阅需求，可 以推断出未来借阅行为，寻找各个学科领域中的一些相互关联的知识、优化图 书馆的馆藏布局，提高图书馆的服务质量。 本文是以u n i c o r n 图书管理系统为研究对象，在原有的图书系统上，提出 了基于数据挖掘的图书管理系统模型的目标，利用关联规则算法，挖掘借阅历 史数据中有价值的信息，提供给管理者，同时将其应用到对读者的主动推荐服 务上。 第一节关联规则概述 设i = 1 1 ，1 2 ，i m 是项的集合，称为项集。设任务相关的数据d 是数据 库事务的集合，其中每个事务t 是项的集合，使得t i 。每一个事务有一个标 识符，称作t i d 。设a 是一个项集，事务t 包含a 当且仅当a _ t n l 。 关联规则是形如a = b 的蕴涵式，其中a c i ，b c i ，并且a n b = o 。 定义3 1规则a = b 在事务集d 中成立，具有支持度s ，其中s 是d 中事 务a ub ( 即集合a 和b 的并或a 和b 二者) 的百分比。 定义3 - 2规则a = b 在事务集d 中具有置信度c ，其中c 是d 中包含a 的 事务同时也包含b 的的百分比。规则a = b 的置信度等于包含a 和b 的事务数与 包含a 的事务数之比，即：c o n f id e n c e ( a = b ) = s u p p o r t ( a ub ) s u p p o r t ( a ) 。 定义3 3 对项目集i 和事务数据库d ，t 中所有满足用户最小支持度 ( m i n s u p p o r t ) 的项目集，即大于或等于m i n s u p p o r t 的i 的非空子集，称为频繁 项目集( f r e q u e n ti t e m s e t s ) 定义3 4d 在i 上满足最小支持度和最小置信度( m i n c o n f i d e n c e ) 的关联 规则称为强关联规则。 一般地，给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小 支持度和最小置信度来寻找强关联规则的过程。关联规则挖掘问题可以划分成 两个子问题。 第三章对经典a p r i o r i 算法的改进 1 发现频繁项目集 通过用户给定的最小支持度，寻找所有频繁项目集，即满足s u p p o r t 不小于m i n s u p p o r t 的所有项目子集。 2 生成关联规则 通过用户给定的最小可信度，在每个最大频繁项目集中，寻找可信度 不小于最小可信度的关联规则。 第二节a p r io ri 算法 3 2 1a p rio ri 算法基本思想 a p r i o r i 算法是最经典的挖掘关联规则算法，它是r a g r a w a l 和r s k r i k a n t 于1 9 9 4 年提出的布尔关联规则挖掘频繁项集的原创性算法。算法使用一种称作 逐层搜索的迭代方法来完成频繁项集的挖掘工作，k 项集用于搜索( k + 1 ) 项集。 首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找 出频繁1 项集的集合。该集合记作l 1 。然后，l l 用于找频繁2 项集的集合l 2 ，l 2 用于找l 3 ，如此下去，直到不能再找到频繁k 项集。找每个k 项集需要一次数据 库全扫描n 。为压缩搜索空间，提高频繁项集产生的效率，需要使用a p r i o r i 性 质。 a p r i o r i 性质：频繁项集的所有非空子集也必须是频繁的。 a p r i o r i 性质是反单调的，意指如果一个集合不能通过测试，则它的所有超 集也都不能通过相同的测试。所以a p r i o r i 性质可以归结为：频繁项集的所有 非空子集都是频繁的，非频繁项集的所有超集都是非频繁的。 - a p r i o r i 核心算法描述如下： d ：事务数据库 r a i n _ s u p ：最小支持度计数阈值 l ：d 中的频繁项集 ( 1 ) c 1 = c a n d i d a t ei - i t e m s e t s ： ( 2 ) l i = c c 1 i c c o u n t m i n s u p ) ： ( 3 ) f o r ( k = 2 ；l k l ：k + + ) 产生c l 计算c l 中各项支持度计数，产生l l 从k = 2 开始，循环生成频繁k 项集， 直到不能再生成频繁项集为止 9 第三章对经典a p r i o r i 算法的改进 ( 4 ) c k = a p r i o r i g e n ( l k 一1 ) ： ( 5 ) f o re a c h 事务te d ( 6 )c t = s u b s e t ( c k ，t ) ： ( 7 ) f o re a c h 候选c c t ( 8 ) c c o u n t + + ： ( 9 ) ) ( 1 0 ) l k = c c kc c o u n t m i n s u p ) ( 1 2 ) ( 1 3 ) r e t u r nl = u kl k ： 算法说明： 利用连接步和剪枝步算法， 由l k - 1 生成c k 扫描d ，对c k 计数 得到t 的子集， t 的子集中属于c k 并且 支持度计数m i n s u p 的成为l k 1 产生频繁1 项集l l ， 2 从k = 2 开始，由频繁( k 一1 ) 项集l k 一1 产生候选k 项集c k ，这里使用连接步( 对 两个只有一个项不同的属于l k 1 的频繁项集做一个连接) 和剪枝步算法。 3 扫描事务数据库d ，对c k 计数，生成l k 。 c k 中的每个元素需在事务数据库中进行验证来决定其是否加入l k ，这里的 验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据 库，这需要很大的i o 负载。 4 k + l ，重复第2 、3 步，直到l k 为空，算法停止。 其中，由l k 一1 生成c k 的函数a p r i o r i - g e n 的算法描述如下： l k - 1 频繁k - 1 项集 c k ：候选k 项集 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 s ) ( 1 ) f o re a c hi t e m s e tl l l k l ； ( 2 ) f o re a c hi t e m s e t1 2 l k l ； ( 3 )i f ( 1 l 1 = 1 2 1 ) 八( 1 1 2 = 1 2 2 ) 八( 1 1 k - 2 = 1 2 k 一2 ) 八 ( 1 1 k - 1 1 2 k 1 ) t h e n ( 4 ) 1 0 第三章对经典a p f i o f i 算法的改进 ( 5 )c = l l 0 0 1 2 ；连接步：产生候选 ( 6 ) ifh 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 (7)deletec ；剪枝步：删除非频繁的候选 ( 8 ) e l s ea d dat oc k ； ( 9 ) ( 1 0 ) r e t u r nc ； 连接步算法中，假定事务或项集中的项按字典次序排序。对于( k 一1 ) 项集l i ， 意味将项排序，使l i 1 1 2 2 l i k - 1 。执行连接l k l o 。l k 一1 ，其中l k 一1 的元 素是可连接的，如果它们的前( k 一2 ) 个项相同的话。即l k - 1 的元素1 l 和1 2 是可连 接的，如果( 1 i 1 = 1 2 1 ) 八( 1 l 2 = 1 2 2 ) a ( 1 i k 一2 - 1 2 k - 2 ) a ( 1 l k - 1 = n ，而且，对于任意的k e y l ，k e y 2 ，f ( k e y l ) ! = f ( k e y 2 ) 。如果m = n ，则f 是最小完美哈希函数( m i n i m a lp e r f e c th a s h f u n c t i o n ，简称m p h f ) 。 本文构造了一个类哈希函数，与哈希函数不同的是，哈希函数的函数值是 整数，而本文中的类哈希函数的函数值是小数。该函数将n 个2 项集映射到n 个小数上，实现了与最小完美哈希函数相同的结果，既能保证占用最少的哈希 地址数、完全无冲突，同时又能保证在数据增加或减少的时候不需要更换函数。 _ 构造类哈希函数 设集合i = 1 1 ，1 2 ，i n ) ，对i 中的的每一项i i 赋一个序号s ( i i ) ，即 i l ，1 2 ，i n 的序号分别为l ，2 ，3 ，n 。 类哈希函数表达式为： h a s h ( i i ，i j ) = s ( i i ) + s ( i j ) 1 0 1 8 n ( s ( i j ” 其中，l e n ( s ( i j ) ) 是s ( i j ) 的位数 一举例说明 项集i = i l ，1 2 ，1 3 ，1 4 ，1 5 ) 。事物数据库d 如表3 2 所示，最小支持度计数为 2 。于是可得c 1 = i x ，1 2 ，1 3 ，1 4 ，i s ，n = 5 。假设s ( 工1 ) = l ，s ( 1 2 ) = 2 ，s ( 1 3 ) = 3 ， s ( 1 4 ) = 4 ，s ( 1 5 ) = 5 表3 1 事物数据库d t i di t e m s l i l ，1 2 ，1 3 2 1 2 ，1 3 3 i l ，1 2 4 1 2 ，1 3 ，1 4 5 1 2 ，1 4 ，1 5 1 5 第三章对经典a p r i o r i 算法的改进 事务1 的所有2 项集为： 1 1 ，1 2 ，f 1 1 ，1 3 ) ， 1 2 ，1 3 。 h a s h ( i l ，1 2 ) ：1 + 2 1 0 l e n ( 2 ) _ - - - l + 2 l o t = l + o 2 = 1 2 h a s h ( i l ，工3 ) ：1 + 3 1 0 1 e n ( ：i + 3 1 0 1 = i + 0 3 = i 3 h a s h ( 1 2 ，1 3 ) ：2 + 3 1 0 l e n ( 3 ) _ 2 + 3 1 0 = 2 + 0 3 = 2 3 对于事务2 ，可得 h ( 1 2 ，1 3 ) = 2 3 依次类推，扫描数据库一次后可得到所有2 项集的计数值 表3 2 所有2 项集计数 类h a s h 函数值 i 2王32 32 42 5 计数 2l321 内容i l ，1 21 1 ，1 31 2 ，1 31 2 ，1 41 2 ，1 5 设最小支持度= 2 ，则l 2 - - - ( i l ，1 2 ) ， 1 2 ，1 3 ) ，f 1 2 ，1 4 ) 3 3 2 改进的c k 剪枝步算法 1 理论证明 性质1 ：频繁项集的所有非空子集都是频繁的。 性质2 ：非频繁项集的所有超集都是非频繁的。 推论：t k 是k 项集，t k c k ，如果频繁( k 一1 ) 项集l k l 中包含t k 的( k 一1 ) 项子集的个数小于k ，则t k 不可能是频繁项集。 证明；项集t k 的k l 项子集的个数为k ( 例如5 项集的4 项子集的个数为 4 ) ，如果频繁项集l k _ l 中包含t k 的( k 一1 ) 项子集的个数小于k ，则 存在t k 的某一( k 1 ) 项子集是非频繁项集，由性质2 可知k 项集 本身也不是频繁项集。 1 6 第三章对经典a p f i o f i 算法的改进 当l k 一1 联接生成c k 时，判断它k l 项子集是否存在于l k 一1 中，如不在就直 接删除。这样每生成一个k 项集时，就要搜索一遍l k 一1 。我们不希望每生成一 个k 项集时，就要搜索一遍l k l ，而是当所有连接完成后，扫描一遍l k 一1 ，对 于l k l 中的任意元素，判断它是否是c k 中的元素t k 的子集，如果，对t k 进行 计数。也就是统计l k 一1 中包含c k 中任意元素t k 的k l 项子集的个数。然后根 据t k 进行剪枝。由上面推论可知，t k 的计数( 即l k 一1 中包含的t k 的子集的个数) 如果小于k ，则删除。 ( 伪代码 a 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 s ；m i n s u p p o r t ：m i n i m u m s u p p o r tt h r e s h o l d ) ( 1 ) f o re a c hi t e m s e t1 1 l k l ； ( 2 ) f o re a c hi t e m s e t1 2 l k l ； ( 3 )i f ( 1 l 1 = 1 2 1 ) 八( 1 1 2 = 1 2 2 ) 八八( 1 l k - 2 = i z k - 2 ) 八 ( 1 1 k - 1 1 2 k 一1 ) t h e n ( 4 )t k = l l 1 2 ；连接步 ( 5 ) f o re a c hi t e m s e ti t l k l扫描所有l k l 中的元素 ( 6 ) f o re a c hc a n d i d a t et kec k扫描所有c k 中的元素 ( 7 ) i fl li st h es u b s e to ft kt h e n 判断l k - l 中是不是包含t k ( 8 ) t k n u m b e r + + ；如果包含，t k 的计数+ 1 ( 9 ) c k = t k c k i t k n u m b e r = k ；计数值= k 的k 项集写入c k 中 ( 1 0 ) r e t u r nc k ： 2 举例 l z = “i l ，1 2 ) ， i l ，1 3 ) ，