LEE CHANWOO

📝 Blog 2024 version 1.6.0
🔖 SEP 5, 2024

5 분 소요


Extended Isolation Forest (EIF)

Extended Isolation Forest는 Isolation Forest 알고리즘을 기반으로 하는 비지도 이상치 탐지 알고리즘입니다. 원래의 Isolation Forest 알고리즘은 새로운 형태의 이상치 탐지를 제공하지만, 트리 분기로 인한 편향 문제가 있습니다. 알고리즘을 확장하면 분기를 조정하여 편향성을 완화하고 원래 알고리즘은 특수한 경우에만 적용됩니다.

편향의 원인은 분기가 이진 검색 트리(BST)와의 유사성에 의해 정의되기 때문입니다. 각 분기점에서 특징과 값이 선택되는데, 아래 왼쪽 그림에서 볼 수 있듯이 분기점이 축 중 하나에 평행하기 때문에 편향이 발생합니다.

image Visualization of a tree branching from Extended Isolation Forest paper [2].

일반적인 경우에는 각 분기점에 대해 임의의 기울기를 정의해야 합니다(위 오른쪽 그림). 특징과 값을 선택하는 대신 분기 절단에 대한 임의의 기울기 n 과 임의의 절편 p 를 선택합니다.

Extended Isolation Forest의 경우 extension_level 하이퍼파라미터를 사용하면 Isolation Forest의 일반화를 활용할 수 있습니다. 숫자 0 은 분할 지점이 기울기에 따라 무작위화되지 않기 때문에 Isolation Forest의 동작에 해당합니다. 기능이 P 인 데이터 세트의 경우, 최대 extension_level 은 P-1 이며 전체 확장을 의미합니다. extension_level 이 증가하면 표준 Isolation Forest의 편향이 감소합니다. 확장 수준이 낮을수록 각 피처의 최소 및 최대 범위가 크게 다른 도메인에 적합합니다(예를 들어, 첫 번째 피처는 밀리미터 단위로 측정되고 두 번째 피처는 미터 단위로 측정되는 경우).

Extended Isolation Forest에서 주어진 데이터 포인트 x 에 대한 데이터 분할에 대한 분기 기준은 다음과 같습니다: (x - p) * n ≤ 0

여기서

  • x, p, n은 P 특징을 가진 벡터
  • p 는 분할할 데이터의 하위 샘플에서 나온 경계가 있는 균등 분포에서 생성된 임의의 절편
  • n 은 N(0,1) 분포에서 생성된 분기 절단에 대한 임의의 기울기입니다.

extension_level 의 기능은 n 의 임의 항목을 0으로 강제하는 것입니다. extension_level 하이퍼파라미터 값은 0 에서 P-1 사이입니다. 값이 0 이면 모든 기울기가 모든 축과 평행이 되며, 이는 Isolation Forest의 동작에 해당합니다. 확장 수준이 높을수록 분할이 extension_level - 축 수와 평행이 된다는 의미입니다. 전체 확장은 extension_level 이 P-1 과 같음을 의미합니다. 이는 분기점의 기울기가 항상 무작위임을 나타냅니다.

extension_level 하이퍼파라미터에 대한 자세한 내용은 원본 논문[2]의 고차원 데이터 및 확장 레벨(High Dimensional Data and Extension Levels) 섹션을 참조하세요.


Example

image

  • 1번 부분은 잘 작동된다. 하지만 2번, 3번에서는 실제로는 이상치일 가능성이 높은데, Isolation Forest에서는 정상으로 판별할 가능성이 높다.


image

  • 위 그림에서 볼 수 있듯이 고스트 클러스터의 발생이 보입니다. 임계값은 이상을 찾는 데 사용되므로 잘못된 탐지가 발생할 수 있습니다.


image

image

image


Anomaly score distribution

image


Python

%matplotlib inline
import matplotlib.pyplot as plt
import sys
import igraph as ig
import matplotlib.pyplot as plt
import numpy as np
import random as rn
import eif as iso
# pip install eif==1.0.2
import copy
import seaborn as sb
import pandas as pd
sb.set_style(style="whitegrid")
sb.set_color_codes()
ig.__version__

> '0.11.6'

import numpy as np
import matplotlib.pyplot as plt

# Parameters for the main distribution
main_mean = [10, 15]
main_cov = [[3, 1], [1, 3]]
num_points_main = 1000
anomaly_value = [25, 10]

main_distribution = np.random.multivariate_normal(main_mean, main_cov, num_points_main)

anomaly_point = np.array([anomaly_value])
plt.figure(figsize=(8, 8))
plt.scatter(main_distribution[:, 0], main_distribution[:, 1], label="Main Distribution", color='b', alpha=0.5)
plt.scatter(anomaly_point[:, 0], anomaly_point[:, 1], color='r', label="Anomalous Point")
plt.xlabel("Dimension 1")
plt.ylabel("Dimension 2")
plt.legend()
plt.title("2D Signal with Peripheral Anomaly")
plt.grid(True)
plt.show()

