一种图转导半监督分类方法

摘要

本发明公开了一种图转导半监督分类方法，包括以下步骤：步骤一、获取视频图像信息；步骤二、选取视频图像上的已标记点；步骤三、在未标记样本点中选取预选样本点；步骤四、对预选样本点进行分类；步骤五、对未标记样本点进行分类。本发明对未标记样本点进行预选取，然后通过计算样本相似度对预选样本点进行分类，减少预选样本点之间的虚假连接，进而缩减了构图的时间，利用已标记样本点的样本类别和已标记样本点与未标记样本点的样本相似度得出未标记样本点的分类结果，解决了对已标记样本集的依赖性问题，提高分类的精度。

说明书

技术领域

本发明属于数据处理技术领域，具体涉及一种图转导半监督分类方法。

背景技术

目前，监督学习、无监督学习以及半监督学习算法为三大热门学习算法。基于现实中图像、模型等领域具有的海量数据中只有小部分标记样本的现状，充分利用标记数据以及无标记数据进行分类学习，成为更主流的研究方式，这也造就了半监督学习算法在分类算法中炙手可热的地位。半监督学习算法拥有两个分支，即归纳学习算法和转导学习算法，其中，是否生成分类器是两种算法最大的区别。具体而言，归纳学习是利用标记数据和未标记数据学习得到分类器，进而通过分类器进行数据分类的方法，而图转导学习并不需要形成分类器，直接利用整个数据集便可以进行分类。相比而言，图转导算法更为经济。在图转导算法中，聚类假设、流形假设以及局部和全局一致性假设是比较常用的假设方法，其中，聚类假设保障了图转导算法中，数据在相邻位置上相似度较高时，对应节点趋于相似的标记。

目前，国内外已有很多学者对图转导算法进行研究，并提出诸多算法。标签传播算法是图转导算法的基础，通过图的边将标记信息传播到未标记节点，由于图转导算法是基于聚类假设，所以权重大的边比权重小的边标记传播更容易一些，在权重为0的边终止标记传播。在此基础上衍生出调和高斯场、局部与全局一致性、极大极小标签传播算法、最小代价路径标签传播算法等方法。不论是调和高斯场算法还是局部与全局一致性算法都过于依赖初始标记集，若图中含有噪声，或者因为其他因素使得输入数据集不可划分类别时，通过图转导方法得到的分类结果缺乏准确性。因此为了充分利用标记样本点与未标记样本点，提高分类的精度，需要一种图转导半监督分类方法，解决了对初始标记集的依赖性问题，提高了分类准确率。

发明内容

本发明所要解决的技术问题在于针对上述现有技术中的不足，提供一种图转导半监督分类方法，对未标记样本点进行预选取，然后通过计算样本相似度对预选样本点进行分类，减少预选样本点之间的虚假连接，进而缩减了构图的时间，利用已标记样本点的样本类别和已标记样本点与未标记样本点的样本相似度得出未标记样本点的分类结果，解决了对已标记样本集的依赖性问题，提高分类的精度。

为解决上述技术问题，本发明采用的技术方案是：一种图转导半监督分类方法，其特征在于，该方法包括以下步骤：

步骤一、获取视频图像信息：视频图像传感器采集视频图像并将得到的视频图像传输给计算机，计算机将得到的视频图像存入总样本集X，总样本集X中的样本点个数为n×h，n和h均为不小于2的正整数，

步骤二、选取视频图像上的已标记点：总样本集X中的样本点按类别分为C类，计算机在所述视频图像上选取已标记样本点，已标记样本点包括所述类别中的所有类别，计算机将已标记样本点存入已标记样本集X_l，已标记样本集X_l中的样本点个数为l×h，l为不大于n的正整数，将已标记样本点的样本类别存入已标记样本类别集Y_l，将未标记样本点存入未标记样本集X_u，未标记样本集X_u中的样本点的样本类别组成未标记样本类别集Y_u，未标记样本集记X_u中的样本点个数为(n-l)×h；

步骤三、在未标记样本点中选取预选样本点：

步骤301、选取未标记样本点的中心样本点：

