<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/do-clustering-by-dimensional-collapse/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://r-posts.com/do-clustering-by-dimensional-collapse/"> R-posts.com</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<h2>Problem</h2>
<p>Image that someone in a bank want to find out whether some of bank’s credit card holders are acctually the same person, so according to his experience， he set a rule: the people share either the same address or the same phone number can be reasonably regarded as the same person. Just as the example:</p>
<pre>library(tidyverse)
a &lt;- data_frame(id = 1:16,
                addr = c(&quot;a&quot;, &quot;a&quot;, &quot;a&quot;, &quot;b&quot;, &quot;b&quot;, &quot;c&quot;, &quot;d&quot;, &quot;d&quot;, &quot;d&quot;, &quot;e&quot;, &quot;e&quot;, &quot;f&quot;, &quot;f&quot;, &quot;g&quot;, &quot;g&quot;, &quot;h&quot;),
                phone = c(130L, 131L, 132L, 133L, 134L, 132L, 135L, 136L, 137L, 136L, 138L, 138L, 139L, 140L, 141L, 139L),
                flag = c(1L, 1L, 1L, 2L, 2L, 1L, 3L, 3L, 3L, 3L, 3L, 3L, 3L, 4L, 4L, 3L))

head(a)

## id   addr    phone   flag
## 1    a   130 1
## 2    a   131 1
## 3    a   132 1
## 4    b   133 2
## 5    b   134 2
## 6    c   132 1 </pre>
<p>In the dataframe </p>
<pre>]czoxOlwiYVwiO3tbJiomXX0=[</pre>
<p>, the letters in column </p>
<pre>]czo0OlwiYWRkclwiO3tbJiomXX0=[</pre>
<p> stand for address information, the numbers in column </p>
<pre>]czo1OlwicGhvbmVcIjt7WyYqJl19[</pre>
<p> stand for phone numbers, and the integers in column </p>
<pre>]czo0OlwiZmxhZ1wiO3tbJiomXX0=[</pre>
<p> is what he want: the CLUSTER flag which means “really” different persons.</p>
<p><img alt="The records in a bank" src="https://i0.wp.com/r-posts.com/wp-content/uploads/2018/05/dim_coll_001-1.png?w=660" data-recalc-dims="1"></p>
<p>In the above plot, each point stand for a “identity” who has a address which you can tell according to horizontal axis , and a phone number which you can see in vertical axis. The red dotted line present the “connections” betweent identities, which actually means the same address or phone number. So the wanted result is the blue rectangels to circle out different flags which reprent really different persons.</p>
<h2>Goal</h2>
<p>The “finding the same person” thing is typically a clustring process, and I am very sure there are pretty many ways to do it, Such as <a rel="nofollow" href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure" target="_blank">Disjoint-set data structure</a>. But, I can not help thinking mayby we can make it in a simple way with R. that’s my goal.</p>
<h2>“Dimensional Collapse”</h2>
<p>When I stared at the plot, I ask myself, why not map the x-axis information of the points to the very first one according to the y-axis “connections”. When everything goes well and all done, all the grey points should be mapped along the red arrows to the first marks of the groups, and there should be only 4 marks leave on x-axis: a, b, d and g, instead of 9 marks in the first place. And the y-axis information, after contributing all the “connection rules”, can be put away now, since the left x-axis marks are exactly what I want: the final flags. It is why I like to call it “Dimensional Collapse”. </p>
<p>Furthermore, in order to take advantage of R properties, I also:<br>
1. Treat both dimensions as integers by factoring them.<br>
2. Use “integer subsetting” to map and collapse.</p>
<p><img alt="Dimensional Collapse" src="https://i2.wp.com/r-posts.com/wp-content/uploads/2018/05/dimension-collapse-02.png?w=660" data-recalc-dims="1"></p>
<pre>axis_collapse &lt;- function(df, .x, .y) {
    .x &lt;- enquo(.x)
    .y &lt;- enquo(.y)
    
    # Turn the address and phone number into integers.
    df &lt;- mutate(df,
                 axis_x = c(factor(!!.x)),
                 axis_y = c(factor(!!.y)))
    
    oldRule &lt;- seq_len(max(df$axis_x))
    
    mapRule &lt;- df %>%
      select(axis_x, axis_y) %>%
      group_by(axis_y) %>%
      arrange(axis_x, .by_group = TRUE) %>%
      mutate(collapse = axis_x[1]) %>%
      ungroup() %>%
      select(-axis_y) %>%
      distinct() %>%
      group_by(axis_x) %>%
      arrange(collapse, .by_group = TRUE) %>%
      slice(1) %>%  
      ungroup() %>%
      arrange(axis_x) %>%
      pull(collapse)
    
    # Use integer subsetting to collapse x-axis.
    # In case of indirect &quot;connections&quot;, we should do it recursively.
    while (TRUE) {
        newRule &lt;- mapRule[oldRule]
        if(identical(newRule, oldRule)) {
            break
        } else {
            oldRule &lt;- newRule
        }
    }
    
    df &lt;- df %>%
      mutate(flag = newRule[axis_x],
             flag = c(factor(flag))) %>%
      select(-starts_with(&quot;axis_&quot;))
    
    df
}</pre>
<p>Let see the result.</p>
<pre>a %>%
  rename(flag_t = flag) %>% 
  axis_collapse(addr, phone) %>%
  mutate_at(.vars = vars(addr:flag), factor) %>%
  ggplot(aes(factor(addr), factor(phone), shape = flag_t, color = flag)) +
  geom_point(size = 3) +
  labs(x = &quot;Address&quot;, y = &quot;Phone Number&quot;, shape = &quot;Target Flag:&quot;, color = &quot;Cluster Flag:&quot;)</pre>
<p><img alt="The Clustering result compared to the target" src="https://i2.wp.com/r-posts.com/wp-content/uploads/2018/05/dimension-collapse-03.png?w=660" data-recalc-dims="1"></p>
<p>Not bad so far.</p>
<h2>Calculation Complexity</h2>
<p>Let make a simple test about time complexity.</p>
<pre>test1 &lt;- data_frame(addr = sample(1:1e4, 1e4), phone = sample(1:1e4, 1e4))
test2 &lt;- data_frame(addr = sample(1:1e5, 1e5), phone = sample(1:1e5, 1e5))

bm &lt;- microbenchmark::microbenchmark(n10k = axis_collapse(test1, addr, phone),
                                     n100k = axis_collapse(test2, addr, phone),
                                     times = 30)

summary(bm)

## expr min lq  mean    median  uq  max neval   cld
## n10k     249.2172    259.918     277.0333    266.9297    279.505     379.4292    30  a
## n100k    2489.1834   2581.731    2640.9394   2624.5741   2723.390    2839.5180   30  b 
</pre>
<p>It seems that the growth of consumed time is in linear relationship with data increase holding the other conditions unchanged. That is acceptable.</p>
<h2>More Dimensions?</h2>
<p>To me, since this method collapse one dimension by transfering their clustering information to the other dimension, so the method should can be used resursively on more than 2 dimensions. But I am not 100% sure. Let do a simple test.</p>
<pre>a %>%
  # I deliberately add a column which connect group 2 and 4 only.
  mutate(other = c(LETTERS[1:14], &quot;D&quot;, &quot;O&quot;)) %>%
  # use axis_collapse recursively
  axis_collapse(other, phone) %>%
  axis_collapse(flag, addr) %>%
  ggplot(aes(x = factor(addr), y = factor(phone), color = factor(flag))) +
  geom_point(size = 3) +
  labs(x = &quot;Address&quot;, y = &quot;Phone Number&quot;, color = &quot;Cluster Flag:&quot;)
</pre>
<p><img alt="Dimensional Collapse when more than 2 dimensions" src="https://i2.wp.com/r-posts.com/wp-content/uploads/2018/05/dimension-collapse-04.png?w=660" data-recalc-dims="1"></p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://r-posts.com/do-clustering-by-dimensional-collapse/"> R-posts.com</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/VBVSqDAMCNo" height="1"></a></div>