Automatic text summarization using string vector based K nearest neighbor

Abstract

This article proposes the modified KNN (K Nearest Neighbor) algorithm which receives a string vector as its input data and is applied to the text summarization. The results from applying the string vector based algorithms to the text categorizations were successful in previous works and the text summarization is able to be viewed into a binary classification where each paragraph is classified into summary or non-summary. In the proposed system, a text which is given as the input is partitioned into a list of paragraphs, each paragraph is classified by the proposed KNN version, and the paragraphs which are classified into summary are extracted ad the output. The proposed KNN version is empirically validated as the better approach in deciding whether each paragraph is essential or not in news articles and opinions. We need to define and characterize mathematically more operations on string vectors for modifying more advanced machine learning algorithms.

Keywords

String vector semantic similarity string vector based KNN text summarization

1 Introduction

Introduction Text summarization refers to the process of selecting essential parts from a text automatically as its brief version. Each text is partitioned into sentences or paragraphs by the punctuation mark or the carriage return, respectively, and the text summarization may be viewed as a binary classification where each sentence or paragraph is classified into the essence part or not. Each sentence or paragraph is encoded into its structured form and prepare sentences or paragraphs labeled with essence or remaining as the samples. The system constructs the classification capacity by learning the labeled samples, classify novice sentences or paragraphs into essence or non-essence, and present the one which is classified into essence. We need to distinguish the automatic summarization from the manual summarization in that the manual summarization refers to the process of rewriting the entire text into its brief form.

Let us consider the motivations for doing this research. Since the text summarization task may be interpreted into a binary classification, it is regarded as an instance of text categorization [3]. In the traditional text categorization systems, texts were encoded into numerical vectors, which were very inefficient representations [18]. The numerical vectors as surrogates of texts have very poor transparency; they are unable to present their contents, symbolically [18]. Therefore, in this research, we encode each text into a string vector, in order to solve the problems.

Let us mention the proposals of this research as the solutions to the above problems. The text partitions which are paragraphs or sentences are encoded into string vectors, and the semantic similarity measure between string vectors is defined in this research. Using the similarity measure, we modify the KNN (K Nearest Neighbor) where a string vector is given as the direct input data. The modified version is used as the approach to the classification task which is mapped from the text summarization. Hence, in this research, the task of text summarization is regarded as the binary classification of each sentence or paragraph into an essence or a remaining one.

This research is expected to provide some benefits. By encoding the texts into the alternative representations to the numerical vectors, it is possible to avoid the above problems completely. It is more efficient and compact to encode texts into string vectors; the dimension of string vectors is usually only tens, while that of numerical vectors is usually hundreds, ten times for maintaining enough system robustness. The string vectors are more transparent than numerical vectors since they are characterized symbolically; we are able to guess the contents by referring only representations without their full sentences. However, as remaining tasks, we need to define more advanced operations on string vectors, in order to modify more advanced machine learning algorithms.

This article is organized into the five sections. In Section 2, we survey the relevant previous works. In Section 3, we describe in detail what we propose in this research. In Section 4, we validate empirically the proposed approach by comparing it with the traditional one. In Section 5, we mention the general discussion on the empirical validations and remaining tasks for doing the further research.

2 Previous works

PreviousWorks This section is concerned with the previous works which are relevant to this research. In Section 2.1, we explore the previous cases of applying the KNN algorithm to text mining tasks. In Section 2.2, we survey the schemes of encoding texts or words into structured data. In Section 2.3, we describe the previous machine learning algorithms which receive alternative structured data such as tables and string vectors to numerical vectors. Therefore, in this section, we provide the history about this research, by surveying the relevant previous works.

2.1 Using KNN algorithm to text mining tasks

Section02.01 This section is concerned with the previous cases of applying the KNN algorithm to text mining tasks. Classifying texts or words belong to a text mining task, and the KNN algorithm is adopted as the approach to the task in this research. The KNN algorithm belongs to the lazy learning algorithm which does not learn training examples in advance. The fact that the KNN algorithm is popularly used in classification tasks in any domain, as well as text categorization is the reason of adopting and modifying the KNN algorithm. In this section, we survey cases of applying the KNN algorithm to the word categorization, text categorization, and spam mail filtering.

Let us mention the previous cases of applying the KNN algorithm to the word categorization and its similar tasks. In 2001, Kim et al. translated words using the KNN algorithm between English and Korean [22]. In 2003, Pekar and Staab classified words into their synonyms, using the KNN algorithm [29]. In 2016, Stauffer et al. represented optimal images of handwritten words into graphs and applied the KNN to the word recognition [31]. The word categorization in this research is the task of classifying words based on their topics or meaning; it should be distinguished from ones which are mentioned in the above literatures.

Let us mention the previous cases of applying the KNN algorithm to the text categorization. In 2001, Sam et al. proposed the modified version of KNN which considers the feature importance for computing the similarity between numerical vectors [5]. In 2010, Khan et al. reviewed machine learning approaches including the KNN algorithm to the text categorization [21]. In 2014, Vishwanath et al. proposed the KNN version which computes the similarity between a test document and a class prototype and the Naive Bayes, as the approaches to text categorization [32]. Even recently, texts are still encoded into numerical vectors in using the KNN for the text categorization, in above literatures.

