Dasein's ‎Archive

문제링크 : www.acmicpc.net/problem/1436

정답 코드

N = int(input())
n = 666
count = 0

while True:
    if '666' in str(n):
        count += 1
    
    if count == N:
        print(n)
        break
    n += 1

문제 풀이

이번 문제는 가능한 모든 경우의 수를 검사하는 '브루트포스 알고리즘'에 해당하는 문제이다.

문제에서 가장 중요하게 요구되는 것은 연속된 3번 이상의 6을 포함한 숫자를 찾는 것이다.

1. 666

2. 1666

3. 2666

4. 3666

5. 4666

...

처음 1번째 수는 666으로 지정하고 그로부터 '666'이 포함된 숫자를 찾아나가며, 숫자를 찾을 때마다 count를 1씩 증가시킨다. 이 과정을 반복하면서 찾으려고하는 N번째 숫자와 count가 일치하면 반복문을 종료하며, 결과값을 출력한다.

루프 불변성은 알고리즘이 타당한 이유를 쉽게 이해할 수 있도록 하기 위해서 사용된다.

루프 불변성을 보이기 위해서 세 가지 특성인 초기조건, 유지조건, 종료조건을 모두 만족해야 한다.

• 초기조건: 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다.
• 유지조건: 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도 계속 참이어야 한다.
• 종료조건: 루프가 종료될 때 그 불변식이 알고리즘의 타당성을 보이는 데 도움이 될 유용한 특성을 가져야 한다.

초기조건과 유지조건을 만족하면 루프가 반복을 시작하는 순간에 루프 불변성은 항상 참이다. 첫 반복이 시작되기 전에 불변식을 만족함을 보이고, 다음 반복으로 넘어갈 때 불변식이 만족함을 보이는 것은 수학적 귀납법과 유사하다.

※ 수학적 귀납법이란?

- P(0)이 성립한다.
- 임의의 $n \in N$에 대하여, $P(n)$이 성립한다면, $P(n+1)$ 역시 성립한다.(여기서, $N$은 자연수 집합)

그렇다면, 임의의 $n \in N$에 대하여, $P(n)$이 성립한다. 이것을 수학적 귀납법이라고 한다.

종료조건이 가장 중요한데, 이는 루프 불변성을 보이는 목적이 결국 알고리즘의 타당성을 보이는 것이기 때문이다.

보통 루프의 종료조건이 완료될 때까지 루프 불변성을 이용한다. 일반적인 수학적 귀납법은 귀납적 과정이 무한히 반복되는 데 반해 여기서는 루프가 종료될 때 귀납적 과정도 끝난다.

루프 불변성의 개념을 삽입 정렬에 적용시켜서 삽입 정렬 알고리즘이 타당함을 보이려고 한다.

아래의 의사코드는 정렬된 배열 $A[1, ..., j-1]$에 새로운 값인 $A[j]$를 삽입하는 삽입정렬의 의사코드이다.

INSERTION-SORT(A)

for j=2 to A.length
	key = A[j]
    // A[j]를 정렬된 배열 A[1, ..., j-1]에 삽입한다.
    i = j - 1
    
    while i>0 and A[i] > key
    	A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

• 초기조건: 루프의 첫 반복이 시작하는 시점인 $j=2$일 때 루프 불변성이 성립하는지 살펴본다. 시작하는 경우 부분배열 A[1 ... j-1]은 A[1] 한 개의 원소로 구성되어 있으므로 정렬되어 있으므로, 루프의 첫 반복 시작 전에 루프 불변성이 만족한다.
• 유지조건: 매 반복 시 루프 불변성이 유지되는지를 살펴본다. 삽입 정렬에서는 A[j]가 올바른 위치를 찾을 때까지 기존의 부분 배열을 오른쪽으로 한 칸씩 이동시키면서 적절한 위치에 삽입된다. 따라서 매 반복시 부분 배열인 A[1 ... j]는 정렬된 상태로 유지된다. 따라서 루프 불변성이 유지된다.
• 종료조건: 루프가 종료 되었을 때 어떤 상황이 발생하는지 조사해본다. 삽입 정렬의 경우에는 전체 배열인 A[1 ... n]이 정렬되었으면 알고리즘이 타당함을 의미한다.

3. 계층적 클러스터링

* 계층적 클러스터링(hierarchical clustering)

- K 평균 대신 사용하는 클러스터링 방법으로 K 평균과는 아주 다른 결과를 보여준다.

- K 평균보다 유연하고, 수치형 변수가 아니라도 쉽게 적용이 가능하다.

- 특잇점이나 비정상적인 그룹이나 레코드를 발견하는 데 민감한다. 또한, 직관적인 시각화가 가능하여 클러스터를 해석하기가 수월하다

※ 계층적 클러스터링의 유연성에는 비용이 따른다.

→ 수백만 개의 레코드가 있는 대규모 데이터에는 적용할 수 없다. 따라서 계층적 클러스터링은 대부분 상대적으로 데이터 크기가 작은 문제에 주로 적용된다.

1) 간단한 예제

  $n$개의 레코드와 $p$개의 변수가 있는 일반적인 데이터에 대해 적용한 계층적 클러스터링은 아래 두 가지 기본 구성 요소를 기반으로 한다.

• 두 개의 레코드 $i$와 $j$ 사이의 거리를 측정하기 위한 거리 측정 지표 $d_{i,j}$
• 두 개의 클러스터 $A$와 $B$ 사이의 차이를 측정하기 위한, 각 클러스터 구성원 간의 거리 $d_{i,j}$를 기반으로 한 비유사도 측정지표 $D_{A,B}$

- 계층적 클러스터링은 각 레코드 자체를 개별 클러스터로 설정하여 시작하고 가장 가까운 클러스터를 결합해나가는 작업을 반복한다.

- R에서는 hclust 함수를 사용하여 계층적 클러스터링을 수행할 수 있다.

2)  덴드로그램

- 계층적 클러스터링은 트리 모델과 같이 자연스러운 시각적 표현이 가능하며, 이를 덴드로그램 이라고 한다.

- R에서는 plot 명령을 사용하여 이를 생성할 수 있다.

- 트리의 잎은 각 레코드들을 의미하며, 트리의 가지 길이는 해당 클러스터 간의 차이 정도를 나타낸다.

- K 평균과 달리 클러스터의 수를 미리 지정할 필요는 없다. cutree 함수를 사용하면 원하는 개수의 클러스터를 추출할 수 있다.

3) 병합 알고리즘

- 계층적 클러스터링에서 가장 중요한 알고리즘은 병합(agglomerative) 알고리즘이다.

- 병합 알고리즘은 단일 레코드로 구성된 클러스터에서 시작하여 점점 더 큰 클러스터를 만든다.

< 알고리즘 >

1. 데이터의 모든 레코드에 대해, 단일 레코드로만 구성된 클러스터들로 초기 클러스터 집합을 만든다.
2. 모든 쌍의 클러스터 $k,l$ 사이의 비유사도 $D(C_k, C_l)$을 계산한다.
3. $D(C_k, C_l)$에 따라 가장 가까운 두 클러스터 $C_k$와 $C_l$을 병합한다.
4. 둘 이상의 클러스터가 남아 있으면 2단계로 다시 돌아간다. 그렇지 않고 클러스터가 하나 남는다면 알고리즘을 멈춘다.

4) 비유사도 측정

- 각 레코드 쌍 $(x_1, x_2, \cdot\cdot\cdot, x_p)$와 $(y_1, y_2, \cdot\cdot\cdot, y_p)$에 대해 거리지표를 사용하여 두 레코드 사이의 거리 $d_{x,y}$를 측정한다. 예를 들어 아래의 유클리드 거리를 사용할 수 있다.

$d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\cdot\cdot\cdot+(x_p-y_p)^2}$

* 완전연결(complete linkage) 방식

- A와 B 사이의 모든 레코드 쌍의 최대 거리를 사용한다.

$D(A,B) = max d(a_i, b_j)$ 모든 $i,j$ 쌍에 대해

* 단일연결(single linkage) 방식

- 두 클러스터의 레코드 간 최소 거리를 사용한다.

$D(A,B) = min d(a_i, b_j)$ 모든 $i,j$ 쌍에 대해

* 평균연결(average linkage) 방식

- 모든 거리 쌍의 평균을 사용하는 방법으로 이는 단일 연결과 완전연결 방법 사이를 절충한 방법이다.

