基于一致性和知识粒度的半监督特征选择方法

万丽娟，钱文彬*，曾武序

（1.江西农业大学 软件学院，江西 南昌 330045；2.江西农业大学 计算机与信息工程学院，江西 南昌 330045）

0 引言

数据挖掘旨在从数据信息中获取规则和知识，已被应用到多个领域。但随着数据信息量的爆发式增长，“维度灾难”给高维的数据挖掘分析带来了严峻的挑战［1-2］。当前，特征选择是对高维数据进行数据预处理的重要技术之一［3-4］，并根据数据是否存在类别标记可分为监督特征选择、半监督特征选择和无监督特征选择。监督特征选择的数据为正确且非空标记数据［5-6］；无标记特征选择的数据都为无标记的样本［7-8］。由于标注样本类别的成本非常昂贵，因此实际数据集中往往含有少量的标记数据和大量的未标记数据［9-10］。目前，半监督数据中仅利用标记信息较难精确地完成分类学习任务，此类问题引起了研究者的广泛关注［11-12］。

目前，针对半监督学习的特征选择方法研究，Razieh等［13］通过拉普拉斯算法结合正则化和损失函数方法，提出一种半监督特征选择方法；Shi等［14］结合自训练和拉普拉斯权重提出了半监督特征选择方法，其利用多视图提高分类性能并预测未标记数据，从而获得特征子集；Pang等［15］基于标记和特征之间的关系预测未标记数据的标记信息，从中选择满足条件的特征子集；Lü等［16］结合自适应全局结构学习和流行学习提出学习框架，选取更具有代表性的特征作为特征选择结果；Wang等［17］结合标记传播和半结构化图学习进行半监督降维，其语义信息从标记传播到学习结构图上的未标记样本，获取未标记数据的标记信息从而进行特征选择。上述半监督特征选择方法主要是根据已有标记的数据训练分类模型，再根据分类模型预测未标记数据的标记信息进行特征选择。但是，在现实生活中因为存在着少量的标记数据，通过标记数据训练模型得到的伪标记信息往往存在一定的偏差。

粗糙集理论是一种新的处理不确定、不精确、不完备和信息的数学工具［18］，目前已成为特征选择的重要手段之一。在粗糙集中，正域约简的思想是利用正域下的依赖度获取分类性能较高的特征子集。Xie等［19］提出基于局部搜索的k-size正域约简方法，利用局部搜索和正域约简之间的关系设计的最优归约和局部归约；Yuan等［20］结合模糊粗糙集提出了无监督学习的正域约简方法，主要考虑是在没有标记信息情况下的混合特征选择模型。同时，知识粒度是利用数据粒化的思想分析特征的重要性。Jing等［21］引用增量机制和知识粒度来处理动态特征选择的学习任务；Li等［22］利用知识粒度覆盖处理无法定义的粒度问题。在上述的方法中，主要处理监督数据或无监督数据，较少考虑数据中同时含有标记和无标记样本的情况，因此如何使用粒计算方法处理半监督数据学习任务并进行特征选择具有重要的研究意义。

为此，本文提出基于一致性和知识粒度的半监督特征选择方法。针对半监督数据中含有标记数据和未标记数据，对于有标记的数据，为了更好地衡量特征相对于样本标记的重要度，利用正域下的依赖度去度量样本的一致类；同对于未标记数据，采用知识粒度对未标记样本进行数据粒化去衡量特征对样本空间的可区分性，因此结合数据分布情况提出一种新型的半监督特征选择方法。为了验证该方法的可行性，在公共数据集UCI上八个数据集上与当前四种半监督特征选择对比方法进行实验分析，实验结果表明，提出的方法分类性能得到提高，并获取较为合理的特征选择结果。

1 基础知识

定义1［22］设 DS=(U，A，V，f)为一个决策表。其中，论域为U={UL∪UU}，其中UL={x1，x2，…，xl} 为 有 标 记 数 据 ， UU={xl+1，…，xm} 为 未 标 记 数 据 ； 特 征A={C∪D}，其C是条件特征，D是决策特征；V是特征值的集合，在半监督学习中，存在大量缺少标记信息的样本，因此VD可取空值；f是分类映射函数，即f：U×C∪D→V。

