DE10034694A1 - Verfahren zum Vergleichen von Suchprofilen - Google Patents

Abstract

Die Erfindung betrifft ein Verfahren zum automatischen Vergleichen von Suchprofilen. DOLLAR A Mit dem erfindungsgemäßen Verfahren wird ein Suchprofil mit einem oder mehreren in einer Datenbank abgespeicherten Angebotsprofilen verglichen. Die einzelnen Profile sind in Datenfelder unterteilt, in welche die zu vergleichenden Informationen gespeichert sind. Innerhalb eines jeden Profils sind unterschiedliche Typen von Datenfeldern vorgesehen, wobei die einzelnen Profile den gleichen Aufbau besitzen. Beim Vergleichen eines Suchprofils mit einem Angebotsprofil werden zumindest zwei unterschiedliche Typen von Datenfeldern mit unterschiedlichen Vergleichsfunktionen verglichen. Aus dem hierdurch ermittelten vorläufigen Vergleichswerten wird dann ein entgültiger Vergleichswert berechnet. DOLLAR A Beim erfindungsgemäßen Verfahren werden somit für die unterschiedlichen Typen von Datenfeldern unterschiedliche Vergleichsfunktionen angewandt. Dies erlaubt einen wesentlich individuelleren Vergleich der einzelnen Informationen als es von herkömmlichen Verfahren bekannt ist.

Description

Die Erfindung betrifft ein Verfahren zum Vergleichen von zwei Suchprofilen.

Verfahren zum automatischen Vergleichen und Bewerten von Suchprofilen werden beispielsweise in Suchmaschinen im Inter­ net verwendet, um die einzelnen von den Suchmaschinen unter­ suchten möglichen Ergebnisse auf ihre Relevanz bezüglich der eingegebenen Suchbegriffe zu bewerten und gegebenenfalls als relevantes Ergebnis anzuzeigen. Werden mehrere Ergebnisse er­ mittelt, so werden diese mit abnehmender Relevanz sortiert und dem Benutzer in der entsprechenden Reihenfolge darge­ stellt.

Aus der Veröffentlichung von D. Kuokka und L. Harada, In­ tegrating 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 ver­ glichen werden, das sind Textausschnitte mit beliebiger Wort­ folge. Die Freitexte werden bei diesem Verfahren in Dokument­ vektoren gewandelt und diese Dokwnentvektoren werden bei ei­ ner 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. Wi­ doff, Dynamic Service Matchmaking among Agents in Open Infor­ mation Environments, Journal ACM SIGMOND Record, Special Is­ sue on Semantic Interoperability in Global Information Sys­ tems, A. Ouksel, A. Sheth (Eds.), 1999, und K. Sycara, J. Lu, M. Klusch Interoperability among Heteroge­ nous 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 In­ formationen mittels heterogener Agentensysteme in einer offe­ nen Umgebung, wie dem Internet auszuführen. Eine offene Umge­ bung 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:
  • 1. 2.1. Das Suchprofil und die angebotenen Informationseinheiten werden mit einem speziellen Gewichtungsverfahren (term frequency-invers document frequency weighting) vergli­ chen.
  • 2. 2.2. Bei einem Ähnlichkeitsvergleich werden die Anzahl und die Deklaration der Eingabe- und Ausgabevariablen sowie der Eingabe- und Ausgabefunktionen verglichen.
  • 3. 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 Suchan­ frage 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 In­ formation der Suchanfrage und die gesamte Information einer der angebotenen Informationseinheiten bei jedem Schritt sepa­ rat 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 mit­ teln. 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 Bewer­ ten von Informationen aufgerufen, die einen Teil des Ver­ gleichs- und Bewertungsvorganges übernehmen. Hierdurch können auch aufwendige Suchanfragen zügig abgearbeitet werden.

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

Die Aufgabe wird durch Verfahren zum Vergleichen von Suchpro­ filen mit den Merkmalen gemäß den unabhängigen Patentansprü­ chen gelöst.

Bei einem Verfahren zum Vergleichen eines ersten Suchprofils mit mindestens einem zweiten Suchprofil, wobei die Suchprofi­ le 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 Ver­ gleichen 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 Unter­ ansprüchen angegeben.

