The paper discusses the developing of information system for analysis and aggregation of news from news servers and social resources. The basic purpose of the system is to provide relevantly aggregated news information for the user. The paper reviewed the used techniques for gathering and storing of news information. The paper discusses the used methods for news processing such as news online clustering and news sentiment analysis. The architecture and implementation principles of developed system are given.
The job of journalists and editors is to react as quickly as possible to hot news, so they have to examine a lot of publications that appear on the Internet in a short time. Moreover, each event can be covered in many articles and publications, and therefore the amount of data becomes su ciently large. In addition to the news, there are also social networks where users can express their attitude to certain news, discuss events, come to their \own" conclusion and so on. All this information (news items, articles, social posts) should be read, compared and analyzed by the editors of many news agencies. However, often the editor can't process the whole data stream, so we need to provide a short description of these news, various additional information, using which editor would be able to assess if it can be valuable and interesting, and also to tie discussions in social networks to the news, to provide maximum information, bring various statistical data about the social posts and much more.
To solve these problems, we have developed the information system that is discussed in details in this paper.
The article [
The designed system should consist of several independent modules, each of which must solve its own task. Among these tasks, we can distinguish: collecting and storing data, news clustering, selecting text attributes and its characteristics, aggregation of data for the same information event and providing information in a format convenient for the editor.
Thus, it is possible to divide the system into three main subsystems: a collection subsystem, a subsystem for executing text processing tasks and a subsystem for displaying information. The high-level system structure is represented at Fig. 1. The work ow of this subsystem is represented in the diagram in Fig. 2.
All collected data from the Web (news articles and social posts and comments) are stored inside document-oriented database MongoDB. After being collected, news are transferred to the queue for the processing subsystem using RabbitMQ as a messaging broker, where task routing is used to de ne the type of processing for each individual news article.
The word processing system consists of several subsystems, each of which performs its own task. However, all subsystems operate on a common principle.
When the news is received, a task is formed to analyze this news in all the subsystems, but, formally, three tasks are created: the task for clustering, the task for determining the emotional coloring of social posts, and the selection of keywords.
All tasks are resource-intensive, therefore, it is necessary to ensure maximum concurrency in the implementation of all phases in order to reduce the average waiting time for news processing. In production there is a requirement to process not less than 20,000 news per day. So the news processing time must be less than 5 seconds.
To accommodate all these requirements, the processing subsystem architecture, displayed in the Fig. 3 was developed. Each worker processes the news and adds the meta information to the database
The diagram shows three task queues that are responsible for their own processing types. Tasks then processed by their corresponding handlers.
Due to the fact that task for sentiment analysis is quite resource intensive in terms of using the CPU during training and using RAM both during training and operation of the trained model it was decided to perform a sentiment analysis of text in a separate microservice where the necessary models were placed in memory, and the interaction of workers with this microservice is carried out through the HTTP API.
In addition to processing each news, it is necessary to identify the aggregated characteristics of the cluster. For this purpose, an aggregator is added to the scheme. Its task is to get updated news clusters and aggregate the characteristics of cluster's elements. Processed clusters are displayed in the editor's interface. 3
In this paper, we will discuss system from two levels point of view. The higher level is a structure description layer using metagraph approach and the lower level is an implementation layer.
According to paper [
The metagraph is described as follows: M G = hV; M V; Ei; where MG { metagraph; V { set of metagraph vertices; MV { set of metagraph metavertices; E { set of metagraph edges.
Metagraph vertex vi = fatrkg; vi 2 V , where atrk { attribute. Metagraph edge ei = hvS ; vE ; fatrkgi; ei 2 E, where vS { source vertex (metavertex) of the edge; vE { destination vertex (metavertex) of the edge; atrk { attribute.
The metagraph fragment is de ned as M Gi = fevj g; evj 2 (V [ E [ M V ), where evj { an element that belongs to union of vertices, edges and metavertices. The metagraph metavertex: mvi = hfatrkg; M Gf i; mvi 2 M V , where mvi { metagraph metavertex; atrk { attribute, M Gf { metagraph fragment.
The metagraph itself is not more than a complex data structure. To process and transform metagraph data the metagraph agents are used. There are two kinds of metagraph agents: the metagraph function agent agF and the metagraph rule agent agR.
The metagraph function agent serves as a function with input and output parameter in form of metagraph: agF = hM GIN ; M GOUT ; AST i; where agF { metagraph function agent; M GIN { input parameter metagraph; M GOUT { output parameter metagraph; AST { abstract syntax tree of metagraph function agent in form of metagraph.
The metagraph rule agent uses rule-based approach: agR = hM G; R; AGST i; R = frig; ri : M Gj ! OP MG; where agR { metagraph rule agent; M G { working metagraph, a metagraph on the basis of which the rules of agent are performed; R { set of rules ri; AGST { start condition (metagraph fragment for start rule check or start rule); M Gj { a metagraph fragment on the basis of which the rule is performed; OP MG { set of actions performed on metagraph.
The distinguishing feature of metagraph agent is its homoiconicity which means that it can be data structure for itself.
Thus, metagraph approach is a good basis for complex graph structures and their transformations representation. Now we can describe the elements of architecture of modules of proposed system in terms of metagraph approach. 4 4.1
The metagraph representation of clustering module is given at Fig. 4
The clustering module may be implemented as a metagraph rule agent which generates the output metagraph M G. The news text messages ti are transformed into metagraph vertices vi, which may be annotated with attributes (source text message, auxiliary clustering metrics).
The output metagraph M G contains a set of metavertices-clusters M V C = fM V Ckg. Each metavertex-cluster contains earlier clustered vertices-messages v1, v2, . . . vn. Depending on used clustering algorithm vertices-messages may be connected with necessary edges e1, e2, . . . en.
Clustering metagraph rule agent may add new metavertex-cluster M V Ck+1 and then add new vertex-message vi to this cluster. For new vertex-message vi necessary edges inside the cluster may be added (edge ei is shown as an example). For new metavertex-cluster M V Ck+1 necessary edges also may be added connecting new cluster with other clusters (edge mvek+1 is shown as an example).
The rule system of clustering metagraph rule agent contains two rules. When the news text messages ti arrives then it is transformed into metagraph vertices vi. Then depending on the current state of the metagraph M G one of the two following rules are performed: 1. (M G; vi) ! Alg(M G; vi) = M V Ck; M V Ck + vi; M V Ck + feig Using clustering algorithm for new vertex vi the appropriate metavertexcluster M V Ck is selected. Then new vertex vi with necessary edges feig are adding to selected cluster. 2. (M G; vi) ! Alg(M G; vi) = ; M G+M V Ck+1; M G+fmvek+1g; M V Ck+1+ vi; M V Ck+1 + feig If appropriate metavertex-cluster cannot be selected then new metavertexcluster M V Ck+1 and set of necessary edges fmvek+1g are adding to metagraph. Then new vertex vi with necessary edges feig are adding to new cluster.
The clustered metagraph structure may be considered as a basis for next stages of text processing. It may be transformed with other metagraph agents. 4.2
The detailed algorithm Alg for news clustering module may be represented as follows: 1. Initializing an empty set of clusters. 2. For each news: 2.1. Preprocess text. Split the text into words, delete punctuation (commas, dots, colons, etc.), remove stop words (prepositions, conjunctions, interjections), put the word into the normal form, for example, in the in nitive for the verb, in the masculine singular for nouns and adjectives. 2.2. Increase the count of scanned news. 2.3. Increase the count of number of all words included in the text of the news. 2.4. Calculate minhash from the news and add it to the index. 2.5. Determine the most similar news using the LSH procedure. 2.6. For each news: 2.6.1. Create a pair of news from step 2 and step 2.6. 2.6.2. De ne WMD between the rst and second news from the pair. 2.6.3. De ne the vector TF-IDF of the rst and second news. 2.6.4. Determine the cosine of the angle between the vectors obtained in the previous step. 2.6.5. Find the arithmetic mean between WMD and the cosine metric obtained in the previous step. Consider this number as the distance between the news. 2.7. Find the minimum distance between processed news and all similar news. 2.8. If this distance is less than speci ed threshold, add the news to the cluster that contains the news with the shortest distance, otherwise create a new cluster with the current news article.
The algorithm doesn't need any additional data for preprocessing or training
to perform news clustering in the streaming mode. In this case, setting the
number of clusters is not necessary, the algorithm splits the entire set of texts
into clusters, depending on the threshold parameter de ned in step 2.8 of the
algorithm. The speed required in this task is achieved by using the LSH technique
to approximate the distance between news articles. This technique is described
in details in [
In other words, the algorithm assigns a new element of the stream to the closest cluster.
Let's review some algorithms steps in more detail. In clause 2.6.3. texts
represented as vectors of TF-IDF coe cients of their words. This measure is based
on the frequency of occurrence of a term (word or literal) in the text and in
the entire set of texts. Use of this for the task of determining the relevance of a
document to a query is described in the article [
Practically, any other metric can be used, but experiments show that the best option is the conversion of texts into TF-IDF vectors.
During the experiments, optimal thresholds were chosen, under which the quality of the algorithm was maximal. Of course, theese thresholds are optimal for the test set of data. In the ideal case, the threshold should vary depending on the amount and nature of the data in the system. For test data we took and manually marked clusters of news articles and posts in social networks. Quality was assessed using the F1 metric.
To calculate the F1-score, we need to determine the number of False / True Positive / Negative examples. However, in the case of clustering, it is di cult to determine the method for obtaining the values of FP, FN, TP, and TN, since the number of clusters is unknown in advance and it is impossible to determine the correspondence between the resulting cluster and the cluster from the initial set.
Therefore, it is possible to break all the initial data into a set of all possible
pairs of texts belonging to the same cluster. In the same way, we will split the
resulting set of clusters, as described in [
As a result, there are two sets of pairs, where each pair is represented by two texts referring to the same cluster. We denote the pairs obtained from the original set as G, and the pairs from the resulting set as C, so: T P = jG \ Cj, F P = jC n Gj, F N = jG n Cj, F 1 = 2 T P2+FT NP+F P .
Figure 5 shows that the F1-score was near 0.78 when using the Jaccard metric against approx. 0.82 when using TF-IDF weighting texts on the same dataset.
This approach works well, since it takes into account the frequency of words in the texts, but this is a purely statistical approach.
To take into account the semantic component, step 2.6.2 was added to the
algorithm. At this step, the measure of the distance WMD (Word Mover's
Distance) between the titles of news is estimated. WMD is an extension of the EMD
task for texts and described in details in [
The gure 5c shows the results of using WMD.
Since counting WMD of large texts takes a long time, it was decided to evaluate WMD using the news titles. At the same time, the quality of clustering was improved, F1-score for the variant with WMD for the title and TF-IDF for the text was improved by 6%.
With the increase in the number of news, the processing time of one news is increasing, as it is required to compare a new element with an increasing number of already existing elements. To stabilize the time of one iteration, steps 2.4 and 2.5 were added to the algorithm. (sau)re Jaccard distance mea-(cbos)inTeFd-IisDtaFncveecmtoeraizsuinrge and (rTceF)su-CIltDosmFwpahanerdnisoounnslioynfgTcWlFu-sMItDeDrFin+g
In these steps, the LSH method is implemented, which allows to approximate the distance measure with the MinHashing operation.
The gure 6 shows a comparison of the processing time of one news using LSH and without it depending on the iteration number.
(a) Iteration time without LSH (b) Iteration time with LSH
The iteration time without using LSH grows with each iteration, while on the second gure the time is much less (approx. 0.25s) and does not grow, that is, stable. This is extremely important in the system, since the iteration time directly a ects the speed of news appearance in the editor's interface. 5
Keywords combinations are extremely important for the editor, as they allow to understand quickly the essence of news articles without reading the whole text.
First, the POS-tagging of the text is performed, that is, for each word the most likely part of the speech is exposed. After this, using the regular expressions by parts of the speech, the necessary word combinations are selected. For example, \adjective + preposition + noun" or \adjective + noun". For the news, regular expressions like \preposition + noun" and \number + noun" are also important, since they allow to identify phrases like \in Moscow", \June 21", etc.
However, it is not enough just to select word combinations for all news, it is important to de ne them for the news cluster, for one information event, so aggregation is also applied for this task.
To solve this problem, the following algorithm is used in the aggregation module: 1. For each news and its phrases we create a \normalized" set of word combinations: each word in each phrase is put into its normal form. 2. For the entire news cluster, the frequencies of normalized word combinations are calculated and sorted in descending order. 3. 10 most common normalized word combinations are taken. 4. Normalized word combinations are converted to the original ones.
Therefore, for each cluster a set of the most popular word combinations is formed. Normalization in step 1 required because phrases that di er only in the case or conjugation of individual words should be considered as one word combination.
Additionally, the NER task (highlighting named entities) can be set, since the news often refers to the classical entities of this task (geographic locations, persons, corporations). 6
Sentiment analysis in the news analysis system is a core component that helps a reporter to better understand opinion of people about a speci c news article throughout the social networks. The clustering algorithm discussed earlier is used to combine social content with the corresponding news. When the clustering nished sentiment analysis of each individual social post happens providing the reporter with a feedback about people's opinion in the Internet to better analyze news and events. Various aggregated statistics can be built to understand areal, demographic or other distributions of users' attitude to speci c events. 6.1
The metagraph representation of sentiment analysis module is given at Fig. 7.
The stage I is entities detection. The result of stage I is a metagraph containing entities-metavertices (the only metavertex M E is represented at Fig. 7) with included entities-vertices E1 . . . EN .
The stage II is opinion target expression. After stage II the sentences related to entities are detected. The Fig. 7 shows metavertex SE containing sentences. Metavertices M E and SE and their inner vertices are connected with corresponding edges.
The stage III is polarity detection. After stage III all entities are connected with corresponding polarities. Polarities are shown as metavertex P containing three vertices-polarities: positive (+), negative (-) and neutral (?). In our implementation, the neutral polarity is not used.
The task of sentiment analysis can be formulated as a problem of binary classi cation of text (using positive and negative polarities). As input, such classi er is supplied with a set of texts T = fT 1; T 2; : : : ; T ng, at the output there is a label (1 or 0) assigned to a positive or negative text. The binary mark in practice is replaced by the probability that the text is positive.
For training and testing models we used two common datasets: IMDB Large
Movie Database [
Two main approaches used in this system will be considered: the SVM-based approach and the convolutional neural network approach. Before model training and predicting new values, we need to preprocess the data and present it in a form that is convenient for the model. All texts passed through preprocessing | clearing of unnecessary data, bringing words to normal form, dividing into words, etc.
The next step is to words vectorization, i.e. encode text data to numeric. This
operation can be performed in di erent ways, but the most e cient is
transformation of words into a certain linear space in which the semantic proximity of
words can be expressed in the distance (cosine or Cartesian) between the
vectors representing the given words. At the moment there are two popular word
vectorizing algorithms | Word2Vec [
Let's now consider each of the models for sentiment analysis separately.
6.2.1 SVM Support Vector Machine (SVM) is a linear method of classi
cation, the main principle is to maximize the \margin" between objects of di erent
classes. It is a very popular model for solving natural language processing tasks
[
Two methods of encoding text data were considered: TF-IDF for texts, and also average vectors of Word2Vec (both GloVe and Google Word2Vec). In addition, we searched for the best free hyperparameter C of the function that is optimized during SVM learning procedure: 8< 21 kwk2 + C Pn
i=1 i ! minw;b; i ci(w xi b) 1 i; 1 i : i 0; 1 i n n
C is responsible for how it's permissible to algorithm to make mistakes in learning, i.e. how wide or narrow should be the gap between classes. The larger the value of C, the smaller the gap, and vice versa. The table 1 shows the results of the experiments.
The best quality was shown by the algorithm with C = 0:196 with the result
of 0.89 on the test sample for the IMDB dataset and C = 0:311 with the result
0.92 on the test sample for the SAR14 dataset.The TF-IDF vectorization of the
texts showed the best result on both datasets.
6.2.2 CNN We used model described in details in [
All the attributes are then fed to the fully connected softmax layer, where the output is the prediction of probability of tonality of text. As a regularization, Dropout layers are used, the main task of which is to leave a certain predetermined probability keep prob in the neural network or not. As the vectorization of words, we compared the pretrained Wor2Vec Google, pretrained GloVe vectors, and the vectors learned in the process of network training itself. Using crossvalidation, the optimal network structure was chosen (in terms of the size of lters and the number of them).
The graph of the model is as follows is in Fig. 8. Modeling results are shown in the table 2.
The best result was achieved on both datasets with pretrained vectors using
the con guration [
So, in the developed sentiment analysis subsystem we use an ensemble of the
described SVM and CNN models to achieve the best performance. The
comparison of results achieved in the baseline SVM model described in [
In this paper, we presented architecture and implementation principles of an intelligent news analysis system. The system consists of three main subsystems: a collection subsystem, a subsystem for executing text processing tasks and a subsystem for displaying information. The implementation of clustering module and sentiment analysis module are discussed in details. The operational principles of these modules are represented using metagraph approach. As the future work, we plan to improve the quality of implemented modules and add new modules such as aspect-based sentiment analysis module.