<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/visualising-similarity-maps-vs-graphs/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://www.exactness.net/post/163519386590"> The Exactness of Mind</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<figure data-orig-width="450" data-orig-height="600"><img data-orig-width="450" src="https://i1.wp.com/68.media.tumblr.com/5ccf8103e42da145aa9cb7b65b1922d1/tumblr_inline_otsnjgcv281qa0hyw_540.png?resize=450%2C600" data-recalc-dims="1" data-orig-height="600"></figure>
<p>The visualization of complex data<br>
sets is of essential importance in communicating your data products.<br>
Beyond pie charts, histograms, line graphs and other common forms of<br>
visual communication begins the reign of data sets that encompass too<br>
much information to be easily captured by these simple data displays. A<br>
typical context that abounds with complexity is found in the areas of<br>
text mining, natural language processing, and cognitive computing in<br>
general; such a complex context for data<br>
presentation is pervasive in an attempt to build a visual interface for<br>
products like semantic search engines or recommendation engines. For<br>
example, statistical models like LDA (Latent Dirichlet Allocation)<br>
enable for a thorough insight into the similarity structure across<br>
textual documents or vocabulary terms used to describe them. But as the<br>
number of pairwise similarities between terms of documents to be<br>
presented to the end users increases, the problem of effective data<br>
visualization becomes harder. In this and the following blog posts, I<br>
wish to present and discuss some of the well-known approaches to<br>
visualize difficult data sets from the viewpoint of pure ergonomics, as<br>
well as to suggest some improvements and new ideas here and there.</p>
<p><b>A simple similarity map for iris</b></p>
<p>In this first blog on this topic, the idea is to<br>
focus on the basics of ergonomics in the visualization of similarity<br>
information. We will compare two ideas: the usage of similarity maps following a dimensionality reduction of the dataset – which can be taken as a sort of baseline idea in the visualization of similarity data – and the usage of directed graphs from higher-dimensional spaces directly, which is less common. I would like to put forward an argument in support of the later approach which I started using some time ago.</p>
<p>But first, let us have some data. I will use a well<br>
known, rather simple data set, merely for the purposes of the<br>
illustration here: namely, the famous iris:</p>
<blockquote><p># – the iris dataset</p>
<p>data(iris)<br>head(iris)</p>
</blockquote>
<blockquote><p> Sepal.Length Sepal.Width Petal.Length Petal.Width Species</p>
<p>1          5.1         3.5          1.4         0.2  setosa</p>
<p>2          4.9         3.0          1.4         0.2  setosa</p>
<p>3          4.7         3.2          1.3         0.2  setosa</p>
<p>4          4.6         3.1          1.5         0.2  setosa</p>
<p>5          5.0         3.6          1.4         0.2  setosa</p>
<p>6          5.4         3.9          1.7         0.4  setosa</p>
</blockquote>
<p>The iris dataset with its<br>
four numerical and one categorical variable is, as you will see,<br>
complicated quite enough to illustrate the main problem that I wish to<br>
discuss. Now, let’s illustrate the problem. The classical approach to<br>
assess the similarity between the different observations (rows) in this<br>
dataset would be to derive some metric from the numerical variables,<br>
perform dimensionality reduction, and then plot the data points in a<br>
lower-dimensional space. I will work with Euclidean distance and a<br>
non-linear dimensionality reduction approach by performing ordinal<br>
multidimensional scaling (MDS) with {smacof} in R:</p>
<blockquote><p># – distances in iris:<br>dIris &lt;-dist(iris[, 1:4], method = “euclidean”)</p>
</blockquote>
<p>Following the computation of Euclidean distances,<br>
each observation from the dataset can be treated as if it was<br>
represented by a set of features, each feature standing for a distance<br>
from the observation under discussion to all other observations in the<br>
dataset (including itself, where the distance is zero). The source data<br>
were four-dimensional (four continuous variables were used to represent<br>
each observation); now they are N-dimensional, with N representing the<br>
number of observations. But, being distances, the data now convey<br>
information about the similarities between the observations. Now, the<br>
dimensionality reduction step:</p>
<blockquote><p># – multidimensional scaling w. {smacof}<br>library(smacof)<br>mdsIris &lt;-smacofSym(dIris, type = “ordinal”)<br>mdsIris$stress<br>confIris &lt;-as.data.frame(mdsIris$conf)</p>
<p># – add category to confIris:<br>confIris$Species &lt;-iris$Species<br>head(confIris)</p>
<p>    D1      D2         Species</p>
<p>1 -0.8962210  0.09385943  setosa</p>
<p>2 -0.9060827 -0.05265667  setosa</p>
<p>3 -0.9608955 -0.03096467  setosa</p>
<p>4 -0.9167038 -0.08550457  setosa</p>
<p>5 -0.9101914  0.10073609  setosa</p>
<p>6 -0.7702262  0.22385668  setosa</p>
</blockquote>
<p>In ordinal multidimensional scaling, only the<br>
ordering of the initial distances is preserved; the obtained mapping is<br>
thus invariant under rotation and translation – like any MDS solution –<br>
and any monotonic scale transformation that preserves the rank order of<br>
similarity. The stress of the final MDS configuration is .025, not bad. Now we have a 2D representation of the data. Let’s plot it with {ggplot2}:</p>
<blockquote><p># – visualize w. {ggplot2}<br>library(ggplot2)<br>library(ggrepel)<br>library(RColorBrewer)<br>confIris$Color &lt;-recode(confIris$Species, ‘setosa’ = ‘aquamarine3’, ‘versicolor’ = ‘coral3’, ‘virginica’ = ‘deepskyblue3’)</p>
<p>confIris &lt;-confIris[order(confIris$Species), ]<br>confIris$Label[which(confIris$Species == ‘setosa’)] &lt;-paste(’s’, 1:length(which(confIris$Species == ‘setosa’)), sep = “”)<br>confIris$Label[which(confIris$Species<br>
== ‘versicolor’)] &lt;-paste(’ve’, 1:length(which(confIris$Species ==<br>
‘versicolor’)), sep = “”)<br>confIris$Label[which(confIris$Species ==<br>
‘virginica’)] &lt;-paste(‘vi’, 1:length(which(confIris$Species ==<br>
‘virginica’)), sep = “”)</p>
<p>ggplot(confIris, aes(x = D1, y = D2, label = Label)) + geom_text_repel(aes(x = D1, y = D2, label = Label),<br>size = 2, segment.size = .1) +<br>geom_point(size = 1.5, color = confIris$Color) +<br>geom_point(size = 1, color = “white”) +<br>ggtitle(‘Iris: semantic map.’) +<br>theme_bw() + theme(plot.title = element_text(size = 10))</p>
</blockquote>
<figure data-orig-width="450" data-orig-height="487"><img data-orig-width="450" src="https://i2.wp.com/68.media.tumblr.com/b99f96c76410f639578a2d73a9d8b4a7/tumblr_inline_otsnek1Qo31qa0hyw_540.png?resize=450%2C487" data-recalc-dims="1" data-orig-height="487"></figure>
<p>With 150 objects to represent, it is already difficult to read the similarity map. It can be readily seen that different types of observations (“s” for “setosa”, “vi” for “virginica”, and “ve” for “versicolor”, the famous iris$Species,<br>
each additionally indexed by the observation number in the respective<br>
class) tend to cluster naturally. However, we know one very important<br>
thing about the iris dataset: it is not<br>
linearly separable. In the simplest possible explanation of what<br>
non-linear separability means: look for the border between the blue (“virginica”) and red (“versicolor”)<br>
points, and try to imagine a straight line through the plane that<br>
perfectly separates the two classes (and then generalize if you wish: no<br>
plane in 3D, no hyper-plane in a higher dimensional space… can separate<br>
the classes perfectly). Ask yourself: what observations are the most responsible for these feature in the iris dataset? For example, is “vi7” at the<br>
bottom of the map a problematic case in categorization? What about the<br>
following: “vi50”, “vi47”, “ve34”, “ve23”? The observation “vi7” is<br>
found far away from the other members of its category, however, it’s<br>
still somewhat lonesome in this 2D similarity map. Observations “vi50”,<br>
“vi47”, “ve34”, and “ve23”, found in the lower right segment of the map<br>
but closer to its center, on the other hand, are found in a very<br>
crowded part of the similarity space: could they be a part of<br>
explanation for the presence of non-linear separability in iris?</p>
<p>The problem of ergonomics is obviously related to the<br>
overcrowding of the points in the map. The conceptual problem with<br>
dimensionality reduction to simple, visually comprehensible similarity<br>
spaces, is that there is no dimensionality reduction without a loss of information from<br>
the initial, higher-dimensional space (except in some really rare,<br>
theoretically possible cases). As we will see, as a consequence of this<br>
there are situations when seemingly unimportant observations manage to<br>
hide a part of their nature in a lower-dimensional representation. But<br>
we need to see that first.</p>
<p><b>Similarity in iris as a directed graph</b></p>
<p>Before performing dimensionality reduction with<br>
ordinal MDS, we were found in a 150-dimensional similarity – distance,<br>
actually – space. In spite of being a powerful technique for non-linear<br>
dimensionality reduction, MDS has “eaten” some of the information from<br>
the initial hyperspace. Now, let’s see if we can go back into the<br>
hyperspace and visualize it somehow to enable us discuss the importance<br>
of particular observations in this dataset. Each data point is described<br>
as a vector of 150 elements, each element representing the distance<br>
between the data point under observation and some other data point.<br>
Let’s search through these vectors and find the nearest neighbor – the most similar observation – for each data point:</p>
<blockquote><p># – iris as a directed graph:</p>
<p>mdsDistIris &lt;-as.matrix(mdsIris$confdist)<br>nnIris &lt;-apply(mdsDistIris, 1, function(x) {<br>minDist &lt;-sort(x, decreasing = T)<br>minDist &lt;-minDist[length(minDist)-1]<br>which(x == minDist)[1]<br>})</p>
<p># – graphFrame:</p>
<p>graphFrame &lt;-data.frame(from = 1:150, <br>                       to = nnIris,<br>                       Species = iris$Species)</p>
</blockquote>
<p>We have first discovered the nearest neighbors, and<br>
the introduced a new variable, Degree, that describes to how many other<br>
observations (excluding itself) does a particular data point presents<br>
the nearest neighbor. In the following similarity map, the size of the<br>
marker represents the degree of each observation:</p>
<figure data-orig-width="450" data-orig-height="487"><img data-orig-width="450" src="https://i2.wp.com/68.media.tumblr.com/2560a551db2cefc95b5ee8ebd51bf3f6/tumblr_inline_otsngqBwOH1qa0hyw_540.png?resize=450%2C487" data-recalc-dims="1" data-orig-height="487"></figure>
<p>Observations “vi50” and “ve34” stand close to each<br>
other, belonging to different classes; moreover, they are marked as<br>
having a higher degree in the nearest neighbor network (we haven’t<br>
visualized the network yet) than many other observations; they are candidates to represent the nearest neighbors to each other. </p>
<p>Still, “vi7” at the bottom<br>
of the map is certainly not a hub. In the next step, we change the<br>
visualization strategy. Again, get ready for a loss of information.<br>
While MDS attempts at a representation that will preserve as many as<br>
possible information about all pairwise<br>
similarities from the initial dataset, thus necessarily compromising<br>
with some error present in the lower-dimensional representation, we<br>
chose to sacrifice the context and represent information on similarity neighborhoods only. We will represent the similarity data from iris by instantiating a directed graph, with each node representing an observation, and each node having exactly one link, pointing towards the nearest neighbor of the respective observation. We use {igraph} to construct and represent the graph:</p>
<blockquote><p># – represent high-dimensional Iris neighbourhoods as directed graph:</p>
<p>graphFrame$from &lt;-confIris$Label[graphFrame$from]<br>graphFrame$to &lt;-confIris$Label[graphFrame$to]<br>library(igraph)  <br>irisNet &lt;-graph.data.frame(graphFrame, directed = T)<br>V(irisNet)$size &lt;-degree(irisNet)*1.25<br>V(irisNet)$color &lt;-as.character(confIris$Color)<br>V(irisNet)$label &lt;-confIris$Label</p>
<p># – plot w. {igraph}</p>
<p>par(mai=c(rep(0,4)))<br>plot(irisNet,</p>
<p>     vertex.shape = “circle”,<br>    vertex.frame.color = NA,<br>    edge.width = .75,<br>    edge.color = “grey”,<br>    edge.arrow.size = 0.15,<br>    vertex.label.font = 1,<br>    vertex.label.color = “black”,<br>    vertex.label.family = “sans”,<br>    vertex.label.cex = .65,<br>    vertex.label.dist = .35,<br>    edge.curved = 0.5,<br>    margin = c(rep(0,4)))</p>
</blockquote>
<figure data-orig-width="450" data-orig-height="487"><img data-orig-width="450" src="https://i2.wp.com/68.media.tumblr.com/ba66ae4bc51932449ff025f0e7a4021b/tumblr_inline_otsnheKgwA1qa0hyw_540.png?resize=450%2C487" data-recalc-dims="1" data-orig-height="487"></figure>
<p>As expected, “vi50” and “vi34” have mutual links,<br>
standing for each other’s nearest neighbor, and still being members of<br>
different categories; but “vi39” and “ve21” too, a fact that was less<br>
obvious in the similarity map. Also, we now discover that the nearest<br>
neighbor to “vi7” is “ve13” from another class.<br>
The clustering in the nearest neighbor graphs occurs naturally, and<br>
thus the graph conveys some information about the similarity context for<br>
groups of points in spite of the fact that it was not intentionally<br>
built to represent such information. </p>
<p><b>Maps vs. Graphs</b></p>
<p>The nearest neighbor directed graph approach is not<br>
very common among the attempts to visualize similarity data. However,<br>
following years of work in the field of distributive semantics, I have<br>
started abandoning similarity maps as a mean of data visualization<br>
almost completely in favor of graphs. While I haven’t performed any<br>
methodologically rigorous comparisons among the two approaches, I have<br>
used both in building interfaces for semantic search engines, and the<br>
users turned out to be always more satisfied with directed nearest<br>
neighbor graphs in comparisons to similarity maps. Intuitively, I would<br>
say the main reason is the absence of too much crowding of data points.<br>
Also, the aesthetics of graphs seem more pleasing. Graphs are maybe a<br>
bit more difficult to visually search through: the links and the<br>
occurrence of clusters tend to somehow guide the eye to search for a<br>
particular data point in the imminent neighborhood only. Again, I don’t<br>
find the ergonomics of similarity maps much more efficient in that<br>
respect. The drawback of directed graphs: while some important clusters<br>
of nearest neighbors emerge naturally in them, the graph layout will not<br>
necessarily enable the user to recognize the way the observations tend<br>
to group in general. I have experimented with directed graphs in which<br>
two nearest neighbors are selected for each observations, and that works<br>
too, but the graph becomes unreadable quickly for any number significantly larger than ten to fifteen observations. </p>
<figure data-orig-width="450" data-orig-height="418"><img data-orig-width="450" src="https://i2.wp.com/68.media.tumblr.com/22e522a2064515a79b73eb303d00293b/tumblr_inline_otsnhznEZa1qa0hyw_540.png?resize=450%2C418" data-recalc-dims="1" data-orig-height="418"></figure>
<p>Comparing the loss of information in similarity maps in contrast to the nearest neighbor graphs, it seems to me that the latter have<br>
a clear advantage in the presentation of complex datasets, and I would<br>
clearly prefer the graphs in any situation – or at least suggest always<br>
using them as an additional method of interpretation alongside the<br>
respective maps. In order to illustrate, I have inspected ordinal MDS solutions for iris<br>
distances in Euclidean space, ranging the solution dimensionality from<br>
two to five, and computed the accuracy of determining correctly the N-th<br>
neighbor for each observation for each solution. The following line<br>
chart is quite telling.<br>On the x-axis we find the order of the neighbor (1st, 2nd,<br>
etc), while the accuracy of correctly determining the neighbor of the<br>
respective order across the observations is represented on the y-axis (%<br>
scale). One can now have a quite direct insight into the behavior of<br>
information loss in ordinal MDS. The 2D solution seems to be especially problematic, with far less than 50% recognition of the 1st<br>
neighbor across the observations. The local information from<br>
higher-dimensional spaces represented by directed graphs perfectly<br>
complements the compromises made in the lower-dimensional similarity<br>
maps.</p>
<p>Goran S. Milovanović, PhD<br><a rel="nofollow" href="http://t.umblr.com/redirect?z=http%3A%2F%2FSmartCat&t=ZDE1YzY0NTYzZDVjZjRmYjRhOTlkYWMxMzAxZGYxN2U1NmFmODE3ZixRcWhrR0dpQw%3D%3D&b=t%3AfxfLHZZpYe9t9Oek1n3iNg&p=http%3A%2F%2Fwww.exactness.net%2Fpost%2F157582845120%2Fasknasa-whats-the-optimal-time-for-aliens-to&m=1" target="_blank">Data Science Consultant, SmartCat</a></p>
<figure data-orig-height="180" data-orig-width="180"><img data-orig-width="180" src="https://i1.wp.com/68.media.tumblr.com/03ea67987ffd18eb50e257273ee7f362/tumblr_inline_otsnkus6R61qa0hyw_540.png?resize=180%2C180" data-recalc-dims="1" data-orig-height="180"></figure>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://www.exactness.net/post/163519386590"> The Exactness of Mind</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/ZGwkhbg_kx0" height="1"></a></div>