人体传感器网络数据中的规律挖掘

# 人体传感器网络数据中的规律挖掘 ## 1. 问题定义 在人体传感器数据库中进行规律模式挖掘，需要明确一些基本概念和定义。 ### 1.1 基本符号与定义 - 设 $L = \{s_1, s_2, \ldots, s_n\}$ 是特定人体传感器网络中的一组人体传感器。 - 集合 $X = \{s_j, \ldots, s_k\} \subseteq L$（其中 $j \leq k$ 且 $j, k \in [1, n]$）被称为传感器模式。 - 基于 $L$ 的人体传感器数据库 $SD$ 定义为一组时期 $T = \{t_1, \ldots, t_m\}$，每个时期 $t = (tid, Y)$ 是一个元组，其中 $tid$ 表示传感器事件发生的时隙 ID（假设时间空间被划分为等大的时隙），$Y$ 是在相同时隙内报告事件的事件检测传感器模式。若 $X \subseteq Y$，则称 $t$ 包含 $X$ 或 $X$ 在 $t$ 中出现，这样的时隙 ID 记为 $t_X^j$（$j \in [1, m]$）。因此，$T_X = \{t_X^j, \ldots, t_X^k\}$（$j, k \in [1, m]$ 且 $j \leq k$）是 $X$ 在 $SD$ 中出现的所有时隙 ID 的集合。 ### 1.2 模式的周期 设 $t_X^{j + 1}$ 和 $t_X^j$（$j \in [1, (m - 1)]$）是 $T_X$ 中的两个连续时隙 ID，它们之间的时隙数（或时间差）定义为 $X$ 的一个周期，记为 $p_X$（即 $p_X = t_X^{j + 1} - t_X^j$，$j \in [1, (m - 1)]$）。为简化周期计算，在 $SD$ 开始时考虑一个无传感器的“空”时期，即 $t_f = null$，其中 $t_f$ 表示要考虑的第一个时期。类似地，要考虑的最后一个时期 $t_l$ 是 $SD$ 中的第 $m$ 个时期，即 $t_l = t_m$。 例如，在表 1 的人体传感器数据库中，模式 “S2,S6” 出现的时期集合为 $T_{S2,S6} = \{3, 5\}$。因此，“S2,S6” 的周期为 3（$= 3 - t_f$）、2（$= 5 - 3$）和 4（$= t_l - 5$），其中 $t_f = 0$ 且 $t_l = 9$。 | Id | Epoch | |----|-------| | 1 | S4, S1 | | 2 | S3, S2, S1, S5 | | 3 | S6, S1, S5, S2 | | 4 | S1, S2, S5, S3 | | 5 | S1, S5, S2, S6 | | 6 | S4, S2, S3 | | 7 | S5, S3, S4 | | 8 | S4, S5, S6 | | 9 | S2, S3, S4 | ### 1.3 模式的规律性 设对于 $T_X$，$P_X$ 是 $X$ 的所有周期的集合，即 $P_X = \{p_X^1, \ldots, p_X^r\}$，其中 $r$ 是 $X$ 在 $SD$ 中的周期总数。则 $X$ 的规律性可表示为 $reg(X) = Max(p_X^1, \ldots, p_X^r)$。例如，在表 1 的数据库中，$reg(S2,S6) = 4$，即 $Max(3, 2, 4)$。 如果一个模式的规律性不超过用户给定的最大规律性阈值 $max\_reg \lambda$（$1 \leq \lambda \leq |SD|$），则称该模式为规则模式。规律性阈值可以设置为数据库大小的百分比，例如，$max\_reg = 10\%$ 的 $|SD|$ 可能表示 $\lambda = 0.1 \times |SD|$。给定 $\lambda$ 和 $SD$，规则模式挖掘问题是发现 $SD$ 中规律性不超过 $\lambda$ 的所有规则模式的完整集合。$RPSD$ 指的是给定 $max\_reg$ 时 $SD$ 中所有规则模式的完整集合。 设 $SD^+$ 和 $SD^-$ 分别表示添加到 $SD$ 和从 $SD$ 中删除的事务集合。更新后的数据库 $USD$ 可通过 $SD \cup SD^+$、$SD \cup SD^-$ 或 $SD \cup SD^+ \cup SD^-$ 获得。给定 $SD$、$SD_i^{+/-}$（$i$ 是 $SD$ 上的更新次数）和 $\lambda$，增量规则模式挖掘是发现 $RP_{USD}$；规则模式挖掘是在保持数据库固定的情况下，随着 $\lambda$ 的变化找到 $RPSD$ 或 $RP_{USD}$。 ## 2. SDR - 树：设计、构建与挖掘 ### 2.1 SDR - 树结构 提出的传感器数据规律性树（SDR - 树）旨在通过单次扫描传感器网络读数来捕获完整的（更新后的）人体传感器网络（BSN）数据。它以紧凑的结构捕获每个传感器时期的所有信息，避免了对传感器数据库的重复扫描。 SDR - 树与 RP - 树类似，有一个根节点和一组子树（根的子节点）。它还维护一个称为传感器数据表（SD - 表）的头表，以捕获每个不同传感器的相对规律性信息。SD - 表中的每个传感器都有一个单独的指针，指向 SDR - 树中携带该传感器的第一个节点。 SDR - 树中有两种类型的节点：普通节点和尾节点。两种节点都维护父节点、子节点和节点遍历指针，而尾节点还会跟踪它作为最后一个节点的所有时期（在一个 tid - 列表中）。因此，$N[t_1, t_2, \ldots, t_n]$ 表示一个尾节点，其中 $N$ 是传感器节点的名称，$t_i$ 是 $N$ 作为最后一个传感器的时期的时隙 ID（$n$ 是从根到该节点的时期总数）。需要注意的是，SDR - 树中的普通节点和尾节点都不维护支持计数。 与 RP - 树中的 R - 表不同，SRD - 树中的 SD - 表按顺序由五个字段组成： 1. 传感器名称（$i$） 2. $i$ 的规律性（$r$） 3. $i$ 最近出现的 tid 4. 一个一位标志（$m$），用于指示 $i$ 是否有任何更改 5. 指向 $i$ 在 SDR - 树中的指针（$p$） SD - 表的结构和构建过程与 RP - 树中的 R - 表有显著差异。每个传感器的规律性（$r$）和 $tl$ 值在构建 SDR - 树并遍历一次后计算得出。只有当传感器数据在当前数据库（例如，原始 $SD$ 或 $SD^+$）的任何时期中被修改（即出现或删除）