Clustering-Based Article Identification in Historical Newspapers

Martin Riedl, Daniela Betz, Sebastian PadóNAACL 2019

TL;DR

This paper tackles the challenge of automatically identifying individual articles within digitized historical newspapers, a crucial step for large-scale historical research. They propose a novel approach that uses only the OCR text, framing the problem as a segmentation and clustering task, and introduce a new annotated dataset to evaluate their methods. Their findings highlight the effectiveness of word embeddings for article clustering and underscore the significant impact of OCR quality on performance.

What Problem Does This Paper Address?

Historical newspapers are invaluable resources for understanding past societies, but accessing and analyzing their content at scale is hindered by the digitization process. While many archives provide scanned pages and even OCR'd text, this raw output often consists of page-level text files, not individual articles. This means that articles, especially those spanning multiple pages or even issues, are fragmented. Furthermore, the OCR process itself is prone to errors due to the poor quality of scans, complex layouts, and varied typesetting of historical documents. This paper addresses the critical gap of automatically identifying and grouping these fragmented article pieces into coherent, full articles using only the imperfect textual data generated by OCR.

Methods

The authors frame the problem as a two-step process: segmentation and clustering.

  1. Text Segmentation: They employ a modified version of the TextTiling algorithm. TextTiling works by dividing text into segments based on lexical similarity, assuming that coherent text uses similar vocabulary. The algorithm identifies potential segmentation boundaries by analyzing the similarity scores between adjacent text blocks.
  2. Segment Clustering: Once segments are identified, the core task is to group segments that belong to the same article. They use spectral clustering, a powerful technique that operates on a dimensionality-reduced similarity matrix, making it robust. The key innovation here is the exploration of different similarity measures between text segments:
  3. Jaccard similarity on word distributions.
  4. Jaccard similarity on character n-grams (ranging from 2 to 8 characters).
  5. Cosine similarity between fastText word embeddings. This is particularly interesting as fastText can generate embeddings for out-of-vocabulary words, which is crucial for noisy OCR text.

Datasets

The paper introduces a newly created annotated dataset for article identification in historical newspapers.

  • Dataset Source: Five issues of the New York Tribune Sunday magazine from March 1912.
  • Annotation: 82 pages were annotated by three annotators. Segments were marked as either part of an article (with a unique ID) or as an advertisement. Advertisements were merged due to high disagreement.
  • Key Characteristics: The dataset includes long articles, some of which are serializations spanning multiple issues, and it reflects the challenges of OCR quality and complex newspaper layouts.
  • Evaluation Settings:
    • BYISSUE: Evaluating clustering within individual newspaper issues.
  • ALLISSUES: Evaluating clustering across all issues, which is a more challenging task due to longer-range dependencies.

Key Insights and Ideas

  • OCR Quality is King (or Queen): The most significant takeaway is that the quality of the OCR output is the primary bottleneck. Even sophisticated clustering methods struggle when the input text is heavily corrupted by OCR errors. Filtering pages by OCR quality significantly improved results.
  • Word Embeddings Outperform N-grams: Surprisingly, despite the expectation that character n-grams might be more robust to OCR errors, cosine similarity based on fastText word embeddings consistently outperformed Jaccard similarity on word or character n-gram distributions for most cases. This suggests that embeddings capture semantic coherence more effectively, even with noisy text.
  • Segmentation is Hard: Automatically segmenting newspaper pages into article-like chunks is a difficult task. The TextTiling algorithm, while useful, tends to over-segment the text, leading to a substantial drop in clustering performance when used as a preprocessing step.
  • Clustering Works Best with Gold Standards: When provided with perfect segmentation (gold standard), the clustering approach yields promising results, especially within a single issue. The challenge escalates significantly when trying to cluster across multiple issues.

Key Results

  • Experiment 1 (Gold Standard Segmentation):
    • BYISSUE: The best F1 score achieved was around 68% using fastText embeddings with 14 clusters. Cosine similarity on fastText embeddings outperformed Jaccard similarity on words and 7-grams by about 2.8 points F1.
  • ALLISSUES: F1 scores were lower but still substantial, with the best performance around 55% for 7-gram similarity and fastText embeddings.
  • Experiment 2 (Automatic Segmentation):
    • TextTiling Segmentation: Achieved low precision (0.1168) but high recall (0.6602), indicating significant over-segmentation.
  • Clustering with Automatic Segments: Performance dropped considerably. For BYISSUE, F1 dropped from ~0.68 to ~0.46. For ALLISSUES, it dropped from ~0.55 to ~0.28. FastText embeddings remained the best similarity measure.
  • OCR Quality Impact: Filtering pages by OCR quality showed that performance could improve significantly, with F1 scores reaching up to 0.7629 for high-quality pages.

Limitations and Future Work

  • Limitations:
    • The primary limitation is the low quality of OCRed historical texts, which severely impacts performance.
  • Automatic segmentation using TextTiling is prone to over-segmentation, hindering downstream clustering.
  • The dataset, while novel, is limited to a specific newspaper and time period.
  • Future Work:
    • Improving OCR Quality: This remains the most critical area.
  • Integrating Visual Features: The authors suggest that incorporating visual features from the newspaper pages (e.g., layout, font styles) alongside textual information could significantly improve segmentation and article identification.
  • Manual Segmentation as a Compromise: Given the difficulty of automatic segmentation, they propose that manual segmentation, even with less effort than full OCR post-correction, could be a valuable intermediate step.
  • Expanding the Dataset: Creating larger and more diverse datasets for evaluation.

Summary updated

BibTeX
@inproceedings{riedl2019clustering,
  author = {Martin Riedl and Daniela Betz and Sebastian Padó},
  title = {{Clustering-Based Article Identification in Historical Newspapers}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2019},
}
Figure