Ανακάλυψη γνώσης από ακολουθίες και δεδομένα συναλλαγών

Abstract

Although “Knowledge Discovery in Databases” is a young field of research and application, having its roots in the late 1980s, it is already mature enough to offer useful analytical tools, embedded in popular software packages, for all kinds of busi-nesses and organizations. Its applications cover the entire spectrum of human activity, from healthcare and molecular biology to banking, commerce, industry and educa-tion. This growing variety of applications along with the vast amounts of storage and computing power available increases the need for more algorithms that are applica-tion-specific, faster and more effective. The importance of Knowledge Discovery in Databases (KDD) is further established by the fact that the progress and development of several fields (such as Molecular Biology) largely depends on its ability to deliver reliable and powerful techniques. Considering also that general purpose algorithms often fail to reach the performance standards set by real-world applications and the fact that KDD is a semi-automatic procedure that requires human guidance and inter-vention, one can understand the urgent need for new, specialized techniques as well as the improvement of existing ones. This thesis concerns a set of techniques for knowledge discovery from sequen-tial and transactional data. Both data categories share a common property, namely or-der, along (at least) one dimension. Specifically, two chapters of this thesis refer to the first data category. In the first one, a novel algorithm is proposed for the discov-ery of weak periodicities in discrete time series data. The algorithm is based on the circular autocorrelation function for the extraction of a refined set of candidate peri-odicities, used for mining periodic patterns. The second chapter that concerns sequen-tial data belongs to the research field of Bioinformatics. A new data mining metho-dology is developed for the prediction of the initiation site of the biological process of translation, in genome sequences. The proposed methodology identifies the main components of this problem and assigns a computational component to each separate-ly, in a modular fashion, achieving a high level of accuracy. The contribution of the thesis to knowledge discovery from transactional data is also twofold, covering two chapters. In the first one, a new algorithm is proposed for the prediction of rare events. The algorithm adopts an intuitive framework, em-beds the temporal information of the transaction in its items, delivering predictive patterns timely and effectively. In the second chapter of this category, the novel prob-lem of mining for mutually exclusive items is introduced and formulated and a set of metrics, along with a mining algorithm are provided.

Σήμερα, οι τεχνικές ανακάλυψης γνώσης από βάσεις δεδομένων έχουν πλέον ωριμάσει και ενσωματωθεί σε εμπορικά πακέτα λογισμικού για επιχειρήσεις και ορ-γανισμούς όλων των ειδών. Οι εφαρμογές της εκτείνονται από τον τομέα της υγείας, μέχρι τις τράπεζες, τις επιχειρήσεις, τον παγκόσμιο ιστό και τη μοριακή βιολογία, ακολουθώντας κατά πόδας τη διείσδυση της πληροφορικής σε όλους τους τομείς της ανθρώπινης δραστηριότητας. Η ολοένα και αυξανόμενη ποικιλία των εφαρμογών της σε συνδυασμό με την άφθονη επεξεργαστική ισχύ και τα διαθέσιμα μέσα αποθήκευ-σης, δημιουργούν την ανάγκη για ακόμα περισσότερες τεχνικές, ακόμα πιο εξειδι-κευμένους αλγορίθμους με ακόμα μεγαλύτερη αποτελεσματικότητα και ταχύτητα. Η εξέλιξη σε πολλούς τομείς, όπως η Μοριακή Βιολογία, εξαρτάται άμεσα από τη δια-θεσιμότητα και την απόδοση των αντίστοιχων εργαλείων ανακάλυψης γνώσης. Λαμ-βάνοντας μάλιστα υπόψη ότι οι αλγόριθμοι γενικής χρήσης δε μπορούν να αποδώ-σουν εξίσου καλά με τους εξειδικευμένους και πως η ανακάλυψη γνώσης είναι μια διαδικασία ημιαυτόματη, που εξαρτάται άμεσα από την καθοδήγηση του χρήστη, α-ντιλαμβάνεται κανείς την αναγκαιότητα ανάπτυξης νέων τεχνικών και βελτίωσης των υπαρχουσών. Η παρούσα διατριβή πραγματεύεται ένα σύνολο τεχνικών ανακάλυψης γνώ-σης από ακολουθίες και από δεδομένα συναλλαγών. Και οι δύο κατηγορίες δεδομέ-νων χαρακτηρίζονται από την ιδιότητα της διάταξης κατά μήκος μιας (τουλάχιστο) διάστασης. Συγκεκριμένα για την πρώτη κατηγορία, στην παρούσα διατριβή αναφέρονται δύο κεφάλαια. Στο πρώτο από αυτά προτείνεται ένας νέος αλγόριθμος για την ανακά-λυψη ασθενών περιοδικοτήτων σε βάσεις δεδομένων διακριτών χρονοσειρών. Ο προ-τεινόμενος αλγόριθμος βασίζεται στη συνάρτηση κυκλικής αυτοσυσχέτισης για την εξαγωγή ενός περιορισμένου συνόλου υποψήφιων περιόδων, που χρησιμοποιούνται για την εξόρυξη περιοδικών προτύπων. Το δεύτερο κεφάλαιο αυτής της κατηγορίας, εντάσσεται στο πλαίσιο της Βιοπληροφορικής. Προτείνεται μια νέα μεθοδολογία για την ακριβή πρόβλεψη του σημείου έναρξης της βιολογικής διαδικασίας της μετάφρα-σης σε μια γονιδιακή ακολουθία. Η μεθοδολογία αυτή προσεγγίζει το πρόβλημα με δομημένο τρόπο, ενσωματώνοντας βιολογική γνώση στη διαδικασία εξόρυξης, επι-τυγχάνοντας ιδιαίτερα υψηλά ποσοστά ακρίβειας. Στη δεύτερη κατηγορία δεδομένων (στις συναλλαγές) αφιερώνονται επίσης δύο κεφάλαια της διατριβής. Το πρώτο από αυτά περιλαμβάνει έναν νέο αλγόριθμο για την πρόβλεψη σπανίων γεγονότων σε μια βάση δεδομένων συναλλαγών. Ο αλγό-ριθμος αυτός ενσωματώνει τη χρονική (ή ακολουθιακή) πληροφορία της συναλλαγής στα αντικείμενα που περιέχει, ώστε να προβλέψει με ακριβή τρόπο την εμφάνιση ε-νός σπανίου αντικειμένου. Στο δεύτερο κεφάλαιο αυτής της κατηγορίας, ορίζεται ένα νέο πρόβλημα, εκείνο της ανακάλυψης αμοιβαίως αποκλειόμενων αντικειμένων από βάσεις δεδομένων συναλλαγών και προτείνονται κατάλληλες μετρικές, μαζί με έναν αλγόριθμο για την εξόρυξή τους.