New Textstrukturierung mit Data-Mining- Verfahrengraubitz/diasdem/papers/... · 2003. 3. 4. · 2...

Prof. Myra Spiliopoulou

Handelshochschule Leipzig

ChemnitzChemnitz, 22.06.01, 22.06.01

Textstrukturierung mit Data-Mining-

Verfahren

Textstrukturierung mit Data-Mining-

Verfahren

2

Das DFG-Projekt DIAsDEMDas DFG-Projekt DIAsDEM

Ziel:Integration von Altlastdaten und Texten von mehreren Quellen in ein Informationssystem

Methodik: Data Mining

Die Forschungsgruppen:

HHL:• Myra Spiliopoulou• Karsten Winkler• Henner Graubitz (HiWi)

LMU:• Stefan Conrad• Evgenia Altarewa

3

AgendaAgenda

• Texteinträge in einem Informationssystem --

Was bedeutet „Integration“ ?

• Knowledge-Discovery-from-Texts in DIAsDEM

Das DIAsDEM Workbench

• Eine Fallstudie

4

Integration von Texten in ein ISIntegration von Texten in ein IS

Der Betrieb von Spielhallen in Teltow und das Aufstellen von Geldspiel- und Unterhaltungsautomaten. Stammkapital: 25.000 EUR. Gesellschaft mit beschränkter Haftung. Der Gesellschaftsvertrag ist am 12. November 1998 abgeschlossen und am 19. April 1999 abgeändert.(...) Pawel Balski, 14.04.1965, Berlin, ist zum Ge-schäftsführer bestellt. Er vertritt dieGesellschaft stets einzeln und (...)

Daniel Spiel-Center GmbHPotsdamer Str. 94, 14513 Teltow

HRB 1257606.05.99

5

Integration von Texten in ein ISIntegration von Texten in ein IS

• Die Eintragung in das Handelsregister ist obligatorisch für Unternehmen in Deutschland.

• Für jedes Unternehmen existieren mehrere Eintragungen, und zwar beim Handelsgericht jeder Niederlassung.

• Die Angaben in den Handelsregistern sind gesetzlich bindend.

• Jede Eingabe kann Angaben eines früheren Eintrags (zum Teil) aufheben.

6

Integration von Texten in ein ISIntegration von Texten in ein IS

Der Betrieb von Spielhallen in Teltow und das Aufstellen von Geldspiel- und Unterhaltungsautomaten. Stammkapital: 25.000 EUR. Gesellschaft mit beschränkter Haftung. Der Gesellschaftsvertrag ist am 12. November 1998 abgeschlossen und am 19. April 1999 abgeändert. (...) Pawel Balski, 14.04.1965, Berlin, ist zum Ge-schäftsführer bestellt. Er vertritt dieGesellschaft stets einzeln und (...)

Wer sind die Geschäftsführer von Daniel Spiel-Center GmbH ?

sowie alle weitere Personen, die früher dazu bestellt wurden und deren Bestellung nicht rückgängig gemacht worden ist.

7

Integration von Texten in ein ISIntegration von Texten in ein IS

Erwünschte Funktionalität für ein HRG-IS:

• Das Suchergebnis soll alle relevante Eintragungen enthalten.

• Es soll keine unrelevante Eintragungen enthalten.

• Nur die gesuchten Angaben sollen gezeigt werden, der Rest des Textes soll nur nach Aufforderung erscheinen.

8

Integration von Texten in ein ISIntegration von Texten in ein IS

Der DIAsDEM Vorschlag:

• Semantische Auszeichnung der Texte in XML

mit Data Mining Verfahren

• Ableitung einer DTD für das Textarchiv

• Überführung des Textarchivs zu einer Sammlung semistrukturierter Dokumente

• Anwendung einer XML-basierten Anfragesprache für die Suche über die Dokumentensammlung

9

KDT in DIAsDEMKDT in DIAsDEM

• Gruppierung aller Textelemente, die sich mit demselben Thema befassen

• Inhaltliche Charakterisierung jeder Gruppe

• Identifizierung von wichtigen Entitäten in den einzelnen Textelementen

• Zusammenführung der Gruppennamen und Entitätenbeschreibungen in einer DTD