定义2［23］设 DS=(U，A，V，f)是一个决策表，∀x，y∈U。任意特征集B⊆A，其等价关系IND(B)为：

在等价关系IND(B)中，将论域U划分为等价类，可表示为 U/IND(B)={X1，X2，…，Xn}，其中Xn为在等价关系下划分的等价类。

定义3［24］设 DS=(U，A，V，f)是一个决策表，∀x，y∈U。任意特征集B⊆A，[x]B表示在等价关系IND(B)下包含元素x的等价类。对于根据决策特征D划分的等价关系可表示为：U/D= {D1，D2，…，Dq}，其 上 、下近似集定义为：

在决策表DS中，其决策特征的下近似集可以得到条件特征集B的正域：POSB(D)=∪X∈U/D-BX。

定义4［25］设 DS=(U，A，V，f)是一个决策表，∀x，y∈U。A={C∪D}，C表示条件特征，D表示决策特征。∀B⊆C，决策特征D对于条件特征B的依赖度定义为：

其中|·|表示集合的样本个数，由于POSB(D)为论域的子集，γB(D)的值域为[0，1]，当 γB(D)=1时，表示特征集B为该论域的特征选择结果。

2 基于一致性和知识粒度的半监督特征选择

在本节中，将会详细介绍基于一致性和知识粒度的半监督特征选择的具体实现方法。对于半监督数据集，采用依赖度去度量有标记样本特征与标记的相关性，以及使用知识粒度方法去衡量无标记样本的特征相对于整个样本空间的可区分性。其具体定义如下。

定义5 设 DS=(U，A，V，f)是一个 决策表，∀x，y∈U。A={C∪D}，C表示条件特征，D表示决策特征。∀B⊆C和∀c∈(C−B)，则针对于特征集B下条件特征c相对于决策特征D的重要度为：

由于 γB(D)的值域为 [0，1]，条件特征 c相对于决策特征D的重要度的值域为[0，1]，若重要度的值为0则表示该特征为冗余特征，否则该特征为不可缺少特征。当增加一个特征时，相应的重要度表示增加特征后的依赖度的变化。

定义 6 设 DS=(U，A，V，f)是一个决策表，∀x，y∈U。A={C∪D}，C表示条件特征，D表示决策特征。∀B⊆C，若B为特征选择后的特征子集，则满足：

（1）γB(D)= γC(D)；

（2）∀b ∈ B，γB−{b}(D)≠ γB(D)。

根据以上定义和性质，利用正域下的依赖度可用于分析有标记一致类样本，从而进行特征选择的过程，但是，半监督数据中存在大部分无标记样本［26］，为了充分利用无标记样本的特征信息进行特征选择，因此，引入了知识粒度方法来处理此类学习任务。

定义7［22］设 DS=(U，A，V，f)是一个决策表，A={C∪D}，C表示条件特征，D表示决策特征。∀B⊆C，基于条件特征B划分的等价类为 U/IND(B)={X1，X2，…，Xn}，则条件特征B的知识粒度定义GD(B)为：

其中|·|表示集合的样本个数，基于该公式，知识粒度是对在该粒度下的等价类进行类内的不确定性度量。

性质2 给定一个决策表DS=(U，A，V，f)，∀x，y∈U。A={C∪D}，C 表示条件特征，D表示决策特征 。 若B，E⊆C， 且 B≺E 则GD(B)> GD(E)。其中，≺ 表示一种偏好关系。为了更好表示知识粒度对于决策表的可区分性，其表示为知识粒度的辨识度，定义如下。

定义 8 设 DS=(U，A，V，f)是一个决策表，A={C∪D}，∀B⊆C。知识 B的辨识度Dis(B)为：

定义 9 设 DS=(U，A，V，f)是一个决策表 ，A={C∪D}， ∀B⊆C 和 ∀b∈(C−B)，则条件特征b相对于特征子集B的重要度为：

定理 1 设 DS=(U，A，V，f)是一个决策表 。 A={C∪D}， ∀B⊆C，若 GD(B)=GD(C)且对于任意条件特征b∈B，并Siggk(b，B−|b|)>0，则B为A的一个特征子集。

由于半监督数据中存在有标记数据和无标记数据，其特征的重要度需要充分考虑该两部分数据中特征的重要度，为此考虑数据分布情况，构造了基于一致性和知识粒度的半监督特征选择方法，其特征的重要度计算定义给出如下。

