DE10034694B4

DE10034694B4 - Verfahren zum Vergleichen von Suchprofilen sowie dessen Verwendung

Info

Publication number: DE10034694B4
Application number: DE10034694A
Authority: DE
Inventors: Daniel Veit
Original assignee: Siemens Corp
Current assignee: Siemens Corp
Priority date: 2000-07-17
Filing date: 2000-07-17
Publication date: 2005-06-09
Anticipated expiration: 2020-07-18
Also published as: WO2002006974A3; EP1301872A2; WO2002006974A2; JP4868484B2; JP2004515837A; US7831602B2; DE10034694A1; CN1304991C; CN1455902A; US20040030680A1

Abstract

Verfahren zum Vergleichen eines ersten Suchprofils mit mindestens einem zweiten Suchprofil, wobei die Suchprofile jeweils mehrere Datenfelder aufweisen, dadurch gekennzeichnet, dass die Datenfelder des ersten Suchprofils und des zweiten Suchprofils jeweils zumindest zwei Datenfelder mit einem unterschiedlichen Typ umfassen, welcher bei dem jeweiligen Datenfeld des ersten und des zweiten Suchprofilvektors gleich ist, bei welchem Verfahren beim Vergleichen des ersten Suchprofils mit dem zweiten Suchprofil die zumindest zwei unterschiedlichen Typen von Datenfeldern mit unterschiedlichen Vergleichsfunktionen verglichen werden.

Description

Die Erfindung betrifft ein Verfahren zum Vergleichen von zwei Suchprofilen der im Oberbegriff des Patentanspruchs 1 angegebenen Art sowie dessen Verwendung.

Verfahren zum automatischen Vergleichen und Bewerten von Suchprofilen werden beispielsweise in Suchmaschinen im Internet verwendet, um die einzelnen von den Suchmaschinen untersuchten möglichen Ergebnisse auf ihre Relevanz bezüglich der eingegebenen Suchbegriffe zu bewerten und gegebenenfalls als relevantes Ergebnis anzuzeigen. Werden mehrere Ergebnisse ermittelt, so werden diese mit abnehmender Relevanz sortiert und dem Benutzer in der entsprechenden Reihenfolge dargestellt.

Aus der Veröffentlichung von D. Kuokka und L. Harada, Integrating Information vie Matchmaking, Journal of Intelligent Information Systems (JIIS) 6(2/3), Seiten 261-279, 1996 ist ein Verfahren zum automatischen Vergleichen und Bewerten von Informationen bekannt, das als COINS (COmmon INterest Seeker) bezeichnet wird. Mit diesem Verfahren können Freitexte verglichen werden, das sind Textausschnitte mit beliebiger Wortfolge. Die Freitexte werden bei diesem Verfahren in Dokumentvektoren gewandelt und diese Dokumentvektoren werden bei einer Suche verglichen und bewertet. Hierzu wird ein inverser Algorithmus der Dokumenthäufigkeit (term frequency – invers document frequency algorithm) angewandt.

Die Veröffentlichung K. Sycara, J. Lu, M. Klusch und S. Widoff, Dynamic Service Matchmaking among Agents in Open Information Environments, Journal ACM SIGMOND Record, Special Issue on Semantic Interoperability in Global Information Systems, A. Ouksel, A. Sheth (Eds.), 1999, und K. Sycara, J. Lu, M. Klusch Interoperability among Heterogenous Software Agents on the Internet, CMU-RJ-TR-98-22, The Robotics Institute Carnegie Mellon University, Pittsburgh, Okt. 1998 betreffen eine Computersprache, die es erlaubt ein Verfahren zum automatischen Vergleichen und Bewerten von Informationen mittels heterogener Agentensysteme in einer offenen Umgebung, wie dem Internet auszuführen. Eine offene Umgebung bedeutet, dass sich nicht alle Agenten kennen müssen. Diese Sprache wird als Larks (languege for Advertisement and Request for Knowledge Sharing) bezeichnet. Bei Larks wird der Vergleichsvorgang in folgende fünf Einzelschritte unterteilt:

1. Bei einem Kontextvergleich werden diejenigen angebotenen Informationseinheiten einer Datenbank mit der Anfrage im gleichen oder ähnlichen Kontext verglichen.
2. Bei einem Syntaxvergleich wird die Anfrage mit den durch den Kontextvergleich ausgewählten Informationseinheiten in drei Teilschritten verglichen:
2.1. Das Suchprofil und die angebotenen Informationseinheiten werden mit einem speziellen Gewichtungsverfahren (term frequency-invers document frequency weighting) verglichen.
2.2. Bei einem Ähnlichkeitsvergleich werden die Anzahl und die Deklaration der Eingabe- und Ausgabevariablen sowie der Eingabe- und Ausgabefunktionen verglichen.
2.3. Bei einem Signaturvergleich werden die Variablentypen der Eingabe- und Ausgabevariablen verglichen.
3. Bei einem semantischen Vergleich wird geprüft, ob die Eingabe- und Ausgabefunktionen eines aus einer Suchanfrage und einem Informationsangebot bestehenden Paar verglichen.

Mit diesem bekannten Verfahren wird versucht, eine möglichst gute Bewertung zu erzielen, das heißt eine Bewertung, die der Bewertung durch einen Menschen möglichst ähnlich ist. Hierzu werden bei einzelnen Bewertungsschritten unterschiedliche Schwerpunkte gesetzt. Die einzelnen Bewertungsschritte werden jeweils sequentiell ausgeführt, wobei jeweils die gesamte Information der Suchanfrage und die gesamte Information einer der angebotenen Informationseinheiten bei jedem Schritt separat ausgewertet werden.

