Φιλτράρισμα και εξόρυξη δεδομένων σε αντικείμενα πληροφορίας

Abstract

The subject of this doctoral dissertation is the study of filtering and data mining problems in heterogeneous information objects. More specifically, the research focuses on how various filtering and data mining techniques can be used to solve significant problems arising from the rapid expansion of the internet, the growing demand for improved and personalized services for users, and the need to maintain the software systems that support this global explosion of information usage. Although these problems appear to be heterogeneous, they all stem from the overarching need to support and manage the rapid global spread of web-based information. Data mining techniques, with their broad applicability across different types of data, present an ideal solution to the aforementioned challenges. In recent years, substantial research has been conducted on how to apply these techniques to web usage data as well as XML data. Furthermore, there is growing interest in their application to software evaluation, where the source code files of a software system serve as the data source, in order to detect and address issues early. XML (eXtensible Markup Language) has become the standard for data representation on the Web. The explosive growth of data represented in XML created a need for efficient search within the hierarchical structure of XML documents to locate specific information. This requirement, along with the need for fast access to XML tree nodes, led to the development of specialized indexes. These indexes must be dynamic to adapt to the evolving nature of the data. Additionally, due to the need to retrieve specific information, it is essential to filter XML datasets using predefined patterns and rules to identify data matching these criteria. At the same time, the clustering of large volumes of XML data for further processing necessitates intelligent and efficient grouping algorithms, which must be tailored to both the semi-structured nature of XML and the actual content it represents. Moreover, the vast amount of data to be processed makes distributed management in peer-to-peer (P2P) networks increasingly attractive, as it provides advantages such as load balancing and distributed storage. The internet's rapid expansion has also led to efforts to enhance the services offered by websites to better serve their users. Personalizing the presented content requires a thorough study of user behavior as reflected in website usage data (clickstreams). Discovering common behavior patterns among users can only be achieved through the application of suitable data mining algorithms. Additionally, the dimensions of internal, external, and usage quality of a software product evolve throughout its lifecycle. For example, quality at the start of the lifecycle emphasizes external and user-centric aspects, which differ from internal aspects such as design quality that concern software engineers. Data mining techniques aimed at achieving the necessary quality levels (e.g., quality assessment) must take these dimensions into account at each stage of the product lifecycle. In this context, the dissertation's research focuses on identifying the specific challenges posed by XML data and on designing efficient algorithms for filtering, clustering, and managing XML data in peer-to-peer networks. Furthermore, it examines how to process and extract knowledge from web usage data to enable the delivery of personalized information to users. This part of the research emphasizes effective user clustering based on browsing history and the definition of a similarity metric between users using their historical data. Lastly, the dissertation addresses the application of data mining techniques to source code metrics of a software system to assess their quality and identify potential issues early. Research in this area focused on designing a clustering algorithm for source code metrics, enabling the grouping of code components (packages, classes, functions) based on quality, and introducing a new methodology for the overall assessment of a complete software system. Key research contributions include: - Efficient XML data filtering algorithms applicable to publish-subscribe systems for delivering only user-relevant information. -Novel clustering algorithms for large volumes of XML data across different levels using data mining methods. -A new model for managing distributed XML data in peer-to-peer networks for optimal distributed search and retrieval. This model uses new XML clustering algorithms for optimal data distribution and distributed Bloom Filters for more efficient query routing.- A clustering algorithm focused on software quality evaluation metrics to assist system analysts in the early detection and resolution of source code quality issues.- Efficient data mining algorithms for web usage data utilizing multi-level data clustering techniques.

