Ensemble Learning - Bagging, RandomForest

Ensemble Learning이란?

• 모형 결합(model combining)방법은 앙상블 방법론(ensemble methods)라고도 한다. 이는 특정한 하나의 예측 방법이 아니라 복수의 예측모형을 결합하여 더 나은 성능의 예측을 하려는 시도이다.

• 모형 결합 방법을 사용하면 일반적으로 계산량은 증가하지만 다음과 같은 효과가 있다.

  • 단일 모형을 사용할 때 보다 성능 분산이 감소하기에 과최적화(overfitting)을 방지한다.
  • 개별 모형이 성능이 안좋을 경우에는 결합 모형의 성능이 더 향상된다.

• Ensemble Learning은 캐글이나 다른 대회에서 높은 성능을 자랑하며 여러 차례 우승을 차지한 알고리즘으로 그만큼 강력하지만, 현업에서는 Ensemble Learning을 사용하지 않을 가능성이 매우 높다. 왜냐하면 굉장히 강력하지만 다른 모델들과의 성능차이가 엄청나게 차이나는 것이 아니며, 실제 Domain에서 중요한 변수가 무엇인지와 같은 원인을 찾는 feature selection 부분이 더 중요할 수 있기 때문이다. 물론, 성능측면이 중요한 Domain분야에서는 Ensemble Learning이 중요할 것이다.

• Ensemble이라는 의미의 사전적 정의는 ‘합창단’, ‘조화’라는 의미를 지닌다. 즉, 머신러닝에서의 개념은 여러개의 모델을 조합을 시킨다라는 의미로 받아들일 수 있다.

• 통계학에서의 대수의 법칙이라는 개념이 있는데, 큰 모집단에서 무작위로 뽑은 표본의 수가 많아 질수록(보통은 30개이상의 관측이) 모집단의 평균에 가까울 확률이 높아진다는 개념이다. 많은 시행의 결과가 수학적으로 합리적인 결과를 보여준다는 것을 의미하는데, Ensemble learning에 적용하여 생각해보면 다수의 모델이 더 합리적인 성능을 가져올 수 있다는 것으로 해석할 수도 있다.

• 하지만 아래에서 합치는 모델의 성능 자체가 떨어지는 모델을 가지고 Ensemble learning을 진행한다고 해도 성능을 올릴 수는 없다.

• 아래에서는 이진분류에 대해서만 언급했지만, 대부분의 classification 문제에서는 One VS Rest 방식으로 문제를 풀기에 이진 분류 뿐만아니라, class가 여러개인 multi class 문제에서도 적용되는 내용이다.

• 아래에서와 같이 각각의 성능이 0.5인 분류기들을 voting을 통해 결과를 내게 되는데, 각각의 weak한 분류기들의 조합을 통해 최종적으로는 0.625라는 성능을 내게 된다.

• 다수결 모형이 개별 모형보다 더 나은 성능을 보이는 이유는 다음 실험에서도 확인 할 수 있다. 만약 개별 모형이 정답을 출력할 확률이 $p$인 경우에 서로 다르고 독립적인 모형 $N$개를 모아서 다수결 모형을 만들면 정답을 출력할 확률이 다음과 같아진다.

$$\sum_{k>\frac{N}{2}}^N \binom N k p^k (1-p)^{N-k}$$

def total_error(p, N):
    te = 0.0
    for k in range(int(np.ceil(N/2)), N + 1):
        te += sp.misc.comb(N, k) * p**k * (1-p)**(N-k)
    return te


x = np.linspace(0, 1, 100)
plt.plot(x, x, 'g:', lw=3, label="개별 모형")
plt.plot(x, total_error(x, 10), 'b-', label="다수결 모형 (N=10)")
plt.plot(x, total_error(x, 100), 'r-', label="다수결 모형 (N=100)")
plt.xlabel("개별 모형의 성능")
plt.ylabel("다수결 모형의 성능")
plt.legend(loc=0)
plt.show()

