基于孤立森林采样策略的企业异常用水模式检测

林青轩，郭 强，邓春燕，王雅静，刘建国

(1.上海理工大学复杂系统科学研究中心,上海 200093; 2.上海财经大学会计与财务研究院,上海 200433)

0 引言

企业异常用水模式检测是指从企业用水量数据中找出异常的模式，企业用能数据如用水量和用电量是企业生产经营状况最直接的反映，分析企业用水量数据能够一定程度上检测出企业生产经营上的异常行为。公共安全部门若能及时发现生产运作状态异常的企业，并对其进行事前干预，对于保护公民的人身安全和维护社会安全有十分重要的意义。另外，以往公共安全部门多采用现场稽查的形式对企业是否正常运营进行判断，十分耗费人力物力而且不能及时地进行监管。因此，公共安全部门亟需一套行之有效的企业异常用水模式检测方法。

机器学习方法已经被应用于此类发现异常模式的任务，已经有效应用于信用卡反欺诈[1-2]、垃圾网页识别[3-4]和用户异常用电识别[5]等领域。在解决此类问题的过程中，通常会遇到不平衡分类的问题，即真实数据集中两类样本数量差异巨大，且真实数据中含有大量噪声样本。传统分类算法的预测目标是降低总体的分类错误率，为了提升整体的准确度，分类器更关注多数类，结果导致在测试集上的预测结果偏向为多数类，虽然整体准确度很高，但是没有对少数类进行有效的预测。近年来，大量学者研究通过改变数据分布来解决不平衡分类问题，其中，过采样(over-sampling)和欠采样(under-sampling)是两种最常用的技术[6]，典型的方法有随机欠采样技术、综合小类过采样技术(Synthetic Minority Over-sampling Technique,SMOTE)[7]和自适应综合过采样(Adaptive Synthetic Sampling,ADASYN)[8]等。过采样是一种对少数样本进行扩充使得样本数接近平衡的采样方法，它虽然不会产生重复样本，却可能引入噪声[9]，不适合用于含有较多噪声的场景。卢晓勇等[3]提出用随机欠采样和随机森林的方法检测垃圾网页，但随机欠采样方法仅仅通过抽样的方式简单平衡了类别并没有考虑数据集中样本“代表性”的问题，每个样本以相同的概率被抽取。因此，本文先考虑样本“代表性”的问题，基于孤立森林算法(Isolation Forest,iForest)计算多数类中每个样本点的“孤立”程度，“孤立”程度一定程度上表示了样本的“代表性”，越被“孤立”的样本点“代表性”则越低；再通过优先对“代表性”高的样本进行采样，然后将抽取的样本和少数类合并构建较平衡的训练数据集，以解决不平衡分类问题。

iForest算法[10]相比基于直方图的异常得分算法(Histogram-based Outlier Score,HBOS)[11]和局部异常因子算法(Local Outlier Factor,LOF)[12]，iForest不要求特征间独立且无需计算距离，速度较快，更适合企业异常用水模式检测场景下特征之间存在相关性的低频短时间序列数据。

获得较平衡的训练数据集后，有监督的机器学习方法可以更好地执行预测的任务。本文利用XGBoost这一有监督的机器学习方法对企业异常用水模式进行预测，XBGoost[13]是2016年由Chen提出的对梯度提升树(Gradient Boosting Decision Tree,GBDT)算法的改进和实现，相比于传统的GBDT只考虑了损失函一阶的导数信息，XBGoost对损失函数进行了二阶泰勒展开，还在目标函数中加入了正则项，有效地防止过拟合，具有效果好、速度快的优点。在某市企业用水量数据集上的实验表明，基于iForest采样策略训练的XGBoost分类器可以提升企业异常用水模式的检测效果。

1 孤立森林算法

iForest算法是一种无监督的方法，该算法主要通过从训练数据集中随机选取一个特征，在该特征的最大值最小值之间随机选取一个分裂点，小于分裂点的进入左侧分支，大于或等于分裂点的进入右侧分支；不断重复上述过程直到只剩一个样本或相同样本或达到树的深度限制，然后通过路径长度来表示一个样本点被“孤立”的程度。路径长度h(x)指样本点x从根节点到外部节点所经过的二叉树的边数，通常路径长度较小的样本被“孤立”的程度高。路径长度h(x)的计算公式为

h(x)=e+C(T.size)

(1)

其中，e表示数据x从子树(iTree)的根节点到叶节点过程中经过的边的数目，C(T.size)表示在一棵用T.size条样本数据构建的二叉树的平均路径长度。C(n)的计算公式为

