A new simple and effective measure for bag-of-word inter-document similarity measurement

Sunil Aryal, Kai Ming Ting, Takashi Washio, Gholamreza HaffariarXiv 2019 · arXiv

Abstract

Traditional document similarity measures often rely on tf-idf weighting schemes designed for keyword-based information retrieval. However, these assumptions can fail in "query-by-example" tasks where the query is a full document. This paper introduces Sp, a data-dependent probabilistic similarity measure for bag-of-words representations. Sp evaluates similarity based on the distribution of term frequencies across a collection, avoiding explicit weighting and providing more intuitive results. Empirical evaluations across ten benchmark datasets demonstrate that Sp is highly competitive, consistent, and robust compared to state-of-the-art measures like BM25 and cosine similarity.

Introduction

Measuring inter-document similarity is a cornerstone of text mining, essential for tasks such as clustering, classification, and information retrieval. For decades, the combination of cosine similarity and tf-idf (term frequency-inverse document frequency) weighting has served as the standard approach.

Despite its success, tf-idf has inherent limitations when applied to "query-by-example" (QBE) scenarios. In QBE, the "query" is an entire document rather than a few keywords. The core assumptions of tf-idf—that higher term frequency always implies higher relevance and that rare words are universally more important—can lead to counter-intuitive results. For example, if a query document contains a specific term once, a document containing it fifty times might be considered more similar by tf-idf than one containing it once, despite the latter being a closer match in terms of topical focus.

The Sp Similarity Measure

To address these issues, the authors propose Sp, a measure that leverages the global distribution of term frequencies. Instead of assigning static weights to terms, Sp calculates similarity based on the "gap" between term frequencies in two documents relative to the rest of the collection.

Methodology

The fundamental intuition behind Sp is that two documents are similar with respect to a term if few other documents in the collection have a frequency count falling between them. If the interval between the frequency of a word in document A and document B is sparsely populated, the two documents are considered more similar for that term.

Mathematically, Sp is defined as: $$s_{sp}(\mathbf{x}, \mathbf{y}) = \frac{1}{|T_{\mathbf{x}} \cup T_{\mathbf{y}}|} \sum_{t_i \in T_{\mathbf{x}} \cap T_{\mathbf{y}}} \log \frac{N}{|\{z \in D : \min(x_i, y_i) \leq z_i \leq \max(x_i, y_i)\}|}$$

This approach offers several technical advantages:

  • Data-Dependency: It automatically adapts to the specific characteristics of the dataset without requiring manual tuning of tf-idf variants.
  • Scale Invariance: The measure is invariant to monotonic scaling of frequency values.
  • Efficiency: With preprocessing, Sp operates in $O(M)$ time, maintaining the speed of standard cosine similarity.

Addressing the IDF Blind Spot

Traditional IDF can fail to capture significant similarity signals. For instance, if a term appears in every document, its IDF weight becomes zero, effectively ignoring it. However, if a query and a candidate document share a specific, high frequency for that term while others do not, this is a strong indicator of similarity that Sp naturally captures.

Table 2: A scenario demonstrating how traditional IDF can fail by ignoring frequent but discriminative terms.

Comparison of Assumptions

The Sp approach fundamentally differs from tf-idf in its underlying assumptions regarding term importance and document ranking.

Table 3: Comparison of underlying assumptions between traditional tf-idf and the proposed Sp approach.

While tf-idf assumes a linear or logarithmic relationship between frequency and relevance, Sp treats similarity as the inverse of the probability of finding a document between two frequency points. This density-based approach is more robust against the outliers and skewed distributions common in natural language data.

Experimental Evaluation

The authors evaluated Sp across ten diverse benchmark datasets, including TREC (Fbis, La1s, La2s, New3s), 20 Newsgroups (Ng20), Ohsumed (Ohscal), Reuters (R8, R52), Yahoo (Wap), and University Web Pages (Webkb).

Key Results

Performance was measured using Mean Average Precision (MAP@25) against BM25 and various cosine similarity weighting schemes:

  1. Binary Representation: Sp significantly outperformed existing measures in binary scenarios (presence/absence of words), effectively "learning" an optimal weighting scheme from the data distribution.
  2. Consistency: Unlike cosine similarity, which shows high variance depending on the chosen tf-idf variant, Sp provided consistently high performance across all ten datasets.
  3. Robustness: Sp avoids the "negative weight" issue present in BM25, where extremely common terms can paradoxically decrease similarity scores.

Conclusion and Future Work

Sp represents a simple yet effective shift in how we measure document similarity. By moving from static term weighting to a data-dependent probabilistic model, it provides more intuitive results for query-by-example tasks.

Currently, Sp is limited to the Bag-of-Words model and does not account for semantic relationships or word order. Future research could explore extending this density-based similarity approach to other data types, such as categorical or numerical features in broader machine learning applications. Additionally, optimizing updates for dynamic, non-static collections remains an area for further development.

Summary updated

Abstract

To measure the similarity of two documents in the bag-of-words (BoW) vector representation, different term weighting schemes are used to improve the performance of cosine similarity---the most widely used inter-document similarity measure in text mining. In this paper, we identify the shortcomings of the underlying assumptions of term weighting in the inter-document similarity measurement task; and provide a more fit-to-the-purpose alternative. Based on this new assumption, we introduce a new simple but effective similarity measure which does not require explicit term weighting. The proposed measure employs a more nuanced probabilistic approach than those used in term weighting to measure the similarity of two documents w.r.t each term occurring in the two documents. Our empirical comparison with the existing similarity measures using different term weighting schemes shows that the new measure produces (i) better results in the binary BoW representation; and (ii) competitive and more consistent results in the term-frequency-based BoW representation.
BibTeX
@misc{aryal2019new,
  author = {Sunil Aryal and Kai Ming Ting and Takashi Washio and Gholamreza Haffari},
  title = {{A new simple and effective measure for bag-of-word inter-document similarity measurement}},
  year = {2019},
  eprint = {1902.03402},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.03402},
}
Figure