# Unsupervised Optimal Discriminant Vector Based Feature Selection Method

Authors: Su-Qun Cao; Jonathan H. Manton
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

An efficient unsupervised feature selection method based on unsupervised optimal discriminant vector is developed to find the important features without using class labels. Features are ranked according to the feature importance measurement based on unsupervised optimal discriminant vector in the following steps. First, fuzzy Fisher criterion is adopted as objective function to derive the optimal discriminant vector in unsupervised pattern. Second, the feature importance measurement based on elements of unsupervised optimal discriminant vector is defined to determine the importance of each feature. The features with little importance measurement are removed from the feature subset. Experiments on UCI dataset and fault diagnosis are carried out to show that the proposed method is very efficient and able to deliver reliable results.


---

## Body

## 1. Introduction

Feature selection (FS) has become an active research topic in the area of pattern recognition, machine learning, data mining, intelligent fault diagnosis, and so forth. It is performed to choose a subset of the original features by removing redundant and noisy features from high-dimensional datasets in order to reduce computational cost, increase the classification accuracy, and improve result comprehensibility.In the supervised FS algorithms, since class labels are available in supervised learning, various feature subsets are evaluated using some function of prediction accuracy to select only those features which are related to or lead to the decision classes of the data under consideration. There are numerous supervised feature selection methods [1–7] such as Fisher criterion [1, 2], Relief [3], and Relief-F [4].However, for many existing datasets, class labels are often unknown or incomplete because large amounts of data make it difficult for humans to manually label the categories of each instance. Moreover, human labeling is expensive and subjective. Thus, it indicates the significance of unsupervised dimensionality reduction. Principal component analysis (PCA) [8] is often used in unsupervised pattern. However, PCA creates new features or principal components which are functions of original features. It is difficult to obtain intuitive understanding of the data using the new features only. Some unsupervised feature selection methods [8–14] have been proposed such as SUD [9]. SUD, which is a sequential backward selection algorithm to determine the relative importance of variables for Unsupervised Data, uses entropy similarity measurement to determine the importance of features with respect to the underlying clusters.It is known to us that the famous Fisher criterion which can derive optimal discriminant vector is commonly used to realize feature dimension reduction in supervised pattern. In the unsupervised pattern, how to overcome the lack of the class information to realize feature selection is a worthy topic.


## 2. An Overview of Optimal Discriminant Vector

Fisher criterion is a discriminant criterion function that was first proposed by Fisher. It is based on the between-class scatter and the within-class scatter. By maximizing this criterion, one can obtain an optimal discriminant vector. After the sample is projected to this vector, the within-class scatter is minimized and the between-class scatter is maximized [15].Givenc pattern classes X(i)=[xi1,xi2,...,xiNi] in the pattern set which contains Nd-dimensional patterns, where i=1,2,…,c, Ni is the number of all the patterns in the ith class; thus, N=N1+N2+⋯+Nc. Fisher criterion is defined as follows:
(1)JFC(ω)=ωTSbωωTSwω,
where Sb is the between-class scatter matrix denoted by
(2)Sb=∑i=1cNiN(mi-x-)(mi-x-)T,
and Sw is the within-class scatter matrix denoted by
(3)Sw=1N∑i=1c∑j=1Ni(xji-mi)(xji-mi)T,
where mi denotes the mean of the ith class, and x- denotes the mean of all the patterns in the pattern set.In order to seek an optimal discriminant vectorω by maximizing the Fisher criterion, the optimal discriminant vector ω* can be obtained by solving the following eigen-system equation:
(4)Sw-1Sbω*=λω*,
where λ is diagonal and consists of the corresponding eigenvalues. When the inverse of  Sw exists,  ω* can be obtained by the maximum eigenvalue of  Sw-1Sb*.


## 3. Unsupervised Optimal Discriminant Vector Based Feature Selection Method

