Julia: Ähnlichkeitsabfragen auf Bewegungsdaten

Hallo Forum,

ich habe eine ganze Menge an Bewegungsdaten, die durch unterschiedliche Sensoren aufgenomen worden sind. Meine Überlegung ist, diese in ein relationales Schema (PostgreSQL) einzupflegen, um anschließend Ähnlichkeitsabfragen auf diesen Daten durchzuführen.

Das Problem: Ich bin mir nicht sicher, ob es überhaupt geht / ob es zu kompliziert für mich ist.

Kennt sich vielleicht jemand mit Ähnlichkeitsabfragen auf Bewegungsdaten aus und kann mir ein paar grundlegende Informationen / Hinweise dazu schreiben? Oder ein paar Links für die Einstiger geben?

Ich bin bei der Recherche in diesem Zusammenhang ein paar mal auf den Begriff k-d-Bäume gestoßen, kann diesen aber nicht so richtig zuordnen. Wenn ich diese nutzen möchte, muss ich dies bereits bei der Erstellung meines Schema berücksichtigen?

Schönen Dank im Voraus und viele Grüße

Julia

  1. Hallo,

    Das Problem: Ich bin mir nicht sicher, ob es überhaupt geht / ob es zu kompliziert für mich ist.

    Gehen tut es bestimmt. Obs zu kompliziert ist, kriegt man dann irgendwan mit…

    Kennt sich vielleicht jemand mit Ähnlichkeitsabfragen auf Bewegungsdaten aus und kann mir ein paar grundlegende Informationen / Hinweise dazu schreiben? Oder ein paar Links für die Einstiger geben?

    Statistik

    Ich bin bei der Recherche in diesem Zusammenhang ein paar mal auf den Begriff k-d-Bäume gestoßen, kann diesen aber nicht so richtig zuordnen.

    K-d-Baum

    Wenn ich diese nutzen möchte, muss ich dies bereits bei der Erstellung meines Schema berücksichtigen?

    Ja, die Überlegungen zum Datenmodell sollten am Anfang stattfinden.

    Vielmehr kann ich leider nicht dazu sagen.

    Gruß
    Kalk

  2. Hallo Julia,

    um dazu irgendwas sagen zu können, müsste man vielleicht wissen, welcher Art deine Bewegungsdaten sind. Bilder? Ein Piep eines Bewegungsmelders, der sagt "hier und jetzt war ETWAS"? Ein Piep eines RFC-Transponders, der sagt: "Person AB oder Objekt XY war zum Zeitpunkt T am Ort Q"?

    Kannst Du, ohne mögliche Betriebs- oder andere Geheimnisse zu verraten, beschreiben, welche Bewegungen Du da beobachtet hast und welche Ähnlichkeiten du finden willst?

    Ein K-D-Baum hat den Zweck, eine gegebene Menge an Punkten in einem n-dimensionalen Raum (als Begriff der Linearen Algebra) so aufzuteilen, dass man mit binärer Suche feststellen kann, in welchem der so gefundenen Teile ein neuer Punkt anzuordnen wäre. Ob Dir das bei der Suche nach Ähnlichkeiten hilft, weiß ich nicht. Wenn deine Sensoren an festen Orten stehen, ist der K-D-Baum vermutlich sogar ungeeignet, weil Du ja nur von diesen Orten Meldungen bekommen kannst und nicht von anderswo. Dir würde dann die Sensor-ID für eine einfache Indexsuche reichen, um andere Meldungen dieses Sensors zu identifizieren.

    Es sei denn, deine Sensoren können variable Orte melden (z.B. Sensor X überwacht einen größeren Bereich und stellt fest, dass sich an der Raumzeit-Koordinate (x,y,z,t) in diesem Bereich etwas tut. Bewegt sich ein Objekt durch den überwachten Bereich, würde dieser Sensor eine Folge von Messungen mit unterschiedlichen Orten und Zeiten liefern. Das wäre dann aber ein sehr spezieller und teurer Sensor.

    Rolf

    --
    sumpsi - posui - clusi
    1. Hallo Rolf,

      vielen Dank für Deine Antwort!

      Ich möchte die Daten nutzen, die menschliche Bewegungen (z.B. Laufen, Springen, Tanzen usw.) repräsentieren und durch unterschiedliche Körpersensoren aufgenommen werden.

      Die Sensoren werden an verschiedenen Körperteilen befestigt und liefern Informationen unterschiedlicher Art:

      • XYZ-Koordinaten vom Körperpunkt
      • Relative Daten zum Körperrumpf
      • Winkeldaten z.B. für Armbewegungen usw.

      Beispiel (sehr verkürzt):

      |%frame Nr.|accX |accY |accZ | |1 | 0.17376493| 3.3732831| 9.2007666| |2 | 0.19092396| 3.4044027| 9.1984268| |3 | 0.18168643| 3.4179294| 9.2029451| |... |... |... |...

      Diese Daten möchte ich in ein relationales Schema einpflegen. Die Ähnlichkeitsabfragen die ich anschließend machen möchte, sollten zu einer bestimmten Bewegung (z.B. Sprung mit beiden Beinen) in der Datenbank nach ähnlichen Bewegungen suchen und diese ausgeben.

      Und dazu versuche ich jetzt erstmal die Grundlegende Informationen zu finden, aber die Suche gestaltet sich bisher sehr spärlich. Daher auch das Posting und die Frage nach K-D-Bäumen.

      Ich hoffe, ich konnte das einigermaßen vermitteln und meine Fragen dazu sind jetzt etwas klarer geworden.

      Noch mal vielen Dank und viele Grüße

      Julia

      1. Hallo Julia,

        spannende Aufgabe, das wird mit Sicherheit kein Leichtes. Ich hab leider nur ein paar generische Tipps für dich, vielleicht helfen sie ja trotzdem.

        Zuerst, vergiss mal alles über die Datenbank und sonstige Peripherie, das lenkt in diesem Stadium der Lösungsfindung nur vom Kern des Problem ab.

        Und dann breite dein Sonar aus und versuche ähnliche Probleme zu loten. Bei deiner Beschreibung musste ich zum Beispiel an Gestenerkennung denken, das könnte ein mögliches Stichwort für deine Recherche sein. Solche Algorithmen werden heute kaum noch per Hand entworfen, weil eine analytische Herangehensweise zu aufwendig ist. Stattdessen setzt man gerne maschinelles Lernen darauf an, das könnte auch in deinem Fall funktionieren.

        Viele Grüße
        1UP

        1. Hallo 1unitedpower,

          vielen Dank für Deine Antwort und für die Hinweise.

          Ich bin auch bei der Recherche schon oft genau auf "Deep Learning", "Neuronale Netze" usw. gestoßen.

          Meine Aufgabestellung verlangt aber explizit zu schauen, ob die Ähnlichkeitssuche mit relationalen Datenbanken lösbar ist (u.a. auch ob es sinnvoll ist), und entsprechende Strukturen für die Anfragen vorzubereiten.

          Aber ich schaue trotzdem nochmal in die Richtung des maschinelen Lernens, vielleicht lässt sich das verbinden.

          Viele Grüße

          Julia

          1. Meine Aufgabestellung verlangt aber explizit zu schauen, ob die Ähnlichkeitssuche mit relationalen Datenbanken lösbar ist (u.a. auch ob es sinnvoll ist), und entsprechende Strukturen für die Anfragen vorzubereiten.

            Das wieder klingt für eine Person, die immerhin den Bachelor in Informatik machen will, als "machbar".

          2. Hallo Julia,

            Meine Aufgabestellung verlangt aber explizit zu schauen, ob die Ähnlichkeitssuche mit relationalen Datenbanken lösbar ist

            Ich habe eine Weile überlegt, wie ich das angehen würde.

            Vermutlich hast Du Sensordaten von einer Anzahl von Bewegungstypen, und von jedem Typ mehrere Messungen. Und dann bekommst Du Sensordaten von einer neuen Messung, und sollst dann sagen: Das war wahrscheinlich eine Kniebeuge, ein Nasebohren oder ein Torwandschuss.

            Erster Schritt wäre wohl, die Bewegungsdauer zu normieren, und die Messzeitpunkte der Sensoren von absoluter auf relative Zeitmessung umzustellen.

            Im zweiten Schritt würde ich mir die Bewegungskurve jedes einzelnen Sensors anschauen. Es ist anzunehmen, dass alle Sensoren ihre Daten im gleichen Takt liefern, d.h. du hast 100 Messzeitpunkte und von jedem Sensor einen Messwert zu diesem Zeitpunkt. Wenn deine Messungen in dieser Hinsicht nicht vergleichbar sind (z.B. Bewegungstyp "Sprung", Messung 1 hat 157 Messzeiten und Messung 2 hat 132 Messpunkte), dann musst Du normieren. Zum Beispiel auf 100 zeitlich gleich verteilte Messpunkte. Dazu musst Du die Bewegungskurve des Sensors passend interpolieren - im einfachsten Fall linear. Wenn die zeitlichen Abstände der Messungen klein genug sind, sollte das hinreichend sein.

            Du brauchst ggf. auch eine räumliche Normierung. Wenn du die Sprungmessung eines Kindes hast, und die Sprungmessung von Dirk Nowitzki, sind die Sensoren unterschiedlich weit voneinander entfernt. D.h. das musst Du auf eine Einheitsgröße skalieren, und hoffen, dass das überhaupt möglich ist. Hier wäre einer der Knackpunkte der Arbeit.

            Am Ende hat die Bewegung 100 Datensätze, und zu jedem Datensatz gehört ein Messwert pro Sensor.

            Aus deinen Rohdaten von - sagenwirmal - 100 Sprüngen kannst Du nun DEN typischen Sprung herausdestillieren. D.h. du hast pro Sensor und Zeitpunkt 100 Zahlenwerte. Dafür kannst Du Mittelwert und Varianz bestimmen, und hast dann als Sprungcharakteristik 100 Zeitpunkte für N Sensoren, und pro Sensor Mittelwert und Varianz. Für die Ermittlung von Mittelwert und Varianz müsste man bereits eine SQL Abfrage einsetzen können (das wäre aber relativ unwichtig, das ist noch Teil der Datenpräparation).

            Jetzt kommt eine unbekannte Bewegung, die Du erkennen sollst. Auch die normierst Du zeitlich und räumlich auf 100 Messzeitpunkte mit je N Sensorwerten.

            Jetzt wird es spannend. Vermutlich soll nun EINE SQL Abfrage eine Liste von Kennzahlen liefern, die die Ähnlichkeit der unbekannten Bewegung zu den bekannten Bewegungsmustern beschreibt. Reduzieren wir das mal auf einen Vergleichs-Bewegungstyp. Da müsste man pro Zeitpunkt die Abweichung der gemessenen Bewegung zum "typischen" Sensorwert bestimmen, und dann feststellen, wie "gut" diese Abweichung in Anbetracht der Varianz dieses Sensorwertes ist. Eventuell kann man hier, analog der Methode der kleinsten Quadrate, stärkere Abweichungen höher gewichten als kleine Abweichungen. Und dann summierst Du alle diese Abweichungen und nimmst das als Kennzahl. An Hand deiner Ausgangsbewegungsmuster, aus denen du die charakteristische Bewegung gebildet hast, kannst Du ein Maß dafür finden, welcher Bereich für diese Kennzahl gut oder schlecht ist.

            Keine Ahnung ob das zielführend ist. Es ist nur ein grobes Ideengerüst. Du musst Dir deinen Bachelor (oder sagt man dann Bachelorette?) ja auch verdienen 😀

            Aber auf jeden Fall ist es nicht NUR mit SQL lösbar, man muss schon einiges an Arbeit in die Datenaufbereitung stecken.

            Rolf

            --
            sumpsi - posui - clusi
            1. Hallo Rolf,

              vielen vielen Dank, dass Du Dir so viele Gedanken gemacht hast. Finde ich super-nett!

              Vermutlich hast Du Sensordaten von einer Anzahl von Bewegungstypen, und von jedem Typ mehrere Messungen. Und dann bekommst Du Sensordaten von einer neuen Messung, und sollst dann sagen: Das war wahrscheinlich eine Kniebeuge, ein Nasebohren oder ein Torwandschuss.

              Genau so sieht es aus!

              Erster Schritt wäre wohl, die Bewegungsdauer zu normieren, und die Messzeitpunkte der Sensoren von absoluter auf relative Zeitmessung umzustellen.

              [...]

              Aber auf jeden Fall ist es nicht NUR mit SQL lösbar, man muss schon einiges an Arbeit in die Datenaufbereitung stecken.

              Sehr sehr sinnvolle Gendanken! Danke Dir! Diese werde ich beim nächsten Treffen mit dem Professor auf jeden Fall zur Sprache bringen.

              In den ersten Gespächen zur Bachelorarbeit habe ich die Aufgabe so aufgefasst, dass die Daten (so wie sie sind) in die Datenbank eingepflegt werden sollten. Natürlich muss dafür ein entsprechendes relationales Schema erstellt werden.

              Und die Ähnlichkeitsanfragen wurden als "Aufgabe danach" bezeichnet.

              Nun habe ich aber auch meine Zweifel gehabt, ob es für diese Ähnlichkeitsanfragen nicht gewisse Strukturen vorliegen sollten. So wie ich Dich verstanden habe, kommt man ggf. gar nicht daran vorbei, die Daten selber "anzupacken" und entsprechend anzupassen / aufzubereiten.

              Noch mal vielen vielen Dank für Deine Hilfe

              Julia

              1. Hallo Julia,

                So wie ich Dich verstanden habe, kommt man ggf. gar nicht daran vorbei, die Daten selber "anzupacken" und entsprechend anzupassen / aufzubereiten.

                Es wäre abstrakt denkbar, diese Aufbereitung zur Abfragezeit mit Hilfe einer View durchzuführen. Aber zum einen kann ich mir nicht vorstellen, wie das konkret aussehen sollte, und es dürfte auch eine ziemlich langsame Angelegenheit werden. Wenn Du mit deinem Prof verhandelst, kannst Du ja zur Sprache bringen, was er sich da genau vorstellt.

                Aber vielleicht sind die Daten ja auch schon in irgendeiner Weise normiert.

                Was mir noch einfiel: Stumpfes Vergleichen von Messwerten zum relativen Messzeitpunkt X könnte zu Problemen führen. Die Probanden führen ggf. eine komplexe Bewegung mit unterschiedlichem Rhythmus aus. Der eine macht den ersten Teil schneller, der andere vielleicht den zweiten. D.h. Du müsstest auch noch eine Rhythmusnormierung durchführen, was eine Art Kurvendiskussion bedeutet (finden von Maxima und Minima, so dass Du die übereinander legen kannst).

                Womöglich ist es an dieser Stelle sogar zielführender, nur noch das Kurvenverhalten zu betrachten (beginnt steigend, hat ein Maximum, ist fallend, hat einen Sattel, fällt weiter, steigt in Phase x stärker als es in Phase y fällt) - aber dann müsste man eine Art "Sprache" erfinden, die aus einem Bewegungsmuster ein Codewort macht (sXfSfNs = steigt, maX, fällt, sattel, fällt, miN, steigt) - keine Ahnung, nur eine Idee. Meine rudimentären Erinnerungen an theoretische Informatik melden sich da mit Chomsky-Typ-2 Grammatik - wenn's stimmt, wäre das ein fettes Kreuz auf dem Buzzword-Bingo Sheet deines Profs. Wenn nicht, eine fette 6 im Notenheft 😂

                Solche Codewörter kannst Du dann in der DB suchen, aber du kannst sie - denke ich - ganz schlecht in der DB erzeugen.

                Rolf

                --
                sumpsi - posui - clusi
  3. Hallo Julia,

    ich habe von diesem Thema leider keine Ahnung, aber vielleicht hilft dir ja die PostGIS-Erweiterung?

    LG,
    CK

    1. Hallo Julia,

      ich habe von diesem Thema leider keine Ahnung, aber vielleicht hilft dir ja die PostGIS-Erweiterung?

      Dto. in MariaDB. MySQL kann es auch. Ob es weitere gibt mögen andere wissen.

      1. Hallo Christian, hallo ursus,

        vielen Dank für eure Anworten und für eure Hinweise bezüglich PostGIS bzw. GIS-Features in MySQL.

        Ich werde mir die Möglichkeiten darin auf jeden Fall anschauen.

        Bei der Aufgabenstellung geht es um ein mögliches Thema für eine Arbeit. Ich bin noch am überlegen, ob dieses Thema für mich (als Einsteiger in diese Thematik) nicht eine Nummer zu groß ist.

        Viele Grüße

        Julia

        1. mögliches Thema für eine Arbeit

          Was denn für eine "Arbeit"? Ich kann mir vorstellen, dass die von Dir nur grob umrissende Aufgabe auch in einem universitären Umfeld nicht etwa ein Thema für eine Einzelperson, sondern eher für eine jahrelang fortgesetzte kollektive Forschung, z.b. von Doktoranden, ist. "Ähnliche Bewegungen" klingt stark nach Statistik in 4D, also 3D + Zeit und für einem unendlich großen Definitionsaufwand. Nicht dass am Ende der "deutsche Gruß" als "Winken zum Abschied" und das "Eintreten auf einen am Boden liegenden" als "Vergeblicher Versuch des Übersteigen eines Hindernisses", gedeutet wird - oder gar anders herum - und sodann mit dem automatisch ausgelösten Auftritt von 4 bis 8 Vogonen verknüpft ist…

          1. Hallo ursus,

            da muss ich mich bei Dir bedanken!

            Ich hatte selber schon so eine leise Vorahnung, dass das Ganze viel zu kompliziert für mich werden könnte. Aber da ich, wie gesagt, in diesem Bereich ganz "grün" bin, konnte ich das schlecht beurteilen.

            Wenn ich Dich richtig verstanden habe, bist Du also der Meinung, dass diese Thematik für eine Bachelorarbeit für eine Einzelperson mit dem oben erwähnten Vorwissen zu kompliziert ist? 😉

            Noch mal vielen Dank und viele Grüße

            Julia

            1. Hallo Julia,

              Wenn ich Dich richtig verstanden habe, bist Du also der Meinung, dass diese Thematik für eine Bachelorarbeit für eine Einzelperson mit dem oben erwähnten Vorwissen zu kompliziert ist? 😉

              In welchem Fach denn?

              Bis demnächst
              Matthias

              --
              Pantoffeltierchen haben keine Hobbys.
              ¯\_(ツ)_/¯
              1. Hallo Matthias,

                in Informatik.

                Viele Grüße

                Julia

            2. Wenn ich Dich richtig verstanden habe, bist Du also der Meinung, dass diese Thematik für eine Bachelorarbeit für eine Einzelperson mit dem oben erwähnten Vorwissen zu kompliziert ist?

              Wenn ich Dich richtig verstanden habe, bist Du der Meinung, dass ein Erklärbär, der selbst vor 34 Jahren im Mathe-Abitur eine 3 hatte (weil er den Mathe-Unterricht, der immer Montags in einer Doppelstunde ab 16:30 stattfand, schlicht verschlafen hat) ohne Kenntnis der konkreten Aufgabenstellung (und der Frage, ob der Infornatik-Bachelor an einer Uni, einer sonstigen Hochschule oder Berufsakademie erreicht werden soll) eine verwertbare Aussage treffen kann?

              Das wäre ganz schön sportlich.

              1. Hallo ursus,

                nein, dann habe ich Dich wohl falsch verstanden.

                Trotzdem danke für die Hilfe!

                Viele Grüße

                Julia

                1. Ich kann Dir (wie jeder andere hier) nur Anhaltspunkte liefern. Der wichtigste wäre: Traust Du Dir das zu? hast Du irgendeine Affinität zu dem Thema oder bist Du womöglich sogar "negativ interessiert"? Hast Du gar Angst vor dem Thema? Dann wäre es besser, das nicht zu machen und sich nach Alternativen umzuschauen.

            3. Aloha ;)

              Wenn ich Dich richtig verstanden habe, bist Du also der Meinung, dass diese Thematik für eine Bachelorarbeit für eine Einzelperson mit dem oben erwähnten Vorwissen zu kompliziert ist? 😉

              Ich habe selbigen Bachelor seit kurzem. Meine Bachelorarbeit war sicher keine der aufwändigsten, die man sich vorstellen kann (Gott sei Dank - berufsbegleitend und mit Familie wäre das anders auch nicht machbar gewesen), und trotzdem: genug Arbeit für die damit verbundenen Leistungspunkte (20 an der Uni in Ulm) hat dringesteckt.

              Trotzdem war der Aufwand, verglichen mit dem, was du da umrissen hast, deutlich geringer.

              Das bedeutet nicht, dass ich das Thema direkt ausschließen würde. Es bedeutet aber, dass das Thema auf jeden Fall entweder sachlich stark eingeschränkt werden muss (z.B.: nur eine bestimmte Bewegung erkennen o.ä.) – oder es muss von Anfang an klar vereinbart werden, dass das Ziel deiner Arbeit nicht sein kann, endgültige Aussagen zur Machbarkeit zu erreichen, sondern, dass du in deiner Arbeit nur verschiedene Ansätze auf grundsätzliche Machbarkeit untersuchen kannst, um damit die Grundlage für eine weitere Beschäftigung mit der Thematik zu liefern.

              Zum Vergleich: Ich habe im Rahmen meiner Bachelorarbeit eine Angular-Komponente entworfen, die bei unkomplizierter Einbindung in der Lage sein sollte, bestehende Angular-Anwendungen zu internationalisieren (d.h. Übersetzungen anbieten, in Fließtext einfügen und selbige managen) und ich war da, obwohl die Fragestellung weniger Fallstricke hatte, in der zur Verfügung stehenden Zeit auch nur in der Lage, Kernfunktionalitäten zu implementieren; für viele Komfortfunktionen, über die ich zuvor mit meinem Betreuer gesprochen hatte, war schlicht zu wenig Zeit zur Realisierung, da blieb es dann halt bei einer Demonstration der grundsätzlichen Machbarkeit.

              Grüße,

              RIDER

              --
              Camping_RIDER a.k.a. Riders Flame a.k.a. Janosch Zoller
              # Twitter # Steam # YouTube # Self-Wiki # Selfcode: sh:) fo:) ch:| rl:) br:^ n4:? ie:% mo:| va:) js:) de:> zu:} fl:( ss:) ls:[
              1. Hallo RIDER,

                vielen Dank für Deine Antwort!

                Ich habe selbigen Bachelor seit kurzem.

                Dann bist Du ja schon einen Schritt weiter als ich, gratuliere nachträglich!😉

                Trotzdem war der Aufwand, verglichen mit dem, was du da umrissen hast, deutlich geringer.

                Das ist sehr wichtig für mich zu wissen. Ich habe ja erstmal keinen Vergleich und keine richtige Vorstellung, wie viel Aufwand eine Bachelorarbeit (bei uns nur 14 LP) sein "darf".

                Das bedeutet nicht, dass ich das Thema direkt ausschließen würde. Es bedeutet aber, dass das Thema auf jeden Fall entweder sachlich stark eingeschränkt werden muss (z.B.: nur eine bestimmte Bewegung erkennen o.ä.) – oder es muss von Anfang an klar vereinbart werden, dass das Ziel deiner Arbeit nicht sein kann, endgültige Aussagen zur Machbarkeit zu erreichen, sondern, dass du in deiner Arbeit nur verschiedene Ansätze auf grundsätzliche Machbarkeit untersuchen kannst, um damit die Grundlage für eine weitere Beschäftigung mit der Thematik zu liefern.

                Das werde ich beim nächsten Treffen mit dem Professor auf jeden Fall besprechen / darüber diskutieren, wie man das Ganze im Rahmen einer Bachelorarbeit eingrenzen könnte / sollte.

                Noch mal vielen vielen Dank für Deine Hilfe

                Julia