# This Python 3 environment comes with many helpful analytics libraries installed
# It is defined by the kaggle/python Docker image: https://github.com/kaggle/docker-python
# For example, here's several helpful packages to load

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from imblearn import over_sampling, under_sampling
import matplotlib.pyplot as plt
import seaborn as sns

# Input data files are available in the read-only "../input/" directory
# For example, running this (by clicking run or pressing Shift+Enter) will list all files under the input directory

import os
for dirname, _, filenames in os.walk('/kaggle/input'):
    for filename in filenames:
        print(os.path.join(dirname, filename))

# You can write up to 20GB to the current directory (/kaggle/working/) that gets preserved as output when you create a version using "Save & Run All" 
# You can also write temporary files to /kaggle/temp/, but they won't be saved outside of the current session
"""
**Ваша задача этом соревновании** - предсказать вероятность того, подойдет ли репетитор для подготовки к экзамену по математике.
Вам будут даны два датасета: train.csv (содержит признаки и целевую переменную) и test.csv (только признаки).
The evaluation metric is **ROC AUC**
"""
"""
### 1. EDA(Exploratory Data Analaysis)
"""
"""
Считываем данные
"""
SAMPLE_SUBMISSION = pd.read_csv('/kaggle/input/gb-classification-choose-tutors/sample_submission.csv')
TRAIN = pd.read_csv('/kaggle/input/gb-classification-choose-tutors/train.csv')
TEST = pd.read_csv('/kaggle/input/gb-classification-choose-tutors/test.csv')
"""
Посмотрим на количество наблюдений и количество фичей
"""
TRAIN.shape
"""
#### Если в данных есть неизвестные, пропущенные, или некорректно заполненные данные, то мы это увидим с .info()
"""
TRAIN.info()
"""
Покажем первые 10 записей в таблице
"""
TRAIN.head(10)
"""

Датасет состоит из 10000 записей и 13 фичей(признаков), из которых одна - целевая переменная

**id** - идентификатор

**age** - возраст

**years_of_experience** - опыт

**lesson_price** - стоимость урока

**qualification** - квалификация

**physics** - физика

**chemistry** - химия

**biology** - биология

**english** - английский

**geography** - география

**history** - история

**mean_exam_points** - средний балл за экзамен

**choose** - выбор и наша целевая переменная (1 - подойдет/0 - нет)

Как мы видим, у нас есть некоторые данные о репетиторе и данные о его неких познаниях в разных предметах, но не в математике.

"""
"""
#### Обзор количественных признаков
"""
TRAIN.describe()
"""
#### Обработка пропусков
"""
TRAIN.isna().sum()
"""
Пропусков нет
"""
"""
1.6 Seaborn countplot дает информацию о данных в каждом классе, здесь рассмотрим наш target
"""
sns.countplot(x="choose", data=TRAIN)
TRAIN['choose'].value_counts()
"""
Видим что у нас значительный перевес значения для фичи choose: 0 - 8891, 1 - 1109
"""
"""
#### Построим матрицу корреляций(только линейная зависимость)
"""
plt.figure(figsize = (20,15))

sns.set(font_scale=1.4)
sns.heatmap(TRAIN.corr().round(3), annot=True, linewidths=.5, cmap='GnBu')

plt.title('Correlation matrix')
plt.show()
"""
#### Посмотрим распределение каждой переменной
"""
TRAIN.hist(bins=30, figsize=(22,17))
plt.show()
"""
Удалим незначимые признаки
"""
def drop_column(column_list, TRAIN, TEST):
    for col in column_list:
        TRAIN = TRAIN.drop([col], axis=1)
        TEST = TEST.drop([col], axis=1)


column_list = ['Id', 'history', 'geography', 'english']   
drop_column(column_list, TRAIN, TEST)
"""
Добавим новые признаки
"""
TRAIN['index_qualification'] = (TRAIN['years_of_experience'] + 0.01) / (TRAIN['age'] + TRAIN['lesson_price'])
TEST['index_qualification'] = (TEST['years_of_experience'] + 0.01) / (TEST['age'] + TEST['lesson_price'])