image

  • main_distribution.shape: (1001, 2)
  • anomaly_point.shape: (1, 2)


Comparing performance between The iForest and the EIF

F0 = iso.iForest(main_distribution, ntrees=500, sample_size=256, extension_level=0) # iForest
F1 = iso.iForest(main_distribution, ntrees=500, sample_size=256, extension_level=1) # EIF

anomaly_scores_0=F0.compute_paths(X_in=main_distribution) # anomaly score created by iForest
anomaly_scores_1=F1.compute_paths(X_in=main_distribution) # anomaly score created by EIF
  • main_distribution.shape: (1001, 2)
  • anomaly_scores_0.shape: (1001,)


# To set the threshold I used the Median Absolute Deviation (MAD) method
def compute_mad(scores):
    median = np.median(scores)
    abs_deviations = np.abs(scores - median)
    mad = np.median(abs_deviations)
    return mad

def set_threshold(scores, scaling_factor=10):
    median = np.median(scores)
    mad = compute_mad(scores)
    threshold = median + (scaling_factor * mad)
    return threshold

threshold0 = set_threshold(anomaly_scores_0)
threshold1 = set_threshold(anomaly_scores_1)

x, y = main_distribution[:,0], main_distribution[:,1]
anomaly_indices_0 = np.where(anomaly_scores_0 > threshold0)[0]
anomaly_indices_1 = np.where(anomaly_scores_1 > threshold1)[0]



fig1 = plt.figure()
plt.scatter(x, y)
plt.scatter(x[anomaly_indices_0], y[anomaly_indices_0], color='green',label="predicted anomalous point")
plt.xlabel("Dimension 1")
plt.ylabel("Dimension 2")
plt.legend()
plt.grid(True)
plt.title('Standard')
plt.show()

fig2= plt.figure()
plt.scatter(x, y)
plt.scatter(x[anomaly_indices_1], y[anomaly_indices_1], color='red',label="predicted anomalous point")
plt.xlabel("Dimension 1")
plt.ylabel("Dimension 2")
plt.legend()
plt.grid(True)
plt.title('Extended')
plt.show()

image

image

Score Maps

def getDepth(x, root, d):
    n = root.n
    p = root.p
    if root.ntype == 'exNode':
        return d
    else:
        if (x-p).dot(n) < 0:
            return getDepth(x,root.left,d+1)
        else:
            return getDepth(x,root.right,d+1)

def getVals(forest,x,sorted=True):
    theta = np.linspace(0,2*np.pi, forest.ntrees)
    r = []
    for i in range(forest.ntrees):
        temp = forest.compute_paths_single_tree(np.array([x]),i)
        r.append(temp[0])
    if sorted:
        r = np.sort(np.array(r))
    return r, theta

x, y = main_distribution[:,0], main_distribution[:,1]

xx, yy = np.meshgrid(np.linspace(0, 300, 300), np.linspace(0, 40, 300))

S0 = F0.compute_paths(X_in=np.c_[xx.ravel(), yy.ravel()])
S0 = S0.reshape(xx.shape)

S1 = F1.compute_paths(X_in=np.c_[xx.ravel(), yy.ravel()])
S1 = S1.reshape(xx.shape)
f = plt.figure(figsize=(12,6))

ax1 = f.add_subplot(121)
levels = np.linspace(np.min(S0), np.max(S0), 10)
CS = ax1.contourf(xx, yy, S0, levels, cmap=plt.cm.YlOrRd)
plt.scatter(x, y, s=15, c='None', edgecolor='k')


ax2 = f.add_subplot(122)
levels = np.linspace(np.min(S1),np.max(S0),10)
CS = ax2.contourf(xx, yy, S1, levels, cmap=plt.cm.YlOrRd)
plt.scatter(x, y, s=15, c='None', edgecolor='k')


plt.show()

image


Forest Visualization

Sorted = False
fig = plt.figure(figsize=(12, 6))
ax1 = plt.subplot(121, projection='polar')
rn, thetan = getVals(F0, np.array([10., 0.]), sorted=Sorted)
for j in range(len(rn)):
    ax1.plot([thetan[j], thetan[j]], [1,rn[j]], color='b', alpha=1, lw=1)

ra, thetaa = getVals(F0, np.array([-5.,-3.]), sorted=Sorted)
for j in range(len(ra)):
    ax1.plot([thetaa[j], thetaa[j]], [1,ra[j]], color='r', alpha=0.9, lw=1.3)

ax1.set_title("Generic\nNominal: Mean={0:.3f}, Var={1:.3f}\nAnomaly: Mean={2:.3f}, Var={3:.3f}".format(np.mean(rn), np.var(rn), np.mean(ra), np.var(ra)))

