В этой статье мы рассмотрим, как можно реализовать популярный алгоритм поиска аномалий — Isolation Forest — на языке программирования C#. Алгоритм Isolation Forest эффективен для выявления аномальных данных в больших объемах информации и не требует предварительной обработки данных, что делает его универсальным инструментом. Мы подробно остановимся на теоретической части алгоритма, приведем его реализацию в C# и продемонстрируем использование на практических примерах.
Isolation Forest (Изоляционный лес) — это алгоритм, разработанный для обнаружения аномалий в данных. Он основан на идее изолирования точек от выбросов с помощью случайных деревьев, которые построены не для классификации или регрессии, а специально для выявления аномалий. Этот подход позволяет эффективно и быстро определять данные, отклоняющиеся от нормы.
-
Isolation Trees (Изоляционные деревья): Каждое из этих деревьев строится на случайно выбранных подмножествах данных и работает следующим образом:
- Разбиение набора данных происходит посредством выбора случайной переменной и значения, после чего узлы дерева разделяют данные на две группы.
- Процесс продолжается до тех пор, пока все точки не будут изолированы или достигнут максимальная глубина дерева.
-
Path Length (Длина пути): Для каждой точки данных в Isolation Tree вычисляется “путь” — количество шагов, необходимых для изоляции этой точки. Чем короче путь, тем больше вероятность того, что точка является аномалией.
-
Isolation Forest: Состоит из коллекции Isolation Trees. Анализируя среднюю длину пути для каждой точки данных по всем деревьям, можно определить степень аномальности.
Для вычисления вероятности того, что данные являются аномалией, используется формула:
[ s(x) = 2^{-\frac{E(h(x))}{c(n)}} ]
где ( E(h(x)) ) — ожидаемая длина пути для точки ( x ), а ( c(n) ) — коэффициент коррекции, зависящий от размера выборки.
Коэффициент ( c(n) ) вычисляется по формуле:
[ c(n) = 2 H(n-1) – \frac{2 (n-1)}{n} ]
где ( H(i) ) — гармоническая последовательность.
Перед началом кодирования необходимо подготовить среду разработки. Для работы с C# можно использовать такие IDE, как Visual Studio или JetBrains Rider.
Мы начнем созданием базовых классов и структур данных, необходимых для реализации Isolation Forest:
using System;
using System.Collections.Generic;
public class Node
{
public int FeatureIndex { get; set; }
public double Threshold { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
}
public class IsolationTree
{
private readonly List<double> _samples;
private readonly Random _random = new Random();
private readonly int _heightLimit;
public Node Root { get; private set; }
public IsolationTree(List<double[]> samples, int heightLimit)
{
_samples = samples.ConvertAll(sample => sample[0]); // Пример для одномерного случая
_heightLimit = heightLimit;
}
}
Реализуем методы, необходимые для построения Isolation Tree:
public class IsolationTree
{
// Предыдущий код...
public void Build(int currentHeight)
{
if (_samples.Count <= 1 || currentHeight >= _heightLimit)
{
Root = new Node { FeatureIndex = -1 }; // Листовой узел
return;
}
int featureIndex = _random.Next(_samples.Count);
double threshold = GetRandomThreshold(featureIndex);
var leftSamples = new List<double>();
var rightSamples = new List<double>();
foreach (var sample in _samples)
{
if (sample <= threshold)
leftSamples.Add(sample);
else
rightSamples.Add(sample);
}
Root = new Node { FeatureIndex = featureIndex, Threshold = threshold };
Root.Left = new IsolationTree(leftSamples.ConvertAll(x => new double[] { x }), _heightLimit).Build(currentHeight + 1);
Root.Right = new IsolationTree(rightSamples.ConvertAll(x => new double[] { x }), _heightLimit).Build(currentHeight + 1);
}
private double GetRandomThreshold(int featureIndex)
{
double min = double.MaxValue;
double max = double.MinValue;
foreach (var sample in _samples)
{
if (sample < min) min = sample;
if (sample > max) max = sample;
}
return min + _random.NextDouble() * (max - min);
}
}
Теперь мы можем создать класс, который будет представлять сам лес из деревьев:
public class IsolationForest
{
private readonly int _nTrees;
private readonly int _subSamplingSize;
private readonly List<IsolationTree> _trees;
public IsolationForest(int nTrees, int subSamplingSize)
{
_nTrees = nTrees;
_subSamplingSize = subSamplingSize;
_trees = new List<IsolationTree>();
}
public void Fit(List<double[]> samples)
{
for (int i = 0; i < _nTrees; i++)
{
var subset = GetRandomSubset(samples);
var tree = new IsolationTree(subset, GetHeightLimit(subset.Count));
tree.Build(0);
_trees.Add(tree);
}
}
private List<double[]> GetRandomSubset(List<double[]> samples)
{
var randomIndices = new HashSet<int>();
while (randomIndices.Count < _subSamplingSize && randomIndices.Count < samples.Count)
{
int index = new Random().Next(samples.Count);
randomIndices.Add(index);
}
var subset = new List<double[]>(_subSamplingSize);
foreach (var index in randomIndices)
{
subset.Add(samples[index]);
}
return subset;
}
private int GetHeightLimit(int n)
{
// Расчет ожидаемой глубины дерева
double log = Math.Log(n - 1) + 0.5772156649; // Логарифм натуральный и константа Эйлера
return (int)Math.Ceiling(log / Math.Log(2));
}
public List<double> Predict(List<double[]> samples)
{
var scores = new List<double>();
foreach (var sample in samples)
{
double pathLength = 0;
for (int i = 0; i < _nTrees; i++)
{
pathLength += PathLength(sample, _trees[i].Root) / GetHeightLimit(_subSamplingSize);
}
double anomalyScore = CalculateAnomalyScore(pathLength);
scores.Add(anomalyScore);
}
return scores;
}
private int PathLength(double[] sample, Node node)
{
if (node.FeatureIndex == -1) return 0;
var value = sample[node.FeatureIndex];
if (value <= node.Threshold)
{
if (node.Left != null) return 1 + PathLength(sample, node.Left);
else return 1;
}
else
{
if (node.Right != null) return 1 + PathLength(sample, node.Right);
else return 1;
}
}
private double CalculateAnomalyScore(double pathLength)
{
// Реализация расчета аномальности по формуле Isolation Forest
int n = _subSamplingSize;
double c_n = 2 * Math.Log(n - 1) + 0.5772156649 - 2 * (n - 1) / n; // Гармоническая последовательность
return Math.Pow(2, -pathLength / c_n);
}
}
Теперь мы можем создать простой пример использования Isolation Forest:
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
// Генерация случайных данных с аномалиями
var samples = new List<double[]>();
Random random = new Random();
for (int i = 0; i < 100; i++)
{
double[] sample;
if (i % 10 == 0) // Добавление аномальных данных каждые 10 шагов
sample = new double[] { random.NextDouble() * 50 };
else
sample = new double[] { random.NextDouble() * 2 };
samples.Add(sample);
}
// Инициализация Isolation Forest с параметрами
var isolationForest = new IsolationForest(nTrees: 100, subSamplingSize: 256);
// Обучение модели на данных
isolationForest.Fit(samples);
// Прогнозирование аномальности новых данных
var scores = isolationForest.Predict(samples);
// Вывод результатов
for (int i = 0; i < scores.Count; i++)
{
Console.WriteLine($"Sample {i}: Score={scores[i]:F4}");
}
}
}
- Генерация данных: Мы создаем случайные данные, включая аномальные (по одной каждые 10 шагов).
- Инициализация Isolation Forest: Задаются параметры — количество деревьев и размер подвыборки для построения каждого дерева.
- Обучение модели: Метод
Fitиспользуется для обучения леса на данных. - Прогнозирование аномальности: Метод
Predictвычисляет и возвращает оценку аномалии для каждой точки данных.
В этой статье мы рассмотрели теоретическую основу Isolation Forest и представили его реализацию на языке C#. Мы показали, как можно использовать такие библиотеки, как System.Collections.Generic для работы с коллекциями данных и Random для генерации случайных значений. Приведенный пример демонстрирует базовое использование алгоритма для обнаружения аномальных данных.
Isolation Forest является мощным инструментом в области машинного обучения, особенно для задач выявления выбросов. Реализация на C# позволяет использовать этот алгоритм в широком спектре приложений, таких как финансовый мониторинг, безопасность и обработка больших данных.
Если вы хотите дальше изучить Isolation Forest, рекомендуется ознакомиться с расширенными версиями алгоритма, такими как iForest++ или использовать более продвинутые библиотеки для обработки данных в C#, такие как ML.NET.

