基于SOM神经网络的半监督分类算法

赵 建 华

(1. 西北工业大学计算机学院，陕西 西安 710072; 2. 商洛学院数学与计算机应用学院，陕西 商洛 726000)

·计算机软件理论、技术与应用·

基于SOM神经网络的半监督分类算法

赵 建 华1,2

(1. 西北工业大学计算机学院，陕西 西安 710072; 2. 商洛学院数学与计算机应用学院，陕西 商洛 726000)

为提高半监督分类的性能，提出一种基于SOM神经网络的半监督分类算法SSC-SOM。结合SOM的聚类特性，基于先聚类后标记的思想，充分利用有标记样本和未标记样本训练SOM分类器；将聚类的形成和有标记样本分配到各个聚类中同时进行，并根据有标记样本计算各个聚类的聚类中心；在整个未标记样本的范围内，根据聚类中心，使用K近邻算法对未标记样本进行标记，挖掘未标记样本的隐含信息。在UCI数据集中进行分类实验，其结果表明，SSC-SOM的分类率比SSOM提高2.22 %，且收敛性较好。

半监督学习；自组织特征映射神经网络；分类；聚类

0 引言

半监督学习是一种结合有监督学习和无监督学习的学习方法，综合利用少量有标记样本和大量的未标记样本来提高学习性能，是一个非常热门的研究方向[1]。半监督分类[2-3]利用大量未标记数据扩大分类算法的训练集，主要研究从有监督学习的角度出发, 当已标记训练样本不足时, 如何自动地利用大量未标记样本信息辅助分类器的训练。

将自组织神经网络(self-organizing feature maps,SOM)引入到半监督学习领域，设计基于SOM的半监督学习算法，是目前学者涉入较少的一个课题。孙雁飞等[4]提出一种基于半监督学习的GA-SOM聚类方法，该方法用半监督学习进行样本的初始化，利用SOM作为训练器对无标签样本进行聚类，并申请了专利。在该专利中，SOM仅仅用于处理半监督学习初始化后的数据。Shen Furao 等[5]提出一种基于自组织增量型神经网络(SOINN)的半监督自主学习算法，将SOINN作为学习器，通过输入数据的不同拓扑结构将其分类成不同的族群，并主动标签一些教师节点，用这些教师节点实现对所有未标签样本进行标记；然而，该算法仅仅使用最初的有标记样本训练分类器，使得算法对初始的已标签样本的依赖性太强；同时该算法严格地讲，并不是一种真正意义上的SOM半监督分类算法。Astudillo等[6]利用基于树拓扑结构SOM算法 (tree-based topology oriented SOM ,TTOSOM)进行半监督分类，首先使用TTOSOM建立随机的、有结构的网络拓扑结构，将网络分为几个聚类，将有标记的样本分配到不同的SOM的神经元中，最后在每个聚类中，实现对标记样本的分类。然而，在该算法中，如何将标记样本有效地分布到每个聚类中，本身就是一个较复杂的过程；同时在每个聚类中，用有监督分类算法实现对未标记样本进行标记，也只能在局部找到最优值。阳时来等[7]在已有的无监督生长型分层自组织映射GHSOM神经网络算法的基础上，提出一种半监督GHSOM算法，该算法借鉴cop-kmeans算法的半监督思想，使用Must-Link和Cannot-Link 2种约束关系作为先验知识，利用少量有标记的数据指导大规模未标记数据的聚类过程。该算法是一种半监督聚类算法，同样存在分类精度不高，分类结果不易统计等缺点。

针对以上问题，本文将SOM神经网络引入到半监督分类领域，提出一种基于SOM的半监督分类算法SSC-SOM (semi supervised classification algorithm based on SOM neural network)。SSC-SOM基于先聚类后标记的思想，扩充有标记样本的数目，提高算法的分类精度。它充分利用有标记样本和未标记样本训练分类器SOM，训练输入层和竞争层之间的权值W(1)，同时，充分利用有标记样本的标记信息，调整竞争层和输出层之间的权值W(2)，实现对样本的分类和类别预测；在训练SOM过程中，聚类的形成和有标记样本分配到各个聚类中同时进行，并计算各个聚类的聚类中心，在整个未标记样本的范围内，根据聚类中心，使用K近邻算法实现对未标记样本的标记，扩充有标记样本，反复迭代。最后，在UCI数据集进行分类实验，验证该算法的有效性。

1 SOM神经网络

自组织特征映射(SOM)神经网络是由芬兰学者Teuvo Kohonen 于1981 年提出的，是一种无监督聚类方法，它能将输入模式在输出层映射成一维或二维离散图形，识别环境特征并自动聚类[8]。

