不等式女性男性

非ユークリッド関係性データの
局所的な視覚化
大阪府立大学 大学院 工学研究科
○山本剛史 本多克宏 野津亮 市橋秀友
目次
I. はじめに
II. Fuzzy c-Medoidsに基づく線形クラスタリング
III. 関係性データの局所的な視覚化
IV.数値実験
V. おわりに
目次
I. はじめに
II. Fuzzy c-Medoidsに基づく線形クラスタリング
III. 関係性データの局所的な視覚化
IV.数値実験
V. おわりに
はじめに
研究背景
リレーショナルクラスタリング：
関係性データに内在するデータ構造を抽出
 Relational Fuzzy c-Means(RFCM) [Hathaway and Bezdek 1989]
 Fuzzy c-Meansの関係性データへの拡張版
 Non Euclidean Relational Fuzzy(NERF) c-Means
[Hathaway and Bezdek 1994]


非ユークリッドな関係性データへ対応
Fuzzy c-Medoids(FCMdd)に基づく線形クラスタリング

[Haga et al. 2010]
関係性データから線形構造を抽出
非ユークリッドな関係データからの
線形構造の抽出できるように拡張 [Yamamoto et al. 2010]
はじめに
本研究の目的
 関係性データの局所的な視覚化
抽出した線形構造を利用
 クラスターにおける局所的な主成分得点よ
る低次元マップを作成
 低次元マップからの知識発見

FCMddに基づく線形クラスタリングを非ユークリッド
な関係性データに実行，クラスターごとに視覚化
目次
I. はじめに
II. Fuzzy c-Medoidsに基づく線形クラスタリング
III. 関係性データの局所的な視覚化
IV.数値実験
V. おわりに
関係性データ
2
D

{
d
 各データ間の関係を表す行列
ij } i, j  1,2,..., n


非類似度：どれだけデータが似ていないか
データ間の距離のみ： プロトタイプ計算が困難
体重(kg)
65
男性
class
1
⑤
④
⑥
60
55
②
①
プロトタイプ
③
50
女性
class
160 165 170 175 180
身長
(cm)
1
2
3
4
5
6
2
3
4
5
6
0.0 5.00 11.2 11.2 14.1 20.6
5.00 0.0 7.1 7.1 11.2 15.8
11.2 7.1 0.0 10.0 15.0 14.1
11.2 7.1 10.0 0.0 5.00 10.0
14.1 11.2 15.0 5.00 0.0 11.2
20.6 15.8 14.1 10.0 11.2 0.0
関係データは通常の方法では，クラスタリング困難
Fuzzy c-Medoids (FCMdd)
[Krishnapuram et al. 2001]
体重
(kg)
65
Medoid
男性
class
60
プロトタイプ：データ点から選択
距離のみで表現
Medoid
55
女性
class
50
160
165
170
Medoids
175
180
身長
(cm)
関係性データに適用可能
Medoidを2点選択
プロトタイプを直線に拡張
Prototype Line
FCMddに基づく線形クラスタリング
[Haga et al. 2010]
 直線プロトタイプの定義
x c2 を通る直線
2つのmedoids xc1 ，
Linec (xc1 , xc2 )  {x | x  xc1  t (xc2  xc1 ); t  R}
d (xi , Linec ) : 直線 Linecとデータ点 x i の距離
xi
d c1i
xc1
d ( xi , Linec ) 
2
d c2 i
dc1c2
x c2
2
d c1i

(d c21i  d c22i  d c21c2 ) 2
4d c21c2
Linec
関係性データで線形クラスタリング可能
FCMddに基づく線形クラスタリング
[Haga et al. 2010]
アルゴリズム:以下の2stepの繰り返し
1. 直線プロトタイプを定義するMedoidを2点選択
2. 各クラスのメンバシップ（所属度合い）更新
直線プロトタイプとデータ点との誤差の総和の最小化
C
n
min L fcmdd   uci Dci
 : fuzzifier
c 1 i 1
C
s.t.　uci  0,1　 uci  1
c 1
Dci  d 2 ( xi , Linec )

d c21i

( d c21i  d c22i  d c21c2 ) 2 uci
4d c21c2
 C
 Dci 


 

 l 1  Dli 



1
 1





1
非ユークリッド関係データの問題点
問題点 : 三角不等式が不成立
dc1i  dc2i  dc1c2
xi
d c1i
xc1
d 2 ( xi , Linec )  d c21i 
d c2 i
dc1c2
dc1i  dc2i  dc1c2
(d c21i  d c22i  d c21c2 ) 2
4d c21c2
x c2 Linec
非ユークリッドな関係データ
ユークリッド
 - spread transformation
β-spread transformation
[Hathaway and Bezdek 1994]
関係性データ D の非対角成分に  を追加
D  D    (M  I )
1  1


I ：単位行列
M    
1  1
P  I  (1 / n)M


もし が PDP の最大固有値ならば，
D は完全にユークリッド
 が最大固有値よりもずっと小さい値でも
