Μελέτη μεθοδολογιών παραλληλισμού για την υλισμική απεικόνιση της άλγεβρας δυαδικών σχέσεων και κανόνων από δένδρα αποφάσεων

Abstract

During the operation of an object oriented information system, the objects derived are holding references one of another. These objects can be viewed as interconnected forming relationships amongst them. A set of interconnected objects can also be considered as a set of pairs of objects, since the pairing implies a relation (connection) between the pair members. A binary relation is defined as a set of such object pairs. The algebra of binary relations (Tarski 1941, Chin 1951, Jonsson 1951, Jonsson 1952, Tarksi 1987, Givant 1994) can provide an algebraic framework (Sarathy 1993, Gyssens 1994a, Van den Bussche 2001) for manipulating object oriented databases. Previous attempts to use the algebra of binary relations for object manipulation purposes resulted in graph-oriented systems, where graphs were used for querying, browsing, updating and restructuring object databases (Gyssens 1990, Gyssens 1994b, Sarathy 1993) or architectures of software systems (Hold 1998). In this dissertation, instead of using graphs, an extension to the OQL of the ODMG’s object data standard 3.0 for incorporating binary relational expressions for query declarations is proposed. In this proposal, the introduction of simple and multiple merged chains of binary relations in query declarations extends the concept of relation composition, which is defined by the binary relational algebra. A Semi- Dewavefront-like Algorithm, which is mapped on a Bidirectional Multi- Functional Engine-BMFE is also introduced for efficient query execution purposes. This algorithm (and engine) processes the simple and multiple merged chains of binary relations introduced in the OQL extension and declared in queries. The basic elements of the architecture of this engine can be of two types of array processors, a synchronous Square Systolic Device (for Wavefront-like Computations) - S2DWC and an asynchronous Bi-directional Parallel Cubic Engine - BPCE. These array processors are the mappings of the semi-group structure of the binary relational algebra. The multifunctional engine is an extension of this mapping, since it processes, across multiple directions, multiple relations structured as simple or multiple merged chains. These systems were designed and extensively tested using environments provided by suitable VHDL tools and were FPGA implemented virtually producing hybrid systems, composed by both software and hardware (middleware). Decision trees or rules that are derived from machine learning algorithms can be further processed, especially if they are of special forms that serve concrete needs. Data accessing via decision trees is also investigated in this dissertation, through a proposed algorithm for the extraction of rules from decision trees with complex nominal data that could be even in the form of free text. The goal of the algorithm is to process a decision tree generated using the classification algorithm ID3, which processed data in natural language expressions form and to extract rules expressed in natural language. In this case, the algorithm’s input tree is full of complex nominal expressions. Since this tree is of unknown form and size, it cannot be easily processed using parallel techniques. However, it does not apply for the hardware mapping of the rules themselves. Herein are investigated certain parallel methodologies which are applied in the design and implementation of a chip that is able to recognize and classify patterns of medical measures relative to the breast cancer disease. This chip called Integrated Intelligent Medical Classification Engine - I2MCE was FPGA implemented and extensively tested in a VHDL environment. Measures taken from the patient are fed into this chip that recognizes them according to the classification rules incorporated in its design. The result achieved concerns the nature of the cancer under examination, namely, benign or malignant. A parallel program that simulates the medical diagnostic chip exhibits the parallelism of these methodologies. The program is implemented using the threads and the inter-thread communication of the java programming language. A series of similar medical diagnostic chips can be designed and implemented for a number of diseases using the introduced methodologies. These chips can be incorporated in portable microdevices that can be used by doctors and health care professionals in general for diagnosis decision support purposes.

