Кодирование и объяснение принципов работы оптического распознавания символов с помощью популярного алгоритма K ближайших соседей

Оптическое распознавание символов (OCR) присутствует в нашей повседневной жизни чаще, чем мы себе это представляем. Когда мы используем Google Translate для перевода текста с изображений, мы используем OCR. Когда мы отправляем письмо и оно доходит до места назначения, OCR работает на нас. Когда человек с ослабленным зрением сканирует документ, а машина читает его за него, опять же, OCR берет на себя ответственность за это. Это всего лишь несколько случаев присутствия OCR в нашей рутине, но на сегодняшний день их бесконечно больше, и их количество будет только увеличиваться в ближайшем будущем.

Эта статья призвана проиллюстрировать, что такое оптическое распознавание символов, и представить пошаговое приложение для ознакомления с ним. Я буду использовать набор данных MNIST для обучения модели машинного обучения, которая сможет распознавать рукописные цифры на картинках. После тонкой настройки алгоритма я оценю его точность.

Что такое оптическое распознавание символов?

Оптическое распознавание символов (OCR), также известное как распознавание текста, представляет собой технологию, способную преобразовывать печатные или рукописные символы в машиночитаемый текст. OCR использует как аппаратные, так и программные средства. В то время как аппаратное обеспечение часто состоит из оптических сканеров или камер, программное обеспечение, которому посвящена эта статья, состоит из алгоритмов машинного обучения, таких как классификатор KNN, классификатор SVM или нейронные сети.

Текущие приложения OCR безграничны. Просто процитирую некоторые из них:

  • Генерация электронных версий (мягких версий) старых книг или документов (см. Google Книги)
  • Сканировать дорожные знаки для автономного вождения
  • Создание инструментов, позволяющих читать незрячим и слабовидящим людям (см. AFB)
  • Преобразование рукописного текста в реальном времени
  • Автоматическое извлечение информации из паспортов или страховых документов

Выбор модели

Оптическое распознавание символов — это проблема классификации, что означает, что это проблема машинного обучения, где выходные данные являются категориальными (т. е. принадлежат конечному набору значений). Выходные классы — это, конечно же, разные символы.
В этом приложении мы позаботимся о распознавании рукописных цифр. Количество выходных классов равно 10 и состоит из целых чисел от 0 до 9:

Существует много готовых алгоритмов классификации, поэтому нам нужно выбрать тот, который хорошо подходит для этой цели. Основное ограничение при выборе алгоритма заключается в том, что он должен подходить для мультиклассовой классификации. На самом деле, поскольку классов больше 2, это нельзя считать проблемой бинарной классификации.

Некоторые алгоритмы изначально способны обрабатывать задачи многоклассовой классификации (например, стохастический градиентный спуск, случайный лес или наивные байесовские классификаторы). Другие алгоритмы (такие как машина опорных векторов или классификаторы логистической регрессии) изначально являются бинарными классификаторами. Даже если существуют методы выполнения мультиклассовой классификации с помощью бинарных классификаторов (стратегии один против всех или один против одного), в рамках этой статьи я будет придерживаться собственного мультиклассового классификатора.

K-классификатор ближайших соседей

Поскольку общепринятой теории, согласно которой алгоритм обучения является лучшим для каждого типа задач, не существует, мой выбор падает на классификатор k-ближайших соседей(KNN)главным образом из-за своей простоты: у него мало гиперпараметров для настройки (количество соседей для рассмотрения k, функция расстояния, которая обычно соответствует евклидову или манхэттенскому расстоянию), и, кроме того, он непараметрический (это означает, что он не требует предположений о распределении данных). Недостатком KNN является плохое масштабирование с большими наборами данных из-за его внутренней природы: он должен сканировать весь набор данных всякий раз, когда необходимо классифицировать новый пример. По этой причине имеет смысл изучить дополнительные алгоритмы обучения, такие как деревья решений или случайный лес.

Идея KNN заключается в том, что пример i имеет высокую вероятность принадлежности к определенному классу, назовем его m, если m также самый популярный класс из k ближайших примеров в пространстве признаков. Более формально алгоритм обучения KNN следует следующим шагам:

  1. Учитывая один неизвестный пример, измерьте его расстояние от всех помеченных примеров в наборе данных.
  2. Возьмите k помеченных примеров, которые находятся ближе всего к непомеченному.
  3. На основе классов k ближайших соседей спрогнозируйте класс непомеченного примера.
  4. Повторите шаги 1–3 для всех немаркированных примеров.

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