Beim erfindungsgemäßen Verfahren zum automatischen Verglei­ chen und Bewerten von Informationen wird ein von einem Benut­ zer vorgegebenes Suchprofil mit einem in einer Datenbank ab­ gespeicherten Angebotsprofil verglichen. Die Profile sind je­ weils in eine bestimmte Anzahl Datenfelder unterteilt, in welchen die zu vergleichenden Informationen gespeichert sind. Jedes Profil weist zumindest zwei unterschiedliche Typen von Datenfeldern auf. Die zu vergleichenden Profile umfassen je­ weils die gleichen Typen von Datenfeldern.

Beim Vergleichen eines Suchprofils mit einem Angebotsprofil werden die zumindest zwei unterschiedlichen Typen von Daten­ feldern mit unterschiedlichen Vergleichsfunktionen verglichen und der jeweilige Vergleich mit einem vorläufigen Vergleichs­ wert bewertet. Aus den vorläufigen Vergleichswerten wird ein endgültiger Vergleichswert berechnet.

Das erfindungsgemäße Verfahren vergleicht somit in einzelne Datenfelder strukturierte Profile. Mit der Erfindung werden für die unterschiedlichen Typen von Datenfeldern unterschied­ liche Vergleichsfunktionen angewandt, mit welchen vorläufige Vergleichswerte berechnet werden. Hierdurch können die Inhal­ te der einzelnen Datenfelder typspezifisch verglichen und be­ wertet werden. Aus den vorläufigen Vergleichswerten wird ein endgültiger Vergleichswert berechnet.

Mit der Erfindung werden somit die einzelnen Datenfelder typ­ spezifisch verglichen und die Ergebnisse der Einzelverglei­ che, 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 we­ sentlich realistischere Ergebnisse als bei den bisher bekannten 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 Vergleichsfunkti­ onen einfach zu erstellen und durch einen kurzen Programmab­ schnitt realisierbar. Hierdurch wird die Implementation des erfindungsgemäßen Verfahrens für eine bestimmte Anwendung we­ sentlich vereinfacht und zudem ist das erfindungsgemäße Ver­ fahren schnell ausführbar, da die einzelnen kurzen Programm­ abschnitte nur spezifische, zum Vergleich notwendige Aufgaben bearbeiten.

Nach einer bevorzugten Ausführungsform der Erfindung sind ein oder mehrere komplexe Datenfelder vorgesehen, die sich je­ weils 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 Infor­ mationen 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 ange­ ordnet ist, auf welche sie sich bezieht.

Nach einer bevorzugten Ausführungsform der Erfindung werden zum Vergleichen von Freitexte enthaltenden Datenfeldern Doku­ mentvektoren erstellt, wobei die einzelnen Elemente der Vek­ toren Gewichtungsfaktoren sind, die die Relevanz der Elemente beschreiben, und als vorläufiger Vergleichswert ein euklidi­ scher 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 klei­ ner 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 Suchagen­ ten und Angebotsagenten gespeicherten Profile vergleicht und bewertet. Vorzugsweise ist das Agentensystem ein offenes A­ gentensystem, 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:

Fig. 1 eine Tabelle, die unterschiedliche Basisdatenfelder zeigt,

Fig. 2 eine Profilbeschreibung in Tabellenform,

Fig. 3 eine Profilstruktur in einem Blockschaltbild,

Fig. 4 das Verfahren zum automatischen Vergleichen und Be­ werten von Informationen in einem Flussdiagramm,

Fig. 5a zwei zu vergleichende Freitexte,

Fig. 5b zwei Datensätze, die von den in Fig. 4a gezeigten Freitexten abgeleitet sind,

Fig. 5c Bewertungsergebnisse für die einzelnen Wörter der Datensätze in Tabellenform,

Fig. 6 ein Beispiel für eine Angebotsbeschreibung für eine Kooperationsbörse,

Fig. 7 ein Agentensystem in einem Blockschaltbild, und

Fig. 8 ein Netzwerk zum Verbinden von Computern, auf dem das Agentensystem aus Fig. 6 installiert ist in ei­ nem Blockschaltbild.

Beim erfindungsgemäßen Verfahren zum automatischen Verglei­ chen und Bewerten von Informationen wird ein Suchprofil mit einem in einer Datenbank abgespeicherten Angebotsprofil ver­ glichen. Fig. 2 zeigt eine Profilbeschreibung eines Ausfüh­ rungsbeispieles der Erfindung. Diese Profilbeschreibung um­ fasst acht Datenfelder, von welchen in Fig. 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 an­ gegeben ist.

