AI

※ 본 내용은 Coursera, Machine Learning - Andrew Ng 강의, 강의자료를 바탕으로 작성하였습니다.

<Recommender System>

Recommender System은 사용자의 기존 선호도를 바탕으로 다른 상품(ex) 영화, 물건 등)에 대한 선호도를 예측하는 모델을 만들고, 추천해주는 시스템이다.

수업에서 다루는 이유는 다음과 같다.

- 학문의 영역에서는 몰라도, 현업에서 가장 자주 사용되는 머신러닝 시스템이다.

- 자동으로 좋은 feature를 선택하는 알고리즘을 다뤄볼 수 잇다.(Collaborative Filtering)

- 개념

행은 영화, 열은 사용자이고 i행 j열은 i행 영화에대해 유저-j 가 평가한 점수를 나타낸다. 

추천 시스템을 구축하기 위해 유저의 선호도를 학습하는 것은, 

기본적으로 각각의 user에 대해 linear regression의 파라미터를 찾는 과정과 동일하다고 볼 수 있다.

표의 우측에 검은 색으로 나타낸 feature  x1과 x2는 각각 그 영화의 장르를 수치화한 것이다.

*이렇게 feature가 주어진 상태로 학습하는 것을 content-based recommendation system이라고 한다.

해당 feature와 각각의 user들의 영화에 대한 평가들을 바탕으로 각 user별 파라미터를 찾을 수 있다.

예를 들어, 로맨스 장르의 비율이 높은 영화들을 선호하는 Alice(j = 1)의 경우, 파라미터는 다음과 같이 학습될 것이다.

$ \theta^{(1)} = \begin{bmatrix}0
\\ 5
\\ 0

\end{bmatrix}$

따라서 ?로 표시된 1행 3열의 영화의 경우, 4.95의 값을 예상할 수 있다.

*$ \theta^{(j)}$ 는 user-j에 대한 파라미터를 의미한다.

- Optimization Algorithm

파라미터의 최적화 역시 linear regression과 큰 차이가 없다.

우선 user-j에 대한 optimization objective는 다음과 같다.

linear regression 에서의 least squre function과 매우 유사하다.

m으로 나누는 것이 빠진 것을 제외하면 사실 동일하다.(상수를 없앤 것이므로 최적화에 영향을 주지 않는다)

(*$ i:r(i,j)=1$은 user의 평가가 있는 element에 대해서 합한다는 것을 의미한다. '?'로 표시된 데이터 제외.)

이를 모든 user에 대해 적용한 최종 optimization objective는 다음과 같다.

j=1~$ n_u$를 추가한 것, 즉 모든 user에 대해 연산하는 것만 추가되었다.

gradient descent를 적용하기 위한 편미분 값 또한 확인할 수 있다.(마찬가지로 linear regression과 거의 동일)

- Collaborative Filtering

앞서 content based recommendation system을 살펴보았는데, 

실제로는 각 영화(또는 상품 등)에 대해 그렇게 feature를 만드는 것이 쉽지 않을 수 있다. 

이번에는 반대로 $ \theta$가 먼저 주어진 상황을 가정해보자.

영화-i에 대한 user-j의 평가는 $ {\theta^{(j)}}^Tx(i)$ 로 계산할 수 있었는데, 

이번엔 반대로 $\theta$가 주어졌으므로 실제 $ y_{ij}$와 $ {\theta^{(j)}}^Tx(i)$의 차를 줄이도록 $ x^{(i)}$를 학습할 수 있을 것이다.

즉, 위와 같이 optimization algorithm을 정의하면 각 영화들에 대한 feature, $ x^{(i)}$를 학습할 수 있을 것이다.

이러한 경우, 각 feature는 어떠한 의미를 갖기보단 알고리즘이 자동으로 학습(선택)한 feature가 될 것이다.

이렇듯 feature가 주어지면 parameter를 학습할 수 있고, parameter가 주어졌을 때 feature를 학습할 수 있다는 점을 이용하여 두 과정을 교차적으로 반복 수행하면 둘 모두를 학습시킬 수 있는 것이 Collaborative Filtering의 아이디이이다.

실제로는 두 과정을 교차적으로 반복 수행하진 않고, 하나의 optimization objective를 정의한다.