Weiterhin sind sogenannte Multi-Matchmaker bekannt, das sind Verfahren, die mehrere separate Verfahren zum automatischen Vergleichen und Bewerten von Informationen ausführen können und die jeweiligen Ergebnisse zu einem Gesamtergebnis mitteln. Derartige Multi-Matchmaker arbeiten grundsätzlich wie die herkömmlichen Verfahren zum Vergleichen und Bewerten von Informationen. Lediglich wenn eine vorbestimmte Suchanfrage nicht im erforderlichen Zeitrahmen bewältigt werden kann, werden weitere ähnliche Verfahren zum Vergleichen und Bewerten von Informationen aufgerufen, die einen Teil des Vergleichs- und Bewertungsvorganges übernehmen. Hierdurch können auch aufwendige Suchanfragen zügig abgearbeitet werden.

Aus der Veröffentlichung EP 0 674 282 A2 ist ein Verfahren bekannt, welches es erlaubt, auf PCs in einem Netzwerk Profile zu speichern und die Profile anderer PCs zu durchsuchen.

Aus der WO 99/10819 A1 ist ein Verfahren zur Darstellung der Relevanz elektronischer Dokumente in Bezug auf benutzerspezifische Suchprofile bekannt. Dokumente und Suchprofile werden dabei als Vektoren aufgefasst.

Aus der US 5 794 227 A ist ein Verfahren zur Optimierung der Reihenfolge, in welcher Vergleiche der Komponenten eines boolschen Abfrage-Ausdrucks auf einen Datenbankeintrag angewendet werden, bekannt.

Der Erfindung liegt die Aufgabe zugrunde ein Verfahren zum automatischen Vergleichen und Bewerten von Informationen (Suchprofilen) zu schaffen, mit dem eine Bewertung möglich ist, die der Bewertung durch einen Menschen sehr ähnlich ist und mit geringem Rechenaufwand erzielt wird.

Die Aufgabe wird durch ein Verfahren zum Vergleichen von Suchprofilen mit den Merkmalen gemäß dem Patentanspruch gelöst.

Bei einem Verfahren zum Vergleichen eines ersten Suchprofils mit mindestens einem zweiten Suchprofil, wobei die Suchprofile jeweils mehrere Datenfelder aufweisen und die Datenfelder des ersten Suchprofils und des zweiten Suchprofils jeweils zumindest zwei Datenfelder mit einem unterschiedlichen Typ umfassen, welcher bei dem jeweiligen Datenfeld des ersten und des zweiten Suchprofilvektors gleich ist, werden beim Vergleichen des ersten Suchprofils mit dem zweiten Suchprofil die zumindest zwei unterschiedlichen Typen von Datenfeldern mit unterschiedlichen Vergleichsfunktionen verglichen.

Vorteilhafte Ausgestaltungen der Erfindung sind in den Unteransprüchen angegeben.

In einer Weiterbildung ist das erste oder das zweite Suchprofil ein in einer Datenbank abgespeichertes Angebotsprofil. Der jeweilige Vergleich der Datenfelder wird mit einem vorläufigen Vergleichswert bewertet. Aus den vorläufigen Vergleichswerten wird ein endgültiger Vergleichswert berechnet.

Die Weiterbildung vergleicht somit in einzelne Datenfelder strukturierte Profile. Mit der Erfindung werden für die unterschiedlichen Typen von Datenfeldern unterschiedliche Vergleichsfunktionen angewandt, mit welchen vorläufige Vergleichswerte berechnet werden. Hierdurch können die Inhalte der einzelnen Datenfelder typspezifisch verglichen und bewertet werden. Aus den vorläufigen Vergleichswerten wird ein endgültiger Vergleichswert berechnet.

Mit der Weiterbildung werden somit die einzelnen Datenfelder typspezifisch verglichen und die Ergebnisse der Einzelvergleiche, das heißt, die vorläufigen Vergleichswerte, zu einem endgültigen Vergleichswert zusammengefasst.

Mit dem erfindungsgemäßen Verfahren wird der Vergleich der einzelnen Datenfelder typspezifisch durchgeführt, wodurch wesentlich realistischere Ergebnisse als bei den bisher bekann ten Verfahren erzielt werden. Da jeweils mit den einzelnen Vergleichsfunktionen nur bestimmte Datenfelder verarbeitet werden, und nicht immer der gesamte Datenumfang eines Profils verarbeitet werden muss, sind die einzelnen Vergleichsfunktionen einfach zu erstellen und durch einen kurzen Programmabschnitt realisierbar. Hierdurch wird die Implementation des erfindungsgemäßen Verfahrens für eine bestimmte Anwendung wesentlich vereinfacht und zudem ist das erfindungsgemäße Verfahren schnell ausführbar, da die einzelnen kurzen Programmabschnitte nur spezifische, zum Vergleich notwendige Aufgaben bearbeiten.

Nach einer bevorzugten Ausführungsform der Erfindung sind ein oder mehrere komplexe Datenfelder vorgesehen, die sich jeweils auf mehrere Datenfelder beziehen. Sind diese weiteren Datenfelder wiederum komplexe Datenfelder, so beziehen die sich wiederum auf mehrere Datenfelder. Am Ende einer solchen Kette sind Basisdatenfelder angeordnet, in welchen die Informationen der Profile abgespeichert sind. Die Datenfelder sind in unterschiedlichen Ebenen angeordnet, wobei ein komplexes Datenfeld, das sich auf mehrere weitere Datenfelder bezieht in der jeweils übergeordneten Ebene zu den Datenfeldern angeordnet ist, auf welche sie sich bezieht.

