MLlib의 확장 가능한 의사 결정 트리

의사 결정 트리와 그 앙상블은 분류 및 회귀 등의 기계 학습 작업을 위한 업계의 핵심 요소입니다. 의사 결정 트리는 해석하기 쉽고, 범주형 및 연속 특징을 처리하며, 다중 클래스 분류로 확장되며, 특징 크기를 조정할 필요가 없으며, 비선형성 및 특징 상호 작용을 캡처할 수 있습니다.

인기 때문에 거의 모든 기계 학습 라이브러리는 결정 트리 알고리즘의 구현을 제공합니다. 그러나 대부분은 단일 머신 연산용으로 설계되었으며 분산 환경으로 우아하게 확장할 수 있는 경우는 거의 없습니다. Apache Spark는 확장 가능한 분산 의사 결정 트리 구현에 이상적인 플랫폼입니다. Spark의 인메모리 컴퓨팅을 통해 교육 데이터 세트에 대해 여러 번의 패스를 효율적으로 수행할 수 있기 때문입니다.

약 1년 전, 오픈소스 개발자들은 힘을 합쳐 빠른 분산 의사 결정 트리 구현을 개발했으며, 이는 릴리스 1.0 이후 스파크 MLlib 라이브러리의 일부였습니다. 그 이후로 스파크 커뮤니티는 의사 결정 트리 코드를 적극적으로 개선했습니다. 이 블로그 게시물에서는 구현 방법을 설명하고 몇 가지 중요한 최적화 기능을 강조하며 확장성을 입증하는 테스트 결과를 제공합니다.

Spark 1.1의 새로운 기능: MLlib 의사 결정 트리는 이제 다중 클래스 분류를 지원하며 여러 가지 성능 최적화를 포함합니다. 이제 스칼라와 자바 외에도 파이썬을 위한 API가 제공됩니다.

알고리즘 배경

높은 수준에서 의사 결정 트리 모델은 레이블을 예측하기 위해 특징 값을 테스트하는 계층적 if-else 문으로 간주될 수 있습니다. 이진 분류 작업을 위한 예제 모델은 아래와 같습니다. 이 데이터는 1970년대의 자동차 주행거리 데이터를 기반으로 합니다! 이 도구는 무게(무거운/경량)와 마력을 기준으로 차량의 주행거리지(높은/낮은)를 예측합니다.

모델은 트리를 하향식으로 구축하여 훈련 데이터 세트에서 학습됩니다. 분할 기준이라고도 하는 if-else 문은 정보 이득의 개념을 극대화하기 위해 선택되었습니다. 이는 상위 노드와 비교하여 기본 (두 개) 자식 노드의 레이블 변동성을 줄입니다. 학습된 의사 결정 트리 모델은 나중에 새로운 인스턴스의 레이블을 예측하는 데 사용할 수 있습니다.

이러한 모델은 해석 가능하며 종종 실제로 잘 작동합니다. 또한 앙상블 트리 알고리즘을 사용하여 트리를 결합하여 더욱 강력한 모델을 구축할 수도 있습니다. 랜덤 포레스트나 부스트된 트리와 같은 트리 상징은 종종 분류와 회귀 작업 모두에서 업계에서 최고의 성능을 발휘합니다.

간단한 API

아래 예제는 MLlib의 의사 결정 트리를 Spark 1.1의 새로운 Python API를 사용하여 몇 줄의 코드를 사용하여 쉽게 학습할 수 있는 방법을 보여줍니다. 이 도구는 데이터 세트를 읽고, 의사 결정 트리 모델을 학습한 다음 모델의 학습 오류를 측정합니다. Java 및 Scala 예제는 DecisionTree의 Spark 문서에서 확인할 수 있습니다.

최적화된 구현

스파크는 정교한 DAG 실행 엔진과 반복적 연산을 위한 인메모리 캐싱 기능을 갖추고 있기 때문에 확장 가능한 분산 의사 결정 트리 구현에 이상적인 컴퓨팅 플랫폼입니다. 몇 가지 주요 최적화 사항에 대해 설명합니다.

