Up

非計量多次元尺度法

Nonmetric Multidimensional Scaling

 

非類似度データに対して、それに対応する対象の布置を与える座標を求める。座標と距離の関係は、Minkowski distance (Borg & Groenen, 1997)Minkowski-metric (Kruskal, 1964)と呼ばれている次式で与える。

 

 

いま、非類似度データに対応するとして与えられた距離を、座標値から算出された距離をで表すとき、これらの差の2乗和

 

 

は座標値の関数である。距離に対して関数(2)を最小にする座標値を極値探索法により求める。極値探索法として、scipy.optimize.minimizePowell法を用いた。

極値探索法は初期値が必要であるが、多次元尺度法の場合、初期値の影響を強く受けやすい。本ウェブサイトでは、Torgerson (1958)の尺度法(Torgerson scaling)と呼ばれている方法を用いて初期値を設定した(Borg, Groenen & Mair, 2013, p. 81)。すなわち、距離データに対して2重中心化(double centering: )と固有分解(characteristic decomposition)によって初期値を設定した(Borg & Groenen, 2005; Carroll and Wish, 1974)。距離行列を、座標値行列をで表すとき、ユークリッド距離(2-metric)の下で導かれる次式で求められる(岡本安晴「心理学データ分析と測定」勁草書房pp. 197-200)。

 

 

式(3)で与えられる布置を初期値とする極値探索法によって、式(2)の値を極小にする座標値を求めるが、1回目の探索でよい極小値が得られるとは限らない。得られた解にランダムな変動を加えて再度極値探索を行うということを繰り返して適切と思われる解を選ぶ。

さらに、非計量多次元尺度法では、非類似度データに対して設定される距離は、推定された座標値から計算される距離に対応して更新される。本ウェブサイトのプログラムでは、この更新をKruskals up-and-down-block algorithm (Kruskal, 1964, pp. 127-128)と呼ばれている方法で行っている。このための関数をリストBAに示した。

 

得られた解とデータとの差の大きさは、ストレス公式1(stress formula 1: Borg & Groenen, 2005)と呼ばれている次式で算出している。

 

 

 

プログラムは、r-metricrを指定して実行するものと、rが無限大であるsup metric用のものの2つを用意した。これらのプログラムのソースコードファイルとサンプルデータファイルは、圧縮ファイルfilesNM.zipとして用意した。Minkowski r-metricにおいて、rが有限値の場合City metricEuclid distanceなど)とrが無限の場sup metric)とに分けて説明する。

 

 

Minkowski r-metric (1 <= r < infinity)

プログラムのソースコードは、使用モジュールをリストR1に、本体はリストR2に示した。

リストR1のスクリプトには、1次元のベクトルの関数から、多次元の配列を構成して、式(2)の誤差を求める関数がクラス型linear_func内に定義されている。

 

    def f(self, z):

        x = z.reshape((self.n_obj, self.n_dim))

        t_dist = coord2dist( x, self.r )

        err = np.sum((self.dist - t_dist)**2)

        return err

 

これにより、ベクトルzを多次元配列xに変換して極値探索法を用いている。

 

Minkowski r-metric(1)は、r=1のときはcity-blockManhattan metricなどと呼ばれ、次式で表される。

 

 

図1.1で表される9個の点AIに対して、式(5)による距離を算出して、さらに単調変換を行い図1.2のデータを作成した。

図1.

 

1.2のデータは、図1.1の布置から作成された非類似度データを配列の下三角形の領域のみに設定したもので、この表データをCSVファイルとして保存したものを入力データとして読み込む。CSV形式のファイルは、<岡本安晴「いまさら聞けないPythonでデータ分析」丸善出版pp. 33-35, 101-102>で説明している。

1.

 

リストR2のプログラムNonMetricMDS_r_metric.pyを実行すると、まず入力データファイル名の設定が求められる(図1.3)。

1.

 

1.3では、図1.2のデータファイルDataCity.csvが設定されている。次に、出力用テキストファイル名の設定が求められるので、適当なテキストファイル名を設定する。図1.3では、Results.txtが設定されている。出力ファイル名の設定に続いて、r-metricrの設定が求められる。City block metricでの多次元尺度法であるので、図1.3では、1が設定されている。このrの設定後、読み込んだデータの表示が行われ、続いて、多次元尺度法で用いる次元数の設定が求められる。図1.4では、図1.1の布置に対応して2が設定されている。生データのときは、いくつかの次元数で尺度構成を行ってみて、適切な解を選ぶことになる。