* 최소분산(minimum varuance) 방식 = 워드 기법(Ward's method)

- 클러스터 내의 제곱합을 최소화하므로 K 평균과 유사하다고 할 수 있다.

· 모든 레코드를 각각 자체 클러스터로 할당하여 알고리즘을 시작한다.
· 클러스터들은 모든 레코드가 하나의 클러스터에 속할 때까지 가까운 클러스터와 계속해서 연결된다(병합 알고리즘).
· 병합 과정은 내역이 남고 시각화할 수 있으며, 사용자가 미리 클러스터 수를 지정하지 않더라도 여러 단계에서 클러스터의 수와 구조를 시각화할 수 있다.
· 클러스터 간 거리는 모든 레코드 간 거리 정보를 사용하여 여러 가지 다른 방식으로 계산할 수 있다.

4. 모델 기반 클러스터링

- 계층적 클러스터링과 K 평균 같은 클러스터링 방법들은 모두 휴리스틱한 방법이다.

1) 다변량정규분포

- 다변량정규분포(multivariate normal distribution)는 $p$개의 변수집합 $X_1, X_2, \cdot\cdot\cdot, X_p$에 대해 정규분포를 일반화한 것이다.

- 분포는 평균 집합 $\mu=\mu_1,\mu_2,\cdot\cdot\cdot,\mu_p$과 공분산행렬 $\sum\로 정의된다.

- 공분산행렬 $\sum$는 $p$개의 분산 $\sigma_1^2,\sigma_2^2,\cdot\cdot\cdot,\sigma_p^2$과 $i\neq j$인 모든 변수 쌍에 대한 공분산$\sigma_{i,j}$로 구성된다.

$(X_1, X_2, \cdot\cdot\cdot, X_p)\tilde{N_p}(\mu,\sum)$

이 기호는 변수들이 모두 정규분포를 따른다는 뜻이며, 전체 분포가 변수의 평균 벡터와 공분산행렬에 의해 완벽히 설명된다는 것을 나타낸다.

2) 정규혼합

- 모델 기반 클러스터링의 핵심 아이디어는 각 레코드가 K개의 다변량정규분포 중 하나로부터 발생했다고 가정하는 것이다.

- R에서는 모델 기반 클러스터링을 위해 mclust라는 패키지를 제공한다.

- 모델 기반 클러스터링의 목적은 사실 데이터를 가장 잘 설명하는 다변량정규분포를 찾는 것이다.

3) 클러스터 개수 설정하기

- mclust는 베이즈 정보기준(BIC; Bayesian information criteria) 값이 가장 큰 클러스터의 개수를 선택하도록 동작하기 때문에 클러스터 수를 자동으로 선택한다.

< 모델 기반 클러스터링 기술의 한계 >

- 기본적으로 데이터들이 모델을 따른다는 가정이 필요하다.

- 필요한 계산량 역시 계층적 클러스터링보다 높다.

- 다른 방법들보다 알고리즘이 더 복잡하고 이용하기가 어렵다.

· 클러스터들이 각자 서로 다른 확률분포로부터 발생한 것으로 가정한다.
· 분포(일반적으로 정규분포) 개수에 대한 가정에 따라 서로 다른 적합한 모델이 있다.
· 이 방법은 너무 많은 파라미터(오버피팅의 원인이 될 수 있다)를 사용하지 않으면서도 데이터에 대한 적합한 모델(그리고 연관된 클러스터 개수)을 선택한다.

5. 스케일링과 범주형 변수

- 비지도 학습 기술을 이용할 때는 일반적으로 데이터를 적절하게 스케일해야 한다.

- 범주형 데이터는 일부 클러스터링 과정에서 특별한 문제를 일으킬 수 있으므로, 순서가 없는 요인변수는 일반적으로 원-핫 인코딩을 사용하여 이진(0/1) 변수 집합으로 변환한다.

1) 변수 스케일링

- 매우 다른 스케일 및 단위를 갖는 변수는 클러스터링 절차를 적용하기 전에 적절히 정규화해야 한다.

- 표준화 또는 정규화는 변수를 스케일링하는 일반적인 방법이다.

$z=\frac{x-\bar{x}}{s}$

2) 지배 변수

- 변수들이 서로 동일한 규모로 측정되고 상대적 중요성을 정확하게 반영하는 경우조차도 변수의 스케일을 재조정하는 것이 유용할 수 있다.

- 특정 주성분에 의해 지배되고 있는 경우에는 변수를 스케일링해서 포함하거나, 특정 지배 변수를 전체 분석에서 제외하고 별도로 처리할 수도 있다.

→ 어떤 방법이 항상 옳다고는 할 수 없으며 응용 분야에 따라 달라진다.

3) 범주형 데이터와 고워 거리

- 범주형 데이터가 있는 경우에는 순서형(정렬된 요인) 변수 또는 이진형(더미) 변수를 사용하여 수치형 데이터로 변환해야 한다.

- 데이터를 구성하는 변수들에 연속형과 이진형 변수가 섞여 있는 경우에는 비슷한 스케일이 되도록 변수의 크기를 조정해야 한다.

→ 이를 위한 대표적인 방법은 고워 거리를 사용하는 것이다.

고워 거리의 기본 아이디어는 각 변수의 데이터 유형에 따라 거리 지표를 다르게 적용하는 것이다.

• 수치형 변수나 순서형 요소에서 두 레코드 간의 거리는 차이의 절댓값(맨하탄 거리)으로 계산한다.
• 범주형 변수의 경우 두 레코드 사이의 범주가 서로 다르면 거리가 1이고 범주가 동일하면 거리는 0이다.

< 고워 거리의 계산 >

1. 각 레코드의 변수 $i$와 $j$의 모든 쌍에 대해 거리 $d_{i,j}$를 계산한다.
2. 각 $d_{i,j}$의 크기를 최솟값잉 0이고 최댓값이 1이 되도록 스케일을 조정한다.
3. 거리 행렬을 구하기 위해 변수 간에 스케일된 거리를 모두 더한 후 평균 혹은 가중평균을 계산한다.

- cluster 패키지의 daisy 함수를 사용하면 고워 거리를 계산할 수 있다.

4) 혼합 데이터의 클러스터링 문제

- K 평균과 PCA는 연속형 변수에 가장 적합하다.

- 데이터 집합의 크기가 더 작아질수록 고워 거리를 사용하여 계층적 클러스터링을 하는 것이 좋다.

- 실무에서는 K 평균과 PCA를 이진형 데이터와 함께 사용하는 것은 어려울 수 있다.

· 스케일이 서로 다른 변수들을 스케일이 비슷하도록 변환하여, 스케일이 알고리즘에 큰 영향을 미치지 않도록 한다.
· 일반적인 스케일링 방법은 각 변수에서 평균을 빼고 표준편차로 나눠주는 정규화(표준화) 방법이다.
· 또 다른 방법은 고워거리를 사용하는 것이다. 이 방법은 모든 변수를 0~1  범위로 스케일링한다(수치형과 범주형 데이터가 서로 혼합된 경우에 많이 사용된다).

- 주성분분석과 K 평균 클러스터링은 수치형 데이터의 차원을 축소하기 위해 주로 사용되는 방법이다.

- K 평균은 매우 큰 데이터로 확장이 가능하고 이해하기 쉽다.

- 계층적 클러스터링은 수치형과 범주형이 혼합된 데이터 유형에 적용이 가능하며 직관적인 시각화 방법(댄드로그램)이 존재한다.

- 모델 기반 클러스터링은 휴리스틱한 방법들과 달리 통계 이론에 기초를 두고 있으며 더 엄밀한 접근 방식을 제시한다.

→ 그러나 데이터가 커지면 K 평균이 가장 많이 사용되는 방법이다.

< 참고자료 >
1. Peter Brucs & Andrwe Brucs(2018). 데이터 과학을 위한 통계. 한빛미디어. 이용준 옮김

비지도 학습(unsupervised learning)

- 레이블이 달린 데이터를 이용해 모델을 학습하는 과정 없이 데이터로부터 의미를 이끌어내는 통계적 기법.

- 데이터로부터 모델을 만드는 것이 목적이긴 하지만, 응답변수와 예측변수 사이의 구분이 없다.

< 비지도 학습의 목적 >

- 데이터의 의미 있는 그룹들을 찾기 위해 클러스터링(clustering)을 사용한다.

