機械学習——ランダム森林(RF)アルゴリズム


ランダム森林定義


ランダム森林は比較的新しい機械学習モデルである.古典的な機械学習モデルはニューラルネットワークであり、半世紀以上の歴史がある.ニューラルネットワークの予測は正確だが,計算量は大きい.1980年代にBreimanらが分類ツリーのアルゴリズム(Breiman et al.1984)を発明し,二分データを繰り返して分類または回帰することで計算量が大幅に減少した.2001年にBreimanは分類木をランダム森林(Breiman 2001 a)に組み合わせた.すなわち、データセットのサンプリングにより複数の異なるデータセットを生成し、各データセット上で1つの分類木を訓練し、最終的に各分類木の予測結果と結びつけてランダム森林の事前測定結果とした.ランダム森林は演算量が著しく向上しないことを前提に予測精度を向上させた.ランダム森林は多重公線性に敏感ではなく,結果は欠落したデータと非平衡のデータに対して比較的安定であり,数千個の解釈変数の役割をうまく予測でき(Breiman 2001 b),現在の最良のアルゴリズムの一つと誉められている(Iverson et al.2008).
ランダム森林はその名の通り、ランダムな方法で森林を構築し、森林の中には多くの決定木が構成されており、ランダム森林の各決定木の間には関連がない.森を得た後、新しい入力サンプルが入ったとき、森の中の各決定木にそれぞれ判断させ、このサンプルがどのクラスに属するべきか(分類アルゴリズムの場合)を見て、どのクラスが最も多く選択されているかを見て、このサンプルがそのクラスであると予測させます.ランダムフォレストは、ID 3アルゴリズムのような属性が離散値である量を処理してもよいし、C 4のような属性が連続値である量を処理してもよい.5アルゴリズム.また,ランダム森林は,監視なし学習クラスタリングや異常点検出にも用いることができる.

ランダム森林の構築プロセス:


1.N個のサンプルがある場合、戻されたN個のサンプルがランダムに選択される(ランダムに1個のサンプルを選択した後、選択を続行する).この選択されたN個のサンプルは、決定ツリーのルートノードにおけるサンプルとして決定ツリーを訓練するために使用される.
2.各サンプルにM個の属性がある場合、決定ツリーの各ノードが分裂する必要がある場合、ランダムにこのM個の属性からm個の属性を選択し、条件m<3.決定木の形成過程において各ノードはステップ2に従って分裂しなければならない(次のノードが選択した属性が親ノードが分裂したばかりのときに使用した属性である場合、ノードはすでにリーフノードに達しており、分裂を続ける必要はないことは理解しやすい).これ以上分裂できないまで.決定ツリーの形成過程全体で剪定が行われていないことに注意してください.
4.手順1~3に従って大量の意思決定木を作り、ランダムな森を構成する.
各決定ツリーを構築する過程で、サンプリングと完全な分裂に注意する必要がある2つの点があります.
まず2つのランダムサンプリングのプロセスであり、random forestは入力したデータに対して行、列のサンプリングを行う.ラインサンプリングの場合、サンプリングされたサンプルのセットに重複するサンプルがある可能性があるという戻り方が採用される.入力サンプルがN個であると仮定すると、サンプリングサンプルもN個である.これにより、トレーニング時に各ツリーの入力サンプルがすべてのサンプルではなく、over-fittingが比較的容易に現れない.次にカラムサンプリングを行い、M個のfeatureからm個(m<その後,サンプリング後のデータに対して完全分裂方式を用いて決定ツリーを構築し,決定ツリーのある葉ノードが分裂を続けることができないか,中のすべてのサンプルが同じ分類を指しているかのいずれかである.一般的に多くの決定ツリーアルゴリズムは重要なステップである枝切りであるが,ここではそうではなく,以前の2つのランダムサンプリングの過程がランダム性を保証しているため,枝切りをしなくてもover−fittingは現れない.
次に,コードでランダム森林を実現する方法について述べる.
コード実装プロセス:
(1)ファイルをインポートし、すべてのフィーチャーをfloat形式に変換する
(2)データセットをn部に分割し、クロス検証を容易にする
(3)データサブセットを構築(ランダムサンプリング)し、指定された特徴個数(m個を仮定し、手動パラメータ調整)で最適な特徴を選択する
(4)決定木の構築
(5)ランダム森林の作成(複数の決定木の結合)
(6)テストセットを入力してテストを行い、予測結果を出力する
 
(1)ファイルをインポートし、すべてのフィーチャーをfloat形式に変換する
#    
def loadCSV(filename):
    dataSet=[]
    with open(filename,'r') as file:
        csvReader=csv.reader(file)
        for line in csvReader:
            dataSet.append(line)
    return dataSet
 
#     ,       float  
def column_to_float(dataSet):
    featLen=len(dataSet[0])-1
    for data in dataSet:
        for column in range(featLen):
            data[column]=float(data[column].strip())

(2)データセットをn部に分割し、クロス検証を容易にする

#      N ,      
def spiltDataSet(dataSet,n_folds):
    fold_size=int(len(dataSet)/n_folds)
    dataSet_copy=list(dataSet)
    dataSet_spilt=[]
    for i in range(n_folds):
        fold=[]
        while len(fold) < fold_size:   #     if,if            ,while    ,       
            index=randrange(len(dataSet_copy))
            fold.append(dataSet_copy.pop(index))  #pop()               (        ),         。
        dataSet_spilt.append(fold)
    return dataSet_spilt

(3)データサブセットを構築(ランダムサンプリング)し、指定された特徴個数(m個を仮定し、手動パラメータ調整)で最適な特徴を選択する
#      
def get_subsample(dataSet,ratio):
    subdataSet=[]
    lenSubdata=round(len(dataSet)*ratio)
    while len(subdataSet) < lenSubdata:
        index=randrange(len(dataSet)-1)
        subdataSet.append(dataSet[index])
    #print len(subdataSet)
    return subdataSet
 
#     n   ,  n    ,          
def get_best_spilt(dataSet,n_features):
    features=[]
    class_values=list(set(row[-1] for row in dataSet))
    b_index,b_value,b_loss,b_left,b_right=999,999,999,None,None
    while len(features) < n_features:
        index=randrange(len(dataSet[0])-1)
        if index not in features:
            features.append(index)
    #print 'features:',features
    for index in features:
        for row in dataSet:
            left,right=data_spilt(dataSet,index,row[index])
            loss=spilt_loss(left,right,class_values)
            if loss < b_loss:
                b_index,b_value,b_loss,b_left,b_right=index,row[index],loss,left,right
    #print b_loss
    #print type(b_index)
    return {'index':b_index,'value':b_value,'left':b_left,'right':b_right}

(4)決定木の構築

#     
def build_tree(dataSet,n_features,max_depth,min_size):
    root=get_best_spilt(dataSet,n_features)
    sub_spilt(root,n_features,max_depth,min_size,1) 
    return root
(5)      (        )
#      
def random_forest(train,test,ratio,n_feature,max_depth,min_size,n_trees):
    trees=[]
    for i in range(n_trees):
        subTrain=get_subsample(train,ratio)
        tree=build_tree(subTrain,n_features,max_depth,min_size)
        #print 'tree %d: '%i,tree
        trees.append(tree)
    #predict_values = [predict(trees,row) for row in test]
    predict_values = [bagging_predict(trees, row) for row in test]
    return predict_values

(6)テストセットを入力してテストを行い、予測結果を出力する
#       
def predict(tree,row):
    predictions=[]
    if row[tree['index']] < tree['value']:
        if isinstance(tree['left'],dict):
            return predict(tree['left'],row)
        else:
            return tree['left']
    else:
        if isinstance(tree['right'],dict):
            return predict(tree['right'],row)
        else:
            return tree['right']
   # predictions=set(predictions)

上記のコードのまとめ:
トレーニングセクション:datasetのm個のfeatureを取得して決定ツリーを構築すると仮定します.まず、m個のfeatureの各featureを遍歴し、各行を遍歴し、spilt_を通じてloss関数(分割代価の計算)は、最適な特徴および特徴値を選択し、この特徴値より大きいか否かに基づいて分類(left,rightの2種類に分類)し、上記ステップを不可分または再帰限界値(オーバーフィット防止のため)に達するまで繰り返し実行し、最後に決定ツリーtreeを得る.
テストセクション:テストセットの各行を判断し、決定ツリーtreeは多層辞書であり、各層は2分類であり、各行を決定ツリーtreeの分類インデックスindexに従って一歩一歩奥層に探索し、辞書が現れないまで探索が終了し、得られた値は私たちの予測値である.