SOM结构如图1所示，包括输入层和竞争层2层结构，输入层的维数与输入样本向量维数一致，竞争层节点一般呈二维阵列分布，一个竞争层节点代表一个神经元。SOM 网络的基本工作原理为：网络学习过程中，当样本输入网络时，竞争层的各神经元通过竞争来获取对输入模式的响应，与输入样本距离最小的神经元成为竞争神经元；调整获胜神经元和相邻神经元权值，使其权值靠近输入样本；通过反复训练，各神经元被划分为不同区域，各区域对输入模型具有不同的响应特征，实现对输入模型的聚类[8]。

图1 SOM结构图

SOM可以对未标记样本进行无监督聚类，但是分类结果中同一类别数据对应不同的竞争层节点，竞争层节点的数目比实际类别的数目多。文献[9]将SOM改进为一种有监督的SSOM (supervised SOM)，在SOM 2层结构的基础上，增加了第3层——输出层，输出层的个数同数据分类类别数一致，每个输出节点代表一种数据类别。在进行网络学习训练时，根据每个输入样本的预测类别和实际类别是否相等，选取不同的权值调整公式对权值进行调整。它不仅调整输入层节点和竞争层优胜节点领域内的权值W(1)，而且调整输出节点和竞争层优胜节点领域内的权值W(2)。根据输入样本Xi的输出类别Yi和获胜神经元g对应的输出类别Og是否相等，进行权值调整。若Og=Yi，则根据公式(1) (2)调整神经元权值；否则，根据式(3) (4)调整神经元权值。通过2个权值的组合，便可以很容易实现对输入样本的类别进行分类和统计。

(1)

(2)

(3)

(4)

2 基于SOM的半监督分类算法

2.1 基本思想

本文基于“先聚类后标记”的思想，实现对未标记样本的标记和分类。大体的方法如下：利用聚类算法SOM对未标记样本集进行聚类，形成几个聚类中心；然后利用SSOM对有标记样本进行训练，使得有标记样本分布在每个聚类中心的区域内，形成聚类中心；最后，在包含标记样本和未标记样本的聚类中心的区域内，使用K近邻算法实现对未标记样本的标记,扩充有标记样本的数目[6,10-12]。

2.2 算法实现

首先，充分利用有标记样本集和未标记样本集的属性特征信息训练SOM，形成多个聚类，确定输入层和竞争层之间的权值W(1)；接着，利用有标记样本训练SSOM，确定竞争层和输出层之间的权值W(2)，根据有标记样本类别数确定聚类数和聚类的标记信息；然后，根据每个聚类中有标记样本计算出虚拟的聚类中心；最后，在每个聚类中，以虚拟的聚类中心为中心，使用K近邻算法实现对其他未标记样本进行标记，将新标记的样本扩充到有标记样本集中。算法的框架如图2所示，其具体步骤如下。

第1步：聚类过程。SOM是一种包括输入层和竞争层2层结构、基于聚类思想的无监督分类算法。在对SOM进行训练时，竞争层是根据输入层样本特征之间的距离进行动态调整、自动聚类，因此输入层和竞争层之间不需要样本的标记。SSOM是一种3层结构、基于聚类思想的有监督分类算法，是在SOM结构的基础上增加了1个输出层，输出层会根据样本的标记实现对样本的分类，竞争层和输出层之间需要有标记的样本进行训练。

基于以上事实，使用有标记样本集和未标记样本集共同训练SOM，形成SOM神经网络的竞争层节点布局，确定输入层和竞争层之间的权值W(1)。接着，使用有标记样本训练SSOM，确定竞争层和输出层之间的权值W(2)。使用权值W(1)和权值W(2)的组合形成m分类(即m聚类)，每一类都有一个类标记。

通过这样的处理方式，一方面能充分利用大量未标记样本和少量有标记样本的丰富信息，训练出竞争层分布合理、精确度高的SOM分类器，使有标记样本的分类布局更合理、更符合实际性，另一方面，结合标记样本的标记信息，实现每个聚类中都有标记样本，方便计算聚类中心，实现对未标记样本的标记。

第2步：寻找聚类中心。对于具有某一类标记的所有样本，按照式(5)计算该聚类中的虚拟聚类中心。该聚类中心之所以是虚拟的，是因为它是该聚类中所有有标记样本的平均值，并不一定是一个实实在在的、存在于标记集之中的真实样本。

(5)

式中：μi表示第i类样本的聚类中心；ni表示第i类样本的样本数目；xij表示第i类样本中第j个样本。

第3步：标记。使用K近邻方法给距离该聚类中心最近的k个样本使用类标记进行标记。对于每一个输入，计算其与聚类中心之间的距离。若其与某一个聚类中心的距离小于某一个阈值，则用该标记给这个未标记样本进行标记，将标记后的样本增加到训练集中。将标记后的样本添加到标记样本集，重新训练SOM，反复迭代。描述算法如表1所示。

