2011/02/05 00:25 if (IR or NLP)

Bing이 구글의 검색 결과를 Copy 했다는 구글의 주장

구글의 검색 랭킹 담당자인 Amit Singhal 은
"I’ve got no problem with a competitor developing an innovative algorithm. But copying is not innovation, in my book.”
이라고 말하며, 마이크로소프트의 Bing이 구글의 검색 결과를 배꼈다는 식으로 이야기를 했다.

참고 URL


구글의 주장은 Bing의 검색 결과가 구글의 검색 결과와 시차를 두고 비슷해 지는 것을 발견했다는 것이다. 구글은 이를 입증하기 위해서 실험을 진행하였는데, 그 방법은 이렇다.
100개의 가상의 쿼리를 만들고, 구글 검색 엔진이 그 쿼리와 전혀 관계가 없는 문서를 검색 결과로 출력하도록 만들었다. 한 예로, "hiybbprqag" 라는 존재하지도 않는 단어의 검색 결과로 그 단어가 나타나지도 않는 문서를 검색결과로 나오도록 꾸민 것이다.
그러고는 Internet Explorer 8에 Bing Toolbar를 설치하고 "구글 검색 엔진"에 그 가상의 쿼리를 입력하고, 구글의 검색 결과를 클릭했더니, 수주 후에 그 같은 검색 결과가 Bing의 검색 결과로 나오는게 딱 걸렸다는 스토리다.

얼핏 보면 Bing의 Cheating을 구글이 지혜롭게 잡아낸 것 처럼 보이지만, 뒤집어서 생각하면 Bing의 랭킹 알고리즘 중 하나를 간파한 구글이 어뷰징을 했다고도 볼 수 있다.

실제로 Bing은 구글의 주장을 부정하지는 않았다.
"Opt-in programs like the [Bing] toolbar help us with clickstream data, one of many input signals we and other search engines use to help rank sites."
구글 검색 결과를 클릭하는 클릭 스트림은 랭킹의 수많은 시그널 중 하나일 뿐이라는 것이다. 구글이 가상으로 만든 100개의 쿼리에는 아마 다른 시그널이 전혀 들어갈 여지가 없으므로, 구글의 검색 결과가 그대로 나온 것이라는 말이다. 진짜 쿼리에 대해서는 이런 클릭 스트림의 영향이 main이 아니라, 극히 일부분이라면 구글은 함정 수사의 결과를 과장하고 있는 것이다.
posted by 심보준
TAG 검색, 구글, 빙
Trackback 0 Comment 4

Trackback | http://blog.sragent.pe.kr/trackback/46 관련글 쓰기

댓글을 달아 주세요

  1. 2012/03/15 14:48  Addr Edit/Del Reply

    비밀댓글입니다

  2. 2012/03/21 18:22  Addr Edit/Del Reply

    비밀댓글입니다

  3. 2012/03/27 16:18  Addr Edit/Del Reply

    비밀댓글입니다

  4. 2012/04/05 18:07  Addr Edit/Del Reply

    비밀댓글입니다

2010/08/22 13:06 if (IR or NLP)

NLTK(Natural Language Tool Kit)을 이용한 K-means 클러스터링

아래는 NLTK를 이용한 K-means 클러스터링 예제이다.

#!/usr/bin/python
# -*- coding: utf-8 -*-

from nltk import cluster
from nltk.cluster.util import *

# d0 = "김태호 탈세"
# d1 = "이주호 탈세"
# d2 = "신재민 위장전입 부동산투기"
# d3 = "진수희 탈세"
# d4 = "이현동 위장전입"
# d5 = "유정복 탈세"
# d6 = "이재훈 부동산투기"