- 데이터의 변수들을 관리할 수 있을 만한 수준으로 차원을 줄이는 것(reducing the dimension).

- 변수와 레코드의 수가 아주 큰 상황이라면, 데이터 비지도 학습을 탐색적 데이터 분석의 연장으로 볼 수 있다.

< 비지도 학습과 예측 >

- 클러스터링은 특히 콜드스타트(cold-start) 문제에서 유용한 방법이다.

→ 패턴이 비슷한 데이터들을 분류하여 학습 과정을 더 빨리 시작할 수 있도록 도와준다.

- 빅데이터에서 어떤 작은 부모집단(subpopulation)이 전체 모집단을 잘 대표하지 못한다면, 미리 학습된 모델은 이 부모집단에 대해 좋은 성능을 보일 수 없을 것이다.

→ 클러스터링을 사용하면 부모집단을 식별하고 레이블을 지정할 수 있다.

1. 주성분분석

- 주성분분석(PCA; principal components analysis)은 수치형 변수가 어떤 식으로 공변하는지 알아내는 기법이다.

- PCA의 아이디어는 다수의 수치형 예측변수들을 더 적은 수의 변수들의 집합으로 나타내는 것이다.

- 새로운 변수들은 원래 변수들에 가중치를 적용한 선형결합을 의미한다.

- 전체 변수들의 변동성을 거의 대부분 설명할 수 있는 적은 수의 변수들의 집합을 주성분이라고 하며, 이를 이용해 데이터의 차원을 줄일 수 있다.

1) 예제

두 변수 $X_1$과 $X_2$에 대해 두 주성분 $Z_i$($i$=1또는 2)이 있다고 하자.

$Z_i=w_{i,1}X_1 + w_{i,2}X_2$

- 가중치 $(w_{i,1},w_{i,2})$를 주성분의 부하라고 한다.

- $Z_1$은 전체 변동성을 가장 잘 설명하는 선형결합.

- $Z_2$는 나머지 변동성을 설명한다.(동시에 최악의 비팅을 보이는 선형 조합이기도 하다.)

- R에서는 princomp 함수를 이용해 주성분을 계산할 수 있다.

2) 주성분 계산

1. 첫 번째 주성분을 구하기 위해 PCA는 전체 변동을 최대한 설명하기 위한 예측변수의 선형결합을 구한다.
2. 이 선형결합은 첫 번째 예측변수 $Z_1$이 된다.
3. 같은 변수들을 이용해 새로운 두 번째 변수 $Z_2$를 만들기 위해, 다른 가중치를 가지고 이 과정을 반복한다. 가중치는 $Z_1$과 $Z_2$가 서로 상관성이 없도록 결정한다.
4. 원래 변수 $X_i$의 개수만큼 새로운 변수 $Z_i$를 구할 때까지 이 과정을 계속한다.
5. 대부분의 변동을 설명하기 위해 필요한 만큼의 주성분을 선택해 남겨놓는다.
6. 결과적으로 각 주성분에 대한 가중치 집합을 얻게 된다. 마지막 단계는 원래 데이터를 이 가중치들을 적용해 새로운 주성분으로 변형하는 것이다. 이렇게 얻은 새로운 값들을 예측변수들의 차원이 축소된 형태로 사용할 수 있다.

3) 주성분 해석

- 주성분의 상대적인 중요도를  표시해주는 스크리그래프 : screeplot 함수를 이용

- 상위 주성분들의 가중치를 표시하는 것 : ggplot 패키지와 함께 tidyr 패키지의 gather 함수를 사용.

· 주성분은 예측변수(수치형)들의 선형결합이다.
· 주성분들은 서로 간의 상관관계가 최소화되며 중복성이 줄어들도록 한다.
· 제한된 개수의 주성분들로도 결과 변수에서 대부분의 변동을 설명할 수 있다.
· 제한된 개수의 주성분들을 원래 예측변수를 대신하여 차원이 감소된 형태로 사용할 수 있다.

2. K 평균 클러스터링

- 클러스터링의 목적은 데이터로부터 유의미한 그룹들을 구하는 것이다.

- K 평균(k-means)은 최초로 개발된 클러스터링 기법이다. 알고리즘이 상대적으로 간단하고 데이터 크기가 커져도 손쉽게 사용할 수 있다는 점에서 아직도 널리 사용되고 있다.

- K 평균은 데이터를 K개의 클러스터로 나눈다. 이때 할당된 클러스터의 평균과 포함된 데이터들의 거리 제곱합이 최소가 되도록 한다. 이것을 클러스터 내 제곱합 또는 클러스터 내 SS라고 한다.

1) 예제

- 변수가 $x, y$ 두 개이고 레코드가 $n$개인 데이터가 있다고 하자. $K=4$, 즉 4개의 클러스터로 데이터를 분할하고 싶다고 가정하자.

- 클러스터 $k$에 $n_k$개의 레코드가 들어 있다고 할 때, 클러스터의 중심 $(\bar{x_i}, \bar{y_i})$는 클러스터 내에 존재하는 점들의 평균을 의미한다.

$\bar{x_k}=\frac{1}{n_k}\sum_{i\in클러스터 k}{x_i}\bar{y_k}$

$=\frac{1}{n_k}\sum_{i\in클러스터 k}{y_i}$

- 클러스터 내부의 제곱합은 아래와 같다.

$SS_k=\sum_{i\in클러스터k}(x_i-\bar{x_k})^2+(y_i-\bar{y_k})^2$

- K 평균은 4개의 모든 클러스터의 내부 제곱합$(SS_1+SS_2+SS_3+SS_4)$이 최소가 되도록 레코드들을 클러스터에 할당하는 방법이다.

- R에서 K 평균 클러스터링을 실행하려면 kmeans 함수를 사용한다.

2) K 평균 알고리즘

- 일반적으로 K 평균은 $p$개의 변수 $X_1,\cdot\cdot\cdot,X_p$를 갖는 데이터에 적용될 수 있다. K 평균은 정확한 해를 계산하기는 매우 어려우므로, 휴리스틱한 방법을 통해 국소 최적화된 해를 효과적으로 계산한다.

- 사용자가 미리 정해준 K 값과 클러스터 평균의 초기값을 가지고 알고리즘을 시작하며, 아래 과정을 반복한다.

1. 각 레코드를 거리가 가장 가까운 평균을 갖는 클러스터에 할당한다.
2. 새로 할당된 레코드들을 가지고 새로운 클러스터 평균을 계산한다.

- 각 레코드에 대한 클러스터 할당이 더 이상 변화하지 않을 때 알고리즘이 수렴했다고 볼 수 있다.

- 첫 번째 단계에서 클러스터 평균의 초기값을 설정할 필요가 있다. 보통은 각 레코드를 K개의 클러스터들 가운데 하나에 랜덤하게 할당한 후 그렇게 얻은 클러스터들의 평균을 사용한다.

3) 클러스터 해석

- kmeans에서 가장 중요한 출력은 클러스터의 크기와 클러스터 평균이다.

- 클러스터 크기는 비교적 균일하다. 유난히 균형이 맞지 않는 클러스터가 존재한다면 이는 멀리 떨어진 특잇점들이 있거나 아니면 어떤 레코드 그룹이 나머지 데이터로부터 아주 멀리 떨어져 있다는 것을 의미한다.

4) 클러스터 개수 선정

* 팔꿈치 방법(elbow method)

- 언제 클러스터 세트가 데이터의 분산의 '대부분'을 설명하는지를 알려준다.

- 새로운 클러스터를 더 추가하면 분산에 대한 기여도가 상대적으로 작아진다. 이는 누적 분산이 가파르게 상승한 다음 어느 순간 평평하게 되는 지점을 의미한다.

※ 일반적으로 클러스터의 개수를 정확히 얻는 완벽한 방법은 없다.

· 사용자가 원하는 클러스터 개수 K를 선택한다.
· K 평균 알고리즘은 더 이상 클러스터가 변하지 않을 때까지 반복해서 클러스터 평균이 가장 가까운 클러스터에 레코드를 할당한다.
· 실무적인 고려 사항을 활용해 K를 선택하는 것이 가장 일반적이다. 통계적으로 최적의 클러스터 개수를 구하는 방법은 없다.

< 참고자료 >
1. Peter Brucs & Andrew Brucs(2018). 데이터 과학을 위한 통계. 한빛미디어. 이용준 옮김.

1081 [기초-종합] 주사위를 2개 던지면?

