Домашнее задание №1
Deadline: 27.02.2018 23:59:59
ФИВТ, АПТ, Курс по машинному обучению, Весна 2018
Alexey Romanenko, alexromsput@gmail.com
Задача 1 Покажите, что ROC-AUC в случае, когда классификатор даёт случайные ответы $a(x) = 1$ с вероятностью $p$ и $a(x) = 0$ с вероятностью $1 − p$, будет в среднем равен 0.5 независимо от p и доли класса 1 в обучающей выборке.
<Решение:> Заметим, в среднем $TPR = \frac{TP}{TP+FN} = \frac{pa}{a} = p$, а $FPR = \frac{FP}{TN+FP} = \frac{p(1-a)}{1-a} = p$, то есть в среднем $TPR = FPS$, что и требовалось.
Задача 2 Покажите, что с ростом размерности пространства признаков при равномерном распределении точек в кубе $[0; 1]^𝑑$ вероятность попасть в куб $[0; 0, 99]^𝑑$ стремится к нулю. Это одна из иллюстраций проклятия размерностей (dimension curse). Попробуйте придумать или найти еще какую-нибудь иллюстрацию к этому явлению и кратко изложить.
<Решение:> Из курса теорвера очеивидно следует, что вероятность попасть в такой куб равна отношению объема куба $[0;0.99]^d$ к объему куба $[0;1]^d$ (геометрическая вероятность). Из курса матанализа 3-го семестра следует, что эти объемы равны соответственно $0.99^d$ и $1$ (кратные интегралы). Из курса матанализа 1-го семестра следуте, что $\lim_{d \rightarrow \infty} 0.99^d = 0$ (пределы числовых последовательностей).
Другой пример возникает в теории Рамсея: неизвестно значение $R(5, 5)$ и почти всех $R(m, n)$.
Используя данные из задачи классификации доходов индивидуума http://archive.ics.uci.edu/ml/machine-learning-databases/adult, постройте зависимость величин bias, variance и noise для следующих пар "модель|параметр". Предобработка данных (преобразование признаков, разметка классов) определяется вами.
По каждому построенному графику (для каждого параметра должен быть отдельный график) объясните полученную картину. Совпадает ли она с теоретическими ожиданиями (см. семинар 2)?
In [1]:
import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier
%matplotlib inline
In [2]:
iterations_count = 100
test_sample_size_relative_proportion = 0.5 # От длины обучающей выборки
test_sample_size_absolute_proportion = test_sample_size_relative_proportion / (test_sample_size_relative_proportion + 1)
In [3]:
# Исследуемая сетка параметров
grid = {
"neightbours_count": np.arange(1, 21),
"minkowski_metric_degree": np.arange(1, 11, 0.5),
"train_sample_size_relative_proportion": np.arange(0.5, 2.075, 0.075) # train : tets меняется от 0.5 : 1 до 2 : 1
}
In [4]:
import pandas as pd
def find_sample_and_sample_answers_for_adult_data(max_size_of_sample_such_that_i_am_ready_to_wait_it=10 ** 6):
# Загружаем датасет
raw_dataframe = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/adult/adult.data', header=None)
columns = ('age workclass fnlwgt education educ-num marital-status occupation relationship '
'race sex capital-gain capital-loss hours-per-week native-country salary')
raw_dataframe.columns = columns.split()
# Удалим все объекты, где не все признаки известны
cleared_dataframe = raw_dataframe.replace(' ?', np.nan).dropna()
# Выделяем ответы
sample_answers = np.array(cleared_dataframe['salary'].apply(lambda salary: salary == ' >50K'))[:max_size_of_sample_such_that_i_am_ready_to_wait_it]
# Находим категориальные признаки
some_features_values = cleared_dataframe.values[0]
categorial_features_indexes = []
for i in np.arange(some_features_values.shape[0]):
if type(some_features_values[i]) == np.str:
categorial_features_indexes += [i]
# Избавляемся от категориальных признаков
dataframe = cleared_dataframe.drop(cleared_dataframe.columns[categorial_features_indexes], axis=1)
# Непосредственно наша выборка
sample = np.array(dataframe)[:max_size_of_sample_such_that_i_am_ready_to_wait_it]
return sample, sample_answers
In [5]:
from sklearn.model_selection import train_test_split
# Разбиваем данные на test и train; параметр функции нужно убрать, чтобы взять всю выборку
# sample, sample_answers = find_sample_and_sample_answers_for_adult_data(max_size_of_sample_such_that_i_am_ready_to_wait_it=78)
sample, sample_answers = find_sample_and_sample_answers_for_adult_data()
train_sample, test_sample, train_sample_answers, test_sample_answers = train_test_split(sample, sample_answers,
test_size=test_sample_size_absolute_proportion,
random_state=42)
In [6]:
# Бутстрепинг, что бы это ни значило
train_subsamples = np.empty([iterations_count, train_sample.shape[0], train_sample.shape[1]])
train_subsamples_answers = np.empty([iterations_count, train_sample_answers.shape[0]])
for i in np.arange(iterations_count):
# Выбираем рандомные объекты с повторениями
train_subsample_indexes = np.random.choice(train_sample.shape[0], train_sample.shape[0], replace=True)
train_subsample = train_sample[train_subsample_indexes]
train_subsample_answers = train_sample_answers[train_subsample_indexes]
train_subsamples[i] = train_subsample
train_subsamples_answers[i] = train_subsample_answers
In [7]:
# Размножаем ответы на тестовую выборку
test_sample_answers_multiplied = test_sample_answers.reshape(-1, 1).repeat(iterations_count, axis=1)
In [8]:
grid_depth = grid['minkowski_metric_degree'].shape[0]
bias_variance_dataframe = pd.DataFrame.from_dict({
'minkowski_metric_degree': grid['minkowski_metric_degree'],
'bias': np.array([np.NaN] * grid_depth),
'variance': np.array([np.NaN] * grid_depth),
'error': np.array([np.NaN] * grid_depth)
})
from tqdm import tqdm
for minkowski_metric_degree in grid['minkowski_metric_degree']:
# Предсказываем ответы по созданных подвыборкам
test_sample_answers_predicted = np.empty([test_sample.shape[0], iterations_count])
for i in tqdm(np.arange(iterations_count)):
classifier = KNeighborsClassifier(p=minkowski_metric_degree).fit(train_subsamples[i], train_subsamples_answers[i])
test_sample_answers_predicted[:, i] = classifier.predict(test_sample)
# Считаем error, bias и variance
error = np.sum((test_sample_answers_multiplied - test_sample_answers_predicted) ** 2, axis=1) / iterations_count
bias = (test_sample_answers - np.mean(test_sample_answers_predicted, axis=1)) ** 2
variance = np.var(test_sample_answers_predicted, axis=1)
# Сохраняем полученные результаты
bias_variance_dataframe.loc[bias_variance_dataframe['minkowski_metric_degree'] == minkowski_metric_degree, 'bias'] = bias.mean()
bias_variance_dataframe.loc[bias_variance_dataframe['minkowski_metric_degree'] == minkowski_metric_degree, 'variance'] = variance.mean()
bias_variance_dataframe.loc[bias_variance_dataframe['minkowski_metric_degree'] == minkowski_metric_degree, 'error'] = error.mean()
In [9]:
for i, name in np.ndenumerate(['error', 'bias', 'variance']):
bias_variance_dataframe.plot.line('minkowski_metric_degree', name, figsize=(9, 4))
In [10]:
grid_depth = grid['neightbours_count'].shape[0]
bias_variance_dataframe = pd.DataFrame.from_dict({
'neightbours_count': grid['neightbours_count'],
'bias': np.array([np.NaN] * grid_depth),
'variance': np.array([np.NaN] * grid_depth),
'error': np.array([np.NaN] * grid_depth)
})
from tqdm import tqdm
for neightbours_count in grid['neightbours_count']:
# Предсказываем ответы по созданных подвыборкам
test_sample_answers_predicted = np.empty([test_sample.shape[0], iterations_count])
for i in tqdm(np.arange(iterations_count)):
classifier = KNeighborsClassifier(n_neighbors=neightbours_count).fit(train_subsamples[i], train_subsamples_answers[i])
test_sample_answers_predicted[:, i] = classifier.predict(test_sample)
# Считаем error, bias и variance
error = np.sum((test_sample_answers_multiplied - test_sample_answers_predicted) ** 2, axis=1) / iterations_count
bias = (test_sample_answers - np.mean(test_sample_answers_predicted, axis=1)) ** 2
variance = np.var(test_sample_answers_predicted, axis=1)
# Сохраняем полученные результаты
bias_variance_dataframe.loc[bias_variance_dataframe['neightbours_count'] == neightbours_count, 'bias'] = bias.mean()
bias_variance_dataframe.loc[bias_variance_dataframe['neightbours_count'] == neightbours_count, 'variance'] = variance.mean()
bias_variance_dataframe.loc[bias_variance_dataframe['neightbours_count'] == neightbours_count, 'error'] = error.mean()
In [11]:
bias_variance_dataframe
Out[11]:
In [12]:
for i, name in np.ndenumerate(['error', 'bias', 'variance']):
bias_variance_dataframe.plot.line('neightbours_count', name, figsize=(9, 4))
In [13]:
grid_depth = grid['train_sample_size_relative_proportion'].shape[0]
bias_variance_dataframe = pd.DataFrame.from_dict({
'train_sample_size_relative_proportion': grid['train_sample_size_relative_proportion'],
'bias': np.array([np.NaN] * grid_depth),
'variance': np.array([np.NaN] * grid_depth),
'error': np.array([np.NaN] * grid_depth)
})
from tqdm import tqdm
for train_sample_size_relative_proportion in grid['train_sample_size_relative_proportion']:
test_sample_size_absolute_proportion = 1 - train_sample_size_relative_proportion / (train_sample_size_relative_proportion + 1)
train_sample, test_sample, train_sample_answers, test_sample_answers = train_test_split(sample, sample_answers,
test_size=test_sample_size_absolute_proportion,
random_state=42)
# Бутстрепинг, что бы это ни значило
train_subsamples = np.empty([iterations_count, train_sample.shape[0], train_sample.shape[1]])
train_subsamples_answers = np.empty([iterations_count, train_sample_answers.shape[0]])
for i in np.arange(iterations_count):
# Выбираем рандомные объекты с повторениями
train_subsample_indexes = np.random.choice(train_sample.shape[0], train_sample.shape[0], replace=True)
train_subsample = train_sample[train_subsample_indexes]
train_subsample_answers = train_sample_answers[train_subsample_indexes]
train_subsamples[i] = train_subsample
train_subsamples_answers[i] = train_subsample_answers
# Размножаем ответы на тестовую выборку
test_sample_answers_multiplied = test_sample_answers.reshape(-1, 1).repeat(iterations_count, axis=1)
# Предсказываем ответы по созданных подвыборкам
test_sample_answers_predicted = np.empty([test_sample.shape[0], iterations_count])
for i in tqdm(np.arange(iterations_count)):
classifier = KNeighborsClassifier().fit(train_subsamples[i], train_subsamples_answers[i])
test_sample_answers_predicted[:, i] = classifier.predict(test_sample)
# Считаем error, bias и variance
error = np.sum((test_sample_answers_multiplied - test_sample_answers_predicted) ** 2, axis=1) / iterations_count
bias = (test_sample_answers - np.mean(test_sample_answers_predicted, axis=1)) ** 2
variance = np.var(test_sample_answers_predicted, axis=1)
# Сохраняем полученные результаты
bias_variance_dataframe.loc[bias_variance_dataframe['train_sample_size_relative_proportion'] == train_sample_size_relative_proportion, 'bias'] = bias.mean()
bias_variance_dataframe.loc[bias_variance_dataframe['train_sample_size_relative_proportion'] == train_sample_size_relative_proportion, 'variance'] = variance.mean()
bias_variance_dataframe.loc[bias_variance_dataframe['train_sample_size_relative_proportion'] == train_sample_size_relative_proportion, 'error'] = error.mean()
In [14]:
for i, name in np.ndenumerate(['error', 'bias', 'variance']):
bias_variance_dataframe.plot.line('train_sample_size_relative_proportion', name, figsize=(9, 4))
In [15]:
import warnings
import numpy as np
warnings.simplefilter("ignore")
class KNNClassifier():
def __init__(self, neighbours_count, metric):
'''
neighbours_count - количество ближайших рассматриваемых соседей, int
metric - функция для вычисления расстояния от одного объекта до нескольких других, lambda (2 args)
'''
self.neighbours_count = neighbours_count
self.metric = metric
def fit(self, train_sample, train_sample_answers):
'''
Задает обучающую выборку и ответы для каждого объекта
train_sample = (f_i,j), где f_i,j - значение j-го признака i-го объекта, np.array (2 dims)
train_sample_answers = (с_i), где с_i - идектификатор класса i-го объекта, np.array
classes_id = (c_i), где c_i - индектификатор i-го класса
'''
self.train_sample = train_sample
self.train_sample_answers = train_sample_answers
self.classes_id = np.unique(self.train_sample_answers)
return self
def predict(self, test_sample):
'''
По выборке test_sampel возвращает список предсказанных ответов
test_sample = (f_i,j), где f_i,j - значение j-го признака i-го объекта, np.array (2 dims)
test_sample_answers_predictions = (c_i), где c_i - идентификатор предсказанного класса
'''
test_sample_count = test_sample.shape[0]
test_sample_answer_predictions = np.empty(test_sample_count)
# Если количество соседей больше, чем всего элементов в выборке, то метод не должен упасть
neighbours_count = max(1, min(self.neighbours_count, self.train_sample.shape[0]))
for i in np.arange(test_sample_count):
# Находим neighbours_count ближайших соседей
distances = self.metric(test_sample[i], self.train_sample)
nearest_sample_indexes = np.argpartition(distances, neighbours_count - 1)[:neighbours_count]
nearest_sample_answers = self.train_sample_answers[nearest_sample_indexes]
# Находим самый популярный класс среди neighbours_count ближайших соседей
classes_sizes = np.array(list(map(lambda class_id: np.count_nonzero(nearest_sample_answers == class_id),
self.classes_id)))
test_sample_answer_predictions[i] = np.argmax(classes_sizes)
return test_sample_answer_predictions
In [16]:
# Расстояние от 1d-массива a до строк 2d-массива b
squared_euclidian_metric = lambda a, b: ((a - b) ** 2).sum(axis=1)
In [17]:
from sklearn.model_selection import train_test_split
# Разбиваем данные на test и train
sample, sample_answers = find_sample_and_sample_answers_for_adult_data()
train_sample, test_sample, train_sample_answers, test_sample_answers = train_test_split(sample, sample_answers,
test_size=0.2, random_state=42)
In [18]:
from sklearn.metrics import accuracy_score
for neighbours_count in [3, 5, 10]:
classifier = KNNClassifier(neighbours_count, squared_euclidian_metric)
classifier.fit(train_sample, train_sample_answers)
print('При k = {}: {:.5f} (train) vs. {:.5f} (test)'.format(neighbours_count,
accuracy_score(classifier.predict(train_sample), train_sample_answers),
accuracy_score(classifier.predict(test_sample), test_sample_answers)))
Реализуйте алгоритм отбора признаков ADD_DELL и примените его для kNN на данных sklearn.datasets.digits(). Для этого предлагается реализовать следующие функции
In [19]:
from sklearn.datasets import load_digits
sample = load_digits()
train_sample, test_sample, train_sample_answers, test_sample_answers = train_test_split(sample.data, sample.target,
test_size=0.2, random_state=42)
In [20]:
from copy import deepcopy, copy
def update_min_error_index(estimator, min_error, min_error_set, min_error_index, feature_set,
train_sample, train_sample_answers, test_sample, test_sample_answers,
need_update_equal=False):
'''
Возвращает индексы, где ошибка минимальна
'''
feature_set_size = len(feature_set)
estimator.fit(train_sample[:, feature_set], train_sample_answers)
error = 1 - accuracy_score(test_sample_answers, estimator.predict(test_sample[:, feature_set]))
if error < min_error[feature_set_size]:
min_error_set[feature_set_size] = feature_set
min_error[feature_set_size] = error
if min_error[feature_set_size] < min_error[min_error_index] or \
(need_update_equal and min_error[feature_set_size] == min_error[min_error_index]):
min_error_index = feature_set_size
return min_error_index
def add_iteration(estimator, feature_set,
train_sample, train_sample_answers, test_sample, test_sample_answers,
look_forward=10, start_feature_set=[]):
'''
Итерация добавления признаков
'''
# Инициализация
min_error = { 0: np.inf }
min_error_set = { 0: [] }
min_error_index = 0
if start_feature_set:
estimator.fit(train_sample[:, feature_set], train_sample_answers)
error = 1 - accuracy_score(test_sample_answers, estimator.predict(test_sample[:, feature_set]))
min_error = { len(start_feature_set): error }
min_error_set = { len(start_feature_set): start_feature_set }
min_error_index = len(start_feature_set)
for feature_set_size in np.arange(len(start_feature_set) + 1, len(feature_set) + 1):
# Выделяем несипользованные признаки
min_error[feature_set_size] = np.inf
unused_features_set = set(feature_set).difference(set(min_error_set[feature_set_size - 1]))
unused_features = list(unused_features_set)
# Обновляем список всех признаков и значение ошибки
for feature in unused_features:
new_feature_set = min_error_set[feature_set_size - 1] + [feature]
min_error_index = update_min_error_index(estimator, min_error, min_error_set, min_error_index, new_feature_set,
train_sample, train_sample_answers, test_sample, test_sample_answers)
print('min_error: %.4lf, set_size: %d, added: %s' % (min_error[feature_set_size],
feature_set_size,
min_error_set[feature_set_size][-1]))
# Критерий останова
if min_error_index + look_forward <= feature_set_size:
break
return min_error_set[min_error_index]
def del_iteration(estimator, feature_set, train_sample, train_sample_answers, test_sample, test_sample_answers, look_forward=10):
'''
Итерация удаления признаков
'''
# Инициализация
estimator.fit(train_sample[:, feature_set], train_sample_answers)
error = 1 - accuracy_score(test_sample_answers, estimator.predict(test_sample[:, feature_set]))
min_error = { len(feature_set): error }
min_error_set = { len(feature_set): deepcopy(feature_set) }
min_error_index = len(feature_set)
for feature_set_size in np.arange(len(feature_set) - 1, 0, -1):
min_error[feature_set_size] = np.inf
features = copy(min_error_set[feature_set_size + 1])
# Обновляем список признаков и пересчитываем ошибку классификатора
for feature in features:
new_feature_set = list(set(features).difference(set([feature])))
min_error_index = update_min_error_index(estimator, min_error, min_error_set, min_error_index, new_feature_set,
train_sample, train_sample_answers, test_sample, test_sample_answers)
print('min_error: %.4lf, set_size: %d, deleted: %s' % (min_error[feature_set_size], feature_set_size,
set(min_error_set[feature_set_size + 1]).difference(set(min_error_set[feature_set_size]))))
# Критерий останова
if feature_set_size + look_forward <= min_error_index:
break
return min_error_set[min_error_index]
def add_del(estimator, feature_set, train_sample, train_sample_answers, test_sample, test_sample_answers, look_forward=10):
'''
Итеративное добавление и удаление признаков, пока ошибка не сойдется
'''
# Инициализация
min_error = None
min_error_current = np.inf
start_feature_set = []
bad_iteration_count = 2
while (min_error is None) or (min_error_current < min_error or bad_iteration_count):
min_error = min_error_current
start_feature_set = add_iteration(estimator, feature_set,
train_sample, train_sample_answers, test_sample, test_sample_answers,
look_forward, start_feature_set=start_feature_set)
start_feature_set = del_iteration(estimator, start_feature_set,
train_sample, train_sample_answers, test_sample, test_sample_answers,
look_forward)
estimator.fit(train_sample[:, start_feature_set], train_sample_answers)
min_error_current = 1 - accuracy_score(test_sample_answers, estimator.predict(test_sample[:, start_feature_set]))
if min_error_current >= min_error:
bad_iteration_count -= 1
else:
bad_iteration_count = 2
print('min_error: %.4lf, set_size: %d' % (min_error_current, len(start_feature_set)))
return start_feature_set
In [21]:
estimator = KNeighborsClassifier()
%time feature_set = add_del(estimator, list(range(train_sample.shape[1])), \
train_sample, train_sample_answers, test_sample, test_sample_answers, \
look_forward=4)
%time accuracy_score(test_sample_answers, \
estimator.fit(train_sample[:, feature_set], train_sample_answers).predict(test_sample[:, feature_set]))
Out[21]: