扩展罗宾逊空间：非对称差异空间的复杂性及其算法解决方法

《Discrete Applied Mathematics》：Extending Robinson spaces: Complexity and algorithmic solutions for non-symmetric dissimilarity spaces

　　弗朗索瓦·布鲁克|帕斯卡·普雷阿|克里斯托弗·斯特雷斯·卡罗
卡罗利斯（CaroLIS），艾克斯-马赛大学，法国国家科学研究中心（CNRS），土伦大学，马赛，法国

**摘要**
在这项研究中，我们将罗宾逊空间的概念扩展到了不对称差异的情况下，提高了其在表示和分析复杂数据方面的适用性。在这个广义框架内，我们提出了两个问题，它们扩展了经典的排序问题：一个优化问题和一个决策问题。我们确定这两个问题分别是NP难（NP-hard）和NP完全的（NP-complete）。尽管存在这些复杂性结果，我们还是发现了一些非平凡的情况，在这些情况下这些问题可以在多项式时间内得到解决，从而为它们的可解性提供了宝贵的洞见。

**引言**
相似性和差异性度量是各种数据分析和挖掘方法的基础。传统上，这些度量被认为是对称的，这种性质简化了它们的应用，但也限制了它们的范围。最近的研究越来越强调适应非对称度量的重要性，因为它们能够更准确地模拟现实世界中关系本质上是方向性的情况[1]、[12]、[14]。
传统的数据分析算法已经被调整以处理非对称数据。例如，[16]的作者介绍了一种非对称k-means算法。在[21]中，这种算法被用于提高细胞拉曼成像的聚类性能。此外，在[17]中，作者研究了在机器学习任务中是否应将非对称差异性视为噪声或有意义的信息。他们证明了有向差异性揭示了传统方法在对距离进行对称化时往往忽略的显著结构差异。进一步地，在[22]中，作者利用非对称性来捕捉随机变量之间的依赖性。博韦和冈田在[4]中提供了一个关于适应非对称接近性的多维缩放和聚类分析的模型和方法的全面调查，特别关注数据可视化。
罗宾逊空间是一类特殊的差异性空间，其特点是元素的线性排序，在这种排序中，当远离给定点时差异性不会减小。这种线性排序是罗宾逊空间的定义特征。在对称差异性的情况下，这种排序在两个方向上都是一致的。
在这项工作中，我们旨在将罗宾逊空间的概念扩展到非对称差异性度量上，从而拓宽该框架在分析复杂数据集方面的适用性。我们提出了两个自然的扩展方案，这些方案保留了线性排序的思想。
在单向罗宾逊定义中，我们要求存在一个排序，确保差异性仅在一个方向上不会减小。在双向罗宾逊定义中，我们要求存在一个线性排序，即使在差异性本身不对称的情况下，也能满足罗宾逊条件。

设X是一个包含n个元素的集合。X上的差异性（通常）是一个从X×X到非负实数的对称函数d，使得当x=y时d(x,y)=0。d(x,y)的值表示x和y之间的差异性，而(X,d)是一个差异性空间。如果对于X中的任意三个元素x,y,z，都有x< />< />< /><是兼容的，那么其逆序也是兼容的。如果一个差异性空间允许一个兼容的排序，那么它就是罗宾逊空间。需要注意的是，罗宾逊空间不一定是度量空间。然而，给定一个差异性d，通过d′(x,y)=d(x,y)+k（其中k大于d的所有取值）定义的差异性d′是一个距离，且当且仅当d是罗宾逊空间时，d′也是罗宾逊空间。 罗宾逊差异性最初是为了按时间顺序排列考古沉积物而被发明的[20]，现在已成为排序问题的标准工具（参见[18]中的应用示例）。此外，它们等同于金字塔，这是一个经典的分类模型[10]、[11]，并且在识别tsp问题的可解情况方面也很有帮助[8]。在本文中，我们旨在通过考虑非对称差异性来扩展罗宾逊空间的概念。>< />< />< />< />< />< />< />< />< />< /><排序时，所有段s(x,y)都是区间。