레벨별 교육: 트리의 동일한 레벨에 있는 모든 노드에 대한 분할을 동시에 선택합니다. 이러한 수준별 최적화는 데이터 세트에 대한 패스 수를 기하급수적으로 줄입니다. 트리의 각 노드에 대해 하나의 패스가 아닌 각 수준에 대해 하나의 패스를 만듭니다. 이를 통해 I/O, 컴퓨팅 및 통신 비용을 상당히 절감할 수 있습니다.

대략적인 분위수: 단일 기계 구현은 일반적으로 연속 피쳐에 대해 정렬된 고유 피쳐 값을 최상의 분할 계산을 위한 분할 후보로 사용합니다. 그러나 분산된 데이터 세트에서 정렬된 고유 값을 찾는 작업은 비용이 많이 듭니다. MLlib 의사 결정 트리는 각 피쳐에 대한 분위수를 분할 후보로 사용합니다. 이는 정확도를 크게 저하시키지 않고 의사 결정 트리 성능을 개선하기 위한 표준적인 절충 방안입니다.

맵 연산을 피하십시오: 의사 결정 트리의 초기 프로토타입 구현은 트리 노드에 대한 최적의 분할을 선택할 때 맵 연산과 리듀스 연산을 모두 사용했습니다. 현재 코드는 맵 단계를 피하기 위해 미리 계산된 분할 후보의 알려진 구조를 활용함으로써 계산과 통신을 훨씬 적게 사용합니다.

빈 방식 계산: 최상의 분할 계산은 피쳐를 빈으로 이산화하며, 이러한 빈은 분할에 필요한 충분한 통계량을 계산하는 데 사용됩니다. 우리는 각 인스턴스의 빈 표현을 미리 계산하여 각 반복에 대한 계산을 절약합니다.

확장성

우리는 다양한 데이터 세트 및 클러스터 크기에 대한 경험적 결과를 통해 MLlib 의사 결정 트리의 확장성을 보여줍니다.

데이터 세트 크기에 맞춰 확장

아래 두 그림은 데이터 세트의 인스턴스와 특징 수를 확장할 때 의사 결정 트리의 훈련 시간을 보여줍니다. 교육 시간은 비례적으로 증가했으며 이는 구현의 확장성을 강조했습니다.

이 테스트는 마스터 노드 1개와 작업자 노드 15개가 있는 EC2 클러스터에서 r3.2xlarge 인스턴스(가상 CPU 8개, 메모리 61GB)를 사용하여 실행되었습니다. 트리는 6개 레벨로 구성되었으며 데이터 세트는 spark-perf 라이브러리에서 생성되었습니다.

Spark 1.1의 속도 향상

다음 두 그림은 원래 Apache Spark 1.0 구현과 비교하여 Apache Spark 1.1의 개선점을 보여줍니다. 동일한 데이터 세트와 클러스터에서 새로운 구현은 많은 데이터 세트에서 4~5배 더 빠릅니다!

다음 단계는 무엇입니까?

릴리즈 1.1 이후의 트리 기반 알고리즘 개발은 주로 랜덤 포레스트와 부스팅과 같은 앙상블 알고리즘에 중점을 둘 것입니다. 또한 성능을 위해 의사 결정 트리 코드를 지속적으로 최적화할 것이며 향후 릴리스에서 더 많은 옵션에 대한 지원을 추가할 계획입니다.

의사 결정 트리를 직접 사용하기 시작하려면 지금 Spark 1.1을 다운로드하십시오!

추가 자료

• MLlib 진단트리 문서에서 예제 및 API를 참조하십시오.
• 2014 Spark Summit에서 발표된 의사 결정 트리 프레젠테이션을 시청하십시오.
• 2014년 9월 샌프란시스코 스칼라/베이 지역 기계 학습 모임에서 의사 결정 트리에 관한 또 다른 강연의 비디오와 슬라이드를 확인해 보십시오.

감사의 말

Spark MLlib 의사 결정 트리 작업은 처음에 Hirakendu Das(Yahoo Labs), Evan Sparks(UC Berkeley AMPLab), Ameet Talwalkar 및 Xiangrui Meng(Databricks)과 공동으로 수행되었습니다. 그 이후로 더 많은 기여자가 참여했으며, 여러분의 의견도 환영합니다!

(이 글은 AI의 도움을 받아 번역되었습니다. 원문이 궁금하시다면 여기를 클릭해 주세요)