# Getting over High-Dimensionality: How Multidimensional Projection Methods Can Assist Data Science
## 4 Multidimensional Projection Approaches and Domains
### Force-Based Placement  
Force-based techniques are simple approaches applied to data projection that consider data instances connected by \"virtual springs\" and attempt to minimize the sum of the forces that act upon each data instance. Low dimensional positions are randomly initialized, and the repulsion forces between the springs adjust positions towards balancing [9]. The forces are calculated by \(\delta(x_{i},x_{j})-d(y_{i},y_{j})\), being \(\delta\) and \(d\) dissimilarity functions in original and projected space, respectively. Therefore, distant points in the original space repel each other in the projected space, and close points in the original space attract each other in the projected space. Sadly, the mapping accuracy is impaired by the computational complexity of \(O(n^{3})\) (\(n\) iterations of \(O(n^{2})\) force calculations), making its application in large datasets unfeasible. [PERSON] [61] handled this problem with a limited-size neighborhood of each data instance. After randomly initializing the projected space, considering an object \(x_{i}\), the process creates a \(V_{i}\) subset that contains \(k\)-near-neighbor of \(x_{i}\) and calculates \(\delta_{maxi}\) with the maximum dissimilarity between \(x_{i}\) and the members of \(V_{i}\). In an iterative process, a subset \(S_{i}\) is loaded until reaching \(k^{\prime}\) instances. Each iteration randomly selects a new \(x_{j}\) object that does not belong to \(V_{i}\). If \(\delta(x_{i},x_{j})<\delta_{maxi}\), then \(x_{j}\) is inserted into \(V_{i}\) (since the corresponding point is deleted from \(V_{i}\)) and \(\delta_{maxi}\) is updated; otherwise, \(x_{j}\) is inserted into \(S_{i}\). When \(S_{i}\) is fulled with \(k^{\prime}\) instances, Equation (18) returns the resultant force to be applied to \(y_{i}\) that is linearly proportional to \(\delta(x_{i},x_{j})-d(y_{i},y_{j})\). \[F_{i}=\sum_{v\in V_{i}}F_{in}+\sum_{s\in S_{i}}F_{is} \tag{18}\]  
Therefore, instead of calculating \(n(n-1)\) forces in each iteration, [PERSON] [61] seeks to preserve original distances in projected space, considering a reduced subset of instances. Despite the computational complexity improvement and preservation of small neighborhoods with linear iterations [6], \(O(n^{2})\) operations to balance the layout still hinder its application in real applications [9]. [PERSON] et al. [62] also tried to reduce the computational complexity with a hybrid version of the technique based on a sampling strategy. The process generates a random sample with \(\sqrt{(}n)\) instances and projects them with [PERSON] model. The \(n-\sqrt{(}n)\) remaining data instances are interpolated with a modified version of the Brodbeck and Girardin [63] strategy. These modifications reduced complexity to \(O(n\sqrt{n})\), but it can be inaccurate when applied to complex data structures or can get stuck in a local minimum [64]. Another approach was proposed by [PERSON] et al. [26] and named _Force Scheme_. This projection moves all points in a \(N_{i}\) neighborhood towards an \(y_{i}\) point instead of moving \(y_{i}\) towards its neighbors. In other words, each \(y_{i}\) attracts or repulses other \(y_{j}\) points during an iteration. Positions are updated with a force fraction considering the residual distance function between original and projected spaces, defined as  
\[\Delta=\frac{\delta(x_{i},x_{j})-\delta_{min}}{\delta_{max}-\delta_{min}}-d(y _{i},y_{j}), \tag{19}\]  
where \(\delta_{max}\) and \(\delta_{min}\) are the more significant and the smallest dissimilarities in the original space, respectively. The formulation respects original global dissimilarities, but this characteristic allows the large dissimilarities to dominate the projection process and distort small local neighborhoods. Consequently, in datasets that contain instances with high dissimilarities, the process tends to concentrate points in the out-most edges of the projection. Force Scheme can generate accurate layouts and reach stabilization with few iterations compared with other force projections.