题目内容

你负责监控网络流量以检测异常行为。为了及时发现潜在的安全威胁，你需要对大量的网络流量数据进行异常检测。由于数据维度高且存在噪声，你决定使用孤立森林(lsolation Forest)算法来实现异常检测。

请你编写一个程序，使用Python和NumPy库，对给定的数据集进行异常检测。具体要求如下:

1.读取输入数据集，包含 $(N)$ 个样本，每个样本有 $(M)$ 个特征。

2.读取孤立森林的参数:

• 树的数量 $(T)$ 。

• 每棵树的子样本数量 $(ψ)$ (即每棵树使用的样本数)。

3、在训练过程中，对于每棵树:

• 使用随机采样(无放回)从原始数据集中抽取 $(ψ)$ 个样本，作为该树的训练数据。

• 构建一棵随机二叉树，节点的分裂特征和分裂点均随机选择，直到达到高度限制 $\lceil \log_2(n) \rceil$ 或树的节点数为 $1$ 。

• 记录每个样本在树中的路径长度。

4.计算异常分数:

• 通过计算每个样本在所有树上的路径长度的平均值，并根据该平均路径长度计算异常分数。

• 异常分数的公式: $score=2\frac{-E_h}{c}$ ,其中 $E_h$ 是平均路径长度，$c$ 是由样本数 $ψ$ 计算的常数。

5.在训练完成后，根据异常分数，将样本标记为正常或异常:

• 若异常分数大于阈值 $(r)$ ，则标记为异常样本。

• 阈值 $(r)$ 可取默认值 $(0.5)$ 。

6.输出每个样本的异常分数和标签。

输入描述

• 第一行包含两个整数 $(N)$ 和 $(M)$ ，表示样本数量和特征数量.

• 接下来的 $(N)$ 行，每行包含 $(M)$ 个浮点数，表示每个样本的特征值,特征值之间用空格分隔。

• 最后一行包含两个整数 $(T)$ 和 $(ψ)$ ，用空格分隔。

输出描述

输出 $(N)$ 行，每行包含一个浮点数和一个整数，表示对应样本的异常分数和标签(正常为 $0$ ，异常为 $1$ )，用空格分隔，浮点数保留四位小数，使用 {$x:.4f$} 格式化输出。

补充说明

• 孤立森林(Isolation Forest)

孤立森林通过随机构建二叉树，将样本逐步划分。异常样本更容易被孤立，平均路径长度较短。

• 路径长度计算

在树中，从根节点到达叶节点的路径长度。

对于未完全分割的叶节点，使用调整后的路径长度。

• 异常分数计算公式为: $s(x,ψ)=2^-{\frac{E(h(x))}{c(ψ)}}$

其中:

• $(E(h(x)))$ 为样本 $(x)$ 在所有树中的平均路径长度。

• $(c(ψ))$ 是平均路径长度的调整系数，定义为:

• $c(ψ)=2H(ψ-1)-(\frac{2(ψ-1)}{ψ})$

• $(H(i))$ 为第 $(1)$ 个调和数,$(H(i) =ln(i)+γ), (γ≈0.5772156649)$ 欧拉常数。

• 禁止使用现成的孤立森林库，如 $scikit-lear$ 等，需要自行实现算法逻辑。

• 为了简化计算，调和数 $H(i)$ 可以近似为 $ln(i)+0.5772$ 。

• 由于涉及随机过程，为了结果可重复，可以在程序中设置随机种子: $np.random.seed(0)$ ,所有随机过程皆由此实现。

样例1

输入

10 2
1.0 2.0
2.0 1.0
1.5 1.5
8.0 8.0
9.0 8.0
8.5 9.0
0.0 0.0
9.0 9.0
10.0 10.0
5.0 5.0
100 5

输出

0.5070 1
0.4878 0
0.4966 0
0.4749 0
0.4651 0
0.4679 0
0.5430 1
0.4651 0
0.4981 0
0.4907 0