Mahout Canopy Clustering - #TokyoWebmining 9
•
31 likes•10,542 views
Mahout Canopy Clustering - #TokyoWebmining 9
Recommended
Recommended
More Related Content
What's hot
What's hot (19)
Similar to Mahout Canopy Clustering - #TokyoWebmining 9
Similar to Mahout Canopy Clustering - #TokyoWebmining 9 (20)
More from Koichi Hamada
More from Koichi Hamada (20)
Recently uploaded
Recently uploaded (10)
Mahout Canopy Clustering - #TokyoWebmining 9
- 1. 第9回データマイニング+WEB勉強会＠東京 2011/01/16 Mahout Canopy Clustering hamadakoichi 濱田 晃一
- 2. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 3. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 4. hamadakoichi 濱田晃一 http://iddy.jp/profile/hamadakoichi 4
- 5. hamadakoichi 濱田晃一 データマイニング+WEB勉強会＠東京 主催者です 5
- 6. 講師資料 データマイニング・機械学習、 Mahout、R、等 各種講師資料を公開しています http://www.slideshare.net/hamadakoichi 6
- 7. 活動領域 ソーシャルメディアのデータマイニング活用 2000万人以上の人々へ 各人のつながり・楽しみ・好み 個性にあった適切なサービス提供 Social Media Social Graph Fun Like Personality Objective Process Data Mining Machine Learning 各人のつながり、楽しみ、好み、個性にあった より適切なサービス提供 7
- 8. 活動領域 活動が紹介されました 8
- 9. 活動領域 活動が紹介されました Tech総研 9 （※記事から抜粋）
- 10. hamadakoichi 濱田晃一 10
- 11. hamadakoichi 濱田晃一 理論物理 博士(2004.3取得) 量子統計場の理論 Statistical Field Theory Spontaneously Time-Reversal Symmetry Breaking Anisotropic Massless Dirac Fermions 博士論文： http://hosi.phys.s.u-tokyo.ac.jp/~koichi/PhD-thesis.pdf 11
- 12. hamadakoichi 濱田晃一 文部大臣に褒められた 元 文部大臣・法務大臣 六法全書著者・元法学政治学研究科長 森山眞弓さん 菅野和夫さん 12
- 13. hamadakoichi 濱田晃一 Los Angelesでプロダンサーに褒められた ・HIP HOP/House ダンス歴１３年 ・ダンス開始後 1年半でL.A.でプロダンサーに褒められる Youtube Channel： http://www.youtube.com/hamadakoichi 13
- 14. hamadakoichi 濱田晃一 毎週末３時間ダンスコーチをしています ■過去、東京と京都でも ダンス部を創設。 コーチをしていました 駒場物理ダンス部 京都大学基礎物理学研究所ダンス部 部長兼コーチ 部長兼コーチ 現在： 毎週末 ３時間ダンスコーチ Youtube Channel： http://www.youtube.com/hamadakoichi 14
- 15. 数理解析手法の実ビジネスへの適用 2004年 博士号取得後 数理解析手法を実ビジネス適用の方法論構築 主な領域 ◆活動の数理モデル化・解析手法 ◆活動の分析手法・再構築手法 ◆活動の実行制御・実績解析システム … 内容抜粋 “Decoupling Executions in Navigating Manufacturing "Unified graph representation of processes Processes for Shortening Lead Time and Its Implementation for scheduling with flexible resource to an Unmanned Machine Shop”, assignment", 15
- 16. 数理解析手法の実ビジネスへの適用：活動例 活動例 活動の統一グラフモデルを構築・解析 Unified graphical model of processes and resources 青字：割付モデル属性 [ ] : Optional Node ・priority(優先度) Edge ・duration(予定時間) [・earliest(再早開始日時) ] Process Edge Process [・deadline(納期) ] [・or(条件集約数) ] 前プロセスの終了後に後プロセスが プロセスを表す 開始できること表す ・attributes（属性） preemptable(中断可否), successive(引継ぎ可否) Uses Edge workload(作業負荷) Processが使用する uses uses uses uses uses uses Assign Region を表す Assign Region Assigns from Edge 同一Resourceを割付け続ける Assign Regionに assigns from assigns from 指定Resourceの子Resource集合の 範囲を表す assigns assigns 中から割付けることを示す 企業01 [process] has has [startDate(開始日時)] [endDate(終了日時)] Assigns Edge 製品01 組織A StartDateからEndDateまでの間 Resource has Assign RegionにResourceを 割付対象要素を表す has has has has has has 割付けることを表す ・capacity(容量) ・calender(カレンダー) AAA01 AAB02 … 山田さん 田中さん 鈴木さん ・attributes(属性) Has Edge 東さん Resourceの所有関係を表す 16
- 17. 数理解析手法の実ビジネスへの適用：活動例 一品一様の業務プロセスの 動的なプロセス制御数理体系を構築 全体生産リードタイム中央値を 1/2.7に短縮 設計開始～頭だし出荷リードタイム 設 計 開 始 ～ 頭 だ し出 荷 CT対 週 集 計 開 始 日 時 の 箱 ひ げ 図 体系適用 500 適用後 設計開始～頭だし出荷CT 400 360.4h(15.0日) 1/2.7 300 200 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 141.6h(5.9日) 00 00 9: 9: 9: 9: 9: 9: 9: 9: 9: 9: 9: 9: 9: 9: / 20 / 27 / 04 / 11 / 18 / 25 / 01 / 08 / 15 / 22 / 29 / 06 / 13 / 20 / 09 / 09 / 10 / 10 / 10 / 10 / 11 / 11 / 11 / 11 / 11 / 12 / 12 / 12 04 04 04 04 04 04 04 04 04 04 04 04 04 04 20 20 20 20 20 20 20 20 20 20 20 20 20 20 週 集 計 開 始 日 時 17
- 18. 数理解析手法の実ビジネスへの適用：活動例 ビジネスとともに 学術分野でも貢献 変動性から生じる動的な課題 ・リソースの競合 ・滞留 ・納期遅延 … 一品一様な業務プロセスを含む 統計解析・制御数理モデル ・統計的な有効変数算出 ・統計数理モデル化 －優先順位制御 －実行タイミング制御 －統計フィードバック －適正リソース量算出 ・予測数理体系 論文（体系の一部） M.Nakao, N. Kobayashi, K.Hamada, T.Totsuka, S.Yamada, “Decoupling Executions in Navigating Manufacturing Processes for Shortening Lead Time and Its Implementation to an Unmanned Machine Shop”, CIRP Annals - Manufacturing Technology Volume 56, Issue 1, Pages 171-174 (2007) 18
- 19. 思い より広く蓄積されたデータを有効活用し 世界の未来をよりよいものにしていきたい データマイニング+WEB勉強会＠東京 Google Group： http://groups.google.com/group/webmining-tokyo 19
- 20. 現在の活動領域 ソーシャルメディアのデータマイニング活用 2000万人以上の人々へ 各人のつながり・楽しみ・好み 個性にあった適切なサービス配信 日々20億以上の活動の活用 Social Media Social Graph Fun Like Personality Objective Process Data Mining Machine Learning 各人のつながり、楽しみ、好み、個性にあった より適切なサービス提供 20
- 21. よりよい世界の実現 ソーシャル・活動情報の活用により より適切な情報・サービス配信される世界を実現したい Social Media Social Graph Fun Like Personality Objective Process Data Mining Machine Learning 各人のつながり、楽しみ、好み、個性にあった より適切なサービス提供 21
- 22. よりよい世界の実現 ソーシャル・活動情報の活用により より適切な情報・サービス配信される世界を実現したい 世界中の人々が 個々人のつながり・楽しみ・好みにあった適切な情報・サービスを 自ら探さなくても得ることができる世界 Social Media Social Graph Fun Like Personality Objective Process Data Mining Machine Learning 各人のつながり、楽しみ、好み、個性にあった より適切なサービス提供 22
- 23. よりよい世界の実現 よりよい世界を実現したい 一緒に実現する仲間を募集しています
- 24. よりよい世界の実現 よりよい世界を実現したい 一緒に実現する仲間を募集しています
- 25. よりよい世界の実現 よりよい世界を実現したい 一緒に実現する仲間を募集しています 大規模ソーシャルメディアのデータマイニング （2100万会員 １日20億アクション以上） （※2100万会員モバゲータウンはデータマイニングの宝の山／Tech総研 より抜粋） ・統計解析／データマイニング／機械学習／自然言語処理 ・大規模分散処理 ぜひご連絡下さい koichi.hamada@gmail.com
- 26. よりよい世界の実現 よりよい世界を実現したい 一緒に実現する仲間を募集しています 大規模ソーシャルメディアのデータマイニング （2100万会員 １日20億アクション以上） （※2100万会員モバゲータウンはデータマイニングの宝の山／Tech総研 より抜粋） ・統計解析／データマイニング／機械学習／自然言語処理 ・大規模分散処理 R ぜひご連絡下さい koichi.hamada@gmail.com
- 27. よりよい世界の実現 よりよい世界を実現したい 一緒に実現する仲間を募集しています 大規模ソーシャルメディアのデータマイニング （2100万会員 １日20億アクション以上） （※2100万会員モバゲータウンはデータマイニングの宝の山／Tech総研 より抜粋） ・統計解析／データマイニング／機械学習／自然言語処理 ・大規模分散処理 R Hadoop/Pig/Hive/Zebra ぜひご連絡下さい koichi.hamada@gmail.com
- 28. よりよい世界の実現 よりよい世界を実現したい 一緒に実現する仲間を募集しています 大規模ソーシャルメディアのデータマイニング （2100万会員 １日20億アクション以上） （※2100万会員モバゲータウンはデータマイニングの宝の山／Tech総研 より抜粋） ・統計解析／データマイニング／機械学習／自然言語処理 ・大規模分散処理 R Hadoop/Pig/Hive/Zebra Mahout ぜひご連絡下さい koichi.hamada@gmail.com
- 29. よりよい世界の実現 よりよい世界を実現したい 一緒に実現する仲間を募集しています 大規模ソーシャルメディアのデータマイニング （2100万会員 １日20億アクション以上） （※2100万会員モバゲータウンはデータマイニングの宝の山／Tech総研 より抜粋） ・統計解析／データマイニング／機械学習／自然言語処理 ・大規模分散処理 R Hadoop/Pig/Hive/Zebra Mahout …etc ぜひご連絡下さい koichi.hamada@gmail.com
- 30. 参加者 自己紹介Ｔｉｍｅ （1人１分半ほど：計５０分） 30
- 31. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 32. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 33. Mahoutとは 33
- 34. Mahoutとは Open Sourceでスケーラブルな 機械学習・データマイニングのライブラリ ・Apache プロジェクト ・機械学習・データマイニングのライブラリ ・Java オープンソース ・Hadoop（大規模 分散処理基盤）上で動作 （Hadoop：象, Mahout: 象使い） http://mahout.apache.org 34
- 35. Mahoutとは Open Sourceでスケーラブルな 機械学習・データマイニングのライブラリ ・Apache プロジェクト ・機械学習・データマイニングのライブラリ ・Java オープンソース ・Hadoop（大規模 分散処理基盤）上で動作 （Hadoop：象, Mahout: 象使い） http://mahout.apache.org 35
- 36. Mahoutとは Open Sourceでスケーラブルな 機械学習・データマイニングのライブラリ ・Apache プロジェクト ・機械学習・データマイニングのライブラリ ・Java オープンソース ・Hadoop（大規模 分散処理基盤）上で動作 （Hadoop：象, Mahout: 象使い） http://mahout.apache.org 36
- 37. Mahoutとは Open Sourceでスケーラブルな 機械学習・データマイニングのライブラリ ・Apache プロジェクト ・機械学習・データマイニングのライブラリ ・Java オープンソース ・Hadoop（大規模 分散処理基盤）上で動作 （Hadoop：象, Mahout: 象使い） http://mahout.apache.org 37
- 38. Mahoutとは Open Sourceでスケーラブルな 機械学習・データマイニングのライブラリ ・Apache プロジェクト ・機械学習・データマイニングのライブラリ ・Java オープンソース ・Hadoop（大規模 分散処理基盤）上で動作 （Hadoop：象, Mahout: 象使い） http://mahout.apache.org 38
- 39. Mahoutとは Open Sourceでスケーラブルな 機械学習・データマイニングのライブラリ ・Apache プロジェクト ・機械学習・データマイニングのライブラリ ・Java オープンソース ・Hadoop（大規模 分散処理基盤）上で動作 ・Hadoop：象, Mahout: 象使い http://mahout.apache.org 39
- 40. Mahoutとは Open Sourceでスケーラブルな 機械学習・データマイニングのライブラリ ・Apache プロジェクト ・機械学習・データマイニングのライブラリ ・Java オープンソース ・Hadoop（大規模 分散処理基盤）上で動作 ・Hadoop：象, Mahout: 象使い http://mahout.apache.org 40
- 41. Mahoutとは Open Sourceでスケーラブルな 機械学習・データマイニングのライブラリ Applications Examples Freq. Genetic Pattern Classification Clustering Recommenders Mining Math Utilities Collections Apache Vectors/Matrices/ Lucene/Vectorizer (primitives) Hadoop SVD http://cwiki.apache.org/confluence/display/MAHOUT/Algorithms http://www.slideshare.net/gsingers/intro-to-apache-mahout 41
- 42. 2010/10/31 Mahout 0.4 42
- 43. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 44. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 45. Clusteringとは データを類似度に従い グループに分けること 45
- 46. Clusteringとは データを類似度に従い グループに分けること クラスタリングA 46
- 47. Clusteringとは データを類似度に従い グループに分けること クラスタリングA クラスタリングB 47
- 48. Clusteringとは データを類似度に従い グループに分けること クラスタリングA クラスタリングB 48
- 49. 活用例：マーケティングリサーチ マーケティングリサーチ データ 好きなお酒に関するアンケート 消費者クラスタ Clustering ユーザーベクトル 商品・メディア評価 Aさん Bさん Cさん チューハイ氷結 5 5 1 カロリ 4 5 1 196℃ 4 1 1 … カクテルパートナー 4 4 2 Slat 1 1 1 ほろよい 1 2 2 ウメッシュ 1 1 3 … 1 1 1 テレビ 1 1 5 参考： @bob3bob3 さん： ネット 5 1 1 「市場細分化とクラスター分析」（第３回データマイニング＋WEB勉強会＠東京） http://www.slideshare.net/bob3/cfakepathtokyo-webmining3-201004 … … … …
- 50. 活用例：マーケティングリサーチ マーケティングリサーチ 消費者のニーズを知り、ターゲティング・チャネル選定に活かす データ 好きなお酒に関するアンケート 消費者クラスタ ・苦いもの ・300円台 甘いもの Clustering 100円台 ユーザーベクトル 商品・メディア評価 Aさん Bさん Cさん ・甘いもの ・低カロリ チューハイ氷結 5 5 1 ・テレビ カロリ 4 5 1 196℃ 4 1 1 … カクテルパートナー 4 4 2 ・甘いもの ・塩味 Slat 1 1 1 ・低カロリ ・炭酸 ・ネット ・400円台 ほろよい 1 2 2 自社ターゲットで 新しい ウメッシュ 1 1 3 到達できていない ユーザーニーズの発見 … 1 1 1 ユーザー層の発見 テレビ 1 1 5 参考： @bob3bob3 さん： ネット 5 1 1 「市場細分化とクラスター分析」（第３回データマイニング＋WEB勉強会＠東京） http://www.slideshare.net/bob3/cfakepathtokyo-webmining3-201004 … … … …
- 51. 活用例：健診データ 健診データ データ 健診データ 受診者クラスタ Clustering ユーザーベクトル 健康特徴 Aさん Bさん Cさん 年齢 46 44 … BMI 25.6 20.1 血圧上 126 119 血圧下 77 70 中性脂肪 321 156 空腹時血糖値 95 98 LDL 130 123 GOT 23 27 GPT 41.5 38 参考：@dichika さん： 「健診データへのクラスタリング適用例」（第３回データマイニング＋WEB勉強会＠東京） yGTP 51.5 79 http://www.slideshare.net/guestbe53f7/kenshin … … …
- 52. 活用例：健診データ 健診データ 病人の特徴を知り、病気の予防に活かす データ 健診データ 受診者クラスタ Clustering メダボリック ユーザーベクトル シンドローム 健康特徴 Aさん Bさん Cさん 年齢 46 44 … メタボリック BMI 25.6 20.1 シンドローム予備軍 血圧上 126 119 ⇒減量指導する 血圧下 77 70 中性脂肪 321 156 空腹時血糖値 95 98 LDL 130 123 GOT 23 27 GPT 41.5 38 参考：@dichika さん： 「健診データへのクラスタリング適用例」（第３回データマイニング＋WEB勉強会＠東京） yGTP 51.5 79 http://www.slideshare.net/guestbe53f7/kenshin … … …
- 53. クラスタリング手法の種類 手法と帰属度の分類軸がある 分類 種類 内容 手法 階層的手法 ①各データそれぞれを一つのクラスタとする ②状態を初期状態とするクラスタの距離、類似度で２つのクラ スタを逐次的に併合していく ③目的のクラスタ数まで併合が行われたときに処理を終了す る 非階層的手法 ①データの良さを表す評価関数を設定する （分割最適化） ②評価関数に対する最適解（最適分割）を探索する 帰属度 ハードクラスタリ 各データは一つのクラスタのみに所属する ング ソフトクラスタリ 各データが複数のクラスタリングに所属することを許す ング （※最も帰属度が高いクラスタを抽出すると、ハードクラスタリ ングとなる） 53
- 54. クラスタリング手法の種類 手法と帰属度の分類軸がある 分類 種類 内容 手法 階層的手法 ①各データそれぞれを一つのクラスタとする ②状態を初期状態とするクラスタの距離、類似度で２つのクラ スタを逐次的に併合していく ③目的のクラスタ数まで併合が行われたときに処理を終了す る 非階層的手法 ①データの良さを表す評価関数を設定する （分割最適化） ②評価関数に対する最適解（最適分割）を探索する 帰属度 ハードクラスタリ 各データは一つのクラスタのみに所属する ング ソフトクラスタリ 各データが複数のクラスタリングに所属することを許す ング （※最も帰属度が高いクラスタを抽出すると、ハードクラスタリ ングとなる） 54
- 55. クラスタリング手法の種類 手法と帰属度の分類軸がある 分類 種類 内容 手法 階層的手法 ①各データそれぞれを一つのクラスタとする ②状態を初期状態とするクラスタの距離、類似度で２つのクラ スタを逐次的に併合していく ③目的のクラスタ数まで併合が行われたときに処理を終了す る 非階層的手法 ①データの良さを表す評価関数を設定する （分割最適化） ②評価関数に対する最適解（最適分割）を探索する 帰属度 ハードクラスタリ 各データは一つのクラスタのみに所属する ング ソフトクラスタリ 各データが複数のクラスタリングに所属することを許す ング （※最も帰属度が高いクラスタを抽出すると、ハードクラスタリ ングとなる） 55
- 56. クラスタリング手法の種類 クラスタリング手法 種類 ハード ソフト 階層的 ・Group Average method ・Single Linkage Method ・Complete Linkage Method ・Ward Method ・Centroid Method ・Median Method 非階層的 ・k-means ・Fuzzy k-means ・Canopy ・Gaussian Discriminative Analysis ・Mean-Shift ・Dirichlet Processing ・Spectral Clustering 56
- 57. クラスタリング手法の種類 クラスタリング手法 種類 ハード ソフト 階層的 ・Group Average method ・Single Linkage Method ・Complete Linkage Method ・Ward Method ・Centroid Method ・Median Method 非階層的 ・k-means ・Fuzzy k-means ・Canopy ・Gaussian Discriminative Analysis ・Mean-Shift ・Dirichlet Processing ・Spectral Clustering 57
- 58. クラスタリング手法の種類 クラスタリング手法 種類 ハード ソフト 階層的 ・Group Average method ・Single Linkage Method ・Complete Linkage Method ・Ward Method ・Centroid Method ・Median Method 非階層的 ・k-means ・Fuzzy k-means ・Canopy ・Gaussian Discriminative Analysis ・Mean-Shift ・Dirichlet Processing ・Spectral Clustering 58
- 59. クラスタリング手法の種類 クラスタリング手法 種類 ハード ソフト 階層的 ・Group Average method ・Single Linkage Method ・Complete Linkage Method ・Ward Method ・Centroid Method ・Median Method 非階層的 ・k-means ・Fuzzy k-means ・Canopy ・Gaussian Discriminative Analysis ・Mean-Shift ・Dirichlet Processing ・Spectral Clustering 59
- 60. クラスタリング手法の種類 Mahout Clustering 実装 種類 ハード ソフト 階層的 ・Group Average method ・Single Linkage Method ・Complete Linkage Method ・Ward Method ・Centroid Method ・Median Method 非階層的 ・k-means ・Fuzzy k-means ・Canopy ・Gaussian Discriminative Analysis ・Mean-Shift ・Dirichlet Processing ・Spectral Clustering 60
- 61. Mahout Clustering Mahout Clustering クラスタリング手法 特徴 k-means Clustering クラスタをクラスタ数個の代表値で特徴づけクラ スタリング： 非階層的手法で最も代表的な手法。現実のクラス タリングでも使われることが多く、実用的な手法。 Fuzzy k-means K-meansで各要素が複数クラスタに帰属する形に 拡張： 距離に帰属度を掛け合わせクラスタ評価。 Gaussian Discriminative Analysis, 確率モデルでのクラスタリング： Dirichlet Processing Clustering 観測データが異なる確率分布(ガウス分布/ディリ クレ分布)の混合分布であると仮定。個体が属する クラスを隠れ変数を推定する。データの発生メカ ニズムが確率モデルでうまくモデル化できるとき、 強力な手法。 Canopy 指定距離の範囲[D1, D2]内のデータ点セットを抽 出する：K-meansの初期重心算出で用いられる。 Mean Shift 密度増加が最大半径で各クラスタ算出：指定距離 範囲でクラスタリング半径を順次増やしていく。 Spectral Clustering (Eigencut) 類似度グラフの分割によるクラスタリング 61
- 62. Mahout Clustering Mahout Clustering クラスタリング手法 特徴 k-means Clustering クラスタをクラスタ数個の代表値で特徴づけクラ スタリング： 非階層的手法で最も代表的な手法。現実のクラス タリングでも使われることが多く、実用的な手法。 Fuzzy k-means K-meansで各要素が複数クラスタに帰属する形に 拡張： 距離に帰属度を掛け合わせクラスタ評価。 Gaussian Discriminative Analysis, 確率モデルでのクラスタリング： Dirichlet Processing Clustering 観測データが異なる確率分布(ガウス分布/ディリ クレ分布)の混合分布であると仮定。個体が属する クラスを隠れ変数を推定する。データの発生メカ ニズムが確率モデルでうまくモデル化できるとき、 強力な手法。 Canopy 指定距離の範囲[D1, D2]内のデータ点セットを抽 出する：K-meansの初期重心算出で用いられる。 Mean Shift 密度増加が最大半径で各クラスタ算出：指定距離 範囲でクラスタリング半径を順次増やしていく。 Spectral Clustering (Eigencut) 類似度グラフの分割によるクラスタリング 62
- 63. Mahout Clustering Mahout Clustering クラスタリング手法 特徴 k-means Clustering クラスタをクラスタ数個の代表値で特徴づけクラ スタリング： 非階層的手法で最も代表的な手法。現実のクラス タリングでも使われることが多く、実用的な手法。 Fuzzy k-means K-meansで各要素が複数クラスタに帰属する形に 拡張： 距離に帰属度を掛け合わせクラスタ評価。 Gaussian Discriminative Analysis, 確率モデルでのクラスタリング： Dirichlet Processing Clustering 観測データが異なる確率分布(ガウス分布/ディリ クレ分布)の混合分布であると仮定。個体が属する クラスを隠れ変数を推定する。データの発生メカ ニズムが確率モデルでうまくモデル化できるとき、 強力な手法。 Canopy 指定距離の範囲[D1, D2]内のデータ点セットを抽 出する：K-meansの初期重心算出で用いられる。 Mean Shift 密度増加が最大半径で各クラスタ算出：指定距離 範囲でクラスタリング半径を順次増やしていく。 Spectral Clustering (Eigencut) 類似度グラフの分割によるクラスタリング 63
- 64. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 65. k-means アルゴリズム
- 66. k-means： 最も単純なアルゴリズム (E.W. Forgy 1965) ①データセットの中からK個のクラスタの 代表点 c1,c2,…,cKをランダムに選ぶ 例） データ数 N=5,クラスタ数 K=2 3 4 c2 × c1 2 5 1× 66
- 67. k-means： 最も単純なアルゴリズム (E.W. Forgy 1965) ①データセットの中からK個のクラスタの 代表点 c1,c2,…,cKをランダムに選ぶ ②各データ x に対し、 ciとの距離を測り 最も距離の短い ci に対するに対する クラスタを xのクラスタに設定する 評価関数（最小化問題） 例） データ数 N=5,クラスタ数 K=2 3 3 3 4 4 c2 4 c2 c2 × c1 × c1 × c1 × 2 5 2 5 2 5 1× 1× 1 67
- 68. k-means： 最も単純なアルゴリズム (E.W. Forgy 1965) ①データセットの中からK個のクラスタの 代表点 c1,c2,…,cKをランダムに選ぶ ②各データ x に対し、 ciとの距離を測り ③各クラスタの平均値（重心）を 最も距離の短い ci に対するに対する クラスタの代表点とする。 クラスタを xのクラスタに設定する (K個の平均値がクラスタを代表) ※各データ x のクラスタが変化しなくなるまで繰り返す 評価関数（最小化問題） 例） データ数 N=5,クラスタ数 K=2 3 3 3 3 4 4 c2 4 c2 4 c2 c2 × × c1 c1 × c1 × c1 × × 2 5 2 5 2 5 2 5 1× 1× 1 1 68
- 69. k-means： 課題 ①データセットの中からK個のクラスタの 代表点 c1,c2,…,cKをランダムに選ぶ K-means Clustering 初期のランダム性に依存し、適切に離れ たクラスタが得られるとは限らない。 ②各データ x に対し、 ciとの距離を測り ③各クラスタの平均値（重心）を 最も距離の短い ci に対するに対する クラスタの代表点とする。 クラスタを xのクラスタに設定する (K個の平均値がクラスタを代表) ※各データ x のクラスタが変化しなくなるまで繰り返す 評価関数（最小化問題） 例） データ数 N=5,クラスタ数 K=2 3 3 3 3 4 4 c2 4 c2 4 c2 c2 × × c1 c1 × c1 × c1 × × 2 5 2 5 2 5 2 5 1× 1× 1 1 69
- 70. k-means： 課題 多くのClustering 目的距離離れたクラスタを得たいとき、 ①データセットの中からK個のクラスタの クラスタ数 K個が適切とは限らない 代表点 c1,c2,…,cKをランダムに選ぶ K-means Clustering 初期のランダム性に依存し、適切に離れ たクラスタが得られるとは限らない。 ②各データ x に対し、 ciとの距離を測り ③各クラスタの平均値（重心）を 最も距離の短い ci に対するに対する クラスタの代表点とする。 クラスタを xのクラスタに設定する (K個の平均値がクラスタを代表) ※各データ x のクラスタが変化しなくなるまで繰り返す 評価関数（最小化問題） 例） データ数 N=5,クラスタ数 K=2 3 3 3 3 4 4 c2 4 c2 4 c2 c2 × × c1 c1 × c1 × c1 × × 2 5 2 5 2 5 2 5 1× 1× 1 1 70
- 71. k-means： 課題 多くのClustering 目的距離離れたクラスタを得たいとき、 ①データセットの中からK個のクラスタの クラスタ数 K個が適切とは限らない 代表点 c1,c2,…,cKをランダムに選ぶ K-means Clustering 初期のランダム性に依存し、適切に離れ たクラスタが得られるとは限らない。 ②各データ x に対し、 ciとの距離を測り ③各クラスタの平均値（重心）を 最も距離の短い ci に対するに対する クラスタの代表点とする。 クラスタを xのクラスタに設定する (K個の平均値がクラスタを代表) ※各データ x のクラスタが変化しなくなるまで繰り返す 評価関数（最小化問題） 例） データ数 N=5,クラスタ数 K=2 3 3 3 3 4 4 c2 4 c2 4 c2 c2 × × c1 c1 × c1 × c1 × × 2 5 2 5 2 5 2 5 1× 1× 1 1 71
- 72. これらのClusteringの課題を 解決する方法論
- 73. これらのClusteringの課題を 解決する方法論 Canopy Clustering 2000 (McCallum, Nigam, Ungar)
- 74. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 75. Canopy Clustering アルゴリズム
- 78. Canopy Clustering 0. データ点をランダムサンプリング 1. どの canopy にも属していない 点 xi を選ぶ 78
- 79. Canopy Clustering 0. データ点をランダムサンプリング 1. どの canopy にも属していない 点 xi を選ぶ 2. xi から距離 T2以内にある点を 削除する。 T2 T2 79
- 80. Canopy Clustering 0. データ点をランダムサンプリング 1. どの canopy にも属していない 点 xi を選ぶ 3. 点xi の T1以内にある点を 2. xi から距離 T2以内にある点を xi と 同じ Canopy cx に所属させ 削除する。 canopy重心を求める T2 T2 c1 T1 80
- 81. Canopy Clustering 0. データ点をランダムサンプリング 1. どの canopy にも属していない 点 xi を選ぶ 3. 点xi の T1以内にある点を 2. xi から距離 T2以内にある点を xi と 同じ Canopy cx に所属させ 削除する。 canopy重心を求める ※削除される点がなくなるまで繰り返す T2 T2 T2 c1 T1 c1 T1 T2 81
- 82. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 83. Mahout Clustering : 実行手順 座標点データ クラスタ数K Point の key, clusterId 83
- 84. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 Vectorsファイル出力 クラスタ数K Point の key, clusterId 84
- 85. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 Vectorsファイル出力 Random点抽出・初期重心設定 クラスタ数K K個ランダム点抽出 初期クラスタ重心設定 初期クラスタ重心ファイル出力 Clustering ClusterDriver KmeansDriver/ Fuzzy kmeansDriver/ etc Point の key, clusterId 85
- 86. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 Vectorsファイル出力 Random点抽出・初期重心設定 Canopy Generation/Clustering クラスタ数K K個ランダム点抽出 Canopy生成 初期クラスタ重心設定 初期クラスタ重心ファイル出力 Canopyファイル出力 Clustering ClusterDriver KmeansDriver/ Fuzzy kmeansDriver/ etc Point の key, clusterId 86
- 87. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 Vectorsファイル出力 Random点抽出・初期重心設定 Canopy Generation/Clustering クラスタ数K K個ランダム点抽出 Canopy生成 初期クラスタ重心設定 初期クラスタ重心ファイル出力 Canopyファイル出力 Clustering ClusterDriver KmeansDriver/ Fuzzy kmeansDriver/ etc Point の key, clusterId 87
- 88. Mahout Clustering： 役割 データ表現： org.apache.mahout.math Interface 内容 Vector データ点表現のインターフェース Class 内容 DenseVector Vector のdoubleの配列での実装 Canopy実行： org.apache.mahout.clustering.canopy.CanopyDriver Class 内容 Canopy Canopyを表現 (DistanceMeasureClusterを継承) CanopyDriver Canopyジョブを実行する K-means実行： org.apache.mahout.clustering.kmeans.KMeansDriver Class 内容 Cluster クラスタを表現 KMeansDriver K-meansジョブを実行する 距離算出法 指定： org.apache.mahout.common.distance Ｉｎｔｅｒｆａｃｅ 内容 DistanceMeasure ２点間の距離算出法のインターフェース Class 内容 EuclideanDistanceMeasure ユークリッド距離での実装 … 他距離 (Manhattan, SquareEuclidean, ..etc) 88
- 89. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 Vectorsファイル出力 Random点抽出・初期重心設定 Canopy Generation/Clustering クラスタ数K K個ランダム点抽出 Canopy生成 初期クラスタ重心設定 初期クラスタ重心ファイル出力 Canopyファイル出力 Clustering ClusterDriver KmeansDriver/ Fuzzy kmeansDriver/ etc 結果 <Point id, cluster Id> 89
- 90. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 Vectorsファイル出力 Random点抽出・初期重心設定 Canopy Generation/Clustering クラスタ数K K個ランダム点抽出 Canopy生成 初期クラスタ重心設定 初期クラスタ重心ファイル出力 Canopyファイル出力 Clustering ClusterDriver KmeansDriver/ Fuzzy kmeansDriver/ etc 結果 <Point id, cluster Id> 90
- 91. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 List<Vector> を作成し Vectorsファイル出力 Sequence Fileに出力する Random点抽出・初期重心設定 Canopy Generation/Clustering クラスタ数K K個ランダム点抽出 Canopy生成 初期クラスタ重心設定 初期クラスタ重心ファイル出力 Canopyファイル出力 Clustering ClusterDriver KmeansDriver/ Fuzzy kmeansDriver/ etc 結果 <Point id, cluster Id> 91
- 92. Mahout Clustering : 実行手順 SequenceFileを作成 SequenceFile(WritableComparable, VectorWritable) 参考 Mahout: Data Converter for Clustering – hamadakoichi blog http://d.hatena.ne.jp/hamadakoichi/20110112/p1 92
- 93. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 Vectorsファイル出力 Random点抽出・初期重心設定 Canopy Generation/Clustering クラスタ数K K個ランダム点抽出 Canopy生成 初期クラスタ重心設定 初期クラスタ重心ファイル出力 Canopyファイル出力 Clustering ClusterDriver KmeansDriver/ Fuzzy kmeansDriver/ etc 結果 <Point id, cluster Id> 93
- 94. Mahout Clustering : 実行手順 Canopy実行 コマンドライン実行 (CanopyDriver呼出） $MAHOUT_HOME/bin/mahout canopy ¥ -i vectors ¥ -o canopycentroids ¥ -dm org.apache.mahout.common.distance.EuclideanDistanceMeasure ¥ -t1 2000 -t2 1500 -xm mapreduce 意味 $MAHOUT_HOME/bin/mahout canopy ¥ -i <入力vectorのディレクトリパス> ¥ -o <canopyの出力パス> ¥ -dm <距離定義クラス> ¥ -t1 <T1 閾値> ¥ -t2 <T2 閾値> ¥ -xm <mapreduce での分散実行か> 94
- 95. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 Vectorsファイル出力 Random点抽出・初期重心設定 Canopy Generation/Clustering クラスタ数K K個ランダム点抽出 Canopy生成 初期クラスタ重心設定 初期クラスタ重心ファイル出力 Canopyファイル出力 Clustering ClusterDriver KmeansDriver/ Fuzzy kmeansDriver/ etc 結果 <Point id, cluster Id> 95
- 96. Mahout Clustering : 実行手順 K-means実行 コマンドライン実行 (KmeansDriver呼出） $MAHOUT_HOME/bin/mahout kmeans ¥ -i vectors ¥ -c canopycentroids ¥ -o clusters ¥ -dm org.apache.mahout.common.distance.EuclideanDistanceMeasure ¥ -cd 0.1 -x 100 ¥ -xm mapreduce 意味 $MAHOUT_HOME/bin/mahout canopy ¥ -i <入力vectorのディレクトリパス> ¥ -c <canopy (初期cluster)のディレクトリパス> ¥ -o <出力パス> ¥ -cd <収束 閾値> ¥ -xm <mapreduce 実行か> -x <最大繰り返し回数> 96
- 97. Mahout Clustering : 実行手順 座標点データ Mahout点表現データ (Vectors) 作成 Vectors 生成 Vectorsファイル出力 Random点抽出・初期重心設定 Canopy Generation/Clustering クラスタ数K K個ランダム点抽出 Canopy生成 初期クラスタ重心設定 初期クラスタ重心ファイル出力 Canopyファイル出力 Clustering ClusterDriver KmeansDriver/ Fuzzy kmeansDriver/ etc 結果 <Point id, cluster Id> 97
- 98. Mahout Clustering : 結果を見る Clustering結果を SequenceFileからテキストファイルに変換 Clustering Output形式 key Value pointId ClusterId コマンドライン実行 (ClusterDumper呼出） $MAHOUT_HOME/bin/mahout bin/mahout clusterdump ¥ -s clusters/clusters-15 ¥ -o output.txt -d vectors/dictionary.file-0 意味 $MAHOUT_HOME/bin/mahout canopy ¥ -s<clusterの SequentialFileディレクトリパス> ¥ -c <canopy (初期cluster)のディレクトリパス> ¥ -o <テキストの出力パス> ¥ 98
- 99. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 100. 参考資料： ■ Canopy Clustering 元論文 Efficient clustering of high-dimensional data sets with application to reference matching, A. McCallum, K. Nigam, L. H. Ungar (2010) http://www.kamalnigam.com/papers/canopy-kdd00.pdf Mahout Wiki Canopy Clustering https://cwiki.apache.org/MAHOUT/canopy-clustering.html 100
- 101. 参考資料：Mahout/Hadoop http://www.slideshare.net/hamadakoichi/apache-mahout-04-random-forests http://www.slideshare.net/hamadakoichi/mahoutweb http://www.slideshare.net/karubi/web-mining-0620 http://www.slideshare.net/yanaoki/hadoop-4113186
- 102. 参考資料：R/Clustering http://www.slideshare.net/hamadakoichi/webr-r http://www.slideshare.net/hamadakoichi/r-3754836 http://www.slideshare.net/bob3/cfakepathtokyo-webmining3-201004 http://www.slideshare.net/guestbe53f7/kenshin
- 103. 参考資料： ■ Apach Mahout http://mahout.apache.org http://cwiki.apache.org/MAHOUT http://cwiki.apache.org/confluence/display/MAHOUT/Algorithms http://www.slideshare.net/gsingers/intro-to-apache-mahout ■ Mahout In Action (Manning Early Access Edition) http://www.manning.com/owen/ 103
- 104. 参考資料： 集合知イン・アクション 集合知プログラミング 104
- 105. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に
- 106. 最後に 蓄積されたデータを有効活用してきたい 106
- 107. 最後に 蓄積されたデータを有効活用してきたい Google Group： http://groups.google.com/group/webmining-tokyo 107
- 108. 最後に データマイニング+WEB勉強会 発表者を募集しています 連絡 Google Group： http://groups.google.com/group/webmining-tokyo Twitter ： http://twitter.com/hamadakoichi 108
- 109. ご清聴ありがとうございました 109
- 110. AGENDA ◆自己紹介 ◆Mahoutとは ◆Clustering ◆Clustering ◆k-means Clustering ◆Canopy Clustering ◆Mahout Clustering ◆Canopy and K-means Clustering ◆参考資料 ◆最後に