Fisher criterion mentioned above can only be used in supervised pattern. This means that traditional optimal discriminant vector cannot be calculated directly by the unlabeled samples. Cao et al. [16] introduce fuzzy theory into Fisher criterion and define fuzzy Fisher criterion. Maximizing this criterion cannot only realize clustering but also obtain optimal discriminant vector.Suppose that the membership functionuij∈[0,1] with ∑i=1cuij=1 for all j and the fuzzy index m>1 is a given real value, where uij denotes the degree of the jth d-dimensional pattern belonging to the ith class; we can define the following fuzzy within-class scatter matrix Sfw:
(5)Sfw=∑i=1c∑j=1Nuijm(xj-mi)(xj-mi)T
and the following fuzzy between-class scatter matrix Sfb:
(6)Sfb=∑i=1c∑j=1Nuijm(mi-x-)(mi-x-)T.
Thus, we can derive fuzzy Fisher criterion as follows:
(7)JFFC=ωTSfbωωTSfwω.It is obvious that maximizingJFFC directly in (7) is not a trivial task due to the existence of its denominator. However, we can reasonably relax this problem by applying the following Lagrange multipliers; λ and βj(j=1,2,…n) together with the constraint ∑i=1cuij=1 to (7):
(8)F=ωTSfbω-λωTSfwω+∑j=1Nβj(∑i=1cuij-1).Setting∂F/∂ω to be zero, we have
(9)Sfw-1Sfbω=λω,
where ω is the eigenvector belonging to the largest eigenvalue λ of Sfw-1Sfb.Setting∂F/∂mi to be zero, we have
(10)mi=∑j=1Nuijm(xj-(1/λ)x-)∑j=1Nuijm(1-(1/λ)).
Here, mi is a local maximum of F [17] proved in Appendix.Setting∂F/∂uij to be zero, we have
(11)uij=(ωT(xj-mi)(xj-mi)Tω-(1/λ)ωT(mi-x-)(mi-x-)Tω)-1/(m-1)∑k=1c(ωT(xj-mk)(xj-mk)Tω-(1/λ)ωT(mk-x-)(mk-x-)Tω)-1/(m-1).
When (11) is used, as stated previously, uij should satisfy uij∈[0,1]; hence, in order to satisfy this constraint, we let uij=1 and ui′j=0 for all i′≠i, if
(12)ωT(xj-mi)(xj-mi)Tω≤1λωT(mi-x-)(mi-x-)Tω.With the above discussion, we can obtain the optimal discriminant vectorω in unsupervised pattern and then do feature selection based on ω. Now, let us illustrate this by the following experiment on 2-dimensional artificial dataset.Figure1 contains 168 2-dimensional samples. Through maximizing fuzzy Fisher criterion, we can obtain 2-class clustering result shown as red points and blue points, respectively, and can also get the vector ω=(ω1,ω2)′=(0.4562,-0.8899)′ shown as a line in Figure 2. We project all samples to x-axis and y-axis. It is obvious that projective points in x-axis from different class are overlaping while those in y-axis are separated well. It means that Y feature is more important than X feature for leading to the decision classes. This is consistent with |ω2|>|ω1| which gives us a revelation that we can apply the vector ω for feature selection.Figure 1
2-dimensional artificial dataset.Figure 2
The clustering result based on fuzzy Fisher criterion (the solid line is the optimal discriminant vectorω).Supposeω=(ω1,ω2,…ωd)′; we define fk as the k single feature importance measurement for comparison:
(13)fk=|ωk|∑k=1d|ωk|.To the above artificial dataset,f1=0.3389 is the importance measurement of X feature and f2=0.6611 is the importance measurement of Y feature.Proposed MethodStep 1.
Set the given thresholdε or the number of iterations α; initialize U=[μij]c×N and m=(m1,m2,…,mc) using K-means.Step 2.
ComputeSfw,Sfb using (5), (6), respectively.Step 3.
Compute the largest eigenvalueλ and the corresponding ω using (9).Step 4.
Updatemi and μij using (10), (11), and (12), respectively.Step 5.
ComputeJFFC.Step 6.
IfJFFC<ε or the number of iterations ≥α, go to Step 7; otherwise go to Step 2.Step 7.
Compute the feature importance measurements which are normalized asfk. Then sort fk by the descending order.Step 8.
Set the feature importance thresholdθ.Step 9.
Find a feature subset sizedθ which is a minimize number making ∑k=1dθfk no less than the threshold θ.Step 10.
Choosedθ features corresponding to the sorted fk in the descending order, that is, fk (k=1,2,…,dθ), as the selected features and then terminate.Different feature importance thresholdθ leads to different feature subset size. In Step 7 of proposed method, features have already been sorted by the descending order. If the feature subset size dθ is given from the start, we can simply select the first dθ features. But if dθ is not given, we can use θ to determine the feature subset size. The bigger θ is, the larger dθ is. The recommended range of θ is from 0.8 to 0.95.


