Продам сайты

Реализация алгоритма поиска аномалий (Isolation Forest)

В этой статье мы рассмотрим, как можно реализовать популярный алгоритм поиска аномалий — Isolation Forest — на языке программирования C#. Алгоритм Isolation Forest эффективен для выявления аномальных данных в больших объемах информации и не требует предварительной обработки данных, что делает его универсальным инструментом. Мы подробно остановимся на теоретической части алгоритма, приведем его реализацию в C# и продемонстрируем использование на практических примерах.

Isolation Forest (Изоляционный лес) — это алгоритм, разработанный для обнаружения аномалий в данных. Он основан на идее изолирования точек от выбросов с помощью случайных деревьев, которые построены не для классификации или регрессии, а специально для выявления аномалий. Этот подход позволяет эффективно и быстро определять данные, отклоняющиеся от нормы.

  1. Isolation Trees (Изоляционные деревья): Каждое из этих деревьев строится на случайно выбранных подмножествах данных и работает следующим образом:

    • Разбиение набора данных происходит посредством выбора случайной переменной и значения, после чего узлы дерева разделяют данные на две группы.
    • Процесс продолжается до тех пор, пока все точки не будут изолированы или достигнут максимальная глубина дерева.
  2. Path Length (Длина пути): Для каждой точки данных в Isolation Tree вычисляется “путь” — количество шагов, необходимых для изоляции этой точки. Чем короче путь, тем больше вероятность того, что точка является аномалией.

  3. 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}");
        }
    }
}
  1. Генерация данных: Мы создаем случайные данные, включая аномальные (по одной каждые 10 шагов).
  2. Инициализация Isolation Forest: Задаются параметры — количество деревьев и размер подвыборки для построения каждого дерева.
  3. Обучение модели: Метод Fit используется для обучения леса на данных.
  4. Прогнозирование аномальности: Метод Predict вычисляет и возвращает оценку аномалии для каждой точки данных.

В этой статье мы рассмотрели теоретическую основу Isolation Forest и представили его реализацию на языке C#. Мы показали, как можно использовать такие библиотеки, как System.Collections.Generic для работы с коллекциями данных и Random для генерации случайных значений. Приведенный пример демонстрирует базовое использование алгоритма для обнаружения аномальных данных.

Isolation Forest является мощным инструментом в области машинного обучения, особенно для задач выявления выбросов. Реализация на C# позволяет использовать этот алгоритм в широком спектре приложений, таких как финансовый мониторинг, безопасность и обработка больших данных.

Если вы хотите дальше изучить Isolation Forest, рекомендуется ознакомиться с расширенными версиями алгоритма, такими как iForest++ или использовать более продвинутые библиотеки для обработки данных в C#, такие как ML.NET.

Оцените статью
Все о языке программирования C#