ボロノイ図いろいろ - kaisehのブログ
Webエンジニアバトルロワイヤルでは、平面分割手法としてボロノイ図と「疑似築道法」というものをデモしたんですが、そのとき説明に使った4種類の2次元ボロノイ図を以下に載せます。 通常のボロノイ図 「どの母点が最も近くにあるか」にもとづいて平面を分割します。ボロノイ辺は母点の垂直二等分線になります。 マンハッタン距離にもとづくボロノイ図 ユークリッド距離の代わりにマンハッタン距離を使うと、見た目ががらっと変わって、路線図や天気予報のときの都道府県図っぽくなります。 加法的重み付きボロノイ図 (Additively Weighted Voronoi Diagram) 母点にそれぞれ重みを設定して、ユークリッド距離に重みを加算したものを距離関数としてボロノイ図を作ると、ボロノイ領域を膨らませたり縮ませたりできます。ボロノイ辺は双曲線になります。 加法的重み付きべき乗ボロノイ図 (Additivel
『Blogopolisの裏側』発表資料 - kaisehのブログ
昨日のSeasar Conference 2009 Autumnで発表させていただいた『Blogopolisの裏側』の資料を公開します。 Blogopolisの裏側View more documents from kaiseh. 資料の28枚目に、重み付きボロノイ図の重心ベースレイアウトの説明用動画がありました。その動画は以下にアップしました。 講演者の皆さん、運営の皆様、本当にお疲れ様でした！ 追記 id:mi-changさん p14ででてる「頂点数」、「多角形数」って何を意味してるんだろう?頂点数が多いということはより多くのタグと結びついているってこと? これは、1つ1つのエントリーやブログ、地区（カテゴリ）に対応する土地の幾何データのことです。例えば、5角形の土地の場合は5個の頂点座標が必要になります。土地の頂点数はレイアウト上の理由で決まるもので、タグとは直接関係はありません。
適切なクラスタ数を推定するX-means法 - kaisehのブログ
K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。 これに対して、X-means法というK-means法の拡張が提案されていることを知りました。X-means法を使うと、データに応じて最適なクラスタ数を推定できます。 K-means and X-means implementations http://www-2.cs.cmu.edu/~dpelleg/download/xmeans.pdf X-means法の考え方は、K=2で再帰的にK-means法を実行していくというもので、クラスタの分割前と分割後でBIC（ベイズ情報量規準）を比較し、値が改善しなくなるまで分割を続けます。 調べたところ、Javaのデータマイニングツー
グラフ理論ライブラリのJGraphTを使ってみた - kaisehのブログ
JGraphT JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。 無向グラフ UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>( DefaultEdge.class); g.addVertex("a"); g.addVertex("b"); g.addVertex("c"); g.addEdge("a", "b"); g.addEdge("b", "c"); System.out.println(g.vertexSet()); System.out.println(g.edgeSet()); System.out.println(g.edgesOf("c"));
RDBMSをKey-Value Storageとして使う場合のパフォーマンス計測（H2, MySQL編） - kaisehのブログ
Tokyo Cabinet, QDBM, Lux IOなど、DBM同士のパフォーマンス比較はWebで良く見かけるのですが、MySQLのような普通のRDBMSをKey-Value Storage的に使用した場合、DBMと比べてどれくらい差が付くものなのかイメージが湧かなかったので、実際に計測してみました。 Javaプログラムから、Berkeley DB、H2、MySQLの3種類のストレージを使用しました。条件は以下の通りです。 Berkeley DB Java Edition 3.3.75 デフォルト設定 H2 1.1.106 jdbc:h2:file:~/dbmbench Embeddedモードで使用 デフォルト設定 DDLは以下を使用 create table casket ( id integer auto_increment primary key, key_ varchar(255
K-means法によるクラスタリングのスマートな初期値選択を行うK-means++ - kaisehのブログ
K-means法は、入力データからK個のランダムな個体を初期クラスタの中心として選択し、以降、クラスタの重心を移動させるステップを繰り返すことでクラスタリングを行う非階層的手法です。K-means法はシンプルで高速ですが、初期値依存が大きいのが弱点で、不適切な初期値選択をすると間違った解に収束してしまいます。 以下は、Introduction to Information Retrievalの16章に出てくる例です。 {d1, d2, ..., d6}をK=2でクラスタリングする場合、{{d1, d2, d4, d5}, {d3, d6}}が大域最適解ですが、初期クラスタの中心をd2, d5で与えると、{{d1, d2, d3}, {d4, d5, d6}}という誤った解に収束してしまいます。 この問題を改善するK-means++という手法を見つけたので、試してみました。 K-means+
TopHatenar＋HatenarMapsのシステム構成 - kaisehのブログ
TopHatenarとHatenarMapsのシステム構成が、バージョンアップの度に複雑化してきて、自分でも把握しづらくなってきたので、整理する意味で図を作ってみました。 図に示したように、HatenarMapsは、S2RMIを使ってTopHatenarと協調動作しています。はてなダイアリーとはてなブックマークに関するデータをクロールしているのは、TopHatenarの側です。HatenarMapsの側では、TopHatenarのService層をS2RMI経由でコールして、集計済みのはてブ情報を取得し、クラスタリング処理の後にポリゴンを計算しています。その他、HatenarMaps上でコメントビームの表示等がリクエストされる度に、TopHatenarをコールしています。よって、HatenarMaps側のDBには、基本的にポリゴンデータしか入っていません。 以下、図中に出てくるフレームワー
情報視覚化のテキスト『ビジュアライジング・データ』 - kaisehのブログ
Javaをベースとした視覚化用プログラミング言語、Processingの主要開発者であるBen Fryさんの書籍『Visualizing Data』を翻訳した『ビジュアライジング・データ』が、オライリージャパンから出版されます。 ビジュアライジング・データ ―Processingによる情報視覚化手法 作者: Ben Fry,増井俊之(監訳),加藤慶彦出版社/メーカー: オライリージャパン発売日: 2008/12/01メディア: 大型本購入: 35人 クリック: 718回この商品を含むブログ (65件) を見る 監訳は増井俊之さんです。僕も少しだけ査読校正に加わらせていただきましたので、内容を紹介します。 この本は、Processingのコードを使って、情報視覚化の手法をじっくりと解説しています。Processingは元々、プログラミング初心者向けに開発された言語なので、書籍中に出てくるサン
TopHatenar部門別トップユーザー一覧・第2版 - kaisehのブログ
TopHatenarの部門別ランキングでは、「ニコニコ動画」「nicovideo」「niconico」のように、ブックマークタグの表記ゆれによって部門が分かれてしまう場合がありました。今回、この表記ゆれを統合して、部門を再編しました。 表記ゆれの統合は、ブックマークの分布に基づいて計算しているので、今後再統合・再分離が起きる可能性があります。 今回の統合で部門が圧縮されたことで、新しく38部門が登場しました。そこで、id:takerunbaさんがまとめてくれた部門別トップユーザーの一覧の改訂版を作ってみました。ユーザ名だけでなく、タグ独占率や最多タグ獲得エントリーも載せてみました。 背景の赤い部分が、今回統合された部門です。163番の「sf」以降が、新しく登場した部門です。 ※1度目の投稿で文字数制限に引っ掛かってしまったため、再投稿しました。申し訳ありません。 番号 部門名 タグ総数 1
ニュースの可視化サイト『Newsgraphy』を公開しました - kaisehのブログ
日本のニュースを地図化して俯瞰できる『Newsgraphy』というサービスを作りました。 Newsgraphy 6月に公開して大きな反響をいただいたHatenarMapsの可視化手法を、Yahoo!のトピックスAPIから取得したニュース記事に適用して、いろいろと機能強化を施したものがNewsgraphyです。Mashup Award 4thにも応募しています。 追記（2008/9/26）: 「HatenarMapsの可視化手法を適用」と書きましたが、これは二次元平面へのマッピング手法（Voronoi Treemap）のことで、クラスタリング手法は含んでいません。Newsgraphyは、Yahoo!で分類済みのニュースカテゴリ階層を使用しています。 ニュースの可視化と言えばnewsmapが有名ですが、newsmapよりも面白くて実用性の高いサイトを目指して開発しました。 以下、Newsgra
要素の挿入、削除、ランダムアクセスが全部高速なリストを作った - kaisehのブログ
スキップリスト（Skip List）は1990年に発表された比較的新しいアルゴリズムで、要素の挿入や削除、検索を平衡木と同等のパフォーマンスで実行可能なリスト構造です。 Skip Listは連結リストの多層構成になっています。路線に例えると、最下層のリンクは各駅停車のように、全要素を結んでいます。一方、上層のリンクは急行や特急のように、途中の要素をスキップするようになっています。この路線を特急→急行→…→各駅と乗り継ぐことで、目的の要素に高速に到達できる仕組みです。もっと詳しい解説はこちらやこちらにあります。 で、ここからが本題です。Skip Listの実装はいくつも出ているんですが、Sorted Listとしての実装ばかりで、要素を任意順序で格納できてランダムアクセス（indexを指定してのアクセス）可能なSkip Listが見つからなかったので、自分で作ってみました。 通常のSkip
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