Semantische Auszeichnung von Texten in XML:

Element := Satz

Labeling

Named-Entity Extraction

10

KDT in DIAsDEMKDT in DIAsDEM

Clustering

Aufbereitungsphase

Identifizierte Entitäten

ClustererXML DTDSätze mit XML-Tags

Alle Sätze aller Dokumente im Archiv

Cluster Labeling

XML Dokumente

11

KDT in DIAsDEM (Input)KDT in DIAsDEM (Input)

Aufbereitungsphase

TextsätzeThesaurusReferenz-schema

Entitäts-beschreibungen

bestellenGeschäftsführerGesellschaftGesellschafterProkuraProkurist

Datum = DD Monat YY

12

KDT in DIAsDEM (Prep)KDT in DIAsDEM (Prep)

Referenz-schema

Aufbereitungsphase

TextsätzeThesaurusEntitäts-

beschreibungen

Pawel Balski,14.04.1965,Berlin,ist zum Geschäftsführer bestellt.

1. Ausblendung aller erkannten Entitäten

2. Abbildung aller Wörter auf ihre WortstämmePERSON, DATUM, ORT, sein zu Geschäftsführer bestellen.

3. Vektorisierung der Sätze anhand des Thesaurus<bestellen, Geschäftsführer, Gesellschaft, Prokura>

1 1 0 0

PERSON,DATUM, ORT,ist zum Geschäftsführer bestellt.

13

KDT in DIAsDEM (Mining)KDT in DIAsDEM (Mining)

Clustering

Referenz-schema

Aufbereitungsphase

TextsätzeThesaurusEntitäts-

beschreibungen

Inhomogene Gruppen

Homogene Gruppen

14

Iteratives ClusteringIteratives Clustering

• Gruppierung der Vektoren nach einem Ähnlichkeitsmaß

• Evaluation der Qualität der erzeugten Clusters

• Ausblendung aller Vektoren, die zu “guten” Clusters gehören.

• Wiederholung des Gruppierungsvorgangs für die übriggebliebenen Vektoren

nach Anpassung der Steuerungsparameter

15

Cluster QualitätCluster Qualität

• Qualitätskriterien:

* Hohe Ähnlichkeit innerhalb des Clusters

+ Große Anzahl von Vektoren im Cluster

+ Kleine Anzahl von dominierenden Begriffen

• weil: Cluster = = DTD Komponente

+ Ein XML-Tag kann erst dann effektiv genutzt werden, wenn es oft im Archiv vorkommt.

+ Ein XML-Tag soll einen sinnvollen und intuitivenBegriff darstellen.

16

Cluster QualitätCluster Qualität

• Prozentsatz der auftretenden Begriffe im Cluster zu der Gesamtzahl der Begriffe im Thesaurus

• Prozentsatz der häufig auftretenden Begriffe im Cluster zu der Anzahl aller Begriffe im Cluster

Zwei Kennzahlen für das dritte Qualitätskriterion:

17

KDT in DIAsDEM (Labeling)KDT in DIAsDEM (Labeling)

Clustering

Referenz-schema

Aufbereitungsphase

TextsätzeThesaurusEntitäts-

beschreibungen

Inhomogene Gruppen

Homogene Gruppen

Cluster Labeling XML DTD

18

Cluster LabelingCluster Labeling

• Gruppe I: Begriffe, die sehr häufig im Cluster auftreten

• Gruppe II: Weitere Begriffe, die vom Clustering Algorithmus als signifikant bezeichnet wurden

nach Häufigkeit geordnet,und dem Experten zur Auswahl vorgeschlagen.

Die Begriffe im Cluster werden gruppiert:

ClusterLabel

Referenz-schema

19

HRG Text mit XML MarkierungHRG Text mit XML Markierung

Der Betrieb von Spielhallen in Teltow und das Aufstellen von Geldspiel- und Unterhaltungsautomaten.(...)<GeschäftsführerBestellen>Pawel Balski,14.04.1965, Berlin, ist zum Geschäftsführerbestellt</GeschäftsführerBestellen>.<Vertretung>Er vertritt dieGesellschaft stets einzeln und (...)</Vertretung>

Daniel Spiel-Center GmbHPotsdamer Str. 94, 14513 Teltow

