Online First

Bun and Ishizuka (2002) first published the concept of TF*PDF algorithm for detecting hot topics. In TF*PDF algorithm, they defined the publisher of a news item as a channel. If the PDF weight of a term is higher than the weights of other terms, then the term is hotter than the other terms.

Fig. 1 illustrates the features of the TF*PDF algorithm. Each document in Fig. 1 has 50 terms, and the term “cat” can be considered as an example of a word with the feature of PDF weight. In Fig. 1(a), the term “cat” appears in several documents, and the PDF weight is 1.087. The highest PDF weight in all cases indicates that the term is relatively a hot term. The term “cat” shows up twice in both Fig. 1(b) and Fig. 1(c). Note that the PDF weight of “cat” is 0.544 in Fig. 1(b), but the PDF weight is 0.330 in Fig. 1(c). The PDF weight is higher when instances of the term are gathered in a channel (as in Fig. 1(b)) than it is when the instances are scattered over multiple channels (as in Fig. 1(c)). The PDF weight of “cat” in Fig. 1(d) is 0.330. This means that if a term only appears in a single document, its PDF weight is lower than separate instances of the term appear in multiple documents.

Fig. 1. 
Features of the TF*PDF algorithm

Bun and Ishizuka applied the concept of TF*PDF for the automatic identification of hot topics; however, in this study, an algorithm automatically applies the concept of TF*PDF to produce summaries of news events. In this study, the day of the news event is a more noteworthy factor than the publisher of a document; therefore, in this study, “day” (and not “news publisher”) is used as the channel.

After calculating the PDF weight of each term, the proposed algorithm constructs the semantic relationship between each pair of sentences. If the PDF-modified cosine similarity between two sentences is higher than a threshold, which is selected by users, the algorithm considers these two sentences to be related. The relationships between sentences compose a semantic network, as illustrated in Fig. 2. This work considers the priority of a sentence to be proportional to the number of relationships in which it is involved. In Fig. 2, d1-s4 has the highest number of relationships with other sentences.As a result, this work considers d1-s4 as the paramount sentence in the summary. On the contrary, this work considers d1-s2 and d3-s1 as less vital, because they have no relationships with most of the other sentences.

Fig. 2. 
Relationship network among sentences

For inspecting and quantizing the importance of a sentence, this work adopts the concept of degree centrality from complex network.

Fig. 3 illustrates the process of PMCN multi-document summarization algorithms. This study divides the algorithm into four parts: preprocess data, establish a similarity matrix, establish a relationship matrix, and output the summary. Each stage of the algorithm has a distinct target.

Fig. 3. 
Phases of PMCN multi-document summarization algorithm

Fig. 4 displays the relationships among channel, document, and sentence. In this study, a document is a news report; a channel is defined as the specific date of a news story. The channel consists of documents. Each document comprises several sentences. Each sentence has a unique name. The code defines d_x-s_y to be the unique name for the yth sentence of the xth day.

Fig. 4. 
Relationships among channel, document, and sentence

This study uses the MySQL Stopwords list¹⁾ as a reference. The MySQL Stopwords list contains 543 frequently used words in English. This study displays a set of raw data as an example in Table 1(a). Stop words such as “are” in d₁-s₁ and “is” and “a” in d₁-s₂ are removed according to the stop word list. Table 1(b) shows the result of removing stop words. In the process of stemming, “cats” and “pets” in d₁-s₁ return to their stems “cat” and “pet.” “Ate” in d₂-s₁ is transformed to its verb root “eat.”

After the removal of stop words and stemming, the words remaining in the sentences are defined as terms. For example, in Table 1(b) “cat” and “pet” are terms in d₁-s₁. After that, the occurrences of each term in all sentences are calculated, and the term-sentence matrix is thus constructed.

The information in Table 1(c) serves to establish Table 1(d). In d₁-s₁, only the terms “cat” and “pet” appear, so the values of “cat” and “pet” are 1 and the rest of the terms are 0 in row d₁-s₁ of Table 1(d).

Table 2 uses the information in Table 1(d) to illustrate the method of deriving the PDF weight. The row labels d₁ and d₂ represent the term frequencies in day 1 and day 2, respectively. For example the term “pet” appears 2 times in day 1, but appears 0 times in day 2. The PDF weight of each term must be calculated. As an example, the PDF weight of “cat” can be calculated as follows. In day 1, term “cat” appears in once in two documents, therefore the value is exp(1/2) divided by the term vector of day 1. Similarly, in day 2, term “cat” appears in once in two documents, therefore the value is exp(1/2) divided by the term vector of day 2.

As an example, the PDF weight of “fish” can be calculated as follows. In day 1, term “fish” appears in once in two documents, therefore the value is exp(1/2) divided by the term vector of day 1. Similarly, in day 2, term “fish” appears in both two documents, therefore the value is exp(1/2) divided by the term vector of day 2. The other PDF values are calculated similarly and are shown in Table 2.

The sentence similarity matrix is established by calculation of the PDF-modified cosine similarity between every pair of sentences. Table 3 shows the sentence similarity matrix with the weights derived from Table 2 Consider, for example, the similarity between d₁-s₁ and d₁-s₂; the PDF-modified cosine similarity is calculated as follows:

Table 3 indicates that the PDF-modified similarity between d₁-s₂ and d₂-s₂ is 0.756; however, for another example, the PDF-modified similarity between d₁-s₁ and d₂-s₂ is calculated as follows:

This means d₂-s₂ is more similar to d₁-s₂ than to d₁-s₁.

The sentence similarity matrix in Table 3 shows the similarities between certain sentences. Complex network includes Boolean matrix technique; the sentence similarity matrix can be transform into a Boolean matrix, termed the sentence relationship matrix.