(2)

其中，n为样本个数，H(n-1)可用ln(i)+0.577 215 664 9(欧拉常数)估算，以同样的方式构建包含多棵iTree，则样本的“孤立”程度即可基于路径长度被检测出来，可以通过S(x,n)分值判断。定义如下：

(3)

其中，E(h(x))是样本点x在iForest中所有孤立树的路径长度的平均值，n表示单棵iTree的训练样本数。

2 基于孤立森林采样策略的企业异常用水模式检测方法

基于iForest算法计算不平衡数据集中多数类样本“代表性”得分，本文改进了对多数类样本的采样策略，优先对多数类中样本“代表性”得分高的样本进行采样，然后和少数类样本构建更加平衡的训练数据集。

假设将训练数据集U{(xi,yi)|(x1,y1),…,(xu,yu)}中样本数较多的一类称为多数类N{(xi,yi)|(x1,y1),…,(xu,yu)}，样本数较少的一类称为少数类S{(xi,yi)|(xl+1,yl+1),…,(xu,yu)}。基于iForest的欠采样方法首先计算多数类N中样本的“孤立”程度得分scl，即样本的“代表性”；再将多数类N中的样本按照得分scl排序，以采样比例k%从多数类N中按照排序抽取组成较平衡的训练数据集N′；最后将新的训练数据集N′和少数类S合并构成较平衡的训练数据集U′；然后用XGBoost对较平衡的训练数据集U′分类训练，获得分类器C；最后用分类器C对测试数据集T{xj|x1,…,xt}进行分类，得到测试数据集的分类结果L{yj|y1,…,yt}。

方法：基于iForest采样策略的二分类预测方法。

输入：

不平衡训练数据集及其分类U{(xi,yi)|(x1,y1),…,(xu,yu)}；

测试数据集T{xj|x1,…,xt}。

输出：

测试数据集的分类L{yj|y1,…,yt}。

步骤：

1) 将不平衡训练数据集U按类别分为多数类N和少数类S；

2)n=多数类N的样本数；

3)s=少数类S的样本数；

4)k%=采样比例；

5) 建立i棵子树iTree，构建iForest：

(1) 从训练数据集中随机选择n个样本点，作为子树的根节点；

(2) 如果当前树的高度e超过设置高度h，则返回子树；

(3) 否则，随机选择一个特征q；

(4) 随机在特征q的最大值和最小值之间选择切分点p；

(5) 将小于p的样本放入左子节点，将大于p的样本放入右子节点；

(6) 在子节点中递归步骤b-e；

6) 利用构建好的iForest计算多数类中的样本得分scl；

7) 对多数类N中每个样本按照得分scl升序排序；

8) 抽取前k%的样本组成新的样本集合N′；

9) 将集合N′和小类S合并为平衡的数据集U′；

10) 使用XGBoost算法对数据集U′进行分类训练，得到分类器C；

11) 使用分类器C对测试数据集T进行预测，最终得到测试集的分类L。

3 实验和实验结果

3.1 数据集及评价指标

本文采用的数据集为某市7 604家企业13个月的用水量数据，数据采集间隔为1个月，其中正常企业为7 051家，标记为异常的样本为553家，异常样本占比约为7.3%。

通过以月和季度为周期构造统计性特征，计算均值、方差、极差、偏度和峰度，并且通过对数差分的方式提取每两个月之间企业用水量的波动特征，最终得到29维的特征。

本研究采用机器学习中常用的标准指标作为评价指标，主要有召回率(Recall)和AUC(Area Under ROC Curve)等。AUC值用来评价预测异常模式效果的好坏，召回率则用来评价分类器是否将异常模式“全面”的预测出来。

3.1.1 AUC

AUC[14]是指ROC(Receiver Operating Characteristic)曲线下方面积，AUC用一个数值来表示分类器效果的好坏，较大的AUC值表示较好的预测性能。AUC的范围属于(0.5,1.0)，0.5表示随机预测的情况，1.0表示最理想的分类情况。

ROC曲线[15]所在平面的横坐标是假正例率(False Positive Rate,FPR)，纵坐标是真正例率(True Positive Rate,TPR)。对某个分类器而言，根据其在测试样本上的表现得到一个TPR和FPR点对。这样，此分类器就可以映射成ROC平面上的一个点。调整这个分类器分类时候使用的阈值，我们就可以得到一个经过(0,0)，(1,1)的曲线，这就是此分类器的ROC曲线。

