Суть метода заключается в том, что критерием качества рассматриваемого решения является сумма квадратов ошибок, которую стремятся свести к минимуму. Для применения этого математического метода требуется провести как можно большее число измерений неизвестной случайной величины (чем больше — тем выше точность решения) и некоторое множество предполагаемых решений, из которых требуется выбрать наилучшее. Если множество решений параметризировано, то нужно найти оптимальное значение параметров.
Почему сводятся к минимуму квадраты ошибок, а не сами ошибки? Дело в том, что в большинстве случаев ошибки бывают в обе стороны: оценка может быть больше измерения или меньше его. Если складывать ошибки с разными знаками, то они будут взаимно компенсироваться, и в итоге сумма даст нам неверное представление о качестве оценки. Часто для того, чтобы итоговая оценка имела ту же размерность, что и измеряемые величины, из суммы квадратов ошибок извлекают квадратный корень.
МНК используется в математике, в частности — в теории вероятностей и математической статистике. Наибольшее применение этот метод имеет в задачах фильтрации, когда необходимо отделить полезный сигнал от наложенного на него шума.
Его применяют и в математическом анализе для приближённого представления заданной функции более простыми функциями. Ещё одна из областей применения МНК — решение систем уравнений с количеством неизвестных меньшим, чем число уравнений.
Я придумал ещё несколько весьма неожиданных областей применения МНК, о которых хотел бы рассказать в этой статье.
МНК и опечатки
Бичом автоматических переводчиков и поисковых систем являются опечатки и орфографические ошибки. Действительно, если слово отличается всего на 1 букву, программа расценивает его уже как другое слово и переводит/ищет его неправильно или не переводит/не находит его вообще.
У меня возникла похожая проблема: имелось две базы данных с адресами московских домов, и надо было их объединить в одну. Но адреса были записаны в разном стиле. В одной базе был стандарт КЛАДР (всероссийский классификатор адресов), например: «БАБУШКИНА ЛЕТЧИКА УЛ., Д10К3». А в другой базе был почтовый стиль, например: «Ул. Летчика Бабушкина, дом 10 корп.3». Вроде бы ошибок нет в обоих случаях, а автоматизировать процесс невероятно сложно (в каждой базе по 40 тысяч записей!). Хотя и опечаток там тоже хватало… Как дать компьютеру понять, что 2 вышеприведённых адреса принадлежат одному и тому же дому? Тут-то мне и пригодился МНК.
Что я сделал? Найдя очередную букву в первом адресе, я искал ту же букву во втором адресе. Если они обе находились на одном и том же месте, то я полагал ошибку для этой буквы равной 0. Если они располагались на соседних позициях, то ошибка была равна 1. Если имелся сдвиг на 2 позиции, ошибка равнялась 2
Разумеется, номера домов и корпусов обрабатывались отдельно. Не знаю, изобрёл ли я очередной «велосипед», или это впрямь было новаторством, но задача была решена быстро и качественно. Интересно, применяется ли этот метод в поисковых системах? Возможно, применяется, поскольку каждый уважающий себя поисковик при встрече незнакомого слова предлагает замену из знакомых слов («возможно, вы имели в виду…»). Впрочем, они могут делать этот анализ как-то по-другому.
МНК и поиск по картинкам, лицам и картам
Этот метод можно применить и в поиске по картинкам, чертежам, картам и даже по лицам людей.
Сейчас все поисковики, вместо поиска по картинкам, по сути, используют поиск по подписям к картинкам. Это, несомненно, полезный и удобный сервис, но я предлагаю дополнить его настоящим поиском по картинкам.
Вводится картинка-образец и для всех изображений составляется рейтинг по сумме квадратов отклонений характерных точек. Определение этих самых характерных точек есть сама по себе нетривиальная задача. Однако она вполне решаема: например, для лиц это уголки глаз, губ, кончик носа, ноздри, края и центры бровей, зрачки
Сопоставив эти параметры, можно найти лицо, наиболее похожее на образец. Я уже видел сайты, где такой сервис работает, и вы можете найти знаменитость, наиболее похожую на предложенную вами фотографию, и даже составить анимацию, превращающую вас в знаменитость и обратно. Наверняка этот же метод работает в базах МВД, содержащих фотороботы преступников.
Да и по отпечаткам пальцев можно тем же методом делать поиск. Поиск по картам ориентируется на естественные неровности географических объектов — изгибы рек, горных хребтов, очертания берегов, лесов и полей.
Вот такой замечательный и универсальный метод МНК. Я уверен, что вы, дорогие читатели, сможете и сами найти множество необычных и неожиданных областей применения этого метода.
Классно написано!
Редко кто может человеческим языком описать суть математических методов.
На очереди ( надеюсь) методы, "дихтомии", "золотого сечения" , "градиент" и метод "наискорейшего спуска"?
Оценка статьи: 5
0 Ответить
Статья понравилась. Наукову думку забывать не стоит. Да, историческая справка:
МНК впервые был предложен князем математики Карлом Гауссом (1794-95) и Адриен Мари Лежандром (1805-06) для обработки астрономических и геодезических данных. Строгое обоснование и установление границ содержательной применимости метода даны нашими А. А. Марковым и А. Н. Колмогоровым.
Но вот конкретно для решения задачи о слиянии двух списков (баз данных адресов) я бы предложил иной алгоритм, попроще, можно даже вообще без МНК обойтись.
Последовательность шагов такая:
1) создать формат внутреннего представления (ВП) записи, который бы позволял однозначно осуществлять сортировку по заданному предикату (улица - дом - квартира)
2) конвертировать в этот формат каждую запись обоих списков (convert); на выходе получим два списка в едином формате
3) произвести слияние списков; на выходе получим один список в формате ВП
4) произвести сортировку этого списка = (sort with predicate)
5) удалить повторяющиеся записи = (std::unique); это просто, т.к. повторяющиеся записи в отсортированном списке идут друг за другом
6) провести верификацию полученного списка (устранить опечатки, проверить диапазоны номеров)
7) удалить повторяющиеся записи, возникшие после устранения опечаток в п.6 = (unique);
Пояснения к пунктам.
2) для конверсии достаточно написать вручную или сгенерировать с использованием к.-л. автоматического средства (Lex, Flex etc) лексический анализатор (ЛА), он же сканер, он же токенайзер, т.е. по-сути ДКА (детерминированный конечный автомат). Для имеющих базовые познания в области формальных языков и грамматик – плёвое дело, тривиальный таск. При этом скорость работы такого ЛА – линейная: О(N), где N – длина входной цепочки. Как только лексема распознана (например – название улицы), её значение помещается в соответствующее поле генерируемой записи (в формате ВП).
6) Вот для верификации – проверке на опечатки, можно замечательно использовать МНК, как вы и предложили. В качестве референсного списка следует взять список всех улиц города, и в качестве эвристик, снижающих число кандидатов на сравнение, использовать факт отсортированности референсного и рабочего списков, а так же то, что опечатки можно обнаружить только в названиях улиц.
Оценка сложности (производительность) алгоритма, по пунктам:
1) 0; 2) O(C*N); 3) O(N) | O(C) – зависит от природы контейнера; 4) O(N*LOG(N)); 5) O(N); 6) O(N) ?; 7) O(N).
Т.о. нигде не хуже N*LOG(N), а у вас, кажется, полином третьёй степени может вылезти, если производить сравнение обоих списков и буковок по принципу каждый с каждым, без каких-либо ограничивающих эвристик. Впрочем, это зависит от деталей реализации, которые вы, по понятным причинам, опустили, - статья то о МНК. С другой стороны, современные числодробилки всё стерпят, лишь бы до экспоненциальной сложности (при больших N) не дошло. Машинное время дешевеет, труд инженера дорожает, нередко менее эффективный, но быстрее реализуемый (в смысле времени написания кода) алгоритм экономически выгоднее. Любопытно также, что теоретическая оценка алгоритмов – это одно, а третьи факторы (например, производительность подсистемы памяти, подкачки страниц, кешей и т.д.) и величина константных членов формул, в реальной ситуации - совсем другое. Как говорится, "Computer scientists deal with algorithms that you may call practical in theory but unpractical in practice." (c) Timothy Gowers.
0 Ответить
Евгений Сударкин, стандарт КЛАДР вполне подходит для ВП, т.к. специально для этих целей и разрабатывался. Поэтому остаётся конвертация почтового стандарта в КЛАДР. Но ошибки, которые либо уже есть, либо неизбежно появятся при конвертации, всё равно придётся исправлять, так почему бы не сделать этого сразу, минуя промежуточную процедуру преобразования почтового адреса в КЛАДР?
0 Ответить
Виктор Губерниев, не вопрос. Просто захотелось порассуждать вслух по поводу. Дъябол, как всегда, в деталях. Когда нет всей информации – приходится домысливать.
Идея применить МНК для подбора «ближайшей» строки понравилась. Хорошая, годная идея.
0 Ответить
Виктор Губерниев, цитата:
Так, поисковая система Вики на запрос «метод наименьших квадратов» выдаёт – «did you mean: метро наименьших казаков». 
. Это при том, что правильная статья у них имеется. Да, есть ещё над чем работать.
Интересно, применяется ли этот метод в поисковых системах? Возможно, применяется, поскольку каждый уважающий себя поисковик при встрече незнакомого слова предлагает замену из знакомых слов («возможно вы имели в виду…»).
Конечно применяется!
0 Ответить
Евгений Сударкин, представил себе подземелье с гномами в папахах...
0 Ответить
интересно
очепятку исправьте:
"Если они обе находились в одном на том же месте..."
0 Ответить
Людвиг Бетховен, спасибо, поправили.
Виктор Губерниев, существует сайт с "настоящим поиском по картинкам": http://www.tineye.com, есть его плагин для FF. Но ищет плохо, проиндексировано им ограниченное число сайтов.
0 Ответить
Виктор Губерниев,
:
Спасибо за статью!
Совершенно неожиданный подход - то, как Вы придумали использовать МНК - очень классно и просто красиво!
Удивило малое количество комментов - все изучали статистику, все её используют, без неё никуда, но при этом молчат...
Странно. Ведь все учили, все сдавали...
Напоминаю Стандарт Минвуза РФ - тот,где статистики по минимуму,для экономистов и финансистов,так сказать,гуманитариев - на естественно-научных факультетах стандарт пошире и поболе
Перечень тем Стандарта для Социальных и Экономических специальностей:
Линейная модель множественной регрессии; метод наименьших квадратов (мнк); свойства оценок мнк; показатели качества регрессии; линейные регрессионные модели с гетероскедастичными и автокоррелированными остатками; обобщенный метод наименьших квадратов (омнк); регрессионные модели с переменной структурой (фиктивные переменные); нелинейные модели регрессии и их линеаризация; характеристики временных рядов; модели стационарных и нестационарных временных рядов, их идентификация; система линейных одновременных уравнений; косвенный, двухшаговый и трехшаговый метод наименьших квадратов.
Конец цитаты.
0 Ответить
Виктор Губерниев,
Хорошая статья.
Ассоциация разговора психотерапевта с дамой, приведшей на обследование своего сыночка:
- У Вашего сыночка, дама, - Эдипов комплекс!
- Эдипов комплекс, Эдипов комплекс! Фигня всё это! Главное - чтоб он больше мамочку любил!
Оценка статьи: 5
0 Ответить
Виктор Губерниев, в памяти всплывает дисперсия и среднеквадратичное отклонение. Только, как я помню, там большую роль играет характер отклонений - или это иглы, или систематические отклонения. В каких-то случаях нужно брать среднеквадратичное, в другом - среднее арифметическое отклонений по модулю (чтоб ушел знак).
.
Если честно, в примерах использование именно среднеквадратичного отклонения я не понял
Оценка статьи: 5
0 Ответить
Ю. Лях, всё просто:
каждая буква в слове-образце занимает определённую позицию P. Если в тестовом слове есть та же буква на позиции P1, то считаем величину ошибки: E = P-P1, если таких букв несколько, берем букву с минимальной ошибкой. Если в тестовом слове данной буквы нет, то полагаем ошибку E = n + 1, где n - длина слова-образца.
Для всего тестового слова суммируем квадраты ошибок и получаем квадратичную ошибку для тестового слова. Сравниваем её с квадратичными ошибками для других тестовых слов. Выбираем то тестовое слово, для которого квадратичная ошибка минимальна.
0 Ответить
Отличная идея. Велосипед не изобретен. Но применение для поиска в текстах похожих слов мне лично пригодится.
0 Ответить
Молодец!!
Оценка статьи: 5
0 Ответить
Виктор Губерниев, весьма интересно!
Оценка статьи: 5
0 Ответить
Дело в том, что в большинстве случаев ошибки бывают в обе стороны: оценка может быть больше измерения или меньше его. Если складывать ошибки с разными знаками, то они будут взаимно компенсироваться
Кроме того, этот метод замечательно сглаживает влияние грубых ошибок на уравненный результат.
зы
статья безусловно хороша.
Оценка статьи: 5
0 Ответить