Определить шаблон повторяемости событий для набора дат

Question

Я ищу шаблон, алгоритм или библиотеку, которая возьмет набор дат и вернет описание повторения, если один из них выйдет, т. Е. Набор [11-01-2010 , 11-08-2010, 11-15-2010, 11-22-2010, 11-29-2010] даст что-то вроде «Каждый понедельник ноября».

Кто-нибудь видел что-либо подобное раньше или какие-либо предложения по наилучшему способу его реализации?

Answer 1

Grammatical Evolution (GE) подходит для такого рода проблем, потому что вы ищете ответ, который придерживается определенного языка. Грамматическая эволюция также используется для генерации программ, составления музыки, проектирования и т. Д.

Я бы подойти к задаче, как это:

Структура проблема пространства с грамматикой.

Построить a Context-free Grammar, который может представлять все требуемые шаблоны повторения. Рассмотрим правила производства как эти:

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.geneticprogramming.us/Home_Page.html

Evaluate каждого решения

Функция пригодности может принять во внимание текстуальной длины решения, количество дат, сгенерированных более одного раза, количество пропущенных дат, а также количество ошибочных дат.

Пример кода

По желанию, и потому что это такой интересный вызов, я написал элементарную реализацию алгоритма, чтобы вы начали. Хотя он работает, он ни в коем случае не завершен, дизайн должен окончательно задуматься, и как только вы почерпнули фундаментальные идеи из этого примера, я рекомендую вам рассмотреть использование библиотек, о которых я упомянул выше.

/// <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

Я думаю, вам нужно будет его построить, и я думаю, что это будет дьявол в деталях проекта. Начните с получения более тщательных требований. Какие шаблоны дат вы хотите распознать? Придумайте список примеров, которые вы хотите, чтобы ваш алгоритм успешно идентифицировал. Напишите свой алгоритм для удовлетворения ваших примеров. Поместите свои примеры в тестовый набор, поэтому, когда вы получите разные требования, вы можете убедиться, что вы не сломали старые.

Я предсказываю, что вы напишете 200 операторов if-then-else.

ОК, у меня есть одна идея. Ознакомьтесь с понятиями sets, unions, coverage, intersection и так далее. Имейте список коротких шаблонов, которые вы ищете, например: «Каждый день в октябре», «Каждый день в ноябре» и «Каждый день в декабре». Если эти короткие шаблоны содержатся в наборе дат, тогда определите функцию union, которая может сочетать более короткие шаблоны интеллектуальными способами. Например, допустим, вы сопоставили три шаблона, о которых я упоминал выше. Если вы получите Union, вы получите: «Каждый день с октября по декабрь». Вы могли бы стремиться вернуть наиболее краткий setunions, что cover ваш набор дат или что-то в этом роде.

Answer 3

Посмотрите на свою любимую программу календаря. Посмотрите, какие шаблоны повторяемости событий он может генерировать. Обратный инженер их.

Answer 4

Если ваша цель - генерировать удобочитаемые описания шаблона, как в вашем «Каждый понедельник ноября», то вы, вероятно, захотите начать с перечисления возможных описаний. Описания могут быть разбиты на частоту и пределы, например,

Частота:

• Каждый день ...
• Каждый второй/третий/четвертый день ...
• будние дни/выходные дни. ..
• Каждый понедельник ...
• Alternate понедельники ...
• Первый/второй/последний понедельник ...
• ...

Bounds:

• ... в январе
• ... между 25 марта и 25 октября
• ...

Там выиграл Это не так много, и вы можете проверить их один за другим.

Answer 5

Что бы я сделал:

1. Создать образцы данных
2. Используйте алгоритм кластеризации
3. Сформировать образцов с использованием алгоритма
4. Создание фитнес-функции для измерения, насколько хорошо она соотносится с полный набор данных. Алгоритм кластеризации будет предлагать либо 0, либо 1 предложение, и вы можете отвлечь его от того, насколько хорошо он вписывается в полный набор.
5. Элементат/объединить возникновение с уже найденными наборами и повторить этот алгоритм.

Глядя на это, вы можете использовать либо симулированное отжиг, либо генетический алгоритм. Кроме того, если у вас есть описания, вы можете сравнить описания для создания образца.

Answer 6

Вы можете получить доступ к системной дате или системной дате и времени и сконструировать насыщенные точки календаря в памяти на основе даты и дня недели, возвращенных результатом вызова или функции. Затем используйте количество дней в соответствующих месяцах для их суммирования и добавьте количество дней дневной переменной на вход и/или получите доступ к календарной точке на соответствующую неделю, начинающуюся с воскресенья или понедельника, и вычислите или увеличите индекс до правильного день. Построить текстовую строку с использованием фиксированных символов и вставить соответствующую переменную, такую ​​как полное имя дня недели, по мере необходимости. Для получения всех событий, из которых события должны отображаться или считаться, могут быть множественные обходы.

Answer 7

Во-первых, найти последовательность, если она существует:

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 

Наконец, дело с "в ноябре", "с 2007 по 2010 год" и т.д., должно быть очевидно.

НТН

Answer 8

Мне нравится @arjen ответ, но я не думаю, что есть необходимость для сложного алгоритма. Это так просто. Если есть шаблон, есть шаблон ... поэтому будет работать простой алгоритм. Сначала нам нужно подумать о типах моделей, которые мы ищем: ежедневно, еженедельно, ежемесячно и ежегодно.

Как распознать?

Daily: есть запись каждый день Weekly: есть запись каждую неделю Ежемесячно: есть запись каждый месяц Год: есть запись каждый год

трудно? Нет. Просто подсчитайте количество повторений, которые у вас есть, а затем классифицируйте.

Вот моя реализация

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()); 
    } 
}