Фильтрация шумовых выбросов

Проблема

Предположим, мы производим «измерение» некой двумерной величины много раз. Но наш «прибор» с некоторой вероятностью дает сбой, поэтому мы получаем примерно такой результат:

Данные измерений до фильтраНевооруженным глазом заметен кластер «правильных» измерений. Но как его выделить программно? Актуально, когда вариант «ручного» просмотра результатов человеком невозможен: например, если измерения производятся автоматически и являются промежуточным звеном в каком нибудь процессе. Конечно, можно применить сложные статистические техники и машинное обучение. Но когда данные имеют один единственный «популярный» кластер, а «помехи» имеют случайный характер, возможно, наиболее эффективным методом будет…

Ура! Это первый мой пост с картинками 🙂

Идея

Идея состоит в том, чтобы учитывать только те данные, которые отклонились от среднего не больше чем среднее отклонение. Возможно, звучит сложно, однако, на самом деле, все предельно просто и вычислительно-эффективно:

  1. Вычисляем среднее арифметическое по всем данным
  2. Вычисляем отклонение всех данных от среднего
  3. Вычисляем среднее отклонение
  4. Исключаем те измерения, отклонение которых(шаг 2) оказалось больше среднего отклонения
  5. По оставшимся измерениям уверенно считаем среднее и среднее отклонение что и является искомым результатом и описывает кластер

Иллюстрация

Резюме

Метод эффективный и очень простой, в силу чего я не могу претендовать на авторство: вполне вероятно, что он имеет какое нибудь научно-верное название и активно применяется. Но я бы назвал его «Deviation threshold pruning» или «Отсечение по порогу отклонения». Добавлю, что метод мной успешно применен и решает вполне реальную проблему: для вычисления оптического потока применяется алгоритм Лукаса-Канаде, который, в принципе, вполне точный в большинстве случаев, но в нескольких точках может дать вообще неверные результаты.

ЗЫ

Уже после написания статьи натолкнулся на понятие Outlier (выброс) и алгоритмы их детектирования (Outlier Detection). Собственно, могу порекомендовать python-библиотеку для машинного обучения scikit-learn и в частности ее модуль outlier detection. Кстати, есть еще алгоритмы novelty detection — очень похоже на outlier detection, но его назначение в том, чтобы защититься от будущих выбросов, которых нет в изначальной выборке.  То есть, изначально дано некоторое подмножество данных, по которым строится горизонт, с помощью которого в дальнейшем фильтруются новые данные: выбросы отбрасываются если они выпадают из горизонта. Оба подхода широко применяются в машинном обучении. Уверен, есть и «гибридные» алгоритмы: например, можно при появлении выброса на лету слегка «подправлять» горизонт таким образом, чтобы выбросы скапливающиеся в одном кластере в итоге перестали считаться выбросами. Получается самообучение.

Спасибо, что читаете!

Код

Доступен на GitHub

import numpy as np
from matplotlib import pyplot as plt

pts = np.float32([
    (4.0,4.0),(4.1,4.1),(4.1,4.0),
    (3.9,4.0),(3.9,4.1),(3.9,3.9),
    (4,4.5),(3.8,3.8),(4.2,3.9),
    (4.1,4.1),(4.5,4.1),(4.5,3.7),

    (7,2),(7,1),(7,6),(8,6),(10,6),(7,7),(8,4),
    ])

mean_pt = np.mean(pts,axis=0)
mean_x,mean_y = mean_pt
diffs = np.apply_along_axis(np.linalg.norm,1,pts - mean_pt)
mean_diff = np.mean(diffs)

filtered = [pts[i] for i,diff in enumerate(diffs) if diff <= mean_diff]
filtered = np.float32(np)
filtered_mean = np.mean(filtered,axis=0)

plt.plot(pts[:,0],pts[:,1],'ro')
plt.plot(mean_x,mean_y,'w^')
plt.plot(filtered[:,0],filtered[:,1],'bo')
plt.plot(filtered_mean[0],filtered_mean[1],'w^')
plt.show()
Запись опубликована в рубрике Алгоритмы с метками , , , , , , , . Добавьте в закладки постоянную ссылку.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *