0 引言

由于现实生活中存在大量的无标记样本, 而有标记样本非常有限。因此, 利用少量有标记样本和大量无标记样本共同训练分类器的半监督学习算法应运而生^{[1, 2]}。自训练算法^{[3, 4]}是半监督学习算法中的一种, 它先用少量有标记样本训练分类器, 再选出高质量的无标记样本加入到有标记样本集中, 迭代循环直至算法收敛。自训练算法的简单有效性, 使得该算法广泛应用于文本分类^[5]、图像处理^[6]、地形识别^[7]等多个领域。

自训练过程中, 如何选取高质量样本进行训练, 成为广大学者争相研究的课题。由于朴素贝叶斯算法具有简单、高效和稳定性强等特点, 部分学者将朴素贝叶斯计算得出的后验概率作为置信度选取高质量样本。文献[8]引入一种改进的朴素贝叶斯算法, 该算法通过将集成分类器最大后验概率与朴素贝叶斯后验概率之和作为置信度, 解决了重复出现最大后验概率值的问题, 有利于选取高质量样本。Taheri等^[9]提出了一种新的属性加权朴素贝叶斯分类器, 该分类器考虑了条件概率的权重, 其中目标函数是基于朴素贝叶斯分类器的结构和属性权重建立的, 它的最佳权重由局部优化方法确定, 来源于真实世界数据集上的实验结果显示了所提方法的有效性。董立岩等^[10]根据类别C_i的后验概率与非C_i类的平均概率之差作为置信度, 选取置信度最大的h个样本加入训练集, 提出了一种基于半监督学习的新型半监督朴素贝叶斯算法, 该方法通过将选出的高质量样本加入训练集进行训练, 提高了分类正确率。张维等^[11]首先将朴素贝叶斯分类器作为初始分类器对有标记样本进行分类, 然后对无标记样本使用EM算法, 迭代训练初始分类器, 在Amazon. cn数据集上的实验结果表明, 该方法提升了算法的有效性。

样本的空间结构包含着重要信息, 在利用好这些信息的基础上选取高质量样本能大大提升自训练算法的性能。针对传统朴素贝叶斯自训练方法未能利用样本空间结构所含信息的问题, Gan等^[12]提出用半监督模糊C均值聚类(semi-supervised fuzzy C means, SFUC)来改进自训练算法。他们认为无标记样本可能含有数据空间结构的潜在信息, 利用这些信息能更好地辅助自训练。半监督度量的模糊聚类算法(semi-supervised metric-based fuzzy clustering algorithm, SMUC)通过学习马氏距离来取代模糊C均值中的欧式距离, 文献[13]使用SMUC改进自训练, 效果好于SFUC。以上两种方法很好地利用了空间结构所包含的样本信息, 实验结果证实了所提方法的可行性和有效性。Karlos等^[14]计算出无标记样本与有标记样本间的距离, 选取离类中心最近的h个样本进行朴素贝叶斯分类。该方法在一定程度上考虑到了整个样本空间结构对分类正确率的影响。

在文献[14]的工作基础上, 本文提出了一种使用加权K-最近邻[15, 16(] K-nearest-neighbor, KNN)改进朴素贝叶斯自训练的算法(improved naive Bayesian self-training algorithm based on weighted K-nearest neighbors, WKNNNBST), 采用加权K-最近邻的方法通过样本间的距离以及加权核函数得出无标记样本的隶属度。该隶属度在一定程度上能反映出样本空间潜在的结构, 在一个较好的空间结构上对未标记样本分类, 能有效提升分类正确率。

1 本文算法 1.1 算法思想

在传统的半监督朴素贝叶斯自训练过程中, 使用朴素贝叶斯计算置信度时, 是通过以往的经验和分析得出的先验概率来决定后验概率从而得出样本所属类别置信度^[17], 这样会使分类决策存在一定的错误。在自训练过程中, 选择未标记样本时可能会将大量带有错误类标号的样本添加到训练集中, 再一次次地迭代, 降低了分类正确率^[18]。但如果未标记样本与已标记样本在空间结构上距离越近, 那么该未标记样本所含的信息也就更准确, 分类时将会得出更高的正确率。但传统朴素贝叶斯在自训练过程中并未考虑到整个样本集的空间结构对分类正确率的影响。

为了解决传统朴素贝叶斯自训练算法存在的以上问题, 本文提出了基于加权KNN改进朴素贝叶斯自训练的算法。加权KNN计算未标记样本在特征空间中的K个最相似(即特征空间中最邻近)样本的过程中, 会采用距离公式计算未标记样本与每个已标记样本间的距离, 再用第K+1个近邻距离来标准化前K个近邻距离, 然后用加权函数将标准化距离转化为未标记样本与已标记样本的同类概率, 最后根据K个近邻求出未标记样本属于每个类的后验概率, 随即计算出未标记样本属于每个类的隶属度。因此, 隶属度的高低能很好地反映出整个样本集的空间结构, 当某个无标记样本的最大隶属度较高时, 说明该无标记样本在空间结构上离真实样本的类中心越近, 所含的信息也更准确。所以, 在一个较好的空间结构上对未标记样本进行分类, 充分地利用了样本的空间结构信息, 能很好地降低自训练过程中的迭代错误。