## 4. Experimental Results

### 4.1. Feature Selection on UCI DatasetWine

In this experiment, the benchmarking UCI datasetWine[18] was chosen to test the feature selection effectiveness of SUD, Relief-F and our method. We use the following Rand index [19] to evaluate the clustering performance of the dimension reduction data:
(14)Rand(P1,P2)=a+bn×(n-1)/2,
where P1, P2 denote the clustering results for the original dataset without noise and the corresponding noisy dataset, a denotes the number of any two patterns in the original dataset belonging to the same cluster in P1, P2, b denotes the number of any two patterns in the original dataset belonging to two different clusters in P1, P2, and n is the number of all patterns in the original dataset. Obviously, Rand(P1,P2)∈[0,1]. And Rand(P1,P2)=1 when P1 is the same as P2. The smaller Rand(P1,P2), the bigger the difference between P1 and P2. In other words, the corresponding algorithm has less robust capability in this case.Table1 illustrates the basic information of the dataset. We choose 130 samples which belong to class 1 and class 2 as testing dataset. The parameters for the proposed method are set as follows:
(15)ε=0.001,α=20,θ=0.90.Table 1
Class distribution and features ofWine dataset.
Class
Number of samples
Features
Number
Name
Class 1
59
1
Alcohol
Class 2
71
2
Malic acid
Class 3
48
3
Ash
4
Alcalinity of ash
5
Magnesium
6
Total phenols
7
Flavanoids
8
Nonflavanoid phenols
9
Proanthocyanins
10
Color intensity
11
Hue
12
OD280/OD315 of diluted wines
13
ProlineTable2 lists the importance measurement of every feature computed by the proposed method. Due to the threshold θ, 6 features will be selected from original features. Figure 3 shows the Rand index values corresponding to the number of features using SUD, Relief-F and our method.Table 2
The feature importance measurement ofWine dataset.
Number
Number of features
The feature importance measurementfk
∑
k
=
1
d
θ
f
k
1
3
0.3180
0.3180
2
1
0.2709
0.5889
3
12
0.1793
0.7682
4
7
0.0520
0.8202
5
8
0.0445
0.8647
6
11
0.0364
0.9011
7
10
0.0301
0.9312
8
9
0.0243
0.9555
9
4
0.0241
0.9796
10
6
0.0088
0.9884
11
2
0.0057
0.9941
12
5
0.0049
0.9990
13
13
0.0009
0.9999Figure 3
Rand index values corresponding to the number of features.From Figure3, we can easily find that data selected features by the proposed method have the best clustering result among these three algorithms.


### 4.2. Feature Selection for Fault Diagnosis

