基于邻接表存储与哈希表的频繁项集挖掘算法.pdf
《基于邻接表存储与哈希表的频繁项集挖掘算法.pdf》由会员分享,可在线阅读,更多相关《基于邻接表存储与哈希表的频繁项集挖掘算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、第 卷第 期计算机应用与软件 年 月 基于邻接表存储与哈希表的频繁项集挖掘算法吴昊刘钊顾进广(武汉科技大学计算机科学与技术学院湖北 武汉 )(武汉科技大学大数据科学与工程研究院湖北 武汉 )(湖北省智能信息处理与实时工业系统重点实验室湖北 武汉 )收稿日期:。国家自然科学基金项目();国家社会科学基金重大计划项目()。吴昊,硕士生,主研领域:数据挖掘,智能计算。刘钊,教授。顾进广,教授。摘要针对 算法从数据中挖掘频繁项集的计算时间效率较低和空间内存占用较高的问题提出一种 ()算法。该算法利用哈希表来存储数据,极大地提高了项集支持度频数的计算效率,结合图存储的思想利用邻接表来存储候选项集,极大地
2、优化了内存空间占用,同时将候选项集构建大根堆,通过堆排序的思想与动态剪枝算法思想优化了频繁项集的计算速度和候选项集存储的内存空间,有效地优化了传统 算法的计算时间效率和内存空间占用方面的不足。一系列对比实验表明,算法在时间效率和空间效率都有一定的提高。关键词时间复杂度空间复杂度动态剪枝哈希表存储邻接表存储中图分类号 文献标志码 :(,)(,)(,),(),引言频繁项集 是从数据资源中挖掘具有潜在价值的信息,频繁项挖掘的经典算法是 算法,但是该算法存在明显的不足:算法的计算时间花费较大和内存空间占用较高。近年来,研究者们根据 算法不足之处提出了改进方法。例如,文献 提出了利用数据结构优化预剪枝步
3、骤,结合 支持的细粒度计算模型的特征,将事务数据库水平划分为 个块,第 期吴昊,等:基于邻接表存储与哈希表的频繁项集挖掘算法 分配到 个节点,在 个节点上运行 算法 次,找到所有频繁项集,利用剪枝的方法有效地减少了频繁项集的挖掘时间,但是每个节点的运行时间由数据块上的节点数决定。文献 提出了一种改进的 算法,该算法重构了数据库的存储结构,简化了项集的连接过程,仅需将 个频繁项目集与 个频繁项目集结合即可生成 个频繁项目集,从而大大地减少了连接数,只需一次修剪即可直接获取频繁项集,减少了无效的候选项集计算,较好地提高了频繁项集的生成效率。虽然该算法减少了数据的连接次数,但是仍然需要对进数据库进行
4、多次扫描,运算过程比较复杂。文献 提出了一种基于 并行处理的频繁项集挖掘方法,使用 云计算框架作为数据挖掘平台,引入了矩阵模型并结合 模型来实现并行化改进 算法,从而缩短算法的运行时间。该算法在处理海量数据集时具有良好的效率和扩展性,但是该算法通常运行在集群中,需要强大的计算和存储能力支撑。曹莹等 提出了一种改进 算法,该算法采用事务数据向量矩阵与行候选向量相结合的优化方法,减少生成冗余的候选项集,优化了候选项集计算过程,减少事务数据向量的存储量和项集之间的比较次数,提高频繁项集的挖掘效率。文武等 提出了一种结合遗传算法的 算法搜索频繁项集,利用 算法和遗传算法的特点,利用交叉计算产生候选项集
5、和变异算法筛选频繁项集,减少了冗余项集,较好地提高搜索效率。赵学健等 提出了一种利用正交链表存储数据所对应的关系矩阵,克服了多次扫描数据库的缺点,同时优化了传统的 算法的自连接和剪枝过程,但是该算法需要利用正交链表存储数据库中的数据,因此对数据的处理量受限于主存空间。本文提出一种基于邻接表存储与哈希表的频繁项集挖掘算法(算法)。该算法利用哈希表的特性,将数据库中的数据进行处理,将数据全部转化为哈希表进行映射,在后续计算项集支持度频数的时候不必进行数据与项集自匹配的过程,由于只需要在哈希表中进行查找来计算项集支持度频数 ,极大地减少了每一轮项集支持度频数的计算时间。由于只需要对数据库中的数据扫描
6、一次存在哈希表中,极大地减少了 的时间开销与负载。同时,结合图存储的思想利用邻接表来存储项集,有效地优化了存储项集的内存空间占用,在计算候选项集的过程中,利用堆排序的思想构建大根堆和动态剪枝的思想减少了冗余项集的计算,进一步优化了算法执行时间和内存空间占用。预测算法简介 算法是基于一种迭代计算搜索的方式,同时利用频繁 项集的自连接来扩展生成()项集,首先获取频繁 项集(简称),然后通过 自连接扩展生成候选 项集(简称),然后通过候选 项集扩展生成频繁 项集(简称),一直迭代下去,直到不能继续扩展生成下一项频繁项集,该迭代方法结束 。由上述步骤可以看出 算法的不足之处:)数据预处理后,每生成一个
7、候选项集时,对数据库每一条数据进行多次扫描,当计算各候选 (,)项集的支持度频数,至少要扫描 次数据库中的数据,多次访问数据库将会造成 上有较大时间开销与负载,消耗大量的时间 。)算法在扩展下一项的过程中扫描数据库中都会因为项集自连接而产生大量冗余的候选项集。例如频繁 项集经过自连接扩展生成所有候选 项集 ,就需要进行多次自连接,生成的候选项集与最小支持度比较次数增多,消耗了大量计算时间。项集个数为 的频繁项集,其生成频繁 项集时间复杂度为 (),在此过程中生成的冗余数据占用了大量的内存空间 。)在频繁项集进行扩展生成下一项时,测试 ()里每个()项集是否是 中的频繁()项集,需要扫描 ,次
8、,对于 扫描的时间复杂度为 (),所以对每一个候选 项集 扫描时间复杂度为 (),在计算过程中需要消耗大量时间 。根据上述 算法在时间复杂度和空间复杂度的不足,本文提出一种 算法进行优化。挖掘算法 算法描述邻接表 ()就是把从同一个顶点出发到达的相邻节点的点和边连接在同一个单链表中,单链表的每个节点代表一条边,称为边节点。每个边节点有三个域:该起点项集对应终点的项集,起点项集与终点项集进行交集后的项集与项集频数,以及指向下一个边节点的指针。在邻接表中,还需要一个用于存储顶点信息的顶点数组。结合邻接表存储的图节点的思想(关联项集如图 计算机应用与软件 年所示,边的权重表示两点项集的支持度频数),
9、邻接表中节点属性(如图 所示),利用邻接表存储频繁项集 (如图 所示)。图 关联项集图 链表节点属性图 关联项集的邻接表定义 假定候选项集 (,),项集中的 在哈希表 (,)中的第(,)行中都能通过哈希表找到,证明 中的全部存在于哈希表 第 (,)行中则候选项集(,)对应的支持度频数计数加 。定义 如果集合(,)的频数小于最小支持度频数,则 集合是非频繁项集,如果 ,可以判断(,)是非频繁项集 。定义 如果(,)集合的频数大于最小支持度频数,可以判断 是频繁项集,如果 ,则集合 (,)所有子集合都是频繁项集 。推论 假设频繁 项集的集合数量记为,如果 ,说明该数据库最多只能存在频繁 项集,一定
10、不存在()项集,反之,如果 ,说明可以继续扩展()项集 。证明:在每一次扩展生成候选项集中,如果出现频数满足最小支持度频数的项集即为频繁项集,频繁项集如果没有包含于其他项集,即为最大项频繁项集。根据定义 可知,频繁项集的子集一定为频繁项集这一性质,频繁()项集一定有频繁 项子集,而频繁()项集的频繁 项子集的数量一定不少于(),如果频繁 项集的子集数量小于(),则表示最终只能扩展生成频繁 项集 。算法的优化方法 算法通过以下方法进行优化:)本文提出一种哈希表存储方式来存储数据,即把数据库中的数据预处理后,存储在哈希表中,然后在哈希表中进行计算项集支持度频数,利用哈希表存储的方法就仅需要扫描一次
11、数据,在后续的过程中极大地减少了 的时间开销与负载。)在哈希表中,假设数据有 行,每个候选项集有 个事务,根据定义 ,利用哈希表进行计算候选项集支持度频数,在哈希表中进行查找,如果候选项集(,)中每个项集都能够在该条数据的哈希表的第 (,)行中找到,该项集对应的支持度频数计数加 ,因此候选项集中的每个事务利用哈希表查找单个项集所需要的时间复杂度为 (),则查找(,)项集所需要时间需要(),所需要的时间远远小于数据之间进行逐个匹配以及计算项集频繁的时间,优化了计算项集支持度频数的运算过程,极大地优化了计算过程。)将每轮交叉连接生成的项集进行判断,利用哈希表的特性同时结合定义 和定义 ,进行动态剪
12、枝,减少了冗余项集的存储和计算过程,优化了计算过程,优化了项集的内存占用空间。)利用哈希表可以判断在当前轮已经计算的项集,将当前轮已经生成的项集及项集支持度频数存入到哈希表中,在后面的计算中,就可以利用哈希表进行判断,如果该项集已经计算过,不需要重复计算,减少了存储冗余项集的计算时间。)利用图存储的思想,利用邻接表存储两点项集生成的候选项集,利用定义 与定义 ,结合哈希表对当前轮的项集进行动态剪枝与去除重复项集,将筛选后的候选项集存储在邻接表中,极大地优化了内存空间。)当前轮计算结束后,利用堆排序思想构建大根堆,将候选项集插入大根堆中进行排序,每次删除大根堆中支持度频数最大的项集,并将该项集插
13、入新的邻接表中,当大根堆中最大元素不满足最小支持度后,堆排序结束,剩余的不符合要求的项集不需要排序,将剩余项集存储非频繁项集集合中,为计算下一轮项集优化了存储空间。第 期吴昊,等:基于邻接表存储与哈希表的频繁项集挖掘算法 算法的优化基于前面的定义和推论,算法优化具体步骤如下:)首先扫描数据库,对数据库中的数据进行预处理(假设数据库数据为 条,最小支持度为 ,由此可以计算出最小支持度频数为 ),按照字母首位进行排序,并且将数据以键 值对映射的方式存储在哈希表 中,只需要遍历一次数据库中的数据,就可以将数据存储到哈希表 中,在后续的过程中需要在哈希表 中进行计算项集支持度频数,因此不需要多次访问数
14、据库中的数据,减少了访问数据库次数,降低了 方面的时间开销与负载,然后遍历哈希表计算出每一项的事务频数,得到候选 项集(简称)。)对于步骤 )得到的,遍历 中所有项集,对于不满足最小支持度频数的项集直接存入集合 (存储非频繁项集),事务频数满足最小支持度频数的项集直接存入集合(,)存储频繁项集),此时生成频繁 项集(假设 中数量为 ),将的 到 项与 的 到 项进行交叉连接取并集可以扩展生成 项集。)根据推论 ,如果 ,可以继续扩展下一项,此时利用 和 的项集交叉连接进行取并集生成新的项集 ,首先判断 是否在哈希表 出现,如果该项集存在哈希表 中,则不需要进行计算该项集频数,直接进行该轮下一个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 邻接 存储 哈希表 频繁 挖掘 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。