CN106503731A - A kind of based on conditional mutual information and the unsupervised feature selection approach of K means - Google Patents

Abstract

The present invention provides an unsupervised feature selection method based on conditional mutual information and K-means. First, the data without class labels is clustered through multiple K-means algorithms with different initial conditions, and then based on each clustering , considering the modularity value of each feature and the conditional mutual information between different features, and using the correlation independence index between features to select a subset of features with high correlation and low redundancy. The final feature subset is obtained by summarizing the feature subsets obtained from different K-means clustering results. The invention can be effectively applied to unlabeled and unbalanced data sets, and the obtained feature subsets have high correlation and low redundancy.

Description

An Unsupervised Feature Selection Method Based on Conditional Mutual Information and K-means

technical field

The invention belongs to the problem of feature selection in the field of machine learning, and specifically relates to a method for unsupervised feature selection of an unlabeled data set by using conditional mutual information and a K-means algorithm.

Background technique

In the practical application of machine learning, the number of features is often large, there may be irrelevant features, and there may be interdependence between features. The more the number of features, the longer it takes to analyze the features and train the model, and it is easy to cause the "dimension disaster", making the model more complex, which will lead to consequences such as a decline in the model's generalization ability. Therefore, feature selection is particularly important.

Feature selection, also known as feature subset selection or attribute selection, refers to selecting a feature subset from all features to make the constructed model better. Feature selection can eliminate irrelevant or redundant features, so as to reduce the number of features, improve model accuracy, and reduce running time. On the other hand, selecting the truly relevant features simplifies the model and makes it easier for researchers to understand the process of data generation.

According to the combination of searching the optimal feature subset and building the learning model, feature selection methods can be roughly divided into two types: wrapper feature selection (Wrapper) and filter feature selection (Filter). Encapsulated feature selection repeatedly runs the learning algorithm to evaluate the quality of the attribute set. It is better than filtered feature selection in accuracy, but it has poor generalization performance for other classifiers. In the face of high-dimensional datasets, the computational complexity in the learning process is high because the encapsulated feature selection needs to be tightly coupled with specific learning algorithms. Filtering feature selection does not require a specific learning algorithm, but uses appropriate criteria to quickly evaluate the quality of features, so it is a method with high computational efficiency.

Most of the existing traditional feature selection methods take improving the classification accuracy as the optimization goal, without fully considering the distribution of data samples, and generally pursue the learning effect of large classes, and tend to ignore the learning performance of small classes. In order to solve the problem of data imbalance, at the data level, the positive samples of the training set can be resampled before training, so that the positive and negative samples can be balanced, and then corresponding learning (Exploratory under-sampling for class -imbalance learning.Liu X Y, Wu J, Zhou Z H), but this cannot make use of all the data, which will reduce the classification accuracy. At the algorithm level, the traditional feature selection algorithm is improved according to the characteristics of the unbalanced distribution of data categories, so that the algorithm can adapt to samples with unbalanced category distribution (new algorithm for feature selection in imbalanced problems: IM-IG. You Mingyu , Chen Yan, Li Guozheng), but this method is limited to two-type imbalance problems, and is not suitable for multi-type imbalance problems.

For filtering feature selection, many supervised feature selection methods have been proposed, such as applying mutual information to evaluate candidate features, and selecting the top features as the input of the neural network classifier (Using mutual information for selecting features in supervised neural netlearning.R.Battiti), but this method ignores the redundancy between features, resulting in the selection of many redundant features, which is not conducive to the performance improvement of subsequent classifiers. Moreover, this method is only suitable for data with class label information, and is not suitable for unsupervised feature selection.

In the field of unsupervised feature selection, many unsupervised feature selection methods for text have been proposed, but these methods cannot be directly applied to numerical data. Some unsupervised feature selection methods applied to numerical data, such as unsupervised filtering feature selection algorithms for classification features, are based on one-pass clustering algorithms and use the importance of each feature in different clusters as a basis for judgment , and finally select feature subsets according to the changing law of importance (research on unsupervised feature selection method for classification features. Wang Lianxi, Jiang Shengyi), this method only uses one clustering algorithm to divide the data, so that the clustering results exist Randomness cannot guarantee the accuracy of feature selection.

