全面剖析用于人工智能isolation_forest算法技术
随着机器学习近年来的流行，尤其是深度学习的火热。机器学习算法在很多领域的应用越来越普遍。最近，作者在一家广告公司做广告点击反作弊算法研究工作。想到了异常检测算法，并且上网调研发现有一个算法非常火爆，那就是本文要介绍的算法 isolation forest，简称 iforest 。
南大周志华老师的团队在2010年提出一个异常检测算法isolation forest，在工业界很实用，算法效果好，时间效率高，能有效处理高维数据和海量数据，这里对这个算法进行简要总结。
itree的构造
提到森林，自然少不了树，毕竟森林都是由树构成的，那么我们在看isolation forest（简称iforest）前，我们先来看看isolation-tree（简称itree）是怎么构成的，itree是一种随机二叉树，每个节点要么有两个女儿，要么就是叶子节点，一个孩子都没有。给定一堆数据集d，这里d的所有属性都是连续型的变量，itree的构成过程如下：
随机选择一个属性attr；
随机选择该属性的一个值value；
根据attr对每条记录进行分类，把attr小于value的记录放在左女儿，把大于等于value的记录放在右孩子；
然后递归的构造左女儿和右女儿，直到满足以下条件：
传入的数据集只有一条记录或者多条一样的记录；
树的高度达到了限定高度；
itree构建好了后，就可以对数据进行预测啦，预测的过程就是把测试记录在itree上走一下，看测试记录落在哪个叶子节点。itree能有效检测异常的假设是：异常点一般都是非常稀有的，在itree中会很快被划分到叶子节点，因此可以用叶子节点到根节点的路径h(x)长度来判断一条记录x是否是异常点；对于一个包含n条记录的数据集，其构造的树的高度最小值为log(n)，最大值为n-1，论文提到说用log(n)和n-1归一化不能保证有界和不方便比较，用一个稍微复杂一点的归一化公式：
s(x,n)就是记录x在由n个样本的训练数据构成的itree的异常指数，s(x,n)取值范围为[0,1]异常情况的判断分以下几种情况：
越接近1表示是异常点的可能性高；
越接近0表示是正常点的可能性比较高；
如果大部分的训练样本的s(x,n)都接近于0.5，整个数据没有明显的异常。
由于是随机选属性，随机选属性值，一棵树这么随便搞肯定是不靠谱，但是把多棵树结合起来就变强大了；
iforest的构造
itree搞明白了，我们现在来看看iforest是怎么构造的，给定一个包含n条记录的数据集d，如何构造一个iforest。iforest和random forest的方法有些类似，都是随机采样一部分数据集去构造每一棵树，保证不同树之间的差异性，不过iforest与rf不同，采样的数据量psi不需要等于n，可以远远小于n，论文中提到采样大小超过256效果就提升不大了，并且越大还会造成计算时间的上的浪费，为什么不像其他算法一样，数据越多效果越好呢，可以看看下面这两个个图：
左边是原始数据，右边是采样了数据，蓝色是正常样本，红色是异常样本。可以看到，在采样之前，正常样本和异常样本出现重叠，因此很难分开，但我们采样之和，异常样本和正常样本可以明显的分开。
除了限制采样大小ψ以外，我们还要给每棵itree设置最大高度为l=ceilng(log2ψ)，这是因为异常数据记录都比较少，其路径长度也比较低，而我们也只需要把正常记录和异常记录区分开来，因此只需要关心低于平均高度的部分就好，这样算法效率更高，不过这样调整了后，后面可以看到计算h(x)需要一点点改进，先看iforest的伪代码：
iforest构造好后，对测试进行预测时，需要进行综合每棵树的结果，于是
e(h(x))表示记录x在每棵树的高度均值，另外h(x)计算需要改进，在生成叶节点时，算法记录了叶节点包含的记录数量，这时候要用这个数量size估计一下平均高度，h(x)的计算方法如下：
对高维数据的处理
在处理高维数据时，可以对算法进行改进，采样之后并不是把所有的属性都用上，而是用峰度系数kurtosis挑选一些有价值的属性，再进行itree的构造，这跟随机森林就更像了，随机选记录，再随机选属性。
只使用正常样本
这个算法本质上是一个无监督学习，不需要数据的类标，有时候异常数据太少了，少到我们只舍得拿这几个异常样本进行测试，不能进行训练，论文提到只用正常样本构建iforest也是可行的，效果有降低，但也还不错，并可以通过适当调整采样大小来提高效果。
总结
iforest具有线性时间复杂度。因为是ensemble的方法，所以可以用在含有海量数据的数据集上面。通常树的数量越多，算法越稳定。由于每棵树都是互相独立生成的，因此可以部署在大规模分布式系统上来加速运算。
iforest不适用于特别高维的数据。由于每次切数据空间都是随机选取一个维度，建完树后仍然有大量的维度信息没有被使用，导致算法可靠性降低。高维空间还可能存在大量噪音维度或无关维度（irrelevant attributes），影响树的构建。对这类数据，建议使用子空间异常检测（subspace anomaly detection）技术。此外，切割平面默认是axis-parallel的，也可以随机生成各种角度的切割平面，详见“on detecting clustered anomalies using sciforest”。
iforest仅对global anomaly 敏感，即全局稀疏点敏感，不擅长处理局部的相对稀疏点 （local anomaly）。目前已有改进方法发表于pakdd，详见“improving iforest with relative mass”。
iforest推动了重心估计（mass estimation）理论发展，目前在分类聚类和异常检测中都取得显著效果，发表于各大顶级数据挖掘会议和期刊（如sigkdd，icdm，ecml）。
注意
目前燕哥还没有发现有java开源库实现了该算法。目前只有python机器学习库scikit-learn的0.18版本对此算法进行了实现。而我的项目绝大多数都是java实现的，因此我需要自己实现该算法。算法源码已实现并开源到我的github上，读者可以下载源码并用idea集成开发环境直接打开项目，并运行测试程序以查看算法的检测效果。
电气五防和微机五防的区别
爱立信谈3GPP Release 19
电子负载是如何实现过压、过流、短路、过热等保护功能的呢？
加密货币借记卡提供商Wirex在欧洲各地推出了Iban的功能
智慧医疗安防市场未来大有潜力可挖
全面剖析用于人工智能isolation_forest算法技术
dvdt滤波器的优点
Vayyar推新款毫米波3D成像片上系统评估套件
一种新型的生物质核壳微囊
虚拟现实的三个特征_虚拟现实的起源
4G路由器使用技巧与优势解析
浅谈智能箱式变电站的功能
以信息技术“点亮”未来能源，迈威通信携光储通信系统解决方案出击SNEC
ZLG致远电子基于LoRa推出无线低功耗网络协议
光纤连接器的性能特点、损耗和衰减
适用于智慧银行的音视频系统整体解决方案
WebSocket有什么优点
四足机器人将是产业下一个爆发点?
给SiC FET设计PCB有哪些注意事项？
静电计级运算放大器ADA4530-1的性能及应用
南大周志华老师的团队在2010年提出一个异常检测算法isolation forest，在工业界很实用，算法效果好，时间效率高，能有效处理高维数据和海量数据，这里对这个算法进行简要总结。
itree的构造
提到森林，自然少不了树，毕竟森林都是由树构成的，那么我们在看isolation forest（简称iforest）前，我们先来看看isolation-tree（简称itree）是怎么构成的，itree是一种随机二叉树，每个节点要么有两个女儿，要么就是叶子节点，一个孩子都没有。给定一堆数据集d，这里d的所有属性都是连续型的变量，itree的构成过程如下：
随机选择一个属性attr；
随机选择该属性的一个值value；
根据attr对每条记录进行分类，把attr小于value的记录放在左女儿，把大于等于value的记录放在右孩子；
然后递归的构造左女儿和右女儿，直到满足以下条件：
传入的数据集只有一条记录或者多条一样的记录；
树的高度达到了限定高度；
itree构建好了后，就可以对数据进行预测啦，预测的过程就是把测试记录在itree上走一下，看测试记录落在哪个叶子节点。itree能有效检测异常的假设是：异常点一般都是非常稀有的，在itree中会很快被划分到叶子节点，因此可以用叶子节点到根节点的路径h(x)长度来判断一条记录x是否是异常点；对于一个包含n条记录的数据集，其构造的树的高度最小值为log(n)，最大值为n-1，论文提到说用log(n)和n-1归一化不能保证有界和不方便比较，用一个稍微复杂一点的归一化公式：
s(x,n)就是记录x在由n个样本的训练数据构成的itree的异常指数，s(x,n)取值范围为[0,1]异常情况的判断分以下几种情况：
越接近1表示是异常点的可能性高；
越接近0表示是正常点的可能性比较高；
如果大部分的训练样本的s(x,n)都接近于0.5，整个数据没有明显的异常。
由于是随机选属性，随机选属性值，一棵树这么随便搞肯定是不靠谱，但是把多棵树结合起来就变强大了；
iforest的构造
itree搞明白了，我们现在来看看iforest是怎么构造的，给定一个包含n条记录的数据集d，如何构造一个iforest。iforest和random forest的方法有些类似，都是随机采样一部分数据集去构造每一棵树，保证不同树之间的差异性，不过iforest与rf不同，采样的数据量psi不需要等于n，可以远远小于n，论文中提到采样大小超过256效果就提升不大了，并且越大还会造成计算时间的上的浪费，为什么不像其他算法一样，数据越多效果越好呢，可以看看下面这两个个图：
左边是原始数据，右边是采样了数据，蓝色是正常样本，红色是异常样本。可以看到，在采样之前，正常样本和异常样本出现重叠，因此很难分开，但我们采样之和，异常样本和正常样本可以明显的分开。
除了限制采样大小ψ以外，我们还要给每棵itree设置最大高度为l=ceilng(log2ψ)，这是因为异常数据记录都比较少，其路径长度也比较低，而我们也只需要把正常记录和异常记录区分开来，因此只需要关心低于平均高度的部分就好，这样算法效率更高，不过这样调整了后，后面可以看到计算h(x)需要一点点改进，先看iforest的伪代码：
iforest构造好后，对测试进行预测时，需要进行综合每棵树的结果，于是
e(h(x))表示记录x在每棵树的高度均值，另外h(x)计算需要改进，在生成叶节点时，算法记录了叶节点包含的记录数量，这时候要用这个数量size估计一下平均高度，h(x)的计算方法如下：
对高维数据的处理
在处理高维数据时，可以对算法进行改进，采样之后并不是把所有的属性都用上，而是用峰度系数kurtosis挑选一些有价值的属性，再进行itree的构造，这跟随机森林就更像了，随机选记录，再随机选属性。
只使用正常样本
这个算法本质上是一个无监督学习，不需要数据的类标，有时候异常数据太少了，少到我们只舍得拿这几个异常样本进行测试，不能进行训练，论文提到只用正常样本构建iforest也是可行的，效果有降低，但也还不错，并可以通过适当调整采样大小来提高效果。
总结
iforest具有线性时间复杂度。因为是ensemble的方法，所以可以用在含有海量数据的数据集上面。通常树的数量越多，算法越稳定。由于每棵树都是互相独立生成的，因此可以部署在大规模分布式系统上来加速运算。
iforest不适用于特别高维的数据。由于每次切数据空间都是随机选取一个维度，建完树后仍然有大量的维度信息没有被使用，导致算法可靠性降低。高维空间还可能存在大量噪音维度或无关维度（irrelevant attributes），影响树的构建。对这类数据，建议使用子空间异常检测（subspace anomaly detection）技术。此外，切割平面默认是axis-parallel的，也可以随机生成各种角度的切割平面，详见“on detecting clustered anomalies using sciforest”。
iforest仅对global anomaly 敏感，即全局稀疏点敏感，不擅长处理局部的相对稀疏点 （local anomaly）。目前已有改进方法发表于pakdd，详见“improving iforest with relative mass”。
iforest推动了重心估计（mass estimation）理论发展，目前在分类聚类和异常检测中都取得显著效果，发表于各大顶级数据挖掘会议和期刊（如sigkdd，icdm，ecml）。
注意
目前燕哥还没有发现有java开源库实现了该算法。目前只有python机器学习库scikit-learn的0.18版本对此算法进行了实现。而我的项目绝大多数都是java实现的，因此我需要自己实现该算法。算法源码已实现并开源到我的github上，读者可以下载源码并用idea集成开发环境直接打开项目，并运行测试程序以查看算法的检测效果。
电气五防和微机五防的区别
爱立信谈3GPP Release 19
电子负载是如何实现过压、过流、短路、过热等保护功能的呢？
加密货币借记卡提供商Wirex在欧洲各地推出了Iban的功能
智慧医疗安防市场未来大有潜力可挖
全面剖析用于人工智能isolation_forest算法技术
dvdt滤波器的优点
Vayyar推新款毫米波3D成像片上系统评估套件
一种新型的生物质核壳微囊
虚拟现实的三个特征_虚拟现实的起源
4G路由器使用技巧与优势解析
浅谈智能箱式变电站的功能
以信息技术“点亮”未来能源，迈威通信携光储通信系统解决方案出击SNEC
ZLG致远电子基于LoRa推出无线低功耗网络协议
光纤连接器的性能特点、损耗和衰减
适用于智慧银行的音视频系统整体解决方案
WebSocket有什么优点
四足机器人将是产业下一个爆发点?
给SiC FET设计PCB有哪些注意事项？
静电计级运算放大器ADA4530-1的性能及应用