과제 10

source('./util.R')

mycolor = c(myred, mygreen, myblue)
listVec = list(c(1/2, 1/2, 2), c(1/3, 4/3, 1), c(2/3, 5/3, 2), 
	c(1/2, 7/3, 1), c(1/2, 8/3, 1),	c(4/3, 1/3, 3), c(5/3, 2/3, 2), 
	c(3/2, 3/2, 2), c(3/2, 5/2, 1),	c(5/2, 1/2, 3), c(7/3, 5/3, 3), 
	c(8/3, 4/3, 1), c(7/3, 5/2, 3), c(8/3, 5/2, 3))
M = do.call(rbind, listVec)
options(repr.plot.width=5.5, repr.plot.height=6)
plot(c(0,3), c(0,3), cex.axis=1.15, cex.lab=1.15, 
	type="n", xlab="X1", ylab="X2")
points(M[,1], M[,2], pch=20, cex=1.5, col=mycolor[as.vector(M[,3])])

• 위와 같은 데이터가 주어졌을 때 두 번 분할(split)하여 분류나무를 만들고자 한다.
• 분할 경계는 X1=1, X1=2, X2=1, X2=2 로 제한한다.
• 그리디(Greedy) 알고리듬을 사용한다.

1. 분할하기 전의 초기 엔트로피 ent_init를 구하여라.
2. 첫 분할에서 4가지 경우 각각에 대하여 엔트로피가 얼마나 감소했는지 계산하고 최적의 분할을 선택하여라.
3. 첫 분할에서 얻은 두 개의 영역 각각에 대하여 가능한 모든 분할과 그때의 엔트로피의 감소를 계산하고 최적의 분할을 선택하여라.
4. 최종적으로 얻은 분류나무의 엔트로피 ent_final를 구하여라.
5. ent_init - ent_final = entropy_decrement_1st + entropy decrement_2nd 임을 확인하여라.

• 엔트로피의 값은 소숫점 이하 4자리까지 나타낸다.

entropy = function(pvec) {
    pvec = to_vec(for(p in pvec) if(p > 0) p) # remove 0's from pvec
    return(- sum(pvec * log(pvec)))
}

N_all = length(listVec) # number of all dots
nred = length(to_vec(for(i in 1:N_all) if(M[i,3]==1) i)) # number of red dots
ngreen = length(to_vec(for(i in 1:N_all) if(M[i,3]==2) i)) # number of green dots
nblue = length(to_vec(for(i in 1:N_all) if(M[i,3]==3) i)) # number of blue dots
cat("number of dots =", N_all, nred, ngreen, nblue, "\n")
pvec = c(nred, ngreen, nblue)/N_all
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("initial entropy = %.4f\n", ent_init <- entropy(pvec)))

number of dots = 14 5 4 5 
pvec = (0.357, 0.286, 0.357) 
initial entropy = 1.0934

# Split by X1 = 1, obtain R111 and R112.
R111 = to_vec(for(i in 1:N_all) if(M[i,1] < 1) i) # 1st region 
R112 = to_vec(for(i in 1:N_all) if(M[i,1] >= 1) i) # 2nd region

N111 = length(R111)
n111r = length(to_vec(for(i in R111) if(M[i,3]==1) i))
n111g = length(to_vec(for(i in R111) if(M[i,3]==2) i))
n111b = length(to_vec(for(i in R111) if(M[i,3]==3) i))
cat("number of dots =", N111, n111r, n111g, n111b, "\n")
pvec = c(n111r, n111g, n111b)/N111
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 111 = %.4f\n", ent111 <- entropy(pvec)))

N112 = length(R112)
n112r = length(to_vec(for(i in R112) if(M[i,3]==1) i))
n112g = length(to_vec(for(i in R112) if(M[i,3]==2) i))
n112b = length(to_vec(for(i in R112) if(M[i,3]==3) i))
cat("number of dots =", N112, n112r, n112g, n112b , "\n")
pvec = c(n112r, n112g, n112b)/N112
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 112 = %.4f\n", ent112 <- entropy(pvec)))

ent11 = (ent111*N111 + ent112*N112)/N_all
dec11 = ent_init - ent11
cat(sprintf("entropy decrement by X1:1 = %.4f\n", dec11))

number of dots = 5 3 2 0 
pvec = (0.600, 0.400, 0.000) 
entropy 111 = 0.6730
number of dots = 9 2 2 5 
pvec = (0.222, 0.222, 0.556) 
entropy 112 = 0.9950
entropy decrement by X1:1 = 0.2134

# Split by X1 = 2, obtain R121 and R122.
R121 = to_vec(for(i in 1:N_all) if(M[i,1] < 2) i) # 1st region
R122 = to_vec(for(i in 1:N_all) if(M[i,1] >= 2) i) # 2nd region