Nach einer bevorzugten Ausführungsform der Erfindung werden zum Vergleichen von Freitexte enthaltenden Datenfeldern Dokumentvektoren erstellt, wobei die einzelnen Elemente der Vektoren Gewichtungsfaktoren sind, die die Relevanz der Elemente beschreiben, und als vorläufiger Vergleichswert ein euklidischer Abstand zwischen den beiden Dokumentvektoren berechnet wird. Die Berechnung eines euklidischen Abstandes genügt der Anforderung an eine metrische Distanzfunktion, nämlich dass zwei identische Vektoren den Abstand 0 besitzen und dass der Abstand von einem ersten zu einem zweiten Vektor identisch zum Abstand vom zweiten zum ersten Vektor ist, und dass der Abstand zwischen einem ersten und einem dritten Vektor kleiner oder gleich dem Abstand zwischen dem ersten und einem zweiten Vektor zuzüglich des Abstandes zwischen dem zweiten und dem dritten Vektor ist.

Das erfindungsgemäße Verfahren kann sehr vorteilhaft in ein Agentensystem integriert werden. Dieses Agentensystem umfasst zumindest drei Typen von Agenten, nämlich einen Suchagenten, einen Angebotsagenten und einen Vergleichsagenten, der nach einer Aufforderung durch den Suchagenten die in den Suchagenten und Angebotsagenten gespeicherten Profile vergleicht und bewertet. Vorzugsweise ist das Agentensystem ein offenes Agentensystem, das heißt, dass weitere Agenten, insbesondere Angebotsagenten hinzugefügt werden können. Die Agenten sind vorzugsweise mobile Agenten, das heißt, dass sie in einem Computernetzwerk an verschiedenen Plätzen aktiv sein können und den Ort im Computernetzwerk verändern können.