定义10 设 DS=(U，A，V，f)是一个决策表，A={C∪D}，C表示条件特征，D表示决策特 征 。 ∀B⊆C，∀c∈(C−B)和 b∈(C−B−c)，则特征重要度为：

其中α为有标记数据在半监督数据中占有比例，有标记数据部分中条件特征c的重要度为Sigpos(c，B，D)，无标记数据部分中条件特征 c的重要度为Siggk(c，B)。在计算有标记数据和无标记数据条件特征重要度的基础上，将其两者在同一量纲下进行融合计算最终该条件特征在半监督数据中重要度值，在此基础上，与该条件特征之外的其他特征中最大重要度值进行归约，保证算法的可行性。其算法如算法1所示。

算法中步骤一是对数据预处理；步骤二是初始化变量；在步骤三中，针对每个特征进行计算其重要度，在步骤3.1中是根据该特征在正域下的依赖度去衡量样本的一致类，步骤3.2中利用知识粒度对数据粒化度量该特征对样本空间的可区分性，步骤3.3根据数据分布情况计算该特征的重要度，步骤3.4对所计算出的特征重要度进行排序；步骤4根据排序结果选取特征选择结果。

3 实例分析

为进一步详细介绍算法的详细流程。以表1的半监督数据为例进行分析说明算法流程。其 中 U={x1，x2，x3，x4，x5，x6，x7，x8，x9，x10}，前 5个样本为有标记样本，后5个样本为无标记样本 ，C={c1，c2，c3，c4，c5}为 条 件特征集 ，D 为 决策特征集，在半监督数据中，无标记信息的决策特征表示为“*”。

将半监督数据集划分为有标记数据部分和无标记数据部分，对于有标记数据部分，首先，根据标记进行等价类划分，得到U/IND(D)={{x1，x4，x5}， {x2，x3}}={X1，X2}，并令γ∅(D)=0；之后对单个特征进行划分等价类，比如对于c1特征，我们可以得到U/IND(c1)={{x1，x3，x5}，{x2，x4}}= {C1，C2}，其一致性为0，因此其依赖度γci(D)=0，其重要 度 也 为 0。 依 次 ，计 算 出Sigl(c2，Redl，D)=2/5 ，Sigl(c3，Redl，D)=1/5 ，Sigl(c4，Redl，D)=0，Sigl(c5，Redl，D) =0，之后选取重要度最大值的特征加入候选特征集Red中，并保存相应特征的重要度，此时Redl={c2}；之后从其他特征中选择重要度最大值的特征，比如特征c1，对条件特征集合c1∪c2进行划分等价类，得U/IND(c1∪c2)={{x1，x5}，{x2，x4}，{x3}}={C1，C2，C3}，其依赖度为 γ(c1∪c2)(D)=3/5，重要度为 Sigl(c1，c2，D)=3/5−2/5=1/5。依次计算得出特征的重要度为1/5、1/5、1/5。选其中一个特征加入候选子集并记录其重要度，此时候选子集Redl={c1∪c2}；依次步骤计算相应特征的重要度并获取候选子集。

对于无标记数据部分，采用知识粒度方法进行数据粒化来处理该类学习任务。首先，令GD(∅)=1，对于单个特征进行划分等价类，比如c1特征，我们可以得到等价类为U/IND(c1)={{x6，x8，x10}，{x7， x9}}，根据知识粒度公式，可得辨识度为GD(c1)=(32+22)/(5)2=13/25，重要度为Sigu(c1，∅)=12/25。依次可计算出其他特征的重要度为12/25、12/25、8/25、12/25。此时的候选子集为Redu={c1}，并记录该特征的重要度；之后计算除了候选子集的特征重要度，比如特征c2，通过对条件特征集合c1∪c2进行等价类划分，得到U/IND(c1∪ c2)={{x6，x10}，{x7，x9}，{x8}}，其 辨 识 度为 9/25，其重要度为4/25，依次算出其他特征的重要度为6/25、4/25、4/25。选择 c3特征加入候选子集中，并记录该特征的重要度，此候选子集为Redu={c1∪c3}；依次计算相应特征对应的重要度，并获取候选子集。