• 각각의 분류기(모델)를 통해 최종적으로는 해당 데이터들의 decision boundary의 평균을 사용하는 것과 동일한 결과를 얻을 수 있다.

• 아래에서와 같이 Test data에 대해 일정부분 bias되는 부분을 줄이기 위해 overfitting이 잘 되는 트리기반의 모형을 주로 베이스 모델로 사용한다.

• Ensemble Learning의 종류는 아래 그림과 같이 나눌 수 있다. 쉽게 말하면 Bagging은 여러 개의 모델을 만들기 위해서는 Tree기반이나 선형회귀 분석 같은 경우는 동일한 feature와 동일한 data를 사용했을 경우 동일한 결과를 내주기 때문에, 모델을 여러 개 만들기 위해서 데이터를 나누어서 각 모델에 fitting시키는 것을 의미한다. Random Forest는 데이터 뿐만 아니라 feature들의 선택도 각 모델별로 달리하여 fitting하는 것이며, Boosting은 분류기가 틀리게 예측한 데이터들에 대해 그 다음 학습기는 좀 더 학습을 잘 할 수 있도록 가중치를 주는 개념이다. 마지막으로 Stacking은 성능순으로 점수를 매기는 캐글에서는 0.1%라도 올리는 것이 중요하기 때문에 사용되어 지는데, 다른 Ensemble 기법들 보다 많은 성능을 높이지는 못하여 잘 사용되지는 않는다. 굉장히 많은 학습 연산량을 필요로 하기 때문에 실제 Domain에서 사용되어지기에는 쉽지 않다.

• 위에서 언급한 것과 같이 모형 결합 방법은 크게 나누어 취합(aggregation) 방법론과 부스팅(boosting)방법론으로 나눌 수 있다.
  • 취합 방법론은 사용할 모형의 집합이 이미 결정되어있다.
  • 부스팅 방법론은 사용할 모형을 점진적으로 늘려간다.

• 각 방법론의 대표적인 방법들은 아래와 같다.

  • 취합 방법론

    • 다수결(Majority Voting)
    • 배깅(Bagging)
    • 랜덤 포레스트(Random Forests)

  • 부스팅 방법론

    • 에이다부스트(AdaBoost)
    • 그레디언트 부스트(Gradient Boost)

다수결 방법(Voting)

• 다수결 방법은 가장 단순한 모형 결합 방법으로 전혀 다른 모형도 결합할 수 있다. 다수결 방법은 Hard Voting과 Soft Voting 두 가지로 나뉘어진다.
  • hard voting: 단순 투표. 개별 모형의 결과 기준
  • soft voting: 가중치 투표. 개별 모형의 조건부 확률의 합 기준
  • 일반적으로 hard voting보다는 soft voting이 예측 성능이 좋아서 더 많이 사용된다.

• Scikit-Learn의 ensemble 서브 패키지는 다수결 방법을 위한 VotingClassifier클래스를 제공한다. 입력인수는 다음과 같다.

  • estimators: 개별 모형 목록, 리스트나 named parameter 형식으로 입력
  • voting: 문자열 {hard, soft} hard voting과 soft voting 선택. 디폴트는 hard
  • weights: 사용자 가중치 리스트

• 다음과 같은 예제 데이터를 가지는 이진 분류 문제를 생각해보자.

X = np.array([[0, -0.5], [-1.5, -1.5], [1, 0.5], [-3.5, -2.5], [0, 1], [1, 1.5], [-2, -0.5]])
y = np.array([1, 1, 1, 2, 2, 2, 2])
x_new = [0, -1.5]
plt.scatter(X[y == 1, 0], X[y == 1, 1], s=100, marker='o', c='r', label="클래스 1")
plt.scatter(X[y == 2, 0], X[y == 2, 1], s=100, marker='x', c='b', label="클래스 2")
plt.scatter(x_new[0], x_new[1], s=100, marker='^', c='g', label="테스트 데이터")
plt.xlabel("x1")
plt.ylabel("x2")
plt.title("이진 분류 예제 데이터")
plt.legend()
plt.show()

