C4.5 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
C4.5 알고리즘은 ID3 알고리즘을 개선한 의사 결정 트리 구축 알고리즘이다. 정보 엔트로피 개념을 사용하여 훈련 데이터를 분류하며, 정규화된 정보 이득을 기준으로 데이터를 분할한다. ID3에 비해 연속형 및 이산형 속성 처리, 누락된 속성 값 처리, 다양한 비용을 가진 속성 처리, 트리 가지치기 등의 개선 사항을 포함한다. C4.5를 개선한 C5.0/See5 알고리즘은 속도, 메모리 사용량, 트리 크기, 부스팅 지원 등에서 향상된 성능을 제공한다.
더 읽어볼만한 페이지
- 결정 트리 - ID3 알고리즘
ID3 알고리즘은 존 로스 퀸란이 1979년에 개발한 의사 결정 트리 학습 알고리즘으로, 정보량의 기대값을 계산하여 트리의 노드를 생성하며, 학습 효율이 높지만 국소 최적해 문제와 과적합 가능성 등의 단점도 가진다. - 결정 트리 - 랜덤 포레스트
랜덤 포레스트는 결정 트리들을 앙상블하여 분류, 회귀, 검출 등에 활용되며, 랜덤화 기술로 일반화 성능을 향상시키는 기계 학습 알고리즘이다. - 분류 알고리즘 - 인공 신경망
- 분류 알고리즘 - 퍼셉트론
퍼셉트론은 프랭크 로젠블랫이 고안한 인공신경망 모델로, 입력 벡터에 가중치를 곱하고 편향을 더한 값을 활성화 함수에 통과시켜 이진 분류를 수행하는 선형 분류기 학습 알고리즘이며, 초기 신경망 연구의 중요한 모델로서 역사적 의미를 가진다.
| C4.5 알고리즘 | |
|---|---|
| 기본 정보 | |
 | |