a, b = map(int, input().split())
for i in range(1,a+1):
    for j in range(1, b+1):
        print(i, j)

1082 [기초-종합] 16진수 구구단?

a = int(input(), 16)
for i in range(1,16):
    print("%X*%X=%X" %(a,i,a*i))

1083 [기초-종합] 3 6 9 게임의 왕이 되자!

a = int(input())

for i in range(1, a+1):
    if(i%3==0):
        print("X", end=" ")
    else:
        print(i, end=" ")

1084 [기초-종합] 빛 섞어 색 만들기

r, g, b = map(int, input().split())
cnt = 0

for i in range(r):
    for j in range(g):
        for k in range(b):
            print(i, j, k)
            cnt += 1

print(cnt)

1085 [기초-종합] 소리 파일 저장용량 계산하기

h, b, c, s = map(int, input().split())
size = h*(b>>2)*c*s
print("%0.1f MB" %(size/(2<<20)))

h, b, c, s = map(int, input().split())
size = h*b*c*s
print("%0.1f MB" %(size/(8*1024*1024)))

1086 [기초-종합] 그림 파일 저장용량 계산하기

w, h, b = map(int, input().split())
size = w*h*b
print("%.2f MB" %(size/(8*1024*1024)))

1087 [기초-종합] 여기까지! 이제 그만~

a = int(input())
sum = 0
i = 1
while(1):
    if sum < a:
        sum += i
        i += 1
    else:
        break

print(sum)

1088 [기초-종합] 3의 배수는 통과?

a = int(input())

for i in range(1,a+1):
    if(i%3==0):
        continue
    print(i, end=" ")

1089 [기초-종합] 수 나열하기1

a, d, n = map(int, input().split())
sum = a
for i in range(1,n):
    sum += d
print(sum)

1090 [기초-종합] 수 나열하기2

a, r, n = map(int, input().split())
sum = a
for i in range(1, n):
    sum *= r
print(sum)

1091 [기초-종합] 수 나열하기3

a, m, d, n = map(int, input().split())
result = a

for i in range(1, n):
    result = (result*m) + d
print(result)

1092 [기초-종합] 함께 문제 푸는 날

a, b, c = map(int,input().split())
day = 1

while(1):
    if(day%a==0 and day%b==0 and day%c ==0):
        break
    day += 1
print(day)

a, b, c = map(int,input().split())
day = 1

while(day%a != 0 or day%b != 0 or day%c != 0):
    day += 1
print(day)

1093 [기초-1차원배열] 이상한 출석 번호 부르기1

n = int(input())
x = list(map(int,input().split()))
a = []

for i in range(23):
    a.append(0)

for j in x:
    a[j-1] += 1

for k in a:
    print(k, end=" ")

1094 [기초-1차원배열] 이상한 출석 번호 부르기2

n = int(input())
k = list(map(int,input().split()))
x = []

for a in range(n):
    x.append(0)

for b in range(n):
    x[b] = k[n-b-1]

for c in x:
    print(c, end = " ")

n = int(input())
k = list(map(int,input().split()))

for i in range(n):
    print(k[n-i-1], end = " ")

1095 [기초-1차원배열] 이상한 출석 번호 부르기3

n = int(input())
k = list(map(int,input().split()))
min = k[0]

for i in range(n):
    if min >= k[i]:
        min = k[i]
print(min)

1096 [기초-2차원배열] 바둑판에 흰 돌 놓기

n = int(input())
board = []
for i in range(19):
    board.append([])
    for j in range(19):
        board[i].append(0)

for j in range(n):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1

for a in range(19):
    for b in range(19):
        print(board[a][b], end=" ")
    print()

1097 [기초-2차원배열] 바둑알 십자 뒤집기

board = []
for i in range(19):
    board.append([])
    x_board = list(map(int,input().split()))
    for j in x_board:
        board[i].append(j)

n = int(input())
for k in range(n):
    x, y = map(int,input().split())
    
    for x_i in range(19):
        if(board[x_i][y-1]==0): board[x_i][y-1] = 1
        else: board[x_i][y-1]=0
    
    for y_i in range(19):
        if(board[x-1][y_i]==0): board[x-1][y_i] = 1
        else: board[x-1][y_i]=0
        
for a in range(19):
    for b in range(19):
        print(board[a][b], end=" ")
    print()

1098 [기초-2차원배열] 설탕과자 뽑기

h, w = map(int, input().split())

board = []
for i in range(h):
    board.append([])
    for j in range(w):
        board[i].append(0)

n = int(input())

for k in range(n):
    l, d, x, y = map(int, input().split())
    
    if d==0: # 가로
        for i in range(y-1,l+y-1):
            board[x-1][i] = 1
    
    if d==1: # 세로
        for j in range(x-1, l+x-1):
            board[j][y-1] = 1
            
for a in range(h):
    for b in range(w):
        print(board[a][b], end=" ")
    print()

1099 [기초-2차원배열] 성실한 개미

board = []
for i in range(10):
    board.append([])
    x_board = list(map(int,input().split()))
    for j in x_board:
        board[i].append(j)

x = y = 1 # start point

while True:
    if board[x][y] == 0:
        board[x][y] = 9
    elif board[x][y] == 2:
        board[x][y] = 9
        break
    
    if (board[x][y+1] == 1 and board[x+1][y] == 1): break
    
    if board[x][y+1] == 1: x += 1
    else: y+= 1
    
for a in range(10):
    for b in range(10):
        print(board[a][b], end=" ")
    print()

3. 배깅과 랜덤 포레스트

- 다중 모델의 평균을 취하는 방식(혹은 다수결 투표), 다른 말로 앙상블 모델은 단일 모델을 사용하는 것보다 더 나은 성능을 보인다.

< 앙상블 방법의 가장 간단한 버전 >

1. 주어진 데이터에 대해 예측 모델을 만들고 예측 결과를 기록한다.
2. 같은 데이터에 대해 여러 모델을 만들고 결과를 기록한다.
3. 각 레코드에 대해 예측된 결과들의 평균(또는 가중평균, 다수결 투표)을 구한다.

-> 앙상블 기법은 상대적으로 적은 노력만으로도 좋은 예측모델을 만들 수 있다는 점에서 정말 파워풀하다.

1) 배깅

- 배깅이란 '부트스트랩 종합(bootstrap aggregation)'의 줄임말로 다양한 모델들을 정확히 같은 데이터에 대해 구하는 대신, 매번 부트스트랩 재표본에 대해 새로운 모델을 만든다.

< 배깅 알고리즘 >

- 응답변수 $Y$와 $P$개의 예측변수 $X=X_1, X_2, \cdot\cdot\cdot,X_P$로 이루어진 $N$개의 레코드가 있다고 가정하자.

1. 만들 모델의 개수 $M$과 모델을 만드는데 사용할 레코드의 개수 $n$($n<N$)의 값을 초기화한다. 반복 변수 $m$=1로 놓는다.
2. 훈련 데이터로부터 복원추출 방법으로 $n$개의 부분데이터 $Y_m$과$X_m$을 부트스트랩 재표본 추출한다.
3. 의사 결정 규칙 $\hat{f_m}(X)$를 얻기 위해, $Y_m$과 $X_m$을 이용해 모델을 학습한다.
4. $m=m+1$로 모델 개수를 늘린다.$m\leq M$이면 다시 1단계로 간다.

$\hat{f_m}$이 $Y=1$인 경우의 확률을 예측한다고 했을 때, 배깅 추정치는 다음과 같이 정의할 수 있다.

$\hat{f}=\frac{1}{M}(\hat{f_1}(X)+\hat{f_2}(X)+\cdot\cdot\cdot+\hat{f_M}(X))$

2) 랜덤 포레스트

- 랜덤 포레스트는 의사 결정 트리 모델에 한 가지 중요한 요소가 추가된 배깅 방법을 적용한 모델로써, 레코드를 표폰추출할 때, 변수 역시 샘플링 하는 것이다.

- 랜덤 포레스트에서는 알고리즘의 각 단계마다, 고를 수 있는 변수가 랜덤하게 결정된 전체 변수들의 부분집합에 한정된다.

< 랜덤 포레스트 알고리즘 >

