确定一组日期的事件重复模式

Question

我正在寻找一种模式、算法或库，它将采用一组日期并在其中一个退出时返回重复的描述，即集合 [11-01-2010, 11-08-2010, 11-15-2010 , 11-22-2010, 11-29-2010] 会产生类似“十一月的每个星期一”的结果。

有没有人以前见过这样的事情或者对实施它的最佳方法有任何建议？

Answer 1

语法进化 (GE) 适合此类问题，因为您正在寻找一个答案坚持某种语言。语法进化还用于程序生成、作曲、设计等。

我会这样处理这个任务：

用语法构建问题空间。

构造一个可以表示所有所需重复模式的上下文无关语法。考虑如下的生产规则：

datepattern -> datepattern 'and' datepattern
datepattern -> frequency bounds
frequency -> 'every' ordinal weekday 'of the month'
frequency -> 'every' weekday
ordinal -> ordinal 'and' ordinal
ordinal -> 'first' | 'second' | 'third'
bounds -> 'in the year' year

由这些规则生成的模式的一个示例是：“2010 年每月的第二个和第三个星期三以及 2011 年的每个星期二”

实现此类的一种方法语法将通过类层次结构进行，稍后您将通过反射对其进行操作，就像我在下面的示例中所做的那样。

将此语言映射到一组日期

您应该创建一个函数，该函数从您的语言中获取一个子句，并递归地返回它所涵盖的所有日期的集合。这使您可以将您的答案与输入进行比较。

在语法的指导下，搜索潜在的解决方案

您可以使用遗传算法或模拟退火将日期与语法相匹配，使用动态编程试试运气，或者从简单的强力枚举所有可能的方法开始条款。

如果您使用遗传算法，您的突变概念应该包括根据您的生产规则之一的应用将一个表达式替换为另一个表达式。

请查看以下 GE 相关网站以获取代码和信息：
http://www.bangor.ac.uk/~eep201/jge/
http://nohejl.name/age/
http://www.genicprogramming.us/Home_Page.html

评估每个解决方案

函数可以考虑解决方案的文本长度、多次生成的日期数量、错过的日期数量以及生成的错误日期数量。

示例代码