# features = [김태호, 이주호, 신재민, 진수희, 이현동, 유정복, 이재훈, 탈세, 위장전입, 부동산투기]
d = [None] * 7 
d[0] = [1, 0, 0, 0, 0, 0, 0, 1, 0, 0]
d[1] = [0, 1, 0, 0, 0, 0, 0, 1, 0, 0]
d[2] = [0, 0, 1, 0, 0, 0, 0, 0, 1, 1]
d[3] = [0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
d[4] = [0, 0, 0, 0, 1, 0, 0, 0, 1, 0]
d[5] = [0, 0, 0, 0, 0, 1, 0, 1, 0, 0]
d[6] = [0, 0, 0, 0, 0, 0, 1, 0, 0, 1]

vectors = [numpy.array(f) for f in d]
# 초기 mean vector = [탈세], [위장전입], [부동산투기]
means = [[0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]] 

k = 3 
clusterer = cluster.KMeansClusterer(k, euclidean_distance, initial_means=means)
clusters = clusterer.cluster(vectors, True, trace = False)

for i in xrange(len(clusters)) :
    print 'd[%d] = cluster %d' %  (i, clusters[i])

실행 결과
d[0] = cluster 0
d[1] = cluster 0
d[2] = cluster 1
d[3] = cluster 0
d[4] = cluster 1
d[5] = cluster 0
d[6] = cluster 2
posted by 심보준
TAG k-means, nltk
Trackback 0 Comment 2

Trackback | http://blog.sragent.pe.kr/trackback/44 관련글 쓰기

댓글을 달아 주세요

  1. 엔트로피의크기 2010/08/29 14:39  Addr Edit/Del Reply

    근데, kmeans 속도 무지 쫌 저기하지 않아요? ^^;;

2009/09/13 00:16 if (IR or NLP)

조건부 확률과 Naive Bayes Classifier

예를 들어,
설문 조사 결과 모든 소비자를 놓고 봤을 때 냉면을 좋아할 확률이 70%라고 하는데, 전체가 아니라 남자가 냉면을 좋아할 확률이 궁금해 졌다. 
"남자의 경우 냉면을 좋아할 확률은?"  

비슷한 예로,
"한국인의 경우 키가 180 이상일 확률은?"
"두산 베어스가 9회에 지고 있는 상황에서 경기에 이길 확률은?"
이렇게, 그냥 확률이 아니라, 어떤 조건하에서, 어떤 경우, 어떤 상황이 주어진(given이라고 읽는다) 상태에서의 확률이 조건부 확률(Conditional Probability)이다. 그리고, 식으로는

P(냉면이좋아 | 남자)

이렇게 쓴다.

통계 기반 언어처리에서 이 조건부 확률은 무수히 많이 쓰인다.
예를 들어, 문서 분류기(Document Classifier)에서는 다음과 같은 조건부 확률이 쓰인다.
문서에 구글, 야후라는 단어가 나타난 경우 그 문서의 카테고리가 IT일 확률은? 식으로는

P(Category=IT | 구글, 야후)


자, 그럼 본격적으로 저 확률을 계산을 해보겠다.
조건부 확률의 정의에 의해서,

P(Category=IT | 구글, 야후) = P(Category=IT, 구글, 야후) / P(구글, 야후)

이다.
식에서 분자 부분을 읽어보면, Category=IT이고, 구글, 야후 라는 단어가 나올 확률이다. 용어로는 Joint Probability라고 한다. 우리말로는 잘 모르겠다. -.-;; 
난 사실 이 부분을 맨 처음 들었을 때, 조건부 확률과 Joint 확률의 의미 차이가 정말 마음에 와 닿지 않았다.
A가 주어진 경우, B이고 C일 확률(조건부 확률) 이랑,
A이고 B이고 C일 확률(Joint 확률) 이랑
뭐가 달라?
그런데, 저 위의 조건부 확률의 정의, 즉, 계산 방법을 곱씹어 보면 의미 차이가 조금씩 와 닿는다.
만일 전체 샘플이 1000개라고 하면, 1000개중에서 카테고리가 IT이고, 구글이랑 야후라는 단어가 나타나는 문서가 5개가 있다면 P(Category=IT, 구글, 야후) = 5/1000 = 0.005 이다.
만일 전체 샘플이 1000개 인데 그중에 야후, 구글이라는 단어가 나타나는 문서가 10개이고, 10개중에 카테고리가 IT인 문서가 5개 라면, P(Category=IT | 구글, 야후) = 5 / 10 = 0.5 이다.
구글, 야후가 나온 문서로 한정 지으면 카테고리가 IT일 확률은 0.5라는 얘기다. 참 쉽다. 정말?

자자, 이제 진짜 문서 분류 얘기를 해보자. 진짜 문서에 구글, 야후 처럼 달랑 두 단어 있는 문서를 만나는 행운이 과연얼마나 있을까? 실상은 이렇다.

P(Category=IT | 구글, 야후, 네이버, 다음, ... 그외 수백 단어)

조건부 확률의 정의에 의해

P(Category=IT | 구글, 야후, 네이버, 다음, ... 그외 수백 단어)
=  P(Category=IT, 구글, 야후, 네이버, 다음... 그외 수백 단어) / P(구글, 야후, 네이버, 다음, ... 그외 수백 단어)

말로 풀자면 이렇다. 우린 지금, 문서에 구글, 야후, 네이버, 다음, ... 그외 수백 단어가 나타난 상황하에서 문서의 카테고리가 IT인 확률을 알고 싶다.  정의에 의해서 샘플 중에서 구글, 야후, 네이버, 다음, ... 그외 수백단어가 똑같이 나온 문서들 중에서, 카테고리가 IT인 문서를 세보면 조건부 확률을 구할 수 있다.
그런데 과연, 샘플에 구글, 야후, 네이버, 다음, ... 그외 수백단어가 똑같이 나온 문서가 1개는 있을까? 있는게 이상하다. 결론! 조건부 확률 정의 식은 무용지물이다.

이 시점에서 어디서 주워들은 독립가정을 들이 미는 사람이 있을 법하다. 그러니까, 정의식의 분자에 독립가정을 적용하면, 즉, '각 단어의 출현은 서로 아무 인과 관계가 없어' 라고 가정하면, 각 단어 출현 확률의 곱으로 바꿀 수 있다 뭐 이런거 말이다. 그렇게 해볼까?

P(Category=IT | 구글, 야후, 네이버, 다음, ... 그외 수백 단어) 
=  P(Category=IT, 구글, 야후, 네이버, 다음... 그외 수백 단어) / P(구글, 야후, 네이버, 다음, ... 그외 수백 단어)
=  P(Category = IT) x P(구글) x P(야후) x P(네이버) x P(다음) x P(... 그외 수백 단어) / P(구글) x P(야후) x P(네이버) x P(다음) x P(... 그외 수백 단어)
= 약분하면 --> P(Category = IT)
결론 : P(Category=IT | 구글, 야후, 네이버, 다음, ... 그외 수백 단어) = P(Category = IT) --> 조건이 있으나 없으나 확률은 똑같다는 모순에 도달!

응? 결국 저 독립가정의 결론은 수백 단어가 나오든 수천 단어가 나오든 '카테고리가 IT일 확률은 그냥 카테고리가 IT일 확률이다.' 라는 가정을 해버렸다는 뜻이다. 이 가정은 옳지 않다. 문맥을 보고 카테고리를 결정하려고 하는게 애초의 목적이니까.

그래서, 필요한게 Bayesian Rule이다. Bayesian Rule에 의하면

P(Category=IT | 구글, 야후, 네이버, 다음, ... 그외 수백 단어)
= P(Category=IT) x P(구글, 야후, 네이버, 다음, ..., 그외 수백 단어 | Category=IT) / P(구글) x P(야후) x P(네이버) x P(다음) x P(... 그외 수백 단어)

 
로 쓸 수 있다. 여기서 두번째 확률
P(구글, 야후, 네이버, 다음, ..., 그외 수백 단어 | Category=IT) 은 구할 수 있나? 즉, 샘플에서 Category=IT인 문서들 중에서 구글, 야후, 네이버, 다음, ..., 그외 수백 단어가 똑같이 나오는 문서는 몇개? 역시나 샘플에는 수백개의 단어가 똑같이 나오는 문서는 없을 것이니 이거 역시 불가!
하지만, 여기서 저 위에서 처럼 어설프지 않은 제대로 된 독립가정을 할 수 있는데 이름하여 '조건부 독립(Conditional Independence)' 가정이다. 말로 풀어 쓰자면 이렇다.
Category가 IT인 조건 아래에서는 구글, 야후, 네이버, 다음, 그외 수백 단어의 출현은 독립적인 사건이라고 가정한다. 이걸 식으로 쓰면

P(구글, 야후, 네이버, 다음, ..., 그외 수백 단어 | Category=IT)
= P(구글|Category=IT) x P(야후|Category=IT) x P(네이버|Category=IT) x P(다음|Category=IT) x ...  x P(그외 수백 단어|Category=IT)

이다. P(구글|Category=IT) 는 샘플에서 (구글이란 단어가 있는 문서 수 / 카테고리가 IT인 문서 수)로 확률을 구하면 된다.

최종적으로 Naive Bayes Classifier는 이런 확률 계산을 모든 카테고리에 대해서 해본 다음 확률이 제일 높은 카테고리를 선택하게 된다. 마지막 정리는 뽀대나게 수식 편집기로.
세번째 줄에서 네번째 줄로 넘어 갈때 분모가 사라진 이유는 여기서는 argmax 카테고리 c를 구하는게 목적이므로, 모든 카테고리에서 같은 값인 분모는 생략해 버린 것이다.
posted by 심보준
TAG Naive Bayes Classifier, 조건부 확률
Trackback 0 Comment 4

Trackback | http://blog.sragent.pe.kr/trackback/33 관련글 쓰기

댓글을 달아 주세요

  1. 엔트로피의크기 2009/09/17 10:31  Addr Edit/Del Reply

    joint probability는 결합확률이라고 불리더라고요.
    글고, Ctegory가 뭡니까? ㅋㅋ Category 오타.
    conditional independence가 가정되는 이유는 대개 계산복잡도가 커지니까 문제를 단순히 하기위해서라고 합니다.
    근데요, smoothing parameter도 중요할걸요? ㅋㅋ

  2. 심보준 2009/09/17 17:31  Addr Edit/Del Reply

    허걱. 하필 그림에서 오타야.

  3. 강석진 2009/11/06 11:01  Addr Edit/Del Reply

    너무 좋은 내용이라서 rkamin.egloos.com 으로 퍼갑니다. 지우시길 원하시면 지우겠습니다.

2009/08/05 19:20 if (IR or NLP)

Latent Semantic Analysis(LSA)

1. 단어 매칭만으로는 뭔가 부족한 정보검색
예부터 들이 밀고 이야기를 시작해보겠다.
이 예에서, 키워드 검색이라면 주어진 쿼리에 문서1만 매칭에 성공한다. 그런데, 문서의 의미를 가만히 살펴 보면, 문서2 역시 쿼리에 적당한 문서이다. Latent Semantic Analysis(이하 LSA)는 예에서 보듯이 키워드 매칭으로 찾을 수 없는, 의미가 가까운 단어-문서, 단어-단어, 문서-문서를 찾을 수 있게 해준다. 

어떻게 '중국집 메뉴' 와 '짜장면 짬뽕'이 가깝다는 것을 찾아준다는 것일까? 이 때 이용하는 정보가 co-occurrence (공기, 共起)정보다. 문서1을 보면 '중국집 메뉴'와 '짜장면 짬뽕'은 같이 쓰였다. 바꿔 말해, co-occur한다.(共起한다.) 이 사실을 힌트 삼아 쿼리와 문서2 또한 가깝다고 유추할 수 있다. 

LSA는 개념적으로 co-occurrence 정보를 이용한다. co-occurrence 정보를 이용한다는 것은 단어의 '형태(morphology)가 아닌 의미(semantic)'를 이용한다는 뜻이다. 예를 들어 '배'라는 단어는 같은 문장에 co-occur 하는 동사가 '타다' 인지 '먹다' 인지에 따라 의미가 갈라지게 된다.  또한, '식당', '맛있게', '배부르게' 라는 단어와 같은 문장에 co-occur하는 처음 보는 단어는 아마 '음식'일 것이다. LSA는 이론적으로는 선형대수학의 SVD(Sigular Value Decomposition)을 이용한다. SVD를 계산하는 방법에 대해서는 얘기하지 않을 것이다. 시간은 없고, 라이브러리는 많다.

2. LSA는 SVD를 이용한다.
이제 부터가 진짜다. 다음과 같은 단어-by-문서 행렬 A가 있다.(Reference:이 예는 Foundations of Statistical Natural Language Processing에서 베꼈다.)

예제 : 단어-by-문서 원래 행렬

SVD는 원래의 단어-by-문서 행렬 A를 3개의 행렬로 분해(Decomposite, SVD의 D)한다.
At×d = Tt×nSn×n(Dd×n)T
여기서 아래첨자 txd는 t행 d열의 행렬이라는 뜻이고. 위첨자 T는 전치행렬(transposed matrix)인데, 원래 행렬의 행과 열을 뒤바꿔 놓은 행렬이다. t 는 단어 개수, d는 문서 개수 n은 min(t,d)이다. 행렬 A의 SVD를 (각자 구한 라이브러리를 이용하여)구하면 다음과 같이 3개의 행렬이 얻어진다.

원래 행렬 A 의 SVD

T는 단어에, D는 문서에 대응되는 행렬이다. 각 단어와 문서는 5차원 공간의 한 점으로 표현되고 있다. 대각행렬 S는 오른쪽 아래로 갈 수록 작은 값을 가지는데 5개의 값은 1~5번째 차원의 Scale로 생각할 수 있다. 더 뒤쪽 차원으로 갈 수록 그 Scale이 낮아진다는 뜻이다. 위에서 얘기했듯이 n의 값 5는 t와 d중 작은 값이다. 그런데, SVD는 여기서 n보다 훨씬 작은 k 값을 설정해서 그 이상의 차원은 날려버리는 방법으로 차원 축소를 해버린다.

3. LSA는 co-occurrence + 차원 축소
SVD에 대한 자세한 얘기는 대부분 생략했지만, 개념적인 이야기로 한번만 더 정리하고 넘어가겠다. 위 예 처럼 조그만 예가 아니라 실제 상황에서는 t(단어 개수), d(문서 개수)의 값은 수*만에 이를 것이다. min(t, d)인 n 역시 수*만에 이를 것이다. 만일 t = 100만, d= 500만 이었다면, 원래 행렬 A는 100만 차원 공간에 있는 500만개의 점을 표현하는 행렬이다. SVD를 구하는데 k = 100으로 정한다면, 행렬 A는 다음과 같은 3개의 행렬로 분해된다.
T : 100차원 공간에 100만개의 단어에 대응되는 점으로 표현
D : 100차원 공간에 500만개의 문서에 대응되는 점으로 표현
S : 1 ~ 100번째 차원의 중요도를 나타내는 대각행렬
위 표현에서 '대응되는 점'이라는 간접적인 표현을 쓴 것은 직접적으로 값을 사용하는 게 아니기 때문에 그렇게 쓴 것이다. 용도에 맞게 행렬을 사용하는 방법은 잠시 후에 얘기하겠다. 

일단, 여기서 D 행렬만 놓고 생각을 해보자. 원래의 공간에서는 500만개의 문서는 100만 차원 공간의 한 점으로 표현되었다. 그런데, 행렬 D에서는 500만개의 문서가 100차원으로 차원 축소된 공간의 한 점으로 '투영된다(projection)'. 축소된 공간으로 투영되는 와중에 비슷한 co-occurrence 패턴을 가지는 문서나 단어는 가까운 위치로 접근을 하게 된다. (무슨 마술 처럼 이야기를 하네-.-;;;) 그래서 LSA의 핵심 개념을 두 가지로 요약하면,
1. co-occurrence 정보 이용
2. 차원 축소
가 되겠다.

4. 활용 - 분해된 행렬의 사용방법
그럼, 잠시 미뤄 놓았던 3개의 행렬을 사용하는 방법을 말할 차례이다. 위의 예(5 x 6짜리 A행렬)에서 구했던 3개의 행렬을 k = 2로 차원 축소를 하면 3 ~ 5차원은 버려지고, 아래와 같은 차원 축소된 조합이 된다.

2차원으로 차원 축소한 SVD


3가지 시나리오에서의 이용방법은 다음과 같다.
1. 단어 - 단어간의 유사도 T X S 행렬의 row 간의 유사도로 계산한다.
2. 문서 - 문서 S X DT 행렬의 colum 간의 유사도로 계산한다.
3. 단어 - 문서 TSDT의 각 요소가 단어와 문서간의 유사도이다.
제일 만만한 2번 시나리오, 문서-문서간의 유사도를 어떻게 계산하는지만 예를 들어 보겠다. 위 그림에서 S X DT 행렬을 구해보면 다음과 같다.

S X DT 행렬

결과적으로 DT 행렬을 S행렬에 의해 re-scaling한 행렬이다. 암튼 문서1과 문서2의 유사도는 위 행렬의 1번째 컬럼과 2번째 컬럼의 cosine 유사도를 구하면 된다. 그렇다면, 모든 문서 쌍에 대해서 문서-by-문서간의 coine 유사도를 계산할 수 있다. 그 결과를 표로 그리면 다음과 같다.

문서-문서 간의 유사도

1.00은 자기 자신과 비교한 것이니까 빼고, 문서4-문서5가 가장 가까운 문서로, 문서3-문서6이 가장 먼 문서로 판명되었다. 맨위에 나온 행렬 A 그림에서 원래 문서를 찾아보면 이해가 될 것이다. 그런데, 여기서 문서2-문서3의 비교 결과가 흥미롭다. 원래 행렬 A에서 보면 두 문서는 공유하는 단어가 하나도 없다. 하지만 이 표에서는 유사도가 0.88로 매우 높게 나온다. 이게 다 co-occurrence와 차원 축소를 이용한 LSA의 결과이다. 

휴~ 여기까지. 누군가는 처음부터 끝까지 읽었으면 하는 마음에 내용을 줄이다 줄이다 보니 너무 많은 부분이 빠졌다. 특히, SVD에 의한 차원 축소에 대한 부분은 거의 한강을 건너 뛰는 수준이다. 이 부분에 대한 설명은 위 예제를 베껴온 Foundataions of Statistical Natural Language Processing 책에 정말 잘 나와있다. 아... 이런 말로 마무리를 하게 되다니. 아뭏든 여기까지 읽어준 분이 있다면, 감사합니다.
posted by 심보준
Trackback 1 Comment 13

Trackback | http://blog.sragent.pe.kr/trackback/28 관련글 쓰기

  1. LSA (Latent Semantic Analysis)

    Tracked from  Del data mining for information retrieval 2011/11/29 13:33

    http://blog.sragent.pe.kr/entry/Latent-Semantic-AnalysisLSA http://en.wikipedia.org/wiki/Singular_value_decomposition http://stat.ethz.ch/R-manual/R-patched/library/base/html/svd.html 문서들을 N개의 차원(단어)로 이루어진 M개의 문서 ..

댓글을 달아 주세요

  1. 엔트로피의크기 2009/08/26 22:27  Addr Edit/Del Reply

    진짜 정리를 잘하셨군요.

  2. sofree 2009/10/25 14:56  Addr Edit/Del Reply

    너무 잘 봤습니다. 프린트해서 삼공펀치로 찍어서 철 해놨습니다.^^
    질문하나 해도 될까요?
    3가지 시나리오 이용방법 중에,
    문서-문서 유사도 검색을 S X DT 행렬의 colum 간의 유사도로 계산하는 근거는 뭔가요?

  3. sofree 2009/10/25 14:58  Addr Edit/Del Reply

    (위의 질문에 이어서..)
    정확한 이해를 위해서는
    eigenvector나 eignevalue가 의미하는 것을 알아야 할 듯 싶은데..저는 단지 계산하는 방법 정도만 알고 있는듯 싶어서요.

    • 심보준 2009/10/25 23:31  Addr Edit/Del

      잘 보셨다니 감사드립니다.

      부끄럽게도 저도 SVD를 수학적으로 이해한게 아니라서 시원한 답을 못드리겠습니다.
      SVD의 결과를 놓고 개념적을 파악한 수준입니다.

      본문의 밑에서 두번째 그림에서 보듯이 S X DT행렬의 각 컬럼들은 원래의 문서 vector를 2차원 vector로 차원 축소한 것들입니다. 따라서 문서간의 유사도를 컬럼 벡터간의 유사로 계산을 합니다.

  4. 민경구 2010/05/12 15:09  Addr Edit/Del Reply

    오랫만이네 잘 배우고 감 ^^;
    근데 적절한 차원값 k는 어떻게 정하면 좋은것이야... 연락처는 mingk24 골뱅이 지메일 ~~

    • 심보준 2010/05/13 14:08  Addr Edit/Del

      반갑다 ^^
      Foundations ... 책에서는
      "Values of k that are frequently chosen are 100 and 150." 이라고만 나와 있는데, 자세한 내용은 더 찾아봐야 알겠다.

  5. 유고연방 2010/09/28 16:17  Addr Edit/Del Reply

    아...정말 필요한 정보였는데...감사합니다.
    나름 된 포스팅이군요.^^
    근데 문서2하고 문서3 공유하는 단어가 없는데 유사도 높게 나온건 어찌 받아들여야 하나요?ㅋ
    아까 첫번째 예에서 짬뽕-메뉴 이런 식으로 co-occurrence의 결과로 봐야하겠지만.....
    맞나요?ㅋ
    암튼 좋은 포스팅 감사합니다.

    • 심보준 2010/09/29 13:51  Addr Edit/Del

      문서2와 문서3은 모두 문서1과 공유하는 단어가 있는 탓에 유사한 문서로 나왔습니다.

  6. 연수용 2010/10/11 21:55  Addr Edit/Del Reply

    좋은 자료 잘 읽고 갑니다.^^

  7. 감사 2011/08/03 04:19  Addr Edit/Del Reply

    올려주신 자료는 정말 유용하게 잘 봤습니다. svd로 주신 예제로 다 돌려봤는데요 마지막에 코사인 유사도는 어떻게 구하나요? 제가 매틀랩 초보라서.... 어떻게 계산해야하는지 알려주실수 있나요? 부탁드립니다~

  8. 이영록 2011/09/28 21:27  Addr Edit/Del Reply

    LSA에 대해 공부하고 있는데 다른 자료들 보고 잘 이해가 안됬는데,

    이글을 보고 완전 이해하고 갑니다. 정리 완전잘하셨어요 필요한 부분만

  9. park.suhyuk 2011/11/29 13:16  Addr Edit/Del Reply

    재미있게 읽고 갑니다. "SVD + 대각행렬 차원축소"가 핵심이네요. 그리고 3가지나(?) 응용할 수 있으니 정말 멋지네요~ 감사합니다.

2009/04/26 01:26 if (IR or NLP)

k-means++ : k-means에서 초기 center를 잘 선정하는 방법

k-means알고리즘은 맨 처음 k개의 center를 잘못 정하면 엉뚱한 결과가 생길 수 있다.
예를 들면, 다음 그림과 같은 경우이다.
k=3 일때, 파란색 세개의 클러스터로 묶이는 것이 올바른 결과다. 하지만, 잘못 해서(또는 재수가 없어서) 두번째 열의 인스턴스 세개를 초기 center로 잡고 k-means 알고리즘을 돌리면 엉뚱하게도 빨간색 묶음으로 클러스터링되는 난감한 결과가 생기고 만다. 이게 2차원으로 시각화 되어서 그렇지, 실제 상황에서는 눈에도 잘 안뜨일 듯.

그래서, 이제 갖가지 초기 center 정하는 방법들이 등장하게 된다. 창시자들이 저렇게 빈틈을 남겨주어야 후배 연구자들이 먹구 살 거리가 생기게 된다. 암튼, 개선안 중에 하나가 그럼 되도록 center간의 간격을 멀게 멀게 만들자는 것이다. 위의 예를 계속 이용하면 아마 이렇게 될 것이다.

1 ~ 3이 초기 center로 선정된 instance들이다. 1번은 랜덤으로 선정된 것이고, 2번은 1번으로 부터 제일 먼 것, 3번은 1번, 2번으로 부터 가장 먼 것으로 선정된다. 이렇게 선정한 세개의 center를 가지고 클러스터링을 하면 창시자의 부족함을 매꾸며 성공적인 클러스터링을 달성함과 동시에 후배들에게 또다시 TODO list를 남겨준다. 즉, 이 방법 또한 큰 약점을 가지고 있는데, Outlier라는 넘을 만나면 여지 없이 무너지는 수가 있다.
이 번에는 k=2인 경우인데 되도록 먼 인스턴스를 선택 하다보니 맨 오른쪽 독도 같은 outlier가 초기 center로 선정되었다. 이러고 k-means를 돌리면, 7:1의 클러스터링이 탄생할 것이다. outlier말고, 가운데 3개 중에 하나가 선택되면 좋을 텐데 말이다.

이래서 등장한 것이 k-means++. k-means++는 다음 순서대로 하나씩 하나씩 1번 부터 k번째 center까지 정한다. 이게 개념은 참 간단한데, 글로 표현하는 것이 쉽지가 않다.
1. 1 번째 center는 랜덤으로 정한다.
2. for i = 2 ~ k
    모든 인스턴스 x마다 아래의 확률을 부여한다.
    p(x) = D(x)2/Σx'D(x')2     [x'는 인스턴스집합 X의 원소들]
    여기서 D(x)는 x에서 지금까지의 center중 제일 가까운 center와의 거리를 뜻한다.
    그러면, 모든 인스턴스에 확률이 부여된 이 상태에서 i 번째 center를 'random으로 찍는다'.
    높은 확률이 부여되어 있다는 것은 i번째 center로 선정될 가능성이 높다는 뜻이다.
D(x)의 뜻이 핵심이다. center를 한개 한개 만들어 가는데, 지금까지 만들어진 center중에 제일 가까운 center와의 거리.
위 식의 분모는 모든 인스턴스 x의 D(x)2의 합이니까. 모든 x에 대해서 같고, 결국 분자인 D(x)2이 큰 게 확률이 높다. 그러면 결국 D(x)가 클수록 확률이 높다. 이 얘기는 지금까지 만들어진 center들과 멀 수록 확률이 높다는 건데, 그럼 결국 먼거를 찍는다는 얘기?? 그럼, 저 위에 거랑 똑같다? 그럴리가.
중요한 건, 확률을 저렇게 정해놓고, 랜덤으로 찍는다는 것이다. 그러니까, 거리가 먼 outlier는 물론 확률은 높다. 하지만, 거리가 가장 먼 놈을 무조건 선정하지는 않는다는 것이다. 무조건 먼거로 결정할 거면 그냥 D(x)만 구하지, 굳이 D(x)2 나누기 D(x')2의 합을 굳이 구하지는 않았겠지. 그림을 보면,

파란색이 1번째 center이고, 이제 2번째 center를 선정하려고 한다. 숫자는 인스턴스 마다 지금까지 center 중(지금은 파란 인스턴스 하나뿐) 제일 가까운 것과의 거리인 D(x)이다.
이제 인스턴스마다 확률을 부여해야 하는데, 분모 먼저 구하면 모든 D(x)2의 합이니까 12+52+52+52+82=140 이다. 그러면, 제일 가까운 인스턴스의 확률은 1/140, 빨간색 애들은 각각 25/140, 제일 먼 애는 64/140 의 확률을 받는다. 이런 확률를 놓고 랜덤으로 찍는다. 제일 먼 인스턴스의 확률(64/140)이 가장 높지만, 세개의 빨간 인스턴스 중의 하나가 될 확률(3 * 25/140)이 더 높다. 먼 것도 유리하지만, 몰려있는 것중 하나가 될 확률도 높다. 2제곱이라는 숫자는 거리를 확률에 반영하는 정도를 결정하는 factor라고 생각하면 되겠다.

요약 정리 : k-means++는 확률 기반으로,
1. center가 밀집되지 않게
2. outlier는 되도록 피하면서
k개의 초기 center를 선정하는 방법이다.

참고 :
k-means++: The Advantages of Careful Seeding(David Arthur et al. 2007)
slides
posted by 심보준
Trackback 0 Comment 10

Trackback | http://blog.sragent.pe.kr/trackback/26 관련글 쓰기

댓글을 달아 주세요

  1. 엔트로피의크기 2009/04/30 14:05  Addr Edit/Del Reply

    제일 먼 인스턴스의 확률(64/176)이 가장 높지만, -> 제일 먼 인스턴스의 확률(64/140)이 가장 높지만, ??
    그리고, 인스턴스 밀집도를 표현하는 '3'을 곱해주는 것은 위 식에 안나와 있잖아요. T.T

    • 심보준 2009/05/01 20:13  Addr Edit/Del

      숫자 오타는 수정했어.
      식은 인스턴스 하나가 선택될 확률이고,
      빨간 인스턴스 3개중에 하나가 선택될 확률이니까 곱하기 3.
      열심히 읽어줘서 감사.

  2. 마루 2009/11/27 05:56  Addr Edit/Del Reply

    음.. 궁금한 점이 있는데요 두번째 센터까지는 저렇게 구한다지만 세번째 센터를 구할때 거리에 관해서 이미 정해진 두 센터중 어떤 센터를 기준으로 확률을 계산해야 하나요? 점들별로 가까운 센터가 다 틀릴텐데.. 이부분이 이해가 안되요 ㅡ.ㅜ

    • 심보준 2009/11/27 12:37  Addr Edit/Del

      알고리즘 설명 박스에 보면
      "여기서 D(x)는 x에서 지금까지의 center중 제일 가까운 center와의 거리를 뜻한다." 라는 말이 있습니다.
      3번째 센터를 구기 위해 D(x)를 계산할 때는 1, 2번째 센터중 가까운 센터와의 거리를 구하고, 4번째 센터를 구할 차례라면 1, 2, 3 번째 센터중 가중 가까운 센터와의 거리를 구하고...
      이런식으로 진행됩니다.

  3. 마루 2009/11/27 13:09  Addr Edit/Del Reply

    음..분자의 D(x)는 해당 인스턴스에서 가장 가까운 정해진 센터의 거리가 되는것으로 이해하는게 맞는건가요 ㅡ.ㅜ
    ^^; 그리고 또있는데요 분모의 sum D(x') 는 무조건 첫번째 센터에서 모든 인스턴스로의 거리의 합이되는건가요?
    참 어려운거같아요 ㅡ.ㅜ

    • 심보준 2009/11/27 18:14  Addr Edit/Del

      첫번째 질문의 답은 '예'이구요.

      두번째 질문의 답은
      인스턴스 각각 마다 가장 가까운 센터를 다르게 선정하는 것이 맞습니다.

  4. 마루 2009/11/28 14:14  Addr Edit/Del Reply

    감사합니다 ^^ 많은 도움이 되었어요~

  5. 유리막대 2010/04/23 20:01  Addr Edit/Del Reply

    좋은글 감사합니다. 그런데 글을 읽던중 궁금한점이 있어서 글을 남깁니다.
    위의 내용을 요약하자면 영상의 모든점의 확률(D(x))를 랜덤으로 뽑아서 seed로 뽑힐 확률을 높인다는 개념인거 같은데..
    그렇다면 굳이 분모(D(x'))가 필요한 이유가 있는지 궁금합니다.
    분모 값으로 정규화를 해주지 않아도,, 랜덤으로 뽑기에 필요한 값의 분포는 D(x)가 충분히 가지고 있는게 아닌가 궁금합니다. 분모를 사용하지 않을경우에 다른점이 있는지요...

  6. Hoonyz7 2011/05/26 17:10  Addr Edit/Del Reply

    좋은 포스팅 잘 읽었습니다.

    k-means에 대해 공부하다가 k-means++이 있는것도 알게 되었네요.

    말씀하신대로라면 k-means++에서 다음 center를 구하기위해 선택하는 방법은

    Genetic algorithm의 Roulette wheel selection과 거의 흡사하다고 생각되는군요.. 맞는지요 ??

  7. 김일두 2011/11/27 16:15  Addr Edit/Del Reply

    잘 보고 갑니다 :)

2009/04/03 16:54 if (IR or NLP)

한자어가 우리말을 얼마나 애매 모호하게 만드는지 알아봤습니다.

한국어 언어 처리나 검색 엔진 튜닝을 하다 보면 '한자어' 때문에 발생하는 중의성이 정말 많습니다.
문제의 시작은 이렇습니다.
家 : 집 가
價 : 값 가
可 : 옳을 가
加 : 더할 가
假 : 거짓 가
... (이하 24개 생략)
-----> 한글로 쓰면 모두 '가'
'가'가 너무 극단적인가 하면 그렇지도 않습니다. '사'는 60개 입니다. 키보드로 '사' 치고 한자키 눌러 보면 알 수 있습니다.
상황이 이러하니, 어떤 단어가 '***가***' 이렇게 생겼다면 '가' 부분에서 29개의 의미적 중의성이 발생합니다. 

좀더 자세히 알아보려고 간단한 프로그램을 만들어 돌려봤습니다. 얘기 더 나가기 전에 용어 정리 한번 하는게 좋을 듯 합니다.
한자 : '家', '羅' 이런 것들
한자 독음 : 한자를 한글로 읽은 것. '가', '나'
한자어 : '한국', '남자', '여자' 처럼 한자 단어를 한글로 쓴것
이게 표준 용어 인지는 잘 모르고 제가 이렇게 쓰겠다는 겁니다.
먼저, 우리가 자주 쓰이는 한자를 어떻게 모을까... 궁리하다가 '천자문'을 긁었습니다. 그리고, 1000개의 한자에 대해서 한자 독음으로 치환해 보아봤습니다. 한자 독음 변환은 여기를 참고하면 됩니다.
천자문 한자를 독음한 결과는
사 : 20개 한자
조 : 16개 한자
상 : 15개 한자
수 : 15개 한자
기 : 14개 한자
이 : 12개 한자
경 : 12개 한자
...(생략)
체 : 1개 한자
첨 : 1개 한자
농 : 1개 한자
이렇게 321개의 한글 음절로 읽히고 있었습니다. 그러니까, 321개의 한글 음절은 평균적으로 3.12개(=1000/321)의 중의성을 가지고 있습니다.

그런데, 더욱 난감한 것은 이런 한자어 음절이 차지하는 비율입니다.
약 85,000개의 블로그 포스트에 대해서 프로그램을 돌려봤더니 한글 음절이 38,137,237번 출현했고 글자 개수는 3,019개 였고, 이 중에 천자문 한글 독음 321글자는 25,513,041번 출현으로 전체의 67%에 이르렀습니다.
그러니까, 11%(321/3019)의 한자 독음 음절이 전체 음절의 67%를 차지하고 있다는 말입니다. 헉스!
한글로 된 문장을 읽으면서 3분의 2의 글자 글자 마다 3~4개의 한자중 어떤 의미에 해당하는지, 우리는 갈등하고 있다 이것이죠.
3~4개 뿐만이 아닙니다. '가', '이', '을' 이런 글자는 한자어 외에 순우리말 조사로도 쓰이니까, 중의성은 더 늘어납니다. 게다가, '사', '조', '상' 이렇게 뜻이 여러개인 글자는 문장에 더 많이 나오겠죠.

한글자 짜리 한자 독음이 그렇다는 것이고, 단어로 가면 좀더 중의성을 체감할 수가 있습니다. 우리나라의 지역 이름은 거의 대부분 두글자짜리 한자어인데요. 중의성을 띄는 지역 이름이 부지기수입니다.
서울, 대전, 대구, 부산 부터 봐도, 서울 빼고는 모두 다른 뜻이 있는 단어들입니다. 수도권을 둘러 보면, 양주, 구리, 오산, 이천(숫자 이천말입니다.) 등등이 있구요. 강남역에 가면 택시 기사 아저씨들이 이렇게 외칩니다.
"분당 만원!"
10분만 가도 10만원입니다.

이렇게 된 이유는, 한자를 한글로 표기하는 과정에서 발음이 특정 음절로 수렴되는 현상이 일어난 것입니다.
중국어에는 한국어에는 없는 발음들이 존재합니다. 그 반대의 경우도 물론 있겠지요. 없는 발음도 한글로 표기를 해야 하니 수렴이 현상이 일어나게 됩니다. 영어 'r'발음과 'l'발음이 모두 'ㄹ'로 표기되는 것과 마찬가집니다. 그리고, 중국어에는 성조도 있습니다.
또, 훈민정음 이래로, 아니 그 이전부터 한자 1개에 독음 1음절이 지켜지고 있는데, 원래 중국어는 안 그렇거든요. 예를 들어, '愛'라는 글자의 한글 독음은 '애'입니다. 그런데 중국어로는 '아이'라고 읽습니다. 두 음절로 읽히는 글자들까지 한 음절로 읽으려고 하니까 독음에 수렴현상이 일어나게 됩니다.

이런 문제의 맥락에서 한자, 한글 병기를 주장하는 사람들이 있었던 것이겠죠. 모든 일간지에서 한글 전용이 채택된 지가 얼마 안되었구요, 중의성이 절대 허락 안되는 법전에서는 아직도 한자가 병기되고 있습니다. 저는 한자, 한글 병기로 돌아가자는 쪽은 절대 아닙니다. 그 보다는 될 수 있으면, 한자어 대신 순우리말을 쓰자는 쪽입니다. 그러니까,
'출입문개방요망' 이렇게 쓰지 말고, '문을 열어놔 주세요' 이렇게 쓰자는 말입니다. 사용하지 말고 쓰자는 말입니다.
posted by 심보준
TAG 한자어
Trackback 0 Comment 2

Trackback | http://blog.sragent.pe.kr/trackback/25 관련글 쓰기

댓글을 달아 주세요

  1. 레몬라임 2009/04/09 14:05  Addr Edit/Del Reply

    찬성이요~
    근데, 요새 인간들은 한자어보다 영어 독음으로 해서 말이죠. 그게 더... ㅋㄷㅋㄷ

  2. 심보준 2009/04/25 23:03  Addr Edit/Del Reply

    응 그런데, 영어 독음은 중의성보다, 오타가 많아서 힘들지
    콜린 베일리 래
    코린 베일리 래
    코린 배일리 레
    ...

2009/03/11 22:45 if (IR or NLP)

K-means 알고리즘을 이용한 영화 배우 클러스터링

k-means 알고리즘을 이용해서 영화 배우 이름을 클러스터링 하는 실험을 해보았습니다.

단어가 문서에 출현하는 횟수를 다음과 같은 테이블로 표현할 수 있습니다.

각각의 열을 하나의 문서 벡터로 표현할 수 있는 것과 마찬가지로, 각각의 행은 하나의 '단어(텀) 벡터'로 표현할 수 있습니다. 즉, 아래와 같은 모습입니다.
A = <1, 3, 0, 0, 0>
B = <0, 0, 0, 1, 2>
C = <2, 1, 0, 0, 3>
D = <0, 0, 3, 0, 0>
이처럼 각각의 단어를 벡터로 표현할 수 있습니다.
또한, 이렇게 구한 벡터끼리 유사도(Similarity)를 구하면 두 단어가 얼마나 가까운 단어인지 계산할 수 있습니다. 위의 예를 보면 A와 B는 멀고, C는 A, B 양쪽에 모두 가깝다는 것을 알 수가 있습니다. 이런 벡터 표현을 이용하면, 문서를 클러스터링 하는 것과 똑같은 방법으로 단어를 클러스터링 할 수도 있습니다. 단어 클러스터링은 관련 검색어나, 토픽맵, 관련 문서 찾기 등 다양한 의미 기반 응용프로그램에 이용될 수 있습니다.

K-means 알고리즘
저는 K-means 알고리즘을 이용해서 단어 클러스터링을 테스트해 보았습니다. 아래는 K-means 알고리즘에 대한 간략한 소개입니다.
1. 적당한 클러스터 개수 K를 선정한다.
2. 각 클러스터 마다 초기 중심 벡터(centroid)를 선택한다.
3. 각 instance를 각 클러스터의 중심벡터와 비교하여 가장 가까운 클러스터로 할당한다.
4. 각 클러스터에 할당된 instance들의 평균을 계산하여 클러스터마다 새로운 중심벡터를 구한다.
5. 3, 4를 반복하면 클러스터링이 진행된다. 인스턴스가 새로운 클러스터로 이동하는 일이 없어지면 iteration을 중단한다.
이 알고리즘에는 K의 선택, 초기 centroid의 선정, iteration 중단 조건, 유사도 계산 방법 등 몇가지 이슈가 있지만, 이 포스팅에서는 다루지 않겠습니다.

클러스터링 실행
85,771개의 최근 블로그 포스트에 등장한 영화배우 이름 1005개를 이용해서 클러스터링을 실행해 보았습니다. 영화배우 이름 목록은 여기서 구했습니다. 영화 배우 벡터는 다음과 같이 표현됩니다. 0인 부분은 생략하고, 대신 <문서번호:출현횟수> 방식으로 표현했습니다.
박주미 = <8746:1, 55731:1>
문근영 = <220:1, 803:3, 3016:1, 3954:1, 6033:3, 8124:1, 8837:5, 9184:1, 9770:1, 13362:1, 15403:1, 16514:2, 16517:1, 18811:1, 20047:1, 29290:1, 33458:1, 36278:1, 36694:1, 41038:1, 41066:2, 42945:5, 42946:1, 42949:4, 43094:1, 44280:1, 49120:3, 53376:1, 53377:4, 580      21:2, 58027:2, 60246:4, 60431:7, 61896:1, 63994:2, 64110:2, 65770:5, 68207:3, 72367:2, 74112:3, 74474:5, 76494:6, 76495:10, 76496:8, 76497:10, 81073:10>
배두나 = <8320:1, 13707:1, 55315:1, 63738:1.0>
이연희 = <707:2, 2155:1, 7680:2, 10572:2, 18510:1, 18806:1, 22324:1, 22329:1, 22331:1, 30836:1, 33760:2, 38076:2, 39504:4, 45111:3, 46030:1, 53222:1, 55306:1, 55731:1, 65607:2, 66649:1, 68665:2, 70244:1, 70251:1, 75375:1, 80136:1, 84844:1>

클러스터 개수 K는 그냥 별다른 고민없이 50으로 정했고, cosine 유사도를 이용했습니다. 실행결과 흥미있는 클러스터를 몇개 골라봤습니다. <center> 표시는 클러스터의 중심벡터와 가장 가까운 배우 이름입니다.
CLUSTER-9 : [강성연, 김민선, 김영호, 김정태, 김태연, 문성근, 박지영, 유지태, 전세홍, 최규환, 추자현<center>, 현정은]
이 클러스터는 '미인도'와 3월말 개봉 예정인 '실종'이라는 영화의 배우들이 몰려있습니다. 김민선, 김영호, 추자현, 최규환 등이 '미인도' 출연진이고 문성근, 추자현, 전세홍은 '실종' 출연 배우들입니다. 추자현 덕분에 문성근과 김영호가 같은 클러스터에 묶이게 되었습니다.

CLUSTER-12 : [강병규, 김수미, 김태진, 김흥기, 배도환, 유인촌, 이계인, 이순재, 이준기<center>]
이 클러스터의 주류는 '전원일기' 출연진입니다. 김수미, 김태진, 유인촌, 이계인이 전원일기 출연진입니다. 이계인이 노마아빠고, 김태진이 노마라고 합니다. 그런데, 이런. 최불암 회장님이 빠졌네요. 이준기가 이계인과 일지매에 출연한 인연으로 묶였고, 강병규는 유인촌하고 베이징 올림픽 응원하러 간 인연으로 엮였습니다.

CLUSTER-41 : [김래원, 박진희, 백도빈<center>, 백윤식, 엄정화, 엄태웅, 유건, 정시아]
정시아가 백윤식의 아들 백도빈하고 결혼을 했는데, 유건이 사회를 봤다고 합니다. 김래원은 엄태웅의 누나 엄정화하고 인사동 스캔들을 찍고 있다고 합니다. 두 그룹은 별 관계가 없는데, 연애 소식 관련 모둠 글에서 하나로 엮였습니다. 문서수가 작으니 이런 문제가 생기는군요.

CLUSTER-42 : [구혜선<center>, 김소은, 김현주, 김형준, 김혜성, 민지, 윤지후, 이민정, 이민호, 이시영, 장태성, 정의철]
꽃남 클러스터가 나왔습니다. 배우 윤지후가 등장인물 윤지후로 묶여 버렸습니다. F4가 다 들어갔는지는 제가 드라마를 안봐서 잘 모르겠습니다.

아무래도 클러스터링을 하기에는 문서수가 적었습니다. 문서수가 적은 이유는 성능 후진 단일 머신에서 돌렸기 때문입니다. 그러다 보니, 최불암, 김혜자 회장님이 내외분이 전원일기 클러스터에 안 묶이고, 부부인데 떨어진 경우도 많았습니다. 아, 물론 옥소리와 박철은 같은 클러스터에 묶이더군요. 전체 결과를 파일로 첨부해 놓았습니다.

 
posted by 심보준
TAG k-means, 클러스터링, 텀클러스터링
Trackback 1 Comment 4

Trackback | http://blog.sragent.pe.kr/trackback/24 관련글 쓰기

  1. 꽃남 악녀 국지연

    Tracked from  Del 연예의 인연으로... 2009/03/17 16:38

    꽃남 악녀 국지연1984년04월17일생으로 현재 모델이고 KBS 2TV \"꽃보다 남자\"에 출연하고 있으며, 동서식품,코카콜라,한국 피자헛,보광 휘닉스 파크,하이트 맥주등 텔레비전 광고에 출연중임.

댓글을 달아 주세요

  1. 2009/04/09 14:06  Addr Edit/Del Reply

    비밀댓글입니다

  2. 엔트로피의크기 2009/04/24 10:45  Addr Edit/Del Reply

    음... 요새 이런 것을 하고 계셨군요. 이제 다시 읽게 되었습니다.
    근데요,
    5. 3, 4를 반복하면 클러스터링이 진행된다. 인스턴스가 새로운 클러스터로 이동하는 일이 없어지면 iteration을 중단한다.
    이거요.
    (생략) 인스턴스가 새로운 클러스터로 이동하는 일이 '적정 기준치 개수 이하이면' iteration을 중단한다.
    아니에요? 흐...
    그리고, 꽃남의 주력 인물 6명중 3명밖에 안나왔습니다. 그것도 실명과 극중 이름이 섞여서......ㅋㄷㅋㄷ
    http://search.daum.net/search?t__nil_searchbox=btn&nil_id=tot&w=tot&stype=tot&q=%B2%C9%BA%B8%B4%D9%B3%B2%C0%DA

  3. 엔트로피의크기 2009/04/24 10:47  Addr Edit/Del Reply

    아, 다시다시.
    꽃남의 주력 인물 6명중 3명밖에 안나왔습니다. 그것도 실명과 극중 이름이 섞여서......ㅋㄷㅋㄷ
    요것은 문서 수가 많아지면 개선될 것 같네요.. 그죠? ㅎㅎㅎ

2009/02/01 14:37 if (IR or NLP)

정규분포 이론을 이용한 검색엔진의 정확도 평가

떨어진 미션이 있어서 통계 공부를 좀 하고, 공부한 내용을 정리해 봤습니다. 내용을 요약하자면, 검색엔진의 정확도를 평가했을 때, 그 평가가 얼마나 신뢰할만한지 통계학의 정규분포 이론을 이용해서 계산하고, 설명하는 내용입니다. 이 포스트를 이해하면 팀장과 이런 대화를 나눌 수 있습니다.
A: 우리 검색엔진의 정확도는 85~90%입니다.
팀장: 그 말 몇 %나 신뢰할 수 있지?
A: 믿어주세요. 95% 확실합니다.

일의 출발은 이렇습니다.
우리가 개발한 검색엔진의 정확도를 측정하려고 합니다. 정확도는 재현율일 수도 있고, 정확률일 수도 있고, F-measure일 수도 있습니다. 그냥 통칭해서 정확도라고 하겠습니다. 정확도를 측정하기 위해서 수작업을 통해서 정답셋을 만들기로 했습니다.

어떤 질의 Q에 대한 정답셋은 아래와 같이 만듭니다.
1. 검색엔진이 색인하는 모든 문서에서 n개의 문서를 샘플링합니다.
2. n개의 샘플 문서를 사람이 하나씩 하나씩 읽어가며 질의 Q에 대해서 검색결과로 올바른지 아닌지 체크를 합니다.
3. 체크된 n개의 샘플 문서를 질의 Q에 대한 정답셋이라고 합니다.

정답셋을 이용해서 질의 Q에 대해 검색엔진의 정확도는 다음과 같이 측정합니다.
1. 검색엔진에 질의 Q를 실행하면 검색 결과가 주루룩 나올 것입니다.
2. n개의 샘플 문서를 하나씩 하나씩 검토합니다.(검색 결과를 하나씩 살피는게 아닙니다.)
 - 각각의 문서에 대해 정답셋에서 체크한 내용과 검색엔진의 판단이 같으면 검색엔진이 정답을 맞춘것입니다.
 - 반대로 판단이 다르면, 즉, 정답셋에는 이 문서는 이 질의에 나와야 된다 그러는데 검색엔진이 이 문서를 안찍었다든가, 아니면 정답셋에는 이 문서가 이 질의에 안 맞다고 그랬는데 검색엔진 결과에 포함되었을 때 검색엔진이 틀린 답을 낸 것입니다.
3. 여기까지 하면, 질의 Q에 대해서 검색엔진이 n개의 문제를 풀어서 맞춘게 몇개, 틀린게 몇개 그래서 점수는 몇점 이렇게 성적표를 받게 됩니다.

여기서 질문이 하나 생깁니다.

몇개의 문서를 샘플링해야 위에서 계산한 검색엔진의 성적이 믿을만 할까?

검색엔진한테 10개의 문제를 풀게하는 것보다는 당연히 100개의 문제를 풀게 하는게 실력을 파악하는데 더 정확할 것입니다. 엔진은 지치지 않으니까 당연히 다다익선! 더 많은 문제를 풀게 할 수록 우리가 얻는 점수는 더 신뢰할 수 있는 점수 일 것입니다. 그런데 문제는 엔진이 지치는게 아니라, 사람이 지친다는 것입니다. 정답셋을 만드는 과정은 만일 100만개의 문서를 샘플링했다면 100만개의 문서를 하나씩 읽어가며 질의에 적합한 문서인지 아닌지 체크를 해야 합니다. 그러니까, '많을 수록 좋은건 알아, 하지만, 적어도 몇개의 문서를 샘플링하면 믿을만 한거야?' 이것이 문제입니다.

결론부터 얘기하자면 통계학을 이용하면 위의 질문에 대해서 직접적인 답은 못주지만, 다음과 같이 결론을 이야기할 수는 있습니다.

1만개의 문서를 샘플링해서 측정한 이 검색엔진의 정확도는 0.7 ~ 0.9일 확률이 95% 입니다.

음... 뭐랄까 신중하지만 정확한 설명입니다. 샘플의 개수를 좀더 늘리면서 똑같이 95%의 신뢰도로 정확도가 얼만지 측정하면, 이번에는 구간이 좁아질 것입니다.

2만개로 샘플을 늘려서 측정한 이 검색엔진의 정확도는 0.75~0.85일 확률이 95% 입니다.

바로, 지체 없이, 공식과 예제 들어가도록 하겠습니다.
샘플 문서의 개수가 n개, 검색엔진 돌려서 채점한 결과 r개가 맞았을 때, 이 검색엔진의 정확도를 N% 만큼 신뢰도로 구하면 다음과 같은 구간을 구할 수 있습니다.


여기서 Z(N)은 신뢰도에 따라 값이 달라지는데 95% 신뢰도로 구하고 싶으면, 1.96이라는 값을 사용하면 되고, 90% 신뢰도로 구하고 싶으면 1.64라는 작은 값을 사용하게 됩니다. 좀 낮은 신뢰도로 말하면 더 좁은 구간을 제시할 수 있다 이런 얘기입니다.
위 식을 사용하는 예제 들어갑니다.
예제> 1000개의 문서를 샘플링 해서 검색엔진이 800개를 맞췄다. 95% 신뢰구간으로 검색엔진의 정확도를 설명하라.
풀이> x=800/1000 = 0.8 이고, Z(N) 루트 어쩌구 하는 식은 1.96X루트(0.8X0.2/1000)=0.02479 이므로
"이 검색엔진의 정확도는 0.77521 ~ 0.82479 일 확률이 95% 입니다." 라고 얘기할 수 있습니다.
샘플링 하는 문서 개수를 10000개로 늘려보고, 같은 비율인 8000개를 맞췄다면 이번에는 Z(N) 루트 어쩌구 하는 식이 1.96X루트(0.8X0.2/10000)=0.00784 이므로
"이 검색엔진의 정확도는 0.79216 ~ 0.80784 일 확률이 95% 입니다." 라고 더 정확하게 얘기할 수 있게됩니다.

얘기가 이정도 진행되면, 지금 정규분포(Normal Distribution)를 얘기하려 한다는 것을 알만한 사람은 다 알 수 있을 것입니다. Z(N) = 1.96 이 숫자도 통계책 부록 표준 정규분포표에서 따온 숫자입니다.
그렇다면, 도대체 뭐가 정규분포를 따른다는 얘기일까요? 이 질문이 가장 핵심적인 부분입니다.

우리가 만든 검색엔진의 정확도의 확률분포는 정규분포이다.

'의'를 중첩해서 대단히 죄송합니다만, 이 포스트를 이해하고 싶으신 분은 이 문장이 가슴에 와닿을 때까지 반복해서 읽으셔야만 합니다. 도저히 와닿지 않으면, 아래 그림의 x축과 y축을 곱씹고 다시 저 문장이 와닿을 때까지 읽어보십시오.
즉, 다음과 같은 정규분포입니다.

이 그래프의 경우 검색엔진의 정확도가 60%일 확률이 가장 높습니다. 검색엔진의 정확도가 50%일 확률과 70%일 확률은 같습니다. 즉, 대칭입니다.
우리가 저 위의 식을 사용하겠다는 것은 검색엔진의 정확도가 이 그래프처럼 생긴 정규분포라고 가정하겠다는 뜻입니다.
그런데, 무슨 근거로 검색엔진의 정확도가 정규분포라고 함부로 가정을 할 수가 있는 것일까요? 여기서 통계 이론 하나가 더 필요합니다.

이항분포(Binomial Distribution)에서 샘플의 개수 n이 충분히 크다면 그 이항분포는 정규분포이다.

검색엔진이 정답을 맞춘 횟수의 분포는 이항분포(이항분포가 뭔지는 잠깐만 홀딩)입니다. 이항분포는 샘플의 개수가 충분히 크다면 정규분포가 됩니다. 정답을 맞춘 횟수를 샘플의 개수 n으로 나눈 정확도의 분포 또한 정규분포가 됩니다.

정리하자면, 검색엔진의 정답 맞추기의 확률분포는 이항분포입니다. 이항분포에서 샘플 개수가 충분히 크면 정규분포입니다.  정규분포라면 저 위의 공식에다가 샘플의 개수와 샘플에서 측정한 정확도를 대입하여, 검색엔진의 진짜 정확도를 추정(Estimation)할 수가 있습니다. 그럼 마지막으로 이항분포가 뭔지, 검색엔진의 정답 맞추기가 왜 이항분포인지를 설명하고 마치도록 하겠습니다.

통계학에서 성공-실패 두 가지 경우의 수가 존재하는 독립적인 실행을 n번 반복하는 것을 베르누이 시행(Bernoulli Trial)이라고 합니다. 베르누이 시행에서 성공 횟수의 확률 분포를 이항분포라고 합니다. 베르누이 시행의 대표적인 예로 찌그러진 동전 던지기를 들 수 있습니다. 이 실험의 목적은 찌그러진 동전이 앞면 몇% 짜리 동전인지 알아보는 것입니다. 이 것을 알아보기 위해 100번을 던져봤더니 앞면이 70번 나왔습니다. 이게 한번의 n=100짜리 베르누이 시행입니다. 첫번째 베르누이 시행의 결과는 이 동전은 앞면 70% 짜리 동전입니다. 두번째 베르누이 시행을 하면 아마 70번 언저리의 어떤 숫자가 또 나올 것입니다. 베르누이 시행을 여러번 하면 이 동전에 대해서 다음과 같이 얘기할 수 있을 것입니다.
"이 동전은 n=100짜리 베르누이 시행을 했을 때 앞면이 70번 나올 확률이 30%, 69번 나올 확률이 10%, 68번 나올 확률이 7%..."
이 내용을 그래프로 그리면 이 동전의 이항분포가 되는 것입니다.

우리 검색엔진의 정확도 평가 또한 이항분포를 따릅니다. n=100 이라면 100개의 문서 각각에 대해 결과를 맞추는지 못맞추는지 판단합니다. 즉, 동전을 100번 던집니다. 통계학 정리에 따르면 n이 충분히 큰 이항 분포는 정규분포로 가정할 수 있다고 합니다. 일반적으로(Rule of Thumb) n>=30 정도면 정규분포로 볼 수 있고, np(1-p) > 5 라는 식으로도 최소한의 n을 산정할 수가 있습니다. 여기서 p는 검색엔진의 진짜(궁극적인, 실제의)정확도인데, 그건 우리가 구하고자 하는 그 자체이므로, 실험에서 구해지는 추정치(즉, 맞춘개수/n)를 대입하면 될 것입니다.

마지막으로 정리 한번 더 하겠습니다. 반복 또 반복...
검색엔진의 정답 맞추기는 동전 던지기처럼 베르누이 시행이고, 확률분포는 이항분포입니다. 이항분포이므로 샘플개수가 충분히 크면 정규분포 가정을 이용할 수 있습니다. 정규분포 가정을 이용하면 저 위의 식을 이용하여 검색엔진의 정확도를 계산하고 그 결과를 다음과 같이 얘기할 수 있습니다.
"이 검색엔진의 정확도는 0.85~0.95일 확률이 95%이다."
이 말을 통계학적인 용어로 바꿔말하면 "95% 신뢰구간에서 +- 0.05의 오차를 가진다" 라고 얘기합니다.
만일 더 많은 샘플을 사용한다면 같은 신뢰구간에서 더 작은 오차를 가지게 될 것입니다.

-----------------------------------------------------------------------------------------------------------------

제가 정규분포에 대해 스터디를 하게 된 것은 두가지 질문에 답을 얻기 위한 것이었습니다.
첫째, 우리가 할 검색엔진 평가 작업에 대해서 정규분포 가정을 적용할 수 있을까?
둘째, 신뢰도를 95%로 고정하면 몇개의 문서를 샘플링을 해야 하나?

첫번째 질문에 대해서는 검색엔진 평가가 베르누이 시행이라는 설명으로 해결했다고 할 수 있습니다만, 둘째 질문에 대해서는 정규분포 이론에 대해서 무지했었다는 것을 알게 되었습니다. 샘플링은 다다익선이고 샘플이 적으면 오차 범위가 넓어지는 것이 공식이 설명하는 바였습니다. 아 물론, 이항분포가 정규분포가 되기 위해서 샘플이 30개는 넘어야 한다는 사실은 알게 되었습니다.

posted by 심보준
TAG 검색엔진평가, 이항분포, 정규분포, 정답셋
Trackback 0 Comment 1

Trackback | http://blog.sragent.pe.kr/trackback/18 관련글 쓰기

댓글을 달아 주세요

  1. 레몬라임 2009/02/26 01:03  Addr Edit/Del Reply

    흠흠, 회사에서는 윗분의 감성 척도가 평가 기준 아닐까요? ㅎㅎㅎ

2008/12/13 01:56 if (IR or NLP)

음식이름 포스팅 Part 2

지난번에 블로그에서 음식이름의 출현 횟수를 통계낸 포스팅을 했었습니다. 그 포스트에서 예고를 했듯이 이번에는 음식 이름의 co-occurrence(공기, 共起, 동시출현) 정보를 뽑아 보았습니다. 지난번과 마찬가지로 약 8만개의 rss feed 주소로 약 75만개의 포스트에서 통계 정보를 만들었습니다.
먼저 단순하게 co-occurrence 횟수를 세어 본 결과는 다음과 같습니다. 횟수를 보다 정확히 말하면 두개의 음식이 한개의 포스트에 함께 출현한 횟수입니다.

사용자 삽입 이미지

매우 친숙한 조합이 상위에 많이 나왔습니다. '라면-밥' 이 '김치-밥'을 제치고 1등을 차지했습니다. 저는 사실 '김치-라면'이 1등을 차지하지 않을까 했었는데 기대만큼 해주지를 못했습니다. 100등까지 쭉 보면 재밌는 조합이 많이 있습니다. 20등 '밥-피자' 이걸 같이 먹었다는 건지 뭔지. 25등 '김치-빵'이 있는데 이 조합 먹어봤는데 괜찮습니다. 김치라는 음식이 아무 음식에나 굉장히 잘 어울립니다. 자꾸 얘기가 새는 군요. 배가 고파집니다. 100등 '샌드위치-샐러드'까지 의미있어 보이는 조합이 많습니다.
그런데, '라면-사과'는 도대체 뭥미? 인가 싶어서 구글로 검색을 때려 봤더니 흠 역시 중의성을 가진 두개의 단어라 음식 이름 쌍이 아닌 결과들이 많습니다. 예를 들어 이런 것들 입니다. 남자라면 사과랍니다.  뭐 키워드 매칭이라는 바닥 자체가 그렇습니다. 새겨서 이해해야 할 때가 많고, 또 그걸 뭐라고 하는 사람도 별로 없습니다.

그런데, 이 방법은 사실 매우 옳지 않습니다. 단순히 동시 출현한 횟수를 세는 것은 당연히 많이 출현하는 음식들이 유리하게 됩니다. 두 단어의 의존 정도를 계산하는 방법으로 Mutual Information이나 카이제곱 테스트 등등이 있는데요, 저는 Mutual Information을 사용해 보았습니다.
Mutual Information(정확히 말하자면 Pointwise Mutual Information)의 계산식은 다음과 같습니다.
사용자 삽입 이미지




예를 들어, 전체 문서셋의 전체 토큰 개수가 1억개이고 라면이 20번 출현, 김치가 30번 출현, 라면-김치 동시 출현이 10번이라면 MI는 다음과 같습니다.
사용자 삽입 이미지





그런데, 위의 식을 사용하면 한가지 문제가 있습니다. 즉, Sparse 데이터 문제가 발생을 해서, 굉장히 적은 출현 빈도가 나타나는 단어들이 높은 MI값을 받어 버립니다. 위에서 했던 단순 카운팅 때와 정반대의 문제입니다. 이 문제의 해결 방법을 비롯해서 Mutual Information에 대한 자세한 내용은 저~~ 유명한 구글을 이용하시기 바랍니다. 저는 기냥 단순하게 동시 출현 횟수가 30보다 작은 단어쌍은 싹둑 잘라냈습니다. 결과는 이렇습니다.

사용자 삽입 이미지

1등이 아주 제대로입니다. 총각김치는 깍두기를 제치고 배추김치와 더 가까운 김치로 판정났습니다. 탕수육과의 궁합에서는 짜장면(22위,25위)이 짬뽕(28위)보다 앞섰습니다. 저 위쪽의 표는 밥, 라면, 빵 이런 주식류였는데 여기는 시원하고 얼큰한 국수나 국물있는 음식같은 메인 메뉴들이 많이 보입니다. 17위 '보쌈-족발' 아 정말 땡깁니다. 그만 정리하고 뭐라도 먹어야 할 듯합니다. 지금 시간 1시 51분 이러면 안돼는데...
posted by 심보준
Trackback 0 Comment 3

Trackback | http://blog.sragent.pe.kr/trackback/15 관련글 쓰기

댓글을 달아 주세요

  1. 레몬라임 2008/12/15 12:00  Addr Edit/Del Reply

    예, 맞아요. 출현 빈도가 적은 데이터에 대한 고려에 따라 상호정보량 계산의 결과로 제시하기도 하고 안하기도 하죠...^^; 재미난 실험이네요. 그런데 출현빈도가 높은 것들은 실험하지 않아도 당연히 그럴거라 추정할 수 있는 거 아니에염? ㅋㅋ

    • sragent 2008/12/15 16:11  Addr Edit/Del

      당연한 내용이지만 넣는게 글 전체의 모양새가 살거든...

  2. 2011/08/09 23:31  Addr Edit/Del Reply

    비밀댓글입니다

2008/10/28 01:39 if (IR or NLP)

블로그 출현 음식 이름 TOP 100

문득 블로그에 출현하는 음식 이름의 순위를 매겨 보고 싶어졌습니다. 제가 약 8만개의 rss feed 주소로 75만개 정도의 블로그 포스트를 수집해 놓은 것이 있습니다. 이럴 때 쓸 수도 있는 것이었군요.

먼저 음식 DB를 멋들어지게 구축하는 방법을 고민하기 시작했습니다. 위키피디아의 요리 카테고리를 크롤할까 궁리를 한참하다가 이건 좀 오바다 싶어서 그냥,
네이버 요리법 디렉토리와 쓸만한 칼로리표를 마우스로 손 크롤했습니다. 이렇게 해서 모두 1079개의 음식목록을 만들었습니다. 감, 죽 등 형태소 분석 오류 가능성이 높은 한글자 짜리 음식은 아쉽지만 분석 대상에서 제외했습니다.
블로그 포스트를 형태소 분석하고, 출현하는 음식이름을 카운팅, 정렬을 했습니다.

>결과 뚜둥~
사용자 삽입 이미지


라면이 밥을 제치고 1등을 차지했습니다. 음- 물론, 라면은 중의성이 있는 단어라 공정하지 못한 결과일 수도 있습니다. 80만개의 포스트에서 3만번 이상 '라면' 이라... 거품이 심하군요. 암튼 어쨌든. 따지자면 '밥'이란 단어도 특정 음식이 아니라 음식 일반을 총칭하는 단어로 쓰이기도 하기 때문에 2위에 까지 오를 수 있었겠지요. 과일 중에서는 사과가 압도적인 일등...앗 그러고 보니 사과도 중의성이 있군요. 흠흠흠. 하여간 과일, 샐러드류가 의외로 상위권을 차지했습니다.
라면을 제외한 분식류에서는 김밥이 만두, 떡볶이를 제쳤습니다. 짬뽕과 짜장면의 대결은 순위상으로는 짬뽕이 이겼지만, 짜장면과 자장면을 합친 숫자에서는 역시 짜장면의 승리입니다. 샌드위치가 햄버거를 이겼고, 김치찌개가 된장찌개를 이겼습니다. 아 이런. 그런데 삼겹살이 빠졌습니다. '삼겹살구이'라는 이름으로 올라가 있는 것을 알아차리지 못했습니다.

다음에는 음식이름의 co-occurrence 정보를 뽑아 보면 흥미로울 듯하다는 생각도 드는군요.
posted by 심보준
Trackback 0 Comment 6

Trackback | http://blog.sragent.pe.kr/trackback/9 관련글 쓰기

댓글을 달아 주세요

  1. 지민아빠 2008/10/28 12:07  Addr Edit/Del Reply

    co-occurrence 라는 말은 어려워요. 이왕이면 쉽게. ^^

    • sragent 2008/10/28 13:27  Addr Edit/Del

      동시 출현이요. 한 문서에 동시에 나오는 음식 이름을 보고싶다는 뜻.
      공기(共起)라는 말로 쓰기도 하는데. 더 구리죠.
      잘 알면서 ^^

  2. gruter 2008/10/28 21:47  Addr Edit/Del Reply

    멋있습니다.^^

  3. 레몬라임 2008/10/29 20:44  Addr Edit/Del Reply

    음식이름과 잘 공기하는 단어죠. '맛있습니다'
    연관 검색어 추출의 주된 방식이죠. ㅇㅎㅎ

    • sragent 2008/11/03 11:03  Addr Edit/Del

      음식이름과 공기하는 단어들을 뽑아 놓는 것도 쓸모가 쏠쏠할듯.

prev 1 2 next