表1 SSC-SOM算法过程描述

第4步：分类。使用最终的半监督分类器SSC-SOM实现对样本的分类。

为防止算法陷入局部最优点，在对每个输入样本进行标记时，不是从每个聚类的范围内寻找距离该聚类中心的最小值，而是从所有的未标记样本中寻找距离该聚类中心的最小值。

2.3 算法分析

SSC-SOM算法与SOM相比较，都根据输入层所有样本特征属性信息之间的距离进行动态调整，实现对样本的聚类，都充分利用了所有样本，包括有标记样本和未标记样本的特征信息；但是，SOM没有用到有标记样本的标记信息，这是一个巨大的浪费。SOM只能根据竞争层节点的数目进行聚类，聚类的类别比样本的实际类别要多，分类精度不高； SSC-SOM充分利用了有标记样本的标记信息，利用有标记样本调整竞争层和输出层之间的权值，实现对样本的分类和类别预测，分类精度更高。

SSC-SOM算法与SSOM算法相比较，都利用了有标记样本调整竞争层和输出层之间的权值，实现对样本的分类和类别预测。但是，SSOM仅仅用到有标记样本的信息，大量未标记样本中的隐含信息被浪费了； SSC-SOM充分利用了所有样本的信息训练输入层和竞争层之间的权值W(1)，同时，在聚类中通过K近邻算法扩充有标记样本的数目。很容易推测出，SSOM训练出的分类器精度不如SSC-SOM，这在实验部分得到了证明。

3 实验和结果分析

实验平台选用Intel Core2 Duo CPU 2.0GHz、内存2.0GB的PC，安装Windows XP 操作系统和MATLAB 7.8.0 (R2009.0a) 编程环境。

MATLAB程序中，实验参数选取如下：η1=0.8(学习率1)，η2=0.8(学习率2)，μ=0.2(权值系数)，M=12(竞争层神经元个数)，r=1.5(学习半径)，K=1。其中，终止条件F表示未标记样本集为空。学习率和权值系数为SSOM中的参数，不同的参数对SSOM的分类精度影响比较大，这里使用交叉验证方法[9]选取最优参数作为实验参数。

实验采用UCI数据(http：//archive.ics.uci.edu/ml/)中常用的6个数据集，如表2所示。

对于表2所选取的样本，将训练集和测试集的样本数目比例设为1∶1。将训练集分为有标记样本和未标记样本2种，按照有标记样本占训练集样本总数目的百分比不同，构造3类半监督分类实验数据集，百分比λ的计算公式如式(6)所示。λ的取值分别为5%、10%和20%。

(6)

表2 实验数据集

对于构造的3类半监督分类实验数据集，分别使用普通的SSOM分类算法(即训练集仅使用最初的有标记样本集训练SSOM分类器)、经典的半监督分类算法tri-training[13](其中分类器采用SSOM作为有监督分类算法)和本文提出的SSC-SOM算法(即SOM的训练集使用所有的有标记样本集和未标记样本集，使用SOM和SSOM扩充有标记样本数目，使用扩充后的有标记样本训练分类器)进行分类实验。按照式(7)统计实验结果， rate表示对测试集样本进行分类测试的正确分类率。实验结果如表3—10所示。

(7)

表3—6是SSC-SOM和SSOM的实验结果对比。表7—10是SSC-SOM和tri-training的实验结果对比。

从表3—5可以看出，相对于仅仅使用有标记样本训练分类器的SSOM而言，SSC-SOM分类率rate得到了提高，平均提高2.22 %(如表6所示)。这是因为：1)SSC-SOM充分利用有标记样本和未标记样本数据的信息训练分类器SOM，确定输入层和竞争层之间的权值W(1)，此时的W(1)更能准确反映出输入层到竞争层的映射关系，比SSOM算法得到的权值精确度要高；2)SSC-SOM在全局范围内使用K近邻算法对未标记样本进行标记，能有效地挖掘未标记样本的隐含信息，增加有标记样本的数目。所以，SSC-SOM训练出来的分类器比仅仅使用最初的标记样本训练出来的SSOM分类器精度要高，这也表明SSC-SOM能有效地增加有标记样本，具有较好的分类性能。

同时还可以看到，随着标记样本集数目不断增加，到达一定程度时，SSC-SOM和SSOM的分类率差距越来越小。这是由于此时有标记样本数目已经非常充足，半监督学习已经演化成有监督学习。这也反映出SSC-SOM算法具有较好的收敛性，分类率收敛于有监督学习SSOM (所有的训练样本都是有标记的)的求解，但是，该算法和SSOM一样，对初始化的有标记样本集的依赖性较强，合理选取初始的有标记集L能减小算法的误差；所以SSC-SOM算法是条件稳定的。