The present invention first clusters the data without class labels through multiple K-means algorithms with different initial conditions, and then, on the basis of this clustering, comprehensively considers the modular measurement value of each feature and the conditional interaction between different features. Information, obtain feature subsets with high correlation and low redundancy, and finally summarize the feature subsets obtained from different K-means clustering results.

Contents of the invention

Purpose: The technical problem to be solved by this invention is the feature selection problem of unlabeled data sets, and an unsupervised feature selection method based on conditional mutual information and K-means is proposed. The data without class labels is clustered through the K-means algorithm with different initial conditions multiple times, which eliminates the randomness of feature selection on a single clustering result and reduces the impact of data imbalance on feature selection. On the basis of each clustering, comprehensively consider the modularity metric value of each feature and the conditional mutual information between different features, and use the correlation independence index between features to select the one with high correlation and low redundancy. combination of features. The final feature subset is obtained by summarizing the feature subsets obtained from different K-means clustering results. The invention can be effectively applied to unlabeled and unbalanced data sets, and the obtained feature subsets have high correlation and low redundancy.

Technical scheme of the present invention is as follows:

An unsupervised feature selection method based on conditional mutual information and K-means, comprising the following steps:

Step 1), perform multiple K-means clustering with different K values and different cluster centers on the unlabeled data set, and obtain each clustering result;

Step 2), according to the different clustering results obtained in step 1), constructing a feature vector diagram of each feature for each clustering result in turn;

Step 3), according to the eigenvector diagram constructed in step 2), calculate the modularization metric value of each feature, and put the feature with the largest modularization metric value into the feature subset;

Step 4), according to the initial feature subset obtained in step 3), calculate the conditional mutual information of each remaining feature with respect to each feature in the feature subset, so as to calculate the relative independence measure of each remaining feature with respect to the feature subset value;

Step 5), adding the modularization metric value of each remaining feature obtained in step 3) and the correlation independence metric value obtained in step 4) with a certain weight, and using the calculation result as the score of each remaining feature;

Step 6), put the feature with the highest score obtained in step 5) into the feature subset, and then iteratively perform step 4), step 5), and step 6), until the number of features in the feature subset reaches the required number ;

In step 7), the feature subsets formed according to different K-means clustering results obtained in step 6) are summarized to obtain the final feature subset.

Further, in the unsupervised feature selection method based on conditional mutual information and K-means of the present invention, step 1) performs multiple K-means clustering with different K values and different cluster centers on the unlabeled data set, and obtains each The second clustering result. The present invention first uses the K-means clustering algorithm to cluster the unlabeled data set for multiple times with different initial values. During initialization, the maximum number of clusters, the minimum number of clusters, and the number of clusters of the K-means clustering algorithm are artificially specified. Each time clustering is performed, the K-means algorithm randomly selects a number between the maximum number of clusters and the minimum number of clusters as the number k of clusters, and randomly selects k points in the data set as the initial centroid, passing K The -means clustering algorithm can obtain the result of each clustering in turn, that is, the class label C.

Further, in the unsupervised feature selection method based on conditional mutual information and K-means of the present invention, step 2) according to the different clustering results obtained in step 1), construct the feature vector diagram of each feature in turn for each clustering result . The construction of the eigenvector diagram of a certain feature in the data set is to use each sample as a point when the eigenvalue and class label of the feature are known, assuming that the class of a certain sample contains x samples, Then connect the point corresponding to the sample with the x-1 sample points closest to its eigenvalue, perform the above operations on all samples in the data set under the same feature, and construct the eigenvector diagram of the feature .

Further, in the unsupervised feature selection method based on conditional mutual information and K-means of the present invention, step 3) calculates the modularized metric value of each feature according to the feature vector graph constructed in step 2), and the calculation formula is:

In the formula, i and j are two points in the eigenvector graph constructed in step 2); A _ij is the adjacency matrix of the eigenvector graph, if there is an edge from i to j, then A _ij =1, otherwise it is 0; M is the total number of connections, that is, the total number of edges in the feature vector graph; k _i and k _j are the degrees of nodes i and j respectively; the binary function δ(C _i , C _j ) indicates that if nodes i and j belong to the same cluster , then it is 1, otherwise it is 0; after calculating the respective modularity metric values according to the eigenvector diagram of each feature, normalize all the modularity metric values to obtain Q', and correspond to the maximum value of Q' features into the feature subset.

