isolation-forest-ts

TypeScript/Node.js implementation of the Isolation Forest algorithm for unsupervised anomaly detection.

TypeScript/Node.js向け Isolation Forest(教師なし異常検知)実装。

Overview / 概要

Isolation Forest (Liu, Ting & Zhou, 2008) detects anomalies by isolating observations through random recursive partitioning. Anomalies require fewer partitions to isolate than normal points, since they lie in sparse regions of the feature space. This yields an anomaly score without needing labeled data or distance/density computation, giving near-linear time complexity and low memory usage.

Isolation Forest(Liu, Ting & Zhou, 2008)は、無作為な再帰的分割により観測点を分離することで異常を検知する。異常値は特徴空間の疎な領域に位置するため、正常点より少ない分割回数で分離できる。この性質により、ラベル付きデータや距離・密度計算を必要とせず異常スコアを算出可能。計算量はほぼ線形、メモリ使用量も小さい。

Algorithm / アルゴリズム

Training (fit) / 学習

1. Build nEstimators isolation trees (iTrees), each from a random subsample of size sampleSize drawn (without replacement) from the training set. nEstimators 本の分離木(iTree)を構築。各木は学習データから非復元抽出したサイズ sampleSize のサブサンプルから作る。
2. Each tree is built recursively: 各木は以下の手順で再帰的に構築する:
   • If the subsample has ≤ 1 point, or the current depth reaches heightLimit (ceil(log2(sampleSize))), create an external (leaf) node storing the count of points it holds. サブサンプルが1点以下、または深さが heightLimit(ceil(log2(sampleSize)))に達した場合、保持点数を記録した外部(葉)ノードを作成する。
   • Otherwise, pick a feature uniformly at random, then pick a split value uniformly at random between the min and max of that feature within the current subsample. それ以外の場合、特徴量を一様乱数で選択し、現サブサンプル内でのその特徴量の最小値〜最大値間から分割値を一様乱数で選ぶ。
   • Partition points into left (< splitValue) and right (>= splitValue) subsets and recurse. 左(< splitValue)・右(>= splitValue)に分割し再帰する。
3. Store the resulting forest of trees. 構築した木の集合を森として保持する。

Scoring (score / predict) / スコアリング

For a point x: / 点 x について:

1. For each tree, compute the path length h(x) — the number of edges traversed from the root to the external node containing x, plus an adjustment c(size) for the leaf's remaining point count (average path length of an unsuccessful BST search), to account for leaves that were not fully split down to size 1. 各木でパス長 h(x) を計算する。ルートから x を含む外部ノードまでの辺数に、葉の残り点数に対する補正 c(size)(BST探索失敗時の平均パス長)を加算する。これは1点まで分割しきれなかった葉を補正するため。

2. Average h(x) across all trees: E[h(x)]. 全木の h(x) を平均: E[h(x)]。

3. Compute the anomaly score: / 異常スコアを計算:

   s(x, n) = 2 ^ ( -E[h(x)] / c(n) )

   where n = sampleSize and c(n) is the average path length normalization term: ここで n = sampleSize、c(n) は平均パス長の正規化項:

   c(n) = 2 * H(n - 1) - (2 * (n - 1) / n)     for n > 2
   c(n) = 1                                     for n == 2
   c(n) = 0                                     for n <= 1
   H(i) = ln(i) + Euler-Mascheroni constant (≈ 0.5772156649)

   c(2) is special-cased to the paper's exact value rather than the general formula, because the harmonic-number approximation above is inaccurate at this size. c(2) は一般式でなく論文の厳密値を特別に用いる。上記の調和数近似は このサイズで不正確なため。

4. Interpretation of s: / s の解釈:

   • s close to 1 → anomaly / 1 に近い → 異常
   • s close to 0 → normal point / 0 に近い → 正常
   • s around 0.5 → no distinct anomaly in the whole sample / 0.5 付近 → サンプル全体に明確な異常なし

Installation / インストール

pnpm add isolation-forest-ts

API

class IsolationForest

new IsolationForest(options?: IsolationForestOptions)

IsolationForestOptions