1. 전체 데이터로부터 부트스트랩 샘플링(복원추출)을 한다.
2. 첫 분할을 위해 비복원 랜덤표본추출로 $p(p<P)$개의 변수를 샘플링한다.
3. 샘플링된 변수 $X_{j(1)}, X_{j(2)},\cdot\cdot\cdot,X_{j(p)}$에 대해 분할 알고리즘을 적용한다.
   1. $X_{j(k)}$의 각 변수 $s_{j(k)}$에 대해
      1. 파티션 $A$에 있는 레코드들을 $X_{j(k)}<s_{j(k)}$인 하위 영역과 $X_{j(k)}\geq s_{j(k)}$인 하위 영역으로 나눈다.
      2. $A$의 각 하위 영역 내부의 클래스의 동질성을 측정한다.
   2. 분할 영역 내부의 클래스 동질성을 최대로하는 $s_{j(k)}$의 값을 선택한다.
4. 분할 영역 내부의 클래스 동질성을 최대로 하는 $X_{j(k)}$와 $s_{j(k)}$ 값을 선택한다.
5. 다음 분할을 진행하기 위해, 2단계부터 시작해 이전 단계들을 반복한다.
6. 트리가 모두 자랄 때까지 위와 같은 분할 과정을 반복한다.
7. 1단계로 돌아가 또 다른 부트스트랩 표본을 추출해 같은 과정을 반복한다.

- 보통은 각 단계마다 전체 변수의 개수가 $P$개 일 때, $\sqrt{P}$개의 변수를 샘플링한다.

- R에서는 랜덤 포레스트를 구현해놓은 randomForest 패키지가 있다.

* 주머니 외부(OOD; out-of-bag) 추정 에러는 트리 모델을 만들 때 사용했던 학습 데이터에 속하지 않는 데이터를 사용해 구한 학습된 모델의 오차율을 말한다.

- 랜덤 포레스트는 일종의 '블랙박스' 모델이다. 단순한 단일 트리보다 훨씬 정확한 예측 성능을 보이지만 간단한 트리를 통해 얻을 수 있는 직관적인 해석은 불가능하다.

3) 변수 중요도

- 랜덤 포레스트는 피처와 레코드의 개수가 많은 데이터에 대해 예측 모델을 만들 때 장점을 발휘한다.

< 변수 중요도를 측정하는 방법 >

• 변수의 값을 랜덤하게 섞었다면, 모델의 정확도가 감소하는 정도를 측정한다(type=1). 변수를 랜덤하게 섞는다는 것은 해당 변수가 예측에 미치는 모든 영향력을 제거하는 것을 의미한다. 정확도는 OOB 데이터로부터 얻는다(결국 교차타당성검사와 같은 효과를 갖는다).
• 특정 변수를 기준으로 분할이 일어난 모든 노드에서 불순도 점수의 평균 감소량을 측정한다(type=2). 이 지표는 해당 변수가 노드의 순도를 개선하는 데 얼마나 기여했는지를 나타낸다. 물론 이 지표는 학습 데이터를 기반으로 측정되기 때문에, OOB 데이터를 가지고 계산한 것에 비해 믿을 만하지 않다.

4) 하이퍼파라미터

- 다른 여러 머신러닝 알고리즘과 마찬가지로 랜덤 포레스트는 성능을 조절할 수 있는 손잡이가 달린 일종의 블랙박스 알고리즘이라고 할 수 있다. 이러한 손잡이를 하이퍼파라미터(hyperparameter)라고 부른다.

- 랜덤 포레스트에서 하이퍼파라미터는 좀 더 결정적인 영향을 미치는 중요한 요소이다. 특히 오버피팅을 피하기 위해 매우 중요하다.

< 랜덤 포레스트의 하이퍼파라미터 >

• nodesize : 말단 노드의 크기를 의미한다. 분류 문제를 위한 기본 설정은 1이며, 회귀문제에서는 5이다.
• maxnodes : 각 결정 트리에서 전체 노드의 최대 개수를 의미한다. 기본적으로는 제한이 없고 다만 nodesize 제한 설정에 따라 가장 큰 트리의 크기가 결정된다.

-> nodesize와 maxnodes를 크게 하면 더 작은 트리를 얻게 되고 거짓 예측 규칙들을 만드는 것을 피할 수 있게 된다.

· 앙상블 모델은 많은 모델로부터 얻은 결과를 서로 결합해 모델 정확도를 높인다.
· 배깅은 앙상블 모델 가운데 하나의 형태로, 부트스트랩 샘플을 이용해 많은 모델들을 생성하고 이 모델들을 평균화한다.
· 랜덤 포레스트는 배깅 기법을 의사 결정 트리 알고리즘에 적용한 특별한 형태이다. 랜덤 포레스트에서는 데이터를 재표본추출하는 동시에 트리를 분할할 때 예측변수 또한 샘플링한다.
· 랜덤 포레스트로부터 나오는 출력 중 유용한 것은 예측변수들이 모델 정확도에 미치는 영향력을 의미하는 변수 중요도이다.
· 랜덤 포레스트에서는 오버피팅을 피하기 위해 교차타당성검사를 통해 조정된 하이퍼파라미터를 사용한다.

4. 부스팅

- 배깅은 상대적으로 튜닝이 거의 필요 없지만 부스팅은 적용하고자 하는 문제에 따라 주의가 필요하다.

- 선형회귀 모델에서는 피팅이 더 개선될 수 있는지 알아보기 위해 잔차를 종종 사용했다. 부스팅은 이러한 개념을 더 발전시켜, 이전 모델이 갖는 오차를 줄이는 방향으로 다음 모델을 연속적으로 생성한다.

- 에이다부스트, 그레이디언트 부스팅, 확률적 그레이디언트 부스팅은 가장 자주 사용되는 변형된 형태의 부스팅 알고리즘이다.

1) 부스팅 알고리즘

- 다양한 부스팅 알고리즘의 바탕에 깔려 있는 기본 아이디어는 모두 같다.

< 에이다부스트 알고리즘 >

1. 먼저 피팅할 모델의 개수 $M$을 설정한다. 그리고 반복 횟수를 의미하는 $m=1$로 초기화한다. $w_i=\frac{1}{N}$으로 초기화한다($i=1,2,\cdot\cdot\cdot,N$). 앙상블 모델을 $\hat{F_0}=0$으로 초기화한다.
2. 관측 가중치 $w_1,w_2,\cdot\cdot\cdot,w_N$을 이용해 모델 \hat{f_m}을 학습한다. 이때 잘못 분류된 관측치에 대해 가중치를 적용한 합을 의미하는 가중 오차 $e_m$이 최소화되도록 학습한다.
3. 앙상블 모델에 다음 모델을 추가한다. $\hat{F_m}=\hat{F_{m-1}}+\alpha_{m}\hat{f_m}$ 여기서 $\alpha_m=\frac{log{1}-e_m}{e_m}$이다.
4. 잘못 분류된 입력 데이터에 대한 가중치를 증가하는 방향으로 가중치 $w_1, W-2, \cdot\cdot\cdot,w_N$을 업데이트한다. $\alpha_m$에 따라 증가 폭이 결정되며, $\alpha_m$이 클수록 가중치가 더 커진다.
5. 모델 반복 횟수를 $m=m+1$으로 증가시키고 $m \leq M$이면 다시 1단계로 돌아간다.

이 과정을 통해 얻은 부스팅 추정치는 다음과 같다.

$\hat{F}=\alpha_1\hat{f_1}+\alpha\hat{f_2}+\cdot\cdot\cdot+\alpha_M\hat{f_M}$

- $\alpha_m$ 값을 이용해 모델의 오차가 낮을수록 더 큰 가중치를 부여한다.

< 그레이디언트 부스팅 >

- 에이다부스팅과 거의 비슷하지만, 비용함수를 최적화하는 접근법을 사용했다는 점에서 차이가 있다.

- 가중치를 조정하는 대신에 모델이 유사잔차(pesudo-residual)를 학습하도록 한다. 이는 잔차가 큰 데이터를 더 집중적으로 학습하는 효과를 가져온다.

< 확률적 그레이디언트 부스팅 >

- 렌덤 포레스트에서와 유사하게, 매 단계마다 데이터와 예측변수를 샘플링하는 식으로 그레이디언트 부스팅에 랜덤한 효과를 추가한다.

2) XG부스트

- 부스팅 방법 가운데 대중적으로 가장 많이 사용되는 오픈소스 소프트웨이이다.

- R에서도 xgboost 패키지를 이용해 XG부스트를 사용할 수 있다.

< XG 부스트 중요 파라미터 >