Die Erfindung wird nachfolgend anhand der in den Zeichnungen dargestellten Ausführungsbeispielen näher erläutert. In denen zeigen:
1 eine Tabelle, die unterschiedliche Basisdatenfelder zeigt,
2 eine Profilbeschreibung in Tabellenform,
3 eine Profilstruktur in einem Blockschaltbild,
4 das Verfahren zum automatischen Vergleichen und Bewerten von Informationen in einem Flussdiagramm,
5a zwei zu vergleichende Freitexte,
5b zwei Datensätze, die von den in 4a gezeigten Freitexten abgeleitet sind,
5c Bewertungsergebnisse für die einzelnen Wörter der Datensätze in Tabellenform,
6 ein Beispiel für eine Angebotsbeschreibung für eine Kooperationsbörse,
7 ein Agentensystem in einem Blockschaltbild, und
8 ein Netzwerk zum Verbinden von Computern, auf dem das Agentensystem aus 6 installiert ist in einem Blockschaltbild.
Beim erfindungsgemäßen Verfahren zum automatischen Vergleichen und Bewerten von Informationen wird ein Suchprofil mit einem in einer Datenbank abgespeicherten Angebotsprofil verglichen. 2 zeigt eine Profilbeschreibung eines Ausführungsbeispieles der Erfindung. Diese Profilbeschreibung umfasst acht Datenfelder, von welchen in 2 in der linken Spalte die Bezeichnung des jeweiligen Datenfeldes, in der mittleren Spalte das Variablenzeichen des Datenfeldes und in der rechten Spalte eine Kurzbeschreibung des Datenfeldes angegeben ist.
Grundsätzlich unterscheidet man bei einem automatischen Vergleichsverfahren zwischen einem Angebotsprofil und einem Suchprofil. Die Profilbeschreibung des Angebotsprofils und des Suchprofils stimmen im Aufbau überein. Sie unterscheiden sich lediglich durch den Inhalt ihres Datenfeldes Profiltyp, in dem die Angabe, ob es sich um ein Angebotsprofil bzw. um ein Suchprofil handelt, gespeichert ist. Das Datenfeld Profiltyp t ist ein boolsches Datenfeld, dessen Inhalt entweder 0 oder 1 sein kann. Die weiteren Datenfelder sind der Titel, die Schlüsselwörter, die genaue Beschreibung, die Kosten, Datumsangaben, Dauer und die Teilnehmer. Das Datenfeld Titel enthält eine Kurzbeschreibung der angebotenen bzw. gesuchten Leistung in Form eines sogenannten Verb-Substantiv-Ausdruck. Die Verwendung derartiger Verb-Substantiv-Ausdrücke ist aus V.S. Subrahmanian (Herausgeber), Piero Bonatti, Jürgen Dix, Thomas Eiter, „Heterogeneous Active Agents", Cit Press; ISBN: 0262194368 bekannt. Das Datenfeld Schlüsselwörter enthält einen Satz von Schlüsselwörtern. Im Sinne der vorliegenden Beschreibung ist ein Satz eine ungeordnete Sammlung von Elementen des gleichen Typs, wie z.B. Wörter, reelle Zahlen, ganze Zahlen oder dergleichen. Die Variable eines Satzes wird zwischen zwei geschweiften Klammern dargestellt.
Das Datenfeld genaue Beschreibung umfasst einen Freitext, in dem in angebotene bzw. gesuchte Leistung beschrieben ist.
Das Datenfeld Kosten beinhaltet eine Angabe über die minimal oder maximal zu erwartenden Kosten. Das Datenfeld Kosten stellt somit ein Intervall dar.
Im Datenfeld Dauer ist die Zeitdauer angegeben, die gebraucht wird, um die angebotene Leistung auszuführen.
Das Datenfeld Teilnehmer enthält eine Liste der Namen derjenigen Teilnehmer, die die Leistung anbieten bzw. anbieten sollen. Eine Liste wird in der durch ein hochgestelltes Pluszeichen dargestellt. Der Klammerausdruck [1:2] bedeutet, dass jedes Listenelement aus zwei Einzelelementen zusammengesetzt ist, nämlich dem Vor- und dem Nachnamen. Das Datenfeld τ₈ [1:2]⁺ und das Datenfeld (τ₁) sind komplexe Variablen, die unten näher erläutert werden.
In 3 ist die Struktur der Profilbeschreibung aus 2 gezeigt. Die Profilbeschreibung ist in drei Ebenen unterteilt (Ebene 0, Ebene 1 und Ebene 2). Die Ebene 2 ist die höchste Ebene, in der die in 2 gezeigten Datenfelder angeordnet sind. Die komplexen Datenfelder τ₁ und τ₈[1:2]⁺ beziehen sich jeweils auf weitere Datenfelder, die durch entsprechende Variablen in der darunterliegenden Ebene dargestellt sind. So sind in der Ebene mehrere Datenfelder τ₁ angeordnet, in welchen jeweils ein Schlüsselwort abgespeichert ist. Die komplexe Variable τ₁ bezieht sich somit auf die in der Ebene 1 abgespeicherte Liste von Schlüsselwörtern. Das komplexe Daten feld τ₈[1:2]⁺ der Teilnehmer bezieht sich auf eine Liste von weiteren Datenfeldern. Die Elemente dieser Liste sind Feldanordnungen [1:2], die jeweils zwei Namen, den Vor- und Nachnamen, umfassen. Grundsätzlich umfasst eine Feldanordnung eine bestimmte Anzahl von Elementen des gleichen Typs. Die Feldanordnungen τ₈[1:2] beziehen sich somit auf weitere Datenfelder, die in der Ebene 0 angeordnet sind und jeweils einen Einworteintrag aufweisen, nämlich den Vornamen oder den Nachnamen. Zwei derartige Datenfelder τ₈ sind jeweils zu einer derartigen Feldanordnung zusammengefasst.
Die Datenfelder, die sich auf weitere Datenfelder in einer untergeordneten Ebene beziehen werden als komplexe Datenfelder bezeichnet. Die übrigen Datenfelder sind Basisdatenfelder.
In den Basisdatenfeldern sind die Informationen des jeweiligen Profils gespeichert. Über die komplexen Datenfelder werden mehrere Basisdatenfelder in Form von Sätzen, Listen, Feldanordnungen oder Registern (Record) auf eine einzige Feldanordnung in der höchsten Ebene projiziert. Register sind ähnlich wie Feldanordnungen aus aufeinanderfolgenden Elementen einer vorbestimmten Anzahl ausgebildet, die wiederum aus unterschiedlichen Typen bestehen können.
Durch die oben beschriebene Baumstruktur mittels der sich von einer übergeordneten Ebene zu einer untergeordneten Ebene verzweigenden komplexen Datenfeldern wird in der obersten Ebene (hier: Ebene 2) für jede begriffliche Einheit lediglich ein einziges Datenfeld vorgesehen.
In 1 ist eine Liste der Basisdatenfelder angegeben. In Spalte 1 sind die Variablennamen der Basisdatenfelder τ₁ bis τ₈ angebeben. In der mittleren Spalte sind die Namen der entsprechenden Basisdatenfelder enthalten und in der rechten Spalte ist eine kurze Beschreibung des Inhalts angegeben.
Das vorliegende Ausführungsbeispiel ist für einen Vergleich von Sprachelementen der englischen Sprache ausgeführt. Deshalb sind die Schlüsselwörter τ₁ Substantive der englischen Sprache. Die Verb-Substantiv-Ausdrücke τ₂ sind Ausdrücke, die aus einem Verb und zumindest einem Substantiv zusammengesetzt sind. Ein Freitext τ₃ besteht aus einer beliebigen Kombination von Wörtern, Buchstaben und Zahlen. Eine Zahl τ₄ ist entweder eine ganze Zahl (Integer) oder eine reelle Zahl. Ein Intervall τ₅ ist eine Feldanordnung vom Typ V₁, V₂, wobei V₁ und V₂ die Grenzen des Intervalls in Form von ganzen Zahlen oder reellen Zahlen sind. Ein Datumsintervall τ₆ ist eine Feldanordnung, die zwei Datumsangeben D.M.Y aufweist, die jeweils die Datumsgrenze der Feldanordnung darstellt. Eine Zeit τ₇ ist eine Feldanordnung mit den Angaben Y:D:H:M:S:M_s, wobei Y das Jahr, D der Tag, H die Stunde, M die Minute, S die Sekunde und M_s eine 1/100-Sekunde sind. Ein Name τ₈ ist ein beliebiger geeigneter Name einer Person.
4 zeigt schematisch den Ablauf des erfindungsgemäßen Verfahrens für die in 3 gezeigte Profilstruktur.
Das Verfahren beginnt mit dem Schritt S1. Im Schritt S2 werden die Datenfelder Teilnehmer mittels einer Namensvergleichsfunktion verglichen. Stimmen zwei Namen, das heißt zwei aus einem Vor- und Nachnamen zusammengesetzte Feldanordnungen überein, so ergibt die Namensvergleichsfunktion, die als vorläufiger Vergleichswert einen Abstand berechnet, den Abstand 0. Stimmen die zu vergleichenden Namen nicht überein, so ergibt die Namensvergleichsfunktion als vorläufigen Vergleichswert den Abstand 1. Bei dem Vergleich der Datenfelder Teilnehmer im Schritt S2 wird jeweils eine Feldanordnung des Suchprofils mit allen entsprechenden Feldanordnungen des Angebotsprofils verglichen. Dieser Vergleich erfolgt somit zwischen den Feldanordnungen der Ebene 0. Stimmt eine Feldanordnung des Suchprofils mit einer der Feldanordnungen des Angebotsprofils überein, so wird in der Ebene 1 des Suchprofils, in das der gefundenen Feldanordnung zugeordnete Datenfeld τ₈[1:2] als vorläufiger Vergleichswert der Wert 0 eingetragen. Konnte diese Feldanordnung (= Vor- und Nachnamen) nicht gefunden werden, so wird in das entsprechende Datenfeld in der Ebene 1 der Wert 1 eingetragen. Nach Abschluss des Schrittes S2 sind alle Datenfelder τ₈[1:2] mit einem vorläufigen Vergleichswert versehen.
Im Schritt S3 werden die vorläufigen Vergleichswerte, die den Namen zugeordnet sind, bewertet. Dies erfolgt in der Regel durch eine gewichtete Mittelwertbildung. Da die zu vergleichenden Elemente jeweils vom gleichen Typ sind, sind sie gleichwertig und werden deshalb alle mit 1 gewichtet. Es wird somit jeweils ein Mittelwert der in die komplexen Datenfeldern τ₈[1:2] eingetragenen Werte gebildet. Dieser Mittelwert ist ein vorläufiger Vergleichswert zweiter Ordnung, der in der Ebene 2 in dem komplexen Datenfeld der Namensliste t₈[1:2]⁺ eingetragen wird.
Im nachfolgenden Schritt S4 werden die die Schlüsselwörter beinhaltenden Datenfelder τ₁ des Suchprofils mit den entsprechenden Datenfeldern des Angebotsprofils verglichen. Die Vergleichsfunktion zum Vergleichen der Schlüsselwörter ist derart ausgebildet, dass jedes Schlüsselwort des Suchprofils mit jedem Schlüsselwort des Angebotsprofils verglichen wird und falls ein Schlüsselwort des Suchprofils nicht unter den Schlüsselwörtern des Angebotprofils enthalten ist, der Wert 1 gespeichert wird. Ansonsten wird der Wert 1 gespeichert. Als vorläufiger Vergleichswert wird der Mittelwert dieser Werte berechnet und in das Datenfeld der Liste der Schlüsselwörter {τ₁} eingetragen.
Die Verfahrensschritte S3 und S4 werden in der Ebene 1 ausgeführt.
Im darauffolgenden Verfahrensschritt S5 werden die Inhalte der Datenfelder Titel τ₂, genaue Beschreibung τ₃, Kosten τ₅, Datumsangaben τ₆, und Dauer τ₇ miteinander verglichen.
Die Vergleichsfunktion zum Vergleichen der Titel τ₂ ist eine übliche Vergleichsfunktion zum Vergleichen von Verb-Substantiv-Ausdrücken.
Die Vergleichsfunktion zum Vergleichen des Datenfelds genaue Beschreibung τ₃ ist eine Vergleichsfunktion zum Vergleichen von Freitexten. 5a zeigt zwei Beispiele von Freitexten d₁, d₂, die jeweils einen Text in englischer Sprache umfassen. Diese Freitexte werden zunächst in Datensätze DS₁ und DS₂ transformiert, in welche alle Wörter aus den Freitexten übernommen werden, die keine Stopwörter sind. Stopwörter sind Wörter, die wenig Informationsgehalt besitzen. Es existieren Listen mit den üblichen Stopwörtern. Im vorliegenden Fall werden folgende Wörter als Stopwörter beurteilt:
this, is, in, a, the, and, off, can, be, are, with, we, for, to, an, able, wich, our, not, shout, already, make.
In den Datensätzen DS₁ und DS₂ sind hinter den einzelnen Wörtern jeweils ihre Häufigkeit in den entsprechenden Freitexten angegeben. Die einzelnen Wörter sind in den Datensätzen alphabetisch sortiert.
Zum Vergleichen der Freitexte müssen die Wörter der Datensätze mit Gewichtungsfaktoren versehen sein. Zur Berechnung der Gewichtungsfaktoren wird zunächst eine sogenannte inverse Dokumentenhäufigkeit idf_j berechnet, die folgendermaßen definiert ist:
wobei N die Gesamtzahl aller Dokumente und df_j die Anzahl der Dokumente ist, die das Wort j enthalten. Beim folgenden Ausführungsbeispiel stellt jeder Freitext ein Dokument dar. Insgesamt gibt es neben den in 5a gezeigten zwei Freitexten noch weitere 18 Freitexte weiterer 18 Angebotsprofile. Die Gesamtzahl der Dokumente N beträgt somit 20.
Mit der inversen Dokumenthäufigkeit werden diejenigen Wörter, die sehr häufig vorkommen, mit einem gegen 0 gehenden Wert gewichtet und die Wörter, die nur in wenigen Dokumenten vorkommen, mit einem gegen 1 gehenden Wert gewichtet. Hierdurch werden bei der inversen Dokumentenhäufigkeit idf_j seltene Wörter stärker als häufige Wörter gewichtet. Seltene Wörter haben in der Regel einen höheren Informationsgehalt als häufige Wörter.
Neben der inversen Dokumenthäufigkeit wird auch die Häufigkeit tf_i,j der Wörter j in den Dokumenten i berücksichtigt. Somit ergibt sich als Gewichtungsfaktor w_i,j das Produkt aus der Häufigkeit tf_i,j und der inversen Dokumenthäufigkeit idf_j (w_i,j = tf_i,j·idf_j).
Für die Wörter der in 5b gezeigten Datensätze ist deren inverse Dokumentenhäufigkeit df_j und sind die Gewichtungsfaktoren w_1,j und w_2,j in der Tabelle aus 5c aufgeführt.
Die Gewichtungsfaktoren w_1,j und w_2,j bilden jeweils Elemente von Dokumentenvektoren DV₁ und DV₂.
Beim Vergleichen zweier Freitexte wird der Abstand der korrespondierenden Dokumentenvektoren DV₁ und DV₂ berechnet. Erfindungsgemäß wird der Abstand zwischen den beiden Vektoren als euklidischer Abstand gemäß folgender Formel berechnet:
Die euklidische Norm erfüllt alle Voraussetzungen an einen metrischen Abstand:

– Der Abstand zwischen zwei identischen Vektoren ist 0.
– Der Abstand von einem ersten Vektor zu einem zweiten Vektor ist gleich dem Abstand vom zweiten Vektor zum ersten Vektor. Das heißt die Abstandsberechnung ist symmetrisch.
– Der Abstand von einem ersten Vektor zu einem dritten Vektor ist kleiner als die Summe der Abstände vom ersten Vektor zu einem zweiten Vektor und vom zweiten Vektor zum dritten Vektor.

Nur wenn die Abstandsberechnung diese Voraussetzung erfüllt, ist sichergestellt, dass immer ein sinnvoller Abstand ermittelt wird.
Anstelle der Berechnung des Abstandes zwischen den beiden Dokumentenvektoren mittels eines euklidischen Abstandes ist es auch möglich, wie es bei herkömmlichen Vergleichsverfahren ausführt wird, die Abstände der beiden Vektoren mittels des Cosinus zwischen den beiden Vektoren zu berechnen.
Die Vergleichsfunktion zum Vergleichen der die Kosten enthaltenden Datenfelder ist eine Vergleichsfunktion zum Vergleichen von Intervallen. Der Abstand zwischen zwei Intervallen i₁, i₂, die durch reelle Zahlen i₁ = [l₁, r₁] und i₂ = [l₂, r₂] angebeben sind, berechnet sind nach folgender Formel:
Zum Berechnen des Abstandes der Datenfelder Datumsangaben und Dauer werden an sich bekannte Vergleichsfunktionen verwendet.
Beim vorliegenden Ausführungsbeispiel werden keine Zahlen verglichen, weshalb auch keine entsprechende Vergleichsfunktion zum Vergleichen verwendet wird. Eine solche Vergleichsfunktion lässt sich beispielsweise sehr einfach durch Bestimmen des Absolutwertes der Differenz zwischen den zu vergleichenden Zahlen realisieren.
Die beim Vergleich der Datenfelder τ₂, τ₃, τ₅, τ₆ und τ₇ ermittelten vorläufigen Vergleichswerte werden abgespeichert. Hiermit ist der Schritt S5 abgeschlossen.
Im Schritt S6 werden die einzelnen vorläufigen Vergleichswerte zu den Datenfeldern τ₁ bis τ₈ der Ebene 2 zur Berechnung eines endgültigen Vergleichswertes verwendet. Hierbei wird eine gewichteter Mittelwert berechnet, wobei die einzelnen Datenfelder je nach ihrer Bedeutung unterschiedlich stark gewichtet sind. Das Ergebnis dieser gewichteten Mittelwertsbildung ist ein Abstandswert, der den Abstand zwischen den beiden zu vergleichenden Profilen, dem Suchprofil und dem Angebotsprofil, angibt.
Da in der Regel ein Ähnlichkeitswert und kein Abstandswert erwünscht ist, wird der Kehrwert des Abstandswertes gebildet (Schritt S7). Dieser Ähnlichkeitswert stellt den entgültigen Vergleichswert dar. Dieser Vergleichswert wird im Schritt S8 ausgegeben. Im Schritt S9 wird das Verfahren beendet.
Der entgültige Vergleichswert kann dazu verwendet werden, das entsprechende Angebotsprofil in einer Liste von Angebotsprofilen entsprechend der berechneten Ähnlichkeit zum Suchprofil zu sortieren.
Wird vom Benutzer beim initiieren eines Suchvorganges festgelegt, dass er die ähnlichsten Angebotsprofile wünscht, so wird für jedes Angebotsprofil das oben beschriebene erfindungsgemäße Verfahren durchgeführt, die einzelnen Angebotsprofile mit absteigender Ähnlichkeit bzgl. des Suchprofils sortiert und die ähnlichsten Angebotsprofile als Ergebnis an den Benutzer ausgegeben.
Das erfindungsgemäße Verfahren kann als Computerprogramm zum automatischen Vergleich von Profilen realisiert werden. Eine besonders vorteilhafte Realisierung des erfindungsgemäßen Verfahrens ist in Form eines Agentensystems.
Agenten sind autonome, kooperative Softwareeinheiten, die aus Code und Daten bestehen. Sie sind eigenständig funktionierende Softwareeinheiten, bei welchen keine ständige Interaktion mit dem Benutzer notwendig ist. Es gibt sowohl stationäre als auch mobile Agenten.
Mobile Agenten sind z.B. aus der US 5,603,031 bekannt. Mobile Agenten sind Programme, die an einem Computernetzwerk an verschiedenen Plätzen aktiv sein können und ihren Ort im Computernetzwerk verändern können.
In 7 ist schematisch der Ablauf des erfindungsgemäßen Verfahrens mittels dreier Agenten dargestellt. Hierbei wird ein Vergleichsagent, ein Suchagent und ein Angebotsagent verwendet. Der Vergleichsagent enthält eine Datenbank, in dem die ihm bekannten Angebotsagenten mit ihren jeweiligen Angebotsprofilen gespeichert sind. Die Angebotsagenten können sich in der entsprechenden Datenbank mit ihrem Angebotsprofil eintragen bzw. dieses Angebotsprofil wieder löschen, falls sie das entsprechende Angebot nicht mehr aufrecht erhalten.
Ein Suchagent, der eine bestimmte Leistung sucht, wendet sich an einen Vergleichsagenten und sendet an den Vergleichsagenten eine Suchanfrage. Die Suchanfrage enthält ein entsprechendes Suchprofil. Dieses Suchprofil vergleicht der Vergleichsagent mit den in seiner Datenbank gespeicherten Ange botsprofilen und bewertet sie gemäß dem oben beschriebenen Verfahren. Er übermittelt dem Suchagenten eine entsprechende Suchantwort, die eine Liste mit den Namen der relevanten Angebotsagenten enthält, wobei jeder Angebotsagent mit einem Vergleichswert bewertet ist.
Der Suchagent kann die Suchantwort entweder an seinen ursprünglichen Auftraggeber weiterleiten oder an den Angebotsagenten, dem der beste Vergleichswert zugeordnet ist, eine Anfrage um Lieferung der entsprechenden Leistung senden. Die Leistung kann dann von dem Angebotsagenten an den Suchagenten erbracht werden, der sie an seinen Auftraggeber weiterleitet.
8 zeigt schematisch vereinfacht ein Netzwerk, in dem ein derartiges Agentensystem realisiert ist. Das Netzwerk weist mehrere Computer 1 auf, die über Datenleitungen 2 miteinander verbunden sind. Auf den einzelnen Computern 1 ist jeweils ein Agentensystem AG installiert. Im Netzwerk befinden sich einige mobile Agenten AG-I bis AG-III, die entweder auf einem der Computer 1 angeordnet sind, bzw. sich von einem zu einem anderen Computer bewegen.
Jedes Agentensystem weist eine Agentenplattform auf, die Dienstprogramme umfasst, welche ein Agent benötigt, um an dem jeweiligen Computer 1 ausgeführt werden zu können.
Die Agenten AG-I sind Angebotsagenten und die Agenten AG-II sind Suchagenten. Der Agent AG-III ist ein Vergleichsagent. In dem Vergleichsagent AG-III sind die Angebotsprofile der Angebotsagenten AG-I gespeichert. Ein Suchagent AG-II kann an den Vergleichsagenten AG-III eine Suchanfrage stellen, die dieser mit einer entsprechenden Suchantwort beantwortet.
Die Suchagenten können dann die Suchantwort in der entsprechend vorbestimmten Art und Weise weiterbehandeln und insbesondere an denjenigen Benutzer, der einen Computer des Netzwerkes bedient, weiterleiten.
Das erfindungsgemäße Verfahren kann als Softwareprodukt realisiert werden, das in einem Netzwerk, beispielsweise in Form eines Vergleichsagenten abgespeichert ist. Das erfindungsgemäße Verfahren kann jedoch auch auf einem beliebigen elektronisch lesbaren Datenträger oder einem Halbleiterspeicher in einem Computer abgespeichert und in dem Computer zur Ausführung gebracht werden.
Die Erfindung wird oben anhand eines Ausführungsbeispieles näher erläutert. Sie ist jedoch nicht auf die konkrete Ausführungsform des Ausführungsbeispieles beschränkt. Wesentlich für die Erfindung ist, dass die einzelnen Profile durch unterschiedliche Typen von Datenfeldern strukturiert sind und dass für die unterschiedlichen Typen von Datenfeldern unterschiedliche Vergleichsfunktionen angewandt werden. Hierdurch erhält man eine multidimensionale Bewertung der zu vergleichenden Profile. Diese multidimensionale Bewertung der Profile ergibt eine sehr individuelle Bewertung, die sehr ähnlich der Bewertung durch einen Menschen ist. Im Rahmen der Erfindung ist es z.B. möglich, dass die Basisfelder mit anderen Inhalten als bei obiger Ausführungsform belegt sind. Es ist auch möglich, dass Profile unterschiedlicher Struktur verglichen werden, wobei eines der beiden Profile auf ein weiteres Profil abgebildet wird, dessen Struktur mit der des zu vergleichenden Profils übereinstimmt.
Durch diese zusätzliche Abbildung kann das erfindungsgemäße Verfahren wird der Einsatzbereich erheblich erweitert. Es kann z.B. zweckmäßig sein, ein relativ kleines Profil mit bspw. drei bis fünf unterschiedlichen Typen von Datenfeldern vorzusehen, auf das beliebige Informationseinheiten abgebildet werden. Diese Informationseinheiten werden dann mittels der ihnen zugeordneten strukturierten Profile verglichen.

