CN105512311B - An Adaptive Feature Selection Method Based on Chi-square Statistics - Google Patents

Abstract

An adaptive feature selection method based on chi-square statistics. The method relates to the field of computer text data processing. First, the training text set and the test text set are preprocessed, including word segmentation and stop word processing. Adaptive text feature selection, define word frequency factor and inter-class variance, introduce them into the CHI algorithm, add appropriate scale factors to the CHI algorithm, and finally combine the evaluation indicators of the classic KNN algorithm to automatically adjust the scale factor, so that the improved CHI is suitable for Different corpora to ensure high classification accuracy. The experimental results show that compared with the traditional CHI method, the classification accuracy of the present invention is improved for both balanced corpus and unbalanced corpus respectively.

Description

An Adaptive Feature Selection Method Based on Chi-square Statistics

technical field

The invention relates to the field of computer text data processing, in particular to an adaptive text feature selection method based on chi-square statistics (χ ² , CHI).

Background technique

In today's era of big data, it is very important to mine the potential value of data. As a technology for discovering the potential value of data, data mining has attracted great attention. Text data accounts for a considerable proportion of big data, and text classification, as a data mining method to effectively organize and manage text data, has gradually become a hot spot of attention. It has been widely used in information filtering, information organization and management, information retrieval, digital library and spam filtering. Text Classification (TC) refers to the process of automatically classifying unknown category texts into one or more categories according to their content under a predetermined category system. Commonly used text classification methods, such as K-Nearest-Neighbor (KNN), Bayesian (Naive Bayes, NB) and Support Vector Machine (SVM) and so on.

The current text classification process includes preprocessing, feature dimensionality reduction, text representation, classifier learning and evaluation. The most commonly used text representation is the vector space model. The high dimensionality and sparsity of the vector space increase the time and space complexity. It greatly affects the accuracy of text classification, so the feature dimensionality reduction process is very important, which directly affects the efficiency and accuracy of classification. Feature dimensionality reduction mainly includes two methods—Feature Extraction and Feature Selection. Linguistic-based feature extraction requires natural language processing technology and high computational complexity, while feature selection method based on statistical theory The complexity is low and does not require too much background knowledge, so the feature selection method is more widely used. The basic idea of feature selection is to construct an evaluation function, evaluate and score each feature item of the feature set, sort all feature items according to the evaluation score, and select a specific number of features as the final text feature set. Commonly used feature selection methods are chi-square statistics, document frequency (Document Frequency, DF), information gain (Information Gain, IG), mutual information (Mutual Information, MI), expected cross entropy (Expected Cross Entropy, ECE) and text evidence weight (Weight of Evidence, WE) etc.

As one of the commonly used text feature selection methods, the CHI method has the characteristics of simple implementation and low time complexity; however, it also has many shortcomings, so that the classification effect is not ideal. The shortcomings of the CHI algorithm mainly include two aspects: first, CHI only considers the document frequency of feature items, ignoring the word frequency of feature items, resulting in the weight of low-frequency words being amplified; The weights of feature items that are many and often appear in other classes. In view of the shortcomings of the CHI algorithm, many researchers have improved it and summarized the improvement methods into the following two aspects: First, a number of adjustment parameters are introduced to reduce the reliance on low-frequency words, but the method does not consider the relationship between feature items and categories. positive and negative correlations between. Second, a scale factor α is introduced, which is classified according to its positive and negative correlations and assigned different weights to improve the feature selection ability of the CHI model, but the scale factor needs to be selected through experience. Considering the shortcomings of various CHI improved algorithms, it is of great academic significance and practical value to design a CHI text feature selection method with high classification accuracy.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide an improved CHI text feature selection method, thereby improving the accuracy of text classification. On the one hand, this paper introduces the word frequency factor and inter-class variance to reduce the CHI's reliance on low-frequency words, and selects the feature items that appear frequently in a specific class and are evenly distributed in this class; on the other hand, an adaptive scale factor μ is introduced to Classify according to their positive and negative correlations and assign different weights to reduce the error caused by artificial selection of scale factors.

The features of the present invention are as follows:

Step 1, download the Chinese corpus released by Fudan University from the Internet - the training text set and the test text set;