• subsample : 각 반복 구간마다 샘플링할 입력 데이터의 비율을 조정한다.
• eta : 부스팅 알고리즘에서 $\alpha_m$에 적용되는 축소 비율을 결정한다.

3) 정규화: 오버피팅 구하기

- xgboost 함수를 무작정 사용할 경우, 학습 데이터에 오버피팅되는 불안정한 모델을 얻을 수 있다.

< 오버피팅의 문제점 >

• 학습 데이터에 없는 새로운 데이터에 대한 모델의 정확도가 떨어진다.
• 모델의 예측 결과에 변동이 매우 심하고 불안정한 결과를 보인다.

- 모델의 복잡도에 따라 벌점을 추가하는 형태로 비용함수를 변경하는 방법인 정규화(regularization) 방법을 통해 오버피팅을 방지할 수 있다.

-xgboost의 alpha와 lambda는 각각 맨하탄 거리와 유클리드 거리를 의미한다. 이 파라미터들을 크게 하면, 모델이 복잡해질수록 더 많은 벌점을 부여하게 되고 결과적으로 얻어지는 트리의 크기가 작아지게 된다.

< 능형회귀와 라소 회귀 >

- 능형회귀(ridge regression)은 잔차제곱합에 회귀계수의 개수와 크기에 따라 벌점을 추가한 값을 최소화한다. $\lambda$는 계수에 대해 어느 정도 벌점을 부여할 것인가를 결정한다. 이 값이 클수록 모델이 데이터에 오버피팅할 가능성이 낮아진다.

$\sum_{i=1}^n(Y_i-\hat{b_0}-\hat{b_1}X_i-\cdot\cdot\cdot-\hat{bX_p})^2+\lambda(\hat{b_1}^2+\cdot\cdot\cdot+\hat{b_p}^2)$

- 라소(Lasso) 회귀는 벌점 항에 유클리드 거리 대신 맨하탄 거리를 이용한다.

$\sum_{i=1}^n(Y_i-\hat{b_0}-\hat{b_1}X_i-\cdot\cdot\cdot-\hat{bX_p})^2+\alpha(\mid{\hat{b_1}}\mid+\cdot\cdot\cdot+\mid\hat{b_p}\mid)$

- xgboost 함수의 파라미터 lambda와 alpha가 이 같은 방식으로 작동한다.

4) 하이퍼파라미터와 교차타당성검사

- 동시에 설정하는 파라미터 수가 많아진다면 어떤 기준을 가지고 이 파라미터들을 골라야 할까?

-> 교차타당성검사를 활용한다.

< 교차타당성검사 >

1. 데이터를 $K$개의 서로 다른 그룹(폴드)으로 랜덤하게 나눈다.
2. 각 폴드마다 해당 폴드에 속한 데이터를 제외한 나머지 데이터를 가지고 모델을 학습한 후, 폴드에 속한 데이터를 이용해 모델을 평가한다.-> 표본 밖 데이터에 대한 모델의 성능을 보여준다.
3. 설정한 하이퍼파라미터 조합마다 폴드에 대한 오차의 평균을 계산해서 전체적으로 가장 낮은 평균 오차를 갖는 최적의 하이퍼파라미터 조합을 찾는다.

< XG부스트의 하이퍼 파라미터 >

• eta : 부스팅 알고리즘에서 $\alpha$에 적용되는 0과 1 사이의 축소인자(shrinkage factor). 기본값은 0.3이지만, 노이즈가 있는 데이터에 대해서는 더 작은 값을 추천한다.
• nrounds : 부스팅 라운드 횟수. eta가 작은 값이라면 알고리즘의 학습 속도가 늦춰지기 때문에 라운드 횟수를 늘려야 한다. 오버피팅을 방지하는 파라미터 설정이 포함된 경우, 라운드 횟수를 좀 더 늘려도 괜찮다.
• max_depth : 트리의 최대 깊이(기본값은 6). 깊이가 아주 깊은 트리를 만드는 랜덤 포레스트와는 반대로 부스팅 트리는 깊이가 얕다. 이는 노이즈가 많은 데이터에 대해 모델이 복잡한 거짓 상호작용을 회피하는 데 도움이 된다.
• subsample 및 colsample_bytree : 전체 데이터에서 일부 데이터를 비복원 샘플링하는 비율 및 예측변수 중 일부 변수를 샘플링하는 비율. 이는 랜덤 포레스트에서 오버피팅을 피하기 위해 사용했던 것들과 유사하다.
• lambda 및 alpha : 오버피팅을 조절하기 위해 사용되는 정규화(regularization) 파라미터들.

· 부스팅 방법은 일련의 모델들을 피팅할 때 이전 라운드에서 오차가 컸던 레코드들에 가중치를 더하는 방식을 사용하는 앙상블 모델의 한 부류이다.
· 확률적 그레이디언트 부스팅은 부스팅 가운데에서 가장 일반적으로 사용되며 가장 좋은 성능을 보인다. 확률적 그레이디언트 부스팅의 가장 일반적인 형태는 트리 모델을 사용한다.
· XG부스트는 확률적 그레이디언트 부스팅을 사용하기 위한 가장 유명한 소프트웨어 패키지이다. 데이터 과학에서 활용되는 거의 대부분의 언어를 지원한다.
· 부스팅은 데이터에 오버피팅되기 쉽다. 이를 피하기 위해 하이퍼파라미터를 잘 설정해야 한다.
· 정규화는 파라미터 개수에 관한 벌점 항목을 모델링에 포함하여 오버피팅을 피하는 방법이다.
· 부스팅에서 여러개의 하이퍼파라미터들의 조합을 찾아야 할 때, 교차타당성검사는 아주 중요하다.

< 참고자료 >
1. Peter Brucs & Andrew Brucs(2018). 데이터 과학을 위한 통계. 한빛미디어. 이용준 옮김.

1061 [기초-비트단위논리연산] 비트단위로 OR 하여 출력하기

a, b = map(int, input().split())
print(a|b)

1062 [기초-비트단위논리연산] 비트단위로 XOR 하여 출력하기

a, b = map(int, input().split())
print(a^b)

1063 [기초-삼항연산]두 정수 입력받아 큰 수 출력하기

a, b = map(int, input().split())
print("%d"%(a if a>b else b))

1064 [기초-삼항연산] 정수 3개 입력받아 가장 작은 수 출력하기

a, b, c = map(int, input().split())
print("%d" % (a if a<(b if b<c else c) else (b if b<c else c)))

1065 [기초-조건/선택실행구조] 정수 3개 입력받아 짝수만 출력하기

a, b, c = map(int, input().split())
if(a%2==0): print(a)
if(b%2==0): print(b)
if(c%2==0): print(c)

1066 [기초-조건/선택실행구조] 정수 3개 입력받아 짝/홀 출력하기

a, b, c = map(int, input().split())
print("%s" % ("even" if a%2==0 else "odd"))
print("%s" % ("even" if b%2==0 else "odd"))
print("%s" % ("even" if c%2==0 else "odd"))

1067 [기초-조건/선택실행구조] 정수 1개 입력받아 분석하기

a = int(input())
if(a<0):    
    if(a%2==0):
        print("minus")
        print("even")
    else:
        print("minus")
        print("odd")

else:
    if(a%2==0):
        print("plus")
        print("even")
    else:
        print("plus")
        print("odd")

a = int(input())
print("%s" %("minus" if a<0 else "plus"))
print("%s" %("even" if a%2==0 else "odd"))

1068 [기초-조건/선택실행구조] 정수 1개 입력받아 평가 출력하기

a = int(input())

if(a>=90): print("A")
elif(a>=70): print("B")
elif(a>=40): print("C")
else: print("D")

1069 [기초-조건/선택실행구조] 평가 입력받아 다르게 출력하기

a = ord(input())

if(a==65):print("best!!!")
elif(a==66):print("good!!")
elif(a==67):print("run!")
elif(a==68):print("slowly~")
else:print("what?")

1070 [기초-조건/선택실행구조] 월 입력받아 계절 출력하기

a = int(input())

if(a>=3 and a<=5): print("spring")
elif(a>=6 and a<=8): print("summer")
elif(a>=9 and a<=11): print("fall")
else: print("winter")

1071 [기초-반복실행구조] 0 입력될 때까지 무한으로 출력하기1

a = list(map(int,input().split()))
    
for i in a:
    if(i==0): break
    else: print(i)

1072 [기초-반복실행구조] 정수 입력받아 계속 출력하기

