JP5815468B2 - Spam classification model generation apparatus, method and program - Google Patents

Description

  The present invention relates to a spam classification model generation apparatus, method, and program, and more particularly, to a spam classification model generation apparatus, method, and program for discriminating spam documents.

  In a search system such as a web search system, when acquiring a search target document and making it searchable, a spam page that causes a reduction in user satisfaction may be determined in advance and removed. At this time, in order to cope with a large amount of spam pages created every day, a discriminator using a machine learning method based on an evaluation data set (hereinafter referred to as “training data”) labeled with spam and non-spam. There is a method of automatically generating (see Non-Patent Document 1, for example). In the present specification, the spam page is hereinafter referred to as spam, and the non-spam page is referred to as ham.

  There are two misclassifications in spam classification: False Negativ (FN) error that misclassifies spam as ham, and False Positive (FP) error that misclassifies ham as spam. In a normal service operation method, spam-determined data is removed from the search target, so that an FP error that misclassifies a document that is ham as spam is very lossy.

  In addition, when acquiring the target data for creating the evaluation data set, since the spam and ham labels are not known in advance, the number of cases of spam and ham in the training data generally tends to be biased.

G. V. Cormack, "Content-based web spam detection", In Proceedings of the 3rd International workshop on Adversarial Information Retrieval on the Web (AIRWeb '07), 2007.

  As described above, the conventional spam classifier generation method does not consider the number of ham and spam cases in the given training data, so when the number of cases is biased, the spam classifier is generated appropriately. could not. In addition, since the loss was set equally for the case error, the FP error could not be kept low with respect to the FN error. Therefore, there is a problem that it is difficult to generate a highly accurate spam classification model with a low FP error.

  The present invention has been made in view of the above points, and provides a spam classification model generation apparatus, method, and program capable of appropriately generating a spam discrimination model even with training data with biased cases. With the goal.

In order to solve the above problems, the present invention (Claim 1) is a spam classification model generation device for discriminating spam documents,
When a case that has a spam label and a feature vector of either a spam page (spam) or a non-spam page (ham) that is subject to spam determination is input, the case is determined according to the size of the margin set in advance for each class. The loss of the case is calculated, and the combination of the loss value and case information is stored in the spam label array or the ham label array according to the spam label, and the case with the maximum loss from each label array is stored in the label. spam of removing from the array, the loss extracts a feature vector of the maximum case, updates the polymerization viewed vector using the feature vector and stores the updated heavy viewed vector spam classification model storing means A classification model generation means;
A classification data storage means for storing a feature vector for each case of spam discrimination;
A spam score is calculated using the weight vector of the spam classification model storage means and the feature vector of the classification data storage means. If the spam score is equal to or greater than a predetermined threshold, it is determined as spam and is smaller than the threshold In this case, it is determined to be ham, and spam classification means for outputting the determination result is included.

Further, the present invention (Claim 2) provides the spam classification model generating means,
When calculating the loss of the case,
Means for updating the case so that the error is zero and the change amount of the L2 norm of the weight vector is minimized;

Further, the present invention (Claim 3) is the spam classification model generating means,
Case selection means for selecting the same number of cases with the same maximum loss from the spam label array and the ham label array.

Further, the present invention (Claim 4) is the case selecting means,
Each time the weight vector is updated, an update count counter is incremented, and when the value of the update count counter is an even number, means for extracting a case from the spam label array, and when odd, from the ham label array Including.

  As described above, according to the present invention, it is possible to generate a spam discrimination model even using training data with biased cases. In addition, it is possible to give different importance to non-spam cases and spam cases, and even when training data is biased, it is highly accurate with low FP errors that misclassify non-spam cases as spam. A spam classifier can be generated.

It is a block diagram of the spam classification production | generation apparatus in one embodiment of this invention. It is an image of the update of the weight in one embodiment of this invention. It is a flowchart of the process of the spam classification model production | generation part in one embodiment of this invention. It is a flowchart of the process of the spam classification part in one embodiment of this invention.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 1 shows a configuration of a spam classification model generation device according to an embodiment of the present invention.

  The spam classification model generation apparatus shown in the figure includes a spam training data DB 10, a spam classification model generation unit 20, a spam classification model DB 30, a spam classification unit 40, a classification data DB 50, and a prediction label DB 60.

  The spam training data DB 10, the spam classification model DB 30, the classification data DB 50, and the prediction label DB 60 are storage media such as a hard disk.

  The spam classification model generation unit 20 reads the spam training data in the spam training data DB 10 and outputs the spam classification model to the spam classification model DB 30.

  An example of the data structure of the spam training data DB 10 is shown in Table 1.

スパム訓練データＤＢ１０は、1レコードに1事例の訓練データを格納しており、事例ＩＤ，スパムラベルと特徴ベクトルのカラムで構成されている。ここで「事例」とは、スパム判定の単位である文書のことを表し、判定されたスパムラベルｙと、Ｍ次元の特徴ベクトルｘ^T=(x₁，x₂，…，ｘ_M)の情報を持つ。スパムラベルｙ∈｛＋１，−１｝は、spamの場合＋１、hamの場合−１とする。表１では、"spam"、"ham"で表している。特徴ベクトルには例えば、当該ページに含まれている単語情報やリンク情報などを用いる。特徴ベクトルの各カラムは、当該事例の特徴ベクトルの値を格納している。

The spam training data DB 10 stores one case of training data in one record, and includes a column of case IDs, spam labels, and feature vectors. Here, “example” represents a document that is a unit of spam determination, and information of the determined spam label y and M-dimensional feature vector x ^T = (x ₁ , x ₂ ,..., X _M ). have. The spam label yε {+ 1, −1} is +1 for spam and −1 for ham. In Table 1, “spam” and “ham” are used. For example, word information or link information included in the page is used as the feature vector. Each column of the feature vector stores the value of the feature vector of the case.

  An example of the data structure of the spam classification model DB 30 is shown in Table 2.

スパム分類モデルＤＢ３０は、事例の特徴ベクトルの次元数と同じ次元数である重みベクトルｗ^T=(w₁，w₂，…，ｗ_M)の情報を格納しており、ｗ_iが特徴ｘ_iに対する重みである。

The spam classification model DB 30 stores information of weight vectors w ^T = (w ₁ , w ₂ ,..., W _M ) having the same number of dimensions as the feature vector of the case, and w _i is a feature x _i. Is a weight for.

  The spam classification model generation unit 20 changes the margin by setting the error to 0 for the case read from the spam training data DB 10 and updating the weight parameter so that the change amount of the L2 norm of the weight vector is minimized. An image of updating the weight parameters is shown in FIG. In the figure, an example is shown in which the weight parameter is updated so that the loss becomes 0 for the input example (training data).

  In the spam classification model generation unit 20, a positive example margin size E (+1), a negative example margin size E (-1), a cost parameter C, the number of iterations n, the number of selected samples u, and a threshold t for output are set in advance for the system. Suppose that it is set.

  FIG. 3 is a flowchart of the process of the spam classification model generation unit in one embodiment of the present invention.

Step 101) The spam classification model generation unit 20 initializes the weight vector w. If there is no prior setting, let w ^T = (0, 0,..., 0). In addition, the update counter is initialized and i ← 0.

  Step 102) For all cases included in the spam training data DB 10, the loss is calculated based on the current weight vector. The loss for a case (x, y) is calculated using the margin E (y) considering the label.