基于以上分析, 本文算法首先用加权KNN选出无标记样本中最大隶属度较高的前h个样本, 再用朴素贝叶斯分类器对这h个样本进行分类, 随后选取分类置信度高的前f (f < h)个样本加入到有标记样本中进行下一次训练。这样, 降低了自训练过程的错误累积, 从而提高了算法的分类精度。利用WKNNNBST算法生成数据类标号的过程如图 1所示。其中L表示有类标号的样本集, U表示无类标号的样本集, Top h表示从无类标号样本集中选取隶属度高的h个样本, Top f表示从隶属度高的h个样本集中选取置信度高的f个样本, WKNN(weighted K-nearest neighbors algorithm)表示加权K-最近邻算法, NBC(naive Bayes classifier)表示朴素贝叶斯分类器。

1.2 基于加权KNN的隶属度的选择

在自训练学习过程中, 如果未标记样本离已标记样本空间距离越近, 那么它的隶属度也相对更大, 标注的隶属度越大的样本, 所得到的类标号与真实的类标号更可能相同, 可以用最大后验概率来代表属于某个类的隶属度。

设有类标号的数据集L={(x_i, y_i) }, 其中: 为训练样本, n为x_i个数, y_i是x_i对应的类标号, , 无类标号的数据集U={x_{n + 1}, x_n+2, …, x_m}。d(x_t, x_i)为样本x_t与它的k+1近邻的距离, i=1, 2, …, k + 1。用它的第k+1个近邻到x_t的距离来标准化前k个近邻到x_t样本的距离, 则有

(1)

然后用加权核函数, 将标准化距离转化为x_t和x_i的同类概率P (x_i|x_t), 则有

(2)

最后根据x_t的k个近邻求出x_t属于类ω_r(r=1, 2, …, s)的后验概率, 则有

(3)

其中

(4)

(5)

则无标记样本的隶属度可以定义为

(6)

这样便得出了KNN分类器的隶属度^[19]。

1.3 WKNNNBST算法流程

输入:有类标号的样本集L, 无类标号的样本集U。

输出:测试集Test的预测类别C, 分类正确率R。

步骤:

Step 1  通过样本集L和U训练加权KNN分类器, 从而得出U中所有样本的分类隶属度, 然后选出每个未标记样本所属类别的隶属度的最大值。

Step 2  再将每个未标记样本的最大隶属度按降序排序, 选出U中隶属度高的前h个样本。

Step 3  将选出的h个样本用朴素贝叶斯分类器进行再一次分类, 并将得到的置信度按降序排序。

Step 4  在Step 3中选出置信度高的前f个样本, 其中f小于h。

Step 5  将选出的f个样本以及对应的类标号加入到L集形成更新后的L集。

Step 6  原始U集对应减去挑选出的f个样本集, 形成新的U集。

Step 7  重复Step1到Step 6, 直到U集为空。

Step 8  循环结束, 利用新得到的L集来预测Test中的样本所属类别C, 并计算预测正确率R。

2 仿真实验 2.1 实验算法及说明

为了说明本文算法的有效性, 设计了5个对比算法, 在9个数据集上的对比实验。选用的算法如下:

① 朴素贝叶斯算法(Naive Bayes, NB)。

② 朴素贝叶斯自训练算法(Naive Bayes selftraining, NBST)。

③ 基于文献[10]提出的半监督朴素贝叶斯新算法(Novel semi-supervised Naive Bayes, NSNB)。

④ 基于文献[13]提出的半监督基于度量的模糊聚类自训练(semi-supervised metric-based fuzzy clustering self-training, SMUCST)。

⑤ 传统的半监督K最近邻算法结合朴素贝叶斯算法(K-nearest neighbor combined with Naive Bayes, KNNNB)。

实验的数据来源于UCI以及Kaggle数据集, 共9个(如表 1)。对数据集Lonosphere和Image Segmentation做预处理, 删除其中的离散属性列。

实验中, 把每组数据随机分成训练集和测试集, 其中训练集占80%, 测试集占20%。再在训练集中随机选取10%做初始化有标记样本, 其余样本除去类标签后作为无标记样本。所有算法进行十折交叉验证, 取10次平均分类正确率。