在获得有标记数据部分中特征对应的重要度以及无标记数据部分中特征的重要度后，根据定义10进行融合计算特征在半监督数据下的重要度，并获取在半监督数据下的候选特征子集。

4 实验对比与分析

4.1 数据集和数据预处理

为验证本文提出的半监督特征选择算法的可行性，从UCI数据集中选取了8个公共数据集进行测试和分析，数据集的详细信息如表2所示。实验的测试环境为：CPU为i5-4590S CPU @ 3.00 GHz，内存为8.0 GB，操作系统为Window 10， 采 用 Pycharm 和 MATLAB 平 台 进行编程。

数据预处理实验进行测试和分析的过程中，将UCI数据集根据标记比例α进行划分为有标记数据和无标记数据［27-28］。在本文中，α的取值为0.2，即有标记数据的比例的取值为20%；并将数据集划分为无标记样本的标记信息设为空值构成半监督数据。

4.2 评估标准和算法比较

本文选用分类准确率作为评估标准。为了保证对比实验的公平性，本文选取了3种不同的分类器进行测试，即K近邻分类器（KNN）、SVM分类器和决策树分类器（DT）［29］。本文算法以及对比方法均基于十倍交叉验证方法对数据集进行特征选择，根据特征选择结果在此三种分类器上的分类性能验证算法的可行性。本文实验选取了4种半监督特征选择对比算法 ，分 别 为 Semi-JMI［30］、Semi-MIM［30］、Semi-P［31］和 Semi-D［31］方法。

4.3 实验结果与分析

为了验证算法的有效性，与当前四种半监督特征选择方法Semi-JMI、Semi-MIM、Semi-P和Semi-D在有标记数据比例为20%的情况下进行对比，并采用KNN、SVM和CT三种不同分类器下的分类精度作为约简结果如表3—5所示，粗体表示分类精度最高值。其中Rank（↓）为在实验方法中精度值排名序号值的平均值，该值越小表示该实验方法的性能更好，Win/Tie/Loss表示实验方法与其他对比方法表现性能“更好/相等/更低”的数量对比。

由表3—5的实验数据可得，采用Semi-CG半监督特征选择方法在八个真实数据集的标记数据比例为20%的特征选择结果在三种不同分类器下的分类性能有较明显的优势。实验结果表明Semi-CG方法可以有效充分利用未标记数据的信息，选择出对分类性能较好的特征子集。另外在处理未标记数据时，采用知识粒度方法考虑特征对整个样本空间的可区分性可以充分利用未标记数据特征信息进而获取更为可靠的特征子集。

为了进一步详细分析特征子集对分类性能的影响，本文以有标记数据比例为20%的情况为例，在Optdits和Letter这两个数据集上，计算并记录特征选择结果在KNN、SVM和DT分类器上的分类精度随特征个数的增加变化的趋势结果，如图1−3所示。

由图1−3可以看出，Semi-CG方法较比其他四种半监督特征选择方法，在大部分的情况下，分类精度相对较高。在分类器KNN上，数据集Optdits在随着特征个数的增加，其分类精度也随之增加，增加的幅度也随之趋于稳定，KNN分类器在Semi-CG方法下训练的分类模型较好，在Letter数据集上的趋势也是显示增加的趋势，在大部分情况下，Semi-CG方法的分类性能较优。在其他分类器下的情况也呈现相同趋势，但在分类器SVM，数据集Letter下，其分类精度的增加趋势与其他方法性能较为接近。

综上，随着数据的特征数目的增加，Semi-CG算法的分类性能也随之增加，并在大部分的情况下优于其他半监督特征选择方法。本文算法可以更有效地利用无标记数据中的信息，提高特征选择结果的分类性能。

5 结论

粗糙集和粒计算是数据挖掘的强有力工具。针对数据的标注代价过高，本文采用粒计算更有效的获取无标记数据的信息进行特征选择，本文利用知识粒度方法详细分析特征空间中特征的相关性获取更多未标记数据的信息，并结合依赖度分析有标记数据中特征与标记的相关性进行特征选择，提高了分类精度。实验分析表明，Semi-CG半监督特征选择方法8个UCI数据集以及三个不同分类器上能够获得分类性能较好的特征约简结果。目前，本文主要是针对单标记数据进行半监督特征选择，下一步工作将研究在多标记数据情况下半监督特征选择工作。