Αντικείμενο της παρούσας διδακτορικής διατριβής είναι η μελέτη προβλήματων φιλτραρίσματος και εξόρυξης δεδομένων σε ετερογενή αντικείμενα πληροφορίας. Πιο συγκεκριμένα, η έρευνα επικεντρώθηκε στο πως οι διάφορες τεχνικές φιλτραρίσματος και εξόρυξης δεδομένων μπορούν να χρησιμοποιηθούν για την επίλυση σημαντικών προβλημάτων που προκύπτουν από την ραγδαία εξάπλωση του διαδικτύου, την ολοένα και αυξανόμενη ζήτηση για παροχή καλύτερων και προσωποποιημένων υπηρεσιών στους χρήστες καθώς και στην ανάγκη συντήρησης των συστημάτων λογισμικού που καλούνται να υποστηρίξουν την παγκόσμια αυτή έκρηξη στην χρήση της πληροφόρησης. Τα προβλήματα αυτά μοιάζουν να είναι ετερογενή μεταξύ τους, αλλά στην πραγματικότητα και τα τρία προκύπτουν από την ανάγκη να υποστηριχθεί και να εξυπηρετηθεί η ραγδαία αυτή εξάπλωση της δικτυακής πληροφόρησης παγκοσμίως. Οι τεχνικές Εξόρυξης Δεδομένων, με την ευρεία εφαρμογή τους σε διαφόρων ειδών δεδομένα, παρουσιάζουν ως μια ιδανική λύση στα προβλήματα που αναφέρθηκαν προηγουμένως. Τα τελευταία χρόνια, αρκετή έρευνα έχει διεξαχθεί στο πως μπορούν να εφαρμοσθούν σε δεδομένα χρήσης του παγκοσμίου ιστού, καθώς και σε XML δεδομένα. Επίσης ενδιαφέρον υπάρχει και κατά την αξιολόγηση λογισμικού όπου η πηγή δεδομένων είναι τα αρχεία πηγαίου κώδικα ενός συστήματος λογισμικού, ώστε να αναγνωρισθούν και να επιλυθούν έγκαιρα τυχόν προβλήματα. Η eXtensible Markup Language (XML) είναι το πρότυπο για αναπαράσταση δεδομένων στον Παγκόσμιο Ιστό. Η ραγδαία αύξηση του όγκου των δεδομένων που αναπαρίστανται σε XML δημιούργησε την ανάγκη αναζήτησης μέσα στην δενδρική δομή ενός ΧΜL εγγράφου για κάποια συγκεκριμένη πληροφορία. Η ανάγκη αυτή ταυτόχρονα με την ανάγκη για γρήγορη πρόσβαση στους κόμβους του ΧΜL δέντρου, οδήγησε σε διάφορα εξειδικευμένα ευρετήρια. Για να μπορέσουν να ανταποκριθούν στη δυναμική αυτή των δεδομένων, τα ευρετήρια πρέπει να έχουν τη δυνατότητα να μεταβάλλονται δυναμικά. Επίσης, λόγω της απαίτησης για αναζήτηση συγκεκριμένης πληροφορίας είναι απαραίτητο το φιλτράρισμα ενός συνόλου XML δεδομένων διαμέσου κάποιων προτύπων και κανόνων ώστε να βρεθούν εκείνα τα δεδομένα που ταιριάζουν με τα αποθηκευμένα πρότυπα και κανόνες. Ταυτόχρονα, η ανάγκη συσταδοποίησης ενός μεγάλου όγκου XML δεδομένων για περαιτέρω επεξεργασία, κάνει απαιτητική την ανάγκη εφαρμογής έξυπνων και αποδοτικών αλγορίθμων ομαδοποίησης, οι οποίοι θα είναι προσαρμοσμένοι τόσο στην ημι-δομημένη φύση της XML όσο και στο πραγματικό περιεχόμενο το οποίο αναπαριστά [1]. Τέλος, λόγω του μεγάλου όγκου δεδομένων που πρέπει να επεξεργαστούν, η κατανεμημένη διαχείριση σε δίκτυα ομότιμων κόμβων (P2P) γίνεται ολοένα και πιο ελκυστική καθώς προσφέρει πολλά πλεονεκτήματα όπως επιμερισμό του φόρτου εργασίας καθώς και κατανομή τουαποθηκευτικού χώρου. Επιπλέον, η ραγδαία εξάπλωση του διαδικτύου οδήγησε και σε μια προσπάθεια αναβάθμισης των υπηρεσιών που παρέχουν οι διάφοροι ιστότοποι, με στόχο την καλύτερη εξυπηρέτηση των χρηστών που τους επισκέπτονται. Η πρόσπαθεια εξατομίκευσης του προβαλλόμενου περιεχομένου προϋποθέτει μια ενδελεχή μελέτη της συμπεριφοράς των χρηστών, όπως αυτή αποτυπώνεται από τα δεδομένα χρήσης (clickstreams) του δικτυακού ιστοτόπου. Η εύρεση κοινών προτύπων συμπεριφοράς μεταξύ των χρηστών μπορεί μόνο να επιτευχθεί με την εφαρμογή κατάλληλων αλγόρίθμων εξόρυξης δεδομένων. Τέλος οι διαστάσεις της εσωτερικής, της εξωτερικής και της ποιότητας στη χρήση ενός προϊόντος λογισμικού αλλάζουν κατά τη διάρκεια ζωής του. Για παράδειγμα η ποιότητα όπως ορίζεται στην αρχή του κύκλου ζωής του λογισμικού δίνει πιο πολλή έμφαση στην εξωτερική και σε αυτή του χρήστη και διαφέρει από την εσωτερική ποιότητα, όπως η ποιότητα της σχεδίασης η οποία είναι εσωτερική και αφορά τους μηχανικούς λογισμικού. Οι τεχνικές εξόρυξης δεδομένων που μπορούν να χρησιμοποιηθούν για την επίτευξη του απαραίτητου επιπέδου ποιότητας, όπως είναι η αξιολόγηση της ποιότητας πρέπει να λαμβάνουν υπόψιν τους τις διαφορετικές αυτές διαστάσεις σε κάθε στάδιο του κύκλου ζωής του προϊόντος. Στα πλαίσια αυτής της διδακτορικής διατριβής η έρευνα επικεντρώθηκε στην αναγνώριση των ιδιαιτέρων προβλημάτων και προκλήσεων που εισάγουν τα XML δεδομένα ώστε να σχεδιαστούν αποδοτικοί αλγόριθμοι φιλταρίσματος, συσταδοποίησης και διαχείρισης XML δεδομένων σε δίκτυα ομότιμων κόμβων. Επιπλέον, μελετήθηκε το πρόβλημα της επεξεργασίας και εξόρυξης γνώσης από δεδομένα χρήσης του διαδικτύου ώστε να γίνει εφικτή η παροχή προσωποποιημένων πληροφοριών στον χρήστη. Η έρευνα στον τομέα αυτό επικεντρώθηκε στο πως μπορεί να γίνει αποδοτική ομαδοποίηση των χρηστών με βάση το ιστορικό τους σε ένα δικτυακό τόπο καθώς και στο πως μπορεί να οριστεί μια μετρική ομοιότητας μεταξύ δύο χρηστών κάνοντας χρήση του ιστορικού τους. Τέλος, μελετήθηκε το πρόβλημα της εφαρμογής τεχνικών εξόρυξης δεδομένων σε μετρικές πηγαίου κώδικα ενός συστήματος λογισμικού ώστε να γίνει δυνατή η αξιολόγηση της ποιότητάς τους και η έγκαιρη αναγνώριση τυχόν προβλημάτων. Η έρευνα στον τομέα αυτό επικεντρώθηκε στην σχεδίαση ενός αλγορίθμου συσταδοποίησης για μετρικές πηγαίου κώδικα, ώστε τα συστατικά στοιχεία του πηγαίου κώδικα (πακέτα, κλάσεις, συναρτήσεις) να μπορούν να ομαδοποιηθούν ανάλογα με την ποιότητά τους, καθώς και στην εισαγωγή μιας νέας μεθοδολογίας για την συνολική αξιολόγηση ενός ολοκληρωμένου συστήματος λογισμικού. Τα ερευνητικά αποτελέσματα της εργασίας αυτής επικεντρώνονται στα ακόλουθα: • Αποδοτικοί αλγόριθμοι φιλταρίσματος δεδομένων σε μορφή XML, οι οποίοι μπορούν να εφαρμοσθούν σε συστήματα δημοσιεύσεων-συνδρομητών για την προώθηση στους χρήστες μόνο σχετικής με τα ενδιαφέροντά τους πληροφορίας. [3] [5] • Καινοτόμοι αλγόριθμοι συσταδοποίησης μεγάλου όγκου XML δεδομένων σε διαφορετικά επίπεδα με χρήση αλγορίθμων εξόρυξης δεδομένων. [4] • Νέο μοντέλο διαχείρισης διαμοιρασμένων XML δεδομένων σε δίκτυα ομότιμων κόμβων για βέλτιστη κατανεμημένη αναζήτηση και ανάκτηση των επιθυμητών δεδομένων. Το προτεινόμενο μοντέλο κάνει χρήση των νέων αλγόριθμων ομαδοποίησης XML δεδομένων ώστε να επιτύχει την βέλτιστη κατανομή των δεδομένων στους κόμβους ενός δικτύου καθώς και κατανεμημένα Bloom Filters για αποδοτικότερη δρομολόγηση των ερωτημάτων. [2] • Νέος αλγόριθμος συσταδοποίησης εστιασμένος σε μετρικές αξιολόγησης της ποιότητας ενός συστήματος λογισμικού με σκοπό τη διευκόλυνση των αναλυτών συστημάτων για την έγκαιρη διάγνωση και αντιμετώπιση προβλημάτων που σχετίζονται με την ποιότητα του πηγαίου κώδικα. [8] [10] [11] • Αποδοτικοί αλγόριθμοι εξόρυξης δεδομένων σε δεδομένα χρήσης στον παγκόσμιο ιστό με χρήση πολλαπλών επιπέδων ομαδοποίηση δεδομένων. [6] [7]