1.4

 

次元数が設定されると計算が始まり、求められた布置による距離を縦軸に、入力データ値(で表されている)を横軸にとった散布図(Shepard diagram)が表示される(図1.5)。

1.5

 

保存ボタンをクリックすると、表示グラフを保存することができる。閉じるボタンをクリックすると、Windowは閉じられる。

1.5のフォームを閉じると、求められた解による点の布置が表示される(図1.6)。

1.6

 

1.6のフォームを閉じると、次に表示する布置の横軸の次元dim1と縦軸の次元dim2の設定が求められる。dim1に0以下の整数値を設定すると布置の表示終了となり、よりよい布置の可能性を探るために尺度構成を続けるかどうかを聞いてくる(図1.7)。

1.7

 

1.5Shepard diagramおよび図1.6に示されている布置が図1.1の布置と比べてより満足のいくものが得られることを期待して尺度構成を続けることにする。極値探索法の場合、探索の出発点(初期値)を変えると、異なる点(極小点)に収束する可能性がある。尺度構成を続けるため、Cを入力する。

よりよい布置を求めるために尺度構成を繰り返して、2回目(Solution 2)に得られた布置によるShepard diagramが図1.8である。

1.8

 

このときの点の布置は図1.9のようになっている。座標軸の反転を除いてよく図1.1の布置に一致している。座標軸の反転は、式(5)のモデルによる距離が座標軸の反転に関して不変であることによる。

1.9

 

 

プログラムを終了するときは、図1.7の状態においてQを入力すればよい。

 

 

 

Minkowski r-metricは、r=2のときはユークリッド距離と呼ばれ、次式で表される。

 

 

プログラムの使用法は、r=2と設定することを除いて、上のcity block metricの場合と同様である。

1.1の布置に対してユークリッド距離を算出して単調変換を行い、図1.10のデータを得た。

1.10

 

プログラムNonMetricMDS_r_metric.pyを起動して、図1.10CSV形式のファイルDataEuclid.csvを入力ファイルとして指定する(図1.11)。

1.11

 

出力用テキストファイル名を適当に設定して、r-metricrを2とする。次元数は2を設定した。計算が終了すると、まず入力データ(で表されている)を横軸、求められた布置から算出された距離を縦軸とする散布図(Shepard diagram)が表示される(図1.12)。

 

1.12

 

1.12のフォームを閉じると、次に対象の布置が表示される(図1.13)。

 

1.13

 

ユークリッド距離は、布置の回転および反転に関して不変であるので、図1.13の布置は図1.1の布置とよく対応していると言える。

 

 

 

Sup metric

Minkowski r-metricにおいて、の場合は次式で与えられる。

 

 

距離(7)は、-metricsup metric (Kruskal, 1964)dominance metric (Borg & Groenen, 1997)などと呼ばれている。式(7)の場合は、座標値の差が最大のもののみが距離に寄与するので、布置と距離の関係が弱い。このため、まずr=5の場合をsup metricの近似として用いて極値探索を行い、その後、sup metricによる極値探索を行っている(リス参照)。プログラムのソースコードはウェブサイトの後ろにリスト2として示した。極値探索がr=5r-metricによるものとsup metricによるものの2段構成になっていることを除けば、上のr-metricの場合(リスト1)と同じである。

1.1の布置に対して、sup metricによる距離データを作成して単調変換を行い図2.1のデータを得た。

2.1

 

プログラムNonMetricMDS_sup_metric.pyを起動して、入力データファイルとして図2.1のファイルDataSup.csvを設定し、出力用テキストファイル名を適当に設定する(図2.2)。

2.2

 

次元数を設定すると(図2.2では2)、計算が始まり、極値探索が終了するとShepard diagramが表示される(図2.3)。

 

2.3

 

2.3のフォームを閉じると、次に布置が表示される(図2.4)。

 

2.4

 

反転を除いて図1.1の布置によく対応しているようであるが、よりよい解の得られることを期待して尺度構成を繰り返す。

2.5Shepard diagramを得る。

 

2.5

 

このときの布置は、図2.6のようである。

 

2.6

 

尺度構成の繰り返しはここまでとするときは、図1.7の画面でQを入力すればよい。

 

 

参考文献

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.

Borg, I., Groenen, P. J. F. & Mair, P. (2013). Applied multidimensional scaling. New York: 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.