The steel plates faults dataset used in this experiment was donated by Semeion, Research Center of Sciences of Communication, Via Sersale 117, Rome, Italy [20, 21]. It classifies steel plates’ faults into 7 different types: Pastry, Z_Scratch, K_Scratch, Stains, Dirtiness, Bumps, and Other_Faults. The dataset includes 1941 samples and every sample owns 27 independent features.Table3 shows class distribution and list of features. We choose 348 samples which belong to Pastry and Z_Scratch faults as testing dataset. The parameters for the proposed method are set as the previous experiment.Table 3
Class distribution and features of steel plates dataset.
Class
Number of samples
Features
Number
Name
Pastry
158
1
X_Minimum
Z_Scratch
190
2
X_Maximum
K_Scratch
391
3
Y_Minimum
Stains
72
4
Y_Maximum
Dirtiness
55
5
Pixels_Areas
Bumps
402
6
X_Perimeter
Other_Faults
673
7
Y_Perimeter
8
Sum_of_Luminosity
9
Minimum_of_Luminosity
10
Maximum_of_Luminosity
11
Length_of_Conveyer
12
TypeOfSteel_A300
13
TypeOfSteel_A400
14
Steel_Plate_Thickness
15
Edges_Index
16
Empty_Index
17
Square_Index
18
Outside_X_Index
19
Edges_X_Index
20
Edges_Y_Index
21
Outside_Global_Index
22
LogOfAreas
23
Log_X_Index
24
Log_Y_Index
25
Orientation_Index
26
Luminosity_Index
27
SigmoidOfAreasTable4 lists the importance measurement of every feature computed by the proposed method. Due to the threshold θ, 11 features will be selected from original features. Figure 4 shows the Rand index values corresponding to the number of features using SUD, Relief-F, and our method.Table 4
The feature importance measurement of steel plates dataset.
Number
Number of features
The feature importance measurementfk
∑
k
=
1
d
θ
f
k
1
19
0.2191
0.2191
2
15
0.1339
0.353
3
16
0.1283
0.4831
4
17
0.0777
0.559
5
13
0.0676
0.6266
6
12
0.0676
0.6942
7
20
0.0577
0.7519
8
27
0.0548
0.8067
9
21
0.051
0.8577
10
24
0.0343
0.892
11
22
0.0341
0.9261
12
23
0.0247
0.9508
13
25
0.0099
0.9607
14
2
0.0075
0.9682
15
1
0.0074
0.9756
16
26
0.007
0.9826
17
7
0.0044
0.987
18
6
0.0033
0.9903
19
4
0.0029
0.9932
20
3
0.0029
0.9961
21
14
0.0021
0.9982
22
9
0.001
0.9992
23
10
0.0005
0.9997
24
18
0.0001
0.9998
25
5
0.0001
0.9999
26
11
0
0.9999
27
8
0
0.9999Figure 4
Rand Index values corresponding to the number of features.Figure4 shows that the proposed method is able to find the important features. It also shows that the performance of the proposed method without using class labels is very close to and sometimes better than that of SUD or Relief-F which ranks the original features using the class labels.


## 4.1. Feature Selection on UCI DatasetWine

In this experiment, the benchmarking UCI datasetWine[18] was chosen to test the feature selection effectiveness of SUD, Relief-F and our method. We use the following Rand index [19] to evaluate the clustering performance of the dimension reduction data:
(14)Rand(P1,P2)=a+bn×(n-1)/2,
where P1, P2 denote the clustering results for the original dataset without noise and the corresponding noisy dataset, a denotes the number of any two patterns in the original dataset belonging to the same cluster in P1, P2, b denotes the number of any two patterns in the original dataset belonging to two different clusters in P1, P2, and n is the number of all patterns in the original dataset. Obviously, Rand(P1,P2)∈[0,1]. And Rand(P1,P2)=1 when P1 is the same as P2. The smaller Rand(P1,P2), the bigger the difference between P1 and P2. In other words, the corresponding algorithm has less robust capability in this case.Table1 illustrates the basic information of the dataset. We choose 130 samples which belong to class 1 and class 2 as testing dataset. The parameters for the proposed method are set as follows:
(15)ε=0.001,α=20,θ=0.90.Table 1
Class distribution and features ofWine dataset.
Class
Number of samples
Features
Number
Name
Class 1
59
1
Alcohol
Class 2
71
2
Malic acid
Class 3
48
3
Ash
4
Alcalinity of ash
5
Magnesium
6
Total phenols
7
Flavanoids
8
Nonflavanoid phenols
9
Proanthocyanins
10
Color intensity
11
Hue
12
OD280/OD315 of diluted wines
13
ProlineTable2 lists the importance measurement of every feature computed by the proposed method. Due to the threshold θ, 6 features will be selected from original features. Figure 3 shows the Rand index values corresponding to the number of features using SUD, Relief-F and our method.Table 2
The feature importance measurement ofWine dataset.
Number
Number of features
The feature importance measurementfk
∑
k
=
1
d
θ
f
k
1
3
0.3180
0.3180
2
1
0.2709
0.5889
3
12
0.1793
0.7682
4
7
0.0520
0.8202
5
8
0.0445
0.8647
6
11
0.0364
0.9011
7
10
0.0301
0.9312
8
9
0.0243
0.9555
9
4
0.0241
0.9796
10
6
0.0088
0.9884
11
2
0.0057
0.9941
12
5
0.0049
0.9990
13
13
0.0009
0.9999Figure 3
Rand index values corresponding to the number of features.From Figure3, we can easily find that data selected features by the proposed method have the best clustering result among these three algorithms.