기존의 두 cost function 중 ①과 ②는 사실 같은 식이다. j와 i는 column을 기준으로 전체를 탐색할지, row를 기준으로 탐색할지에 대한 표시의 차이이다.

따라서 두 파라미터($ \theta$와 $ x$)를 모두 최적화하기 위한 cost function은 ③과 같이 정의할 수 있다. 

※ $ x_0$ 를 추가하지 않는 것을 확인할 수 있다. 이는 intercept와 같은 역할을 하는 feature가 필요하다면 알고리즘 상 알아서 선택하면 되기 때문이다.(알고리즘이 자동으로 feature를 선택하는 특징 때문.)

최종적으로 알고리즘에 대해 정리하면 위와 같다. 

과정 1에서 initialize할 때, 0으로 초기화하지 않는데 이는 NN에서와 유사한 이유이다.(symmetric breaking)

(0으로 초기화한다면 gradient를 업데이트할 때 변하지 않는다는 것을 식에서 확인 가능)

※ feature를 알아서 선택한다면, feature의 수를 어떻게 설정해야 되는지에 대한 질문이 생겼는데, 이에 대한 질문과 답변이 해당 강좌의 토론 포럼에 존재하였다.

결론적으로 feature의 수를 tuning해야는데, 이때 bias와 variance 문제를 고려하여 조정하면 된다.

(ex) learning curve 출력해보기)

- vectorization

$ X$와 $ \Theta$를 위와 같이 정의하면 $ X\Theta^T$의 연산을 통해 Y를 계산할 수 있다.

- 관련 영화 추천

그렇다면 movie - i와 유사한 영화를 어떻게 추천해야 할까?

해당 영화와 feature가 가장 유사한 영화

즉,

\left \| x^{(i)} -  x^{j}\right  \|

위 식, 거리가 가장 작은 영화부터 추천하면 된다.

- Mean Normalization

score등은 이미 scare이 유사하게 되어있기 때문에 scaling은 필요없지만,

mean normalization은 유용할 수 있다.

위 데이터의 eve와 같이 어느 영화도 평가한 적이 없는 user가 있다면 cost function을 최적화함에 따라

해당 유저의 $ \theta$는 모두 0으로 초기화 될 것이고, 모든 예상 점수는 0점이 될 것이다.

(*가장 앞과 두번째 sum 계산엔 포함되지 않고, 마지막 sum에만 파라미터의 제곱이 들어가므로 0으로 하는 것이 최적화)

그러나 초기 예측값으로 무조건 0이 되는 것보다는 평균 값이 되는 것이 더 합리적이다.

따라서 위와 같이 Mean Normalization을 적용한 데이터를 통해 학습을 수행하면 초기 예측값이 0으로 나오는 것이 문제가 되지 않을 것이다.

(※ 평균은 row-wise, column-wise 어느 것을 사용해도 문제가 되지는 않는다. 정보가 없는 유저에 대한 첫 예측값인 0이 평균이 되도록 하는 것이 적용하는 이유이다.)

※ 본 내용은 Coursera, Machine Learning - Andrew Ng 강의, 강의자료를 바탕으로 작성하였습니다.

<Anomaly Detection>

Anomaly Detection은 비정상적인 데이터를 검출해내는 unsupervised learning 알고리즘이다.

(이후에 살펴보겠지만, training에 y가 사용되지 않는다.)

예를 들어 위와 같이 데이터(un-labeled)가 주어졌을 때, 우측하단의 anomaly로 표현된 데이터는 일반적인 데이터의 분포와 일치하지 않는 것을 확인할 수 있는데, 이를 anomlay detection으로 검출할 수 있다. 

트레이닝 데이터로 feature에 대한 가우시안 분포를 찾고, p($ X_{test}$)가 임의의 값 $ \varepsilon $보다 작으면 anomaly로 판단시키는 방식이다.

- 사기 검출

- 불량 검사

등에 이용된다.

- Algorithm

앞서 말했듯, training 데이터로 가우시안 분포의 파라미터인 $ \mu$와 $ \sigma$를 학습한다.(각각의 feature에 대해.)

※ 가우시안 분포

-> pdf가 다음과 같은 분포를 따름.

$p = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}} $

