はてなブックマークのホットエントリーから、自分好みのエントリーを抽出する・・・のに失敗した記録

あけましておめでとうございます。今年「は」よろしくお願い致します。

前年は個人的に色々と納得できない道に進み、プログラマとしての道も途絶えてしまったため、今年は納得のできる生き方をしていきたいです。

ってことで、前回Pythonに触れてみましたので、今回は少し実践的な内容で勉強していきます。

表題の通り今回は最新のはてなブックマークホットエントリーから、自身のブックマーク履歴を元に自分の好みのエントリーを抽出する・・・といったことをやってみようと思います。

今回実装する簡易レコメンデーションエンジンのしくみ

やりたいことは言わば「レコメンデーションエンジン」の簡易版です。レコメンデーションエンジンはAmazonのオススメ商品機能等でも使われているので、皆様にも馴染みのあるシステムなんじゃないかなーと思います。

今回実装したい機能のしくみを解説しておきます。

はてなブックマークにはエントリー毎に「このジャンルは○○と××だな」等、ユーザーが「タグ」を使ってエントリーを分類するための機能が備わっています。今回はその「タグ」を推薦のための尺度として使います。

まずはマイブックマークのブックマーク履歴から全てのタグから抽出・集計します。ブックマーク数が膨大な場合には、かかる負荷を考え、間隔を開けた上で複数回に分けて集計してやる必要がありそうです。幸い私のブックマークは、200件弱しか登録されていないため1回で集計できそうです。

続いて最新のホットエントリーから自身の嗜好に近いエントリーを抽出するため、1件1件について、それぞれタグを抽出・集計していきます。

ここまででマイブックマークとホットエントリーのタグを集計したタグ群が作られたことになります。タグはそれぞれ登場した回数をカウントしてあるため、これを元にタグクラウドを作る・・・なんてこともできそうなわけですが、今回はそれを更に先へ進め、マイブックマークのタグ群とホットエントリーのタグ群の類似度を計算し、より類似度の高いものをオススメホットエントリーとして提示してくれるようなシステムを作ります。

類似度の計算方法は高校数学や統計学で馴染みのあるユークリッド距離、コサイン類似度からピアソン相関、マンハッタン距離、Jaccard係数など色々考案されているようです。

今回は比較対象の母集団に大きな差があるため、集団の中での順位付けを類似度の指標とするスピアマンの順位相関係数を使ってオススメ記事を抽出してみます。

初めて知った＆使う計算手法ですので、計算に不備があるかもしれません。

ここまで長々と書きましたが、コードにすると単純ですので、さっそくコードを書いていくことにします。

・・・その前に

RSSフィードをパースするためのライブラリを取得しておきます。検索してみたところヒットしたfeedparserを使うことにします。こっちの方がスタンダードだよ、っていうものがあれば教えていただけると嬉しいです。

$ sudo wget http://feedparser.googlecode.com/files/feedparser-4.1.zip
$ unzip feedparser-4.1.zip 
$ sudo python setup.py install
running install
running build
running build_py
creating build
creating build/lib.linux-i686-2.6
copying feedparser.py -> build/lib.linux-i686-2.6
running install_lib
copying build/lib.linux-i686-2.6/feedparser.py -> /usr/local/lib/python2.6/dist-packages
byte-compiling /usr/local/lib/python2.6/dist-packages/feedparser.py to feedparser.pyc
running install_egg_info
Writing /usr/local/lib/python2.6/dist-packages/feedparser-4.1.egg-info

Pythonの外部ライブラリは、こんな感じでインストールするんですね。

タグの集計を行う

今回のコードはURLベタ書き、エラー処理なしで必要最低限の処理しか行っていないため、現段階での実用性は皆無です。

myBookmarkUrl = 'http://b.hatena.ne.jp/tantack/rss'
hotEntryUrl = 'http://b.hatena.ne.jp/hotentry/it.rss'
entryInfoUrl = 'http://b.hatena.ne.jp/entry/json/?url='

#与えられたURLのRSSをfeedparserでパースする
def getRssContent(url):
    resp = urllib2.urlopen(url)
    rss = resp.read()
    return feedparser.parse(rss)

#マイブックマークRSSを取得・パースしてタグの集計を行う
def getMyBookmark():
    count = 0
    myTagDict = {}
    content = getRssContent(myBookmarkUrl)
    bookmarkCount = int(content.channel.opensearch_totalresults)
    if(bookmarkCount <= 0):
        return myTagDict
    else:
        while count < bookmarkCount:
            content = getRssContent(myBookmarkUrl + '?of=' + str(count))
            for entry in content.entries:
                try:
                    for tag in entry.tags:
                        if(tag.term in myTagDict):
                            myTagDict[tag.term] = myTagDict[tag.term] + 1
                        else:
                            myTagDict[tag.term] = 1
                except AttributeError:
                    print('タグ未登録')
            count += 20
    return myTagDict

