Tech Tips

  1. 要素技術
  2. 442 view

ベーシックな クラスタリング

学習の仕方

  • 教師あり学習
    入力と期待される出力のデータセットを用いて学習する。
  • 教師なし学習
    入力データセットのみを用いて自動的に構造を学習する。

データセットの準備

ブログの クラスタリング をそのブログの単語頻度を用いて行う。
URLのリストを用意しておき、それをクロールしてブログのタイトルと単語頻度のリストを生成する。
URLのリストはここを利用した。 スクリプトは以下を用いる。 
#!/usr/bin/python

import feedparser
import re

#
# Count words in rss feed
#
def getwordcounts(url):
    d = feedparser.parse(url)
    wc = {}

    for e in d.entries:
        if 'summary' in e: summary=e.summary
        else: summary=e.description

        words = getwords(e.title + ' ' + summary)
        for word in words:
            wc.setdefault(word,0)
            wc[word] += 1
    return d.feed.title,wc

#
# Delete unuseful character and split words
#
def getwords(html):
    txt = re.compile(r'<[^>]+>').sub('',html)
    words = re.compile(r'[^A-Z^a-z]+').split(txt)
    return [word.lower() for word in words if word != '']

if __name__ == '__main__':
    apcount = {}
    wordcounts = {}
    feedcount = 0
    feedlist = [line for line in file('feedlist.txt')]
    for feedurl in feedlist:
        try:
            title,wc = getwordcounts(feedurl)
            wordcounts[title] = wc
            for word,count in wc.items():
                apcount.setdefault(word,0)
                if count > 1:
                    apcount[word] += 1
        except:
            print 'Failed to parse feed %s' % feedurl

        feedcount += 1
        print 'finish %d/%d' % (feedcount, len(feedlist))

    wordlist = []
    for w,bc in apcount.items():
        frac = float(bc)/len(feedlist)
        if frac > 0.1 and frac < 0.5: wordlist.append(w)

    out = file('blogdata.txt', 'w')
    out.write('Blog')
    for word in wordlist: out.write('\t%s' % word)
    out.write('\n')
    for blog,wc in wordcounts.items():
        out.write(blog)
        for word in wordlist:
            if word in wc: out.write('\t%d' % wc[word])
            else: out.write('\t0')
        out.write('\n')
出力の一部は以下のようになる。
Blogkidsmusicwantwrong
techSchneier on Security0010
The Superficial – Because You’re Ugly0011
Copyblogger0040

階層的 クラスタリング

階層的クラスタリングは似ているグループをまとめるという作業を段階的に行うことによって、
階層構造を見つけ出すアルゴリズムである。
clustering
以下に概念的な図を示す。
最初は１つのデータ同士をまとめるということを行っていく。
次に、まとめたグループをさらに近いグループ同士でまとめていく。
最後に、すべてのグループをまとめた１つのグループ（以下の図の赤丸）が生成される。
Dendrogram
すべてをまとめたグループをルートノードとして、階層構造を図示したものにデンドログラムというものがある。
上記の図におけるデンドログラムは以下のようになる。
先ほど作成したデータセットを利用して各フィードの階層的クラスタリングをする
プログラムは以下のようになる。 
#!/usr/bin/python

from math import sqrt

#
# Calculate pearson correlation between p1 and p2
#
def pearson(p1,p2):
    # calculate p's variance
    sum1 = sum(p1)
    sum2 = sum(p2)

    sum1Sq = sum([pow(p,2) for p in p1])
    sum2Sq = sum([pow(p,2) for p in p2])

    pSum = sum([p1[i]*p2[i] for i in range(len(p1))])

    num = pSum-(sum1*sum2/len(p1))
    den=sqrt((sum1Sq-pow(sum1,2)/len(p1))*(sum2Sq-pow(sum2,2)/len(p1)))

    if den == 0: return 0
    return 1.0 - num/den

#
# Read Dataset
#
def readfile(filename):
  lines=[line for line in file(filename)]

  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

#
# Cluster class
#
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

#
# Hierarchical Clustering
#
def hcluster(rows, distance=pearson):
  distances = {}
  currentclustid = -1

  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)

    # Get lowest cluster
    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)]

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

    # Calculate average cluster
    mergevec = [(clust[lowestpair[0]].vec[i]+clust[lowestpair[1]].vec[i])/2.0 for i in range(len(clust[0].vec))]

    # Make new cluster
    newcluster = bicluster(mergevec, left=clust[lowestpair[0]], right=clust[lowestpair[1]], distance=closest, id=currentclustid)

    currentclustid -= 1
    del clust[lowestpair[1]]
    del clust[lowestpair[0]]
    clust.append(newcluster)

  return clust[0]

#
# Print result after hierarchical clustering
#
def printclust(clust, labels=None, n=0):
  for i in range(n): print ' ',
  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)

if __name__ == '__main__':
  blognames,words,data=readfile('blogdata.txt')
  clust=hcluster(data)
  printclust(clust, labels=blognames)

デンドログラムの描画

Python Image Library(PIL)を利用してデンドログラムを描画する。 
#!/usr/bin/python

from PIL import Image,ImageDraw
import clusters

#
# Calculate heights of the dendrogram
#
def getheight(clust):
  if clust.left == None and clust.right == None: return 1
  return getheight(clust.left) + getheight(clust.right)

