Information Extraction & Text Mining is a subfield of Natural Language Processing (NLP) that focuses on automatically extracting structured information and knowledge from unstructured textual data.

Natural Language Processing (NLP) is an interdisciplinary subfield of linguistics, computer science, and artificial intelligence concerned with the interactions between computers and human language, in particular how to program computers to process and analyze large amounts of natural language data. The goal is a computer capable of 'understanding' the contents of documents, including the contextual nuances of the language within them. The technology can then accurately extract information and insights contained in the documents as well as categorize and organize the documents themselves.

Text Segmentation is a subfield of Syntactic Text Processing that deals with automatically dividing a text into smaller segments or units that can be analyzed or processed separately. It involves developing algorithms and models that can identify and classify the structural or semantic boundaries between different sections or paragraphs in a text, and group them into meaningful and coherent segments.

Text Clustering is a subfield of Information Extraction & Text Mining that deals with grouping similar documents or sentences into clusters based on their content. The goal of text clustering is to discover patterns in large amounts of unstructured text data and identify groups of documents that share common themes, topics, or features.

<h1>Clustering-Based Article Identification in Historical Newspapers</h1> <h2>Abstract</h2> <p>This article focuses on the problem of identifying articles and recovering their text from within and across newspaper pages when OCR just delivers one text file per page. We frame the task as a segmentation plus clustering step. Our results on a sample of 1912 New York Tribune magazine shows that performing the clustering based on similarities computed with word embeddings outperforms a similarity measure based on character n-grams and words. Furthermore, the automatic segmentation based on the text results in low scores, due to the low quality of some OCRed documents.</p> <h2>1 Introduction</h2> <p>Historical newspapers are among the “most important” and “most often used” sources for many historians (Tibbo, 2003): Since the rise of regional and local newspaper culture in the late 18th and early 19th centuries, newspapers provide a window into national and global events and debates as well as into local everyday life (Slauter, 2015). Traditionally, historical newspapers were stored on microfilms in local archives. Access was manual, required travel and authorization, and was often complicated by poor film quality (Duff et al., 2004). Digital availability of newspapers has scaled up the accessibility of historical newspapers tremendously and enabled large-scale analysis of phenomena like text re-use (Smith et al., 2015) or ethnic stereotyping (Garg et al., 2018). Digital access to the full range of information in a newspaper is challenging, though. It requires (a), scanning of newspaper pages or microfilms into digital image files; (b), optical character recognition (OCR) to transfer images into text streams; and (c), identification of articles in the text stream. 1 Few historical newspapers have gone through all steps. For example, the vast Chronicling America archive of historical newspapers at the Library of Congress 2 only underwent steps (a) and (b), providing text files at the level of newspaper pages, without manual OCR post-correction (see Figure 1). Due to the multi-column format of almost all newspapers, each text file contain multiple articles. In addition, many articles span several pages: they are split across text files. This is an obvious obstacle to any analysis requiring complete articles. It becomes particularly pressing for articles that span multiple issues (typically days or weeks). Notable among them are serial stories or serial novels , serialization being among the most important publication strategies for literary works in the 19th and 20th centuries (Lund, 1993). In this paper, we investigate the task of article identification across newspaper pages , corresponding to step (c) above. We use only textual information from OCR as input, modelling the task as a sequence of a segmentation and a clustering step. Whereas most previous work solely uses image data for similar tasks, here, we examine the performance of an approach that uses textual information only. We introduce and provide a new annotated dataset sampled from the 1912 New York Tribune magazine. We find that clustering segments works relatively well for individual issues and becomes substantially more difficult across issues. Segment similarity based on word embeddings outperforms character n-grams similarities for most cases. The major challenge of the task is mainly the inferior scan quality which results in poor OCR text output.</p> <h2>2 Related Work</h2> <p>The task tackled in this paper can be split into two sub-tasks: the detection of the different articles and the clustering of parts of the same article. Most previous work performs the segmentation of newspaper pages directly at the image level (Hebert et al., 2014; Meier et al., 2017). This strategy avoids having to deal with spelling errors arising from OCR. However, these methods are not applicable when only textual output is available. A different line of research addresses the detection of segments in texts. Often, contemporary newspaper texts, Wikipedia articles or novels are artificially merged (e.g. Choi, 2000; Galley et al., 2003). Most of these methods are based on similarities between adjacent sentences or segments. The similarities are mostly computed using words (Hearst, 1997; Choi, 2000) or dense vector representations like topic models (Bestgen, 2006; Riedl and Biemann, 2012) or embeddings (Alemi and Ginsparg, 2015). Another related task is genre classification, in particular for newspaper texts. Lorang et al. (2015) present a classifier for detecting poetic content, which is however based again on images and incorporates image preprocessing techniques. Lonij and Harbers (2016) build a general genre classifier for text spans, but only for historical Dutch newspapers. A general limitation of this approach is that the articles which we want to separate may not differ in gender: this is often true (e.g., editorial content in the middle with advertisements on the side) but not always (e.g., multi-column pages such as title pages). At the textual level, article identification is related to author identification (Stamatatos, 2009) and style breach detection (Tschuggnall et al., 2017), which group texts by author. However, these settings typically do not attempt grouping at the story level and use predefined lists of authors. Also, noisy texts are generally not considered.</p> <h2>3 Method</h2> <p>Recall that in this article we have the goal of turning a collection of (textual) newspaper pages into a collection of (textual) articles. We follow the intuition that articles should be recoverable through coherence at multiple levels. Not only are articles semantically coherent in terms of vocabulary and names by virtue of typically covering one topic, but they are also stylistically coherent since they are typically written by one author. We operationalize this intuition by recovering articles through semantic clustering of text segments. The most straightforward type of text segment provided by historical newspapers is the individual line. However, multi-column layouts lead to very short lines which are too information poor for reliable clustering. Therefore, we adopt a two-step procedure as shown in Figure 2: We first subdivide the pages into segments (stretches of text that presumably belong to the same article). Then, we cluster segments within and across pages to assign all segments of the same article in one cluster. Text Segmentation. TextTiling (Hearst, 1997) is based on the intuition that chunks that are semantically coherent use a similar vocabulary. First the document is segmented into sentences and tokens. In the next step the lexical similarity between two neighboring blocks of b = 10 sentences is computed. TextTiling computes lexical similarities of pairs of adjacent blocks around the i -th gap, s i , as the cosine similarity between the lexical distributions of both blocks. Plotting these scores, TextTiling assumes that minima within this line indicate also segmentation boundaries. In order to find segmentation boundaries, a depth score, D i = ( s i − 1 − s i ) + ( s i +1 − s i )) , is computed and local minima are selected. Segment Clustering. Subsequently, we cluster the segments into articles. In this study, we focus on semantic similarity among segments and do not take positional information into account. We use a simple but powerful clustering method, spectral clustering (Ng et al., 2002). Spectral clustering applies k -means not to the original similarity matrix, but to a dimensionality-reduced version, increasing expressiveness and robustness of the method. Thus, we first build the matrix by computing similarity scores between all segments. Based on this matrix, we then perform the spectral clustering. Two measures of pairwise segment similarity appear particularly appropriate for OCRed, and thus noisy, texts. The traditional one is the similarity of words or character n-gram distributions, using the Jaccard coefficient. We hypothesize, that due to OCR errors, character n-grams might work better than using complete words. Thus, we compute the Jaccard coefficient on words as well as on character n-grams ( n =2– 8). A more recent approach is using the cosine similarity between 200 dimensional embeddings defined as centroids of their fastText word embeddings (Bojanowski et al., 2017). Using fastText we benefit from the functionality that embeddings can be generated from out-of-vocabulary words.</p> <h2>4 Dataset</h2> <p>To our knowledge, there is no standard dataset for article identification in historical newspapers. 3 Thus, we created such a dataset. We selected the five March 1912 issues of the New York tribune Sunday magazine 4 for annotation since this dataset contains long articles, some but not all of which are serializations that extend over multiple issues. We annotated a total of 82 pages. The annotation was performed by three annotators so that each page was annotated by two different annotators. We annotated each segment in the OCR output, marking it either as part of an article with a unique ID, or as an advertisement. The high number of short advertisements, combined with the low OCR quality due to very small and artistic typesetting, led to high disagreement on the segmentation annotations. Since our focus is on articles, we merged all advertisement blocks. The resulting annotation achieves a Cohen’s (Cohen, 1960) kappa score of κ = 0.85, (”almost perfect” agreement). Subsequently, we manually checked the disagreements and merged the annotations. 5 In the following experiments, we consider either all pages of one issue (B Y I SSUE setting), or all pages of all issues (A LL I SSUES setting). The B Y I SSUE dataset contains an average of 37 gold segments corresponding to 12.6 articles. The A L L I SSUES dataset consists of 53 different articles split among 185 gold segments — i.e., we have an average of 3 to 4 segments per article.</p> <h2>5 Experimental Setup</h2> <p>Preprocessing. We remove all non-alphanumeric characters and transform similarities exponentially for clustering. The fastText embeddings are trained on all 1912 English-language newspapers available from Library of Congress. Design. We conduct two experiments. In the first experiment, we use our gold standard (manually annotated) segment boundaries and perform only clustering. This setup reveals the performance of the clustering method. The second experiment adopts a more realistic setting and evaluates clustering performance when using automatically predicted segments obtained by TextTiling. Evaluation. In the first experiment, only the clustering needs to be evaluated. For the evaluation, we rely on the B-cubed measure, an adaptation of the familiar IR precision/recall/F 1 measure to the clustering setup (Bagga and Baldwin, 1998). In the second experiment, we additionally evaluate automatic segmentation, for which we report precision and recall. Using this measure is motivated as when using automatic text segmentation as a preprocessing step, we prefer high recall, resulting in fine-grained segments. Due to the non-deterministic nature of the spectral clustering, we perform each clustering run 5 times and report averages.</p> <h2>6 Results 6.1 Experiment 1: Gold boundaries</h2> <p>First, we inspect the effect of computing similarity in different ways for the B Y I SSUE setting for 12 clusters, the average number of articles per issue (cf. Section 4). The results in Table 1 show that among the Jaccard-based similarities, there is an interesting tendency for relatively long n-grams to work well, with the best results for n=7. Furthermore, in contrast to our intuition that the word level would suffer from OCR errors, we see better results for words than for n-grams. The overall best results are achieved by Cosine similarity on fastText embeddings which can be understood as an optimized combination of word and character n-gram information. Next, we vary the number of clusters and retain the three best-performing similarity measures. (The analysis shown in Table 1 is robust across numbers of clusters). For the B Y I SSUE setting (see Table 2), we consider between 10 and 15 clusters. We find that Precision generally increases with increased number of clusters, while Recall decreases, as could be expected. The maximum F1 score of just above 68% is obtained for cluster sizes of 14 (fastText-based and 7-gram similarities) and 15 (word-based similarity). This corresponds closely to, and is a bit higher than, the average number of gold clusters in that dataset (viz., 12.6). Embedding-based similarity outperforms trigrambased similarity by about 2.8 points F1. In the A LL I SSUES setting, we expect to see around 53 articles and thus explore performance m C o s i n e f a s t T e x t between 50 and 55 clusters (see Table 3). The F1 scores are generally lower than for the B Y I SSUE setting, but still substantial. We find similar tendencies as before (Precision increasing and Recall decreasing with the number of clusters). However, there is more variance than in the B Y I SSUE setting, so the patterns are less clear. We achieve best performance for 7-gram-based similarity with 55 clusters, for the word-based similarity with 54 and for embedding-based similarity with 54 clusters. The best performing number of clusters is again close to, and a bit higher than, the true number of articles. Here, also the 7-gram Jaccard similarity performs better than using words and is essentially on par with the fastText embeddings. We interpret this finding as showing that long n-gram shared between segments (e.g. person names, place names, etc.) are a surprisingly good indicator of article identity, even in the face of noisy OCR output.</p> <h2>6.2 Experiment 2: Automatic boundaries</h2> <p>We first evaluate TextTiling, our automatic segmentation method (cf. Section 3) and find a low Precision (0.1168) but a comparatively high Recall (0.6602). This means that precise segmentation of the noisy, OCRed historical texts is challenging indeed: TextTiling over-segments the texts. This happens, for example, when parts of a page “look different” in a scan (e.g. due to folds) and OCR introduces systematically different errors. We still prefer overto under-segmentation, since overB-Cubed segmented articles stand a chance of being recombined in the clustering step. Table 4 shows the results for article identification on automatically segmented text (we report only results for the previously best numbers of clusters). As can be expected given the segmentation results, performance drops substantially compared to Experiment 1. What is notable is the difference between the B Y I SSUE and the A LL I SSUES settings: For B Y I SSUE , performance drops moderately from 0.68 to 0.46 F1, while for A LL I SSUES we see a huge decrease from 0.55 to 0.28 F1. Similarity behaves consistently: fastText performs best for both settings, while word-based similarity yields the lowest scores.</p> <h2>6.3 Discussion</h2> <p>The results of our experiments show that processing historical newspaper is a challenging task, due to the high variance of the OCR quality. Sometimes, pages are hardly readable (cf. Figure 1); on other pages, the quality varies greatly among sections. We further investigated the impact of OCR quality by annotating each page with an OCR quality indicator on a four-point Likert scale (-1: unusable, 0: bad, 1: medium, 2: good), averaging over two annotators. Then, we repeated the B Y I SSUE setting of Exp. 1 with 14 clusters, including only pages with a quality at or above different thesholds. Table 5 shows the results. Even though performance might be expected to decrease for filtered datasets since the fixed number of clusters becomes less appropriate, it mostly remains similar (0.0) and improves using a threshold of 0.5. 6 This shows that OCR is indeed a leading source of problems.</p> <h2>7 Conclusion</h2> <p>This paper has introduced a new dataset for the text segmentation and identification of articles in historical newspapers with OCR-induced noise. We have shown results for two tasks: a) article segmentation and b) article clustering. Overall, results are promising for clustering based on gold standard segmentation, but degrade significantly when segmentation is performed automatically. This indicates manual segmentation, which involves much less effort than OCR postcorrection, is a worthy target when some manual annotation resources are available. Arguably, segmentation can also be improved further by the inclusion of visual features (Meier et al., 2017), which appears a promising direction for future research.</p> <h2>Acknowledgments</h2> <p>This study was supported by the DFG grant Oceanic Exchanges (KO 5362/2-1) and the CRETA center funded by the German Ministry for Education and Research (BMBF).</p> <h2>References</h2>

This article focuses on the problem of identifying articles and recovering their text from within and across newspaper pages when OCR just delivers one text file per page. We frame the task as a segmentation plus clustering step. Our results on a sample of 1912 New York Tribune magazine shows that performing the clustering based on similarities computed with word embeddings outperforms a similarity measure based on character n-grams and words. Furthermore, the automatic segmentation based on the text results in low scores, due to the low quality of some OCRed documents.

Publication:

Clustering-Based Article Identification in Historical Newspapers

Related Fields of Study

Citations

References