이 후 최종의사 결정은 $ p(x) $의 값과 임의로 정한 $ \varepsilon $의 값을 비교하여 결정한다.

어떠한 데이터 $ x$에 대해 $ p(x)$는 다음과 같이 계산한다.

$ \prod_{j=1}^{n}{p(x;\mu_j,\sigma_j^2)} $,

즉, 각 feature에 대해 train을 통해 학습한 가우시안 분포의 파리미터와, 그를 바탕으로 계산한 pdf 값들의 곱을 계산한다.

알고리즘을 정리하면 다음과 같다.

*step2에서 $ \sigma$의 학습 시 m으로 나누는데, 통계학에서는 m-1으로 나누기도 한다. 

약간의 차이가 있지만 주로 m이 큰 머신러닝에서는 문제가 되지 않고, m으로 나누는게 일반적이라고 한다. 

- 성능 평가

기본적으로 모델의 학습에는 y set이 사용되지 않는 unsupervised learning이지만,

알고리즘을 테스트하는 것에는 y set을 사용한다.

다른 supervised learning과 같이 cross validation set과 test set을 추가로 이용한다. 두 데이터 셋에는 y label이 포함된다.

실제 데이터를 가정한 예시는 다음과 같다.

10000개의 정상 데이터와 20개의 비정상 데이터가 있다고 할 경우 ①로 표시된 것과 같이 분류하면 된다.

training 데이터에는 normal data만 사용된다.

-> 일반적인 분포를 찾고, 그에 벗어나는 것을 찾는 것이 목적이므로 normal 데이터만 학습시키는 것이다.

(anomalous한 데이터가 조금은 포함되어도 괜찮다.)

②와 같이 사용하는 경우도 있지만 권장하지 않는다.

Cross Validation set을 이용하여 $ \varepsilon $의 값을 조정해갈 수 있고,

최종적으로 test set을 통해 모델의 성능을 평가해볼 수 있다.

anomaly detection의 결과는 skewed된 데이터가 나오기 때문에 accuracay가 아니라,

precision, Recall을 이용한 F1 score를 통해 판단해야 한다.

- Anomaly Detection vs Supervised Learning

F1 score를 적용하는 것을 보고 supervised learning을 통해한 작업과 유사한 작업을 한다는 것을 알 수 있을 것이다.

그렇다면 두 알고리즘 중 어떤 알고리즘을 선택해야할까?

결과적으로 정리하면 y = 1(anomaly)의 데이터가 많이 없다면 anomaly detection을 적용하는 것이 좋고,

데이터가 충분하여 y=1인 경우에 대한 데이터도 꽤 있다면 supervised learning을 적용하는 것이 좋다.

*강의에서는 anomaly 데이터의 수가 0~20개인 경우 보통 anomaly detection을 적용한다고 한다.

y=1에 대한 데이터가 충분하지 않아도 y=0에 대한 데이터만 있다면 anomaly detection을 위한 일반적인 데이터의 분포를 학습할 수 있지만, supervised learning에서는 y=0과 y=1을 구분하기 위한 충분한 특징을 학습할 수 없기 때문이다. 

- feature 선택, 처리

알고리즘을 보면 알 수 있듯이, feature로 주어지는 데이터가 정규분포를 따를 수록 좋은 성능을 보일 것이다.

(1) 변환

따라서 위 그림의 밑 예시 처럼 가우시안 분포를 따르지 않는 변수가 있다면, 해당 변수를 변환하여 새로운 변수로 매핑하는 방법을 취한다. 에를 들어, log를 취하거나 루트를 취하는 등의 방식이 있다.

(2) 조합하여 생성

상관관계가 있는 두 변수를 조합하여 새로운 변수로 생성해야 되는 경우도 있다.

data center의 컴퓨터들에 대해 위와 같은 feature가 주어진다고 하자. 

직관적으로도 알 수 있듯이, CPU의 load와 network traffic 는 비례한다.

위 feature를 이용하여 detection을 수행하면, CPU load 적당히 높은 것은 크게 문제가 되지 않을 것이다.(detect 되지 않음)

그러나 이때 network traffic이 거의 없었다면 CPU 의 load가 높은 경우는 detect되었어야 하는 경우이다.(ex)무한 loop에 걸림)

각각의 변수를 따로 보게되면 anomly지만 detection에 실패하게 되는 것이다.

