Content deleted Content added
→See also: t-sne |
Citation bot (talk | contribs) Altered pages. Add: chapter-url, doi, authors 1-1. Removed or converted URL. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. Upgrade ISBN10 to 13. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:LinguisticMystic/cs/outline | #UCB_webform_linked 1368/2277 |
||
| (9 intermediate revisions by 6 users not shown) | |||
Line 1:
{{Short description|Set of related ordination techniques used in information visualization}}
[[File:RecentVotes.svg|thumb|400px|An example of classical multidimensional scaling applied to voting patterns in the [[United States House of Representatives]]. Each blue dot represents one
'''Multidimensional scaling''' ('''MDS''') is a means of visualizing the level of [[Similarity measure|similarity]] of individual cases of a data set. MDS is used to translate distances between each pair of <math display="inline"> n </math> objects in a set into a configuration of <math display="inline"> n </math> points mapped into an abstract [[Cartesian coordinate system|Cartesian space]].<ref name="MS_history">{{cite journal |last= Mead|first=A |date= 1992|title= Review of the Development of Multidimensional Scaling Methods |journal= Journal of the Royal Statistical Society. Series D (The Statistician)|volume= 41|issue=1 |pages=27–39 |quote= Abstract. Multidimensional scaling methods are now a common statistical tool in psychophysics and sensory analysis. The development of these methods is charted, from the original research of Torgerson (metric scaling), Shepard and Kruskal (non-metric scaling) through individual differences scaling and the maximum likelihood methods proposed by Ramsay. |jstor=2348634 }}</ref>▼
{{Data Visualization}}
▲'''Multidimensional scaling''' ('''MDS''') is a means of visualizing the level of [[Similarity measure|similarity]] of individual cases of a data set. MDS is used to translate distances between each pair of <math display="inline"> n </math> objects in a set into a configuration of <math display="inline"> n </math> points mapped into an abstract [[Cartesian coordinate system|Cartesian space]].<ref name="MS_history">{{cite journal |last= Mead|first=A |date= 1992|title= Review of the Development of Multidimensional Scaling Methods |journal= Journal of the Royal Statistical Society. Series D (The Statistician)|volume= 41|issue=1 |pages=27–39 |doi=10.2307/2348634 |quote= Abstract. Multidimensional scaling methods are now a common statistical tool in psychophysics and sensory analysis. The development of these methods is charted, from the original research of Torgerson (metric scaling), Shepard and Kruskal (non-metric scaling) through individual differences scaling and the maximum likelihood methods proposed by Ramsay. |jstor=2348634 }}</ref>
More technically, MDS refers to a set of related [[Ordination (statistics)|ordination]] techniques used in [[information visualization]], in particular to display the information contained in a [[distance matrix]]. It is a form of [[non-linear dimensionality reduction]].
Line 74 ⟶ 77:
{{main|Generalized multidimensional scaling}}
An extension of metric multidimensional scaling, in which the target space is an arbitrary smooth non-Euclidean space. In cases where the dissimilarities are distances on a surface and the target space is another surface, GMDS allows finding the minimum-distortion embedding of one surface into another.<ref name="bron">{{cite journal |vauthors=Bronstein AM, Bronstein MM, Kimmel R |title=Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching |journal=Proc. Natl. Acad. Sci. U.S.A. |volume=103 |issue=5 |pages=1168–72 |date=January 2006 |pmid=16432211 |pmc=1360551 |doi=10.1073/pnas.0508601103 |bibcode=2006PNAS..103.1168B |doi-access=free }}</ref>
=== Super multidimensional scaling (SMDS) ===
An extension of MDS, known as Super MDS, incorporates both distance and angle information for improved source localization. Unlike traditional MDS, which uses only distance measurements, Super MDS processes both distance and angle-of-arrival (AOA) data algebraically (without iteration) to achieve better accuracy.<ref>{{cite conference |last1=de Abreu |first1=G. T. F. |last2=Destino |first2=G. |title=Super MDS: Source Location from Distance and Angle Information |conference=2007 IEEE Wireless Communications and Networking Conference |___location=Hong Kong, China |pages=4430–4434 |year=2007 |doi=10.1109/WCNC.2007.807}}</ref>
The method proceeds in the following steps:
# '''Construct the Reduced Edge Gram Kernel:''' For a network of <math>N</math> sources in an <math>\eta</math>-dimensional space, define the edge vectors as <math>v_{i} = x_{m} - x_{n}</math>. The dissimilarity is given by <math>k_{i,j} = \langle v_i, v_j \rangle</math>. Assemble these into the full kernel <math>K = VV^T</math>, and then form the reduced kernel using the <math>N-1</math> independent vectors: <math>\bar{K} = [V]_{(N-1)\times\eta}\ [V]_{(N-1)\times\eta}^T</math>,
# '''Eigen-Decomposition:''' Compute the eigen-decomposition of <math>\bar{K}</math>,
# '''Estimate Edge Vectors:''' Recover the edge vectors as <math> \hat{V} = \Bigl( U_{M \times \eta}\, \Lambda^{\odot \frac{1}{2}}_{\eta \times \eta} \Bigr)^T </math>,
# '''Procrustes Alignment:''' Retrieve <math>\hat{V}</math> from <math>V</math> via Procrustes Transformation,
# '''Compute Coordinates:''' Solve the following linear equations to compute the coordinate estimates <math>\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},
</math>
This concise approach reduces the need for multiple anchors and enhances localization precision by leveraging angle constraints.
==Details==
Line 122 ⟶ 149:
* [[ELKI]] includes two MDS implementations.
* [[MATLAB]] includes two MDS implementations (for classical (''cmdscale'') and non-classical (''mdscale'') MDS respectively).
* The [[R (programming language)|R programming language]] offers several MDS implementations, e.g. base ''cmdscale'' function, packages [https://CRAN.R-project.org/package=smacof smacof]<ref>{{Cite journal|
* [[scikit-learn]] contains function [http://scikit-learn.org/stable/modules/generated/sklearn.manifold.MDS.html sklearn.manifold.MDS].
Line 142 ⟶ 169:
== Bibliography ==
{{refbegin}}
* {{cite book |last1=Cox |first1=T.F. |last2=Cox |first2=M.A.A. |editor1-last=Unwin |editor1-first=A |editor2-last=Chen |editor2-first=C |editor3-last=Hardle |editor3-first=W. K. |title=
* {{cite book |author=Coxon, Anthony P.M. |title=The User's Guide to Multidimensional Scaling. With special reference to the MDS(X) library of Computer Programs |publisher=Heinemann Educational Books |___location=London |year=1982 }}
* {{cite journal |author=Green, P. |title=Marketing applications of MDS: Assessment and outlook |journal=Journal of Marketing |volume=39 |pages=24–31 |date=January 1975 |doi=10.2307/1250799 |issue=1 |jstor=1250799 }}
| |||