The spam mail filtering refers to a particular text categorization where each email is classified into spam or ham. In 2003, James et al. proposed the neural networks as the approach to the spam mail filtering and compared it with the KNN algorithm as the base approach [6]. In 2004, Lai and Tsai proposed the four machine learning algorithms including the KNN as the email categorization tools [23]. In 2010, Frite et al. used the KNN algorithm for the spam mail filtering with resampling methods [4]. In the above literatures, emails are regarded as texts and encoded into numerical vectors.

We survey the cases of using the KNN for the text mining tasks: word categorization, text categorization, and spam mail filtering. Textual data are encoded into numerical vectors in all above literatures. The KNN algorithm has been used as very popular approach to text mining tasks as well as any other kinds of classification tasks. Even if another approach has been proposed to the word and text categorization, it has been compared with the KNN algorithm. In this research, we adopt the KNN based on the above literatures and modify it into more suitable version for text mining tasks.

2.2 Encoding schemes

Section02.02 This is concerned with the previous works on encoding words or texts into structured data. It has been assumed that the input data are always given as numerical vectors in applying machine learning algorithms to applications in any domain. In almost cases of applying machine learning algorithms to text mining texts, texts or words are encoded into numerical vectors. In order to solve the problems in encoding so, there were previous trials of encoding them into alternative structured data to numerical vectors. In this section, we explore the previous schemes of encoding texts or words into structured data.

It is known that texts or words are usually encoded into numerical vectors, by surveying articles on machine learning approaches to text categorization. In 1995, Wiener encoded texts into approximately three hundreds dimensional numerical vectors, in applying the neural networks to the text categorization [33]. In 1999, Yang encoded texts absolutely into numerical vectors, in evaluating machine learning algorithms in apply them to the text categorization [34]. In 2002, Sebastiani surveyed the machine learning approaches to the text categorization, under the assumption of encoding texts into numerical vectors [30]. The fact that texts should be encoded into numerical vectors for doing the text mining tasks is confirmed through the above literatures.

There existed the previous trials of encoding text into tables, instead of tables for doing the text categorization and clustering. In 2008, Jo modified the single pass algorithm into its table based version for the text clustering [9]. In 2011, Jo invented the table marching algorithm as the method of categorizing texts in his patent [15]. In 2015, Jo improved the table matching algorithm into the stable and robust version [16]. The table becomes the alterative text representation to the numerical vector for doing the both tasks.

There also existed the previous trials of encoding texts into string vectors as one more alternative structured data for doing the both tasks. In 2009, Jo proposed the semantic similarity between string vectors for using the KNN and the SVM for ding the text categorization [11]. In 2010, Jo modified the k means algorithm into its string vector based version as the approach to the text clustering [12]. In 2015, Jo defined and characterized mathematically the numerical operations on string as the fundamental research for modifying other machine learning algorithms into their string vector based versions [17]. It requires to define and characterize more semantic operations for modifying more advanced machine learning algorithms.

In this research, we adopt the scheme where paragraphs are encoded into string vectors. In each string vector, the features indicate the relations between a text and a word, and the feature values do the text identifiers which satisfying the relations. We define the semantic similarity between two string vectors which is always given as a normalized value between zero and one. The similarity between words, becomes the basis for computing the similarity matrix. The KNN algorithm is modified as the approach to the text summarization by replacing the cosine similarity.

2.3 Specialized machine learning algorithms

This section is concerned with the previous works on approaches to the text mining tasks where texts are encoded into alternative representations to numerical vectors. In Section 2.3, we explored the previous schemes of encoding texts into structured data and the modified versions of existing machine learning algorithms using the scheme. In this section, we introduce the string kernel which is a kernel function on string in using the SVM to the text categorization, and mention the new neural networks, NTC (Neural Text Categorizer) and NTSO (Neural Text Self Organizer) for doing the text categorization and the text clustering. It takes very much time for applying the string kernel version to the text categorization and needs more operations for advancing the created neural networks. In this section, we explore cases of using the string kernel based SVM and the two creative neural networks to text mining tasks.

The string kernel was proposed as a kernel function in using the SVM for classification tasks, in order to avoid problems in encoding texts into numerical vectors. In 2002, Lodhi et al. initially proposed the string kernel, in order solve the problems in doing so [25]. In 2004, Leslie et al. applied the string kernel to protein classification where a protein is given as a string [24]. In 2006, Kate and Mooney used the string kernel for processing semantically sentences, instead of entire full texts [20]. The SVM with the string kernel works not successfully in the text categorization, but it works successfully in the protein classification.

The neural network, NTC (Neural Text Categorizer), was previously invented as a more suitable approach to the text categorization. In 2000, Jo initially proposed the NTC, but it used its weights which are fixed based on word frequencies [7]. In 2008 and 2010, Jo improved the NTC into the version where word weights are updated, and applied it to both the exclusive text categorizations and the soft ones [10, 13]. In 2012, Pawar and Gawande mentioned the NTC as innovative approach to the text categorization, and in 2015, Abainia et al. applied it for categorizing Arabic texts [1, 28]. In future, the NTC needs to be expanded from the swallow version into deep version.

The NTSO (Neural Text Self Organizer) was previously created as a more suitable approach to the text clustering. In 2005, Jo and Japkowicz invented initially as the approach to the text clustering [19]. In 2006, Zehng et al. mentioned the NTSO as one of the main text clustering tools [35]. In 2010, Jo validated empirically the NTSO performance by comparing it with the popular approaches such as the k means algorithm and the Kohonen Networks [14]. The NTSO will be modified into its supervised version and semi-supervised version in future, like the Kohonen Networks.

