確定事件重現模式的一組日期

Question

我正在尋找一種模式，算法或庫，將採取一組日期並返回重現的描述，如果一個退出，即設置[11-01-2010 ，11-08-2010，11-15-2010，11-22-2010，11-29-2010]會產生類似於「11月的每個星期一」的內容。

以前有沒有人看過類似的東西，或者對實現它有什麼建議？

Answer 1

Grammatical Evolution (GE)適用於這類問題，因爲您正在尋找符合某種語言的答案。語法演變也用於節目製作，音樂創作，設計等等。

我接近這樣的任務：

結構問題空間語法。

構建能夠表示所有期望的重現模式的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

評估每個解決方案

適應度函數可以考慮文本長度的解決方案，不止一次生成的日期數量，錯過的日期數量以及生成的錯誤日期數量。

示例代碼

通過請求，因爲它是這樣一個有趣的挑戰，我寫了一個基本的實現算法，讓你開始。雖然它的工作原理尚未完成，但設計應該明確地思考一下，一旦你從這個例子中收集了基本的東西，我建議你考慮使用上面提到的庫。

/// <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函數，以智能方式組合較短的格式。例如，假設您匹配上面提到的三種模式。如果你們在一起，你會得到：「十月到十二月的每一天。」你可以瞄準迴歸最簡潔的setunionscover你的日期或類似的東西。

Answer 3

看看你最喜歡的日曆程序。查看它可以生成的事件重現模式。逆向工程他們。

Answer 4

我會怎麼做：

1. 創建數據
2. 的樣品使用算法
3. 創建一個適應度函數來衡量它有多好相關的使用聚類算法
4. 生成樣本完整的數據集。聚類算法會提出0或1個建議，你可以衡量它與整套設備的匹配程度。
5. Elementate /將事件與已找到的集合合併並重新運行此算法。

看着你可能想要使用模擬退火或遺傳算法。另外，如果您有說明，則可能需要比較說明以生成樣本。

Answer 5

您可以訪問系統日期或系統日期和時間，並根據調用或函數結果返回的日期和星期幾在存儲器中構建粗略日曆點。然後使用相關月份中的天數對它們進行求和並添加輸入中的一天中的變量天數和/或從週日或週一開始訪問相關周的日曆點，並計算或遞增指數天。根據需要使用固定字符構造文本字符串並插入相關變量，例如星期幾的全名。可能需要多次遍歷才能獲得要顯示或計數事件的所有事件。

Answer 6

首先，找一個序列，如果它存在：

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年」 等等，應該是顯而易見的。

HTH

Answer 7

我喜歡@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()); 
    } 
}