【半监督分类】基于K-means和Label+Propagation的半监督网页分类

1.软件版本

matlab2013b

2.本算法理论知识

首先“K均值算法”和“基于局部和全局一致性算法”的整合，并不是两个算法的简单拼凑，这里，实际上结合了“K均值算法”和“基于局部和全局一致性算法”两者算法的思想。根据你提供的算法思想，算法的基本步骤是：

-----------------------------------------------------------------------------------------------------

输入：数据集（其中训练样本和测试样本分别占一定的比例）和图像其中有少量样本已被标记类别，而且每一类至少标记一个训练样本。

-----------------------------------------------------------------------------------------------------

Step1：计算少量有标记样本的均值，得到c（类别数目）个初始聚类中心点；

Step2：使用欧式距离计算未标记数据到c个初始中心点的距离，将未标记样本分配到距离中心点最近的那类中，划分出c个簇；

Step3：使用测地距离的相似性度量方法，选择各个簇中相似度大于等于0.9的个（各个簇中的数目不一样）样本，求它们的均值，作为c个新中心点以及得到c个平均半径；

Step4：循环（2）（3），直到c个中心点固定；

Step5：对个样本以及距离各个中心点半径内的样本进行标记；

Step6：用基于局部和全局一致性算法对剩下的未标记的样本进行标记，其中已标记数据只使用c个中心点；（已有现成的程序）

Step7：在全部样本标记完后，再计算出各个类的c个中心点。

Step8：对于新的测试数据，通过计算测试数据与各个中心点的相似度，选择可信度最高的进行标记。

-----------------------------------------------------------------------------------------------------

输出：分别将数据集分成已标记和未标记以及测试数据集三部分，其中测试数据集占30%的比例，已标记和未标记的共占70%。用10折交叉验证法进行测试，输出F1-measure各个指标的结果，输出分类后的图像及指标结果。以已标记数据作为训练集，保证每个类别有一个已标记的训练集，然后按照不同的比例扩展训练集，一个数据集的precision和recall测试结果都是未标记数据和测试数据结果的均值。对数据集按已标记数据占得不同比例进行测试。

3.程序设计简介

这里，根据每个步骤，编写相应的代码，并输出最后的结果：

Step1：计算少量有标记样本的均值，得到c（类别数目）个初始聚类中心点；

代码中的这个步骤就是step1的主要内容

Step2：使用欧式距离计算未标记数据到c个初始中心点的距离，将未标记样本分配到距离中心点最近的那类中，划分出c个簇；

通过这个步骤，可以将数据做个初步的分类。

Step3：使用测地距离的相似性度量方法，选择各个簇中相似度大于等于0.9的（）个（各个簇中的数目不一样）样本，求它们的均值，作为c个新中心点以及得到c个平均半径；

Step4：循环（2）（3），直到c个中心点固定；

由于论文中式余弦相似度，所以这里两个方法都做了。

Step5：对（）个样本以及距离各个中心点半径内的样本进行标记；

关于这个步骤，半径在代码中计算，但是为了方便后面的过程，将分类好的数据标上簇的编号，而没有分类的则编号为0；

Step6：用基于局部和全局一致性算法对剩下的未标记的样本进行标记，其中已标记数据只使用c个中心点；

Step7：在全部样本标记完后，再计算出各个类的c个中心点。

Step8：对于新的测试数据，通过计算测试数据与各个中心点的相似度，选择可信度最高的进行标记。

运行结果如下所示：

测试集的分类结果及分类正确率。

首先将图片输入图片，进行特征的提取，然后对特征进行分类，最后将需要测试的图片进行分类，并计算分类精度。

其运算结果如下所示：

A09-18