#
source:
orange/docs/widgets/rst/unsupervized/mds.rst
@
11778:ecd4beec2099

Revision 11778:ecd4beec2099, 5.6 KB checked in by Ales Erjavec <ales.erjavec@…>, 5 months ago (diff) |
---|

Line | |
---|---|

1 | .. _MDS: |

2 | |

3 | MDS |

4 | === |

5 | |

6 | .. image:: ../../../../Orange/OrangeWidgets/Unsupervised/icons/MDS.svg |

7 | |

8 | Multidimensional scaling (MDS) - a projection into a plane fitted to the given |

9 | distances between the points |

10 | |

11 | Signals |

12 | ------- |

13 | |

14 | Inputs: |

15 | - Distance Matrix |

16 | A matrix of (desired) distances between points |

17 | - Example Subset (ExampleTable) |

18 | A subset of examples to be marked in the graph |

19 | |

20 | |

21 | Outputs: |

22 | - Selected Examples |

23 | A table of selected examples |

24 | |

25 | |

26 | Signals Example Subset and Selected Examples are only applicable if Distance |

27 | Matrix describes distances between examples, for instance if the matrix comes |

28 | from :ref:`Example Distance`. |

29 | |

30 | Description |

31 | ----------- |

32 | |

33 | Multidimensional scaling is a technique which finds a low-dimensional (in our |

34 | case a two-dimensional) projection of points, where it tries to fit the given |

35 | distances between points as well is possible. The perfect fit is typically |

36 | impossible to obtain since the data is higher dimensional or the distances are |

37 | not Euclidean. |

38 | |

39 | To do its work, the widget needs a matrix of distances. The distances can |

40 | correspond to any kinds of object. However, the widget has some functionality |

41 | dedicated to distances between examples, such as coloring the points and |

42 | changing their shapes, marking them, and outputting them upon selection. |

43 | |

44 | The algorithm iteratively moves the points around in a kind of simulation of a |

45 | physical model: if two points are too close to each other (or too far away), |

46 | there is a force pushing them apart (together). The change of the point's |

47 | position at each time interval corresponds to the sum of forces acting on it. |

48 | |

49 | .. image:: images/MDS.png |

50 | |

51 | The first group of buttons set the position of points. :obj:`Randomize` sets |

52 | the to a random position; the initial positions are also random. |

53 | :obj:`Jitter` randomly moves the points for a short distance; this may be |

54 | useful if the optimization is stuck in a (seemingly) local minimum. |

55 | :obj:`Torgerson` positions the points using Torgerson's method. |

56 | |

57 | Optimization is run by pushing :obj:`Optimize`. :obj:`Single Step` makes a |

58 | single step of optimization; this is primarily useful for educative purposes. |

59 | |

60 | Stress function defines how the difference between the desired and the actual |

61 | distance between points translates into the forces acting on them. Several are |

62 | available. Let current and desired be the distance in the current projection |

63 | and the desired distances, and diff=current-desired. Then the stress functions |

64 | are defined as follows: |

65 | |

66 | - :obj:`Kruskal stress`: diff\ :sup:`2` |

67 | - :obj:`Sammon stress`: diff\ :sup:`2`\ /current |

68 | - :obj:`Signed Sammon stress`: diff/current |

69 | - :obj:`Signed relative stress`: diff/desired |

70 | |

71 | |

72 | The widget redraws the projection during optimization. It can do so at |

73 | :obj:`Every step`, :obj:`Every 10 steps` or :obj:`Every 100 steps`. Setting a |

74 | lower refresh interval makes the animation more visually appealing, but can be |

75 | slow if the number of points is high. |

76 | |

77 | The optimization stops either when the projection changes only minimally at |

78 | the last iteration or when a specified number of steps have been made. The two |

79 | conditions are given with options :obj:`Minimal average stress change` and |

80 | :obj:`Maximal number of steps`. |

81 | |

82 | The bottom of the settings pane shows the average stress (the lower the better) |

83 | and the number of steps made in the last optimization. |

84 | |

85 | .. image:: images/MDS-Graph.png |

86 | :alt: MDS 'Graph' tab |

87 | :align: left |

88 | |

89 | The second tab with settings defines how the points are visualized and the |

90 | settings related to outputting the data. The user can set the size of points |

91 | (:obj:`Point Size`) or let the size depend on the value of some continuous |

92 | attribute (:obj:`Size`) of the example the point represents. The color and |

93 | shape of the point (:obj:`Color`, :obj:`Shape`) can depend upon values of |

94 | discrete attributes. Any attribute can serve as a label. |

95 | |

96 | These options are only active if the points represents examples (that is, if |

97 | there is a table of examples attached to the distance matrix on the widget's |

98 | input). If the points represent attributes (e.g. the distance matrix comes |

99 | from :ref:`Attribute Distance`, the points can be labeled by attribute names. |

100 | If the points come from a labeled distance file (see :ref:`Distance File`, the |

101 | labels can be used for annotating the points. |

102 | |

103 | The widget can superimpose a graph onto the projection, where the specified |

104 | proportion of the most similar pairs is connected, with the width of connection |

105 | showing the similarity. This is enabled by checking :obj:`Show similar pairs` |

106 | and setting the proportion of connected pairs below. Enabling this option |

107 | during the optimization can illustrate how the algorithm works, though drawing |

108 | too many connections at each refresh can make the optimization very slow. The |

109 | picture below shows a rendering of the zoo data set with this option enabled. |

110 | |

111 | .. image:: images/MSD-Connected.png |

112 | :alt: MDS Similar Pairs |

113 | |

114 | The remaining options deal with zooming selecting the points and sending them |

115 | on. The magnifying glass enables zooming, and the other two icons enable |

116 | selection of examples with rectangular or arbitrary selection areas. The |

117 | buttons in the left group undo the last action, remove all selection and send |

118 | the selected examples. Sending the examples can be automatic if |

119 | :obj:`Auto send selected` is checked. |

120 | |

121 | The output data can have the coordinates of each point appended, either as |

122 | normal attributes (:obj:`Append coordinates`) or as meta attributes |

123 | (:obj:`Append coordinates as meta`). |

124 | |

125 | The MDS graph performs many of the functions of the visualizations widget. It |

126 | is in many respects similar to the :ref:`Scatter Plot`, so we recommend |

127 | reading its description as well. |

128 | |

129 | Examples |

130 | -------- |

131 | |

132 | The above graphs were drawn using the following simple schema. |

133 | |

134 | .. image:: images/MDS-Schema.png |

135 | :alt: MDS Scheme |

**Note:**See TracBrowser for help on using the repository browser.