步骤3011、未标记样本点分类：未标记样本集X_u中的未标记样本点按所述类别分为C类，x_ji表示未标记样本集X_u中的任意一个未标记样本点，>

步骤3012、选取每类未标记样本点的中心样本点：计算机根据准则函数计算每个未标记样本点x_ji的准则函数值，A>u的隶属度矩阵，A_ij,s表示未标记样本点x_ji对中心样本点u_s的隶属度，x_ji表示未标记样本集X_u中的任意一个未标记样本点，u_s表示每一类未标记样本点中的中心样本点，U表示由中心样本点u_s组成的聚类中心集，U＝(u₁,...,u_s,...,u_C)，1≤s≤C，m表示模糊加权幂指数；

步骤3013:令得到：其中 k≠s，1≤k≤C；

步骤3014:对A_ij,s随机赋值，A_ij,s的取值满足

步骤3015:将A_ij,s的值代入公式得到u_s；将计算得到的u_s的值代入公式得到A_ij,s；

步骤3016：重复步骤3015，直到A_ij,s的前后两次计算结果的差值不大于ε，其中ε表示隶属度误差阈值，计算机将此时u_s的取值存入数据存储器；

步骤302、计算未标记样本点到中心样 本点的距离：计算机计算距离集合D，D＝[D₁,D₂,...,D_C]，D表示未标记样本集X_u中每一个未标记样本点>ji到每一个中心样本点u_s的距离集合，D_s表示距离集合D中任意一个距离子集合，

其中D_s表示每一个未标记样本点x_ji到中心样本点u_s的距离集合；

步骤303、排序选取：计算机对集合D_s中每列数据按从小到大的顺序进行排序，选择集合D_s中前r行数据对应的未标记样本点x_ji组成预选样本集>u，X'_u的大小为r×h，r<n；

步骤四、对预选样本点进行分类：

步骤401、构建训练集：将预选样本集X'_u加入已标记样本集X_l中组成训练集X'，训练集X'＝{X_l,X'_u}，计算机将训练集X'中的样本点存储在数据存储器中，X'的大小为(l+r)×h；

步骤402、计算样本相似度：计算机计算样本相似度为w_pq-ab，其中x_pq表示预选样本集X'_u中的任意样本点，x_ab表示已标记样本集X_l中的任意样本点，1≤p≤r，1≤a≤l，1≤q≤h，1≤b≤h，σ为带宽参数，σ>0；

步骤403、计算传递概率集：计算机根据公式计算样本点x_pq将标记信息传递到样本点x_ab的传递概率P_pq-ab，P表示由传递概率P_pq-ab组成的传递概率集，P的大小为(l+r)×h，将P划分为四个子矩阵，其中1≤e<h；

步骤404：预选样本集X'_u对应的样本类别集为预选样本类别集Y_u'，预选样本类别集Y_u'的大小为r×h，训练集X'对应的样本类别集为训练样本类别集>

步骤405：根据公式Y′_(g)＝P×Y′_(g-1)，推导出：Y′_u(g)＝P_reY_l(g-1)+P_rCY′_u(g-1)，其中g表示迭代次数，Y′_(g)表示第g次迭代后的训练样本类别集，>l(g)表示第g次迭代后的已标记样本类别集，Y′_u(g)表示第g次迭代后的预选样本类别集，对g和Y′_u(g-1)赋初值，令g＝1，Y′_u(g-1)＝0；

步骤406、迭代计算Y′_u(g)，直到Y′_u(g)＝Y′_u(g-1)，完成迭代计算，迭代计算完成后的Y′_u(g)即为预选样本集X'_u对应的样本类别集为Y_u'，计算机将迭代计算完成后的Y′_u(g)保存在数据存储器中；

步骤五、对未标记样本点进行分类：建立未标记样本集为X″_u，>u＝X-X_u'，未标记样本集X″_u中的样本点个数为(n-l-r)×h，未标记样本点x_do表示未标记样本集X″_u中的任意一个未标记样本点，其中，>

