Fast computation of concept lattices using data mining techniques

We present a new algorithm called TITANIC for computing concept lattices. It is based on data mining techniques for computing frequent itemsets. The algorithm is experimentally evaluated and compared with B. Ganter's Next-Closure algorithm.

Conceptual knowledge discovery and data analysis

In this paper, we discuss Conceptual Knowledge Discovery in Databases (CKDD) in its connection with Data Analysis. Our approach is based on Formal Concept Analysis, a mathematical theory which has been developed and proven useful during the last 20 years. Formal Concept Analysis has led to a theory of conceptual information systems which has been applied by using the management system TOSCANA in a wide range of domains. In this paper, we use such an application in database marketing to demonstrate how methods and procedures of CKDD can be applied in Data Analysis. In particular, we show the interplay and integration of data mining and data analysis techniques based on Formal Concept Analysis. The main concern of this paper is to explain how the transition from data to knowledge can be supported by a TOSCANA system. To clarify the transition steps we discuss their correspondence to the five levels of knowledge representation established by R. Brachman and to the steps of empirically grounded theory building proposed by A. Strauss and J. Corbin.

Efficient data mining based on formal concept analysis

Formal Concept Analysis is an unsupervised learning technique for conceptual clustering. We introduce the notion of iceberg concept lattices and show their use in Knowledge Discovery in Databases (KDD). Iceberg lattices are designed for analyzing very large databases. In particular they serve as a condensed representation of frequent patterns as known from association rule mining. In order to show the interplay between Formal Concept Analysis and association rule mining, we discuss the algorithm TITANIC. We show that iceberg concept lattices are a starting point for computing condensed sets of association rules without loss of information, and are a visualization method for the resulting rules.

A Language for Interactive Cooperative Agents

Cooperative behaviour of agents within highly dynamic and nondeterministic domains is an active field of research. In particular establishing highly responsive teamwork, where agents are able to react on dynamic changes in the environment while facing unreliable communication and sensory noise, is an open problem. Moreover, modelling such responsive, cooperative behaviour is difficult. In this work, we specify a novel model for cooperative behaviour geared towards highly dynamic domains. In our approach, agents estimate each other’s decision and correct these estimations once they receive contradictory information. We aim at a comprehensive approach for agent teamwork featuring intuitive modelling capabilities for multi-agent activities, abstractions over activities and agents, and a clear operational semantic for the new model. This work encompasses a complete specification of the new language, ALICA.

Conceptual knowledge processing with formal concept analysis and ontologies

Among many other knowledge representations formalisms, Ontologies and Formal Concept Analysis (FCA) aim at modeling ‘concepts’. We discuss how these two formalisms may complement another from an application point of view. In particular, we will see how FCA can be used to support Ontology Engineering, and how ontologies can be exploited in FCA applications. The interplay of FCA and ontologies is studied along the life cycle of an ontology: (i) FCA can support the building of the ontology as a learning technique. (ii) The established ontology can be analyzed and navigated by using techniques of FCA. (iii) Last but not least, the ontology may be used to improve an FCA application.

A finite state model for on-line analytical processing in triadic contexts

About ten years ago, triadic contexts were presented by Lehmann and Wille as an extension of Formal Concept Analysis. However, they have rarely been used up to now, which may be due to the rather complex structure of the resulting diagrams. In this paper, we go one step back and discuss how traditional line diagrams of standard (dyadic) concept lattices can be used for exploring and navigating triadic data. Our approach is inspired by the slice & dice paradigm of On-Line-Analytical Processing (OLAP). We recall the basic ideas of OLAP, and show how they may be transferred to triadic contexts. For modeling the navigation patterns a user might follow, we use the formalisms of finite state machines. In order to present the benefits of our model, we show how it can be used for navigating the IT Baseline Protection Manual of the German Federal Office for Information Security.

Ontology merging with formal concept analysis

Ontologies have been established for knowledge sharing and are widely used as a means for conceptually structuring domains of interest. With the growing usage of ontologies, the problem of overlapping knowledge in a common domain becomes critical. In this short paper, we address two methods for merging ontologies based on Formal Concept Analysis: FCA-Merge and ONTEX. --- FCA-Merge is a method for merging ontologies following a bottom-up approach which offers a structural description of the merging process. The method is guided by application-specific instances of the given source ontologies. We apply techniques from natural language processing and formal concept analysis to derive a lattice of concepts as a structural result of FCA-Merge. The generated result is then explored and transformed into the merged ontology with human interaction. --- ONTEX is a method for systematically structuring the top-down level of ontologies. It is based on an interactive, top-down- knowledge acquisition process, which assures that the knowledge engineer considers all possible cases while avoiding redundant acquisition. The method is suited especially for creating/merging the top part(s) of the ontologies, where high accuracy is required, and for supporting the merging of two (or more) ontologies on that level.

