algorithm - 如何检测数字模式中的热连胜？

Question

这更像是一个算法问题，假设您有一个类似 4 6 2 4 9 5 23 54 33 的模式，最后三个数字是连胜。我想知道如何以编程方式(或数学方式)检测到这一点。

目前我正在考虑使用比方说过去 3 个值的尾随平均值来扫描数据。如果新值 (23) 突然比该平均值高很多，我们就会标记可能出现连续上垒的开始。后面的数字不应与它相差太多，以认为热连胜仍在继续。

这听起来像是一种有效的方法吗？是否已经存在解决此类问题的算法？

Answer 1

好的。我已经试过了，但在我开始之前我必须说这不是基于任何算法(至少:我没有故意将它基于现有算法)并且它有一些缺陷(它没有说明对于负数/零)并且可能有许多边缘情况需要解决。

为了找到两个数字之间的距离以确定它们是否相似，我找到了 this simple formula :

Percent difference = (L - S) / S

其中 L 代表“最大”，S 代表“最小”。

首先，输出 5 个 50 个值在 1 到 40 之间的随机序列:

7 14 34 13 4 1 3 34 10 29 25 32 28 39 14 32 37 30 21 27 28 27 26 25 27 34 15 36 3 29 32 35 8 32 20 5 30 4 17 16 27 35 7 34 7 37 14 31 38 23 
Possible hot streak (treshold 0,95): 27 - 28 - 27
Possible hot streak (treshold 0,95): 28 - 27 - 26
Possible hot streak (treshold 0,95): 27 - 26 - 25

9 16 17 3 11 19 28 10 25 10 25 6 31 21 37 29 24 35 20 9 2 34 14 6 1 33 21 31 19 30 20 23 38 19 21 16 19 6 21 1 17 20 18 7 30 22 4 26 37 17 
Possible hot streak (treshold 0,8): 17 - 20 - 18

14 18 12 30 22 15 3 12 3 18 38 36 31 35 30 3 8 13 39 21 11 19 14 19 31 22 16 7 15 19 29 34 33 2 16 3 12 8 37 6 14 7 4 4 2 21 29 22 17 27 
Possible hot streak (treshold 0,8): 38 - 36 - 31
Possible hot streak (treshold 0,8): 36 - 31 - 35
Possible hot streak (treshold 0,8): 31 - 35 - 30
Possible hot streak (treshold 0,8): 29 - 34 - 33

14 31 26 16 6 35 5 32 38 39 38 35 36 24 29 4 3 29 20 28 31 39 15 34 8 4 15 11 18 11 32 34 30 28 5 38 9 17 35 21 37 19 9 37 8 18 11 20 14 37 
Possible hot streak (treshold 0,95): 38 - 39 - 38

18 39 3 29 36 14 17 32 9 3 20 33 15 28 8 5 6 9 19 30 35 25 34 38 30 13 30 17 27 29 33 35 36 20 33 33 31 2 31 30 21 16 9 33 2 5 4 21 30 3 
Possible hot streak (treshold 0,9): 33 - 35 - 36
Possible hot streak (treshold 0,9): 33 - 33 - 31

我采用的想法非常简单:给定一个项目列表，对其进行迭代，从当前索引开始对前 3 个进行分组，然后查看它们是否在可接受的阈值范围内。如果是，请继续，直到找到当前阈值内的所有组合。如果没有与设置阈值的组合，则从阈值中减去 0.05(又名:更宽松)并重新开始。

需要注意的是，该算法基本上是在序列中搜索一组归一化的值。您可以通过 - 在运行算法后 - 计算被视为热连胜的 3 个值的总和来改进这一点，并在该阈值中取最大的值总和。这应该会给你最高的连胜纪录。

所以这个算法所做的是寻找条纹，您所要做的就是找到热条纹(这是微不足道的)。

还有一些方面可以改进，只采用周围值较低的序列，但这将取决于您希望算法走多远。

这种方法的一个好处是它已经部分做到了这一点(您会注意到序列通常位于整个数据集的较高部分)，因为用于确定两个数字之间差异的公式。

值 3 和 2 将返回 0.5 的百分比差异，而值 30 和 29 将返回 0.03，因此算法会更快地选择后者。在这方面，您已经自动收集了热条纹，但它没有考虑周围的值以更加精确。

代码:

void Main()
{
    for(int i = 0; i < 5; i++){
        var list = GetList();
        DisplayList(list);
        GetHotStreaks(list);
    }
}

private static Random rand = new Random();

private List<int> GetList(){
    var list = new List<int>();

    for(int i = 0; i < 50; i++){
        list.Add(rand.Next(1, 40));
    }
    return list;
}

private void DisplayList(List<int> list){
    for(int i = 0; i < list.Count; i++){
        Console.Write(list[i] + " ");
    }
    Console.WriteLine();
}

private void GetHotStreaks(List<int> list){
    double treshold = 0.95;
    bool found = false;

    while(treshold > 0.0){
        for(int i = 0; i < list.Count - 2; i++){
            if(AreWithinRange(list[i], list[i + 1], list[i + 2], treshold)){
                Console.WriteLine (string.Format("Possible hot streak (treshold {0}): {1} - {2} - {3}", treshold, list[i], list[i + 1], list[i + 2]));
                found = true;
            }
        }

        if(found){
            Console.WriteLine ();
            return;
        }

        treshold -= 0.05;
    }   
}

private bool AreWithinRange(int val1, int val2, int val3, double treshold){
    return AreWithinRange(val1, val2, treshold) && AreWithinRange(val2, val3, treshold);
}

// http://www.oracle.com/webfolder/technetwork/data-quality/edqhelp/Content/processor_library/matching/comparisons/percent_difference.htm
private bool AreWithinRange(int val1, int val2, double treshold){
    double max = Math.Max(val1, val2);
    double min = Math.Min(val1, val2);
    double pd = (max - min) / min;

    //Console.WriteLine ("Values: val1: {0}\t val2: {1}\t PD: {2}\t T: {3}", val1, val2, pd, treshold);
    return pd <= 1 - treshold;
}