计算未标记样本点x_do的样本类别f^*(x_do)，其中，x_pi表示训练集X'中的任意一个训练集样本点，y_pi表示训练集样本点x_pi的样本类别，f(x_pi)表示训练集样本点x_pi在决策函数f处得到的函数预测值f(x_pi)，1≤p≤l+r，γ₁表示希尔伯特空间函数的复杂度，表示决策函数f在希尔伯特空间的范数，>2表示几何结构函数的复杂度，W_pi-do表示训练集样本点x_pi与未标记样本点x_do的样本相似度。

上述的一种图转导半监督分类方法，其特征在于：步骤三中在未标记样本点中选取预选样本点的方法还包括随机选取。

上述的一种图转导半监督分类方法，其特征在于：所述隶属度误差阈值ε＝0.01。

上述的一种图转导半监督分类方法，其特征在于：所述模糊加权幂指数 m＝2。

本发明与现有技术相比具有以下优点：

1、本发明对未标记样本点进行排序和预选取，将未标记样本点中含有对分类有用信息的样本点加入到训练集，提高了分类准确性，提高了构图的效率，同时避免了人工参与标注，节省人力和时间投入。

2、本发明通过计算样本相似度对预选样本点进行分类，以样本相似度作为样本点之间转导的依据，并通过迭代的方法对预选样本点进行样本类别分类，减少了预选样本点之间的虚假连接，进而缩减了构图的时间，提高了分类效果。

3、本发明采用半监督的算法，利用已标记样本点的样本类别和已标记样本点与未标记样本点之间的样本相似度计算出未标记样本点的样本类别，解决了由于未标记样本点对已标记样本点的依赖性导致分类精度差的问题，从而提高了未标记样本点的分类精度。

综上所述，本发明对未标记样本点进行预选取，然后通过概率转移矩阵对预选样本点进行分类，减少预选样本点之间的虚假连接，进而缩减了构图的时间，分类器利用训练集中的已标记样本点和未标记样本集中的未标记样本点得出未标记样本点的分类结果，解决了对已标记样本集的依赖性问题，提高分类的精度。

下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。

附图说明

图1为本发明的方法流程图。

图2为本发明图转导半监督分类方法的电路原理框图。

图3为本发明图转导半监督分类方法与传统的图转导方法、GT(R)+SSL 方法和GT(C)+SSL方法的分类结果对比示意图。

附图标记说明:

1—视频图像传感器； 2—计算机； 3—数据存储器。

具体实施方式

如图1和图2所示，本发明包括以下步骤：

步骤一、获取视频图像信息：视频图像传感器1采集视频图像并将得到的视频图像传输给计算机2，计算机2将得到的视频图像存入总样本集X，总样本集X中的样本点个数为n×h，n和h均为不小于2的正整数；

需要说明的是，所述视频图像包括二维彩色图像和二维黑白图像。

步骤二、选取视频图像上的已标记点：总样本集X中的样本点按类别分为C类，计算机2在所述视频图像上选取已标记样本点，已标记样本点包括所述类别中的所有类别，计算机2将已标记样本点存入已标记样本集X_l，已标记样本集X_l中的样本点个数为l×h，l为不大于n的正整数，将已标记样本点的样本类别存入已标记样本类别集Y_l，将未标记样本点存入未标记样本集>u，未标记样本集X_u中的样本点的样本类别组成未标记样本类别集Y_u，未标记样本集记X_u中的样本点个数为(n-l)×h；

实际使用时，以二维彩色图像模型为对象，对二维彩色图像本身进行分类，二维彩色图像中，样本点按类别分为2类，包括背景和目标对象，即C＝2，背景样本点的样本类别表示为1，目标对象样本点的样本类别表示为0。在二维彩色图像上以画线方式选取已标记样本点，具体选取结果如下所示：

步骤三、在未标记样本点中选取预选样本点：

步骤301、选取未标记样本点的中心样本点：

步骤3011、未标记样本点分类：未标记样本集X_u中的未标记样本点按所述类别分为C类，x_ji表示未标记样本集X_u中的任意一个未标记样本点，1≤j≤n-l，1≤i≤h；

需要说明的是，实际使用时，未标记样本点也分为背景样本点和目标对象样本点。

