[EM] 배깅(Bagging) 이론
안녕하세요 MySAS 홍보대사 한노아입니다.
오늘은 앙상블 방법 중 “데이터를 조조절하는 방법”의 가장 대표적인 예 중 하나인 배깅(Bagging)방법의 이론적 배경에 대해 알아보도록 하겠습니다.
배깅(Bagging) 개요
Bootstrap aggregating의 준말로 훈련용 데이터 집합으로부터 크기가 같은 표본을 여러 번 단순확률 반복추출 하여 각각에 대해 분류기를 생성하고, 이렇게 생성된 분류기들의 결과를 종합하여 의사결정을 내리는 방법을 말합니다.
*단순확률 반복추출을 Bootstrap Sampling이라고도합니다.
흐름도(Flow Chart)
위 흐름도표를 보면 알 수 있 듯 Bagging은 훈련용(Train) 데이터에서 Bootstrap Sampling을 통해 N개의 부분 데이터셋(Sub dataset)을 생성하여 각각에 대해 학습알고리즘(Learning Algorithm)을 적용해 분류기Classifier)를 생성하는 방법입니다. 그리고 이렇게 생성 된 분류기에 사전에 별도로 나눠 놓았던 평가용(Test) 데이터를 이용하여 모형을 평가하게 됩니다.
의사결정 방법
위 흐름도(Flow Chart)에서는 투표(Voting)방법만을 명시해 두었지만 일반적으로 연속형 종속변수에 대해서는 예측치의 평균을 이용하고, 범주형 종속변수에 대해서는 각 분류기의 사후확률의 평균 또는 분류결과의 투표(Voting)방법을 통해 집단을 결정하게 됩니다.
Out-of-Bag(OOB)
배깅의 경우 반복추출 방법을 사용하기 때문에 같은 표본이 한 데이터에서 여러 번 추출될 수 있다는 특징 존재합니다. 또한 이러한 성질 때문에 한번도 추출되지 않는 데이터 역시 존재하게 되고 이러한 표본들을 OOB(Out-Of-Bag)샘플이라고 별도로 명명하기도 합니다.
N개의 관측치가 존재하는 데이터에서 여기서 N개의 표본을 단순확률 반복추출 하게 될 경우 각 데이터가 뽑힐 확률은 이론적으로 아래와 같습니다.
이때 N이 충분히 크다면 위 식은 아래와 같은 상수값으로 수렴하게 됩니다.
따라서 N, 즉 표본의 수가 충분히 크다면 전체의 약 36.8%의 표본은 추출되지 않는 것을 알 수 있습니다. 이렇게 해당 분류기를 생성하는 데에 참여하지 않은 샘플 즉 OOB 샘플을 활용하여 각 분류모형에 대한 의사결정 가중치를 조정하기도 하고, 분류모형의 오분류율을 추정하는 등 다양한 용도 이용되기도 합니다.
배깅 알고리즘(Bagging Algorithm)
위 표는 배깅 알고리즘에 대한 의사코드입니다. 보시는 바와 같이 우선 부트스트랩 표본의 수(학습시킬 분류기의 수와 동일함)와 각 분류기에 학습에 이용할 표본의 크기를 결정합니다.
그 다음 k=1 부터 K까지 크기가 n인 부스트랩 표본 Dk생성하고, 생성된 표본 데이터에 대해 분류기를 각각 생성합니다. 이 과정을 사전에 설정한 K(총 분류기의 수)번 반복합니다.
그렇게 생성된 분류기들의 분류결과를 Ck(x)라고 할 때 이들의 결과들의 최대 빈발 분류결과를 전체 모형의 예측결과로 설정합니다. 그리고 그것을 C*(x)라고 부릅니다.
알고리즘 상으로는 내용이 복잡해 보이지만 알고리즘의 내용 역시 사전에 흐름도에서 살펴본 내용과 동일한 것을 알 수 있습니다.
마치며
오늘은 배깅 알고리즘에 대해 알아보았습니다. 기존 앙상블의 개념과 배깅 알고리즘의 가장 큰 차이는 학습데이터를 조정하여 각 모형의 독립성을 확보하려고 노력했다는 것입니다. 즉, 부트스트랩 샘플링을 통해 각 학습모형이 서로 다르게 학습되어 결과적으로 각각의 분류기가 상호 독립적인 방법으로 평가용 데이터에 대한 의사결정 결과를 내놓고 이 결과를 종합하여 더 좋은 의결정을 할 수 있게 되게 한 것입니다.
다음 시간에는 E-miner에서 배깅 알고리즘을 구연하는 두 가지 방법에 대해 알아보고, 실습데이터를 이용해 이를 직접 실습해 보도록 하겠습니다.
Reference
[1] R, SAS, MS-SQL을 활용한 데이터 마이닝 / 자유아카데미 / 이정진 지음
[2] Breiman, L. 1996. “Bagging Predictors.” Machine Learning 24: 123–140.
[3] https://support.sas.com/resources/papers/proceedings14/SAS133-2014.pdf
[4] https://www.stat.berkeley.edu/~breiman/OOBestimation.pdf
