1 In this paper, we present a framework for topic detection in news articles. The framework receives as input the results retrieved from a query-based search and clusters them by topic. To this end, the recently introduced “DBSCAN-Martingale” method for automatically estimating the number of topics and the well-established Latent Dirichlet Allocation topic modelling approach for the assignment of news articles into topics of interest, are utilized. Furthermore, the proposed query-based topic detection framework works on high-level textual features (such as concepts and named entities) that are extracted from news articles. Our topic detection approach is tackled as a text clustering task, without knowing the number of clusters and compares favorably to several text clustering approaches, in a public dataset of retrieved results, with respect to four representative queries.
The need by both journalists and media monitoring companies to
master large amounts of news articles produced on a daily basis, in
order to identify and detect interesting topics and events, has
highlighted the importance of the topic detection task. In general,
topic detection aims at grouping together stories-documents that
discuss about the same topic-event. Formally, a topic is defined in
[
The two main challenges involved in the topic detection problem are the following: one needs to (1) estimate the correct number of topics/news clusters and (2) assign the most similar news articles into clusters. In addition, the following assumptions must be made: Firstly, real data is highly noisy and the number of clusters is not known a priori. Secondly, there is a lower bound for the minimum number of documents per news cluster.
In this context, we present and describe the hybrid clustering
framework for topic detection, which has been developed within
the FP7 MULTISENSOR project2. For a given query-based search,
the main idea is to efficiently cluster the retrieved results, without
the need for a pre-specified number of topics. To this end, the
framework, recently introduced in [
The rest of the paper is organized as follows: Section 2 provides
related work with respect to topic detection, news clustering and
density-based clustering. In Section 3, our framework for topic
detection is presented and described. Section 4 discusses the
experimental results from the application of our framework and
several other clustering methods to four collections of text
documents, related to four given queries, respectively. Finally,
some concluding remarks are provided in Section 5.
2
Topic detection is traditionally considered as a clustering problem
[
Graph-based methods for event detection and multimodal
clustering in social media streams have appeared in [
Density-based clustering does not require as input the number of
topics. OPTICS [
The MULTISENSOR framework for topic detection, which is presented in Figure 1, is approached as a news clustering problem, where the number of topics needs to be estimated. The overall framework is based on textual features, namely concepts and named entities. The number of topics k is estimated by DBSCANMartingale and the assignment of news articles to topics is done using Latent Dirichlet Allocation (LDA).
LDA has shown great performance in text clustering, given the
number of topics. However, in realistic applications, the number of
topics is unknown to the system. On the other hand, DBSCAN
does not require as input the number of clusters, but its
performance in text clustering is very weak, due to the fact that it
assigns too much noise to the news article collection and this
results in very limited performance [
In our approach, the constructed DBSCAN-Martingale combines several density levels and is applied on high-level concepts and named entities. In the following, the construction of DBSCAN-Martingale is briefly reported. 3.1
Given a collection of news articles, density-based clustering
algorithms output clustering vector with values the cluster IDs
[ ] for each news item = 1,2, … , , where we denote by [ ]
the -th element of a vector . In case the -th document is not
assigned to any of the clusters, the -th cluster ID is zero.
Assuming that ( ) is the clustering vector provided by the
DBSCAN [
The DBSCAN-Martingale progressively updates the estimation of the number of clusters (topics), as shown in Figure 2, where 3 topics are detected in 2 iterations of the process. Due to the randomness in the selection of the density levels , it is likely that each realization of the DBSCAN-Martingale will output a random variable ̂as an estimation of the number of clusters. Hence, we allow 10 realizations ̂1, ̂2, … , ̂10 and the final estimation of the number of clusters is the majority vote over them. An illustrative example of 5 clusters in the 2-dimensional plane is demonstrated in Figure 3.
In brief, the DBSCAN-Martingale is mathematically formulated as follows. Firstly, a sample of size , = 1,2, … , is randomly generated in [0, ], where is an upper bound for the density levels. The sample of , = 1,2, … , is then sorted in increasing order. For each density level we find the corresponding clustering vectors ( ) for all stages = 1,2, … , . In the first stage, all clusters detected by ( 1) are kept, corresponding to the lowest density level 1. In the second stage ( = 2), some of the detected clusters by ( 2) are new and some of them have also been detected by ( 1). In order to keep only the newly detected clusters, we keep only groups of numbers of the same cluster ID with size greater than s. Finally, the cluster IDs are relabelled and the maximum value of a clustering vector provides the number of clusters.
Complexity: The DBSCAN-Martingale requires iterations of the
DBSCAN algorithm, which runs in ( log ) if a tree-based
spatial index can be used and in ( 2) without tree-based spatial
indexing [
LDA assumes a Bag-of-Words (BoW) representation of the collection of documents and each topic is a distribution over terms in a fixed vocabulary. LDA assigns probabilities to words and assumes that documents exhibit multiple topics, in order to assign a probability distribution on the set of documents. Finally, LDA assumes that the order of words does not matter and, therefore, LDA is not applicable to word -grams for ≥ 2, but can be applied to named entities and concepts. This input allows topic detection even in multilingual corpora, where -grams are not available in a common language. 4 4.1
In this Section, we describe our dataset and evaluate our method. A part of the present MULTISENSOR database (in which articles crawled from international news websites are stored) was used for the evaluation of our query-based topic detection framework. We use the retrieved results for a given query in order to cluster them into labelled clusters (topics) without knowing the number of clusters. The concepts and named entities are extracted using the DBpedia spotlight6 online tool and the final concepts and named entities replaced the raw text of each news article. The final collection of text documents is available online7.
The queries that were used for the experiments are the following: energy crisis 3 https://github.com/MKLab-ITI/topic-detection 4 https://www.r-project.org/ 5 https://cran.r-project.org/web/packages/dbscan/index.html 6 https://dbpedia-spotlight.github.io/demo/ 7 http://mklab2.iti.gr/project/query-based-topic-detection-dataset energy policy home appliances solar energy
It should be noted that the aforementioned queries are considered representative, with respect to the use cases addressed by the MULTISENSOR project. The output of our topic detection framework can be visualized in Figure 4 for the query “home appliances”, where the retrieved results are clustered by 9 topics. The font size of the clusters’ labels depends on the particular word probability within each cluster. 4.2
In order to evaluate the clustering of the retrieved news articles, we use the average precision (AP), broadly used in the context of information retrieval, clustering and classification. A document of a cluster is considered relevant to (true positive), if at least one concept associated with document appears also in the label of cluster . It should be noted that the labels of the clusters (topics) are provided by the concepts or named entities that have the highest probability (provided by LDA) within each topic. Precision is considered the fraction of relevant documents in a cluster and average precision is the average for all clusters of a query. Finally, we average the AP scores for all considered queries to obtain the Mean Average Precision (MAP).
We compared the clustering performance of the proposed topic
detection framework, in which the DBSCAN-Martingale algorithm
(for estimating the number of topics) and LDA (for assigning news
articles to topics) are employed, against a variety of well-known
clustering approaches, which were also combined with LDA for a
fair comparison. DP-means is a Dirichlet process and we used its
implementation in R8. HDBSCAN is a hierarchical DBSCAN
approach, which uses the “excess-of-mass” (EOM) approach to
find the optimal cut. Nbclust is a majority vote of the first 16
indices, which are all described in detail in [
The AP scores per query and the MAP scores per method over 10 runs of LDA are displayed in Table 1, for each estimation of the number of topics combined with LDA. In addition, the numbers of news clusters estimated by the considered clustering indices for each query are presented in Table 2. Looking at Table 1, we observe a relative increase of 9.65% in MAP, when our topic detection framework is compared to the second highest MAP score (by Hartigan+LDA) and a relative increase of 10.20%, when compared to the most recent approach (NbClust+LDA).
In general, the proposed topic detection framework outperforms all the considered clustering approaches both in terms of AP (within each query) and in terms of MAP (overall performance for all queries), with the exception of the “energy policy” query, where the performance of our framework is matched by that of the Duda and Pseudo t^2 clustering indices.
Finally, we evaluated the time performance of the DBSCANMartingale method and we selected several baseline approaches in order to compare their processing time with that of our approach. In Figure 5, the number of news clusters is estimated for T = 5 iterations for the DBSCAN-Martingale and for maximum number of clusters set to 15 for the indices Duda, Pseudo t^2, Silhouette, Dunn and SDindex. We observe that DBSCAN-Martingale is faster than all other methods. Even when it is applied to 500 documents, it is able to reach a decision about the number of clusters in approximately 0.4 seconds. 5
In this paper, we have presented a hybrid topic detection framework, developed for the purposes of the MULTISENSOR project. Given a query-based search, the framework clusters the retrieved results by topic, without the need to know the number of topics a priori. The framework employs the recently introduced DBSCAN-Martingale method for efficiently estimating the number of news clusters, coupled with Latent Dirichlet Allocation for assigning the news articles to topics. Our topic detection framework relies on high-level textual features that are extracted from the news articles, namely textual concepts and named entities. In addition, it is multimodal, since it fuses more than one sources of information from the same multimedia object. The query-based topic detection experiments have shown that our framework outperforms several well-known clustering methods, both in terms of Average Precision and Mean Average Precision. A direct comparison, by means of time performance, has shown that our approach is faster than several well-performing methods in the estimation of the number of clusters, given as input the same number of query-based retrieved news articles.
As future work, we plan to investigate the behavior of our framework by introducing additional modalities/features, examine the application of alternative (other than LDA) text clustering approaches, as well as investigate the extraction of languageagnostic concepts and named entities, something that could provide multilingual capabilities to our topic detection framework.
This work was supported by the projects MULTISENSOR (FP7610411) and KRISTINA (H2020-645012), funded by the European Commission.