算法NBST、NSNB、SMUCST以及本文算法在自训练迭代过程中所涉及的参数h的取值为无标记样本数量的20%。本文算法所涉及的另一参数f的取值及对应的正确率±标准差见表 2。从表 2可以看出, 在初始有标记样本数量为30%的情况下, f取不同的值对分类正确率的影响。当f=50%×h时, 本文算法整体上效果更好。因此, 在2.2节中, 取f=50%×h进行实验说明。

2.2 实验结果及分析

训练集中随机选取10%做初始化有标记样本, 取10次平均分类正确率±标准差, 如表 3所示, 其中加粗的数据说明在该算法上分类效果最好。本文所提算法与5个对比算法的正确率提升效果如表 4所示。

如表 3所示, 当有标记样本比例为10%时, WKNNNBST算法性能整体上优于对比算法, WKNNSNBST算法在数据集Seeds、Iris、User knowledge modeling、Wine、Abalone、Breast cancer coimbra以及Image segmentation上的正确率均高于其余算法。但在数据集User knowledge modeling上, 本文算法相对与对比算法表现较差, 这主要是因为该数据集自身性质所决定的, 其属性值本身很小, 且属性值之间的差距不大, 当WKNN在计算已标记样本与未标记样本之间的欧氏距离差值过小, 导致类别之间的区分度不大, 影响了最后的分类正确率。

如表 4所示, 当有标记样本比例为10%时, WKNNNBST算法的正确率较其他5个算法整体有提升。可在数据集User knowledge modeling上, 本文算法的正确率却不如NB、SNBST以及NSNB, 这主要是因为属性值过小, 导致WKNN计算属性值之间距离时区分不明显, 使得WKNN很难有效的辅助朴素贝叶斯自训练, 从而降低了算法性能。

为了说明初始有标记样本数对算法的影响, 图 2给出了当初始化有标记样本比例分别为10%、20%、30%、40%以及50%的时候, 做十折交叉验证, 6个算法在9个数据集上的平均分类正确率。

从图 2可以看出, 本文算法在9个数据集上整体优于对比算法, 尤其是在Iris、Wine、Pima、Lono- sphere以及Image segmentation这5个数据集上, 该算法在有标记样本比例极少的情况下正确率较高于其他算法。这是因为本文算法在选择未标记样本时先用加权KNN选出了空间结构上离有标记样本更近的数据, 在此基础上用朴素贝叶斯分类器选取更高置信度的可靠样本加入训练集, 解决了部分样本被误标记的问题, 从而提高了分类正确率。但随着有标记样本比例的增加, 本文算法与对比算法正确率整体趋于稳定, 可以看出在有标记样本足够多的情况下, 样本所含信息量越大, 算法的性能相对也更好。但算法SMUCST在数据集Iris、User knowledge modeling、Wine以及Lonosphere上正确率相对较低, 这可能因为这些数据属性之间相关性较弱, 导致正确率降低。而算法NB、NBST、NSNB、KNNNB以及WKNNNBST都有涉及到朴素贝叶斯分类器, 该分类器对样本属性之间关联不强的数据集有更好的表现力。从图 2中还可以看出在数据集Iris、User knowledge modeling以及Pima上用半监督KNNNB算法计算得出的正确率相对较低, 这不仅与数据集本身的特点有关, 也与KNN算法的特性有关的, 该算法只计算"最近的"邻居样本, 某一类的样本数量很大时, 输入新样本邻居中大容量类的样本占多数, 这就容易导致最终分类出错。因此, 本文选取不易受不平衡样本影响的加权KNN进行实验。观察图 2可发现, 在初始有标记样本占比逐渐增加时本文算法与对比算法的准确度整体上越来越接近, 这是因为当有标记样本数量足够的情况下, 以上所有算法的准确度会逐渐趋于稳定。本文算法主要运用于半监督学习, 半监督学习是基于有标记样本缺失较多的情况下提出的。因此, 本文算法更利于在有标记样本极其缺失的环境中进行分类, 对比实验证实了本文提出的分类算法在各个数据集上均占有一定优势。

3 结语

传统朴素贝叶斯自训练算法是根据以往的经验和分析得出的先验概率来决定后验的概率, 从而得到样本所属类别置信度, 这就容易导致分类决策存在一定的错误, 且整个过程并未利用到训练样本空间结构所包含的信息。针对以上问题, 本文提出了基于加权KNN改进朴素贝叶斯自训练的算法。该算法充分地利用了样本的空间结构信息, 使传统朴素贝叶斯分类器在一个较好的空间结构上对未标记样本进行分类, 确保了每次添加的都为更高质量的样本, 减少迭代过程中的错误累积。在UCI及Kaggle数据集上的对比实验证实了本文提出的算法性能优于其他对比算法。在后续工作中, 将讨论如何通过多个分类器共同对未标记样本分类, 从而选取分类都正确的样本来扩充训练集的问题, 以及如何对大量数据更多分类的样本进行准确分类的问题。