<jupyter_start><jupyter_text>Алгоритмы интеллектуальной обработки больших объемов данных Домашнее задание №2 - Дерево решений **Общая информация****Срок сдачи:** до 1 ноября 2018, 06:00 **Штраф за опоздание:** -2 балла после 06:00 1 ноября, -4 балла после 06:00 8 ноября, -6 баллов после 06:00 15 ноябряПри отправлении ДЗ указывайте фамилию в названии файла   Присылать ДЗ необходимо в виде ссылки на свой github репозиторий в slack @alkhamushНеобходимо в slack создать таск в приватный чат:   /todo Фамилия Имя *ссылка на гитхаб* @alkhamush   Пример:   /todo Ксения Стройкова https://github.com/stroykova/spheremailru/stroykova_hw2.ipynb @alkhamush   Используйте данный Ipython Notebook при оформлении домашнего задания.  Задание 1 (4 балла)Разберитесь в коде MyDecisionTreeClassifier, который уже частично реализован. В комментариях, где написано "Что делает этот блок кода?", ответьте на этот вопрос. Допишите код там, где написано "Ваш код". Ваша реализация дерева должна работать по точности не хуже DecisionTreeClassifier из sklearn. Точность проверяется на wine и Speed Dating Data. Задание 2 (2 балла)Добиться скорости работы fit такой, чтобы она была медленнее sklearn не более чем в 10 раз. Скорость проверяем на  wine и Speed Dating Data. Для ускорения используем только numpy. Задание 3 (2 балла)Добавьте функционал, который определяет значения feature importance. Выведите 10 главных фичей под пунктом Задание 3 (уже написано ниже) для MyDecisionTreeClassifier и DecisionTreeClassifier так, чтобы сразу были видны выводы и по MyDecisionTreeClassifier, и по DecisionTreeClassifier. Используем данные Speed Dating Data. Задание 4 (2 балла)С помощью GridSearchCV или RandomSearchCV подберите наиболее оптимальные параметры для случайного леса (Выберете 2-3 параметра). Используем данные Speed Dating Data. Задание реализуйте под пунктом Задание 5 (уже написано ниже)**Штрафные баллы:**1. Невыполнение PEP8 -1 балл2. Отсутствие фамилии в имени скрипта (скрипт должен называться по аналогии со stroykova_hw2.ipynb) -1 балл3. Все строчки должны быть выполнены. Нужно, чтобы output команды можно было увидеть уже в git'е. В противном случае -1 балл4. При оформлении ДЗ нужно пользоваться данным файлом в качестве шаблона. Не нужно удалять и видоизменять написанный код и текст. В противном случае -1 балл<jupyter_code>import matplotlib.pyplot as plt
import numpy as np
import pandas as pd

from sklearn.datasets import load_wine
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score, f1_score
from sklearn.model_selection import KFold, train_test_split, \
                                    GridSearchCV, RandomizedSearchCV
from sklearn.tree import DecisionTreeClassifier

%matplotlib inline
%load_ext pycodestyle_magic
#%%pycodestyle


