isolationForest二见

1.IsolationForest  anomaly score计算
计算observation x的路径长度：

observation x的路径长度是h(x)，e是深度（深度就等于路径长度），T.size是x所在节点的sample size，C是求这个sample生成所有可能二叉树（叶子数为T.size的full binary tree，论文中叫proper binary tree，除叶节点外，每个节点有两个孩子）的平均路径长度（所有可能的形态，一个形态又有很多叶节点，所有叶节点的平均），C（）公式如下

H(n-1) ≈ ln(n-1) + 0.5772156649，常数是欧拉常数，
最终得分：

普赛表示每棵树的训练样本数，C(普赛)表示用普赛条数据构建的二叉树的平均路径长度，E(h(x))是对某样本点，整个森林的路径长度求平均，除以C(普赛)相当于一种标准化，再以2为底，整个score会介于(0,1]之间，score就有点类似于异常点的p

2.isolationForest的深度并不是超参，深度等于ceil(log2(n))，ceil是向上取整，比如256个样本点，log2(256) = 8，最大深度是8，如果是perfect binary tree，那就有256个叶节点，可以尽可能地isolate每一个样本点

3.为什么

论文中说求叶节点平均路径长度就和计算binary search tree（BST）的unsuccessful search（走到叶节点结束搜索）是一回事，所以直接引用了参考文献，参考文献这个公式又是基于successful search（在内部节点结束搜索），详细的推理我就没看了

4.sklearn的实现中，score_samples是论文中的公式取反，取反的话，结果的值域就从(0,1]变到了[-1,0)，意义不明，不知道是不是为了让结果随路径长度单调递增

5.sklearn中的decision_function，其实就是取反的score+offset，加了过后，让0成为一个界限，0左边的为异常，0右边的为正常，参数默认加的0.5，会根据超参contamination（异常点的百分比）进行调节（比如contamination是0.1，计算出-score的10% percentile，然后得到其加offset变为0的offset，全部加offset，这就保证了<=0的是10%）

6.isolationForest为什么outliers的平均路径长度短，可参考这幅图

一条线相当于切一刀，一个节点的分裂，xi需要很多刀，路径自然就长，而X0路径短

isolationForest可以改进的地方：
1.isolationForest只处理连续变量，分类变量和连续变量存在缺失值怎么处理合适

一些参考资料：
isolationForest代码
https://zhidao.baidu.com/question/2144982579306549708.html
异常检测问题的研究
https://zhuanlan.zhihu.com/p/93779599
BST的不成功搜索
http://www.luyixian.cn/news_show_6361.aspx