double[]-Array diskretisieren

Hallo,

zur Bestimmung des Modus eines double[]-Arrays habe ich eine Methode mit folgender Signatur geschrieben:

public static double[] Modes(this IEnumerable<double> numbers, double discretizationEpsilon)

Um sinnvoll den Modus bzw. die Modi der Werte ermitteln zu können, muss das Array zuerst diskretisiert werden. (Der zweite Parameter der Methode gibt dabei die maximal zulässige Differenz zweier Werte an, um diese als gleich zu betrachten.)
Gibt es eine einfachere, elegantere Möglichkeit, das Array zu diskretisieren, als über alle Elemente zu iterieren und diese in eine zweite Liste zu kopieren, sofern dort nicht schon ein Element mit einer kleineren Abweichung als discretizationEpsilon enthalten ist?

m0rius

Hallo,

Edit 09.08.2012: Das ist schon ein ziemlicher Hack, der nicht verwendet werden sollte. zommi hat weiter unten eine korrekte Lösung gepostet.

eine Möglichkeit wäre die Verwendung eines HashSets unter Angabe eines speziellen IEqualityComparers.

ZB so:

class Program
{
	static void Main(string[] args)
	{
		double[] source = { 1.1, 1, 2, 3, 3, 4, 5 };
		double[] disc = source.Modes(0.5);
	}
}
//-------------------------------------------------------------------------
public static class MyExtensions
{
	public static double[] Modes(this IEnumerable<double> numbers, double discretizationEpsilon)
	{
		HashSet<double> hs = new HashSet<double>(numbers, new ModesComparer(discretizationEpsilon));
		return hs.ToArray();
	}
}
//-------------------------------------------------------------------------
public class ModesComparer : EqualityComparer<double>
{
	private double _discretizationEpsilon;
	//---------------------------------------------------------------------
	public ModesComparer(double discretizationEpsilon)
	{
		if (discretizationEpsilon < 0)
			throw new ArgumentException();

		_discretizationEpsilon = discretizationEpsilon;
	}
	//---------------------------------------------------------------------
	public override bool Equals(double x, double y)
	{
		return Math.Abs(x - y) < _discretizationEpsilon;
	}
	//---------------------------------------------------------------------
	public override int GetHashCode(double obj)
	{
		return 0;
	}
}

Nachtrag:
Diese Implementierung erfüllt zwar den Zweck dieser speziellen Aufgabe - zwei Werte als gleich betrachten falls die absoulte Differenz kleiner als eine gegebene Schranke ist - und dazu wird die GetHashCode-Methode "missbraucht" indem sie immer einen konstanten Wert zurückgibt. Dies entspricht zwar nicht der allgemeinen Definition von GetHashCode, aber für diese spezielle Aufgabe kann das schon so gehackt werden.

Edit:

Bestimmung des Modus eines double[]-Arrays

Was verstehst du darunter?

mfG Gü

Mir kommt da der Gedanke dass dabei unterschiedliche Ergebnisse rauskommen könnten, je nach der Reihenfolge wie die Werte untersucht werden.
Nehmen wir an, alles was sich nur um 1 unterscheidet ist "gleich".
Reihenfolge 2 - 1 - 3 - 4 trägt zuerst 2 ein, 1 und 3 sind dann praktisch schon drin (weil gleich 2), dann wird als nächstes 4 eingetragen.
Reihenfolge 1 - 2 - 3 - 4 trägt zuerst 1 ein, 2 ist wegen der 1 schon drin, dann wird 3 eingetragen und 4 ist auch schon drin.

Ist das so akzeptabel oder muss da auch noch was dran gedreht werden?

Hallo chilic,

Ist das so akzeptabel oder muss da auch noch was dran gedreht werden?

Das muss m0rius bestimmen denn

sofern dort nicht schon ein Element mit einer kleineren Abweichung als discretizationEpsilon enthalten ist?

lässt dies offen.

Generell tritt das von dir angesprochene Problem tritt bei solchen Verfahren (immer) auf. Dies kann zB durch Vorsortierung der Werte umgangen werden.

Um bei deinem Beispiel zu bleiben:
In Variante 1 sind {2, 4} enthalten
in Variante 2 sind {1, 3} enthalten
da aber der akzeptierte Unterschied 1 ist sind beide Mengen wiederum als gleich anzusehen.
Somit könnte man überlegen (da double verwendet wird) ob nicht die resultierende Menge {1.5, 3.5} sein sollte. Wäre dies der Fall könnte das gewünschte Vorgehen mittels Rangordnungsfilter explizit umgesetzt werden.

mfG Gü

Hallo,

für eine Bibliothek, die die Berechnung verschiedener Mittelwerte unterstützt, soll auch der Modus implementiert werden. Für Ganzzahlen ist das ja kein Problem: {1, 2, 4, 2, 3, 4, 2, 4} hat die Modi 2 und 4 (beide sind 3 Mal enthalten), {1, 2, 3, 2, 4} hat den Modus 2 (2 Mal enthalten).