a = int(input())
b = list(map(int,input().split()))

for i in b:
    print(i)

1073 [기초-반복실행구조] 0 입력될 때까지 무한으로 출력하기2

a = list(map(int,input().split()))
    
for i in a:
    if(i==0): break
    else: print(i)

1074 [기초-반복실행구조] 정수 1개 입력받아 카운트다운 출력하기1

a = int(input())

while(a!=0):
    print(a)
    a -= 1

1075 [기초-반복실행구조] 정수 1개 입력받아 카운트다운 출력하기2

a = int(input())

while(a!=0):
    print(a-1)
    a -= 1

1076 [기초-반복실행구조] 문자 1개 입력받아 알파벳 출력하기

a = ord(input())
i = ord('a')
while(1):
    if(i<=a):
        print("%c" %i)
        i += 1
    else: break

1077 [기초-반복실행구조] 정수 1개 입력받아 그 수까지 출력하기

a = int(input())

for i in range(a+1):
    print(i)

1078 [기초-종합] 짝수 합 구하기

a = int(input())
sum = 0

for i in range(1, a+1):
    if(i%2==0):
        sum += i
print(sum)

1079 [기초-종합] 원하는 문자가 입력될 때까지 반복 출력하기

a = list(input().split())
    
for i in a:
    print("%c" %i)
    if(i=='q'): break

1080 [기초-종합] 언제까지 더해야 할까?

a = int(input())
sum = 0
for i in range(1,a):
    if(sum<a): sum += i
    else: break
print(i-1)

Chapter 6. 통계적 머신러닝

1. K 최근접 이웃

- K 최근접 이웃(KNN; k-nearest neighbor) 알고리즘의 아이디어

• 특징들이 가장 유사한(즉, 예측변수들이 유사한) K개의 레코드를 찾는다.
• 분류 : 이 유사한 레코드들 중에 다수가 속한 클래스가 무엇인지 찾은 후에 새로운 레코드를 그 클래스에 할당한다.
• 예측(KNN 회귀라고도 함) : 유사한 레코드들의 평균을 찾아서 새로운 레코드에 대한 예측값으로 사용한다.

- KNN은 가장 간단한 예측/분류 방법 중 하나이다. 회귀와는 달리 모델을 피팅하는 과정이 필요 없다.

- KNN이 완전히 자동화된 방법은 아니다. 특징들이 어떤 척도에 존재하는지, 가까운 정도를 어떻게 측정할 것인지, K를 어떻게 설정할 것인지에 따라 예측 결과가 달라진다.

- 모든 예측변수들은 수치형이어야 한다.

1) 거리지표

- 유사성(similarity) 혹은 근접성(nearness)은 거리 지표를 통해 결정된다. 이 지표는 $(x_1, x_2, \cdot\cdot\cdot,x_p)$와 $(u_1, u_2, \cdot\cdot\cdot, u_p)$가 얼마나 멀리 떨어져 있는지 측정하는 함수라고 할 수 있다.

※ 유클리드 거리(Euclidean distance)

- 유클리드 거리는 특별히 계산상의 이점이 있다. KNN은 $K$ x $n$(데이터 개수) 번만큼 쌍대가 필요하기 때문에 데이터 개수가 커질수록 계산량이 더 중요해진다.

$\sqrt{(x_1-u_1)^2+(x_2-u_1)^2+\cdot\cdot\cdot+(x_p-u_p)^2}$

※ 맨하탄 거리(Manhattan distance)

- 맨하탄 거리는 한 번에 대각선이 아닌 한 축방향으로만 움직일 수 있다고 할 때, 두 점 사이의 거리라고 할 수 있다.

- 점과 점 사이의 이동 시간으로 근접성을 따질 때 좋은 지표가 된다.

$\mid{x_1-u_1}\mid+\mid{x_2-u_2}\mid+\cdot\cdot\cdot+\mid{x_p-u_p}\mid$

2) 원-핫 인코더

- 대부분의 통계 모델이나 머신러닝 모델에서 몇 가지 요인(문자열) 변수를 포함하고 있는 형태의 변수는, 같은 정보를 담고 있는 이진 가변수의 집합으로 변환해야 한다.

- 선형회귀나 로지스틱 회귀에서 원-핫 인코딩은 다중공선성과 관련된 문제를 일으킨다. 이런 경우 한 가변수를 생략하는 방법이 있다. 하지만, KNN이나 다른 방법에서는 이것이 문제가 되지 않는다.

3) 표준화(정규화, z점수)

- 표준화 혹은 정규화란, 모든 편수에서 평균을 빼고 표준편차로 나누는 과정을 통해 변수들을 모두 비슷한 스케일에 놓는다.

$z = \frac{x-\bar{x}}{s}$

- 이 값을 일반적으로 z 점수라고 부른다. 이는 평균으로부터 표준편차만큼 얼마나 떨어져 있는지를 의미한다. 이를 통해 변수의 스케일로 인한 영향을 줄일 수 있다.

- KNN이나 다른 알고리즘(예로 주성분분석과 클러스터링)에서는 데이터를 미리 표준화하는 것이 필수이다.

4) K 선택하기

- K를 잘 선택하는 것은 KNN의 성능을 결정하는 아주 중요한 요소이다.

- K가 너무 작으면 데이터의 노이즈 성분까지 고려하는 오버피팅 문제가 발생한다.

- K 값이 클수록 결정 함수를 좀 더 부드럽게 하는 효과를 가져와 학습 데이터에서의 오버피팅 위험을 낮출 수 있다.

- 반대로 K를 너무 크게 하면 결정 함수가 너무 과하게 평탄화되어(오버스무딩) 데이터의 지역 정보를 예측하는 KNN의 기능을 잃어버리게 된다.

- 특히 홀드아웃 데이터 또는 타당성검사를 위해 따로 떼어놓은 데이터에서의 정확도를 가지고 K 값을 결정하는 데 사용한다.

5) KNN을 통한 피처 엔지니어링

- KNN은 구현이 간단하고 직관적이다 보니 널리 활용된다.

- 성능 면에서는, 다른 복잡한 분류 방법들에 비해 그렇게 경쟁력이 있다고 보기 어렵다.

- 실용적인 측면에서, 다른 분류 방법들의 특정 단계에 사용할 수 있게 모델에 '지역적 정보(local knowledge)'를 추가하기 위해 KNN을 사용할 수 있다.

• KNN은 데이터에 기반하여 분류 결과(클래스에 속할 확률)를 얻는다.
• 이 결과는 해당 레코드에 새로운 특징(피처)으로 추가된다. 이 결과를 다른 분류 방법에 사용한다. 원래의 예측변수들을 두 번씩 사용하는 셈이 된다.

- 예측 능력을 높이기 위해 피처(예측 변수)들을 새롭게 만들어내기 위한, '피처 엔지니어링' 개념으로 볼 수 있다.

- K 최근접 이웃(KNN) 방법이란 유사한 레코드들이 속한 클래스로 레코드를 분류하는 방법이다.
- 유사성(거리)은 유클리드 거리나 다른 관련 지표들을 이용해 결정한다.
- 가장 가까운 이웃 데이터의 개수를 의미하는 K는 학습 데이터에서 얼마나 좋은 성능을 보이는지를 가지고 결정한다.
- 일반적으로 예측변수들을 표준화한다. 이를 통해 스케일이 큰 변수들의 영향력이 너무 커지지 않도록 한다.
- 예측 모델링의 첫 단계에서 종종 KNN을 사용한다. 이렇게 얻은 값을 다시 데이터에 하나의 예측변수로 추가해서 두 번째 단계의 (KNN이 아닌) 모델링을 위해 사용한다.

2. 트리 모델

- 트리 모델은 회귀 및 분석 트리(CART; classification and regression tree), 의사 결정 트리(decision tree), 혹은 단순히 그냥 트리(tree)라고도 불린다.

- 트리 모델들과 여기서 파생된 강력한 랜덤 포레스트(random forest)와 부스팅 같은 방법들은 회귀나 분류 문제를 위해 데이터 과학에서 가장 널리 사용되는 강력한 예측 모델링 기법들의 기초라고 할 수 있다.

- 트리 모델이란 if-then-else 규칙의 집합체라고 할 수 있다. 따라서 이해하기도 쉽고 구현하기도 쉽다.

