2023-10-12 26th Class
K-means Clustering Visualization
import numpy as np
import matplotlib.pyplot as plt
def get_data_from_centroid(centroid, n_data):
data = np.random.normal(loc=centroid, scale=1, size=(n_data, 2))
return data
def get_sample_dataset(n_classes, n_data):
centroids = np.array([np.random.uniform(low=-10, high=10, size=(2,)) for x in range(n_classes)])
target_cls = np.array([i for i in range(n_classes) for _ in range(n_data)])
data = None
for i, centroid in enumerate(centroids):
if i == 0:
data = get_data_from_centroid(centroid, n_data)
continue
curr_dataset = get_data_from_centroid(centroid, n_data)
data = np.vstack([data, curr_dataset])
return data, target_cls, centroids
def kmeans_plusplus_init(X, k):
init_cent = X[np.random.choice(len(X))]
centers = [init_cent]
print('here')
for _ in range(1, k):
near_dists = np.array([min([np.linalg.norm(x - c)**2 for c in centers]) for x in X])
probs = near_dists / near_dists.sum()
next_cent = X[np.random.choice(len(X), p=probs)]
centers.append(next_cent)
return centers
def kmeans_clustering(X, centers, max_iters=100):
for _ in range(max_iters):
labels = np.array([np.argmin([np.linalg.norm(x - c)**2 for c in centers]) for x in X])
new_centers = np.array([X[labels == i].mean(axis=0) for i in range(len(centers))])
if np.all(centers == new_centers):
break
centers = new_centers
return centers, labels
def kmeans_visualization(X, y, cents):
class_colors = ['#FF5733', '#FFA500', '#008000', '#FF69B4']
fig, ax = plt.subplots(figsize=(7, 7))
# all data
ax.scatter(x=X[:, 0], y=X[:, 1], c=[class_colors[label] for label in y], alpha=0.5)
# centroids
for c in cents:
ax.scatter(x=c[0], y=c[1], color="b")
plt.show()
if __name__ == '__main__':
data, target_cls, centroids = get_sample_dataset(n_classes=4, n_data=100)
centers = kmeans_plusplus_init(X=data, k=4)
final_centers, labels = kmeans_clustering(X=data, centers=centers)
kmeans_visualization(data, labels, final_centers)
Decision Tree
Decision Tree는 root node에서 어떤 질문으로 시작하는지에 따라(어떤 feature) depth가 달라진다.
email spam prediction
![[19_spam.JPG]]
- decision tree 작성시에는 feature 기준으로 depth를 늘려 분류
- 한 번 사용한 feature 는 하위 노드(leaf node)에서 더이상 사용하지 않음
- root 노드에서 어떤 feature로 시작하는지에 따라 depth가 달라지게 됨
featrue (categorical, continuous)
target class (categorical-> classification, continuous->regressioin)
Entropy
from 열역학 제 1법칙…
무질서도라고도 부르며 불순도를 측정하는 기준(impurity metrics)
카드를 12장 뽑는 경우에 모두 같은 숫자라면 uncertainty=0이고, entropy도 0임
p=확률
decision tree는 information based machine learning이라고 함
정보량
드물게 발생할 수록 정보량은 높음 (degree of surprise: 놀람의 정도)
entropy는 정보량의 기댓값(평균)
발생 사건들의 정보량을 모두 구해서 (가중)평균을 구한 것
log_2에서 밑이 2인 로그를 쓰는 이유는 컴퓨터는 정보이론이기때문에 0,1로 구성이되어서 2로 사용함
numpy를 활용한 entropy 계산 방법
def entropy_test():
# the 3rd entropy
p31 = 1/2
p32 = 1/2
h3 = -(p31 * np.log2(p31) + p32 * np.log2(p32))
print(h3) # 1.0
# the 4th entropy
p41 = 1/2
p42 = 1/4
p43 = 1/4
h4 = -(p41 * np.log2(p41) + p42 * np.log2(p42) + p43 * np.log2(p43))
print(h4) # 1.5
# the 5th entropy
p51 = 1/3
p52 = 1/3
p53 = 1/3
h5 = -(p51 * np.log2(p51) + p52 * np.log2(p52) + p53 * np.log2(p53))
print(h5) # 1.584962500721156
# the 6th entropy
p6 = np.array([1 / 12 for _ in range(12)])
p6_entropy_list = p6 * np.log2(p6)
h6 = -np.sum(p6_entropy_list)
print(h6) # 3.584962500721156
- ndarray상태에서 np.log2나 곱하기등을 씌우면 모든 요소에 연산이 적용됨
- np.sum() 안에 인자로 list나 ndarray를 넣으면 python 기본 모듈 sum과 동일한 원리로 계산됨
- 불확실할 수록 엔트로피 값은 높게 나옴
- 확률이 1/2인 경우는 1이었는데, 1/12 정도씩인 경우에는 3까지 상승함
암기: 클래스가 2개일 때 P가 전부 1/2 인경우 entropy 값은 1
weighted entropy
하위 생성된 노드의 데이터셋 크기에 따라 가중치를 부여하는 것
information gain
얼마만큼의 정보를 획득했는지(정보 획득량)
분기 이전의 불순도와 분기 이후의 불순도의 차이
- entropy가 0에 수렴할수록 불순도가 낮은 것 = 확실해진다는 의미
- decision tree는 leaf를 타고 내려갈 수록 구분이 잘 되어지는 원리
- Information Gain은 parent의 entropy와 children의 entropy 차이
- IG값이 크다는 것은 기존보다 분기 후에 더 확실해졌다(낮은 entropy가 되었다)는 의미
- 따라서 decision tree에서 분기하는 기준은
각 feature 기준으로 분기를 했을 때 IG 값을 구해서
가장 높은 IG 값을 갖는 feature가 제일 확실하게 분류 처리를 하는 것이기 때문에
해당 feature을 하위 노드로 선택을 하는 것
Entropy / Information Gain 계산 방법
Information gain의 단위는 bits
Multi Class Decision Tree 해부 😱
수식 + Python Code (feat. 될 때까지 한다)
The vegetation classification dataset
| ID | STREAM | SLOPE | ELEVATION | VEGETATION |
|---|---|---|---|---|
| 1 | FALSE | steep | high | chapparal |
| 2 | TRUE | moderate | low | riparian |
| 3 | TRUE | steep | medium | riparian |
| 4 | FALSE | steep | medium | chapparal |
| 5 | FALSE | flat | high | conifer |
| 6 | TRUE | steep | highest | conifer |
| 7 | TRUE | steep | high | chapparal |
0️⃣ Root Node (H0)
루트노드는 decision tree의 가장 상단 (0층)
루트 노드 층의 entropy를 구한다.
H(VEGETATION, D)
CODE
# root node
probs = [3/7, 2/7, 2/7]
probs = np.array(probs)
h0 = -np.sum(probs * np.log2(probs))
print('root node H: ', h0)
# root node H: 1.5566567074628228
루트 노드의 Entropy 값은 1.5566
1️⃣ Split by Feature (H1)
리프노드(leaf node)는 parent node에서 가지를 친 children node, 즉 하위 노드이다.
- 전체 데이터셋에서 특정 feature의 unique 값을 기준으로 각각 entropy를 구한다.
- 그리고 그 값에 weight, 가중치를 곱하여 더한다.
가중치는 feature내의 특정 class에 해당하는 인스턴스의 개수 / 상위 노드의 인스턴스 개수로 구한다
ex) 전체 7개중 4개가 true인 경우 -> 가중치는 4/7
#️⃣ STREAM
feature stream의 클래스는 True, False 2개이다.
True, False 기준으로 데이터를 filtering하여 instance를 확인한다.
TRUE
| ID | STREAM | SLOPE | ELEVATION | VEGETATION |
|---|---|---|---|---|
| 2 | TRUE | moderate | low | riparian |
| 3 | TRUE | steep | medium | riparian |
| 6 | TRUE | steep | highest | conifer |
| 7 | TRUE | steep | high | chapparal |
TREAM이 TRUE인 instance 번호: 2, 3, 6, 7
PIVOT TABLE
개수 : ID 열 레이블
| 행 레이블 | TRUE | FALSE | 총합계 |
|---|---|---|---|
| chapparal | 1 | 2 | 3 |
| conifer | 1 | 1 | 2 |
| riparian | 2 | 2 | |
| 총합계 | 4 | 3 | 7 |
-
True/False 인 인스턴스들을 y값인 vegetation의 3가지 클래스로 각각 구분한다.
-
True인 인스턴스 셋에서 chapparal 1개 + conifer 1개 + riparian 2개 = 4개이고
-
True의 엔트로피값에는 4/7 의 가중치를 곱해준다. (True개수 / Parent node의 인스턴스 개수)
-
False인 인스턴스 셋에서 chapparal 2개 + conifer 1개 = 3개이고
-
False의 엔트로피값에는 3/7 의 가중치를 곱해준다.
이제 Partition Entropy의 값에 각각 weight를 곱하여 더한 최종 entropy 값을 구하는 공식에
H1 (True인 인스턴스의 entropy)를 구하여 대입한다.
FORMULAS
CODE
# stream
# true
probs = [1/4, 1/4, 2/4]
probs = np.array(probs)
h1_str_t = -np.sum(probs * np.log2(probs))
print('h1층의 피처 stream에서 true의 entropy: ', h1_str_t)
# h1층의 피처 stream의 entropy: 1.5
FALSE
| ID | STREAM | SLOPE | ELEVATION | VEGETATION |
|---|---|---|---|---|
| 1 | FALSE | steep | high | chapparal |
| 4 | FALSE | steep | medium | chapparal |
| 5 | FALSE | flat | high | conifer |
TREAM이 FALSE인 instance 번호: 1, 4, 5
PIVOT TABLE
개수 : ID 열 레이블
| 행 레이블 | TRUE | FALSE | 총합계 |
|---|---|---|---|
| chapparal | 1 | 2 | 3 |
| conifer | 1 | 1 | 2 |
| riparian | 2 | 2 | |
| 총합계 | 4 | 3 | 7 |
이번에는 피처 STREAM중에서 False인 데이터의 엔트로피를 계산한다.
False인 인스턴스 셋에서 chapparal 2개 + conifer 1개 = 3개로
chapparal과 conifer 2종류의 인스턴스가 총 3개가 있다.
확률은 2/3과 1/3으로 entropy를 계산한다.
FORMULA
CODE
# false
probs = [2/3, 1/3]
probs = np.array(probs)
h1_str_f = -np.sum(probs * np.log2(probs))
print('h1층의 피처 stream에서 false의 entropy: ', h1_str_f)
# h1층의 피처 stream에서 false의 entropy: 0.9182958340544896
전체 공식에 H2를 대입하여 최종 계산한다.
FORMULAS
CODE
# final h1_str
h1_str = 4/7 * h1_str_t + 3/7 * h1_str_f
print('h1층의 피처 stream의 최종 entropy: ', h1_str)
# h1층의 피처 stream의 최종 entropy: 1.2506982145947811
따라서 H1 STREAM의 entropy = 1.2507
#️⃣ SLOPE
FLAT
| ID | SLOPE | ELEVATION | VEGETATION |
|---|---|---|---|
| 5 | flat | high | conifer |
MODERATE
| ID | SLOPE | ELEVATION | VEGETATION |
|---|---|---|---|
| 2 | moderate | low | riparian |
STEEP
| ID | SLOPE | ELEVATION | VEGETATION |
|---|---|---|---|
| 1 | steep | high | chapparal |
| 3 | steep | medium | riparian |
| 4 | steep | medium | chapparal |
| 6 | steep | highest | conifer |
| 7 | steep | high | chapparal |
slope의 경우 flat, moderate, steep 총 3개의 level로 구분된다.
PIVOT TABLE
개수 : ID 열 레이블
| 행 레이블 | flat | moderate | steep | 총합계 |
|---|---|---|---|---|
| chapparal | 3 | 3 | ||
| conifer | 1 | 1 | 2 | |
| riparian | 1 | 1 | 2 | |
| 총합계 | 1 | 1 | 5 | 7 |
FORMULAS
CODE
# slope
# flat - 0
# moderate - 0
# steep
probs = [3/5, 1/5, 1/5]
probs = np.array(probs)
h1_slo_s = -np.sum(probs * np.log2(probs))
print('h1층의 피처 slope에서 steep의 entropy: ', h1_slo_s)
# h1층의 피처 slope에서 steep의 entropy: 1.3709505944546687
# final h1_slo
h1_slo = 1/7 * 0 + 1/7 * 0 + 5/7 * h1_slo_s
print('h1층의 피처 slope의 최종 entropy: ', h1_slo)
# h1층의 피처 slope의 최종 entropy: 0.9792504246104776
따라서 H1 SLOPE의 entropy = 0.9793
#️⃣ ELEVATION
HIGH
| ID | ELEVATION | VEGETATION |
|---|---|---|
| 1 | high | chapparal |
| 5 | high | conifer |
| 7 | high | chapparal |
HIGHEST
| ID | ELEVATION | VEGETATION |
|---|---|---|
| 6 | highest | conifer |
LOW
| ID | ELEVATION | VEGETATION |
|---|---|---|
| 2 | low | riparian |
ELEVATION
| ID | ELEVATION | VEGETATION |
|---|---|---|
| 3 | medium | riparian |
| 4 | medium | chapparal |
elevation의 경우 high, highest, low, medium 총 4개의 level로 구분된다.
PIVOT TABLE
개수 : ID 열 레이블
| 행 레이블 | high | highest | low | medium | 총합계 |
|---|---|---|---|---|---|
| chapparal | 2 | 1 | 3 | ||
| conifer | 1 | 1 | 2 | ||
| riparian | 1 | 1 | 2 | ||
| 총합계 | 3 | 1 | 1 | 2 | 7 |
CODE
# elevation
# high
probs = [2/3, 1/3]
probs = np.array(probs)
h1_ele_high = -np.sum(probs * np.log2(probs))
print('h1층의 피처 elevation에서 high의 entropy: ', h1_ele_high)
# h1층의 피처 elevation에서 high의 entropy: 0.9182958340544896
# highest - 0
# low - 0
# medium
probs = [1/2, 1/2]
probs = np.array(probs)
h1_ele_medium = -np.sum(probs * np.log2(probs))
print('h1층의 피처 elevation에서 medium의 entropy: ', h1_ele_medium)
# h1층의 피처 elevation에서 medium의 entropy: 1.0
# final h1_ele
h1_ele = 3/7 * h1_ele_high + 1/7 * 0 + 1/7 * 0 + 2/7 * h1_ele_medium
print('h1층의 피처 elevation의 최종 entropy: ', h1_ele)
# h1층의 피처 elevation의 최종 entropy: 0.6792696431662097
따라서 H1 ELEVATION의 entropy = 0.6793
root node의 entropy와 IG 비교
| Parent Entropy | 1.5 | |
|---|---|---|
| feature | Rem | Information Gain |
| STREAM | 1.257 | 0.243 |
| SLOPE | 0.9793 | 0.5207 |
| ELEVATION | 0.6793 | 0.8207 |
- Decision Tree는 특정 feature로 분기한 결과 entropy값이 가장 작은(불순도가 낮은) 경우,
- 즉 Information Gain이 높게 나오는 경우를 최적의 child node로 판단한다.
따라서 h1층에 최종적으로 선택되는 노드는 ELEVATION이다.
2️⃣ Split by Feature (H2)
- Root node에서 피처 Elevation으로 분기한 결과,
- child node는 highest, high, medium, low 총 4개이다.
HIGHEST
| ID | ELEVATION | VEGETATION |
|---|---|---|
| 6 | highest | conifer |
HIGH
| ID | ELEVATION | VEGETATION |
|---|---|---|
| 1 | high | chapparal |
| 5 | high | conifer |
| 7 | high | chapparal |
MEDIUM
| ID | ELEVATION | VEGETATION |
|---|---|---|
| 3 | medium | riparian |
| 4 | medium | chapparal |
LOW
| ID | ELEVATION | VEGETATION |
|---|---|---|
| 2 | low | riparian |
#️⃣ h1 층 Decision Tree 그림
- 이중 인스턴스(데이터)가 1개라서 더이상 분기하지 않아도 되는 highest와 low를 제외한
- 2가지(high, medium)은 기존 데이터의 다른 feature를 선택하여 분기하여야 한다.
2️⃣-🅰 Split by Feature (H2 - High)
#️⃣ STREAM
ELEVATION high
| 행 레이블 | TRUE | FALSE | 총합계 |
|---|---|---|---|
| chapparal | 1 | 1 | 2 |
| conifer | 1 | 1 | |
| 총합계 | 1 | 2 | 3 |
CODE
'''high node'''
# stream
# false
probs = [1/2, 1/2]
probs = np.array(probs)
h2_str_f = -np.sum(probs * np.log2(probs))
print('h2층의 피처 stream에서 false의 entropy: ', h2_str_f)
# h2층의 피처 stream에서 false의 entropy: 1.0
# final h1_str
h2_str = 1/3 * 0 + 2/3 * h2_str_f
print('h2층의 피처 stream의 최종 entropy: ', h2_str)
# h2층의 피처 stream의 최종 entropy: 0.6666666666666666
h2층의 피처 stream의 최종 entropy: 0.6666
#️⃣ SLOPE
ELEVATION high
개수 : ID 열 레이블
| 행 레이블 | flat | steep | 총합계 |
|---|---|---|---|
| chapparal | 2 | 2 | |
| conifer | 1 | 1 | |
| 총합계 | 1 | 2 | 3 |
SLOPE 기준으로 chapparal과 conifer가 정확하게 분류되었기 때문에,
불순도가 없는 것이다.
h2층의 피처 slope의 최종 entropy: 0
따라서 h1층에 최종적으로 선택되는 노드는 SLOPE이다.
#️⃣ H2-A Decision Tree 그림
2️⃣-🅱 Split by Feature (H2 - Medium)
#️⃣ STREAM
ELEVATION medium
개수 : ID 열 레이블
| 행 레이블 | TRUE | FALSE | 총합계 |
|---|---|---|---|
| chapparal | 1 | 1 | |
| riparian | 1 | 1 | |
| 총합계 | 1 | 1 | 2 |
STREAM 기준으로 chapparal과 riparian이 정확하게 분류되었기 때문에,
불순도가 없는 것이다.
h2층의 피처 stream의 최종 entropy: 0
#️⃣ SLOPE
ELEVATION medium
개수 : ID 열 레이블
| 행 레이블 | steep | 총합계 |
|---|---|---|
| chapparal | 1 | 1 |
| riparian | 1 | 1 |
| 총합계 | 2 | 2 |
CODE
'''medium node'''
# slope
# steep
probs = [1/2, 1/2]
probs = np.array(probs)
h2_slo_s = -np.sum(probs * np.log2(probs))
print('h2층의 피처 slope에서 steep의 entropy: ', h2_slo_s)
# h2층의 피처 slope에서 steep의 entropy: 1.0
- STREAM 기준으로 분류했을 때, chapparal 1/2 riparian1/2 이기 때문에 weight는 1이다.
- (2종류가 1/2씩일 때 weight 1이라고 암기)
h2층의 피처 slope의 최종 entropy: 1
Parent E 1
| feature | Rem | Information Gain |
|---|---|---|
| STREAM | 0 | 1 |
| SLOPE | 1 | 0 |
- stream의 불순도가 0으로 정확하게 분류했다.
- -> stream은 기존 parent node의 entropy와 차이가 1으로
- 0인 slope보다 크게 나타났다.
- (IG값이 크기때문에 stream이 더 최적이라는 의미)
따라서 h2층의 Medium노드의 자식 노드로 선택되는 노드는 STREAM이다.
최종 Decision Tree 그림
The vegetation classification dataset은 총 2층의 depth 짜리 decision tree로 데이터를 분류할 수 있다.
'Education > 새싹 TIL' 카테고리의 다른 글
| 새싹 AI데이터엔지니어 핀테커스 7주차 (월) - Decision Tree with Continuous Values (1) | 2023.10.17 |
|---|---|
| 새싹 AI데이터엔지니어 핀테커스 6주차 (금) - Decision Tree with IGR (0) | 2023.10.14 |
| 새싹 AI데이터엔지니어 핀테커스 6주차 (수) - KNN(full code) (1) | 2023.10.11 |
| 새싹 AI데이터엔지니어 핀테커스 6주차 (화) - KNN (1) | 2023.10.10 |
| 새싹 AI데이터엔지니어 핀테커스 5주차 (금) - Boxplot, Numpy (1) | 2023.10.06 |