根据元素之间的配对关系对列表进行排序

Question

根据元素之间的配对关系对列表进行排序

6

给定一个元素列表，比如 [1,2,3,4]，以及它们之间的配对关系，比如

[[0,  0.5, 1,  0.1]
 [0.5, 0,  1,  0.9]
 [ 1,  1,  0,  0.2]
 [0.1, 0.9, 0.2, 0]]

对于熟悉图论的人来说，这基本上是一个邻接矩阵。

最快的方法是如何排序列表，使得列表中的距离与节点之间的关联度最相关，即具有高关联度的节点对应该彼此靠近。

是否有一种方法可以做到这一点（即使使用贪心算法也可以）而不会过多涉及MDS和ordination理论？

作为额外问题：

请注意，某些节点之间的关联可以完全表示，例如对于列表[1,2,3]和节点之间的关联：

[[0, 0, 1]
 [0, 0, 1]
 [1, 1, 0]]

完美的顺序应该是[1,3,2]。但有些组织无法实现，比如这个：

[[0, 1, 1]
 [1, 0, 1]
 [1, 1, 0]]

任何顺序都是一样好/坏的。

有没有办法判断排序的质量？就是它如何很好地代表成对关系？

- j-i-l

1

如果您同意的话，可以在 [cs.se] 上获得更好的答案。请标记并请求管理员迁移。 - AakashM

那么你的度量/优化目标究竟是什么？（例如L1/L2误差）？ - sascha

最快的执行时间还是最快的实现时间？ - David Eisenstat

@sascha，你说得对，你的例子是可行的。解决我的问题的方法是启发式算法，可以有效地最小化二次损失。我只是想指出，度量标准不是事先定义好的，因为你可以使用任何度量标准（甚至是非适当的度量标准，如余弦距离）将图嵌入到向量空间中。 - j-i-l

1

我编写了一个O(c * n^2 + n * log(n))的一维平衡求解器，它具有吸引力。它有可能给出一个可接受的近似值。 - Louis Ricci

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Louis Ricci · Accepted Answer

这是一个轻度测试过的算法，它采用邻接矩阵，按出现顺序设置元素/节点，然后尝试找到平衡状态。由于这是1d，我选择了一个非常简单的吸引力公式。也许添加排斥力会改善它。

/*
 * Sort the nodes of an adjacency matrix
 * @return {Array<number>} sorted list of node indices
 */
function sort1d(mat) {
    var n = mat.length;
    // equilibrium total force threshold
    var threshold = 1 / (n * n);
    var map = new Map(); // <index, position>
    // initial positions
    for(var i = 0; i < n; i++) {
        map.set(i, i);
    }
    // find an equilibrium (local minima)
    var prevTotalForce;
    var totalForce = n * n;
    do {
        prevTotalForce = totalForce;
        totalForce = 0;      
        for(var i = 0; i < n; i++) {
            var posi = map.get(i);
            var force = 0;
            for(var j = i + 1; j < n; j++) {
                var posj = map.get(j);
                var weight = mat[i][j];
                var delta = posj - posi;
                force += weight * (delta / n);
            }
            // force = Sum[i, j=i+1..n]( W_ij * ( D_ij / n )
            map.set(i, posi + force);
            totalForce += force;
        }
        console.log(totalForce, prevTotalForce);
    } while(totalForce < prevTotalForce && totalForce >= threshold);
    var list = [];
    // Map to List<[position, index]>
    map.forEach(function(v, k) { list.push([v, k]); });
    // sort list by position
    list.sort(function(a, b) { return a[0] - b[0]; });
    // return sorted indices
    return list.map(function(vk) { return vk[1]; });
}

var mat = [
    [0,  0.5, 1,  0.1],
    [0.5, 0,  1,  0.9],
    [1,  1,  0,  0.2],
    [0.1, 0.9, 0.2, 0]
];
var mat2 = [
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0]
];
console.log(sort1d(mat)); // [2, 0, 1, 3]
console.log(sort1d(mat2)); // [0, 1, 2]