TRP和FPR的计算公式为

(4)

(5)

其中，真正例(True Positive,TP)为被模型预测为正的正样本；假负例(False Negative,FN)为被模型预测为负的正样本；假正例(False Positive,FP)为被模型预测为正的负样本；真负例(True Negative,TN)为被模型预测为负的负样本。

3.1.2 查全率

上节计算TRP和FPR中提到，对于二分类问题，可以将样本根据预测结果和真实类别组合划分为TP、FN、FP和TN，查全率[14](Recall)表示在被预测为正例的样本中有多少是真实的正例，计算公式为

(6)

3.2 实验结果

计算样本“代表性”的方法有多种，常用的无监督方法有iForest、HBOS和LOF，LOF的特点是根据样本局部的密度来计算样本的得分，但是忽略样本领域外的样本对其产生的影响，HBOS假设每个特征独立，将每个特征以直方图的形式离散化，然后计算特征在离散区间上频率的乘积作为样本的得分，该方法简单、快速，但是前提假设较强，当特征之间相关性较强时效果会受到影响，iForest通过样本被“孤立”的程度作为样本的得分，并且建立多颗相互独立的子树，综合考虑多颗子树的得分。本文分别测试该3种方法在该数据集的表现，如表1所示，综合比较3种方法预测的AUC和查全率，选择效果较好的iForest作为计算样本“代表性”的方法。

表1 3种无监督方法的预测效果Tab.1 Comparison of three unsupervised methods

为了构造较平衡的训练集，需要确定从大类样本中进行欠采样的比例，本文分别对欠采样比例从0到1进行实验，作为对比，本文分别用XGBoost、基于随机欠采样的XGBoost和基于iForest的XGBoost方法对异常用水模式进行预测，得到的结果为十折交叉验证后的AUC的平均值。

由图1和表2可知，基于iForest的欠采样的预测在采样比例为0.2时效果最佳，AUC值达到0.927，基于随机欠采样的预测在采样比例为0.7时最佳，AUC值为0.885，当不进行欠采样处理时，预测结果的AUC值为0.877。由此可知，在该不平衡数据集下，若对训练集做随机欠采样可以提升预测效果，但是采样过程为随机抽取，若数据集中含有较多“噪音”或是潜在未被标注的异常样本，会被等概率抽取进入训练数据集，从而影响分类器的训练，因此提升效果并不显著，而基于iForest采样策略针对“代表性”高的样本进行优先抽取，一定程度上优先避开了“噪音”样本，故预测结果比基于随机欠采样的AUC提升了约4.7%，查全率提升了21.6%。结果说明，本文提出的企业异常用水模式检测方法在考虑样本“代表性”后进行欠采样可以提升预测效果。

图1 不同采样比例下XGBoost的预测效果对比Fig.1 Comparison of XGBoost in different sampling proportion

表2 不同采样方式下XGBoost的预测效果Tab.2 Result of XGBoost in different sampling methods

为进一步验证在类似场景下该方法的有效性，本文还在社交网络的场景下利用该方法进行了实验，该数据集为某社交网络上用户的活跃度数据，数据采集间隔为周，连续采集了14周的用户活跃度数据，该数据集共有3 099位用户，其中普通用户数为2 790位，非普通用户数为309位，约占总样本的10%。基于随机欠采样方法的预测结果的AUC值为0.669，查全率为0.805；基于iForest采样策略的预测结果的AUC值为0.901，查全率为0.850，相较于基于随机欠采样的方法，AUC值提升了34.7%，召回率提了5.6%。结果说明，该方法在社交网络场景下也具有一定的有效性。

4 总结

本文提出的基于iForest采样策略的方法在企业异常用水模式检测场景中，面对不平衡分类问题取得了较好的效果。首先基于iForest算法计算多数类中样本点的“孤立”程度，通过“孤立”程度衡量样本“代表性”，然后按样本“代表性”得分进行排序，从“代表性”高的样本中优先进行欠采样，然后与少数类样本构成较平衡的训练数据集，训练XGBoost分类器，最后对企业异常用水模式进行预测。在某市的企业用水量数据集上，该方法对企业异常用水模式的预测结果AUC值和查全率可达到0.927和0.891，较基于随机欠采样的方法的0.884和0.733分别提升了4.7%和21.6%。另外，本文还在社交网络场景下利用该方法进行实验，同样也具有一定的有效性。未来的研究可以进一步探索在其他类似不平衡分类的场景下该方法的预测效果。