基于周期采样的数据流频繁项集挖掘算法研究.pdf

《基于周期采样的数据流频繁项集挖掘算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、高技术通讯年第卷第期：：基于周期采样的数据流频繁项集挖掘算法研究!侯伟!杨炳儒吴晨生!周谆（北京科技大学信息工程学院北京）（!北京市科学技术情报研究所北京）摘要针对用于数据流频繁项集挖掘的现有方法存在引入过多次频繁项集以及时空性能与输出精度较低的问题，利用不等式，构造了项集频度周期采样的概率误差边界，给出了动态检测项集支持度变化方法。提出了一种基于周期采样的数据流频繁项集挖掘算法，该算法通过跟踪项集支持度变化确定项集支持度的稳定性，并以此作为调整窗口大小以及采样周期的依据，从而以一个较大的概率保证项集支持度误差有上界。理论分析及实验证明该算法有效，在保证挖掘结果准确度相对较好的条件

2、下，可获得较优执行性能。关键词数据挖掘，数据流，频繁项（）集，周期采样（）而会降低性能及整体精度，后一类算法的设计基于引言项集支持度稳定的假设条件，该假设过于严格，在概念迁移（）较频繁时误差较大。本文在研随着信息技术的发展，数据库中知识发现究分析现有方法的基础上，提出了一种基于周期采（，）技术应运而样的数据流频繁项集挖掘算法———（表示生。作为中的重要过程，数据挖掘（频繁项集（），表示周期采样（，）采用智能算法从数据中提取有益的数据模）），作为一种新的具有概率误差边界的挖掘式［］。事实上，大量数据以数据流的形式产生［］，如方法，该算法跟踪项集支持度变化，它以项集支持度日志数据、交易

3、数据等。数据流与传统的静态数据的稳定性作为调整采样窗口大小和采样周期的依不同，它具有连续性、无序性、无界性及实时性的特据，从而以一个较大的概率保证项集支持度误差有点［］，要求挖掘算法能够实时地反映模式的变化。上界。面向数据流的频繁项集挖掘已成为研究热点之一。与静态环境不同，数据流自身特点通常迫使挖掘算问题背景与定义法对数据最多扫描一遍，且不能保存全部历史数据，同时对其处理速度的要求也较为严格，而且项集组设IU={x，x，⋯，xI}为由全体项目x（i

4、理集。具有I个项目的项集称为I-项集。事务为一速度之间取得平衡。二元组（tid，Y），其中tid为事务索引，Y为一项集。相关算法基本可以分为两类，即以若事务T的项集Y为项集X的超集，即Y#X，则［］、［］为代表的具有确定误差边界的算称事务T支持项集X。法，以及以［］、［］为代表的利用概率边界数据流由不断到达的事务构成，一般假设它是（如边界），在一定概率下具有误差边界的无限的。一事务流可视为一个窗口W=算法。这些算法在一定程度上缓解了时空复杂性，［T，T，⋯，T!］，其中!为当前时刻。一个项集X然而前一类算法通常会引入过多的次频繁项集，从在窗口W内的频度Fre（gX）是指W内支持X的

5、事"国家自然科学基金（），国家科技成果重点推广计划（）和北京市自然科学基金（）资助项目。!男，年生，博士生；研究方向：数据挖掘；联系人，：（收稿日期：）——高技术通讯年月第卷第期务数。项集在窗口内的支持度定义为（）小，当负荷过载时算法根据过载情况确定采样率，以（），其中为中的事务总数。若采样集代替事务流，直到负载下降。这类方法试图（），则称为中的频繁项集，其中（以部分样本代表数据流整体，然而项集支持度一般）为用户预设的最小支持度阈值。是不稳定的，因此难以设计合理的采样方法，从而输给定事务流与最小支持度阈值，数据流频繁出结果精度较低。项集挖掘可以归结为尽可能准确地找出窗口中的所有频繁

6、项集及其支持度。大量理论分析与实践算法理论基础证明，在数据流中无法设计高效且精确的频繁项集挖掘方法。因此一般采取输出近似结果的变通方!"周期采样概率误差边界式，即算法仅给出项集支持度的估计值（），而为应对数据流环境中高速、持续产生的事务，一该项集的真实支持度是（），两者一般不同。目些算法采取随机采样等策略，并利用，前有两类方法：（）估计支持度满足（）等概率边界，以部分事务近似数据流整体。（）!，即其具有确定边界!；（）估计支持度为方便讨论，在此给出下列引理使用的部分假设：设满足{（）（）!}"，即误差（，，⋯，）为一系列独立的服从分布超过边界!的概率具有确定下界"。由于项集频的随机

7、变量，概率｛｝，随机变量繁性不稳定，算法不仅需要维护当前频繁项集的支服从二项分布。实数!，"是常量，这里分别持度，还要维护支持度大于!的项集，即次频繁表示支持度误差上界与失败概率上届，为估计项集，其很可能变为频繁。支持度。［］是第一类方法中最具代表性引理"（边界［］）对任意!（，），的。它将事务流划分为一系列桶，每个桶包含下列不等式成立：「!个事务，!为误差上界，结构维护项集信{(!)}!（）息，项集的信息由三元组（，（），（））表达，其中（）为插入后的频度，（）{(