- 회귀나 로지스틱 회귀와 반대로 트리는 데이터에 존재하는 복잡한 상호관계에 따른 숨겨진 패턴들을 발견하는 능력이 있다.

- KNN이나 나이브 베이즈 모델과 달리, 예측변수들 사이의 관계로 단순 트리 모델을 표시할 수 있고 쉽게 해석이 가능하다.

- 트리 모델을 얻기 위해 사용되는 R 패키지로는 rpart와 tree가 있다.

1) 재귀 분할 알고리즘

- 재귀 분할은 간단하면서도 직관적인 방법이다. 예측변수 값을 기준으로 데이터를 반복적으로 분할해나간다. 분할할 때에는 상대적으로 같은 클래스의 데이터들끼리 구분되도록 한다.

- 응답변수 $Y$와 $P$개의 예측변수 집합 $X_j(j=1,\cdot\cdot\cdot,P)$가 있다고 가정하자.

1. 각 예측변수 $X_j$에 대해.
   1. $X_j$에 해당하는 각 변수 $s_j$에 대해
      1. $A$에 해당하는 모든 레코드 $X_j < s_j$인 부분과 나머지 $X_j \geq s_j$인 부분으로 나눈다.
      2. $A$의 각 하위 분할 영역 안에 해당 클래스의 동질성을 측정한다.
   2. 하위 분할 영역 내에서의 클래스 동질성이 가장 큰 $s_j$ 값을 선택한다.
2. 클래스 동질성이 가장 큰 변수 $X_j$와 $s_j$ 값을 선택한다

- 알고리즘의 재귀부분

1. 전체 데이터를 가지고 $A$를 초기화한다.
2. $A$를 두 부분 $A_1$과 $A_2$로 나누기 위해 분할 알고리즘을 적용한다.
3. $A_1$과 $A_2$ 각각에서 2번 과정을 반복한다.
4. 분할을 해도 더 이상 하위 분할 영역의 동질성이 개선되지 않을 정도로 충분히 분할을 진행했을 때, 알고리즘을 종료한다.

- 각 영역은 해당 영역에 속한 응답변수들의 다수결 결과에 따라 0 또는 1로 예측결과를 결정한다.

2) 동질성과 불순도 측정하기

- 각 분할 영역에 대한 동질성, 즉 클래스 순도(class purity)를 측정하는 방법이 필요하다.

- 해당 파티션 내에서 오분류된 레코드의 비율 $p$로 예측의 정확도를 표시할 수 있으며 이는 0(완전)에서 0.5(순수 랜덤 추측) 사이의 값을 갖는다.

- 지니 불순도(Gini impurity)와 엔트로피(entropy)가 대표적인 불순도 측정 지표이다.

- 분할 영역 $A$의 지니 불순도와 엔트로피는 아래와 같다.

- 지니 불순도 : $I(A) = p(1-p)$

- 앤트로피 :  $I(A) = -p log_{2}(p)-(1-p)log_{2}(1-p)$

* 지니 불순도를 지니 계수(Gini coefficient)와 혼동하지 않도록 한다. 둘 다 모두 개념적으로 비슷하지만 지니 계수는 이진 분류 문제로 한정되며, AUC 지표와 관련이 있는 용어다.

3) 트리 형성 중지하기

- 가지치기를 하는 가장 일반적인 방법은 홀드아웃 데이터에서의 에러가 최소가 되는 지점까지 가지치기를 진행하는 것이다.

- 좋은 일반화 성능을 얻기 위해 언제 트리 성장을 멈춰야 하는지 결정하는 방법이 필요하다. 가지 분할을 멈추는 대표적인 두 가지 방법이 있다.

• 분할을 통해 얻어지는 하위 영역 또는 말단 잎의 크기가 너무 작다면 분할하는 것을 멈춘다. rpart 함수에서 minsplit이나 minbucket 같은 파라미터를 이용해 최소 분할 영역 크기나 말단 잎의 크기를 조절할 수 있다. 기본값은 각각 20과 70이다.
• 새로운 분할 영역이 '유의미'한 정도로 불순도를 줄이지 않는다면 굳이 분할하지 않는다. rprat 함수에서 트리의 복잡도를 의미하는 복잡도 파라미터(complecity parameter)인 cp를 이용해 이를 조절한다. 트리가 복잡해질 수록 cp의 값이 증가한다. 실무에서는 트리의 복잡도가 추가적으로 늘어나는 만큼 cp를 벌점으로 간주해 트리성장을 제한하는 데 사용된다.

- 첫 번째 방법은 탐색 작업에 유용할 수 있지만 최적값(새로운 데이터에 대한 예측 정확도를 최대화하기 위한 값)을 결정하기가 매우 어렵다. 복잡도 파라미터 cp를 이용하면 어떤 크기의 트리가 새로운 데이터에 대해 가장 좋은 성능을 보일지 추정할 수 있다.

• cp가 매우 작다면 트리는 실제 의미 있는 신호뿐 아니라 노이즈까지 학습하여 오버피팅되는 문제가 발생한다.
• cp가 너무 크다면 트리가 너무 작아 예측 능력을 거의 갖지 못한다.

- 최적의 cp를 결정하는 것은 편향-분산 트레이드오프를 보여주는 하나의 대표적인 예이다.

- cp를 추정하는 가장 일반적인 방법은 교차타당성 검정을 이용하는 것이다.

1. 데이터를 학습용 데이터와 타당성검사용 (홀드아웃) 데이터로 나눈다.
2. 학습 데이터를 이용해 트리를 키운다.
3. 트리를 단계적으로 계속해서 가지치기한다. 매 단계마다 학습 데이터를 이용해 cp를 기록한다.
4. 타당성검사 데이터에 대해 최소 에러(손실)를 보이는 cp를 기록한다.
5. 데이터를 다시 학습용 데이터와 타당성검사용 데이터로 나누고, 마찬가지로 트리를 만들고 가지치기하고 cp를 기록하는 과정을 반복한다.
6. 이를 여러 번 반복한 후 각 트리에서 최소 에러를 보이는 cp 값의 평균을 구한다.
7. 원래 데이터를 이용해 위에서 구한 cp의 최적값을 가지고 트리를 만든다.

4) 트리 활용하기

* 트리 모델의 장점

• 트리 모델은 데이터 탐색을 위한 시각화가 가능하다. 이는 어떤 변수가 중요하고 변수 간에 어떤 관계가 있는지를 보여준다. 트리 모델은 예측변수들 간의 비선형 관계를 담아낼 수 있다.
• 트리 모델은 일종의 규칙들의 집합이라고 볼 수 있다. 따라서 실제 구현 방법에 대해서, 아니면 데이터 마이닝 프로젝트 홍보에 대해서 비전문가들과 대화하는 데 아주 효과적이라고 할 수 있다.

- 예측에 관해서는, 다중 트리에서 나온 결과를 이용하는 것이 단일 트리를 이용하는 것보다 보통은 훨씬 강력하다.

- 특히, 랜덤 포레스트와 부스팅 트리 알고리즘은 거의 항상 우수한 예측 정확도나 성능을 보여준다.

- 의사 결정 트리는 결과를 분류하거나 예측하기 위한 일련의 규칙들을 생성한다.
- 이 규칙들은 데이터를 하위 영역으로 연속적으로 분할하는 것과 관련이 있다.
- 각 분할 혹은 분기는 어떤 한 예측변수 값을 기준으로 데이터를 위아래 두 부분으로 나누는 것이다.
- 각 단계마다, 트리 알고리즘은 결과의 불순도를 최소화하는 쪽으로 영역 분할을 진행한다.
- 더 이상 분할이 불가능할 때, 트리가 완전히 자랐다고 볼 수 있으며 각 말단 노드 혹은 잎 노드에 해당하는 레코드들은 단일 클래스에 속한다. 새로운 데이터는 이 규칙 경로를 따라 해당 클래스로 할당된다.
- 완전히 자란 트리는 데이터를 오버피팅하기 때문에, 노이즈를 제외한 신호에만 반응하도록 트리에 가지치기를 수행해야 한다.
- 랜덤 포레스트나 부스팅 트리 같은 다중 트리 알고리즘은 우수한 예측 성능을 보장한다. 하지만 규칙에 기반을 둔 단일 트리의 방법의 장점이라고 할 수 있는 전달 능력은 잃어버린다.

< 참고자료 >
1. Peter Brucs & Andrew Brucs(2018). 데이터 과학을 위한 통계. 한빛미디어. 이용준 옮김.