根据请求，并且因为这是一个非常有趣的挑战，我编写了该算法的基本实现来帮助您入门。虽然它可以工作，但它还没有完成，但设计绝对应该得到更多的思考，一旦您从这个示例中收集到基本要点，我建议您考虑使用我上面提到的库之一。

  /// <summary>
  ///  This is a very basic example implementation of a grammatical evolution algorithm for formulating a recurrence pattern in a set of dates.
  ///  It needs significant extensions and optimizations to be useful in a production setting.
  /// </summary>
  static class Program
  {

    #region "Class hierarchy that codifies the grammar"

    class DatePattern
    {

      public Frequency frequency;
      public Bounds bounds;

      public override string ToString() { return "" + frequency + " " + bounds; }

      public IEnumerable<DateTime> Dates()
      {
        return frequency == null ? new DateTime[] { } : frequency.FilterDates(bounds.GetDates());
      }

    }

    abstract class Bounds
    {
      public abstract IEnumerable<DateTime> GetDates();
    }

    class YearBounds : Bounds
    {

      /* in the year .. */
      public int year;

      public override string ToString() { return "in the year " + year; }

      public override IEnumerable<DateTime> GetDates()
      {
        var firstDayOfYear = new DateTime(year, 1, 1);
        return Enumerable.Range(0, new DateTime(year, 12, 31).DayOfYear)
          .Select(dayOfYear => firstDayOfYear.AddDays(dayOfYear));
      }
    }

    abstract class Frequency
    {
      public abstract IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates);
    }

    class WeeklyFrequency : Frequency
    {

      /* every .. */
      public DayOfWeek dayOfWeek;

      public override string ToString() { return "every " + dayOfWeek; }

      public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
      {
        return Dates.Where(date => (date.DayOfWeek == dayOfWeek));
      }

    }

    class MonthlyFrequency : Frequency
    {

      /* every .. */
      public Ordinal ordinal;
      public DayOfWeek dayOfWeek;
      /* .. of the month */

      public override string ToString() { return "every " + ordinal + " " + dayOfWeek + " of the month"; }

      public override IEnumerable<DateTime> FilterDates(IEnumerable<DateTime> Dates)
      {
        return Dates.Where(date => (date.DayOfWeek == dayOfWeek) && (int)ordinal == (date.Day - 1) / 7);
      }

    }

    enum Ordinal { First, Second, Third, Fourth, Fifth }

    #endregion

    static Random random = new Random();
    const double MUTATION_RATE = 0.3;
    static Dictionary<Type, Type[]> subtypes = new Dictionary<Type, Type[]>();

    static void Main()
    {

      // The input signifies the recurrence 'every first thursday of the month in 2010':
      var input = new DateTime[] {new DateTime(2010,12,2), new DateTime(2010,11,4),new DateTime(2010,10,7),new DateTime(2010,9,2),
                    new DateTime(2010,8,5),new DateTime(2010,7,1),new DateTime(2010,6,3),new DateTime(2010,5,6),
                    new DateTime(2010,4,1),new DateTime(2010,3,4),new DateTime(2010,2,4),new DateTime(2010,1,7) };


      for (int cTests = 0; cTests < 20; cTests++)
      {
        // Initialize with a random population
        int treesize = 0;
        var population = new DatePattern[] { (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize), (DatePattern)Generate(typeof(DatePattern), ref treesize) };
        Run(input, new List<DatePattern>(population));
      }
    }

    private static void Run(DateTime[] input, List<DatePattern> population)
    {
      var strongest = population[0];
      int strongestFitness = int.MinValue;
      int bestTry = int.MaxValue;
      for (int cGenerations = 0; cGenerations < 300 && strongestFitness < -100; cGenerations++)
      {
        // Select the best individuals to survive:
        var survivers = population
            .Select(individual => new { Fitness = Fitness(input, individual), individual })
            .OrderByDescending(pair => pair.Fitness)
            .Take(5)
            .Select(pair => pair.individual)
            .ToArray();
        population.Clear();

        // The survivers are the foundation for the next generation:
        foreach (var parent in survivers)
        {
          for (int cChildren = 0; cChildren < 3; cChildren++)
          {
            int treeSize = 1;
            DatePattern child = (DatePattern)Mutate(parent, ref treeSize); // NB: procreation may also be done through crossover.
            population.Add((DatePattern)child);

            var childFitness = Fitness(input, child);
            if (childFitness > strongestFitness)
            {
              bestTry = cGenerations;
              strongestFitness = childFitness;
              strongest = child;
            }

          }
        }
      }
      Trace.WriteLine("Found best match with fitness " + Fitness(input, strongest) + " after " + bestTry + " generations: " + strongest);

    }

    private static object Mutate(object original, ref int treeSize)
    {
      treeSize = 0;


      object replacement = Construct(original.GetType());
      foreach (var field in original.GetType().GetFields())
      {
        object newFieldValue = field.GetValue(original);
        int subtreeSize;
        if (field.FieldType.IsEnum)
        {
          subtreeSize = 1;
          if (random.NextDouble() <= MUTATION_RATE)
            newFieldValue = ConstructRandomEnumValue(field.FieldType);
        }
        else if (field.FieldType == typeof(int))
        {
          subtreeSize = 1;
          if (random.NextDouble() <= MUTATION_RATE)
            newFieldValue = (random.Next(2) == 0
            ? Math.Min(int.MaxValue - 1, (int)newFieldValue) + 1
            : Math.Max(int.MinValue + 1, (int)newFieldValue) - 1);
        }
        else
        {
          subtreeSize = 0;
          newFieldValue = Mutate(field.GetValue(original), ref subtreeSize); // mutate pre-maturely to find out subtreeSize

          if (random.NextDouble() <= MUTATION_RATE / subtreeSize) // makes high-level nodes mutate less.
          {
            subtreeSize = 0; // init so we can track the size of the subtree soon to be made.
            newFieldValue = Generate(field.FieldType, ref subtreeSize);
          }
        }
        field.SetValue(replacement, newFieldValue);
        treeSize += subtreeSize;
      }
      return replacement;

    }

    private static object ConstructRandomEnumValue(Type type)
    {
      var vals = type.GetEnumValues();
      return vals.GetValue(random.Next(vals.Length));
    }

    private static object Construct(Type type)
    {
      return type.GetConstructor(new Type[] { }).Invoke(new object[] { });
    }

    private static object Generate(Type type, ref int treesize)
    {
      if (type.IsEnum)
      {
        return ConstructRandomEnumValue(type);
      }
      else if (typeof(int) == type)
      {
        return random.Next(10) + 2005;
      }
      else
      {
        if (type.IsAbstract)
        {
          // pick one of the concrete subtypes:
          var subtypes = GetConcreteSubtypes(type);
          type = subtypes[random.Next(subtypes.Length)];
        }
        object newobj = Construct(type);

        foreach (var field in type.GetFields())
        {
          treesize++;
          field.SetValue(newobj, Generate(field.FieldType, ref treesize));
        }
        return newobj;
      }
    }


    private static int Fitness(DateTime[] input, DatePattern individual)
    {
      var output = individual.Dates().ToArray();
      var avgDateDiff = Math.Abs((output.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000)) - input.Average(d => d.Ticks / (24.0 * 60 * 60 * 10000000))));
      return
        -individual.ToString().Length // succinct patterns are preferred.
        - input.Except(output).Count() * 300 // Forgetting some of the dates is bad.
        - output.Except(input).Count() * 3000 // Spurious dates cause even more confusion to the user.
      - (int)(avgDateDiff) * 30000; // The difference in average date is the most important guide.
    }

    private static Type[] GetConcreteSubtypes(Type supertype)
    {
      if (subtypes.ContainsKey(supertype))
      {
        return subtypes[supertype];
      }
      else
      {

        var types = AppDomain.CurrentDomain.GetAssemblies().ToList()
            .SelectMany(s => s.GetTypes())
            .Where(p => supertype.IsAssignableFrom(p) && !p.IsAbstract).ToArray();
        subtypes.Add(supertype, types);
        return types;
      }
    }
  }

