大规模传感器网络中流间关联挖掘的在线算法

### 大规模传感器网络中流间关联挖掘的在线算法 #### 1. 引言 数据挖掘在数据库研究领域十分活跃，其重要任务之一是从大型数据集中挖掘频繁出现的模式或关联。近年来，流处理尤其是传感器网络受到广泛关注。流处理面临数据量大和在线处理要求高等挑战。 在我们的模型中，传感器仅取有限个离散状态，且只报告状态变化，传感器流可看作一系列与状态变化时间相关的更新序列。我们的目标是发现传感器值在大部分时间内共存的关联。 将传感器值视为项目，挖掘频繁值集类似于挖掘频繁项集。一种方法是将流数据转换为交易数据集，再应用传统挖掘算法，如 Apriori。有两种常见的数据转换方式： - **简单转换**：按固定间隔对传感器状态进行快照生成交易。 - **加权转换**：仅在有更新时生成交易，不同快照的传感器状态有不同寿命，作为交易的权重。 然而，这两种转换方式导出的数据存在大量冗余，导致传统挖掘算法性能不佳。为避免冗余问题，可采用区间列表表示流数据。 #### 2. 问题定义 - **传感器与传感器值**：传感器用于监测和报告物理属性状态，其所有可能状态的集合称为域，假设传感器域有限。传感器值是传感器报告的状态，用“S = v”表示，若传感器 S 在时间 t 的状态为 v，则称传感器值“S = v”在时间 t 有效。 - **支持度与频繁值集**：在时间区间 I 内，若所有传感器值都有效，则称传感器值集 V 在 I 内有效。在时间 T 时，值集 V 的支持持续时间 SD(V) 是 [0, T] 内所有 V 有效的非重叠区间的总长度，支持度 sup(V) 定义为 SD(V)/T。若 sup(V) ≥ ρs（用户指定的支持阈值），则称值集 V 为频繁值集。 - **Lossy Counting 框架**：在流环境下，精确查找频繁值集需要跟踪所有出现过的值集，这在内存和处理上不可行。因此，我们采用 Lossy Counting 框架，报告所有频繁值集以及支持度保证不小于 ρs - ϵ（用户指定的误差界限）的值集。 #### 3. Lossy Counting 算法 Lossy Counting 是一种简单有效的算法，用于从交易流中近似计算频繁项集。用户需指定支持阈值 ρs 和误差界限 ϵ，项集的支持计数存储在数据结构 D 中，D 中的条目形式为 (e, f, ∆)，其中 e 是项集，f 是 e 的近似支持计数，∆ 是计数的误差界限。D 需满足以下属性： - **属性 P1**：若条目 (e, f, ∆) 在 D 中，则 f ≤ fe ≤ f + ∆，其中 fe 是 e 在 N 个交易中的精确支持计数。 - **属性 P2**：若条目 (e, f, ∆) 不在 D 中，则 fe 必须小于 ϵN。 更新 D 的步骤如下： 1. 将交易分成批次，批次大小受可用内存限制。 2. 枚举当前批次 B 中存在的项集，并计算它们在批次中的支持度。 3. 对于出现在 B 中的项集 e，若 D1 中不包含 e 的条目，则创建条目 (e, fB, ϵN1)，除非 fB + ϵN1 ≤ ϵN2（N2 是包括 B 在内的总交易数）；否则，将 D1 中 e 的频率 f 增加 fB。 4. 所有更新完成后，若 f + ∆ ≤ ϵN2，则删除 D 中的条目 (e, f, ∆)。 #### 4. 区间列表 - **区间与区间列表的定义**：区间 I 用 (t, ¯t) 表示，其持续时间 δ(I) = ¯t - t。两个区间 I1 和 I2 重叠时，其交集 I1 ∩ I2 = (t2, min( ¯t1, ¯t2))。区间列表是一系列非重叠区间，按起始时间排序，其持续时间 δ(IL) 是所有区间持续时间之和。两个区间列表 IL1 和 IL2 的交集定义为 IL1 ∩ IL2 = S{I1 ∩ I2 | I1 ∈ IL1 ∧ I2 ∈ IL2}。 - **区间列表表示法挖掘频繁值集**： - 时间被划分为多个区间，每个区间对应一批传感器更新，更新用传感器值的区间列表表示。 - 数据结构 D 用于跟踪某些传感器值集的支持持续时间，其功能和属性与 Lossy Coun