[PYTHON] [Apprentissage automatique] OOB (Out-Of-Bag) et son ratio

OOB (Out-Of-Bag), qui est souvent rencontré lors de la lecture de l'explication sur la forêt aléatoire, sera expliqué en détail.

Échantillonnage bootstrap

En autorisant les doublons à partir des échantillons d'entraînement $ N $ $ \ {\ boldsymbol {x} _i, y_i \} _ {i = 1} ^ N $ et en sélectionnant au hasard le même nombre de $ N $ , La méthode de création d'un ensemble d'échantillons d'apprentissage est appelée échantillonnage bootstrap. Random Forest est nommé "Forest" car il crée de nombreux arbres de décision avec $ M $ d'échantillons d'apprentissage réalisés par cet échantillonnage bootstrap.

À ce stade, $ N $ est sélectionné parmi $ N $ avec des doublons, de sorte que certaines données peuvent ne pas être sélectionnées. Cela s'appelle OOB (Out-Of-Bag). Utilisé pour évaluer les erreurs de forêt aléatoires (comme here) $ i $ th data $ (\ boldsymbol { Se concentrer sur x} _i, y_i) $, $ M $ n'est pas utilisé dans certains de cet ensemble d'échantillons. Par conséquent, le taux d'erreur OOB est de collecter uniquement les arbres inutilisés pour former un sous-arbre et évaluer la précision.

Quant au montant de ce OOB, il semble qu'environ 36% des échantillons ne seront pas utilisés lors de la fabrication d'un échantillon, est-ce vrai? Découvrons-le.

Essayez-le avec une simulation

Le résultat de la sélection aléatoire de 100 à partir de 100 données a été répété 12 fois, et chacune a été comptée et un graphique à barres a été dessiné ci-dessous. Le titre de chaque graphique indique le nombre de données non sélectionnées, c'est-à-dire le nombre d'OOB. On peut dire que le nombre est environ au milieu de 30. Le nombre moyen d'OOB pour 12 était d'environ 34,83. Certainement environ 30%.

Python

rd.seed(71)
n_data = 100
result = np.zeros((12, n_data))

OOBs = []
plt.figure(figsize=(16,8))
for i in range(12):
    ax = plt.subplot(4,3,i+1)
    result[i] = rd.randint(1,n_data+1, n_data)
    res = plt.hist(result[i], bins=range(1,n_data+1))
    cnt = Counter(res[0])
    plt.title("# of OOB = {}".format(cnt[0]))
    OOBs.append(cnts[0])
    plt.xlim(0, n_data)
     
plt.tight_layout() 
print("Average of OOB = {}".format(np.mean(OOBs)))

Pensez théoriquement

Considérez la probabilité qu'un échantillon $ \ boldsymbol {x} _i $ ne soit pas choisi. Puisqu'il y a $ N $ au total, le fait que les données auxquelles vous faites actuellement attention ne soient pas sélectionnées est le même que $ N-1 $, qui est le nombre de données moins l'une des vôtres, donc la probabilité est

\left( { N-1 \over N} \right)

est. Maintenant que nous sélectionnons des échantillons $ N $, nous allons échantillonner à partir de $ N $ fois les ensembles de données, nous allons donc multiplier par $ N $.

\left( { N-1 \over N} \right)^{N} = \left( 1-{ 1 \over N} \right)^{N}

Si vous calculez cela, en fait, si vous augmentez $ N $, ce sera d'environ 36%. Faisons le.

Python

res_list = []
for i in range(6):
    n_data = 10**i
    result = (((n_data-1)/n_data)**n_data)*n_data 
    res_list.append([n_data,  result, result/n_data])
df = pd.DataFrame(res_list)
print( tabulate(df, ["Le nombre de données", "Nombre de colonnes non sélectionné" , "Tarif non choisi"], tablefmt="pipe"))

Il semble qu'il ait convergé à environ 36% correctement: kissing_heart:

Relation avec le nombre de Napier e

** @nykergoto nous a appris la relation avec le nombre de Napiers. Je vous remercie! ** **

Au fait, cette probabilité,

\left( 1-{ 1 \over N} \right)^{N}

Définition du nombre de Napiers $ e $,

\lim_{n \rightarrow \infty} \left( 1 + { 1 \over N} \right)^{N}

C'est similaire à Si vous convertissez la variable en $ t = N-1 $ ici

\left( { N-1 \over N} \right)^{N} = \left( { t \over t+1} \right)^{t+1} = \left( { t+1 \over t} \right)^{-(t+1)} = \left( 1 + { 1 \over t} \right)^{-(t+1)} = \left( \left( 1 + { 1 \over t} \right)^{t+1} \right)^{-1}

Si ce $ t $ est $ t \ rightarrow \ infty $, à partir de la définition du nombre de napiers

\lim_{n \rightarrow \infty}  \left( \left( 1 + { 1 \over t} \right)^{t+1} \right)^{-1} = e^{-1}

Le rapport de OOB, qui est la partie non sélectionnée de l'échantillon bootstrap, était l'inverse du nombre de Napiers!

Quand je le calcule, c'est certainement environ 36%!

Python

np.e**-1

out

0.36787944117144233

référence

Code Python pour cet article (GitHub) 　https://github.com/matsuken92/Qiita_Contents/blob/master/General/OOB-test.ipynb

Scikit-Learn OOB Errors for Random Forests 　http://scikit-learn.org/stable/auto_examples/ensemble/plot_ensemble_oob.html