岡本安晴(2014).心理学データ分析と測定.勁草書房

 

 

 

 

以下のファイルは圧縮ファイルfilesNM.zipにまとめられている。

 

 

リストBA Up-and-down-blocks algorithmのスクリプト例(BlockAverage_v1.py)

 

import copy

def nm_transf(dist):

    """

            The up-and-down-blocks algorithm

        I. Borg & P. J. F. Groenen(2005). Modern multidimensional scaling, 2nd ed., (p. 206).

        J. B. Kruskal (1964). Nonmetric multidimensional scaling.

                                  Psychometrika, 115-129 (pp. 126-128).

                                            

    """   

    a_dist = copy.copy(dist)

    n = len(a_dist)

    #

    #    Check a_dist[0],...,a_dist[n-1] for monotonicity

    #

    Lpos = 0    #   Start from a_dist[0]

    Rpos = 0

    transf_done = False

    while transf_done == False:

        #

        #    Check a_dist[Lpos],...,a_dist[Rpos] for monotonicity

        #

        Lok = False

        Rok = False

        #

        #    Check the right value a_dist[Rpos]

        #    If necessary, adjust the values

        #

        if Rpos >= n - 1:

            Rok = True

        elif a_dist[Rpos] <= a_dist[Rpos+1]:

            Rok = True

        else:

            v = a_dist[Rpos] * (Rpos - Lpos + 1) + a_dist[Rpos+1]

            v /= Rpos - Lpos + 2

            Rpos += 1   

 

            for i in range(Lpos, Rpos+1):

                a_dist[i] = v

        #

        #     Check the left value a_dist[Lpos]

        #     If necessary, adjust the values

        #

        if Lpos <= 0:

            Lok = True

        elif a_dist[Lpos-1] <= a_dist[Lpos]:

            Lok = True

        else:

            v = a_dist[Lpos] * (Rpos - Lpos + 1) + a_dist[Lpos-1]

            v /= (Rpos - Lpos + 2)

            Lpos -= 1

            for i in range(Lpos, Rpos+1):

                a_dist[i] = v

 

        if Lok and Rok:   #  Monotonicity is satisfied. No adjustment is done

            Rpos += 1

            Lpos = Rpos

 

        if Rpos > n-1:

            transf_done = True

           

    return a_dist  

 

 

 

 