| 종류 | 분류 알고리즘 |
| 문제점 | 과적합 관련 없는 속성 |
| 개발 | |
| 개발자 | 로스 퀸란 |
| 개발 시기 | 1993년 |
| 기반 | ID3 알고리즘 |
| 파생 | C5.0 알고리즘 |
| 구현체 | |
2. 알고리즘
C4.5는 ID3 알고리즘과 마찬가지로 정보 엔트로피 개념을 사용하여 훈련 데이터 집합으로부터 의사 결정 트리를 구축한다. C4.5는 각 데이터의 속성이 데이터를 더 작은 부분 집합으로 분할하는 결정에 사용될 수 있다는 사실을 이용하며, 데이터를 분할하기 위한 속성을 선택한 결과로 인한 정규화된 정보 이득(엔트로피의 차이)을 조사한다. 가장 큰 정규화된 정보 이득을 보이는 속성이 결정을 내리는 데 사용되며, 알고리즘은 더 작은 서브리스트에 재귀적으로 적용된다.
2. 1. 작동 원리
C4.5는 ID3 알고리즘과 동일한 방식으로 훈련 데이터 집합으로부터 의사 결정 트리를 구축하며, 정보 엔트로피의 개념을 사용한다. 훈련 데이터는 이미 분류된 샘플 집합 이다. 각 샘플 는 샘플의 속성 값 또는 특징을 나타내는 p차원 벡터 로 구성되며, 가 속하는 클래스도 포함한다.트리의 각 노드에서 C4.5는 샘플 집합을 한 클래스 또는 다른 클래스로 더 효과적으로 분할하는 데이터의 속성을 선택한다. 이 때, 정규화된 정보 이득 (엔트로피의 차이)이 분할 기준으로 사용된다. 가장 높은 정규화된 정보 이득을 가진 속성을 기준으로 데이터를 분할하고, 분할된 하위 목록에 대해 재귀적으로 알고리즘을 적용한다.
이 알고리즘에는 몇 가지 기본 사례가 있다.
- 목록의 모든 샘플이 동일한 클래스에 속하는 경우, 해당 클래스를 선택하도록 지시하는 의사 결정 트리의 리프 노드를 생성한다.
- 어떠한 특징도 정보 이득을 제공하지 않는 경우, C4.5는 클래스의 예상 값을 사용하여 트리 상단에 의사 결정 노드를 생성한다.
- 이전에 보지 못한 클래스의 인스턴스가 발생한 경우, C4.5는 예상 값을 사용하여 트리 상단에 의사 결정 노드를 생성한다.
2. 2. 기본 사례
C4.5 알고리즘에는 다음과 같은 기본 사례들이 있다.- 모든 샘플이 동일한 클래스에 속하는 경우: 의사 결정 트리에 해당 클래스를 선택하는 리프 노드를 생성한다.
- 어떤 특징도 정보 이득을 유발하지 않는 경우: C4.5는 클래스의 기대값을 사용하여 트리의 상위에 결정 노드를 생성한다.
- 클래스의 인스턴스가 생성되지 않는 경우: 이 경우에도 기대값을 사용하여 트리의 상위에 결정 노드를 생성한다.[1]
2. 3. 의사 코드
의사 결정 트리를 구축하기 위한 일반적인 알고리즘은 의사 코드로 다음과 같다.[4]1. 기본 사례를 확인한다.
2. 각 속성 ''a''에 대해, ''a''를 기준으로 분할했을 때 정규화된 정보 이득 비율을 구한다.
3. ''a_best''를 정규화된 정보 이득이 가장 높은 속성으로 한다.
4. ''a_best''를 기준으로 분할하는 의사 결정 ''노드''를 생성한다.
5. ''a_best''를 기준으로 분할하여 얻은 하위 목록에 대해 재귀적으로 수행하고, 해당 노드를 ''node''의 자식으로 추가한다.
3. ID3 알고리즘과의 비교 및 개선점
C4.5는 ID3 알고리즘에 비해 여러 가지 개선 사항을 제공한다. 주요 개선점은 다음과 같다.
- 연속형 및 이산형 속성 모두 처리
- 누락된 속성 값 처리
- 다양한 비용을 가진 속성 처리
- 트리 생성 후 가지치기
3. 1. 연속형 및 이산형 속성 처리
C4.5는 연속형 속성을 처리하기 위해 임계값을 생성하고, 이를 기준으로 속성 값이 임계값보다 큰 경우와 임계값보다 작거나 같은 경우로 데이터를 분할한다.[5]3. 2. 누락된 속성 값 처리
C4.5는 누락된 속성 값을 '?'로 표시하도록 허용한다. 누락된 속성 값은 정보 획득 및 엔트로피 계산에 사용되지 않는다.[5]3. 3. 가지치기
C4.5는 트리가 생성된 후 다시 돌아가서, 도움이 되지 않는 분기를 리프 노드로 대체하여 제거하려고 시도한다.[5]3. 4. 기타
C4.5는 다양한 비용을 가진 속성을 처리할 수 있다.[5]4. C5.0/See5 알고리즘
로스 퀸란은 C4.5를 개선한 C5.0과 See5 (C5.0은 유닉스/리눅스용, See5는 윈도우용)를 상업적으로 판매하고 있다.[6][7] C5.0은 C4.5에 비해 많은 개선이 이루어졌으며, 상업적 이용을 목적으로 소스 코드가 공개되지 않았지만, 프리 소스 코드가 인터프리팅에 이용 가능하며 출력된 결정 트리와 규칙을 사용할 수 있다.
4. 1. C4.5 대비 개선점
퀸란은 C5.0과 See5(유닉스/리눅스용 C5.0, 윈도우용 See5)를 상업적으로 개발했다. C5.0은 C4.5에 비해 다음과 같은 여러 가지 개선점을 제공한다.[6][7]- 속도: C5.0은 C4.5보다 훨씬 빠르다(수 배나 빠름).
- 메모리 사용량: C5.0은 C4.5보다 메모리 효율이 높다.
- 더 작은 의사 결정 트리: C5.0은 C4.5와 비슷한 결과를 얻으면서도 의사 결정 트리가 훨씬 작다.
- 부스팅 지원: 부스팅은 트리의 성능을 향상시키고 더 높은 정확도를 제공한다.
- 가중치 부여: C5.0을 사용하면 서로 다른 케이스와 오분류 유형에 가중치를 부여할 수 있다.
- 위노잉(Winnowing): C5.0 옵션은 유용하지 않을 수 있는 속성을 자동으로 위노잉하여 제거한다.
단일 스레드 리눅스 버전의 C5.0 소스는 GNU 일반 공중 사용 허가서(GPL)에 따라 제공된다.
4. 2. 상용 버전과 오픈 소스
로스 퀸란은 C5.0과 See5 (유닉스/리눅스용 C5.0, 윈도우용 See5)를 개발했으며, 이를 상업적으로 판매하고 있다.[6][7] C5.0은 C4.5에 비해 속도, 메모리 사용량, 의사 결정 트리 크기 등 여러 가지 개선 사항을 제공한다.[6][7] 또한 부스팅을 지원하여 트리의 성능을 향상시키고 더 높은 정확도를 제공하며, 가중치 부여 기능을 통해 서로 다른 케이스와 오분류 유형에 가중치를 부여할 수 있다. C5.0은 유용하지 않을 수 있는 속성을 자동으로 위노잉하여 제거하는 기능도 제공한다.[6][7]단일 스레드 리눅스 버전의 C5.0 소스는 GNU 일반 공중 사용 허가서(GPL)에 따라 제공된다.
5. 구현
참조
[1]
서적
C4.5: Programs for Machine Learning
Morgan Kaufmann Publishers
1993
[2]
웹사이트
Data Mining: Practical machine learning tools and techniques, 3rd Edition
http://www.cs.waikat[...]
Morgan Kaufmann, San Francisco
[3]
웹사이트
Umd.edu - Top 10 Algorithms in Data Mining
http://www.cs.umd.ed[...]
[4]
간행물
Supervised Machine Learning: A Review of Classification Techniques
Informatica
2007
[5]
논문
Improved use of continuous attributes in c4.5
1996
[6]
웹사이트
Is See5/C5.0 Better Than C4.5?
http://www.rulequest[...]
[7]
서적
Applied Predictive Modeling
Springer
2013
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com