针对Top-k高效用项集挖掘算法在挖掘过程中忽略内存管理的问题,提出基于DBP的Top-k高效用项集挖掘算法TKBPH(Top-k buffer pool high utility itemsets mining),采用数据缓冲池(DBP)结构存储效用链表,并由索引链表记录效用链表在DBP的...
详细信息
针对Top-k高效用项集挖掘算法在挖掘过程中忽略内存管理的问题,提出基于DBP的Top-k高效用项集挖掘算法TKBPH(Top-k buffer pool high utility itemsets mining),采用数据缓冲池(DBP)结构存储效用链表,并由索引链表记录效用链表在DBP的位置。数据缓冲池根据挖掘过程情况在数据缓冲池尾部动态插入和删除效用链表,通过索引链表直接读取效用链表避免项集搜索时频繁的比较操作,有效减少内存空间和运行时间消耗。不同类型数据集上的实验结果表明,TKBPH算法在挖掘过程中执行速度更快、内存消耗更少。
高效用项集挖掘(High Utility Itemsets Mining,HUIM)已成为数据挖掘领域研究工作的关键。高效用项集挖掘是为了解决频繁项集挖掘只考虑出现频次的问题,高效用项集挖掘同时考虑事务数据库中项目数量和单位利润。先前大部分HUIM算法只考虑项目存在正效用的情况,然而实际应用中会存在负效用项集。根据先前高效用项集挖掘算法相关修剪策略,低效用项集的子集必是低效用项集。但是事务中存在负效用项,低效用项集的子集可能是高效用项集,因此含负效用项的高效用项集可能会被忽略。不仅如此,现有HUIM算法执行方面,阈值需要用户设定。而在实际应用中阈值的设定直接影响输出结果集的数量,从而极大地影响算法运行效率。阈值过高使得无结果产生,用户不能得到高效用项集(HUIs);阈值过低导致算法运行时间无限增长并且占用大量内存,甚至导致内存溢出。设定合适的阈值是一个困难的问题。针对上述问题本文对高效用项集挖掘算法存在负效用项和阈值设定方面进行研究,研究工作主要如下:(1)针对数据集中包含负效用项的问题,提出含负效用项的高效用项集挖掘算法EHUIN(Efficient High Utility Itemsets Mining with Navigate utility)。算法在第一次扫描数据库时使用覆盖理论指导方法,在初始化链表时对事务加权效用值相等的项集进行覆盖操作。随后在含负效用的传递分支公式tenu(transitive extension with negative utility)帮助下,将链表中项集效用与其传递分支项集效用之和与用户设定最小效用阈值比较,若小于最小效用阈值则项集的传递分支项集均为低效用项集并舍弃。在构建效用链表时使用提前过滤策略,通过计算元组中效用值来判定该效用链表是否为低效用链表,从而降低运行时间,减少内存消耗,进一步提高挖掘效率。经过近60万条数据24组实验证明在数据集稠密程度不一致的情况下,EHUIN算法效率更高,尤其是在稠密数据集上表现更佳。(2)针对最小效用阈值设定的问题,高效用项集挖掘算法通过和Top-k算法结合,将设定阈值的问题转变成设定高效用项集数量的问题。目前Top-k高效用项集挖掘算法主要研究方向是改进数据结构和优化效用链表的构建过程,但忽略效用链表构建后的内存管理。随着数据量增大,挖掘高效用项集所需构建的效用链表增多却无法管理内存资源,之前的算法运行时占用系统大量内存空间和计算开销。针对这一问题,提出新的Top-k高效用项集挖掘算法TKBPH(Top-k Buffer Pool High Utility Mining)。TKBPH算法提出数据缓冲池(DBP)结构管理内存空间,高效存储与检索缓冲池内数据,并在挖掘过程中进行内存复用。在不同类型数据集实验结果证明,TKBPH算法在挖掘过程中执行速度更快,内存消耗更少。
本文首先介绍了实时数据库和传统数据库区别,简要介绍了实时数据库的特点、事务调度以及在SCADA(Supervisory Control And Data Acquisition,数据采集与监视控制系统)系统中的应用。并采用VC6.0为工具就实时数据库的开发与应用进行了简...
详细信息
本文首先介绍了实时数据库和传统数据库区别,简要介绍了实时数据库的特点、事务调度以及在SCADA(Supervisory Control And Data Acquisition,数据采集与监视控制系统)系统中的应用。并采用VC6.0为工具就实时数据库的开发与应用进行了简单的介绍,并提出了数据缓冲池技术在实时数据库中的应用。
暂无评论