• 먼저, 이 문제를 3가지 다른 방법으로 풀어볼 것이다.
  • 로지스틱 회귀모형
  • QDA 모형
  • 가우시안 나이브베이즈 모형

• 마지막으로 3가지 모형을 다수결로 합친 모형을 VotingClassifier클래스로 만들었다. 다만 3가지 모형의 가중치가 각각 1,1,2로 가우시안 나이브베이즈 모형의 가중치를 높였다.

• 결과는 다음과 같이, 로지스틱 회귀모형과 가우시안 나이브베이즈 모형은 클래스 1이라는 결과를 보이지만 QDA모형은 클래스 2라는 결과를 보였다. 소프트 방식의 다수결 모형은 클래스 2라는 결론을 보인다. 만약 하드 방식의 다수결 모형이었다면 예측 결과는 클래스 1이 될 것이다.

from sklearn.linear_model import LogisticRegression
from sklearn.naive_bayes import GaussianNB
from sklearn.discriminant_analysis import QuadraticDiscriminantAnalysis
from sklearn.ensemble import VotingClassifier

model1 = LogisticRegression(random_state=1)
model2 = QuadraticDiscriminantAnalysis()
model3 = GaussianNB()
ensemble = VotingClassifier(estimators=[('lr', model1), ('qda', model2), ('gnb', model3)], voting='soft')

probas = [c.fit(X, y).predict_proba([x_new]) for c in (model1, model2, model3, ensemble)]
class1_1 = [pr[0, 0] for pr in probas]
class2_1 = [pr[0, 1] for pr in probas]

ind = np.arange(4)
width = 0.35  # bar width
p1 = plt.bar(ind, np.hstack(([class1_1[:-1], [0]])), width, color='green')
p2 = plt.bar(ind + width, np.hstack(([class2_1[:-1], [0]])), width, color='lightgreen')
p3 = plt.bar(ind, [0, 0, 0, class1_1[-1]], width, color='blue')
p4 = plt.bar(ind + width, [0, 0, 0, class2_1[-1]], width, color='steelblue')

plt.xticks(ind + 0.5 * width, ['로지스틱 회귀 모형', 'QDA 모형', '가우시안 나이브베이즈', '소프트 다수결 모형'])
plt.ylim([0, 1.1])
plt.title('세가지 다른 분류 모형과 소프트 다수결 모형의 분류 결과')
plt.legend([p1[0], p2[0]], ['클래스 1', '클래스 2'], loc='upper left')
plt.show()

from itertools import product

x_min, x_max = -4, 2
y_min, y_max = -3, 2
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.005),
                     np.arange(y_min, y_max, 0.005))
f, axarr = plt.subplots(2, 2)
for idx, clf, tt in zip(product([0, 1], [0, 1]),
                        [model1, model2, model3, ensemble],
                        ['로지스틱 회귀', 'QDA', '가우시안 나이브베이즈', '다수결 모형']):
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    axarr[idx[0], idx[1]].contourf(xx, yy, Z, alpha=0.2, cmap=mpl.cm.jet)
    axarr[idx[0], idx[1]].scatter(
        X[:, 0], X[:, 1], c=y, alpha=0.5, s=50, cmap=mpl.cm.jet)
    axarr[idx[0], idx[1]].scatter(x_new[0], x_new[1], marker='x')
    axarr[idx[0], idx[1]].set_title(tt)
plt.tight_layout()
plt.show()

