In this paper we present some preliminary results for text corpus visualization by means of so-called reference graphs. The nodes of this graph stand for key words or phrases extracted from the texts and the edges represent the reference relation. The node A refers to the node B if the corresponding key word / phrase B is more likely to co-occur with key word / phrase A than to occur on its own. Since reference graphs are directed graphs, we are able to use graphtheoretic algorithms for further analysis of the text corpus. The visualization technique is tested on our own Web-based corpus of Russian-language newspapers.
The main idea of any text visualisation technique is to plot important elements of the
text (such as key words or key phrases, named entities, or terms). Such pictures can
be seen as a tool for text summarization and information extraction / presentation [
Our project of text collection visualization follows to this direction. We construct socalled reference graphs, where nodes stand for key words / phrases, which are extracted from the whole collection. There is a directed edge between two nodes A and B if node A refers to node B: A =) B . The referral relation shows that the key word or phrase B occurs with a higher probability if the key word or phrase A occurs in the same text and B is more likely to occur in a document where A is present than its expected value over the entire corpus indicates. We use an asymmetrical association measure to extract referral rules that is based on annotated suffix tree scoring. Hence the reference graph is a directed graph, which is a very well studied mathematical structure. This gives us plenty of opportunities for further analysis. 2
We choose a number of Russian news portals (“Izvestia”, “Nezavisimaya gazeta”,“Moscow Komsomoltes”, “Kommersant”). We crawled the section of their web-pages devoted to economics. We process and aggregate all the articles published in 2014, which gives us a total of 4061 articles (1109 from “Kommersant”, 1061 from “Izvestia”, 1284 from “Nezavisimaya gazeta”, and 613 from “Moscow Komsomoltes”). 3
First, following [
According to the annotated suffix tree model [
To build an AST, we split the text into relatively short fragments, strings of two
to four words, and apply them consecutively to ensure that the resulting AST has a
relatively modest size. Our algorithm for constructing an AST [
To use an AST to score the string to text relevance we need to do the following, First we build an AST for every text. Next we match the strings to the AST to estimate the relevance. This is done in several steps: 1. Every string is split into suffixes; 2. Every suffix is matched to the AST. A match is a path from the root of the AST, that coincides with the beginning of the current suffix. To estimate the match we use scoring function: score(match(su x ; ast )) = =
X node2match (
f (node) f (parent(node)) ); where f (node) is the frequency of the matching node and f (parent(node)) is it’s parent frequency; 3. Then the relevance is estimated by averaging the score of a symbol: relevance(string ; text ) = SCORE(string; ast) = = Psu x score(match(su x ; ast ))=jsu x j ; jstring j where jsu x j and jstring j are the lengths of the suffix and the string.
Note, that “score” is a scaling function that converts a match score into a relevance
estimation. We consider three types of the scaling functions, according to [
x 1
x (x) = log = log x log(1 x) Of them, only the linear scaling function has an obvious meaning: it stands for the conditional probability of characters averaged over matching fragments (CPAMF).
Let us calculate the relevance of string “dining” to the AST in Fig. 1. There are
six suffixes of the string “dining”: ‘dining”, “ining”, “ning”, “ing”, “ng”, and “g’ . The
scorings of these suffixes are presented in Table 1.
The reference graph construction method is based on the procedure of scoring
relevance of a key phrase to a text. Because the key phrases are extracted from the whole
collection, we do not know how relevant they are to individual texts. We use annotated
suffix tree (AST) scoring to compute key phrase to text relevance in the same fashion
as it is presented in [
As soon as we get the set of referrals ki =) kj and their confidence and support values, we can plot the reference graphs. For the sake of space we replace key words / phrases with their index numbers. The size of the node depends on the support value. The nodes are color-coded in the following way: the green nodes only refer to other nodes, the violet are only referred by other nodes, the rest of the nodes are blue.
Let us consider two reference graphs constructed for two newspapers ‘Moscow Komsomolets” (upper Fig. 2) and “Nezavisimaya gazeta” (lower Fig. 2), based on articles published in December 2014. First of all, the graph are of similar size: there are 88 nodes and 85 nodes correspondingly. The graphs are of different shapes: the first one is centered around the node 256 (“Russian Government” ), that has the highest support. The second graph is sparse and there is no obvious center. The highest support get the nodes 256 (“Russian Government” ) and 325 (“Economic growth” ). Both graphs share in common a strongly connected component of four nodes 215, 216, 217, 218, that describes consumer behavior (“Consumer price”, “Consumer credit” , “Consumer demand” , “Consumer lending” ), which is no surprise. However there is little intersections in the content of the graphs. The nodes “Vladimir Putin” and “Dmitry Medvev” are absent in the second graph. There are four nodes that deal with Ukraine in the first graph, and only two of them appear in the second. At the same time, there is a node “Saudi Arabia” in the second graph. The majority of nodes in the second graph are Russian Government and Ministry of Finance related, while in the first graph the majority of nodes relate to ruble devaluation and business in Russia. These two graphs clearly show the difference between two newspapers. “Nezavisimaja gazeta” being more politics and business oriented presents the year end situation in Russia as crisis, while the “Moscow Komsomolets” is more oriented towards international relations of Russia and consumer needs. 7
There are several ways of reference graph analysis. such as link analysis and extension
of reference graphs to time-depended case. The most straightforward way to analyse the
structure of the directed edges and to measure centrality of the nodes of the reference
graph is to apply the PageRank algorithm[
Node (Key word/phrase) “Russian market” “Economic sanctions” “Consumer demand” “Consumer credit” “Economic policy”
PageRankValue 0.107 0.063 0.047 0.042 0.035 “Economic sanctions” seem to be the most important event of the December, 2014, widely discussed in both newspapers under consideration. Despite the attitude to economics sanctions might be different, the consumer demand is usually discussed in context of possible consequences. The link analysis confirms the fact that “Nezavisimaya gazeta” is more oriented to market situation, while “Moscow komsomolets” looks at the situation from the world-wide perspective. To analyse how the reference graphs change with time we need to construct a series of reference graphs. Let us split the 2014 year in 25 periods, so that every period lasts for 2 weeks. Now we can construct 25 reference graphs, using the same key words / phrases and subcorpus of the articles published in the given period. Let us focus on the “Izvestia” newspaper. First of all we check, which key words / phrases are relevant (i.e. have high support that is document frequency) to each period. To do this we need to merge all the articles of the period into one text and apply the AST relevance measure. Surprisingly this gives us a simple typology of the key words / phrases. There are key words / phrases that are relevant to all periods, such as “Gas supply” . There are key words / phrases that are relevant for several consequent periods. For example, “Tax concession” is relevant to periods 8-13, that is for the middle of the year (after annexation of Crimea), “Weakening rouble” is relevant to periods 16-20. Finally, there are key words / phrases that are relevant to the beginning and to the end of year periods: “Rate increase” , “the Customs Union” , “Oil price”, “Gasprom” . This might be explained by planning and wrapping up the year using the same vocabulary.
The next step is to check which referrals are present during the whole year and which appear / disappear in some periods. Such referrals are “State Duma” =) “Bill” , “Vladimir Putin” =) “Russian rouble” , “Russian gas” =) “Ukraine government” are present in almost all 25 reference graphs. Closer to the end of the year appear such referrals as “Inflation” =) “Russian currency” . There are some referrals that are appear in disjoint periods. For example, the referral “Retail” =) “Criminal responsibility” appears in periods 3-4, 8, 11-12, 17, 19, 23. Since we plan to make an animation of how reference graphs change with time, such referrals might cause a lot of difficulties. We cannot animate straightforwardly the reference graphs and need some sort of smoothing. 8
Analysis of reference graphs. It is necessary to test some methods for graph analysis such as clustering nodes, measuring centrality (ingluding PageRank and HITS), finding cycles of minimal length, bridges, connected components.
Temporal analysis. The extension of reference graphs to time-depended case will allow us to detect trends and / or events in newspapers by finding temporal references between key word or phrases that occurred yesterday and today’s key word or phrase.
Coloring the nodes. We plan to use the LDA [
Text preprocessing improvement. Further directions of text processing module development include word sense disambiguation and disambiguation for morphological analysis. We need to develop some filters that distinguish between newspaper-specific vocabulary and general vocabulary and take synonyms such as “Russian currency” and “Rouble” into account.
Quantitative evaluation. Since there is no golden standard for text visualisation problems, it is a common idea to conduct a user study for quantitative evaluation. There are three possible designs of the study. To test the information discovery power of referral relation A =) B we ask the user “What is the context of concept B?” and provide 4 possible answers: concept A (right answer), concept C, such that B =) C, concept D, such that D =) A =) B, a random concept. The proportion of right answers will show the validity of referral relation. To test the reference graphs as a search tool, we provide the user with a search engine which is able to search in our text collection, a series of tag clouds for every time period and every source and corresponding series of referral pairs. We ask the user to find concepts, associated to his/her own query. Using only the search engine he/she will hardly find any associated concepts. By looking at tag clouds the user might discover some concepts that are related to the search. But the reference graphs will provide not only the concepts the query refers to or is referred by, but also the concepts achieved according to transitivity of referral relation. To validate this we a) record the average time of determining the associated concepts, b) ask the user to estimate the ease of finding associated concepts by means of every tool. To test the temporal reference graphs, we ask the user to search for his/her own query and understand since when his/her query is important. To answer the question the user may read all the text, rely on the size of the tags of the tag clouds or check, whether the query appears in a certain reference graph. Since the key word / phrase appears in the reference graph, in and only if it has high support and is a part of a reference rule with a high confidence, using the reference graphs might help the user a lot. We use the same validation techniques as we use for the previous test. 9
In this paper we tried to analyse a corpus of articles published in the most popular Russian newspapers in 2014 by means of so-called reference graphs. Every node of a reference graph is a key word or key phrase. The edges of the graph represent reference relation, which means that if node A refers to node B, B is more likely to co-occur with A. The reference graphs can serve not only as a visualization tool, but also as a tool for further text analysis.