#
# Calculate distance with depth
#
def getdepth(clust):
  if clust.left == None and clust.right == None: return 0
  return max(getdepth(clust.left),getdepth(clust.right)) + clust.distance

#
# Draw whole dendrogram
#
def drawdendrogram(clust, labels, png='clusters.png'):
  h = getheight(clust) * 20
  w = 1200
  depth = getdepth(clust)

  scaling=float(w-150)/depth

  img = Image.new('RGB', (w,h), (255,255,255))
  draw = ImageDraw.Draw(img)
  draw.line((0, h/2, 10, h/2), fill=(255,0,0))

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

#
# Draw a node
#
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=(255,0,0))

    draw.line((x, top+h1/2, x+ll, top+h1/2), fill=(255,0,0))

    draw.line((x, bottom-h2/2, x+ll, bottom-h2/2), fill=(255,0,0))

    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))

if __name__ == '__main__':
  blognames,words,data=clusters.readfile('blogdata.txt')
  clust=clusters.hcluster(data)
  drawdendrogram(clust,blognames,png='blogclust.png')
blogclust
出力結果を見てみると
単語レベルでの関連性はどのフィードもほぼ同レベルで面白い結果は得られなかったが、
これでデンドログラムを描画することができた。

k平均法

  • 階層的クラスタリングのツリー表示ではひと手間かけることなしには、はっきりとしたグループに分けることはできない。
  • 階層的クラスタリングは計算量が大きく、アイテムがマージされるときには再び計算が必要になる。
  • k平均法の手順は以下
  • １．ランダムに重心を設定する
  • ２．すべてのアイテムをいずれかの重心に帰属させる
  • ３．重心を割り当てられたアイテムの重心に設定する
  • ２．へ戻る
zero
step1
step2
step3
step4
#!/usr/bin/python

import random
from math import sqrt

#
# Read Dataset
#
def readfile(filename):
  lines=[line for line in file(filename)]

  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

#
# Calculate pearson correlation between p1 and p2
#
def pearson(p1,p2):
    # calculate p's variance
    sum1 = sum(p1)
    sum2 = sum(p2)

    sum1Sq = sum([pow(p,2) for p in p1])
    sum2Sq = sum([pow(p,2) for p in p2])

    pSum = sum([p1[i]*p2[i] for i in range(len(p1))])

    num = pSum-(sum1*sum2/len(p1))
    den=sqrt((sum1Sq-pow(sum1,2)/len(p1))*(sum2Sq-pow(sum2,2)/len(p1)))

    if den == 0: return 0
    return 1.0 - num/den

def kcluster(rows, distance=pearson, k=4):
    # Make k clusters with random
    ranges=[(min([row[i] for row in rows]), max([row[i] for row in rows])) for i in range(len(rows[0]))]
    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)]

        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)

        if bestmatches == lastmatches: break
        lastmatches = bestmatches

        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

if __name__ == '__main__':
    blognames,words,data=readfile('blogdata.txt')
    kclust = kcluster(data, k=10)
    print kclust
    print [blognames[r] for r in kclust[0]]

多次元尺度構成法

#
# Read Dataset
#
def readfile(filename):
  lines=[line for line in file(filename)]

  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

def scaledown(data,distance=pearson,rate=0.01):
    n=len(data)

    realdist=[[distance(data[i],data[j]) for j in range(n)] for i in range(0,n)]
    outersum = 0.0

    loc=[[random.random(),random.random()] for i in range(n)]
    fakedist=[[0.0 for j in range(n)] for i in range(n)]

    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]))]))

        grad=[[0.0,0.0] for i in range(n)]

        totalerror=0
        for k in range(n):
            for j in range(n):
                if j==k: continue
                errorterm=(fakedist[j][k]-realdist[j][k])/realdist[j][k]

                grad[k][0] += ((loc[k][0]-loc[j][0])/fakedist[j][k])*errorterm
                grad[k][1] += ((loc[k][1]-loc[j][1])/fakedist[j][k])*errorterm
                totalerror += abs(errorterm)
        print totalerror

        if lasterror and lasterror <totalerror: break
        lasterror=totalerror

        for k in range(n):
            loc[k][0] -= rate*grad[k][0]
            loc[k][1] -= rate*grad[k][1]
    return loc

def draw2d(data,labels,png="mds2d.png"):
    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))
    img.save(png, 'PNG')

if __name__ == '__main__':
  blognames,words,data=readfile('blogdata.txt')
  coords=clusters.scaledown(data)
  clusters.draw2d(coords,blognames,png='blogs2d.png')

リファレンス

この記事は以下の本を元に知人に解説するために説明の仕方を変えて記述したものである。
なお、１章と２章は公開されている。 集合知プログラミング1,2章

要素技術の最近記事

  1. Udacity Self-Driving Car Engineer Nanodegree …

  2. TF-Agents で独自の環境を利用する方法

  3. Amazon Rekognition Video を使って動画内の顔検出と境界ボックスの描…

  4. [触ってみた]Microsoft Quantum Development Kit

  5. Tensorboardを使ってニューラルネットワークと学習の状況を可視化する

関連記事

  1. [AR][Processing]3Dモデルの描画

  2. [R]k-meansでirisをクラスタリングしてみる

  3. [Ruby][ImageProcessing]rubyで画像…

  4. Excel2010を使って t検定 で新手法と旧手法の差を統…

  5. [Go][LeastSquareMethod]最小二乗法 で…

  6. [Haskell]PGMファイルを読み込む part1

PAGE TOP