原理理解
HBOS(Histogram-based Outlier Score)算法是非参数的异常检测算法。
非参数方法
非参数的方法通常分为两步
- 构建直方图:使用输入数据(训练数据)构造一个直方图。该直方图可以是一元的,或者多元的(如果输入数据是多维的)。
尽管非参数方法并不假定任何先验统计模型,但是通常确实要求用户提供参数,以便由数据学习。例如,用户必须指定直方图的类型(等宽的或等深的)和其他参数(直方图中的箱数或每个箱的大小等)。与参数方法不同,这些参数并不指定数据分布的类型。 - 检测异常点:为了确定一个对象是否是异常点,可以对照直方图检查它。在最简单的方法中,如果该对象落入直方图的一个bin中,则该对象被看作正常的,否则被认为是异常点。
对于更复杂的方法,可以使用直方图赋予每个对象一个异常点得分(outlier scores)。例如令对象的异常点得分为该对象落入的bin的容积的倒数。
使用直方图作为异常点检测的非参数模型的一个缺点是,很难选择一个合适的bin的尺寸。一方面,如果bin尺寸太小,则许多正常对象都会落入空的或稀疏的箱中,因而被误识别为异常点。另一方面,如果bin尺寸太大,则异常点对象可能渗入某些频繁的bin中,因而“假扮”成正常的。
HBOS是一种基于直方图的单变量方法的组合,不能对特征之间的依赖关系进行建模,但是计算速度快,对大数据集友好。其基本假设是数据集的每个维度相互独立。然后对每个维度进行区间(bin)划分,区间的密度越高,异常评分越低。
HBOS算法流程
1.为每个数据维度做出数据直方图。对分类数据统计每个值的频数并计算相对频率。对数值数据根据分布的不同采用以下两种方法:
- 静态宽度直方图:标准的直方图构建方法,在值范围内使用k个等宽箱。样本落入每个桶的频率(相对数量)作为密度(箱子高度)的估计。时间复杂度:$O(n)$
- 2.动态宽度直方图:首先对所有值进行排序,然后固定数量的$\frac{N}{k}$个连续值装进一个箱里,其中N是总实例数,k是箱个数;直方图中的箱面积表示实例数。因为箱的宽度是由箱中第一个值和最后一个值决定的,所有箱的面积都一样,因此每一个箱的高度都是可计算的。这意味着跨度大的箱的高度低,即密度小,只有一种情况例外,超过k个数相等,此时允许在同一个箱里超过$\frac{N}{k}$值。
时间复杂度:$O(n\times log(n))$排序时间复杂度
2.对每个维度都计算出了一个独立的直方图,其中每个箱子的高度表示密度的估计。然后为了使得最大高度为1(确保了每个特征与异常值得分的权重相等),对直方图进行归一化处理。最后,每一个实例的HBOS值(即异常评分)由以下公式计算:
其中:$hist_i(p)$是bin的概率密度,这个公式的意思是,概率密度越低,那么$\text{hist}_i(p)$就越小,那么$\log \left(\frac{1}{\text {hist}_{i}(p)}\right)$就越大,所以异常评分就越高。
$$ H B O S(p)=\sum_{i=0}^{d} \log \left(\frac{1}{\text {hist}_{i}(p)}\right) $$
推导过程:
假设样本p第 i 个特征的概率密度为$p_i(p)$ ,则p的概率密度可以计算为:
$$ P(p)=P_{1}(p) P_{2}(p) \cdots P_{d}(p) $$
两边取对数:
$$ \begin{aligned} \log (P(p)) &=\log \left(P_{1}(p) P_{2}(p) \cdots P_{d}(p)\right) =\sum_{i=1}^{d} \log \left(P_{i}(p)\right) \end{aligned} $$
概率密度越大,异常评分越小,为了方便评分,两边乘以“-1”:
$$ -\log (P(p))=-1 \sum_{i=1}^{d} \log \left(P_{t}(p)\right)=\sum_{i=1}^{d} \frac{1}{\log \left(P_{i}(p)\right)} $$
最后可得:
$$ H B O S(p)=-\log (P(p))=\sum_{i=1}^{d} \frac{1}{\log \left(P_{i}(p)\right)} $$
算法总结
1.异常检测的统计学方法由数据学习模型,以区别正常的数据对象和异常点。使用统计学方法的一个优点是,异常检测可以是统计上无可非议的。当然,仅当对数据所做的统计假定满足实际约束时才为真。
2.HBOS在全局异常检测问题上表现良好,但不能检测局部异常值。但是HBOS比标准算法快得多,尤其是在大数据集上。
代码实现
代码使用的是著名的Python异常检测库 pyod
完成,首先导入所需的库:
import os
import sys
from pyod.models.hbos import HBOS # HBOS模型类
from pyod.utils.data import generate_data # 生成假数据
from pyod.utils.data import evaluate_print # 衡量指标print
from pyod.utils.example import visualize #可视化
设置生成的样本数和异常值比例
contamination = 0.1 # 异常样本的比例
n_train = 200 # 训练样本数
n_test = 100 # 测试样本数
生成数据
# 生成数据
X_train, X_test, y_train, y_test = generate_data(
n_train=n_train,
n_test=n_test,
n_features=2,
contamination=contamination,
random_state=42,
behaviour='new'
)
查看数据大小,其中y
是标签,等于1时是异常样本,等于0时是正常样本
X_train.shape, y_train.shape, X_test.shape, y_test.shape
((200, 2), (200,), (100, 2), (100,))
构建并训练模型,HBOS可以设置如下参数:
- alpha:正则项,默认0.1,避免溢出
- tol:在样本落在bin外面时候的容忍度,默认为0.5
- contamination:异常样本的比例,默认0.1
clf_name = 'HBOS'
clf = HBOS()
clf.fit(X_train)
HBOS(alpha=0.1, contamination=0.1, n_bins=10, tol=0.5)
接下来,获取模型对training data的预测标签和异常分数(outlier scores)
y_train_pred = clf.labels_ # 二元标签 (0: inliers, 1: outliers)
y_train_scores = clf.decision_scores_ # raw outlier scores
对testing data做预测和计算异常分数
y_test_pred = clf.predict(X_test) # outlier 标签 (0 或 1)
y_test_scores = clf.decision_function(X_test) # outlier scores
分布衡量模型在traning data和test data上的性能,evaluate_print
的调用方式为
evaluate_print(模型名字, 真实的target向量, outlier scores)
print("\nOn Training Data:")
evaluate_print(clf_name, y_train, y_train_scores)
print("\nOn Test Data:")
evaluate_print(clf_name, y_test, y_test_scores)
On Training Data:
HBOS ROC:0.9947, precision @ rank n:0.8
On Test Data:
HBOS ROC:0.9744, precision @ rank n:0.6
可视化,visualize
的调用方式为
visualize(模型名字, 训练标签, 真实训练标签, 测试数据, 真实测试标签, 训练异常分数, 测试浴场分数, show_figure=是否显示图片, save_figure=是否保存图片)
visualize(clf_name, X_train, y_train, X_test, y_test, y_train_pred,
y_test_pred, show_figure=True, save_figure=False)