5 марта 2013 в 18:00

Распознавание рукописных символов с использованием Python и scikit из песочницы tutorial

Привет. Наверняка многие интересуются методами машинного обучения и решения различных задач, которые обычными подходами не решаются. Недавно мне посчастливилось попасть на курс Data Mining, организованный в рамках программы GameChangers. Первым же домашним заданием было сделать сабмит на Kaggle — решить задачу Digit Recognizer.

Коротко о данных

Данные для обучения представляют собой csv-таблицу, в первой колонке которой — численные значения написанных цифр, в остальных — 784 значения насыщенности отдельно взятых пикселей (картинки черно-белые). Тестовые данные — такая же таблица, но уже без ответов.

Методы

  • Random Forest
  • kNN-метод
  • SVM с квадратичным ядром
  • SVM с кубическим ядром
  • Method Ensemble


Все вычисления производились на Python с использованием библиотеки scikit, ссылки на дистрибутивы и туториалы прилагаются ниже.

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

Random Forest

Идея алгоритма

Random Forest использует ансамбль решающих деревьев. Само по себе решающее дерево не обеспечивает достаточной точности для этой задачи, но отличается быстротой построения. Алгоритм RF обучает k решающих деревьев на параметрах, случайно выбранных для каждого дерева (в нашем случае параметры — это яркости отдельных пикселей), после чего на каждом из тестов проводится голосование среди обученного ансамбля. В основе построения этого алгоритма лежит идея о том, что если сагрегировать данные с большого количества различных слабых алгоритмов, сведя их в единый ответ, то результат, скорее всего, будет лучше, чем у одного мощного алгоритма.

Реализация

from numpy import savetxt, loadtxt #для загрузки-сохранения csv-файлов
from sklearn.ensemble import RandomForestClassifier #собственно он и делает всю работу
from sklearn.externals import joblib #для промежуточных данных

#загружаем обучающие данные и дампаем их в отдельный файл
dataset = loadtxt(open('train.csv', 'r'), dtype='f8', delimiter=',', skiprows=1)
joblib.dump(dataset, 'training_set.pkl')
dataset = joblib.load('training_set.pkl')

#точно так же загружаем тестовые
test = loadtxt(open('test.csv', 'r'), dtype='f8', delimiter=',', skiprows=1)
joblib.dump(test, 'test_set.pkl')
test = joblib.load('test_set.pkl')

# n_estimators - количество деревьев в ансамбле, n_jobs - количество ядер, на которые распараллеливается алгоритм
forest = RandomForestClassifier(n_estimators = 1000, n_jobs = 4) 
#вот тут нам нужно отделить метки от изображений
target = [x[0] for x in dataset] #метки
train = [x[1:] for x in dataset]

forest.fit(train, target) #обучаем деревья

#метод predict() возвращает многомерный массив (с которым работает numpy), в нашем случае - матрица 1x28000, которая записывается как столбец в csv-файл
savetxt('answer.csv', forest.predict(test), delimiter=',', fmt='%d')


Резюме

На четырех ядрах обучение + решение заняло час с небольшим, это наиболее медленный алгоритм из рассмотренных. Однако, это второй по точности алгоритм, давший при сабмите на Kaggle больше 96% точности.
Возникает проблема оптимального выбора числа деревьев: для данной задачи было сделано несколько прогонов с различными значениями n_estimators, 1000 дала наилучший результат.

kNN — метод

Идея алгоритма

Один из наиболее быстрых алгоритмов классификации. Вкратце: все сущности, используемые в обучении, загоняются в метрическое пространство размерности, равной количеству параметров. После чего при классификации отдельно взятого вектора рассматривается k векторов из обучающей выборки, наиболее близких к исследуемому.
Основной вопрос при использовании данного алгоритма — выбор числа k. При k = 1 алгоритм теряет устойчивость и начинается себя неадекватно вести при появлении шумов, при k, близком к числу векторов обучающей выборки, точность становится избыточной и алгоритм вырождается.

Я запустил алгоритм при разных k и в итоге остановился на изначально рекомендованном k=10

Реализация

Тут все по аналогии с предыдущим исходником, более того, используются дампы, полученные в ходе работы Random Forest.
from sklearn import neighbors
from sklearn.externals import joblib

#загружаем входные данные из файла, полученного при прогоне предыдущего алгоритма
dataset = joblib.load('training_set.pkl')
target = [x[0] for x in dataset] #все то же самое
train = [x[1:] for x in dataset]