希望这能让你走上正轨。请务必在某处分享您的实际解决方案；我认为它在很多场景下都会非常有用。

Answer 2

如果您的目的是生成人类可读的模式描述（如“十一月的每个星期一”），那么您可能希望从枚举可能的描述开始。描述可以分为频率和界限，例如，

频率：

• 每天...
• 每隔/第三/第四天...
• 工作日/周末...
• 每周一...
• 隔周星期一...
• 第一/第二/上周一……
• 范围

：

• ……1月
• ……3月25日至10月25日
• ……

每种不会那么多，可以一一查。

Answer 3

我会做什么：

1. 创建数据样本
2. 使用聚类算法
3. 使用算法生成样本
4. 创建适应度函数来衡量它与完整数据集的关联程度。聚类算法将提出 0 或 1 个建议，您可以根据它与整个集合的适合程度来衡量它。
5. 将出现的事件与已找到的集合元素化/合并，然后重新运行该算法。

考虑到这一点，您可能想要使用模拟退火或遗传算法。此外，如果您有描述，您可能需要比较描述以生成示例。

Answer 4

您可以访问系统日期或系统日期和时间，并根据调用或函数结果返回的日期和星期几在内存中构造粗略的日历点。然后使用相关月份中的天数对其进行求和，并添加输入中日期变量的天数和/或访问从星期日或星期一开始的相关周的日历点，并计算或将索引向前增加到正确的值天。使用固定字符构造文本字符串，并根据需要插入相关变量，例如星期几的全名。可能需要多次遍历才能获得要显示或计数其出现次数的所有事件。

Answer 5

首先，找一个序列，如果存在的话：

step = {day,month,year}
period=0
for d = 1 to dates.count-1
    interval(d,step)=datedifference(s,date(d),date(d+1))
next
' Find frequency with largest interval
for s = year downto day
    found=true
    for d = 1 to dates.count-2
        if interval(d,s)=interval(d+1,s) then
            found=false
            exit for
        end if
    next
    if found then
        period=s
        frequency=interval(1,s)
        exit for
    end if
next

if period>0
    Select case period
      case day
        if frequency mod 7 = 0 then
          say "every" dayname(date(1))
        else
          say "every" frequency "days"
        end if
      case month
        say "every" frequency "months on day" daynumber(date(1))
      case years
        say "every" frequency "years on" daynumber(date(1)) monthname(date(1))
    end select
