太阳城集团

  • / 6
  • 下载费用:30 金币  

一种减少候选项集的数据流高效用项集挖掘算法.pdf

摘要
申请专利号:

太阳城集团CN201611202991.7

申请日:

2016.12.23

公开号:

CN106777182A

公开日:

2017.05.31

当前法律状态:

实审

有效性:

审中

法律详情: 实质审查的生效IPC(主分类):G06F 17/30申请日:20161223|||公开
IPC分类号: G06F17/30 主分类号: G06F17/30
申请人: 陕西理工学院
发明人: 陈涛
地址: 723000 陕西省汉中市汉台区东关正街505号
优先权:
专利代理机构: 北京科亿知识产权代理事务所(普通合伙) 11350 代理人: 汤东凤
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

太阳城集团CN201611202991.7

授权太阳城集团号:

|||

法律状态太阳城集团日:

太阳城集团2017.06.23|||2017.05.31

法律状态类型:

实质审查的生效|||公开

摘要

本发明公开了本发明提供的一种减少候选项集的数据流高效用项集挖掘算法,首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入口与节点的冗余效用值;然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;在候选项集效用中,按照事务集的顺序,依次将第k个事务中的ij项的事务加权效用相加,作为节点ij项的事物加权效用总和,处理次频效用项集,将次频效用项加入到树中;然后通过引入高事务效用阈值与低事务效用阈值,PTUVD存放数据集中的次频效用项集;最后计算实际效用来确定最终的高效用项集。基于真实数据流的实验结果表明,本发明的时空效率与内存占用比均优于其他数据流的高效用模式挖掘算法。

权利要求书

1.一种减少候选项集的数据流高效用项集挖掘算法,其特征在于,包括如下步骤:
S1、首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入
口与节点的冗余效用值;
S2、然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;
S3、在候选项集效用中,按照事务集的顺序,依次将第 k 个事务中的ij项的事务加权效
用相加,作为节点ij项的事物加权效用总和,同时,将项ij的前缀项加入到节点 ij的前缀项
集链表中, 处理次频效用项集,将次频效用项加入到树中;
S4、然后通过引入高事务效用阈值与低事务效用阈值,将事务加权效用率划分为三层,
在原始事务集和新增事务集中分层对应处理,利用HTWUD存放数据集中的高频效用项集,
PTUVD存放数据集中的次频效用项集;
S5、最后计算实际效用来确定最终的高效用项集。
2.根据权利要求1所述的一种减少候选项集的数据流高效用项集挖掘算法,其特征在
于:所述全局树的建立方法如下:
a、首先计算变化事务中每个项集的事务加权效用变化量;
b、然后将它们依照原始数据库的项频度分为高频效用项,次频效用项和低频效用项来
构造PreHU-tree;
c、最后通过搜索PreHU-tree各节点的事务加权效用和前缀项集链表直接确定n-频项;
d、结合前缀项集链表中的项集支持度和项的外部效用挖掘变化式高效用项集。
3.根据权利要求1所述的一种减少候选项集的数据流高效用项集挖掘算法,其特征在
于:所述冗余效用降低算法如下:
A、在一个全局HUS 树的头表中为每项建立一个条件模式基,每个划分的搜索空间头表
中并未包含各项太阳城集团,因此从条件模式基产生候选模式时,无须包含后面项目的效用太阳城集团;
B、假设S={i1<i2<...<im}是当前的排序,其中i1 与im分别是全局树头表的顶部与底部
项,假设挖掘程序从头表选择一项ip建立一个条件模式基,条件模式基中仅包含序列中前
几项{i1,i2,...,ip-1},所以无须添加后面若干项的效用至高效用项中。

说明书

一种减少候选项集的数据流高效用项集挖掘算法

技术领域

本发明属于数据挖掘技术领域,更具体地说,尤其涉及一种减少候选项集的数据
流高效用项集挖掘算法。

背景技术

随着云计算,大数据和互联网的迅猛发展,我们生活中的各方各面都离不开计算
机技术来存储、挖掘和分析数据。我们接收的不仅仅是本体系内部的规模较小的数据,而是
各行业间交叉互联广阔无垠的太阳城集团知识海洋,如何从产生的大规模数据中获取知识和太阳城集团
是一个巨大的挑战。传统的太阳城集团系统中对数据进行增删查改和统计等操作在当下这个日新
月异的社会己经趋于过时老套了,通过什么样的技术对存储量巨大的数据进行挖掘分析,
快速有效的发现数据之间存在的潜在太阳城集团,并通过这些己经挖掘到的太阳城集团为管理者或决策
者提供知识的预测,有效提高资源的利用率,这才是符合时代要求的技术研究。由此,从数
据库中发现知识和主导技术支持数据挖掘的研究开始出现,并快速的得以发展。数据挖掘
就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中,提取隐含在其中的、
人们事先不知道的、但的确是潜在有用的太阳城集团和知识的过程。现在己经有许多现实领域在
应用DM技术,包括制造业、零售业、金融、医疗保健、工程和科学等。同时在行为推荐、网络舆
情监控系统等方面得到很广泛的应用。