위 그림의 $ x_5$와 같이 두 변수를 조합하여 새로운 변수를 만드는 것을 통해 해결할 수 있다.

즉, 상관관계가 있는 변수간에는 조합을 통해 새로운 변수를 생성해주는 것이 좋다. 

- Multivarivate Gaussian Distribution

위와 같이 비례관계인 두 개의 feature가 있다면 각각의 feature의 분포를 이용하면 빨간색 원으로 표시한 데이터는 일반적인 분포와 다름에도 불구하고 anomly로 검출되지 않을 것이다.

좌측의 그래프에 타원으로 표시된 영역을 train해야 하지만, 등고선으로 표시된 영역대로 p를 학습하게 된다.

*이전의 data center의 CPU load와 traffic간을 조합하여 해결하는 것과 같은 문제이다.

두 개의 방법이 모두 이용 가능하다.->선택에 대해서는 마지막에 다룸

이러한 문제를 Multivariate Gaussian 분포를 이용하면 해결할 수 있다.

Multivariate Gaussain Distribution을 살펴보면 다음과 같다.

pdf는 위와 같이 계산하고, parameter로는 $ \mu$와 $ \sum $가 필요하다.

각각 n차원의 벡터와 nXn크기의 행렬이다.

(각 feature의 평균을 계산한 벡터와 covariance matrix)

$ \sum $ parameter의 변화에 따라 분포가 어떻게 나타나는지 알아볼 수 있다.

앞서 설명했던 문제는 예시 - 3과 같은 분포를 통해 해결할 수 있을 것이다.

참고로, 축에 평행한 features로 이뤄진 model의 경우, 어떠한 모델을 사용해도 실제로는 동일한 결과가 나온다.

(mulivariate model에서도 대각 행렬만 나옴, 나머지 = 0)

*증명 생략

- Original model vs Multivariate Gaussian Model

상관관계가 있는 변수의 경우,

(1) features의 조합으로 생성한 feature를 이용한, original 모델을 사용하는 방법

(2) multivariate 모델을 사용하는 방법

두 가지 방법이 있었는데, 두 방법 중에는 어떤 방법을 어떨 때 선택해야 할까.

방법(1) -

장 : 새로운 변수를 생성하는 방법은 m이 클 때 계산적인 측면에서 저렴하다. 

단 : 그러나, feature를 어떻게 조합할지 직접 고려해야 한다.

방법(2) - 

장 : 자동으로 feature간의 상관관계를 고려한다.

단 : m이 클 경우 계산이 expensive하다.(수식에 역행렬 계산이 있음), 또한 m>n인 경우 아예 계산이 불가능하다.

(또 다른 singular한 경우. ex) linear한 관계인 변수가 있다면 적용불가, 하나 삭제하면 적용할 수 있음)

※ 본 내용은 Coursera, Machine Learning - Andrew Ng 강의, 강의자료를 바탕으로 작성하였습니다.

<Dimensionality Reduction>

Dimensionality Reduction은 여러 feature를 하나의 feature로 변환하는 등의 방식으로 차원을 줄이는 것을 의미한다.

- Motivation 1 : Data Compression

Dimesionlity Reduction을 사용하는 이유 중 하나는 Data Compression이다.

말그대로 feature의 수를 줄이므로써 데이터를 압축하는 것이다.

이렇게하면,

(1) Memory, Disk 등의 자원을 효율적으로 사용할 수 있다.

(2) 알고리즘이 더 빠르게 동작할 수 잇다.

주로 (2)번의 이유가 핵심적이라고 볼 수 있다.

위 그림은 2차원 데이터를 1차원으로 압축한 예시이다. 2개의 변수를 조합하여 하나의 새로운 변수 z를 생성한다.

* 10,000차원 -> 1000차원으로 압축하는 등의 과정도 가능하다.

- Motivation 2 : Visualization

시각화는 3차원까지만 가능하기 때문에, 많은 feature를 압축하는 것이 시각화하는 것에도 유용하다.

국가별로 다양한 feature가 있어 특징을 시각화하기 어렵지만, 적절하게 두 개의 차원으로(z1, z2) 축소시켜 시각화할 수 있다.

