root/lang/cplusplus/misc/clustercpp/python/wardcluster/hatenasample.py

#!/usr/local/Python25/bin/python
# _*_ coding: utf-8 _*_
# Copyright (C)  2007 Ayukawa Hiroshi
from collections import defaultdict
from operator import add
from itertools import groupby, chain
import math
import types

import feedparser
import MeCab

from wardcluster import Matrix, DoubleVec, Ward


MECAB_ENCODING = "utf-8"

MEISHI = u"名詞".encode(MECAB_ENCODING)
MICHI = u"未知語".encode(MECAB_ENCODING)
GARBAGECLUSTER = 1
BIGCLUSTER = 8

URL = "http://b.hatena.ne.jp/hotentry?mode=rss"
        
def findcutplane(history, histmap):
    """
    平均高さで斬った切断面を求めます。
    """
    avgdistance = sum(map(lambda h: h.distance, history)) / float(len(history))
    for i, h in histmap.iteritems():
        if h.distance > avgdistance:
            if not h.index1 in histmap or histmap[h.index1].distance <= avgdistance:
                yield h.index1
            if not h.index2 in histmap or histmap[h.index2].distance <= avgdistance:
                yield h.index2

def findleaf(t, leaftype=types.IntType):
    """
    ツリーの葉全体を返します。
    """
    if type(t) == leaftype:
        yield t
    else:
        for n in chain(findleaf(t[0]), findleaf(t[1])):
            yield n
    
def allparent(top, desc, n):
    if n == top:
        yield n
        return
    yield n    
    for m in allparent(top, desc, desc[n]):
        yield m

def repairbags(bags, findplane):
    #切断面から除外されて落ちた葉を拾い集めてどこかに押し込む
    for i in list(bags.keys()):
        if len(bags[i]) <= GARBAGECLUSTER:
            n = findplane(i)
            if n:
                bags[n]+=bags[i]
                bags.pop(i)
            else:
                bags["other"]+=bags[i]
                bags.pop(i)
    return bags

def cutdendrogram(history, size=None, subset=None, dual=False):
    """
    樹形図をカットする関数
    """
    #クラスタリング結果データの整理
    if subset:
        tree = dict(zip(sorted(subset), sorted(subset)))
    else:
        tree = dict(zip(range(size), range(size))) # i=>i(葉)という対応を作る。
    histmap = {}
    desc = {}
    for h in history:
        #print h.newindex, "<-", h.index1, "+", h.index2, "(", h.distance,")"
        tree[h.newindex] = (tree[h.index1] if h.index1 in tree else h.index1,
                            tree[h.index2] if h.index2 in tree else h.index2)
        histmap[h.newindex] = h
        desc[h.index1] = h.newindex
        desc[h.index2] = h.newindex

    #切断面決定
    cutplane = set(findcutplane(history, histmap))

    #切断した葉ごとに分ける、同時に、少ない枝を切断面から除外
    bags = defaultdict(list)
    for i in list(sorted(cutplane)):
        bag = list(findleaf(tree[i]))
        if len(bag) <= GARBAGECLUSTER: # 少ない枝を除外
            cutplane.remove(i)
            bags[i] = bag
        elif dual and len(bag) > BIGCLUSTER: #大きい枝をさらに分割(dualが設定されている場合)
            parents = set()
            for b in bag:
                parents.update(allparent(i, desc, b))
            subhistory = filter(lambda h: h.newindex in parents, history)
            subbags = repairbags(*(cutdendrogram(subhistory, subset=bag, dual=dual)))
            #print "subbags", subbags
            bags.update(subbags)
        else:
            bags[i] = bag
    def findplane(n):
        """
        最も近い切断面を求める。
        """
        if n in histmap:
            if histmap[n].index1 in cutplane:
                return histmap[n].index1
            if histmap[n].index2 in cutplane:
                return histmap[n].index2
        if n == history[-1].newindex:
            return None
        return findplane(desc[n])
    return bags, findplane

def create(html=False):
    """
    分割します。
    """
    tagger = MeCab.Tagger()
    feed = feedparser.parse(URL) #rss取得＆解析
    tagnum = 0
    kwmaster = {}
    kwnum = 0

    vecs = []
    docs = []

    #分かち書きしてベクトル作成
    for e in feed.entries:
        docs.append(dict(title=e["title"], link=e["link"]))
        tags = map(lambda x: x["term"], e.get("tags", []))
        body = u"。".join([e["title"]]+tags) 
        node = tagger.parseToNode(body.encode(MECAB_ENCODING))
        vec = defaultdict(int)
        while node:
            if node.feature.startswith(MEISHI) or node.feature.startswith(MICHI):
                if not node.surface in kwmaster:
                    kwmaster[node.surface] = kwnum
                    vec[kwnum] += 1
                    kwnum += 1
                else:
                    vec[kwmaster[node.surface]] += 1
            node = node.next
        vecs.append(vec)
    size = len(vecs)  #ベクトル本数

    #行列作成
    dimension = max(kwmaster.values())
    matrix = Matrix()
    for vec in vecs:
        dencev = [0.0]*(dimension+1)
        for k,v in vec.iteritems():
            dencev[k] = v #math.log(v+1)
        matrix.append(DoubleVec(dencev))

    #クラスタリング実行
    ward = Ward()
    history = ward.cluster(matrix, size)

    #樹形図をカットする
    bags = repairbags(*(cutdendrogram(history, size, dual=True)))

    #結果表示
    if html:
        print "<html>"
        print "<body>"
        for i in bags.keys():
            print "Group [", i, "]", "-"*20 #, "<br/>"
            for j in bags[i]:
                print (u"<a href='"+docs[j]["link"]+"'>"+docs[j]["title"]+u"</a>").encode("utf-8")
        print "</body>"
        print "</html>"
    else:
        for i in bags.keys():
            print "Group [", i, "]", "-"*20
            for j in bags[i]:
                print j, docs[j]["title"].encode("utf-8")
            
if __name__ == "__main__":
    import optparse
    
    parser = optparse.OptionParser(u"""
    はてなブックマークのホットエントリーの記事をなんとなーく分類します。
    """)
    parser.add_option("-H", "--html", dest="html", default=False, action="store_true",
                      help=u"結果をHTMLとして出力します。", default=False)
    (options, args) = parser.parse_args()
    
    create(options.html)