N121 = length(R121)
n121r = length(to_vec(for(i in R121) if(M[i,3]==1) i))
n121g = length(to_vec(for(i in R121) if(M[i,3]==2) i))
n121b = length(to_vec(for(i in R121) if(M[i,3]==3) i))
cat("number of dots =", N121, n121r, n121g, n121b, "\n")
pvec = c(n121r, n121g, n121b)/N121
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 121 = %.4f\n", ent121 <- entropy(pvec)))

N122 = length(R122)
n122r = length(to_vec(for(i in R122) if(M[i,3]==1) i))
n122g = length(to_vec(for(i in R122) if(M[i,3]==2) i))
n122b = length(to_vec(for(i in R122) if(M[i,3]==3) i))
cat("number of dots =", N122, n122r, n122g, n122b, "\n")
pvec = c(n122r, n122g, n122b)/N122
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 122 = %.4f\n", ent122 <- entropy(pvec)))

ent12 = (ent121*N121 + ent122*N122)/N_all # 두 엔트로피의 가중평균
dec12 = ent_init - ent12
cat(sprintf("entropy decrement by X1:2 = %.4f\n", dec12))

number of dots = 9 4 4 1 
pvec = (0.444, 0.444, 0.111) 
entropy 121 = 0.9650
number of dots = 5 1 0 4 
pvec = (0.200, 0.000, 0.800) 
entropy 122 = 0.5004
entropy decrement by X1:2 = 0.2943

# Split by X2 = 1, obtain R211 and R212.
# 여기에 코드를 넣는다.

# Split by X2 = 2, obtain R221 and R222.
# 여기에 코드를 넣는다.

1. 이상 4개의 분할 중에 가장 좋은 것 하나를 택한다.
2. 2개의 영역에 대해서 가능한 모든 분할을 시도하여 엔트로피가 가장 크게 감소하는 것을 선택한다.
3. 예를 들어 X1=1이 가장 좋게 나타났다면 다음과 같은 5개의 분할들이 가능하다.
   • Split R111 by X2 = 1, obtain R111_211 and R111_212
   • Split R111 by X2 = 2, obtain R111_221 and R111_222
   • Split R112 by X1 = 2, obtain R112_121 and R112_122
   • Split R112 by X2 = 1, obtain R112_211 and R112_212
   • Split R112 by X2 = 2, obtain R112_221 and R112_222

# 두 번째 분할들은 어떻게 진행되는지를 보여주기 위한 예이다.
# R111의 분할 2개와 R112의 분할 3개, 총 5개 중에 3개만 아래에 계산해 보았다.
# 이 쎌은 과제를 제출하기 전에 삭제한다.

# Split R111 by X2 = 1, obtain R111_211 and R111_212
# 이 쎌은 과제를 제출하기 전에 삭제한다.
R111_211 = to_vec(for(i in R111) if(M[i,2] < 1) i) 
R111_212 = to_vec(for(i in R111) if(M[i,2] >= 1) i) 

N111_211 = length(R111_211)
n111_211r = length(to_vec(for(i in R111_211) if(M[i,3]==1) i))
n111_211g = length(to_vec(for(i in R111_211) if(M[i,3]==2) i))
n111_211b = length(to_vec(for(i in R111_211) if(M[i,3]==3) i))
cat("number of dots =", N111_211, n111_211r, n111_211g, n111_211b, "\n")
pvec = c(n111_211r, n111_211g, n111_211b)/N111_211
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 111_211 = %.4f\n", ent111_211 <- entropy(pvec)))

N111_212 = length(R111_212)
n111_212r = length(to_vec(for(i in R111_212) if(M[i,3]==1) i))
n111_212g = length(to_vec(for(i in R111_212) if(M[i,3]==2) i))
n111_212b = length(to_vec(for(i in R111_212) if(M[i,3]==3) i))
cat("number of dots =", N111_212, n111_212r, n111_212g, n111_212b, "\n")
pvec = c(n111_212r, n111_212g, n111_212b)/N111_212
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 111_212 = %.4f\n", ent111_212 <- entropy(pvec)))

ent111_21 = (ent111_211*N111_211 + ent111_212*N111_212)/N111 # 두 엔트로피의 가중평균
cat(sprintf("entropy 111_21 = %.4f\n", ent111_21))
dec111_21 = (ent111 - ent111_21)*N111/N_all
cat(sprintf("entropy decrement by X2:1 = %.4f\n", dec111_21))

number of dots = 1 0 1 0 
pvec = (0.000, 1.000, 0.000) 
entropy 111_211 = -0.0000
number of dots = 4 3 1 0 
pvec = (0.750, 0.250, 0.000) 
entropy 111_212 = 0.5623
entropy 111_21 = 0.4499
entropy decrement by X2:1 = 0.0797

# Split R111 by X2 = 2, obtain R111_221 and R111_222
# 이 쎌은 과제를 제출하기 전에 삭제한다.
R111_221 = to_vec(for(i in R111) if(M[i,2] < 2) i) 
R111_222 = to_vec(for(i in R111) if(M[i,2] >= 2) i) 