Soll nun der Modus vieler double-Werte emittelt werden, macht dies in vielen Situationen nur Sinn, wenn eine gewisse Abweichung zugelassen wird. So soll beispielsweise der Modus von {0.050001, 0.05, 0.049999, 0.08, 0.09} mit einem erlaubten Abweichungswert Epsilon von 0.001 gleich 0.05 sein, weil die ersten drei Werte als gleich anzusehen sind und damit das häufigste Vorkommen aufweisen.

Allerdings führt auch der pragmatische Ansatz (Iteration + Kopie in 2. Liste) nicht zwangsläufig zum gewünschten Ergebnis: So würde 0.050001 als neuer Wert mit der Anzahl der Vorkommen = 1 der neuen Liste hinzugefügt werden. Die folgenden Werte 0.05 und 0.049999 würden wegen der Toleranz nicht hinzugefügt werden, sondern das Vorkommen auf 3 erhöhen. Letzten Endes ist aber nicht zwangsläufig der zuerst (und einzig) eingetragene Wert 0.050001 der Modus, sondern eben 0.05 als arithmetisches Mittel (meiner Ansicht nach ist das eine sinnvolle Definition) der 3 als gleich anzusehenden Werte.

m0rius

Dann wäre die Rundungsfunktion was für dich?
Du hast ja klar definiert, welche Zahlen als exakt gelten sollen und welche auf diese exakten Werte gerundet werden sollen.

Hallo m0rius,

in diesem Fall könnte meine obige Modes-Erweiterungsmethode durch diese ersetzt werden:

public static double[] Modes(this IEnumerable<double> numbers, double discretizationEpsilon)
{
	return numbers
		.GroupBy(d => d, new ModesComparer(discretizationEpsilon))
		.Select(d => d.Average())
		.ToArray();
}

mfG Gü

Hi m0rius,

hab mich mal drangesetzt und ne Methode implementiert.

Meine Auffassung ist:

die Modi sind Zahlen, in deren Epsilon/2-Umkreis jeweils die meisten Elemente der Collection enthalten sind. Und diese Zahlen sind nicht notwendigerweise in der Eingangscollection enthalten

Die Berechnung ist:
Man sortiert die Eingangszahlen und geht nun alle Intervalle zusammenhängender Blöcke durch, die gerade so noch kleiner als Epsilon sind.
Jetzt filtert man diejenigen Intervalle mit den meisten Elementen heraus und gibt deren Mittelwert zurück.

Nun gibts ja eigentlich n² viele Intervalle die man überprüfen muss, aber man kann auch etwas cleverer in einem Durchlauf mit O(n) alle maximal breiten Intervalle, die gerade so noch kleiner als Epsilon sind, ermitteln.
Hierbei schiebt man ein Intervall über die sortierten Zahlen, verschiebt aber untere und obere Grenze separat.
Wenn das Intervall bereits kleiner als Epsilon ist, brauch ich Intervalle mit derselben oberen Grenze, aber größeren kleineren Grenzen ja nicht mehr zu betrachten, sondern verschiebe nun lieber die obere Grenze weiter. Und so kann man immer die Grenzen verschieben und die eine der anderen Nachzeiehn, sodass man immer knapp unter/über Epsilon bleibt.

Aber nun zur (verbesserten) Implementierung:

using System;
using System.Collections.Generic;
using System.Linq;

namespace DoubleModus
{
    static class Extensions
    {
        /// <summary>
        /// Berechnet die Modi einer Collection bei Beachtung der Diskretisierungseinheit Epsilon.
        /// </summary>
        /// <param name="numbers">Eine Collection</param>
        /// <param name="discretizationEpsilon">Diskretisierungseinheit Epsilon</param>
        /// <returns>Array aus Mittelwerten aller maximal-Epsilon-breiten Intervalle mit den jeweils meisten Elementen</returns>
        public static double[] Modes(this IEnumerable<double> numbers, double discretizationEpsilon)
        {
            LinkedList<Interval> bestIntervals = new LinkedList<Interval>();
            int maxCount = 0;

            // Zahlen sortieren
            IOrderedEnumerable<double> sorted = numbers.OrderBy(x => x);

            // Alle maximalgroßen Intervalle durchgehen
            foreach (Interval interval in sorted.Intervals(discretizationEpsilon))
            {
                // Wenn neuer Rekord, alles bisherige löschen
                if (interval.ElementsInside > maxCount)
                {
                    maxCount = interval.ElementsInside;
                    bestIntervals.Clear();
                }

                // Gegebenfalls dieses Intervall als eines der Maximalen abspeichern
                if (interval.ElementsInside == maxCount)
                {
                    bestIntervals.AddLast(interval);
                }
            }

            // Mittelpunkte der Intervalle zurückgeben
            return bestIntervals
                    .Select(x => x.MidPoint)
                    .ToArray();
        }

