読者です 読者をやめる 読者になる 読者になる

集合知プログラミング - Chapter3 Discovering Groups

集合知プログラミング

集合知プログラミング

最近、日本語訳版が発売されてなにかと話題の「Programming Collective Intelligence(集合知プログラミング)」を買って読んでいます。
上のリンクは日本語訳版になっていますが、実際は原著を買いました。他の方のブログ等でも、内容が濃い、サンプルコードが充実しているなどと評判の本なので、この本で英語&pythonも一緒に勉強してしまおうという魂胆です。
まだ、全体を読み通したわけではありませんが、これまで読んだ部分だけでもかなり満足しています。
1つ1つのテーマを深く掘り下げてはいないものの、様々なテーマを網羅的に扱っており、それぞれについて実際のデータを使ったサンプルコードが記載されているのがこの本のよさだと思います。また英語についても難しい単語や表現はほとんど出てこないのでかなり読みやすいです。
この辺の分野に興味のある人であれば買っておいて損はないかと。

Chapter3 Discovering Groups読了後メモ

この章は、教師なし学習の一種であるクラスタリング手法に関する章。実際の例として、ブログ内の単語出現頻度を特徴としたクラスタリングを行っている。

クラスタリング手法には、大きく分けて階層的手法、非階層的手法の2種類がある。それぞれの特徴等については以下のページが分かりやすい。

非階層的手法の代表的なものにk-means法がある。k-means法のサンプルプログラムを改良する課題が章末にあったのでこれに挑戦。
課題内容は、クラスタリング結果を返す際に各データと、そのデータが属するクラスタのセントロイドとの距離合計を返すというもの。すなわち、クラスタリング精度を算出するということ(距離合計の値が小さければクラスタリング精度が高いことになる)

Exercise5

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

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

    # 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

  # この処理を追加
    # Calculate the total distance between all the items and their respective centroids
    distancesum = 0
    for i in range(k):
      for rowid in bestmatches[i]:
        distancesum += distance(clusters[i], rows[rowid])

    #print distancesum


  return bestmatches, distancesum

Exercise6

k-means法のkの値(クラスタ数)を変化させた場合のクラスタリング精度を確認するという内容。
1≦k≦30の範囲でkを変化させた結果は以下の通り。横軸がkで、縦軸がクラスタリング精度(値が小さい程精度がよい)。k-means法は初期クラスタの配置による結果への影響が大きい手法なので、一度試しただけではなんとも言えないがk=15あたりからクラスタリング精度の変化が小さくなっている?