Grundsätzlich unterscheidet man bei einem automatischen Ver­ gleichsverfahren 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 Pro­ filtyp 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, Da­ tumsangaben, 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 ei­ nen Satz von Schlüsselwörtern. Im Sinne der vorliegenden Be­ schreibung ist ein Satz eine ungeordnete Sammlung von Elemen­ ten des gleichen Typs, wie z. B. Wörter, reelle Zahlen, ganze Zahlen oder dergleichen. Die Variable eines Satzes wird zwi­ schen 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 derje­ nigen Teilnehmer, die die Leistung anbieten bzw. anbieten sollen. Eine Liste wird in der durch ein hochgestelltes Plus­ zeichen 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 Fig. 3 ist die Struktur der Profilbeschreibung aus Fig. 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 Fig. 2 gezeigten Datenfelder angeordnet sind. Die komplexen Datenfelder τ₁ und τ₈[1 : 2]⁺ beziehen sich jeweils auf weitere Datenfelder, die durch entsprechende Va­ riablen in der darunterliegenden Ebene dargestellt sind. So sind in der Ebene mehrere Datenfelder τ₁ angeordnet, in wel­ chen jeweils ein Schlüsselwort abgespeichert ist. Die komple­ xe Variable τ₁ bezieht sich somit auf die in der Ebene 1 ab­ gespeicherte Liste von Schlüsselwörtern. Das komplexe Datenfeld t₈[1 : 2]⁺ der Teilnehmer bezieht sich auf eine Liste von weiteren Datenfeldern. Die Elemente dieser Liste sind Feldan­ ordnungen [1 : 2], die jeweils zwei Namen, den Vor- und Nachna­ men, umfassen. Grundsätzlich umfasst eine Feldanordnung eine bestimmte Anzahl von Elementen des gleichen Typs. Die Feldan­ ordnungen τ₈[1 : 2] beziehen sich somit auf weitere Datenfel­ der, die in der Ebene 0 angeordnet sind und jeweils einen Einworteintrag aufweisen, nämlich den Vornamen oder den Nach­ namen. 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 Datenfel­ der bezeichnet. Die übrigen Datenfelder sind Basisdatenfel­ der.

In den Basisdatenfeldern sind die Informationen des jeweili­ gen Profils gespeichert. Über die komplexen Datenfelder wer­ den 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 Elemen­ ten 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 E­ bene (hier: Ebene 2) für jede begriffliche Einheit lediglich ein einziges Datenfeld vorgesehen.

In Fig. 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 ent­ sprechenden 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. Des­ halb 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 Kombinati­ on von Wörtern, Buchstaben und Zahlen. Eine Zahl τ₄ ist ent­ weder 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 je­ weils 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 Se­ kunde und M_s eine 1/100-Sekunde sind. Ein Name τ₈ ist ein be­ liebiger geeigneter Name einer Person.

Fig. 4 zeigt schematisch den Ablauf des erfindungsgemäßen Verfahrens für die in Fig. 3 gezeigte Profilstruktur.

