No description available.

No description available.

Association rule mining (ARM) is the task of identifying meaningful implication rules exhibited in a data set. Most research has focused on extracting frequent item (FI) sets and thus fallen short of the overall ARM objective. The FI miners fail to identify the upper covers that are needed to generate a set of association rules whose size can be exploited by an end user. An alternative to FI mining can be found in formal concept analysis (FCA), a branch of applied mathematics. FCA derives a concept lattice whose concepts identify closed FI sets and connections identify the upper covers. However, most FCA algorithms construct a complete lattice and therefore include item sets that are not frequent. An iceberg lattice, on the other hand, is a concept lattice whose concepts contain only FI sets. Only three algorithms to construct an iceberg lattice were found in literature. Given that an iceberg concept lattice provides an analysis tool to succinctly identify association rules, this study investigated additional algorithms to construct an iceberg concept lattice. This report presents the development and analysis of the Quick Iceberg Concept Lattice (QuICL) algorithms. These algorithms provide incremental construction of an iceberg lattice. QuICL uses recursion instead of iteration to navigate the lattice and establish connections, thereby eliminating costly processing incurred by past algorithms. The QuICL algorithms were evaluated against leading FI miners and FCA construction algorithms using benchmarks cited in literature. Results demonstrate that QuICL provides performance on the order of FI miners yet additionally derive the upper covers. QuICL, when combined with known algorithms to extract a basis of association rules from a lattice, offer a "best known" ARM solution. Beyond this, the QuICL algorithms have proved to be very efficient, providing an order of magnitude gains over other incremental lattice construction algorithms. For example, on the Mushroom data set, QuICL completes in less than 3 seconds. Past algorithms exceed 200 seconds. On T10I4D100k, QuICL completes in less than 120 seconds. Past algorithms approach 10,000 seconds. QuICL is proved to be the "best known" all around incremental lattice construction algorithm. Runtime complexity is shown to be O(l d i) where l is the cardinality of the lattice, d is the average degree of the lattice, and i is a mean function on the frequent item extents.

Formal concept analysis is increasingly applied to query expansion and data mining problems. In this paper I analyze and compare the current concept lattice construction algorithm, and choose iPred and Border algorithms to adapt for query expansion. After I adapt two concept lattice construction algorithms, I apply these four algorithms on one query expansion prototype system. The calculation time for four algorithms are recorded and analyzed. The result of adapted algorithms is good. Moreover I find the efficiency of concept lattice construction is not consistent with complex analysis result. In stead, it is high depend on the structure of data set, which is data source of concept lattice.

