[Programming Collective Intelligence] - 집단지성 프로그래밍 3장 06 K평균 군집화

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

@author: Administrator
'''

# 이전 절 사전 작업...
from ch03_2 import pearson, readfile, hcluster, drawdendrogram
blognames, words, data = readfile('blogdata.txt')

# 3-6 K평균 군집화
# kNN(k Nearest Neighbors) - 머신러닝 인 액션

import random
def kcluster(rows, distance=pearson, k=4):
  # 각 단어가 출현한 최소,최대값을 구한다.
  ranges = [(min([row[i] for row in rows]), max([row[i] for row in rows])) for i in range(len(rows[0]))]
  # 임의의 중심점 k개 생성 - 단, 중심점 1개가 단어 706개의 속성을 포함하고 있다.706차원이란 뜻. 모든 단어를 포함하되, 최소값과 최대값 사이의 임의의 지점 
  # random.random() : 1보다 작은 실수를 반환하는 듯.
  centroid = [[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
  # 100번 루프...그전에 끝나기를 바라는 수밖에...
  for t in range(100):
    c('Iteration %d' % t)
    kresult = [[] for i in range(k)]    # k개의 빈배열을 가진 배열 반환 [[], [], []] 이곳에 군집에 해당하는 데이터(블로그의 index)를 추가한다.
    
    # 각 가로줄별로 가장 근접한 중심점을 찾음(k개 중에) 
    for j in range(len(rows)):
      row = rows[j]
      bestmatch = 0
      # 해당 row 에 가장 근접한 bestmatch(k순번)을 찾는다.
      for i in range(k):
        d = distance(centroid[i], row)
        if d < distance(centroid[bestmatch], row): 
          bestmatch = i
      kresult[bestmatch].append(j)

    # 이전과 결과가 같다면 완료..
    if kresult == lastmatches: break
    
    lastmatches = kresult
    
    # 중심점을 멤버들의 평균으로 이동함
    for i in range(k):
      avgs = [0.0] * len(rows[0])    # [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0] 같은 모습
      if len(kresult[i]) > 0:
        # k 중심점에 속한 데이터들을 다시 꺼내서 평균을 낸다.
        for rowid in kresult[i]:
          for m in range(len(rows[rowid])):
            avgs[m] += rows[rowid][m]
        for j in range(len(avgs)):    # 여기서 for를 왜 돌리지? 평균 계산은 한번만 하면 되지 않나? > 평균이 706개(모든속성)가 필요하다.
          avgs[j] /= len(kresult[i])
        centroid[i] = avgs
      
  return kresult

# kclust = kcluster(data, k=5)
# c([blognames[r] for r in kclust[0]])
# c([blognames[r] for r in kclust[1]])

# 3-7 선호도 군집
# 72p

# www.zebo.com 사이트는 접속불가
# 데이터 얻기와 준비, 제보 결과 스크래핑 생략

'''
  0과 1로된 데이터는 피어슨 상관계수보다는 타니모토 계수가 더 적당하다.
  우선 != 0 보다는 == 1이 더 직관적이다. > 할려고 했는데, 군집화하면서 데이터가 0 또는 1이 아니라 0.5, 0.25 등등 변한다.
  
  책의 타니모터 공식과 인터넷의 공식과 조금 다르다.
  인터넷의 타니모토는 0,1이 아닐뿐더러 집합의 개념이라서 순서에 영향을 받지 않는다.
  그런데 책의 타니모터는 0,1로 구성되어있고, 순서가 중요하다.(교집합 시) > 0과 1로만 구분하기 때문에 순서가 중요하다. 순서를 무시하면, 다 0,1이기 때문에 다 중복-_-;;;
'''
def tanimoto(v1, v2):
  c1, c2, shr = 0, 0, 0
  
  # v1과  v2의 개수가 동일하다는 전제하에
  for i in range(len(v1)):
    if v1[i] != 0: c1 += 1    # in v1
    if v2[i] != 0: c2 += 1    # in v2
    if v1[i] != 0 and v2[i] != 0: shr += 1    # in both
  return 1.0 - (float(shr) / (c1 + c2 - shr))

# 75p
wants, people, data1 = readfile('zebo.txt')
clust = hcluster(data1, distance=tanimoto)
# drawdendrogram(clust, wants, jpeg='zebo1.jpg')

# 3-8 2차원으로 데이터 보기
'''
  사용된 수학공식이 그리 간단하지는 않다...뭘까?? -- 이거 혹시...선형회귀?? 그런거 아니겠지??? 기울기나오는게 왠지...-_-;;
  결과가 그리 신통치 않다-_-;; 4절 계통도 출력한 것과 비교했을때 연관성이 없다...???
    그리 좋아보이는 방법은 아닌듯 하다. 더 좋은 방법은 없을까????
    다차원의 데이터를 2차원으로 쑤셔넣는 방법은 분명 한계가 있고, 오차가 생긴다. 그 오차를 얼마나 줄일 수 있는지가 관건...
     빅뱅처럼.. 모두 다 한곳에서 시작해서 팽창하는 건 어떨까?
      또는... 자리를 찾아가는 과정을 애니메이션으로 보는 것도 좋은 시각적인 방법인듯
