Fusionando puntos aproximadamente iguales en el conjunto de datos

Question

Estoy buscando un algoritmo que pueda ejecutarse rápidamente a través de una matriz corta (< 30 elementos) y fusionar puntos que sean aproximadamente iguales. Probablemente termine siendo algún tipo de algoritmo de segmentación.

El contexto es el siguiente: estoy buscando los picos más altos en un conjunto de datos. Ya he separado los máximos más altos de la escoria utilizando una implementación unidimensional de J-SEG, pero en cualquier lugar donde el conjunto de datos es "plano", obtengo un punto por cada elemento a lo largo de la meseta. Necesito poder fusionar estos puntos de manera adaptativa a un único punto en el centro de la meseta. (Esto también significa que no sé cuántos grupos habrá.)

Muestra conjunto de datos 1 (Muestra/entrada artificial) de entrada:

97 54686024814922.8 
118 406406320535.935 
148 24095826539423.7 
152 1625624905272.95 
160 1625625128029.81 
166 1625625152145.47 
176 1625625104745.48 
179 1625625127365.09 
183 1625625152208.44 
190 1625624974205.81 
194 21068100428092.9 
247 54686024895222.1 

salida ideal:

97 54686024814922.8 
118 406406320535.935 
148 24095826539423.7 
159 1625625061816.08 


182 1625625089631.21 



194 21068100428092.9 
247 54686024895222.1 

muestra de datos 2 (entrada real): de entrada:

2 196412376940671 
123 206108518197124 
135 194488685387149 
148 178463949513298 
154 192912098976702 
156 195042451997727 
161 195221254214493 
168 204760073508681 
172 189240741651297 
182 191554457423846 
187 215014126955355 
201 202294866774063 

Idea l Salida:

2 196412376940671 
123 206108518197124 
135 194488685387149 
148 178463949513298 
157 194391935062974 


168 204760073508681 
172 189240741651297 
182 191554457423846 
187 215014126955355 
201 202294866774063 

muestra de datos 3 (entrada real) de entrada:

2 299777367852602 
26 263467434856928 
35 293412234811901 
83 242768805551742 
104 226333969841383 
107 227548774800053 
178 229173574175201 
181 229224441416751 
204 244334414017228 
206 245258151638118 
239 198782930497571 

de salida ideal:

2  299777367852602 
26  263467434856928 (May be merged 
35  293412234811901 depending on parameters) 
83  242768805551742 
105.5 226941372320718 

179.5 229199007795976 

205  244796282827673 

239  198782930497571 

(. editará en información adicional según sea necesario)

Answer 1

No estoy seguro de si esto es exactamente lo que quiere, pero no hay otras respuestas publicadas, así que h antes de irnos

Lo miré desde la perspectiva de un gráfico. Si estuviera mirando un gráfico y quisiera determinar qué puntos eran horizontales similares que terminarían siendo relativos a la escala de los gráficos. Así que hice una función que acepta un porcentaje de la escala que desea que se considere igual. Luego toma ese porcentaje y lo multiplica por la diferencia máxima entre su conjunto de datos.

Además, el valor similar siempre se compara con el promedio de la meseta actualmente ubicada. Una vez que se detecta que una meseta termina, se juntan las x y se divide por 2 para obtener el centro y luego toma el valor promedio de y y lo agrega como un punto de datos final.

Sin tener acceso a buenos datos de muestra, todo lo que tengo que hacer es generar mi muy pobre generador de datos. Pero en mis valores de prueba dentro del 1% generalmente eliminé aproximadamente la mitad de mis puntos de datos.

Ahora es importante tener en cuenta que esta es una dimensión, la distancia x se ignora por completo. También podría ampliarlo fácilmente para que sea también de dos dimensiones. Otra cosa que consideré hacer es que, en lugar de generar un solo punto de datos para representar mesetas, podría generar un punto de inicio y final del promedio.

namespace PointCondenser 
{ 
    public static class Extensions 
    { 
     static public bool AlmostEqual<T>(this T value, T value2, T epsilon) 
     { 
      return (Math.Abs((dynamic)value - value2) < epsilon); 
     } 
    } 

    public struct Point 
    { 
     public Point(double x, double y) 
     { 
      X = x; 
      Y = y; 
     } 

     public override string ToString() 
     { 
      return string.Format("{0}\t{1}", X, Y); 
     } 

     public double X; 
     public double Y; 
    } 
    class Program 
    { 
     static public Point RandomYPoint(int i) 
     { 
      var r = new Random(); 

      var r2 = new Random(i); 

      var variance = r2.NextDouble()/100; 

      return new Point(i, Math.Abs(r.NextDouble() - variance) * 100); 
     } 

     static public IEnumerable<Point> SmoothPoints(IEnumerable<Point> points, double percent) 
     { 
      if (percent <= 0 || percent >= 1) 
       throw new ArgumentOutOfRangeException("percent", "Percentage outside of logical bounds"); 

      var final = new List<Point>(); 

      var apoints = points.ToArray(); 

      var largestDifference = apoints.Max(x => x.Y) - apoints.Min(x => x.Y); 
      var epsilon = largestDifference * percent; 

      var currentPlateau = new List<Point> { apoints[0] }; 

      for (var i = 1; i < apoints.Length; ++i) 
      { 
       var point = apoints[i]; 
       if (point.Y.AlmostEqual(currentPlateau.Average(x => x.Y), epsilon)) 
        currentPlateau.Add(point); 
       else 
       { 
        var x = (currentPlateau[0].X + currentPlateau[currentPlateau.Count - 1].X)/2.0; 
        var y = currentPlateau.Average(z => z.Y); 

        currentPlateau.Clear(); 
        currentPlateau.Add(point); 

        final.Add(new Point(x, y)); 
       } 
      } 

      return final; 
     } 

     static void Main(string[] args) 
     { 
      var r = new Random(); 
      var points = new List<Point>(); 


      for (var i = 0; i < 100; ++i) 
      { 
       for (var n = 0; n < r.Next(1, 5); ++n) 
       { 
        var p = RandomYPoint(points.Count); 
        points.Add(p); 
        Console.WriteLine(p); 
       } 
       Thread.Sleep(r.Next(10, 250)); 
      } 

      Console.Write("\n\n Condensed \n\n"); 


      var newPoints = SmoothPoints(points, .01); 

      foreach (var p in newPoints) 
       Console.WriteLine(p); 
     } 
    } 
} 

Answer 2

Otro enfoque para agrupar sin parámetros es fusionar los puntos de datos más cercanos. Eso es en cada pasada que encontrará la brecha más pequeña entre dos puntos de datos y luego fusionar los pares con esa brecha.

Como resultado, en cada pase disminuirá la granularidad. Sin embargo, encontrar el espacio más pequeño puede ser costoso a menos que los puntos de datos estén ordenados según el atributo que comparas.

Answer 3

En retrospectiva, también podría haber hecho esto con regresión lineal: si la pendiente es cercana a cero, y la pendiente al siguiente punto es similar a la pendiente promedio de puntos anteriores en la meseta, registre el siguiente punto para fusionarse y continuar.