algorithm - data - Determine el patrón de recurrencia del evento para un conjunto de fechas
data structure and algorithm pdf (8)
Creo que tendrás que construirlo, y creo que será un demonio en el tipo de proyecto de detalles. Comience por obtener requisitos mucho más completos. ¿Qué patrones de fecha quieres reconocer? Cree una lista de ejemplos que desee que su algoritmo identifique con éxito. Escribe tu algoritmo para cumplir con tus ejemplos. Ponga sus ejemplos en una suite de prueba para que luego, cuando obtenga diferentes requisitos, pueda asegurarse de que no rompió los anteriores.
Predigo que escribirás 200 afirmaciones si-entonces-más.
OK, tengo una idea Familiarícese con los conceptos de sets , unions , coverage , intersection , etc. Tenga una lista de patrones cortos que busque, por ejemplo, "Todos los días de octubre", "Todos los días de noviembre" y "Todos los días de diciembre". Si estos patrones cortos están contenidos dentro del conjunto de fechas, entonces defina una función de union que pueda combinar patrones más cortos de manera inteligente. Por ejemplo, digamos que combinaste los tres patrones que menciono anteriormente. Si los une, obtendrá "Todos los días de octubre a diciembre". Podría aspirar a devolver el set más breve de unions que cover su conjunto de fechas o algo así.
Estoy buscando un patrón, algoritmo o biblioteca que tome un conjunto de fechas y devuelva una descripción de la recurrencia si se sale, es decir, el conjunto [11-01-2010, 11-08-2010, 11-15-2010 , 11-22-2010, 11-29-2010] produciría algo así como "Todos los lunes de noviembre".
¿Alguien ha visto algo como esto antes o tiene alguna sugerencia sobre la mejor manera de implementarlo?
Echa un vistazo a tu programa de calendario favorito. Vea qué patrones de recurrencia de eventos puede generar. Invertirlos en ingeniería.
Me gusta la respuesta de @arjen pero no creo que haya necesidad de algoritmos complejos. Esto es tan simple. Si hay un patrón, hay un patrón ... por lo tanto, un algoritmo simple funcionaría. Primero debemos pensar en los tipos de patrones que estamos buscando: diarios, semanales, mensuales y anuales.
¿Cómo reconocer?
Diariamente: hay un registro todos los días. Semanalmente: hay un registro todas las semanas. Mensual: hay un registro todos los meses. Anual: hay un registro todos los años.
¿Difícil? No. Solo cuenta cuántas repeticiones tienes y luego clasifica.
Aquí está mi implementación
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());
}
}
Primero, encuentra una secuencia, si existe:
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
Finalmente, tratar con "en noviembre", "de 2007 a 2010", etc., debería ser obvio.
HTH
Puede acceder a la fecha del sistema o a la fecha y hora del sistema y construir puntos de calendario crudos en la memoria en función de la fecha y el día de la semana según lo que obtenga el resultado de la llamada o función. Luego use el número de días en los meses relevantes para sumarlos y agregue el número de días de la variable de día en la entrada y / o acceda al punto del calendario para la semana correspondiente que comienza el domingo o el lunes y calcule o aumente el índice hacia adelante hasta el punto correcto. día. Construya una cadena de texto utilizando caracteres fijos e inserte la variable relevante, como el nombre completo del día de la semana, según sea necesario. Puede haber múltiples recorridos necesarios para obtener todos los eventos de los cuales se mostrarán o contarán las ocurrencias.
Que haría yo:
- Crear muestras de los datos.
- Utilice un algoritmo de agrupamiento
- Generar muestras utilizando el algoritmo.
- Crear una función de aptitud para medir qué tan bien se correlaciona con el conjunto completo de datos. El algoritmo de agrupación generará 0 o 1 sugerencias, y puede medirlo en función de su compatibilidad con el conjunto completo.
- Elementate / fusione la ocurrencia con los conjuntos ya encontrados y vuelva a ejecutar este algoritmo.
En cuanto a eso, es posible que desee utilizar el recocido simulado o un algoritmo genético. Además, si tiene las descripciones, es posible que desee comparar las descripciones para generar una muestra.
Si su propósito es generar descripciones del patrón legibles para las personas, como en su "Todos los lunes de noviembre", es probable que desee comenzar enumerando las descripciones posibles. Las descripciones se pueden dividir en frecuencia y límites, por ejemplo,
Frecuencia:
- Todos los días ...
- Cada otro / tercer / cuarto día ...
- Laborables / fines de semana ...
- Cada lunes ...
- Lunes alternos ...
- El primer / segundo / último lunes ...
- ...
Límites:
- ... en Enero
- ... entre el 25 de marzo y el 25 de octubre
- ...
No habrá tantos de cada uno, y puedes verificarlos uno por uno.
La evolución gramatical (GE) es adecuada para este tipo de problema, porque está buscando una respuesta que se adhiera a un determinado idioma. La evolución gramatical también se utiliza para la generación de programas, componer música, diseñar, etcétera.
Me acercaría a la tarea así:
Estructurar el espacio problema con una gramática .
Construya una gramática libre de contexto que pueda representar todos los patrones de recurrencia deseados. Considere reglas de producción como estas:
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
Un ejemplo de un patrón generado por estas reglas es: ''cada segundo y tercer miércoles del mes en el año 2010 y todos los martes en el año 2011''
Una forma de implementar una gramática de este tipo sería a través de una jerarquía de clases que luego operará por medio de la reflexión, como lo he hecho en el siguiente ejemplo.
Asigne este idioma a un conjunto de fechas
Debe crear una función que tome una cláusula de su idioma y devuelva de forma recursiva el conjunto de todas las fechas cubiertas por él. Esto le permite comparar sus respuestas con la entrada.
Guiado por la gramática, busca posibles soluciones.
Puede usar un algoritmo genético o un recocido simulado para hacer coincidir las fechas con la gramática, probar suerte con la programación dinámica o comenzar de manera simple con una enumeración de fuerza bruta de todas las cláusulas posibles.
Si elige un algoritmo genético, su concepto de mutación debe consistir en sustituir una expresión por otra basada en la aplicación de una de sus reglas de producción.
Eche un vistazo a los siguientes sitios relacionados con GE para obtener códigos e información: http://www.bangor.ac.uk/~eep201/jge/
http://nohejl.name/age/
http://www.geneticprogramming.us/Home_Page.html
Evaluar cada solución
La función de aptitud podría tener en cuenta la longitud textual de la solución, el número de fechas generadas más de una vez, el número de fechas perdidas, así como el número de fechas incorrectas generadas.
Código de ejemplo
Por solicitud y porque es un desafío tan interesante, he escrito una implementación rudimentaria del algoritmo para que comiences. Aunque funciona, de ninguna manera está terminado, el diseño debería tener un pensamiento más definitivo, y una vez que haya recogido las conclusiones fundamentales de este ejemplo, le recomiendo que considere usar una de las bibliotecas que mencioné anteriormente.
/// <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;
}
}
}
Espero que esto te ponga en camino. Asegúrese de compartir su solución real en algún lugar; Creo que será bastante útil en muchos escenarios.