数据流属性异常值检测算法研究

### 数据流属性异常值检测算法研究 #### 1. 聚类维护与过期数据处理 当聚类数量达到 m 时，需要减少聚类数量以避免超出限制。具体做法是选择两个距离最近的聚类进行合并。由于 LHCF 具有可加性，合并两个 LHCF 相对容易。同时，还需合并两个 OSQ 队列，步骤如下： 1. 合并两个 OSQ 队列，使其按时间戳保持有序。 2. 对于每个节点，找到其在另一个合并聚类中的邻居，以更新数组 preNL 和计数 sucNC。 3. 由于合并后节点的邻居数量只会增加，安全内点在新合并的队列中仍为安全内点，因此不更新安全内点的邻域以节省合并成本。 此外，算法还需消除过期的数据元组。在时间 t，应丢弃所有时间戳早于 t - W + 1 的 OSQ 节点以及早于 t - W + 1 的 TCF。当某个聚类的 LHCF 中不再有 TCF 时，应移除该聚类。 #### 2. 异常值查询模块 异常值查询模块利用每个聚类的 OSQ 队列来查找异常值。具体操作如下： 1. 扫描每个聚类的 OSQ 队列，获取该聚类中每个数据元组的邻居数量。 2. 对于每个 OSQ 节点，在数组 preNL 上进行简单的二分查找（时间复杂度为 O(log k)），可返回当前滑动窗口中最旧的未过期前邻居。 3. 根据数组中最旧未过期前邻居的索引，可得出未过期前邻居的数量，记为 count pre。 4. 将 count pre 和 sucNC 相加得到邻居总数。若该总数小于 k，则将其作为属性异常值报告给用户。 需要注意的是，对于数据元组少于 k 个的微小聚类，不进行异常值检测，因为若进行检测，其所有元组都会被判定为异常值，这在实际应用中没有意义。 #### 3. 近似 AOMA 算法 为解决内存空间有限的问题，提出了近似 AOMA 算法。该算法通过丢弃部分数据元组来降低内存成本，具体步骤如下： 1. **数据丢弃策略**：每个聚类中有异常值、安全内点和不安全内点三种元组。异常值不能丢弃，不安全内点可能在窗口滑动时成为异常值，因此优先保留异常值和不安全内点，丢弃安全内点。当安全内点的数量超过 μn（1 > μ > 0，μ 由可用内存大小和窗口内数据元组数量决定）时，随机选择部分安全内点丢弃。 2. **属性替换**：由于丢弃元组后，OSQ 节点的 preNL 属性无法准确估计前邻居数量，且该属性占用内存较多，因此用两个新属性替代： - **pid**：节点的顺序 ID，新 OSQ 节点的 pid 为前一个节点的 pid 加 1。 - **pidexp**：整个 OSQ 队列的属性，即最新过期节点的 pid。 - **preRatio**：节点的前邻居中安全内点的数量与当前 OSQ 队列中安全内点总数的比值，在节点创建时计算。 通过这两个新属性，可按以下方式估计前邻居数量： 对于一个包含 n 个数据元组的聚类中的节点 q，假设每个节点的邻居在到达时间上均匀分布，则节点 q 的前邻居数量可估计为： $N_p \approx N/n \cdot (q.pid - pidexp)$ 其中，N 是节点首次到达时未被丢弃的邻居数量。由于大多数数据节点是安全内点，可使用安全内点数量近似表示数据节点数量，因此有： $N/n \approx q.preRatio$ 则时间 t 时节点 q 的前邻居数量可仅根据其自身属性计算： $N_p \approx q.preRatio \cdot (q.pid - pidexp)$ 以下是近似 AOMA 算法的伪代码： ```plaintext Require: m 个由 k - means 算法创建的初始聚类 C1...Cm，当前时间 t，用户给定参数 R, k, µ，聚类 c 中的数据元组数量为 nc。 Ensure: 时间 t 时滑动窗口内的所有属性异常值。 1: safe_inlies = 0, pid_inc = 0. 2: for each newcomer data tuple p do 3: Call cluster maintenance module update cluster info. 4: safe_pre = 0. 5: Create new OSQ node q for p and append to the queue of its cluster. 6: Scan OSQ and return all nodes lie within R from q. 7: for each returned node qpre do 8: if ++qpre.sucNC > k then 9: safe_inlies++, safe_pre++. 10: Mark qpre as safe inlier. 11: if safe_inliers > μnc then 12: Randomly choose a safe inlier to remove. 13: q.preRatio = safe_pre / safe_inlies 14: for each cluster c in current window do 15: for each node q in the OSQ queue of c do 16: if q.sucNC < k then 17: count_pre = q.preRatio · (q.pid - pidexp) 18: if co ```