Adaptive Real-time Anomaly-based Intrusion Detection using Data Mining and Machine Learning Techniques

Die zunehmende Vernetzung der Informations- und Kommunikationssysteme führt zu einer weiteren Erhöhung der Komplexität und damit auch zu einer weiteren Zunahme von Sicherheitslücken. Klassische Schutzmechanismen wie Firewall-Systeme und Anti-Malware-Lösungen bieten schon lange keinen Schutz mehr vor Eindringversuchen in IT-Infrastrukturen. Als ein sehr wirkungsvolles Instrument zum Schutz gegenüber Cyber-Attacken haben sich hierbei die Intrusion Detection Systeme (IDS) etabliert. Solche Systeme sammeln und analysieren Informationen von Netzwerkkomponenten und Rechnern, um ungewöhnliches Verhalten und Sicherheitsverletzungen automatisiert festzustellen. Während signatur-basierte Ansätze nur bereits bekannte Angriffsmuster detektieren können, sind anomalie-basierte IDS auch in der Lage, neue bisher unbekannte Angriffe (Zero-Day-Attacks) frühzeitig zu erkennen. Das Kernproblem von Intrusion Detection Systeme besteht jedoch in der optimalen Verarbeitung der gewaltigen Netzdaten und der Entwicklung eines in Echtzeit arbeitenden adaptiven Erkennungsmodells. Um diese Herausforderungen lösen zu können, stellt diese Dissertation ein Framework bereit, das aus zwei Hauptteilen besteht. Der erste Teil, OptiFilter genannt, verwendet ein dynamisches "Queuing Concept", um die zahlreich anfallenden Netzdaten weiter zu verarbeiten, baut fortlaufend Netzverbindungen auf, und exportiert strukturierte Input-Daten für das IDS. Den zweiten Teil stellt ein adaptiver Klassifikator dar, der ein Klassifikator-Modell basierend auf "Enhanced Growing Hierarchical Self Organizing Map" (EGHSOM), ein Modell für Netzwerk Normalzustand (NNB) und ein "Update Model" umfasst. In dem OptiFilter werden Tcpdump und SNMP traps benutzt, um die Netzwerkpakete und Hostereignisse fortlaufend zu aggregieren. Diese aggregierten Netzwerkpackete und Hostereignisse werden weiter analysiert und in Verbindungsvektoren umgewandelt. Zur Verbesserung der Erkennungsrate des adaptiven Klassifikators wird das künstliche neuronale Netz GHSOM intensiv untersucht und wesentlich weiterentwickelt. In dieser Dissertation werden unterschiedliche Ansätze vorgeschlagen und diskutiert. So wird eine classification-confidence margin threshold definiert, um die unbekannten bösartigen Verbindungen aufzudecken, die Stabilität der Wachstumstopologie durch neuartige Ansätze für die Initialisierung der Gewichtvektoren und durch die Stärkung der Winner Neuronen erhöht, und ein selbst-adaptives Verfahren eingeführt, um das Modell ständig aktualisieren zu können. Darüber hinaus besteht die Hauptaufgabe des NNB-Modells in der weiteren Untersuchung der erkannten unbekannten Verbindungen von der EGHSOM und der Überprüfung, ob sie normal sind. Jedoch, ändern sich die Netzverkehrsdaten wegen des Concept drif Phänomens ständig, was in Echtzeit zur Erzeugung nicht stationärer Netzdaten führt. Dieses Phänomen wird von dem Update-Modell besser kontrolliert. Das EGHSOM-Modell kann die neuen Anomalien effektiv erkennen und das NNB-Model passt die Änderungen in Netzdaten optimal an. Bei den experimentellen Untersuchungen hat das Framework erfolgversprechende Ergebnisse gezeigt. Im ersten Experiment wurde das Framework in Offline-Betriebsmodus evaluiert. Der OptiFilter wurde mit offline-, synthetischen- und realistischen Daten ausgewertet. Der adaptive Klassifikator wurde mit dem 10-Fold Cross Validation Verfahren evaluiert, um dessen Genauigkeit abzuschätzen. Im zweiten Experiment wurde das Framework auf einer 1 bis 10 GB Netzwerkstrecke installiert und im Online-Betriebsmodus in Echtzeit ausgewertet. Der OptiFilter hat erfolgreich die gewaltige Menge von Netzdaten in die strukturierten Verbindungsvektoren umgewandelt und der adaptive Klassifikator hat sie präzise klassifiziert. Die Vergleichsstudie zwischen dem entwickelten Framework und anderen bekannten IDS-Ansätzen zeigt, dass der vorgeschlagene IDSFramework alle anderen Ansätze übertrifft. Dies lässt sich auf folgende Kernpunkte zurückführen: Bearbeitung der gesammelten Netzdaten, Erreichung der besten Performanz (wie die Gesamtgenauigkeit), Detektieren unbekannter Verbindungen und Entwicklung des in Echtzeit arbeitenden Erkennungsmodells von Eindringversuchen.

