[Programming Collective Intelligence] - 집단지성 프로그래밍 3장 03 계층적 군집화

# -*- coding: utf-8 -*-
from myutil import consolePrintWithLineNumber as c
'''
Created on 2015. 8. 24.

@author: Administrator
'''

# 3-3 계층적 군집화

# 60p

# 3-2의 결과값 로드하기(blogdata1.txt)
'''
  file 구조가 다음과 같다면
   --------------
  □■■■■■■■■■■■■■■
  □■■■■■■■■■■■■■■
  □■■■■■■■■■■■■■■
  □■■■■■■■■■■■■■■
  □■■■■■■■■■■■■■■
  □■■■■■■■■■■■■■■
  에서
  
  rownames : --------------
  colnames : □□□□□□□□□□□□□
  data :
  ■■■■■■■■■■■■■■
  ■■■■■■■■■■■■■■
  ■■■■■■■■■■■■■■
  ■■■■■■■■■■■■■■
  ■■■■■■■■■■■■■■

'''
def readfile(filename):
  lines = [line for line in open(filename, 'r', encoding='UTF-8')]
  
  colnames = lines[0].strip().split('\t')[1:]
  rownames = []
  data = []
  for line in lines[1:]:
    p = line.strip().split('\t')
    rownames.append(p[0])
    data.append([float(x) for x in p[1:]])
  return rownames, colnames, data

# 피어슨 상관계수 공식 
from math import sqrt
def pearson(v1, v2):
  sum1 = sum(v1)
  sum2 = sum(v2)
  
  sum1Sq = sum([pow(v, 2) for v in v1])
  sum2Sq = sum([pow(v, 2) for v in v2])  
  
  pSum = sum([v1[i] * v2[i] for i in range(len(v1))])
  
  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

# 트리 노드를 나타내는 클래스 모형
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(data, distance=pearson):
  distances = {}
  currentclustid = -1

  # 각 가로줄을 클러스터 배열로 지정
  clust = [bicluster(data[i], id=i) for i in range(len(data))]

  while len(clust) > 1:
    lowestpair = (0, 1)    # 두 클러스터간의 거리 정의 디폴트...
    closest = distance(clust[0].vec, clust[1].vec)    # 두 클러스터간의 거리 정의 디폴트... 

    # 가장 작은 거리를 갖는 쌍을 찾아라!!! - 두 항목을 비교하는 방법으로 버블정렬 알고리즘을 이용한다.  
    # 버블정렬 참고 : http://blog.naver.com/vvvb78/220349103670
    '''
      len(clust) 가 10이라면
      i  j
      0  1
      0  2
      0  3
      0  4
      .....
      0  9
      1  2
      1  3
      1  4
      .....
      1  8
      1  9
      2  3
      .....
      .....
      8  9
    '''
    for i in range(len(clust)):
      for j in range(i + 1, len(clust)):
        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)]    # in distances 인 경우

        if d < closest:
          closest = d
          lowestpair = (i, j)

    # 가장 작은 거리를 갖는 쌍을 찾아서 군집을 할거니까... 그 쌍의 평균을 찾아서 중심점을 갱신함
    mergevec = [(clust[lowestpair[0]].vec[i] + clust[lowestpair[1]].vec[i]) / 2.0 
                  for i in range(len(clust[0].vec))]

    # 새로운 군집 생성
    newcluster = bicluster(mergevec, left=clust[lowestpair[0]], right=clust[lowestpair[1]], distance=closest, id=currentclustid)

    currentclustid -= 1    # currentclustid가 음수로 가장 큰 값이 가장 마지막으로 남는 ROOT 가 되는 셈이다.
    del clust[lowestpair[1]]    # 리스트 삭제
    del clust[lowestpair[0]]    # 리스트 삭제
    clust.append(newcluster)    # 리스트 추가

  return clust[0]    # 결국 하나의 클러스터만 남는다. 클러스터의 left, right를 조사하면 또 다른 클러스터(자식 노드)를 가지고 있음을 알 수 있다. 재귀적으로.... 

# clust를 콘솔에 프린트(재귀적으로...-_-)
def printclust(clust, labels=None, n=0):
  for i in range(n): 
    print(' ', end='')    # 파이썬 3.4에서 print 이후 줄바꿈하지 않을려면 end를 지정
  if clust.id < 0:
    print('-')
  else:
    if labels == None:
      print(clust.id)
    else:
      print(labels[clust.id])

  if clust.left != None: 
    printclust(clust.left, labels=labels, n=n + 1)
  if clust.right != None: 
    printclust(clust.right, labels=labels, n=n + 1)

blognames, words, data = readfile('blogdata1.txt')
clust = hcluster(data)
# printclust(clust, labels=blognames)