• 아래 각 모형별로 decision boundary를 살펴 보았을 경우 어떠한 생각이 드는가? 필자의 생각엔 물론 전제조건이 아래 train 데이터가 모집단의 분포를 대표할 수 있는 데이터들이라는 가정하에 soft 방식으로 한 결과는 옳지 못한 결과라고 생각한다. 2클래스로 분류되기엔 1 클래스가 많은 영역에 존재하기 때문이다. 이렇게 시각화를 통해 살펴보는 방법도 결과에 대한 검증을 위해 필요할 것이다. 허나, 다변량인 경우는 몇가지 중요한 변수들에 대해서만 시각화를 해 본다던가 아니면 해당 조합들에 대해 모두 그려보는 것도 때론 좋은 방법일 수 있을 것이다.

• 앞서 모형 결합에서 사용하는 독립적인 모형의 수가 많을 수록 성능 향상이 일어날 가능성이 높다는 것을 알았다. 각각 다른 확률 모형을 사용하는데에는 한계가 있으므로 보통은 배깅 방법을 사용하여 같은 확률 모형을 쓰지만 서로 다른 결과를 출력하는 다수의 모형을 만든다.

배깅(Bagging)

• Bagging은 Bootstrap Aggregating의 약자로 Sampling을 하는 방식이 Bootstrap방식을 사용하기 때문이다. 아래 그림에서 볼 수 있듯이 복원추출의 방식이라고 생각하면된다. 하나의 모델에 대하여 데이터를 추출할 경우 해당 모델에 들어가있는 데이터는 중복된 데이터가 있을 수 있다.(오른쪽 첫번째 데이터세트에서와 같이)

  • 같은 데이터 샘플을 중복사용(replacement)하지 않으면: Pasting
  • 같은 데이터 샘플을 중복사용(replacement)하면: Bagging
  • 데이터가 아니라 다차원 독립 변수 중 일부 차원을 선택하는 경우에는: Random Subspaces
  • 데이터 샘플과 독립 변수 차원 모두 일부만 랜덤하게 사용하면: Random Patches

• 이렇게 추출하는 데이터는 전체 데이터 중 약 63%정도만 추출을 하게 된다. 아래 첫 번째 그림에서는 밑줄이 그러진 원의 데이터는 추출되지 않는 데이터들이다. 2번째 그림은 Bootstrap size가 5라면 5개씩 12개의 데이터 set를 복원추출을 통하여 뽑는 것이다. 여기서의 $k$는 임의로 정할 수 있다.

• 위에서 언급했듯이 추출되지 않은 데이터 set이 있는 것은 학습에 활용되지 않았으므로 그대로 두면 데이터를 낭비하는 것과 동일하다. 물론 Test set을 미리 나누어 놓고 해당 Test set을 prediction한 결과를 voting하여 성능을 측정하지만, 사용되지 않은 데이터(Out-of_Bag data)에 대해서도 모델별 성능을 계산한다.

• 트리(Tree)와 배깅(Bagging)을 비교하자면 깊이 성장한 트리는 overfitting이 굉장히 심해지기 때문에 분산이 증가하기 때문에 편향은 줄어들 것이다. 그러나 배깅은 이러한 트리들을 결합시키므로 편향이 유지되며, 분사은 감소하는 모델이 될 것이다. 학습데이터의 noise에 robust하다. 그러나 모형해석이 어려워지는 단점이 있다. 이러한 단점이 실제 Domain에서 사용되지 못하는 이유가 될 수 있다.

• Scikit-Learn의 ensemble 서브 패키지는 배깅 모형 결합을 위한 BaggingClassifier 클래스를 제공한다. 사용법은 아래와 같다. 참고로 BaggingRegressor도 존재하며 사용법은 동일하다.
  • base_estimator: 기본모형
  • n_estimators: 모형 갯수. default=10
  • bootstrap: 데이터 중복 사용 여부. default=True
  • max_samples: 데이터 샘플 중 선택할 샘플의 수 혹은 비율. default=1.0
  • bootstrap_features: feature의 중복 사용 여부. default=False
  • max_features: 다차원 독립 변수 중 선택할 차원의 수 혹은 비율. default=1.0

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.svm import SVC
from sklearn.ensemble import BaggingClassifier

