#!/usr/bin/env python
# coding: utf-8

# <center>
# <img src="../../img/ods_stickers.jpg">
# ## Открытый курс по машинному обучению
# <center>Автор материала: Измайлов Константин Константинович (@Izmajlovkonstantin).

# ##  <center>Отбор признаков с помощью алгоритма Boruta или как приручить лесного демона. <BR> </center>

# <img src="https://raw.githubusercontent.com/Twoweaks/random/master/leshyboruta12.png" width="700">

# ### 1. Введение

# Решая ту или иную задачу машинного обучения не стоит забывать одно простое правило: <I>"Garbage in - garbage out" </I>, означающее, что чем "зашумленнее" были поданы данные на входе, тем хуже будет решение задачи.
# 
# Корректный отбор признаков - один из важнейших этапов предобработки данных. Особенно критичен отбор признаков при решении задач в индустрии, когда датасаентист встречается с большим набором фичей, многие из которых не имеют отношения к решаемой проблеме.
# 
# Отбор признаков обеспечаивает следующие преимущества:
# <UL>
# <LI> уменьшение переобучения;
# <LI> повышение точности;
# <LI> сокращение времени обучения;
# <LI> сокращение затрат на поиск и обновление информации (характерно для индустрии).    
# </UL>
#     
#     

# Существуют три основных класса алгоритмов отбора признаков:
# <OL>
# <LI> <B> Фильтры </B> - применяются до классификации, не зависят от алгоритма самой модели. Признаки отбираются, как правило, основываясь на оценках статистических тестов (корреляци Пирсона, LDA, ANOVA и т.д.);
# <LI> <B> Встроенные методы </B> - выполняют отбор признаков неотделимо от процесса обучения модели (наприм. - Lasso-регрессия); 
# <LI> <B> Оберточные методы </B> - используют информацию о важности признаков, полученную от алгоритмов обучения, и затем находят сложные зависимости между ними. 
# </OL>    

# Схематичное изображение оберточного метода.
# <img src="https://raw.githubusercontent.com/Twoweaks/random/master/Wrapper_1.png" width="700">

# Одним из таких оберточных методов, который будет рассмотрен в данном туториале, будет алгоритм <B> Boruta </B>, названный в честь лесного славянского демона, реализующий адаптационный алгоритм для модели случайного леса (Kursa, Rudnicki, 2010).

# ### 2. Алгоритм Boruta

# Основная идея алгоритма заключается в сравнении исходных признаков с их теневыми копиями (англ. - shadow features) - признаками, полученными с помощью случайного перемешивания значений исходных признаков между строками. Соответственно, признаки, которые мало чем отличаются от теневых будут совершенно не важны для модели.   

# <U>Рассмотрим алгоритм пошагово:</U>
# <OL>
#     <LI> Добавить в исходный набор данных теневые копии всех признаков (обычно добавляется по 5 теневых признаков для каждого признака исходного набора данных, вне зависимости от их общего числа);
#     <LI> Обучить несколько раз алгоритм (в данном случае - случайный лес) на новом наборе данных;
#     <LI> Рассчитать важность всех признаков на каждой итерации алгоритма.
#     Важность признаков рассчитывается как дополнительная ошибки регрессии, вызванная исключением этого признака из модели. Среднее  $μ$  этой дополнительной ошибки и его стандартное отклонение $σ$ рассчитываются по всем деревьям в лесу, которые используют оцениваемый признак для прогнозирования. Мера $Z$ каждого признака рассчитывается как  $\dfrac{μ}{σ}$. Данная оценка не может использоваться напрямую для определения важности каждого из признаков модели в отдельности, так как не имеет нормального распределения. 
#         <BR>
#      <LI> Для каждого из признаков с помощью биноминального распределения подсчитывается, какая вероятность того, что $Z$-мера исходного признака будет выше $Z$-меры всех его теневых признаков. Рассчитывается уровень значимости $p$ с поправкой на множественную проверку гипотез (для алгоритма Boruta используется достаточно консервативная коррекция Бонфферони), так как такое сравнение делается для тысячи итераций;
#        <LI> Признаки, у которых веротяность $Z$-меры теневых признаков статистически значима выше вероятности $Z$-меры исходного признака считаются неважными и выбрасываются из обучаемого набора данных (зачастую со своими теневыми копиями);
#         <LI> Процедура повторяется до тех пор, пока не будет достигнут заданный набор итераций или всем признаком не будет проставлен признак важности.
# </OL>

# ### 3. Интерфейс алгоритма

# Изначально алгоритм был реализован на R, а уже затем перенесен на Python с некоторыми изменениями:
# <UL>
#     <LI> поправка на множественную проверку гипотез стала более лояльной, но осталась возможность использовать коррекцию Бонфферони (задается опционально через параметр алгоритма <I> two_step  </I>);
#     <LI> скорректировано сравнение признаков с их теневыми копиями, в новой реализации учитываются перцентили, вместо строгого количественного сравнения в оригинальном алгоритме;
#         <LI> в том числе оптимизирована работа алгоритма, увеличено его бытсродействие и стабильность, добавлена совместимость с любым ансамблевым методом из sklearn.
#     </UL>

