Microsoft PowerPoint - 12Clustering(2).ppt [互換モード]

Transcription

1 k-meas クラスタリング : 定式化 知的情報処理. 仲間を集めるクラスタリング () 入力 : 個の点からなる集合 V パラメータ k 出力 : k 個の点 ( クラスタの中心 ) からなる集合 X で すべての可能な X のなかで 二乗歪 (squared error dstorto) d(vx) が最小のもの 櫻井彰人慶應義塾大学理工学部 二乗歪 -Meas クラスタリング : やさしい場合 点 v と点集合 X が与えられたとき v から X への距離 Iut: 個の点からなる集合 V d(v X) は v から X の最近接点へのユークリッド距離であるとする. 個の点からなる集合 V={v v } と点集合 X が与えられたとき 二乗歪 Squared Error Dstorto は次のように定義される Outut: ある一個の点 ( クラスタ中心 ) で のすべての可能な選び方のなかで 二乗歪 d(v) が最小となるもの -Meas クラスタリングはやさしい問題. しかし 中心 ( クラスタ数 ) が 個以上となると とたんに難しい問題 (NP- 完全 ) となる. 効率のよい発見的方法の一つに Lloyd アルゴリズムがある d(vx) = d(v X) / < < K-Meas クラスタリング : Lloyd アルゴリズム. Lloyd アルゴリズム. 任意に k 個のクラスタ中心を選ぶ 3. whle クラスタ中心が変更された 4. 各データ点をクラスタ C に割り当てる割り当てるクラスタは 最も近いクラスタ中心のクラスタ ( k) 5. すべての点への割り当てが終わったら 各クラスタの重心を新たなクラスタ中心とするすなわち 新たなクラスタ中心は クラスタ C それぞれに v / C 全 v C * このアルゴリズムは局所解に陥ることがある. 座標軸 座標軸

2 座標軸 3 座標軸 座標軸 座標軸 5 クラスタリング demo 座標軸 4 3 htt://home.de.olm.t/matteucc/cluster/tutoral_html/aletkm.html htt:// 3 htt://tech.toyo.com/ja/blo/009/04/09/kmeas-vsualse/ 座標軸 統計的な枠組み ガウス混合分布 : または 6 個のクラスタがありそう (?) クラスタを正規分布でモデル化しよう複数個の取り扱いはどうする? 前提をおく : 観測値はある混合分布からのサンプルである () = () 各クラスタは混合分布を構成する個々の分布に対応する

3 3 = [0 0] = [0 0] = [0 0] = I = 0.6I = I ガウス混合分布 フィッティング : と () のパラメータ ( 平均 分散等 ) を推定する尤度最大化ガウス混合分布 ( ガウス分布の重み付き線形和 ) をフィッティングする各 はいずれかの分布 ( クラスタ ) に属すると考える 対数尤度を最大化する () を求める L lo lo lo 尤度最大化の困難点 変更 : 対数尤度を最大化する ( ) を求める 困難点 ( 等式制約もあるが ): L lo lo lo L lo θ π 考え方を変える 各 は 番目の分布から得られたと考える そうすると L lo lo lo θ π : : lo L θ π lo どのクラスタに属するか? しかし 各 は 番目の分布から得られた とする は知りようがない ここで を適当に仮定する ( そして 各分布のパラメータを最尤推定し それから を推定することを繰り返す ) のが k-meas 法 EM アルゴリズムが考えられた 各点 が各分布 に属する確率 ( = となる確率 ) を求める ( )/ 正規化定数を計算する これらの確率をもとに 周辺尤度を最大化するパラメータを求める のパラメータを最尤推定する という反復計算 一般には 局所最適解に収束

4 EM- アルゴリズムの実行イメージ K-Meas クラスタリングとの比較 EM アルゴリズムの長所と短所 長所 統計的基盤 理論的に健全 信頼性等が計算可能 検定もできる 短所 計算が大変 世の中のものに 分布 を予め仮定するのが妥当か 現実問題への適用に際し その妥当性に疑問がある場合が多い 再 : クラスタリング方法の分類 階層的クラスタリング : ある基準に従って 階層的に対象 ( データ ) の集合を分割していく 非階層的クラスタリング モデル法 : 各クラスタに ( 統計的 ) モデルを仮定し データに最もあうように パラメータを決定する 分割的クラスタリング : いくつかの分割を作成し ある基準に従い評価する 濃度に基づく : 濃度 密度 結合度に基づく グリッド法 : 多層の粒度構造に基づく 例 : 文書分類はできるか? 実は できない! クラスタリングするには 各文書をなんらかの数値ベクトルで表現しないといけない どうやる? 文書クラスタリング 普通は次のように行う 文書を単語に分ける 例 : 明日は晴れでしょう 明日 + は + 晴れ + で + しょう + どこにでもある単語 ( at s a ) ははずす なぜでしょうか? 余りにも特殊な単語ははずす なぜでしょうか? 文書ごとに文書の特徴ベクトルを作る 各単語に番号を振り その番号を場所とするベクトルである 各要素は 当該文書中に出現する当該単語の回数 ( または 0/) 文書を点 この特徴ベクトルをその点の座標と考えて クラスタリングを行う 4

5 文書クラスタリング : 困ること ベクトルの次元が極めて高くなる 短い文書 ( 実験を行う ewsrou への投稿記事でも ) かつ少ない文書数でもすぐ数千 数万になる すなわち 数千次元 数万次元 人間が図で見れるのは多くて 3 次元 検索エンジンへの適用例 企業内での活用例はあるようである 検索エンジンとしては 様々な要素がからむため 成功していないのが実情である 実は 高次元 というのはいろいろな問題を引き起こす要因である 計算に時間がかかる ( いくらメモリが とか とかいっても ) メモリ不足 実は ベクトルの距離の定義が難しくなる ユークリッド距離は適さなくなってしまう Vvsmo (006) Vvsmo (006) Vvsmo (007) Clusty (007) htt://vvsmo.com/ 5

