杨 立

（运城学院 公共计算机教学部，山西 运城044000）

基于计数的频繁项挖掘算法适用于每个数据元组所含知识相等或近似的情况，例如用户在网页上的点击流，搜索引擎的关键词流、路由器上的IP包流等情况。但在更多的情况下，每个事务代表的知识是不相等的。如电信系统中的通话记录，每个用户的电话用时是不相同的；在证券交易中心，每笔交易的金额也是不同的。许多小客户的事务数多，但每笔事务的权值很小；重要的大客户事务数虽少，但每笔事务的权值很大。如果此时用原有的频繁项挖掘算法，将不能很好地体现那些事务数少但重要性高的客户。而采用新的基于权重的算法，则可以很好地找出那些重要性高的元素。

本文提出的基于权重的新算法是对原有Lossy Counting[1]的扩展。不仅可以解决基于计数的频繁项挖掘问题，还能解决基于权重的频繁项挖掘问题。并且Lossy Counting算法本质上是新算法的一个特例(窗口定长，权值为1)。新算法在应用域上超出了原有算法，甚至可支持基于计数与权重的混合查询。

1 Lossy Counting算法

算法数据结构为三元组(e，f，Δ)的集合D。其中 e表示为流中的元素，f为估计的计数，Δ为f可能的最大误差。D初始为空，每当有一个新元素e到达时，首先在D中查找是否已存在包含e的元组。若存在则对应的该元组计数 f加 l；否则创建一个新的元组(e，1，bcurr-1)。当到达窗口边界时，对 D进行如下裁剪：若元组（e，f，Δ)满足f+Δ≤bcurr，则删除该元组。当查询到达时，返回所有 f≥(s-ε)N的元组。

2 Lossy Weight算法

本文提出的基于权重的频繁项挖掘算法(Lossy Weight Algorithm)与原有算法有着相同的定义：根据用户定义的门槛参数s∈(0，1)，输出在整个流数据中所占权重比重大于s的所有元素。……