Mean shift clustering

67 %
33 %
Information about Mean shift clustering
Technology

Published on March 15, 2014

Author: ssuser29c971

Source: slideshare.net

Description

This document was made in order to explain "Mean shift clustering" which is one of Clustering methods.

. はじめに .. ...... 岡田 和典「ミーンシフトの原理と応用」情報処理学会研究報告. CVIM, [コンピュータビジョンとイメージメディア] 2008(27), pp.401-414, 2008-03-10 を紹介する. 今回は特に”原理”部分に焦点を当てる. . ...... 発表:数理科学コース B4, 奥野彰文,2013 年 6 月 14 日 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 1 / 12

[予備知識 1] k-means S := {xi}n i=1 ⊂ Rd :given dataset k ∈ N :クラスタの数 (given) C := {C1, ..., Ck} :クラスタ µ(Ci) := E {xj ∈ Ci} ∈ Rd :クラスタの平均点 E := k∑ i=1 ∑ xj∈Ci ∥xj − µ(Ci)∥2 E が最小となるよう、xj の配属先 Ci を決定する. 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 2 / 12

[予備知識 2] 勾配法 (別名:山登り法、最急降下法) f : Rd → R の x ∈ Rd 方向への微分は df dx = ∇f · ∆x = |∇f||∆x| cos θ 2 0 2 4 6 2 0 2 4 6 0.0 0.1 0.2 0.3 . 勾配法の更新式: xt+1 = xt + γ∇f(xt) (γ を決めるのは意外と難しい) 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 3 / 12

. Kernel の定義: .. ...... 以下の性質を満たす関数 K (·) : Rd → R を「Kernel」と呼ぶ. (1) 非負実数値を取り可積分. (2) ∫ Rd K (x) dx = 1. (3) K (−x) = K (x) for all x ∈ Rd. 例) 正規カーネル:Kg (x) = Ag exp ( −1 2 ∥x∥2 ) . Kernel の表示 .. ...... Kernel K (·) は x ≥ 0 上有界で区分的に連続な非負値関数 k(x) を用いて 定義される: K (x) = k(∥x∥2 ) ここで k(x) を特に「プロファイル」とも呼ぶ. 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 4 / 12

. Kernel Density Estimation(KDE) .. ...... ˆf(x) := 1 nhd ∑ xi∈S K ( x − xi h ) = 1 nhd ∑ xi∈S k ( ∥ x − xi h ∥2 ) 例) K (·) = Kg (·):正規カーネル, S = {−2, 0, 0.5, 1, 2} ⊂ R1, 4 2 0 2 4 0.05 0.10 0.15 0.20 0.25 0.30 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 5 / 12

別のカーネルを使ってみる (データは同じ): 4 2 0 2 4 0.05 0.10 0.15 0.20 0.25 0.30 Figure: Epanechnikov カーネル 4 2 0 2 4 0.05 0.10 0.15 0.20 0.25 0.30 Figure: フラットカーネル . KDE の評価 .. ...... S が確率密度関数 f を持つ一次元データ列であるとき、 ∃C > 0 s.t. ∫ R ( ES { ˆf(x) } − f(x) )2 dx ≤ Ch4 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 6 / 12

福永のミーンシフト S := {xi}n i=1 ⊂ Rd :given dataset, h ∈ R > 0 :fixed radius, m(µ) := E {xi ∈ S | ∥µ − xi∥ ≤ h} : Rd → Rd 初期値 ˜x0 ∈ Rd を与え ˜xt+1 := m( ˜xt) より ˜x1, ˜x2, ... を生成する. 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 7 / 12

