c# - 将数字列表分组为类似数字的固定集合(首选循环移位)

Question

这可能更像是一道数学题，但它最终会变成代码，所以这里...

我有一组任意数字，需要根据用户输入的最接近的相似性将其分组为固定数量的组。集合的长度和数字的值都可以变化。

这是一个示例集...

1.2
1.3
0.5
0.7
1.3
1.4
0.7
0.9
1.1
1.3

必须保留这些项目的顺序 - 最终集合不能重新排序，但可以移动。例如，最后的数字可以成为第一个数字。 这个集合被应用于一个圆，所以任何保持圆的完整性的东西都是好的。

因此，如果用户输入 4 作为所需的组数，我希望输出如下:

0 =>
    1.2
    1.3
1 =>
    0.5
    0.7
2 =>
    1.3
    1.4
    0.7
3 =>
    0.9
    1.1
    1.3

在更好的情况下，可以改变数字以提高它们在组中的相似度。例如，将最后两个数字移到开头...

0 =>
    1.1
    1.3
    1.2
    1.3
1 =>
    0.5
    0.7
2 =>
    1.3
    1.4
3 =>
    0.7
    0.9

是否有对此有用的算法？关于如何完成这样的事情有什么建议吗？

谢谢!

Answer 1

您要完成的是 Single-Linkage clustering 的特例，其中您的域是线性和圆形的。您将拥有一个距离数组，而不是距离矩阵。据推测，您的距离函数是数组中数字之差的绝对值。

这段代码绝不是最简洁、写得最好的 C#；但它确实突出了聚类算法的所有重要步骤:

简单的距离计算

class Node
{
    public double Value { get; set; }
    public Node NextNode { get; set; }
    public Cluster Cluster { get; set; }
}

class Cluster : List<Node>
{

}

static void Main()
{
    double[] values = new double[]
    {
        1.2,
        1.3,
        0.5,
        0.7,
        1.3,
        1.4,
        0.7,
        0.9,
        1.1,
        1.3,
    };

    List<Node> nodes = new List<Node>();

    foreach (double value in values)
    {
        nodes.Add(new Node { Value = value });
    }

    // Put each node in a cluster by itself
    foreach (Node node in nodes)
    {
        node.Cluster = new Cluster();
        node.Cluster.Add(node);
    }

    // Create the cirular Linked List here
    // could probably use System.Collections in some way
    // but using simple self written classes for clarity
    for (int n = 1; n < nodes.Count; n++)
    {
        nodes[n - 1].NextNode = nodes[n];
    }
    nodes[nodes.Count - 1].NextNode = nodes[0];

    // Create a sorted distance list
    List<Node> sortedNodes = new List<Node>(nodes);
    sortedNodes.Sort((a, b) =>
        {
            var aDistToNext = Math.Abs(a.Value - a.NextNode.Value);
            var bDistToNext = Math.Abs(b.Value - b.NextNode.Value);

            return aDistToNext.CompareTo(bDistToNext);
        });

    // Register each node / cluster to the output list
    List<Cluster> clusters = new List<Cluster>();
    foreach (Node node in nodes)
    {
        clusters.Add(node.Cluster);
    }


    // Merge clusters until the desired number is reached
    int distIdx = 0;

    while (clusters.Count > 4)
    {
        // Obtain the two next closest nodes
        var nodeA = sortedNodes[distIdx];
        var nodeB = nodeA.NextNode;

        // Merge the nodes into a single cluster
        nodeA.Cluster.AddRange(nodeB.Cluster);

        // Remove the unnecessary cluster from output set
        clusters.Remove(nodeB.Cluster);
        nodeB.Cluster = nodeA.Cluster;

        distIdx++;
    }

    // Print the output results
    for (int n = 0; n < clusters.Count; n++)
    {
        Console.WriteLine("{0} =>", n);

        foreach (Node node in clusters[n])
        {
            Console.WriteLine("\t{0}", node.Value);
        }
    }
}

请注意，该算法按预期工作；但是，它给出的结果与原始问题中发布的结果不同。差异是由于节点间距离相等时的模糊链接。

输出:

0 =>
        0.5
        0.7
1 =>
        1.3
        1.4
2 =>
        0.7
3 =>
        0.9
        1.1
        1.3
        1.2
        1.3

高级距离计算

如果您想在连接到先前集群中已经加入的节点之前优先考虑相似距离加入的节点，您可以修改排序算法以优先考虑未连接的节点:

sortedNodes.Sort((a, b) =>
    {
        var aDistToNext = Math.Abs(a.Value - a.NextNode.Value);
        var bDistToNext = Math.Abs(b.Value - b.NextNode.Value);

        var result = aDistToNext.CompareTo(bDistToNext);

        if (result != 0)
            return result;
        else
        {
            var aNextDistToNext = Math.Abs(a.NextNode.Value - a.NextNode.NextNode.Value);
            var bNextDistToNext = Math.Abs(b.NextNode.Value - b.NextNode.NextNode.Value);

            return bNextDistToNext.CompareTo(aNextDistToNext);
        }
    });

这给出了预期的结果:

0 =>
        0.5
        0.7
1 =>
        1.3
        1.4
2 =>
        0.7
        0.9
3 =>
        1.1
        1.3
        1.2
        1.3