In this research, we set the text summarization as the task against which we challenge. In the string kernel based SVM, the lexical similarity between strings is computed, rather than semantic ones; it is more suitable for processing proteins than for doing texts. The two neural networks, NTC and NTSO, take actually much computation time and are very complicated with respect to implementations; they are usually used for implementing heavy versions of text categorization and clustering systems. It requires the mathematical definition and characterizations on more operations on strings for expanding them. Therefore, in this research, we propose the modified KNN version for implementing light versions.

3 Proposed approach

ProposedApproach This section is concerned with encoding words into string vectors, modifying the KNN (K Nearest Neighbor) into the string vector based version and applying it to the text summarization, and consists of the three sections. In Section 3.1, we deal with the process of encoding texts into string vectors. In Section 3.2, we describe formally the similarity matrix and the semantic operation on string vectors. In Section 3.3, we focus on the process of applying the KNN to the given task with viewing it into a classification task.

3.1 Text encoding

We deal with the process of mapping texts into string vectors, in this section. Figure 1 shows the basic three steps which are involved in encoding texts. A text is given as the input and a string vector which is composed of words is generated as the output. The features of string vectors are defined as posting, static, and grammatical properties. Therefore, we describe in detail how to encode a text into a string vector.

Fig.1

The Process of Text Encoding.

As the first step of encoding a text into a string vector, the text is indexed into a list of words. The text is segmented into tokens by white spaces, punctuation marks, and other special characters. Each token is changed into its root form through the stemming process. Among stemmed tokens, grammatical words which are called stop words are removed. After doing so, posting, statistical, and grammatical information are assigned to each remaining word.

In order to map a text into a string vector, we need to define features of string vector. In previous works on the string vector based machine learning algorithms, word frequencies were used for defining the features [7]. In this research, we proposes the three types of string vector features: posting features, statistical features, and grammatical features. The posting features are ones which indicate where words are positioned in the text, the statistical features are ones which indicate how many words occurs in the text, and the grammatical features are ones which indicate what words play role of. Because in the proposed system, the POS tagging module is not available, we use the posting and the statistical information about words as string vector features. We define the string vector features as follows:

Highest Frequent Word in the given Text

Second Highest Frequent Word in the given Text

Third Highest Frequent Word in the given Text

Highest TF-IDF Weighted Word

Second Highest TF-IDF Weighted Word

Third Highest TF-IDF Weighted Word

The Last Word in the Text

The First Word in the Last Paragraph

The Last Word in the First Paragraph

Once the above features are defined, we explain the process of assigning words to features. In the above process, a text is indexed into a list of words, together with their information. We defined the nine items as string vector features manually and, from the text the system takes words which correspond to the nine features. The nine words become the elements of the string vector. The dimension of string vectors which represent texts becomes nine, following the number of above features.

In the current research, the nine features are defined manually, but it is feasible, because the number of features is small. However, in encoding texts into numerical vectors, the features are defined, automatically; it is the trade off between the two encoding schemes. Even if the dimension of string vector is very smaller, the classification performance is better than the traditional classification systems where the raw data is encoded into numerical vectors. The reason is that numerical vectors representing texts tend to be sparse, but the string vector is very compact. In next research, we will consider schemes of defining the string vector features, automatically.

3.2 String vectors

StringVectors This section is concerned with the operation on string vectors and the basis for carrying out it. It consists of two subsections and assumes that a corpus is required for performing the operation. In Section 1, we describe the process of constructing the similarity matrix from a corpus. In Section 1, we define the string vector formally and characterize the operation mathematically. Therefore, this section is intended to describe the similarity matrix and the operation on string vectors.

3.2.1 Similarity matrix

SimilarityMatrix Before explaining the operation on string vectors, we focus on the similarity matrix which is basis for executing it. The similarity matrix is constructed from a corpus as the square matrix. Its rows and columns correspond to words which are available in the corpus. The entries of the similarity matrix becomes the semantic similarity between two corresponding words. Therefore, in this section, we describe formally the similarity matrix.

In the similarity matrix, each entry indicate the semantic similarity between two words. The two words are notated by t_i and t_j, and they are viewed as the two sets of texts, T_i and T_j. The similarity between the two words is computed by Equation (1), $sim (t_{i}, t_{j}) = \frac{2 | T_{i} \cap T_{j} |}{| T_{i} | + | T_{j} |}$ (1) where |T_i| is the cardinality of the set, T_i. The similarity is always given as a normalized value between zero and one; if two documents are exactly same to each other, the similarity becomes 1.0 as follows: $sim (t_{i}, t_{j}) = \frac{2 | T_{i} \cap T_{i} |}{| T_{i} | + | T_{i} |} = 1.0$ and if two words have no shared texts, T_i∩ T_j = ∅ the similarity becomes 0.0 as follows: $sim (t_{i}, t_{j}) = \frac{2 | T_{i} \cap T_{j} |}{| T_{i} | + | T_{j} |} = 0.0$ The more advanced schemes of computing the similarity, considering word positions and frequencies, will be considered in next research.

Assuming that there are N words in the corpus, we build the N × N square matrix, as follows: $S = (\begin{matrix} s_{11} & s_{12} & \dots & s_{1 d} \\ s_{21} & s_{22} & \dots & s_{2 d} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ s_{d 1} & s_{d 2} & \dots & s_{dd} \end{matrix}) .$ N individual words which are contained in the collection correspond to the rows and columns of the matrix. The entry, s_ij is computed by Equation (1) as follows: $s_{ij} = sim (t_{i}, t_{j})$ It takes the quadratic complexity to the number of words, O (N²), to build the similarity matrix. If the corpus is assumed to be fixed, the similarity matrix will be used continually, once it is built.

