계층적 클러스터링은 가장 유사한 두 그룹을 지속적으로 병합함으로써 그룹의 계층을 형성한다. 이러한 각 그룹은 개별 블로그에서 단일 항목으로 시작한다. 각 반복에서 이 방법은 모든 그룹 쌍 사이의 거리를 계산하고, 가장 가까운 그룹들은 함께 병합되어 새로운 그룹을 형성한다. 이것은 한 그룹만 있을 때까지 반복된다. 그림 3-1은 이 과정을 보여준다.
그림에서, 항목의 유사성은 상대적 위치(두 항목이 가까울수록 더 유사함)로 표현된다. 처음에는, 그 그룹들은 단지 개별 품목일 뿐이다. 두 번째 단계에서는 가장 가까운 두 항목인 A와 B가 합쳐져 두 항목 사이의 중간 위치에 있는 새로운 그룹을 형성했음을 알 수 있다. 세 번째 단계에서 이 새로운 그룹은 C와 합병된다. D와 E는 이제 가장 가까운 두 항목이기 때문에 새로운 그룹을 형성한다. 마지막 단계는 나머지 두 그룹을 통합한다.
계층적 클러스터링이 완료된 후에는 대개 결과를 계층으로 배열된 노드를 표시하는 덴드로그램이라는 그래프 형식으로 본다. 위 예제의 덴드로그램은 그림 3-2와 같다.
이 덴드로그램은 연결부를 사용하여 각 군집에 어떤 품목이 있는지 보여줄 뿐만 아니라, 그 거리도 아이템이 얼마나 멀리 떨어져 있는지 보여준다. AB 클러스터는 DE 클러스터가 개별 D, E 항목보다 개별 A, B 항목에 훨씬 가깝다. 그래프를 이렇게 렌더링하면 클러스터 내의 항목이 얼마나 유사한지 확인하는 데 도움이 되며, 이는 클러스터의 조임으로 해석될 수 있다.
이 섹션에서는 블로그 데이터셋을 클러스터링하여 블로그의 계층을 생성하는 방법을 보여 주며, 성공하면 블로그를 주제별로 그룹화한다. 첫째, 데이터 파일에 로드하는 방법이 필요할 것이다. clusters.py이라는 파일을 만들고 여기에 다음 기능을 추가하십시오.
def readfile(filename):
lines=[line for line in file(filename)]
# First line is the column titles
colnames=lines[0].strip( ).split('\t')[1:]
rownames=[]
data=[]
for line in lines[1:]:
p=line.strip( ).split('\t')
# First column in each row is the rowname
rownames.append(p[0])
# The data for this row is the remainder of the row
data.append([float(x) for x in p[1:]])
return rownames,colnames,data
이 기능은 맨 위 행을 열 이름 목록으로 읽고 맨 왼쪽 열을 행 이름 목록으로 읽은 다음 모든 데이터를 큰 목록에 넣으며, 이 목록의 모든 항목은 해당 행의 데이터가 된다. 모든 셀의 수는 데이터의 행과 열에 의해 참조될 수 있으며, 이는 로네임 및 콜네임 목록의 색인에 해당된다.
다음 단계는 친밀함을 정의하는 것이다. 우리는 2장에서 유클리드 거리와 피어슨 상관관계를 두 영화 비평가들이 얼마나 비슷한지를 판단하는 방법의 예로 사용하여 이것을 논의했다. 이 예에서 일부 블로그는 다른 블로그보다 더 많은 항목을 포함하거나 훨씬 더 긴 항목을 포함하며, 따라서 전반적으로 더 많은 단어를 포함할 것이다. Pearson의 상관관계는 두 개의 데이터 세트가 얼마나 직선에 잘 맞는지 결정하기 위해 노력하기 때문에 이에 대해 수정될 것이다. 이 모듈에 대한 Pearson 상관 관계 코드는 두 개의 숫자 목록을 가져가고 그 상관 관계 점수를 반환한다.
from math import sqrt
def pearson(v1,v2):
# Simple sums
sum1=sum(v1)
sum2=sum(v2)
# Sums of the squares
sum1Sq=sum([pow(v,2) for v in v1])
sum2Sq=sum([pow(v,2) for v in v2])
# Sum of the products
pSum=sum([v1[i]*v2[i] for i in range(len(v1))])
# Calculate r (Pearson score)
num=pSum-(sum1*sum2/len(v1))
den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))
if den==0: return 0
return 1.0-num/den
두 항목이 완벽하게 일치할 때는 Pearson 상관 관계가 1.0이고 관계가 전혀 없을 때는 0.0에 가깝다는 점을 기억하십시오. 코드의 최종 라인은 Pearson 상관 관계를 1.0 빼서 더 비슷한 항목들 사이에 더 작은 거리를 만든다.
계층적 클러스터링 알고리즘의 각 클러스터는 두 개의 분기가 있는 트리의 포인트 또는 데이터 집합의 실제 행과 연결된 엔드포인트(이 경우 블로그). 또한 각 클러스터에는 엔드포인트의 행 데이터 또는 다른 노드 유형에 대한 두 가지 분기의 병합된 데이터인 해당 위치에 대한 데이터도 포함되어 있다. 이러한 모든 속성을 가진 바이클러스터라는 클래스를 만들 수 있으며, 계층적 트리를 나타내는 데 사용할 수 있다.
class bicluster:
def __init_ _(self,vec,left=None,right=None,distance=0.0,id=None):
self.left=left
self.right=right
self.vec=vec
self.id=id
self.distance=distance
계층적 클러스터링을 위한 알고리즘은 단지 원래 항목인 클러스터 그룹을 만드는 것으로 시작한다. 함수의 주 루프는 가능한 모든 쌍을 시도하고 상관 관계를 계산함으로써 두 개의 가장 좋은 일치점을 검색한다. 최상의 클러스터 쌍은 단일 클러스터로 병합된다. 이 새 클러스터의 데이터는 두 이전 클러스터의 평균 데이터 입니다. 이 프로세스는 클러스터가 하나만 남을 때까지 반복된다. 이 모든 계산을 하는 데는 시간이 많이 소요될 수 있으므로, 쌍의 항목 중 하나가 다른 클러스터로 병합될 때까지 반복해서 계산해야 하므로 각 쌍의 상관 관계 결과를 저장하는 것이 좋다.
def hcluster(rows,distance=pearson):
distances={}
currentclustid=-1
# Clusters are initially just the rows
clust=[bicluster(rows[i],id=i) for i in range(len(rows))]
while len(clust)>1:
lowestpair=(0,1)
closest=distance(clust[0].vec,clust[1].vec)
# loop through every pair looking for the smallest distance
for i in range(len(clust)):
for j in range(i+1,len(clust)):
# distances is the cache of distance calculations
if (clust[i].id,clust[j].id) not in distances:
distances[(clust[i].id,clust[j].id)]=distance(clust[i].vec,clust[j].vec)
d=distances[(clust[i].id,clust[j].id)]
if d<closest:
closest=d
lowestpair=(i,j)
# calculate the average of the two clusters
mergevec=[
(clust[lowestpair[0]].vec[i]+clust[lowestpair[1]].vec[i])/2.0
for i in range(len(clust[0].vec))]
# create the new cluster
newcluster=bicluster(mergevec,left=clust[lowestpair[0]],
right=clust[lowestpair[1]],
distance=closest,id=currentclustid)
# cluster ids that weren't in the original set are negative
currentclustid-=1
del clust[lowestpair[1]]
del clust[lowestpair[0]]
clust.append(newcluster)
return clust[0]
각 클러스터는 병합된 두 클러스터를 참조하기 때문에 이 기능으로 반환된 최종 클러스터를 반복적으로 검색하여 모든 클러스터와 해당 엔드 노드를 재생성할 수 있다.
계층적 클러스터링을 실행하려면 Python 세션을 시작하고 파일을 로드한 다음 데이터에 대해 hcluster를 호출하자.
python
>> import clusters
>> blognames,words,data=clusters.readfile('blogdata.txt')
>> clust=clusters.hcluster(data)
이 작업은 실행하는데 몇 분 정도 걸릴 수 있다. 거리를 저장하면 속도가 현저히 증가하지만, 알고리즘은 여전히 모든 블로그 쌍 간의 상관 관계를 계산할 필요가 있다. 이 과정은 외부 라이브러리를 사용하여 거리를 계산함으로써 더 빨리 만들 수 있다. 결과를 보려면 클러스터링 트리를 반복적으로 가로지르는 간단한 기능을 만들어 파일 시스템 계층처럼 인쇄하면 된다.
# indent to make a hierarchy layout
for i in range(n): print ' ',
if clust.id<0:
# negative id means that this is branch
print '-'
else:
# positive id means that this is an endpoint
if labels==None: print clust.id
else: print labels[clust.id]
# now print the right and left branches
if clust.left!=None: printclust(clust.left,labels=labels,n=n+1)
if clust.right!=None: printclust(clust.right,labels=labels,n=n+1)
이것의 출력은 그다지 화려해 보이지 않고 블로그 목록과 같은 대규모 데이터 집합으로 읽기가 조금 어렵지만 클러스터링이 제대로 작동하는지 전체적으로 잘 알 수 있다. 다음 섹션에서는 읽기 쉽고 각 클러스터의 전체 확산을 보여 주기 위해 스케일로 그려지는 그래픽 버전을 만드는 방법에 대해 살펴보기로 한다.
>> reload(clusters)
>> clusters.printclust(clust,labels=blognames)
출력목록은 100개의 블로그를 모두 포함할 예정이며, 따라서 상당히 길어질 것이다. 이 데이터 집합을 실행할 때 찾은 클러스터의 예:
세트의 원본 항목이 표시된다. 대시는 두 개 이상의 병합된 항목의 클러스터를 나타낸다. 여기서 그룹을 찾는 좋은 예를 볼 수 있다. 가장 인기 있는 피드에는 검색 관련 블로그가 이렇게 많이 있다는 것도 흥미롭다. 여러 개의 정치 블로그, 기술 블로그, 블로그를 살펴보면서 블로그에 관한 블로그도 발견할 수 있어야 한다.
몇 가지 이상 현상도 발견될 것이다. 이 작가들은 같은 주제에 대해 쓰지 않았을 수도 있지만, 클러스터링 알고리즘은 그들의 워드 주파수가 서로 관련이 있다고 말한다. 이것은 그들의 글쓰기 스타일을 반영하는 것일 수도 있고 단순히 데이터가 다운로드된 날을 기준으로 한 우연의 일치일 수도 있다.