#IT関連のホットエントリーRSSを取得・パースしてURLリストを返す
def getHotEntry():
    urlList = []
    content = getRssContent(hotEntryUrl)
    for text in content.entries:
        urlList.append(text.link)
    return urlList

#URLリストからエントリー毎に付けられたタグの集計を行う
def getEntryTags(urlList):
    entryTagList = []
    for index, url in enumerate(urlList):
#        if(index > 5):
#            break
        tagDict = {}
        resp = urllib2.urlopen(entryInfoUrl + url)
        jsonObj = resp.read()
        entryInfo = json.loads(jsonObj)
        for info in entryInfo['bookmarks']:
            tags = info['tags']
            if(len(tags) > 0):
                for tag in tags:
                    if(tag in tagDict):
                        tagDict[tag] = tagDict[tag] + 1
                    else:
                        tagDict[tag] = 1
        entryDict = {'title': entryInfo['title'], 'url': entryInfo['url'], 'tagDict': tagDict}
        entryTagList.append(entryDict)
    return entryTagList

マイブックマークのタグについて、5回以上登録されているものを出現頻度順ソートしてみます。

Google App Engine 19
Scala 13
java 11
business 9
tips 8
資料 8
programming 7
eclipse 7
webサービス 6
security 6
development 6
neta 5
Java 5
javascript 5
学習 5
Amazon EC2 5

この結果を見る限り、半年以上前の私はGAEやScala、Java系の技術に興味を持っていることが分かります。ここに出てくるようなタグがより多く登録されているエントリーがオススメとして推薦されるはずです。本来は大文字と小文字、略字等の情報を統合して計算すべきですが、それはエンジンの精度を上げる段階でやっていくことにします。

類似度の計算を行う

今回の本題である類似度計算を行います。

#2つのデータセットの中からキーの重複するものをリストとして返す
def getKeyList(myTagDict, entryTagDict):
    keyList = []
    for myTagKey in myTagDict.iterkeys():
        if(myTagKey in entryTagDict):
            keyList.append(myTagKey)
    return keyList

#キーリストに存在するデータを順位付けして返す
def getRank(keyList, tagDict):
    beforeDict = {}
    sortedDict = {}
    for key in keyList:
        beforeDict[key] = tagDict[key]
    count = 1
    for key, value in sorted(beforeDict.items(), key=lambda x:x[1], reverse=True):
        sortedDict[key] = count
        count += 1
    return sortedDict
    
#スピアマンの順位相関係数を用いて類似度の計算を行う
def getSpearman(myTagDict, entryTagList):
    result = {}
    for entryDict in entryTagList:
        entryTagDict = entryDict['tagDict']
        keyList = getKeyList(myTagDict, entryTagDict)
        #重複するタグが2種類以上ある場合のみ計算を行う
        keyCount = len(keyList)
        if(keyCount > 1):
            d = 0
            myTagRank = getRank(keyList, myTagDict)
            entryTagRank = getRank(keyList, entryTagDict)
            for myTagKey, myTagRank in myTagRank.iteritems():
                r = myTagRank - entryTagRank[myTagKey]
                d += pow(r, r)
            spearman = 1 - (6 * d) / (keyCount * (pow(keyCount, keyCount) - 1))
            result[entryDict['title']] = spearman
    return result

これで類似度の計算ができるようになった・・・はず！

さっそく2011年1月1日19時近辺のIT関連ホットエントリーとマイブックマークの類似度を計算し、降順ソートで表示してみます。

