Proposal and study of statistical features for string similarity computation and classification

Érick Oliveira Rodrigues, Dalcimar Casanova, Marcelo Teixeira, Vinicius Pegorini, Fábio Favarim, Esteban Walter Gonzalez Clua, Aura Conci, Panos Liatsis

TL;DR

This paper introduces novel statistical features derived from Co-occurrence Matrices (COM) and Run-Length Matrices (RLM) for computing string similarity, outperforming existing methods on synthetic and real-world plagiarism datasets. These language-agnostic features offer a robust approach to text comparison, classification, and plagiarism detection.

What Problem Does This Paper Address?

Comparing strings for similarity is crucial in various applications like optical character recognition (OCR), plagiarism detection, and text entailment. Traditional methods often rely on language-specific information or are computationally intensive. This paper addresses the need for language-agnostic, statistically-driven features that can effectively capture string similarity across different contexts and languages, aiming to improve accuracy and efficiency in these tasks.

Methods

The authors propose adaptations of Co-occurrence Matrices (COM) and Run-Length Matrices (RLM), commonly used in visual computing, for string similarity computation.

  • COM Features: These features are derived from matrices that capture the co-occurrence of characters at specific distances within strings. New features like Co-occurrence Probability (COP), Probability Score (PS), Total Probability Score (TPS), and Co-occurrences Over Distances (COD) are introduced.
  • RLM Features: These features are based on an adapted concept of Run-Length Encoding. New features include Sum of Occurrences (SO), Weighted Sum of Occurrences (WSO), Maximal Occurrence (MO), and variations thereof (MOML, MLMO, MORL), as well as an RLM-based Maximal Consecutive Longest Common Subsequence (RLMMCLCS).
  • Other Features: The paper also evaluates established features like Longest Common Subsequence (LCS), Maximal Consecutive Longest Common Subsequence (MCLCS), Mutual Information (MI), and various edit distances (Hamming, Levenshtein, Damerau).
  • WMI: A modified version of Mutual Information, Weighted Mutual Information (WMI), is proposed, incorporating a shift operation to account for character order.

Datasets

  • Synthetic Dataset: Generated strings of varying lengths (up to 14 and 200 characters) with controlled randomness (R variable) to simulate different degrees of string similarity.
  • Wikipedia Plagiarism Dataset: A real-world dataset created by Clough and Stevenson (2011), containing student answers to computer science questions, with four levels of plagiarism (near copy, light revision, heavy revision, non-plagiarism).

Key Insights and Ideas

  • COM and RLM Outperform: The newly proposed COM and RLM features demonstrated superior performance compared to traditional methods like LCS and edit distances, especially in scenarios with higher randomness or longer strings.
  • Language Agnosticism: The statistical nature of COM and RLM features makes them inherently language-agnostic, a significant advantage for cross-lingual applications.
  • Randomness Matters: The performance of features is highly dependent on the degree of randomness between strings. RLM features, in particular, showed resilience to increased randomness.
  • MI Limitations: Standard Mutual Information (MI) proved to be less effective for string similarity compared to its weighted counterpart (WMI) and other statistical features.
  • Feature Importance Varies: The ranking of features showed that COM and RLM-based features are generally more valuable for string comparison and plagiarism detection tasks.

Key Results

  • Synthetic Datasets: In experiments with synthetic data, COM and RLM features outperformed other groups in 3 out of 4 cases. For longer strings (up to 200 characters) and moderate randomness (R=0.15), RLM features achieved the highest accuracy.
  • Plagiarism Detection: On the Wikipedia plagiarism dataset, the proposed RLM group achieved the highest accuracy (84.21%), outperforming previous state-of-the-art results.
  • Classifier Performance: The LMT (Logistical Model Trees) classifier generally yielded the best accuracies on synthetic datasets, while Decision Table and Naive Bayes were effective for the plagiarism dataset.
  • Feature Extraction Time: COM and RLM feature extraction, after initial matrix construction, was efficient, with COM requiring an additional ~4.5µs and RLM ~16.7µs per instance.

Limitations and Future Work

  • Feature Optimization: The authors suggest that further exploration of COM and RLM features could yield even better results.
  • Classifier Choice: While LMT performed well, its computational cost for predictive model generation might be a concern in applications requiring frequent retraining.
  • Dataset Limitations: The paper acknowledges that the source code and datasets used are available for further exploration.
  • Future Work: The authors propose that other features based on COM and RLM can be explored, and the proposed framework can be further investigated for its full potential in string similarity computation.

Summary updated

BibTeX
@article{rodrigues2020proposal,
  author = {Érick Oliveira Rodrigues and Dalcimar Casanova and Marcelo Teixeira and Vinicius Pegorini and Fábio Favarim and Esteban Walter Gonzalez Clua and Aura Conci and Panos Liatsis},
  title = {{Proposal and study of statistical features for string similarity computation and classification}},
  journal = {Int. J. Data Min. Model. Manag.},
  year = {2020},
  url = {https://openreview.net/forum?id=WVL7A9s0mn},
}
Figure