end if

最后，处理“11月”、“2007年到2010年”等，应该是显而易见的。

华泰

Answer 6

我喜欢@arjen 的回答，但我认为不需要复杂的算法。这就是这么简单。如果有模式，就有模式……因此一个简单的算法就可以了。首先，我们需要考虑我们正在寻找的模式类型：每日、每周、每月和每年。

如何识别？

每日：每天都有记录
每周：每周有一条记录
每月：每月有一条记录
每年：每年都有记录

难吗？不会。只需数一下有多少次重复，然后进行分类即可。

这是我的实现

RecurrencePatternAnalyser.java

public class RecurrencePatternAnalyser {

    // Local copy of calendars by add() method 
    private ArrayList<Calendar> mCalendars = new ArrayList<Calendar>();

    // Used to count the uniqueness of each year/month/day 
    private HashMap<Integer, Integer> year_count = new HashMap<Integer,Integer>();
    private HashMap<Integer, Integer> month_count = new HashMap<Integer,Integer>();
    private HashMap<Integer, Integer> day_count = new HashMap<Integer,Integer>();
    private HashMap<Integer, Integer> busday_count = new HashMap<Integer,Integer>();

    // Used for counting payments before due date on weekends
    private int day_goodpayer_ocurrences = 0;
    private int day_goodPayer = 0;

    // Add a new calendar to the analysis
    public void add(Calendar date)
    {
        mCalendars.add(date);
        addYear( date.get(Calendar.YEAR) );
        addMonth( date.get(Calendar.MONTH) );
        addDay( date.get(Calendar.DAY_OF_MONTH) );
        addWeekendDays( date );
    }

    public void printCounts()
    {
        System.out.println("Year: " +  getYearCount() + 
                " month: " +  getMonthCount() + " day: " +  getDayCount());
    }

    public RecurrencePattern getPattern()
    {
        int records = mCalendars.size();
        if (records==1)
            return null;

        RecurrencePattern rp = null;

        if (getYearCount()==records)
        {
            rp = new RecurrencePatternYearly();
            if (records>=3)
                rp.setConfidence(1);
            else if (records==2)
                rp.setConfidence(0.9f);
        }
        else if (getMonthCount()==records)
        {
            rp = new RecurrencePatternMonthly();
            if (records>=12)
                rp.setConfidence(1);
            else
                rp.setConfidence(1-(-0.0168f * records + 0.2f));
        } 
        else 
        {
            calcDaysRepetitionWithWeekends();
            if (day_goodpayer_ocurrences==records)
            {
                rp = new RecurrencePatternMonthly();
                rp.setPattern(RecurrencePattern.PatternType.MONTHLY_GOOD_PAYER);
                if (records>=12)
                    rp.setConfidence(0.95f);
                else
                    rp.setConfidence(1-(-0.0168f * records + 0.25f));
            }
        }

        return rp;
    }

    // Increment one more year/month/day on each count variable
    private void addYear(int key_year)  { incrementHash(year_count, key_year); }
    private void addMonth(int key_month)    { incrementHash(month_count, key_month); }
    private void addDay(int key_day)    { incrementHash(day_count, key_day); }

    // Retrieve number of unique entries for the records
    private int getYearCount() { return year_count.size(); }
    private int getMonthCount() { return month_count.size(); }
    private int getDayCount() { return day_count.size(); }

    // Generic function to increment the hash by 1  
    private void incrementHash(HashMap<Integer, Integer> var, Integer key)
    {
        Integer oldCount = var.get(key);
        Integer newCount = 0;
        if ( oldCount != null ) {
            newCount = oldCount;
        }
        newCount++;
        var.put(key, newCount);
    }

    // As Bank are closed during weekends, some dates might be anticipated
    // to Fridays. These will be false positives for the recurrence pattern.
    // This function adds Saturdays and Sundays to the count when a date is 
    // Friday.
    private void addWeekendDays(Calendar c)
    {
        int key_day = c.get(Calendar.DAY_OF_MONTH);
        incrementHash(busday_count, key_day);
        if (c.get(Calendar.DAY_OF_WEEK) == Calendar.FRIDAY)
        {
            // Adds Saturday
            c.add(Calendar.DATE, 1);
            key_day = c.get(Calendar.DAY_OF_MONTH);
            incrementHash(busday_count, key_day);
            // Adds Sunday
            c.add(Calendar.DATE, 1);
            key_day = c.get(Calendar.DAY_OF_MONTH);
            incrementHash(busday_count, key_day);
        }
    }

