1 PyOD
1-1 PyOD简介
https://pyod.readthedocs.io/en/latest/pyod.models.html
Python Outlier Detection（PyOD）是当下最流行的Python异常检测工具库（toolkit）。该工具库的主要亮点包括：
- 包括近20种常见的异常检测算法，比如经典的ABOD以及最新的深度学习如对抗生成模型（GAN）和集成异常检测（outlier ensemble）
- 支持不同版本的Python：包括2.7和3.5+；支持多种操作系统：windows，macOS和Linux
- 简单易用且一致的API，只需要几行代码就可以完成异常检测，方便评估大量算法
- 使用JIT和并行化（parallelization）进行优化，加速算法运行及扩展性（scalability），可以处理大量数据
1-2 PyOD使用
from pyod.models.knn import KNN # imprt kNN分类器
# 训练一个kNN检测器
clf_name = 'kNN'
clf = KNN() # 初始化检测器
clf clf.fit(X_train) # 使用X_train训练检测器clf
# 返回训练数据X_train上的异常标签和异常分值
y_train_pred = clf.labels_ # 返回训练数据上的分类标签 (0: 正常值, 1: 异常值)
y_train_scores = clf.decision_scores_ # 返回训练数据上的异常值 (分值越大越异常)
# 用训练好的clf来预测未知数据中的异常值
y_test_pred = clf.predict(X_test) # 返回未知数据上的分类标签 (0: 正常值, 1: 异常值)
y_test_scores = clf.decision_function(X_test) # 返回未知数据上的异常值
2 KNN
2-1 基本原理
对于特征空间中的一个样本，如果与之最相似的（即特征空间中距离最近的）k个样本中的大多数都属于某一类别，则该样本的分类结果也是这个类别。
2-2 如何找到最近的K个样本
暴力搜索
kd_tree
https://www.cnblogs.com/lesleysbw/p/6074662.html
① 什么叫做KD_tree
K：K邻近查询中的k；D：空间是D维空间（Demension）tree：二叉树
② 建树过程
K-D tree的建立就是分裂空间的过程
首先我们来定义树节点的状态：
分裂点（split_point）
分裂方式（split_method）
左儿子（left_son）
右儿子（right_son）建树依据：
先计算当前区间 [ L , R ] 中（这里的区间是点的序号区间，而不是我们实际上的坐标区间），每个点的坐标的每一维度上的方差，取方差最大的那一维，设为 d，作为我们的分裂方式（split_method ），把区间中的点按照在 d 上的大小，从小到大排序，取中间的点 sorted_mid 作为当前节点记录的分裂点，然后，再以 [ L , sorted_mid-1 ] 为左子树建树 ， 以 [sorted_mid+1 , R ] 为右子树建树，这样，当前节点的所有状态我们便确定下来了：
split_point= sorted_mid
split_method= d
left_son = [ L , sorted_mid-1 ]
right_son = [ sorted_mid+1 , R ]
- 举例：
假设现在我们有平面上的点集 E ，其中有 5 个二维平面上的点 ： （1,4）（5,8） （4,2） （7,9） （10,11）。
首先，我们对整个区间 [1 , 15] 建树：先计算区间中所有点在第一维（也就是 x 坐标）上的方差：
平均值 ： ave_1 =5.4
方差 ： varance_1 =9.04
再计算区间中所有点在第二维（也就是 y 坐标）上的方差：
平均值：ave_2 =6.8
方差：varance_2 =10.96
明显看见，varance_2 > varance_1 ，那么我们在本次建树中，分裂方式 ：split_method =2， 再将所有的点按照第2维的大小从小到大排序，得到了新的点的一个排列：
（4,2） （1,4） （5,8） （7,9） （10,11）
取中间的点作为分裂点 sorted_mid =（5，8）作为根节点，再把区间 [1 , 2] 建成左子树 , [4 , 5] 建成右子树，此时，直线 ： y = 8 将平面分裂成了两半，前面一半给左儿子，后面一半给了右儿子，如图：
建左子树 [1, 3] 的时候可以发现，这时候第一维的方差大 ，分裂方式就是1 ，把区间 [ 1, 2 ] 中的点按照 第一维 的大小，从小到大排序 ，取中间点（1,4） 根节点，再以区间 [ 2, 2] 建立右子树 得到节点 （4,2）
建右子树 [4 , 5] 的时候可以发现，这时还是第一维的方差大， 于是，我们便得到了这样的一颗二叉树 也就是 K-D tree，它把平面分成了如下的小平面，使得每个小平面中最多有一个点：
③ 查询过程：
查询，其实相当于我们要将一个点“添加”到已经建好的 K-D tree 中，但并不是真的添加进去，只是找到他应该处于的子空间即可，所以查询就显得简单的。
每次在一个区间中查询的时候，先看这个区间的分裂方式是什么，也就是说，先看这个区间是按照哪一维来分裂的，这样如果这个点对应的那一维上面的值比根节点的小，就在根节点的左子树上进行查询操作，如果是大的话，就在右子树上进查询操作。
每次回溯到了根节点（也就是说，对他的一个子树的查找已经完成了）的时候，判断一下，以该点为圆心，目前找到的最小距离为半径，看是否和分裂区间的那一维所构成的平面相交，要是相交的话，最近点可能还在另一个子树上，所以还要再查询另一个子树，同时，还要看能否用根节点到该点的距离来更新我们的最近距离。为什么是这样的，我们可以用一幅图来说明：
首先[1,5]按y轴分裂，y6=1<y3=8，接着在[1,2]上查询。在查询到左儿子的时候，我们发现，现在最小的距离是 r = 10 ，当回溯到父亲节点的时候，我们发现，以目标点（10,1）为圆心，现在的最小距离 r = 10 为半径做圆，与分割平面 y = 8 相交，这时候，如果我们不在父亲节点的右儿子进行一次查找的话，就会漏掉（10,9） 这个点，实际上，这个点才是距离目标点 （10,1） 最近的点
由于每次查询的时候可能会把左右两边的子树都查询完，所以，查询并不是简单的 log(n) 的，最坏的时候能够达到 sqrt(n)。
- ball_tree
https://github.com/YinghongZhang/BallTree-MIPS
① 原理
为了改进KDtree的二叉树树形结构，并且沿着笛卡尔坐标进行划分的低效率，ball tree将在一系列嵌套的超球体上分割数据。也就是说：使用超球面而不是超矩形划分区域。虽然在构建数据结构的花费上大过于KDtree，但是在高维甚至很高维的数据上都表现的很高效。
球树递归地将数据划分为由质心C和半径r定义的节点，使得节点中的每个点都位于由r和C定义的超球内。通过使用三角不等式来减少邻居搜索的候选点数量。
② 建树过程
选择一个距离当前圆心最远的观测点A，和距离A最远的观测点B，将圆中所有离这两个点最近的观测点都赋给这两个簇的中心，然后计算每一个簇的中心点和包含所有其所属观测点的最小半径。对包含n个观测点的超圆进行分割，只需要线性的时间。
③ 查询
使用ball tree时，先自上而下找到包含target的叶子结点（c, r），从此结点中找到离它最近的观测点。这个距离就是最近邻的距离的上界。检查它的兄弟结点中是否包含比这个上界更小的观测点。方法是：如果目标点距离兄弟结点的圆心的距离d > 兄弟节点所在的圆半径R + 前面的上界r，则这个兄弟结点不可能包含所要的观测点。否则，检查这个兄弟结点是否包含符合条件的观测点。
2-3 参数设置
classpyod.models.knn.KNN(contamination=0.1, n_neighbors=5, method='largest', radius=1.0, algorithm='auto', leaf_size=30, metric='minkowski', p=2, metric_params=None, n_jobs=1, **kwargs)
- contamination：污染度
- n_neighbors：选取相邻点数量
- method：‘largest’、‘mean’、‘median’
- ‘largest’：使用与第k个相邻点的距离作为异常得分
- ‘mean’：使用k个相邻点距离的平均值作为异常得分
- ‘median’：使用k个相邻点距离的中值作为异常得分
- radius：radius_neighbors使用的参数空间半径
- algorithm：找到最近的k个样本
- kd_tree：依次对K维坐标轴，以中值切分，每一个节点是超矩形，适用于低维（<20时效率最高）
- ball_tree：以质心c和半径r分割样本空间，每一个节点是超球体，适用于高维（kd_tree高维效率低）
- brute：暴力搜索
- auto：通过 fit() 函数拟合，选择最适合的算法；如果数据稀疏，拟合后会自动选择brute，参数失效
- leaf_size：kd_tree和ball_tree中叶子大小，影响构建、查询、存储，根据实际数据而定。树叶中可以有多于一个的数据点，算法在达到叶子时在其中执行暴力搜索即可。如果leaf size 趋向于 N（训练数据的样本数量），算法其实就是 brute force了。如果leaf size 太小了，趋向于1，那查询的时候 遍历树的时间就会大大增加。
- metric：距离计算标准 https://blog.csdn.net/eric41050808/article/details/24365765
- euclidean：欧氏距离（p = 2）
- manhattan：曼哈顿距离（p = 1）
- minkowski：闵可夫斯基距离
- p：metric参数，默认为2
- metric_params：metric参数
- n_jobs：并行作业数。-1时，n_jobs为CPU核心数。
3 IForest
3-1 基本原理
用一个随机超平面来切割数据空间, 直到每个子空间里面只有一个数据点为止。切割次数的多少可用来区分异常。
https://www.jianshu.com/p/5af3c66e0410
iForest 由t个iTree孤立树组成，每个iTree是一个二叉树，其实现步骤如下：
- 从训练数据中随机选择N个点样本点作为subsample，放入树的根节点。
- 随机指定一个维度，在当前节点数据中随机产生一个切割点p——切割点产生于当前节点数据中指定维度的最大值和最小值之间。
- 以此切割点生成了一个超平面，然后将当前节点数据空间划分为2个子空间：把指定维度里小于p的数据放在当前节点的左孩子，把大于等于p的数据放在当前节点的右孩子。
- 在孩子节点中递归步骤2和3，不断构造新的孩子节点，直到孩子节点中只有一个数据（无法再继续切割） 或 孩子节点已到达限定高度。
可以看到d最有可能是异常，因为其最早就被孤立（isolated）了。
获得t个iTree之后，iForest 训练就结束，然后我们可以用生成的iForest来评估测试数据了。对于一个训练数据x，我们令其遍历每一棵iTree，然后计算x最终落在每个树第几层（x在树的高度），得到x在每棵树的高度平均值。获得每个测试数据的average path length后，我们可以设置一个阈值，低于此阈值的测试数据即为异常。
IForest具有线性时间复杂度。
IForest不适用于特别高维的数据。
3-2 参数设置
classpyod.models.iforest.IForest(n_estimators=100, max_samples='auto', contamination=0.1, max_features=1.0, bootstrap=False, n_jobs=1, random_state=None, verbose=0)
- n_estimators：估算器数量。默认100棵树
- max_samples：训练每个估算器（tree）需要抽取的样本数。默认选256个样本建树
- int：抽取max_samples个
- float：抽取max_samples*X.shape[0]（即样本行数）个
- auto：抽取min(256, n_samples)个
- contamination：污染度
- max_features：训练每个估算器需要抽取的特征数，高维数据时不必分割所有特征
- int：抽取max_features个
- float：抽取max_features*X.shape[1]即（样本列数）个
- bootstrap：
- true：单一树需拟合替换的随机样本
- false：进行无需更换的取样
- n_jobs：并行作业数。-1时，n_jobs为CPU核心数
- random_state：随机数种子/生成器
- verbose：控制建树过程
4 MCD
最小协方差行列式（Minimum Covariance Determinant）
4-1 基本原理
- MCD
https://max.book118.com/html/2017/1217/144650709.shtm
论文《Minimum covariance determinant and extensions》中有更详细描述。
- FastMCD
- 若n较小（600），使用MCD方法，会随机选取 n_features+1 个样本作为初值，构造协方差矩阵S0并计算样本均值T0，直接从T0、S0开始迭代；
- 若n较大，将随机样本h分为最多五个不相交的子集；每个子集中，使用MCD方法，保存10个子集T和S；之后合并子集，在合集中继续迭代所有子集T和S，得到10个合集T和S；最后在n中，迭代合集T和S，得到最终结果。
论文《A Fast Algorithm for the Minimum Covariance Determinant Estimator》有更详细描述。
4-2 参数设置
classpyod.models.mcd.MCD(contamination=0.1, store_precision=True, assume_centered=False, support_fraction=None, random_state=None)
- contamination：污染度
- store_precision：是否存储中间值
- assume_centered：假设居中
- true：计算稳健位置和协方差，重新计算协方差估计值。适用于处理均值等于0但不全为0的数据
- false：直接用FastMCD计算稳健位置和协方差
- support_fraction：设置参与估算的点的比例h（0.5n<h<n，默认0.75n）
- none：support_fraction的最小值为[n_sample + n_features + 1] / 2
- float：原始MCD估算的比例
- random_state：随机数种子/生成器