Table 4 shows the sentence relationship matrix derived from Table 3 For the convenience of further demonstration, a threshold h = 0.7 can serve as an example. Table 3 indicates that the similarity between d₁-s₁ and d₁-s₂ is 0.549, which is lower than the threshold 0.7. Consequently, the relationship between d₁-s₁ and d₁-s₂ is 0. In the same way, the similarity between d₂-s₂ and d₁-s₂ is 0.756, which is higher than the threshold 0.7. Hence, the relationship between d₂-s₂ and d₁-s₂ is 1. The sentence relationship matrix is mathematically equivalent to its graph form. Each sentence is a vertex and each cell entry in the matrix is an edge in the graph. The matrix in Table 4 is equivalent to Fig. 5.

Fig. 5. 
Graph form of Table 4

Fig. 5 shows the relationship between each pair of sentences. A line between two sentences indicates that the two sentences are related. Thus, the relationships among sentences weave a network that can undergo degree centrality. Fig. 5 shows that d₂-s₂ has the largest number of relationships with other sentences. This means d₂-s₂ is one of the most crucial sentences in the semantic network. However, if the number of sentences were much higher, centrality measures from complex network could be used to extract pivotal sentences.

Freeman (1978) first depicted degree centrality for a measurement of centrality in graph theory and complex network. Freeman (1978) defined degree centrality as the number of edges that connected a vertex to other vertices. In Table 4 (or Fig. 2), which is equivalent to Table 4), d₁-s₁ is not related to any other sentence. As a result, the degree centrality of d₁-s₁ is 0. On the contrary, d₂-s₂ is related to d₁-s₂ and d₂-s₁, so the degree centrality of d₂-s₂ is 2. The calculation of degree centrality is displayed as Equation (7). The degree centrality of a sentence is calculated by adding up all the relationships that share the same column as the sentence, and then subtracting 1. The 1 must be subtracted to remove the diagonal element because the relationship of the sentence with itself is always 1.

where,

• Degree centrality(s) stands for the degree centrality of sentence s

• colSum(s) is the summation of all elements of the same column as s

In this study, the sentences are ranked by degree centrality. The user defines the parameter k, and then the algorithm outputs the k sentences with the highest degree centrality values as the result summary. If the degree centrality is the same, the algorithm compares the highest similarity values in the sentence similarity matrix. For the sample data in Table 5, the output summary of the raw data in Table 1 is “Fish was dead.” and “Cat ate the fish.”

Algorithm 1 specifies the main processes of TF*PDF multi-document summarization, excluding the data preprocessing.

Algorithm 1. PMCN multi-document summarization algorithm

Step 1. Remove the stop words.

Step 2. Stem the words.

Step 3. Calculate the frequency of each term in every sentence to construct the term-sentence matrix.

Step 4. Calculate the PDF-modified cosine similarity of every pair of sentences to establish the sentence similarity matrix.

Step 5. Define parameter h as a threshold of similarity for the sentence relationship matrix.

Step 6. Derive the degree centrality of each sentence.

Step 7. Rank the sentences by degree centrality.

Step 8. Select the top k sentences.

Step 9. Sort the selected sentences in chronicle order.

Table 6 shows a brief overview of tasks d30001t, d30002t, and d30003t. The tasks include 10 documents with similar numbers of sentences, but task d30002t has a notably larger standard deviation for the number of sentences in the documents.

Table 7 shows a sample of the sentences in the d30001t dataset. After dataset preprocessing, including the removal of stop words and stemming, the terms can be identified, and several terms are shown as the column headings of Table 8.

After terms are identified, the term-sentence matrix can be constructed. Table 8 shows a part of the term-sentence matrix derived from the data in Table 7.

By using the information in Table 8, the PDF weight can be calculated for each term. Table 9 lists the 15 terms with the highest PDF weights. The PDF weight indicates the importance of a term.

Using the PDF weights shown in Table 9, the PDF-modified cosine similarity between every pair of sentences can be derived, and the sentence similarity matrix can be constructed; part of that matrix is shown in Table 10.

A threshold h = 0.5 was selected for the sentence relationship matrix. A sample of the sentence relationship matrix is presented in Table 11. Table 11 reveals that the pairs of sentences from d₁s₁ to d₁s₅ are related to each other; however, d₁s₆ does not relate to any sentences from d₁s₁ to d₁s₅.

The content of Table 11 is equivalent to a subgraph of the relationship graph shown in Fig. 6. The results of this research indicate that for this task, two groups of sentences are highly related to the other sentences in each group. Five critical sentences are related to both of those two groups. A well-designed algorithm should output those critical sentences in its summary.

Fig. 6. 
Relationship graph of task d30001t

The degree centrality of each sentence can be calculated from the results listed in Table 11. The degree centrality values of sentences from task d30001t are shown in Table 12; the degree centrality value of d₁s₂ is higher than those of other sentences. Thus, it should appear in the final summary. Conversely, because of its low degree centrality, d₁s₆ should not appear in the summary.

Finally, the algorithm selects the top k = 5 sentences for the summary and sorts the selected sentences in chronicle order; the result is shown in Table 13.

In this study, 23 tasks from the DUC2004 dataset were used for evaluation. The DUC2004 dataset has a manual summary that was regarded as the “correct answer.” ROUGE, a n-gram based method, was used as a validation tool; precision, recall, and F-score were compared for the PMCN (PDF-Modified similarity and Complex Network) multi-document summarization algorithm and LexRank. Both PMCN and LexRank process a 4-sentence summary, which is the same as the reference hand-made summary. The results of comparison of ROUGE-1 scores are shown in Tables 14. Though in most of the cases, the proposed algorithm performs lower F-score than LexRank does, the proposed method performs well in recall. This means proposed algorithm capable to obtain important messages than LexRank does.