Google Distance + TTA + KNN

최근에 간단간단하게 짜본 프로그램이 몇가지 있는데 그 중에 하나를 소개합니다.

유사도 측정에관한 논문을 분석 후 값을 한번 짜봤습니다.

관련 URL : http://www.cs.vu.nl/~frankh/postscript/WWW07.pdf

일단 Google Distance 입니다.

단어 두개를 가지고 Google에 검색된 결과값에 따른 Distance 를 구해주는 공식입니다.

저렇게 NGD를 뽑아내는 함수만 잘 만들어 주면 구현하는데 어렵지 않습니다.

Client 가 입력하는 50개정도의 단어를 Google 에 Search 를 한 뒤

50개에 대한 f(x) 값과 f(x,y) 값을 추출하여 파일에 저장합니다.

이렇게 50개의 단어를 Word 로 받아 온 뒤 f(x) 는 npc.txt 에 저장하였고 

f(x,y) 는 npc_both.txt에 차례대로 저장하였습니다.Perl 을 사용하여 구글에서 파싱을 하였으며, 50단어를 검색하여 

각각의 파일에 저장하는데 30분 가량 걸렸습니다.

문제는 TTA 입니다 일단 알고리즘 부터 먼저 보겠습니다.

 TTA 알고리즘을 사용하면 각 단어들의 유사도를 측정하여 클러스터링을 할 수 있으며,

이 값을 Tree로 뽑아 낼 수 있습니다. 

저 같은 경우에는 직접 Tree를 짜서 구현을 하였는데,

STL 같은 부분을 사용하기 보다 직접 자기가 이해하고 

구현해보는것이 중요하다는 느낌을 많이 받았습니다.

Tree 분류후 thresholds 값에 따라 유사도가 비슷한 단어끼리 그룹을 이루게 되며,

클러스터링이 마무리 됩니다.

왼쪽의 Tree가 각 그룹별로 묶여진 형태이며 마우스로 그룹을 선택하면 오른쪽 그림과 같이

리스트뷰에 각 그룹의 요소들과 검색된 값인 NPC 값을 확인 할 수 있습니다.

그룹의 나눠지는 단계를 볼 수 있도록 출력에 신경을 써서 만들었습니다.

위 그림은 다른 먹는(?) 부분에 관해서 뽑혀진 그룹입니다.

마지막으로 KNN 을 구현하는것이 남았는데,

이렇게 클러스터링 된 그룹에서 내가 어떤 단어를 넣었을 때

이 단어가 어느 그룹에 속해지는지를 판단해서 그 그룹을 찾는 기능입니다.

C++ / MFC 로 구현한 전체적으로 구현된 프로그램 입니다. ( 보다싶이 UI는 형편없습니다..)

Input Data 버튼을 눌렀을 시 mint 를 Google 에서 Search 를 하여

각 값들에 대한 유사도를 Check 한뒤 가장 유사도가 가까운 그룹을 알려줍니다.

mint 라는 값을 검색하니 

Peppermint Spearmint 가 있는 그룹에 속해져 있다고 결과가 잘 나오는군요 :)

위의 버튼중에 Server 를 켜게 되면 쓰레드로써 외부에서 접속을 할 수 있도록 설정이 됩니다.

그 후 소켓으로 단어를 입력 받으면 

구글에서 검색 을 하여 어느 그룹에 속해있는지 Check 를 한 뒤,

소켓을 보낸 사용자에게 다시 그 결과를 보내줍니다.

소켓으로 결과를 보내는 부분은 C로 간단하게 짰는데 아래와 같습니다.

결과만 확인하기 위해 콘솔로 짰지만.. 영 볼품이 없네요 ^^;

전체적인 System Architecture 입니다.

하는 일이 많아 구현하는데 보름 가까이 걸렸는데

상당히 재밌있는 프로그램 이었습니다.

간만에 Perl 도 만져보았고, 유익한 정보를 얻은 것 처럼 재밌었습니다.

그래도 하드코어한 C는 이제 그만 짜고 싶기도 하네요 ㅡ_ㅠ

어느 누군가 이것이 필요한 프로그램이 필요할 까 싶어 블로그에 올립니다.

P.S. 어제 김길태씨가 잡혀서 한시름 놓았습니다.  :)