Further, in the unsupervised feature selection method based on conditional mutual information and K-means of the present invention, step 4) calculates the condition of each remaining feature relative to each feature in the feature subset according to the initial feature subset obtained in step 3) Mutual information, so as to calculate the relative independence measure of each remaining feature with respect to the feature subset, the calculation formula is:

In the formula, f _r is the remaining features that have not been selected into the feature subset, f _j is the feature in the feature subset, and S is the feature subset; where RI( _fr , f _j ) means that the remaining feature f _r is relative to the feature sub-set The relative independence of f _j , one of the features in the set, is calculated as:

In the formula, H(C) is the entropy of the target variable C, I(f _r ; C|f _j ) and I(f _j ; C|f _i ) are the conditional mutual information of feature f _r and feature f _j , and the calculation formula for:

In the formula, N is the number of samples in the data set, and C is the number of classes. After calculating the relative independence measure of each remaining feature with respect to the feature subset, all the relative independence measures are normalized to obtain I _ri '.

Further, in the unsupervised feature selection method based on conditional mutual information and K-means of the present invention, step 5) combines the normalized modularization metric value of each remaining feature obtained in step 3) with step 4) to obtain the value of each remaining feature The normalized correlation independence measurement value is added with a certain weight, namely: s=wQ'+(1-w)I _ri ', the w in the formula is artificially specified, and the value range is [0,1], and the calculation result is used as each scores for the remaining features.

Further, in the unsupervised feature selection method based on conditional mutual information and K-means of the present invention, step 6) puts the feature corresponding to the s maximum value obtained in step 5) into the feature subset, and then iteratively performs step 4) , Step 5), and Step 6), until the number of features in the feature subset reaches the required number, and the number of features is manually specified.

Further, in the unsupervised feature selection method based on conditional mutual information and K-means of the present invention, step 7) summarizes the feature subsets formed according to different K-means clustering results obtained in step 6), and according to the required The number of features selects the features with the most occurrences to form the final feature subset.

Beneficial effect

Aiming at the feature selection problem of the unlabeled data set in machine learning, the present invention combines the K-means algorithm with the conditional mutual information between features, which helps to select the most important features in the unlabeled data set. This method uses the K-means algorithm with different initial conditions to cluster unlabeled data sets, which can eliminate the randomness of feature selection on a single clustering result, reduce the impact of data imbalance on feature selection, and make up for The previous feature selection method is not ideal for feature selection of unbalanced datasets or is only suitable for labeled datasets; at the same time, in order to obtain feature subsets with high correlation and low redundancy, this method is On the basis of class, comprehensively consider the modular measure value of each feature and the conditional mutual information between different features, and use the correlation independence index between features to select a feature combination with high correlation and low redundancy. The feature subsets extracted multiple times are summarized to obtain the final feature subset. The combination of K-means algorithm and conditional mutual information makes the feature selection algorithm not only applicable to balanced or unbalanced unlabeled data sets, but also improves the correlation of feature subsets and reduces their redundancy, thereby selecting the most Important collection of features.

Description of drawings

Figure 1 is a flowchart of an unsupervised feature selection method based on conditional mutual information and K-means.

Figure 2 is an example of constructing a feature vector map for a dataset.

detailed description

Below in conjunction with accompanying drawing, the implementation of technical scheme is described in further detail:

The unsupervised feature selection method based on conditional mutual information and K-means of the present invention will be further described in detail in conjunction with the flow chart and the implementation case.

In this implementation case, the conditional mutual information and K-means algorithm are used to select the features of the unlabeled data set. As shown in Figure 1, this method includes the following steps:

Step 10, performing multiple K-means clustering with different K values and different cluster centers on the unlabeled data set, and obtaining each clustering result;

In step 101, the maximum number of clusters MAX and the minimum number of clusters MIN of the K-means algorithm are predetermined in the input stage, and before each clustering, a number is randomly selected in the range of [MAX, MIN] as a cluster The number k, and randomly select k points in the data set as the initial centroid;

Step 102, the total number of times T of performing the K-means clustering algorithm is predetermined in the input stage, and each time the K-means algorithm is executed, a set of clustering results, that is, the class label C, can be obtained, and the K-means clustering algorithm is repeated. Classes until the number of clustering times reaches the preset total number, and finally T groups of different clustering results can be obtained;

Step 20, according to the clustering results obtained in the previous step, sequentially constructing feature vector diagrams of each feature for each clustering result;

