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の影響を
受けにくい
 k-means法に比べて処理コストがかかる
 クラスタの数kをあらかじめ指定する必要が
ある
大きなデータベースへの適用
• 大きなデータベースに対する効率的な分割
アルゴリズム
– CLARA(Clustering LARge Applications)
– CLARANS(Clustering LARge Applications
based upon RANdomized Search)
CLARAとCLARANS
• CLARA
– データの集合全体について考える代わりに、デー
タの小さなサンプルをとって考える
– このサンプルの中から、PAMを用いてmedoidを決
定する
– サンプルをいくつかとり、得られた結果の中から
最も良いものを出力する
• CLARANS
– CLARAを改良したもの
– medoidを更新した時に新たにサンプリングを行う
点において、CLARAと異なっている
8.5
Hierarchical Methods
Hierarchical Methods
• 与えられたデータオブジェクトの集合に対す
る、階層構造(hierarchical decomposition)を
生成する
• 階層構造がボトムアップ的に形成されるか
トップダウン的に形成されるかによって、凝集
型(agglomerative)と分枝型(divisive)に分かれ
る
2つのタイプのメソッド
【凝集型メソッド】(ボトムアップ)
2
3
step 0
1
4
a
ab
b
abcde
c
cde
d
de
e
4
3
2
1
step 0
【分枝型メソッド】(トップダウン)
階層的手法の難しさ
• 純粋な階層的クラスタリングでは、一度マー
ジあるいは分割が行われると、それを修正す
ることができない
• 階層的手法の質を向上させるアイデア
→他のクラスタリング手法を組み合わせる
– 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つの要素で表す
CF  ( N , LS , SS )
• N : クラスタ内の点の数
• LS: N点の線形和
• SS: N点の二乗和
• CF tree
– clustering featureを格納する平衡木
– nonleaf nodeには、その子ノードが持って
いるCFの総和が格納される
CF Tree
node A (root: 全てのデータ)
nodeBの nodeCの nodeDの
CF
CF
CF
node C
node B
CF
CF
CF
CF
node D
CF
オブジェクトの集合(サブクラスタ)
CF
CF
CF
CF
アルゴリズムの流れ
• Phase 1
– データベースをスキャンしてCF木を作る
– オブジェクトが挿入されるたびにCF木が動
的に構築されていく
– オブジェクトは、最も距離が近い葉エント
リーに挿入される
– CF木のサイズが主記憶の容量を超えたら、
CF木を再構築する
• Phase 2
– 既存のクラスタリングアルゴリズムを適用
し、CF木の葉ノードをクラスター化する
BIRCHの特色
 計算時間がオブジェクト数に対して線形
 入力されたオブジェクトに対して動的なクラス
タリングが可能
 高速で実行可能で、大きなデータベースにも
拡張可能
 CF木の各ノードはある限られた数のエント
リーしか持つことができないため、CF木の
ノードはユーザから見て「自然な」ものになっ
ているとは限らない
 クラスタの形が球状でない場合、うまく働か
ない
8.6
Density-Based Methods
Density-Based Methods
• 密度(density)の概念に基づく
• その“近傍”(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
Oから
density-reachable
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という階層構造を生成す
る
Animal
P(C0)=1.0
P(scales|C0)=0.25
…
Fish
P(C1)=0.25
P(scales|C1)=1.0
…
Amphibian
P(C2)=0.25
P(moist|C2)=1.0
…
Mammal
P(C4)=0.5
P(hair|C4)=1.0
…
Mammal/bird
P(C3)=0.5
P(hair|C3)=0.5
…
Bird
P(C5)=0.5
P(feathers|C5)=1.0
…
Neural Network Approach
• 各クラスタを見本(exemplar)として表す
• 見本はクラスタの”プロトタイプ”として振舞う
• 新たなオブジェクトは、何らかの距離尺度に
基づいて、最も類似している見本を持つクラ
スタへ分配される
• 有名なものに次の2つの手法がある
– 競合学習(competitive learning)
– 自己組織化特徴マップ
(self-organizing feature maps)
8.9
Outlier Analysis
Outlierってなに
• outlier
– 他のデータと著しく異なっていたり、つじつ
まの合わないデータ
– 例:年齢が999歳
• 多くのデータマイニングアルゴリズムは、
outlierによる影響を最小化したり、outlierを取
り除くことを試みている
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とみなされる
ダウンロード

PPT - 徳山研究室