Hoeffding 트리 알고리즘은 스트림 데이터 분류를 위한 의사결정 트리 학습 방법입니다. 처음에는 웹 클릭스트림을 추적하고 사용자가 액세스할 웹 호스트 및 웹 사이트를 예측하는 모델을 구성하는 데 사용되었습니다. 일반적으로 하위 선형 시간으로 실행되며 기존 배치 학습자와 거의 동일한 의사 결정 트리를 생성합니다.
그것은 작은 샘플이 최적의 분할 속성을 선택하기에 충분할 수 있다는 아이디어를 이용하는 Hoeffding 트리를 사용합니다. 이 아이디어는 Hoeffding 경계(또는 Additive Chernoff 경계)에 의해 수학적으로 지원됩니다.
범위가 R인 랜덤 변수 r에 대해 N개의 독립적인 관찰을 한다고 가정합니다. 여기서 r은 속성 선택 측정입니다. (확률의 경우 R은 1이고, 정보 이득의 경우 log c이며, 여기서 c는 클래스의 개수입니다.) Hoeffding 트리의 경우 r은 정보 이득입니다. 이 샘플의 평균 r'을 계산하면 Hoeffding 경계는 r의 실제 평균이 최소 r'−ε이고 확률이 1−δ이며 여기서 δ는 사용자 지정이고
$$\varepsilon=\sqrt{\frac{R^{2}ln\frac{1}{\delta}}{2N}} $$
회프딩 트리 알고리즘은 분할 속성을 선택할 때 노드에 필요한 가장 작은 수 N을 높은 확률로 결정하기 위해 회프딩 경계를 사용합니다. Hoeffding 경계는 대부분의 다른 경계 방정식과 달리 확률 분포와 무관합니다. 이것은 정보 이득의 확률 분포를 아는 것이 불가능할 수 있기 때문에 바람직합니다.
알고리즘은 속성 A와 정확도 매개변수 δ로 설명되는 일련의 훈련 예제 S를 입력으로 사용합니다. 평가 함수 G(Ai ) 정보 이득, 이득 비율, 지니 지수 또는 기타 속성 선택 측정이 될 수 있습니다. 결정 트리의 각 노드에서 G(Ai ) 나머지 속성 중 하나에 대해 Ai . 목표는 Hoeffding 경계를 만족하는 가장 작은 수의 튜플 N을 찾는 것입니다.
알고리즘은 속성 A와 정확도 매개변수 δ로 설명되는 일련의 훈련 예제 S를 입력으로 사용합니다. 평가 함수 G(Ai ) 정보 이득, 이득 비율, 지니 지수 또는 기타 속성 선택 측정이 될 수 있습니다. 결정 트리의 각 노드에서 G(Ai ) 나머지 속성 중 하나에 대해 Ai . 목표는 Hoeffding 경계를 만족하는 가장 작은 수의 튜플 N을 찾는 것입니다.
주어진 노드에 대해 Aa G(Aa)가 가장 높은 G를 달성하는 속성이고 Abbe가 두 번째로 높은 G를 달성하는 속성입니다. ) - G(Ab )> ε, 여기서 ε은 계산됩니다.
Hoeffding 트리 알고리즘에서 유지해야 하는 유일한 통계는 nijk 개수입니다. 값 vj에 대해 속성 Ai의 클래스 레이블 yk 포함 . 따라서 d가 속성의 수이고 v는 속성에 대한 최대 값 수이고 c는 클래스 수이고 l은 트리의 최대 깊이(또는 레벨 수)이면 필요한 총 메모리 O(ldvc)입니다.