Удаление стойкого хвоста из (ненормального) распределения. Проблема неактуальных ценностей. (выборка дисперсии / k-средних / VaR, массив чисел)

Question

Хотя я понимаю, что этот вопрос сложен с математикой, настоящий ответ на него будет полезен для всех, кто имеет дело с оператором MongoDB $bucket (или его аналогами SQL), и построение данных диаграммы кластера / тепловой карты.

Подробное описание проблемы:

У меня есть массив уникальных / различных значений цен из моей БД (это всегда массив numbers с .01 точность).

Как вы можете видеть, большинство его значений находятся в диапазоне от ~ 8 до 40 (в данном конкретном случае).

[
    7.9,  7.98,  7.99,  8.05,  8.15,  8.25,   8.3,  8.34,   8.35,  8.39,
    8.4,  8.49,   8.5,  8.66,   8.9,  8.97,  8.98,  8.99,      9,   9.1,
   9.15,   9.2,  9.28,   9.3,  9.31,  9.32,   9.4,  9.46,   9.49,   9.5,
   9.51,  9.69,   9.7,   9.9,  9.98,  9.99,    10,  10.2,  10.21, 10.22,
  10.23, 10.24, 10.25, 10.27, 10.29, 10.49, 10.51, 10.52,  10.53, 10.54,
  10.55, 10.77, 10.78, 10.98, 10.99,    11, 11.26, 11.27,  11.47, 11.48,
  11.49, 11.79, 11.85,  11.9, 11.99,    12, 12.49, 12.77,   12.8, 12.86,
  12.87, 12.88, 12.89,  12.9, 12.98,    13, 13.01, 13.49,  13.77, 13.91,
  13.98, 13.99,    14, 14.06, 14.16, 14.18, 14.19,  14.2,   14.5, 14.53,
  14.54, 14.55, 14.81, 14.88,  14.9, 14.98, 14.99,    15,  15.28, 15.78,
  15.79,  15.8, 15.81, 15.83, 15.84,  15.9, 15.92, 15.93,  15.96,    16,
   16.5,    17, 17.57, 17.58, 17.59,  17.6, 17.88, 17.89,   17.9, 17.93,
  17.94, 17.97, 17.99,    18, 18.76, 18.77, 18.78, 18.99,  19.29, 19.38,
  19.78,  19.9, 19.98, 19.99,    20, 20.15, 20.31, 20.35,  20.38, 20.39,
  20.44, 20.45, 20.49,  20.5, 20.69,  20.7, 20.77, 20.78,  20.79,  20.8,
   20.9, 20.91, 20.92, 20.93, 20.94, 20.95, 20.96, 20.99,     21, 21.01,
  21.75, 21.98, 21.99,    22, 22.45, 22.79, 22.96, 22.97,  22.98, 22.99,
     23, 23.49, 23.78, 23.79,  23.8, 23.81,  23.9, 23.94,  23.95, 23.96,
  23.97, 23.98, 23.99,    24, 24.49,  24.5, 24.63, 24.79,   24.8, 24.89,
   24.9, 24.96, 24.97, 24.98, 24.99,    25, 25.51, 25.55,  25.88, 25.89,
   25.9, 25.96, 25.97, 25.99,    26, 26.99,    27, 27.55,     28,  28.8,
  28.89,  28.9, 28.99,    29, 29.09,    30, 31.91, 31.92,  31.93,  33.4,
   33.5,  33.6,  34.6,  34.7, 34.79,  34.8,    35, 38.99,  39.57, 39.99,
     40,    49,    50, 50.55, 60.89, 99.99, 20000, 63000, 483000
]

Сама проблема или Как решить ( не) хвост нормального распределения из (ненормальный) элементов

Мне нужно найти / определить нерелевантные значения, какой-то «грязный хвост», и удалить / исключить его. На самом деле мне даже не нужно удалять его из массива, реальный случай - найти соответствующий номер latest. Чтобы определить его как значение cap, для нахождения диапазона от floor (минимальное значение) до cap (максимальное значение), например:

floor value => 8
cap value => 40

О чем я говорю?

Например, в некоторых случаях: это будут значения после 40 (или, возможно, даже 60), например: 49, 50, 50.55, 60.89, 99.99, 20000, 63000, 483000

Определены ( my me ) как ненормально.

Что будет засчитано как ответ?

1. S уровень. Четкий / оптимальный код (язык не имеет значения, но предпочтительнее JavaScript) или формула (если она есть в математике), которая может решить проблему для небольшого / не ресурсоемкого объема использования ЦП / ОЗУ и времени. Было бы идеально, если бы мне даже не нужно было проверять каждый элемент в массиве или я мог бы пропустить некоторые из них, например, начиная с peak / самого популярного значения в массиве.