TRAIN['index_experience'] = (TRAIN['age'] * (TRAIN['years_of_experience'] + 0.01)) / (TRAIN['qualification'])
TEST['index_experience'] = (TEST['age'] * (TEST['years_of_experience'] + 0.01)) / (TEST['qualification'])
TRAIN.shape, TEST.shape
X = TRAIN.drop('choose', axis=1).values
y = TRAIN.choose.values
TEST = TEST.values
# Балансировка классов(нужна больше для модели KNN и логистической регрессии, так как иначе модель будет видеть рядом только данные одного класса, 
# что некорректно скажется на предсказании)
#from imblearn.over_sampling import SMOTE
#sm = SMOTE(random_state=0, k_neighbors=11)
#X_train_res, y_train_res = sm.fit_resample(X, y)
#print(f"Before OverSampling, counts of label '1': {sum(y == 1)}")
#print(f"Before OverSampling, counts of label '0': {sum(y == 0)} \n")

#print(f'After OverSampling, the shape of train_X: {X_train_res.shape}')
#print(f'After OverSampling, the shape of train_y: {y_train_res.shape} \n')

#print(f"After OverSampling, counts of label '1': {sum(y_train_res == 1)}")
#print(f"After OverSampling, counts of label '0': {sum(y_train_res == 0)}")
"""
### 2. KNN Classification
**Метод к-ближайших соседей** - Здесь нам нужно подобрать число K-соседей, близлежащие к нашей точке

[Метод k-ближайших соседей](https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_k-%D0%B1%D0%BB%D0%B8%D0%B6%D0%B0%D0%B9%D1%88%D0%B8%D1%85_%D1%81%D0%BE%D1%81%D0%B5%D0%B4%D0%B5%D0%B9) (англ. k-nearest neighbors algorithm, k-NN) — метрический алгоритм для автоматической классификации объектов или регрессии.

В случае использования метода для классификации объект присваивается тому классу, который является наиболее распространённым среди k соседей данного элемента, классы которых уже известны. В случае использования метода для регрессии, объекту присваивается среднее значение по k  ближайшим к нему объектам, значения которых уже известны.

Алгоритм может быть применим к выборкам с большим количеством атрибутов (многомерным). Для этого перед применением нужно определить функцию расстояния; классический вариант такой функции — евклидова метрика. 
"""
"""
#### Добавим вычисления евклидовой метрики и метрики accuracy
"""
"""
#### Зададим класс описывающий модель KNN с учетом весов расстояний
"""
class KNN_model:
    # Для работы на обучении определяем данные для работы
    def __init__(self, x, y):
        self.x_train, self.x_test, self.y_train, self.y_test = train_test_split(x, y, test_size=0.3, random_state=42)
        self.y_pred = None

    # Евклидова метрика (евклидово расстояние) — метрика в евклидовом пространстве — расстояние между двумя точками евклидова пространства, 
    # вычисляемое по теореме Пифагора. 
    def e_metrics(self, x1, x2):
        distance = np.sum(np.square(x1 - x2))
        return np.sqrt(distance)

    # Метрика accuracy на основании которой будем делать вывод о качестве модели
    def accuracy(self, pred, y):
        return sum(pred == y) / len(y)

    # Для работы уже по предсказанию вероятности класса
    @staticmethod
    def knn(x_train, y_train, x_test, k, weights=None):

        answers = []
        for x in x_test:

            # расчет расстояний от классифицируемого объекта до
            # объектов обучающей выборки
            distances = np.sqrt(np.sum(np.square(x - x_train), axis=1))

            # создаем словарь со всеми возможными классами
            classes = {class_item: 0 for class_item in set(y_train)}

            # больше оптимизации
            test_distances = np.c_[distances, y_train]
            for d in sorted(test_distances, key=lambda x: x[0])[0:k]:
                classes[d[1]] += 1

            # Записываем в список ответов вероятность для 1 класса
            answers.append(classes[1] / (classes[1] + classes[0]))

        return answers

    # метод для подсчета оптимального количества k-ближайших соседей в цикле
    def count_best(self):
        k_list = [9]

        k_result = {}
        y_pred_dic = {}

        for k in k_list:
            self.y_pred = self.knn_weight(self.x_train, self.y_train, self.x_test, k)
            y_pred_dic[k] = self.y_pred
            k_result[k] = self.accuracy(self.y_pred, self.y_test)
        print(f"Лучший результат при k = {sorted(k_result, key=k_result.get)[-1]}: {k_result[sorted(k_result, key=k_result.get)[-1]]}")
        print(k_result)

        return y_pred_dic[sorted(k_result, key=k_result.get)[-1]]
