untitled
辻井研演習３ 単語クラスタリングの諸考察 岡野原 大輔 04/05/24 1 背景 集合中の要素を、それらの間で定義される類似度や全体の整合性を基準にして似ている要素同士で分類する クラスタリング技術は多くの分野において、有効であることが示されてきた。自然言語処理分野においても、 単語を分類したり、文書を分類するなど、多くのケースで使用されている。 単語を Class に分類することの利点は、N-gram などの学習において、推定すべきパラメーター数に対し、 得られる情報が少ない場合に起こる Sparseness の問題が、Class N-gram を用いた補間 [2] によって解決さ れ、より頑健なモデルとなり、言語モデルの精度が向上することが挙げられる。他の利点として、文書クラス タリングにおいて、文書中の単語の出現状況を各文書の feature として用いて分類する場合、単語数
Power Iteration Clustering - tsubosakaの日記
岡野原さんのtweetで紹介されていたPower Iteration Clusteringという文章分類の手法に関する論文[1,2]を読んでみた。 背景 n個のデータX={x_1,...,x_n}が与えられたときに各データ間の類似度s(x_i,x_j)を成分に持つ類似度行列Aを考える。 また次数行列としてAのi行目の値を合計したd_{ii} = \sum_j A_{ij}を対角成分にもつ対角行列をDとする。 このときW:=D^{-1} Aをnormalized affinity matrixと定義する。簡単のためWはフルランクであるとする。 この行列はすべての要素が1となる固有ベクトルをもち、この時固有値は1となる。実はこれが最大固有値である(行列Aの行和が1となること+Gershgorin circle theorem(en)より導かれる)。また、行列Wの固有値を1=λ_1>=...>=
Streaming k-means approximation - tsubosakaの日記
実家に帰省中，電車の中で読んでた論文の紹介。 概要 k-meansはクラスタリングテクニックとして非常に基本的な手法である。 しかし、k-meansでは全データに対してラベリングを複数回繰り返す必要があり、全データ点を保存する必要がある、そこでk-meansの出力であるk個のクラスタ中心をワンパスで見つける方法を提案する。 ここで得られるクラスタ中心は最適値と比較したときにO(log k)の近似となっている ストリームアルゴリズムについて 本論文で言っているStreamingの意味としては入力を前から見ていって、すべて保存しないアルゴリズムのことを言っている。いわゆるオンラインアルゴリズムのように入力が入ってくるたびに何かしらの結果が得られるわけではない。また，ストリームの長さは有限である事を仮定している。 k-meansとは k-meansとはデータ点 X = {x_1 , ... x_
Tag Hierarchyをつくったよ
来年も作りたい！ふきのとう料理を満喫した 2024年春の記録 春は自炊が楽しい季節 1年の中で最も自炊が楽しい季節は春だと思う。スーパーの棚にやわらかな色合いの野菜が並ぶと自然とこころが弾む。 中でもときめくのは山菜だ。早いと2月下旬ごろから並び始めるそれは、タラの芽、ふきのとうと続き、桜の頃にはうるい、ウド、こ…
k-means++を試し中 - のんびり読書日記
http://d.hatena.ne.jp/kaiseh/20090113/1231864089 上の記事を見て、k-means++が面白そうだったので、ちょっとだけ試してみた。 k-meansは初期値に大きく依存するところが嫌い。初期値への依存度を軽減するために、初期値を変えて何回か試行してその中で一番良い結果のものを使用する、なんてことをしないといけない。そのため処理時間も馬鹿にならなくなってしまうので、ちょっとこれじゃあなあ…ということで使ってなかった。 でも今回のk-means++は初期値をうまく求めることで、精度と速度の向上が得られるらしい。これはうれしい！ 論文著者のページにサンプルコードがあったので試してみようと思ったんだけど、MFCを使っているみたいで僕の環境ではコンパイルできず…。 http://www.stanford.edu/~darthur/kMeansppTest
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+
お気に入りに入れる条件って
お気に入りに入れる条件って どういう人を はてブのお気に入り に入れるべきかというのは実は難しいんじゃないか。 その基準がどうにも明らかでないと、お気に入りに入れるべき人を自動で推薦、 みたいなのって意味がないと思うのだけど、どうなんでしょ。 第2回SBM研究会 の会場で大西さんにそういう質問したんだけど、 つまり「類似度の高い人を推薦」つったって、 類似度が最大、つまり完全に同じものをブクマしている人をお気に入りに入れても、 それって意味あるの？ という問題。 類似度の計算はいろいろあるみたいなんだけど、 それはとりあえず置いておいて、とにかく類似度が計算できるとしましょう。 そんで、なんで類似度が高くなるのかというと、 二人が同じところを巡回しているからだ、というのはあるんじゃないか。 はてブのホッテントリから同じようにピックアップしてブクマしてたら、 そりゃ傾向が似るでしょうと。 R
文書クラスタリングの技法ゼミ
III. 文書クラスタリングの技法 A. 単一パスアルゴリズム 1. k-means 法の適用 2. Willett のアルゴリズム 3. 平均クラスタリング・アルゴリズム
FrontPage - 情報論的学習理論と機械学習の「朱鷺の杜Wiki」
朱鷺の杜Wiki（ときのもり うぃき）† 朱鷺の杜Wikiは，機械学習に関連した，データマイニング，情報理論，計算論的学習理論，統計，統計物理についての情報交換の場です．これら機械学習関係の話題，リンク，関連事項，書籍・論文紹介などの情報を扱います． 更新されたページを確認するにはRSSリーダを使って右下のRSSリンクをチェックするか，最終更新のページを参照してください． ページの中でどこが更新されたかを見るには，上の「差分」をクリックして下さい． 数式の表示に MathJax を利用しています．数式の上でコンテキストメニューを使うと各種の設定が可能です．特に設定をしなくても数式は閲覧できますが，フォントをインストールすれば数式の表示がきれいで高速になります．詳しくは 数式の表示 のページを参照して下さい． ごく簡単なWikiの使い方がこのページの最後にあります．トップページやメニューなど
Fuzzy c-Means法
ここまでは，ある個体がクラスターに属するか否かの二者択一の問題を考えていたが，現実世界の問題を考えた際には，ある個体が唯一のクラスターに完全に属するという状況の他にも，複数のクラスターにある程度ずつ属しているという状況もしばしば存在する．そこで，個体のクラスターへの所属の度合いをあいまいに表そうとするファジィクラスタリングが提案されている． ある個体（人物）を二つのクラスターに分類することを考えよう．もし，二つのクラスターが「男」と「女」のグループに対応しているとするならば，その個体はいずれか一方のクラスターに所属し，もう一方には該当しないだろう．しかし，二つのクラスターが「野球」と「サッカー」に対応するグループであり，クラスターへの所属がその個体の嗜好を表す場合であったなら，どうなるであろうか．どちらかといえば「野球」が好きだが，「サッカー」もある程度好むということもあり得る． おのおの
rep.dvi
Markov Cluster Algorithm Web † † Web Web Kleinberg HITS Web Web HITS Web Markov Cluster Algorithm ( ) Web The Discovery Method of Multiple Web Communities with Markov Cluster Algorithm Kazutami KATO† and Hiroshi MATSUO† A web community is a set of web pages created by individuals or associations with a common interest on a topic. Kleinberg’s HITS algorithm find a web community on a query topic by
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
はてなブログ | 無料ブログを作成しよう
はてなブログ | 無料ブログを作成しよう
CiteSeerX
はてなブログ | 無料ブログを作成しよう
はてなブログ | 無料ブログを作成しよう
Clustering of time series data—a survey - ScienceDirect
データマイニング分野のクラスタリング手法（1） (application/pdf オブジェクト)
accelerated PBN : 混合ガウス分布によるクラスタリングを実装するときは・・・
accelerated PBN : LIBLINEARってご存知でした？