「距離とクラスタリング」

九州大学 大学院システム情報科学研究院
情報知能工学部門
データサイエンス実践特別講座
備瀬竜馬, Diego Thomas, 正井克俊

データ（ベクトル）間の距離、類似度2

データ解析における「距離」とは？
●データ解析における「距離」●要するにデータ間の類似度 （似てない具合）●距離が小さい2データは「似ている」●単位がある場合もない場合も𝒚𝒙𝒛3

距離がわかると何に使えるか？
実は超便利！
●データ間の「類似度」を定量的に比較できる●「xとyは全然違う/結構似ている」 「xとyは28ぐらい違う」●「xにとっては，yよりもzのほうが似ている」●データ集合のグルーピングができる●似たものとどおしでグループを作る●データの異常度が測れる●他に似たデータがたくさんあれば正常，一つもなければ異常[Goldstein, Uchida, PLoSONE, 2016]

ユークリッド距離 (1)●地図上の2点𝑥1
𝒙= 𝑥 ,
2𝑦1
𝒚= 𝑦2

𝒚𝑦2

𝒙𝑥2

この間の距離は？
𝑥 − 𝑦 と記載

𝑥1𝑦1

ユークリッド距離 (2)●2次元の場合

𝒙と𝒚の距離の二乗●3次元の場合

𝒙と𝒚の距離の二乗

𝒙𝑥1𝑥2

𝒚𝑦1𝑦2

𝒙𝑥1𝑥2
𝑥3

𝒚𝑦1
𝑦2
𝑦3

要素の差の二乗

要素の差の二乗

要素の差の二乗
要素の差の二乗
要素の差の二乗ユークリッド距離 (3)●𝐷次元の場合

𝒙と𝒚の距離の二乗

𝒙𝑥1
⋮𝑥𝐷

𝒚𝑦1
⋮𝑦𝐷

要素の差の二乗⋮
要素の差の二乗というわけで，何次元ベクトルでも距離は計算可能

もちろん1次元ベクトル(数値)間の距離も計算可能

𝑥1 − 𝑦1 2

マンハッタン距離

ユークリッド距離

L1距離(マンハッタン距離)8マンハッタン？
●斜めには行けない街●平安京距離どのコースも同じマンハッタン距離！

●平城京距離●札幌距離

でもいいかも●「市街地距離」と呼ばれることもGoogle map

9マンハッタン距離:プログラミング (7)●N次元の場合𝑥1
𝒙= ⋮ ,𝑥𝑁

𝑦1
𝒚= ⋮𝑦3𝒙と𝒚の距離= 𝑥1 − 𝑦1 + ⋯ + 𝑥𝑁 − 𝑦𝑁
各要素の差の絶対値の和

np.linalg.norm(x-y, ord=1) で計算できる※ ユークリッド距離が「L2」ノルム、マンハッタン距離が「L1」ノルムとも呼ばれるため

10

ユークリッド距離で測る類似度
256 × 256

256 × 256

256 × 25665536次元ベクトル 𝒛65536次元ベクトル 𝒙65536次元ベクトル 𝒚

画像間距離

画像間距離

𝒙−𝒚𝒙−𝒚12249.03<16957.99

人の目には 𝒛 より 𝒚 の方が 𝒙 に類似しているが、ユークリッド距離だと、 𝒛 の方が 𝒙 からの距離が近い

11

他の類似度
イメージ図
𝒛𝒙12249.03<16957.99

輝度の強さが違うだけで、ベクトルの方向は一緒
𝒚角度で類似度を測る
12内積●内積は角度を考慮した類似度

𝒙∙𝒚= 𝒙𝒚 cos 𝜃𝒙∙𝒚cos 𝜃 =𝒙 𝒚𝒙

𝒚
長さ= 𝒚

𝜃

長さ= 𝒙

各成分２乗して足してルートとったやつ

13

内積●一定の大きさのベクトル𝒚を回転させながら𝒙と内積を取ると...

𝒙∙𝒚=𝟎

𝒚𝒙
𝒙 ∙ 𝒚 →最小

𝒙と𝒚が同一方向なら大きい
逆方向なら小さい𝒙 ∙ 𝒚 →最大𝒙と𝒚の類似度に使えそう!

14正規化相関（コサイン類似度）
 正規化相関𝒙∙𝒚cos 𝜃 =𝒙 𝒚

import numpy as np＃ｘとｙの定義x = np.array([60,180])y = np.array([60,150])＃コサイン類似度
D = np.dot(x,y) # 内積
xd = np.linalg.norm(x) #||x||yd = np.linalg.norm(y) #||y||C = D/(xd*yd) # コサイン類似度
print(C) # 表示15

正規化相関で測る類似度
256 × 256

256 × 256

256 × 25665536次元ベクトル 𝒛65536次元ベクトル 𝒙65536次元ベクトル 𝒚画像間
コサイン類似度

0.932

画像間距離
コサイン類似度<1.016

まとめ:numpy を使えば簡単●ユークリッド距離●マンハッタン距離
●内積

●コサイン

17

練習１：2つのデータ間の各類似度：
ユークリッド距離、マンハッタン距離、内積、コサイン類似度を求めよう

3
6𝒙=,𝒚 =のとき 各類似度は？
5136𝒙 = 5 , 𝒚 = 1 のとき 各類似度は？
2218

