多次元尺度法

アメリカ合衆国下院の投票パターンに古典的多次元尺度法を適用した例。青い点は民主党下院議員1名、赤い点は共和党下院議員1名を表しています。

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

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

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

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

種類

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

古典的な多次元尺度法

これは主座標分析（PCoA）、トルガーソン・スケーリング、またはトルガーソン・ガワー・スケーリングとも呼ばれます。これは、アイテムのペア間の非類似度を表す入力行列を受け取り、歪みと呼ばれる損失関数を最小化する座標行列を出力します。歪みは次の ように与えられます 。 ^{[ 2 ]}ここで、 はN次元空間のベクトル、はとの間のスカラー積、 は、以下のアルゴリズムのステップ2で定義される行列の要素であり、距離から計算されます。 $${\displaystyle {\text{ひずみ}}_{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は距離を計量的に想定しているため、直接的な非類似度評価には適用できません。

計量多次元尺度法（mMDS）

これは古典的な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.}$

非計量多次元尺度法（NMDS）

メトリック 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 手順の例です。

一般化多次元尺度法（GMD）

計量多次元尺度法の拡張であり、対象空間は任意の滑らかな非ユークリッド空間である。類似度が面上の距離であり、対象空間が別の面である場合、GMDSは、ある面から別の面への歪み最小の埋め込みを求めることを可能にする。^{[ 5 ]}

超多次元尺度法（SMDS）

MDSの拡張版であるスーパーMDSは、距離と角度の両方の情報を組み込むことで、音源位置推定精度を向上させます。距離測定のみを使用する従来のMDSとは異なり、スーパーMDSは距離と到来角（AOA）の両方のデータを代数的に（反復処理なしで）処理することで、より高い精度を実現します。^{[ 6 ]}

この方法は以下のステップで進行します。

1. 縮小エッジグラムカーネルを構築する：次元空間のソースネットワークにおいて、エッジベクトルを と定義する。非類似度は で与えられる。これらを完全カーネル にまとめ、独立ベクトル 、を用いて縮小カーネルを形成する。${\displaystyle N}$ ${\displaystyle \eta }$ ${\displaystyle v_{i}=x_{m}-x_{n}}$ ${\displaystyle k_{i,j}=\langle v_{i},v_{j}\rangle }$ ${\displaystyle K=VV^{T}}$ ${\displaystyle N-1}$ ${\displaystyle {\bar {K}}=[V]_{(N-1)\times \eta }\ [V]_{(N-1)\times \eta }^{T}}$
2. 固有分解:の固有分解を計算します。${\displaystyle {\bar {K}}}$
3. エッジベクトルの推定:エッジベクトルを次のように復元します。${\displaystyle {\hat {V}}={\Bigl (}U_{M\times \eta }\,\Lambda _{\eta \times \eta }^{\odot {\frac {1}{2}}}{\Bigr )}^{T}}$
4. プロクルステスのアライメント:プロクルステスの変換を介して 取得、${\displaystyle {\hat {V}}}$ ${\displaystyle V}$
5. 座標の計算:次の線形方程式を解いて座標の推定値を計算する。${\displaystyle {\begin{pmatrix}1\vline \mathbf {0} _{1\times N-1}\\\hline \mathbf {[C]} _{N-1\times N}\end{pmatrix}}\cdot {\begin{pmatrix}\mathbf {x} _{1}\\\hline [\mathbf {X} ]_{N-1\times \eta }\end{pmatrix}}={\begin{pmatrix}\mathbf {x} _{1}\\\hline [\mathbf {V} ]_{N-1\times \eta }\end{pmatrix}},}$

この簡潔なアプローチにより、複数のアンカーの必要性が減り、角度の制約を活用してローカリゼーションの精度が向上します。

詳細

分析対象となるデータは、距離関数が定義されたオブジェクト（色、顔、株価など）の集合であり、 ${\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では、このノルムはユークリッド距離ですが、より広い意味では、メトリックまたは任意の距離関数である可能性があります。^{[ 7 ]} 例えば、数値記述子とカテゴリ記述子を含む混合型データを扱う場合、ガワー距離が一般的な代替手段です。 ${\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 ^{[ 8 ]}（順序尺度データを扱う）のどちらかを選択できます。
4. 次元数の決定– 研究者は、コンピュータに作成させる次元数を決定する必要があります。MDS解の解釈可能性はしばしば重要であり、低次元の解は通常、解釈と視覚化が容易になります。しかし、次元の選択は、アンダーフィッティングとオーバーフィッティングのバランスをとる問題でもあります。低次元の解は、非類似度データの重要な次元を除外することで、アンダーフィッティングになる可能性があります。高次元の解は、非類似度測定におけるノイズにオーバーフィッティングする可能性があります。したがって、 AIC、BIC、ベイズ係数、クロスバリデーションなどのモデル選択ツールは、アンダーフィッティングとオーバーフィッティングのバランスをとる次元数を選択するのに役立ちます。
5. 結果のマッピングと次元の定義– 統計プログラム（または関連モジュール）は結果をマッピングします。マップは各製品を（通常は2次元空間で）プロットします。製品間の近接性は、使用されたアプローチに応じて、それらの製品の類似性または好まれ度を示します。ただし、埋め込みの次元がシステムの動作の次元と実際にどのように対応するかは必ずしも明らかではありません。ここでは、対応関係について主観的な判断を下すことができます（知覚マッピングを参照）。
6. 結果の信頼性と妥当性を検証する–決定係数（R2）を計算し、尺度化されたデータの分散のうち、MDS法で説明できる割合を決定します。決定係数が0.6であれば、許容可能な最小値とみなされます。決定係数が0.8であれば、計量尺度では良好とみなされ、0.9であれば、非計量尺度では良好とみなされます。その他の検定としては、クラスカルのストレス、分割データ検定、データ安定性検定（あるブランドを除外する検定など）、再検定信頼性などが挙げられます。
7. 結果を包括的に報告する– マッピングに加えて、少なくとも距離尺度（例：ソレンソン指数、ジャカード指数）と信頼性（例：ストレス値）を示す必要があります。また、使用したプログラムによって定義されることが多いアルゴリズム（例：クラスカル、マザー）も示すことが強く推奨されます（アルゴリズムレポートの代わりになる場合もあります）。開始設定を指定した場合やランダムに選択した場合は、実行回数、次元評価、モンテカルロ法の結果、反復回数、安定性評価、各軸の比例分散（r-square）も示してください。

実装

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

参照

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

参考文献

1. Mead, A (1992). 「多次元尺度法の発展に関するレビュー」. Journal of the Royal Statistical Society. Series D (The Statistician) . 41 (1): 27– 39. doi : 10.2307/2348634 . JSTOR  2348634.要旨.多次元尺度法は、心理物理学および官能分析において現在一般的な統計ツールとなっています。これらの手法の発展は、Torgerson（計量尺度法）、ShepardとKruskal（非計量尺度法）による最初の研究から、個体差尺度法、そしてRamsayが提唱した最尤法に至るまで、図表化されています。
2. Borg, I.; Groenen, P. (2005).現代多次元尺度法：理論と応用（第2版）. ニューヨーク: Springer-Verlag. pp.  207– 212. ISBN 978-0-387-94845-4。
3. Genest, Christian; Nešlehová, Johanna G.; Ramsay, James O. (2014). 「A Conversation with James O. Ramsay」 . International Statistical Review / Revue Internationale de Statistique . 82 (2): 161– 183. JSTOR 43299752. 2021年6月30日閲覧。 
4. ウィッケルマイヤー、フロリアン. 「MDS入門」サウンドクオリティ研究ユニット、オールボー大学、デンマーク(2003): 46
5. Bronstein AM, Bronstein MM, Kimmel R (2006年1月). 「一般化多次元尺度法：等長不変な部分表面マッチングのための枠組み」 . Proc. Natl. Acad. Sci. USA . 103 (5): 1168–72 . Bibcode : 2006PNAS..103.1168B . doi : 10.1073 /pnas.0508601103 . PMC 1360551. PMID 16432211 .  
6. de Abreu, GTF; Destino, G. (2007). Super MDS: 距離と角度情報による発信源位置特定. 2007 IEEE Wireless Communications and Networking Conference. 香港, 中国. pp.  4430– 4434. doi : 10.1109/WCNC.2007.807 .
7. Kruskal, JB , Wish, M. (1978), Multidimensional Scaling , Sage University Paper series on Quantitative Application in the Social Sciences, 07-011. Beverly Hills and London: Sage Publications.
8. Kruskal, JB (1964). 「非計量仮説への適合度の最適化による多次元尺度構成法」Psychometrika . 29 (1): 1– 27. doi : 10.1007/BF02289565 . S2CID 48165675 . 
9. Leeuw, Jan de; Mair, Patrick (2009). 「Majorizationを用いた多次元尺度法：RにおけるSMACOF」 . Journal of Statistical Software . 31 (3). doi : 10.18637/jss.v031.i03 . ISSN 1548-7660 . 

参考文献

• Cox, TF; Cox, MAA (2001). 「多次元尺度法」 . Unwin, A; Chen, C; Hardle, WK (編).データ可視化ハンドブック. Springer. doi : 10.1007/978-3-540-33037-0_14 . ISBN 978-3-540-33037-0。
• コクソン、アンソニー・P・M (1982). 『多次元尺度法ユーザーズガイド』MDS(X)ライブラリのコンピュータプログラムを中心に. ロンドン: ハイネマン・エデュケーショナル・ブックス.
• Green, P. (1975年1月). 「MDSのマーケティングへの応用：評価と展望」. Journal of Marketing . 39 (1): 24– 31. doi : 10.2307/1250799 . JSTOR  1250799 .
• McCune, B. & Grace, JB (2002). 『生態学的コミュニティの分析』 オレゴン州グレネデンビーチ: MjM Software Design. ISBN 978-0-9721290-0-8。
• ヤング、フォレスト・W.（1987年）『多次元尺度法：歴史、理論、そして応用』ローレンス・エルバウム・アソシエイツ、ISBN 978-0898596632。
• ウォーレン・S・トルガーソン（1958年）『スケーリングの理論と方法』ニューヨーク：ワイリー、ISBN 978-0-89874-722-5。