另外,需要注意的是，SSOM仅仅使用已有的有标记样本训练网络，而SSC-SOM需要实现对未标记样本进行标记。在扩充新标记样本的过程中，SSC-SOM势必增加一些时间的开销。在对未标记进行标记之前，可以采用主动学习算法缩减未标记样本的规模，只选取信息量丰富的未标记样本进行标记。这样需要标记的未标记样本的数目就大大减小，可以有效地减小时间开销。

将SSC-SOM与tri-training进行对比,其结果如表7—10所示。可以看出，SSC-SOM能较好地提高分类率，具有较好的稳定性。

表3 分类率rate(λ=5%) %

表4 分类率rate(λ=10%) %

表5 分类率rate(λ=20%) %

表6 分类率提高值统计表 %

表7 分类率rate(λ=5%) %

表8 分类率rate(λ=10%) %

表9 分类率rate(λ=20%) %

表10 分类率提高值统计表 %

4 结束语

本文将SOM神经网络引入半监督分类领域，基于“先聚类后标记”的思想，结合无监督SOM神经网络的聚类特征和有监督SSOM神经网络的分类性能，提出一种基于SOM神经网络的半监督分类算法(SSC-SOM)，充分利用未标记样本和有标记样本的信息训练分类器，实现对未标记样本的标记和分类。实验结果表明，该算法操作简单，能较容易实现对未标记样本的分类，性能良好。

[1]周志华. 基于分歧的半监督学习[J]. 自动化学报, 2013, 39(11):1871-1878.

[2]ZHU X J. Semi-supervised Learning Literature Survey[R]. Madison： University of Wisconsin, 2008.

[3]李昆仑,曹铮,曹丽苹，等.半监督聚类的若干新进展[J].模式识别与人工智能,2009,22(5):735-742.

[4]孙雁飞,张顺颐,亓晋，等.一种基于半监督学习的GA-SOM聚类方法：中国，201010576193[P]. 2011-04-20.

[5]Shen Furao, Yu Hui, Sakurai Keisuke, et al. An Incremental Online Semi-supervised Active Learning Algorithm Based on Self-organizing Incremental Neural Network[J]. Neural Computing & Applications,2011, 20(7):1061-1074.

[6]Astudillo Cesar A, John Oommen B. On Achieving Semi-supervised Pattern Recognition by Utilizing Tree-based SOMs[J].Pattern Recognition, 2013,46：293-304.

[7]阳时来, 杨雅辉, 沈晴霓, 等. 一种基于半监督 GHSOM 的入侵检测方法[J]. 计算机研究与发展, 2013, 50(11):2375-2382.

[8]HAGAN M T, DEMUTH H B, BEALE M H. Neural Network Design[M]. Beijing： China Machine Press,2002:64-85.

[9]赵建华,李伟华.有监督SOM神经网络在入侵检测中的应用[J]. 计算机工程,2012, 38(12) ：110-111.

[10]唐明珠,阳春华,桂卫华. 基于改进的QBC和CS-SVM的故障检测[J].控制与决策.2012， 27 (10):1489-1493.

[11]文志强，胡永祥,朱文球.流行上的K最近邻分类方法[J].计算机应用,2012,32(12):3311-3314.

[12]赵建华.一种安全的基于分歧的半监督分类算法[J].西华大学学报：自然科学版,2014,33(5):1-6.

[13]ZHOU Z H, LI M. Tri-Training： Exploiting Unlabeled Data using Three Classifiers[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(11):1529-1542.

(编校：饶莉)

Semi-supervisedClassificationAlgorithmBasedonSOMNeuralNetwork

ZHAO Jian-hua1,2

(1.CollegeofComputer,NorthwesternPolytechnicalUniversity,Xi’an710072China;2.SchoolofMathematicsandComputerApplication,ShangluoUniversity,Shangluo726000China)

In order to improve the performance of semi-supervised classifier, a kind of semi-supervised classification algorithm SSC-SOM is proposed. Based on the clustering characteristics of SOM and the Cluster-then-Label idea, labeled data and unlabeled data are all used to train SOM. The labeled samples are assigned to each cluster and the clusters form simultaneously. The clustering centers are work out.K-NN algorithm is adopted to label the unlabeled samples according to the clustering centers and the information from the unlabeled samples is mined. With UCI dataset, experiments were carried out and the results show that the classification rate of SSC-SOM increases by 2.22 % than SSOM and the SSC-SOM method had good convergence.

semi-supervised learning; SOM; classification; clustering

2014-03-15

陕西省教育厅科研计划项目资助(12JK0748)；商洛学院科研项目资助(14SY006,14SKY007)。

赵建华(1982—)，男，讲师，博士研究生，主要研究方向为机器学习。

TP181

：A

：1673-159X(2015)01-0036-05

10.3969/j.issn.1673-159X.2015.01.006