목차
Decision Tree
결정트리 형태
결정트리 학습 알고리즘
결정트리를 이용한 회귀
ensemble classifier
k-nearest neighbor, KNN
군집화 알고리즘
naive Bayes classifier
Decision Tree
트리의 형태로 의사결정 지식을 표현한 것
결정트리 형태
단말 노드 : class, 대표값
내부 노드 : 노드들 중 단말노드를 제외한 부분으로 비교 속성이라 할 수 있다
간선 : 속성 값
![](https://blog.kakaocdn.net/dn/otygV/btsHKKhcwMh/9V8hN82F3AYoeTfoiGykV0/img.png)
결정트리 학습 알고리즘
![](https://blog.kakaocdn.net/dn/Nnqys/btsHLehRQRd/mJXl4N7drfVeBY76kS0LKK/img.png)
Algorithm
- 모든 데이터를 포함한 하나의 노드에서 시작
- 반복적인 노드 분할
분할 속성을 선택
속성값에 따라 서브 트리 생성
데이터를 속성 값에 따라 분배
=> 이러한 decision tree의 경우, 아주 복잡하여 해당 문제를 세세하게 분류하며 정확도는 99%인 트리와, 비교적 간단하되 정확도는 95%로 약간 떨어지는 트리 중 후자가 더 낫다. 과적합 문제
그렇다면 분할 속성:splitting attribute을 어떻게 결정할 것인가?
어떤 속성을 선택하는 것이 효율적인가?
분할한 결과가 가능하면 동질적:pure인 것으로 만드는 속성을 선택하는 것이 좋다
엔트로피 entropy
=> 동질적인 정도를 측정하는 척도이다
정보량 측정 목적의 척도로 엔트로피가 낮다 = 정보량이 확실하게 존재한다 = good
![](https://blog.kakaocdn.net/dn/HmdTV/btsHKoMkuyD/4tvK89W1wk3r6KdzNMBrs1/img.png)
p(c) : 부류 c에 속하는 것의 비율
![](https://blog.kakaocdn.net/dn/bWmdAC/btsHLt63dke/BiCKaY0AuLNsNygD6bZ1cK/img.png)
![](https://blog.kakaocdn.net/dn/oHjtI/btsHKLmQ47E/4Z42QKF4DFAlPkKr8kmuZK/img.png)
정보 이득이 높아지는 방향으로 분할해야함
IG = I - Ires
( Ires : 특정한 속성으로 분할한 후의 각 부분집합의 정보량 가중평균 )
= 분할한 후의 정보량 차이
= 정보 이득이 클 수록 우수한 분할 속성
![](https://blog.kakaocdn.net/dn/HGwhU/btsHLEAv7Fo/mbcLVnIrph9N0YSKDhfF9K/img.png)
학습 데이터 ex)
![](https://blog.kakaocdn.net/dn/1Ypxq/btsHMcwLjro/QLFZo7A9eC6eeSYtDIJc6K/img.png)
결정트리 학습 알고리즘 예시
1) 엔트로피 계산
분류 전 원래 I 계산
![](https://blog.kakaocdn.net/dn/c0S9KM/btsHKlCdfsI/IO1YsChhhSnbjcxHFKtKd1/img.png)
2) 속성을 결정해서 분할 후 정보이득 계산 (기존 분류 전 엔트로피와 분류 후 엔트로피 차이 계산)
- 속성의 세부 값들의 엔트로피를 계산하고, 해당 속성의 엔트로피 res 값을 구해서 IG를 비교해야함
![](https://blog.kakaocdn.net/dn/cF2RA0/btsHMuxgNMq/ajvjA9KK5BQxW146wDbqH0/img.png)
![](https://blog.kakaocdn.net/dn/SHzPU/btsHLeIV5gA/FX0NsnDT94ElyJXww84h20/img.png)
![](https://blog.kakaocdn.net/dn/AsUsz/btsHMCaV8K3/BK6CK6yhWcmYxnX2KYWzw0/img.png)
위 과정을 말단 노드(특정 class, 대표값)가 나올 때까지 분류해줘야함
![](https://blog.kakaocdn.net/dn/chTJWb/btsHKqQTDjp/ulJWEowWt7aKhteEZy4bx0/img.png)
![](https://blog.kakaocdn.net/dn/bwVrEb/btsHLGrxtlx/UCkRW2Ln6dKoVFmauAXfi1/img.png)
![](https://blog.kakaocdn.net/dn/bLzUQ6/btsHKLAqY6o/fwhYjakKVV7KKuehp9QXMk/img.png)
하지만 이러한 정보이득 척도의 단점이라고 한다면!
속성값이 많은 것을 선호한다는 것!=> 분류의 의미가 없는 like 학번이나 이름
속성값이 많으면 데이터 집합을 세부적으로, 많은 부분집합으로 분할하게 됨
이에 대한 개선의 척도는
1. 정보 이득비
2. 지니 지수
** 두 척도 설명 가능해야함
정보이득 비 : information gain ratio
정보이득 척도를 계산한 것
=> 속성값이 많은 속성에 불이익을 줌
![](https://blog.kakaocdn.net/dn/oD6Ch/btsHLuEMwxn/jvACHpbW1xpqzzXfZH0huk/img.png)
![](https://blog.kakaocdn.net/dn/clIDdw/btsHKAy7UYZ/rE2HX7FWGlT7E0Tf7P8XeK/img.png)
분류 전 엔트로피 구하고
분류 후 각 분류값들의 엔트로피를 사용해서 분류 후 엔트로피 구해서
둘의 차이는 IG를 구함
그 후 분류 후의 엔트로피를 구해서
둘을 나눠주면 정보이득비를 구할 수 있음
지니 지수 : Gini index
데이터 집합에 대한 지니 값
- i,j가 class 라고 한다면
![](https://blog.kakaocdn.net/dn/bbG4uT/btsHKjEo05N/dyqq6lggtAFcKT5V6KHqT1/img.png)
![](https://blog.kakaocdn.net/dn/eewcI2/btsHKqwDGxg/WMwDLqX8kshqvaHOKZVVZ0/img.png)
=> 지니 지수를 사용하여 이득값을 계산함
![](https://blog.kakaocdn.net/dn/b9iZie/btsHKCRgmzs/SdOlIfGJsgVF0TLAkdUnd1/img.png)
결정트리 알고리즘
- ID3 알고리즘 : 범주형 속성 데이터에 대한 decision tree
- C4.5 알고리즘 : 범주형 속성값, 수치형 속성값을 갖는 데이터에 대한 decision tree
- C5.0 알고리즘 : 4.5 개선
- CART 알고리즘 : 수치형 속성을 갖는 데이터에 적용
결정트리를 이용한 회귀
회귀를 위한 결정트리
=> 출력값이 수치
![](https://blog.kakaocdn.net/dn/eqYlEX/btsHLYFwvb5/Rz0dwPj39N1wkbbEa8k4JK/img.png)
![](https://blog.kakaocdn.net/dn/bFOLTK/btsHKPCDzCY/K3tVDtmNdJf3PGuK4ZF5Sk/img.png)
분류를 위한 결정트리와 차이점이라고 하면 단말 노드가 class값이 아닌 수치값이다
회귀 결정트리의 경우 분할 속성 선택 시, 표준편차 축소인 SDR를 최대로 하는 속성을 선택
![](https://blog.kakaocdn.net/dn/boA19i/btsHLHqvC3q/w8J2lsApuJhQoh2vqHVCO1/img.png)
![](https://blog.kakaocdn.net/dn/Qo2hc/btsHLxarteb/j3j2XpWjZshZ9RL4t80wv0/img.png)
ensemble classifier
주어진 학습 데이터 집합에 대해 여러 개의 서로 다른 classifier를 사용하며
이들의 판정 결과를 voting이나 weighted voting을 적용하여 결합한다
- bootstrap : 붓스트랩
주어진 학습 데이터 집합에서 복원 추출하여 다수의 학습 데이터 집합을 만들어냄
- bagging : bootstrap aggregating
붓스트랩을 통해 여러 개의 학습 데이터 집합을 생성
각 학습 데이터 집합별로 classifier를 생성해 학습하고
이들을 voting or weighted voting을 적용하여 최종 판정을 진행함
![](https://blog.kakaocdn.net/dn/cKsAsK/btsHLxO2ByD/Z6Gc9Ff5oAL2Wm9NyObx6K/img.png)
- boosting
k개 분류기를 순차적으로 만들어가는 앙상블 classifier
=> 분류 정확도에 따라 학습 데이터에 가중치를 변경해가며 분류기를 생성함
=> bagging 보다 성능 더 좋을 수 있음
![](https://blog.kakaocdn.net/dn/egO0Kg/btsHKOjrGPG/GjHcKya37HLj0P2mfmqUG0/img.png)
AdaBoost 알고리즘
N개의 학습 데이터 di에 대한 초기 가중치 wi
-> 학습 오류값 error : 잘못 분류한 학습 데이터의 가중치 합, 값이 0.5 미만인 분류기들만 사용
학습
-> 오류값이 0.5 미만인 분류기가 학습되는 경우
분류기의 신뢰도 알파에 대해
잘못 판정한 학습 데이터 가중치는 크게,
제대로 판정한 학습 데이터의 가중치는 줄여서 적용함
위 가중치 합이 1이 되도록 정규화
![](https://blog.kakaocdn.net/dn/NGhkr/btsHLbTcACP/BFKmC5AKn27PCpnMC2kBu1/img.png)
![](https://blog.kakaocdn.net/dn/byLmmR/btsHMMkbPZR/JZbKmIr14b1ZUqCed0vJgk/img.png)
k-nearest neighbor, knn
(입력, 결과)가 있는 데이터들이 주어진 상확 속,
새로운 입력에 대한 결과를 추정할 때 결과를 아는 최근접 K개 데이터에 대한 결과정보를 이용하는 방법
질의가 주어지면 k개의 가장 근접한 학습 데이터를 찾기 위해 모든 학습 데이터 간의 거리를 계산해야함
=> 데이터 개수가 많아지면 계산 시간이 증가한다
비교 대상 학습 데이터를 효과적으로 선택하기 위해 indexing, 또는 다양한 자료 구조들을 사용하는 것이 가능
하지만 고차원 데이터에서는 이도 비효율적이다.
![](https://blog.kakaocdn.net/dn/bJnAaG/btsHKIjwJgm/tjJFyoKraYWZgo7AY4Mjv0/img.png)
![](https://blog.kakaocdn.net/dn/c8ZPj6/btsHKqDonKm/GHpvtVlv2uhMkEdpbThTWk/img.png)
![](https://blog.kakaocdn.net/dn/KQQbr/btsHLXGEwKV/8aPKG1iO7klcaehFnNdH2k/img.png)
clustering algorithm
군집화 알고리즘
데이터를 유사한 것끼리 분류함
=> 군집 내 유사도는 크게, 군집 외 유사도는 작게
hierarchical clustering
군집화의 결과가 군집들이 계층적인 구조를 갖도록 함
- 병합형 : 각 데이터가 하나의 군집을 구성하는 상태에서 시작하여 가까이 있는 군집끼리 결합하는 과정 반복
- 분리형 : 모든 데이터를 포함한 군집에서 시작해 유사성을 바탕으로 군집을 분리해 계층적 구조를 점차 형성함
partitioning clustering
계층적 구조를 만들지 않고 전체 데이터를 유사한 것들끼리 나누어 묶음
ex) k-means
k-means는 군집화에 사용, knn는 분류, 회귀에 사용
![](https://blog.kakaocdn.net/dn/bJ5FAn/btsHML6EOCn/rBrAP775NqQN7mtLl4X56K/img.png)
![](https://blog.kakaocdn.net/dn/bqB25R/btsHMOh0WHz/RRExXIu641vIOIpbutExk1/img.png)
![](https://blog.kakaocdn.net/dn/c0XPRU/btsHMvXidy7/7291aQ1mBNSMECZPlVD191/img.png)
naive Bayes classifier
![](https://blog.kakaocdn.net/dn/Kbyix/btsHKbsUHXR/ZLKGHN47K5ilXscNMBZOvK/img.png)
![](https://blog.kakaocdn.net/dn/LUGcp/btsHLEHkbq9/WGv5LuN5odd5pP91spEOek/img.png)
![](https://blog.kakaocdn.net/dn/1nvHZ/btsHMAKXYx2/YDSB6HOpTKkqgJeEPR4QV1/img.png)
'학교 > 인공지능개론' 카테고리의 다른 글
SVM (0) | 2024.06.07 |
---|---|
기계학습 : 추가 신경망 (0) | 2024.06.05 |
기계학습 1 (0) | 2024.05.10 |
Fuzzy Theory (0) | 2024.04.18 |
탐색과 최적화 (0) | 2024.03.13 |