2. Уровень. Ваш собственный опыт или code попробуйте с любыми соответствующими результатами или улучшите текущую формулу с большей эффективностью. Если нет ответа S tier горизонта, вы победитель.

3. B уровень. Что-нибудь полезное. Статья в блоге / ссылка на Google. Главное требование - иметь смысл. Неочевидные решения приветствуются. Даже если ваш код потребляет много ОЗУ / ЦП или занимает огромное количество времени.

TL: ВИЗУАЛЬНОЕ УТОЧНЕНИЕ DR

По каким критериям и как я следует «нацеливаться на хвост» / удалять из массива нерелевантные элементы со значениями x (резко возрастающие и редко встречающиеся)?

Хвостик

Answer 1

В данном наборе данных есть несколько огромных выбросов, которые несколько затрудняют анализ с использованием стандартных статистических методов (если бы он вел себя лучше, я бы рекомендовал подогнать к нему несколько распределений-кандидатов и выяснить, какое из них лучше всего подходит - логарифмическое нормальное распределение, бета-распределение, гамма-распределение и т. д. c).

Проблема определения того, какие выбросы следует игнорировать, может быть решена в общем c более упрощенными, но менее строгими методами; один из методов состоит в том, чтобы сравнить значения данных в различных процентилях и отбросить те, где различия становятся «слишком высокими» (для подходящим образом выбранного значения «слишком велико»).

Например, вот последние несколько записей, если мы go поднялись на два процентиля; столбец дельты показывает разницу между предыдущим процентилем и этим.

Процентили на 2

Здесь вы можете видеть, что разница с предыдущей записью увеличивается почти на 2, когда мы достигаем 87, и увеличивается (в основном) оттуда. Чтобы использовать "хорошее" число, давайте сделаем отсечение 85-го процентиля и проигнорируем все значения выше этого.

Учитывая отсортированный список выше в массиве с именем data, мы игнорируем любой индекс выше

Math.floor(data.length*85/100)

Приведенный выше анализ можно повторить в коде, если он должен динамически изменяться (или чтобы привлечь внимание к отклонениям, когда 85 - неправильное значение), но я оставляю это в качестве упражнения для читателя.

Answer 2

Это версия 2 кода, и точная версия, которая работает в настоящий момент на производстве. Он покрывает около 80% + проблем, но по-прежнему остается bottle -neck.

/** priceRangeArray ALWAYS SORTED ASC */
let priceRangeArray = [1,2,3...]
/** Resulting array */
let priceArray = []
/** Control variable */
let prev_sV = 0
/** Array length is always more then 3 elements */
const L = priceRangeArray.length;
/** Sample Variance algorithm */
for (let i = 2; i < L-1; i++) {
    /**
     * We skip the first two value, because 1st sV could be too low
     * sV becomes previous sV
     */
     if (prev_SV === 0) {
       /** prev_sV of 2nd element */
       prev_sV = ( 1 / L * (Math.pow(priceRangeArray[1],2))) - (Math.pow((1 / L * priceRangeArray[1]),2));
     } else {
       prev_sV = sV 
     }
     /**
     * sample variance, right?
     * 1 / L * (el ^ 2) - ( 1 / L * el) ^ 2
     * @type {number}
     */
     sV = ( 1 / L * (Math.pow(priceRangeArray[i],2))) - (Math.pow((1 / L * priceRangeArray[i]),2));
     /** User-defined, 1.1 is a control constant */
     if (prev_sV * 1.1 < sV) {
        break;
     }
    /** Control passed values to new array */
    priceArray.push(priceRangeArray[i]);
}
console.log(priceArray)

Он основан на статье Wikipedia Variance . Лог c довольно прост, пока я не могу удалить начало (первые 2 значения, даже если они слишком низкие), я начинаю цикл for of с 3-го элемента массива и проверяю каждый следующий из их с моей формулой control (что-то с sqrt(pow^2) текущего и предыдущего значения).

Первая версия этого кода, имеет линейный лог c и просто меняет предыдущее значение с текущего, по одному из этих простых принципов, например:

• Если текущее значение вдвое ( xN ) больше предыдущего, то break
• Если текущее значение больше предыдущего, на 10%, тогда break.

Настоящая проблема в том, что он не работает с начальными или маленькими значениями в массивах типа: [ 1,2,3,4,13,14,16,22,100,500000].

Где, как вы можете видеть, значение cap может быть определено как 4 вместо 22 или 100.