Categories: 機械学習・レコメンド要素技術

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

学習の仕方

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

データセットの準備

ブログの クラスタリング をそのブログの単語頻度を用いて行う。
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

階層的 クラスタリング

階層的クラスタリングは似ているグループをまとめるという作業を段階的に行うことによって、
階層構造を見つけ出すアルゴリズムである。
以下に概念的な図を示す。
最初は１つのデータ同士をまとめるということを行っていく。
次に、まとめたグループをさらに近いグループ同士でまとめていく。
最後に、すべてのグループをまとめた１つのグループ（以下の図の赤丸）が生成される。
すべてをまとめたグループをルートノードとして、階層構造を図示したものにデンドログラムというものがある。
上記の図におけるデンドログラムは以下のようになる。
先ほど作成したデータセットを利用して各フィードの階層的クラスタリングをする
プログラムは以下のようになる。 
#!/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')
出力結果を見てみると
単語レベルでの関連性はどのフィードもほぼ同レベルで面白い結果は得られなかったが、
これでデンドログラムを描画することができた。

k平均法

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

某Web系の会社でエンジニアをやっています。 学術的なことに非常に興味があります。 趣味は楽器演奏、ジョギング、読書、料理などなど手広くやっています。

Share
Published by
zuqqhi2
Tags: クラスタリング
10年 ago

Recent Posts

PubSubClient の便利さと注意点

Arduino から AWS …

2か月 ago

Java の環境構築方法メモ

普段 Java を使用しないの…

4か月 ago

PlatformIO IDE for VSCode を使用して VSCode で Arduino にプログラムを書き込む方法

Arduino にプログラムを…

10か月 ago

ROS Docker イメージで発生した GPG error の解消方法

この前 ROS の公式 Doc…

11か月 ago

Streamlit で訪れた国を色づけした世界地図を作成できるアプリケーションを作成してみた

Streamlit は Pyt…

1年 ago

M5Stack Core2 for AWS – ESP32 IoT開発キットで Amazon FreeRTOS を動かしてみた (macOS)

先日、SWITCHSCIENC…

2年 ago