** assignment和orientation问题的np难度**
本节介绍了两个证明分配问题和定向问题np完全性的归约。这些归约提供了关于问题计算界限的关键见解，并为某些情况下的有效算法方法打开了大门。

**作为决策问题，我们可以以下方式解决分配和定向问题：**
** assignment问题：** 给定一个差异性空间(x,d)和一个有向树t?=(v,e?)（其中|x|=|v|），是否存在一个双射，使得t?中的每条有向路径都是单向罗宾逊的？

**当所有路径都是罗宾逊时的最优定向**
在本节中，我们关注这样的情况：对于给定的差异性空间(x,d)和一棵树t=(x,e)，t中的每条路径都是罗宾逊的。当(x,d)是一个t-罗宾逊空间并且t代表其对应的树之一时，满足这一条件。在这种特殊情况下，我们提出了一种o(n2)时间的算法来高效解决定向问题。 ** assignment和orientation问题的np难度** 本节介绍了两个证明分配问题和定向问题np完全性的归约。这些归约提供了关于问题计算界限的关键见解，并为某些情况下的有效算法方法打开了大门。 **作为决策问题，我们可以以下方式解决分配和定向问题：** ** assignment问题：** 给定一个差异性空间(x,d)和一个有向树t?=(V,E?)（其中|X|=|V|），是否存在一个双射，使得T?中的每条有向路径都是单向罗宾逊的？ **当所有路径都是罗宾逊时的最优定向** 在本节中，我们关注这样的情况：对于给定的差异性空间(x,d)和一棵树t=>
** assignment和orientation问题的np难度**
本节介绍了两个证明分配问题和定向问题np完全性的归约。这些归约提供了关于问题计算界限的关键见解，并为某些情况下的有效算法方法打开了大门。

**作为决策问题，我们可以以下方式解决分配和定向问题：**
** assignment问题：** 给定一个差异性空间(x,d)和一个有向树t?=(v,e?)（其中|x|=|v|），是否存在一个双射，使得t?中的每条有向路径都是单向罗宾逊的？

**当所有路径都是罗宾逊时的最优定向**
在本节中，我们关注这样的情况：对于给定的差异性空间(x,d)和一棵树t=(x,e)，t中的每条路径都是罗宾逊的。当(x,d)是一个t-罗宾逊空间并且t代表其对应的树之一时，满足这一条件。在这种特殊情况下，我们提出了一种o(n2)时间的算法来高效解决定向问题。>在这种情况下，最优的定向是指对于对称但不相同的差异，T，Tractable实例的一种定向。在本节中，我们研究了两种情况：d 是集合 X 上的对称但不相同的差异。在 5.1 节中，当我们有 T=(X,E) 表示一个星形结构时，我们给出了一种最优的 O(n^2) 时间算法来解决定向问题，该算法可以转化为一个高效的 O(n^3) 时间算法来解决分配问题。在 5.2 节中，当 T 表示一条路径时，我们为定向问题提供了一种高效的 O(n^3) 时间算法。

结论

在这项工作中，我们将 Robinson 空间的概念扩展到了包括非对称差异的情况，大大拓宽了其适用范围。在这个扩展的框架内，我们引入了两个新问题：分配问题（Assignment problem）和定向问题（Orientation problem），这两个问题都是对经典排序问题（seriation problem）的泛化。我们证明了分配问题是 NP 完全的（NP-complete），而定向问题是 NP 困难（NP-hard），这突显了这些问题在计算上的挑战。

致谢

本工作的部分内容是在 C. Thraves Caro 在地中海中央理工学院（école Centrale Méditerranée）休假期间完成的。我们还要感谢审稿人对手稿的仔细审阅以及他们提出的许多有助于提高论文可读性的建议。