Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/272
Title: Αποδοτικοί αλγόριθμοι εξατομίκευσης βασισμένοι σε εξόρυξη γνώσης απο δεδομένα χρήσης Web
Other Titles: Effective personalization algorithms based on Web usage mining
Authors: Ρήγκου, Μαρία
Issue Date: 2007-06-25T06:12:31Z
Keywords: Εξατομίκευση
Αλγόριθμος
Εξόρυξη γνώσης
Παγκόσμιος ιστός
Keywords (translated): Personalization
Algorithm
Data mining
Web
Abstract: Το Web αποτελεί πλέον µια τεράστια αποθήκη πληροφοριών και συνεχίζει να µεγαλώνει εκθετικά, ενώ η ανθρώπινη ικανότητα να εντοπίζει, να επεξεργάζεται και να αντιλαµβάνεται τις πληροφορίες παραµένει πεπερασµένη. Το πρόβληµα στις µέρες µας δεν είναι η πρόσβαση στην πληροφορία, αλλά το ότι όλο και περισσότεροι άνθρωποι µε διαφορετικές ανάγκες και προτιµήσεις πλοηγούνται µέσα σε περίπλοκες δοµές Web χάνοντας στην πορεία το στόχο της αναζήτησής τους. Η εξατοµίκευση, µια πολυσυλλεκτική ερευνητική περιοχή, αποτελεί µια από τις πιο πολλά υποσχόµενες προσεγγίσεις για τη λύση του προβλήµατος του πληροφοριακού υπερφόρτου, παρέχοντας κατάλληλα προσαρµοσµένες εµπειρίες πλοήγησης. Η διατριβή εξετάζει αλγοριθµικά θέµατα που σχετίζονται µε την υλοποίηση αποδοτικών σχηµάτων εξατοµίκευσης σε περιβάλλον web, βασισµένων σε εξόρυξη γνώσης από δεδοµένα χρήσης web. Οι τεχνικές ανακάλυψης προτύπων που µελετώνται περιλαµβάνουν το clustering, την εξόρυξη κανόνων συσχέτισης και την ανακάλυψη σειριακών προτύπων, ενώ οι προτεινόµενες λύσεις εξατοµίκευσης που βασίζονται στις δύο τελευταίες τεχνικές συνδυάζουν τα δεδοµένα χρήσης µε δεδοµένα περιεχοµένου και δοµής. Ειδικότερα, στο πρώτο κεφάλαιο της διατριβής, ορίζεται το επιστηµονικό πεδίο των σύγχρονων τεχνολογιών εξατοµίκευσης στο περιβάλλον του web, εστιάζοντας στη στενή σχέση τους µε το χώρο του web mining, στοιχειοθετώντας µε αυτό τον τρόπο το γενικότερο πλαίσιο αναφοράς. Στη συνέχεια, περιγράφονται τα διαδοχικά στάδια της τυπικής διαδικασίας εξατοµίκευσης µε έµφαση στη φάση ανακάλυψης προτύπων και τις τεχνικές machine learning που χρησιµοποιούνται σε δεδοµένα χρήσης web και το κεφάλαιο ολοκληρώνεται µε µια συνοπτική περιγραφή της συµβολής της διατριβής στο πεδίο της εξατοµίκευσης σε περιβάλλον web. Στο δεύτερο κεφάλαιο προτείνεται ένας αλγόριθµος για εξατοµικευµένο clustering, που βασίζεται σε µια δοµή range tree που διατρέχεται σε πρώτη φάση για τον εντοπισµό των web αντικειµένων που ικανοποιούν τα ατοµικά κριτήρια του χρήστη. Στα αντικείµενα αυτά, εφαρµόζεται στη συνέχεια clustering, ώστε να είναι δυνατή η αποδοτικότερη διαχείρισή τους και να διευκολυνθεί η διαδικασία λήψης αποφάσεων από πλευράς χρήστη. O αλγόριθµος που προτείνεται αποτελεί βελτίωση του αλγόριθµου kmeans range, καθώς εκµεταλλεύεται το range tree που έχει ήδη κατασκευαστεί κατά το βήµα της εξατοµίκευσης και το χρησιµοποιεί ως τη βασική δοµή πάνω στην οποία στηρίζεται το βήµα του clustering χρησιµοποιώντας εναλλακτικά του k-means, τον αλγόριθµο k-windows. Ο συνολικός αριθµός παραµέτρων που χρησιµοποιούνται για την µοντελοποίηση των αντικειµένων υπαγορεύει και τον αριθµό των διαστάσεων του χώρου εργασίας. Η συνολική πολυπλοκότητα χρόνου του αλγορίθµου είναι ίση µε O(logd-2n+v), όπου n είναι ο συνολικός αριθµός των στοιχείων που δίνονται σαν είσοδος και v είναι το µέγεθος της απάντησης. Στο τρίτο κεφάλαιο της διατριβής προτείνεται ένα αποδοτικό σχήµα πρόβλεψης µελλοντικών δικτυακών αιτήσεων βασισµένο στην εξόρυξη σειριακών προτύπων πλοήγησης (navigation patterns) από αρχεία server log, σε συνδυασµό µε την τοπολογία των συνδέσµων του website και τη θεµατική κατηγοριοποίηση των σελίδων του. Τα µονοπάτια που ακολουθούν οι χρήστες κατά την πλοήγηση καταγράφονται, συµπληρώνονται µε τα κοµµάτια που λείπουν λόγω caching και διασπώνται σε συνόδους και σε επεισόδια, ώστε να προκύψουν σηµασιολογικά πλήρη υποσύνολά τους. Τα πρότυπα που εντοπίζονται στα επεισόδια µοντελοποιούνται µε τη µορφή n-grams και οι αποφάσεις πρόβλεψης βασίζονται στη λογική ενός µοντέλου n-gram+ που προσοµοιάζει το all Kth-τάξης µοντέλο Markov και πιο συγκεκριµένα, το επιλεκτικό µοντέλο Markov. Η υβριδική προσέγγιση που υιοθετεί το προτεινόµενο σχήµα, επιτυγχάνει 100% coverage, ενώ κατά τις πειραµατικές µετρήσεις το άνω όριο της ακρίβειας έφθασε το 71,67% στο σύνολο των προβλέψεων που επιχειρήθηκαν. Το χαρακτηριστικό του πλήρους coverage καθιστά το σχήµα κατάλληλο για συστήµατα παραγωγής συστάσεων, ενώ η ακρίβεια µπορεί να βελτιωθεί περαιτέρω αν µεγαλώσει το παράθυρο πρόβλεψης. Στο τέταρτο κεφάλαιο της διατριβής, εξετάζεται η ενσωµάτωση λειτουργιών εξατοµίκευσης στις ηλεκτρονικές µαθησιακές κοινότητες και προτείνεται ένα σύνολο από δυνατότητες εξατοµίκευσης που διαφοροποιούνται ως προς τα δεδοµένα στα οποία βασίζονται, την τεχνική εξόρυξης προτύπων που χρησιµοποιούν και την αντίστοιχη πολυπλοκότητα υλοποίησης. Οι υπηρεσίες αυτές περιλαµβάνουν: (α) εξατοµίκευση µε βάση το ρόλο του χρήστη, (β) εξατοµίκευση µε βάση το βαθµό δραστηριοποίησης του χρήστη, (γ) εξατοµίκευση µε βάση την ανακάλυψη προτύπων στα ατοµικά ιστορικά µελέτης των εκπαιδευόµενων και (δ) εξατοµίκευση µε βάση συσχετίσεις του περιεχοµένου των µαθηµάτων.
Abstract (translated): The Web has become a huge repository of information and keeps growing exponentially under no editorial control, while the human capability to find, read and understand content remains constant. Providing people with access to information is not the problem; the problem is that people with varying needs and preferences navigate through large Web structures, missing the goal of their inquiry. Web personalization is one of the most promising approaches for alleviating this information overload, providing tailored Web experiences. The present dissertation investigates algorithmic issues concerning the implementation of effective personalization scenarios in the web environment, based on web usage mining. The pattern discovery techniques deployed comprise clustering, association rule mining and sequential pattern discovery, while the proposed personalization schemas based on the latter two techniques integrate usage data with content and structure information. The first chapter introduces the scientific field of current web personalization technology, focusing on its close relation with the web mining domain, providing this way the general framework of the dissertation. Next, the typical web personalization process is described with emphasis on the pattern discovery phase along with an overview of the machine learning techniques applied on web usage data. The chapter concludes with a synoptic description of the contribution of the dissertation to web personalization research and applications domian. The second chapter introduces an algorithm for personalized clustering based on a range tree structure, used for identifying all web objects satisfying a set of predefined personal user preferences. The returned objects go through a clustering phase before reaching the end user, thus allowing more effective manipulation and supporting the decision making process. The proposed algorithm improves the k-means range algorithm, as it uses the already constructed range tree (i.e. during the personalized filtering phase) as the basic structure on which the clustering step is based, applying instead of the kmeans, the k-windows algorithm. The total number of parameters used for modeling the web objects dictates the number of dimensions of the Euclidean space representation. The time complexity of the algorithm is O(logd-2n+v), where d is the number of dimensions, n is the total number of web objects and v is the size of the answer. The third chapter proposes an effective prediction schema for web requests based on extracting sequential navigational patterns from server log files, combined with the website link structure and the thematic categorization of its content pages. The schema records the paths followed by users when browsing through the website pages, completes them with the missing parts (due to caching) and identifies sessions and episodes, so as to derive meaningful path subsets. The patterns extracted from the episodes are modeled in the form of n-grams and the prediction decisions are based on an n-gram+ model that resembles an all Kth-order Markov model and more specifically a selective Markov model. The hybrid approach adapted achieves full-coverage prediction, and reached the upper limit of 71,67% presicion when tested at an experimental setting. The full-coverage feature makes the proposed schema quite suitable for recommendation engines, while precision is further improved when using a larger prediction window. The fourth chapter examines the integration of personalized functionalities in the framework of electronic learning communities and studies the advantages derived from generating dynamic adaptations on the layout, the content as well as the learning scenarios delivered to each community student based on personal data, needs and preferences. More specifically, the chapter proposes a set of personalization functions differentiated by the data they use, the pattern discovery technique they apply and the resulting implementation complexity. These services comprise: (a) personalization based on the user role in the community, (b) personalization based on the level of user activity, (c) personalization based on discovery of association rules in the personal progress files of students, and (d) personalization based on predefined content correlations among learning topics.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΔΔ)

Files in This Item:
File Description SizeFormat 
200.pdf2.57 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.