그 결과 대략적으로 GDP가 어느 정도인지 GDP/person 은 어느 정도인지에 대한 정보를 파악할 수 있게 되었다. 

<PCA, Principal Component Analysis>

PCA는 Dimensinality Reduction에 자주 사용되는 알고리즘 중 하나이다.

데이터를 projection시킬 벡터를 찾는데, 

해당 직선(2차원에서 투영할 시)과 데이터 사이의 거리제곱의 합이 최소가 되는 벡터를 찾는다.

예를 들어 위와 같은 데이터가 있을 때, l1으로 표시된 직선에 데이터를 projection하는 것이 l2로 표현된 직선에 projection하는 것보다 데이터와 직선사이의 거리 제곱의 합이 더 작을 것임을 알 수 잇다.

이때의 거리를 projection error라고 한다.

※ PCA와 linear regression의 차이

기본적으로 linear regression과 PCA에서 오차를 계산하는 방법이 다른 것을 알 수 있다.

또한 근복적으로도 다른 알고리즘이다.

- Preprocessing

PCA를 적용하기 전에는 다음과 같은 전처리를 수행해야 한다.

(1) Mean Normalization( 평균을 0으로, x:= x-m)

원점 지나는 vector를 찾는 과정이기 때문에 필요한 것으로 생각됨.

* PCA의 경우 수학적 증명을 많이 생략하였다. 자세한 이유는 수학적 내용을 살펴봐야 될듯.

(2) Feature Scaling (scale 차이가 큰 경우)

feature sacling은 변수의 variance를 최대한 보존하는 방향으로 수행되는데,

scale이 유독 큰 변수가 있는 등의 경우 해당 변수가 variance계산에 미치는 영향이 커지는 등의 문제가 발생하기 때문이다.

- 알고리즘 적용

수식과 라이브러리를 통해 PCA를 적용하는 법은 다음과 같다.

이하의 수식이 projection error를 최소화하는 수식과 동일한 내용이다. (증명은 생략하였음)

(1) sigma = covariance matrix를 계산한다. (nXn 크기)

*sum을 표시하기 위한 sigma와 다른 것에 주의

(2) 해당 matrix에 대한 singular value decomposition을 수행한다.

* Octave기준 svd 함수 사용,

* Covariance matrix의 경우, eigenvector를 찾는 것과 동일

(3) 결과로 나온 U 행렬 (nXn 크기)에서 k번째 열까지를 선택하여 $ U_{reduce}$ matrix로 사용한다.(nXk 크기)

*k는 축소 후 차원

(4) $ z^{(i)} = (U_{reduce})^Tx^{(i)} $,  kX1 크기의 차원이 축소된 데이터를 얻을 수 있다.

다시 한 번 정리하면 위와 같다.

- Reconstruction

압축했던 데이터를 다시 복원해야할 수도 있다.

압축에 사용됐던 식을 이용하여 복원을 수행할 수 있다.

$ z^{(i)} = (U_{reduce})^Tx^{(i)} $

임을 이용하여

$ x_{approx}^{(i)} = U_{reduce}z^{(i)}$

로 계산하면 된다.

(* U는 orthogonal 하기 때문에 transpose가 역함수와 동일하다고 한다. 따라서 위 식이 성립)

완전히 복원에 성공하는 것은 아니고, projection을 했던 형태 그대로 원래의 차원에 위치시킬 수 있다. 

따라서 $ x_{approx}$로 표시한다.

