Сюда переношу все, что связано со статистикой и нужно было на практике – в тестировании, разработке и в других инженерных задачах.
Арифметической прогрессией (арифметической последовательностью) – последовательность с фиксированным инкрементом.
Арифметической прогрессией (арифметической последовательностью) - называется последовательность чисел a1,a2,...,an, каждое из которых, начиная с a2, получается из предыдущего прибавлением к нему одного и того же постоянного числа d (разность прогрессии), то есть:An=An−1+D. - Если известен первый член прогрессии и её разность, то n-ый член арифметической прогрессии находится по формуле An=A1+D(n−1). - Сумма первых (т.е. только для последовательности integer с шагом 1) элементов находится по формуле n*(n+1)/2 # example 100, 110, 120, 130, 140, 150, 160, 170, 180 # calc n-member a_9 = 100 + 10 * (9-1) = 180 # example2 1, 2, 3, 4, 5, 6, 7, 8, 9 # calc sum of members a_sum = (9 * 10)/2 = 45
Двоичным (булевым) n-мерным вектором – двоичная последовательность.
Двоичным (булевым) n-мерным вектором называют набор из n чисел (b1, b2, ..., bn), каждое из которых может принимать только значения в двоичной системе счисления – 0 или 1. Двоичный вектор является обратным (инвертированным), если он образован из заменой всех нулей единицами, а единиц – нулями. Например, если вектор равен (0,1,1,1,0,1), то инвертированный (1,0,0,0,1,0).
Геометрической прогрессией – последовательность с фиксированным множетелем.
Геометрической прогрессией - это последовательность, первый член которой не равен нулю, а каждый последующий член равен произведению предыдущего члена на некоторое фиксированное ненулевое число (называемое знаменателем геометрической прогрессии q). Любой член геометрической прогрессии может быть вычислен по формуле Bn = B1*q^(n-1) # example 3, 12, 48, 192, 768, 3072 # calc n-member a_6 = 3 * 4^5 = 3072
Коэффициент корреляции (correlation coefficient) – Корреля́ция (от лат. correlatio «соотношение»), или корреляцио́нная зави́симость — статистическая взаимосвязь двух или более случайных величин (либо величин, которые можно с некоторой допустимой степенью точности считать таковыми). При этом изменения значений одной или нескольких из этих величин сопутствуют систематическому изменению значений другой или других величин ((почему это важно – в wiki)). Пример расчета в python.
| Количественная мера тесноты связи |
Качественная характеристика силы связи |
| 0,1-0,3 | Слабая |
| 0,3-0,5 | Умеренная |
| 0,5-0,7 | Заметная |
| 0,7-0,9 | Высокая |
| 0,9-0,99 | Весьма высокая |
Размах (range) – разница между максимальным и минимальным значением выборки, максимальное расстояние между значениями ряда/выборки. Полезно помимо размаха так же рассчитывать процент размаха от минимального (range/min * 100) – покажет на сколько минимальная величина отклоняется от максимального в процентах.
https://en.wikipedia.org/wiki/Range_(statistics) In statistics, the range of a set of data is the difference between the largest and smallest values. Sample RANGE : The spread (distance or value) from the lowest to the highest value in the sample.
Среднеквадратическое отклонение (СКО) – наиболее распространённый показатель рассеивания значений случайной величины относительно её математического ожидания ((среднего значения)). Обычно он означает квадратный корень из дисперсии случайной величины, но иногда могут означать тот или иной вариант оценки этого значения.
Нужно уметь применять статистику (с этим часто проблема) и если задача найти максимальное расстояние между значениями ряда/выборки – то среднеквадратичное отклонение не подходит, нужно считать размах (выше про него).
Встречаются также синонимы словосочетания среднеквадрати́ческое отклоне́ние, как то́: среднее квадрати́ческое отклоне́ние; среднеквадрати́чное отклоне́ние; квадрати́чное отклоне́ние; станда́ртное отклоне́ние; станда́ртный разбро́с.
Очень хорошо описано в wiki, включая то, что не добавил сюда – пример расчета величины среднеквадратичного отклонения (расчет среднего, расчет квадрата отклонений каждой величины, расчет дисперсии в виде среднего от квадратов отклонений, расчет отклонения в виде корня дисперсии), примеры из жизни, когда оно может использоваться (погода, спорт, экономика).
Стандартное отклонение измеряется в тех же единицах, что и сама случайная величина, а дисперсия измеряется в квадратах этой единицы измерения. Большее значение среднеквадратического отклонения показывает больший разброс значений в представленном множестве со средней величиной множества; меньшее значение, соответственно, показывает, что значения в множестве сгруппированы вокруг среднего значения.
Например, у нас есть три числовых множества: {0, 0, 14, 14}, {0, 6, 8, 14} и {6, 6, 8, 8}. У всех трёх множеств средние значения равны 7, а среднеквадратические отклонения, соответственно, равны 7, 5 и 1. У последнего множества среднеквадратическое отклонение маленькое, так как значения в множестве сгруппированы вокруг среднего значения; у первого множества самое большое значение среднеквадратического отклонения — значения внутри множества сильно расходятся со средним значением.
# Excel
=СТАНДОТКЛОН.Г(0;0;14;14) # 7
=СТАНДОТКЛОН.Г(0;6;8;14) # 5
=СТАНДОТКЛОН.Г(6;6;8;8) # 1
В общем смысле среднеквадратическое отклонение можно считать мерой неопределённости. К примеру, в физике среднеквадратическое отклонение используется для определения погрешности серии последовательных измерений какой-либо величины. Это значение очень важно для определения правдоподобности изучаемого явления в сравнении с предсказанным теорией значением: если среднее значение измерений сильно отличается от предсказанных теорией значений (большое значение среднеквадратического отклонения), то полученные значения или метод их получения следует перепроверить.
Процент одного числа от другого – часто есть задача сколько составляет число X от числа Y. Формула расчета простейшая, но зачастую (float, большие значения int) быстрее скопипастить. Удобный калькулятор.
Формула: (x/y) * 100
Перцентиль, процентиль (percentile) – это сотая доля объема измеренной совокупности, выраженная в процентах. Процентиль позволяет понять как данные распределены разделив их на 100 долей. Частные случаи:
-
- Медиана – это 50ый процентиль.
- Cамое большое значение в исходном наборе данных – 100-й процентиль.
- Самое малое значение – 0-й.
Например, пятый процентиль охватывает 5% объема выборки. Предположим, показатель Ивана равен пятому процентилю. Это означает, что Иван написал тест лучше, чем 5% студентов. Процентиль (или центиль ) - это показатель, используемый в статистике , указывающий значение, ниже которого падает данный процент наблюдений в группе наблюдений. Например, - 20-й процентиль - это значение (или балл), ниже которого могут быть обнаружены 20% наблюдений. Эквивалентно 80% наблюдений находятся выше 20-го процентиля. - 80-й процентиль - 20% наблюдений находятся выше 80-го процентиля.
Используется в нагрузочном тестировании (напр. JMeter) как метрика, не скрывающая всплески/выбросы, в отличии от среднего значения.
Пример расчета перцентиля/процентиля
-
- Логика расчета и три разных способа расчета (могут давать разный результат!) хорошо описаны тут
- Расчет самый простой в Excel, автоматизация расчета возможна с использованием python + numpy, python + pandas. Пример расчета перцентиля 80,90,95,99 поведение в случае выборки с “выбросом”.
- Сложнее посчитать самому, но вполне возможно
Пример расчета значения 50-го процентиля (медианы) для набора 1, 2, 3, 4, 5 разными способами.
# EXCEL
=PERCENTILE.INC({1;2;3;4;5};0,5) = 3
=PERCENTILE.EXC({1;2;3;4;5};0,5) = 3
=ПРОЦЕНТИЛЬ.ВКЛ({1;2;3;4;5};0,5) = 3
=ПРОЦЕНТИЛЬ.ВЫКЛ({1;2;3;4;5};0,5) = 3
# PYTHON
>>> import numpy as np
>>> a = np.array([1,2,3,4,5])
>>> p = np.percentile(a, 50)
>>> print(p)
3.0
# Ручной расчет - самый простой (не точный, но значения будут близки или равны получаемым в excel/python):
1) Сортируем массив данных по возрастанию и нумеруем (ранжируем, присваиваем номер) результат сортировки 2) Определяем номер/ранг на основе заданного процентиля n = ceil(P/100 * N) 2.1) P - искомый процентиль 2.2) N - общее количество номеров/рангов 3.3) n - ранг 3) Значение соответствующее рангу считаем процентилем
1 значение - 1 ранг
2 значение - 2 ранг
3 значение - 3 ранг
4 значение - 4 ранг
5 значение - 5 ранг
n = 50/100 * 5 = ceil(2.5) = 3
Доверительный интервал – интервал, в котором с заданной вероятностью (доверительной вероятностью) заключен параметр генеральной совокупности (напр. генеральное среднее). Доверительная вероятность выражается числом от 0 до 1 или в процентах, например 90%, 95%, 99% и показывает вероятность того, что действительное значение исследуемой переменной будет лежать в принятом (указанном) диапазоне.
Среднее значение (average/mean) – сумма значений элементов поделенная на два:
(N1 + N2 + N3)/2
Средневзвешанное значение (weighed average/mean) – когда элементы не равноценны т.к. если веса всех элементов равны – это простое среднее. Используется часто на практике – например, расчет NSS LABS throughput, расчет IMDB score. Пример расчет, когда вес первого 0.9, второго 1.2, третьего 2.2:
(N1*0.9 + N2*1.2 + N3*2.2)/2
NSS Labs The weighted arithmetic mean is similar to an ordinary arithmetic mean (the most common type of average), except that instead of each of the data points contributing equally to the final average, some data points contribute more than others. The notion of weighted mean plays a role in descriptive statistics and also occurs in a more general form in several other areas of mathematics. If all the weights are equal, then the weighted mean is the same as the arithmetic mean. IMDb Weighted Average Ratings IMDb publishes weighted vote averages rather than raw data averages. The simplest way to explain it is that although we accept and consider all votes received by users, not all votes have the same impact (or ‘weight’) on the final rating. When unusual voting activity is detected, an alternate weighting calculation may be applied in order to preserve the reliability of our system. To ensure that our rating mechanism remains effective, we do not disclose the exact method used to generate the rating.
Медиана — это значение признака, справа и слева от которого находится равное число наблюдений (по 50%, 50ый процентиль). Для получения значения, которое находится по середине выборки правильнее использовать медиану, а не среднее значение. Потому что среднее не учитывает выбросы, в отличии от медианы.
Рассчитать медиану для числового ряда просто (не говоря про python функции, с ними пример ниже): Например, медианой набора {11, 9, 3, 5, 5} является число 5, так как оно стоит в середине этого набора после его упорядочивания: {3, 5, 5, 9, 11}. Если в выборке чётное число элементов, медиана может быть не определена однозначно: тогда для числовых данных чаще всего используют полусумму двух соседних значений – то есть медиану набора {1, 3, 5, 7} принимают равной 4 (пример №2 расчета в Excel для такого случае ниже). Можно также сказать, что медиана является 50-м персентилем, 0,5-квантилем или вторым квартилем выборки или распределения.
Медиа́на (от лат.mediāna «середина») набора чисел — число, которое находится в середине этого набора, если его упорядочить по возрастанию, то есть такое число, что половина из элементов набора не меньше него, а другая половина не больше. Пример №1 (python) Среднее для ряда 1 2 6 = 3 Медиана для ряда 1 2 6 = 2 >>> import statistics >>> l = [1,2,6] >>> statistics.mean(l) 3 >>> statistics.median(l) 2 Пример №2 (excel) Медиана для ряда 1 2 3 4 5 6 7 8 9 10 = 5.5 ((5+6/2)) =MEDIAN(1;2;3;4;5;6;7;8;9;10) =PERCENTILE.INC(A1:A10; 0,5) =PERCENTILE.EXC(A1:A10; 0,5) Пример №3 (python) Дано: список зарплат рядовых медицинских сотрудников больницы (в тыс. руб.): 25, 17, 23, 18, 24, 23, 16, а также зарплата главврача – 85 и его заместителя – 50. Каков средний уровень зарплаты в больнице? Согласно среднему арифметическому, средняя зарплата по больнице – 31,2 тыс. рублей. Если же мы посчитаем вместо среднего арифметического медиану, то получим 23 тыс. рублей. Что, по-вашему, ближе к правде? Пример расчет в python: >>> import statistics >>> l = [25, 17, 23, 18, 24, 23, 16, 85, 50] >>> statistics.mean(l) 31.22222222222222 >>> statistics.median(l) 23 Наглядно между какими значениями находится среднее (23) и медиана (31): 16 17 18 23 23 24 25 50 85 В случае же отклонения распределения от нормального закона среднее значение использовать некорректно, так как оно является слишком чувствительным параметром к так называемым «выбросам» — нехарактерным для изучаемой выборки,слишком большим или слишком малым значением (рис. 2). В этом случае для характеристики центральной тенденции в выборке должен применяться другой параметр — медиана. Медиана — это значение признака, справа и слева от которого находится равное число наблюдений (по 50%). Этот параметр (в отличие от среднего значения) устойчив к «выбросам». Заметим также,что медиана может использоваться и в случае нормального распределения — в этом случае медиана совпадает со средним значением.
Alert – ниже спорно.
Парадокс Монти Холла – почитал, казалось бы даже очень показательный пример с выборкой из 1000 не поменял моего мнения в ошибочности «парадокса». Считаю так, потому что запоминания состояния в игре нет, судя по таблице в wiki (ведущий открыл третью дверь с козой, но, в комбинаторике за ней авто, а за «оставшимися» дверьми козы – третий вариант) и выбрал ты плохой или хороший изначально в выборке из 1000 (или 1 МЛН, неважно) не важно – от того, что ты выбрал в начале не делает выбранный изначально вариант более хорошим или альтернативный вариант более хорошим. При этом если запоминание состояние добавить – то логика, описанная в парадоксе как верная выглядит корректной (менять выбор правильно).
Их вес равноценен при принятии последнего решения, а не первичного.
Тебе может
1) казаться психологически что выбранный вариант верен («мой выбор ‘выбил’ почти все редультаты fail» – такую логику оспаривает корректно парадокс),
2) казаться, что нужно поменять выбор («вероятность иметь изначально ошибочный выбор намного выше, чем успешный» – по якобы корректной логике парадокса)
но и первое и второе ошибка!
Рекурсия – в простом случае реализации вызов из функции самой функции. В общем случае. Пример реализации рекурсии описан в статье Python, пример оценки сложности в Оценка сложности алгоритма (асимптотическая оценка, оценка Big O)
Использовать рекурсию нужно аккуратно, зачастую задача прекрасно решается без нее. Рекурсия в общем случае более накладная операция по памяти см. в Оценка сложности алгоритма (асимптотическая оценка, оценка Big O). Я ее использовал для построителя топологии (запросы в базу для построения вниз по дереву графа) и binary search (поиск производительности), но к примеру, расчет факториала (ниже) легко реализуется за счет for + range (с рекурсией же вообще не работает на 1 млн. числах, в то числе с выкручиванием recursion depth sys.setrecursionlimit(xxx) падает с Segmentation fault: 11). Я тем более не говорю про определение является ли палиндромом строка, что можно реализовать сравнением массивов (деление на 2 и reverse перед сравнением).
При этом не стоит всегда выбирать итеративное решение вместо реркурсии, даже если оно есть – рекурсивное решение может быть значительно сложнее для реализации, а одинаковая потенциальная асимптотика в сравнении с итеративным решением + более простой код зачастую перевешивают минусы рекурсии.
Кроме того pay attention:
Для полноты картины обязательно надо упомянуть о борьбе с рекурсией. Зачем же с ней бороться? Повышается производительность. Но это не значит, что с ней просто необходимо бороться, ведь применение рекурсии очевиднее, проще и приятнее, чем итерационные варианты.
Последовательность/ряд Фибоначчи – частый вопрос на собеседованиях. Элемент равен сумме двух предыдущих N = (N-1)+(N-2). Соотношение смежных элементов около 0.61 (близко к золотому делению/сечению). Пример расчета числа и дерево вызовов есть в статье Python, пример оценки сложности в Оценка сложности алгоритма (асимптотическая оценка, оценка Big O)
Пузырьковая сортировка – базовая сортировка со сложностью O(n^2), популярный вопрос на собеседованиях. Почти все другие алгоритмы сортировки более эффективны (подробнее в оценке сложности). Принцип работы – в каждую итерацию мы гарантированно определяем «пузырек» в виде максимального элемента и перемещаем его вправа. Количество итераций в итоге не более чем N^2 (с дополнительным вычитанием последнего элемента). Пример реализации есть в статье Python, пример оценки сложности в Оценка сложности алгоритма (асимптотическая оценка, оценка Big O)
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется перестановка элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).
Быстрая сортировка на основе рекурсии (quick sort)
Сортировка рекурсивным слиянием (merge sort; recursive sorting algorithm) с двоичным делением