最近邻分类中的距离度量学习算法实现与验证(3)
时间:2017-05-07 19:57 来源:毕业论文 作者:毕业论文 点击:次
聚类算法获得更好的结果。 1．3kNN的缺陷及改进 kNN算法的一个很大的优势在于它的判定边缘是非线性的，并且只有一个整型参 数（通过交叉验证很容易得到），分类的质量也随着训练集中样本数的增加而自动地提高。 然而，kNN却有两个严重的缺陷：一个是计算量过于庞大，由于为每一个样本分 类时，都需要搜索整个训练集，并且计算和存储与训练集中每个样本的距离，导致过 多的计算和存储开销。另一个是模型问题：如何定义kNN算法所使用距离度量标准。 理想情况下，kNN分类中的距离度量应该适用于任何问题，但显然，欧式距离无法做 到这一点。事实上，正如许多研究人员的研究成果[6,10,11] 所示,使用通过训练集学习得到的距离度量方法可以显著地提高kNN算法的性能。甚至即使是一个简单输入空间的 线性变换都可以改善kNN算法。 针对以上问题，NCA算法利用了概率性的近邻样本选择规则，通过在训练集上最 优化留一分类错误率，学习了一种二次的距离度量标准，在保存大部分信息的前提下 降低输入样本的文数，有效的减少了存储空间的开销，在低文的输入空间，也可以通 过使用特殊的数据结构（例如KD-trees，ball-trees）降低搜索的时间开销。当然， 低文的输入数据也大大减小了样本间的距离计算量。 LMNN算法是以马氏距离度量为基础的，并通过优化这种度量标准使得近邻样本尽 量属于同一个类别，而不同类别样本间的距离尽可能的大。以往的研究中，距离度量 学习算法的主要目标是尽量减少同类别样本间的距离，这样的目标是很难实现的，它 并不会促使kNN算法的性能产生改变，因为kNN的准确性并不要求所有同类别样本都 是紧密集群的。LMNN算法与支持向量机[12] 有相似之处，但不同的是LMNN算法不需要 更改和扩展就能完成多类（相对于二类）分类问题。在NCA和基于能量模型的算法研 究上的突破很大程度启发了LMNN算法，虽然基于同一目标，但在方法上却有着很大 的不同，LMNN算法利用半定规划解决优化问题，凸优化的全局最小值可以有效的计算 得到。2弱监督距离度量学习算法 2．1学习距离度量标准假设有一些点集 ，并且给定特定的点对之间是“相似的”： S：（）∊S如果和是“相似的”（1） 弱监督学习算法试图学习一种距离度量标准d(x,y),使得“相似”点更加靠近彼此。 我们可以考虑从以下形式学习一种距离度量标准：.（2） 为了保证满足非负性和三角不等式，要求A是半正定的，A⪰0。令A=I，得到的就是 欧式距离度量标准；如果将A对角化，那么A对角线上的数字就是输入样本每个分量 对应的“权重”；更多情况下，A将作为Rn空间上的马氏距离度量的参数，这也就等同于利用A1/2 x代替x，然后利用欧式距离进行计算。 获得A的一个简单的方法是使得点对（xi，xj）∊S距离平方和尽可能小：A⪰0.（5） 对于（4）式中大于号右边常数1的选择并不是很重要，若用其他常数c代替1，所产 生的结果将会是c2 A。这个问题在参数矩阵A中的目标函数是线性的，并且（4）和（5） 很容易被证明是两个凸约束，因此，这是一个凸优化问题，可以得到有效的解决。同 时也必须注意到，尽管式（4）是一个简单的线性约束，但它有可能导致矩阵A1/2成为 行矩阵（这样就会将所有的样本投影到一条直线上），所以我们试图用其他的约束代替式（4）。 (责任编辑：qin) |