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

Привет. Наверняка многие интересуются методами машинного обучения и решения различных задач, которые обычными подходами не решаются. Недавно мне посчастливилось попасть на курс 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(target, 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

Вот и все. В следующем посте будут рассмотрены методы оптимизации параметров самих алгоритмов.