FMK 2013, Suchstrategien, Martin Braendle & Volker Krambich

FileMaker Konferenz 2013 Salzburg

www.filemaker-konferenz.com Dr. Martin Brändle, Dr. Volker Krambrich Suchstrategien

Suchstrategien

Dr. Martin Brändle, Dr. Volker Krambrich



Über Martin: Als ...

•  FileMaker Entwickler –  denke ich in Datenstrukturen –  entwickle ich für das Web (Custom Web Publishing, MVC-Ansatz)

•  Computational Chemist (Quantenchemie) –  denke ich in Algorithmen –  liess ich die CPUs während Tagen braten

•  Informationsspezialist NDS I+D (Chemieinformation) –  arbeite ich mit Daten in FileMaker und anderen Systemen –  denke ich in Kategoriensystemen –  denke ich in Symbolen, grafischen Strukturen, Topologien –  arbeite ich oft mit anderen Informationssystemen als FileMaker –  beschäftige ich mich mit Recherchefragen der Kunden und versuche sie

zu unterstützen

Kontakt: [email protected]





Über Volker

•  Linguist und Informatiker, promoviert •  FileMaker 12 Certified Developer •  FileMaker Certified Trainer und Lehrer •  Schwerpunkte: Prozessmodellierung, Custom Software, (Instant) Web

Publishing (auch HTML, XML, XSLT), Modellierung

•  FileMaker Re-Cycling — betagte Lösungen aufpeppen und in moderne Programme überführen

Kontakt: [email protected]



Programm

•  Wahr oder Falsch / Ja oder Nein / Schwarz oder Weiss •  Textsuchen: Wie können wir Erfolg verbessern? – Query-Analyse –  Stoppwörter –  Unterstützte Suche – Meinen Sie?

•  Facettierung: Clustern und Verfeinern •  Ähnlichkeit •  Netzwerke •  Mustererkennung: Fragmentierung •  Schlussbetrachtung



Textsuchen klassisch



Wie können wir den Endnutzer bei der Recherche unterstützen?

•  Ausbildung und Support: Schulung, Training, Support

•  Technische Massnahmen –  GUI: Simpel und logisch – Quickfind/Google-like

•  Eine Suchzeile/mehrere Attribute gleichzeitig suchen •  Suchfrage und Resultate auf einem Schirm

- Nicht nur Search, sondern auch Browse - Vorgegebene Einstiegspunkte oder Favoriten - rasche Navigation zu nützlichen Resultaten - Benutzer erhält Vorstellung, was in der Datenbank sein könnte

– Optimierung der Suchfragen und -antworten



Beispiel



Optimierung der Suchfragen

•  Log der Suchfragen erstellen –  Erfasst

•  Query •  Zeitstempel •  Suchtyp (einfach/fortgeschritten) •  Sprache GUI •  Anzahl Treffer pro gesuchter Tabelle

–  Abgeleitete Merkmale •  Erfolg (1/0) •  Anzahl Wörter •  Anzahl Ziffern/Zahlen •  Anteil Sonderzeichen (Operatoren, weitere) •  Anteil Grossschreibung



Implementation Suchschema (Beispiel CWP)



Analyse und Optimierung der Suchfragen

•  Projekt ACUEIL: Analyse von ca. 150‘000 Suchen 2005-2008 (2013: ca. 360‘000)

Ergebnis: Einfache Massnahmen: Filtern der Eingabe •  Indizierende Sonderzeichen wie . , : ; & entfernen •  Stoppwörter (bedeutungsarme Wörter) entfernen

an, and, das, de, der, of, on, the, und, ... –  sinnvoll bei Suche in Texten mit natürlicher Sprache –  nicht sinnvoll z.B. bei Personennamen (Lookup), Einzeldaten

•  Übersetzung von Schlüsselbegriffen in Datenrepräsentation (Erfassungsregeln) der DB –  Beispiel: Volume, Volumes à Vol, calculations à calcs.

•  Filterung via Substitute(“ “ & text & “ “; [“ an “; “ “]; [“ and “; “ “]; ....)



Optimierung der Daten (Antworten)

•  Ergebnis aus Analyse: Benutzer verwenden Copy & Paste •  Beispiele von Eingaben –  ARCHIV DER PHARMAZIE UND BERICHTE DER DEUTSCHEN

PHARMAZEUTISCHEN GESSELSCHAFT –  ANGEWANDTE CHEMIE-INTERNATIONAL EDITION

•  Merkmale: Grossschreibung, Bindestrich, Falschschreibung •  Herkunft: Science Citation Index (Web of Science) •  Massnahme –  Hinterlegung der „falschen“ Daten in einem zusätzlichen Feld („Fussnote“,

„Bemerkung“), das mitgesucht wird (konkret: 156 Titel) –  Key-Value-Modell hilfreich

[sic!]



Sucherfolg vs. Anzahl Suchbegriffe



Unterstützte Suchen

Tippfehler reduziert Voransicht der Resultate



Implementation

•  Bedingungen –  Performance (Tippgeschwindigkeit) –  Daten stammen aus mehreren Tabellen –  Suchen und Aggregieren über mehrere Tabellen, Sortieren zu langsam

•  Lösung –  Vorsortierte Tabelle (Präkoordination), ca. 100‘000 Strings –  Periodischer Update (jährlich, Bereinigung und Konsolidierung der Daten)

•  Implementation –  YUILibrary Autocomplete Widget

•  http://yuilibrary.com/yui/docs/autocomplete/ •  XML Datenquelle (FM PHP API) •  Cache browserseitig



Ambivalente/Unsinnige Fragen

•  Ambivalente Anfragen: zuviele Treffer (>100) –  Science –  Inorg Chem –  Nature –  Cell

•  Unsinnige Anfragen –  falsch verstandenes Zitat: Bsp. ibid –  Nicht Standard-Zeitschriftenabkürzungen, Bsp. JOMC, C –  falsches Findmittel

•  Patente: U S P, Ger. Offen. •  ganze Artikelreferenzen •  chemische Verbindungsnamen

–  falsches Feld, Bsp. ISBN-Nummer in Titel etc.

•  Häufige Tippfehler, z.B. Hollemann, Göppel



Beispiel „Meinen Sie?“



Meinen Sie?

•  à la Google –  begrifforientiert: Alternativbegriff für eingegebenen Begriff –  benötigt Index der Begriffe –  benötigt Wortähnlichkeit/Silbentrenn-Algorithmus

(z.B. Levenshtein-Distanz für Wortähnlichkeit) –  teuer (CPU, Speicher)

•  à la FileMaker –  resultatorientiert: zu Begriff wird Link zu richtigem Resultat oder

alternativer Lösungsweg vorgeschlagen –  nutzt Fachkompetenz der Einrichtung – wenige, ausgewählte Begriffe –  billig



Facettierung – Clustern und Verfeinern

•  Grundidee –  Breit suchen –  Statistische Analyse der Resultate nach vordefinierten Kategorien

•  Histogramm Attribute und Anzahl –  Verfeinern durch Hinzufügen von Attributen zur Suchfrage



Beispiel Facettierung (Apache Solr)



Beispiel Facettierung: Reaxys



Demo



Facettierung mit FileMaker Pro 12



Facettierung ohne ExecuteSQL?

•  Möglicher Lösungsansatz mit Custom Functions –  CustomList (Agnès Barouh) bzw. HyperList (Todd Geist)

•  Virtuelle Liste über Found Set –  UniqueList (Agnès Barouh) –  Distribution (Bruce Robertson) –  SortList (Agnès Barouh)





Demo Volker

Volker, da kannst du etwas zum Einstieg zeigen. Demonstrierst du uns Hyperlists?





Case study: Contracts administration

Suchbegriff

Utrio





Case study: Contracts administration Zusatztreffer






•  Kategorie •  Ergebnisanzeige •  Suchbegriff

wiederholen





Case study: Contracts administration •  suche in unbekanntem Feld

(Verfasser, Titel, Untertitel, Kommentar etc.)

•  SuchKategorie erkennen (Name; ISBN; Telefonnummer etc.)

•  unscharf suchen: John oder Jon •  Ergebnismenge begrenzen •  Kategorisieren