- 성능 평가, choosing k (# of principal components)

PCA를 수행할 때는 차원을 축소한 후에 variance가 얼마나 보존되는지가 중요하다.

따라서 다음과 같은 수식을 통해 k를 선택할 수 있다.

그렇다면 k를 하나씩 줄여가며 위 식을 모두 계산해야할까?

앞서 svd(Sigma)의 결과로 나왔던 S matrix를 이용하면 그렇지 않아도 된다.

좌측의 경우 k마다 계산을 반복해야 되는 reconstruction을 수행해야하는 번거로움이 있지만, 

우측은 matrix의 결과만을 이용하여 k를 선택할 수 있다.

S matrix는 대각행렬로 주어지고, 

검은색 사각형으로 표시한 식이 varinace의 보존 비율을 계산하는 식과 동일한 의미이다.

우측의 방법이 계산상 유리하다.

꼭 k를 선택할 때 뿐만 아니라, 어떤 k를 선택했을 때 variance가 얼마나 보존되었는지 나타내는 지표로도 사용할 수 있다.

* 이 부분 역시 수식에 대한 의미는 별도로 공부해야 할 듯.

- Applying PCA

PCA를 적용할 때 주의해야할 점이 있다.

PCA를 적용한 모델을 test할 때 test data도 같은 과정으로 압축을 수행해야 할 것이다.

즉, 앞서 x->z로 압축할 때, $ U_{reduce}$ matrix를 사용한 수식을 새로 들어오는 test 또는 validation data에도 적용을 해야한다. 

이때 $ U_{reduce}$ 행렬이 train 데이터로만 결정되어야 한다.

다시 말해 U = svd(sigma)로 계산되므로, sigma = Convariance Matrix가 training data로만 계산되어야 한다.

또한 잘못된 사용 예시도 존재한다.

(1) to prevent overtting

feature를 줄임으로써 overfitting을 방지하게 위해 PCA를 사용하는 것은 권장하지 않는다.

대신 regularization을 사용하는 것이 좋다.

PCA가 효과 있을 수도 있지만, 잃는 데이터가 존재하기 때문이다.

regularization은 잃는 데이터 없이 overfitting을 방지할 수 있으므로 이를 쓰는 것이 더욱 좋다.

(2) 무조건 PCA를 적용

PCA는 유용한 알고리즘이지만 앞서 말했듯이 잃는 데이터가 존재할 수 있다.

따라서 original 데이터로 사용해서 발생한 문제를 PCA로 해결할 수 있을 때만 사용하는 것이 좋다.

ex) 너무 많은 feature로 인한 속도 저하

※ 본 내용은 Coursera, Machine Learning - Andrew Ng 강의, 강의자료를 바탕으로 작성하였습니다.

<Clustring>

Clustring은 Unsupervised learning의 대표적인 예시로, labeled 되어있지 않은 데이터를 특정 집단으로 분류하는 알고리즘이다. 즉 input data의 y가 주어지지 않는다.

supervised learning에서는 두 데이터의 label을 보고 그것을 잘 구분하는 decision boundary를 찾는 방식이였다면, unsupervised learning에서는 label은 주어지지 않고, 알고리즘 스스로 군집을 분류한다.

<K-means algorithm>

K-means algoritm은 clustring을 수행하는 대표적인 알고리즘 중 하나이다.

알고리즘의 원리는 다음과 같다.

우선 위와 같은 데이터를 가정한다.

다음으로 임의의 점 두 개(몇 개의 집단으로 분류할 것인지에 따라 다름)를 선택한 후 해당 점과 거리를 기준으로 데이터를 분류한다. 

* 기준이 되는 점을 cluster centroids 라고 한다.

이렇게 데이터가 분류되고 나면, 다시 그 점들의 평균의 위치로 cluster centroids를 이동한다. 

계속하여 같은 과정을 반복하다가 더 이상 centroid의 위치가 변하지 않는다면 clustering을 마친다.

* 분류가 잘 된 시점에서는 centroid가 변하여도 더 이상 clustering에 차이가 발생하지 않는다. 이 후 평균을 계산하여 centroid를 위치하면 점들이 바뀌지 않기 때문에 같은 값이 나온다. 따라서 clustering이 완료된 것이다. 

위 과정을 확인하여 알고리즘의 동작 원리를 알 수 있다.

- K-means 구현

우선 K-means를 구현하기 위한 input은 2가지이다.

(1) 데이터( un-labeled)

(2) K (number of clusters)

K 또한 input으로 직접 선택해야 한다.

앞서 살펴본 알고리즘의 동작을 코드로 작성하면 위와 같다.

①로 표시된 반복은 각 데이터를 어떤 cluster로 분류할지 계산하고 $ c^{i}$로 저장하는 과정이다.

해당 데이터와 가장 가까운 centroid를 선택한다. (square값을 계산하는 것과 그냥 거리를 비교하는 것에는 큰 의미가 없다)

②로 표시된 반복은 cluster 별로 평균을 계산하여 다시 centroid를 선택하는 과정이다. 

* 만약 어떤 데이터도 cluster-k로 선택되지 않았다면, 

