基于线性链表的关联规则数据挖掘技术在数字图书馆中的应用.doc

基于线性链表的关联规则数据挖掘技术在数字图书馆中的应用汪育健 邹攀（电子科技大学图书馆，成都 610054） （电子科技大学计算机学院 成都 610054）[摘要]关联规则挖掘是数据挖掘的一个重要研究方向，而把相关技术应用在数字图书馆可提高图书馆数字资源的利用率,提高图书馆服务层次本文就针对图书馆挖掘应用上讨论了一种借助特殊数据结构实现了最大频繁项目集的挖掘算法，从而实现了关联规则的快速发现由于该算法只需一次访问事务数据库，可以避免频繁访问数据库造成时间上的巨大浪费；对于像图书馆这样数量级别越高的数据库其优越性表现尤为明显[关键词]关联规则挖掘，线性链表，事务数据库，数字图书馆[分类号]TP311Association Rules Data Mining Technology Based on Linear Linker in the Digital Library ApplicationWang Yujian(Library, Univ.of Electro.Sci.& Tech.of China. Chengdu 610054, China.) Zou Pan(School of Computer Science & Engineering, UESTC. Chengdu 610054, China)[Abstract]Association rules mining is an important research aspect of data mining, And the related technology applications in the digital library can improve the utilization of library resources, improve the library service levels. In this paper, for the Library mining applications, to discuss algorithms which in the help of a special data structure to achieve the maximum frequent item sets, to achieve the rapid discovery of association rules. Because this algorithm visit Transaction Database only needs one time, can avoid visiting the database to make in the time frequently the huge waste. The number of higher-level library database of its superiority of performance is particularly evident.[Keywords]Association rules mining, Linear linker, Transaction DB, Digital library1.问题概述数据挖掘技术是一门交叉学科，它把人们对数据的应用从低层次的简单查询提升到对数据进行更高层次的提炼和分析。

近年来数据挖掘技术的研究非常活跃,它在电子商务、零售业、电信业等行业已经有了较为广泛的应用在我国随着数字图书馆建设的不断发展，数字化图书馆建设已经开始进入第二和第三阶段，即资源整合与面向用户的数字化服务阶段众所周知在图书馆,积累了大量的历史数据，这些数据背后隐藏着许多重要的信息，人们希望能够进行更高层次的分析，以便更好地为读者服务数据挖掘技术的产生使我们能够从大量信息中提取所需的信息,数据挖掘,又称数据库中的知识发现,是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含的、未知的和潜在有用的信息的非平凡的过程 [1]数据挖掘的关联规则挖掘对于提升图书馆的信息服务有着积极的现实意义关联规则挖掘中最有影响的是 Apriori 算法 [1]，它是 1994 年 Agrawal 等人提出的,其思路为把挖掘关联规则分解为 2 个过程：(1)找出所有大于最小支持度的项集； (2)对于每个频繁项集,产生所有大于最小置信度的规则Apriori算法使用了递推的方法来产生所有频集，利用一个层次顺序搜索的迭代方法来完成频繁项集的挖掘工作，即利用 k-项集来生成(k+1)-项集，用候选项集 Ck找频繁项集 Lk。

过程由连接和剪枝两步组成，它能比较有效地产生关联规则但存在缺点是明显的:数据库扫描次数过多，每寻找一次 k-项集(k=1,……,K)都需要扫描数据库一次，共扫描 K 次；可能产生大量的候选项目集，若频繁 1-项集的个数为 100，则将产生 1030(2100)个候选项集由此可知,，Apriori 算法的瓶颈是找出所有频繁数据项本文针对数字图书馆个性化服务的要求和特点，提出应用基于线性链表的关联规则数据挖掘技术在数字化图书馆中的应用，并给出它的算法描述2．线性链表的关联规则数据挖掘在数字化图书馆中的应用基本思想在日常的借阅事务中,图书馆存储有大量的信息，在这些错综复杂的信息当中,存在着一定的联系,可能会发现被借阅的图书之间会存在着一定的关联性，如以计算机为学习或工作方向的人可能会比较关心计算机类的图书,对有相同需求的客户群进行有效的关联可以进一步提高工作效率又由上文知检测候选项目集是 Apriori 系列算法的性能瓶颈，针对 Apriori 算法的不足，根据频繁项集的性质，论文提出基于线性链表的关联规则数据挖掘应用于数字化图书馆线性链表的关联规则数据挖掘算法只需扫描事务数据库一次，减少了算法的时间开销，且由于算法保留了备用候选频繁项目集，使得该算法也能够有效地支持更新挖掘。