Le traitement automatique de documents consiste en la transformation dans un format compréhensible par un système informatique de données présentes au sein de documents et compréhensibles par l'Homme. L'analyse de document et la compréhension de documents sont les deux phases du processus de traitement automatique de documents. Étant donnée une image de document constituée de mots, de lignes et d'objets graphiques tels que des logos, l'analyse de documents consiste à extraire et isoler les mots, les lignes et les objets, puis à les regrouper au sein de blocs. Les différents blocs ainsi formés constituent la structure géométrique du document. La compréhension de documents fait correspondre à cette structure géométrique une structure logique en considérant des liaisons logiques (à gauche, à droite, au-dessus, en-dessous) entre les objets du document. Un système de traitement de documents doit être capable de : (i) localiser une information textuelle, (ii) identifier si cette information est pertinente par rapport aux autres informations contenues dans le document, (iii) extraire cette information dans un format compréhensible par un programme informatique. Pour la réalisation d'un tel système, les difficultés à surmonter sont liées à la variabilité des caractéristiques de documents, telles que le type (facture, formulaire, devis, rapport, etc.), la mise en page (police, style, agencement), la langue, la typographie et la qualité de numérisation du document. Dans ce mémoire, nous considérons en particulier des documents numérisés, également connus sous le nom d'images de documents. Plus précisément, nous nous intéressons à la localisation d'informations textuelles au sein d'images de factures, afin de les extraire à l'aide d'un moteur de reconnaissance de caractères. Les factures sont des documents très utilisés mais non standards. En effet, elles contiennent des informations obligatoires (le numéro de facture, le numéro siret de l'émetteur, les montants, etc.) qui, selon l'émetteur, peuvent être localisées à des endroits différents. Les contributions présentées dans ce mémoire s'inscrivent dans le cadre de la localisation et de l'extraction d'informations textuelles fondées sur des régions identifiées au sein d'une image de document.Tout d'abord, nous présentons une approche de décomposition d'une image de documents en sous-régions fondée sur la décomposition quadtree. Le principe de cette approche est de décomposer une image de documents en quatre sous-régions, de manière récursive, jusqu'à ce qu'une information textuelle d'intérêt soit extraite à l'aide d'un moteur de reconnaissance de caractères. La méthode fondée sur cette approche, que nous proposons, permet de déterminer efficacement les régions contenant une information d'intérêt à extraire.Dans une autre approche, incrémentale et plus flexible, nous proposons un système d'extraction d'informations textuelles qui consiste en un ensemble de régions prototypes et de chemins pour parcourir ces régions prototypes. Le cycle de vie de ce système comprend cinq étapes:- Construction d'un jeu de données synthétiques à partir d'images de factures réelles contenant les informations d'intérêts.- Partitionnement des données produites.- Détermination des régions prototypes à partir de la partition obtenue.- Détermination des chemins pour parcourir les régions prototypes, à partir du treillis de concepts d'un contexte formel convenablement construit.- Mise à jour du système de manière incrémentale suite à l'insertion de nouvelles données / Document processing is the transformation of a human understandable data in a computer system understandable format. Document analysis and understanding are the two phases of document processing. Considering a document containing lines, words and graphical objects such as logos, the analysis of such a document consists in extracting and isolating the words, lines and objects and then grouping them into blocks. The subsystem of document understanding builds relationships (to the right, left, above, below) between the blocks. A document processing system must be able to: locate textual information, identify if that information is relevant comparatively to other information contained in the document, extract that information in a computer system understandable format. For the realization of such a system, major difficulties arise from the variability of the documents characteristics, such as: the type (invoice, form, quotation, report, etc.), the layout (font, style, disposition), the language, the typography and the quality of scanning.This work is concerned with scanned documents, also known as document images. We are particularly interested in locating textual information in invoice images. Invoices are largely used and well regulated documents, but not unified. They contain mandatory information (invoice number, unique identifier of the issuing company, VAT amount, net amount, etc.) which, depending on the issuer, can take various locations in the document. The present work is in the framework of region-based textual information localization and extraction.First, we present a region-based method guided by quadtree decomposition. The principle of the method is to decompose the images of documents in four equals regions and each regions in four new regions and so on. Then, with a free optical character recognition (OCR) engine, we try to extract precise textual information in each region. A region containing a number of expected textual information is not decomposed further. Our method allows to determine accurately in document images, the regions containing text information that one wants to locate and retrieve quickly and efficiently.In another approach, we propose a textual information extraction model consisting in a set of prototype regions along with pathways for browsing through these prototype regions. The life cycle of the model comprises five steps:- Produce synthetic invoice data from real-world invoice images containing the textual information of interest, along with their spatial positions.- Partition the produced data.- Derive the prototype regions from the obtained partition clusters.- Derive pathways for browsing through the prototype regions, from the concept lattice of a suitably defined formal context.- Update incrementally the set of protype regions and the set of pathways, when one has to add additional data.

Context and lattice orbifolds have been discussed by M. Zickwolff, B. Ganter and D. Borchmann. Preordering the folding automorphisms by set inclusion of their orbits gives rise to further development. The minimal elements of this preorder have a prime group order and any group element can be dissolved into the product of group elements whose group order is a prime power. This contribution describes a way to compress an orbifold annotation to sets of such minimal automorphisms. This way a hierarchical annotation is described together with an interpretation of the annotation. Based on this annotation an example is given that illustrates the construction of an automaton for certain pattern matching problems in music processing.

Draft and proof of an algorithm computing incremental changes within a labeled layouted concept lattice upon insertion or removal of an attribute column in the underlying formal context. Furthermore some implementational details and mathematical background knowledge are presented. / Entwurf und Beweis eines Algorithmus zur Berechnung inkrementeller Änderungen in einem beschrifteten dargestellten Begriffsverband beim Einfügen oder Entfernen einer Merkmalsspalte im zugrundeliegenden formalen Kontext. Weiterhin sind einige Details zur Implementation sowie zum mathematischen Hintergrundwissen dargestellt.

Context and lattice orbifolds have been discussed by M. Zickwolff, B. Ganter and D. Borchmann. Preordering the folding automorphisms by set inclusion of their orbits gives rise to further development. The minimal elements of this preorder have a prime group order and any group element can be dissolved into the product of group elements whose group order is a prime power. This contribution describes a way to compress an orbifold annotation to sets of such minimal automorphisms. This way a hierarchical annotation is described together with an interpretation of the annotation. Based on this annotation an example is given that illustrates the construction of an automaton for certain pattern matching problems in music processing.

Cette thèse présente un cadre de travail d'analyse de trajectoires contenant une phase de prétraitement et un processus d’extraction de trajectoires d’objets mobiles. Le cadre offre des fonctions visuelles reflétant le comportement d'évolution des motifs de trajectoires. L'originalité de l’approche est d’allier extraction de motifs fréquents, extraction de motifs émergents et analyse formelle de concepts pour analyser les trajectoires. A partir des données de trajectoires, les méthodes proposées détectent et caractérisent les comportements d'évolution des motifs. Trois contributions sont proposées : Une méthode d'analyse des trajectoires, basée sur les concepts formels fréquents, est utilisée pour détecter les différents comportements d’évolution de trajectoires dans le temps. Ces comportements sont “latents”, "emerging", "decreasing", "lost" et "jumping". Ils caractérisent la dynamique de la mobilité par rapport à l'espace urbain et le temps. Les comportements détectés sont visualisés sur des cartes générées automatiquement à différents niveaux spatio-temporels pour affiner l'analyse de la mobilité dans une zone donnée de la ville. Une deuxième méthode basée sur l'extraction de concepts formels séquentiels fréquents a également été proposée pour exploiter la direction des mouvements dans la détection de l'évolution. Enfin, une méthode de prédiction basée sur les chaînes de Markov est présentée pour prévoir le comportement d’évolution dans la future période pour une région. Ces trois méthodes sont évaluées sur ensembles de données réelles . Les résultats expérimentaux obtenus sur ces données valident la pertinence de la proposition et l'utilité des cartes produites / This dissertation presents a trajectory analysis framework, which includes both a preprocessing phase and trajectory mining process. Furthermore, the framework offers visual functions that reflect trajectory patterns evolution behavior. The originality of the mining process is to leverage frequent emergent pattern mining and formal concept analysis for moving objects trajectories. These methods detect and characterize pattern evolution behaviors bound to time in trajectory data. Three contributions are proposed: (1) a method for analyzing trajectories based on frequent formal concepts is used to detect different trajectory patterns evolution over time. These behaviors are "latent", "emerging", "decreasing", "lost" and "jumping". They characterize the dynamics of mobility related to urban spaces and time. The detected behaviors are automatically visualized on generated maps with different spatio-temporal levels to refine the analysis of mobility in a given area of the city, (2) a second trajectory analysis framework that is based on sequential concept lattice extraction is also proposed to exploit the movement direction in the evolution detection process, and (3) prediction method based on Markov chain is presented to predict the evolution behavior in the future period for a region. These three methods are evaluated on two real-world datasets. The obtained experimental results from these data show the relevance of the proposal and the utility of the generated maps

Draft and proof of an algorithm computing incremental changes within a labeled layouted concept lattice upon insertion or removal of an attribute column in the underlying formal context. Furthermore some implementational details and mathematical background knowledge are presented.:1 Introduction 1.1 Acknowledgements 1.2 Supporting University: TU Dresden, Institute for Algebra 1.3 Supporting Corporation: SAP AG, Research Center Dresden 1.4 Research Project: CUBIST 1.5 Task Description und Structure of the Diploma Thesis I Mathematical Details 2 Fundamentals of Formal Concept Analysis 2.1 Concepts and Concept Lattice 2.2 Visualizations of Concept Lattices 2.2.1 Transitive Closure and Transitive Reduction 2.2.2 Neighborhood Relation 2.2.3 Line Diagram 2.2.4 Concept Diagram 2.2.5 Vertical Hybridization 2.2.6 Omitting the top and bottom concept node 2.2.7 Actions on Concept Diagrams 2.2.8 Metrics on Concept Diagrams 2.2.9 Heatmaps for Concept Diagrams 2.2.10 Biplots of Concept Diagrams 2.2.11 Seeds Selection 2.3 Apposition of Contexts 3 Incremental Updates for Concept Diagrams 3.1 Insertion & Removal of a single Attribute Column 3.1.1 Updating the Concepts 3.1.2 Structural Remarks 3.1.3 Updating the Order 3.1.4 Updating the Neighborhood 3.1.5 Updating the Concept Labels 3.1.6 Updating the Reducibility 3.1.7 Updating the Arrows 3.1.8 Updating the Seed Vectors 3.1.9 Complete IFOX Algorithm 3.1.10 An Example: Stepwise Construction of FCD(3) 3.2 Setting & Deleting a single cross 4 Iterative Exploration of Concept Lattices 4.1 Iceberg Lattices 4.2 Alpha Iceberg Lattices 4.3 Partly selections 4.3.1 Example with EMAGE data 4.4 Overview on Pruning & Interaction Techniques II Implementation Details 5 Requirement Analysis 5.1 Introduction 5.2 User-Level Requirements for Graphs 5.2.1 Select 5.2.2 Explore 5.2.3 Reconfigure 5.2.4 Encode 5.2.5 Abstract/Elaborate 5.2.6 Filter 5.2.7 Connect 5.2.8 Animate 5.3 Low-Level Requirements for Graphs 5.3.1 Panel 5.3.2 Node and Edge 5.3.3 Interface 5.3.4 Algorithm 5.4 Mapping of Low-Level Requirements to User-Level Requirements 5.5 Specific Visualization Requirements for Lattices 5.5.1 Lattice Zoom/Recursive Lattices/Partly Nested Lattices 5.5.2 Planarity 5.5.3 Labels 5.5.4 Selection of Ideals, Filters and Intervalls 5.5.5 Restricted Moving of Elements 5.5.6 Layout Algorithms 5.5.7 Additional Feature: Three Dimensions and Rotation 5.5.8 Additional Feature: Nesting 6 FCAFOX Framework for Formal Concept Analysis in JAVA 6.1 Architecture A Appendix A.1 Synonym Lexicon A.2 Galois Connections & Galois Lattices A.3 Fault Tolerance Extensions to Formal Concept Analysis / Entwurf und Beweis eines Algorithmus zur Berechnung inkrementeller Änderungen in einem beschrifteten dargestellten Begriffsverband beim Einfügen oder Entfernen einer Merkmalsspalte im zugrundeliegenden formalen Kontext. Weiterhin sind einige Details zur Implementation sowie zum mathematischen Hintergrundwissen dargestellt.:1 Introduction 1.1 Acknowledgements 1.2 Supporting University: TU Dresden, Institute for Algebra 1.3 Supporting Corporation: SAP AG, Research Center Dresden 1.4 Research Project: CUBIST 1.5 Task Description und Structure of the Diploma Thesis I Mathematical Details 2 Fundamentals of Formal Concept Analysis 2.1 Concepts and Concept Lattice 2.2 Visualizations of Concept Lattices 2.2.1 Transitive Closure and Transitive Reduction 2.2.2 Neighborhood Relation 2.2.3 Line Diagram 2.2.4 Concept Diagram 2.2.5 Vertical Hybridization 2.2.6 Omitting the top and bottom concept node 2.2.7 Actions on Concept Diagrams 2.2.8 Metrics on Concept Diagrams 2.2.9 Heatmaps for Concept Diagrams 2.2.10 Biplots of Concept Diagrams 2.2.11 Seeds Selection 2.3 Apposition of Contexts 3 Incremental Updates for Concept Diagrams 3.1 Insertion & Removal of a single Attribute Column 3.1.1 Updating the Concepts 3.1.2 Structural Remarks 3.1.3 Updating the Order 3.1.4 Updating the Neighborhood 3.1.5 Updating the Concept Labels 3.1.6 Updating the Reducibility 3.1.7 Updating the Arrows 3.1.8 Updating the Seed Vectors 3.1.9 Complete IFOX Algorithm 3.1.10 An Example: Stepwise Construction of FCD(3) 3.2 Setting & Deleting a single cross 4 Iterative Exploration of Concept Lattices 4.1 Iceberg Lattices 4.2 Alpha Iceberg Lattices 4.3 Partly selections 4.3.1 Example with EMAGE data 4.4 Overview on Pruning & Interaction Techniques II Implementation Details 5 Requirement Analysis 5.1 Introduction 5.2 User-Level Requirements for Graphs 5.2.1 Select 5.2.2 Explore 5.2.3 Reconfigure 5.2.4 Encode 5.2.5 Abstract/Elaborate 5.2.6 Filter 5.2.7 Connect 5.2.8 Animate 5.3 Low-Level Requirements for Graphs 5.3.1 Panel 5.3.2 Node and Edge 5.3.3 Interface 5.3.4 Algorithm 5.4 Mapping of Low-Level Requirements to User-Level Requirements 5.5 Specific Visualization Requirements for Lattices 5.5.1 Lattice Zoom/Recursive Lattices/Partly Nested Lattices 5.5.2 Planarity 5.5.3 Labels 5.5.4 Selection of Ideals, Filters and Intervalls 5.5.5 Restricted Moving of Elements 5.5.6 Layout Algorithms 5.5.7 Additional Feature: Three Dimensions and Rotation 5.5.8 Additional Feature: Nesting 6 FCAFOX Framework for Formal Concept Analysis in JAVA 6.1 Architecture A Appendix A.1 Synonym Lexicon A.2 Galois Connections & Galois Lattices A.3 Fault Tolerance Extensions to Formal Concept Analysis