[박혜웅] Clustering(K-Means) for Delicious data

Delicious(http://www.delicious.com) 는 사용자들의 북마크 정보를 저장하는 서비스로 북마크할 때. URL에 대한 태그도 함께 저장한다. 

Programming Collective Intelligence [집단지성 프로그래밍] - 2008, Toby Segaran 의 예제로도 사용되듯이 이 태그 정보를 마이닝하면 좋은 데이타를 얻을 수 있다.

그래서 Delicious 데이타를 K-Means 알고리즘을 이용해서 Clustering 해 보았다. 보다 좋은 결과를 얻기 위해, K-Means 의 기본 알고리즘에 클러스터를 동적으로 분할 또는 제거 하도록 기능을 추가했다. (시간상 병합기능은 구현을 못했다.) 

대용량 데이타를 처리해야 하기 때문에 모든 코드는 직접 구현했다.

원본데이타 포맷

Delicious 데이타는 아래와 같은 포맷을 갖는다. 각 레코드는 줄바꿈으로 구분되며, 각 필드는 탭으로 구분된다.

각 탭의 의미는 순서대로 "날짜", "사용자(해쉬값)", "URL", "태그"이다. 이 때, (사용자 해쉬값은 개인정보를 보호하기 위해 사용자 아이디 대신 사용된 것이다.)

# 날짜          사용자(해쉬값)                       URL                                                 태그
2003-09-01      7be36a805924c0379f88832f036946af http://www.oz.net/~moz/lyrics/lyricsin.htm     lyrics

가공내역

사용된 데이타는 Delicious 2007년 12월 데이타로 데이타파일은 약 2.5GB 이며, 전체 레코드 수는 23,631,266 이지만, 가공하여 21,517,432 개를 입력 데이타로 사용하였다.

originalRows = 23,631,266 # 원본 레코드 수

removedRows = -2,162,890 # 비정상적인 태그라서 제거된 레코드 수

splitedRows = +49,056 # 다수의 태그라서 분리된 레코드 수

totalRows = 21,517,432 # 클러스터링에 입력된 레코드 수

설정파일

# KMeans 알고리즘을 수행할 최대 회수

# 단, KMeansLoopMax 이하의 회수라도 클러스터의 변경이 없으면 수행을 중단한다.

KMeansLoopMax = 100

# 클러스터의 수

initClusterCount = 100

minClusterCount = 50

maxClusterCount = 150

# minClusterSize 미만의 엔트리를 가지는 클러스터는 제거한다.

# minClusterSize 는 maxClusterSize 보다 작아야 한다.

# 단, 전체 클러스터의 수가 minClusterCount 보다 커야 한다.

# 기본값=1

minClusterSize = 2

# maxClusterSize 초과의 엔트리를 가지는 클러스터는 분할한다.

# maxClusterSize 는 minClusterSize 보다 커야 한다.

# 단, 전체 클러스터의 수가 maxClusterCount 보다 작아야 한다.

# 기본값=100

maxClusterSize = 50

클러스터링 결과

[cluster]TagURLClusters.txt

아래는 클러스터링 결과의 일부이다. 설정값을 변경하면서 몇 번 수행하고, 결과가 좋은 것을 뽑은 것이다.

노이즈가 약간 있는데, 아마도 입력 데이타를 더 많이 사용하면 노이즈가 줄어들 것으로 예상된다.

cluster[10] count:4

apps lifehacker windows utilities

cluster[12] count:4

freeware opensource software tools

cluster[13] count:2

linux ubuntu

cluster[15] count:7

drugs economics toread war article culture government

cluster[16] count:3

language english dictionary

cluster[19] count:5

apple ipod itunes mac osx

cluster[21] count:3

creativity literature writing

cluster[22] count:4

generator text image tool