올해로 4살이 된 조카가 바탕화면의 아이콘을 보고 자꾸 사탕을 찾는 것이었다. 처음에는 제엄마를 닮아 식탐이 강한 것이려니 생각 했었다. 그렇지만 정답을 알고 나서 잃어버린 동심에 대해 뼈져리게 느낄 수 있었다.

다음 그림에서 '사탕'을 찾아 보시오

정답보기

인공지능 2차 프로젝트 결과가 생각보다 잘 나왔다. 취업과 내장형시스템설계 때문에 거의 신경을 쓸 수 없어서 2차 프로젝트 준비 기간도 매우 짧았었지만, 운좋게도 도입했던 아이디어가 내 입장에서는 나름 로또를 터트려 준 덕분이었다.

2차 프로젝트 주제는 kNN(k-Nearest-Neighbor) 분류(Classification)였다. 학습 데이터(Training Data)가 실수값의 벡터 메트릭스 형태로 주어지고, 이것을 분석하여 입력되는 테스트 데이터(Test Data)를 분류해서 예측값을 출력해보는 것이다. 이 예측값의 정확도가 평가 척도가 된다. 교수님은 kNN방법을 기반으로 아이디어를 적용하여 문제를 풀어보라 하셨다. 1차 프로젝트인 TSP(Travelling Salesman Problem:외판원문제)에서 학생들의 결과 편차가 심해서 그랬는지 조교가 애초부터 1-NN으로 분류하는 프로그램을 웹에 업로드 해 놓았다.

kNN에서 변수가 될 수 있는 사항을 크게 세 가지로 보았다. 거리 개념 설정, k값 설정 그리고 특징 선택(feature selection).

첫 번째 거리 개념에 대해서는 일반적으로 생각하는 유클리드 거리(Euclidean Distance)외에 멘하탄 거리(Manhattan Distance), 마할라노비스 거리(Mahalanobis Distance) 등 여러 가지가 있다. 마할라노비스 거리(참고: 마할라노비스 거리 구하기 예제)는 데이터들 간의 상관관계를 분석하여 거리를 측정하기 때문에 분류 문제에 대해서 매우 효과적일 것이라고 생각했었지만, 딱 봐도 어려운 개념이었기 때문에 포기하고 유클리드 거리를 사용하기로 하였다.

두 번째는 k값 설정. 이 부분에 대해서는 학습 데이터를 반으로 나누어 반쪽을 가상 학습데이터, 나머지 반쪽을 가상 테스트 데이터로 설정한 후에 분류를 수행하여 가장 최적의 정확도를 보이는 k값을 채택하여 실제 테스트 데이터를 분류하는 데 사용하도록 하였다.

특징 선택에 대해서는 otsu 이진화(참고: Otsu's method)에서 사용한 분산 분석을 응용하였다. 즉, 전체 분산이 크고, intra-class variance가 작은 특징에 대해서 거리 측정시에 조금 더 가중치를 주어 보았다. 좀더 구체적으로, 각 특징 i에 대하여, 전체 분산을 intra-class variance로 나눈 값을 weight[i]로 하였을 때 아래와 같은 거리 측정을 수행하게 된다(변별력을 주기 위해 원래 개념에서 적절하게 수식을 변경해 보았다).

샘플로 주어진 세 개의 데이터집합에서의 정확도는 각각 97.77%, 96.29%, 80.00% 가 나왔다. 프로그램 데모에서도 세 개의 테스트 데이터집합이 주어졌고, 정확도는 83.33%, 87.50%, 62.00%가 나왔다. 세 번째 데이터에 대해서 안 좋은 결과가 나왔는데, 아마도 k값 설정 부분에서 무식하게 학습 데이터 집합을 보이는 그대로 절반으로 잘라서 산출한 정확도를 바탕으로 설정하였기 때문에, 대부분의 경우에서 k값이 1이 되어 조교가 파 놓은 함정에 걸린 듯하였다.

중간 보고때 교수님과의 미팅에서 '분산 분석'이라는 키워드를 말씀드리자, 교수님께서 "누구나 다 하는 그거?" 라며 *피식* 하시길래 자포자기 심정으로 구현하게 되었는데, 결과가 비교적 잘 나와서 천만다행이었다. 컴파일러 수업 때에도 그랬었지만 이 교수님 수업은 들인 노력에 비해 결과가 좋은 것 같다.