Cluster Analysis 徳山研究室M2 鈴木　晶子

発表内容 クラスタリングとは 大量のデータを操作するために、クラスタリングメソッドに要求されること クラスタリング技術の紹介 分割法、階層的手法、密度に基づく方法、格子に基づく方法、モデルに基づく方法 Outlier detection

クラスタリングとは クラスタリング(Clustering) データをクラス(class)またはクラスタ(cluster)にグループ化すること 同じクラスタに属するオブジェクトを比較した時には、互いに高い類似性をもつ 異なるクラスタに属するオブジェクトを比較した時には、高い相違性をもつ 非類似度(dissimilarity)は、オブジェクトを記述する属性値に基づいて評価される

クラスタリングの応用(1/2) クラスタリングは多くの分野において、幅広く用いられている 応用例： 自動車保険において、高い損害賠償を伴う保険証保持者のグループを特定する 情報検索の目的で、ウェブ上の文書をクラス分けする クラスタリングによって、データの密な領域と疎な領域を識別することができる データの大域的な分布パターンや、属性間の相関を発見することができる

クラスタリングの応用(2/2) クラスタリングをデータマイニングのツールとして用いる場合、2通りの用い方がある データ分布を調べ、各クラスタの特徴を観察するための独立したツールとしての用い方 特徴づけ、あるいは分類を行うための、前処理としての用い方

クラスタリングへの要求 データマイニング分野において、クラスタリングに要求されること Scalability(拡張性) 異なるタイプの属性を扱えること 任意のカタチをしたクラスタの発見 入力パラメータを決定するための知識ができるだけ求められないこと ノイズの入ったデータを扱えること 入力レコードの順序に依存しないこと 高次元性 Constraint-based clustering(特定の制約下におけるクラスタリング) 解釈のしやすさと、使いやすさ

様々な種類のデータ クラスタリングで扱うデータには様々な種類がある Interval-scaled variables 連続した値をとる Binary variables(ニ値変数) Nominal variables ニ値変数の一般化で、2つ以上の状態をとる Ordinal variables 値に順序が定められている Ratio-scaled variables 指数スケールのような、非線形の尺度をもつ

タイプの混合したデータ 多くのデータベースにおいては、様々なタイプの変数が混ざっている このようなデータの非類似度は、全ての変数を[0.0, 1.0]の共通したスケール上に置き換えることにより、求めることができる

主なクラスタリング手法の分類 Partitioning methods (分割手法) Hierarchical methods (階層的手法) Density-based methods (密度に基づく手法) Grid-based methods (格子に基づく手法) Model-based methods (モデルに基づく手法)

8.4 Partitioning Methods

Partitioning Method 入力 n個のオブジェクトからなるデータベース クラスタの数k(k≦n) 出力 入力に対するk個の分割 各分割がクラスタを表す クラスタは、目的となる分割基準(距離など)を最適化するように形成される 各オブジェクトは厳密にひとつのグループに属する

古典的な分割手法 各クラスタに代表点を定め、クラスタ内の各オブジェクトと代表点との非類似度を求める この和を最小化するように分割を行う 代表点の取り方として、k-means法とk-medoids法が有名 k-means method そのクラスタに含まれているオブジェクトの平均値（重心）をもとにして評価される k-medoids method medoid(最もクラスタの中心付近に位置するオブジェクト)をもとにして評価される

k-Means Method

k-means methodの性質 クラスタが小さくまとまっていて、互いに離れたところにあれば、うまく機能する 大きなデータセットの処理には比較的拡張性があり、効果的 クラスタの平均値が定義できる時にしか使えない カテゴリ属性が含まれるデータには用いることができない クラスタの数kをあらかじめ指定する必要がある ノイズやoutlierの影響を受けやすい

k-Medoids Method PAM(Partitioning around Medoids) k-medoids algorithmを取り入れたもののひとつ はじめに、ランダムにk個のmedoidを選び、その後良いmedoidsを選ぶよう繰り返す 取り得る全てのオブジェクトのペアについて考え、medoidとなるオブジェクトを交換してより良いものへ変えていく