と求めることができる。上記では、予めクラス毎に設定されたマージンの大きさ（E(y)）に応じて損失の計算を行っている。

It can be asked. In the above, the loss is calculated according to the margin size (E (y)) set in advance for each class.

Then, the loss value and case information pair (l ⁽ⁱ⁾ , x ⁽ⁱ⁾ , y ⁽ⁱ⁾ ) calculated by the equation (1) is stored in an array corresponding to the label. In the case of y = + 1, that is, in the case of spam, it is stored in the array for spam. In the case of y = −1, that is, in the case of ham, it is stored in the array for ham. In order to select the case with the maximum loss in step 104 using this arrangement, it is computationally efficient to store data using a data structure such as a peep tree. Each array is stored in a memory (not shown).

  Step 103) The selected example counter j is initialized and j ← 0.

Step 104) If i mod 2 = 0, that is, if the update count counter i for updating the weight vector is an even number, a case with the greatest loss is obtained from the spam array, and the case is removed from the spam array. . In other cases, that is, when the update count counter is an odd number, a case with the maximum loss is obtained from the ham array, and the case is removed from the ham array. Let the loss of the case selected here be l _t , the label be y _t , and the feature vector be x. By performing the process, it is possible to eliminate the influence of the uneven number of cases.

  Step 105) Update the weight vector based on the selected case. The update of the weight vector is described in, for example, the literature “K. Crammer, O. Dekel, J. Keshet, SS-Shwartz and Y. Singer,“ Online Passive-Aggressive Algorithm ”, Journal of Machine Learning, vol. 7, pp. 551- 585, 2006. "

で計算することができる。ここで、

Can be calculated with here,

である。ここで‖ｘ‖は特徴ベクトルのL2ノルムを表し、

It is. Where ‖x‖ represents the L2 norm of the feature vector,

で計算できる。

It can be calculated with

  Step 106) The counter is updated so that i ← i + 1 and j ← j + 1.

  Step 107) If j <u and i <n, return to Step 104; otherwise, go to Step 108. Here, u and n are predetermined parameters (constants), and the relationship between u and n is empirically u << n.

  Step 108) If i <n, return to Step 102. Otherwise, the process proceeds to step 109.

  Step 109) The weight vector w is output to the spam classification model DB 30, and the process is terminated.

  The spam classification unit 40 receives the data of the classification data DB 50 as an input, and outputs the spam classification result to the prediction label DB 60. At that time, it is possible to sequentially receive data corresponding to one record of the classification data DB 50 and sequentially output a result corresponding to one record of the prediction label DB 60.

  Table 3 shows the data structure of the classification data DB 50.

分類データＤＢ５０は、スパム判別を行う対象のデータを格納しており、事例ＩＤと特長ベクトルｘの特徴を格納している。分類データＤＢ５０のデータベーススキーマは、スパム訓練データ１０からラベルカラムを除いたものとなる。