# 클러스터 확인(음수는 새로 생성된 군집. 0이상은 최하위노드들. id가 음수에 가까워질수록 distance가 커진다.)
c(clust.id, clust.distance)
c(clust.left.id, clust.left.distance)
c(clust.right.id, clust.right.distance)
c(clust.left.left.id, clust.left.left.distance)
c(clust.left.right.id, clust.left.right.distance)
c(clust.right.left.id, clust.right.left.distance)
c(clust.right.right.id, clust.right.right.distance)
c(clust.right.right.left.id, clust.right.right.left.distance)
c(clust.right.right.right.id, clust.right.right.right.distance)
c(blognames)

# 64p
# 3-4 계통도 출력
'''
  PIL 을 사용해야 하는데 파이썬 2.x 버전까지밖에 없다. 헉... 
  > pip install pillow 를 사용하자

  좌표 기준
  draw.line(x1, y1, x2, y2)

  ┌─────> x
  │┌─────────┐
  ││         │
  ↓│         │
  y│         │
   └─────────┘
   
'''

from PIL import Image, ImageDraw

def getheight(clust):
  if clust.left == None and clust.right == None: return 1    # 최하위 노드 하나당 1의 높이를 가진다.

  return getheight(clust.left) + getheight(clust.right)

def getdepth(clust):
  if clust.left == None and clust.right == None: return 0    # 최하위 노드

  return max(getdepth(clust.left), getdepth(clust.right)) + clust.distance    # distance값 : 최하위노드는 0, 새로 생성된 군집의 경우 1 < x < 1.3 정도이다.. 

# 재귀적으로 처리...
def drawnode(draw, clust, x, y, scaling, labels):
  if clust.id < 0:
    h1 = getheight(clust.left) * 20
    h2 = getheight(clust.right) * 20
    top = y - (h1 + h2) / 2
    bottom = y + (h1 + h2) / 2

    ll = clust.distance * scaling
    draw.line((x, top + h1 / 2, x, bottom - h2 / 2), fill=(0, 255, 0))    # green - 왼쪽과 오른쪽을 분기해주는 수직선    
    draw.line((x, top + h1 / 2, x + ll, top + h1 / 2), fill=(255, 0, 0))    # red - 오른쪽 선
    draw.line((x, bottom - h2 / 2, x + ll, bottom - h2 / 2), fill=(0, 255, 255))    # sky - 왼쪽선        

    drawnode(draw, clust.left, x + ll, top + h1 / 2, scaling, labels)    # 왼쪽 클러스터 재귀
    drawnode(draw, clust.right, x + ll, bottom - h2 / 2, scaling, labels)    # 오른쪽 클러스터 재귀
  else:   
    draw.text((x + 5, y - 7), labels[clust.id], (0, 0, 0))    # black - 최하위 노드는 텍스트만 출력
    
def drawdendrogram(clust, labels, jpeg='clusters.jpg'):
  h = getheight(clust) * 20
  w = 1000
  depth = getdepth(clust)

  scaling = float(w - 150) / depth
  
  img = Image.new('RGB', (w, h), (200, 200, 200))    # gray
  draw = ImageDraw.Draw(img)

  draw.line((0, h / 2, 10, h / 2), fill=(255, 255, 0))    # yellow - 최상단 ROOT 1회

  drawnode(draw, clust, 10, (h / 2), scaling, labels)
  img.save(jpeg, 'JPEG')

# 왼쪽, 오른쪽으로 나눠질때 수평선이 짧은수록 비슷한 항목이다.(자세히 보면 (Signal, Guy)가 (Search, Google)보다  좀더 짧다...-_-;;;;)
drawdendrogram(clust, blognames, jpeg='blogclust3.jpg')

# 3-5 세로줄 군집화 (행렬 회전)
# 68p
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

# rdata = rotatematrix(data)
# wordclust = hcluster(rdata)
# drawdendrogram(wordclust, words, jpeg='wordclust3.jpg')

154 >  (-4, 1.2753446233570573)
155 >  (-2, 1.0624362008490937)
156 >  (-3, 1.1490411065687218)
157 >  (1, 0.0)
158 >  (4, 0.0)
159 >  (0, 0.0)
160 >  (-1, 1.0526604354970446)
161 >  (2, 0.0)
162 >  (3, 0.0)
163 >  ['Eschaton', 'Search Engine Watch', 'Signal v. Noise', 'Guy Kawasaki', 'Google Blogoscoped']

04 계통도 출력

 

 

저자의 원본 소스blogdata.txt를 분석했을때 결과

 

 

 

 

05 세로줄 군집화

(소스 : blogdata.txt 위와 동일)