We try to characterize the similarity matrix, mathematically. In the diagonal positions of the similarity matrix, the entry is always given as one, since the corresponding words are exactly same to each other. In the off-diagonal position, the entry value is a continuous real number between zero and one. The semantic similarity between two words which is computed by Equation (1) is always given as a normalized value. The similarity matrix is symmetry and it is proved as follows: $s_{ij} = sim (t_{i}, t_{j}) = \frac{2 | T_{i} \cap T_{j} |}{| T_{i} | + | T_{j} |} = \frac{2 | T_{j} \cap T_{i} |}{| T_{j} | + | T_{i} |}$ $= sim (t_{j}, t_{i}) = s_{ji}$

It takes much time to build the similarity matrix from a corpus. Once the matrix is built, it may be used continually, if the corpus is fixed. When the corpus is changed continually, the system becomes infeasible, if the similarity matrix is rebuilt, accordingly. When some texts are added or deleted, we need to consider the scheme of updating the similarity matrix, in the next research. Since the similarity matrix is usually big, we may consider using small distributed similarity matrix as basis for carrying out the operation.

3.2.2 String vector and semantic similarity

StringVector and Semantic Similarity We mention the operation on string vectors which is called semantic similarity. In the traditional classification system, we used the cosine similarity or the Euclidean distance as the operation on numerical vectors. Using the string vector as the input vector was proposed by Jo in 2000 [7], so very few operations are defined. This research defines the semantic similarity between two string vectors and uses it for modifying the KNN algorithm. In this section, we will describe the operation formally.

A string vector refers to a finite ordered set of strings as follows: $str = [{str}_{1}, {str}_{2}, . . . ., {str}_{d}]$ An element in the vector, str_i indicates a text identifier which corresponds to its attribute. The number of elements of the string vector, str is called its dimension. In order to perform the operation on string vectors, we need to define the similarity matrix which was described in Section 1, in advance. Therefore, a string vector consists of strings, while a numerical vector does of numerical values.

Let us mention the semantic similarity between two string vectors which corresponds to the cosine similarity between two numerical vectors. The two string vectors are denoted as follows: ${str}_{1} = [{str}_{11}, {str}_{12}, . . . ., {str}_{1 d}]$

${str}_{2} = [{str}_{21}, {str}_{22}, . . . ., {str}_{2 d}]$

where each element, d_1i and d_21i indicates a text identifier. The operation is defined as Equation (2) as follows: $sim ({str}_{1}, {str}_{2}) = \frac{1}{d} \sum_{i = 1}^{d} sim (d_{1 i}, d_{2 i})$ (2) The similarity matrix was constructed by the scheme which is described in Section 1, and the sim (d_1i, d_2i) is computed by looking up it in the similarity matrix. We may compute the similarity between two string vectors, interactively, without constructing the similarity matrix.

Let us characterize mathematically the operation on the string vectors. The commutative law applies as follows: $sim ({str}_{1}, {str}_{2}) = \frac{1}{d} \sum_{i = 1}^{d} sim (d_{1 i}, d_{2 i})$ $= \frac{1}{d} \sum_{i = 1}^{k} sim (d_{2 i}, d_{1 i}) = sim ({str}_{2}, {str}_{1})$ If the two string vectors are exactly same, its similarity becomes 1.0 as follows: $if {str}_{1} = {str}_{2} with \forall_{i} sim (d_{1 i}, d_{2 i}) = 1.0$ $then sim ({str}_{1}, {str}_{2}) = \frac{1}{d} \sum_{i = 1}^{d} sim (d_{1 i}, d_{2 i}) = \frac{d}{d} = 1.0$

However, note that the transitive rule does not apply as follows: $if sim ({str}_{1}, {str}_{2}) = 0.0 and sim ({str}_{2}, {str}_{3}) = 0.0$ $then, not always sim ({str}_{1}, {str}_{3}) = 0.0$

Many operations were defined and characterized mathematically to numerical vectors, while very few operations were done to string vectors. In this research, only semantic similarity is defined and used for modifying the KNN algorithm. We need more advanced operations on string vectors for modifying other machine learning algorithms. In modifying the k means algorithm or the k medoid algorithm, we need the operation which correspond to averaging over numerical vectors. After this research, we try to modify the k means algorithm into its string vector based version.

3.3 Application to text summarization

Applicationto Text Summarization We mention the strategy of applying the proposed KNN version to the text summarization, in this section. The task should be mapped into a classification task where each item is classified into summary or non-summary, before applying it. We gather sample paragraphs which were labeled with summary or non-summary, and encode them into structured forms. The paragraphs which are classification targets are also texts; the classification which is mapped from the text summarization should be distinguished from the text categorization. Therefore, the text summarization is interpreted as a binary classification and the application scheme will be mentioned.

Figure 2 shows the proposed version of KNN where raw data is encoded into string vectors. The labeled sample texts are gathered and encoded into string vectors. A novice text is given as classification target, and encoded into a string vector. The KNN computes its similarities with the training string vectors by the process which was described in Section 1. It selects most similar training ones as its nearest neighbor, and decides by voting the labels of nearest neighbors. Since string vectors are compact representations, the proposed KNN version is expected be more robust than the traditional version.

Fig.2

The Proposed Version of KNN.