步骤3012、选取每类未标记样本点的中心样本点：计算机2根据准则函数计算每个未标记样本点x_ji的准则函数值，>u的隶属度矩阵，A_ij,s表示未标记样本点x_ji对中心样本点u_s的隶属度，x_ji表示未标记样本集X_u中的任意一个未标记样本点，u_s表示每一类未标记样本点中的中心样本点，U表示由中心样本点u_s组成的聚类中心集，U＝(u₁,...,u_s,...,u_C)，1≤s≤C，m表示模糊加权幂指数；

需要说明的是，当样本点按类别分为背景和目标对象时，计算每类未标记样本点的中心样本点，即是计算背景样本点的中心样本点和目标对象样本点的中心样本点。

步骤3013:令得到：其中 k≠s，1≤k≤C；

步骤3014:对A_ij,s随机赋值，A_ij,s的取值满足

步骤3015:将A_ij,s的值代入公式得到u_s；将计算得到的u_s的值代入公式得到A_ij,s；

步骤3016：重复步骤3015，直到A_ij,s的前后两次计算结果的差值不大于ε，其中ε表示隶属度误差阈值，计算机2将此时u_s的取值存入数据存储器3；

本实施例中，对准则函数J(A,U)求导，即得到u_s和A_ij,s的表达式。然后通过对A_ij,s赋初值，计算u_s，再将计算得到的u_s作为下一次计算的初值，代入得到下一个A_ij,s的值，直到前后两次计算得到的A_ij,s的差值不大于0.01，最后一次计算结果的A_ij,s值对应的u_s即为中心样本点，从而得到背景样本点的中心样本点和目标对象样本点的中心样本点。

本实施例中，模糊加权幂指数m＝2。

步骤302、计算未标记样本点到中心样本点的距离：计算距离集合D， D＝[D₁,D₂,...,D_C]，D表示未标记样本集X_u中每一个未标记样本点x_ji到每一个中心样本点u_s的距离集合，D_s表示距离集合D中任意一个距离子集合，

其中D_s表示每一个未标记样本点x_ji到中心样本点u_s的距离集合；

本实施例中，即是计算每一个未标记样本点距离背景样本点的中心样本点的距离和距离目标对象样本点的中心样本点的距离，距离表示未标记样本点与中心样本点的相关度，距离越小，相关度越大。

步骤303、排序选取：将集合D_s中每列数据按从小到大的顺序进行排序，选择集合D_s中前r行数据对应的未标记样本点x_ji组成预选样本集X'_u，X'_u的大小为r×h，r<n；

需要说明的是，将集合D_s中每列数据按从小到大的顺序进行排序，即是将未标记样本点与中心样本点的相关度按照从大到小的顺序排列。选择集合>s中前r行数据对应的未标记样本点x_ji，即是选择了与中心样本点的相关度较大的r×h个未标记样本点。

实际使用时，将集合D_s中每列数据按从大到小的顺序进行排序，选择集合D_s中前25列数据对应的未标记样本点x_ji组成预选样本集X'_u，X'_u的大小为25×2，即将预选样本X'_u中的100个未标记样本点加入训练集X'中，完成了未标记样本点的预选取。

需要说明的是，步骤三中在未标记样本点中选取预选样本点的方法还包括随机选取。

步骤四、对预选样本点进行分类：

步骤401、构建训练集：将预选样本集X'_u加入已标记样本集X_l中组成训练集X'，训练集X'＝{X_l,X'_u}，计算机2将训练集X'中的样本点存储在数据存储器3中，X'的大小为(l+r)×h；

需要说明的是，训练集X'_u中包括已标记样本点和预选样本点，对预选样本点的分类是以已标记样本点和预选样本点之间的样本相似度为依据的。

步骤402、计算样本相似度：计算机2根据公式计算样本相似度为w_pq-ab，其中x_pq表示预选样本集X'_u中的任意样本点，xab表示已标记样本集X_l中的任意样本点，1≤p≤r，1≤a≤l，1≤q≤h，1≤b≤h，σ为带宽参数，σ>0；