Eine SPARQL-Schnittstelle für OData-Services

Enterprise-Resource-Planning-Systeme (ERP-Systeme) bilden für die meisten mittleren und großen Unternehmen einen essentiellen Bestandteil ihrer IT-Landschaft zur Verwaltung von Geschäftsdaten und Geschäftsprozessen. Geschäftsdaten werden in ERP-Systemen in Form von Geschäftsobjekten abgebildet. Ein Geschäftsobjekt kann mehrere Attribute enthalten und über Assoziationen zu anderen Geschäftsobjekten einen Geschäftsobjektgraphen aufspannen. Existierende Schnittstellen ermöglichen die Abfrage von Geschäftsobjekten, insbesondere mit Hinblick auf deren Attribute. Die Abfrage mit Bezug auf ihre Position innerhalb des Geschäftsobjektgraphen ist jedoch über diese Schnittstellen häufig nur sehr schwierig zu realisieren. Zur Vereinfachung solcher Anfragen können semantische Technologien, wie RDF und die graphbasierte Abfragesprache SPARQL, verwendet werden. SPARQL ermöglicht eine wesentlich kompaktere und intuitivere Formulierung von Anfragen gegen Geschäftsobjektgraphen, als es mittels der existierenden Schnittstellen möglich ist. Die Motivation für diese Arbeit ist die Vereinfachung bestimmter Anfragen gegen das im Rahmen dieser Arbeit betrachtete SAP ERP-System unter Verwendung von SPARQL. Zur Speicherung von Geschäftsobjekten kommen in ERP-Systemen typischerweise relationale Datenbanken zum Einsatz. Die Bereitstellung von SPARQL-Endpunkten auf Basis von relationalen Datenbanken ist ein seit längerem untersuchtes Gebiet. Es existieren verschiedene Ansätze und Tools, welche die Anfrage mittels SPARQL erlauben. Aufgrund der Komplexität, der Größe und der Änderungshäufigkeit des ERP-Datenbankschemas können solche Ansätze, die direkt auf dem Datenbankschema aufsetzen, nicht verwendet werden. Ein praktikablerer Ansatz besteht darin, den SPARQL-Endpunkt auf Basis existierender Schnittstellen zu realisieren. Diese sind weniger komplex als das Datenbankschema, da sie die direkte Abfrage von Geschäftsobjekten ermöglichen. Dadurch wird die Definition des Mappings erheblich vereinfacht. Das ERP-System bietet mehrere Schnittstellen an, die sich hinsichtlich des Aufbaus, der Zielsetzung und der verwendeten Technologie unterscheiden. Unter anderem wird eine auf OData basierende Schnittstelle zur Verfügung gestellt. OData ist ein REST-basiertes Protokoll zur Abfrage und Manipulation von Daten. Von den bereitgestellten Schnittstellen weist das OData-Interface gegenüber den anderen Schnittstellen verschiedene Vorteile bei Realisierung eines SPARQL-Endpunktes auf. Es definiert eine Abfragesprache und einen Link-Adressierungsmechanismus, mit dem die zur Beantwortung einer Anfrage benötigten Service-Aufrufe und die zu übertragende Datenmenge erheblich reduziert werden können. Das Ziel dieser Arbeit besteht in der Entwicklung eines Verfahrens zur Realisierung eines SPARQL-Endpunktes auf Basis von OData-Services. Dazu wird zunächst eine Architektur vorgestellt, die als Grundlage für die Implementierung eines entsprechenden Systems dienen kann. Ausgehend von dieser Architektur, werden die durch den aktuellen Forschungsstand noch nicht abgedeckten Bereiche ermittelt. Nach bestem Wissen ist diese Arbeit die erste, welche die Abfrage von OData-Schnittstellen mittels SPARQL untersucht. Dabei wird als Teil dieser Arbeit ein neuartiges Konzept zur semantischen Beschreibung von OData-Services vorgestellt. Dieses ermöglicht die Definition von Abbildungen der von den Services bereitgestellten Daten auf RDF-Graphen. Aufbauend auf den Konzepten zur semantischen Beschreibung wird eine Evaluierungssemantik erarbeitet, welche die Auflösung von Ausdrücken der SPARQL-Algebra gegen semantisch annotierte OData-Services definiert. Dabei werden die Daten aller OData-Services ermittelt, die zur vollständigen Abarbeitung einer Anfrage benötigt werden. Zur Abfrage der relevanten Daten wurden Konzepte zur Erzeugung der entsprechenden OData-URIs entwickelt. Das vorgestellte Verfahren wurde prototypisch implementiert und anhand zweier Anwendungsfälle für die im betrachteten Szenario maßgeblichen Servicemengen evaluiert. Mit den vorgestellten Konzepten besteht nicht nur die Möglichkeit, einen SPARQL-Endpunkt für ein ERP-System zu realisieren, vielmehr kann jede Datenquelle, die eine OData-Schnittstelle anbietet, mittels SPARQL angefragt werden. Dadurch werden große Datenmengen, die bisher für die Verarbeitung mittels semantischer Technologien nicht zugänglich waren, für die Integration mit dem Semantic Web verfügbar gemacht. Insbesondere können auch Datenquellen, deren Integration miteinander bisher nicht oder nur schwierig möglich war, über Systeme zur föderierten Abfrage miteinander integriert werden.