        /// <summary>
        /// Iteriert über alle maximalen Intervalle aus der Collection, welche kleiner gleich Epsilon sind.
        /// </summary>
        /// <param name="sortedNumbers">Sortierte Aufzählung</param>
        /// <param name="discretizationEpsilon">Maximalgröße der Intervalle</param>
        public static IEnumerable<Interval> Intervals(this IEnumerable<double> sortedNumbers, double epsilon)
        {
            SlidingWindow window = new SlidingWindow(sortedNumbers);

            window.MoveStart();
            window.MoveEnd();

            if(window.EndReached) // wenn kein Element enthalten
                yield break;

            Interval lastInterval = window.Interval;

            // Solange das Ende noch nicht erreicht ist
            while (!window.EndReached)
            {
                // Obere Grenze solange weiterschieben, wie es geht
                while (!window.EndReached && window.Width <= epsilon)
                {
                    lastInterval = window.Interval; // das letzte immernoch speichern
                    window.MoveEnd();
                } 

                // das letzte Intervall zurückgeben, welches gerade noch kleiner gleich Epsilon war
                yield return lastInterval;

                // Untere Grenze solange nachziehen bis wir wieder Epsilon erreicht haben
                while (!window.EndReached && window.Width > epsilon)
                {
                    window.MoveStart();
                }    
            }
        }
        

        public struct Interval
        {
            public double Start;
            public double End;
            public int ElementsInside;

            public double MidPoint { get { return (Start + End) / 2; } }

            public override string ToString()
            {
                return String.Format("[{0} : {1}]({2})", Start, End, ElementsInside);
            }
        }


        /// <summary>
        /// Ein über eine Collection gleitendes Fenster
        /// </summary>
        public class SlidingWindow
        {
            IEnumerator<double> StartEnumerator, EndEnumerator;

            public bool EndReached { get; private set; }
            public int ElementsInside { get; private set; }

            public double Start { get { return StartEnumerator.Current; } }
            public double End { get { return EndEnumerator.Current; } }
            public double Width { get { return End - Start; } }

            public SlidingWindow(IEnumerable<double> collection)
            {
                StartEnumerator = collection.GetEnumerator();
                EndEnumerator = collection.GetEnumerator();
                ElementsInside = 1;
                EndReached = false;
            }

            public Interval Interval
            {
                get
                {
                    return new Interval()
                    {
                        Start = Start,
                        End = End,
                        ElementsInside = ElementsInside
                    };
                }
            }

            public void MoveStart() // verschiebt den Beginn des Fensters
            {
                ElementsInside--;
                EndReached |= !StartEnumerator.MoveNext();
            }
            public void MoveEnd() // verschiebt das Ende des Fensters
            {
                ElementsInside++;
                EndReached |= !EndEnumerator.MoveNext();
            }
        }
    }
}

Nachtrag: Nun hab ich oben was von O(n) geschrieben, beim durchlaufen der Intervalle. Da aber das Sortieren der Eingangswerte O(n log n) benötigt, ist dies natürlich die gesamte Laufzeit der Methode.

beste Grüße
zommi

Hallo zommi,

irgendwo ist noch ein Bug drin. Wenn ich deinen Code mit { 0.050001, 0.05, 0.049999, 0.08, 0.09 } und eps=1e-3 teste kommt nur 0.05 anstatt { 0.05, 0.08, 0.9 } raus. Oder ist das gemäß deiner Auffassung der Mode so korrekt?

mfG Gü

Hi gfoidl,

ich seh das schon als korrekt an.
der Modus 0.05 repräsentiert ja {0.050001, 0.05, 0.049999}, also 3 Zahlen in seiner Umgebung. Und um 0.08 und 0.09 gibts kein Intervall das ebenfalls mindestens 3 Zahlen umfasst.
(Höchstens eines, dass eine Zahl umfasst, was du auch siehst, wenn du einfach mal alle Intervals ausgibst. Also einfach nur die Methode Intervals aufrufen und nicht Modes.)

beste Grüße
zommi

btw: den muss ich einfach noch loswerden 🙂 Deine EqualityComparer ist schon mörder-gehackt. Nicht nur, dass GetHashCode ja fies ist, nein Equals selbst ist ja nicht einmal transitiv. 8o Insofern ein "böse" von mir 😉

Hallo zommi,

vielen Dank für deine Implementierung und den Code, da arbeite ich mich mal in Ruhe durch 😃.

m0rius

Hallo zommi,

hast Recht. Ich hab den Modus falsch berücksichtigt und anstatt dessen nur "gefiltert".

Auf den Kommentar hab ich eh schon lange gewartet (da mir das sehr wohl bewusst ist) 😄

mfG Gü

Hallo nochmal,

da arbeite ich mich mal in Ruhe durch 😃

Hab jetzt eine verschönerte Implementierung hochgeladen. Siehe oben! Die algorithmische Idee mit dem verschiebbaren Intervall ist sehr schön objektorientiert umsetzbar. (Was man wohl nicht von allen Algorithmen behaupten kann)

Sollte jetzt wesentlich besser verständlich sein!

beste Grüße
zommi

Hallo zommi,

hierfür hat sich deine Mühe gelohnt: NAverage: Extended mean calculation functionality for .NET

m0rius