The abundance of news being generated on a daily basis has made it hard, if not impossible, to monitor all news developments. Thus, there is an increasing need for accurate tools that can organize the news for easier exploration. Typically, this means clustering the news stream, and then connecting the clusters into story lines. Here, we focus on the clustering step, using a local topic graph and a community detection algorithm. Traditionally, news clustering was done using sparse vector representations with TF{IDF weighting, but more recently dense representations have emerged as a popular alternative. Here, we compare these two representations, as well as combinations thereof. The evaluation results on a standard dataset show a sizeable improvement over the state of the art both for the standard F1 as well as for a BCubed version thereof, which we argue is more suitable for the task.
The rest of this paper is organized as follows: Section 2 gives a brief overview of relevant previous work. Section 3 describes the core system based on newsLens and the di erent representations for the news articles. Section 4 presents our experiments and discusses the evaluation results. Finally, Section 5 concludes and points to possible directions for future work. 2
The Topic Detection and Tracking (TDT) task aims to help search and organize news-oriented textual material from a variety of broadcast news media. In particular, it asks to cluster news into topics, which are commonly called stories. Below, we describe three systems that are closely related to our work here.
Laban and Hearst [LH17] proposed newsLens, a system for organizing a large dataset of news articles into a collection of major stories. Their topic detection algorithm creates local clusters based on keywords extracted from the articles. The system further visualizes the story timelines, showing important information about the story. However, the performance of their algorithm was not formally evaluated, and here we ll this gap by testing our reimplementation thereof on a standard benchmark dataset.
Miranda et al. [MZCB18] focused on clustering a stream of news articles in English, Spanish and German. They used vector representation for the articles and built clusters by maintaining two types of centroid functions for each monolingual cluster. For their experiments, they adapted a dataset from [RML+16], and they processed it to turn it into a collection of articles annotated with monolingual and cross-lingual cluster labels, where story clusters are about particular events. They evaluated their model on the test part of their dataset. We use the English partition of the dataset and we compare our results against theirs.
Barron-Ceden~o et al. [BMZ+18] generated short video overviews describing the coverage of the same event by di erent news outlets automatically. Four modules were involved in the video production: event identi cation, de-duplication, coverage diversi cation, and image gathering. The end user was provided with illustrated videos aiming to present di erent viewpoints for the coverage of the same event. Unlike the above work, their clustering algorithm represents the individual news articles using doc2vec embeddings [LM14]. 3
We re-implemented, to the best of our ability, the relevant core modules of the newsLens system [LH17], and we consider this reimplementation as our baseline.
The pipeline of newsLens has several stages: (i ) extracting keywords from the articles, (ii ) identifying local topics (clusters), and (iii ) merging long-term topics to give rise to stories. Each document is represented as a bag-of-words vector and weighted with TF{IDF. A word wi is selected as a keyword for document dj if its TF{IDF score is higher than a manually set threshold T0nl, where the superscript nl stands for newsLens. Two articles are included in the same topic if they share several keywords and have close dates of publication. The articles are grouped into common local topics by building a graph. Articles (ai, aj ) are linked by an edge in the graph if they have su cient overlap in keywords: jkwi \ kwj j T1, where T1nl is another manually-set threshold. The local topics graph is further re ned using a community detection algorithm, following the Louvain method [BGLL08]. After the local topics have been created, a topic-matching process is used for stories that might be interrupted in time. Two topics are merged into a story if they do not overlap in time, but are similar in terms of keyword distribution. Each topic is represented by a vector v(ti) for topic ti, which contains the number of keywords in all articles about topic ti. The similarity between a new and an old topic is computed using cosine. If it is above a threshold T2nl, the topics are merged.
In our algorithm, we consider only the modules for identi cation of local topics and for matching long-term topics, which we enhance as described below. 3.1
Identi cation of Local Topics The local topics clustering module is responsible for creating the preliminary clusters of news articles. Its input consists of overlapping windows, each spanning n consecutive days. The outcome is a graph G = (V; E) where V is the set of vertices |the news articles| and E is the set of edges. An edge between two articles fdi; dj g 2 V exists only if sim(di; dj ) T1, where sim is the cosine similarity computed over representations of the articles and T1 is an empirically set threshold. We explore both sparse and dense vectorial representations.
For the sparse representation, we compute TF{IDF vectors. The preprocessing in this case consists of casefolding, lemmatization1, punctuation removal, and stopwording. For the latter, we use a pre-de ned list [SDK10] and we combine it with a list of the words with a document frequency higher than 85% in the training set. We consider di erent parts of the documents to build the vectors: (i) the titles, (ii) the bodies, (iii) and both.
For the dense representation, we compute 300-dimensional doc2vec vectors [LM14], which we train on the Signal Media One-million news articles corpus [CAMM16], which contains 265,512 blog articles and 734,488 news articles from 93k unique sources over a period of one month. We use the same preprocessing as before.
We merged the sequence of overlapping local graphs in the order of their creation. Following [LH17], in order to avoid merging topics that are loosely connected, we further re ned the topics graph structure using a community detection algorithm: the Louvain method [BGLL08]. Due to the comparison of the similarities in a spanning window, it is possible for di erent densely connected topics to connect erroneously. The role of the community detection algorithm is to nd the correct assignment of the nodes into communities. It detects communities in networks using a heuristic that maximizes the modularity of the obtained communities. The modularity of a partition is a scalar value between 1 and 1 that measures the density of links inside communities as compared to links between communities [BGLL08]. 3.3
Matching Long-Term Topics The input to this module are the clusters generated across the di erent n-day windows from the previous module. The objective now is to identify long-term stories that might have been interrupted for a period of time. Two local topics coming from non-overlapping windows are merged if the cosine similarity sim(ti; tj ) T2, where ti (tj ) is the mean of all vectors belonging to topic i (j) and T2 is an empirically set threshold. 4
In this section, we describe the dataset, the evaluation measure, the experimental setup, and the evaluation results. 4.1
Dataset For our experiments, we use the corpus from [MZCB18]. It is a collection of 33,807 news articles with streaming clusters identi ed across three languages: English, Spanish, and German. We use the English part, which contains 20,959 documents, and the original training{test split. Table 1 reports some statistics about this dataset. The training partition includes articles in the time interval from December 18, 2013 to February 2, 2014, while the articles in the test set come between November 2, 2014 and August 25, 2015. Whereas in the training partition there are numerous gaps with an average of three days without an article, in the test partition the gaps can be as long as 3 months. This is an important factor to take into account when trying to identify long-term topics. 4.2
Evaluation For evaluating our models, we use the BCubed versions of precision, recall and F1-measure [AGAV09]. BCubed measures favor solutions that (i ) split a cluster that mixes two categories into two pure clusters (cluster homogeneity), (ii ) unify two clusters that contain only items from the same category (cluster completeness), (iii ) add an item of a di erent category to an already noisy cluster instead of a pure one, and (iv ) make small errors in a big cluster rather than a large number of small errors in small clusters.
The BCubed measures are de ned as follows. Let Li be the category of document i and Ci be the cluster of document i. The relation correctness between documents i and j is calculated as follows:
Correctness(i; j) = (1, if Li = Lj and Ci = Cj
0, Otherwise
The BCubed precision of a document is the proportion of documents in its cluster that belong to the same category, including itself. The BCubed recall of a document is the proportion of documents belonging to the same category that appear in its cluster. The overall BCubed precision and recall are computed as follows: (1) (2) (3) (4) BCubed P = Avgi[Avgi:Ci=Cj [Correctness(i; j)]]
BCubed R = Avgi[Avgi:Li=Lj [Correctness(i; j)]] Additionally to these measures, we also report the standard versions of precision and recall:2 P =
tp tp + f p
R =
tp tp + f n where tp, f p, and f n stand for true positives, false positives, and false negatives, respectively.
Both the BCubed and the standard F1-measure are computed as the harmonic mean of precision and recall: F1 = 2
P R P + R
BCubed F1 = 2
BCubed P BCubed R BCubed P + BCubed R 4.3
Experimental Setup We tuned the hyper-parameters of our model using a temporal 4-fold cross-validation on the training set. We used grid search optimizing for F1, exploring n = [4; 5; 6] for the size of the sliding window, and T1 2 f0:10; 0:11; : : : ; 0:50g and T2 2 f0:60; 0:61; : : : ; 0:90g for the thresholds. We found di erent values for T1 for the di erent experiments, due to the di erent models for identi cation of local topics; yet, we always obtained the same values for n = 6, T2 = 0:8 and 50% window overlap, as best performing in the preliminary tests. 4.4
Results
The last two rows of Table 2 show the results of the experiments using logistic regression with TF{IDF similarity alone and in combination with doc2vec similarity as input. The supervised model TF{IDF & doc2vec shows an improvement of over 0.7 points absolute in terms of BCubed F1-measure over the standard approach (93.67 vs. 92.97). This model is the one that generates the least clusters, a number that is also closer to the actual number to be found. On the other hand, the experiment with supervised TF{IDF achieved worse BCubed F1 = 94.30, comparing to the unsupervised BCubed F1 = 94.41.
Finally, in order to investigate the impact of the Louvain community detection algorithm, Table 3 shows the results of applying it on the TF{IDF model in two ways: (i ) before and (ii ) after merging two local topics graphs (cf. end of Section 3.1). We can see that the latter works better; we observed similar results for most of our models. We have presented an algorithm for clustering news streams, which is an improved version of a previously proposed general framework. We further compared sparse vector representations with TF{IDF weighting vs. doc2vec-based dense representations, as well as combinations thereof. The evaluation results on a standard dataset have shown sizable improvements over the state of the art both for the standard F1 score as well as for a BCubed version thereof, which we argue is more suitable for the task.
In future work, we plan to improve the process of topic matching. This would require us to build a dataset with news stories that seemingly die, but then reemerge with large gaps in time. [CAMM16] David Corney, Dyaa Albakour, Miguel Martinez, and Samir Moussa. What do a million news articles look like? In Proceedings of the First International Workshop on Recent Trends in News Information Retrieval, pages 42{47, Padua, Italy, 2016. [HKMA16] Kazuma Hashimoto, Georgios Kontonatsios, Makoto Miwa, and Sophia Ananiadou. Topic detection using paragraph vectors to support active learning in systematic reviews. Journal of Biomedical Informatics, 62, 06 2016. [LH17] Philippe Laban and Marti Hearst. newsLens: Building and visualizing long-ranging news stories. In Proceedings of the Events and Stories in the News Workshop, pages 1{9, Vancouver, Canada, 2017. [LM14] Quoc Le and Tomas Mikolov. Distributed representations of sentences and documents. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of ICML '14, pages 1188{1196, Bejing, China, 2014. [MZCB18] Sebasti~ao Miranda, Arturs Znotins, Shay B. Cohen, and Guntis Barzdins. Multilingual clustering of streaming news. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, EMNLP '18, pages 4535{4544, Brussels, Belgium, 2018. [RML+16] Jan Rupnik, Andrej Muhic, Gregor Leban, Primoz Skraba, Blaz Fortuna, and Marko Grobelnik. News across languages - cross-lingual document similarity and event tracking. J. Artif. Intell. Res., 55:283{316, 2016. [SDK10] Benjamin Stone, Simon Dennis, and Peter J. Kwantes. Comparing methods for single paragraph similarity analysis. Topics in Cognitive Science, 3:92{122, 2010.