    private void calcDaysRepetitionWithWeekends()
    {               
        Iterator<Entry<Integer, Integer>> it =
                busday_count.entrySet().iterator();
        while (it.hasNext()) {
            @SuppressWarnings("rawtypes")
            Map.Entry pair = (Map.Entry)it.next();
            if ((int)pair.getValue() > day_goodpayer_ocurrences)
            {
                day_goodpayer_ocurrences = (int) pair.getValue();
                day_goodPayer = (int) pair.getKey();
            }
            //it.remove(); // avoids a ConcurrentModificationException
        }
    }
}

RecurrencePattern.java

public abstract class RecurrencePattern {

    public enum PatternType {
        YEARLY, MONTHLY, WEEKLY, DAILY, MONTHLY_GOOD_PAYER 
    }   
    public enum OrdinalType {
        FIRST, SECOND, THIRD, FOURTH, FIFTH 
    }

    protected PatternType pattern;
    private float confidence;
    private int frequency;

    public PatternType getPattern() {
        return pattern;
    }

    public void setPattern(PatternType pattern) {
        this.pattern = pattern;
    }

    public float getConfidence() {
        return confidence;
    }
    public void setConfidence(float confidence) {
        this.confidence = confidence;
    }
    public int getFrequency() {
        return frequency;
    }
    public void setFrequency(int frequency) {
        this.frequency = frequency;
    }   
}

RecurrencePatternMonthly.java

public class RecurrencePatternMonthly extends RecurrencePattern {
    private boolean isDayFixed;
    private boolean isDayOrdinal;
    private OrdinalType ordinaltype;

    public RecurrencePatternMonthly()
    {
        this.pattern = PatternType.MONTHLY;
    }
}

RecurrencePatternYearly.java

public class RecurrencePatternYearly extends RecurrencePattern {
    private boolean isDayFixed;
    private boolean isMonthFixed;
    private boolean isDayOrdinal;
    private OrdinalType ordinaltype;

    public RecurrencePatternYearly()
    {
        this.pattern = PatternType.YEARLY;
    }
}   

Main.java

public class Algofin {

    static Connection c = null;

    public static void main(String[] args) {
        //openConnection();
        //readSqlFile();

        RecurrencePatternAnalyser r = new RecurrencePatternAnalyser();

        //System.out.println(new GregorianCalendar(2015,1,30).get(Calendar.MONTH));
        r.add(new GregorianCalendar(2015,0,1));
        r.add(new GregorianCalendar(2015,0,30));
        r.add(new GregorianCalendar(2015,1,27));
        r.add(new GregorianCalendar(2015,3,1));
        r.add(new GregorianCalendar(2015,4,1));

        r.printCounts();

        RecurrencePattern rp;
        rp=r.getPattern();
        System.out.println("Pattern: " + rp.getPattern() + " confidence: " + rp.getConfidence());
    }
}

Answer 7

我认为你必须建造它，而且我认为这将是一个细节问题的项目。首先获得更彻底的要求。您想识别哪些日期模式？列出您希望算法成功识别的示例列表。编写你的算法来满足你的例子。将您的示例放入测试套件中，这样当您稍后收到不同的需求时，您可以确保没有破坏旧的需求。

我预测你会写 200 个 if-then-else 语句。

好吧，我确实有一个想法。熟悉集合、并、覆盖、交集等概念。列出您要搜索的简短模式，例如“十月的每一天”、“十一月的每一天”和“十二月的每一天”。如果这些短模式包含在日期集中，则定义一个 Union 函数，该函数可以以智能方式组合较短的模式。例如，假设您匹配了我上面提到的三种模式。如果将它们联合在一起，您会得到“十月到十二月的每一天”。您的目标可能是返回最简洁的集联合，覆盖您的日期集或类似内容。

Answer 8

看看您最喜欢的日历程序。查看它可以生成哪些事件重复模式。对它们进行逆向工程。