The text summarization is mapped into a binary classification, as shown in Fig. 3. A text is given as the input, and it is partitioned into paragraphs by carriage return. Each paragraph is classified into either of the two categories: ‘essence’ and ‘not’. The paragraphs which are classified into ‘essence’ are selected as the output of the text summarization system. For doing so, we need to collect paragraphs which are labeled with one of the two labels as sample examples, in advance.

Fig.3

View of Text Summarization into Binary Classification.

Let us consider the process of collecting sample paragraphs for doing the binary classification. The text summarization is mapped into the binary classification, as mentioned above. As shown in Fig. 4, a particular paragraph may be regarded differently, depending on the given domain; a paragraph should be summary in a particular domain, but it should be non-summary in another. The text collection from which we collect paragraphs should be partitioned into sub-collections by the domain. Here, the text which is given as the input is assumed to be tagged with its own domain.

Fig.4

Text Summarization: Domain Dependent Classification.

Let us consider the process of applying the KNN to the text summarization which is mapped into a classification. A text is given as the input, and the classifier which corresponds to the subgroup which is most similar to the given text with respect to its content is selected. The text is partitioned into paragraphs, and each paragraph is classified into ‘essence’ or ‘not’ by the classifier. The paragraphs which are classified into ‘essence’ are extracted as results from summarizing the text. Note that the text is rejected, if all paragraphs are classified into ‘not’.

In the text categorization, a text is classified into one or some among the predefined categories, independently of domains. However, the text summarization, a paragraph should be regarded as a summary or not, depending on the given domain. This is the reason of partitioning the text collection into sub-collections domain by domain and assuming that each text is tagged with its own domain. The domain granularity which is the degree of how much specific each domain is decides the text summarization performance. In too specific domains, we expect good performance, but it is difficult to obtain sample paragraphs.

4 Experiments

Experiments This section is concerned with the empirical experiments for validating the proposed version of KNN, and consists of the five sections. In Section 1, we present the results from applying the proposed version of KNN to the text summarization on the collection, NewsPage.com. In Section 1, we show the results from applying it for classifying paragraphs into summary or not, from the collection, Opinosis. In Section 1 and 1, we mention the results from comparing the two versions of KNN with each other in the task of text summarization from 20NewsGroups.

4.1 NewsPage.com

SectionFourOne This section is concerned with the experiments for validating the better performance of the proposed version on the collection: NewsPage.com. We interpret the text summarization into the binary classification where each paragraph is classified into summary or non-summary, and gather the paragraphs which are labeled with one of the two categories, from the collection, topic by topic. Each paragraph is classified exclusively into one of the two labels. We fix the input size as 50 dimensions of numerical vectors, and use the accuracy as the evaluation measure. Therefore, this section is intended to observe the performance of the both versions of KNN in the four different domains.

In Table 1, we specify the text collection, NewsPage.com, which is used in this set of experiments. The collection was used for evaluating approaches to text categorization tasks in previous works [16]. In each category, we extract 250 paragraphs and label them with summary or non-summary, keeping the complete balance over the two labels. In each category, the set of 250 paragraphs is partitioned into the training set of 200 paragraphs and the test set of 50 ones. Each text is segmented into paragraphs by a carriage return, and they are corrected manually, in the process of extracting paragraphs.

Table 1
The Number of Texts and Paragraphs in NewsPage.comTableThreeOne

Category #Texts #Training Paragraphs #Test Paragraphs

Business 500 200 (100+100) 50 (25+25)

Health 500 200 (100+100) 50 (25+25)

Internet 500 200 (100+100) 50 (25+25)

Sports 500 200 (100+100) 50 (25+25)

Category	#Texts	#Training Paragraphs	#Test Paragraphs
Business	500	200 (100+100)	50 (25+25)
Health	500	200 (100+100)	50 (25+25)
Internet	500	200 (100+100)	50 (25+25)
Sports	500	200 (100+100)	50 (25+25)

Let us mention the experimental process for validating empirically the proposed approach to the task of text summarization. We collect the sample paragraphs which are labeled with summary or non-summary in each of the four topics: Business, Sports, Internet, and Health, and encode them into numerical and string vectors. For each of 50 examples, the KNN computes its similarities with the 200 training examples, and selects the three similarity training examples as its nearest neighbors. This set of experiments consists of the four independent binary classifications each of in which each paragraph is classified into one of the two labels by the two versions of KNN algorithm. We compute the classification accuracy by dividing the number of correctly classified test examples by the number of test examples, for evaluating the both versions.

In Fig. 5, we illustrate the experimental results from deciding whether each paragraph is a summary, or not, using the both versions of KNN algorithm. The y-axis indicates the accuracy which is the rate of the correctly classified examples in the test set. Each group in the x-axis means the domain within which the text summarization which is viewed as a binary classification is performed, independently. In each group, the gray bar and the black bar indicate the accuracies of the traditional version and the proposed version of the KNN algorithm. The most right group in Fig. 1 consists of the averages over the accuracies of the left four groups, and the input size which is the dimension of numerical vectors is set to 50.

Fig.5

Results from Summarizing Texts in Text Collection: NewsPage.com.

Let us make the discussions on the results from doing the text summarization, using the both versions of KNN algorithm, as shown in Fig. 5. The accuracy which is the performance measure of this classification task is in the range between 0.46 and 0.52. The proposed version of KNN algorithm works strongly better in the two domains: Health and Sports. It matches with the traditional version in the domain, Internet, but it loses in the domain, Business. In spite of that, from this set of experiments, we conclude the proposed version works much better than traditional one, in averaging over the four cases.

