« さくらインターネットサーバでのCPAN設定:うまくいかない人のために | トップページ | クラスタリング(分類)処理 »

類似性を探そう!

ふぁぼったーという、twitterのfavoriteをカウントして集計してくれるサービスがあるのですが、たまに似たようなものというか、ほとんど同じものがふぁぼられてることがあります。
似たようなものを排除できないかなーと思って、いろいろ考えてみました。
というか、実況で同一postで並んでるのをひたすらfavoriteして、TOPが埋まって鬱陶しいんですよ!

方針はこんなかんじ。
1.ふぁぼったーの「人気」から上位・・・だいたい10ページ分を取得
2.HTMLを解析してデータ抽出(スクレイピング)
3.抽出したデータをデータベースに突っ込む
4.突っ込んだデータをもとに、類似性を計算

1〜3は Ruby 、 4は(モジュール等の関係から) Perl を使いました。

1.net/http
2. 特になし。正規表現(そして後方参照)多用。
3.Ruby DBI

4.String::Trigram
これについては、下記ブログを参考にさせていただきました。というか、ここで知りました。
livedoor Developers Blog:String::Trigram でテキストの類似度を測る - livedoor Blog(ブログ)

結果としてはこんなかんじ。大きくなるんでダイジェストで。
左から、件数、類似率、対象1、対象2。

% perl chksiml.pl | sort | uniq -c 
70 57 ぞ! ぞ!!!
6 57 ぞ!!! ぞ!
566 72 ぞ! ぞ!!
80 72 ぞ!! ぞ!
27 78 ぞ!! ぞ!!!
7 78 ぞ!!! ぞ!!
10 88 H!I!N!A!HINAGIKU!... H!I!N!A!HINAGIKU!...
45 100 H!I!N!A!HINAGIKU!... H!I!N!A!HINAGIKU!...
1 100 ぞ! ぞ!
703 100 ぞ! ぞ!
136 100 ぞ!! ぞ!!
1 100 ぞ!!! ぞ!!!
1 100 ぼ! ぼ!

閾値50%にしましたが・・・多すぎっつーか固まりすぎ(笑)


ちなみにソースはこちら。

#!/usr/bin/perl

use POSIX ;
use Time::Local ;
use DBI ;
use String::Trigram ;

$DATABASE_CONSTR = "dbi:mysql:test:db.example.com" ;
$DATABASE_USER = "user" ;
$DATABASE_PASS = "password" ;

$TARGET_DATE = "2009-09-05" ;
$QUERY = "SELECT stat_id,stat_text,stat_date FROM `uf_favdata` WHERE stat_date >='" . $TARGET_DATE . " 00:00:00' AND stat_date <='" . $TARGET_DATE . " 23:59:59' ORDER BY stat_id " ;

$td_year = substr( $TARGET_DATE , 0 , 4 ) ;
$td_mon = substr( $TARGET_DATE , 5 , 2 ) ;
$td_day = substr( $TARGET_DATE , 8 , 2 ) ;

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

@idlist = () ;
while( @m = $sth->fetchrow_array ) {
$st_id = $m[0] ;
$st_text = $m[1] ;
$st_date = $m[2] ;

$st_ctime = mktime( substr( $st_date , 17 , 2 ) ,
substr( $st_date , 14 , 2 ) ,
substr( $st_date , 11 , 2 ) ,
$td_daty ,
$td_mon - 1 ,
$td_year - 1900 ) ;

$var_text{ $st_id } = $st_text ;
$var_date{ $st_id } = $st_ctime ;
push @idlist , $st_id ;
push @idlist2 , $st_id ;
}

$sth->finish ;

foreach $i_id ( @idlist ) {
shift @idlist2 ;
foreach $j_id( @idlist2 ) {
last if ( $var_date{ $j_id } - $var_date{ $i_id } > 60 * 5 ) ;
$similarity_rate = String::Trigram::compare( $var_text{ $i_id } ,
$var_text{ $j_id } ) * 100 ;
if ( $similarity_rate > 50 ) {
$p_i_text = substr( $var_text{ $i_id } , 0 , 27 ) ;
$p_j_text = substr( $var_text{ $j_id } , 0 , 27 ) ;
$p_i_text .= "..." if ( length( $p_i_text ) >= 27 ) ;
$p_j_text .= "..." if ( length( $p_j_text ) >= 27 ) ;
printf( "%3d %-30s %-30s\n" , $similarity_rate , $p_i_text , $p_j_text ) ;
}
}
}

おまけ。
前の記事で、さくらインターネットでのCPAN設定の記事を書きました。
で、今回もさくらのサーバに String::Trigram をCPAN経由で入れようとして・・・案の定失敗しました。

In file included from Trigram.xs:6:
/usr/include/malloc.h:3:2: error: #error "<malloc.h> has been replaced by <stdlib.h>"

こんなのが出て。
~/.cpan/build/ 以下にソースがあるので、探し出して、includeの malloc.h を stdlib.h に変更しました。このへんは注意が必要です。

|

« さくらインターネットサーバでのCPAN設定:うまくいかない人のために | トップページ | クラスタリング(分類)処理 »