# <U> Параметры алгоритма: </U>
# <B>estimator</B> : object 
# <B>n_estimators </B> : int or string, default = 1000 
# <B>perc</B> : int, default = 100 
# <B>alpha </B> : float, default = 0.05 
# <B>two_step </B>  : Boolean, default = True 
# <B>max_iter</B>  : int, default = 100 
# <B>verbose </B>  : int, default=0 
# 
# Более подробно о параметрах и атрибутах можно прочитать [тут](https://github.com/scikit-learn-contrib/boruta_py).

# ### 4. Пример реализации

# Применять алгоритм Boruta будем на публичном датасете <I>  Breast Cancer Wisconsin (Diagnostic) Data Set </I> представляющий собой проблему классификации, где по характеристикам опухоли в женской груди необходимо определить, является ли опухоль доброкачественной (benign) либо злокачественной (malignant). 

# In[1]:


# импортируем необходимые библиотеки
import warnings
warnings.filterwarnings('ignore')
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
from boruta import BorutaPy
import numpy as np
from sklearn.model_selection import StratifiedKFold
from sklearn.metrics import roc_auc_score

#загружаем сам датасет
from sklearn.datasets import load_breast_cancer
data = load_breast_cancer()

df = pd.DataFrame(np.c_[data['data'], data['target']],
                  columns= np.append(data['feature_names'], ['target']))


# In[2]:


df.head()


# Датасет состоит из 30 признаков и одного целевого признака. О значении большинства признаков остается лишь догадываться, тем более определить их значимость, датасаентисту, не разбирающемуся в медицине, не представляется возможным.

# In[3]:


print('Доля меток с злокачественной опухолью - {}.'.format(np.round(df[df.target == 1].shape[0]/df.shape[0],2)))


# Валидировать алгоритм будем на 3 фолдах, в качестве метрики будем использовать ROC AUC score.

# In[4]:


X = df.iloc[:,:-1]
y = df['target']

def validation(ensemble, X, y, n_folds = 3):
    rocs = []
    skf = StratifiedKFold(n_splits=n_folds)
    for train, test in skf.split(X, y):
        X_train, X_test = X.loc[train,:], X.loc[test,:]
        y_train, y_test = y[train],y[test]
        ensemble.fit(X_train,y_train)      
        rocs.append(roc_auc_score(y_test,ensemble.predict_proba(X_test)[:,1]))
    return np.mean(rocs)


# Воспользуемся коробочным решением алгоритма и посмотрим на результат.

# In[5]:


clf = RandomForestClassifier(n_estimators=500,max_depth=3, random_state=10)
print('ROC AUC SCORE - {}.'.format(validation(clf, X, y)))


# Коробочное решение алгоритма справляется уже неплохо, попробуем призвать нашего лесного демона, может, он сможет улучшить наш алгоритм. При этом, попробуем добавить в данные немного шума, посмотрим, сможет ли Boruta найти их. 

# In[6]:


X_with_noise = X.copy()
X_with_noise['random_noise_0'] = np.random.random( X_with_noise.shape[0])
X_with_noise['random_noise_1'] = np.random.random( X_with_noise.shape[0])
X_with_noise['random_noise_2'] = np.random.random( X_with_noise.shape[0])
X_with_noise['random_noise_3'] = np.random.random( X_with_noise.shape[0])

feat_selector = BorutaPy(clf, n_estimators='auto', verbose=2, random_state=17, max_iter=50)
feat_selector.fit(X_with_noise.values, y)


# Уже на 8 итерации Boruta определил 4 добавленных шумовых признака. В том числе, для некоторых признаков исходного датасета была поставлена метка <I>Tentative</I>, то есть алгоритм не совсем уверен, являются ли данные метки важными для предсказания или нет. 
# 
# Определим, что это за признаки и попробуем обучить алгоритм без них.

# In[7]:


# Неважные для обучения признаки
X_with_noise.columns[np.where(feat_selector.ranking_ !=1)]


# In[8]:


X_important = X.iloc[:,np.where(feat_selector.ranking_ ==1)[0]]
clf = RandomForestClassifier(n_estimators=500,max_depth=3, random_state=10)
print('ROC AUC SCORE - {}.'.format(validation(clf, X_important, y)))


# Качество алгоритма улучшилось! А значит, наш лесной демон выполнил свою работу и может отправляться обратно в лес.

# ### 5. Заключение

# Хоть и в данном примере Boruta отработал на отлично, и с его помощью удалось улучшить качество алгоритма, но это не всегда так. В любом случае, попробовать использовать алгоритм стоит.
# 
# Стоит отметить, что у алгоритма есть небольшой баг, который автор еще не устранил:
# в том случае, если по завершению всех итераций алгоритма Boruta не нашёл ни одного неважного признака (Rejected = 0) вылетает ошибка <B>"iteration over a 0-d array"</B>. До выхода нового апдейта модуля для корректной работы алгоритма можно добавлять колонку констант, которая будет наверняка принята алгоритмом как rejected и не спровоцирует вышеобознаечнную ошибку. 
# 
# По личному опыту скажу, что Boruta хорошо заходит в задачах с генерацией большого количества искусственных признаков: в задачах кредитного скоринга, но не стоит забывать, что работа алгоритма может занять много времени в зависимости от объема данных. 
# 
# Также в сети появилась новая улучшенная версия Boruta, реализованная на всеми любимом XGBoost. Прочитать про нее можно [тут](https://github.com/chasedehan/BoostARoota).
# 
# На последок, желаю всем успехов в тренировки своих демонов, надеюсь данный туториал был вам полезен!

# <img src="https://raw.githubusercontent.com/Twoweaks/random/master/i_006.png" width="400">