Mp-dissimilarity–A data dependent dissimilarity measure
研究的问题
本文通过研究如何利用数据分布来衡量两个实例之间的不相似性，进而提出一种新的数据相关差异度量，称为“mp-dissimilarity”，这为高维空间的分类和信息检索任务提供了更好的性能。
研究动机
最近邻搜索是许多数据挖掘算法的核心过程，但在高维空间中可靠地实现仍然是一项具有挑战性的任务。这是因为传统基于几何模型的相异性度量的有效性会随着维数的增加而减小，无法到达高精度和高可靠性。因此本文提出一种新颖的相关差异度量来解决高维空间下的这一问题。
先进性与贡献
不依赖于传统的几何距离，而是利用数据分布来衡量实例之间的不相似性，这巧妙地避开了高纬度的难题。通常大范围的数据分布和距离测量中所有点对几乎等距，此时这种度量将发挥绝对优势。这也符合心理学上“两个实例之间的判断相异性会受到测量环境和其他实例的影响”这一观点。例如在非洲（白人很少和黑人很多）比在美国（有很多白人）的情况下，两个白人被认为更相似。
具体方法
- 首先对样本数据集做尺寸一致化处理，得到d x m的训练数据集X（d为数据集维度，亦即实例的属性数；m为实例数）和与m个实例一一对应的标记集Y（1 x m）
- 依次遍历X的每一个维度，在每次遍历中，需要做：
- 计算第i维度数据的标准差σi，得到邻域参数ςi = σi / 2
- 循环计算Xi上任意不同的两点度量：根据邻域Ri（Xij，Xik）=[min(Xij，Xik)-ςi, max(Xij，Xik)+ςi]，得到该邻域内实例点的数量n = | Ri（Xij，Xik）|，从而得到任意两点间度量mpi（Xij，Xik）=n / m
- 对任意不同点的度量求所有维度上的Lp范数，即mp（Xj，Xk）=（∑（mpi（Xij，Xik））^p）^(1/p )
- 此时得到了m个样本点的mp度量矩阵mp（m x m），度量越小，两个实例点越相似
- 应用mp度量矩阵我们可以采用KNN算法进行分类和预测等进一步研究
优缺点及思考：
可以在信息检索方面应用该度量，通常会进行多轮相关性反馈，每轮提供一组反馈实例（包含正反馈和负反馈）以优化性能，相比于传统的Lp范数，mp度量将会有更好的性能和准确度。
本文提出一种新的距离度量，它根据数据分布而不是传统的几何距离来进行度量样本距离，进一步优化分类预测问题模型。这在高纬空间往往发挥巨大优势，但是在计算上需要巨大的时间成本，因为需要一维一维地计算每个维度上任意不同两点之间的mp度量。
这种新的距离度量可在很多研究中应用，其进一步的研究应该放在如何用一种时间复杂度更小的算法求解距离度量。
2018.9.24
