BISON, RTD Forschungsprojekt

Institutionen
  • FB Informatik und Informationswissenschaft
Publikationen
  Berthold, Michael (Hrsg.) (2012): Bisociative Knowledge Discovery

Bisociative Knowledge Discovery

×
Modern knowledge discovery methods enable users to discover complex patterns of various types in large information repositories. However, the underlying assumption has always been that the data to which the methods are applied originates from one domain.<br /><br /><br /><br />The focus of this book, and the BISON project from which the contributions originate, is a network-based integration of various types of data repositories and the development of new ways to analyse and explore the resulting gigantic information networks. Instead of seeking well-defined global or local patterns, the aim was to find domain-bridging associations. These are particularly interesting if they are sparse and have not been encountered before.<br /><br /><br /><br />The 32 contributions presented in this state-of-the-art survey, together with a detailed introduction to the book, are organized in topical sections on bisociation; representation and network creation; network analysis; exploration; and applications and evaluation.

Forschungszusammenhang (Projekte)

    Nagel, Uwe; Thiel, Kilian; Kötter, Tobias; Piatek, Dawid; Berthold, Michael R.(2012): Towards Discovery of Subgraph Bisociations Bisociative Knowledge Discovery / Berthold, Michael R. (Hrsg.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - (Lecture Notes in Computer Science ; 7250). - S. 263-284. - ISBN 978-3-642-31829-0

Towards Discovery of Subgraph Bisociations

×
The discovery of surprising relations in large, heterogeneous information repositories is gaining increasing importance in real world data analysis. If these repositories come from diverse origins, forming different domains, domain bridging associations between otherwise weakly connected domains can provide insights into the data that are not accomplished by aggregative approaches. In this paper, we propose a first formalization for the detection of such potentially interesting, domaincrossing relations based purely on structural properties of a relational knowledge description.

Forschungszusammenhang (Projekte)

    Berthold, Michael R.(2012): Towards Bisociative Knowledge Discovery Bisociative Knowledge Discovery / Berthold, Michael R. (Hrsg.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - (Lecture Notes in Computer Science ; 7250). - S. 1-10. - ISBN 978-3-642-31829-0

Towards Bisociative Knowledge Discovery

×
Knowledge discovery generally focuses on finding patterns within a reasonably well connected domain of interest. In this article we outline a framework for the discovery of new connections between domains (so called bisociations), supporting the creative discovery process in a more powerful way. We motivate this approach, show the difference to classical data analysis and conclude by describing a number of different types of domain-crossing connections.

Forschungszusammenhang (Projekte)

    Thiel, Kilian; Berthold, Michael R.(2012): Node Similarities from Spreading Activation Bisociative Knowledge Discovery / Berthold, Michael R. (Hrsg.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - (Lecture Notes in Computer Science ; 7250). - S. 246-262. - ISBN 978-3-642-31829-0

Node Similarities from Spreading Activation

×
In this paper we propose two methods to derive different kinds of node neighborhood based similarities in a network. The first similarity measure focuses on the overlap of direct and indirect neighbors. The second similarity compares nodes based on the structure of their possibly also very distant neighborhoods. Both similarities are derived from spreading activation patterns over time. Whereas in the first method the activation patterns are directly compared, in the second method the relative change of activation over time is compared. We applied both methods to a real world graph dataset and discuss some of the results in more detail.

Forschungszusammenhang (Projekte)

    Dubitzky, Werner; Kötter, Tobias; Schmidt, Oliver; Berthold, Michael R.(2012): Towards Creative Information Exploration Based on Koestler's Concept of Bisociation Bisociative Knowledge Discovery / Berthold, Michael R. (Hrsg.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - (Lecture Notes in Computer Science ; 7250). - S. 11-32. - ISBN 978-3-642-31829-0

Towards Creative Information Exploration Based on Koestler's Concept of Bisociation

×
Creative information exploration refers to a novel framework for exploring large volumes of heterogeneous information. In particular, creative information exploration seeks to discover new, surprising and valuable relationships in data that would not be revealed by conventional information retrieval, data mining and data analysis technologies. While our approach is inspired by work in the field of computational creativity, we are particularly interested in a model of creativity proposed by Arthur Koestler in the 1960s. Koestler’s model of creativity rests on the concept of bisociation. Bisociative thinking occurs when a problem, idea, event or situation is perceived simultaneously in two or more “matrices of thought” or domains. When two matrices of thought interact with each other, the result is either their fusion in a novel intellectual synthesis or their confrontation in a new aesthetic experience. This article discusses some of the foundational issues of computational creativity and bisociation in the context of creative information exploration.

Forschungszusammenhang (Projekte)

    Kötter, Tobias; Berthold, Michael R.(2012): From Information Networks to Bisociative Information Networks Bisociative Knowledge Discovery / Berthold, Michael R. (Hrsg.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - (Lecture Notes in Computer Science ; 7250). - S. 33-50. - ISBN 978-3-642-31829-0

From Information Networks to Bisociative Information Networks

×
The integration of heterogeneous data from various domains without the need for prefiltering prepares the ground for bisociative knowledge discoveries where attempts are made to find unexpected relations across seemingly unrelated domains. Information networks, due to their flexible data structure, lend themselves perfectly to the integration of these heterogeneous data sources. This chapter provides an overview of different types of information networks and categorizes them by identifying several key properties of information units and relations which reflect the expressiveness and thus ability of an information network to model heterogeneous data from diverse domains. The chapter progresses by describing a new type of information network known as bisociative information networks. This kind of network combines the key properties of existing networks in order to provide the foundation for bisociative knowledge discoveries. Finally based on this data structure three different patterns are described that fulfill the requirements of a bisociation by connecting concepts from seemingly unrelated domains.

Forschungszusammenhang (Projekte)

    Kötter, Tobias; Berthold, Michael R.(2012): (Missing) Concept Discovery in Heterogeneous Information Networks Bisociative Knowledge Discovery / Berthold, Michael R. (Hrsg.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - (Lecture Notes in Computer Science ; 7250). - S. 230-245. - ISBN 978-3-642-31829-0

(Missing) Concept Discovery in Heterogeneous Information Networks

×
This article proposes a new approach to extract existing (or detect missing) concepts from a loosely integrated collection of information units by means of concept graph detection. Thereby a concept graph defines a concept by a quasi bipartite sub-graph of a bigger network with the members of the concept as the first vertex partition and their shared aspects as the second vertex partition. Once the concepts have been extracted they can be used to create higher level representations of the data. Concept graphs further allow the discovery of missing concepts, which could lead to new insights by connecting seemingly unrelated information units.

Forschungszusammenhang (Projekte)

  Kötter, Tobias(2012): Konzepterkennung in Informationsnetzwerken

Konzepterkennung in Informationsnetzwerken

×
Konzepte spielen in unserem täglichen Leben eine wichtige Rolle, wenn auch nur unbewusst.<br /><br />So gruppieren Konzepte Objekte mit gemeinsamen Eigenschaften und ermöglichen uns das Abstrahieren und Kommunizieren von bestehendem Wissen sowie die Verarbeitung der pausenlos auf uns einströmenden Flut von Informationen.<br /><br />Dabei agiert ein Konzept als Repräsentant seiner Mitglieder und ihrer gemeinsamen Eigenschaften.<br /><br />Wenn wir an das Konzept der Transportmittel denken, fallen uns spontan einige Mitglieder und ihre Eigenschaften ein, die diese als Transportmittel auszeichnen.<br /><br />Eine weitere Besonderheit der Konzepte ist, dass ein Objekt Mitglied in scheinbar unabhängigen Konzepten sein kann.<br /><br />So gilt ein Auto sowohl als Transportmittel als auch als Luxusgegenstand.<br /><br /><br /><br />Der in dieser Arbeit beschriebene Ansatz macht sich diese Leistungsfähigkeit und Flexibilität von Konzepten zunutze, um das kreative Denken zu fördern.<br /><br />So ermöglicht der Ansatz das Finden von existierenden sowie unbekannten Konzepten in heterogenen Daten, welche das Verständnis für komplexe Systeme fördern sowie interessante und unerwartete Zusammenhänge aufdecken.<br /><br /><br /><br />Da bei der Suche nach unerwarteten Zusammenhängen nicht von Anfang an feststeht, wonach man eigentlich sucht, sollte bei der Integration der zur Verfügung stehenden Daten möglichst keine Information verloren gehen.<br /><br />Daher basiert der beschriebene Ansatz auf Informationsnetzwerken, welche dank ihrer flexiblen Datenstruktur die Integration von Daten unterschiedlichster Beschaffenheit und Qualität unterstützen.<br /><br />So speichern Informationsnetzwerke die Informationen in Form von Beziehungen zwischen Objekten in einer Graphstruktur, wobei Objekte als Knoten und ihre Beziehungen als Kanten im Graphen repräsentiert werden.<br /><br /><br /><br />Basierend auf dieser Datenrepräsentation beruht der beschriebene Ansatz auf der Annahme, dass Objekte durch ihre direkten Nachbarn im Netzwerk beschrieben werden.<br /><br />Somit bilden ähnliche Objekte und ihre gemeinsamen Nachbarn einen quasi bipartiten Graphen.<br /><br />Dieser aus den beiden Knotenpartitionen und ihren Verbindungen bestehende Teilgraph bildet die Basis des beschriebenen Ansatzes, den sogenannten Konzeptgraphen.<br /><br />Die Güte der Verbindungen zwischen den beiden Knotenpartitionen wird mithilfe einer Gütefunktion bestimmt, welche das Fehlen einzelner Verbindungen bestraft.<br /><br />Daher sollten sich die ähnlichen Objekte möglichst viele Nachbarn teilen.<br /><br />Einen Spezialfall stellen dabei die vollständigen Konzeptgraphen dar, deren Knotenpartitionen vollständig verbunden sind.<br /><br /><br /><br />Zum Klassifizieren der Knoten eines Konzeptgraphen werden ferner Heuristiken basierend auf der Graphstruktur vorgestellt, welche die Identifizierung der Mitglieder und Eigenschaften eines Konzeptes sowie des Konzeptrepräsentanten ermöglichen.<br /><br />Dabei ist der Typ eines Knotens kontextabhängig und kann so in unterschiedlichen Konzeptgraphen variieren.<br /><br />Die Heuristik zur Bestimmung des Konzeptrepräsentanten liefert darüber hinaus ein Maß für dessen Güte, welches zum Auffinden eines fehlenden Repräsentanten verwendet werden kann.<br /><br />Ein fehlender Konzeptrepräsentant kann dabei ein Anzeichen für unvollständige und verrauschte Daten sein.<br /><br />Er kann aber auch ein Hinweis auf eine Gruppe von Objekten mit gemeinsamen Eigenschaften sein, die bisher noch nicht entdeckt wurden und daher noch keinen Konzeptrepräsentanten besitzen.<br /><br /><br /><br />Neben der Formalisierung von Konzeptgraphen werden Verfahren zum Finden von vollständigen Konzeptgraphen sowie Ansätze zum Finden von allgemeinen Konzeptgraphen beschrieben.<br /><br />Die beschriebenen Verfahren und Ansätze basieren auf existierenden Verfahren zum Finden von Frequent Item Sets, welche sich durch die Konvertierung des Graphen in eine Transaktionsliste anwenden lassen.<br /><br /><br /><br />Fallstudien demonstrieren schließlich die Existenz sowie die Flexibilität und Vielfältigkeit von Konzeptgraphen anhand von zwei unterschiedlichen Datensätzen aus der realen Welt.<br /><br />So basiert der erste Datensatz auf einer Enzyklopädie mit Artikeln aus unterschiedlichen Wissensgebieten.<br /><br />Der zweite Datensatz basiert hingegen auf strukturierten sowie unstrukturierten Informationen über Medikamente.<br /><br /><br /><br />In beiden Datensätzen werden sinnvolle Konzeptgraphen mithilfe des beschriebenen Verfahrens zum Finden von vollständigen Konzeptgraphen gefunden und ihre Knoten unter Verwendung der vorgestellten Heuristiken in die unterschiedlichen Typen eingeteilt.<br /><br />Basierend auf dem Gütewert für den Konzeptrepräsentanten werden ferner Konzeptgraphen ohne sinnvollen Repräsentanten identifiziert, welche unbekannte Zusammenhänge aufdecken.<br /><br />Überlappende Konzeptgraphen demonstrieren schließlich die volle Flexibilität und Vielfältigkeit von Konzeptgraphen.<br /><br />So können die Überlappungen sowohl zum Identifizieren von Hierarchien verwendet werden als auch zu einem besseren Verständnis komplexer Zusammenhänge führen.<br /><br />Darüber hinaus ermöglichen sie auch das Auffinden fehlender Verbindungen, die zu neuen Erkenntnissen führen.<br /><br /><br /><br />Durch die Verwendung von Informationsnetzwerken als Eingabedaten und dem Auffinden von existierenden sowie unbekannten Konzepten unterstützt das in dieser Arbeit vorgestellte Verfahren das kreative Denken, indem es sowohl das Verständnis komplexer Systeme fördert als auch interessante und unerwartete Zusammenhänge aufdeckt.

Forschungszusammenhang (Projekte)

    Haun, Stefan; Gossen, Tatiana; Nürnberger, Andreas; Kötter, Tobias; Berthold, Michael R.(2012): On the Integration of Graph Exploration and Data Analysis : the Creative Exploration Toolkit Bisociative Knowledge Discovery / Berthold, Michael R. (Hrsg.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - (Lecture Notes in Computer Science ; 7250). - S. 301-312. - ISBN 978-3-642-31829-0

On the Integration of Graph Exploration and Data Analysis : the Creative Exploration Toolkit

×
To enable discovery in large, heterogenious information networks a tool is needed that allows exploration in changing graph structures and integrates advanced graph mining methods in an interactive visualization framework. We present the Creative Exploration Toolkit (CET), which consists of a state-of-the-art user interface for graph visualization designed towards explorative tasks and support tools for integration and communication with external data sources and mining tools, especially the data-mining platform KNIME. All parts of the interface can be customized to fit the requirements of special tasks, including the use of node type dependent icons, highlighting of nodes and clusters. Through an evaluation we have shown the applicability of CET for structure-based analysis tasks.

Forschungszusammenhang (Projekte)

  Borgelt, Christian; Braune, Christian; Kötter, Tobias; Grün, Sonja(2011): New algorithms for finding approximate frequent item sets Soft Computing ; 16 (2011), 5. - S. 903-917. - ISSN 1432-7643. - eISSN 1433-7479

New algorithms for finding approximate frequent item sets

×
In standard frequent item set mining a transaction supports an item set only if all items in the set are present. However, in many cases this is too strict a requirement that can render it impossible to find certain relevant groups of items. By relaxing the support definition, allowing for some items of a given set to be missing from a transaction, this drawback can be amended. The resulting item sets have been called approximate, fault-tolerant or fuzzy item sets. In this paper we present two new algorithms to find such item sets: the first is an extension of item set mining based on cover similarities and computes and evaluates the subset size occurrence distribution with a scheme that is related to the Eclat algorithm. The second employs a clustering-like approach, in which the distances are derived from the item covers with distance measures for sets or binary vectors and which is initialized with a one-dimensional Sammon projection of the distance matrix. We demonstrate the benefits of our algorithms by applying them to a concept detection task on the 2008/2009 Wikipedia Selection for schools and to the neurobiological task of detecting neuron ensembles in (simulated) parallel spike trains.

Forschungszusammenhang (Projekte)

    Borgelt, Christian; Kötter, Tobias(2011): Mining fault-tolerant item sets using subset size occurrence distributions Advances in Intelligent Data Analysis X / Gama, João; Bradley, Elizabeth; Hollmén, Jaakko (Hrsg.). - Berlin, Heidelberg : Springer Berlin Heidelberg, 2011. - (Lecture Notes in Computer Science ; 7014). - S. 43-54. - ISBN 978-3-642-24799-6

Mining fault-tolerant item sets using subset size occurrence distributions

×
Mining fault-tolerant (or approximate or fuzzy) item sets means to allow for errors in the underlying transaction data in the sense that actually present items may not be recorded due to noise or measurement errors. In order to cope with such missing items, transactions that do not contain all items of a given set are still allowed to support it. However, either the number of missing items must be limited, or the transaction's contribution to the item set's support is reduced in proportion to the number of missing items, or both. In this paper we present an algorithm that efficiently computes the subset size occurrence distribution of item sets, evaluates this distribution to find fault-tolerant item sets, and exploits intermediate data to remove pseudo (or spurious) item sets. We demonstrate the usefulness of our algorithm by applying it to a concept detection task on the 2008/2009 Wikipedia Selection for schools.

Forschungszusammenhang (Projekte)

    Brandes, Ulrik; Lerner, Jürgen; Nagel, Uwe(2010): Network ensemble clustering using latent roles Advances in Data Analysis and Classification ; 5 (2010), 2. - S. 81-94. - ISSN 1862-5347

Network ensemble clustering using latent roles

×
We present a clustering method for collections of graphs based on the assumptions that graphs in the same cluster have a similar role structure and that the respective roles can be founded on implicit vertex types. Given a network ensemble (a collection of attributed graphs with some substantive commonality), we start by partitioning the set of all vertices based on attribute similarity. Projection of each graph onto the resulting vertex types yields feature vectors of equal dimensionality, irrespective of the original graph sizes. These feature vectors are then subjected to standard clustering methods. This approach is motivated by social network concepts, and we demonstrate its utility on an ensemble of personal networks of migrants, where we extract structurally similar groups and show their resemblance to predicted acculturation strategies.

Forschungszusammenhang (Projekte)

Mittelgeber
NameKennzifferBeschreibungLaufzeit
Kooperation757/08keine Angabe
Weitere Informationen
Laufzeit: 01.06.2008 – 31.05.2011