<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Домашнее задание №3
<span style="color
Step1:  Задача 3 (10% баллов)
Известно, что на $n$-й итерации двухклассового метода AdaBoost
был выбран базовый классификатор, допускающий ошибку только на одном объекте $x_j$. Найдите нормированный вес $w_j^{(n+1)}$ при этом объекте на следующей итерации.
Перепишем форулы со слайдов, подставив в них условия задачи. Считаем, что веса нормируются на каждой итерации. Вычисляем волшебные формулы
Step2:  Тестирование (15%)
Загрузите датасет Wine Data Set (https
Step3:  Покажите, как менялись значения критерия качества accuracy при увеличении параметра num_trees. Видны ли следы переобучения?
Step4:  Следы переобучения не видны. 
Step5:  Сейчас мой ансамбль оказался лучше, однако это может измениться при использовании прочих параметров.
Модификация Random Forest (15%)
Измените свою реализацию RandomForest так, чтобы случайное подмножество признаков выбиралось не в каждом сплите, а перед построением всего дерева. Сравните результат работы с обычным RandomForest.
<ASSISTANT_TASK:>
Python Code:
# Ваш ответ здесь
Explanation: Домашнее задание №3
<span style="color: red; font-size: 14pt">Дедлайн: 20 марта 23:59</span>
Машинное обучение, ФИВТ, Весна 2018
Оформление дз: 
- Присылайте выполненное задание на почту ml.course.mipt@gmail.com
- Укажите тему письма в следующем формате ML2018_fall &lt;номер_группы&gt; &lt;фамилия&gt;, к примеру -- ML2018_fall 596 ivanov
- Выполненное дз сохраните в файл ML2018_&lt;фамилия&gt;_&lt;группа&gt;_task&lt;номер задания&gt;.ipnb, к примеру -- ML2018_ivanov_596_task1.ipnb
Вопросы:
- Присылайте вопросы на почту ml.course.mipt@gmail.com (или в телеграм-канал)
- Укажите тему письма в следующем формате ML2018_fall Question &lt;Содержание вопроса&gt;
PS1: Используются автоматические фильтры, мы не найдем ваше дз, если вы укажете тему письма в неправильном формате.
PS2: Просроченный дедлайн снижает максимальный вес задания по формуле, указнной на первом семинаре
Часть 1. Теоретические задачи
30% баллов за задание, оценочное время выполнения 30 минут
Задача 1 (10% баллов)
Предположим, что мы решаем задачу бинарной классификации и что у нас есть три алгоритма $b_1(x)$, $b_2(x)$ и $b_3(x)$, каждый из которых ошибается с вероятностью p. Мы строим композицию взвешенным голосованием: алгоритмам присвоены значимости $w_1$, $w_2$ и $w_3$, и для вынесения вердикта суммируются значимости алгоритмов, проголосовавших за каждый из классов:
$$a_0 = \sum_{i=1}^3 w_i [b_i(x)=0]$$
$$a_1 = \sum_{i=1}^3 w_i [b_i(x)=1]$$
Объект $x$ относится к классу, для которого такая сумма оказалась максимальной. Например, если первые два алгоритма голосуют за класс $0$, а третий — за класс $1$, то выбирается класс $0$, если $w_1 + w_2 > w_3$, и класс $1$ в противном случае. Какова вероятность ошибки такой композиции этих трех алгоритмов, если:
1. $w_1 = 0.2, w_2 = 0.3, w_3 = 0.2$;
2. $w_1 = 0.2, w_2 = 0.5, w_3 = 0.2$? 
Так как каждый вес меньше суммы двух других, то вероятность ошибки не завиисит от весов и решается простым большинством. Алгоритм ошибается, если по крайней мере два алгоритма ошиблись, то есть $p' = p^3 + p^2 (1 - p) \cdot 3 = 3p^2 - 2p^3$.
Так как $w_2$ больше суммы остальных двух весов, то $a(x) = b_2(x)$ тождественно, то есть $p' = p$.
Задача 2 (10% баллов)
Рассмотрим задачу бинарной классификации. Будем считать, что все алгоритмы из базового семейства возвращают ответы из отрезка $[0,1]$, которые можно интерпретировать как вероятности принадлежности объектов классу $1$. В качестве функции потерь возьмем отрицательный логарифм правдоподобия:
$$L(y,z) = -(y \log{z}+(1-y)\log{(1-z)})$$
В формуле $y$ - правильный ответ, $z$ - ответ алгоритма. Выпишите формулы для поиска базовых алгоритмов $b_n$ и коэффициентов $\gamma_n$ в градиентном бустинге.
End of explanation
import numpy as np
def bagging(sample, sample_answers, subsamples_count):
    '''
    Делаем subsamples_count выборок с повторениями из sample и соответствующих им sample_answers.
    '''
    subsamples = np.empty([subsamples_count, sample.shape[0], sample.shape[1]])
    subsamples_answers = np.empty([subsamples_count, sample_answers.shape[0]])
    
    for i in np.arange(subsamples_count):
        subsample_indexes = np.random.choice(sample.shape[0], sample.shape[0], replace=True)
        subsample = sample[subsample_indexes]
        subsample_answers = sample_answers[subsample_indexes]
        subsamples[i] = subsample
        subsamples_answers[i] = subsample_answers
    
    return subsamples, subsamples_answers
import sklearn
from sklearn.tree import DecisionTreeClassifier
class RandomForest(sklearn.base.BaseEstimator, sklearn.base.ClassifierMixin):
    # Сделал по умолчанию max_depth=None вместо np.inf для совместимости с sklearn.tree.DecisionTreeClassifier
    def __init__(self, trees_count, max_features=None, max_depth=None, criterion='gini'):
        self.trees_count = trees_count
        self.max_features = max_features
        self.max_depth = max_depth
        self.criterion = criterion
        self.trees = np.empty(self.trees_count, dtype=DecisionTreeClassifier)
    
    def fit(self, train_sample, train_sample_answers):
        '''
        Создает деревья, используя bagging и random subspaces method.
        '''
        train_subsamples, train_subsamples_answers = bagging(sample, sample_answers, self.trees_count)
        
        for i in np.arange(self.trees_count):
            classifier = DecisionTreeClassifier(max_features=self.max_features, max_depth=self.max_depth, criterion=self.criterion)
            classifier.fit(train_subsamples[i], train_subsamples_answers[i])
            self.trees[i] = classifier
            
        return self
    
    def predict(self, test_sample):
        '''
        Предсказать класс, используя обученные деревья
        '''
        test_sample_answers = np.empty([self.trees_count, test_sample.shape[0]], dtype=np.int64)
        
        for i in np.arange(self.trees_count):
            test_sample_answers[i] = self.trees[i].predict(test_sample)
        # https://stackoverflow.com/a/19202117
        bincount = lambda tree_test_sample_answers: np.bincount(tree_test_sample_answers, minlength=4)
        bins_by_column = np.apply_along_axis(bincount, 0, test_sample_answers)
        classes = bins_by_column.argmax(axis=0)
        
        return classes
Explanation: Задача 3 (10% баллов)
Известно, что на $n$-й итерации двухклассового метода AdaBoost
был выбран базовый классификатор, допускающий ошибку только на одном объекте $x_j$. Найдите нормированный вес $w_j^{(n+1)}$ при этом объекте на следующей итерации.
Перепишем форулы со слайдов, подставив в них условия задачи. Считаем, что веса нормируются на каждой итерации. Вычисляем волшебные формулы:
$$\text{err}n = \frac{\sum{i=1}^{N} w_i [y_i \neq G_n(x_i)]}{\sum_{i=1}^{N} w_i} = \frac{w_j}{\sum_{i=1}^{N} w_i} = w_j;$$
$$ \alpha_n = \log \frac{1 - \text{err}n }{\text{err}_n } = \log \frac{1 - w_j}{w_j} .$$
Пересчитываем веса:
$$ w_j \leftarrow w_j e^{\alpha_n [y_j \neq G_n(x_j)]} = w_j e^{\alpha_n} = w_j \frac{1 - w_j}{w_j} = 1 - w_j; $$
$$ w_i \leftarrow w_i e^{\alpha_n [y_i \neq G_n(x_i)]} = w_i e^0 = w_i, \text{если } i \neq j.$$
Нормируем:
$$ w_j \leftarrow \frac{1 - w_j}{\sum{i=1, i \neq j}^{N} w_i + 1 - w_j} = \frac{1 - w_j}{2 - 2w_j} = 0.5.$$
Часть 2. Random Forest
70% баллов за задание, оценочное время выполнения 3 часа
Реализация (40%)
Необходимо реализовать класс RandomForest (для решения задачи классификации)
Спецификация:
- класс наследуется от sklearn.BaseEstimator;
- конструктор содержит следующие параметры: 
    - num_trees - количество деревьев в лесе;
    - max_depth - максимальная глубина дерева (по умолчанию - numpy.inf); 
    - max_features - количество признаков, принимаемое к рассмотрению при разбиении (аналогичный параметр есть в sklearn имплементации). Параметр может принимать значения:
        - int - тогда рассматриваем max_features признаков при каждом разбиении;
        - float - max_features обозначает процент, int(max_features * n_features) признаков рассматривается при каждом разбиении;
        - “sqrt” - max_features=sqrt(n_features);
        - “log2” - max_features=log2(n_features);
        - None - max_features=n_features;
    - criterion - критерий разбиения (для классификации - 'gini' или 'entropy', по умолчанию - 'gini'); функции с подсчетом энтропийного и критерия Джини можно взять из предыдущего дз;
класс имеет методы fit и predict;
метод fit принимает матрицу объектов X и вектор ответов y (объекты numpy.ndarray) и возвращает экземпляр класса
    RandomForest, представляющий собой Random Forest, обученный по выборке (X, y) с учётом заданных в конструкторе параметров; 
метод predict принимает матрицу объектов и возвращает вектор предсказанных ответов;
End of explanation
import pandas as pd
from sklearn.model_selection import train_test_split
raw_dataframe = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data', header=None)
sample = raw_dataframe.values[:, 1:]
sample_answers = raw_dataframe.values[:, 0]
train_sample, test_sample, train_sample_answers, test_sample_answers = train_test_split(sample, sample_answers,
                                                                                        test_size=0.2,
                                                                                        random_state=42)
classifier = RandomForest(trees_count=10)
classifier.fit(train_sample, train_sample_answers)
print(classifier.predict(test_sample) == test_sample_answers)
Explanation: Тестирование (15%)
Загрузите датасет Wine Data Set (https://archive.ics.uci.edu/ml/datasets/wine). Разделите выборку на обучающую и тестовую с помощью метода train_test_split, используйте значения параметров test_size=0.2, random_state=42. Попробуйте обучить Random Forest на предложенном датасете
End of explanation
from sklearn.metrics import accuracy_score
# Можно увеличить до 200, ничего не поменяется. Просто не хочется загромождать вывод.
for trees_count in np.arange(1, 40):
    classifier = RandomForest(trees_count=trees_count)
    classifier.fit(train_sample, train_sample_answers)
    print('При {:2} деревьях точность {:.3f}.'.format(trees_count, accuracy_score(classifier.predict(test_sample), test_sample_answers)))
Explanation: Покажите, как менялись значения критерия качества accuracy при увеличении параметра num_trees. Видны ли следы переобучения?
End of explanation
from sklearn.ensemble import RandomForestClassifier
for trees_count in np.arange(1, 40):
    my_classifier = RandomForest(trees_count=trees_count)
    my_classifier.fit(train_sample, train_sample_answers)
    their_classifier = RandomForestClassifier(n_estimators=trees_count)
    their_classifier.fit(train_sample, train_sample_answers)
    print('При {:2} деревьях точность моего составляет {:.3f}, а точность библиотечного — {:.3f}.'\
          .format(trees_count,
                  accuracy_score(my_classifier.predict(test_sample), test_sample_answers),
                  accuracy_score(their_classifier.predict(test_sample), test_sample_answers)))
Explanation: Следы переобучения не видны. :)
Сравните качество работы вашей реализации RandomForest и реализации из sklearn.
End of explanation
import sklearn
from sklearn.tree import DecisionTreeClassifier
class ModifiedRandomForest(sklearn.base.BaseEstimator, sklearn.base.ClassifierMixin):
    # Сделал по умолчанию max_depth=None вместо np.inf для совместимости с sklearn.tree.DecisionTreeClassifier
    def __init__(self, trees_count, max_features=None, max_depth=None, criterion='gini'):
        self.trees_count = trees_count
        self.max_features = max_features
        self.max_depth = max_depth
        self.criterion = criterion
        self.trees = np.empty(self.trees_count, dtype=DecisionTreeClassifier)
        self.feature_indexes = np.empty([self.trees_count, self.max_features], dtype=np.int64)
    
    def fit(self, train_sample, train_sample_answers):
        '''
        Создает деревья, используя bagging и random subspaces method.
        '''
        raw_train_subsamples, train_subsamples_answers = bagging(sample, sample_answers, self.trees_count)
        
        for i in np.arange(self.trees_count):
            if self.max_features is not None:
                self.feature_indexes[i] = np.random.choice(raw_train_subsamples.shape[2], self.max_features)
            else:
                self.feature_indexes[i] = np.arange(raw_train_subsamples.shape[2])
                
            train_subsamples = raw_train_subsamples[:, :, self.feature_indexes[i]]
            
            classifier = DecisionTreeClassifier(max_features=None, max_depth=self.max_depth, criterion=self.criterion)
            classifier.fit(train_subsamples[i], train_subsamples_answers[i])
            self.trees[i] = classifier
            
        return self
    
    def predict(self, test_sample):
        '''
        Предсказать класс, используя обученные деревья
        '''
        test_sample_answers = np.empty([self.trees_count, test_sample.shape[0]], dtype=np.int64)
        
        for i in np.arange(self.trees_count):
            test_sample_answers[i] = self.trees[i].predict(test_sample[:,  self.feature_indexes[i]])
        # https://stackoverflow.com/a/19202117
        bincount = lambda tree_test_sample_answers: np.bincount(tree_test_sample_answers, minlength=4)
        bins_by_column = np.apply_along_axis(bincount, 0, test_sample_answers)
        classes = bins_by_column.argmax(axis=0)
        
        return classes
average_accuracy = 0
average_modified_accuracy = 0
iterations_count = 40
max_trees_count = 40
for i in np.arange(iterations_count):
    for trees_count in np.arange(1, max_trees_count):
        classifier = RandomForest(trees_count=trees_count, max_features=10)
        classifier.fit(train_sample, train_sample_answers)
        average_accuracy += accuracy_score(classifier.predict(test_sample), test_sample_answers) / iterations_count / max_trees_count
        modified_classifier = ModifiedRandomForest(trees_count=trees_count, max_features=10)
        modified_classifier.fit(train_sample, train_sample_answers)
        average_modified_accuracy += accuracy_score(modified_classifier.predict(test_sample), test_sample_answers) / iterations_count / max_trees_count
        if i == 0:
            print('При {:2} деревьях точность моего составляет {:.3f}, а точность модифицированного — {:.3f}.'\
                  .format(trees_count,
                          accuracy_score(classifier.predict(test_sample), test_sample_answers),
                          accuracy_score(modified_classifier.predict(test_sample), test_sample_answers)))
print('В среднем точность обычного леса составляет {:.7f}, а точность модифицированного — {:.7f}.'\
      .format(average_accuracy, average_modified_accuracy))
Explanation: Сейчас мой ансамбль оказался лучше, однако это может измениться при использовании прочих параметров.
Модификация Random Forest (15%)
Измените свою реализацию RandomForest так, чтобы случайное подмножество признаков выбиралось не в каждом сплите, а перед построением всего дерева. Сравните результат работы с обычным RandomForest.
End of explanation
<END_TASK>