一种基于最小最大邻域阶构图的半监督分类法

为克服K近邻图边的对称问题及互K近邻图的连通性的不足，并且针对局部全局一致性学习(LLGC)算法的分类精度在很大程度上取决于控制参数α的设置，设置不合理可能造成分类的准确率较低，聚类的结果不准确的情况，研究提出一种半监督学习分类算法，将最小最大邻域阶构图法(KMM)结合少参数的简洁局部全局一致性学习(BB-LLGC)，即KMM-BB-LLGC算法，兼顾边的对称及整个图的连通，简化图上的目标函数，使其不受参数α的影响。用UCI数据库中的数据集进行实验，与KNN-LLGC、KNN-BB-LLGC、KMM-LLGC几种分类方法进行对比，实验表明，提出的方法能可以带来更高的分类准确率，达到较高的分类精度，算法效率更高，可以实现对样本精确、快速的分类。

机器学习的核心是学习数据，从数据中获取未知规律，利用规律对未知样本进行预测和分析[1]。半监督学习突破了传统方法只考虑一种样本类型的局限，综合利用有标签与无标签样本[2] [3] [4]，对于样本空间描述的更详细并且分类性能良好。以图表为基础的半监督分类，直接用标示、识别的方法，通过邻域图的结构将标签信息传递到无标签的数据上，具有很好的直观性和解释性[5]。常用的K 近邻图在连接关系中存在不对称性的问题，互K 近邻图对边的连接严格要求对称，难以保证图的连通。针对以上不足，研究使用KMM 构图方法，连边时考虑到相对的对称性，目的是既得到容易连通的图，又能保证连接关系的可靠性[6]。

简洁局部全局一致性学习算法(BB-LLGC)是在LLGC 算法的基础上提出的一种半监督学习算法，具有精确度高、计算速度快等优点[7]。本文将二者结合，提出KMM-BB-LLGC 算法，算法在构图上可以达到更高的相对几何对称性又保证边紧密连接，并且控制参数少、使用简单，收敛速度快。用UCI 数据库中的数据集进行实验，验证算法的有效性。

2. 算法相关描述 通常基于图模型的半监督学习算法大致包括三个步骤，首先选择某种构图方式构造图，接下来定义目标函数，然后进行目标函数最小化，得到最佳分类效果。

2.1. 构图 常用的K 近邻构图本质上是一种有向图，通常的做法是简单的忽略掉边的方向，图中每个样本点强制性的与它最近的K 个邻居连接，如xi 是xj 的K 近邻，则两点之间就存在一条边，而不考虑xj 是否是xi的K 近邻，从而可能导致连接关系的不对称。K 近邻图不能反映样本之间边的对称性，造成分类的准确率较低，聚类的结果不准确。

互K 近邻图是要求必须把每条边都以对称性的方式连接起来，即xi，xj 必须互为对方的K 近邻才会存在边的连接，这是方式往往难以保证连通性[8]。针对两种构图方法的不足，需要一个既能得到容易连通的图，又能保证连接关系的可靠性的构图方法来解决。