class MyDecisionTreeClassifier:
    NON_LEAF_TYPE = 0
    LEAF_TYPE = 1

    def __init__(self, min_samples_split=2, max_depth=None,
                 sufficient_share=1.0, criterion='gini', max_features=None):
        self.tree = dict()
        self.min_samples_split = min_samples_split
        self.max_depth = ((2 ** 31) - 1 if max_depth is None else max_depth)
        self.sufficient_share = sufficient_share
        self.num_class = -1
        self.feature_importances_ = None
        if criterion == 'gini':
            self.G_function = self.__gini
        elif criterion == 'entropy':
            self.G_function = self.__entropy
        elif criterion == 'misclass':
            self.G_function = self.__misclass
        else:
            print('invalid criterion name')
            raise

        if max_features == 'sqrt':
            self.get_feature_ids = self.__get_feature_ids_sqrt
        elif max_features == 'log2':
            self.get_feature_ids = self.__get_feature_ids_log2
        elif max_features is None:
            self.get_feature_ids = self.__get_feature_ids_N
        else:
            print('invalid max_features name')
            raise

    def __gini(self, l_c, l_s, r_c, r_s):
        l_s = l_s.astype('float')
        r_s = r_s.astype('float')
        return 2 - (((l_c / l_s)**2).sum(axis=1)
                    + ((r_c / r_s)**2).sum(axis=1))

    def __entropy(self, l_c, l_s, r_c, r_s):
        return - (((l_c / l_s) * np.log2(l_c / l_s)).sum(axis=1)
                  + ((r_c / r_s) * np.log2(r_c / r_s)).sum(axis=1))

    def __misclass(self, l_c, l_s, r_c, r_s):
        return 2 - ((l_c / l_s).max(axis=1) + (r_c / r_s).max(axis=1))

    def __get_feature_ids_sqrt(self, n_feature):
        feature_ids = range(n_feature)
        np.random.shuffle(feature_ids)
        return feature_ids[:int(np.sqrt(n_feature))]

    def __get_feature_ids_log2(self, n_feature):
        feature_ids = range(n_feature)
        np.random.shuffle(feature_ids)
        return feature_ids[:int(np.log2(n_feature))]

    def __get_feature_ids_N(self, n_feature):
        return np.arange(n_feature)

    def __sort_samples(self, x, y):
        sorted_idx = x.argsort()
        return x[sorted_idx], y[sorted_idx]

    def __div_samples(self, x, y, feature_id, threshold):
        left_mask = x[:, feature_id] > threshold
        right_mask = ~left_mask
        return x[left_mask], x[right_mask], y[left_mask], y[right_mask]

    def __find_threshold(self, x, y):
        # Что делает этот блок кода?
        # берем индексы, сортирующие x (срез данных вдоль выбранной фичи),
        # и в массивы sorted_x, sorted_y помещаем последовательность
        # элементов x, y, в порядке, заданном вышеупомянутыми индексами;
        # инициализируем переменные class_number - число классов и
        # cut_size - число отделяемых элементов
        sorted_x, sorted_y = self.__sort_samples(x, y)
        class_number = self.num_class
        cut_size = np.int(self.min_samples_split / 2 - 1)

        # Что делает этот блок кода?
        # отделяем элементы, если нужно;
        # находим индексы границы между классами в y и помещаем в
        # r_border_ids, если таковые имеются, иначе прерываемся
        if cut_size == 0:
            splitted_sorted_y = sorted_y
        else:
            splitted_sorted_y = sorted_y[cut_size:-cut_size]
        r_border_ids = np.where(splitted_sorted_y[:-1] !=
                                splitted_sorted_y[1:])[0] + (cut_size + 1)

        if len(r_border_ids) == 0:
            return np.inf, None

        # Что делает этот блок кода?
        # r_border_ids составлена таким образом, что
        # (r_border_ids[n] - r_border_ids[n-1]) дает число
        # идущих подряд одинаковых элементов, помещаем эти
        # числа в массив eq_el_count;
        # помещаем в матрицу на основе one hot encoding
        # информацию сколько какой класс повторялся
        eq_el_count = r_border_ids - np.append(np.array([cut_size]),
                                               r_border_ids[:-1])
        one_hot_code = np.zeros((r_border_ids.shape[0], class_number))
        one_hot_code[np.arange(r_border_ids.shape[0]),
                     sorted_y[r_border_ids - 1]] = 1
        class_increments = one_hot_code * eq_el_count.reshape(-1, 1)
        class_increments[0] = class_increments[0] + \
            np.bincount(sorted_y[:cut_size], minlength=class_number)

        # по границам смены классов в y строим различные разумные
        # разбиения на l и r и вычисляем их размеры
        l_class_count = np.cumsum(class_increments, axis=0)
        r_class_count = np.bincount(sorted_y,
                                    minlength=class_number) - l_class_count
        l_sizes = r_border_ids.reshape(l_class_count.shape[0], 1)
        r_sizes = sorted_y.shape[0] - l_sizes

        # вычисляем impurity для получившихся разбиений и находим
        # оптимальное разбиение
        gs = self.G_function(l_class_count, l_sizes, r_class_count, r_sizes)
        idx = np.argmin(gs)

        # возвращаем минимальную неопределенность и порог разбиения
        left_el_id = l_sizes[idx][0]
        return gs[idx], (sorted_x[left_el_id-1] + sorted_x[left_el_id]) / 2.0

    def __fit_node(self, x, y, node_id, depth, pred_f=-1):
        # Ваш код
        # Необходимо использовать следующее:
        # self.LEAF_TYPE
        # self.NON_LEAF_TYPE

        # self.tree
        # self.max_depth
        # self.sufficient_share
        # self.min_samples_split

        # self.get_feature_ids
        # self.__find_threshold
        # self.__div_samples
        # self.__fit_node

        if node_id == 0:
            self.tree.clear()

        n_sample, n_feature = x.shape
        y_un = np.unique(y)
        y_bins = np.bincount(y)
        y_bmax = y_bins.argmax()
        max_bins = n_sample * self.sufficient_share

        if (depth >= self.max_depth) or (n_sample < self.min_samples_split) \
                or (y_un.size == 1) or (y_bmax >= max_bins):
            self.tree[node_id] = (self.LEAF_TYPE, y_bmax, y_bins / n_sample)
            return

        feature_ids = self.get_feature_ids(n_feature)
        thresholds = np.empty((feature_ids.size, 2), dtype=float)
        for i in feature_ids:
            thresholds[i] = self.__find_threshold(x[:, i], y)
        best_feature = np.argmin(thresholds[:, 0])
        best_gs, best_split = thresholds[best_feature]

        if best_split is None:
            self.tree[node_id] = (self.LEAF_TYPE, y_bmax, y_bins / n_sample)
            return

        x_l, x_r, y_l, y_r = \
            self.__div_samples(x, y, feature_ids[best_feature], best_split)

        if (y_l.size == 0) or (y_r.size == 0):
            self.tree[node_id] = (self.LEAF_TYPE, y_bmax, y_bins / n_sample)
            return

        self.tree[node_id] = (self.NON_LEAF_TYPE, feature_ids[best_feature],
                              best_split)

        self.feature_importances_[feature_ids[best_feature]] += best_gs

        self.__fit_node(x_l, y_l, 2*node_id + 1, depth + 1, pred_f)
        self.__fit_node(x_r, y_r, 2*node_id + 2, depth + 1, pred_f)

    def fit(self, x, y):
        self.num_class = np.unique(y).size
        self.feature_importances_ = np.zeros((x.shape[1],), dtype=np.float32)
        self.__fit_node(x, y, 0, 0)

    def __predict_class(self, x, node_id):
        node = self.tree[node_id]
        if node[0] == self.__class__.NON_LEAF_TYPE:
            _, feature_id, threshold = node
            if x[feature_id] > threshold:
                return self.__predict_class(x, 2 * node_id + 1)
            else:
                return self.__predict_class(x, 2 * node_id + 2)
        else:
            return node[1]

    def __predict_probs(self, x, node_id):
        node = self.tree[node_id]
        if node[0] == self.__class__.NON_LEAF_TYPE:
            _, feature_id, threshold = node
            if x[feature_id] > threshold:
                return self.__predict_probs(x, 2 * node_id + 1)
            else:
                return self.__predict_probs(x, 2 * node_id + 2)
        else:
            return node[2]

    def predict(self, X):
        return np.array([self.__predict_class(x, 0) for x in X])

    def predict_probs(self, X):
        return np.array([self.__predict_probs(x, 0) for x in X])

    def fit_predict(self, x_train, y_train, predicted_x):
        self.fit(x_train, y_train)
        return self.predict(predicted_x)