# Методом проб и ошибок 9 - лучшее число k
# model = KNN_model(X_train_res, y_train_res)
# y_KNN = KNN_model.knn(X_train_res, y_train_res, X_TEST, 9)
"""
Результат: KNN дала нам точность предсказания вероятности - knn 0.90246, но эта модель оказалась не самой лучшей.
"""
"""
### 3. Random forest
**Random forest** (с англ. — «случайный лес») — алгоритм машинного обучения, предложенный Лео Брейманом и Адель Катлер (англ.)русск., заключающийся в использовании комитета (ансамбля) решающих деревьев. Алгоритм сочетает в себе две основные идеи: метод бэггинга Бреймана, и метод случайных подпространств (англ.)русск., предложенный Тин Кам Хо (англ.)русск.. Алгоритм применяется для задач классификации, регрессии и кластеризации. Основная идея заключается в использовании большого ансамбля решающих деревьев, каждое из которых само по себе даёт очень невысокое качество классификации, но за счёт их большого количества результат получается хорошим. 
"""
"""
Реализация алгоритма
"""
# Реализуем генерацию 𝑁 бутстрап-выборок и подмножества признаков для нахождения разбиения в узле.
np.random.seed(42)


def get_bootstrap(data, labels, N):
    n_samples = data.shape[0]  # размер совпадает с исходной выборкой
    bootstrap = []

    for i in range(N):
        sample_index = np.random.randint(0, n_samples, size=n_samples)
        b_data = data[sample_index]
        b_labels = labels[sample_index]

        bootstrap.append((b_data, b_labels))

    return bootstrap


def get_subsample(len_sample):
    # будем сохранять не сами признаки, а их индексы
    sample_indexes = list(range(len_sample))

    len_subsample = int(np.sqrt(len_sample))

    subsample = np.random.choice(sample_indexes, size=len_subsample, replace=False)

    return subsample


# Реализуем класс узла
class Node:

    def __init__(self, index, t, true_branch, false_branch):
        self.index = index  # индекс признака, по которому ведется сравнение с порогом в этом узле
        self.t = t  # значение порога
        self.true_branch = true_branch  # поддерево, удовлетворяющее условию в узле
        self.false_branch = false_branch  # поддерево, не удовлетворяющее условию в узле


# И класс терминального узла (листа)
class Leaf:

    def __init__(self, data, labels):
        self.data = data
        self.labels = labels
        self.prediction = self.predict()

    def predict(self):
        # подсчет количества объектов разных классов
        classes = {}  # сформируем словарь "класс: количество объектов"
        for label in self.labels:
            if label not in classes:
                classes[label] = 0
            classes[label] += 1

        # найдем класс, количество объектов которого будет максимальным в этом листе и вернем его
        prediction = max(classes, key=classes.get)
        return prediction


# Расчет критерия Джини
def gini(labels) -> float:
    #  подсчет количества объектов разных классов
    classes = {}
    for label in labels:
        if label not in classes:
            classes[label] = 0
        classes[label] += 1

    #  расчет критерия
    impurity = 1
    for label in classes:
        p = classes[label] / len(labels)
        impurity -= p ** 2

    return impurity


# Расчет прироста
def gain(left_labels, right_labels, root_gini):
    # доля выборки, ушедшая в левое поддерево
    p = float(left_labels.shape[0]) / (left_labels.shape[0] + right_labels.shape[0])

    return root_gini - p * gini(left_labels) - (1 - p) * gini(right_labels)


# Разбиение датасета в узле
def split(data, labels, column_index, t):
    left = np.where(data[:, column_index] <= t)
    right = np.where(data[:, column_index] > t)

    true_data = data[left]
    false_data = data[right]

    true_labels = labels[left]
    false_labels = labels[right]

    return true_data, false_data, true_labels, false_labels


