AI - 9. kNN, Gaussian Mixture

1. kNN Algorithm

-  기계학습 알고리즘 중에 가장 간단하고 이해하기 쉬운 알고리즘이다.

- 두개의 클래스로 구성된 데이터가 위처럼 나타나 있다고하자.

- knn이 어떻게 이 두 군집을 분류하는지 알아보자.

- 새로운 input으로 별이 위에 처럼 표시되었다고 하자.

- 별을 중심으로 k=3이 되는 원을 그린다는건 원 안에 3개의 데이터가 있도록 그린다는 것이다.

- 마찬가지로 별을 중심으로 k=5가 되는 원을 그린다는건 원 안에 5개의 데이터가 있도록 그린다는 것이다.

- k가 3인 knn모델의 경우는 원 안에 초록 원이 더 많으니 별표를 원이라고 인식한다.

- 하지만 k가 5라면 별표를 파랑 네모라고 인식하게 된다. 

- k가 증가함에 따라 분류결과가 달라지는 것이다.

- 참고로 일반적으로 k는 홀수를 사용한다. 

- 만약 원 안에 파랑네모 두개 초록원 두개가 있다면? 판단을 내리기 어렵다.

- k=3의 경우 아무리 별표와 파랑 네모가 가장 가까워도 원 안에 초록원이 많으니 초록원이라고 인식한다.

- 즉 거리에 대한 가중치를 무시하는 것이다.

- 따라서 Advanced kNN는 위의 두가지 문제를 해결하기 위해서 가까운 특징들에 대해서는 가중치를 부여하고 멀리있는 특징에 대해서는 낮은 가중치를 부여한다.

 

- kNN은 가장 가까운 이웃을 찾기 위해 새로운 데이터를 기존의 모든 데이터와 비교해야 한다. 즉 특징 공간에 있는 모든 데이터에 대해 정보를 필요로 한다. 

- 따라서 데이터와 클래스가 많아지만 그와 비례해서 메모리 공간과 계산시간이 많이 든다.

- 장점으로는 사전학습이나 준비과정이 없다.

2. K-means clustering

- 예를들어 의류 회사에서 S, M, L을 구분하기 위해 사람들의 키와 체중을 조사했다고 하자. 

- k-means알고리즘은 관측한 데이터들을 k개로 clusting하는 것을 말한다.

- 위의 예시에 적용하면 랜덤으로 3개의 데이터를 추출한다. 이 세개의 데이터가 중심이 된다.

- 이 세 중심점으로 부터 모든 데이터들의 거리를 구하고 가장 가까운 놈들끼리 뭉친다.

- 이렇게 세 그룹으로 뭉치고 나면 무게중심을 다시 구한다.

- 위 과정을 반복한다. 

- 소속된 클러스터가 바뀌지 않으면 멈출때가 된 것이다.

3. K를 선택하는 방법

- 팔꿈치 방법(elbow method) : k를 1부터 증가시키면서 K-means 클러스터링을 수행한다.

- k에 따라서 SSE(sum of squared error)를 계산한다.

- 이렇게 그려진 그래프에서 그래프가 수렴하는 지점에서 k를 정하게 된다.

4. Gaussian Mixture

- 결국 군집은 mean과 variance로 아래처럼 표현이 가능하다. 즉 군집을 확률로 표현이 가능해진다.

- 영상에 한 지점에 대해서 시간에 따른 변화를 R,G,B 좌표에 표시하면 다음과 같다.

- 결국 세개의 군집의 형태로 나타나고 이들은 각각 하나의 gaussian model이 된다.

- 세 모델을 합한걸 sum of gaussian이라고 하고 검정 선이다.

- 영상의 한 점이 시간에 따라 변하는 분포를 군집화 한다.

- 각 군집을 gaussian distribution으로 mean과 variance로 정의가 가능하고

- 이 세 gaussian distribution을 합해서 하나의 확률로 나타낼 수 있다.

- t+4의 새로운 이미지가 추가되면 그 특정 point를 그래프에 추가한다

- 새로운 데이터가 들어왔으니 centerpoint를 갱신하게 된다.

- 하지만 뜬금없이 새로 들어온 데이터 때문에 중심이 크게 바뀌면 안되니까 이제까지 쌓여있는 데이터들의 가중치를 감안하도록 로우를 사용하게 된다. 새로운 데이터가 들어와도 중심을 약하게 이동시키도록 한다.

- 만약 centerpoint로부터 데이터들이 촘촘히 모여있다면 그 지점은 변하지 않는 배경일 확률이 크다.

- 배경을 인식할 수 있다면 전체 이미지에서 배경만 날려서 움직이는 물체를 인지할 수 있다. (차영상기법)

- 만약 사람이 등장하면 centerpoint가 크게 변할 것이다. 이 경우는 사람을 배경으로 인식하지 않아야 된다.

- 반면 자동차가 나타나 주차되었다면 빠르게 그 차를 배경으로 인식해야 할것이다. 

- 그 결정을 하는것이 discriminant equation이다. 평균을 이동시킬지 말지 margin을 두고 결정한다.

- Correlation equation은 과거, 현재 시간의 연관성을 나타낸다.

- 차가 주차되었다면 빠르게 배경으로 인식해야하기 때문에 learing rate를 변화시켜 빠르게 학습하도록 할 수 있다.