EFIM——数据流上频繁项集挖掘的高性能算法

来源 :第二十三届中国数据库学术会议(NDBC2006) | 被引量 : 0次 | 上传用户:muniao090908
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近来许多应用领域如股票数据、网络流量监控,点击流、传感器网络、电话记录等领域中需要处理数据流问题,所以数据流的问题越来越引起人们的关注.而频繁模式的发现通常又是其他挖掘问题如关联规则发现、序列模式发现等其他挖掘问题的基础,在现有的频繁模式挖掘算法中,一个主要的缺陷就是当支持度减小或者单项集(distinct item)的数目增多时内存的要求将很大,有些甚至呈指数增长,这样就限制了算法的进一步应用.在本文中,我们提出了一种新的方法来发现数据流中的频繁项集,针对数据流环境中挖掘频繁项集存在的一些问题,我们的工作主要有如下几个方面:1)解决了在有限内存中挖掘频繁项集的问题,并且在当支持度非常低或者单项集(distinct itemset)非常多的情况下对内存的使用也达到了一个非常合理的数量.2)我们设计的算法在理论上和实践中都证明是非常精确的,在任何时候,精确度都达到了100%,然而其他的频繁挖掘算法如Jin和Agrawal提出的In-core算法,(该算法是到目前为止最精确的算法),也只是在少数情况下精确度达到100%并且当ε增大时,精确度随之下降.3)我们设计了一个新的数据结构(F1FET)并且提出了一种新的维护方法.最后的实验结果也表明我们的算法较之于其他方法在节省内存方面和准确性方面都有较大的优越性。
其他文献
近年来,一种新型数据形式数据流得到了广泛的应用和研究,数据流是持续快速到达的数据序列,数据量巨大,并且数据分布具有时变性.聚类是数据流处理的一个中心问题. 本文研究
会议
随着数据库系统的发展,数据的多维性已经广泛地存在于各种领域.由于人类没有对高维数据的空间猜想能力,不能对其产生直观的认识,因此可视化多维数据一般是寻找一种方法把多维
会议
新闻数据作为一种非常重要的数据对象,在网络和期刊报纸中广泛存在,对新闻数据的挖掘尤其是重要新闻事件的查找在日常生活中有非常广泛的应用.对于查找重要新闻事件,我们一般
会议
关联规则挖掘是数据挖掘中很重要的研究方向之一,传统的关联规则挖掘方法主要基于支持度和可信度阈值,这些方法在挖掘过程中总是假设数据库中的每个项目具有相同的地位和作用
会议
Rough集理论利用近似概念对信息系统的数据进行分类以获取信息表中的知识,遗传算法对问题求解具有其独特的优点,将两者结合起来利用两者优点,通过一个信息表实例计算,示例了
随着对语义Web研究的深入,需要构建越来越多的领域本体.目前大家在公认的构建领域本体的过程中,都需要领域专家的参与和协作,由知识工程师根据该领域的结构,将相关词汇和术语
会议
传统的宏观经济学是在数学和统计的基础上发展起来的,已取得一些成绩.但以往的宏观经济管理多采用常规方法,以单纯的经验判断为基础,缺乏系统的观点,忽视精密的数量计算,管理
会议
自从WWW问世以来,其信息容量飞速增长.由于Internet是一个开放性、动态性和异构性的全球分布式网络,信息资源分布非常分散,没有统一的管理机构,从而导致了信息获取的困难.
会议
今年是中国植物学会成立五十周年,许多会员自然会联想到学会的创始人之一,连任多年的理事长,钱崇澍老先生。在1963年中国植物学会三十周年庆祝会上,曾经共同祝贺了钱老的八
随着XML数据的应用范围和复杂度的快速增长,各种应用对XML数据的查询、定位和获取的需求不断增加,引发了对XML数据进行合理存储和快速查询的要求. 对于同样的查询条件,在
会议