Step 2, using ICTCLAS, an open source word segmentation software of the Chinese Academy of Sciences, to perform preprocessing such as word segmentation and stop word removal on the training text set and the test text set, and obtain the training text set and test text set after word segmentation;

Step 3, adopt the adaptive text feature selection method based on CHI to perform feature selection on the training text set after word segmentation, and obtain the feature vocabulary corresponding to the training text set;

The calculation formula of the traditional CHI text feature selection method is as follows:

Among them, A represents the number of documents that contain feature t _k and belong to category C _i , B represents the number of documents that contain feature t _k but does not belong to category C _i , C represents the number of documents that do not contain feature t _k and belong to category C _i , D represents the number of documents that do not contain feature t _k and do not belong to category C _i .

An adaptive text feature selection method based on CHI is proposed, and the formula is as follows:

χ _new ² (t _k ,C _i )=[μ*χ ² (t _k ,C _i ) ⁺ +(1-μ)*χ ² (t _k ,C _i ) ^- ]*α*β

Among them, μ is the scale factor, α is the word frequency factor, and β is the between-class variance. The formulas of α and β are defined as follows:

Among them, m is the total number of categories in the training set, tf(t _k ,C _i ) represents the number of occurrences of the feature item t _k in the category C _i , Represents the number of times the feature item t _k appears in the entire training text set. In the training set, the category C _i contains p documents which are d _i1 , d _i2 ,...,d _ij ,...,d _ip , tf(t _k ,d _ij ) indicates that the feature item t _k is in the category C the number of occurrences of _i in the jth document, represents the total number of times the feature t _k appears in the category C _i , Represents the total number of times the feature item t _k appears in all documents in the entire training text set. The word frequency factor α represents the proportion of the word frequency that contains the feature item _tk in a specific class C _i to the word frequency of the entire training set _tk . The larger the α, the higher the frequency of the feature item in a specific class and the less or almost no appearance in other classes. Obviously, such a feature item has a higher ability to distinguish between categories; the smaller the α, the more the feature. Items appear less frequently in a particular class and more frequently appear in other classes. Obviously, such feature items have a weaker class discrimination ability.

in, m represents the number of categories, df _i is the number of documents containing t _k in category C _i , is the average number of documents containing t _k per category, Indicates that the number of texts in which the feature word appears in a particular class is greater than or equal to the average Indicates that the number of texts in which the feature word appears in a particular class is less than the average The β value is used to measure the degree of deviation between the frequency of documents containing feature words in a certain class and the average of document frequencies of all classes. The larger the β is, it means that the number of documents containing the feature word t _k in the category C _i is larger than the average of the number of documents containing the feature word t _k in all classes, and it is much larger, and such a feature item has a higher category discrimination ability. .

In step 4, each training text and each test text are represented by the feature words of the feature vocabulary as a vector form, and the weight of each dimension is calculated according to TFIDF=TF×IDF, and TF (Term Frequency) is the word frequency, which refers to the feature. The number of times the item appears in the document, IDF (Inverse Document) is the inverse document frequency, the formula is IDF=log(M/n _k +0.01), M is the number of texts contained in the document collection, and n _k represents the document containing the word number;

Step 5, perform KNN classification;

The training text set is S, the test text is d, n is the feature vector dimension threshold, and K is 35.

Step 5.1, use the cosine value of the included angle of the vector to calculate the similarity between the test text d and all the texts in S;

Step 5.2, select the K texts with the largest similarity obtained in step 5.1 as the K nearest neighbor texts of the test text d;

Step 5.3: Calculate the weight of the test text d belonging to each category, and assign the test text d to the category with the largest weight.

Let the known category of the training text d _i be C _j , the weight calculation formula is as follows:

Among them, Sim(d, d _i ) is the cosine similarity between the test text d and the known category text d _i , and the formula is as follows:

Among them, n is the feature vector dimension threshold, X _j represents the weight of the j-th dimension of the text d to be tested (0<j≤n), and x _ij represents the weight of the j-th dimension of the training text vector d _i .

y(d _i , C _j ) is the category attribute function, the formula is as follows:

Step 6: Calculate the precision, recall and F ₁ value of the KNN classification algorithm, and obtain the final scale factor by setting the maximum threshold of the difference between the F ₁ values of the two classification results before and after, and the step size of the scale factor μ growth. value of μ to ensure high classification accuracy.