リストR1 リストR2で用いられるモジュール(mymodule.py

 

import numpy as np

 

def coord2dist( x, r ):

    """

        Calculate distances from coordinate x

        by 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 x

            by 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:

    """

            Calculate sum of squared differences between

            the target distances and derived r-metric

            distances from flattened coordinate z

    """

    def __init__(self, n_obj, n_dim, dist, r):

        self.n_obj = n_obj

        self.n_dim = n_dim

        self.dist = dist

        self.r = r

 

    def f(self, z):

        x = z.reshape((self.n_obj, self.n_dim))

        t_dist = coord2dist( x, self.r )

        err = np.sum((self.dist - t_dist)**2)

        return err

 

 

class linear_func_sup:

    """

            Calculate sum of squared differences between

            the target distances and derived sup-metric

            distances from flattened coordinate z

    """

    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

 

 

 

 

リストR2 r-metricによるMDSスクリプト例(NonMetricMDS_r_metric.py

 

import csv

import numpy as np

import scipy.optimize as so

import matplotlib.pyplot as plt

from mymodule import *

from BlockAverage_v1 import *   # as ba

 

fin_name = input('Input data file(*.csv) = ')

fout_name = input('Output file name(*.txt) = ')

fout = open(fout_name, 'w')

fout.write('Input date file...{}\n'.format(fin_name))

r = float(input('For r-metric, r = '))

fout.write('For 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 = '))

 

dist /= dist.max()

 

#

#       Double centering and characteristic decomposition

#       for initial configuration

#

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             #   Double centering

w, v = np.linalg.eigh(XXp)      #   Characteristic decomposition

idx = np.argsort(-w)

 

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)

 

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:

    iter = 0

    x1 = None

    Stress_1 = None

    dhat_t_1 = dist     #   Initial values

    dhat_t_0 = None

    while True:

        print('\niter = ', iter)

        func = linear_func(n_obj, n_dim, dhat_t_1, r)

        if iter <= 0:

            if SltnID <= 1:

                x0 = X_init.reshape(n_obj * n_dim)

            else:

                x0 = X_init.reshape(n_obj * n_dim) + \

                    np.random.normal(scale = 0.1, size = n_obj * n_dim)

        else:

           

            x0 = x1.reshape(n_obj * n_dim) + \

                    np.random.normal(scale = 0.1, size = n_obj * n_dim)

 

        iter += 1

 

        res = so.minimize(func.f, x0, method='Powell',

                          options={'maxiter':1000, 'disp':True})

        print('res =\n', res)

        x1 = res.x.reshape((n_obj, n_dim))

        means = x1.mean(axis = 0)

        x1 = x1 - means

        #

        #       Estimated distances by the optimized coordinates

        #

        d_hat = np.empty((n_obj * (n_obj - 1)) // 2)

        i_pos = np.empty((n_obj * (n_obj - 1)) // 2)

        j_pos = 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)

                i_pos[t_pos] = i

                j_pos[t_pos] = j

                t_pos += 1

        #

        #       Transformation by up-and-down blocks algorithm

        #

        d_pair = np.array([(u, v, ipos, jpos) for u, v, ipos, jpos in

                           zip(d_delta, d_hat, i_pos, j_pos)],

                          dtype = ([('delta', float), ('dhat', float),

                                    ('ipos', int), ('jpos', int)]))

        """

                          dtype = ([('delta', np.float), ('dhat', np.float),

                               ('ipos', np.int), ('jpos', np.int)]))

        """

        idx = np.argsort(d_pair, order = ['delta', 'dhat'])

        dhat = d_pair[idx]['dhat']

        i_pair = d_pair[idx]['ipos']

        j_pair = d_pair[idx]['jpos']

       

        transf_d = nm_transf(dhat)     #   Transformation

   

        dhat_t =  transf_d 

        delta = d_pair[idx]['delta']

 

        dhat_ave = np.zeros((n_obj, n_obj))

        for p in range((n_obj * (n_obj - 1)) // 2):

            dhat_ave[i_pair[p]][j_pair[p]] = transf_d[p] 

            dhat_ave[j_pair[p]][i_pair[p]] = transf_d[p] 

 

        dhat_ave /= dhat_ave.max()

 

        dhat_t_0 = dhat_t_1         #   The previous values

        dhat_t_1 = dhat_ave         #   The new estiamted distances

 

        diff_d = np.sum((dhat_t_0 - dhat_t_1) ** 2)

        diff_d /= (n_obj * (n_obj - 1)) /2

        print('\ndiff_d = {}\n'.format(diff_d))

 

        if (diff_d < 1.0e-3):

            print('\niter = {}\n'.format(iter))

            v_num = np.sum((dhat - dhat_t) ** 2)

            v_den = np.sum(dhat ** 2)

            Stress_1 = (v_num / v_den) ** 0.5

            break

             

    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.plot(delta, dhat_t, 'b')

    plt.xlabel(r'$\delta_{i,j}$', fontsize = 14)

    plt.ylabel(r'$\hat{d}_{i,j}$', fontsize = 14)

    plt.title('Shepard diagram: Solution-{}'.format(SltnID), fontsize = 16)

    plt.tight_layout(h_pad = 5, w_pad = 5)

    plt.show()

    #

    #        Configuration of objects  

    #

    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

        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

 

    SltnID += 1

   

fout.close()

print('\n{} was saved.\n'.format(fout_name))

 

 

 

リストS1 リストS2のスクリプトで用いられるモジュール(mymodule_sup.py

 

import numpy as np

 

def coord2dist( x, r ):

    """

        Calculate distances from coordinate x

        by 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 x

            by 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:

    """

            Calculate sum of squared differences between

            the target distances and derived r-metric

            distances from flattened coordinate z

    """

    def __init__(self, n_obj, n_dim, dist, r):

        self.n_obj = n_obj

        self.n_dim = n_dim

        self.dist = dist

        self.r = r

 

    def f(self, z):

        x = z.reshape((self.n_obj, self.n_dim))

        t_dist = coord2dist( x, self.r )

        err = np.sum((self.dist - t_dist)**2)

        return err

 

 

class linear_func_sup:

    """

            Calculate sum of squared differences between

            the target distances and derived sup-metric

            distances from flattened coordinate z

    """

    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

 

 

 

 