# Нахождение наилучшего разбиения
def find_best_split(data, labels):
    #  обозначим минимальное количество объектов в узле
    min_leaf_samples = 5

    root_gini = gini(labels)

    best_gain = 0
    best_t = None
    best_index = None

    n_features = data.shape[1]

    feature_subsample_indices = get_subsample(n_features)  # выбираем случайные признаки

    for index in feature_subsample_indices:
        # будем проверять только уникальные значения признака, исключая повторения
        t_values = np.unique(data[:, index])

        for t in t_values:
            true_data, false_data, true_labels, false_labels = split(data, labels, index, t)
            current_gain = gain(true_labels, false_labels, root_gini)

            #  выбираем порог, на котором получается максимальный прирост качества
            if current_gain > best_gain:
                best_gain, best_t, best_index = current_gain, t, index

    return best_gain, best_t, best_index

# Построение дерева с помощью рекурсивной функции
def build_tree(data, labels):

    gain, t, index = find_best_split(data, labels)

    #  Базовый случай - прекращаем рекурсию, когда нет прироста в качества
    if gain == 0:
        return Leaf(data, labels)

    true_data, false_data, true_labels, false_labels = split(data, labels, index, t)

    # Рекурсивно строим два поддерева
    true_branch = build_tree(true_data, true_labels)
    false_branch = build_tree(false_data, false_labels)

    # Возвращаем класс узла со всеми поддеревьями, то есть целого дерева
    return Node(index, t, true_branch, false_branch)

# Теперь добавим функцию формирования случайного леса.
def random_forest(data, labels, n_trees):
    forest = []
    bootstrap = get_bootstrap(data, labels, n_trees)

    for b_data, b_labels in bootstrap:
        forest.append(build_tree(b_data, b_labels))

    return forest

# Функция классификации отдельного объекта
def classify_object(obj, node):

    #  Останавливаем рекурсию, если достигли листа
    if isinstance(node, Leaf):
        answer = node.prediction
        return answer

    if obj[node.index] <= node.t:
        return classify_object(obj, node.true_branch)
    else:
        return classify_object(obj, node.false_branch)


# функция формирования предсказания по выборке на одном дереве
def predict(data, tree):
    classes = []
    for obj in data:
        prediction = classify_object(obj, tree)
        classes.append(prediction)
    return classes


# предсказание голосованием деревьев
def tree_vote(forest, data):
    # добавим предсказания всех деревьев в список
    predictions = []
    for tree in forest:
        predictions.append(predict(data, tree))
        
    # сформируем список с предсказаниями для каждого объекта
    predictions_per_object = list(zip(*predictions))

    # выберем в качестве итогового предсказания вероятности для каждого объекта отношение количества объектов 1 класса ко всем объектам
    voted_predictions = []
    for obj in predictions_per_object:
        # voted_predictions.append(max(set(obj), key=obj.count))
        unique = dict(zip(list(obj), [list(obj).count(i) for i in list(obj)]))
        if unique.get(1) is None:
            unique[1] = 0
        if unique.get(0) is None:
            unique[0] = 0
        voted_predictions.append(unique[1] / (unique[1]+unique[0]))

    return voted_predictions


# Введем функцию подсчета точности как доли правильных ответов
def accuracy_metric(actual, predicted):
    correct = 0
    for i in range(len(actual)):
        if actual[i] == predicted[i]:
            correct += 1
    return correct / float(len(actual)) * 100.0
# Число деревьев в случайном лесу выведено экспериментальным путем
# Лучшие метрики:
# Точность случайного леса из 9 деревьев на обучающей выборке: 95.057
# Точность случайного леса из 9 деревьев на тестовой выборке: 89.567

# Удалили Id
# Точность случайного леса из 7 деревьев на обучающей выборке: 94.471
# Точность случайного леса из 7 деревьев на тестовой выборке: 89.067

# Введем фичу index_qualification
# Точность случайного леса из 9 деревьев на обучающей выборке: 95.286
# Точность случайного леса из 9 деревьев на тестовой выборке: 89.300

# Добавили фичу index_experience
# Точность случайного леса из 9 деревьев на обучающей выборке: 97.843
# Точность случайного леса из 9 деревьев на тестовой выборке: 88.700

n_trees = 9

my_forest = random_forest(X, y, n_trees)

# Получим ответы для обучающей выборки
# train_answers = tree_vote(my_forest, X)

# И получим вероятности для финальной выборки
y_RandomForest = tree_vote(my_forest, TEST)
"""
Записываем результат
"""
SAMPLE_SUBMISSION.choose = y_RandomForest
SAMPLE_SUBMISSION.to_csv('submit.csv', index=False)