Step 6.1, set the initial F ₁ value to 0, the initial μ value to 0.5, ε=0.0001 is the threshold of the difference between the two F ₁ before and after, and τ=0.05 is the step size of the scaling factor μ increase;

Step 6.2, repeat step 5 to obtain the value of F ₁ ′, and obtain the difference ΔF=|F ₁ ′-F ₁ | between the two F ₁ before and after;

Step 6.3, if ΔF is less than ε, obtain the scale factor μ at this time; if ΔF is greater than or equal to ε, then let μ′=μ+τ, F ₁ =F ₁ ′, repeat steps 6.2 and 6.3 until a suitable The scale factor μ.

Compared with the prior art, the present invention has the following beneficial effects.

The present invention proposes an adaptive feature selection method based on chi-square statistics. The classification algorithm selects the KNN algorithm for classifying the test text. The flow chart of the whole process is shown in Figure 1, and the flow chart of calculating the scale factor μ is shown in Figure 2. The accuracy indicators of the corpus are shown in Table 1, and the accuracy of the unbalanced corpus is shown in Table 2. Compared with the traditional CHI method, on the one hand, this paper introduces the word frequency factor and the inter-class variance to reduce the CHI's reliance on low-frequency words, and selects the feature items that appear frequently in a specific class and are evenly distributed in this class; An adaptive scale factor μ is introduced to classify and assign different weights according to its positive and negative correlations, and this method is suitable for corpora with different distributions, thereby reducing the error caused by artificial selection of scale factors. It can be seen from Table 1 and Table 2 that compared with the traditional CHI method, the classification accuracy of the present invention is improved for both balanced corpus and unbalanced corpus respectively.

Description of drawings

Figure 1 is a flow diagram of the general process of the present invention.

FIG. 2 is a flow chart of calculating the scale factor μ according to the present invention.

Detailed ways

The present invention adopts the following technical means to realize:

An adaptive text feature selection method based on chi-square statistics. First, perform preprocessing of training text set and test text set, including word segmentation and stop word processing. Second, perform adaptive text feature selection based on chi-square statistics, define word frequency factor α and inter-class variance β, and introduce them into CHI Algorithm, adding a suitable scale factor μ for the CHI algorithm, and finally, combined with the classical KNN algorithm, automatically adjust the scale factor μ, so that the improved CHI is suitable for different corpora to ensure higher classification accuracy.

The above-mentioned adaptive text feature selection method based on chi-square statistics is used for text classification, including the following steps:

Step 1, download the Chinese corpus released by Fudan University from the Internet - the training text set and the test text set;

Step 2, using the word segmentation software ICTCLAS to perform preprocessing such as word segmentation and stop word removal on the training text set and the test text set, and obtain the training text set and the test text set after word segmentation;

Step 3, adopt the adaptive text feature selection method based on CHI to perform feature selection on the training text set after word segmentation, and obtain the feature vocabulary corresponding to the training text set;

The calculation formula of the traditional CHI text feature selection method is as follows:

Among them, A represents the number of documents that contain feature t _k and belong to category C _i , B represents the number of documents that contain feature t _k but does not belong to category C _i , C represents the number of documents that do not contain feature t _k and belong to category C _i , D represents the number of documents that do not contain feature t _k and do not belong to category C _i .

An adaptive text feature selection method based on CHI is proposed, and the formula is as follows:

χ _new ² (t _k ,C _i )=[μ*χ ² (t _k ,C _i ) ⁺ +(1-μ)*χ ² (t _k ,C _i ) ^- ]*α*β (2)

Among them, μ is the adaptive factor, α is the word frequency factor, and β is the inter-class variance. The formulas of α and β are defined as follows:

Among them, m is the total number of categories in the training set, tf(t _k , C _i ) represents the number of occurrences of the feature item t _k of the category C _i , Represents the number of times the feature item t appears in the entire training text set. The category C _i in the training set contains n documents, which are d _i1 , d _i2 ,...,d _ij ,...,d _in , tf(t _k ,d _ij ) indicates that the feature item t _k is in the category C the number of occurrences of _i in the jth document, represents the total number of times the feature t _k appears in the category C _i , Represents the total number of times the feature item t _k appears in all documents in the entire training text set. The word frequency factor α represents the proportion of the word frequency that contains the feature item t _k in a specific class to the word frequency of the entire training set t _k . The larger the α, the higher the frequency of the feature item in a specific class and the less or almost no appearance in other classes. Obviously, such a feature item has a higher ability to distinguish between categories; the smaller the α, the more the feature. Items appear less frequently in a particular class and more frequently appear in other classes. Obviously, such feature items have a weaker class discrimination ability.