HRB 1257606.05.99

20

KDT in DIAsDEM (NEEX)KDT in DIAsDEM (NEEX)

Clustering

Referenz-schema

Aufbereitungsphase

TextsätzeThesaurusEntitäts-

beschreibungen

Inhomogene Gruppen

Homogene Gruppen

Cluster Labeling XML DTD

XML Dokumente

NEEX

Entitäten

21

NEEXNEEX

• entdeckt

– Namen von Personen, Unternehmen und Ortschaften

– Datumsangaben und Geldbeträge

• mit Hilfe

– eines Regelsatzes

– des Postbuchs

– des Telefonbuchs

Der Named-Entity-EXtractor

22

HRG Text mit XML MarkierungHRG Text mit XML Markierung

Der Betrieb von Spielhallen in Teltow und das Aufstellen von Geldspiel- und Unterhaltungsautomaten.(...)<GeschäftsführerBestellenPerson=“Pawel Balski” Datum=“14.04.1965”Ort=“Berlin”>Pawel Balski,14.04.1965,Berlin,ist zum Geschäftsführer bestellt</GeschäftsführerBestellen>.<Vertretung>Er vertritt dieGesellschaft stets einzeln und (...)</Vertretung>

Daniel Spiel-Center GmbHPotsdamer Str. 94, 14513 Teltow

HRB 1257606.05.99

23

Das DIAsDEM WorkbenchDas DIAsDEM Workbench

Clustering

Referenz-schema

DIAsDEM Preprocessor

TextsätzeThesaurusEntitäts-

beschreibungen

Inhomogene Gruppen

Homogene Gruppen

Cluster Labeling XML DTD

XML Dokumente

NEEX

Entitäten

DIAsDEM Monitor

24

FallstudieFallstudie

• HRG Eintragungen zu Neugründungen im Jahr 1999

– 1,145 Dokumente

– 10,785 Sätze

• Thesaurus mit 85 Begriffen

Semantische Aufzeichnung eines Datensatzes ausdem Handelsgericht Potsdam

25

Fallstudie Fallstudie

• Aufbereitungsphase

– TreeTagger (IMS Stuttgart) : Stemming

– DIAsDEM Preprocessor: NEEX und Vektorisierung

• Iteratives Clustering

– IBM Intelligent Miner for Data: “demographic” clustering function

– DIAsDEM Monitor: 3 Iterationen über den Datensatz

• Ergebnis: 73 homogene Clusters

26

Fallstudie Fallstudie

• Evaluation

– Fehlertyp I: Der XML-Tag eines Satzes entspricht nicht dem Inhalt

– Fehlertyp II: Ein Satz hat keinen XML-Tag, obwohl es einen passenden XML-Tag gibt

• Manuelle Inspektion von 5% der Dokumente

• Ergebnis

– Fehlertyp I: 0.375% im bearbeiteten Datensatz

– Fehlertyp II: 3.565% im bearbeiteten Datensatz

27

Zusammenfassung und AusblickZusammenfassung und Ausblick

• Semantische Annotation von Texten in XML:

– Module zu Textaufbereitung: Entdeckung von wichtigen Entitäten und Vektorisierung

– Das DIAsDEM Monitor: Gruppierung von Textelementen in große und homogene Clusters, die durch eine kleine Anzahl von Begriffen beschrieben werden können

– Plug-in Konzept zur Anbindung von Mining Modulen und Textaufbereitungssoftware

• Eintragung der XML-markierten Texten in ein DBMS

28

Zusammenfassung und AusblickZusammenfassung und Ausblick

• In Bearbeitung:

– Automatisierte Auswahl der Begriffe für den Vektorenraum durch Koppelung des Thesaurus mit dem Referenzschema

– Erweiterung des Ranking-Moduls für die Generierung von Labels

– Evaluierung mehrerer Clustering-Algorithmen und Ähnlichkeitsmaßstäbe

• Geplant: Ableitung von komplexen DTDs

29

Vielen Dank für Ihre Aufmerksamkeit !Vielen Dank für Ihre Aufmerksamkeit !

FragenMyra Spiliopoulou

myra@ebusiness.hhl.dehttp://ebusiness.hhl.de