Claims

Verfahren zum Vergleichen eines ersten Suchprofils mit mindestens einem zweiten Suchprofil, wobei die Suchprofile jeweils mehrere Datenfelder aufweisen, dadurch gekennzeichnet, dass die Datenfelder des ersten Suchprofils und des zweiten Suchprofils jeweils zumindest zwei Datenfelder mit einem unterschiedlichen Typ umfassen, welcher bei dem jeweiligen Datenfeld des ersten und des zweiten Suchprofilvektors gleich ist, bei welchem Verfahren beim Vergleichen des ersten Suchprofils mit dem zweiten Suchprofil die zumindest zwei unterschiedlichen Typen von Datenfeldern mit unterschiedlichen Vergleichsfunktionen verglichen werden.
Verfahren nach Anspruch 1, – wobei das erste oder das zweite Suchprofil ein in einer Datenbank abgespeichertes Angebotsprofil ist, – wobei der jeweilige Vergleich der Datenfelder mit einem vorläufigen Vergleichswert bewertet wird, – wobei aus den vorläufigen Vergleichswerten ein endgültiger Vergleichswert berechnet wird.
Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass die Profile mehrere Ebenen umfassen, wobei zumindest in einer der Ebenen ein komplexes Datenfeld vorgesehen ist, das sich auf mehrere Datenfelder einer untergeordneten Ebene be zieht, wobei das komplexe Datenfeld eine Variable ist, in die beim Vergleichen ein komplexer Vergleichswert eingesetzt wird, der aus den zu dem komplexen Datenfeld untergeordneten Datenfeldern berechnet wird.
Verfahren nach Anspruch 3, dadurch gekennzeichnet, dass sich das komplexe Datenfeld auf Basisdatenfelder bezieht, wobei in den Basisdatenfeldern die Informationen der Profile abgespeichert sind.
Verfahren nach Anspruch 4, dadurch gekennzeichnet, dass das komplexe Datenfeld in der obersten Ebene angeordnet ist und dass unter der obersten Ebene mehrere Ebenen angeordnet sind, wobei die Beziehung von dem komplexen Datenfeld der obersten Ebene zu den Basisdatenfelder der nicht in der zur obersten Ebene unmittelbar unteren Ebene angeordneten Basisdatenfelder über weitere komplexe Datenfelder hergestellt wird, die in den Ebenen zwischen der obersten Ebene und den Ebenen, in welchen die Basisdatenfelder angeordnet sind, angeordnet sind.
Verfahren nach einem der Ansprüche 2 bis 5, dadurch gekennzeichnet, dass der endgültige Vergleichswert mit einer gewichteten Mittelwertbildung aus den vorläufigen Vergleichswerten berechnet wird.
Verfahren nach einem der Ansprüche 2 bis 6, dadurch gekennzeichnet, dass die vorläufigen Vergleichswerte jeweils einen Informationsabstand darstellen, dessen Wert umso größer ist, je stärker sich die entsprechenden Informationen unterscheiden.
Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass zum Berechnen des endgültigen Vergleichswertes aus den vorläufigen Vergleichswerten ein endgültiger Informationsabstand berechnet wird und von diesem Informationsabstand der Kehrwert berechnet wird, der den endgültigen Verkehrswert bildet.
Verfahren nach einem der Ansprüche 2 bis 8, dadurch gekennzeichnet, dass die Vergleichsfunktionen entweder zwei jeweils ein Datum, einen Zahlenwert, einen Freitext, ein Schlüsselwort, ein Intervall, eine Uhrzeit oder einen Namen enthaltende Datenfelder vergleicht und bewertet.
Verfahren nach einem der Ansprüche 2 bis 9, gekennzeichnet durch eine Vergleichsfunktion zum Vergleichen zweier jeweils einen Freitext enthaltende Datenfelder, indem – die beiden Freitexte in einzelne Wörter zerlegt werden, – für jeden Freitext jeweils ein Datensatz erstellt wird, der alle Wörter des jeweiligen Freitextes umfasst, die kein Stopwort sind, – jedes Wort der Datensätze gemäß seiner Relevanz innerhalb des Freitextes und gemäß seiner Relevanz innerhalb der Datenbank mit einem Gewichtungsfaktor (w_ij)gewichtet wird, wobei die Gewichtungsfaktoren der beiden Datensätze Elemente jeweils eines Dokumentvektors (DV_i, DV_j) sind, und – Berechnen eines Abstandes der beiden Dokumentvektoren, wobei der Abstand den vorläufigen Vergleichswert darstellt.
Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass als Abstand ein euklidischer Abstand zwischen den beiden Dokumentvektoren (DV_i, DV_j) berechnet wird.
Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass als Abstand der Kosinus zwischen den beiden Dokumentvektoren (DV_i, DV_j) berechnet wird.
Verfahren nach einem der Ansprüche 2 bis 12, dadurch gekennzeichnet, dass ein K.O.-Kriterium verwendet wird, das ein vorläufiges Vergleichsergebnis zu einem bestimmten Feld der zu vergleichenden Profile überwacht und bei einem vorbestimmten Wert des vorläufigen Vergleichsergebnisses das endgültige Vergleichsergebnis auf einen vorbestimmten Wert setzt, unabhängig von den übrigen Vergleichsergebnissen.
Verfahren nach einem der Ansprüche 2 bis 13, dadurch gekennzeichnet, dass zumindest eine Vergleichsfunktion ein Schwellwertkriterium umfasst, das beim Über- oder Unterschreiten des Schwellwertes das Vergleichsergebnis auf einen vorbestimmten Wert setzt.
Verfahren nach einem der Ansprüche 2 bis 14, gekennzeichnet durch eine Vergleichsfunktion zum Vergleichen zweier jeweils ein Zahl enthaltende Datenfelder, indem als Vergleichswert der Absolutbetrag der Differenz zwischen den beiden Zahlen berechnet wird.
Verfahren nach einem der Ansprüche 2 bis 15, gekennzeichnet durch eine Vergleichsfunktion zum Vergleichen von zwei jeweils ein Intervall enthaltenden Datenfeldern, wobei die Grenzen der beiden Intervalle (i₁, i₂) durch reelle Zahlen (i₁ = [l₁,r₁] und i₂ = [l₂, r₂]) angegeben sind, und der Vergleichswert d (i₁, i₂) gemäß folgender Formel berechnet wird:
Verfahren nach einem der Ansprüche 2 bis 16, gekennzeichnet durch eine Vergleichsfunktion zum Vergleichen zweier jeweils einen Namen enthaltende Datenfelder, indem der vorläufige Vergleichswert gleich Null gesetzt wird, falls die zu vergleichenden Namen übereinstimmen oder gleich unendlich gesetzt wird, falls sich die Namen unterscheiden.
Verwendung des Verfahrens nach einem der Ansprüche 2 bis 17 in einem Netzwerk zum Verbinden mehrerer Computer, wobei in den angezeigten Computern ein Agentensystem installiert ist und das Netzwerk mehrere Agenten aufweist, darunter ein Vergleichsagent, der zum Ausführen des Vergleichs ausgebildet ist, und ein Suchagent, der an den Vergleichsagenten eine Suchanfrage richten kann, auf welche der Vergleichsagent automatisch in einer Datenbank abgespeicherte Angebotsprofile mit einem mit der Suchanfrage übermittelten Suchprofil vergleicht und bewertet.
Verwendung nach Anspruch 18, dadurch gekennzeichnet, dass die Datenbank mit den darin enthaltenen Angebotsprofilen im Vergleichsagenten enthalten ist.
Verwendung nach Anspruch 18 oder 19, dadurch gekennzeichnet, dass mehrere Angebotsagenten vorgesehen sind, die ein ihrem Angebot entsprechendes Angebotsprofil dem Vergleichsagenten zum Speichern in seiner Datenbank übermittelt bzw. bei einer Rücknahme des Angebotes eine Nachricht an den Vergleichsagenten zum Löschen des Angebotsprofils übermitteln.