这次在网上学习别人记笔记的方式，感觉很有意思，不知道我能从中学到多少。可惜markdown做富文本表格太麻烦了…但是用别的，比如word、pdf，都不方便即时打开。。。算了吧，选择了markdown还是按标题目录来整理笔记

为什么读此文章

原因有二：

是我最早接触的论文之一，当年没看，现在拿来读一下，本来想略读，然后就忍不住多看了几遍…
周志华是作者之一，应该很顶

文献链接：Isolation Forest

文献总结

孤立森林是一种异常检测方法，侧重以孤立的方式直接寻找异常而非比对正常样本。

这个孤立的思想很棒，少了很多计算的步骤，但同时有很棒的准确性，毕竟基于的是异常本身的重要性质。

文献内容

目的

给异常检测领域提供一种新方法——孤立森林。

该方法来源于以往没人用过的孤立的思想来做异常检测，且可以发现由此提出的孤立森林有诸多优点。

背景

大方向是异常检测，看着就知道很重要
传统的（模型驱动的）异常检测方法把测试样本与已知正常样本对比，不符即为异常。这个想法很基础很实在√
上面方法的缺点有2，1是泛化不好，因为方法效果与正常样本库相关；2是计算代价大，往往只能用于低维小规模数据，因为这些方法常常用到距离等度量方式
在此提出并使用孤立的概念，把异常点孤立于其它正常样本。思想是利用了异常的2个性质，1是它们真的只是少数；2是特征与正常样本必是不同的。由此思想，用树来孤立异常数据，异常数据会在树根部被孤立，正常样本只会在深处被孤立。

方法——从孤立树到孤立森林

孤立森林是什么：
- 背景提到了孤立树的概念，集成起来就是孤立森林。孤立森林方法只有2个变量，1是树的个数，2是sub-sampling size，一开始我猜这个size翻译为二次采样的size，做一次全分割用的样本数；后来我发现我猜错了，在文章第3章中说明了这个是可以设置多个树，相当于多个异常检测专家，分别随机取一部分数据来检测异常，这些数据的size叫sub-sampling size，至于为什么将在优缺点部分介绍。
- 异常的2个性质体现在孤立分割上就是，异常越少，所需分割次数就越少；以及异常会早早被割出来，即异常的平均路径长度average path lengths短，图1很形象。
孤立树是什么：
- 先给出基本数据假设：数据集$X=\{x_1, \cdots, x_n\}$，$n$个样本，每个样本是$d$维的，有$d$个分量。
- 首先是一棵树，然后在这里，是特定的一种树。用节点来描述，它的节点$T$只有两种，一种是外部节点，就是接下来没有分支了；第二种是内部节点，且分支有且只有两个子节点$(T_l, T_r)$，即左右子节点。
- 那么数据集X的孤立方式是，每次随机孤立一个分量，如第$q$个，孤立的分割阈值是$p$，这样把数据分为两部分。多次孤立的停止条件有：
  - 树达到临界高度
  - 最后只有一个点了，即$|X|=1$
  - 所有数据都只有一个值，没法孤立
异常的判定——异常score：
- 有了方法的概念和方法的构成单元，下面说方法的度量，即怎么样算是异常。基本的想法是path（路径）长度：样本$x$的路径长度记为$h(x)$，在树上，$x$被孤立出来需要的分割次数。但是这个$h(x)$不好，因为这个$h(x)$算不算异常也要看整个树的深度、样本量什么的；因此需要一般性的异常score作为度量。
- 这个score来源于BST，二元搜索树，因为发现孤立树和BST有相似的性质。借BST文章的结论，其不成功搜索的路径长度$c(n)$与这里的$h(x)$类似，于是采用(1, 2)式的形式计算了此异常score $s(x, n)$。个人感觉就是$h(x)$不general，引用$c(n)$给它做了某种标准化。图2和图3解释得非常好，一目了然，分别介绍了定性的$s(x, n)$合理性和类似等高线的异常判断方式。

优缺点

孤立森林与已有方法主要区别：
- 它可以利用sub-sampling，这个sub-sampling指什么？，是只用一部分数据就可以了，体现在孤立森林的局部：孤立树的使用上；如果数据多，往往树越深，正常样本也多，往往难以检测出异常。具体有两种情形——swamping and masking，分别指错把正常样本识别为异常，和异常点太多，比如扎堆出现，一看还以为都是正常的，其异常性被数量掩盖了。针对它们，只要取一部分数据就可以得到更好的效果，文章第3章画了两张图，非常形象地阐述了机理👍！
- 不需要计算什么距离、密度，大大降低计算复杂度
- 由集成的优点，大的森林可以处理大量数据了，包括高维情形
孤立森林的优点：
- 线性时间的复杂度，对运算内存的要求为很低的常数。1个原因是不需要计算什么距离、密度，另一个原因是按照方法中孤立的方式，即使树是完全树，最多（每次只孤立1个点）的内部节点有$n-1$个。最多的全部节点有$n-1+n=2n-1$个（自己画个图就知道了），所以对变量的内存要求是有界的，与样本量呈线性关系。
- 首次把孤立应用于异常检测，似乎用了二次采样，其它已有方法不行
- 它的2个变量都比较小，就可以表现优异

实验——如何训练孤立森林

和一般的机器学习方法类似，先训练出一个孤立森林模型，再拿测试数据测试。

训练总体的算法是孤立树的集成——孤立森林，为算法1，递归式地分割数据集
- 算法1中包括算法2，单颗孤立树的训练，这些都已经说过了。
- 算法1、2中有3个参数要提前设置：子采样数、树的最大深度和树的棵树，这些都根据实验经验确定，子采样数默认$\psi=256$，深度默认$l=ceiling(\log_2 \psi)$，棵树默认$t=100$。
最后测试的时候计算的score要一直到被孤立出去，且使用递归的方式一点点计算。