해당 cluster를 제거하거나, random initizaliztion하는 방법을 선택한다.(많이 발생하는 경우는 x)

위 과정을 centroid가 고정될 때까지 반복하면 된다. 

- Optimization Objective

앞서 supervised learning에서도 항상 cost function을 정의했듯이, 

K-means algoritm에서도 optimization objective, cost function이 존재한다.

알고리즘의 구현 과정에 cost function이 사용되진 않지만, cost function을 최적화하는 과정과 앞서 설명한 구현이 결국 같은 내용이다.

또한 cost function을 정의하면 알고리즘이 제대로 동작하는지 debug할 수 있다.

cost fuction은 다음과 같다.

K-mean algorithm에서 cost function을 distortion function이라고도 한다.

앞서 ①로 표시한 과정은 centroid를 고정시킨 상태에서 J를 최소화하는 과정이고, 

②로 표현한 centroid를 평균으로 이동하는 과정에서도 J는 작아질 수 밖에 없다.

* 수학적으로 디테일하게 풀 수도 있지만 생략, 직관적으로도 이해할 수 있음

ex) (1, 0), (5, 0) 과의 거리 제곱의 합이 가장 작은 점은 그 평균인 (3, 0)임.

결론적으로, J는 알고리즘을 수행하는 과정에서 증가하는 경우가 발생하면 안된다.

(증가한다면 구현에 문제가 있는 것)

- Random Initialization

centroid를 임의로 초기화할 때, 조금 더 좋은 방법이 있다.

성능을 보장하는 방법은 없지만, input data 중에서 서로 다른 k개를 선택하는 방법이다.

그렇게하더라도 초기화를 어떻게 하는지에 따라 다음과 같은 문제가 발생할 수 있다.

K-means 알고리즘은 local optima를 갖는다. 어떤 centroid로 시작하는지에 따라 다른 결과가 나올 수 있다.

그렇기 때문에 최선의 방법은 서로 다른 initialization에 대해 알고리즘을 여러 번 수행하는 것이다.

(대략 50-1000 times까지도.)

이렇게 하는 것이 항상 global optima를 보장하는 것은 아니지만 local optima를 찾더라도 꽤 낮은 J를 갖는 값을 찾을 가능성이 크다.

* K에 따라서도 차이가 있다. K가 작다면(2-10 정도) 여러번 적용해보는 것이 큰 향상을 줄 가능성이 크다.

K가 크다면 여러번 적용해보지 않더라도 처음부터 괜찮은 성능을 보여줄 가능성이 크다. 그렇기 때문에 여러번 적용할 경우 향상은 기대해볼 수 있지만 큰 차이는 없을 가능성도 크다.

- K, # of cluster 선택

앞선 예시들은 간단한 형태로 시각화를 통해 대략 어느 정도의 분류가 필요할지 확인할 수 있었다.

그러나 실제 데이터는 시각화가 쉽지 않은 경우가 많고, 또한 그렇게 하더라도 명확하게 몇 개의 cluster가 있다고 말하기 어려운 경우도 있다.

그렇다면 K는 어떻게 선택해야할까? 

이 문제에 대해 명확한 해결책은 없지만 다음과 같은 점을 고려해 볼 수 있다.

(1) Elbow Method

한가지 방법은 Elbow method를 이용해보는 것이다. 위 그림의 좌측 그래프와 같이 변화량이 작아지는 지점을 선택하는 것이다. 그러나 오른쪽과 같은 그래프에 대해서는 적용할 수 없다.

* K가 증가할수록 J는 감소한다. 다만, local optima가 계산된 경우에서는 그렇지 않을 수 있다.

(2) purpose of clustering

clustering의 목표를 기준으로 K를 선택할 수도 있다.

예를 들어, 위와 같이 신체 조건에 따라 옷의 size를 clustring한다고 해보자.

clustring의 목표가 상품판매이고, 

만약 5개의 size로 구분했을 때 판매량이 증가했다면, K=5로 선택할 수 있다.

또는 3개의 size로 구분했을 때 순수익이 더욱 증가하여 더 좋다고 평가한다면, K=3으로 선택할 수 있다.

K의 선택에는 automatic한 알고리즘이 없기때문에, 위와 같은 방법들을 적용해보는 것이 좋다.