基于有偏采样的集成异常值检测与分层贝叶斯模型消息长度近似

### 基于有偏采样的集成异常值检测与分层贝叶斯模型消息长度近似 #### 基于有偏采样的集成异常值检测 在异常值检测领域，若所选异常值检测算法的时间复杂度为 \(O(n^2)\)，操作步骤的总时间复杂度为 \(O(cm^2n^2)\)。在算法的投票步骤中，每个子集的数据点预期数量会减少到 \(m′n^2\)，其中 \(m′\) 是算法步骤 2 后的预期采样率，且 \(m′ < m\)。最终，BSS 和 DBSS 相对于数据点数量的时间复杂度均为 \(O(n^2)\)，这与所选异常值检测算法和随机子采样（RS）算法的时间复杂度相似。不过，常数 \(c\)、\(m\) 以及 \(m′\) 的选择可能会影响时间复杂度。由于 BSS 和 DBSS 算法具有并行化集成计算的潜力，时间复杂度有望进一步降低至接近线性。 ##### 数据集 在实验中，使用了两种类型的合成数据集（共 11 个不同的合成数据集）和 3 个来自 UCI 机器学习库的公开真实数据集。各数据集的属性总结如下表： | 数据集 | 数据点数量 | 维度 | 类别数量 | 异常值标签 | | --- | --- | --- | --- | --- | | Synthetic - D | 2000 | 可变(5:5:50) | 5 | 添加 5% 均匀噪声 | | Synthetic - M | 5000 | 10 | 5 | 马氏距离 | | UCI Covertype | 5743 | 10 | 7 | ‘4’ | | UCI Vowels | 1456 | 12 | 4 | ‘1’ | | UCI Protein | 5575 | 9 | 2 | 小于等于 0 | 各数据集异常值标签的分配方式如下： 1. **Synthetic - D**：生成 10 个该组合成数据集，通过将数据维度从 5 改变到 50，同时固定数据点数量和聚类数量，以评估方法的检测准确性和可扩展性。并且向所有 Synthetic - D 数据集添加 5% 的异常值。 2. **Synthetic - M**：使用不同类型的异常值来评估算法，通过每个数据点到其聚类中心的马氏距离来标记数据集。 3. **Covertype**：选择数值特征（即 1 到 9 和 44），选取数据点数量最少的标记子集并将其标记为异常值，异常值率为 2.23%。 4. **Protein**：选择第一个属性作为标签属性，值小于等于 0 的记录被视为异常值记录，异常值率为 2.55%。 5. **Vowels**：使用训练数据集中的记录，类别标签为 1、6、7 和 8，从类别 1 中随机选择 50 个数据点并将其标记为异常值，异常值率为 3.4%。 ##### 异常值检测准确性 将 BSS 和 DBSS 算法与子采样（RS）算法进行比较，研究不同采样率对检测准确性的影响。改变采样率 \(m\) 从 0.1 到 0.9，同时考虑最近邻数量 \(k\) 对检测准确性的影响。改变 \(k\) 为 2、5 和 10，发现除 Covertype 数据集外，所有数据集在 \(k