为便于论述表达基本思想,首先给出经过预处理的读者借阅信息表1 及有关定义；一个具体事由一个唯一的事务标识和一组有序项目集组成，其中论文假定最小支持计数为 3表 1 读者借阅信息表事务编号 Tid (读者) 项 Items (借阅信息)1 I2,I3,I4,I62 I2,I4,I53 I1,I3,I4,I64 I1,I45 I2,I4,I66 I2,I3,I67 I1,I3,I4,I68 I2,I69 I2,I3,I5,I6线性链表的关联规则算法只需遍历事务数据库一次,用来生成频繁 1-项集.并由此可以得到频繁 2-项集,频繁 3-项集……频繁 k-项集.对于频繁 i(1≤i≤k )—项集,采用了一种特殊的数据结构---链表簇来存贮.簇中的每一链表用来表示频繁 i-项目集各项目的信息,表头节点(patternData)和表节点(tidData)存储结构如图 1 所示.nextL pattern newed count nextP(patternData)tid nextP(tidData)图 1 存储结构图 1 中 nextL 是一指针，用来链接簇中下一链表；pattern 用来存储频繁 i-项目集某一项目；newed 用来标示项目集 pattern 域是否生成了新的频繁项目集，同时也作为最大频繁项目集判断条件，初始值为 false，若由 pattern 域产生了新的频繁项目集，其值变为 true，当新的频繁 K+1 项目集的链表簇生成后，若某频繁 k 项目集对应 newed 域值仍然为 false，则该频繁 k-项目集链表对应的 pattern 域值为一最大频繁项目集；count 是该项目集的支持计数；nextP 用来链接表节点。

对于 tidDada，tid 是支持项目集 pattern 的事务标识，保持字典递增有序，nextP 用来链接下一个支持项目集 pattern 节点定义：最大频繁项目集——如果某一频繁项目集的所有超集都是非频繁项目集，则该频繁项目集称为最大频繁项目集根据定义知：当一个频繁 i-项目集不能据此生成频繁 i＋1 项目集，该频繁项目集是一最大频繁项目集则其频繁 1-项目集的链表簇构造如图 2 所示112117 09 033I1 I2I3I4I5I64 7 05 22 6 6 35 3 6 9 0857749 0 08头结点falsefalsefalsefalsefalsefalse3656279 0图 2 频繁 1—项目集的链表簇构造性质：频繁项目集的所有子集都是频繁的线性链表的关联规则算法的原理在于先求取所有的最大频繁项目集，然后依次求取每一个最大频繁项目集的子集，从而得到频繁项目集线性链表的关联规则算法求最大频繁项目集如下：输入：事务数据库(T)，最小支持度(根据最小支持度和项目集的个数，可以得到最小支持计数)；输出：最大频繁项目集(Answer)①计算最小支持计数，最小支持计数(Minsup)＝最小支持度*事务数；②生成频繁 1-项目集 L，及其对应的链表族；③依次处理频繁 K-项目集对应的链表，据此得到最大频繁项目集。

1）初始化 pvh，pvn 为链表族表头结点扫描指针，pvh 指向链表族第一条单链表，pvn 指向 pvh 所指链表的下一条链表2）while(pvn→next≠null)/*链表族中还有待处理链表时*/{/*依次处理各链表*/while(pvn≠null){pvhw=pvh→nextP；pvnw=pvn→nextP/*初始化 pvhw 为 pvh 指针所指单链表的工作指针，初始化 pvnw 为 pvn 所指单链表的工作指针*/if(pattern=GeneratePattern(pvh->pattern，pvn->pattern) ≠null){/*用 pvh，pvn 所在链表头结点的项目集生成新的项目集pattern，如果 pattern 符合条件，计算对应事务数是否大于阈值 minsup/count=0；while(pvhw≠null&&pvnw≠null){if(pvhw→tid==pvnw→tid)count++；else if(pvhw→tid=minsup){/*对于项目集 pattern 生成一个新的链表加入到频繁(k+1)项目集链表族中*/join(ph，pattern，pvh，pvn)；pvh→newed=true；pvn→newed=true；/*表明这两条链表产生了频繁(k+1)项目集*/}}pvn=pvn→nextP；}if(pvh→newed==false)/*表明该频繁 k 项目集没有生成频繁(k+1)项目集*/Answer=answer∪pvh→pattern/*pvh 所在频繁 k 项目集加入到最大频繁项目集*/else{pvh=pvh→nextP；pvn=pvh→nextP；}}（3）由于算法在生成新的项目集时，采用了穷举法，Answer 中某个项目集可能是另外一个项目集的真子集，要将其删除；经过两次迭代，最终频繁 3-项目集如图 3 所示。

I3I4I6 false 3 1 7 03图 3 频繁 3-项目集的链表簇构造3.算法性能算法的时间复杂度分析如下：设事务数据库的记录数为 N，项目集为 M，对每个记录中项目集进行一次频繁项挖掘计算，总的计算次数为 N*M；假设频繁i-项目集(对应于链表中节点)平均长度为 L，个数(对应于族中链表的条数)为S，则生成频繁( i+1)-项目集的链表族需分别计算 L*S(S-1)/2 次，而约简非频繁项目集需要计算 L*S 次,则一次频繁项目集的生成要计算 L*S(S+1)次，假设最大频繁项目集平均个数 K，则总的计算量为(2+K)K/2*L*SS+1)+M*N 次所以时间复杂度为 O(L*K2*S2+M*N)算法中在生成频繁 1-项目集时占用单元为 M。