4.2 Opinopsis

SectionFourTwo This section is concerned with the set of experiments for validating the better performance of the proposed version on the collection, Opinosis. We view the text summarization into a binary classification where each paragraph is classified into summary or non-summary, and collect the paragraphs, labeling manually with one of summary and non-summary from the collection. Each paragraph is exclusively classified into one of the two labels. We fix the input size to 50 and use the accuracy as the evaluation measure. In this section, we observe the performance of the both versions of KNN algorithm, in the three experiments as many as topics.

In Table 2, we specify the text collection, Opinosis, which is used in this set of experiments. The collection was used in previous works for evaluating the approaches to text categorization. We extracted the 50 paragraphs in each topic, and they are labeled with ‘summary’ or ‘non-summary’, keeping the complete balance over the labels. The 50 paragraphs is partitioned into the 40 as the training set and the 10 as the test set, in each topic. Each text is segmented into paragraphs by the carriage return, and some of them are corrected, in the processing of extracting paragraphs from texts.

Table 2
The Number of Texts and Paragraphs in OpiniopsisTableThreeTwo

Category #Texts #Training Paragraphs #Test Paragraphs

Car 23 40 (20+20) 10 (5+5)

Electronic 16 40 (20+20) 10 (5+5)

Hotel 12 40 (20+20) 10 (5+5)

Category	#Texts	#Training Paragraphs	#Test Paragraphs
Car	23	40 (20+20)	10 (5+5)
Electronic	16	40 (20+20)	10 (5+5)
Hotel	12	40 (20+20)	10 (5+5)

We perform this set of experiments by the process which is described in section 1. We collect sample paragraphs which are labeled with ‘summary’ and ‘non-summary’ in each of the three domains: ‘Car’, ‘Electronics’, and ‘Hotel’, and we encode them into 50 sized numerical vectors and string vectors. For each test example, the both versions of KNN computes its similarities with the 40 training examples and select the three most similar training examples as its nearest neighbors. Each test example is classified into ‘keyword’ or ‘non-keyword’ by the two versions of KNN algorithm; we performed the three independent experiments as many as the domains. The classification accuracy is computed by the number of correctly classified test examples by the number of the test examples for evaluating the both versions of KNN algorithm.

In Fig. 6, we illustrate the experimental results from the text summarization which is mapped into a classification task, using the both versions of KNN algorithm. Like Fig. 5, the y-axis indicates the value of accuracy, and the x-axis indicates the group of two versions by a domain of Opniopsis. In each group, the gray bar and the black bar indicate the results of the traditional version and the proposed version of KNN algorithm. In Fig. 6, the most right group indicates the averages of the both version over their results of the left three groups. Therefore, Fig. 6 shows the results from classifying paragraphs into one of ‘summary’, and ‘non-summary’, by the both versions.

Fig.6

Results from Summarizing Texts in Text Collection: Opiniopsis.

We discuss the results from doing the text summarization which is mapped into a binary classification, using the both versions of KNN algorithm on Opinosis, shown in Fig. 6. While the accuracy values of the traditional version stay at 0.5, those of the proposed version range between 0.5 and 0.6. The proposed version works better than the traditional one, in the two domains: Car and Electronics. It is leaded by the traditional one in the domain, Hotel; its accuracy is 0.4. From this set of experiments, we conclude that the proposed one works slightly better in averaging the three cases.

4.3 20NewsGroups I: General version

SectionFourThree This section is concerned with one more set of experiments for validating the better performance of the proposed version on text collection, 20NewsGroup I. We gather paragraphs which are labeled with ‘summary’ or ‘non-summary’, from each broad category of 20NewsGroups I, by viewing the text summarization into a binary classification. The task of this set of experiments is to classify each paragraph exclusively into one of the two labels in each topic which is called domain. We fix the input size to 50 in encoding the paragraphs and use the accuracy as the evaluation measure. Therefore, in this section, we observe the performances of the both versions in the four different domains.

In Table 3, we specify the general version of 20NewsGroups which is used for evaluating the two versions of KNN algorithm. In 20NewsGroup, the hierarchical classification system is defined with the two levels; in the first level, the six categories, alt, comp, rec, sci, talk, misc, and soc, are defined, and among them, the four categories are selected, as shown in Table 3. In each category, we extract 250 paragraphs from 4000 or 5000 texts; the first half is labeled with ‘summary’, and the other half is labeled with ‘non-summary’. The 250 paragraphs is partitioned into the 200 ones in the training set and the 50 ones in the test sets, as shown in Table 3. In the process of gathering the classified paragraphs, each of them is labeled manually into one of the two categories by scanning individual texts.

Table 3
The Number of Texts and Paragraphs in 20NewsGroups ITableThreeThree

Category #Texts #Training Paragraphs #Test Paragraphs

Comp 5000 200 (100+100) 50 (25+25)

Rec 4000 200 (100+100) 50 (25+25)

Sci 4000 200 (100+100) 50 (25+25)

Talk 4000 200 (100+100) 50 (25+25)

Category	#Texts	#Training Paragraphs	#Test Paragraphs
Comp	5000	200 (100+100)	50 (25+25)
Rec	4000	200 (100+100)	50 (25+25)
Sci	4000	200 (100+100)	50 (25+25)
Talk	4000	200 (100+100)	50 (25+25)