步骤403、计算传递概率集：计算机2根据公式计算样本点x_pq将标记信息传递到样本点x_ab的传递概率P_pq-ab，P表示由传递概率P_pq-ab组成的传递概率集，P的大小为(l+r)×h，将P划分为四个子矩阵，其中1≤e<h；

需要说明的是，由于传递概率集P的大小为(l+r)×h，将P划分为四个子矩阵，其中P_le的大小为l×e，P_l(h-e)的大小为l×(h-e)，P_re的大小为r×e，>r(h-e)的大小为r×(h-e)。

步骤404：预选样本集X'_u对应的样本类别集为预选样本类别集Y_u'，预选样本类别集Y_u'的大小为r×h，训练集X'对应的样本类别集为训练样本类别集>

步骤405：根据公式Y′_(g)＝P×Y′_(g-1)，推导出：Y′_u(g)＝P_reY_l(g-1)+P_rCY′_u(g-1)，其中g表示迭代次数，Y′_(g)表示第g次迭代后的训练样本类别集，>l(g)表示第g次迭代后的已标记样本类别集，Y′_u(g)表示第g次迭代后的预选样本类别集，对g和Y′_u(g-1)赋初值，令g＝1，Y′_u(g-1)＝0；

需要说明的是，Y′_(g)＝P×Y′_(g-1)的展开式为：计算得到Y_l(g)＝P_leY_l(g-1)+P_l(h-e)Y′_u(g-1)，Y′_u(g)＝P_reY_l(g-1)+P_rCY′_u(g-1)，由于>l(g)为已知值，所以此处只保留计算Y′_u(g)的公式。

步骤406、迭代计算Y′_u(g)，直到Y′_u(g)＝Y′_u(g-1)，完成迭代计算，迭代计算完成后的Y′_u(g)即为预选样本集X'_u对应的样本类别集为Y_u'，计算机2将迭代计算完成后的Y′_u(g)保存在数据存储器3中；

实际使用时，利用已标记样本集X_l中样本点的样本类型预测预选样本集>u中样本点的样本类型，已标记样本集X_l中样本点的样本类型与预选样本集>u中样本点的样本类型之间按照样本相似度进行传递，利用样本相似度进行转导计算，两个样本点之间的样本相似度越大，越容易传递，因此减少了样本点之间的虚假连接，进而缩减了构图分类时间。

步骤五、对未标记样本点进行分类：建立未标记样本集为X″_u，X″_u＝X-X_u'，未标记样本集X″_u中的样本点个数为(n-l-r)×h，未标记样本点x_do表示未标记样本集X″_u中的任意一个未标记样本点，其中，>

计算未标记样本点x_do的样本类别f^*(x_do)，其中，x_pi表示训练集X'中的任意一个训练集样本点，y_pi表示训练集样本点x_pi的样本类别，f(x_pi)表示训练集样本点x_pi在决策函数f处得到的函数预测值f(x_pi)，1≤p≤l+r，γ₁表示希尔伯特空间函数的复杂度，表示决策函数f在希尔伯特空间的范数，>2表示几何结构函数的复杂度，W_pi-do表示训练集样本点x_pi与未标记样本点x_do的样本相似度。

确定希尔伯特空间函数的复杂度γ₁和几何结构函数的复杂度γ₂的取值，>1＝{-5:1:5}，lgγ₂＝{-5:1:5}。采用半监督算法对未标记样本点进行分类，即采用已标记样本点的样本类别和已标记样本点与未标记样本点的样本相似度确定未标记样本点的样本类别。充分利用已标记样本点与未标记样本点，解决了对初始标记集的依赖性问题，提高分类的精度，本发明的图转导半监督分类方法与传统的图转导方法、GT(R)+SSL方法和GT(C)+SSL方法的分类结果如图3所示，其中，方法1表示传统的图转导方法，方法2表示GT(R)+SSL>

以上所述，仅是本发明的实施例，并非对本发明作任何限制，凡是根据本发明技术实质对以上实施例所作的任何简单修改、变更以及等效结构变化，均仍属于本发明技术方案的保护范围内。