Κατά την λειτουργία ενός αντικειμενοστρεφούς πληροφορικού συστήματος, τα αντικείμενα τα οποία παράγονται συγκρατούν αναφορές το ένα του άλλου. Αυτά τα αντικείμενα μπορούν να θεωρηθούν ως διασυνδεδεμένα σχηματίζοντας σχέσεις μεταξύ τους. Ένα σύνολο από διασυνδεδεμένα αντικείμενα μπορεί επίσης να θεωρηθεί ως ένα σύνολο από ζεύγη αντικειμένων, επειδή η ύπαρξη σχέσης (διασύνδεσης) μεταξύ των μελών ενός ζεύγους υπονοείται. Τα αντικείμενα περιέχουν ενθυλακωμένες πληροφορίες, μπορούν να αποθηκευτούν, να ανακληθούν και οι ενθυλακωμένες πληροφορίες τους να ανακτηθούν. Αυτές τις ιδιότητες των αντικειμένων αξιοποιούν οι αντικειμενοστρεφείς βάσεις δεδομένων. Η άλγεβρα των δυαδικών σχέσεων (Tarski 1941, Chin 1951, Jonsson 1951, Jonsson 1952, Tarksi 1987, Givant 1994) μπορεί να προσφέρει ένα αλγεβρικό πλαίσιο για την διαχείριση (Sarathy 1993, Gyssens 1994a, Van den Bussche 2001) των αντικειμενοστρεφών βάσεων δεδομένων Προηγούμενες προσπάθειες για τη χρήση της άλγεβρας των δυαδικών σχέσεων για σκοπούς διαχείρισης αντικειμένων κατέληξαν σε γραφικώς προσανατολισμένα συστήματα, όπου τα γραφήματα χρησιμοποιούνταν για ερωτήματα, αναζητήσεις και ενημερώσεις αντικειμενοστρεφών βάσεων (Gyssens 1990, Gyssens 1994b, Sarathy 1993) ή επαναδομήσεις αρχιτεκτονικών λογισμικού (Hold 1998). Σε αυτή την διατριβή, αντί της χρήσης γραφημάτων προτείνεται η επέκταση της γλώσσας ερωτήσεων αντικειμένων της ομάδας διαχείρισης αντικειμένων δεδομένων (ODMG’s OQL) με δυαδικές σχεσιακές αλγεβρικές εκφράσεις για να χρησιμοποιηθεί για διατυπώσεις ερωτήσεων προς αντικειμενοστρεφείς βάσεις. Σε αυτή την πρόταση η εισαγωγή απλών και συγχωνευμένων πολλαπλών αλυσίδων δυαδικών σχέσεων, στις διατυπώσεις ερωτήσεων, επεκτείνει την έννοια της σύνθεσης σχέσεων, η οποία ορίζεται στην άλγεβρα δυαδικών σχέσεων. Σχηματίζεται έτσι ένα δηλωτικό μοντέλο υποβολής ερωτήσεων προς αντικειμενοστρεφείς βάσεις. Ένας Αλγόριθμος Διπλού (Πολλαπλού) Άκρου Οιωνεί Κυματομετώπης, ο οποίος απεικονίζεται σε μια Αμφίδρομη Πολυλειτουργική Μηχανή προτείνεται για την αποδοτική εκτέλεση αυτών των ερωτήσεων. Αυτός ο αλγόριθμος (και η πολυλειτουργική μηχανή) επεξεργάζεται τις απλές και πολλαπλές συγχωνευμένες αλυσίδες δυαδικών σχέσεων που προτάθηκαν στην επέκταση της OQL και δηλώνονται στα ερωτήματα. Τα βασικά στοιχεία της αρχιτεκτονικής αυτής της μηχανής μπορεί να είναι δύο τύποι διατάξεων επεξεργαστών: μια σύγχρονη Τετραγωνική Συστολική Συσκευή για Υπολογισμούς Οιωνεί Κυματομετώπης και μια ασύγχρονη Αμφίδρομη Παράλληλη Κυβική Μηχανή. Αυτές οι διατάξεις επεξεργαστών είναι οι απεικονίσεις της δομής της ημιομάδας της δυαδικής σχεσιακής άλγεβρας. Η πολυλειτουργική μηχανή είναι μια επέκταση αυτής της απεικόνισης, αφού επεξεργάζεται κατά όλες τις διευθύνσεις, πολυάριθμες σχέσεις δομημένες ως απλές η συγχωνευμένες πολλαπλές αλυσίδες. Αυτά τα συστήματα σχεδιάστηκαν, τα επί μέρους τμήματά τους δοκιμάστηκαν εκτεταμένα και υλοποιήθηκαν με προγραμματιζόμενους πίνακες πυλών (FPGAs) σε περιβάλλοντα παρεχόμενα από κατάλληλα VHDL εργαλεία, γεγονός που μπορεί να οδηγήσει σε υβριδικά συστήματα συντιθέμενα από λογισμικό και υλισμικό. Για κάθε αντικειμενοστρεφές πληροφορικό σύστημα μια πολυλειτουργική μηχανή μαζί με τις δύο εναλλακτικές διατάξεις επεξεργαστών που χρησιμοποιεί μπορεί να σχεδιαστεί και να υλοποιηθεί με τη χρήση των ερευνώμενων μεθοδολογιών. Δένδρα αποφάσεων και κανόνες που παράγονται από αλγόριθμους μηχανικής μάθησης μπορούν να επεξεργαστούν περαιτέρω, ιδίως εάν είναι ειδικών μορφών και εξυπηρετούν συγκεκριμένες ανάγκες. Η πρόσβαση σε δεδομένα μέσω δένδρων αποφάσεων ερευνάται επίσης σε αυτήν την διατριβή, με ένα προτεινόμενο αλγόριθμο για την εξαγωγή κανόνων από δένδρα αποφάσεων πλήρη φυσικών εκφράσεων. Ο σκοπός του αλγόριθμου είναι να επεξεργάζεται τέτοια δένδρα αποφάσεων τα οποία είναι δυσανάγνωστα και τα οποία δημιουργούνται από την χρήση του αλγόριθμου ταξινόμησης ID3 που τροποποιούμενος κατάλληλα μπορεί να δεχθεί στην είσοδό του δεδομένα με σύνθετες λεκτικές εκφράσεις. ..........................