The classification data DB 50 stores data to be subjected to spam discrimination, and stores case IDs and features of feature vectors x. The database schema of the classification data DB 50 is obtained by removing the label column from the spam training data 10.

  An example of the data structure of the prediction label DB 60 is shown in Table 4.

予測ラベルＤＢ６０は、入力された各事例に対して予測ラベルと予測スコアの情報を格納している。

The prediction label DB 60 stores information on a prediction label and a prediction score for each input case.

  FIG. 3 is a flowchart of the processing of the spam classification unit according to the embodiment of the present invention.

Step 201) The spam classification unit 40 acquires weight vector information from the spam classification model DB 30 and sets it as an M-dimensional weight vector w ^T = (w ₁ , w ₂ ,..., W _M ).

Step 202) Acquire unprocessed data from the classification data DB 50 and set it as an M-dimensional feature vector x = (x ₁ , x ₂ ,..., X _M ).

  Step 203) Using the weight vector acquired in Step 201 and the feature vector acquired from Step 202, the spam score s is calculated.

に従って計算する。

Calculate according to

  Step 204) If the spam score s is greater than or equal to a threshold set in the system in advance, it is determined as spam, and otherwise it is determined as ham. The determined prediction label

とする。

And

  Step 205) Case ID, spam score s and prediction label for the case

を、予測ラベルＤＢ６０に出力する。

Is output to the prediction label DB 60.

  Step 206) If there is unprocessed data in the classification data DB 50, the process returns to Step 202, and if not, the process ends.

  By performing the above processing, it is possible to suppress the adverse effect of misclassifying ham as spam even when training data is biased, and to realize highly accurate spam classification with FP errors suppressed. Is possible.

  In addition, the operation | movement of each component of the spam classification model production | generation apparatus in said embodiment is constructed | assembled as a program, installed in the computer utilized as a spam classification model production | generation apparatus, is made to execute, or distribute | circulates via a network It is possible.

  The present invention is not limited to the above-described embodiments, and various modifications and applications are possible within the scope of the claims.

10 Spam training data DB
20 Spam classification model generator 30 Spam classification model DB
40 Spam classification section 50 Classification data DB
60 prediction label DB

Claims (8)

A spam classification model generation device for discriminating spam documents,
When a case that has a spam label and a feature vector of either a spam page (spam) or a non-spam page (ham) that is subject to spam determination is input, the case is determined according to the size of the margin set for each class. The loss value and case information pair are stored in the spam label array or ham label array according to the spam label, and the case with the greatest loss is removed from the label array, the loss extracts a feature vector of the maximum case, and spam classification model generating means updates the heavy look vector, and stores the updated heavy viewed vector spam classification model storing unit by using the feature vectors,
A classification data storage means storing a feature vector for each case of spam discrimination;
A spam score is calculated using the weight vector of the spam classification model storage means and the feature vector of the classification data storage means. If the spam score is equal to or greater than a predetermined threshold, it is determined as spam and is smaller than the threshold In the case, it is determined as ham and spam classification means for outputting the determination result;
A spam classification model generation device characterized by comprising: The spam classification model generation means includes:
When calculating the loss of the case,
The spam classification model generation apparatus according to claim 1, further comprising means for updating the case so that an error is 0 and an amount of change in the L2 norm of the weight vector is minimized. The spam classification model generation means includes:
2. The spam classification model generation apparatus according to claim 1, further comprising: case selecting means for selecting the same number of cases with the same number of losses from the spam label array and the ham label array. The case selection means includes:
Each time the weight vector is updated, an update count counter is incremented, and when the value of the update count counter is an even number, means for extracting a case from the spam label array, and when odd, from the ham label array The spam classification model generation device according to claim 3 including. A spam classification model generation method for discriminating spam documents,
When the spam classification model generation means inputs a case with a spam label and a feature vector of either a spam page (spam) or a non-spam page (ham) that is subject to spam determination, the margin set for each class The loss of the case is calculated according to the size, and the combination of the loss value and the case information is stored in an array of spam labels or an array of ham labels according to the spam label. removed from the array of labels, the loss extracts a feature vector of the maximum case, updates the polymerization viewed vector using the feature vector and stores the updated heavy viewed vector spam classification model storing means A spam classification model generation step;
A spam classification unit calculates a spam score using the weight vector of the spam classification model storage unit and the feature vector of the classification data storage unit that stores a feature vector for each case of spam discrimination target, and the spam score Is determined to be spam if it is greater than or equal to a predetermined threshold, ham if it is less than the threshold, and a spam classification step that outputs the determination result;
A spam classification model generation method characterized by: In the spam classification model generation step,
The spam classification model generation method according to claim 5, wherein, when calculating the loss of the case, the update is performed such that an error is set to 0 for the case and the change amount of the L2 norm of the weight vector is minimized. In the spam classification model generation step,
6. The spam classification model generation method according to claim 5, wherein the same number of cases with the same loss is selected from the spam label array and the ham label array. Computer
The spam classification model production | generation program for functioning as each means of the spam classification model production | generation apparatus of any one of Claims 1 thru | or 4.

Images