k-medoids methodの性質 k-means法に比べてノイズやoutlierの影響を受けにくい

大きなデータベースへの適用 大きなデータベースに対する効率的な分割アルゴリズム CLARA(Clustering LARge Applications) CLARANS(Clustering LARge Applications based upon RANdomized Search)

CLARAとCLARANS CLARA CLARANS データの集合全体について考える代わりに、データの小さなサンプルをとって考える このサンプルの中から、PAMを用いてmedoidを決定する サンプルをいくつかとり、得られた結果の中から最も良いものを出力する CLARANS CLARAを改良したもの medoidを更新した時に新たにサンプリングを行う点において、CLARAと異なっている

8.5 Hierarchical Methods

Hierarchical Methods 与えられたデータオブジェクトの集合に対する、階層構造(hierarchical decomposition)を生成する 階層構造がボトムアップ的に形成されるかトップダウン的に形成されるかによって、凝集型(agglomerative)と分枝型(divisive)に分かれる

2つのタイプのメソッド 【凝集型メソッド】（ボトムアップ） step 0 1 2 3 4 a ab b abcde c cde d de e 【分枝型メソッド】（トップダウン）

階層的手法の難しさ 純粋な階層的クラスタリングでは、一度マージあるいは分割が行われると、それを修正することができない 階層的手法の質を向上させるアイデア →他のクラスタリング手法を組み合わせる BIRCH CURE ROCK Chameleon

BIRCH BIRCH: Balanced Iterative Reducing and Clustering using Hierarchies クラスタを要約して表現するために2つの概念を用いる clustering feature clustering feature tree(CF tree)

clustering featureとCF tree CF(clustering feature) クラスタの要約情報を3つの要素で表す N : クラスタ内の点の数 LS: N点の線形和 SS: N点の二乗和 CF tree clustering featureを格納する平衡木 nonleaf nodeには、その子ノードが持っているCFの総和が格納される

CF Tree node A (root: 全てのデータ) node B node C node D オブジェクトの集合（サブクラスタ）

アルゴリズムの流れ Phase 1 データベースをスキャンしてCF木を作る オブジェクトが挿入されるたびにCF木が動的に構築されていく オブジェクトは、最も距離が近い葉エントリーに挿入される CF木のサイズが主記憶の容量を超えたら、CF木を再構築する Phase 2 既存のクラスタリングアルゴリズムを適用し、CF木の葉ノードをクラスター化する

BIRCHの特色 計算時間がオブジェクト数に対して線形 入力されたオブジェクトに対して動的なクラスタリングが可能 高速で実行可能で、大きなデータベースにも拡張可能 CF木の各ノードはある限られた数のエントリーしか持つことができないため、CF木のノードはユーザから見て「自然な」ものになっているとは限らない クラスタの形が球状でない場合、うまく働かない

8.6 Density-Based Methods

Density-Based Methods その“近傍”(neighborhood) の密度がある閾値を越えている限り、クラスタを成長させ続ける ノイズ(outlier)を取り除いたり、任意の様々な形をしたクラスタを発見するために用いることができる

Density-Based Methods 密度に基づくクラスタリングアルゴリズム DBSCAN OPTICS cluster orderingという順序をオブジェクトに対して与えてクラスタリングを行う DENCLUE 密度分布関数(density distribution function)という関数を定め、この関数の値をもとにクラスタリングを行う

DBSCAN DBSCAN: Density-Based Spatial Clustering of Applications with Noise 半径ε以内にMinPts個以上のオブジェクトを含むようなオブジェクトを、次々に集めていく Oから density-reachable ε オブジェクトO

DBSCAN density-based cluster density-reachableなオブジェクトの極大集合をクラスタと考える どのクラスタにも含まれないオブジェクトはノイズとみなされる

8.7 Grid-Based Methods

