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/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명밖에 안나왔습니다. 그것도 실명과 극중 이름이 섞여서......ㅋㄷㅋㄷ
    요것은 문서 수가 많아지면 개선될 것 같네요.. 그죠? ㅎㅎㅎ

prev 1 next