계층적 클러스터링은 가장 유사한 두 그룹을 지속적으로 병합함으로써 그룹의 계층을 형성한다. 이러한 각 그룹은 개별 블로그에서 단일 항목으로 시작한다. 각 반복에서 이 방법은 모든 그룹 쌍 사이의 거리를 계산하고, 가장 가까운 그룹들은 함께 병합되어 새로운 그룹을 형성한다. 이것은 한 그룹만 있을 때까지 반복된다. 그림 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개의 블로그를 모두 포함할 예정이며, 따라서 상당히 길어질 것이다. 이 데이터 집합을 실행할 때 찾은 클러스터의 예:


세트의 원본 항목이 표시된다. 대시는 두 개 이상의 병합된 항목의 클러스터를 나타낸다. 여기서 그룹을 찾는 좋은 예를 볼 수 있다. 가장 인기 있는 피드에는 검색 관련 블로그가 이렇게 많이 있다는 것도 흥미롭다. 여러 개의 정치 블로그, 기술 블로그, 블로그를 살펴보면서 블로그에 관한 블로그도 발견할 수 있어야 한다.


몇 가지 이상 현상도 발견될 것이다. 이 작가들은 같은 주제에 대해 쓰지 않았을 수도 있지만, 클러스터링 알고리즘은 그들의 워드 주파수가 서로 관련이 있다고 말한다. 이것은 그들의 글쓰기 스타일을 반영하는 것일 수도 있고 단순히 데이터가 다운로드된 날을 기준으로 한 우연의 일치일 수도 있다.

  • 네이버 블로그 공유하기
  • 네이버 밴드에 공유하기
  • 트위터 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기