![距離がわかると何に使えるか？
実は超便利！
●データ間の比較が定量的にできる
●「xとyは全然違う/結構似ている」 「xとyは28ぐらい違う」
●「xにとっては，yよりもzのほうが似ている」
●データ集合のグルーピングができる
●似たものとどおしでグループを作る
●データの異常度が測れる
●他に似たデータがたくさんあれば正常，
一つもなければ異常
[Goldstein, Uchida, PLoSONE, 2016]](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-4-320.jpg)
![ユークリッド距離:プログラミング (１０)
12
●2次元の場合 ? =
?1
?2
, ? =
?1
?2
＃xとyの距離の二乗：各要素の二乗和
d2 = (x[0]-y[0])**2 + (x[1]-y[1])**2
＃平方根
d = math.sqrt(d2)
# 表示
print d
なるべく一般化してプログラムを記載！
これなら、 ? と ? への入力後は同じ](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-12-320.jpg)
![ユークリッド距離:プログラミング (１１)
13
●３次元の場合 ? =
?1
?2
?3
, ? =
?1
?2
?3
＃xとyの距離の二乗：各要素の二乗和
d2 = (x[0]-y[0])**2 + (x[1]-y[1])**2
＋ (x[2]-y[2])**2
＃平方根
d = math.sqrt(d2)
# 表示
print d
次元が変わると、プログラムが変わってしまった
?1000次元だと、1000個分の要素を書かないといけない？](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-13-320.jpg)
![ユークリッド距離:プログラミング (１２)
14
●N次元の場合 ? =
?1
?
? ?
, ? =
?1
?
?3
＃xとyの距離の二乗：各要素の二乗和
for ii in range(len(x)):
d2 += (x[ii]-y[ii])**2
＃平方根
d = math.sqrt(d2)
# 表示
print d
何次元になっても、同じプログラムで表記できる。
?関数にしておくと、繰り返し簡単に使える。](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-14-320.jpg)
![ユークリッド距離:プログラミング (１３)
15
import numpy
＃ｘとｙの定義
x = numpy.array([60,180])
Y = numpy.array([60,150])
＃xとyの距離の計算
d = numpy.linalg.norm(x-y)
実は、pythonに関数が用意されている。
Webで調べて既にあるものを利用するのも
プログラミングの大事なスキル！](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-15-320.jpg)
![マンハッタン距離:プログラミング (7)
19
●N次元の場合 ? =
?1
?
? ?
, ? =
?1
?
?3
for ii in range(len(x)):
d2 += numpy.abs(x[ii]-y[ii])
# 表示
print d
?と ?の距離= ?1 ? ?1 + ? + ? ? ? ? ?
各要素の差の絶対値の和
絶対値](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-19-320.jpg)
![マンハッタン距離:プログラミング (7)
20
import numpy
＃ｘとｙの定義
x = numpy.array([60,180])
Y = numpy.array([60,150])
＃xとyの距離の計算
d = numpy.linalg.norm(x-y, 1)
こちらも、pythonに関数が用意されている。](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-20-320.jpg)
![練習1: 距離
●ユークリッド距離（任意の次元）を計算する関数を自身で定義して、
下記のベクトル間のユークリッド距離を求めよ
●例１）A=[10,8], B=[5,3]
●例２）A=[10,8,3], B=[5,3,7]
●numpyのデフォルトの関数を実行して結果が同じか比較せよ
●マンハッタン距離（任意の次元）を計算する関数を自身で定義して、
上記のベクトル間のマンハッタン距離を求めよ
21](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-21-320.jpg)
![分布の可視化
●csvファイル” height_weight.csv”を読み込み、「横
軸：身長、縦軸：体重」としてプロットして、分布の形状を
確かめよう。点Aを別の色で表示しよう。
plt.scatter(vlist[:,0], vlist[:,1],c='blue',marker='o',s=30)
plt.scatter(A[0], A[1],c=‘red’,marker=‘+’,s=100)
色 マーカー
の形
マーカー
のサイズ](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-23-320.jpg)
![距離の可視化（１）
●A=(180,75)からの各点へのユークリッド距離をそれぞれ
算出し、最も距離が近い順に並び替えて、距離に応じて色
を変えて表示
# compute distances
A = np.array([180,75])
dlist = []
for row in vlist:
d = np.linalg.norm(A-row)
dlist.append(d)
# 距離が短い順に並び替え
sinds = np.argsort(dlist)[::-1]](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-24-320.jpg)
![距離の可視化（２）
●距離に応じて色を変えて表示
# visualize
import matplotlib.cm as cm
count = 0
# 距離の近い順にプロット
for i in sinds:
row = vlist[i]
# 並び順に応じて色を決定
c = cm.hot(count/len(vlist))
# 決定した色を指定してプロット
plt.scatter(row[0],row[1],color=c)
count += 1
# 点Aの可視化
plt.scatter(A[0], A[1], c=‘green’,
marker=‘+’, s=60)](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-25-320.jpg)
![正規化相関：プログラミング
32
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 # 表示](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-32-320.jpg)
![練習４:類似度
●ベクトル間の正規化相間（類似度）を計算する関数を自身で定義
して、下記のベクトル間の類似度と距離を求めよ
●例１）A=[17,16], B=[5,3], C=[4,4]
?A-B、B-C、C-A間についてそれぞれ求めよう
●点A,B、Cへ原点から線を引いて可視化せよ
可視化した点の距離と角度を見て、類似度と距離の違いを考えよ
34](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-34-320.jpg)
![K-means：プログラミング
●ステップ0：
●データ入力
●クラスタ数の決定
45
import csv
＃データの入力
f = open(‘data.csv’,’rb’)
Reader = csv.reader(f)
vlist = []
for row in Reader:
vlist.append([float(row[0]),
float(row[1])])
vlist = np.array(vlist)
f.close()
#k(クラスタ数)の決定
K = 4;](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-45-320.jpg)
![K-means：プログラミング
●ステップ1：
●初期代表点の決定（ランダム）
46
＃random値の範囲決定
a = np.min(vlist[:,0])
b = np.max(vlist[:,0])
c = np.min(vlist[:,1])
d = np.max(vlist[:,1])
#ランダムに決定
Clist = np.c_[(b-a)*np.random.rand(K) + a,
(d-c)*np.random.rand(K) + c]
plt.scatter(vlist[:,0], vlist[:,1])
plt.scatter(Clist[:,0], Clist[:,1])](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-46-320.jpg)
![K-means：プログラミング
●ステップ１：
●全ての点で代表点を決定
49
A
C
B
D
X
def selectCluster(vList,Clist):
cIList = [];
for row in vList:
cIList.append(nearest(row,Clist))
Return cIList](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-49-320.jpg)
![K-means：プログラミング
●ステップ2：代表点を更新
●各クラスタの支持者群の平均値を
代表点とする。
50
A
C
B
D
X
def updateCenter(vlist,CIList):
CList = []
for k in range(K):
Z = []
for j in range(len(CIList)):
if CIList[j] == k:
Z.append(vlist[j])
mc = np.mean(Z,0)
CList.append(mc)
return CList](https://image.slidesharecdn.com/distanceclustering-190124085639/85/-50-320.jpg)
距离とクラスタリング
- 5. データ間の距離?類似度：ユークリッド距離 5 ?地図上の2点 ? = ?1 ?2 , ? = ?1 ?2 ?1 ?2 ?2 ?1 ? ? この間の距離は？
- 6. 最も代表的な距離：ユークリッド距離 (3) ● ?と ?の距離の二乗 = ?1 ? ?1 2 + ?2 ? ?2 2 6 ?1 ?2 ?2 ?1 ? ?
- 7. 最も代表的な距離：ユークリッド距離 (5) ● ?と ?の距離の二乗 = ?1 ? ?1 2 + ?2 ? ?2 2 + ?3 ? ?3 2 7 ?1 ?2 ?2 ?1 ? ? この間の距離は？ ?3 ?3
- 8. 最も代表的な距離：ユークリッド距離 (6) ●2次元の場合 ●3次元の場合 8 ?と ?の距離の二乗 ?1 ?2 ?1 ?2 要素の差の二乗 要素の差の二乗 ?1 ?2 ?3 ?1 ?2 ?3 ?と ?の距離の二乗 要素の差の二乗 要素の差の二乗 要素の差の二乗 ? ? ? ?
- 9. 最も代表的な距離：ユークリッド距離 (7) ● ?次元の場合 9 ?1 ? ? ? ?1 ? ? ? ?と ?の距離の二乗 要素の差の二乗 要素の差の二乗 ? ? ? というわけで，何次元ベクトルでも距離は計算可能 もちろん1次元ベクトル(数値)間の距離も計算可能 ?1 ? ?1 2
- 10. ユークリッド距離:プログラミング (８) 10 ●2次元の場合 ? = 60 150 , ? = 60 180 ?と ?の距離= ?1 ? ?1 2 + ?2 ? ?2 2 import math ＃xとyの距離の二乗：各要素の二乗和 d2 = (60-60)**2 + (150-180)**2; ＃平方根 d = math.sqrt(d2) # 表示 print d
- 11. ユークリッド距離:プログラミング (９) 11 ●2次元の場合 ? = 70 160 , ? = 40 130 import math ＃xとyの距離の二乗：各要素の二乗和 d2 = (70-40)**2 + (160-130)**2; ＃平方根 d = math.sqrt(d2) # 表示 print d 違う値になると、もう一度書き直さないといけない。
- 12. ユークリッド距離:プログラミング (１０) 12 ●2次元の場合 ? = ?1 ?2 , ? = ?1 ?2 ＃xとyの距離の二乗：各要素の二乗和 d2 = (x[0]-y[0])**2 + (x[1]-y[1])**2 ＃平方根 d = math.sqrt(d2) # 表示 print d なるべく一般化してプログラムを記載！ これなら、 ? と ? への入力後は同じ
- 13. ユークリッド距離:プログラミング (１１) 13 ●３次元の場合 ? = ?1 ?2 ?3 , ? = ?1 ?2 ?3 ＃xとyの距離の二乗：各要素の二乗和 d2 = (x[0]-y[0])**2 + (x[1]-y[1])**2 ＋ (x[2]-y[2])**2 ＃平方根 d = math.sqrt(d2) # 表示 print d 次元が変わると、プログラムが変わってしまった ?1000次元だと、1000個分の要素を書かないといけない？
- 14. ユークリッド距離:プログラミング (１２) 14 ●N次元の場合 ? = ?1 ? ? ? , ? = ?1 ? ?3 ＃xとyの距離の二乗：各要素の二乗和 for ii in range(len(x)): d2 += (x[ii]-y[ii])**2 ＃平方根 d = math.sqrt(d2) # 表示 print d 何次元になっても、同じプログラムで表記できる。 ?関数にしておくと、繰り返し簡単に使える。
- 15. ユークリッド距離:プログラミング (１３) 15 import numpy ＃ｘとｙの定義 x = numpy.array([60,180]) Y = numpy.array([60,150]) ＃xとyの距離の計算 d = numpy.linalg.norm(x-y) 実は、pythonに関数が用意されている。 Webで調べて既にあるものを利用するのも プログラミングの大事なスキル！
- 16. これで画像間の距離(似てる具合)も測れます 16 65536次元ベクトル ? 65536次元ベクトル ? 画像間距離 ? ? ? 256 × 256 256 × 256 numpy.linalg.norm(x-y) 38574.86
- 19. マンハッタン距離:プログラミング (7) 19 ●N次元の場合 ? = ?1 ? ? ? , ? = ?1 ? ?3 for ii in range(len(x)): d2 += numpy.abs(x[ii]-y[ii]) # 表示 print d ?と ?の距離= ?1 ? ?1 + ? + ? ? ? ? ? 各要素の差の絶対値の和 絶対値
- 20. マンハッタン距離:プログラミング (7) 20 import numpy ＃ｘとｙの定義 x = numpy.array([60,180]) Y = numpy.array([60,150]) ＃xとyの距離の計算 d = numpy.linalg.norm(x-y, 1) こちらも、pythonに関数が用意されている。
- 21. 練習1: 距離 ●ユークリッド距離（任意の次元）を計算する関数を自身で定義して、 下記のベクトル間のユークリッド距離を求めよ ●例１）A=[10,8], B=[5,3] ●例２）A=[10,8,3], B=[5,3,7] ●numpyのデフォルトの関数を実行して結果が同じか比較せよ ●マンハッタン距離（任意の次元）を計算する関数を自身で定義して、 上記のベクトル間のマンハッタン距離を求めよ 21
- 23. 分布の可視化 ●csvファイル” height_weight.csv”を読み込み、「横 軸：身長、縦軸：体重」としてプロットして、分布の形状を 確かめよう。点Aを別の色で表示しよう。 plt.scatter(vlist[:,0], vlist[:,1],c='blue',marker='o',s=30) plt.scatter(A[0], A[1],c=‘red’,marker=‘+’,s=100) 色 マーカー の形 マーカー のサイズ
- 24. 距離の可視化（１） ●A=(180,75)からの各点へのユークリッド距離をそれぞれ 算出し、最も距離が近い順に並び替えて、距離に応じて色 を変えて表示 # compute distances A = np.array([180,75]) dlist = [] for row in vlist: d = np.linalg.norm(A-row) dlist.append(d) # 距離が短い順に並び替え sinds = np.argsort(dlist)[::-1]
- 25. 距離の可視化（２） ●距離に応じて色を変えて表示 # visualize import matplotlib.cm as cm count = 0 # 距離の近い順にプロット for i in sinds: row = vlist[i] # 並び順に応じて色を決定 c = cm.hot(count/len(vlist)) # 決定した色を指定してプロット plt.scatter(row[0],row[1],color=c) count += 1 # 点Aの可視化 plt.scatter(A[0], A[1], c=‘green’, marker=‘+’, s=60)
- 28. ユークリッド距離で測る類似度 28 65536次元 ベクトル ? 65536次元 ベクトル ? 256 × 256 256 × 256 16957.99 人の目には ? より ? の方が ? に類似しているが、 ユークリッド距離だと、 ? の方が ? からの距離が近い 256 × 256 65536次元 ベクトル ? 画像間距離 ? ? ? 画像間距離 ? ? ? 12249.03 <
- 30. 思い出そう：内積 ●なんかcos ? も出てきたような... → その通り．これ↓をつかって内積計算もできます． ●もっと大事なのは： ●－１ ≤ cos ? ≤ １ ● ?が0度（同じ向きのベクトル）： 30 ? ? ? = ? ? cos ? ? ? 長さ= ?長さ= ? ?cos ? = ? ? ? ? ?
- 31. 思い出そう：内積 ●一定の大きさのベクトル?を回転させながら?と内積を取る と... 31 ? ? ? ? ? = ? ? ? ? →最大 ? ? ? →最小 ?と?が 同一方向なら大きい 逆方向なら小さい ?と?の 類似度に 使えそう!
- 32. 正規化相関：プログラミング 32 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 # 表示
- 33. 正規化相関で測る類似度 33 65536次元 ベクトル ? 65536次元 ベクトル ? 256 × 256 256 × 256 1.0 256 × 256 65536次元 ベクトル ? 画像間距離 コサイン類似度 画像間 コサイン類似度 0.932 <
- 39. どういう分割がよいのか？ ● ?個のデータを?個に分割する方法はおよそ? ?通り ●100個のデータを10分割→およそ10100通り ●近くにあるデータが，なるべく同じ部分集合になるように 39
- 45. K-means：プログラミング ●ステップ0： ●データ入力 ●クラスタ数の決定 45 import csv ＃データの入力 f = open(‘data.csv’,’rb’) Reader = csv.reader(f) vlist = [] for row in Reader: vlist.append([float(row[0]), float(row[1])]) vlist = np.array(vlist) f.close() #k(クラスタ数)の決定 K = 4;
- 46. K-means：プログラミング ●ステップ1： ●初期代表点の決定（ランダム） 46 ＃random値の範囲決定 a = np.min(vlist[:,0]) b = np.max(vlist[:,0]) c = np.min(vlist[:,1]) d = np.max(vlist[:,1]) #ランダムに決定 Clist = np.c_[(b-a)*np.random.rand(K) + a, (d-c)*np.random.rand(K) + c] plt.scatter(vlist[:,0], vlist[:,1]) plt.scatter(Clist[:,0], Clist[:,1])
- 47. K-means：プログラミング ●ステップ１： ●代表点の支持者決定 ?最も近い代表点を支持する 距離を活用！ ●ある点Xに着目 ?各代表点までの距離を算出 47 A C B D X ＃XとAの距離の計算 Ad = numpy.linalg.norm(X-A)
- 48. K-means：プログラミング ●ステップ１： ●ある点Xに着目 ●距離が最も近い代表点を決定 48 A C B D X def nearest(X,Clist): minD = Inf; minId = 0; for ii in range(0,len(CList)): C = Clist(ii,:) d = numpy.linalg.norm(X-C) if d < minD minD = d; minId = ii; return minId
- 49. K-means：プログラミング ●ステップ１： ●全ての点で代表点を決定 49 A C B D X def selectCluster(vList,Clist): cIList = []; for row in vList: cIList.append(nearest(row,Clist)) Return cIList
- 50. K-means：プログラミング ●ステップ2：代表点を更新 ●各クラスタの支持者群の平均値を 代表点とする。 50 A C B D X def updateCenter(vlist,CIList): CList = [] for k in range(K): Z = [] for j in range(len(CIList)): if CIList[j] == k: Z.append(vlist[j]) mc = np.mean(Z,0) CList.append(mc) return CList
- 51. K-means：プログラミング 51 ?アルゴリズム ?ステップ0 ?繰り返し ?代表点の選択 ?代表点の更新 ?終了チェック def clustering(vList,K): Clist = random err = 0.1 while dd > err: preClist = Clist CIList = selectCluster(vList,Clist) Clist = updateCenter(CIList,vList,K) dd = average(preClist-Clist)
- 58. K-meansクラスタリング 58 ?アイリスデータ ?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.data
- 59. アイリスデータ解析 59 Sepal length Sepalwide ? Iris-setosa ? Iris-versicolor ? Iris-virginica
- 60. アイリスデータ解析 60 Sepal length Sepalwide ? Iris-setosa ? Iris-versicolor ? Iris-virginica Petal length petalwide Sepal length Petallength Sepal wide petalwide
- 61. 演习