Grid-Based Methods 格子データ構造を用いる方法 空間を、格子構造を形成する有限個のセルに量子化する クラスタリングの操作は、この格子構造に対して行われる 処理時間はデータの数ではなくセルの数に依存するため、速い

Grid-Based Methods STING 典型的なgrid-based approach 格子セルに格納された統計情報をもとに探索を行う WaveCluster ウェーブレット変換を用いてクラスタリングを行う CLIQUE 高次元データ空間におけるクラスタリングのための方法

CLIQUE CLIQUE: Clustering In QUEst density-based とgrid-basedの手法を統合したもの 大きなデータベースにおいて、高次元データをクラスタリングするのに有用

CLIQUE 1st step n次元データ空間を、長方形ユニットに分割 その中から、“密な”ユニットを特定する ユニットは、その中に含まれているデータの割合がある閾値を超えた時に密であるとする Apriori propertyに基づいて探索される 2nd step 連結高濃度ユニットを 覆う最大領域を決定し、 クラスタとする

Apriori Property Apriori property k次元ユニットが密ならば、そのユニットを(k-1)次元空間に射影したものも密である あるk次元ユニットにおいて (k-1)次元空間への射影が密ではない ↓ k次元ユニットも密ではない k-1次元空間で見つかった高濃度ユニットから、k次元空間における高濃度ユニットの候補を生成することが可能

CLIQUEの特徴 入力の順序が結果に影響しにくい データ分布を推測する必要がない 入力サイズに線形時間 データの次元が増えた時に良い拡張性を示す 手法の単純さを犠牲にして、結果の精度を悪化させている

8.8 Model-Based Clustering Methods

Model-Based Clustering 与えられたデータと、ある数学的モデルとの適合性を最適化する 主に2つのアプローチがある 統計的アプローチ(statistical approach) ニューラルネットワーク (neural network approach)

Statistical Approach 概念クラスタリング(conceptual clustering) 機械学習におけるクラスタリングの方法 最初に類似したオブジェクトのグループを特定し、その後、各グループの特徴を見つけ出す（この点が従来のクラスタリングと異なる） 各グループは概念またはクラスを表す 多くの手法では、概念あるいはクラスを決定するために確率的尺度を用いている

概念クラスタリングの例 COBWEB classification treeという階層構造を生成する

Neural Network Approach 各クラスタを見本(exemplar)として表す 見本はクラスタの”プロトタイプ”として振舞う 新たなオブジェクトは、何らかの距離尺度に基づいて、最も類似している見本を持つクラスタへ分配される 有名なものに次の2つの手法がある 競合学習(competitive learning) 自己組織化特徴マップ (self-organizing feature maps)

8.9 Outlier Analysis

Outlierってなに outlier 他のデータと著しく異なっていたり、つじつまの合わないデータ 例：年齢が999歳

Outlier Mining outlierそのものに特別な関心がある場合がある 不正行為の特定 特別なマーケティング 医療における分析 クレジットカードの異常な使用の特定 特別なマーケティング 極端に低い、あるいは高い収入をもつ人のふるまいを識別する 医療における分析 医療手当に対する異常な反応の発見 outlierを発見し、分析すること →outlier mining

Outlier Miningの方法(1/2) 統計的アプローチ(statistical approach) 与えられたデータ集合に対して確率モデル（正規分布とか）を仮定し、モデルに対しdiscordancy test(不一致テスト)を用いることでoutlierを識別する テストの適用には データ集合のパラメータ(データ分布など) 分布のパラメータ(平均値や分散など) 予測されるoutlierの数 が必要となる

Outlier Miningの方法(2/2) 距離に基づくアプローチ (distance-based approach) データの集合Sのうち、少なくとも割合pのオブジェクトが距離d以上離れているとき、そのオブジェクトはoutlierであるとする 偏差に基づくアプローチ (deviation-based approach) グループに含まれているオブジェクトの主な特徴を調べることにより、outlierを特定する この特徴から逸脱していると考えられるオブジェクトはoutlierとみなされる