iris = load_iris()
X, y = iris.data[:, [0, 2]], iris.target

model1 = DecisionTreeClassifier(max_depth=10, random_state=0).fit(X, y)
model2 = BaggingClassifier(DecisionTreeClassifier(max_depth=2), n_estimators=100, random_state=0).fit(X, y)

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1), np.arange(y_min, y_max, 0.1))
plt.subplot(121)
Z1 = model1.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.contourf(xx, yy, Z1, alpha=0.6, cmap=mpl.cm.jet)
plt.scatter(X[:, 0], X[:, 1], c=y, alpha=1, s=50, cmap=mpl.cm.jet, edgecolors="k")
plt.title("개별 모형")
plt.subplot(122)
Z2 = model2.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.contourf(xx, yy, Z2, alpha=0.6, cmap=mpl.cm.jet)
plt.scatter(X[:, 0], X[:, 1], c=y, alpha=1, s=50, cmap=mpl.cm.jet, edgecolors="k")
plt.title("배깅 모형")
plt.suptitle("붓꽃 데이터의 분류 결과")
plt.tight_layout()
plt.show()

• 왼쪽은 단일 모형으로 max_depth=10으로 설정한 Decision tree의 decision boundary의 모습이다. 트리의 깊이가 깊으므로 과최적화(overfitting)이 발생되었다. 오른쪽의 그림은 max_depth=2로 설정한 Decision tree모형을 100개 결합한 배깅 모형의 decision boundary 모습이다. 물론 depth를 작게하여 기본적인 모형자체도 과최적화(overfitting)를 방지하였지만, 배깅을 함으로써 모형의 분산이 줄어들며 더 train data에 robust하게 decision boundary가 그려진것을 확인할 수 있다.

랜덤 포레스트(Random Forest)

• 아래 그림과 같이 배깅은 여러 모델들을 결합하지만 부트스트랩 방식을 사용하여 모델들간의 사용되어지는 데이터가 동일한 집합들이 있을 수 있다. 그러므로 Ensemble Learning의 개념에서 언급했었던 각 모델별 독립이라는 가정에 크게 위반되어진다. 결국 비슷한 트리가 만들어지게 되어 모델들간의 공분산이 크게 되어 모델이 많아짐에 따라 점점 전체 Ensemble 모델의 분산은 커진다는 것이다. 분산이 커진다면 편향이 감소되어 더 좋은것이 아닌가라고 생각이 들수도 있겠지만, 모델의 예측 성능의 변동폭이 너무 크게 되면(분산이 크게 되어) 그만큼 불확신성도 높아지기 때문이다. 게다가, 애초에 다양한 모델에 대한 결합을 한 Ensemble 모델을 만들려고 한 의도조차 변질되어진다.

• 랜덤포레스트(Random Forest)는 의사 결정 나무(Decision Tree)를 개별 모형으로 사용하는 모형 결합 방법을 말한다. 랜덤 포레스트는 데이터 특징차원의 일부만 선택하여 사용한다. 하지만 노드 분리시 모든 독립 변수들을 비교하여 최선의 독립 변수를 선택하는 것이 아니라 독립 변수 차원을 랜덤하게 감소시킨 다음 그 중에서 독립 변수를 선택한다. 이렇게 하면 개별 모형들 사이의 상관관계가 줄어들기 때문에 모형 성능의 변동이 감소하는 효과가 있다. 이러한 방법을 극단적으로 적용한 것이 Extremely Randomized Trees 모형으로 이 경우에는 각 노드에서 랜덤하게 독립 변수를 선택한다.

• 랜덤 포레스트와 Extremely Randomized Trees 모형은 각각 RandomForestClassifier 클래스와 ExtraTreesClassifier 클래스로 구현되어 있다.