in, m represents the number of categories, df _i is the number of documents containing t _k in category C _i , is the average number of documents containing t _k per category, Indicates that the number of texts in which the feature word appears in a particular class is greater than or equal to the average Indicates that the number of texts in which the feature word appears in a particular class is less than the average The β value is used to measure the degree of deviation between the frequency of documents containing feature words in a certain class and the average of document frequencies of all classes. The larger the β is, it means that the number of documents containing the feature word t _k in the category C _i is larger than the average of the number of documents containing the feature word t _k in all classes, and it is much larger, and such a feature item has a higher category discrimination ability. .

In step 4, each training text and each test text are represented by the feature words of the feature vocabulary as a vector form, and the weight of each dimension is calculated according to TFIDF=TF×IDF, and TF (Term Frequency) is the word frequency, which refers to the feature. The number of times the item appears in the document, IDF (Inverse Document) is the inverse document frequency, the formula is IDF=log(M/n _k +0.01), M is the number of texts contained in the document collection, and n _k represents the document containing the word number;

Step 5, perform KNN classification;

The training text set is S, the test text is d, n is the feature vector dimension threshold, and K is 35.

Use the cosine value of the angle between the vectors to calculate the similarity between the test text d and all the texts in S; select the K texts with the highest calculated similarity as the K nearest neighbors of the test text d; calculate the test text d belongs to The weight of each category, assigning the test text d to the category with the largest weight.

Let the known category of the training text d _i be C _j , the weight calculation formula is as follows:

Among them, Sim(d, d _i ) is the cosine similarity between the test text d and the known category text d _i , and the formula is as follows:

Among them, n is the feature vector dimension threshold, X _j represents the weight of the j-th dimension of the text d to be tested (0<j≤n), and x _ij represents the weight of the j-th dimension of the training text vector d _i .

y(d _i , C _j ) is the category attribute function, the formula is as follows:

Step 6: Calculate the precision, recall and F ₁ value of the KNN classification algorithm, and obtain the final scale factor by setting the maximum threshold of the difference between the F ₁ values of the two classification results before and after, and the step size of the scale factor μ growth. value of .

The initial value of F ₁ is set to 0, the initial value of μ is 0.5, ε=0.0001 is the threshold value of the difference between the two times of F ₁ before and after, and τ=0.05 is the step size of the increase of the scale factor μ.

Repeat step 5 to obtain the value of F ₁ ′, and obtain the difference ΔF=|F ₁ ′-F ₁ | between the two times of F ₁ before and after; if ΔF is less than ε, obtain the scale factor μ at this time; if ΔF is greater than or equal to ε , then let μ′=μ+τ, F ₁ =F ₁ ′, repeat the iteration of this step until a suitable scale factor μ is obtained to ensure higher classification accuracy.

Table 1 Comparison of results before and after algorithm improvement (balanced corpus) (%)

Table 2 Comparison of results before and after algorithm improvement (unbalanced corpus) (%)

Claims (1)

1. A chi-square statistic based adaptive feature selection method is characterized by comprising the following steps:

step 1, downloading a Chinese language database, namely a training text set and a test text set, issued by the university of Redandan from the Internet;

step 2, performing word segmentation and stop word removal pretreatment on the training text set and the test text set by using word segmentation software ICTCCLAS to obtain a training text set and a test text set after word segmentation;

step 3, performing feature selection on the training text set after word segmentation by adopting a CHI-based adaptive text feature selection method to obtain a feature word bank corresponding to the training text set;

the calculation formula of the traditional CHI text feature selection method is as follows:

wherein A represents the inclusion of a feature t_kAnd belong to class C_iB represents the number of documents including the feature t_kAnd do not belong to class C_iC represents that the feature t is not included_kAnd belong to class C_iD indicates that the feature t is not included_kAnd do not belong to class C_iThe number of documents;

a CHI-based adaptive text feature selection method is provided, and the formula is as follows:

χ_new ²(t_k,C_i)＝[μ*χ²(t_k,C_i)⁺+(1-μ)*χ²(t_k,C_i)^-]*α*β

wherein μ is a scale factor, α is a word frequency factor, β is an inter-class variance, and the formulas α and β are defined as follows:

where m is the total number of training set classes, tf (t)_k,C_i) Represents class C_iMiddle feature item t_kThe number of times of occurrence of the event,representing a feature item t_kThe number of occurrences in the entire training text set; class C in the training set_iIn which p documents are respectively d_i1,d_i2,...,d_ij,...,d_ip，tf(t_k,d_ij) Representing a feature item t_kIn class C_iThe number of occurrences in the jth document of (1),represents a feature t_kIn class C_iThe total number of occurrences in (a),representing a feature item t_kTotal number of occurrences in all documents in the entire training text set, word frequency factor α indicating the occurrence in a particular class C_iIncluding a feature item t_kThe number of word frequencies of t is in the whole training set_kα is larger, the characteristic item has higher frequency of occurrence in a specific class and has less or almost no frequency of occurrence in other classes, obviously the characteristic item has higher class distinguishing capability, α is smaller, the characteristic item has lower frequency of occurrence in the specific class and has higher frequency of occurrence in other classes, obviously the characteristic item has weaker class distinguishing capability;

wherein,m represents the number of classes, df_iIs of class C_iIn contains t_kThe number of documents in the document file(s),including t for each class on average_kThe number of documents in the document file(s),the number of texts indicating that the feature words appear in a specific class is greater than or equal to the average value The number of texts indicating that the characteristic words appear in a specific class is less than the average valueβ value is used to measure the deviation degree between the document frequency containing characteristic words in a certain class and the average value of all classes of document frequency, β is larger to indicate the class C_iIncluding a feature word t_kThe document number ratio of (1) includes the characteristic word t in all classes_kThe average value of the number of documents is large and is more, and the feature items have higher category distinguishing capability;

step 4, respectively representing each training text and each test text in a vector form by using feature words of a feature word bank, wherein the weight of each dimension is calculated according to TFIDF (TFIDF) ═ TF multiplied by IDF, TF (term frequency) is the frequency of the words and the frequency of the feature items appearing in the document, IDF (inverse document) is the frequency of the inverse document, and the formula is IDF ═ log (M/n)_k+0.01), M is the number of texts contained in the document set, n_kRepresenting the number of documents containing the word;

step 5, KNN classification is carried out;

the training text set is S, the test text is d, n is a feature vector dimension threshold, and K is 35;

step 5.1, calculating the similarity between all texts in the test text d and S by utilizing the cosine value of the vector included angle;

step 5.2, selecting the K texts with the maximum similarity obtained in the step 5.1 as K nearest neighbor texts of the test text d;

step 5.3, calculating the weight of the test text d belonging to each category, and classifying the test text d into the category with the maximum weight;

let training textd_iOf a known class C_jThe weight calculation formula is as follows:

wherein, Sim (d, d)_i) For testing the text d and the known category text d_iThe cosine similarity of (a) is as follows:

where n is the feature vector dimension threshold, X_jRepresenting the weight of j dimension of the text d to be measured, wherein j is more than 0 and less than or equal to n, x_ijRepresenting training text vector d_iThe weight of the jth dimension of (a);

y(d_i,C_j) For the category attribute function, the formula is as follows:

step 6, calculating precision ratio, recall ratio and F of the KNN classification algorithm₁Value, by setting the 2-time classification results F before and after₁The maximum threshold value of the value difference value and the step length of the increase of the scale factor mu are used for obtaining the final value of the scale factor mu so as to ensure higher classification accuracy;

step 6.1, set initial F₁The value is 0, the initial value of μ is 0.5, and ∈ 0.0001 indicates F twice before and after₁The threshold value of the difference, τ -0.05, is the step size of the increase of the scale factor μ;

step 6.2, repeat step 5 to get F₁' value, two times before and after F₁Difference Δ F ═ F₁′-F₁|；

Step 6.3, if the delta F is smaller than epsilon, obtaining the scale factor mu at the moment; if Δ F is greater than or equal to ∈, let μ' ═ μ + τ, F₁＝F₁', repeat step 6.2 and step 6.3 until the appropriate scale factor μ is obtained to ensureHigher classification accuracy is demonstrated.