## 4.2. Feature Selection for Fault Diagnosis

The steel plates faults dataset used in this experiment was donated by Semeion, Research Center of Sciences of Communication, Via Sersale 117, Rome, Italy [20, 21]. It classifies steel plates’ faults into 7 different types: Pastry, Z_Scratch, K_Scratch, Stains, Dirtiness, Bumps, and Other_Faults. The dataset includes 1941 samples and every sample owns 27 independent features.Table3 shows class distribution and list of features. We choose 348 samples which belong to Pastry and Z_Scratch faults as testing dataset. The parameters for the proposed method are set as the previous experiment.Table 3
Class distribution and features of steel plates dataset.
Class
Number of samples
Features
Number
Name
Pastry
158
1
X_Minimum
Z_Scratch
190
2
X_Maximum
K_Scratch
391
3
Y_Minimum
Stains
72
4
Y_Maximum
Dirtiness
55
5
Pixels_Areas
Bumps
402
6
X_Perimeter
Other_Faults
673
7
Y_Perimeter
8
Sum_of_Luminosity
9
Minimum_of_Luminosity
10
Maximum_of_Luminosity
11
Length_of_Conveyer
12
TypeOfSteel_A300
13
TypeOfSteel_A400
14
Steel_Plate_Thickness
15
Edges_Index
16
Empty_Index
17
Square_Index
18
Outside_X_Index
19
Edges_X_Index
20
Edges_Y_Index
21
Outside_Global_Index
22
LogOfAreas
23
Log_X_Index
24
Log_Y_Index
25
Orientation_Index
26
Luminosity_Index
27
SigmoidOfAreasTable4 lists the importance measurement of every feature computed by the proposed method. Due to the threshold θ, 11 features will be selected from original features. Figure 4 shows the Rand index values corresponding to the number of features using SUD, Relief-F, and our method.Table 4
The feature importance measurement of steel plates dataset.
Number
Number of features
The feature importance measurementfk
∑
k
=
1
d
θ
f
k
1
19
0.2191
0.2191
2
15
0.1339
0.353
3
16
0.1283
0.4831
4
17
0.0777
0.559
5
13
0.0676
0.6266
6
12
0.0676
0.6942
7
20
0.0577
0.7519
8
27
0.0548
0.8067
9
21
0.051
0.8577
10
24
0.0343
0.892
11
22
0.0341
0.9261
12
23
0.0247
0.9508
13
25
0.0099
0.9607
14
2
0.0075
0.9682
15
1
0.0074
0.9756
16
26
0.007
0.9826
17
7
0.0044
0.987
18
6
0.0033
0.9903
19
4
0.0029
0.9932
20
3
0.0029
0.9961
21
14
0.0021
0.9982
22
9
0.001
0.9992
23
10
0.0005
0.9997
24
18
0.0001
0.9998
25
5
0.0001
0.9999
26
11
0
0.9999
27
8
0
0.9999Figure 4
Rand Index values corresponding to the number of features.Figure4 shows that the proposed method is able to find the important features. It also shows that the performance of the proposed method without using class labels is very close to and sometimes better than that of SUD or Relief-F which ranks the original features using the class labels.


## 5. Conclusions

An efficient unsupervised feature selection method based on unsupervised optimal discriminant vector is developed to find the important features without using class labels. It adopts fuzzy Fisher criterion to derive the optimal discriminant vector in unsupervised pattern. It defines the single feature importance measurement based on unsupervised optimal discriminant vector to determine the importance of every feature. Two experiments onWine dataset and fault diagnosis were carried out to show that the proposed method is able to find important features and is a reliable and efficient feature selection methodology compared to SUD and Relief-F. In the future, we will research how to introduce kernel techniques to the proposed method to enhance its applicability.



---

*Source: 396780-2013-11-28.xml*