#инициализируем объект-классификатор
clf = neighbors.KNeighborsClassifier(n_neighbors = 10, weights='uniform')
clf.fit(train, target) #обучаем

#решение
test = joblib.load('test_set.pkl')
savetxt('knn_answer.csv', clf.predict(test), delimiter=',', fmt='%d')


Резюме

kNN также показал точность выше 96% при меньшем времени работы.

SVM

SVM (Support Vector Machine) — один из наиболее универсальных методов классификации, отличающийся быстродействием и высокой надежностью. Забегая вперед, скажу, что с его использованием была получена наибольшая среди всех использованных алгоритмов точность в 97,7%

Идея алгоритма

SVM классифицирует векторы, расположенные в многомерном пространстве, схожем с тем, что используется в kNN, разделяя из гиперплоскостью, имеющую размерность n-1, где n — размерность исходного пространства.

Ядра


Метод SVM имеет один из ключевых гиперпараметров, называемый ядром. В библиотеке scikit реализована поддержка всех основных используемых ядер: линейного, радиального и полиномиального. Приведу статистику тестов на небольших выборках маркированных данных:

Точность с линейным ядром = 0.9131
Точность с радиальным ядром = 0.1265
Точность с квадратичным полиномом = 0.9635
Точность с кубическим полиномом = 0.9595

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

Релизация

from sklearn.externals import joblib
from numpy import savetxt
from sklearn import svm

#подгружаем дамп и отделяем метки от данных
dataset = joblib.load('training_set.pkl')
target = [x[0] for x in dataset]
train = [x[1:] for x in dataset]

#инициализируем классификатор. Поле kernel указывает на ядро, degree - степень используемого полинома. По дефолту, кстати, стоит 3.
clf_poly2 = svm.SVC(kernel = "poly", degree = 2)
clf_poly2.fit(train, target) #обучили


test = joblib.load('test_set.pkl') #тестовые данные
savetxt('svm_answer.csv', clf_poly2.predict(test), delimiter=',', fmt='%d')


Резюме

Работает достаточно быстро, с любым ядром обгоняет Random Forest, точность на нормализованных данных отличная.

Method Ensemble

На курсах нам дали дополнительное задание — посмотреть, как изменится точность решения при использовании нескольких алгоритмов одновременно.
Мне хотелось кластеризовать обучающую выборку по суперпикселям и посмотреть что получится, но в дедлайн я не уложился, пришлось сдавать более простой вариант — считывались ответы, данные алгоритмами RF, SVM и kNN, после чего проводилось прямое голосование. Если мнения разделялись — предпочтение отдавалось SVM, как чуть более точному. Однако, этот ансамбль дал решение на полпроцента худшее, чем то, что получалось на чистом SVM, так что улучшить решение мне не удалось.

Ссылки

Использованная библиотека
Вики с подробным описанием алгоритмов
Документация по классу, реализующему Random Forest
Описание SVM с небольшим примером
Больше информации по SVM
Все про kNN

Вот и все. В следующем посте будут рассмотрены методы оптимизации параметров самих алгоритмов.
@LexTalionis
карма
10,0
рейтинг 0,0
Похожие публикации
Самое читаемое Разработка

Комментарии (7)

  • 0
    Я так понимаю, в одном инстансе хранилась ровно одна цифра?

    Интересно, почему SVM с радиальным ядром дал такой низкий результат. Я так понимаю, при для мультикатегориальной классификации scikit-овская реализация использует one-vs-one стратегию?
    • 0
      Все верно. Про радиальное ядро ничего не могу сказать. Есть, кстати, еще ядро sigmoid, там та же ситуация.
    • 0
      > Я так понимаю, при для мультикатегориальной классификации scikit-овская реализация использует one-vs-one стратегию?
      Нет, на сколько я помню там one-vs-all по умолчанию. Хотя one-vs-one тоже можно прикрутить.

      > Интересно, почему SVM с радиальным ядром дал такой низкий результат.
      Вот это действительно странно. Радиальное ядро может дать качество ниже чем линейное, но разница тут слишком велика.
  • 0
    И на какое место оценился ваш сабмит на кегле? Я, помнится, когда эту задачку решал, то сделал тупо RF с n_estimators = 30 и сходу получил 222 место.

    Сильно удивился от того, что если предварительно сделать нормализацию изображения (отмасштабировать и отцентрировать цифры), то точность при этом снижается.
    • 0
      В окрестности 120. С первого сабмита было ~240. Те данные взяты с MNIST, если мне память не изменяет, они там и так все отцентрировали и обрезали как надо.

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