第９回 データマイニング+WEB 勉強会＠東京に参加してきた - nokunoの日記
というわけで行ってきました。第９回 データマイニング+WEB 勉強会＠東京 ( TokyoWebmining 9)?1st Week? 大規模解析・機械学習・クオンツ 祭り? : ATNDFirst Weekって。■大規模解析：1. Mahout Canopy Clustering (講師：@hamadakoichi)(発表30分＋議論60分) Canopy Clusteringは通常の多くの手法と異なり、クラスタ数指定を必要とせず、指定距離 離れたクラスタ算出を実現する。 Hadoop上で動作する大規模データマイニング・機械学習ライブラリ Mahoutでの実行法も含めお話しします2. 機械学習＝機械の代わりに人間が学習 (講師：@shuyo))(発表20分＋議論40分) Gihyo.jp でも機械学習の連載し裾野を広げる活動をされている @shuyo さん。 今回、機械学習の歴史や専門外
Redisのクラスタリング — redis 2.0.3 documentation
New in version 2.2. Redisでは、実際にクライアントと通信をするポート以外に、サービス用チャンネルを開いてすべてのノードはこのチャンネルを使って直接接続しあいます。TCPのベースのポート+4000番が使われるため、クライアント向けに6379番のポートを使用している場合には、10379番を使用します。ノード間の通信には、バンド幅と速度に最適化されたバイナリプロトコルを使用します。クライアントとの通信では通常はアスキープロトコルを使用しますが、いくつか変更があります。ノード同士は、クエリーをプロキシー(転送)することはありません。 ノード間の通信内容¶ 各ノードは、PING/PONGと同時に、自分が通信した上で判断した周辺ノード情報(Gossip/うわさ話)も一緒に送信します。
K-means and X-means implementations
K-means and KD-trees resources Read the K-means paper (PS), or K-means paper (PDF) . Note: recently a similar, though independent, result, was brought to our attention. It predates our work. For completeness, you can read that too. Read the X-means paper (PS) or X-means paper (PDF). The X-means and K-means implementation in binary form is now available for download! Currently, there are versions f
pLSI をハードクラスタリングに使おうとしたけどイマイチだった - nokunoの日記
きっかけはPythonでpLSA(pLSI)を実装している人がいたので、文書クラスタリングに使えないかな、と考えたことでした。satomacoto: PythonでPLSAを実装してみるただpLSIはいわゆるソフトクラスタリングで、以下のような問題がありました。 結果の解釈が直接しづらい 処理時間がかかるこのうち1つ目の問題は文書が与えられたときのクラスタへの所属確率 P(z|d) の最大値を取ってハードなクラスタリングの結果を得れば解決します。しかし、処理時間のほうはEMアルゴリズムの途中で0でないパラメータが多いことが原因なので、単にP(z|d)をハード化しても他のパラメータ （P(z|w,d)など） がなくならないのでイマイチでした。そこで P(z|w,d), P(w|z), P(d|z) の各パラメータをハード化することで高速化できないかなと考えたのですが、結果はかなり劣化してしま
[機械学習] クラスタリングにおけるコサイン類似度に関する性質の証明 - tsubosakaの日記
bayonやCLUTOが爆速な理由 - download_takeshi’s diaryを読んで、すぐには成り立つかどうか分からなかったので証明してみた。 上の記事で述べられていることはクラスタ中のベクトルとその中心ベクトルのコサイン類似度の和と、クラスタ中のベクトルを全て足したベクトルのノルムが一致するというである。 ただしここでクラスタ中の要素ベクトルはすべて大きさ1の規格化されたベクトルであるとする。 証明 今クラスタ内に含まれるベクトルを とする。 このとき全ベクトルを足しこんだ複合ベクトルを とする。またこのクラスタのセントロイドは となる。このときセントロイドと各ベクトルとのコサイン類似度は [tex: s_i = \frac{}{||C|| ||x_i||} = \frac{}{||{C}||}] となる。ここでと正規化されていることを用いた。この類似度の合計は [tex:
![[機械学習] クラスタリングにおけるコサイン類似度に関する性質の証明 - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/437ae042a71338c391758f2afa29457c5ff0c015/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030345%2F1557332441)
bayonやCLUTOが爆速な理由 - download_takeshi’s diary
クラスタリングツールbayonを使っていて、常々「どうしてこんなに高速に処理できんのかなぁ」と疑問に感じていました。repeated bisectionという手法自体がk-means法などと比べると効率がいいのですが、それにしても、それだけでは説明がつかないほど爆速なわけです。 うまく例えられませんが、自前でk-meansのスクリプトを書いて比べてみると、自転車と新幹線くらいちがうという印象です。はじめてCLUTOを触った時、数万件程規模のクラスタリング処理が本当に「あっ」という間に終わってしまい、びっくりした記憶があります。 きっと実装面でなにか特殊なことがあるんだろうなと思い、mixiエンジニアブログでbayonの記事を改めて読み漁っていたら、以下の部分が目に止まりました。 このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほど
スペクトラルクラスタリングは次元圧縮しながらKmeansする手法 - 武蔵野日記
機械学習系のエントリを続けて書いてみる。クラスタリングについて知らない人は以下のエントリ読んでもちんぷんかんぷんだと思うので、クラスタリングという概念については知っているものとする。 それで、今日はスペクトラルクラスタリングの話。自然言語処理以外でも利用されているが、これはグラフのスペクトルに基づくクラスタリングの手法で、半教師あり学習への拡張がやりやすいのが利点。なにをするかというとクラスタリングをグラフの分割問題(疎であるエッジをカット)に帰着して解く手法で、どういうふうに分割するかによって Normalized cut (Ncut) とか Min-max cut (Mcut) とかいろいろある。 完全にグラフが分割できる場合はこれでめでたしめでたしなのだが、実世界のグラフはそんな簡単に切れないことが往々にしてある。それで近似してこのグラフ分割問題を解くのだが、Normalized c
『Blogopolisの裏側』発表資料 - kaisehのブログ
昨日のSeasar Conference 2009 Autumnで発表させていただいた『Blogopolisの裏側』の資料を公開します。 Blogopolisの裏側View more documents from kaiseh. 資料の28枚目に、重み付きボロノイ図の重心ベースレイアウトの説明用動画がありました。その動画は以下にアップしました。 講演者の皆さん、運営の皆様、本当にお疲れ様でした！ 追記 id:mi-changさん p14ででてる「頂点数」、「多角形数」って何を意味してるんだろう?頂点数が多いということはより多くのタグと結びついているってこと? これは、1つ1つのエントリーやブログ、地区（カテゴリ）に対応する土地の幾何データのことです。例えば、5角形の土地の場合は5個の頂点座標が必要になります。土地の頂点数はレイアウト上の理由で決まるもので、タグとは直接関係はありません。
画像研究入門
【目次】 ０．Ｃ言語基礎 ０－１．本当の基礎 ０－２．配列とポインタ ０－３．文字列操作・ファイル操作 １．画像基礎 １－１．画像フォーマット １－２．テキストとバイナリ １－３．配列とポインタ ２．画像処理基礎 ２－１．エッジ処理 ２－２．背景差分処理 ３．グラフ描画基礎 ３－１．ｇｕｎｐｌｏｔ ３－２．折れ線グラフ ３－３．ヒストグラム表示 ４．アルゴリズム基礎 ４－１．ｋ－平均アルゴリズム ４－２．ＥＭアルゴリズム ５．画像表示基礎 ５－１．ＯｐｅｎＧＬ ５－２．ＯｐｅｎＧＬによる二次元表示 ５－３．ＯｐｅｎＧＬによる三次元表示 はじめに これから画像処理・認識の研究を始めようという人を対象とした入門書を作っています．対象は研究室に配属されたばかりの情報系大学の４年生を想定していますが，誰が読んでも分かるように心がけているつもりです．読み進めながら課題を解いていくうちに画像の基礎知識
クラスタリングツール「bayon」を試してみた - download_takeshi’s diary
夜中の3時半過ぎですが、久しぶりになんか書こうと思います。 ちょっと前にmixiのfujisawaさんという方がすごくナイスなソフトウェアをリリースしてくれました。 「軽量データクラスタリングツールbayon」 http://alpha.mixi.co.jp/blog/?p=1049 今までにもCLUTOというすごく高精度なクラスタリングツールがありましたが、こいつはライセンス的にちょっとイケズな感じでした。そこにbayonがスーパーマンのように登場してくれました！「商用利用OKだよ」ということで、仕事の上での悩みが解決しました。本当にありがたいことです。 さてさて、早速使ってみたいんですが、ブログに書くのにちょうどいい題材がなかったので、以前に自分が書いたエントリからデータを持ってくることにしました。 「芸能人の相関関係を探ってみるスクリプト」 http://d.hatena.ne.jp
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
ニコニコ動画の大規模なデータに対するタグ付けとリンク解析 - 武蔵野日記
ニコニコ動画データ分析研究発表会というのが開催されていたようだ。 タイトルや説明文はノイジーなので、動画につけられたタグを使うと割ときれいなデータとして可視化したりできる、という話は、はてなブックマークの関連エントリー機能のときも聞いたような話で、基本的にはインターネットユーザに無料でデータのタグ付けをしてもらっている、という話なんだろうな、と思う。以前紹介したRion Snow の論文 (彼は2005年に Microsoft Research でインターンし、2006年に Powerset (現在は Microsoft に買収済み)、2007年には Google でインターンした人物。ACL という自然言語処理のトップカンファレンスで2006年にベストペーパー受賞)で、 今年の Rion Snow のトークは、Amazon Mechanical Turkというシステムを使って、非常に安価
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) とも呼ばれ，基本的なデータ解析手法としてデータマイニングでも頻繁に利用されています． 分割後の各部分集合はクラスタと呼ばれます．分割の方法にも幾つかの種類があり，全ての分類対象がちょうど一つだけのクラスタの要素となる場合(ハードなもしくは，クリスプなクラスタといいます)や，逆に一つのクラスタが複数のクラスタに同時に部分的に所属する場合(ソフト，または，ファジィなクラスタといいます)があります．ここでは前者のハードな場合のクラスタリングについて述べます．
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+
Introduction to Information Retrieval #16 の復習資料 - naoyaのはてなダイアリー
しばらく間が空いてしまいました。Introduction to Information Retrieval 輪読会 16章の復習資料を以下にアップロードしました。 http://bloghackers.net/~naoya/iir/ppt/iir_16.ppt 16章のテーマは、"Flat Clustering" で話題はクラス分類からクラスタリングへと移ります。16章ではクラスタとクラスタの間に関係性がないフラットクラスタリングを扱い、続く 17章ではクラスタ間に階層的構造を見出す階層型クラスタリング (Hierachical clustering) を扱います。 クラスタリング 13章から15章までは Naive Bayes や SVM などによる "Classification" が話の主題でした。クラスタリングも同様に情報のグルーピングを行うものですが、Classification
アルゴリズム設計 講義資料 2005
Algorithm Design Course Materials 2013 Oct 7: Introduction and Computational Complexity Oct 15: Search Trees Oct 21: Combinatorial Optimization Oct 28: Heuristic Search Nov 5: Text Search Nov 11: Data Compression Nov 18: Memory Management Nov 25: Graph Algorithms 1/2 Dec 2: Graph Algorithms 2/2 Dec 9: Computational Geometry Dec 16: Concurrency Control Jan 15: Canceled Jan 20: Clustering Course Pro
GoogleNewsのレコメンドの中身 - UMEko Branding
先日、全体ゼミで発表したときの内容ですが、ここにまとめときます。。GoogleNewsのレコメンドの中身を追った論文の要約です。少し前の全体ゼミで用いた資料です。ソース：Abhinandan Das,Mayur Datar,Ashutosh Garg,Shyam Rajaram,"Google News Personalization: Scalable OnlineCollaborative Filtering",WWW2007不勉強な個所が多々ありますので、誤っている箇所等ありましたら、是非ご指摘ください。 個人的には、最近のモデルベースの手法の勉強・おさらいという意味で用いているので、GoogleNews独自の拡張なり実装の部分の内容が省かれている場合があります。また、データ構造やMapReduceを用いた計算の仕組みの部分は、ここでは省略しています。。一応、 全体像 ・LSH(Lo
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
はてなブログ | 無料ブログを作成しよう
はてなブログ | 無料ブログを作成しよう