Assessing the users’ need for a spatial decision support system of smallholder farming in Kenya

Accurate data of the natural conditions and agricultural systems with a good spatial resolution are a key factor to tackle food insecurity in developing countries. A broad variety of approaches exists to achieve precise data and information about agriculture. One system, especially developed for smallholder agriculture in East Africa, is the Farm Management Handbook of Kenya. It was first published in 1982/83 and fully revised in 2012, now containing 7 volumes. The handbooks contain detailed information on climate, soils, suitable crops and soil care based on scientific research results of the last 30 years. The density of facts leads to time consuming extraction of all necessary information. In this study we analyse the user needs and necessary components of a system for decision support for smallholder farming in Kenya based on a geographical information system (GIS). Required data sources were identified, as well as essential functions of the system. We analysed the results of our survey conducted in 2012 and early 2013 among agricultural officers. The monitoring of user needs and the problem of non-adaptability of an agricultural information system on the level of extension officers in Kenya are the central objectives. The outcomes of the survey suggest the establishment of a decision support tool based on already available open source GIS components. The system should include functionalities to show general information for a specific location and should provide precise recommendations about suitable crops and management options to support agricultural guidance on farm level.

Interface issues in the ESCHER visual database editor

Presentation at the 1997 Dagstuhl Seminar "Evaluation of Multimedia Information Retrieval", Norbert Fuhr, Keith van Rijsbergen, Alan F. Smeaton (eds.), Dagstuhl Seminar Report 175, 14.04. - 18.04.97 (9716). - Abstract: This presentation will introduce ESCHER, a database editor which supports visualization in non-standard applications in engineering, science, tourism and the entertainment industry. It was originally based on the extended nested relational data model and is currently extended to include object-relational properties like inheritance, object types, integrity constraints and methods. It serves as a research platform into areas such as multimedia and visual information systems, QBE-like queries, computer-supported concurrent work (CSCW) and novel storage techniques. In its role as a Visual Information System, a database editor must support browsing and navigation. ESCHER provides this access to data by means of so called fingers. They generalize the cursor paradigm in graphical and text editors. On the graphical display, a finger is reflected by a colored area which corresponds to the object a finger is currently pointing at. In a table more than one finger may point to objects, one of which is the active finger and is used for navigating through the table. The talk will mostly concentrate on giving examples for this type of navigation and will discuss some of the architectural needs for fast object traversal and display. ESCHER is available as public domain software from our ftp site in Kassel. The portable C source can be easily compiled for any machine running UNIX and OSF/Motif, in particular our working environments IBM RS/6000 and Intel-based LINUX systems. A porting to Tcl/Tk is under way.