•  Lösung zeigt angepasstes fmSearch (Matt Navarre, seedcode.com) im Einsatz

•  Live Demo, wenn Internet hält…






Martin, das war der Übergang zurück zu Dir... …das sieht dir ähnlich!



Ähnlichkeit

vom ! zum ~



Attribut- und Textähnlichkeit

Ähnlichkeit zwischen zwei Attributmengen A, B Ähnlichkeitsmasse •  Jaccard-Koeffizient oder –Index

•  Tanimoto-Ähnlichkeit (für binäre Fingerprints)

•  Sørensen-Dice-Koeffizient oder –Index



Demo



Attribut/Wort-Index •  Eigene Erzeugung –  Extraktion Attribute/Wörter pro

Datensatz –  Stoppwortgefiltert –  Variante: Nur unterschiedliche Wörter

und Anzahl –  Variante: Position(en) mitspeichern

•  Aktionen für Datensatzänderungen –  Insert: Script (via Script Trigger) –  Delete: Löschen via Beziehung –  Performance: Problemlos, Aufwand linear, Script start-/stoppbar,

paralellisierbar



Andere Sichtweise: Attribut-/Begriffsvektoren •  Attribute/Begriffe spannen einen Vektor im n-dimensionalen Indexraum auf •  Winkel zwischen zwei Vektoren ist Mass für Ähnlichkeit Skalarprodukt

Beispiel •  Begriffe (chemical, 3764), (engineering, 5815), (kinetics 7931), (operations

11748), (unit 14728) •  Vektor a: Unit Operations of Chemical Engineering (3764, 5815, 11748,

14728) •  Vektor b: Chemical Engineering Kinetics (3764, 5815, 7931, 0)

cos φ = 0.67

•  Problem: Benötigt Inversen Index



Inverser Index •  Attribut/Begriff à Datensätze •  Attributhäufigkeit

•  Problematik: Inverser Index muss für jede Datensatzänderung (Insert, Delete) nachgeführt werden –  Insert: Existiert Wort bereits? à Record Count erhöhen, sonst einfügen

(via Script Trigger) –  Delete: nur mit Script. Record Count erniedrigen, bei 0 Wort löschen –  Performance: x Suchen pro Datensatzänderung

•  Ersterzeugung, Varianten –  Export (als XML), Gruppieren/Zählen mit XSLT, Reimport –  ExecuteSQL(”SELECT DISTINCT Wort, COUNT(DISTINCT Wort) FROM

WortIndex ORDER BY Wort”; ””; ””) (Problem 2 GB-Limite) Das überlassen wir den FileMaker-Software-Ingenieuren!



Ähnlichkeitsverfahren: Problem Skalierung Für alle Ähnlichkeitsverfahren gilt •  Zwischen 2 Tabellen der Grösse n und m:

s = n*m (wenn n ≃ m à ∼n2)

•  Selbstähnlichkeit in Tabelle der Grösse n:

s = ½ n * (n -1) ∼n2

•  Beispiel: Kleiner Bibliothekskatalog mit 80‘000 Einträgen, Selbstähnlichkeit è 3.2 Milliarden Vergleiche



Lösungsansatz Skalierung

–  Hinzuziehen weiterer Kriterien für Reduktion Grösse Start- und Vergleichsmenge

–  Rollendes Fenster: z.B. Zeit, Anzahl Indexbegriffe, .. –  bei zeit-/personenabhängigen Daten: Gruppieren in Sessions

– Sessionlänge – IP-Adresse – Session-ID (Cookies)



Analyse Resultate

•  7152 Titel prozessiert •  Aufwand ca. 4.5 h •  Effektiv: 1.39 Mio.

Berechnungen •  Theoretisch: Ca. 25.5 Mio -

572 Mio. Berechnungen Gefunden •  1167 Titel mit ≥1 verwandten

Titel(n) (16.3%) •  1506 Paarkorrelationen

J(A,B) # Paare % Paare 1.00 780 51.8 0.95-1.00 0 0 0.90-0.95 25 1.7 0.85-0.90 66 4.4

0.8-0.85 132 8.8 0.75-0.80 164 10.9 0.70-0.75 143 9.5 0.65-0.70 72 4.8 0.60-0.65 124 8.2