The experimental process is identical is that in the previous sets of experiments. We collect the paragraphs by labeling manually them with ‘summary’ or ‘non-summary’ by scanning individual texts in each of the four domains, comp, rec, sci, and talk, and encode them into numerical vectors with the input size fixed to 50. For each test example, we compute its similarities with the 200 training examples, and select the three similar ones as its nearest neighbors. The versions of KNN algorithm classify each of the 50 test examples into one of the two categories by voting the labels of its nearest neighbors. Therefore, we perform the four independent set of experiments as many as domains, in each of which the two versions are compared with each other in the binary classification task.

In Fig. 7, we illustrate the experimental results from deciding whether each paragraph is a summary, or not, on the broad version of 20NewsGroups. Fig. 7 has the identical frame of presenting the results to those of Fig. 5 and 6. In each group, the gray bar and the black bar indicates the achievements of the traditional version and the proposed version of KNN algorithm, respectively. In the x-axis, each group indicates the domain within which each paragraph is classified into ‘summary’, or ‘non-summary’. This set of experiments consists of the four binary classifications in each of which it is done so.

Fig.7

Results from Summarizing Texts in Text Collection: 20NewsGroup I.

Let us discuss the results from doing the text summarization using the both versions of KNN algorithm as shown in Fig. 7. The accuracies of both versions range between 0.48 and 0.85. The proposed version shows its better performances in all of the four domains. It keeps its competitive performance in the other. From this set of experiments, the proposed version wins over the traditional one, certainly, in averaging its achievements of the four domains.

4.4 20NewsGroups II: Specific version

SectionFourFour This section is concerned with one more set of experiments where the better performance of the proposed version is validated on another version of 20NewsGroups. From each specific topic, separately, we gather the paragraphs which are labeled with ‘summary’ or ‘non-summary’. In this set of experiments, we view the text summarization into a binary classification, and carry out the four binary classifications, independently of each other. We fix the input size of representing paragraphs to 50 and use the accuracy as the evaluation metric. Therefore, in this section, we observe the performances of the both versions of KNN algorithm in the four different domains.

In Table 4, we specify the specific version of 20NewsGroups which is used as the test collection, in this set of experiments. Within the general category, sci, we predefine the four categories: ‘electro’, ‘medicine’, ‘script’, and ‘space’. In each topic, we extract 250 paragraphs from approximately 1000 texts and label each of them with ‘summary’ or ‘non-summary’, maintaining the complete balance. The set of 250 paragraphs is partitioned into the training set of 200 ones and the test set of 50 ones, as shown in Table 4. We use the accuracy as the metric for evaluating the results from classifying paragraphs.

Table 4
The Number of Texts and Paragraphs in 20NewsGroups II

Category #Texts #Training Paragraphs #Test Paragraphs

Electro 1000 200 (100+100) 50 (25+25)

Medicine 1000 200 (100+100) 50 (25+25)

Script 1000 200 (100+100) 50 (25+25)

Space 1000 200 (100+100) 50 (25+25)

Category	#Texts	#Training Paragraphs	#Test Paragraphs
Electro	1000	200 (100+100)	50 (25+25)
Medicine	1000	200 (100+100)	50 (25+25)
Script	1000	200 (100+100)	50 (25+25)
Space	1000	200 (100+100)	50 (25+25)

The process of doing this set of experiments is same to that in the previous sets of experiments. We gather sample paragraphs which are labeled with ‘summary’ or ‘non-summary’, in each of the four domains: ‘electro’, ‘medicine’, ‘script’, and ‘space’, and encode them with the fixed input size: 50. We use the two versions of KNN algorithm for their comparisons. Each test paragraph is classified into one of the labels in each domain. We use the accuracy as the evaluation metric.

We present the experimental results from classifying the paragraphs using the both versions of KNN algorithm on the specific version of 20NewsGroups. The frame of illustrating the classification results is identical to the previous ones. In each group, the gray bar and the black bar stand for the achievements of the traditional version and the proposed version, respectively. The y-axis in Fig. 8, indicates the classification accuracy which is used as the performance metric. In this set of experiments, we execute the four independent classification tasks which correspond to their own domains, where each paragraph is classified into ‘summary’ or ‘non-summary’.

Fig.8

Results from Summarizing Texts in Text Collection: 20NewsGroup II.

Let us discuss the results from classifying the paragraphs using the both versions of KNN algorithm on the specific version of 20NewsGroups, as shown in Fig. 8. The accuracies as the performance metrics of this classification task which is mapped from the text summarization range between 0.46 and 0.75. The proposed version shows its better results in three of the four domains. It maintain its matching results in the domain, ‘medicine’. From this set of experiments, it is concluded that the proposed version have its better performance by averaging over the accuracies of the four domains.

5 Conclusion

Conclusion Let us discuss the results from summarizing texts using the two versions of KNN algorithm. In these sets of experiments, we compare the two versions with each other in the classification tasks which is mapped from the text summarizations. The proposed version shows its better results in all of the four collections. The classification accuracies of the traditional version range between 0.46 and 0.55, while those of the proposed version range between 0.52 and 0.70. From the four sets of experiments, we conclude that the proposed version improves the text summarization performance, as the contribution of this research.

We need to consider the remaining tasks for doing the further research. We will apply and validate the proposed approach in summarizing a text in the specific domains such as medicine, engineering, and law, rather than the general domains. In order to improve the performance, we may consider various types of features of string vectors. As another scheme of improving the performance, we define and combine multiple similarity measures between two string vectors with each other. By adopting the proposed approach, we may implement the text summarization system as a module or an independent system.