• 랜덤 포레스트는 CPU 병렬 처리도 효과적으로 수행되어 빠른 학습이 가능하기 때문에 뒤에 소개할 그레디언트 부스팅보다 예측 성능이 약간 떨어지더라도 랜덤 포레스트로 일단 기반 모델을 먼저 구축하는 경우가 많다. 멀티 코어 환경에서는 RandomForestClassifier 생성자와 GridSearchCV 생성 시 n_jobs = -1 파라미터를 추가하면 모든 CPU 코어을 이용해 학습할 수 있다.

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.svm import SVC
from sklearn.ensemble import RandomForestClassifier

iris = load_iris()
X, y = iris.data[:, [0, 2]], iris.target

model1 = DecisionTreeClassifier(max_depth=10, random_state=0).fit(X, y)
model2 = RandomForestClassifier(max_depth=2, n_estimators=100, random_state=0).fit(X, y)

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1), np.arange(y_min, y_max, 0.1))
plt.subplot(121)
Z1 = model1.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.contourf(xx, yy, Z1, alpha=0.6, cmap=mpl.cm.jet)
plt.scatter(X[:, 0], X[:, 1], c=y, alpha=1, s=50, cmap=mpl.cm.jet, edgecolors="k")
plt.title("개별 모형")
plt.subplot(122)
Z2 = model2.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.contourf(xx, yy, Z2, alpha=0.6, cmap=mpl.cm.jet)
plt.scatter(X[:, 0], X[:, 1], c=y, alpha=1, s=50, cmap=mpl.cm.jet, edgecolors="k")
plt.title("배깅 모형")
plt.suptitle("붓꽃 데이터의 분류 결과")
plt.tight_layout()
plt.show()

• 아래 그림에서 오른쪽은 max_depth=2로 설정하고 모형의 수를 100개로 한 RandomForest 모델의 decision boundary의 시각화한 것이다.

• 랜덤 포레스트의 장점 중 하나는 각 독립 변수의 중요도(feature importance)를 계산할 수 있다는 점이다. 포레스트 안에서 사용된 모든 노드에 대해 어떤 독립 변수를 사용하였고 그 노드에서 얻은 information gain을 구할 수 있으므로 각각의 독립 변수들이 얻어낸 information gain의 평균을 비교하면 어떤 독립 변수가 중요한지를 비교할 수 있다.

from sklearn.datasets import make_classification
from sklearn.ensemble import ExtraTreesClassifier

X, y = make_classification(n_samples=1000, n_features=10, n_informative=3, n_redundant=0, n_repeated=0,
                           n_classes=2, random_state=0, shuffle=False)

forest = ExtraTreesClassifier(n_estimators=250, random_state=0)
forest.fit(X, y)

importances = forest.feature_importances_

std = np.std([tree.feature_importances_ for tree in forest.estimators_], axis=0)
indices = np.argsort(importances)[::-1]

plt.title("특성 중요도")
plt.bar(range(X.shape[1]), importances[indices],
        color="r", yerr=std[indices], align="center")
plt.xticks(range(X.shape[1]), indices)
plt.xlim([-1, X.shape[1]])
plt.show()

• 다음은 올리베티 얼굴 사진을 Extreme 랜덤 포레스트로 구한 뒤 특징(pixel) 중요도를 이미지로 나타낸 것이다.

from sklearn.datasets import fetch_olivetti_faces
from sklearn.ensemble import ExtraTreesClassifier

data = fetch_olivetti_faces()
X = data.data
y = data.target

forest = ExtraTreesClassifier(n_estimators=1000, random_state=0)
forest.fit(X, y)

importances = forest.feature_importances_
importances = importances.reshape(data.images[0].shape)

plt.figure(figsize=(8, 8))
plt.imshow(importances, cmap=plt.cm.bone_r)
plt.grid(False)
plt.title("픽셀 중요도(pixel importance)")
plt.show()