ここに” フラットカーネル” Kf (x) := { Af (∥x∥ ≤ 1) 0 (∥x∥ > 1) を導入すると、福永のミーンシフトは以下のように書き直せる: . 福永のミーンシフト .. ...... ˜xt+1 = m( ˜xt) := ∑ xi∈S Kf ( xi− ˜xt h ) xi ∑ xi∈S Kf ( xi− ˜xt h ) . (ここで Kf ( xi− ˜xt h ) = Af ⇔ ∥xi − ˜xt∥ ≤ h を考えると納得しやすい.) Kernel K (·) を入れ替えれば、もっと一般にミーンシフトを拡張できる. 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 8 / 12

カーネル密度推定とミーンシフトの関係 ∇ ˆfK(x) = ∇    1 nhd ∑ xi∈S k ( ∥ x − xi h ∥2 )    = 1 nhd ∑ xi∈S 2(x − xi) h2 k′ ( ∥ x − xi h ∥2 ) = 2 h2    1 nhd ∑ xi∈S k′ ( ∥ x − xi h ∥2 )    × { x − ∑ xi∈S k′ ( ∥x−xi h ∥2 ) xi ∑ xi∈S k′ ( ∥x−xi h ∥2 ) } = 2 h2 ˆfG(x)(mG(x) − x). (g = −k′ ) . ...... mG(x) − x = h2 2 ˆfG(x) ∇ ˆfK(x) =: γ(x)∇ ˆfK(x) 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 9 / 12

G, K がプロファイル g, k を持つとき、g = −k′ であれば、「K は G の シャドウ (カーネル) である」という. ここで . ...... (1) カーネル G でのミーンシフト (2) G のシャドウカーネル K での KDE の勾配法 が対応する. フラットカーネル Kf (x) のシャドウは Ke (x) = { Ae(1 − ∥x∥2) (∥x∥ ≤ 1) 0 (otherwise) (Epanechnikov カーネル) であることから、 . ...... (1) フラットカーネルでのミーンシフト (2) Epanechnikov カーネルでの KDE の勾配法 が対応する. (ミーンシフトを行う=Epanechnikov カーネルから求まる KDE の局所的最大点を探している) 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 10 / 12

ここで G が正規カーネルであれば、K も正規カーネルであるから、 . ...... (1) 正規カーネル G のミーンシフト (2) 正規カーネル K の KDE の勾配法 が対応する. S := {−2, −1.5, 1, 1.5, 2} ⊂ R1, h = 1 での KDE: 4 2 0 2 4 0.05 0.10 0.15 0.20 0.25 0.30 C1 = {−2, −1.5}, C2 = {1, 1.5, 2}. 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 11 / 12

データセット S := {xi}n i=1 ⊂ Rd をクラスタリングする. . ミーンシフトクラスタリング .. ...... (1) データセットを丸ごとコピーして初期値の集合 T = {y1, ..., yn} := S を作る. (2) 各初期値 yi ∈ T でミーンシフトを行うa (3) ミーンシフトの結果が等しい初期値を” 同じグループ” としてクラス タリング. a この処理は並列化が可能. 便利な点 (1) k-means や EM などのアルゴリズムとは異なり、 クラスターの数を指定する必要がない (2) 外れ値に強い. (3) 並列化が可能+計算がシンプルで楽 奥野彰文 (数理科学コース 4 年) ミーンシフトの紹介と原理 2013 年 6 月 14 日 12 / 12

Add a comment

Related presentations

Related pages

Mean shift - Wikipedia, the free encyclopedia

Mean shift is a non-parametric feature-space ... The weighted mean of the density ... Java-based mean-shift implementation for numeric data clustering and ...
Read more

Mean Shift Clustering Overview - Atomic Spin

Mean shift clustering is one of my favorite algorithms. It’s a simple and flexible clustering technique that has several nice advantages over other ...
Read more

Mean shift-clustering

Mean Shift Clustering The mean shift algorithm is a nonparametric clustering technique which does not require prior knowledge of the number of clusters ...
Read more

k-means clustering - Wikipedia, the free encyclopedia

k-means clustering, and its associated expectation-maximization algorithm, is a special case of a Gaussian mixture model, ... Mean shift clustering
Read more

Mean Shift Clustering - File Exchange - MATLAB Central

File Information; Description: Clusters data using the Mean Shift Algorithm. testMeanShift shows an example in 2-D. Set plotFlag to true to visualize ...
Read more

The mean shift clustering algorithm – EFavDB

Mean shift clustering is a general non-parametric cluster finding procedure — introduced by Fukunaga and Hostetler [1], and popular within the computer ...
Read more

2.3. Clustering — scikit-learn 0.17.1 documentation

Mean Shift¶ MeanShift clustering aims to discover blobs in a smooth density of samples. It is a centroid based algorithm, which works by updating ...
Read more

Mean Shift Clustering [Derpanis] - scribd.com

Mean Shift ClusteringKonstantinos G. Derpanis August 15, 2005. Mean shift represents a general non-parametric mode findi...
Read more

MEAN SHIFT SEGMENTATION - TU Dresden

MEAN SHIFT SEGMENTATION An advanced and versatile technique for clustering-based segmentation Let {x i} i=1…n be the original image points, {z
Read more

Mean Shift Clustering - Computer Science

Mean Shift Clustering Konstantinos G. Derpanis August 15, 2005. Mean shift represents a general non-parametric mode finding/clustering proce-dure.
Read more