クラスタリングの性能は向上
β-spread transformation
[Hathaway and Bezdek 1994]
xi
d c2 i  
d c1i  
dc1i  dc2i  dc1c2
Linec dc1i    dc2i    dc1c2  
x c1
dc1c2  
x c2
• 三角不等式が成立
• ユークリッド空間に存在
非ユークリッドな関係データ
ユークリッド
クラスタリング基準が負にならないために，
三角不等式を満たすように を自動的に更新
目次
I. はじめに
II. Fuzzy c-Medoidsに基づく線形クラスタリング
III. 関係性データの局所的な視覚化
IV.数値実験
V. おわりに
関係データの局所的な視覚化
Hagaらは線形ファジィクラスタリングとファジィ主成分分析
との類似性から，関係性データの低次元視覚化法を提案
各クラスターの局所的な主成分得点を使って視覚化
medoids
直線プロトタイプ
f ci2
(d ci21  d ci2 2  d c212 ) 2

：第cクラスターの主成分得点
2
4d c12
関係性データに内在するデータ構造を1次元視覚化
アルゴリズム
Step.1   0 とし，プロトタイプmedoidsの初期化．
Step.2 クラスタリング基準 Dci の計算
Step.3 もし，Dci  0 なら，      を更新．
  max{ dc1c2  dc1i  dc2i   }
Step.4
Step.5
Step.6
Step.7
メンバシップ uci の更新
各々のクラスターのmedoids xc1 ， xc2 探索
収束条件を満たすまでStep2-5の繰り返し
結果から関係データの局所的な視覚化
目次
I. はじめに
II. Fuzzy c-Medoidsに基づく線形クラスタリング
III. 関係性データの局所的な視覚化
IV.数値実験
V. おわりに
数値実験
局所的な視覚化をテキストマイニングに適用
 テキストの非ユークリッドな関係性データを
FCMddに基づく線形クラスタリングに適用
 クラスタリング結果から局所的な視覚化
 視覚化されたデータからの知識発見
数値実験
夏目漱石「こころ」のText Map
2
夏目漱石「こころ」
 上36節，中18節，下56節
 １０個キーワードの出現回
数に関するテキストデータ
 Extended Jaccard係数で関
係性データを作成
作成したこころの非ユークリッドな関係性データ
-2 にFCMddに基づく線形クラスタリングを適用
-1 0
1
2
上
中
下
0
-2
Extended Jaccard係数：類似度を計算するための係数
 キーワードの出現頻
k 1

度で類似度計算
10
10
10
k 1 xik2  k 1 x2jk  k 1 xik x jk  類似度を非類似度に
変換
xik：節iでのキーワードkの出現回数
10
sij
xik x jk
数値実験（クラスタリング結果）
：クラスター1
：クラスター2
：あいまいなメンバシップ
：medoids
2
1
0
 線形構造の抽出に成功
 上，中と下の節に分類
  - spread transformation 実行
  0.3313997
-1
-2
-3
-2
-1
0
1
2
クラスタリング結果
抽出した線形構造から低次元視覚化を実行
数値実験（局所的な視覚化）
節番号
クラスター1
2
40
1
0
-1
-2
:上
:中
0
0.5
1
局所主成分得点の１次元マップ
20
: 上
: 中
0
0
0.5
1
• 上に属する節と，中に属する節がきれいに分割
• 前後の節と内容が乖離した外れ値が一部存在
• 中に属する節では，節番号とクラスター1 における主成
分得点の間に-0.50051 の負の相関
数値実験（局所的な視覚化）
節番号
クラスター2
2
100
1
90
0
-1
-2
:下
0
0.5
1
80
70
:下
局所主成分得点の１次元マップ
0
0.5
1
• それぞれの節は下における中心的人物である「K」
というキーワードに強い影響
• 「K」の登場前（第72 節まで）と，登場後の節で分割
目次
I. はじめに
II. Fuzzy c-Medoidsに基づく線形クラスタリング
III. 関係性データの局所的な視覚化
IV.数値実験
V. おわりに
おわりに
 非ユークリッドな関係データの局所的な視覚化
 局所的な主成分得点による低次元マップ作成
テキストマイニングに適用
低次元マップによってデータの直感的理解が可能
低次元マップから局所的な相関関係を抽出
今後の課題
実世界のデータでの低次元視覚化の適用，
多次元プロトタイプへの拡張
Extended Jaccard係数(予備資料)
Jaccard係数： キーワードの共起情報による類似
とあるキーワードに関する２者間の共起
度計算方法
sij
a

abc
1
0
total
1
0
total
a
b
ab
c
ac
bd
m
d
cd
 Extended Jaccard係数：Jaccard係数を拡張
sij 

m
k 1
2
xik


m
xik x jk
k 1
m
x 2jk
k 1


m
k 1
xik x jk
xik ：節iでのキーワードkの出現回数
dij  max skl  sij 類似度から非類似度へと変換
k ,l