회프딩 트리 알고리즘이란?
회프딩 트리(Hoeffding Tree) 알고리즘은 스트림 데이터(stream data) 분류를 위해 고안된 의사결정 트리 학습 방법입니다. 처음에는 웹 클릭스트림(clickstream)을 추적하고, 사용자가 어떤 웹 호스트나 웹 사이트에 접속할 가능성이 높은지 예측하는 모델을 구축하는 데 활용되었습니다.
이 알고리즘은 일반적으로 선형 미만(sublinear) 시간 안에 실행되며, 전통적인 배치(batch) 학습 방법이 생성하는 것과 거의 동일한 의사결정 트리를 만들어낸다는 점에서 큰 강점을 가집니다.
핵심 아이디어: 작은 샘플로도 충분하다
회프딩 트리는 "작은 샘플만으로도 최적의 분할(splitting) 속성을 선택하기에 충분한 경우가 많다"는 아이디어를 활용합니다. 이 아이디어는 수학적으로 회프딩 바운드(Hoeffding bound), 즉 가법 체르노프 바운드(additive Chernoff bound)에 의해 뒷받침됩니다.
회프딩 바운드의 수학적 원리
범위가 R인 확률 변수 r(여기서 r은 속성 선택 측도입니다)에 대해 N번의 독립적인 관측을 수행했다고 가정해 보겠습니다. 확률 값이라면 R은 1이 되고, 정보 획득량(information gain)이라면 R은 log c(c는 클래스의 수)가 됩니다. 회프딩 트리에서 r은 정보 획득량입니다.
이 샘플의 평균을 r′라고 할 때, 회프딩 바운드는 사용자가 지정한 δ에 대해 참 평균(true mean)이 최소 r′ − ε 이상일 확률이 1 − δ임을 보장하며, ε은 다음과 같이 계산됩니다.
$$\varepsilon=\sqrt{\frac{R^{2}ln\frac{1}{\delta}}{2N}} $$
왜 회프딩 바운드인가?
회프딩 트리 알고리즘은 회프딩 바운드를 이용해, 노드에서 분할 속성을 선택할 때 필요한 최소 예제 수 N을 높은 확률로 결정합니다. 대부분의 다른 바운드 식과 달리 회프딩 바운드는 확률 분포에 독립적이라는 특징이 있습니다. 사용하는 속성 선택 측도가 정보 획득량이든 그 밖의 것이든, 그 확률 분포를 사전에 알 수 없는 경우가 많기 때문에 이러한 특성은 매우 유용합니다.
알고리즘의 입력과 동작 과정
알고리즘은 속성 A로 기술된 학습 예제 시퀀스 S와 정확도 파라미터 δ를 입력으로 받습니다. 또한 평가 함수 G(Ai)가 제공되는데, 이는 정보 획득량(information gain), 획득 비율(gain ratio), 지니 지수(Gini index) 등 다양한 속성 선택 측도가 될 수 있습니다.
의사결정 트리의 각 노드에서는 남아 있는 속성 중 하나인 Ai에 대해 G(Ai)를 최대화해야 합니다. 궁극적인 목표는 회프딩 바운드를 만족하는 가장 작은 튜플(tuple) 수 N을 찾는 것입니다.
특정 노드에서 G 값이 가장 높은 속성을 Aa, 두 번째로 높은 속성을 Ab라고 하겠습니다. 계산된 ε에 대해 G(Aa) − G(Ab) > ε 조건이 충족되면, 해당 노드에서 Aa를 분할 속성으로 선택할 수 있습니다.
메모리 요구량
회프딩 트리 알고리즘에서 유지해야 하는 통계는 오직 카운트 nijk, 즉 속성 Ai의 값 vj와 클래스 레이블 yk의 조합별 개수뿐입니다. 따라서 d를 속성의 수, v를 임의의 속성이 가질 수 있는 최대 값의 수, c를 클래스의 수, l을 트리의 최대 깊이(레벨 수)라고 하면, 필요한 총 메모리는 O(ldvc)입니다.