„Hat sich Aufwand gelohnt?“



Analyse Performance (1)



Analyse Performance (2)

•  Durchschnittliche Berechnungszeit / Zyklus : ca. 10 ms –  17 Scriptschritte (9 für Berechnung, 8 für Speichern Resultat) –  3 ExecuteSQL-Befehle



Nun wissen wir, wie ähnliche Dinge – noch aus demselben Bereich –

gefunden werden können.

Wie ist das mit Zusammenhängen zwischen verschiedenen Domänen?

Netzwerke: Komplexe Zusammenhänge entdecken





Das Diabetes Dilemma...

–  Diabetes (Typ1) ist wachsende Herausforderung

–  Das Problem wächst zu auch zu einem Kostenproblem

–  In 2005 Dialyse in Finnland teurer als der Jahresumsatz von Nokia (ca. 5,4 Mrd. €)

–  Forschungsauftrag: Was sind die Ursachen

–  Ziel: Wie kann man vorbeugen •  Ziel: Prognostizierbarkeit




























Mustererkennung

Siehst Du auch ein Muster?



Demo DNA

•  4 Buchstaben für Nukleotide: C (Cytosin), G (Guanin), A (Adenin), T (Thymin)

•  Identifizierung von Teilsequenzen



n-Gramme (n-grams)

•  Zerlegung von Texten/Zeichenfolgen in Fragmente oder formale Worte der Länge nBeispiel: 3-Gramme von „FileMaker“

**f, *fi, fil, ile, lem, mak, ake, ker, er*, r**

•  evtl. mit Positionsindex

1_fil 2_ile 3_lem 4_mak 5_ake 6_ker 7_ke 8_r •  evtl. gleitender Ausschnitt (Beispiel: Länge 6)

1 1_fil 2_ile 3_lem 4_mak 5_ake 6_ker 2 1_ile 2_lem 3_mak 4_ake 5_ker 6_ke 3 1_lem 2_mak 3_ake 4_ker 5_er 6_r

...



Identifizierung aller Teilsequenzen



Diskussion n-Gramme •  Vorteile –  Sprachunabhängig –  statistische Auswertung eines Textkorpus –  Verteilung erlaubt Identifikation der Sprache –  nicht gleich gut anwendbar auf alle natürlichen Sprachen –  funktioniert auch bei verstmmeltn Textn (fehlertolerantes Retrieval)

•  Nachteil –  Sprachen, die bei Flexion zu starker Formänderung neigen, bereiten

Probleme –  Flexibilität wird mit hohem Aufwand erkauft



Schlussbetrachtung •  Inspiration holen von anderen Gebieten Wolfgang G. Stock, Information Retrieval : Informationen suchen und finden, Oldenbourg Verlag, München, 2007

•  Datenrepräsentation und -suche bedingen sich gegenseitig •  Komplexe Suchen (Ähnlichkeit, Mustererkennung) erfordern Aufwand –  Präkoordinativ: Erzeugen von Fragmenten („Schnipseln“), Übersetzung

vom mehrdimensionalen in linearen Datenraum –  Algorithmisch: Übersetzen der Suchfrage in FileMaker-Repräsentation –  Postkoordinativ: Sammeln, Zusammenfassen, Aufbereiten der Resultate

•  Aufwand und Grenzen im Voraus abschätzen –  Skalierung (Speicher, Performance) –  Portierbarkeit der Methode

(Einzelbenutzer à mehrere Benutzer, Client à Server, Client à Web)



Vielen Dank unseren Sponsoren

Danke für das Bewerten dieses Vortrages



Appendix: Erweiterte Implementation



Appendix: Levenshtein-Distanz

•  Levenshtein-Distanz –  Minimale Anzahl Operationen (Ersetzen,

Einfügen, Löschen eines Buchstabens), um ein Wort in ein anderes zu überführen

•  Analyse von Benutzerkorrekturen –  Tippfehler der Benutzer –  Einsatz des SmartPill Plugins und

der PHP-Funktion levenshtein()

Documents

FMK 2013, Suchstrategien, Martin Braendle & Volker Krambich