Cluster and Merge Similar Values Within a Character Vector

These functions take a character vector as input, identify and cluster similar values, and then merge clusters together so their values become identical. The functions are an implementation of the key collision and ngram fingerprint algorithms from the open source tool Open Refine < http://openrefine.org/>. More info on key collision and ngram fingerprint can be found here < https://github.com/OpenRefine/OpenRefine/wiki/Clustering-In-Depth>.


refinr

Travis-CI Build Status AppVeyor Build Status Coverage Status CRAN_Status_Badge

refinr is designed to cluster and merge similar values within a character vector. It features two functions that are implementations of clustering algorithms from the open source software OpenRefine. The cluster methods used are key collision and ngram fingerprint (more info on these here).

In addition, there are a few add-on features included, to make the clustering/merging functions more useful. These include approximate string matching to allow for merging despite minor mispellings, the option to pass a dictionary vector to dictate edit values, and the option to pass a vector of strings to ignore during the clustering process.

Please report issues, comments, or feature requests.

Installation

Install from CRAN:

install.packages("refinr")

Or install the dev version from this repo:

devtools::install_github("ChrisMuir/refinr")

Example Usage

library(refinr)
x <- c("Acme Pizza, Inc.", "ACME PIZZA COMPANY", "acme pizza LLC", "Acme Pizza, Inc.")
key_collision_merge(x)
#> [1] "Acme Pizza, Inc." "Acme Pizza, Inc." "Acme Pizza, Inc." "Acme Pizza, Inc."

A dictionary character vector can be passed to key_collision_merge, which will dictate merge values when a cluster has a match within the dict vector.

x <- c("Acme Pizza, Inc.", "ACME PIZZA COMPANY", "acme pizza LLC", "Acme Pizza, Inc.")
key_collision_merge(x, dict = c("Nicks Pizza", "acme PIZZA inc"))
#> [1] "acme PIZZA inc" "acme PIZZA inc" "acme PIZZA inc" "acme PIZZA inc"

Function n_gram_merge can be used to merge similar values that contain slight spelling differences. The stringdist package is used for calculating edit distance between strings. refinr links to the stringdist C API to improve the speed of the functions.

x <- c("Acmme Pizza, Inc.", "ACME PIZA COMPANY", "Acme Pizzazza LLC")
n_gram_merge(x, weight = c(d = 0.2, i = 0.2, s = 1, t = 1))
#> [1] "ACME PIZA COMPANY" "ACME PIZA COMPANY" "ACME PIZA COMPANY"
 
# The performance of the approximate string matching can be ajusted using parameters 
# "weight" and/or "edit_threshold".
n_gram_merge(x, weight = c(d = 1, i = 1, s = 0.1, t = 0.1))
#> [1] "Acme Pizzazza LLC" "ACME PIZA COMPANY" "Acme Pizzazza LLC"

Both key_collision_merge and n_gram_merge have optional arg ignore_strings, which takes a character vector of strings to be ignored during the merging of values.

x <- c("Bakersfield Highschool", "BAKERSFIELD high", "high school, bakersfield")
key_collision_merge(x, ignore_strings = c("high", "school", "highschool"))
#> [1] "BAKERSFIELD high" "BAKERSFIELD high" "BAKERSFIELD high"

The clustering is designed to be insensitive to common business name suffixes, i.e. "inc", "llc", "co", etc. This feature can be turned on/off using function parameter bus_suffix.

Workflow for checking the results of the refinr processes

library(dplyr)
library(knitr)
 
x <- c(
  "Clemsson University", 
  "university-of-clemson", 
  "CLEMSON", 
  "Clem son, U.", 
  "college, clemson u", 
  "M.I.T.", 
  "Technology, Massachusetts' Institute of", 
  "Massachusetts Inst of Technology", 
  "UNIVERSITY:  mit"
)
 
ignores <- c("university", "college", "u", "of", "institute", "inst")
 
x_refin <- x %>% 
  refinr::key_collision_merge(ignore_strings = ignores) %>% 
  refinr::n_gram_merge(ignore_strings = ignores)
 
# Create df for comparing the original values to the edited values.
# This is especially useful for larger input vectors.
inspect_results <- data_frame(original_values = x, edited_values = x_refin) %>% 
  mutate(equal = original_values == edited_values)
 
# Display only the values that were edited by refinr.
knitr::kable(
  inspect_results[!inspect_results$equal, c("original_values", "edited_values")]
)
#> |original_values                         |edited_values                    |
#> |:---------------------------------------|:--------------------------------|
#> |Clemsson University                     |CLEMSON                          |
#> |university-of-clemson                   |CLEMSON                          |
#> |Clem son, U.                            |CLEMSON                          |
#> |college, clemson u                      |CLEMSON                          |
#> |Technology, Massachusetts' Institute of |Massachusetts Inst of Technology |
#> |UNIVERSITY:  mit                        |M.I.T.                           |

Notes

  • This package is NOT meant to replace OpenRefine for every use case. For situations in which merging accuracy is the most important consideration, OpenRefine is preferable. Since the merging steps in refinr are automated, there will usually be more false positive merges, versus manually selecting clusters to merge in OpenRefine.
  • The advantages this package has over OpenRefine:
    • Operations are fully automated.
    • Facilitates a more reproducible workflow.
    • Faster when working with large input data (character vectors of length 500000+).

News

refinr 0.3.1

IMPROVEMENTS

  • Package is now linking to the stringdist C API, and calling C functions in place of using stringdist::stringdistmatrix(). This change results in speed improvements in function n_gram_merge(), and requires that stringdist v0.9.5.1 or greater be installed.

refinr 0.3.0

PKG API CHANGES

  • In function n_gram_merge(), renamed arg edit_dist_weights to weight. The only purpose of this arg is to be passed along to function stringdistmatrix from the stringdist package (which uses the name weight, so this change is simply to match that).

BUG FIXES

  • Fixed issue in which input strings that contained accent marks were not being properly handled/clustered (#9). The fix involved adding stringi to Imports and using stringi::stri_trans_general().

  • Fixed issue in n_gram_merge() in which incorrect values were being return when input arg ignore_strings was not NULL, and arg bus_suffix = FALSE (#7).

  • Fixed issue in which input strings that contained punctuation that was NOT surrounded by spaces was returning incorrect values (#6).

  • Fixed issue in which the edit value assigned to a cluster was sometimes not the most frequent string in that cluster (#5).

NEW FEATURES

  • Rewrote some of the cpp functions to incorporate std::unordered_map(), resulting in a substantial speed improvement when passing large character vectors (length 100,000+) to either of the exported functions (#8).

refinr 0.2.0 (2018-01-10)

  • released on CRAN

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("refinr")

0.3.1 by Chris Muir, 9 months ago


https://github.com/ChrisMuir/refinr


Report a bug at https://github.com/ChrisMuir/refinr/issues


Browse source code at https://github.com/cran/refinr


Authors: Chris Muir [aut, cre]


Documentation:   PDF Manual  


GPL-3 license


Imports Rcpp, stringdist, stringi

Suggests testthat, knitr, rmarkdown, dplyr

Linking to Rcpp, stringdist


See at CRAN