2021, Vol. 53
大数据背景下，随着数据获取工具的迅速发展和数据存储技术的不断进步，数据库中存储的数据集的规模也越来越庞大，这给传统的数据挖掘技术带来了严峻而全新的挑战。众所周知，为数据样本确定类标签需要耗费一定的时间以及相应的技术支撑。而随着数据规模的日趋庞大，为所有数据样本确定类标签的代价也随之变得异常昂贵。这显然也是目前大数据背景下分类问题中面临的挑战之一。面对规模异常庞大的数据集，通常只能为其中一小部分确定类标签，而大量存在的是无标记的数据样本。为有效处理这类数据集，众多研究者引入了半监督学习机制来处理部分标记数据的学习任务[1-6]。
特征选择是数据挖掘技术中一种常用的数据预处理技术，对给定数据集进行有效特征子集的选取，只保留对学习任务贡献较大的特征，可有效提高学习模型的泛化能力，降低过拟合以及计算耗时[7-13]。面对部分标记数据集，半监督特征选择算法也引起了众多研究者的广泛关注，并取得了一定的研究成果。文献[14]将有标记样本和无标记样本相结合度量特征的相关性，设计了基于图论的半监督处理机制。文献[15]同时基于无标记样本和有标记样本来构造基于数据的图结构，进行特征选择。文献[16]设计了基于多目标优化理论的半监督特征子集选取机制。文献[17]通过计算特征间相关性来构造特征的近邻，进行有效特征子集的选取。文献[18]将流形学习引入特征选择中，提出了基于流形正则化的半监督特征选择方法。此外，文献[19-20]基于粗糙集理论，定义了半监督意义下新的特征重要度的度量，并给出了相应的特征选择算法。文献[21]基于最大相关最小冗余的特征选择求解策略，分别基于有标记数据和无标记数据给出了相关性和冗余性的计算公式，并给出了相应的半监督特征选择求解过程。在此基础上，为进一步充分利用数据库中大量无标记数据集，本文基于Relief-F算法设计一种面向符号数据的半监督特征选择算法。
Relief-F系列算法的主要特点是基于分析近邻样本对类别的区分能力来确定特征的权重，即特征重要度。其核心思想是：一个优秀的特征应该使得同类的样本更加靠近，而使得不同类的样本更加分散。Relief-F系列算法提出以来已经在许多算法和应用中被广泛使用。针对部分标记的符号数据，本文中首先引入了一种基于耦合学习的样本相似度度量，可更有效地度量符号型数据样本的相似性[22-23]。在此基础上，将Relief-F算法进行拓展用于处理部分标记数据。
本文首先介绍了基于耦合学习的数据样本相似度，然后提出了基于Relief-F的半监督特征选择算法，最后为实验结果及分析。
1 对象的耦合相似度数据样本间的相似度依赖于样本对各个特征取值之间的相似度。对于符号型数据，由于数据取值的无序性，显然不能通过计算距离直接比较。一些研究者通过分析数据取值间的耦合特性，提出了基于耦合学习的符号取值相似度度量(coupled attribute similarity for objects，CASO)[20]。基于耦合的数据取值相似度既考虑了同一特征内部特征取值之间的相似性(intra-coupled attribute value similarity，IaASV)，同时又考虑了其余特征对当前特征取值相似性的贡献(inter-coupled attribute value similarity，IeASV)。该相似度主要通过分析属性值的频率分布和特征间的依赖聚合度来确定最终的相似度度量[23], 具体介绍如下。
定义1 给定一个信息表Sn×m, 则数据表中的对象ux、uy之间的对象耦合相似度CASO(ux, uy)为
| $ CASO({u_x}, {u_y}) = \sum\limits_{j = 1}^m {\delta _j^{Ia}} (v_j^x, v_j^y) \cdot \delta _j^{Ie}(v_j^x, v_j^y, {\{ {V_k}\} _{k \ne j}})，$ |
其中：δjIa为IaASV；δjIe为IeASV；m表示特征的个数；vjx、vjy为在特征j下ux、uy所对应的属性值。
定义2 给定一个信息表Sn×m，对于给定属性值vjx、vjy的特征内耦合属性相似度为
| $ \delta _j^{Ia}(v_j^x,v_j^y) = \frac{{\left| {{G_j}(\{ v_j^x\} )} \right| \cdot \left| {{G_j}(\{ v_j^y\} )} \right|}}{{\left| {{G_j}(\{ v_j^x\} )} \right| + \left| {{G_j}(\{ v_j^y\} )} \right| + \left| {{G_j}(\{ v_j^x\} )} \right| \cdot \left| {{G_j}(\{ v_j^y\} )} \right|}}, $ |
其中：Gj({vjx})、Gj({vjy})为在特征j下属性值等于vjx、vjy的集合。
IaASV是从属性值的频率分布的角度来形容同一特征下属性值之间的相似程度[23]。定义2考虑了在同一特征内部属性值vjx、vjy之间的关系。但是实际数据中，同一特征下的不同取值之间的相似度不仅取决于它们本身，还取决于它们所处的环境，即其余特征对它们相似度的影响。因此，在定义2的基础上，定义3给出了Aj以外的特征At(At≠Aj)对Aj上取值vjx、vjy间相似度的度量。
定义3 给定一个信息表Sn×m，对于给定属性值vjx、vjy的特征间耦合属性相似度为
| $ \begin{array}{l} {\delta ^{Ie}}(v_j^x, v_j^y, {\{ {V_k}\} _{k \ne j}}) = \mathop \sum \limits_{{\rm{ }}k = 1, k \ne j}^n {\alpha _k}{\delta _{j\left| k \right.{\rm{ }}}}(v_j^x, v_j^y, {V_k}), {\rm{ }}{\delta _{j\left| k \right.}}(v_j^x, v_j^y, {V_k}) = \mathop \sum \limits_{{v_k} \in \cap } {\rm{min}}\{ {P_{k\left| j \right.{\rm{ }}}}(\{ {v_k}\} \left| {v_j^x} \right.), {P_{k\left| j \right.{\rm{ }}}}(\{ {v_k}\} \left| {v_j^y} \right.)\} , {\rm{ }}\\ {P_{k\left| j \right.{\rm{ }}}}(\{ V{'_k}\} \left| {{v_j}} \right.) = \frac{{\left| {{G_k}(\{ V'{_k}\} ) \cap {G_j}(\{ {v_j}\} )} \right|}}{{\left| {{G_j}(\{ {v_j}\} )} \right|}}{\rm{ }}, \end{array} $ |
其中：αk是特征Ak(k≠j)的权重参数，
经典Relief-F特征选择算法的核心思想是，首先从数据集中随机选择一个样本，然后分别从该样本的同类和不同类中均选择出k个最近邻样本，通过分析该样本同其近邻间的距离(或相似度)来更新特征的权重。其更新权重的意义在于减去选定样本与其同类近邻在该特征上的差异，增加选定样本与其不同类近邻在该特征上的差异。在此基础上重复抽取多个样本，上述过程重复迭代多次，最终每个特征得到一个平均权重。最后根据权重值的大小可对特征进行排序。
为更好地度量符号数据样本间的相似度，本节中引入定义1~3的耦合相似度(CASO)来求解给定样本的近邻，并在此基础上，将半监督学习机制引入经典Relief-F算法中，对其进行拓展。具体的算法思想为：先从有标记数据中随机抽取数据样本s(假设s的类别为yi)，然后从其余每一类yj(i≠j)中选择一个s的最近邻xj；在所有未标记数据中计算并选取出s和所有xj的k个最近邻样本；基于在无标记数据集中求解到的所有近邻并结合Relief-F算法更新特征的权重。该算法的具体算法流程介绍如下。
算法1 基于Relief-F的半监督特征选择算法(semi-supervised feature selection based on Relief-F，SFSR)。
输入:训练集S=S1∪S2，其中S1为有标记数据，S2为无标记数据，特征个数m，类别集C。
输出:特征的权重值wk(k=1, 2, …, m)。
步骤1初始化特征权重wk=0, k=1, 2, …, m。
步骤2循环执行步骤2.1~2.4 M次。
步骤2.1从有标记样本集S1中随机选择一个样本s，s的类别为cq(cq∈C)。
步骤2.2从无标记样本集S2中，基于定义1求解s的d个近邻，标记为Htq(t=1, 2, …, d)。
步骤2.3在其余的每一类cp∈C(p≠q)中基于定义1求解样本s的一个最近邻样本x，并在无标记样本集中求解x的d个近邻，记为Mtp(t=1, 2, …, d)。
步骤2.4基于公式(1)更新所有特征的权重
| $ {w_k} = {w_k} - \mathop \sum \limits_{t = 1}^d \frac{{D({A_k}, s, H_t^q)}}{{Md}} + \mathop \sum \limits_{p \ne q} \frac{{P({c_p})}}{{1P({c_p})}}\mathop \sum \limits_{t = 1}^d \frac{{D({A_k}, s, M_t^p)}}{{Md}}, $ | (1) |
其中：
步骤3返回结果wk(k=1, 2, …, m)。
算法1对经典Relief-F算法的拓展主要有两个方面：1)引入基于耦合学习的相似度度量来计算给定样本的近邻；2)从无标记样本中寻找给定样本的近邻，充分利用了无标记样本信息。而基于样本近邻来更新特征权重的公式(步骤2.4)仍是使用的经典Relief-F算法中的更新公式。
3 实验分析为验证上述提出的基于Relief-F的半监督特征选择算法, 选取了5组UCI数据集。实验程序所用语言为Python 3.6，程序开发平台为Anaconda Spyder。程序所运行的计算机配置为：CPU Inter(R)CoreTM i5-3230, 2.60 GHz；内存为8 GB；操作系统为Windows 7。数据集的描述见表 1。
|
表 1 数据集描述 Tab. 1 Data sets |
在实际情况中，大部分数据集中已标记的数据占比都比较小，因此在本实验中考虑了数据集中无标记数据占总数据集70%、80%、90%这三种情况。由于针对面向符号数据的半监督特征选择算法的研究还相对较少，实验中所选取的对比试验为前向半监督算法(FSFS)[24]。在此基础上，本节中选取了机器学习中常用的三个分类器logistic、支持向量机(SVM)、朴素贝叶斯(NBC)来进一步验证特征选择结果的有效性。表 2~4分别给出了三种情况下由特征选择算法SFSR和FSFS对表 1中5个数据集选择得到的特征个数和由选择结果诱导的分类精度的比较。其中N表示特征选择结果中特征的个数，分类精度表示由特征选择结果分别在上述三个分类器上通过十折交叉验证得到分类精度，表中数值的前面部分表示十次分类正确率的均值，后面部分表示平均绝对误差。本节中使用的分类器和精度计算方法均集成在数据挖掘软件weka中。另外，表 2~4中加粗的内容表示由不同特征选择算法得到的特征选择结果在相同分类器上得到的分类精度较高的值，例如表 2数据集backup-large由本文算法得到的选择结果在分类器logistics和SVM上分类精度高于由算法FSFS的结果在这两个分类器上的精度，而在分类器NBC上的分类精度则低于算法FSFS的选择结果在该分类器上的精度。
|
|
表 2 无标记数据为70%的情况下特征选择结果的分类精度比较 Tab. 2 The experimental results of classification accuracy on feature subsets with 70% unlabeled objects |
|
|
表 3 无标记数据为80%的情况下特征选择结果的分类精度比较 Tab. 3 The experimental results of classification accuracy on feature subsets with 80% unlabeled objects |
|
|
表 4 无标记数据为90%的情况下特征选择结果的分类精度比较 Tab. 4 The experimental results of classification accuracy on feature subsets with 90% unlabeled objects |
由表 2~4的实验结果可得，本文所设计的基于Relief-F的SFSR算法在5个UCI数据集上选择出的特征子集所得出的分类精度结果大部分都高于或持平于FSFS算法所得出的结果。上述实验结果进一步验证了本文提出的基于Relief-F的SFSR算法的有效性。但是由于本文新算法在求解样本近邻过程中使用的相似度度量需要综合考虑特征取值在所有特征下的相似度，因此新算法的计算效率还有待进一步提高。下一步的研究工作会包括对算法效率的探索和分析。
4 结论针对符号型部分标记数据集，本文通过引入一种基于耦合学习的数据样本相似度，设计了一种基于Relief-F算法的半监督特征选择算法，算法中综合考虑了有标记数据和无标记数据来求解选定样本的近邻，进而更新特征的权重值。为有效验证提出新算法的可行性，实验分析中选取了5组UCI数据集和3种常用机器学习分类器来对新算法的性能进行验证，实验结果进一步验证了算法的有效性。该算法可以充分利用无标记数据信息来更新特征权重值，所得出的特征子集也有效提高了分类器的分类精度。为后续的半监督数据挖掘技术提供了可以借鉴的新思路。
| [1] |
BENABDESLEM K, HINDAWI M. Efficient semi-supervised feature selection: constraint, relevance, and redundancy[J]. IEEE transactions on knowledge and data engineering, 2014, 26(5): 1131-1143. DOI:10.1109/TKDE.2013.86 (  0) |
| [2] |
HUSSAIN A, CAMBRIA E. Semi-supervised learning for big social data analysis[J]. Neurocomputing, 2018, 275: 1662-1673. DOI:10.1016/j.neucom.2017.10.010 ( 0) |
| [3] |
NAKATANI Y, ZHU K Y, UEHARA K. Semisupervised learning using feature selection based on maximum density subgraphs[J]. Systems and computers in Japan, 2007, 38(9): 32-43. DOI:10.1002/scj.20757 ( 0) |
| [4] |
FORESTIER G, WEMMERT C. Semi-supervised learning using multiple clusterings with limited labeled data[J]. Information sciences, 2016, 361/362: 48-65. DOI:10.1016/j.ins.2016.04.040 ( 0) |
| [5] |
陈潇, 李逸薇, 刘欢, 等. 基于网络表示的半监督问答文本情感分类方法[J]. 郑州大学学报(理学版), 2020, 52(2): 52-58. CHEN X, LEE S, LIU H, et al. A semi-supervised sentiment classification method towards question-answering text based on network representation[J]. Journal of Zhengzhou university (natural science edition), 2020, 52(2): 52-58. ( 0) |
| [6] |
刘杰, 刘欢, 李寿山, 等. 基于双语对抗学习的半监督情感分类[J]. 郑州大学学报(理学版), 2020, 52(2): 59-63. LIU J, LIU H, LI S S, et al. Semi-supervised sentiment classification with bilingual adversarial learning[J]. Journal of Zhengzhou university (natural science edition), 2020, 52(2): 59-63. ( 0) |
| [7] |
岳文琦, 张楠, 童向荣, 等. 混合决策信息系统的模糊效用三支决策模型[J]. 郑州大学学报(理学版), 2020, 52(1): 24-32. YUE W Q, ZHANG N, TONG X R, et al. Fuzzy utility three-way decisions model in hybrid decision information systems[J]. Journal of Zhengzhou university (natural science edition), 2020, 52(1): 24-32. ( 0) |
| [8] |
解滨, 董新玉, 梁皓伟. 基于三支动态阈值K-means聚类的入侵检测算法[J]. 郑州大学学报(理学版), 2020, 52(2): 64-70. XIE B, DONG X Y, LIANG H W. An algorithm of intrusion detection based on three-way dynamic threshold K-means clustering[J]. Journal of Zhengzhou university (natural science edition), 2020, 52(2): 64-70. ( 0) |
| [9] |
DASH M, CHOI K, SCHEUERMANN P, et al. Feature selection for clustering-a filter solution[C]//IEEE International Conference on Data Mining. Maebashi City, 2002: 115-122.
( 0) |
| [10] |
DASH M, LIU H. Feature selection for classification[J]. Intelligent data analysis, 1997, 1(1/2/3/4): 131-156. ( 0) |
| [11] |
LIANG J Y, WANG F, DANG C Y, et al. A group incremental approach to feature selection applying rough set technique[J]. IEEE transactions on knowledge and data engineering, 2014, 26(2): 294-308. DOI:10.1109/TKDE.2012.146 ( 0) |
| [12] |
WANG C Z, HU Q H, WANG X Z, et al. Feature selection based on neighborhood discrimination index[J]. IEEE transactions on neural networks and learning systems, 2018, 29(7): 2986-2999. ( 0) |
| [13] |
KOHAVI R, JOHN G H. Wrappers for feature subset selection[J]. Artificial intelligence, 1997, 97(1/2): 273-324. ( 0) |
| [14] |
ZHAO Z, LIU H. Semi-supervised feature selection via spectral analysis[C]//Proceedings of the 2007 SIAM International Conference on Data Mining. Minneapolis, 2007: 641-646.
( 0) |
| [15] |
NAKATANI Y, ZHU K Y, UEHARA K. Semisupervised learning using feature selection based on maximum density subgraphs[J]. Systems and computers in Japan, 2007, 38(9): 32-43. DOI:10.1002/scj.20757 ( 0) |
| [16] |
HANDL J, KNOWLES J. Semi-supervised feature selection via multiobjective optimization[C]//The IEEE International Joint Conference on Neural Network. Vancouver, 2006: 3319-3326.
( 0) |
| [17] |
IZUTANI A, UEHARA K. A modeling approach using multiple graphs for semi-supervised learning[C]//International Conference on Discovery Science. Budapest, 2008: 296-307.
( 0) |
| [18] |
REN J T, QIU Z Y, FAN W, et al. Forward semi-supervised feature selection[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining. Osaka, 2008: 970-976.
( 0) |
| [19] |
LIU K Y, YANG X B, YU H L, et al. Rough set based semi-supervised feature selection via ensemble selector[J]. Knowledge-based systems, 2019, 165: 282-296. ( 0) |
| [20] |
DAI J H, HU Q H, ZHANG J H, et al. Attribute selection for partially labeled categorical data by rough set approach[J]. IEEE transactions on cybernetics, 2017, 47(9): 2460-2471. ( 0) |
| [21] |
XU J, TANG B, HE H B, et al. Semisupervised feature selection based on relevance and redundancy criteria[J]. IEEE transactions on neural networks and learning systems, 2017, 28(9): 1974-1984. ( 0) |
| [22] |
WANG C, DONG X J, ZHOU F, et al. Coupled attribute similarity learning on categorical data[J]. IEEE transactions on neural networks and learning systems, 2015, 26(4): 781-797. ( 0) |
| [23] |
WANG C, CAO L B, WANG M C, et al. Coupled nominal similarity in unsupervised learning[C]. Proceedings of the 20th ACM International Conference on Information and Knowledge Management. Glasgow, 2011: 973-978.
( 0) |
| [24] |
王锋, 刘吉超, 魏巍. 基于信息熵的半监督特征选择算法[J]. 计算机科学, 2018, 45(11A): 427-430. WANG F, LIU J C, WEI W. Semi-supervised feature selection algorithm based on information entropy[J]. Computer science, 2018, 45(11A): 427-430. ( 0) |