リストS2 Sup距離のMDSスクリプト(NonMetricMDS_sup_metric.py

 

import csv

import numpy as np

import scipy.optimize as so

import matplotlib.pyplot as plt

from mymodule_sup import *

from BlockAverage_v1 import *

 

fin_name = input('Input data file(*.csv) = ')

fout_name = input('Output file name(*.txt) = ')

fout = open(fout_name, 'w')

fout.write('Input date file...{}\n'.format(fin_name))

r = 5           #  r-metric is used to estimate an approximate configuration

 

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 /= dist.max()

 

#

#       Double centering and characteristic decomposition

#       for initial configuration

#

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             #   Double centering

w, v = np.linalg.eigh(XXp)      #   Characteristic decomposition

idx = np.argsort(-w)

 

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)

 

x0 = np.zeros(n_obj * n_dim)

 

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:

    iter = 0

    x1 = None

    Stress_1 = None

    dhat_t_1 = dist      #   Initial values

    dhat_t_0 = None

    while True:

        print('\niter = ', iter)

        func = linear_func(n_obj, n_dim, dhat_t_1, r)       #   Funciton with r-metric

        func_sup = linear_func_sup(n_obj, n_dim, dhat_t_1)  #   Function with sup-metric

        if iter <= 0:

            if SltnID <= 1:

                x0 = X_init.reshape(n_obj * n_dim)

            else:

                x0 = X_init.reshape(n_obj * n_dim) + \

                    np.random.normal(scale = 0.1, size = n_obj * n_dim)

        else:

            x0 = x1.reshape(n_obj * n_dim) + \

                    np.random.normal(scale = 0.1, size = n_obj * n_dim)

 

        iter += 1

 

        res = so.minimize(func.f, x0, method='Powell',

                          options={'maxiter':1000, 'disp':True})

        res = so.minimize(func_sup.f, res.x, method='Powell',

                          options={'maxiter':1000, 'disp':True,

                                   'xtol':1.0e-9, 'ftol':1.0e-14})

      

        x1 = res.x.reshape((n_obj, n_dim))

        means = x1.mean(axis = 0)

        x1 = x1 - means

        #

        #       Estimated distances by the optimized coordinates

        #

        d_hat = np.empty((n_obj * (n_obj - 1)) // 2)

        i_pos = np.empty((n_obj * (n_obj - 1)) // 2)

        j_pos = 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

             

                i_pos[t_pos] = i

                j_pos[t_pos] = j

                t_pos += 1

        #

        #       Transformation by up-and-down blocks algorithm

        #

        d_pair = np.array([(u, v, ipos, jpos) for u, v, ipos, jpos in

                           zip(d_delta, d_hat, i_pos, j_pos)],

                          dtype = ([('delta', float), ('dhat', float),

                                    ('ipos', int), ('jpos', int)]))

        idx = np.argsort(d_pair, order = ['delta', 'dhat'])

        dhat = d_pair[idx]['dhat']

        i_pair = d_pair[idx]['ipos']

        j_pair = d_pair[idx]['jpos']

 

        transf_d = nm_transf(dhat)

       

        dhat_t =  transf_d

       

        delta = d_pair[idx]['delta']

        dhat_ave = np.zeros((n_obj, n_obj))

        for p in range((n_obj * (n_obj - 1)) // 2):

            dhat_ave[i_pair[p]][j_pair[p]] = transf_d[p] 

            dhat_ave[j_pair[p]][i_pair[p]] = transf_d[p] 

     

        dhat_ave /= dhat_ave.max()

 

        dhat_t_0 = dhat_t_1

        dhat_t_1 = dhat_ave         #       The new estimated distances

 

        diff_d = np.sum((dhat_t_0 - dhat_t_1) ** 2)

        diff_d /= (n_obj * (n_obj - 1)) /2

 

        if (diff_d < 1.0e-3):

            print('\niter = {}\n'.format(iter))

            v_num = np.sum((dhat - dhat_t) ** 2)

            v_den = np.sum(dhat ** 2)

            Stress_1 = (v_num / v_den) ** 0.5

            break

             

    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.plot(delta, dhat_t, 'b')

    plt.xlabel(r'$\delta_{i,j}$', fontsize = 14)

    plt.ylabel(r'$\hat{d}_{i,j}$', fontsize = 14)

    plt.title('Shepard diagram: Solution-{}'.format(SltnID), fontsize = 16)

    plt.tight_layout(h_pad = 5, w_pad = 5)

    plt.show()

    #

    #           Configuration of objects

    #

    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

        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

 

    SltnID += 1

   

fout.close()

print('\n{} was saved.\n'.format(fout_name))

 

 

 

 

Home