你好，下面是一个孤立森林的源代码， 他是根据周志华老师团队提出的孤立森林算法，用于进行异常点检测。
from random import sample, random, choice, randintfrom math import ceil, log
#from utils import run_time
class Node(object):
def __init__(self, size):
"""Node class to build tree leaves
Keyword Arguments:
size {int} -- Node size (default: {None})
"""
# Node size
self.size = size
# Feature to split
self.split_feature = None
# Split point
self.split_point = None
# Left child node
self.left = None
# Right child node
self.right = None
class IsolationTree(object):
def __init__(self, X, n_samples, max_depth):
"""Isolation Tree class
Arguments:
X {list} -- 2d list with int or float
n_samples {int} -- Subsample size
max_depth {int} -- Maximum height of isolation tree
"""
self.height = 0
# In case of n_samples is greater than n
n = len(X)
if n_samples > n:
n_samples = n
# Root node
self.root = Node(n_samples)
# Build isolation tree
self._build_tree(X, n_samples, max_depth)
def _get_split(self, X, idx, split_feature):
"""Randomly choose a split point
Arguments:
X {list} -- 2d list object with int or float
idx {list} -- 1d list object with int
split_feature {int} -- Column index of X
Returns:
int -- split point
"""
# The split point should be greater than min(X[feature])
unique = set(map(lambda i: X[i][split_feature], idx))
# Cannot split
if len(unique) == 1:
return None
unique.remove(min(unique))
x_min, x_max = min(unique), max(unique)
# Caution: random() -> x in the interval [0, 1).
return random() * (x_max - x_min) + x_min
def _build_tree(self, X, n_samples, max_depth):
"""The current node data space is divided into 2 sub space: less than the
split point in the specified dimension on the left child of the current node,
put greater than or equal to split point data on the current node's right child.
Recursively construct new child nodes until the data cannot be splitted in the
child nodes or the child nodes have reached the max_depth.
Arguments:
X {list} -- 2d list object with int or float
n_samples {int} -- Subsample size
max_depth {int} -- Maximum depth of IsolationTree
"""
# Dataset shape
m = len(X[0])
n = len(X)
# Randomly selected sample points into the root node of the tree
idx = sample(range(n), n_samples)
# Depth, Node and idx
que = [[0, self.root, idx]]
# BFS
while que and que[0][0] <= max_depth:
depth, nd, idx = que.pop(0)
# Stop split if X cannot be splitted
nd.split_feature = choice(range(m))
nd.split_point = self._get_split(X, idx, nd.split_feature)
if nd.split_point is None:
continue
# Split
idx_left = []
idx_right = []
while idx:
i = idx.pop()
xi = X[i][nd.split_feature]
if xi < nd.split_point:
idx_left.append(i)
else:
idx_right.append(i)
# Generate left and right child
nd.left = Node(len(idx_left))
nd.right = Node(len(idx_right))
# Put the left and child into the que and depth plus one
que.append([depth+1, nd.left, idx_left])
que.append([depth+1, nd.right, idx_right])
# Update the height of IsolationTree
self.height = depth
def _predict(self, xi):
"""Auxiliary function of predict.
Arguments:
xi {list} -- 1D list with int or float
Returns:
int -- the depth of the node which the xi belongs to
"""
# Search xi from the IsolationTree until xi is at an leafnode
nd = self.root
depth = 0
while nd.left and nd.right:
if xi[nd.split_feature] < nd.split_point:
nd = nd.left
else:
nd = nd.right
depth += 1
return depth, nd.size
class IsolationForest(object):
def __init__(self):
"""IsolationForest, randomly build some IsolationTree instance,
and the average score of each IsolationTree
Attributes:
trees {list} -- 1d list with IsolationTree objects
ajustment {float}
"""
self.trees = None
self.adjustment = None # TBC
def fit(self, X, n_samples=100, max_depth=10, n_trees=256):
"""Build IsolationForest with dataset X
Arguments:
X {list} -- 2d list with int or float
Keyword Arguments:
n_samples {int} -- According to paper, set number of samples to 256 (default: {256})
max_depth {int} -- Tree height limit (default: {10})
n_trees {int} -- According to paper, set number of trees to 100 (default: {100})
"""
self.adjustment = self._get_adjustment(n_samples)
self.trees = [IsolationTree(X, n_samples, max_depth)
for _ in range(n_trees)]
def _get_adjustment(self, node_size):
"""Calculate adjustment according to the formula in the paper.
Arguments:
node_size {int} -- Number of leaf nodes
Returns:
float -- ajustment
"""
if node_size > 2:
i = node_size - 1
ret = 2 * (log(i) + 0.5772156649) - 2 * i / node_size
elif node_size == 2:
ret = 1
else:
ret = 0
return ret
def _predict(self, xi):
"""Auxiliary function of predict.
Arguments:
xi {list} -- 1d list object with int or float
Returns:
list -- 1d list object with float
"""
# Calculate average score of xi at each tree
score = 0
n_trees = len(self.trees)
for tree in self.trees:
depth, node_size = tree._predict(xi)
score += (depth + self._get_adjustment(node_size))
score = score / n_trees
# Scale
return 2 ** -(score / self.adjustment)
def predict(self, X):
"""Get the prediction of y.
Arguments:
X {list} -- 2d list object with int or float
Returns:
list -- 1d list object with float
"""
return [self._predict(xi) for xi in X]
#@run_time
def main():
print("Comparing average score of X and outlier's score...")
# Generate a dataset randomly
n = 100
X = [[random() for _ in range(5)] for _ in range(n)]
# Add outliers
X.append([10]*5)
# Train model
clf = IsolationForest()
clf.fit(X, n_samples=500)
# Show result
print("Average score is %.2f" % (sum(clf.predict(X)) / len(X)))
print("Outlier's score is %.2f" % clf._predict(X[-1]))
if __name__ == "__main__":
main()
首先随机选择到的维度是 “年龄”，然后随机选择一个切割点 18，小于 18 岁的只有莫小贝一个人，所以她最先被 “孤立” 出来了；第二个随机选择的特征是 ”体重“，只有大嘴高于 80 公斤，所以也被 ”孤立“ 了；第三个选择 ”文化程度“ 这个特征，由于只有秀才的文化程度为高，于是被 ”孤立“ 出来了 ……
假设我们设定树的高度为 3，那么这棵树的训练就结束了。在这棵树上，莫小贝的路径长度为 1，大嘴为 2，秀才为 3，单看这一棵树，莫小贝的异常程度最高。但很显然，她之所以最先被孤立出来，与特征被随机选择到的顺序有关，所以我们通过对多棵树进行训练，来去除这种随机性，让结果尽量收敛。
使用孤立森林的前提是，将 异常点定义为那些 “容易被孤立的离群点 ——孤立森林算法的理论基础有两点：
想象-我们用一个随机超平面对一个数据空间进行切割，切一次可以生成两个子空间-。接下来，我们再继续随机选取超平面，来切割第一步得到的两个子空间，以此循环下去，直到每子空间里面只包含一个数据点为止。直观上来看，我们可以发现， 那些密度很高的簇要被切很多次才会停止切割，即每个点都单独存在于一个子空间内，但那些分布稀疏的点，大都很早就停到一个子空间内了
孤立森林算法总共分两步：
训练 iForest：从训练集中进行采样，构建孤立树，对森林中的每棵孤立树进行测试，记录路径长度；
计算异常分数：根据异常分数计算公式，计算每个样本点的 anomaly score。
由于切割过程是完全随机的，所以需要用 ensemble 的方法来使结果收敛，即反复从头开始切，然后计算每次切分结果的平均值。
获得 t 个孤立树后，单棵树的训练就结束了。接下来就可以 用生成的孤立树来评估测试数据了，即计算异常分数 s。 对于每个样本 x，需要对其综合计算每棵树的结果，通过下面的公式计算异常得分：
如果异常得分接近 1，那么一定是异常点；
如果异常得分远小于 0.5，那么一定不是异常点；
如果异常得分所有点的得分都在 0.5 左右，那么样本中很可能不存在异常点。
1.孤立树的创建。
树的高度限制 l 与子样本数量 ψ 有关。 之所以对树的高度做限制，是因为我们只关心路径长度较短的点，它们更可能是异常点，而并不关心那些路径很长的正常点。
孤立森林中的 “孤立” (isolation) 指的是 “把异常点从所有样本中孤立出来”，论文中的原文是 “separating an instance from the rest of the instances”.
大多数基于模型的异常检测算法会 先 ”规定“ 正常点的范围或模式， 如果某个点不符合这个模式，或者说不在正常范围内，那么模型会将其判定为异常点。
优点：
缺点：
IsolationForest(behaviour=' deprecated", bootstrap=False, contamination=0.1, max_features=1.0, max_samples=' auto',n_estimators=5e, n_jobs=None, random_state=None, verbose=e, warm_start=False)
方法
