RU2251148C1 - Method for stream processing of text messages - Google Patents

Abstract

FIELD: computer science.

SUBSTANCE: method includes text messages from data channel, linguistic words processing is performed, thesaurus of each text message is formed, statistical processing of words in thesaurus is performed, text message and thesaurus are stored in storage. Membership of text message in one of categories from the list is determined, starting data value of text message is determined, stored in storage with text message, data value values are periodically updated with consideration of time passed since their appearance and text messages with data value below preset threshold are erased, during processing of each message values of categories classification signs are updated.

EFFECT: higher efficiency.

1 dwg

Description

The invention relates to text message classification systems and can be used in information processing systems, databases, electronic repositories in the presence of a constant source of text information.

A known method of classifying messages [1], which consists in converting the message text from a special storage format into natural language text, converting the document words into basic word forms, and calculating the word weights in the document in accordance with the frequencies of their appearance; at the training stage, according to the presented set of manually classified documents, a set of classification features is formed, if necessary, the document is classified, it is converted from a special storage format into natural language text, the document is converted into basic word forms, the word weights in the document are calculated based on the SVM classification criterion (Support Vector Machines) and classification features determine whether a document belongs to a category.

However, this method has significant limitations in that it is intended only for classifying messages in static mode and does not contain means for stream processing, such as sequential training of the classifier, as well as evaluating the information content of a text message and the duration of its storage in the repository.

There is also known a method for classifying messages [2], which consists in continuously processing a sequence of text messages, updating at each stage the classification features according to the Widrow-Hoff method; this allows you to simultaneously classify messages and train the classifier. Moreover, there is no need to present the entire training set of documents at once.

However, this method also has limitations associated with the fact that it only describes the procedure for classifying messages and training the classifier and does not describe the complete cycle of processing a message in streaming mode, for example, the initial processing of a document and its storage, and also does not contain mechanisms for evaluating the information content of a text message and the duration of its storage.

The closest in technical essence to the proposed one is a method for identifying objects according to their descriptions [3], suitable for solving the problem, adopted as a prototype, which consists in the fact that they receive text messages in natural languages from an information channel, carry out linguistic processing of the words of each message, form the thesaurus of the text of each message, carry out statistical processing of words in the message thesaurus, save the text message and thesaurus in the repository.

This method allows you to compare this text message with the set of messages received over time intervals, and thereby determine its thematic proximity to these intervals as categories. The disadvantages of the prototype are the impossibility of defining categories other than on a temporary basis, as well as the lack of mechanisms for evaluating the information content of a text message and removing it from the store when it loses its information content.

The technical result obtained from the implementation of the invention is to eliminate the disadvantages of the prototype, that is, to obtain the possibility of arbitrary assignment of categories. Moreover, for each text message, its information content is determined, which affects the duration of storage of this message in the repository.

This technical result is obtained due to the fact that they receive text messages in natural languages from the information channel, carry out linguistic processing of the words of each message, form a thesaurus of the text of each message, perform statistical processing of words in the message thesaurus, save the text message and thesaurus in the repository. In this case, the text message belonging to one category is automatically determined from a predetermined list of categories. In addition, the initial information content of the text message is additionally determined, it is stored in the storage together with the text message; periodically update the informative values of text messages stored in the database, taking into account the elapsed time since their appearance, and delete those text messages whose information content dropped below a predetermined threshold. An additional feature of this method is that when processing each text message, the values of the classification features of the categories are updated.

According to this method, the information content of a text message is determined by two factors:

- the content of the message (word forms included in it, the deviation of the vocabulary of the message from previously encountered);

- time elapsed since the moment the message was entered into the database.

The values of classification features are determined by the distribution of the weights of word forms most often found in messages of this category. For each text message and each category, a membership function is defined that characterizes the measure of membership of a given message in this category. The category for which the value of this function is maximum is assigned to the message. Moreover, in the case of small values of the membership function of a message of this category, the message has an uncharacteristic vocabulary and, in accordance with this method, is assigned a higher value of information content than messages that deliver large to this function.

Immediately after the message enters the database, the message has, in accordance with this method, the maximum information content, since it is most likely has not yet been read and evaluated by the operators of the message processing complex. However, after some time, the information content of the message decreases.

In accordance with the patented method, each text message s that got into the database is assigned an informative value at each time moment t according to the following formula, which is consistent with the reasoning given above:

I (s) = 1- (x (s), c _k ) -α (tt ₀ ),

where x (s) is the weight vector of the word thesaurus wordforms of the message s, c _k is the vector of classification features of category k to which the text message s belongs, t ₀ is the time when message s entered the database, α is the information loss coefficient. The values of t and t ₀ can be expressed in any time units, for example, in seconds. The choice of specific time units will only affect the value of the coefficient α.

The coefficient α is responsible for reducing the information content of the message per unit time and is selected taking into account the requirements of specific applications of this method.

As the information content of messages falls below the information threshold ε, they are removed from the database as uninformative.

At the same time, messages that received the highest informative values from the very beginning will be more in the database; the same ones that were initially uninformative will be deleted faster from the database.

The method can be implemented using a computer or a computing device, presented in the form of a block diagram in the drawing.

A device for implementing the method consists of an information channel 1, block 2 for generating text message thesauruses, control block 3, block 4 for training data, block 5 for classification, block 6 for determining the initial information content of text messages, block 7 for saving text messages, storage 8 for text messages, block 9 updates of classification features, storage of 10 classification features, block 11 for generating time samples, block 12 for recalculating the informativeness of text messages, block 13 for deleting texts x messages.

