Discovering Groups

(정리 중입니다.)

 

단어 벡터

• 구성방법: 블로그 별로 어떤 낱말을 몇 번 썼는지
• 보기 데이터: http://kiwitobes.com/clusters/blogdata.txt

 

군집 방법 알고리즘

• 계층 군집 (Hierarchical Clustering)
• K-평균 군집(K-Means Clustering)

 

2장의 유사도 함수를 이용하여 유사도를 구한다.

• 평론가, 영화, 점수 --> 블로그, 낱말, 횟수
• 평론가의 유사도가 블로그의 유사도가 된다.

• 코드

  1. 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
  2.   return 1.0-num/den

 

계층 군집

• 각 아이템간의 유사도를 구해 가장 가까운 것 두 개를 묶는다.
• 묶은 아이템 둘은 그 평균값을 둘의 대표값으로 취하여 다시 앞 과정을 반복한다.
• 앞 두 과정을 전체가 하나로 묶일 때까지 반복한다.

• 코드

  1. 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
  2. def hcluster(rows,distance=pearson):
       distances={}
       currentclustid=-1
  3.   # Clusters are initially just the rows
       clust=[bicluster(rows[i],id=i) for i in range(len(rows))]
  4.   while len(clust)>1:
         lowestpair=(0,1)
         closest=distance(clust[0].vec,clust[1].vec)
  5.     # 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)
  6.         d=distances[(clust[i].id,clust[j].id)]
  7.         if d<closest:
               closest=d
               lowestpair=(i,j)
  8.     # 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))]
  9.     # create the new cluster
         newcluster=bicluster(mergevec,left=clust[lowestpair[0]],
                              right=clust[lowestpair[1]],
                              distance=closest,id=currentclustid)
  10.     # cluster ids that weren't in the original set are negative
          currentclustid-=1
          del clust[lowestpair[1]]
          del clust[lowestpair[0]]
          clust.append(newcluster)
  11.   return clust[0]
• 이 과정을 트리 형태로 표시할 수 있는데 이 그림을 덴드로그램(dendrogram)이라고 한다.
• (((a, b), c), (d, e)) 편의상 덴드로그램을 이렇게 괄호로 표시했을 때, a, b간의 유사도가 d, e간의 유사도보다 큰 것을 알 수 있다.
• 뭉게구름 형태로 데이터를 묶어 보기가 힘들고, 연산 시간이 큰 편이다.

 

1998 년 Eison은  상관계수를 유전자 사이의 유사도로 정의한 “Hierarchical clustering”방법을 사용하였다. 또 clustering결과를 dendrogram으로 보여주었는데, 유전자의 재배치를 통해 발현정도가 유사한 유전자들을 가까운 거리 에 위치시켰다

- http://expressome.org/index.php/Hierarchical_clustering

 

컬럼 군집(Column Clustering)

• 행과 열을 바꿔서 클러스터링

• 코드

  1. def rotatematrix(data):
       newdata=[]
       for i in range(len(data[0])):
         newrow=[data[j][i] for j in range(len(data))]
         newdata.append(newrow)
       return newdata
• 이전 결과는 (블로그, 낱말)쌍을 클러스터링해서 비슷한 블로그를 모았지만, 행과 열을 바꾸면 낱말의 묶음. 즉 '함께 쓰는 낱말의 묶음'이 나옴

 

K-평균 군집

• 계층 군집과 다르게 몇 개로 나눌지 결정하고 시작한다.
• 2개로 나누기로 했다면 임의의 위치에 점 두 개(seed point)를 찍는다.
• 각 점에 가까운 아이템을 묶는다.
• 각 그룹의 중심점을 계산해서 처음에 찍었던 점을 이동한다.
• 앞 두 단계를 점이 이동하지 않을 때까지 반복한다.

• 코드

  1. def kcluster(rows,distance=pearson,k=4):
       # Determine the minimum and maximum values for each point
       ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows]))
       for i in range(len(rows[0]))]
  2.   # Create k randomly placed centroids
       clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0]
       for i in range(len(rows[0]))] for j in range(k)]
      
       lastmatches=None
       for t in range(100):
         print 'Iteration %d' % t
         bestmatches=[[] for i in range(k)]
        
         # Find which centroid is the closest for each row
         for j in range(len(rows)):
           row=rows[j]
           bestmatch=0
           for i in range(k):
             d=distance(clusters[i],row)
             if d<distance(clusters[bestmatch],row): bestmatch=i
           bestmatches[bestmatch].append(j)
  3.     # If the results are the same as last time, this is complete
         if bestmatches==lastmatches: break
         lastmatches=bestmatches
        
         # Move the centroids to the average of their members
         for i in range(k):
           avgs=[0.0]*len(rows[0])
           if len(bestmatches[i])>0:
             for rowid in bestmatches[i]:
               for m in range(len(rows[rowid])):
                 avgs[m]+=rows[rowid][m]
             for j in range(len(avgs)):
               avgs[j]/=len(bestmatches[i])
             clusters[i]=avgs
          
       return bestmatches
• 초기 시작점 선정 방법은 자유! 하지만 그 위치에 따라 결과에 차이가 있을 수 있다.
• 온라인 데모: http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html

 

데이터를 2차원으로 보기

• 각 아이템을 임의의 위치에 표시한다.
• 각 아이템의 실제 거리를 계산한다.
• 각 아이템을 실제 거리에 맞도록 조금씩 움직인다. 더 이상 움직임이 없을 때까지 이 과정을 반복한다.