Comments 18
Может, я чего-то не понял, но мне кажется, оба алгоритма слишком усложнены.
Поясните, пожалуйста:
для чего интегрировать плотность распределения? есть ли для нас разница, считать каждое значение пиком (дельта-функцией) или ступенькой (разрывом), если суть алгоритма одна и та же?
почему бы просто не создать массив по числу интервалов и складывать в него данные, пройдя одним циклом по
rnd_list?
Спасибо за комментарий. Вы пишете: "для чего интегрировать плотности распределения?", не совсем понимаю, к чему именно относится этот вопрос? Мы нигде не интегрируем плотность распределения, ее нам как раз нужно найти (оценить) по заданному множеству наблюдений случайной величины X (как замечено ниже, совсем не обязательно случайного процесса).
есть ли для нас разница, считать каждое значение пиком (дельта-функцией) ...
Не очень понял, что значит считать значение дельта-функцией (как и в принципе какое либо значение какой либо функцией)? Если вопрос касается сравнения двух подходов, то разница проявляется в результате: по KL метрике второй метод даёт оценку ближе к априорному распределению, чем первый. При больших k первый метод будет страдать от того, что в некоторые бины будет попадать мало наблюдений, вплоть до нуля.
почему бы просто не создать массив по числу интервалов и складывать в него данные, пройдя одним циклом по
rnd_list?
Чтобы определить, в какую ячейку положить очередное значение, нужно выполнить порядка k сравнений с границами интервалов. По сути это и есть первый метод.
Прошу простить, если не ответил по существу - буду рад, если уточните вопрос.
Я имею в виду вот такой алгоритм:
находим максимальное и минимальное значения в rnd_list, назовём их xmax и xmin;
создаём массив pdf из k элементов;
для каждого значения x = rnd_list[i] вычисляем индекс j = (x - xmin) / (xmax - xmin) * k, и увеличиваем pdf[j] на 1.
Всего 2 прохода по rnd_list.
Поясню по первому вопросу...
есть ли для нас разница, считать каждое значение пиком (дельта-функцией) или ступенькой (разрывом), если суть алгоритма одна и та же?
Мы можем представить наш набор данных либо в виде PDF, что в случае дискретного распределения будет являться суммой n дельта-функций, либо в виде CDF, что представляет собой сумму ступенчатых функций.
Но чтобы получить красивый ровный график без пиков, нам нужно его сгладить, и в общем случае эта процедура выполняется с помощью свёртки. Гистограмма - это простейший случай свёртки с прямоугольным ядром, семплированной с разрешением, равным ширине ядра. Т.е. мы берём скользящее окно нужной ширины и, перемещая его вдоль оси x, вычисляем сумму (точнее, интеграл) значений, попавших внутрь окна.
При этом не важно, применяем ли мы свёртку к плотности или к функции распределения, т.к. результаты будут идентичны. Если "размазать" пик плотности распределения, то получится прямоугольный столбец, а если "размазать" ступеньку функции распределения, то получится кусочно-линейная функция. Это соответствует тому, что делает ваша функция pdf_custom.
Развивая мысль дальше, можно отметить, что прямоугольное окно - далеко не лучший сглаживающий фильтр, так как его частотная характеристика (функция sinc) довольно неровная. Для получения более "красивого" графика лучше применить какое-нибудь гладкое ядро типа гауссианы, см. Ядерная оценка плотности.
Это соответствует тому, что делает ваша функция pdf_custom
Я правильно понял Вашу мысль, что подход, основаный на получении оценки PDF из CDF, эквивалентен свертке суммы дельта-функций с неким ядром? Если так, то не могли бы Вы помочь показать это математически? Интересует, в т.ч., конкретный вид ядра свертки, соответствующий такому подходу.
Да, но я всего лишь хотел заметить, что интерполяция CDF эквивалентна расширению каждого пика (дельта-функции) PDF до прямоугольного столбика, границы которого располагаются посередине между значениями X[i-1] и X[i], X[i] и X[i+1], а площадь равна 1/n. Это нельзя считать свёрткой, так как интервалы не равны и ядро разное для каждого X[i].
Что это даёт - то же самое, что и функция pdf_custom, позволяет сделать гистограмму более гладкой. Если некоторое значение X[i] оказалось вблизи границы интервалов гистограммы, то оно в соответствующей пропорции делится по обоим столбцам.
Здесь для наглядности 5 значений и 3 интервала гистограммы.
X = sorted(rnd_list)
Сложность представленного алгоритма также составляет
Сортировка за линейное время? Нет.
Я конечно, немного придираюсь, но это не есть случайный процесс.
Дан набор N значений случайной величины X, сэмплированный из некоторого непрерывного распределения. Необходимо оценить функцию плотности распределения вероятности случайной величины по заданной выборке.
Вы правы. Дело в том, что заголовок повторяет заголовок оригинальной статьи с многоточием и так далее. Вероятно, не самый лучший выбор, и может сбить с толку, т.к. порядок наблюдений в X роли не играет. Наверное, стоит добавить в качестве примечания, как Вы считаете?
Решил ввсе же убрать эти слова из заголовка, т.к. они ни на что не влияют.
Понятно теперь, что заголовок был с отсылкой на оригинальный, не сообразил.
Просто у меня глаз зацепляется на "случайные процессы", всегда когда возможно пытаюсь их вставить в свои аналитические решения :)
А для этой задачи пользуюсь Kernel Density Estimation из scikit-learn.
Вероятно, большинство в целях визуализации используют KDE, я сам не исключение. Однако, предложенный метод оценки PDF может быть полезен в задаче поиска параметров распределения (если вид распределения известен априори) методом оптимизации, поскольку даёт сравнительно малое расхождение с "истинной" плотностью распределения. KDE этим не отличается.
Если честно, то для меня все равно загадка зачем все это надо... и что значит точность. Если тип распределения известен, почему бы не использовать тот же fit из scipy.stats или curve_fit для смесей из того же пакета. Изо всех сил пытаюсь понять чем мне это может помочь и не могу. В какой ситуации я не смогу обойтись готовыми решениями из того же numpy или stats?
Данная заметка (не претендую на громкое название "статья") является ответом на статью https://habr.com/ru/post/585232/, во вступительной части которой автор пишет:
Бывало и такое, что по некоторым причинам, использовать при этом сторонние библиотеки, решающие вопрос, было нежелательно.
Я, честно говоря, не знаю эти причины, могу только гадать. Цель этой заметки в том, чтобы показать, как, оставаясь в условиях использования только нативных python функций решить поставленную задачу иначе, нежели построением гистограммы. В качестве преимущества отмечаются меньшая сложность по сравнению с оригинальным решением, предложенным автором вышеупомянутой статьи, и более высокая точность в смысле меньшего расхождения с теорией при одинаковых условиях. Кстати говоря, характер распределения заранее не известен, так что фитинг не подходит по условию.
Получаем кривую плотности распределения вероятности… быстрее и точнее