Nicht metrische paarweise Ähnlichkeitsdaten

In intelligenter Datenanalyse gibt es zwei gängige Datenrepräsentationen, nämlich die vektorielle Repräsentation und die paarweise Repräsentation. Die Übersetzung der letzteren in die erstgenannte nennt man Einbettung, eine nicht triviale Problematik von stetem, wissenschaftlichen Interesse. Während die paarweise Repräsentation den Daten weniger Einschränkungen auferlegt und so potentiell fähig ist, reichere Struktur festzuhalten, wartet die vektorielle Repräsentation mit vielen mächtigen datenanalytische Werkzeugen auf, da man in solchen Räumen über probabilistische Modelle für die Daten verfügt. Paarweise Daten, die restriktive Bedingungen erfüllen, können getreu in eine vektorielle Repräsentation abgebildet werden. Paarweise Daten, für die dies nicht möglich ist, werden nicht metrisch genannt. Diese Doktorarbeit betrifft nicht-metrische, paarweise Daten. Es ist eine investigative und explorative Studie nicht metrischer, paarweiser Daten, gestützt auf theoretische und konzeptuelle, sowie auf empirische Betrachtungen. Zuerst wird der Leser mit den beiden Datenrepräsentationen vertraut gemacht. Paarweise Daten werden illustriert und die ersten Problematiken angesprochen. Gängige Einbettungsmethoden werden dargestellt. Dann wird gezeigt, dass diese beiden Datenrepräsentationen für eine gewisse Klasse von Lernalgorithmen übereinstimmen, sogar wenn die paarweisen Daten nicht metrisch sind, und traditionelle Techniken nur zu approximativen Vektorrepräsentation führen. Die neuentwickelte Einbettung ist exakt in Bezug auf Struktur. Das Hauptgewicht liegt im Erfassen der Natur und der Folgen von metrischen Verletzungen. Obwohl die wissenschaftliche Gemeinschaft die Problematik wahrzuhaben scheint, wurde diese nach des Autors bestem Wissen nie klar formuliert. Metrische Verletzungen wurden gemeinhin als zufälliges Nebenprodukt von Rauschen betrachtet und wurden mathematisch dementsprechend behandelt. Eine einfache Modellierung metrischer Verletzungen zeigt, dass diese Annahme falsch ist. Eine spezielle Einbettung wird benutzt um den Informationsgehalt metrischer Störungen zu visualisieren und interpretieren. Schliesslich wird gezeigt, dass ein einfacher Algorithmus, der die Struktur über einen Stabilitätsindex auswertet, effizient die Struktur, die von metrischen Verletzungen kodiert wird, extrahieren kann.There are two common data representations in intelligent data analysis, namely the vectorial representation and the pairwise representation. The translation of latter into the former is called embedding. This is a non-trivial issue of ongoing scientific interest. While the pairwise representation imposes less restriction on the data and is thus potentially able to capture richer structure, the vectorial representation has the advantage to offer many powerful data analytical tools, in particular as a consequence of the existence of probabilistic data models in such spaces. Pairwise data satisfying restrictive conditions can be faithfully translated into a vectorial representation. Pairwise data, for which this is not possible are called non-metric pairwise data. This thesis is about non-metric pairwise data. It is an investigative and explorative study of non-metric pairwise data, based on theoretical and conceptual as well as empirical considerations. The reader is first made familiar with the two data representations. Pairwise data are illustrated and first issues raised. Common embedding strategies are developed. It is then shown that these two data representations coincide for a certain class of learning algorithms, even when the pairwise data is non-metric and traditional techniques only obtain approximate vector representations. The new embedding developed is exact with respect to structure. The major focus lies on apprehending the nature and consequences of metric violations. While the scientific community seems aware of such an issue, it has never been clearly formulated to the best of the authors knowledge. Metric violations have commonly been considered an accidental byproduct of noise and have received corresponding mathematical treatment. It is shown by simple modeling of metric violations that this assumption is wrong. A particular embedding method is used to visualize and interpret the information coded by metric violations. Finally the structure coded by metric violations is shown to be efficiently extracted by a simple algorithm which evaluates structure based on a stability index