关联规则挖掘作为数据挖掘技术中一个举足轻重的研究分支,得到了学者的广泛
研究,它主要挖掘项集之间的相关联程度,其中它的核心是频繁项集挖掘。1993年Agrawal
等人通过对Wal-Mart的超市购物篮数据太阳城集团充分研究首次提出了关联规则的概念,之后在
很多行业得到应用。如网上购物平台(天猫、当当等),通过挖掘得到的关联规则可以预测顾
客的购买方式和喜好,然后就可以为每位顾客提供个性化的购买体验。但是关联规则挖掘
只分析了商品之间的关联度大小而没有其他因素的考虑,如物品的数量和利润等,这就会
使出现次数少但是效用高的项集被忽略。为了解决这个问题,学者首次提出了高效用项集
(high utility itemsets)挖掘,它将物品的数量和利润值增加到关联规则模型中,当项集
的总效用值比预先给定的效用阈值大时,就将它称为高效用项集。

但是,随着数据库和网络技术的快速发展,数据存储量的大幅度提升,导致数据不
再是静止的,而是逐渐累积、变化的。如网上平台的销售数据,中国联通移动的通话记录,交
通的实时监控数据等。不同于传统的关联规则挖掘,事务集里的数据会随着太阳城集团而改变,更
新后的数据相比之前的更加重要,如何正确的考虑这些变化的因素并快速有效地挖掘出真
实有价值的知识和太阳城集团,对关联规则挖掘提出了更严格的要求和挑战。传统的分批式频繁
项集挖掘算法只能通过重新扫描更新后的数据库产生新关联项集,现有技术中提出了FUP
算法,算法解决了新增事务集比原始事务集规模小时需要频繁扫描更新后数据库的问题。
将次频繁集的概念和FP-tree结合设计出了prelarge-tree结构有效进行增量挖掘。随后又
提出减量挖掘和变化挖掘的概念。之后在关联规则增量挖掘的基础上又将效用值考虑在
内,利用事务加权效用(TWU)的向下封闭性,在FUP算法和次频繁项集概念的基础上不断改
进,如Lin et al基于FUP算法提出了FUP-HU工算法进行效用增量挖掘,但是当一个项集在
原数据集上是低频效用项而在更新后的数据集上是高频效用项时仍然需要重新扫描更新
后的数据库。鉴于此Pre-HU工算法提出将Two-Phase算法和Pre-large概念整合到效用挖掘
中,利用事务向下封闭性减少了扫描数据库的太阳城集团。

虽然这些效用增量算法提高了更新效率,有效减少了扫描原始数据库的次数,但
仍需产生大量无用候选频项,且只适合处理事务数据库的增加,当原数据库事务中项集改
变(减少,修改等)时仍需重新扫描更新后的数据库,通过本发明能够达到有效减少候选频
项数的目的,不仅能处理事务集的增加,又能处理事务集的改变,同时也能高效的完成动态
效用挖掘任务,这也适应了现阶段对效用挖掘的新要求。

发明内容

本发明的目的是为了解决现有技术中存在的缺点,而提出的一种减少候选项集的
数据流高效用项集挖掘算法。

为实现上述目的,本发明提供如下技术方案:

一种减少候选项集的数据流高效用项集挖掘算法,包括如下步骤:

S1、首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入
口与节点的冗余效用值;

S2、然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;

S3、在候选项集效用中,按照事务集的顺序,依次将第 k 个事务中的ij项的事务加权
效用相加,作为节点ij项的事物加权效用总和,同时,将项ij的前缀项加入到节点 ij的前缀
项集链表中, 处理次频效用项集,将次频效用项加入到树中;

S4、然后通过引入高事务效用阈值与低事务效用阈值,将事务加权效用率划分为三层,
在原始事务集和新增事务集中分层对应处理,利用HTWUD存放数据集中的高频效用项集,
PTUVD存放数据集中的次频效用项集;

S5、最后计算实际效用来确定最终的高效用项集。

优选的,所述全局树的建立方法如下:

a、首先计算变化事务中每个项集的事务加权效用变化量;