'''

from math import sqrt
def scaledown(data, distance=pearson, rate=0.01):
  n = len(data)

  # 항목간의 실제거리 구하기
  '''
  realdist 는 다음의 2차 배열로 이루어져 있다.(0 < ? < 1.1 정도?)
     A B C D E F G H I J K
  A[[0 ? ? ? ? ? ? ? ? ? ?]
  B [? 0 ? ? ? ? ? ? ? ? ?]
  C [? ? 0 ? ? ? ? ? ? ? ?]
  D [? ? ? 0 ? ? ? ? ? ? ?]
  E [? ? ? ? 0 ? ? ? ? ? ?]
  F [? ? ? ? ? 0 ? ? ? ? ?]
  G [? ? ? ? ? ? 0 ? ? ? ?]
  H [? ? ? ? ? ? ? 0 ? ? ?]
  I [? ? ? ? ? ? ? ? 0 ? ?]
  J [? ? ? ? ? ? ? ? ? 0 ?]
  K [? ? ? ? ? ? ? ? ? ? 0]]
  '''
  realdist = [[distance(data[i], data[j]) for j in range(n)] for i in range(0, n)]
  # 2D 내에서 랜덤의 시작점 설정
  loc = [[random.random(), random.random()] for i in range(n)]
  '''
  loc는 (0 <= ? < 1)
  A [[? ?]
  B  [? ?]
  C  [? ?]
  D  [? ?]
  E  [? ?]
  F  [? ?]
  G  [? ?]]
  '''
  fakedist = [[0.0 for j in range(n)] for i in range(n)]
  '''
  fakedist는
     A B C D E F G H I J K
  A[[0 0 0 0 0 0 0 0 0 0 0]
  B [0 0 0 0 0 0 0 0 0 0 0]
  C [0 0 0 0 0 0 0 0 0 0 0]
  D [0 0 0 0 0 0 0 0 0 0 0]
  E [0 0 0 0 0 0 0 0 0 0 0]
  F [0 0 0 0 0 0 0 0 0 0 0]
  G [0 0 0 0 0 0 0 0 0 0 0]
  H [0 0 0 0 0 0 0 0 0 0 0]
  I [0 0 0 0 0 0 0 0 0 0 0]
  J [0 0 0 0 0 0 0 0 0 0 0]
  K [0 0 0 0 0 0 0 0 0 0 0]]
  '''
  
  lasterror = None
  for m in range(0, 1000):
    
    # 투영된 거리(시작점간의 거리)
    for i in range(n):
      for j in range(n):
        fakedist[i][j] = sqrt(sum([pow(loc[i][x] - loc[j][x], 2) for x in range(len(loc[i]))]))    # len(loc[i]) = 2
    grad = [[0.0, 0.0] for i in range(n)]
    
    '''
    grad는 기울기
      A [[0 0]
      B  [0 0]
      C  [0 0]
      D  [0 0]
      E  [0 0]
      F  [0 0]
      G  [0 0]]
    '''
    totalerror = 0
    for k in range(n):    # 기준
      for j in range(n):    # 비교대상
        if j == k: continue    # 같은 항목끼리는 비교할 필요 없으니
        '''    
              실제 거리와 중심점의 차이(오차)
          errorterm > 0은 두점사이의 거리가 실제보다 크다. ==> 가까워져야 한다.
          errorterm = 0 동일
          errorterm < 0은 두점사이의 거리가 실제보다 작다. ==> 멀리 떨어져야 한다.
        ''' 
        errorterm = (fakedist[j][k] - realdist[j][k]) / realdist[j][k]    
        
        grad[k][0] += ((loc[k][0] - loc[j][0]) / fakedist[j][k]) * errorterm    # fakedist[j][k] 나 fakedist[k][j] 나 같다. 대칭행렬이다. 데이터 낭비다-_-;;
        grad[k][1] += ((loc[k][1] - loc[j][1]) / fakedist[j][k]) * errorterm

        totalerror += abs(errorterm)
    c(totalerror)    # 오류값이 점점 작아짐을 볼 수 있다.

    if lasterror and lasterror < totalerror:
      break
    lasterror = totalerror
    
    '''
        이동시키는 건데 왜 마이너스(-)일까?
      grad > 0 현재 내 좌표값이 작아져야 errorterm 을 만족할 수 있다.
      grad < 0 현재 내 좌표값이 커야한다.
      errorterm  (나 - 상대)  ==> grad  ==>  결과
        (+)        (+)          (+)      내 좌표가 작아져야 한다.(두점 사이의 거리가 실제보다 크다., 내 좌표가 상대방좌표보다 크기 때문에 내 좌표가 작아져야 상대방과 가까워질 수 있다.)
        (+)        (-)          (-)      내 좌표가 커져야한다.(두점 사이의 거리가 실제보다 크다, 내 좌표가 상대방좌표보다 작기 때문에 내 좌표가 커져야 상대방과 가까워질 수 있다.)
        (-)        (+)          (-)      내 좌표가 커져야한다.(두점 사이의 거리가 실제보다 작다, 내 좌표가 상대방좌표보다 크기 때문에 내 좌표가 커져야 상대방과 멀어질 수 있다.)
        (-)        (-)          (+)      내 좌표가 작아져야 한다.(두점 사이의 거리가 실제보다 작다., 내 좌표가 상대방좌표보다 작기 때문에 내 좌표가 작아져야 상대방과 멀어질 수 있다.)
    '''
    for k in range(n):
      loc[k][0] -= rate * grad[k][0]
      loc[k][1] -= rate * grad[k][1]

  return loc

from PIL import Image, ImageDraw
def draw2d(data, labels, jpeg='mds2d.jpg'):
  img = Image.new('RGB', (2000, 2000), (255, 255, 255))
  draw = ImageDraw.Draw(img)
  for i in range(len(data)):
    x = (data[i][0] + 0.5) * 1000
    y = (data[i][1] + 0.5) * 1000
    draw.text((x, y), labels[i], (0, 0, 0))
    draw.line((x - 5, y - 5, x + 5, y + 5), fill=(255, 0, 0), width=5)    # 정확한 지점을 표시하기 위해
    draw.line((x + 5, y - 5, x - 5, y + 5), fill=(255, 0, 0), width=5)
  img.save(jpeg, 'JPEG')  

coords = scaledown(data)
draw2d(coords, blognames, jpeg='blogs2d3.jpg')

188 >  4121.873597213046
188 >  3527.591729520054
188 >  3458.56698340106
188 >  3420.5753470845157
188 >  3386.117598961437
188 >  3349.3402380599764
188 >  3314.7706845391162
188 >  3286.9539955820605
188 >  3265.7123638564453
188 >  3247.9648382862897
188 >  3231.3422639954265
188 >  3215.029574750167
188 >  3201.4291006522035
188 >  3188.4369371568264
188 >  3178.7735581496
188 >  3171.6052024640467
188 >  3165.529939646259
188 >  3160.115028255854
188 >  3155.378904106978
188 >  3151.8806880278753
188 >  3148.9512042787637
188 >  3146.5890704524395
188 >  3144.3693057698924
188 >  3141.866858875396
188 >  3139.414879529258
188 >  3136.702858851971
188 >  3133.7800657355956
188 >  3130.706541819401
188 >  3127.7024706090733
188 >  3124.7854981348323
188 >  3122.296076882132
188 >  3120.153154514913
188 >  3118.3955879134364
188 >  3116.737649017945
188 >  3114.685994402978
188 >  3112.3449794950097
188 >  3109.7316182091563
188 >  3107.232114610093
188 >  3105.183714372845
188 >  3103.2758205072328
188 >  3101.255900517773
188 >  3099.3346697129678
188 >  3097.390519131204
188 >  3095.604114304122
188 >  3093.874755422627
188 >  3092.4018424335704
188 >  3090.802934584408
188 >  3088.9206217916562
188 >  3086.723553409899
188 >  3084.3089349077923
188 >  3082.0085108309713
188 >  3079.843430593622
188 >  3077.804308445605
188 >  3075.823237003265
188 >  3074.1569861774433
188 >  3072.5830490954254
188 >  3070.977318054793
188 >  3069.3578148721685
188 >  3067.9405767178405
188 >  3066.5482719629554
188 >  3065.1741022141764
188 >  3063.982207456531
188 >  3062.872197545028
188 >  3061.714669441097
188 >  3060.341866182004
188 >  3058.8705186683524
188 >  3057.4999822277387
188 >  3055.9928919789013
188 >  3054.4809523948015
188 >  3053.1050901347007
188 >  3051.6022429428294
188 >  3050.092295289536
188 >  3048.5037066411396
188 >  3047.1908340219857
188 >  3046.022798830574
188 >  3045.0009973835436
188 >  3044.091949999352
188 >  3043.2004116861326
188 >  3042.466551333877
188 >  3041.8214451587205
188 >  3041.178568450084
188 >  3040.8054437787355
188 >  3040.6585728956134
188 >  3040.5497120032346
188 >  3040.45771357786
188 >  3040.527574529178

75p 타니모토 결과(zebo.txt)

 

 

77p 2차원으로 데이터 보기 결과(blogdata.txt 결과)

> 정확도는 나름...

 

 

 

트리에 나와있는 결과물과 비교해가며 군집을 만들어 보았다. (그림판으로 편집^^)

 

 

 

79p scaledown 함수 수식 - 랜덤으로 생성한 중심에서 실제위치로 이동 (주변 다른 점들과의 비교를 통해, 움직일 변화량을 매회 구해서 이동한다.)

제대로 표현한것이 맞나 모르겠다.

점들의 이동이 마치 힘겨루기 하는 것 같다.

 

실제거리차(이상적인 거리 - 다차원 속성으로 계산한...)