In step 201, the construction of the eigenvector diagram of a certain feature in the data set is to first use each sample as a point when the eigenvalue and class label of the sample are known under the feature, as shown in Figure 2 Data containing two features, each dot and square point on the right represents a sample, and the number next to the point indicates the size of the feature value corresponding to the point;

Step 202, if the total number of samples contained in the class of a certain sample is x, connect the point corresponding to the sample with the x-1 sample points closest to its feature value, as shown in Figure 2, sample 1 The class is C1, and the total number of samples contained in class C1 is 4, then the point corresponding to sample 1 is connected to the 3 sample points closest to its eigenvalue, namely sample 2, sample 7, and sample 6;

Step 203, perform the operation of step 202 on all samples in the data set under the same feature, and then construct the feature vector diagram of the feature;

Step 204, perform the operations of steps 201-203 on all the features in the data set, and then construct the feature vector diagram of all the features, as shown in Figure 2, the data set with 2 features on the left, after step 10, a trip K After -means clustering, the class labels C1 and C2 are obtained, and the right side is the feature vector diagram corresponding to feature 1 and feature 2;

Step 30, according to the eigenvector diagram constructed in the previous step, calculate the modularity metric value of each feature, and put the feature with the largest modularity metric value into the feature subset;

Step 301, according to the formula Calculate the respective modularity measures for each feature;

Step 302, normalize the modularized metric values of each feature to obtain Q';

Step 303, put the feature corresponding to the maximum value of Q' into the feature subset, and delete it from the remaining features;

Step 40, according to the feature subset obtained in the previous step, calculate the relative independence measure value of each remaining feature with respect to the feature subset;

Step 401, according to the conditional mutual information formula Calculate the values of I(f _r ; C|f _j ) and I(f _j ; C|f _i ), that is, the conditional mutual information between the remaining features and the selected features;

Step 402, according to the formula Calculate the relative independence of each remaining feature with respect to a feature in the feature subset;

Step 403, according to the formula Compute the relative independence measure of each remainder with respect to the subset of features;

Step 404, normalize the correlation independence measure value of each remaining feature to obtain I _ri ';

Step 50, add the modularity metric Q' of each remaining feature obtained in step 30 and the correlation independence metric I _ri ' of each feature obtained in step 40 with a certain weight, and use the calculation result as each Scores for the remaining features;

Step 501, the weight w of the modularity measure value and the related independence measure value is preset in the input stage, the value range is [0,1], and the default setting is 0.3;

Step 502, according to the formula s=wQ'+(1-w)I _ri ', calculate the score of each remaining feature;

Step 60, put the feature with the highest score in the previous step into the feature subset, and delete it from the remaining features, repeat step 40, step 50, and step 60 until the number of features in the feature subset reaches the required number , the required number of features a is preset in the input stage;

Step 70: Summarize the feature subsets obtained in the previous step based on different K-means clustering results, select a feature with the most occurrences according to the required number of features, and form and output the final feature subset.

Claims (8)

1. a kind of based on conditional mutual information and the unsupervised feature selection approach of K-means, it is characterised in that including following step Suddenly：

Step 1), to carrying out the K-means clusters of multiple different K values and different cluster centres without label data collection, and obtain every Secondary cluster result；

Step 2), according to step 1) the different cluster results that obtain, each feature is constructed for each cluster result successively Feature vector chart；

Step 3), according to step 2) feature vector chart that constructs, calculate the modularization metric of each feature, and by modularization The maximum feature of metric is put in character subset；

Step 4), according to step 3) the initial characteristicses subset that obtains, calculate each residue character relative in character subset each The conditional mutual information of feature, so that calculate correlation independence metric of each residue character relative to character subset；

Step 5), by step 3) the modularization metric of each residue character and the step 4 that obtain) the correlation independence degree that obtains Value is added with certain weight, using result of calculation as each residue character score；

Step 6), by step 5) feature of highest scoring that obtains is put in character subset, is then made iteratively step 4), step Rapid 5), step 6), the Characteristic Number in character subset reach required for number；

Step 7), by step 6) obtain according to different K-means cluster results formed character subset collected, obtain most Whole character subset.