ax1.set_xticklabels([])
ax1.set_xlabel("Anomaly")
ax1.set_ylim(0, F0.limit)

ax1.axes.get_xaxis().set_visible(False)
ax1.axes.get_yaxis().set_visible(False)
# ax1.text(0, F0.limit+0.4, "800 Trees, full depth")

ax2 = plt.subplot(122, projection='polar')
rn, thetan = getVals(F1, np.array([10., 0.]), sorted=Sorted)
for j in range(len(rn)):
    ax2.plot([thetan[j], thetan[j]], [1,rn[j]], color='b', alpha=1, lw=1)

ra, thetaa = getVals(F1, np.array([-5.,-3.]), sorted=Sorted)
for j in range(len(ra)):
    ax2.plot([thetaa[j], thetaa[j]], [1,ra[j]], color='r', alpha=0.9, lw=1.3)


ax2.set_title("Extended\nNominal: Mean={0:.3f}, Var={1:.3f}\nAnomaly: Mean={2:.3f}, Var={3:.3f}".format(np.mean(rn), np.var(rn), np.mean(ra), np.var(ra)))

ax2.set_xticklabels([])
ax2.set_xlabel("Anomaly")
ax2.set_ylim(0,F0.limit)

ax2.axes.get_xaxis().set_visible(False)
ax2.axes.get_yaxis().set_visible(False)

image


Local Density anomaly

import numpy as np
import matplotlib.pyplot as plt

main_mean = [10, 15]
main_cov = [[3, 1], [1, 3]]
num_points_main = 1000
anomaly_mean = [15, 10]
anomaly_cov = [[1, 0], [0, 1]]
num_points_anomaly = 200
main_distribution = np.random.multivariate_normal(main_mean, main_cov, num_points_main)
anomaly_distribution = np.random.multivariate_normal(anomaly_mean, anomaly_cov, num_points_anomaly)
combined_distribution = np.vstack((main_distribution, anomaly_distribution))
plt.figure(figsize=(8, 8))
plt.scatter(combined_distribution[:, 0], combined_distribution[:, 1], color='b', alpha=0.5)
plt.scatter(anomaly_mean[0], anomaly_mean[1], color='r', label="Local Density Anomaly")
plt.xlabel("Dimension 1")
plt.ylabel("Dimension 2")
plt.legend()
plt.title("2D Signal with Local Density Anomaly")
plt.grid(True)
plt.show()

image

F0 = iso.iForest(combined_distribution, ntrees=500, sample_size=256, ExtensionLevel=0) # iForest
F1 = iso.iForest(combined_distribution, ntrees=500, sample_size=256, ExtensionLevel=1) # EIF

anomaly_scores_0 = F0.compute_paths(X_in=combined_distribution) # anomaly score created by iForest
anomaly_scores_1 = F1.compute_paths(X_in=combined_distribution) # anomaly score created by EIF

x, y = combined_distribution[:, 0], combined_distribution[:, 1]
anomaly_indices_0 = np.where(anomaly_scores_0 > threshold0)[0]
anomaly_indices_1 = np.where(anomaly_scores_1 > threshold1)[0]

fig1 = plt.figure()
plt.scatter(x, y)
plt.scatter(x[anomaly_indices_0], y[anomaly_indices_0], color='green', label="predicted anomalous point")
plt.xlabel("Dimension 1")
plt.ylabel("Dimension 2")
plt.legend()
plt.grid(True)
plt.title('Standard')
plt.show()

fig2= plt.figure()
plt.scatter(x, y)
plt.scatter(x[anomaly_indices_1], y[anomaly_indices_1], color='red', label="predicted anomalous point")
plt.xlabel("Dimension 1")
plt.ylabel("Dimension 2")
plt.legend()
plt.grid(True)
plt.title('Extended')
plt.show()

image

image

xx, yy = np.meshgrid(np.linspace(0, 300, 300), np.linspace(0, 40, 300))

S0 = F0.compute_paths(X_in=np.c_[xx.ravel(), yy.ravel()])
S0 = S0.reshape(xx.shape)

S1 = F1.compute_paths(X_in=np.c_[xx.ravel(), yy.ravel()])
S1 = S1.reshape(xx.shape)
f = plt.figure(figsize=(12,6))

ax1 = f.add_subplot(121)
levels = np.linspace(np.min(S0),np.max(S0),10)
CS = ax1.contourf(xx, yy, S0, levels, cmap=plt.cm.YlOrRd)
plt.scatter(x, y, s=15, c='None', edgecolor='k')


ax2 = f.add_subplot(122)
levels = np.linspace(np.min(S1),np.max(S0),10)
CS = ax2.contourf(xx, yy, S1, levels, cmap=plt.cm.YlOrRd)
plt.scatter(x, y, s=15, c='None', edgecolor='k')

plt.show()

image


References

댓글남기기

참고