According to the method, the device operates as follows. When a text message appears in information channel 1, it is transmitted to block 2.

In block 2, the text message first undergoes preliminary processing, which consists in determining all basic words of their basic word forms. One of the methods [4-7] can be used for this, after which a text message thesaurus is generated. Most often, to solve the problems of finding basic word forms, the Porter algorithm [4] is used, which consists in using special rules for cutting off and replacing word endings.

The message thesaurus consists of all word forms contained in it. In this case, each word form is associated with its normalized weight in the message text, determined by the formula TD-IDF (Term Frequency-Inverted Document Frequency):

tdidf (w) = tf (w) idf (w),

where tf (w) is the frequency of occurrence of the word form w in this message, i.e.

Here c (w) is the number of times the word form w is repeated in this message, N is the total number of words in this message. The value of the inverted frequency of documents idf (w) is calculated by the formula:

idf (w) = log (M) -log (d (w)),

where d (w) is the number of documents known to the system in which the word form w occurs, M is the total number of documents known to the system. To normalize the vector of weights, the Euclidean norm is used:

Next, the generated text message thesaurus is sent to the control unit 3, controlled by the device operator. The control unit 3 allows the device to operate in two modes: in the initial learning mode and normal mode. The mode of primary education is necessary to build the initial classification features. In this mode, the control device receives information about the category to which the text message belongs from block 4. In normal operation, the control block refers to block 5 to determine the category to which the text message belongs.

When classifying a text message, the scalar product is calculated between the normalized vector of the message weights and the weight vectors (classification features) of all categories. Since these vectors are normalized, the scalar product of these vectors is equal to the cosine of the angle between the corresponding vectors in the corresponding multidimensional spaces. The category for which this scalar product will be maximal is assigned to this text message:

Information about this category is transferred from block 5 to control block 3 and then goes to the block for determining the initial informativeness of text messages.

To determine the initial information content of a text message, use the formula:

I (s) = 1- (x (s), c _k ),

where s is the current text message, x (s) is the weight vector of the word forms of the thesaurus of message s, c _k is the vector of classification features of category k to which the text message s belongs. In this case, the scalar product is calculated for all word forms from the intersection of the set of word forms of a given text message and classification signs of category k, and the vectors x (s) and c _k have components corresponding to the corresponding word forms.

From block 6 determining the initial informativeness of a text message, data about the current text message, namely the message itself, its thesaurus and initial informativeness, are sent to block 7, which stores them in storage 8.

Next, control is transferred to block 9. Classification signs corresponding to each category are weight vectors corresponding to all word forms found in any text message from this category. Vector scales are normalized in accordance with the Euclidean norm. The definition of classification features for each category is iterative. To do this, use the dynamic training algorithm for linear Widrow-Hoff classifiers (Widrow-Hoff). Classification signs of categories are extracted from the repository 10 and recalculated according to the formula:

c _{kj, new} = c _{kj, old} -2η ((with _{k, old} , x (s)) - y) x _j (s),

where with _{kj, old} and with _{kj, new} are je components of the old and new vectors of classification signs of the kth category, respectively, y is a vector with one at the position corresponding to the category number to which the text message s belongs, and the rest positions - zeros, η - learning rate coefficient specified by the device operator. Then the updated values of the classification features are entered back into the store 10.

Block 11 sends signals to block 12 with a constant time period specified by the device operator. Upon receipt of the signal, block 12 enumerates all the messages contained in the repository 8 and updates the values of their information contents in accordance with the following formula:

I (s) = I (s) -αΔt,

where α is the coefficient of loss of information content, Δt is the time period between consecutive signals of the unit for generating time samples. New values of informativeness are stored in the storage 8. The coefficient α is set by the device operator.

In block 13 for deleting text messages, all messages contained in the text message storage 8 are enumerated and all messages are deleted from it, the information content of which at the time of verification is lower than the information threshold ε, also set by the device operator.

The values of the coefficients α, η, ε can be different depending on the specific use of this device.

Thus, using the method, there is a classification of text messages on a predetermined set of categories, as well as determining the information content of a text message and deleting it as it loses its information content, thereby achieving the above technical result.

Sources of information taken into account when compiling the application materials:

1. US patent 6327581, cl. G 06 F 015/18.

2. Lewis DD, Shapire RE, Callan JP, Papka R. "Training algorithms for linear text classifiers", In Proceedings of SIGIR-96, 49th ACM International Conference on Research and Development in Information Retrieval, pages 294-306, Zurich, CH 1996.

3. RF patent No. 2167450 C2, class. G 06 F 17/30 - prototype.

4. Porter M.F. "An algorithm for suffix stripping". Program, Vol.14, No.3, 1980, pp. 130-137.

5. RF patent No. 2096825 C1, cl. G 06 F 17/00.

6. US patent No. 6308149, CL. G 06 F 17/27.

7. US patent No. 6430557, CL. G 06 F 017/30; G 06 F 017/27; G 06 F 017/21.

Claims (1)

A method of streaming processing text messages, which consists in receiving text messages in natural languages from an information channel, performing linguistic processing of the words of each message, forming a thesaurus of the text of each message, performing statistical processing of words in the message thesaurus, storing the text message and thesaurus in the repository, characterized in that they automatically determine whether a text message belongs to one category from a predetermined list of categories, while determine the initial information content of the text message, save it in the repository along with the text message; periodically update the information content values stored in the database of text messages taking into account the elapsed time since their appearance, and delete those text messages whose information content has dropped below a predetermined threshold; when processing each text message, the values of the classification features of the categories are updated.