my_clf = MyDecisionTreeClassifier(min_samples_split=2)
clf = DecisionTreeClassifier(min_samples_split=2)
wine = load_wine()
X_train, X_test, y_train, y_test = \
    train_test_split(wine.data, wine.target, test_size=0.1,
                     stratify=wine.target)<jupyter_output><empty_output><jupyter_text>Проверка скорости работы на wine<jupyter_code>%time clf.fit(X_train, y_train)
%time my_clf.fit(X_train, y_train)<jupyter_output>Wall time: 26 ms<jupyter_text>Проверка качества работы на wine<jupyter_code>f1_score(y_pred=clf.predict(X_test), y_true=y_test, average='macro')
f1_score(y_pred=my_clf.predict(X_test), y_true=y_test, average='macro')<jupyter_output><empty_output><jupyter_text>Подготовка данных Speed Dating Data<jupyter_code># тут делаете то же самое, что и на семинаре
# https://github.com/stroykova/spheremailru/blob/master/2018-02/
# lecture_04_trees/pract-speed-dating-trees-proc.ipynb

df = pd.read_csv('Speed Dating Data.csv', encoding='cp1251')
df = df.iloc[:, :97]

df = df.drop(['id', 'idg', 'condtn', 'round', 'position', 'positin1',
              'order', 'partner', 'age_o', 'race_o', 'pf_o_att',
              'pf_o_sin', 'pf_o_int', 'pf_o_fun', 'pf_o_amb', 'pf_o_sha',
              'dec_o', 'attr_o', 'sinc_o', 'intel_o', 'fun_o', 'amb_o',
              'shar_o', 'like_o', 'prob_o', 'met_o', 'field', 'undergra',
              'from', 'zipcode', 'career', 'sports', 'tvsports', 'exercise',
              'dining', 'museums', 'art', 'hiking', 'gaming', 'clubbing',
              'reading', 'tv', 'theater', 'movies', 'concerts',
              'music', 'shopping', 'yoga', 'expnum', 'wave'], axis=1)

