Метод наименьших квадратов и распределение Гаусса

Применение МНК для подбора параметров гауссиан выборки

Два колокола

Черным — частоты данных в выборке + два «колокола», использованных для ее генерации (пунктиром)
Красным — оба «колокола», подобранные для выборки при помощи нелинейного программирования

Функция нормального распределения (Гаусса) f(x)=\frac{1}{\sigma\sqrt{2\pi}}\exp(-\frac{(x-\mu)^2}{2\sigma^2}) называется гауссианой и представляет из себя ни что иное как «кривую колокола», верхушка которого будет располагаться в точке математического ожидания (медианы), а отклонение (разброс) определяет его ширину. Ее же мы увидим, если построим гистограмму по нормально-распределенной выборке: близкие к медиане величины встречаются чаще, чем величины с бОльшим отклонением. Когда колокол в гистограмме только один, получить его параметры очень легко: математическое ожидание и стандартное отклонение всей выборки и являются параметрами колокола.

Однако, предположим, что у выборки есть несколько источников случайных величин, каждый со своей конфигурацией колокола. Под катом рассмотрим применение метода наименьших квадратов для определения параметров всех колоколов при помощи языка программирования Python и библиотек NumPy, SciPy, matplotlib.
Читать далее

Рубрика: Алгоритмы | Метки: , , , , | 2 комментария

Поиск как в админке Django

Снова привет! Осваивался с class-based views и заодно изобретал велосипед делал поиск «как в джанго-админке», то есть такой, чтобы конфигурировался максимально аналогично. Плюс, в частном случае нужно было еще ограничить поиск только «активными» документами. Вот такой маленький сниппет из этого получился: Читать далее

Рубрика: На заметку | Метки: , | Добавить комментарий

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

Проблема

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

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

Рубрика: Алгоритмы | Метки: , , , , , , , | Добавить комментарий

Наивное деление слова по слогам

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

Рубрика: Алгоритмы | Метки: , , | 5 комментариев

Django: экспорт БД через view

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

Скрипты и статику-то мы перенесем. Но что делать с БД? Читать далее

Рубрика: Решение проблем | Метки: , , , | Добавить комментарий

IOError: decoder jpeg not available

Или «Как установить в Ubuntu PIL так, чтобы он мог открыть jpeg?»

— Как установить PIL?
— Конечно же pip install PIL
— Все правильно сделал! Но почему PIL не можеть декодировать JPEG? Читать далее

Рубрика: Разное | Добавить комментарий

Python: Быстрое удаление из deque по индексу

Объект deque в python — это коллекция, представляющая собой нечто общее между стеком и очередью. deque (double-ended queue — двусторонняя очередь) позволяют потокобезопасно добавлять и «отщипывать» элементы только с начала и конца коллекции, зато за константное время O(1). Начиная с python 2.5 появилась возможность удалять из коллекции по значению. Я предлагаю свою реализацию удаления — по индексу, которая основана на возможности «вращать» deque и быстрее чем стандартное удаление из deque в 1000 элементов на 60%. Чем длиннее deque тем больше выигрыш производительности. Читать далее

Рубрика: Алгоритмы, На заметку | Метки: , , | 1 комментарий

Python: Получение класса/функции по строке имени

В Django есть замечательная, по моему мнению, функциональность, позволяющая указывать view для url dispatcher‘а не импортируя ее явно, а в виде строки вроде 'mysite.views.archive', где mysite — это модуль application, views — это его подмодуль с view-объектами (функции или CBV — class based view), а archive— это собственно сам объект view. При этом url dispatcher Django сам импортирует все необходимые модули и получает ссылку на указанный в строке объект. Нужна такая-же функциональность? Как вам такой вариант:

>>> load_object('os.path.isfile')
<function isfile at 0x01361230>

Код и объяснение под катом Читать далее

Рубрика: На заметку | Метки: , | Добавить комментарий

Расстояние Левенштейна — определяем «похожесть» строк

Интересный и очень полезный алгоритм «дистанция Левенштейна» (Levenshtein distance), так же известная как редакционное расстояние или дистанция редактирования. Эта «дистанция» — это минимальное количество правок одной строки (под правками подразумеваются три возможные операции: стирание символа, замена символа и вставка символа), чтобы превратить ее во вторую.

Несколько примеров намного лучше нудных формулировок:
levenshtein('ABC','ABC') = 0
levenshtein('ABC','ABCDEF') = 3
levenshtein('ABC','BCDE') = 3
levenshtein('BCDE','ABCDEF') = 2

Расстояние Левенштейна позволяет субъективно оценить, насколько строки непохожи друг на друга. В этой статье мы рассмотрим  сам алгоритм расчета дистанции Левенштейна в теории и на простом примере по шагам. В конце статьи есть код на Python реализующий данный алгоритм, а также несколько идей по его оптимизации. Читать далее

Рубрика: Алгоритмы | Метки: , , | 18 комментариев

С++: Удаляем из std::vector по вектору индексов

Для того, чтобы удалить элементы из вектора, индексы которых находятся в другом векторе, может пригодиться этот небольшой хэлпер Читать далее

Рубрика: На заметку | Метки: , , | 1 комментарий