| Option | Type | Default | Description / 説明 | |---|---|---|---| | nEstimators | number | 100 | Number of isolation trees to build. Must be a positive integer. / 構築する分離木の本数。正の整数のみ許可。 | | sampleSize | number | min(256, n) | Number of points sampled (without replacement) to build each tree. Must be a positive integer. / 各木構築時に非復元抽出する点数。正の整数のみ許可。 | | contamination | number \| "auto" | "auto" | Expected proportion of anomalies in the data, used to derive the predict() threshold. Must be in (0, 1) when numeric. "auto" uses a fixed default threshold (0.6) instead. / データ中の異常割合の想定値。predict() の閾値算出に使用。数値指定時は (0, 1) の範囲のみ許可。"auto" 指定時は固定デフォルト閾値(0.6)を使用。 | | maxFeatures | number | 1.0 | Fraction of features to consider per tree (feature bagging). Must be in (0, 1]. / 木ごとに使用する特徴量の割合(特徴量バギング)。(0, 1] の範囲のみ許可。 | | randomSeed | number | undefined (random) | Seed for the internal PRNG, for reproducible results. / 内部PRNGのシード値。再現性確保用。 |

Invalid options throw synchronously from the constructor. 不正なオプションはコンストラクタ実行時に同期的に例外を投げる。

Methods / メソッド

fit(data: number[][]): this

Builds the forest from an array of feature vectors (all vectors must have the same length; throws otherwise). 特徴ベクトル配列から森を構築する(全ベクトルは同じ長さである必要があり、異なる場合は例外を投げる)。

score(data: number[][]): number[]

Returns anomaly scores (0–1) for each input vector, per the formula above. Throws if called before fit(). 各入力ベクトルの異常スコア(0–1)を上記の式で返す。fit() 前に呼ぶと例外を投げる。

predict(data: number[][]): (1 | -1)[]

Returns -1 for anomalies and 1 for normal points, using the contamination-derived threshold (or the fixed default threshold of 0.6 when contamination is "auto"). contamination から導出した閾値("auto" の場合は固定デフォルト閾値 0.6)を用いて、異常には -1、正常には 1 を返す。

decisionFunction(data: number[][]): number[]

Returns threshold - score for each point: positive values indicate normal points, negative values indicate anomalies (scikit-learn-compatible convention). 各点について threshold - score を返す。正値は正常、負値は異常(scikit-learn互換の符号規則)。

toJSON(): SerializedForest
static fromJSON(json: SerializedForest): IsolationForest

Serialize/deserialize a trained forest (e.g. for persistence or transfer to a worker/service). 学習済み森をシリアライズ/デシリアライズする(永続化やワーカー/サービスへの転送などに使用)。

Types / 型定義

interface IsolationForestOptions {
  nEstimators?: number;
  sampleSize?: number;
  contamination?: number | "auto";
  maxFeatures?: number;
  randomSeed?: number;
}

type SerializedForest = {
  version: string;
  options: ResolvedOptions;
  sampleSizeUsed: number; // sample size actually used to build the trees, min(options.sampleSize, n)
                          // 木構築に実際使用したサンプルサイズ, min(options.sampleSize, n)
  threshold: number;      // anomaly-score threshold used by predict()
                          // predict() が使用する異常スコア閾値
  trees: ITreeNode[];
};

type ITreeNode =
  | { type: "internal"; splitFeature: number; splitValue: number; left: ITreeNode; right: ITreeNode }
  | { type: "external"; size: number };

Usage / 使用例

import { IsolationForest } from "isolation-forest-ts";

const data: number[][] = [
  [1.0, 2.0],
  [1.1, 2.1],
  [0.9, 1.9],
  [50.0, 50.0], // outlier / 外れ値
];

const forest = new IsolationForest({ nEstimators: 100, sampleSize: 256, contamination: 0.1 });
forest.fit(data);

const scores = forest.score(data);       // e.g. [0.42, 0.41, 0.43, 0.82]
const labels = forest.predict(data);     // e.g. [1, 1, 1, -1]

Complexity / 計算量

• Training / 学習: O(nEstimators * sampleSize * log(sampleSize))
• Scoring / スコアリング: O(nEstimators * log(sampleSize)) per point / 点あたり
• Memory / メモリ: O(nEstimators * sampleSize)

Development / 開発

pnpm install
pnpm run typecheck   # tsc --noEmit
pnpm run test        # vitest run
pnpm run build       # tsup → dist/ (ESM + CJS + .d.ts)

依存関係インストール後、型検証・テスト・ビルドは上記コマンドで実行する。

References / 参考文献

• Liu, F. T., Ting, K. M., & Zhou, Z.-H. (2008). Isolation Forest. IEEE ICDM.
• Liu, F. T., Ting, K. M., & Zhou, Z.-H. (2012). Isolation-based Anomaly Detection. ACM TKDD.

License / ライセンス

ISC © kixixixixi — see LICENSE.