6 Mooter(006) Mooter(006) htt:// Mooter(006) Mooter (007) htt:// Mooter (007) rokker (005) htt:// 6

7 rokker (005) rokker(006) htt:// rokker (007) rokker (007) htt:// rokker (007) Yy ( Vvsmo & Clusty) (00-0) 7

8 Yy (0) Vvsmo (0) Mooter (00-0) Mooter (0) 次元の呪い : これは実問題の問題 高次元の実データ例 MoveLes Curse of dmetoalty という コンビニの売り上げデータを考えよう 一回の売り上げを一個のベクトルであらわす Ecel の表なら 横 行が一回の売り上げ ベクトルの各要素は 各商品に対応する Ecel の表なら 縦 行がある商品一個に対応 ある一年を考えるだけでも 数千 数万行が必要 次元が数千 数万のベクトル 数年分を管理しようと思えば 数万 数十万行 次元が数万 数十万のベクトル 全ユーザ 数量化 3 類適用後 acto adveture amato/chldre comedy crme documetary drama fatasy flm-or horror muscal mystery romace SF thrller war wester 8

9 y y 高次元の実データ例 MoveLes 女性 8 歳 ~4 歳 数量化 3 類適用後 acto adveture amato comedy crme documetary drama flm horror muscal mystery romace SF thrllar wester クラスタ数の推定 適切なクラスタ数はどうやって推定するか? cross valdato ( 交叉検定 ) 評価基準は 各点の対応するクラスタ中心までの距離の和 情報量規準を用いる AIC: 赤池情報量基準 BIC: ベイズ情報量基準 Mclust ではモデルの選択に BIC を用いている htt:// R における cluster > # k-meas stats ackae > # > <- rbd(matr(rorm(00 sd = 0.3) col = ) + matr(rorm(00 mea = sd = 0.3) col = )) > colames() <- c("" "y") > (cl <- kmeas( )) K-meas cluster wth clusters of ses 49 5 パッケージとしては stats ( 標準に含まれている ) e07 cluster などに含まれる ここでは stats の kmeas (k-meas) を試用する なお EM アルゴリズムを用いたクラスタリングには Mclust パッケージの mclust がよくつかわれる Cluster meas: y Cluster vector: [] [3] [63] [94] Wth cluster sum of squares by cluster: [] Avalable comoets: [] "cluster" "ceters" "wthss" "se" > lot( col = cl$cluster) > ots(cl$ceters col = : ch = 8 ce=) > > <- rbd(matr(rorm(0 sd = 0.3) col = 3) + matr(rorm(0 mea = 0.5 sd = 0.3) col = 3)) > colames() <- c("" "y" "") > (cl <- kmeas( )) K-meas cluster wth clusters of ses 48 3 Cluster meas: y Cluster vector: [] [6] [5] [76] Wth cluster sum of squares by cluster: [] Avalable comoets: [] "cluster" "ceters" "wthss" "se" > lot( col = cl$cluster) > ots(cl$ceters col = : ch = 8 ce=) > > lot([:3] col = cl$cluster) > ots(cl$ceters[:3] col = : ch = 8 ce=) > y > # data.frame にすると一覧の図になります > <- data.frame() > lot( col = cl$cluster) > y

10 > # rs では > <- rs[-5] > cl <- kmeas( 3) > lot( col = cl$cluster) > ots(cl$ceters col = :3 ch = 8 ce=) > 本日の課題 Seal.Leth Seal.Wdth Petal.Leth Petal.Wdth Amals のデータを k-meas でクラスタリング分析してください その結果を hclust でのクラスタリング結果と比較してください Amals のデータを直接使うなら 例えば <- Amals[:3] として rs と同様にクラスタリングします クラスタ数は や 3 で試してください 芳しくないなら 恐らく スケールが違うからでしょうから <- myamals としてみてください 散布図から分かることですが 点の分布が小さい方にたくさん集まっています それが原因からもしれません では 対数をとってみましょう lo(amals[:3]) などとすると対数がとれます R で EM # EM alorthm for cluster lbrary(mclust) # data samle mlbech wll be used lbrary(mlbech) smly <- mlbech.smley() colames(smly$) <-c("""") (m4 <- Mclust(smly$=4)) mclustdlot(smly$ arameters=m4$arameters =m4$ what="classfcato") ttle("cluster: 4 clusters") dev.ew() (m4to0 <- Mclust(smly$=4:0)) mclustdlot(smly$ arameters=m4to0$arameters =m4to0$ what="classfcato") ttle("cluster: best 4 to 0 clusters") R で EM # test data でテスト smlytest <- mlbech.smley(=40) colames(smlytest$) <- c("""") dev.ew() testres <- ma(cdes(modelname=m4to0$modelname data=smlytest$ arameters=m4to0$arameters)) mclustdlot(smlytest$ arameters=m4to0$arameters classfcato=testres) # BIC でモデル選択 # 各モデル (EEE とか ) の意味は htt:// m <- mclustbic(smly$) lot(m leedars=lst(="bottomrht" ce=0.7 col=)) 本日の課題 ( 余裕があれば ) lbrary(mlbech) に含まれる mlbech.srals を対象として EM アルゴリズムを用いたクラスタリングを行って下さい 前のスライドと同じ手続きで進めて下さい クラスタ数はいくつぐらいが妥当でしょうか? それは 実際と符合しますか? 符合しないとしたら それはどうしてでしょうか? 0