Footnotes

Acknowledgment

This work was supported by 2018 Hongik University Research Fund.

References

Abainia

, Ouamour

and Sayoud

, Neural Text Categorizer for topic identification of noisy Arabic Texts , Proceedings of 12th IEEE Conference on Computer Systems and Applications, 2015, pp. 1–8.

Baeza-Yates

and Ribeiro-Neto

, Modern Information , Retrieval: The Concepts and Technology behind Search, 2011Addison-Wesley.

Chuang

and Yang

, Extracting sentence segments for text summarization: a machine learning approach, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, 2000 pp. 152–159.

Firte

, Lemnaru

and Potolea

, Spam detection filter using KNN algorithm and resampling, Proceedings of IEEE International Conference on Intelligent Computer Communication and Processing, 2010 pp. 27–33.

Han

, Karypis

S.G.

and Kumar

, Text categorization using weight adjusted k-nearest neighbor classification, Proceedings of Pacific-Asia conference on knowledge discovery and data mining, 2001 pp. 53–65.

James

, Koprinska

and Poon

, A neural network based approach to automated e-mail classification, Proceedings of IEEE International Conferences on Web Intelligence, 2003 pp. 702–705.

, NeuroTextCategorizer: A New Model of Neural Network for Text Categorization, The Proceedings of ICONIP, (2000) pp. 280–285.

, The Implementation of Dynamic Document Organization using Text Categorization and Text Clustering, PhD Dissertation of University of Ottawa, 2006.

, Table based single pass algorithm for clustering news articles, International Journal of Fuzzy Logic and Intelligent Systems, 8 (2008) 231–237.

10.

, Neural text categorizer for exclusive text categorization, Journal of Information Processing Systems, 4 (2008) 77–86.

11.

, Modification of classification algorithm in favor of text categorization, International Journal of Computer Science and Software Technology, 2 (2009) 13–23.

12.

, Modification of clustering algorithms for text clustering, International Journal of Computer Science and Software Technology, 3 (2010) 21–33.

13.

, NTC (Neural Text Categorizer): Neural network for text categorization, International Journal of Information Studies, 2 (2010) 83–96.

14.

, NTSO (Neural Text Self Organizer): A new neural network for text clustering, Journal of Network Technology, 1 (2010) 31–43.

15.

, Device and Method for Categorizing Electronic Document Automatically, 10-2009-0041272, 10-1071495, 2011.

16.

, Normalized table matching algorithm as approach to text categorization, Soft Computing, 19 (2015) 839–849.

17.

, Simulation of numerical semantic operations on string in text collection, International Journal of Applied Engineering Research, 10 (2015) 45585–45591.

18.

and Cho

, Index based approach for text categorization, International Journal of Mathematics and Computers in Simulation, 2 (2008) 127–132.

19.

and Japkowicz

, Text Clustering using NTSO, The Proceedings of IJCNN, (2005) pp. 558–563.

20.

Kate

R.J.

and Mooney

R.J.

, Using String Kernels for Learning Semantic Parsers, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006 pp. 913–920.

21.

Khan

, Baharudin

, Lee

L.H.

and Khan

, A review of machine learning algorithms for text-documents classification, Journal of Advances in Information Technology, 1 (2010) 4–20.

22.

Kim

, Zhang

and Kim

Y.T.

, Collocation dictionary optimization using WordNet and k-nearest neighbor learning, Machine Translation, 16 (2001) 199–108.

23.

Lai

and Tsai

, An empirical performance comparison of machine learning methods for spam e-mail categorization, Proceedings of IEEE International Conference on Hybrid Intelligent Systems, (2004) pp. 44–48.

24.

Leslie

C.S.

, Eskin

, Cohen

, Weston

and Noble

W.S.

, Mismatch string kernels for discriminative protein classification, Bioinformatics, 20 (2004) 467–476.

25.

Lodhi

, Saunders

, Shawe-Taylor

, Cristianini

and Watkins

, Text classification with string kernels, Journal of Machine Learning Research, 2 (2002) 419–444.

26.

Manning

C.D.

and Schutze

, Foundations of Statistical Natural Language Processing, MIT Press, 1999.

27.

Mitchell

, Machine Learning, 1st ed., McGraw-Hill, 1997.

28.

Pawar

P.Y.

, Gawande

S.H.

, A comparative study on different types of approaches to text categorization, International Journal of Machine Learning and Computing, 2 (2012) 423–426.

29.

Pekar

and Staab

, Word classification based on combined measures of distributional and semantic similarity, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, 2003 pp. 147–150.

30.

Sebastiani

, Machine learning in automated text categorization, ACM Computing Survey, (2002) pp. 1–47.

31.

Stauffer

, Fischer

and Riesen

, A novel graph database for handwritten word images, Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition, (2016) pp. 553–563.

32.

Vishwanath

, Kumar

, Kumari

and Pascual

, KNN based machine learning approach for text and document mining, International Journal of Database Theory and Application, 7 (2014) 61–70.

33.

D.Wiener

, A Neural Network Approach to Topic Spotting in Text. Master Thesis, the Faculty of the Graduate School of the University of Colorado. 1995.

34.

Yang

, An evaluation of statistical approaches to text categorization, Information Retrieval, 1 (1999) 69–90.

35.

Zheng

, Cheng

, Huang

and Man

, A comparative study on text clustering methods, Advanced Data Mining and Applications, (2006) 644–651.