計量多次元尺度法
Metric Multidimensional Scaling
距離データ
に対して、それに対応する対象の布置を与える座標
を求める。座標と距離の関係は、Minkowski distance (Borg & Groenen, 1997)、Minkowski-metric (Kruskal, 1964)と呼ばれている次式で与える。
いま、データとして与えられた距離を
、座標値から算出された距離を
で表すとき、これらの差の２乗和
は座標値の関数である。データに対して関数（２）を最小にする座標値を極値探索法により求める。極値探索法として、NumpyのSimplex algorithm（Nelder-Mead法）を用いた。
極値探索法は初期値が必要であるが、多次元尺度法の場合、初期値の影響を強く受けやすい。本ウェブサイトでは、距離データに対して２重中心化（double centering: ）と固有分解（characteristic
decomposition）によって初期値を設定している（Borg & Groenen, 2005;
Carroll and Wish, 1974）。すなわち、距離行列を
、座標値行列を
で表すとき、ユークリッド距離（2-metric）の下で次式が成り立つ（岡本安晴「心理学データ分析と測定」勁草書房、pp. 197-200）。
式（３）で与えられる布置を初期値とする極値探索法によって、式（２）の値を極小にする座標値を求めるが、１回目の探索でよい極小値が得られるとは限らない。得られた解にランダムな変動を加えて再度極値探索を行うということを繰り返して適切と思われる解を選ぶ。
得られた解とデータとの差の大きさは、ストレス公式１（stress formula 1: Borg & Groenen, 2005）と呼ばれている次式で算出している。
プログラムは、r-metricのrを指定して実行するものと、rが無限大であるsup metric用のものの２つを別に用意した。これらのプログラムのソースコードファイルとサンプルデータファイルは、圧縮ファイルfiles.zipとして用意している。Minkowski r-metricにおいて、rが有限値の場合（City metric、Euclid distanceなど）とｒが無限の場合（sup metric）とに分けて説明する。
Minkowski
r-metric (1 <= r < infinity)
プログラムのソースコードは、ウェブサイトの後ろにリスト１として示した。
Minkowski r-metric（１）は、r=1のときはcity-block、Manhattan metricなどと呼ばれ、次式で表される。
図１で表される９個の点A～Iに対して、式（５）による距離を算出すると図２のようになる。
図１
図２は図１の布置の距離を配列の下三角形の領域のみに設定したもので、この表データをCSVファイルとして保存したものを入力データとして読み込む。CSV形式のファイルは、＜岡本安晴「いまさら聞けないPythonでデータ分析」丸善出版、pp. 33-35, 101-102＞で説明している。
図２
リスト１のプログラムMetricMDS.pyを実行すると、まず入力データファイル名の設定が求められる（図３）。
図３
図３では、図２のデータファイルData9City.csvが設定されている。次に、出力用テキストファイル名の設定が求められるので、適当なテキストファイル名を設定する。図３では、Results.txtが設定されている。出力ファイル名の設定に続いて、r-metricのrの設定が求められる。City block metricでの多次元尺度法であるので、図３では、１が設定されている。このrの設定後、読み込んだデータの表示が行われ、続いて、多次元尺度法で用いる次元数の設定が求められる。図４では、図１の布置に対応して２が設定されている。生データのときは、いくつかの次元数で尺度構成を行ってみて、適切な解を選ぶことになる。
図４
次元数が設定されると計算が始まり、求められた布置による距離を縦軸に、入力データ距離を横軸にとった散布図（Shepard diagram）が表示される（図５）。
図５
図５のフォームを閉じると、求められた解による点の布置が表示される（図６）。
図６
図６のフォームを閉じると、次に表示する布置の横軸の次元dim1と縦軸の次元dim2の設定が求められる。dim1に０以下の整数値を設定すると布置の表示終了となり、よりよい布置の可能性を探るために尺度構成を続けるかどうかを聞いてくる（図７）。
図７
図５のShepard diagramおよび図６に示されている布置が図１の布置と比べて満足のいくものではないので、よりよい布置が得られることを期待して尺度構成を続けることにする。尺度構成を続けるため、Cを入力する。
よりよい布置を求めるために尺度構成を繰り返して、１１回目（Solution 11）に得られた布置によるShepard diagramが図８である。
図８
このときの点の布置は図９のようになっている。座標軸の反転を除いてよく図１の布置に一致している。座標軸の反転は、式（５）のモデルによる距離が座標軸の反転に関して不変であることによる。
図９
Minkowski r-metricは、r=2のときはユークリッド距離と呼ばれ、次式で表される。
プログラムの使用法は、r=2と設定することを除いて、上のcity blockの場合と同様である。
図１の布置に対してユークリッド距離を算出すると図10のようになる。
図10
プログラムMetricMDS.pyを起動して、図10のCSV形式のファイルData9Euclid.csvを入力ファイルとして指定する（図11）。
図11
出力用テキストファイル名を適当に設定して、r-metricのrを２とする。次元数は２である。計算が終了すると、まず入力距離データを横軸、求められた布置から算出された距離を縦軸とする散布図（Shepard diagram）が表示される（図12）。
図12
図12のフォームを閉じると、次に対象の布置が表示される（図13）。
図13
ユークリッド距離は、布置の回転および反転に関して不変であるので、図１３の布置は図１の布置とよく対応していると言える。
Minkowski r-metricにおいて、
の場合は次式で与えられる。
距離（７）は、
-metric、sup metric (Kruskal, 1964)、dominance metric (Borg & Groenen, 1997)などと呼ばれている。式（７）の場合は、座標値の差が最大のもののみが距離に寄与するので、布置と距離の関係が弱い。このため、まずr=5の場合をsup metricの近似として用いて極値探索を行い、その後、sup metricによる極値探索を行っている（リスト２参照）。プログラムのソースコードはウェブサイトの後ろにリスト２として示した。極値探索がr=5のr-metricによるものとsup
metricによるものの２段構成になっていることを除けば、上のr-metricの場合（リスト１）と同じである。
図１の布置に対して、sup metricによる距離データを作成すると図14のようになる。
図14
プログラムMetricMDS_sup.pyを起動して、入力データファイルとして図14のファイルData9Sup.csvを設定して、出力用テキストファイル名を適当に設定する（図15）。
図15
次元数を設定すると（図15では２）、計算が始まり、極値探索が終了するとShepard diagramが表示される（図16）。
図16
図16のフォームを閉じると、次に布置が表示される（図17）。
図17
反転を除いて図１の布置によく対応しているようであるが、図16のShepard diagramがもっとよくなることを期待して尺度構成を繰り返す。
図18のShepard diagramを得る。
図18
このときの布置は、図19のようである。
図19
十分によい布置が得られたと思われる。
参考文献
Borg, L. & Groenen, P. (1997). Modern multidimensional scaling: Theory and applications. Springer.
Borg, I. & Groenen, P.J.F. (2005). Modern multidimensional scaling: Theory and application, 2nd ed. Springer.
Carroll, J, D. & Wish, M. (1974). Models and methods for three-way multidimensional scaling. In D. H. Krantz, A. C. Atkinson, R. D. Luce, & P. Suppes (Eds.). Contemporary developments in mathematical psychology, Vol. II.: Measurement, psychophysics, and neural information processing (pp. 57-105). Freeman.
Kruskal, J. B. (1964). Nonmetric multidimensional scaling: A numerical method. Psychometrika, 29, 115-129.
リスト１ Minkowski r-metric (1 <= r < infinity) 用プログラムMetricMDS.py（ソースコードファイルとサンプルデータファイルの圧縮ファイルfiles.zip）
import csv
import numpy as np
import scipy.optimize as so
import matplotlib.pyplot as plt
def coord2dist( x ):
"""
Calculation of distances from coordinates
"""
n_obj = len(x)
n_dim = len(x[0])
dist = np.zeros((n_obj,
n_obj))
for i in range(n_obj):
for
j in range(i):
if j == i:
dist[i][i] = 0.0
else:
v = 0.0
for t in range(n_dim):
v += (np.abs(x[i][t] - x[j][t])) ** r
dist[i][j] = v ** (1.0 / r)
dist[j][i] = dist[i][j]
return dist
class linear_func:
"""
A class for a function, which calculates
sum of errors for coordinates in flattened shape.
"""
def __init__(self, n_obj,
n_dim, dist):
self.n_obj = n_obj
self.n_dim = n_dim
self.dist = dist
def f(self, z):
x =
z.reshape((self.n_obj, self.n_dim))
t_dist = coord2dist( x )
err
= np.sum((self.dist - t_dist)**2)
return err
###########################################################
fin_name = input('Input data
file(*.csv) = ')
fout_name = input('Output file
name(*.txt) = ')
r = float(input('For r-metric, r =
'))
# r for Minkowski
r-metric
fout = open(fout_name, 'w')
fout.write('Input date
file...{}\n'.format(fin_name))
fout.write('\nFor r-metric, r =
{}\n'.format(r))
with open(fin_name, 'r') as fin:
raw_data = [v for v in
csv.reader(fin)]
obj_labels = raw_data[0][1:]
n_obj = len(raw_data) - 1
print('n_obj = ', n_obj)
dist = np.zeros((n_obj, n_obj))
for i in range(n_obj):
for j in range(i + 1):
if j
== i:
dist[i][i] = 0.0
else:
dist[i][j] = float(raw_data[i + 1][j + 1])
dist[j][i] = dist[i][j]
print('dist...\n', dist)
fout.write('\nDistance Data...\n')
for i in range(n_obj):
fout.write('{0:
<5s}'.format(obj_labels[i]))
for j in range(i):
fout.write(' {0: >7.2f}'.format(dist[i][j]))
fout.write('\n')
n_dim = int(input('Number of
dimensions = ')) # Number of dimensions
dist_max = dist.max()
#
# Double
centering
#
NegD2 = (dist ** 2) * (-0.5)
J = np.zeros((n_obj, n_obj))
for i in range(n_obj):
J[i][i] = 1.0
J -= np.ones((n_obj, n_obj)) / n_obj
XXp = J @ NegD2 @ J
w, v = np.linalg.eigh(XXp) # Characteristic decomposition
idx = np.argsort(-w)
print('v[idx]...\n', w[idx])
#
# Initial
configuration
#
w = w[idx]
v = (v.T[idx]).T
X_init = np.zeros((n_obj, n_dim))
for t in range(n_dim):
if w[t] > 0.0:
for
i in range(n_obj):
X_init[i][t] = v[i][t]
* (w[t] ** 0.5)
func = linear_func(n_obj, n_dim, dist)
d_delta = np.empty((n_obj * (n_obj -
1)) // 2)
t_pos = 0
for i in range(1, n_obj):
for j in range(i):
d_delta[t_pos] = dist[i][j]
t_pos += 1
SltnID = 1
while True:
if SltnID <= 1:
x0 =
X_init.reshape(n_obj * n_dim)
else:
x0 =
x1.reshape(n_obj * n_dim) + np.random.normal(scale = dist_max * 0.1, size =
n_obj * n_dim)
res = so.minimize(func.f,
x0, method = 'Nelder-Mead',
options
= {'xatol': 1.0e-7, 'fatol': 1.0e-12})
x1 = res.x.reshape((n_obj,
n_dim))
means = x1.mean(axis = 0)
x1 = x1 - means
d_hat = np.empty((n_obj *
(n_obj - 1)) // 2)
t_pos = 0
for i in range(1, n_obj):
for j in range(i):
v = 0.0
for t in range(n_dim):
v += (np.abs(x1[i][t] - x1[j][t])) ** r
d_hat[t_pos] = v ** (1.0 / r)
t_pos += 1
v_num = np.sum((d_hat -
d_delta) ** 2)
v_den = np.sum(d_hat ** 2)
Stress_1 = (v_num / v_den)
** 0.5
print('\nSolution-{}'.format(SltnID))
print('\nStress-1 = ',
Stress_1)
print('\nX =')
fout.write('\nSolution-{}\n'.format(SltnID))
fout.write('\nStress-1 = {}\n'.format(Stress_1))
fout.write('\nX =\n')
for i in range(n_obj):
print('{0: <5s}'.format(obj_labels[i]), end = '')
fout.write('{0: <5s}'.format(obj_labels[i]))
for
t in range(n_dim):
print(' {0: >7.3f}'.format(x1[i][t]), end = '')
fout.write(' {0: >7.3f}'.format(x1[i][t]))
print()
fout.write('\n')
plt.plot(d_delta, d_hat,
'bo')
plt.xlabel('$d_{i,j}$
(data)', fontsize = 14)
plt.ylabel('$\hat{d}_{i,j}$
(est.)', fontsize = 14)
plt.title('Shepard diagram:
Solution-{}'.format(SltnID), fontsize = 16)
plt.tight_layout(h_pad = 5,
w_pad = 5)
plt.show()
dim1 = 0
dim2 = 1
if dim2 >= n_dim:
dim2
-= 1
while True:
plt.figure(figsize
= (7,7))
x_coord = x1.T[dim1]
y_coord = x1.T[dim2]
for
px, py, s in zip(x_coord, y_coord, obj_labels):
plt.text(px, py, s, fontsize = 14)
plt.plot(x_coord, y_coord, 'bo')
plt.xlabel('Dim-{}'.format(dim1+1), fontsize = 14)
plt.ylabel('Dim-{}'.format(dim2+1), fontsize = 14)
plt.title('Map: Solution-{}'.format(SltnID), fontsize = 16)
plt.tight_layout(h_pad = 5, w_pad = 5)
plt.show()
print('For dimension, put non-positive integer if you want to stop
drawing a map')
dim1
= int(input('dim1 = ')) - 1
if
dim1 < 0:
break
#
Quit this configuration
if
dim1 > n_dim - 1:
dim1 = n_dim - 1
dim2
= int(input('dim2 = ')) - 1
if
dim2 < 0:
dim2 = 0
elif
dim2 > n_dim - 1:
dim2 = n_dim - 1
ck = input('C(ontinue) or
Q(uit) ? ')
if ck[0] in {'Q', 'q'}:
break
# Quit this
program
SltnID += 1
fout.close()
print('\n{} was
saved.\n'.format(fout_name))
リスト２ Sup metric用プログラムファイルMetricMDS_sup.py（ソースコードファイルとサンプルデータファイルの圧縮ファイルfiles.zip）
import csv
import numpy as np
import scipy.optimize as so
import matplotlib.pyplot as plt
def coord2dist( x ):
"""
Calculate distances from coordinates
based on r-metric
"""
n_obj = len(x)
n_dim = len(x[0])
dist = np.zeros((n_obj,
n_obj))
for i in range(n_obj):
for
j in range(i):
if j == i:
dist[i][i] = 0.0
else:
v = 0.0
for t in range(n_dim):
v += (np.abs(x[i][t] - x[j][t])) ** r
dist[i][j]
= v ** (1.0 / r)
dist[j][i] = dist[i][j]
return dist
def coord2dist_sup( x ):
"""
Calculate distances from coordinate
based on sup-metric
"""
n_obj = len(x)
n_dim = len(x[0])
dist =
np.zeros((n_obj, n_obj))
for i in range(n_obj):
for
j in range(i):
if j == i:
dist[i][i] = 0.0
else:
v = 0.0
for t in range(n_dim):
if v < np.abs(x[i][t] - x[j][t]):
v = np.abs(x[i][t] - x[j][t])
dist[i][j] = v
dist[j][i] = dist[i][j]
return dist
class linear_func:
"""
A class of a function, which returns
amount of errors for the coordinates flattend.
Distances are calculated based on r-metric.
"""
def __init__(self, n_obj,
n_dim, dist):
self.n_obj = n_obj
self.n_dim = n_dim
self.dist = dist
def f(self, z):
x =
z.reshape((self.n_obj, self.n_dim))
t_dist = coord2dist( x )
err
= np.sum((self.dist - t_dist)**2)
return err
class linear_func_sup:
"""
A class of a function, which returns
ammount of errors for the coordinates flattend.
Distances are calculated based on sup-metric.
"""
def __init__(self, n_obj,
n_dim, dist):
self.n_obj = n_obj
self.n_dim = n_dim
self.dist = dist
def f(self, z):
x =
z.reshape((self.n_obj, self.n_dim))
t_dist = coord2dist_sup( x )
err
= np.sum((self.dist - t_dist)**2)
return err
#############################################################
fin_name = input('Input data
file(*.csv) = ')
fout_name = input('Output file
name(*.txt) = ')
r = 5
# for approximate
r-metric to sup-metric
fout = open(fout_name, 'w')
fout.write('Input date
file...{}\n'.format(fin_name))
with open(fin_name, 'r') as fin:
raw_data = [v for v in
csv.reader(fin)]
obj_labels = raw_data[0][1:]
n_obj = len(raw_data) - 1
print('n_obj = ', n_obj)
dist = np.zeros((n_obj, n_obj))
for i in range(n_obj):
for j in range(i + 1):
if j
== i:
dist[i][i] = 0.0
else:
dist[i][j]
= float(raw_data[i + 1][j + 1])
dist[j][i] = dist[i][j]
print('dist...\n', dist)
fout.write('\nDistance Data...\n')
for i in range(n_obj):
fout.write('{0:
<5s}'.format(obj_labels[i]))
for j in range(i):
fout.write('
{0: >7.2f}'.format(dist[i][j]))
fout.write('\n')
n_dim = int(input('Number of
dimensions = '))
dist_max = dist.max()
#
# Double
centering
#
NegD2 = (dist ** 2) * (-0.5)
J = np.zeros((n_obj, n_obj))
for i in range(n_obj):
J[i][i] = 1.0
J -= np.ones((n_obj, n_obj)) / n_obj
#
#
Characteristic decomposition
#
XXp = J @ NegD2 @ J
w, v = np.linalg.eigh(XXp)
idx = np.argsort(-w)
#
# Initial
configuration
#
w = w[idx]
v = (v.T[idx]).T
X_init = np.zeros((n_obj, n_dim))
for t in range(n_dim):
if w[t] > 0.0:
for
i in range(n_obj):
X_init[i][t] = v[i][t] * (w[t] ** 0.5)
func = linear_func(n_obj, n_dim, dist)
func_sup = linear_func_sup(n_obj,
n_dim, dist)
d_delta = np.empty((n_obj * (n_obj - 1))
// 2)
t_pos = 0
for i in range(1, n_obj):
for j in range(i):
d_delta[t_pos] = dist[i][j]
t_pos += 1
SltnID = 1
while True:
if SltnID <= 1:
x0 =
X_init.reshape(n_obj * n_dim)
else:
x0 =
x1.reshape(n_obj * n_dim) + np.random.normal(scale = dist_max * 0.1, size =
n_obj * n_dim)
#
#
Approximate configuration using r-metric with r = 5
#
print('\nMinimization based
5-metric started for Solution-{}'.format(SltnID))
res = so.minimize(func.f,
x0, method = 'Nelder-Mead',
options = {'xatol': 1.0e-7, 'fatol': 1.0e-12})
#
#
Optimization using sup-metric
#
print('\nMinimization based
sup-metric started for Solution-{}'.format(SltnID))
res = so.minimize(func_sup.f,
res.x, method = 'Nelder-Mead',
options = {'xatol': 1.0e-7, 'fatol': 1.0e-12})
x1 = res.x.reshape((n_obj,
n_dim))
means = x1.mean(axis = 0)
x1 = x1 - means
d_hat = np.empty((n_obj *
(n_obj - 1)) // 2)
t_pos = 0
for i in range(1, n_obj):
for
j in range(i):
v = 0.0
for t in range(n_dim):
if v < np.abs(x1[i][t] - x1[j][t]):
v = np.abs(x1[i][t] - x1[j][t])
d_hat[t_pos] = v
t_pos += 1
v_num = np.sum((d_hat -
d_delta) ** 2)
v_den = np.sum(d_hat ** 2)
Stress_1 = (v_num / v_den)
** 0.5
print('\nSolution-{}'.format(SltnID))
print('\nStress-1 = ',
Stress_1)
print('\nX =')
fout.write('\nSolution-{}\n'.format(SltnID))
fout.write('\nStress-1 =
{}\n'.format(Stress_1))
fout.write('\nX =\n')
for i in range(n_obj):
print('{0: <5s}'.format(obj_labels[i]), end = '')
fout.write('{0: <5s}'.format(obj_labels[i]))
for
t in range(n_dim):
print(' {0: >7.3f}'.format(x1[i][t]), end = '')
fout.write(' {0: >7.3f}'.format(x1[i][t]))
print()
fout.write('\n')
#
# Shepard
diagram
#
plt.plot(d_delta, d_hat,
'bo')
plt.xlabel('$d_{i,j}$
(data)', fontsize = 14)
plt.ylabel('$\hat{d}_{i,j}$
(est.)', fontsize = 14)
plt.title('Shepard diagram:
Solution-{}'.format(SltnID), fontsize = 16)
plt.tight_layout(h_pad = 5,
w_pad = 5)
plt.show()
#
#
Configuration of the object
#
dim1 = 0
# Abscissa
dim2 = 1
# Ordinate
if dim2 >= n_dim:
dim2
-= 1
while True:
plt.figure(figsize = (7,7))
x_coord = x1.T[dim1]
y_coord = x1.T[dim2]
for
px, py, s in zip(x_coord, y_coord, obj_labels):
plt.text(px, py, s, fontsize = 14)
plt.plot(x_coord, y_coord, 'bo')
plt.xlabel('Dim-{}'.format(dim1+1), fontsize = 14)
plt.ylabel('Dim-{}'.format(dim2+1),
fontsize = 14)
plt.title('Map: Solution-{}'.format(SltnID), fontsize = 16)
plt.tight_layout(h_pad = 5, w_pad = 5)
plt.show()
print('For dimension, put non-positive integer if you want to stop
drawing a map')
dim1
= int(input('dim1 = ')) - 1 # If dim1 - 1 < 0, quit this
configuration
if
dim1 < 0:
break
if
dim1 > n_dim - 1:
dim1 = n_dim - 1
dim2
= int(input('dim2 = ')) - 1
if
dim2 < 0:
dim2 = 0
elif
dim2 > n_dim - 1:
dim2 = n_dim - 1
ck = input('C(ontinue) or
Q(uit) ? ')
# Press key 'Q', then
quit this program.
if ck[0] in {'Q', 'q'}:
break
SltnID += 1
fout.close()
print('\n{} was
saved.\n'.format(fout_name))