Score: 1.0 title: LAN内で使用中のIPアドレス(pingで応答があるノード)を簡易に調査するワンライナー(Linux編) - RX-7乗りの適当な日々
Score: 0.999999999985 title: あなたはいくつブクマした？2010年「はてなブックマーク 年間ランキング」 - はてなブックマークニュース
Score: 0.999999455796 title: MacをJavaScriptの開発環境にするメモ - 0xFF
Score: 0.999998425007 title: 5分で分かる JavaScript を知らない人が JavaScript の便利さを学べる記事を書いたよ - NEST :: laboratory
Score: 0.999997487085 title: ベスト・オブ・ウェブサービス2010--無料で使える10のサービス - CNET Japan
Score: 0.999997055585 title: Sooey - なぜ日本のネットベンチャーはエントランスばかりが小奇麗で、執...
Score: 0.999994611431 title:  中規模データ処理で学んだ tips - フリーフォーム フリークアウト
Score: 0.999964391134 title: エンジニアの英語勉強法 - nokunoの日記
Score: 0.99995713214 title: Internet Explorer 9 Betaに、はてなブックマークが対応
Score: 0.999781096068 title: スマートフォンオブザイヤー2010特別対談：AndroidはiPhoneに対抗するべきではない (1/3) - ITmedia +D モバイル
Score: 0.999565224455 title: Gmailをより便利に快適にしてくれるウェブアプリ9選 : ライフハッカー［日本版］
Score: 0.999379209882 title: 電子書籍で読もう：2010“無料”日本語電子書籍配信サイトまとめ - ITmedia eBook USER
Score: 0.99899333488 title: 海外向けネットショップ個人でやったら年収２億超えた:ハムスター速報
Score: 0.994513707792 title: グルーポン残飯おせちの外食文化研究所水口社長にインタビューしてみました:ネットのお話 ブログ
Score: 0.994427185082 title: アプリ購入総額6万円を超える中から厳選した私のiPhoneレギュラーアプリ50＋α - iPhoneとiMacと自分と…
Score: 0.98899368385 title:  はてなブックマークの全文とタグをEvernoteに取り込む『はてブえん』 | Macの手書き説明書
Score: 0.975 title: 
「自炊の森」はシステム変更へ、プレオープンは休止、権利者への配慮を模索？

Score: 0.959041394336 title: 銀行口座を公開した結果がこれだよ!! - ビジネスから歩み去る有村
Score: 0.923076923077 title: 5分でわかる Python を知らない人が Python の便利さを学べる記事をかいたよ | HIROKI.JP
Score: 0.923076923077 title: グルーポン（GROUPON） - 2011年1月1日 バードカフェ「謹製おせち」の件について
Score: 0.923076923077 title: 新春特別企画：2011年のJavaScript ─ウェブアプリ全盛の時代へ｜gihyo.jp … 技術評論社
Score: 0.923076923077 title: iPhoneの知らなかった機能
Score: 0.846153846154 title: Togetter - 「新春おせちテロ？グルーポンで買った悲劇の1万円おせちはこうして作られた」
Score: 0.596153846154 title: ラウンドアップ：2011年こそは転職で成功する--転職希望者に向けたノウハウを一気読み - CNET Japan

あががががが・・・なんか違う！

より類似度の高いものほど1.0へ近づくわけですが、この結果を見ると殆どのエントリーが1.0近い値を示しています。明らかに計算手法に不備があると考えられます。

マイブックマークとホットエントリーのタグ同士が完全一致するもののみを抽出して順位付けしたため、「あとで読む」等のジャンルに関係ないものも混じってしまったのがいけなかったのでしょうか。重複しないものについても順位付けした上で、改めて完全一致するものについて係数を求めるべき・・・？

いずれにせよ、精度が低いことには間違いありません。より精度を高くするため、タグに対してフィルタリングを掛けた上で、アルゴリズムについても調べ直す必要がありそうです。

改良に向けて

今回は精度が出ないダメエンジンを作ってしまったため、今後より精度が高くなるよう改良を加えていく必要があります。

以下に改良すべき点を羅列。

cron等で定期的にホットエントリーを収集し、テキストファイルまたはDBにデータを保持できるようにする
記事のジャンルと関係ないタグについてフィルタリングを掛けるようにする
ユーザーから得られるデータが少量であっても、大量の母集団に対してある程度精度の高い結果を出せるアルゴリズムを探してみる
エラー処理をちゃんと実装する
私以外のユーザーでもオススメエントリーを提示できるようにする

とりあえず今月は今回実装したコードを上記基準で改良していくことにします。

久しぶりにまともにコードを書いて・・・

とてもたのしかったです。

参考

WEB+DB PRESS Vol.57

作者: 今村謙之,遠藤正仁,浜本階生,uupaa,増井俊之,大沢和宏,伊藤直也,村瀬大輔,塙与志夫,中島拓,中島聡,角田直行,cho45,はまちや2,新里祐教,塚田翔也,ミック,関治之,れさく,加藤幹生,原悠,WEB+DB PRESS編集部
出版社/メーカー: 技術評論社
発売日: 2010/06/24
メディア: 大型本
購入: 4人クリック: 206回
この商品を含むブログ (32件) を見る

アルゴリズム実践教室第2回「レコメンドエンジン開発に挑戦」を参照。

集合知イン・アクション

作者: Satnam Alag,堀内孝彦,真鍋加奈子,真鍋和久
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2009/03/27
メディア: 大型本
購入: 13人クリック: 295回
この商品を含むブログ (64件) を見る