多次元尺度法

多次元尺度法（MDS ）は、データセットの個々のケースの類似性のレベルを視覚化する手段です。MDSは、セット内の各オブジェクトのペア間の距離を、抽象的な直交空間にマッピングされた点の構成に変換するために使用されます。^[1]${\textstyle n}$${\textstyle n}$

より技術的には、MDS は、情報視覚化、特に距離行列に含まれる情報を表示するために使用される一連の関連する順序付け手法を指します。これは、非線形次元削減の一形式です。

セット内の各オブジェクトペア間の距離を含む距離行列と、選択された次元数N が与えられると、MDSアルゴリズムは各オブジェクトをN次元空間（低次元表現）に配置し、オブジェクト間の距離が可能な限り維持されるようにします。N = 1、2、3の場合、結果の点は散布図で視覚化できます。^[2]

MDSへの中核的な理論的貢献は、機能データ解析の創始者ともみなされているマギル大学のジェームズ・O・ラムゼイによってなされました。^[3]

MDS アルゴリズムは、入力行列の意味に応じて 分類されます。

これは主座標分析(PCoA)、Torgerson スケーリング、または Torgerson–Gower スケーリングとしても知られています。これは、アイテムのペア間の相違点を与える入力行列を受け取り、歪みと呼ばれる損失関数を最小化する座標行列を出力します。^[2]は で与えられます。ここ で、 はN次元空間のベクトルを表し、はとの間のスカラー積を表し、 は距離から計算される次のアルゴリズムのステップ 2 で定義される 行列の要素です。$${\displaystyle {\text{Strain}}_{D}(x_{1},x_{2},...,x_{n})={\Biggl (}{\frac {\sum _{i,j}{\bigl (}b_{ij}-x_{i}^{T}x_{j}{\bigr )}^{2}}{\sum _{i,j}b_{ij}^{2}}}{\Biggr )}^{1/2},}$$${\displaystyle x_{i}}$${\displaystyle x_{i}^{T}x_{j}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle b_{ij}}$${\displaystyle B}$

古典的な MDS アルゴリズムの手順:

古典的なMDSは、座標行列が固有値分解によってから導出できるという事実を利用しています。また、行列は近接行列から二重中心化を使用して計算できます。 ^[4]${\displaystyle X}$${\textstyle B=XX'}$${\textstyle B}$${\textstyle D}$

1. 二乗近接行列を設定する${\textstyle D^{(2)}=[d_{ij}^{2}]}$
2. 二重センタリングを適用します。センタリング行列を使用します。ここで、はオブジェクトの数、は単位行列、 はすべて 1 の行列です。${\textstyle B=-{\frac {1}{2}}CD^{(2)}C}$ ${\textstyle C=I-{\frac {1}{n}}J_{n}}$${\textstyle n}$${\textstyle I}$${\textstyle n\times n}$${\textstyle J_{n}}$${\textstyle n\times n}$
3. （出力に必要な次元数）の最大固有値と対応する固有ベクトルを決定します。${\textstyle m}$ ${\textstyle \lambda _{1},\lambda _{2},...,\lambda _{m}}$ ${\textstyle e_{1},e_{2},...,e_{m}}$${\textstyle B}$${\textstyle m}$
4. ここで、 は固有ベクトルの行列であり、は の固有値の対角行列です。${\textstyle X=E_{m}\Lambda _{m}^{1/2}}$${\textstyle E_{m}}$${\textstyle m}$${\textstyle \Lambda _{m}}$${\textstyle m}$${\textstyle B}$

従来の MDS では、メトリック距離が想定されています。したがって、これは直接的な非類似度評価には適用できません。

これは、最適化手順をさまざまな損失関数と、重みなどを持つ既知の距離の入力行列に一般化する、古典的な MDS のスーパーセットです。このコンテキストで役立つ損失関数はストレスと呼ばれ、ストレス主要化と呼ばれる手順を使用して最小化されることがよくあります。メトリック MDS は、残差の二乗和である「ストレス」と呼ばれるコスト関数を最小化します。

${\displaystyle {\text{Stress}}_{D}(x_{1},x_{2},...,x_{n})={\sqrt {\sum _{i\neq j=1,...,n}{\bigl (}d_{ij}-\|x_{i}-x_{j}\|{\bigr )}^{2}}}.}$

メトリック スケーリングでは、距離に対してユーザー制御の指数:とを使用したべき乗変換が使用されます。従来のスケーリングでは、非メトリック スケーリングは、等位回帰を使用して非パラメトリックに相違点の変換を推定することによって定義されます。 ${\textstyle p}$${\textstyle d_{ij}^{p}}$${\textstyle -d_{ij}^{2p}}$${\textstyle p=1.}$

メトリック MDS とは対照的に、非メトリック MDS は、アイテム間マトリックスの相違点とアイテム間のユークリッド距離の間の 非パラメトリックな 単調関係と、低次元空間における各アイテムの位置の両方を検出します。

点間の相違度を とします。埋め込まれた点間のユークリッド距離を とします。 ${\displaystyle d_{ij}}$${\displaystyle i,j}$${\displaystyle {\hat {d}}_{ij}=\|x_{i}-x_{j}\|}$${\displaystyle x_{i},x_{j}}$

ここで、埋め込まれた点の各選択と単調増加関数に対して、「ストレス」関数を定義します。 ${\displaystyle x_{i}}$${\displaystyle f}$

${\displaystyle S(x_{1},...,x_{n};f)={\sqrt {\frac {\sum _{i<j}{\bigl (}f(d_{ij})-{\hat {d}}_{ij}{\bigr )}^{2}}{\sum _{i<j}{\hat {d}}_{ij}^{2}}}}.}$

分母のという因子は、「崩壊」を防ぐために必要です。 の代わりに を定義すると、 を設定してすべての点を同じ点に崩壊させる ことで簡単に最小化できます。${\displaystyle \sum _{i<j}{\hat {d}}_{ij}^{2}}$${\displaystyle S={\sqrt {\sum _{i<j}{\bigl (}f(d_{ij})-{\hat {d}}_{ij})^{2}}}}$${\displaystyle f=0}$

このコスト関数にはいくつかのバリエーションがあります。MDS プログラムは、MDS ソリューションを取得するために自動的にストレスを最小化します。

非メトリック MDS アルゴリズムの核となるのは、2 つの最適化プロセスです。まず、近接性の最適な単調変換を見つける必要があります。次に、構成のポイントを最適に配置して、その距離がスケーリングされた近接性と可能な限り一致するようにする必要があります。

NMDS は 2 つの目的を同時に最適化する必要があります。これは通常、反復的に実行されます。

1. たとえば正規分布からサンプリングするなどしてランダムに初期化します。${\displaystyle x_{i}}$
2. 停止基準に達するまで実行する（例：） ${\displaystyle S<\epsilon }$
   1. 等張回帰によってを解きます。${\displaystyle f=\arg \min _{f}S(x_{1},...,x_{n};f)}$
   2. 勾配降下法またはその他の方法で解きます。${\displaystyle x_{1},...,x_{n}=\arg \min _{x_{1},...,x_{n}}S(x_{1},...,x_{n};f)}$
3. 戻って${\displaystyle x_{i}}$${\displaystyle f}$

Louis Guttmanの最小空間分析 (SSA) は、非メトリック MDS 手順の例です。

メトリック多次元尺度法の拡張であり、対象空間は任意の滑らかな非ユークリッド空間です。相違点が表面上の距離であり、対象空間が別の表面である場合、GMDSは1つの表面から別の表面への最小歪みの埋め込みを見つけることができます。^[5]

分析対象となるデータは、距離関数が定義されたオブジェクト（色、顔、株など）の集合であり、 ${\displaystyle M}$

${\displaystyle d_{i,j}:=}$-番目と-番目のオブジェクト間の距離。${\displaystyle i}$${\displaystyle j}$

これらの距離は非類似度行列のエントリである

${\displaystyle D:={\begin{pmatrix}d_{1,1}&d_{1,2}&\cdots &d_{1,M}\\d_{2,1}&d_{2,2}&\cdots &d_{2,M}\\\vdots &\vdots &&\vdots \\d_{M,1}&d_{M,2}&\cdots &d_{M,M}\end{pmatrix}}.}$

MDSの目標は、 が与えられたとき に 、${\displaystyle D}$${\displaystyle M}$${\displaystyle x_{1},\ldots ,x_{M}\in \mathbb {R} ^{N}}$

${\displaystyle \|x_{i}-x_{j}\|\approx d_{i,j}}$すべて、${\displaystyle i,j\in {1,\dots ,M}}$

ここで、はベクトルノルムです。古典的なMDSでは、このノルムはユークリッド距離ですが、より広い意味では、メトリックまたは任意の距離関数である可能性があります。^[6] たとえば、数値記述子とカテゴリ記述子を含む混合型データを扱う場合、ガワーの距離が一般的な代替手段です。^[要出典]${\displaystyle \|\cdot \|}$

言い換えると、MDS は、距離が維持されるようにオブジェクトからへのマッピングを見つけようとします。次元を 2 または 3 に選択した場合、ベクトルをプロットして、オブジェクト間の類似性を視覚化できます。ベクトルは一意ではないことに注意してください。ユークリッド距離では、ベクトルを任意に変換、回転、反転できますが、これらの変換によってペアワイズ距離は変更されません。 ${\displaystyle M}$${\displaystyle \mathbb {R} ^{N}}$${\displaystyle N}$${\displaystyle x_{i}}$${\displaystyle M}$${\displaystyle x_{i}}$${\displaystyle \|x_{i}-x_{j}\|}$

(注: 記号は実数の集合 を示し、表記はのコピーの直積 を表します。これは実数体上の 次元ベクトル空間です。) ${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {R} ^{N}}$${\displaystyle N}$${\displaystyle \mathbb {R} }$${\displaystyle N}$

ベクトルを決定するにはさまざまなアプローチがあります。通常、MDSは最適化問題として定式化され、 は何らかのコスト関数の最小値として求められます。たとえば、 ${\displaystyle x_{i}}$${\displaystyle (x_{1},\ldots ,x_{M})}$

${\displaystyle {\underset {x_{1},\ldots ,x_{M}}{\mathrm {argmin} }}\sum _{i<j}(\|x_{i}-x_{j}\|-d_{i,j})^{2}.\,}$

数値最適化技術によって解が見つかるかもしれない。特に選択されたコスト関数については、最小化関数は行列の固有値分解によって解析的に表現できる。^[2]

MDS 研究を実施するには、いくつかのステップがあります。

1. 問題の定式化- どの変数を比較したいですか? 比較したい変数はいくつありますか? 研究の目的は何ですか?
2. 入力データの取得- たとえば、回答者は一連の質問を受けます。各製品ペアについて、類似性を評価するよう求められます (通常、非常に類似から非常に非類似までの 7 段階のリッカート尺度を使用)。最初の質問は、たとえば Coke/Pepsi に関するもので、次の質問は Coke/Hires ルートビール、その次は Pepsi/Dr Pepper、その次は Dr Pepper/Hires ルートビール、というように続きます。質問の数はブランド数の関数であり、次のように計算できます。Qは質問数、Nはブランド数です。このアプローチは、「知覚データ: 直接アプローチ」と呼ばれます。他の 2 つのアプローチがあります。1 つは「知覚データ: 派生アプローチ」で、これは製品を意味差分スケールで評価される属性に分解します。もう 1 つは「嗜好データ アプローチ」で、これは回答者に類似性ではなく嗜好を尋ねます。${\displaystyle Q=N(N-1)/2}$
3. MDS統計プログラムの実行– この手順を実行するためのソフトウェアは、多くの統計ソフトウェアパッケージで利用できます。多くの場合、メトリックMDS（間隔または比率レベルのデータを扱う）と非メトリックMDS ^[7]（順序データを扱う）のどちらかを選択できます。
4. 次元の数を決定する– 研究者は、コンピューターに作成させる次元の数を決定する必要があります。MDS ソリューションの解釈可能性は多くの場合重要であり、次元の低いソリューションの方が解釈や視覚化が容易になります。ただし、次元の選択は、アンダーフィットとオーバーフィットのバランスをとる問題でもあります。次元の低いソリューションは、非類似度データの重要な次元を除外することでアンダーフィットする可能性があります。次元の高いソリューションは、非類似度測定のノイズにオーバーフィットする可能性があります。したがって、 AIC、BIC、ベイズ係数、またはクロス検証などのモデル選択ツールは、アンダーフィットとオーバーフィットのバランスをとる次元を選択するのに役立ちます。
5. 結果のマッピングと次元の定義– 統計プログラム (または関連モジュール) が結果をマッピングします。マップは各製品をプロットします (通常は 2 次元空間)。製品同士の近接性は、使用されたアプローチに応じて、製品がどれだけ類似しているか、またはどれだけ好まれているかを示します。ただし、埋め込みの次元がシステム動作の次元と実際にどのように対応しているかは、必ずしも明らかではありません。ここでは、対応についての主観的な判断を行うことができます (知覚マッピングを参照)。
6. 結果の信頼性と妥当性をテストします。R二乗を計算して、MDS 手順で説明できるスケーリングされたデータの分散の割合を決定します。R 二乗が 0.6 であれば、最小許容レベルと見なされます。^{[引用が必要]} R 二乗が 0.8 であれば、メトリック スケーリングには適していると見なされ、.9 であれば、非メトリック スケーリングには適していると見なされます。その他の可能なテストには、Kruskal のストレス、分割データ テスト、データ安定性テスト (つまり、1 つのブランドを除外する)、およびテスト - 再テスト信頼性があります。
7. 結果を包括的に報告する– マッピングとともに、少なくとも距離の尺度 (例: Sorenson 指数、Jaccard 指数) と信頼性 (例: ストレス値) を示す必要があります。また、開始構成を指定した場合やランダムに選択した場合は、使用したプログラムによって定義されることが多いアルゴリズム (例: Kruskal、Mather)、実行回数、次元の評価、モンテカルロ法の結果、反復回数、安定性の評価、および各軸の比例分散 (r 平方) を示すことも非常に推奨されます (アルゴリズム レポートの代わりになる場合もあります)。

• ELKI には 2 つの MDS 実装が含まれています。
• MATLAB には2 つの MDS 実装 (それぞれ、古典的 ( cmdscale ) および非古典的 ( mdscale ) MDS) が含まれています。
• Rプログラミング言語は、基本cmdscale関数、パッケージsmacof ^[8] (mMDSおよびnMDS)、vegan (重み付きMDS)など、いくつかのMDS実装を提供しています。
• scikit-learnには関数 sklearn.manifold.MDS が含まれています。

ウィキメディア・コモンズには、多次元尺度法に関連するメディアがあります。

• データクラスタリング
• t分布確率近傍埋め込み
• 因子分析
• 判別分析
• 次元削減
• 距離幾何学
• ケーリー・メンガー行列式
• サモンマッピング
• 相関関係の図像