df = df.dropna(subset=['age', 'imprelig', 'imprace', 'date'])

df.loc[:, 'field_cd'] = df.loc[:, 'field_cd'].fillna(0)
df.loc[:, 'career_c'] = df.loc[:, 'career_c'].fillna(0)

df.loc[:, 'mn_sat'] = \
            df.loc[:, 'mn_sat'].str.replace(',', '').astype(np.float)
df.loc[:, 'tuition'] = \
            df.loc[:, 'tuition'].str.replace(',', '').astype(np.float)
df.loc[:, 'income'] = \
            df.loc[:, 'income'].str.replace(',', '').astype(np.float)

df.loc[:, 'mn_sat'] = df.mn_sat.fillna(df.mn_sat[df.mn_sat.notna()].mean())
df.loc[:, 'tuition'] = df.tuition.fillna(df.tuition[df.tuition.notna()].mean())
df.loc[:, 'income'] = df.income.fillna(df.income[df.income.notna()].mean())

df.loc[:, 'temp_totalsum'] = \
    df.loc[:, ['attr1_1', 'sinc1_1', 'intel1_1', 'fun1_1',
               'amb1_1', 'shar1_1']].sum(axis=1)

df.loc[:, ['attr1_1', 'sinc1_1', 'intel1_1', 'fun1_1', 'amb1_1',
           'shar1_1']] = (df.loc[:, ['attr1_1', 'sinc1_1', 'intel1_1',
                                     'fun1_1', 'amb1_1', 'shar1_1']].T /
                          df.loc[:, 'temp_totalsum'].T).T * 100

df.loc[:, 'temp_totalsum'] = \
    df.loc[:, ['attr2_1', 'sinc2_1', 'intel2_1', 'fun2_1',
               'amb2_1', 'shar2_1']].sum(axis=1)