b、然后将它们依照原始数据库的项频度分为高频效用项,次频效用项和低频效用项来
构造PreHU-tree;

c、最后通过搜索PreHU-tree各节点的事务加权效用和前缀项集链表直接确定n一频
项;

d、结合前缀项集链表中的项集支持度和项的外部效用挖掘变化式高效用项集。

优选的,述冗余效用降低算法如下:

A、在一个全局HUS 树的头表中为每项建立一个条件模式基,每个划分的搜索空间头表
中并未包含各项太阳城集团,因此从条件模式基产生候选模式时,无须包含后面项目的效用太阳城集团;

B、假设S={i1<i2<...<im}是当前的排序,其中i1 与im分别是全局树头表的顶部与底部
项,假设挖掘程序从头表选择一项ip建立一个条件模式基,条件模式基中仅包含序列中前
几项{i1,i2,...,ip-1},所以无须添加后面若干项的效用至高效用项中。

本发明的技术效果和优点:本发明提供的一种减少候选项集的数据流高效用项集
挖掘算法,首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表
入口与节点的冗余效用值;然后,基于全局树生成候选模式,基于增长算法降低局部树的候
选项集效用;最终,从候选模式中选出高效用模式。基于真实数据流的实验结果表明,本发
明的时空效率与内存占用比均优于其他数据流的高效用模式挖掘算法。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白,以下结合具体实施例,对本
发明进行进一步详细说明。应当理解,此处所描述的具体实施例仅仅用以解释本发明,并不
用于限定本发明。基于本发明中的实施例,本领域普通技术人员在没有做出创造性劳动前
提下所获得的所有其他实施例,都属于本发明保护的范围。

一种减少候选项集的数据流高效用项集挖掘算法,包括如下步骤:

S1、首先,通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入
口与节点的冗余效用值;

S2、然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;

S3、在候选项集效用中,按照事务集的顺序,依次将第 k 个事务中的ij项的事务加权
效用相加,作为节点ij项的事物加权效用总和,同时,将项ij的前缀项加入到节点 ij的前缀
项集链表中, 处理次频效用项集,将次频效用项加入到树中;

S4、然后通过引入高事务效用阈值与低事务效用阈值,将事务加权效用率划分为三层,
在原始事务集和新增事务集中分层对应处理,利用HTWUD存放数据集中的高频效用项集,
PTUVD存放数据集中的次频效用项集;

S5、最后计算实际效用来确定最终的高效用项集。

具体地,所述全局树的建立方法如下:

a、首先计算变化事务中每个项集的事务加权效用变化量;

b、然后将它们依照原始数据库的项频度分为高频效用项,次频效用项和低频效用项来
构造PreHU-tree;

c、最后通过搜索PreHU-tree各节点的事务加权效用和前缀项集链表直接确定n一频
项;

d、结合前缀项集链表中的项集支持度和项的外部效用挖掘变化式高效用项集。

具体地,述冗余效用降低算法如下:

A、在一个全局HUS 树的头表中为每项建立一个条件模式基,每个划分的搜索空间头表
中并未包含各项太阳城集团,因此从条件模式基产生候选模式时,无须包含后面项目的效用太阳城集团;

B、假设S={i1<i2<...<im}是当前的排序,其中i1 与im分别是全局树头表的顶部与底部
项,假设挖掘程序从头表选择一项ip建立一个条件模式基,条件模式基中仅包含序列中前
几项{i1,i2,...,ip-1},所以无须添加后面若干项的效用至高效用项中。

综上所述:本发明提供的一种减少候选项集的数据流高效用项集挖掘算法,首先,
通过数据流中当前窗口的一次扫描建立一个全局树,并降低全局树中头表入口与节点的冗
余效用值;然后,基于全局树生成候选模式,基于增长算法降低局部树的候选项集效用;最
终,从候选模式中选出高效用模式。基于真实数据流的实验结果表明,本发明的时空效率与
内存占用比均优于其他数据流的高效用模式挖掘算法。

最后应说明的是:以上所述仅为本发明的优选实施例而已,并不用于限制本发明,
尽管参照前述实施例对本发明进行了详细的说明,对于本领域的技术人员来说,其依然可
以对前述各实施例所记载的技术方案进行修改,或者对其中部分技术特征进行等同替换,
凡在本发明的精神和原则之内,所作的任何修改、等同替换、改进等,均应包含在本发明的
保护范围之内。

关 键 词:
一种 减少 候选 数据流 高效 用项 挖掘 算法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
太阳城集团本文
本文标题:一种减少候选项集的数据流高效用项集挖掘算法.pdf
链接地址:http://zh228.com/p-6019763.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');