N111_221 = length(R111_221)
n111_221r = length(to_vec(for(i in R111_221) if(M[i,3]==1) i))
n111_221g = length(to_vec(for(i in R111_221) if(M[i,3]==2) i))
n111_221b = length(to_vec(for(i in R111_221) if(M[i,3]==3) i))
cat("number of dots =", N111_221, n111_221r, n111_221g, n111_221b, "\n")
pvec = c(n111_221r, n111_221g, n111_221b)/N111_221
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 111_221 = %.4f\n", ent111_221 <- entropy(pvec)))

N111_222 = length(R111_222)
n111_222r = length(to_vec(for(i in R111_222) if(M[i,3]==1) i))
n111_222g = length(to_vec(for(i in R111_222) if(M[i,3]==2) i))
n111_222b = length(to_vec(for(i in R111_222) if(M[i,3]==3) i))
cat("number of dots =", N111_222, n111_222r, n111_222g, n111_222b, "\n")
pvec = c(n111_222r, n111_222g, n111_222b)/N111_222
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 111_222 = %.4f\n", ent111_222 <- entropy(pvec)))

ent111_22 = (ent111_221*N111_221 + ent111_222*N111_222)/N111 # 두 엔트로피의 가중평균
cat(sprintf("entropy 111_22 = %.4f\n", ent111_22))
dec111_22 = (ent111 - ent111_22)*N111/N_all
cat(sprintf("entropy decrement by X2:2 = %.4f\n", dec111_22))

number of dots = 3 1 2 0 
pvec = (0.333, 0.667, 0.000) 
entropy 111_221 = 0.6365
number of dots = 2 2 0 0 
pvec = (1.000, 0.000, 0.000) 
entropy 111_222 = -0.0000
entropy 111_22 = 0.3819
entropy decrement by X2:2 = 0.1040

# Split R112 by X1 = 2, obtain R112_121 and R112_122
# 이 쎌은 과제를 제출하기 전에 삭제한다.
R112_121 = to_vec(for(i in R112) if(M[i,1] < 2) i) 
R112_122 = to_vec(for(i in R112) if(M[i,1] >= 2) i) 

N112_121 = length(R112_121)
n112_121r = length(to_vec(for(i in R112_121) if(M[i,3]==1) i))
n112_121g = length(to_vec(for(i in R112_121) if(M[i,3]==2) i))
n112_121b = length(to_vec(for(i in R112_121) if(M[i,3]==3) i))
cat("number of dots =", N112_121, n112_121r, n112_121g, n112_121b, "\n")
pvec = c(n112_121r, n112_121g, n112_121b)/N112_121
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 112_121 = %.4f\n", ent112_121 <- entropy(pvec)))

N112_122 = length(R112_122)
n112_122r = length(to_vec(for(i in R112_122) if(M[i,3]==1) i))
n112_122g = length(to_vec(for(i in R112_122) if(M[i,3]==2) i))
n112_122b = length(to_vec(for(i in R112_122) if(M[i,3]==3) i))
cat("number of dots =", N112_122, n112_122r, n112_122g, n112_122b, "\n")
pvec = c(n112_122r, n112_122g, n112_122b)/N112_122
cat("pvec =", sprint_vec(pvec), "\n")
cat(sprintf("entropy 112_122 = %.4f\n", ent112_122 <- entropy(pvec)))

ent112_12 = (ent112_121*N112_121 + ent112_122*N112_122)/N112 # 두 엔트로피의 가중평균
cat(sprintf("entropy 112_12 = %.4f\n", ent112_12))
dec112_12 = (ent112 - ent112_12)*N112/N_all
cat(sprintf("entropy decrement by X1:2 = %.4f\n", dec112_12))

number of dots = 4 1 2 1 
pvec = (0.250, 0.500, 0.250) 
entropy 112_121 = 1.0397
number of dots = 5 1 0 4 
pvec = (0.200, 0.000, 0.800) 
entropy 112_122 = 0.5004
entropy 112_12 = 0.7401
entropy decrement by X1:2 = 0.1639

# 다음의 쎌을 문제 풀이에 참고하십시오.

options(repr.plot.width=5.5, repr.plot.height=6)
plot(c(0,3), c(0,3), type="n", xlab="X1", ylab="X2",
    cex.axis=1.15, cex.lab=1.15)
points(M[,1], M[,2], pch=20, cex=1.5, col=mycolor[as.vector(M[,3])])
labels = character(N_all)
for(i in R121_221) { labels[i] = "G" }
for(i in R121_222) { labels[i] = "R" }
for(i in R122) { labels[i] = "B" }
text(M[,1], M[,2], labels, pos=2)
abline(v=2, col=mygray)
segments(-0.5,2,2,2,col=mygray)

# 4. Compute the final entropy := ent_final
# 5. Verify that ent_init - ent_final = dec** - dec**_***