<jupyter_start><jupyter_text>В этом задании будет использоваться датасет digits из sklearn.datasets. Оставьте последние 25% объектов для контроля качества, разделив X и y на X_train, y_train и X_test, y_test.Целью задания будет реализовать самый простой метрический классификатор — метод ближайшего соседа, а также сравнить качество работы реализованного вами 1NN с RandomForestClassifier из sklearn на 1000 деревьях. Задание 1Реализуйте самостоятельно метод одного ближайшего соседа с евклидовой метрикой для задачи классификации. Можно не извлекать корень из суммы квадратов отклонений, т.к. корень — монотонное преобразование и не влияет на результат работы алгоритма.Никакой дополнительной работы с признаками в этом задании делать не нужно — мы еще успеем этим заняться в других курсах. Ваша реализация может быть устроена следующим образом: можно для каждого классифицируемого объекта составлять список пар (расстояние до точки из обучающей выборки, метка класса в этой точке), затем сортировать этот список (по умолчанию сортировка будет сначала по первому элементу пары, затем по второму), а затем брать первый элемент (с наименьшим расстоянием).Сортировка массива длиной N требует порядка N log N сравнений (строже говоря, она работает за O(N log N)). Подумайте, как можно легко улучшить получившееся время работы. Кроме простого способа найти ближайший объект всего за N сравнений, можно попробовать придумать, как разбить пространство признаков на части и сделать структуру данных, которая позволит быстро искать соседей каждой точки. За выбор метода поиска ближайших соседей в KNeighborsClassifier из sklearn отвечает параметр algorithm — если у вас уже есть некоторый бэкграунд в алгоритмах и структурах данных, вам может быть интересно познакомиться со структурами данных ball tree и kd tree.Доля ошибок, допускаемых 1NN на тестовой выборке, — ответ в задании 1.<jupyter_code>from sklearn import datasets, model_selection, ensemble, metrics
data = datasets.load_digits()
X, y = data.data, data.target
X_train, X_test, Y_train, Y_test = model_selection.train_test_split(X, y, test_size = 0.25, shuffle = False)
def distance(x1, x2):
    return (sum((x1 - x2)**2)**0.5)
res = []
for x_test, y_test in zip(X_test, Y_test):
    arr = [[distance(x_test, x_train), y_train] for x_train, y_train in zip(X_train, Y_train)]
    arr.sort()
    res.append(arr[0][1])
result = sum(Y_test != res)/len(X_test)<jupyter_output><empty_output><jupyter_text>Задание 2Теперь обучите на обучающей выборке RandomForestClassifier(n_estimators=1000) из sklearn. Сделайте прогнозы на тестовой выборке и оцените долю ошибок классификации на ней. Эта доля — ответ в задании 2. Обратите внимание на то, как соотносится качество работы случайного леса с качеством работы, пожалуй, одного из самых простых методов — 1NN. Такое различие — особенность данного датасета, но нужно всегда помнить, что такая ситуация тоже может иметь место, и не забывать про простые методы.<jupyter_code>rfc = ensemble.RandomForestClassifier(n_estimators=1000)
rfc.fit(X_train, Y_train)
acc = metrics.accuracy_score(rfc.predict(X_test), Y_test)
print(1 - acc)<jupyter_output>0.06000000000000005
{'fraction_non_alphanumeric': 0.05796642382008236, 'fraction_numerical': 0.016471333544504276, 'mean_word_length': 5.955947136563877, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '468914', 'license': 'CNRI-Python-GPL-Compatible', 'n_tokens_mistral': 1273, 'n_tokens_neox': 1429, 'n_words': 388, 'path': '1NN_vs_RF.ipynb', 'repo_name': 'djoye21school/python', 'size': '3157'}