Scalaで集合知プログラミング その12
Scala de 集合知プログラミング第3章のクラスタリングを進めていきますよ(｀・ω・´)
今回は前回作成したデータセットを基に実際にクラスタを作成していきますデス
階層的クラスタリング
「最も似ている2つのグループをまとめる」という行動を繰り返すことで、グループの階層を作っていく手法を階層的クラスタリングと呼ぶみたいです。
詳しい過程については本書で解りやすい図と共に解説されているのですが、ざっくりと手順を書くとこんな感じですね
- 最も類似度の高い2つのアイテム（グループ）を選択して、新しくグループ化
- 次に類似度の高い2つのアイテム（グループ）を選択して、新しくグループ化
- (... 以下、繰り返し...)
- 残った2つのアイテム（グループ）を選択して、一つにグループ化
最終的にひとまとめになる＆各アイテムは階層構造に整理されるみたいです(´・ω・｀)
すごくざっくりと書くと、階層構造はたとえばこんな感じですね
- ルート
- グループ1
- アイテムA
- アイテムB
- アイテムC
- グループ1
このように作成される階層構造は、ルートを頂点としたピラミッド型で表現できて、こいつをデンドログラムというグラフで表現することができるそうです(´・ω・｀)
デンドログラムの実例も本書を参照してもらうこと…として、デンドログラムで表現することで、各アイテムのグループ状況に加えて階層構造上でのアイテム間の距離（類似具合）なんかも判断することが出来るとか(´・ω・｀)
これを「クラスタのタイトネスとして解釈できる」って言うらしいですが、クラスタのタイトネスってなんじゃらホイ？
…と、とりあえず今回は階層的クラスタリングなグループ化をやっていきますよ(´・ω・｀)
結構量が多くなるので、ポイントポイントで細切れにしながらサンプルのPythonコードを写経しつつ、Scalaへの翻訳をしていきますデス(´・ω・｀)
まずはブログデータの読み込み
まずはブログデータの読み込み処理からやってみマスよ
- Pythonでブログデータを読み込むコード
# clusters.pyに記述します # blogdata.txtを読み込む処理です 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
- Scalaでファイル読み込み
それではScalaでの読み込み処理を書いてみますですよ(´・ω・｀)
そこまで集計しなくてもよさそうなのでイミュータブル気味で書いてみましたよ
// Cluster.scalaとして保存してやります // パッケージ宣言をします package org.plasticscafe.collective.cluster // 必要なモジュールを読み込みます import scala.io.Source // オブジェクトとして定義します object Cluster{ // ファイル読み込み用の処理です def readfile(filename:String):(List[String], List[String], List[List[Int]]) = { // URL一覧のリストファイルを取得します val source = Source.fromFile(filename) val lines = source.getLines().toList source.close // ヘッダ行から単語一覧を取得します // 1つめの要素はBlog名用のヘッダなので捨てます val colnames = lines(0).trim.split("\t").tail.toList // 再帰で集計処理していきます def counting(lines:List[String]):(List[String], List[List[Int]]) = lines match { case Nil => (Nil, List.empty[List[Int]]) // 行が残っている場合は処理続行です case a :: other => { // 処理対象の行をパースしてブログ名と単語頻出度に分解します val (rownames, data) = counting(other) val line = a.trim.split("\t") // これまでの処理結果とマージして値を返します (line(0) :: rownames, line.tail.map(_.toInt).toList :: data) } } // 集計処理を行って単語ヘッダと結合したうえで値を返します val (rownames, data) = counting(lines.tail) (rownames, colnames, data) } }
とりあえずこんな感じですかね(´・ω・｀)
グループ間の類似度の計算
クラスタリングではアイテム（グループ）間の類似度を基にグループ分けを進めていくことになりますが、今回は単語頻出ベクトルを利用したピアソン相関係数で定義していきます
- まずはPythonで類似度計算です
# clusters.pyに追記します # 2つのアイテム間のピアソン相関係数を計算する処理です from math import sqrt # 求める類似度は完全一致が1、完全に一致しないが0です 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))) # 分母が0になった場合は計算不能なので類似度0 if den == 0: return 0 # 計算したピアソン系数的類似度を返します # １から引くことで小さければ小さい(0に近い)ほど類似！とします return 1.0 - num /den
それではピアソン相関係数計算をScalaでやってみますかね…といっても以前やった内容を単語ベクトルに合わせてちょろっと改変するだけですな(´・ω・｀)
// Cluster.scala内のClusterオブジェクトに追記します // 計算用のモジュールをインポートします import Math.{sqrt, pow} // ピアソン相関係数を求めます def pearson(v1:List[Int], v2:List[Int]):Double = { // 前要素数を取得してやります val n = v1.size // 全ての共通嗜好値の合計を計算します val sum1 = v1.sum val sum2 = v2.sum // 平方の合計を計算してやります val sum1Sq = v1.map(x => pow(x, 2)).sum val sum2Sq = v2.map(x => pow(x, 2)).sum // 積の合計を計算します // Scalaっぽいかどうかはアレなんですが... val pSum = (for (i <- Range(0, n)) yield {v1(i) * v2(i)}).sum // ピアソンスコアを計算します val num = pSum - (sum1 * sum2 / n) val den = sqrt(sum1Sq - pow(sum1, 2) / n ) * sqrt(sum2Sq - pow(sum2, 2) / n ) // 分母が0になったら誤りということで0を返します if(den == 0) return 0 // 値を返します // ピアソン相関係数は1 ~ -1の範囲で推移するので // 1から引くことで小さければ小さいほど類似する...と定義します 1.0 - num / den }
とりあえずできましたな(｀・ω・´)
各クラスタをクラスで定義
各アイテム（グループ）を表現するクラスタは以下の各属性をもつので、こいつをクラスを利用することで表現してやります(｀・ω・´)
- グループの場合は、要素となるアイテム(2つ)
- グループの場合は、要素間の類似度
- 単語頻出度ベクトル
- グループの場合は要素となるアイテムのベクトルの平均
それではクラスを定義してみますよ
# clusters.pyに追記します # 階層的なツリーを表現するクラスを定義シマス(´・ω・｀) class bicluster: # 階層的なツリー内の各ノードを表現します def __init__(self, vec, left=None, right=None, distance=0.0, id=None): # 該当クラスタの子クラスタ（統合元） self.left = left self.right = right # ベクトル情報(単語頻出情報) self.vec = vec # クラスタに一意につけられたID self.id = id # 子クラスタがある場合は、その類似度 self.distance = distance
Clusterクラスを定義してやります(｀・ω・´)
Pythonではclusterクラスの各種パラメータに問答無用でデフォルト値Noneを突っ込んでいますが...Scalaでそれはちょっと…ということでOption型でも使ってみますかね(´・ω・｀)
// Option型を使って値が入らない可能性のあるパラメータを定義してやります // それと外部からアクセスできるようにvalで定義します(´・ω・｀) class Cluster( val vec:List[Int], val left:Option[Cluster]=None, val right:Option[Cluster]=None, val distance:Double=0.0, val id:Option[Int]=None )
...これ、何も考えずにコンパニオンオブジェクト / クラスにしてしまったけども…問題はないのかしら？
ちなみに、ダメでもともと！(｀・ω・´)的にコンパニオンオブジェクトに追記したapplyメソッドはこんな感じです
def apply(vec:List[Int], left:Option[Cluster]=None, right:Option[Cluster]=None, distance:Double=0.0, id:Option[Int]=None) = { // クラスを作成 new Cluster(vec, left, right, distance, id) }
(´ε｀；)ｳｰﾝ…、かなり強引に書いてしまったけども良いのかしら？しかもコンパニオンオブジェクトの使い方が間違っている気がする…困った(´・ω・｀)
詳しい人がいればツッコミおながいします。
