軽量データクラスタリングツールbayon - mixi engineer blog
逆転検事を先日クリアして、久しぶりに逆転裁判1〜3をやり直そうか迷い中のfujisawaです。シンプルなデータクラスタリングツールを作成しましたので、そのご紹介をさせていただきます。 クラスタリングとは クラスタリングとは、対象のデータ集合中で似ているもの同士をまとめて、いくつかのグループにデータ集合を分割することです。データマイニングや統計分析などでよく利用され、データ集合の傾向を調べたいときなどに役に立ちます。 例えば下図の例ですと、当初はデータがゴチャゴチャと混ざっていてよく分からなかったのですが、クラスタリングすることで、実際は3つのグループのデータのみから構成されていることが分かります。 様々なクラスタリング手法がこれまでに提案されていますが、有名なところではK-means法などが挙げられます。ここでは詳細については触れませんが、クラスタリングについてより詳しく知りたい方は以下の
String::Dictionary - naoyaのはてなダイアリー
String::Dictionary という Perl のライブラリを作ってみました。 http://github.com/naoya/perl-String-Dictionary/tree/master String::Dictionary は検索エンジンその他を作る時に必要になる「辞書」のためのデータ構造 + API です。辞書は単語の集まりですが、これを配列やハッシュなどで持つのではなく、単語をすべて繋げた一つの大きな文字列として保持することでメモリ領域を節約したものです。単語は単に文字列連結で持つだけでなく、Front Coding で圧縮しています。以下簡単な解説です。 辞書は例えば [0] ･･･ jezebel [1] ･･･ jezer [2] ･･･ jezerit [3] ･･･ jeziah [4] ･･･ jeziel ...という風に単語を配列で持つことで実現でき
k-means++を試し中 - のんびり読書日記
http://d.hatena.ne.jp/kaiseh/20090113/1231864089 上の記事を見て、k-means++が面白そうだったので、ちょっとだけ試してみた。 k-meansは初期値に大きく依存するところが嫌い。初期値への依存度を軽減するために、初期値を変えて何回か試行してその中で一番良い結果のものを使用する、なんてことをしないといけない。そのため処理時間も馬鹿にならなくなってしまうので、ちょっとこれじゃあなあ…ということで使ってなかった。 でも今回のk-means++は初期値をうまく求めることで、精度と速度の向上が得られるらしい。これはうれしい！ 論文著者のページにサンプルコードがあったので試してみようと思ったんだけど、MFCを使っているみたいで僕の環境ではコンパイルできず…。 http://www.stanford.edu/~darthur/kMeansppTest
クラスタリング (クラスター分析) - Toshihiro Kamishima
クラスタリング (clustering) とは，分類対象の集合を，内的結合 (internal cohesion) と外的分離 (external isolation) が達成されるような部分集合に分割すること [Everitt 93, 大橋 85] です．統計解析や多変量解析の分野ではクラスター分析 (cluster analysis) とも呼ばれ，基本的なデータ解析手法としてデータマイニングでも頻繁に利用されています． 分割後の各部分集合はクラスタと呼ばれます．分割の方法にも幾つかの種類があり，全ての分類対象がちょうど一つだけのクラスタの要素となる場合(ハードなもしくは，クリスプなクラスタといいます)や，逆に一つのクラスタが複数のクラスタに同時に部分的に所属する場合(ソフト，または，ファジィなクラスタといいます)があります．ここでは前者のハードな場合のクラスタリングについて述べます．
人物情報検索のトレンドご紹介 part3 テキストマイニング技術について
ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog こんにちは、Yahoo! JAPAN 研究所の山下達雄です。 今回は「Yahoo!人物名鑑」の一要素である「関連人物モジュール」について技術的な解説をしていきたいと思います。よろしくお願いします。 関連人物モジュールは、人物名鑑のページの右カラムにある「関係ありそうな人物名」で使われています。 例）妻夫木聡さんの場合 ウェブ上のさまざまなテキストデータを分析して、人物同士の関連度を計算し、その関連度の高い人物をタグクラウド形式で表示しています。 関連度の計算には様々なテキストマイニング的な手法を用いていますが、ここではウェブ検索を利用した簡単で効果的を方法を説明します。 ■処理の流れ 分かりやすくするため、関連人物ではなく関連語を
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
How Not To Sort By Average Rating
By Evan Miller February 6, 2009 (Changes) Translations: Dutch Estonian German Russian Ukrainian PROBLEM: You are a web programmer. You have users. Your users rate stuff on your site. You want to put the highest-rated stuff at the top and lowest-rated at the bottom. You need some sort of “score” to sort by. WRONG SOLUTION #1: Score = (Positive ratings) − (Negative ratings) Why it is wrong: Supp
情報検索ことはじめ〜研究者編〜 - シリコンの谷のゾンビ
昨年書いた教科書編が（僕にとっては）嬉しくて跳ね上がるほどブックマークされたので，調子に乗って第二弾を書いてみました．皆様ありがとうございます（ブックマークにがんばってくださいというコメントがあったのがめちゃくちゃ嬉しかったです）．今回は研究寄りですが，少しでも誰かの役に立てば幸いです． 僕は網羅的にサーベイを，キーワード検索以外に主に二つの方法で行っています． 会議毎にサーベイ 研究者毎にサーベイ 1.はさておき，2.ですが，僕は研究者のDBLPをチェックしています．気になる論文の著者のDBLPを眺めると，知らなかった要チェックや！論文を拾うことができます． なので，一線で活躍する研究者の論文は定期的にチェックする必要があります． 今回はIR研究者の中でも，戦闘力が高く，この人は常にウォッチせねばという研究者の一部を紹介したいと思います． 下記は若輩の独断と偏見に基づくものです．一線で活
本文抽出モジュールを RubyForge に登録しました (nakatani @ cybozu labs)
以前このブログで公開していました Web ページ(HTML)から本文と思わしきテキストを抽出するモジュールを RubyForge に登録、 gem でインストールできるようになりました。 gem install extractcontent といっても、このモジュールは１ファイルで構成されていて、依存関係もないので、以前の公開方法のままでもあまり支障はなかったような気もするんですが、RubyForge に登録する練習もしておきたかったし、gem で入れられる方が便利ですよね？ ExtractContent プロジェクトページ http://rubyforge.org/projects/extractcontent/ 一応プロジェクトページの URL も貼り付けておきますが、実質リリースファイル置き場でしかなくて、SCM もまだ使ってません…… また、せっかくリリースするので、 ・「全然 m
AIRS Labs: Railsで簡単にベイジアンフィルタを使えるacts_as_classified
インターンの増田です。 ActiveRecordのデータを使ってベイジアンフィルタを使う必要があったので、この部分をプラグインActs as classified として抜き出してみました。 インストール 依存しているライブラリをインストールします。 gem install classifier stemmer プラグインをインストールします。 ./script/plugin install svn://rubyforge.org/var/svn/actasclassified/trunk/acts_as_classified また、日本語のデータを学習に用いる場合はMeCab とそのRubyバインディングをインストールします。 日本語は(DB, MeCabともに)UTF-8を対象にしています。 使い方 分類したいモデルでacts_as_classifiedとします。 class Arti
ソートアルゴリズムの可聴化 - ならば
Sorting Algorithm Animationsなどのサイトでは、ソートアルゴリズムの可視化の例を見ることができる。今回は可視化に倣ってソートアルゴリズムを可聴化した。聴覚化すると、情報を分かりやすく提示するという方向から外れるけど。 ソートする対象は50から90までの整数をランダムに並べた列。可聴化の方法は、整数をMIDIノート番号とみなして、ソートアルゴリズムが各時点でポイントしている位置にある、MIDIノート番号の音高の音を鳴らすようにした。ChucKのプログラムはいつもより長くなったから最後に載せる。 録音したもの。元の整数列は全部同じで、サイズ（整数の数）は30。 バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート 拡張としては、 より詳細に情報を提示する方向（例：整数同士の位置の交換時に音色を変える） サウンドアートな方向（例
Bayesianって<br>どういう考え方なんだろう
*********** お知らせ *********** YukiWikiによるベイズ統計ファンサイト を開設しました。 このページ「Bayesianってどういう考え方なんだろう」は、 以上のファンサイトへ発展的解消いたします。 どうぞご贔屓に！ ********************************* ベイズ理論は、 普通の確率論とは一風異なる確率理論です。 この小文では、ベイズ理論の意味・意義について 私がこれまでに学び、考えたことについて整理を試みます。 とかく、＜宗教的信念＞のごとくに扱われがちのベイジアン思想ですが そのおかしいところ、よいところなど、基準を明確にして検証していけたら いいな、というのが目標です。 私自身勉強中の身なので定説と異なることを述べていたり、 明らかな間違いもあるかもしれません。 そのつもりでだまされ
しかしSVMも最近は速いらしい - 射撃しつつ前転 改
Complement Naive BayesがSVMより速いよーと主張していたので、SVMもなんか最近は速くなってるらしいよ、という事を紹介してみたい。近年はSVMなどの学習を高速に行うという提案が行われており、実装が公開されているものもある。その中の一つにliblinearという機械学習ライブラリがある。ライブラリ名から推測できる通り、liblinearではカーネルを使うことが出来ない。しかし、その分速度が速く、大規模データに適用できるという利点がある。 liblinearを作っているのはlibsvmと同じ研究グループで、Chih-Jen Linがプロジェクトリーダーであるようだ。libsvmはかなり有名なライブラリで、liblinearにはそういった意味で安心感がある。（liblinearの方は公開されてしばらくは割とバグがあったらしいけど。） liblinearにはL1-SVM, L
楽天も情報爆発しています - 武蔵野日記
楽天テクノロジーカンファレンスには行かれなかったのだが、大規模分散処理フレームワークの設計、実装が進行中 -- 楽天版MapReduce・HadoopはRubyを活用などを読むと、けっこうおもしろそうだったのだな、と分かる。 楽天技術研究所がどういう位置づけなのかは分からないが、こういう基盤技術の開発を支援しているというのは評価していいと思う。(車輪の再発明という気がしないでもないが) 個人的な興味としては楽天が大規模データに対してどういうことをしているかということなのだが、記事を見るといろいろ書いてある。 計算モデルがシンプルでも規模が巨大になるとまったく別の問題が生まれてくる。処理すべき情報量が爆発的に増加しているからだ。 例えば協調フィルタリングではユーザーを縦軸に、商品アイテムを横軸にした購買履歴マトリックスについて計算処理を行う必要があるが、あまりに量が多く、素直に実装すると「2
suffix array
更新履歴 2004/01/07 O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報（例えば、単語の出現回数など）を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。 また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分（例えばCCAG）を調べるといった場合
Purely Functional Data Structures
Most books on data structures assume an imperative language such as C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures from the point of view of functional languages, with examples, and presents design techniques that allow programmers to develop their own functiona
t.dvi
Purely Functional Data Structures Chris Okasaki September 1996 CMU-CS-96-177 School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy. Thesis Committee: Peter Lee, Chair Robert Harper Daniel Sleator Robert Tarjan, Princeton University Copyright c 1996 Chris Okasaki This research was sponso
David MacKay: Information Theory, Inference, and Learning Algorithms: The Book
Information Theory, Inference, and Learning Algorithms (Hardback, 640 pages, Published September 2003) Order your copy Price: £35.00 / $60.00 from |CUP UK/USA| |amazon.co.uk/.com/.ca/.co.jp| | Barnes & Noble USA | booksprice. | fetchbook.info | allbookstores | biggerbooks | blackwells | directtextbook | kalahari.net (South Africa) | Special Paperback edition for South Asia.| Download the book too
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