2. the method for claim 1, it is characterised in that step 1) to without label data collection carry out multiple different K values and The K-means clusters of different cluster centres, and obtain each cluster result；During initialization, K-means clusters are artificially specified The maximum cluster number of algorithm and min cluster number, and cluster number of times；When being clustered each time, K-means algorithms exist A number is randomly choosed as the number k of cluster between maximum cluster number and min cluster number, and is selected in data set at random K point is selected as initial barycenter, by K-means clustering algorithms, the result for being clustered each time successively, i.e. class label C.

3. the method for claim 1, it is characterised in that further, step 2) according to step 1) difference that obtains gathers Class result, constructs the feature vector chart of each feature successively for each cluster result；The spy that a certain feature is concentrated to data The construction of vectogram is levied, is in the case of known to this feature lower eigenvalue and class label, using each sample as a point, vacation If the class that certain sample is located contains x sample, then by the point corresponding to the sample with and the immediate x-1 of its characteristic value individual Sample point is connected, and executes above operation to all samples that data are concentrated, you can construct this feature under same feature Feature vector chart.

4. the method for claim 1, it is characterised in that step 3) according to step 2) feature vector chart that constructs, meter The modularization metric of each feature is calculated, computing formula is：

$Q=\underset{ij}{\Σ}\[\frac{A_{ij}}{2M}-\frac{k_i*k_j}{\left(2M\right)*\left(2M\right)}\]\mathrm{\δ}(C_i,C_j)$

In formula, i, j are steps 2) two points in the feature vector chart that constructs；A_ijIt is the adjacency matrix of feature vector chart, If there is side, A from i to j_ij=1, it is otherwise 0；M is the sum for always connecting side in number, i.e. feature vector chart；k_iAnd k_jPoint It is not the number of degrees of node i and j；Binary function δ (C_i,C_j) represent that if node i and j belong to same cluster, for 1, it is otherwise 0； After feature vector chart according to each feature calculates respective modularization metric, all of modularization metric is carried out Normalization, obtains Q ', the feature corresponding to Q ' maximums is put in character subset.

5. the method for claim 1, it is characterised in that step 4) according to step 3) the initial characteristicses subset that obtains, meter Conditional mutual information of each residue character relative to each feature in character subset is calculated, relative so as to calculate each residue character In the correlation independence metric of character subset, computing formula is：

$I_{ri}(f_r;C|S)=\underset{f_j\∈S}{\Σ}RI(f_r,f_j)$

In formula, f_rIt is the residue character for not being selected into character subset, f_jIt is the feature in character subset, S is character subset；Its Middle RI (f_r,f_j) represent residue character f_rRelative to one of feature in character subset f_jCorrelation independence, computing formula is：

$RI(f_r,f_j)=\frac{I(f_r;C|f_j)+I(f_j;C|f_i)}{2H\left(C\right)}$

In formula, H (C) is the entropy of target variable C, I (f_r；C|f_j) and I (f_j；C|f_i) it is feature f_rWith feature f_jCondition mutual trust Cease, computing formula is：

$I(X_i;Y|X_j)=\underset{i=1}{\overset{N}{\mathrm{\Σ}}}\underset{j=1}{\overset{N}{\mathrm{\Σ}}}\underset{k=1}{\overset{C}{\mathrm{\Σ}}}p(x_i,x_j,y_k)\log \frac{p(x_i,y_k|x_j)}{p\left(x_i\right|x_j)p\left(y_k|x_j\right)}$

In formula, N is the number of sample in data set, and C is the quantity of class.Each residue character is calculated relative to character subset Correlation independence metric after, all of correlation independence metric is normalized, I is obtained_ri'.

6. the method for claim 1, it is characterised in that step 5) by step 3) specification of each residue character that obtains Change modularization metric and step 4) the standardization correlation independence metric that obtains each residue character is added with certain weight, I.e.：S=wQ'+ (1-w) I_ri', the w people in formula is specified, and span is [0,1], and result of calculation is remaining special as each The score that levies.

7. the method for claim 1, it is characterised in that step 6) by step 5) spy corresponding to the s maximums that obtain Levy and be put in character subset, be then made iteratively step 4), step 5), step 6), the Characteristic Number in character subset Number required for reaching, Characteristic Number are artificially specified.

8. the method for claim 1, it is characterised in that step 7) by step 6) obtain poly- according to different K-means The character subset that class result is formed is collected, and selects the most several features of occurrence number according to required Characteristic Number, Constitute final character subset.