В этом задании будет использоваться датасет digits из sklearn.datasets. Оставьте последние 25% объектов для контроля качества, разделив X и y на X_train, y_train и X_test, y_test.
Целью задания будет реализовать самый простой метрический классификатор — метод ближайшего соседа, а также сравнить качество работы реализованного вами 1NN с RandomForestClassifier из sklearn на 1000 деревьях.
In [1]:
from sklearn import datasets
digits = datasets.load_digits()
X = digits.data
y = digits.target
In [2]:
from sklearn.cross_validation import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, train_size=0.75, random_state=0)
In [3]:
def write_answer(data, file_name):
with open(file_name, 'w') as fout:
fout.write(str(data))
Реализуйте самостоятельно метод одного ближайшего соседа с евклидовой метрикой для задачи классификации. Можно не извлекать корень из суммы квадратов отклонений, т.к. корень — монотонное преобразование и не влияет на результат работы алгоритма.
Никакой дополнительной работы с признаками в этом задании делать не нужно — мы еще успеем этим заняться в других курсах. Ваша реализация может быть устроена следующим образом: можно для каждого классифицируемого объекта составлять список пар (расстояние до точки из обучающей выборки, метка класса в этой точке), затем сортировать этот список (по умолчанию сортировка будет сначала по первому элементу пары, затем по второму), а затем брать первый элемент (с наименьшим расстоянием).
Сортировка массива длиной N требует порядка N log N сравнений (строже говоря, она работает за O(N log N)). Подумайте, как можно легко улучшить получившееся время работы. Кроме простого способа найти ближайший объект всего за N сравнений, можно попробовать придумать, как разбить пространство признаков на части и сделать структуру данных, которая позволит быстро искать соседей каждой точки. За выбор метода поиска ближайших соседей в KNeighborsClassifier из sklearn отвечает параметр algorithm — если у вас уже есть некоторый бэкграунд в алгоритмах и структурах данных, вам может быть интересно познакомиться со структурами данных ball tree и kd tree.
Доля ошибок, допускаемых 1NN на тестовой выборке, — ответ в задании 1.
In [4]:
def euclidean_metric(a, b):
return sum((a - b)**2)
In [5]:
lst = list()
for i in range(X.shape[0]):
tmp = list()
for j in range(y.shape[0]):
if i is not j:
tmp.append((euclidean_metric(X[i, :], X[j, :]), y[j]))
lst.append(y[i] == min(tmp, key = lambda t: t[0])[1])
trues, falses = 0.0, 0.0
for el in lst:
if el == True:
trues += 1
elif el == False:
falses +=1
print('precision is ', (trues / (trues + falses)) * 100.0, '%')
write_answer(data = (falses / (falses + trues)), file_name = 'ans_1.txt')
Теперь обучите на обучающей выборке RandomForestClassifier(n_estimators=1000) из sklearn. Сделайте прогнозы на тестовой выборке и оцените долю ошибок классификации на ней. Эта доля — ответ в задании 2. Обратите внимание на то, как соотносится качество работы случайного леса с качеством работы, пожалуй, одного из самых простых методов — 1NN. Такое различие — особенность данного датасета, но нужно всегда помнить, что такая ситуация тоже может иметь место, и не забывать про простые методы.
In [6]:
from sklearn import ensemble
clf = ensemble.RandomForestClassifier(n_estimators = 1000).fit(X_train, y_train)
lst = [ y == a for y, a in zip(y_test, clf.predict(X_test)) ]
trues, falses = 0.0, 0.0
for el in lst:
if el == True:
trues += 1
elif el == False:
falses += 1
print('precision is ', (trues / (trues + falses)) * 100.0, '%')
write_answer(data = (falses / (falses + trues)), file_name = 'ans_2.txt')