Data Clustering: A Review

Presentation on theme: "Data Clustering: A Review"— Presentation transcript:

1 Data Clustering: A Review
A.K. Jain, M.N. Murty, P.J. Flynn 院生ゼミ '04年4月13日（火曜日） 新納浩幸

2 本日の私の担当 第１章： Introduction 1.1 Motivation
1.2 Component of a Clustering Task 1.3 The User's Dilemma and the Role of Expertise 1.4 History 1.5 Outline 第２章： Definitions and Notations

3 クラスタリングとは 似たものどうしに分類すること

4 分類の観点 「似ている」にはある観点が必要 形の類似性

5 クラスタリングの重要性 データの解析はコンピュータの応用システムの基盤 exploratory（調査） データから法則を予想する
confirmatory（確認） 新規のデータに対してある決定を行う どちらの処理においてもクラスタリングが 本質的な処理となる

6 クラスタリングの適用分野 パターン分析 grouping 意思決定 データには事前の情報がない 機械学習 データマイニング 文書検索
画像分割 パターン分類 ... データには事前の情報がない 例） 正規分布など クラスタリングはデータ間の 関係を調べる基本手法

7 分類と識別（１） clustering discriminant analysis 違いは重要 データを分類する 少数の分類されたデータが
与えられ，新たなデータを それらクラスターのどれかに 分類する （教師なし学習） （教師付き学習）

8 分類と識別（２） クラスタリング 識別（→帰納学習） 予め分類されている 少数のデータ 未分類のデータ

9 本サーベイの位置づけ クラスタリングの対象範囲は広い クラスタリングのサーベイは困難 統計学，決定理論をルーツにもつクラスター分析の
中心的な概念と手法をサーベイする パターン認識や画像分析．．．現状の要約 機械学習．．．非常に近い分野のスナップショット その他．．．クラスタリングの重要性のイントロ

10 クラスタリングのステップ Step 1. パターンの表現 （付加的に，素性抽出/選択を含む） Step 2. 類似度（メジャー）の定義

11 Step1. パターンの表現 パターンはベクトルで表現される．ベクトルの各次元を どのようなもの（観点）に対応させるか．
次元（観点）を素性と呼ぶ （予想される）クラスターの数 利用可能なパターンの数 素性の数，タイプ，大きさ これらを勘案して 決める 開発者には制御不可能なものも多い

12 素性選択と素性抽出 素性選択 素性をたくさん集めておき，そのクラスタリングで重要 そうな素性を選択する 素性抽出
入力した素性（複数かも）を変形して，新たな素性を 作成する パターンの表現を決定する際には重要

13 Step2. 類似度の定義 通常はパターンを n 次元実数値ベクトルで表現し， ユークリッド距離によって，非類似度を定義する．
その他，様々な類似度の定義が存在する 本サーベイの４章で紹介

14 Step3. クラスタリング 様々な手法が存在する ５章 ＊ 出力の形はハードかファジー ハード： パターンはどれかひとつのクラスターに属す
ファジー：パターンは各クラスターに属する度合いを持つ ＊ 手法は階層型か分割型 階層型： ボトムアップ，各パターンの統合を繰り返して 全体が１つのクラスタになる． 分割型： トップダウン，評価関数を最適にする分割を 求める ＊ その他，確率的な手法，グラフ理論からの手法

15 Step4. データの要約 得られた各クラスターに簡潔な表現を与える 人間からみて意味のある分類かどうかは不明なので，
人間が直感的に簡潔な表現を与えられるとは限らない 通常はクラスターの代表点がその表現に対応する

16 Step5. 出力の評価 クラスタリング手法の優劣は不可能 出力したクラスタリングはその手法にとっては意味がある
クラスタリング結果の評価（クラスター有効性分析） 評価関数を利用，しかしその関数は主観的 有効性分析：客観的評価，意味のある分類が偶然 起こったものでないことを確認，統計的な手法では 検定で可能，３つのタイプがある （１） 外的評価... 事前の構造を作っておき比較 （２） 内的評価... データが本質的に適切かを決定 （３） 相対的評価... 構造を比較し，相対的なメリットを測る

17 クラスタリング手法の比較 どの手法を使えばよいのか？ Dubes and Jain [1976] （１）クラスターが形成される方法
（２）データの構造 （３）データの構造に対する敏感性 １つの評価の指針，しかし，以下の重要な疑問を 扱う明確なクラスタリング手法はない 正規化の方法，ドメイン知識の利用方法， 膨大な数のデータに対するクラスタリング手法

18 万能のクラスタリング手法 どんなデータでも扱えるような万能な クラスタリング手法はない どんなクラスタリング手法もクラスターの
形状や類似度に基づくクラスターの構成 に関してなんらかの暗黙の仮定をもつため 人間には可能なのか？ Ｎｏ！ 高次元になると人間にとっても難しい

19 よりよいクラスタリングへ ユーザのやるべきこと ＊ 利用するクラスタリング手法をよく理解する ＊ データ収集の詳細を知ること
＊ 専門家（扱うデータの）を持つこと 領域固有の知識 素性抽出，類似度の計算．クラスタリング， クラスターの表現，を改善する

20 データ発生過程の制約 mixture resolving [Titeerington et al. '85]
データは密度関数の混合から発生している クラスタリングの問題 ＊ いくつの密度関数の混合かを決める ＊ それぞれの密度関数のパラメータを決める [Bajcsy '97] density clustering と素性空間の分割

21 クラスタリングの歴史 パターン認識，画像処理，文書検索，生物学，精神医学， 心理学，考古学，地質学，地理学，マーケッティング
などの分野で使われてきた，歴史がある クラスタリングはいろいろな名前で呼ばれてきた 教師なし学習，分類学，ベクトル量子化， 観察による学習， 様々な解説本，解説記事も出版された （具体的には論文参照）

22 本論文の構成 ２章： 論文で使う用語と記号の定義 ３章： パターンの表現，素性抽出，素性選択の概要 ４章： 様々な類似度 大事，中心
５章： クラスタリング手法の整理，解説 ６章： 応用事例，画像解析とデータマイニング ７章： まとめ 本ゼミでは省略

23 用語と記号の定義（１） パターン（素性ベクトル，事例，データ） 素性（属性） パターンの各次元 次元 パターンが何次元のベクトルか

24 用語と記号の定義（２） パターン集合 パターンの集合，ｎ個あるときは n 行 d 列の行列 クラス クラスターのラベル（？） ハード
ハードクラスタリング， i 番目のパターンが属するクラスラベル（１～ｋ）

25 用語と記号の定義（３） ファジー ファジークラスタリング， i 番目のパターンが j 番目のクラスに属する度合い 距離関数
素性空間上の距離を測るものさし