« 類似性を探そう! | トップページ | MacOS X Snow Leopard 入・・・った! »

クラスタリング(分類)処理

前回の記事で、ふぁぼったーのpostの類似性の計算処理を行いました。
今度は、それを元に類似したものどうしでクラスタリングをしてみようと思います。

クラスタリングについては解説されたページがありますが、ちょっと難しいかなーと思います。
クラスタリングとは (クラスター分析とは)

ちなみに私のやった方法ですが、このようにしました。
・類似性の高いもの A-B 、A-C 、A-D 、D-F、D-G、G-J があるとします。
・A-B,A-C,A-Dという関係があるので、まず、B,C,Dの親をAとします。
・D-F,D-Gで、FとGの親をDとしたいのですが、DがすでにAの子なので、これも親をAとします。
・G-Jで、Jの親をGとしたいのですが、GがすでにDの子なので、親をDとします・・・が、DはAの子で「親はA」となっているので、Jも親をAとします。
わかりやすく言うと、クラスタの結合ですね。
ちなみに、さきほどの文献でいうと、階層的クラスタリングの最短距離法という手法に該当します(たぶん)。

これを実装するために、各要素の属性に以下を持たせています。
・自身のID
・自身の直近の親となるID
・自身の親(根本)となるID
・自分が根本の親か、子かのフラグ
4番目は要らないような気がしますが一応持たせました。

今回使用したプログラムの要所をここに紹介したいと思います。

$i_query =<<__QUERY__;
SELECT a.id_parent, COUNT( a.id_parent ) AS cnt, MAX( a.similarity ) AS maxsiml, b.user_id, b.stat_text
FROM `uf_simrel` a, uf_favdata b
WHERE a.id_parent = b.stat_id
GROUP BY a.id_parent
ORDER BY cnt DESC
__QUERY__

$dbh = DBI->connect( $DATABASE_CONSTR , $DATABASE_USER , $DATABASE_PASS ) ;
$sth = $dbh->prepare( $i_query ) ;
$sth->execute() ;

@idlist = () ;
while( @m = $sth->fetchrow_array ) {
$id_parent = $m[0] ;
$counts = $m[1] ;
$maxrate = $m[2] ;
$userid = $m[3] ;
$usertext = $m[4] ;

push @idlist , $id_parent ;
$siml_parent{ $id_parent } = -1 ;
$siml_mark{ $id_parent } = 0 ;
$var_count{ $id_parent } = $counts ;
$var_maxrate{ $id_parent } = $maxrate ;
# print $id_parent . "\n" ;
}
$sth->finish ;

foreach $i_id ( @idlist ) {
$j_query = "SELECT id_parent,id_child,similarity FROM uf_simrel WHERE id_parent=" . $i_id ;
$sth = $dbh->prepare( $j_query ) ; $sth->execute ;
# print $j_query . "\n" ;
if ( $siml_mark{$i_id} == 1 ) {
# already similar
$parent_id = $siml_parent{ $i_id } ;
} else {
# not already
$siml_parent{ $i_id } = $i_id ;
$parent_id = $i_id ;
}
@childlist = () ;
while ( @m2 = $sth->fetchrow_array ) {
$child_id = $m2[1] ;
$simrate = $m2[2] ;
#printf( " parent=%12d child=%12d siml=%6.3f [pp:%12d]\n" ,
# $i_id , $child_id , $simrate , $parent_id ) ;
$siml_parent{ $child_id } = $parent_id ;
$siml_mark{ $child_id } = 1 ;
$parent_count{ $parent_id } ++ ;
}
}

foreach $i_id( @idlist ) {
if ( $siml_mark{$i_id} == 0 ) {
printf( "id=%12d parent=%12d mark=%d count=%4d\n" , $i_id , $siml_parent{ $i_id } , $siml_mark{ $i_id } , $parent_count{ $i_id } ) ;
$k_query = sprintf( "INSERT INTO uf_simclust (parent_id,counts) VALUES (%d,%d) " ,
$i_id , $parent_count{ $i_id } ) ;
$sth = $dbh->prepare( $k_query ) ; $sth->execute() ;
}
}

$dbh->disconnect ;

ここで出力されたクラスタ情報をもとに、元データと結合させると、結果はこんなかんじになりました。
8

思いの外きれいにまとまってしまいました。

|

« 類似性を探そう! | トップページ | MacOS X Snow Leopard 入・・・った! »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/1051972/31345571

この記事へのトラックバック一覧です: クラスタリング(分類)処理:

« 類似性を探そう! | トップページ | MacOS X Snow Leopard 入・・・った! »