Das Verfahren beginnt mit dem Schritt S1. Im Schritt S2 wer­ den die Datenfelder Teilnehmer mittels einer Namensver­ gleichsfunktion verglichen. Stimmen zwei Namen, das heißt zwei aus einem Vor- und Nachnamen zusammengesetzte Feldanord­ nungen ü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 Ver­ gleichswert den Abstand 1. Bei dem Vergleich der Datenfelder Teilnehmer im Schritt S2 wird jeweils eine Feldanordnung des Suchprofils mit allen entsprechenden Feldanordnungen des An­ gebotsprofils verglichen. Dieser Vergleich erfolgt somit zwi­ schen den Feldanordnungen der Ebene 0. Stimmt eine Feldanord­ nung des Suchprofils mit einer der Feldanordnungen des Ange­ botsprofils überein, so wird in der Ebene 1 des Suchprofils, in das der gefundenen Feldanordnung zugeordnete Datenfeld t₈[1 : 2] als vorläufiger Vergleichswert der Wert 0 eingetra­ gen. 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äu­ figen 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 verglei­ chenden 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 Datenfel­ dern τ₈[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 τ₈[1 : 2]+ eingetragen wird.

Im nachfolgenden Schritt S4 werden die die Schlüsselwörter beinhaltenden Datenfelder τ₁ des Suchprofils mit den entspre­ chenden Datenfeldern des Angebotsprofils verglichen. Die Ver­ gleichsfunktion zum Vergleichen der Schlüsselwörter ist der­ art 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 ausge­ fü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. Fig. 5a zeigt zwei Beispiele von Freitexten d₁, d₂, die jeweils einen Text in englischer Sprache umfas­ sen. 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, 15, 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ör­ tern jeweils ihre Häufigkeit in den entsprechenden Freitexten angegeben. Die einzelnen Wörter sind in den Datensätzen al­ phabetisch sortiert.

Zum Vergleichen der Freitexte müssen die Wörter der Datensät­ ze mit Gewichtungsfaktoren versehen sein. Zur Berechnung der Gewichtungsfaktoren wird zunächst eine sogenannte inverse Do­ kumentenhäufigkeit idf_j berechnet, die folgendermaßen defi­ niert ist:

wobei N die Gesamtzahl aller Dokumente und df_j die Anzahl der Dokumente ist, die das Wort j enthalten. Beim folgenden Aus­ führungsbeispiel stellt jeder Freitext ein Dokument dar. Ins­ gesamt gibt es neben den in Fig. 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 vor­ kommen, 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äu­ fige Wörter.

Neben der inversen Dokumenthäufigkeit wird auch die Häufig­ keit 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 Fig. 5b gezeigten Datensätze ist deren inverse Dokumentenhäufigkeit df_j und sind die Gewichtungsfak­ toren w_1,j und w_2,j in der Tabelle aus Fig. 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 kor­ respondierenden Dokumentenvektoren DV₁ und DV₂ berechnet. Er­ findungsgemäß 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 sym­ metrisch.
• - 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 ermit­ telt wird.

Anstelle der Berechnung des Abstandes zwischen den beiden Do­ kumentenvektoren 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 enthal­ tenden Datenfelder ist eine Vergleichsfunktion zum Verglei­ chen von Intervallen. Der Abstand zwischen zwei Intervallen i₁, i₂, die durch reelle Zahlen i₁ = [l₁, r₁] und i₂ = [l₂, r₂] an­ gebeben 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 Vergleichsfunk­ tion zum Vergleichen verwendet wird. Eine solche Vergleichs­ funktion lässt sich beispielsweise sehr einfach durch Bestim­ men des Absolutwertes der Differenz zwischen den zu verglei­ chenden Zahlen realisieren.

Die beim Vergleich der Datenfelder τ₂, τ₃, τ₅, τ₆ und τ₇ ermit­ telten vorläufigen Vergleichswerte werden abgespeichert. Hiermit ist der Schritt S5 abgeschlossen.

Im Schritt S6 werden die einzelnen vorläufigen Vergleichswer­ te 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 ge­ wichtet sind. Das Ergebnis dieser gewichteten Mittelwertsbil­ dung ist ein Abstandswert, der den Abstand zwischen den bei­ den zu vergleichenden Profilen, dem Suchprofil und dem Ange­ botsprofil, 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 Angebotspro­ filen entsprechend der berechneten Ähnlichkeit zum Suchprofil zu sortieren.

Wird vom Benutzer beim initiieren eines Suchvorganges festge­ legt, dass er die ähnlichsten Angebotsprofile wünscht, so wird für jedes Angebotsprofil das oben beschriebene erfin­ dungsgemäße Verfahren durchgeführt, die einzelnen Angebots­ profile 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 funktionieren­ de 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 ver­ schiedenen Plätzen aktiv sein können und ihren Ort im Compu­ ternetzwerk verändern können.

In Fig. 7 ist schematisch der Ablauf des erfindungsgemäßen Verfahrens mittels dreier Agenten dargestellt. Hierbei wird ein Vergleichsagent, ein Suchagent und ein Angebotsagent ver­ wendet. Der Vergleichsagent enthält eine Datenbank, in dem die ihm bekannten Angebotsagenten mit ihren jeweiligen Ange­ botsprofilen 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 Vergleichsagen­ ten eine Suchanfrage. Die Suchanfrage enthält ein entspre­ chendes Suchprofil. Dieses Suchprofil vergleicht der Ver­ gleichsagent mit den in seiner Datenbank gespeicherten Angebotsprofilen und bewertet sie gemäß dem oben beschriebenen Verfahren. Er übermittelt dem Suchagenten eine entsprechende Suchantwort, die eine Liste mit den Namen der relevanten An­ gebotsagenten enthält, wobei jeder Angebotsagent mit einem Vergleichswert bewertet ist.

Der Suchagent kann die Suchantwort entweder an seinen ur­ sprünglichen Auftraggeber weiterleiten oder an den Angebots­ agenten, 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.

Fig. 1 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 eini­ ge mobile Agenten AG-I bis AG-IV, die entweder auf einem der Computer 1 angeordnet sind, bzw. sich von einem zu einem an­ deren 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 entspre­ chend vorbestimmten Art und Weise weiterbehandeln und insbe­ sondere an denjenigen Benutzer, der einen Computer des Netz­ werkes bedient, weiterleiten.

Das erfindungsgemäße Verfahren kann als Softwareprodukt rea­ lisiert werden, das in einem Netzwerk, beispielsweise in Form eines Vergleichsagenten abgespeichert ist. Das erfindungsge­ mäße Verfahren kann jedoch auch auf einem beliebigen elektro­ nisch lesbaren Datenträger oder einem Halbleiterspeicher in einem Computer abgespeichert und in dem Computer zur Ausfüh­ rung gebracht werden.

Die Erfindung wird oben anhand eines Ausführungsbeispieles näher erläutert. Sie ist jedoch nicht auf die konkrete Aus­ führungsform des Ausführungsbeispieles beschränkt. Wesentlich für die Erfindung ist, dass die einzelnen Profile durch un­ terschiedliche Typen von Datenfeldern strukturiert sind und dass für die unterschiedlichen Typen von Datenfeldern unter­ schiedliche Vergleichsfunktionen angewandt werden. Hierdurch erhält man eine multidimensionale Bewertung der zu verglei­ chenden Profile. Diese multidimensionale Bewertung der Profi­ le ergibt eine sehr individuelle Bewertung, die sehr ähnlich der Bewertung durch einen Menschen ist. Im Rahmen der Erfin­ dung 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 vergli­ chen werden, wobei eines der beiden Profile auf ein weiteres Profil abgebildet wird, dessen Struktur mit der des zu ver­ gleichenden 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 abgebil­ det werden. Diese Informationseinheiten werden dann mittels der ihnen zugeordneten strukturierten Profile verglichen.

Claims (20)

1. Verfahren zum Vergleichen eines ersten Suchprofils mit mindestens einem zweiten Suchprofil, wobei die Suchprofile jeweils mehrere Datenfelder aufweisen, dadurch kennzeichnet, dass die Datenfelder des ersten Suchprofils und des zweiten Such­ profils jeweils zumindest zwei Datenfelder mit einem unter­ schiedlichen Typ umfassen, welcher bei dem jeweiligen Daten­ feld des ersten und des zweiten Suchprofilvektors gleich ist, bei welchem Verfahren beim Vergleichen des ersten Suchprofils mit dem zweiten Suchprofil die zumindest zwei unterschiedli­ chen Typen von Datenfeldern mit unterschiedlichen Vergleichs­ funktionen verglichen werden.

2. Verfahren zum automatischen Vergleichen und Bewerten von Informationen, wobei jeweils ein Suchprofil mit einem in ei­ ner Datenbank abgespeicherten Angebotsprofil verglichen wird, und die Profile jeweils in eine bestimmte Anzahl Datenfelder unterteilt sind, in welchen die zu vergleichenden Informatio­ nen gespeichert sind, und jedes Profil zumindest zwei unter­ schiedliche Typen von Datenfeldern besitzt, und die zu ver­ gleichenden Profile jeweils die gleichen Typen von Datenfel­ dern umfassen, wobei
beim Vergleichen eines Suchprofils mit einem Angebotsprofil die zumindest zwei unterschiedlichen Typen von Datenfeldern mit unterschiedlichen Vergleichsfunktionen verglichen werden und der jeweilige Vergleich mit einem vorläufigen Vergleichs­ wert bewertet wird, und
aus den vorläufigen Vergleichswerten ein endgültiger Ver­ gleichswert berechnet wird.

3. 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 bezieht, 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.

4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, dass sich das komplexe Datenfeld auf Basisdatenfelder be­ zieht, wobei in den Basisdatenfeldern die Informationen der Profile abgespeichert sind.

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, dass das komplexe Datenfeld in der obersten Ebene angeordnet ist und dass unter der obersten Ebene mehrere Ebenen angeord­ net 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 Basis­ datenfelder über weitere komplexe Datenfelder hergestellt wird, die in den Ebenen zwischen der obersten Ebene und den Ebenen, in welchen die Basisdatenfelder angeordnet sind, an­ geordnet sind.

6. Verfahren nach einem der Ansprüche 2 bis 5, dadurch gekennzeichnet, dass der endgültige Vergleichswert mit einer gewichteten Mit­ telwertbildung aus den vorläufigen Vergleichswerten berechnet wird.

7. Verfahren nach einem der Ansprüche 2 bis 6, dadurch gekennzeichnet, dass die vorläufigen Vergleichswerte jeweils einen Informati­ onsabstand darstellen, dessen Wert umso größer ist, je stär­ ker sich die entsprechenden Informationen unterscheiden.

8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass zum Berechnen des endgültigen Vergleichswertes aus den vorläufigen Vergleichswerten ein endgültiger Informationsab­ stand berechnet wird und von diesem Informationsabstand der Kehrwert berechnet wird, der den endgültigen Verkehrswert bildet.

9. Verfahren nach einem der Ansprüche 2 bis 8, dadurch gekennzeichnet, dass die Vergleichsfunktionen entweder zwei jeweils ein Da­ tum, einen Zahlenwert, einen Freitext, ein Schlüsselwort, ein Intervall, eine Uhrzeit oder einen Namen enthaltende Daten­ felder vergleicht und bewertet.

10. 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 Stop­ wort sind,
jedes Wort der Datensätze gemäß seiner Relevanz innerhalb des Freitextes und gemäß seiner Relevanz innerhalb der Daten­ bank mit einem Gewichtungsfaktor (w_ij) gewichtet wird, wobei die Gewichtungsfaktoren der beiden Datensätze Elemente je­ weils eines Dokumentvektors (DV_i, DV_j) sind, und
Berechnen eines Abstandes der beiden Dokumentvektoren, wo­ bei der Abstand den vorläufigen Vergleichswert darstellt.

11. Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass als Abstand ein euklidischer Abstand zwischen den beiden Dokumentvektoren (DV_i, DV_j) berechnet wird.

12. Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass als Abstand der Kosinus zwischen den beiden Dokumentvek­ toren (DV_i, DV_j) berechnet wird.

13. 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 verglei­ chenden Profile überwacht und bei einem vorbestimmten Wert des vorläufigen Vergleichsergebnisses das endgültige Ver­ gleichsergebnis auf einen vorbestimmten Wert setzt, unabhän­ gig von den übrigen Vergleichsergebnissen.

14. Verfahren nach einem der Ansprüche 2 bis 13, dadurch gekennzeichnet, dass zumindest eine Vergleichsfunktion ein Schwellwertkrite­ rium umfasst, das beim Über- oder Unterschreiten des Schwell­ wertes das Vergleichsergebnis auf einen vorbestimmten Wert setzt.

15. 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.

16. Verfahren nach einem der Ansprüche 2 bis 15, gekennzeichnet durch eine Vergleichsfunktion zum Vergleichen zwei jeweils ein In­ tervall enthaltende Datenfelder, 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:

17. 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 Ver­ gleichswert gleich Null gesetzt wird, falls die zu verglei­ chenden Namen übereinstimmen oder gleich unendlich gesetzt wird, falls sich die Namen unterscheiden.

18. Netzwerk zum Verbinden mehrerer Computer, wobei in den angezeigten Computern ein Agentensystem installiert ist und das Netzwerk mehrere Agenten aufweist, gekennzeichnet durch einen Vergleichsagenten, der zum Ausführen des Verfahrens nach einem der Ansprüche 2 bis 17 ausgebildet ist, und einem Suchagenten, der an den Vergleichsagenten eine Suchan­ frage richten kann, auf welche der Vergleichsagent automa­ tisch in einer Datenbank abgespeicherte Angebotsprofile mit einem mit der Suchanfrage übermittelten Suchprofils ver­ gleicht und bewertet.

19. Netzwerk nach Anspruch 18, dadurch gekennzeichnet, dass die Datenbank mit den darin enthaltenen Angebotsprofilen im Vergleichsagenten enthalten ist.

20. Netzwerk 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 Vergleichsagen­ ten zum Löschen des Angebotsprofils übermitteln.