Чтобы применить KNN к проблеме классификации, нам нужно указать:

  • Метрика расстояния p. Наиболее часто используется евклидово расстояние, которое является частным случаем расстояния Минковского, где оно установлено p=2. Для двух точек X и Y одинакового размера расстояние Минковского D(X,Y) вычисляется следующим образом:

  • Количество соседей k, которые следует учитывать. Это, возможно, самый важный гиперпараметр KNN, потому что:
    — значение, слишком малое для k, может привести к переобучению
    — слишком большое значение для k может привести к недостаточной подгонке
    Настоятельно рекомендуется оптимизировать k с помощью набора перекрестной проверки.
  • Дополнительная функция взвешивания. Его часто игнорируют, но в некоторых приложениях лучшие результаты достигаются путем установки весовой функции, которая вознаграждает классы ближайших ближайших соседей.
  • Метод агрегации. Обычно выбирается простое большинство голосов.

Здесь я предлагаю краткий снимок алгоритма KNN, более подробную информацию о его функционировании смотрите в этой статье.

Набор данных MNIST

Для обучения нашей модели я буду использовать набор данных MNIST, представляющий собой большую базу данных рукописных цифр. Набор данных содержит 70 000 небольших изображений (28 x 28 пикселей), каждое из которых помечено.

Во-первых, мы должны импортировать набор данных.

Чтобы получить представление о наборе данных, я определяю функцию для печати одного из 70 000 изображений:

Вывод будет:

Набор данных состоит из 70 000 примеров, каждый из которых имеет 784 функции (28 x 28 пикселей). Каждая функция представляет интенсивность данного пикселя на цветовой карте в оттенках серого со значениями функции в диапазоне от 0 до 255.
Значение 0 соответствует белому пикселю, тогда как значение 255 совпадает с черным пикселем.

Обучение модели

Мы разделили набор данных на обучающий набор и тестовый набор, как это принято. Я решил назначить 25% примеров тестовому набору. Тестовый набор будет отложен и никогда не будет трогаться до конца. Его единственная цель состоит в том, чтобы обеспечить обобщенную оценку модели. Настройка гиперпараметров будет выполняться с набором перекрестной проверки.

Давайте сначала попробуем подобрать классификатор с параметрами по умолчанию.

Это должно дать оценку точности около 96,8%, что не так уж плохо, учитывая небольшие усилия, затраченные на создание модели.

Настройка гиперпараметров

Для достижения лучшего результата я попробую настроить гиперпараметры модели методом Grid Search. Поиск по сетке — это исчерпывающий метод поиска. Вот почему я уменьшаю количество кратностей в Cross-Validation, то есть из вычислительных соображений. Я исследую пространство гиперпараметров, рассматривая следующие комбинации:

Другими словами, поиск по сетке исследует комбинацию трех разных значений ближайших соседей k и двух способов агрегирования классов соседей (с одинаковыми весами или взвешенными по расстоянию). Имея 6 возможных комбинаций гиперпараметров, я установил 3 как количество перекрестных проверок, всего 18 шагов обучения.

Еще один возможный гиперпараметр, который стоит проверить, — это метрика расстояния.

После поиска в сетке и процесса перекрестной проверки мы можем получить доступ к наилучшему оценщику, вызвав метод best_estimator_ для подходящего объекта поиска в сетке.

В моем случае лучшей оценкой является та, у которой k=4 и которая использует взвешенное по расстоянию агрегирование.

Теперь я буду оценивать настроенную модель на тестовом наборе. Шаги здесь следующие:

  1. Используйте обученную модель, чтобы предсказать метку каждого примера в тестовом наборе.
  2. Сравните предсказанные метки с фактическими метками
  3. Вычислить показатель точности

Scikit-learn позволяет выполнить все это с помощью одной строки кода:

Точность модели увеличилась до 97,3 % благодаря простому поиску по сетке для поиска лучших гиперпараметров.

Следующие шаги

Для дальнейшего улучшения модели OCR мы можем попробовать различные подходы, такие как запуск других алгоритмов обучения, расширение пространства поиска гиперпараметров и увеличение размера обучающего набора путем синтетического изменения исходных данных (добавление шума, сдвиг или поворот изображений). Далее последует статья, в которой новая модель обучается на синтетически сгенерированных образцах.

Спасибо за прочтение, надеюсь, вам понравилось!