C4.5 알고리즘

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2008년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

C4.5는 로스 퀸랜이 개발한 의사결정 트리를 생성하기 위해 사용하는 알고리즘이다.^[1]C4.5는 퀸랜의 초기 ID3 알고리즘의 확장이다.C4.5에 의해 생성된 결정 트리는 분류에 사용할 수 있으며, 이러한 이유로 C4.5를 흔히 통계 분류기라고 부른다.2011년, Weka 머신러닝 소프트웨어의 저자들은 C4.5 알고리즘을 "현재까지 실제로 가장 널리 사용되는 머신러닝 작업자일 가능성이 높은 획기적인 의사결정 나무 프로그램"이라고 설명했다.^[2]

2008년 Springer LNCS가 발표한 데이터 마이닝 사전 우수 논문 TOP10에서 1위를 차지한 후 꽤 인기를 끌었다.^[3]

알고리즘.

C4.5는 정보 엔트로피 개념을 이용하여 ID3와 같은 방법으로 일련의 훈련 데이터로부터 의사결정 트리를 구축한다.훈련 데이터는 $집합{\displaystyle }$ S${\displaystyle }$= ${\displaystyle {s\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{}_{}{2\mathrm{}}_{}}$, .${\displaystyle }$. . ${\$ S$={s_{1},s_{2},...$이미 분류된 샘플$$ 중 $}}.$Each sample ${\displaystyle s_{i}}$ consists of a p-dimensional vector ${\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}$, where the ${\displaystyle x_{j}}$ represent attribute values or features of the sample, as well as the class in which ${\displays$$tyle s_{i}}}$ 폭포$$.

트리의 각 노드에서 C4.5는 표본 집합을 한 클래스 또는 다른 클래스에서 농축된 하위 집합으로 가장 효과적으로 분할하는 데이터의 속성을 선택한다.분할 기준은 정규화된 정보 이득(엔트로피의 차이)이다.의사결정을 위해 정규화된 정보 이득이 가장 높은 속성을 선택한다.그런 다음 C4.5 알고리즘이 분할된 하위 목록에 반복된다.

이 알고리즘에는 몇 가지 기본 사례가 있다.

• 리스트에 있는 모든 샘플은 같은 등급에 속한다.이렇게 되면 단순히 의사결정 트리에 대해 해당 클래스를 선택하라는 리프 노드를 생성한다.
• 어떤 기능도 어떠한 정보 이득도 제공하지 않는다.이 경우 C4.5는 클래스의 예상 값을 사용하여 트리 위쪽에 의사결정 노드를 생성한다.
• 이전에 보지 못한 클래스의 인스턴스가 발견됨.다시 C4.5는 예상 값을 사용하여 트리 위쪽에 의사결정 노드를 생성한다.

가성음

의사 결정 트리를 만들기 위한 일반적인 알고리즘은 다음과 같다.^[4]

1. 위의 기본 사례를 확인하십시오.
2. 각 속성 a에 대해, a에서 분할하여 정규화된 정보 이득 비율을 구하십시오.
3. a_best를 정규화된 정보 이득이 가장 높은 속성이 되도록 한다.
4. a_best에서 분할되는 의사결정 노드를 생성한다.
5. a_best를 분할하여 얻은 하위 목록에서 다시 실행하고 해당 노드를 노드의 하위 항목으로 추가하십시오.

구현

J48은 Weka 데이터 마이닝 도구에 있는 C4.5 알고리즘의 오픈 소스 Java 구현이다.

ID.3 알고리즘 개선

C4.5는 ID3을 여러 가지 개선하였다.이들 중 일부는 다음과 같다.

• 연속형 및 이산형 속성 처리 - 연속형 속성을 처리하기 위해 C4.5는 임계값을 생성한 다음 속성 값이 임계값보다 높은 값과 그보다 작거나 같은 값으로 목록을 분할한다.^[5]
• 속성 값이 누락된 교육 데이터 C4.5를 처리하면 속성 값을 결측값으로 ?로 표시할 수 있다.누락된 속성 값은 게인 및 엔트로피 계산에 사용되지 않는다.
• 다양한 비용으로 속성 처리.
• 생성 후 가지치기 - C4.5는 일단 트리가 생성되면 다시 트리를 통과하여 잎 노드로 교체하여 도움이 되지 않는 가지를 제거하려고 시도한다.

C5.0/See5 알고리즘 개선

Quinlan은 계속해서 상업적으로 판매하는 C5.0과 See5(유닉스/리눅스용 C5.0, Windows용 See5)를 만들었다.C5.0은 C4.5에 대한 많은 개선사항을 제공한다.이들 중 일부는 다음과 같다.^[6][7]

• 속도 - C5.0이 C4.5보다 상당히 빠르다(규모의 여러 가지 순서)
• 메모리 사용 - C5.0이 C4.5보다 메모리 효율적임
• 더 작은 의사결정 나무 - C5.0은 상당히 작은 의사결정 나무로 C4.5와 유사한 결과를 얻는다.
• 부스팅에 대한 지지 - 부스팅은 나무를 개선하고 나무들에게 더 많은 정확성을 준다.
• 가중치 부여 - C5.0을 사용하면 다른 사례와 잘못된 분류 유형에 가중치를 부여할 수 있다.
• Winnowing - C5.0 옵션은 도움이 되지 않을 수 있는 속성을 제거하기 위해 자동으로 속성을 윈노잉한다.

단일 스레드 Linux 버전의 C5.0의 소스는 GPL에서 사용할 수 있다.

참고 항목

• ID3 알고리즘
• 시간 및 인과 규칙을 생성하도록 C4.5 수정

참조

외부 링크

• Ross Quinlan 홈페이지의 원래 구현: http://www.rulequest.com/Personal/
• 5 및 C5.0 참조