読者です 読者をやめる 読者になる 読者になる

はてなブックマークで階層的クラスタリングしてみた

前回、階層的クラスタリングの手法について解説した訳ですが、手法だけ解説するのも手抜き感がただよってたので、実際に僕のはてなブックマーク50個に対してやってみました。以下がその結果です。基本的には、近い位置にあるヤツが似たグループって扱いになります。

覚えておくと便利なgitのtipsをいくつか - Webtech Walker

UITableViewをStoryboard上でStatic Cellsみたいに使ってみる - 中継地点

ホストOSとゲストOSでファイルを共有する方法 on VirtualBox - EAGLE 雑記
Rubyでメタプログラミング 〜暗黙的に呼ばれるto_procメソッド - (゚∀゚)o彡 sasata299's blog
CLIでJSONの整形をする - ( ꒪⌓꒪) ゆるよろ日記


console.logのブラウザ別動作検証 | blog.ikekou.jp
TypeScript早わかりチートシート - Build Insider

XO: UITabBarControllerと初期化
vim使っているrubyistで、これ入れていないのはヤバいプラグインまとめ 16個 #Vim - Qiita


ハイコンセプトという古くて新しい本を読み直して目から鱗ボロボロだったのでシェア。今だから、読み直すべき。 - Wantedly 航海日誌
Rubyで "&" を使うと幸せになれるらしいよ (*´Д`)ノ - (゚∀゚)o彡 sasata299's blog

仕事で不幸な人をなくしたい─ウォンテッド仲暁子|【Tech総研】
YomanでフロントエンドとREST APIサーバーを同時に開発する方法 - bathtimefish's blog


Node.js チュートリアル | Node ビギナーズブック
TheC10kProblem - 「C10K問題」(クライアント1万台問題)とは、ハードウェアの性能上は問題がなくても、あまりにもクライアントの数が多くなるとサーバがパンクする問題のこと

Rails4で自動テスト環境を整える~cucumber&rspec&guard&spring&factory_girl | Scimpr Blog

天使やカイザーと呼ばれて » 僕が考えたRuby on RailsとDojo toolkitで作るWebアプリのデザインパターン
JavaScriptで変な形のクリック領域を作るとき、svgが便利 - MANA-DOT


KVC Collection Operators が便利っぽい - ほげほげ(仮)
Hakolog

Vimで現在のバッファ(開いているファイル)のfiletypeを取得する方法 - vimまっしぐら★ - vimグループ
最近の案件でのJavaScript開発周辺について、書いてみる | be-hase.com


海外ドラマ「フレンズ」のディクテーションとフレーズの暗記を1ヶ月続ける方法 - Higepon’s blog
Yeomanでフロントエンドとバックエンドサーバを一緒に開発する

rails3でhas_and_belongs_to_manyを利用して多対多の関係を実現する - zerozerofourの日記
Qiita「成果が出るチーム思考」の秘密――「飲みでも敬語は崩さない」「議論ありきのリーン開発」 | ベストチーム・オブ・ザ・イヤー

Node.js + WebSocket + Backbone.jsのすすめ: aticoにようこそ

この春はゆるふわ愛されObjective-Cでキメちゃおう☆ - cat /var/log/shin
Webの仕事をするなら最低限知っておくべき戦略フレームワーク×10
今っぽい Vagrant + Chef Solo チュートリアル - Qiita [キータ]


Facebook PHP SDK 解体新書 第5回「JavaScript SDK と連携してる際に適切に Access Token が取得できない問題について」 :: Crocos Engineering Blog

Beryllium Work: Best Practice of Using Angular.js with Rails: Form
rbenv で gem を使った時に rbenv rehash しなくて良くする - sorry, unimplemented:

自分の中でブレイクしている、vagrant + chef + gitで開発環境を構築する - ロックとチュウーハイとこりんがるな日々

Web-Based UML Sequence Diagram / MSC Generator
スタートアップに転職が決まって読んだ本6冊 | まにまにらいだー

backbone-railsのscaffoldを試してみる | Play Coding!
株式会社ミクシィ様と合同勉強会を開催しました。|サイバーエージェント 公式エンジニアブログ
Chaplin.js、Brunch、Railsを使ったWebアプリ開発(1)〜フロントエンドの環境構築 - Qiita [キータ]

CoffeeScriptでの存在確認演算子のコンパイル結果が2パターンある話 - Takazudo hamalog

Webサイト設計図 – ワイヤーフレームの作り方 | Webクリエイターボックス
Rubyのコードを読むのが捗る技 (Vim) #Ruby #Vim - Qiita


Mac で rbenv を使って Ruby をインストールするときに使うスクリプト - Qiita

Gemfileについて調べてみた - xxxcaqui.log
Backbone.jsをRailsで使った際の、初期設定とルール - maeharinの日記

完備辞書(簡潔ビットベクトル)の解説 - アスペ日記

JavaScript | Developers AppKitBox
PHP で “Login with Facebook” を実装する基本的な方法まとめ - 頭ん中

Functor(関手)ってなんですか? - south37のリレーブログ
jqコマンドが実は高性能すぎてビビッた話 - beatsync.net

所感

クラスタリング自体は書籍「集合知プログラミング」のコードを再利用したので簡単でした。ただ、結果が微妙というか、本当に似たサイトが近いとこに置かれてるかが微妙です...

一応、コードも載せときます。いじるとしたらmergevecjaccardの部分で、「二つの要素をどうくっつけるか」と「どう類似度を見積もるか」を変える事でで結果が変わってくると思います。自分でもいろいろ試してみたんですが、あまり上手くクラスタリングは出来なくて、結局一番シンプルな「和集合」と「jaccard」でクラスタリングを行っています。

# setはvecのarray
# vecは要素名をkey, ポイントをvalueとしたHash
def hcluster(set)
  distances = []
  cluster = set.map.with_index { |elem, id| {id: id, vec: elem[:vec], label: elem[:label]} }
  current_cluster_id = cluster.size

  while cluster.size > 1
    closest_d = Float::INFINITY
    cluster.each_with_index do |elem1, i|
      cluster[(i + 1)..-1].each do |elem2|
        next if elem1 == elem2
        id1 = elem1[:id]
        id2 = elem2[:id]
        d[id1] ||= []
        d[id1][id2] ||= jaccard(elem1[:vec], elem2[:vec])
        if d[id1][id2] < closest_d
          closest_d      = d[id1][id2]
          closest_pair ||= [elem1, elem2]
        end
      end
    end
    closest1, closest2 = closest_pair
    vec1 = closest1[:vec]
    vec2 = closest2[:vec]
    new_cluster = {vec: mergevec(vec1, vec2), id: current_cluster_id, left: closest1, right: closest2}
    current_cluster_id += 1
    cluster.delete closest1
    cluster.delete closest2
    cluster.push new_cluster
  end
  cluster[0]
end

def jaccard(hash1, hash2)
  keys1 = hash1.keys
  keys2 = hash2.keys
  and_num = (keys1 & keys2).length.to_f
  or_num  = (keys1 | keys2).length.to_f

  and_num / or_num
end

def mergevec(vec1, vec2)
  (vec1.keys | vec2.keys).map { |e| [e, 1.0] }.to_h
end

def print_cluster(cluster, offset = 0)
  if cluster[:label] then
    print cluster[:label] + "\n"
  else
    print '*' * 10 + "\n"
    print '>' * (offset - 2) + "\n" if offset > 2
    print_cluster(cluster[:left], offset + 1) if cluster[:left]
    print_cluster(cluster[:right], offset + 1) if cluster[:right]
  end
end

どうでも良い話

markdownで結果をどう表示するかにけっこう悩みました。結論としては、***で線引いて、>で階層構造つけるのがそれっぽい感じかと。もっと見易く出来たらいいんですけどね...