df.loc[:, ['attr2_1', 'sinc2_1', 'intel2_1', 'fun2_1',
           'amb2_1', 'shar2_1']] = \
    (df.loc[:, ['attr2_1', 'sinc2_1', 'intel2_1', 'fun2_1',
            'amb2_1', 'shar2_1']].T /
     df.loc[:, 'temp_totalsum'].T).T * 100

df = df.drop(['temp_totalsum'], axis=1)

for i in [4, 5]:
    feat = ['attr{}_1'.format(i), 'sinc{}_1'.format(i),
            'intel{}_1'.format(i), 'fun{}_1'.format(i),
            'amb{}_1'.format(i), 'shar{}_1'.format(i)]

    if i != 4:
        feat.remove('shar{}_1'.format(i))

    df = df.drop(feat, axis=1)

df_male = df.query('gender == 1').drop_duplicates(subset=['iid', 'pid'])\
                                 .drop(['gender'], axis=1)\
                                 .dropna()
df_female = df.query('gender == 0').drop_duplicates(subset=['iid'])\
                                   .drop(['gender', 'match', 'int_corr',
                                          'samerace'], axis=1)\
                                   .dropna()

df_female.columns = df_female.columns + '_f'

df_female = df_female.drop(['pid_f'], axis=1)

df_pair = df_male.join(df_female.set_index('iid_f'),
                       on='pid',
                       how='inner')

df_pair = df_pair.drop(['iid', 'pid'], axis=1)
X = df_pair.iloc[:, 1:].values
y = df_pair.iloc[:, 0].values
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.1,
                                                    random_state=123)
my_clf = MyDecisionTreeClassifier(min_samples_split=2)
my_clf = DecisionTreeClassifier(min_samples_split=2)<jupyter_output><empty_output><jupyter_text>Проверка скорости работы на Speed Dating Data<jupyter_code>%time clf.fit(X_train, y_train)
%time my_clf.fit(X_train, y_train)<jupyter_output>Wall time: 63 ms<jupyter_text>Проверка качества работы на Speed Dating Data<jupyter_code>f1_score(y_pred=clf.predict(X_test), y_true=y_test, average='macro')
f1_score(y_pred=my_clf.predict(X_test), y_true=y_test, average='macro')<jupyter_output><empty_output><jupyter_text>Задание 3<jupyter_code>clf_features = np.argsort(clf.feature_importances_)[::-1][:10]
my_clf_features = np.argsort(my_clf.feature_importances_)[::-1][:10]
feature_names = df_pair.columns
clf_features_col = clf.feature_importances_[clf_features]
myclf_features_col = my_clf.feature_importances_[my_clf_features]
feature_rating = {"clf_key": feature_names[clf_features],
                  "clf_features": clf_features_col,
                  "myclf_key": feature_names[my_clf_features],
                  "myclf_features": myclf_features_col}
pd.DataFrame(data=feature_rating)<jupyter_output><empty_output><jupyter_text>Задание 4<jupyter_code>from random import randint
from sklearn.model_selection import StratifiedKFold

param_grid = {
    'criterion': ['gini', 'entropy'],
    'min_samples_split': range(2, 20),
    'max_features': range(2, 20)}

cv = StratifiedKFold(n_splits=5, random_state=123, shuffle=True)

model = DecisionTreeClassifier(random_state=123)
random_search = RandomizedSearchCV(model, param_distributions=param_grid,
                                   n_iter=200, n_jobs=-1, cv=cv,
                                   scoring='roc_auc', random_state=123)

random_search.fit(X_train, y_train)
random_search.best_params_
random_search.best_score_<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12163480856437632, 'fraction_numerical': 0.017565007749268124, 'mean_word_length': 2.904527117884357, 'pattern_counts': {'":': 4, '<': 32, '<?xml version=': 0, '>': 36, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '302550', 'license': 'MIT', 'n_tokens_mistral': 6652, 'n_tokens_neox': 6730, 'n_words': 1301, 'path': 'AIPLAD/hw/2/dokukin_hw2.ipynb', 'repo_name': 'sergy2710/spheremail', 'size': '17421'}