距離を使ったちょっと高度な可視化（１）●csvファイル” height_weight.csv”を読み込み、「横軸：身長、縦軸：体重」としてプロットして、分布の形状を確かめたい。ある点Aを別の色で表示してみたい。

こうすればpandasで読み込んだデータが一発でnumpy のデータセット（複数のベクトル）にできます

色マーカーの形

マーカーのサイズ

可視化結果距離を使ったちょっと高度な可視化（２）●A=(180,75)からの各点へのユークリッド距離をそれぞれ算出し、最も距離が遠い順に並び替えて、距離に応じて色を変えて表示

小さい順に並べたときのインデックスを返す関数
例：np.argsort([2,1,3])=[1,0,2]

逆から並べる

距離を使ったちょっと高度な可視化（２）●距離に応じて色を変えて表示# visualize
import matplotlib.cm as cm
import matplotlib.pyplot as plt
count = 0
# 距離の近い順にプロット
for i in sinds:
row = vlist[i]# 並び順に応じて色を決定
c = cm.hot(count/len(vlist))# 決定した色を指定してプロット
plt.scatter(row[2],row[3],color=c)count += 1
# 点Aの可視化
plt.scatter(A[0], A[1], c=‘green’,marker=‘+’, s=60)

遠いほど赤いK-Means

データのクラスタリング(分類)データ集合をグルーピングする●我々は「距離」や「類似度」を手に入れた●結果，「与えられたデータ集合」を「それぞれ似たデータからなる幾つかのグループに分ける」ことが可能に！

24

クラスタリング(clustering)＝
データの集合をいくつかの部分集合に分割する(グルーピング)●各部分集合＝「クラスタ」と呼ばれる

25

各クラスタから代表的なデータを選ぶと...
これらの代表データを見るだけで，データ集合全体の概略が見える

26

どういう分割がよいのか？
●𝑁個のデータを𝐾個に分割する方法はおよそ𝐾 𝑁 通り
●100個のデータを10分割→およそ10100 通り●近くにあるデータが，なるべく同じ部分集合になるように
27

代表的なクラスタリング法：
K-means法（0）初期代表パターン

例えばランダムに与える28代表的なクラスタリング法：
K-means法（1）学習パターン分割

代表パターンのファンクラブ（支持者集合）29

代表的なクラスタリング法：
K-means法（2）代表パターン更新

この中の学習パターンの平均に移動30代表的なクラスタリング法：
K-means法（1）学習パターン分割

31代表的なクラスタリング法：
K-means法（2）代表パターン更新

以後，代表パターンが動かなくなるまで反復
32

K-means：プログラミング●ステップ0：●データ入力●クラスタ数 K の決定

33

K-means：プログラミング●ステップ1：●初期代表点の決定（ランダム）34

K-means：プログラミング●ステップ１：●代表点の支持者決定

B⇒最も近い代表点を支持する
距離を活用！
●ある点Xに着目

CAD•各代表点までの距離を算出
X＃XとAの距離の計算
Ad = numpy.linalg.norm(X-A)
35

K-means：プログラミング●ステップ１：●ある点Xに着目

B●距離が最も近い代表点を決定

CA

DX36K-means：プログラミング●ステップ１：●全ての点で代表点を決定

B

DAC
X

37

K-means：プログラミング●ステップ2：代表点を更新●各クラスタの支持者群の平均値をB代表点とする。
DA

C
X

38

K-means：プログラミング アルゴリズム0.01

ステップ0繰り返し•代表点の選択•代表点の更新•終了チェック

39

K-meansクラスタリング

40

K-meansクラスタリング

41

K-meansクラスタリング

42

K-meansクラスタリング

43

K-meansクラスタリング

44

K-meansクラスタリング

45

K-meansクラスタリング46

ライブラリを使った K-Means クラスタリング

クラスタの中心たち

各データがどのクラスタか（クラスタ０～クラスタ３）

可視化も簡単

演習

演習１●csvファイル” height_weight.csv”を読み込み、A=(180,75)からの各点への正規化相間（類似度）をそれぞれ算出し、類似度の小さい順に並び替えて表示●ヒント）1行目は項目名なので、無視●正規化相間の大きさで色を変えてプロットせよ●ヒント）import matplotlib.cm as cmcm.hot

演習２●クラスタリングの対象となるcsvデータ“data.csv”を読み込み●K=2, 3, 4 でそれぞれ K-means クラスタリングせよ●余裕がある人は自分で K-means を実装せよ

51

アイリスデータ（１） 3クラス
 Iris-setosa Iris-versicolor
 Iris-virginica
 指標
 sepal length sepal width petal length petal width

https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data52

アイリスデータ（２）Sepal width・ Iris-setosa・ Iris-versicolor
・ Iris-virginica

Sepal length53

petal widthSepal width

アイリスデータ（３）Petal length

petal width

Petal length

Sepal length・ setosa・ versicolor
・ virginica

Sepal length

Sepal width

54

演習３
●“iris.csv”を読み込み、以下の２つの指標だけで、K=３でクラスタリング可能か可視化せよ●指標１●sepal length●sepal width●指標２

・自分で K-means を実装
・ライブラリの K-means
どっちもやってみましょう●sepal width●petal width

実際のクラスと見比べてみよう
55