Spelling suggestions: "subject:"κέντρα"" "subject:"κέντρο""
1 |
Μελέτη και ανάπτυξη αυτοοργανώμενων δομών δεδομένωνΑντωνίου, Δημήτριος 26 February 2009 (has links)
Θέμα της παρούσης διπλωματικής εργασίας αποτελεί η μελέτη, ανάπτυξη
και πειραματική επιβεβαίωση αλγοριθμικών τεχνικών για την σχεδίαση
αυτοοργανώμενων δομών δεδομένων (self-organizing data structures) και η
ανάπτυξη τυχαιοποιημένων εκδόσεών τους.
Μια αυτοοργανώμενη δομή δεδομένων διαθέτει κάποιον αλγόριθμο για να
αναδιοργανώνει τους δείκτες και τα δεδομένα κατάστασης μετά από κάθε
πρόσβαση ή πράξη . Ο αλγόριθμος αυτοοργάνωσης είναι σχεδιασμένος ώστε
αντιδρώντας σε αρχικά άγνωστες ιδιότητες της ακολουθίας αιτήσεων (request
sequence), να οδηγεί τη δομή δεδομένων σε κατάσταση πλεονεκτική για τις
ιδιότητες της ακολουθίας με αποτέλεσμα τη μείωση του χρόνου που χρειάζεται
στο μέλλον ανά πράξη. Ο πρώτος αλλά και ο μόνος μέχρι σήμερα πιθανός υποψήφιος
αλγόριθμος αναζήτησης σε δένδρο που μπορεί να είναι Ο(1)-ανταγωνιστικός
είναι το splay δένδρο (splay tree) που παρουσιάστηκε από τους Sleator και
Tarjan [1]. Στην εργασία των Sleator και Tarjan παρουσιάζονται κάποιες
εικασίες, οι οποίες δεν έχουν αποδειχθεί. Σημαντικότερη είναι η εικασία
δυναμικής βελτιστότητας (dynamic optimality conjecture) σύμφωνα με την οποία
το splay δένδρο είναι Ο(1)-ανταγωνιστικό. Η εικασία δυναμικής δακτυλοδότησης
(dynamic finger conjecture) και η εικασία διαπέρασης (traversal conjecture) είναι
αληθείς, αν είναι αληθής η εικασία δυναμικής βελτιστότητας. Ο Cole [3], [4]
προσπάθησε να αποδείξει την ορθότητα της εικασίας δυναμικής δακτυλοδότησης
σε μια από τις σημαντικότερες εργασίες για τα splay δένδρα. O J. Iacono [2]
ανέπτυξε εναλλακτικές δομές δεδομένων που έχουν χρόνο χειρότερης
περίπτωσης ανά πράξη (και όχι επιμερισμένο κόστος) της τάξης του Ο(logn), σε
αντιδιαστολή με τον Ο(n) χρόνο χειρότερης περίπτωσης των splay trees. Σε
αντιπαράθεση με τη δομή του Iacono, οι Mihai Badoiu και Erik D. Demaine
παρουσίασαν μια δυναμική δομή αναζήτησης[7], η οποία επιτυγχάνει την
ενοποιημένη ιδιότητα και που είναι απλούστερη από τη δομή του Iacono. Μεταξύ
όλων των δυναμικών δομών αναζήτησης με βάση τις συγκρίσεις , η
συγκεκριμένη δομή έχει τον καλύτερο χρόνο εκτέλεσης. Εκτός της παραπάνω
δομής, ο Demaine ανέπτυξε ένα Ο(loglogn) ανταγωνιστικό online δυαδικό δέντρο
αναζήτησης[5] , βελτιώνοντας το μέχρι πρότινος βέλτιστο ανταγωνιστικό
ποσοστό της τάξης Ο(logn). Αυτή είναι η πρώτη μεγάλη βελτίωση της εικασίας
δυναμικής βελτιστότητας (dynamic optimality conjecture) των Sleator και Tarjan ,
σύμφωνα με την οποία υπάρχουν Ο(1) ανταγωνιστικά δυαδικά δέντρα
αναζήτησης. Σε σχέση με τη δυναμική βελτιστότητα των Splay trees, σημαντική
συνεισφορά αποτελεί και η εργασία του George F. Georgakopoulos[6]. Ο
George F. Georgakopoulos παρουσιάζει μια επέκταση της splay τεχνικής , την
οποία ονομάζει chain-splay(αλυσιδωτό splay) . Τα chain-splay δέντρα
εφαρμόζουν splay στο στοιχείο που προσπελαύνουμε προς τη ρίζα όπως
ακριβώς γίνεται και στα κλασικά splay trees, αλλά εκτελούν και μερικές τοπικές
splay πράξεις τακτοποίησης κάτω από το στοιχείο που προσπελάσαμε. Αποδεικνύεται πως η τεχνική chain–splay είναι Ο(loglogn) ανταγωνιστική σε
σχέση με οποιοδήποτε offline αλγόριθμο αναζήτησης. Tέλος, ο George F.
Georgakopoulos [9] έδωσε ένα νέο λήμμα επαναζύγισης για τα splay δέντρα και
με βάση αυτό το λήμμα, αποδεικνύει πως τα splay δέντρα είναι ανταγωνιστικά
προς κάθε κλάση δυναμικών ισοζυγισμένων δέντρων.
Οι παραπάνω δομές θα μελετηθούν τόσο σε θεωρητικό όσο και σε
πειραματικό επίπεδο με σκοπό την εξαγωγή χρήσιμων συμπερασμάτων σε
σχέση με την αποδοτικότητά τους αλλά και με σκοπό την καταγραφή των ακόμη
ανοικτών προβλημάτων και των προοπτικών επίλυσης τους. Επιπλέον, θα
παρουσιαστούν τυχαιοποιημένες εκδόσεις των δομών των Demaine και
Georgakopoulos. Οι δομές αυτές θα υλοποιηθούν και η απόδοσή τους θα
τεκμηριωθεί τόσο πειραματικά όσο και θεωρητικά. Σημαντικής σημασίας είναι η
σύγκρισή τους με τις αρχικές δομές, ώστε να εξαχθούν συμπεράσματα σχετικά
με την συμβολή της τυχαιοποίησης στη βελτίωση της απόδοσης των δομών. / -
|
2 |
Δομές δεικτοδότησης και υπολογισμός ερωτημάτων εύρους κ-διαστάσεων σε κατανεμημένα περιβάλλοντα / Indexing structures and computation k-dimensional range queries in distributed environmentsΚαπλάνης, Αθανάσιος 24 November 2014 (has links)
Ανέκαθεν, η ανάγκη του ανθρώπου για πληροφορία ήτανε μια από αυτές που φρόντιζε να ικανοποιήσει όσο το δυνατόν πληρέστερα. Η πληροφορία είναι σε όλες τις περιπτώσεις ένα πολύτιμο εργαλείο στην λήψη αποφάσεων και οι άνθρωποι γρήγορα αντιλήφθηκαν την σημασία της, ειδικότερα μάλιστα στην σύγχρονη εποχή στην οποία μέσω της επιστήμης της Πληροφορικής δόθηκε η δυνατότητα σε μεγάλο μέρος του κοινού να έχει πρόσβαση σε τεράστιο όγκο δεδομένων, τα οποία μέσω της σωστής επεξεργασίας μετατρέπονται σε πληροφορία. Αυτό που πλέον αποτελεί πρόκληση, η οποία μας καλεί σαν επιστήμονες της Πληροφορικής να αντιμετωπίσουμε, είναι η εύρεση και στην συνέχεια η εφαρμογή καινούργιων μεθόδων γρήγορης και ανέξοδης συλλογής, αποδοτικής αποθήκευσης και εποικοδομητικής ανάλυσης δεδομένων, έτσι ώστε να γίνουν πληροφορία ποιοτική, πλούσια και με σημαντική χρηστική αξία. Στις μέρες μας, η ανάπτυξη του κλάδου τόσο των κατανεμημένων συστημάτων όσο και του διαδικτύου, μας έχουνε δώσει την δυνατότητα να χρησιμοποιούνται χαμηλοί σε απαιτήσεις υπολογιστικοί πόροι για να επεξεργάζονται παράλληλα μεγάλο όγκο δεδομένων. Ο κλάδος της Πληροφορικής που ασχολείται εκτενώς με αυτά τα συστήματα είναι τα ομότιμα συστήματα ή αλλιώς p2p συστήματα και ο κατανεμημένος υπολογισμός.
Η παρούσα διπλωματική εργασία έχει ως στόχο να βρίσκει σε κατανεμημένο περιβάλλον σημεία στις δύο διαστάσεις. Ορίζεται, δηλαδή, ένας χώρος από κ – διαστάσεις που είναι το πλέγμα (grid), στον οποίο ο χρήστης προσπαθεί να εντοπίσει σημεία που τον ενδιαφέρουν δημιουργώντας έτσι ερωτήματα εύρους. Το σύστημα θα ψάχνει να βρει το αποτέλεσμα στο ερώτημα αυτό για να καταλήξει σε ποιο από τα άλλα ορθογώνια τμήματα του πλέγματος εμπλέκεται και στην συνέχεια αυτά (τα τμήματα) θα επιστρέφονται. Πιο συγκεκριμένα, το πλέγμα μας χωρίζεται σε τετράγωνες περιοχές και κάθε κόμβος του κατανεμημένου δικτύου αναλαμβάνει να φιλοξενήσει τα σημεία της κάθε τετράγωνης περιοχής. Όλοι αυτοί οι κόμβοι οργανώνονται σε ένα hadoop cluster και τα δεδομένα εισάγονται στην κατανεμημένη βάση δεδομένων HBase που βασίζεται στην αρχιτεκτονική του BigTable της Google File System. Ο τρόπος που οργανώνονται τα δεδομένα στην HBase είναι κατανεμημένος και γίνεται χρήση των B+ -δέντρων. Η χρησιμότητα των B+ -δέντρων σε συνδυασμό με το κατανεμημένο πλαίσιο εργασίας του Hadoop, έγκειται στο γεγονός ότι με την χρήση των απαραίτητων εργαλείων τόσο της HBase όσο και του Hadoop FS, μπορούμε να γνωρίζουμε σε ποιόν κόμβο του hadoop cluster είναι αποθηκευμένοι οι ζητούμενοι κόμβοι του B+ -δέντρου και έτσι να επιτυγχάνεται η γρήγορη ανάκτηση των αποτελεσμάτων σε ένα ερώτημα εύρους.
Η διάρθρωση της εργασίας έχει ως εξής: Στο πρώτο κεφάλαιο γίνεται μια εισαγωγή στις έννοιες του κατανεμημένου υπολογισμού πάνω σε κατανεμημένα περιβάλλοντα. Στο δεύτερο γίνεται μια αναφορά στα ομότιμα δίκτυα (p2p) και πιο συγκεκριμένα αναλύεται το δίκτυο επικάλυψης του BATON που έχει δενδρική δομή όμοια με αυτή του Β+ -δέντρου. Στο τρίτο κεφάλαιο αναφέρεται μια υλοποίηση δεικτοδότησης και απάντησης σε ερωτήματα εύρους στο Νέφος Υπολογιστών με χρήση βασικών δομών δεδομένων B+ -δέντρου. Επίσης, η ART Autonomous Range Tree δομή παρουσιάζεται η οποία μπορεί να υποστηρίξει ερωτήματα εύρους σε τόσο ευρείας κλίμακας σε μη κεντρικοποιημένα περιβάλλοντα και μπορεί να κλιμακώνεται σε σχέση με τον αριθμό των κόμβων, καθώς και με βάση τα στοιχεία που είναι αποθηκευμένα. Η ART δομή ξεπερνά τις πιο δημοφιλείς μη κεντρικοποιημένες δομές, συμπεριλαμβανομένου του Chord (και μερικοί από τους διαδόχους του), του ΒΑΤΟΝ (και τον διάδοχό του) και των Skip-Graphs. Στο τέταρτο και πέμπτο κεφάλαιο, αντίστοιχα, γίνεται μια αναφορά στα βασικότερα σημεία της αρχιτεκτονικής και της λειτουργίας του Hadoop Framework και της HBase. Στο έκτο κεφάλαιο, βρίσκεται η περιγραφή της υλοποίησης της παρούσης διπλωματικής εργασίας μαζί με τους αλγορίθμους και τον τρόπο λειτουργίας τους. Στο επόμενο γίνεται η αξιολόγηση των πειραματικών αποτελεσμάτων της παρούσης διπλωματικής εργασίας καθώς, και το τι συμπεράσματα προκύπτουν μέσα από την αξιολόγηση. Τέλος, στο τελευταίο και όγδοο κεφάλαιο γίνεται η αποτίμηση της διπλωματικής εργασίας, καθώς αναφέρονται τα βασικά της μέρη, όπως επίσης και πιθανές προεκτάσεις που θα βελτίωναν την απόδοση του συστήματος. / Traditionally, the human need for information was one of those seeking to satisfy as much as possible. Information is in every way a valuable tool in decision making and people quickly realized its importance, especially in modern times, when the Information Technology gave the public access to the vast volume of data, which can be further processed into information. What seems to be now a challenge that IT specialists have to face is finding and implementing new methods of fast and inexpensive data collection, efficient storing of data and constructive data analysis, in order to turn them into quality, rich and useful information. Nowadays, the devel-opment of both the field of distributed systems and the Internet gave us the possibility of using computational resources with low requirements for simultaneous processing of large amounts of data. The IT field that deals extensively with these systems are peer-to-peer systems (p2p) and distributed computing.
The present dissertation aims at finding points in a distributed environment in the two-dimensional space. A space of k – dimensions is defined, i.e. the grid, in which the user tries to identify points of interest creating range queries. The system will search to find the result in this question to come up with the rectangular section of the grid that is involved and then these sections will be returned. More specifically, the grid is divided into square areas, and each node of the distributed network will accommodate points of each square area. All these nodes are organized into a hadoop cluster and the data is imported into the HBase distributed database based on BigTable architecture of the Google File System. In HBase data is organized in a distributed way and B+ -trees are used. The utility of B+ -trees in conjunction with the distributed framework of Hadoop lies on the fact that using the necessary tools of both HBase and Hadoop FS we can know in which hadoop cluster node the requested B+ -tree nodes are stored and thus achieve fast results retrieval in a range query.
The structure of the project is as follows: The first chapter is an introduction to the concepts of distributed computing over distributed environments. The second is a reference to peer-to-peer networks (p2p) and more specifically the BATON overlay network, which has a tree structure similar to that of the B+ -tree, is analyzed. The third chapter deals with an indexation and answering implementation on range queries in the Computer Cloud using B+ -tree basic data structures. Also, ART Autonomous Range Tree structure is presented which can support range queries in such large-scale decentralized environments and can scale in terms of the number of nodes as well as in terms of the data items stored. ART outperforms the most popular decentralized structures, including Chord (and some of its successors), BATON (and its successor) and Skip-Graphs. In the fourth and fifth chapter respectively a reference is made to the main points of Hadoop Framework and HBase architecture and operation. The sixth chapter is the description of the implementation of this dissertation together with the algorithms and how they operate. The next chapter is the evaluation of the experimental results of this dissertation and of the conclusions that derive from the evaluation. Finally, the eighth and last chapter is an overview of the dissertation, mentioning its basic parts, as well as possible extensions that would improve the system performance.
|
3 |
Σχεδιασμός και ανάπτυξη αλγορίθμου συσταδοποίησης μεγάλης κλίμακας δεδομένωνΓούλας, Χαράλαμπος January 2015 (has links)
Υπό το φάσμα της νέας, ανερχόμενης κοινωνίας της πληροφορίας, η σύγκλιση των υπολογιστών με τις τηλεπικοινωνίες έχει οδηγήσει στην συνεχώς αυξανόμενη παραγωγή και αποθήκευση τεράστιου όγκου δεδομένων σχεδόν για οποιονδήποτε τομέα της ανθρώπινης ενασχόλησης. Αν, λοιπόν, τα δεδομένα αποτελούν τα καταγεγραμμένα γεγονότα της ανθρώπινης ενασχόλησης, οι πληροφορίες αποτελούν τους κανόνες, που τα διέπουν. Και η κοινωνία στηρίζεται και αναζητά διακαώς νέες πληροφορίες. Το μόνο που απομένει, είναι η ανακάλυψη τους.
Ο τομέας, που ασχολείται με την συστηματική ανάλυση των δεδομένων με σκοπό την εξαγωγή χρήσιμης γνώσης ονομάζεται μηχανική μάθηση. Υπό αυτό, λοιπόν, το πρίσμα, η παρούσα διπλωματική πραγματεύεται την μηχανική μάθηση ως μια ελπίδα των επιστημόνων να αποσαφηνίσουν τις δομές που διέπουν τα δεδομένα και να ανακαλύψουν και να κατανοήσουν τους κανόνες, που “κινούν” τον φυσικό κόσμο.
Αρχικά, πραγματοποιείται μια πρώτη περιγραφή της μηχανικής μάθησης ως ένα από τα βασικότερα δομικά στοιχεία της τεχνητής νοημοσύνης, παρουσιάζοντας ταυτόχρονα μια πληθώρα προβλημάτων, στα οποία μπορεί να βρει λύση, ενώ γίνεται και μια σύντομη ιστορική αναδρομή της πορείας και των κομβικών της σημείων.
Ακολούθως, πραγματοποιείται μια όσο το δυνατόν πιο εμπεριστατωμένη περιγραφή, μέσω χρήσης εκτεταμένης βιβλιογραφίας, σχεδιαγραμμάτων και λειτουργικών παραδειγμάτων των βασικότερων κλάδων της, όπως είναι η επιβλεπόμενη μάθηση (δέντρα αποφάσεων, νευρωνικά δίκτυα), η μη-επιβλεπόμενη μάθηση (συσταδοποίηση δεδομένων), καθώς και πιο εξειδικευμένων μορφών της, όπως είναι η ημί-επιβλεπόμενη μηχανική μάθηση και οι γενετικοί αλγόριθμοι.
Επιπρόσθετα, σχεδιάζεται και υλοποιείται ένας νέος πιθανοτικός αλγόριθμος συσταδοποίησης (clustering) δεδομένων, ο οποίος ουσιαστικά αποτελεί ένα υβρίδιο ενός ιεραρχικού αλγορίθμου ομαδοποίησης και ενός αλγορίθμου διαμέρισης. Ο αλγόριθμος δοκιμάστηκε σε ένα πλήθος διαφορετικών συνόλων, πετυχαίνοντας αρκετά ενθαρρυντικά αποτελέσματα, συγκριτικά με άλλους γνωστούς αλγορίθμους, όπως είναι ο k-means και ο single-linkage. Πιο συγκεκριμένα, ο αλγόριθμος κατασκευάζει συστάδες δεδομένων, με μεγαλύτερη ομοιογένεια κατά πλειοψηφία σε σχέση με τους παραπάνω, ενώ το σημαντικότερο πλεονέκτημά του είναι ότι δεν χρειάζεται κάποια αντίστοιχη παράμετρο k για να λειτουργήσει.
Τέλος, γίνονται προτάσεις τόσο για περαιτέρω βελτίωση του παραπάνω αλγορίθμου, όσο και για την ανάπτυξη νέων τεχνικών και μεθόδων, εναρμονισμένων με τις σύγχρονες τάσεις της αγοράς και προσανατολισμένων προς τις απαιτητικές ανάγκες της νέας, αναδυόμενης κοινωνίας της πληροφορίας. / In the spectrum of a new and emerging information society, the convergence of computers and telecommunication has led to a continuously increasing production and storage of huge amounts of data for almost any field of human engagement. So, if the data are recorded facts of human involvement, then information are the rules that govern them. And society depends on and looking earnestly for new information. All that remains is their discovery.
The field of computer science, which deals with the systematic analysis of data in order to extract useful information, is called machine learning. In this light, therefore, this thesis discusses the machine learning as a hope of scientists to elucidate the structures that govern the data and discover and understand the rules that "move" the natural world.
Firstly, a general description of machine learning, as one of the main components of artificial intelligence, is discussed, while presenting a variety of problems that machine learning can find solutions, as well as a brief historical overview of its progress.
Secondly, a more detailed description of machine learning is presented by using extensive literature, diagrams, drawings and working examples of its major research areas, as is the supervised learning (decision trees, neural networks), the unsupervised learning (clustering algorithms) and more specialized forms, as is the semi-supervised machine learning and genetic algorithms.
In addition to the above, it is planned and implemented a new probabilistic clustering algorithm, which is a hybrid of a hierarchical clustering algorithm and a partitioning algorithm. The algorithm was tested on a plurality of different datasets, achieving sufficiently encouraging results, as compared to other known algorithms, such as k-means and single-linkage. More specifically, the algorithm constructs data blocks, with greater homogeneity by majority with respect to the above, while the most important advantage is that it needs no corresponding parameter k to operate.
Finally, suggestions are made in order to further improve the above algorithm, as well as to develop new techniques and methods in keeping with the current market trends, oriented to the demanding needs of this new, emerging information society.
|
4 |
Σχεδίαση και ανάπτυξη ολοκληρωμένου συστήματος δυναμικής ανάλυσης και πρόβλεψης της επίδοσης εκπαιδευόμενων σε συστήματα ανοιχτής και εξ' αποστάσεως εκπαίδευσηςΧαλέλλη, Ειρήνη 05 February 2015 (has links)
Η ραγδαία ανάπτυξη και διείσδυση των νέων τεχνολογιών πληροφορίας και επικοινωνίας έχει επιφέρει ριζικές αλλαγές σε όλους τους τομείς της ανθρώπινης δράσης (Castells, 1998). Ιδιαίτερο ενδιαφέρον παρουσιάζει η επιρροή των τεχνολογιών αυτών στον τομέα της εκπαίδευσης. Οι εξελίξεις στον χώρο της τεχνολογίας και επικοινωνίας καθώς και η διάδοση του Internet μετεξέλιξαν αναπόφευκτα την εκπαιδευτική διαδικασία, από το κλασσικό συγκεντρωτικό μοντέλο σε ένα πιο άμεσο και ευέλικτο: η «εξ’ Αποστάσεως Εκπαίδευση» (e-learning) είναι μια εναλλακτική μορφή εκπαίδευσης, που επιδιώκει να καλύψει τους περιορισμούς της παραδοσιακής εκπαίδευσης.
Στην παρούσα μεταπτυχιακή διπλωματική εργασία σχεδιάστηκε και υλοποιήθηκε ένα ολοκληρωμένο σύστημα Δυναμικής Ανάλυσης και Πρόβλεψης της επίδοσης των εκπαιδευομένων, για ένα σύστημα εξ΄ αποστάσεως εκπαίδευσης. Η βασική ιδέα εμφορείται από την ανάγκη των ιδρυμάτων εξ΄ αποστάσεως εκπαίδευσης, για την κάλυψη των εκπαιδευτικών αναγκών και την παροχή υψηλής ποιότητας σπουδών. Η εξόρυξη γνώσης για την πρόβλεψη της επίδοσης των εκπαιδευομένων συμβάλλει καθοριστικά στην επίτευξη υψηλής ποιότητας σπουδών. Η ικανότητα και η δυνατότητα πρόβλεψης της απόδοσης των εκπαιδευομένων μπορεί να φανεί χρήσιμη με αρκετούς τρόπους για την διαμόρφωση ενός συστήματος, που θα μπορεί να αποτρέψει την αποτυχία καθώς και την παραίτηση των εκπαιδευομένων. Αξίζει να σημειωθεί ότι στα συστήματα εξ’ αποστάσεως εκπαίδευσης η συχνότητα «εγκατάλειψης» είναι αρκετά υψηλότερη από αυτή στα συμβατικά πανεπιστήμια.
Για την πρόβλεψη της επίδοσης των εκπαιδευομένων, η απαιτούμενη πληροφορία βρίσκεται «κρυμμένη» στο εκπαιδευτικό σύνολο δεδομένων (δλδ. βαθμοί γραπτών εργασιών, βαθμοί τελικής εξέτασης, παρουσίες φοιτητών) και είναι εξαγώγιμη με τεχνικές εξόρυξης. Η χρήση μεθόδων εξόρυξης δεδομένων (data mining) στον τομέα της εκπαίδευσης παρουσιάζει αυξανόμενο ερευνητικό ενδιαφέρον. Ο νέος αυτός «αναπτυσσόμενος» τομέας έρευνας, που ονομάζεται «Εκπαιδευτική Εξόρυξη Δεδομένων», ασχολείται με την ανάπτυξη μεθόδων εξόρυξης «γνώσης» από τα εκπαιδευτικά σύνολα δεδομένων. Πράγμα που επιτυγχάνεται με τη χρήση τεχνικών όπως τα δέντρα απόφασης, τα Νευρωνικά Δίκτυα, Naïve Bayes, k-means, κλπ. Η παρούσα εργασία έχει σχεδιαστεί να προσφέρει ένα μοντέλο εξόρυξης δεδομένων χρησιμοποιώντας τη μέθοδο των δέντρων απόφασης, για το σύστημα τριτοβάθμιας εκπαίδευσης στο ανοιχτό πανεπιστήμιο. Η «γνώση» που προκύπτει από τα δεδομένα εξόρυξης θα χρησιμοποιηθεί με στόχο την διευκόλυνση και την ενίσχυση της μάθησης, καθώς επίσης και στη λήψη αποφάσεων. Στην παρούσα εργασία, εξάγουμε «γνώση» που σχετίζεται με τις επιδόσεις των μαθητών στην τελική εξέταση. Επίσης, γίνεται εντοπισμός των ατόμων που εγκαταλείπουν το μάθημα και των μαθητών που χρειάζονται ιδιαίτερη προσοχή και εντέλει δίνει τη δυνατότητα στους καθηγητές να παράσχουν την κατάλληλη παροχή συμβουλών. / The rapid development and intrusion of information technology and communications have caused radical changes in all sectors of human’s activity. (Castells, 1998). Of particular interest is the great technology’s influence on education. Due to the adoption of the new technologies, e-learning has been emerged and developed. As a result, distance learning has transformed and new possibilities have appeared. It is remarkable that distance learning became and considered as a scout of the new era in education and contributed to the quality of education: e-learning is trying to cover the limitations of conventional teaching environment.
In the present thesis, an integrated system of dynamic analysis and prediction of the performance of students in distance education has been designed and implemented. The initial idea for designing this system came from the higher distance education institutes’ need to provide quality education to its students and to improve the quality of managerial decisions. One way to achieve highest level of quality in higher distance education e-learning system is by discovering knowledge from educational data to study the main attributes that may affect the students’ performance. The discovered knowledge can be used to offer a helpful and constructive recommendations to the academic planners in higher distance education institutes to enhance their decision making process, to improve students’ academic performance, trim down failure rate and dropout rate, to assist instructors, to improve teaching and many other benefits. Dropout rates in university level distance learning are definitely higher than those inconventional universities, thus limiting dropout is essential in university-level distance learning.
|
5 |
Στοχαστικός (γραμμικός) προγραμματισμόςΜαγουλά, Ναταλία 07 April 2011 (has links)
Πολλά είναι τα προβλήματα απόφασης τα οποία μπορούν να μοντελοποιηθούν ως προβλήματα γραμμικού προγραμματισμού. Πολλές όμως είναι και οι καταστάσεις όπου δεν είναι λογικό να υποτεθεί ότι οι παράμετροι του μοντέλου καθορίζονται προσδιοριστικά. Για παράδειγμα, μελλοντικές παραγωγικότητες σε ένα πρόβλημα παραγωγής, εισροές σε μία δεξαμενή που συνδέεται με έναν υδροσταθμό παραγωγής ηλεκτρικού ρεύματος, απαιτήσεις στους διάφορους κόμβους σε ένα δίκτυο μεταφορών κλπ, είναι καταλληλότερα μοντελοποιημένες ως αβέβαιες παράμετροι, οι οποίες χαρακτηρίζονται στην καλύτερη περίπτωση από τις κατανομές πιθανότητας.
Η αβεβαιότητα γύρω από τις πραγματοποιημένες τιμές εκείνων των παραμέτρων δεν μπορεί να εξαλειφθεί πάντα εξαιτίας της εισαγωγής των μέσων τιμών τους ή μερικών άλλων (σταθερών) εκτιμήσεων κατά τη διάρκεια της διαδικασίας μοντελοποίησης. Δηλαδή ανάλογα με την υπό μελέτη κατάσταση, το γραμμικό προσδιοριστικό μοντέλο μπορεί να μην είναι το κατάλληλο μοντέλο για την περιγραφή του προβλήματος που θέλουμε να λύσουμε. Σε αυτή τη διπλωματική υπογραμμίζουμε την ανάγκη να διευρυνθεί το πεδίο της μοντελοποίησης των προβλημάτων απόφασης που παρουσιάζονται στην πραγματική ζωή με την εισαγωγή του στοχαστικού προγραμματισμού. / There are many practical decision problems than can be modeled as linear programs. However, there are also many situations that it is unreasonable to assume that the coefficients of model are deterministically fixed. For instance, future productivities in a production problem, inflows into a reservoir connected to a hydro power station, demands at various nodes in a transportation network, and so on, are often appropriately modeled as uncertain parameters, which are at best characterized by probability distributions.
The uncertainty about the realized values of those parameters cannot always be wiped out just by inserting their mean values or some other (fixed) estimates during the modelling process. That is, depending on the practical situation under consideration, the linear deterministic model may not be the appropriate model for describing the problem we want to solve. In this project we emphasize the need to broaden the scope of modelling real life decision problems by inserting stochastic programming.
|
6 |
Εφαρμογή τεχνικών εξόρυξης γνώσης στην εκπαίδευσηΠαπανικολάου, Δονάτος 31 May 2012 (has links)
Σε αυτή την Διπλωματική εργασία μελετήσαμε με ποιο τρόπο μπορούν να εφαρμοστούν οι διάφορες τεχνικές Εξόρυξης Γνώσης (Data Mining) στην εκπαίδευση. Αυτός ο επιστημονικός τομέας o οποίος ερευνά και αναπτύσσει τεχνικές προκειμένου να ανακαλύψει γνώση από δεδομένα τα οποία προέρχονται από την εκπαίδευση ονομάζεται Εξόρυξη Γνώσης από Εκπαιδευτικά Δεδομένα (Educational Data Mining –EDM. Στην εργασία αυτή εκτός από την θεωρητική μελέτη των αλγορίθμων και των τεχνικών που διέπουν την εξόρυξη γνώσης από δεδομένα γενικά, έγινε και μια λεπτομερέστερη μελέτη και παρουσίαση της κατηγορίας των αλγορίθμων κατηγοριοποίησης (Classification), διότι αυτοί οι αλγόριθμοι χρησιμοποιήθηκαν στην φάση της υλοποίησης/αξιολόγησης. Στην συνέχεια η εργασία επικεντρώθηκε στον τρόπο με τον οποίο μπορούν να εφαρμοστούν αυτοί οι αλγόριθμοι σε εκπαιδευτικά δεδομένα, τι εφαρμογές έχουμε στην εκπαίδευση, ενώ αναφερόμαστε και σε μια πληθώρα ερευνών που έχουν πραγματοποιηθεί πάνω στο συγκεκριμένο αντικείμενο. Στην συνέχεια διερευνήσαμε την εφαρμογή τεχνικών κατηγοριοποίησης στην πρόγνωση της επίδοσης μαθητών Δευτεροβάθμιας Εκπαίδευσης στα μαθήματα της Γεωγραφίας Α’ και Β’ Γυμνασίου. Συγκεκριμένα υλοποιήσαμε και θα αξιολογήσαμε έξι αλγορίθμους οι οποίοι ανήκουν στην ομάδα των αλγορίθμων κατηγοριοποίησης(Classification) και είναι αντιπροσωπευτικοί των σημαντικότερων τεχνικών κατηγοριοποίησης. Από την οικογένεια των ταξινομητών με χρήση δένδρων απόφασης (Decision Tree Classifiers) υλοποιήσαμε τον J48, από τους αλγορίθμους κανόνων ταξινόμησης (Rule-based Classification ) τον Ripper, από τους αλγόριθμους στατιστικής κατηγοριοποίησης τον Naïve Bayes, από την μέθοδο των Κ πλησιέστερων γειτόνων (KNN) τον 3-ΝΝ, από την κατηγορία των τεχνητών νευρωνικών δικτύων τον Back Propagation και τέλος από τις μηχανές διανυσμάτων υποστήριξης (Support Vector Machines SVM) τον SMO (Sequental Minimal Optimazation). Όλες οι παραπάνω υλοποιήσεις και αξιολογήσεις έγιναν με το ελεύθερο λογισμικού Weka το οποίο είναι υλοποιημένο σε Java και το οποίο προσφέρει μια πληθώρα αλγορίθμων μηχανικής μάθησης για να κάνουμε εξόρυξη γνώσης. / In this work we will study the way the misc data mining techniques can be applied to the misc fields of the education. This new scientific field is commonly named Educational Data Mining. In this study we will study the theoretical analysis of the data mining techniques focussing to the classification techniques as those are the most commonly used for prediction purpose. We also intend to predict student performance in secondary education using data mining techniques. The data we collect are concerned the class of Geography and we apply to them six data mining models with the help of the open source machine learning software Weka. We use supervised machine learning algorithms from the Classification field (Decision Tree Classifiers, Rule-based Classification, Neural Networks, k-Nearest Neighbour Algorithm, Bayesian and Support Vector Machines). After we have evaluate the algorithms we build a java tool, that uses the 3-KNN algorithm, to help us predict the performance of a student at the end of the year.
|
7 |
Σχεδιασμός ανάπτυξη και εφαρμογή συστήματος υποστήριξης της διάγνωσης επιχρισμάτων θυρεοειδούς δεδομένων βιοψίας με λεπτή βελόνη FNA με χρήση εξελιγμένων μεθόδων εξόρυξης δεδομένωνΖούλιας, Εμμανουήλ 17 September 2012 (has links)
Σκοπός της παρούσας διδακτορικής διατριβής είναι η ανάπτυξη ενός ολοκληρωμένου συστήματος υποστήριξης της διάγνωσης (Decision Support System - DSS) με χρήση μεθόδων εξόρυξης δεδομένων για την ταξινόμηση επιχρισμάτων βιοψίας με λεπτή βελόνα (Fine Needle Aspiration - FNA). Δύο κατηγορίες επιλέχθηκαν για τα δείγματα FNA: καλοήθεια και κακοήθεια. Το σύστημα αυτό αποτελείται από τις ακόλουθες βαθμίδες: 1) συλλογής δεδομένων, 2) επιλογής δεδομένων, 3) εύρεσης κατάλληλων χαρακτηριστικών, 4) εφαρμογής ταξινόμησης με χρήση μεθόδων εξόρυξης δεδομένων. Επίσης, βασικός στόχος της παρούσας διδακτορικής διατριβής ήταν η βελτίωση της ορθής ταξινόμησης των ύποπτων επιχρισμάτων (suspicious), για τα οποία είναι γνωστή η αδυναμία της μεθόδου FNA να τα ταξινομήσει. Το σύστημα εκπαιδεύτηκε και ελέγχθηκε σε σχέση με το δείγμα για το οποίο είχαμε ιστολογικές επιβεβαιώσεις (ground truth). Για περιπτώσεις οι οποίες χαρακτηρίστηκαν ως μη κακοήθεις από την FNA, και για τις οποίες δεν είχαμε ιστολογικές επιβεβαιώσεις, το δείγμα προέκυψε από την συνεκτίμηση και άλλων κλινικών, εργαστηριακών και απεικονιστικών εξετάσεων.
Στα πλαίσια της παρούσας διδακτορικής διατριβής συλλέχθηκαν εξετάσεις FNA θυρεοειδούς από το Εργαστήριο Παθολογοανατομίας του Α’ Τμήματος Παθολογίας της Ιατρικής Σχολής του Πανεπιστημίου Αθηνών. Δεδομένου ότι το εν λόγω εργαστήριο λειτουργεί και σαν κέντρο αναφοράς, σημαντικός αριθμός των δειγμάτων εστάλησαν εκεί και από άλλα Εργαστήρια Παθολογοανατομίας για επανέλεγχο. Το αρχειακό υλικό ήταν πολύ καλά ταξινομημένο σε χρονολογική σειρά αλλά ήταν σε έντυπη μορφή. Αρχικά πραγματοποιήθηκε η ανάλυση απαιτήσεων για τη δομή και το σχεδιασμό της βάσης δεδομένων. Με βάση τα στοιχεία από την τεκμηριωμένη διάγνωση σχεδιάστηκε και αναπτύχθηκε προηγμένο σύστημα για την κωδικοποίηση και αρχικοποίηση των δεδομένων. Με τη βοήθεια του σχεδιασμού και ανάλυσης απαιτήσεων αναπτύχθηκε και υλοποιήθηκε η βάση δεδομένων στην οποία αποθηκεύτηκαν τα δεδομένα προς επεξεργασία. Παράλληλα, με το σχεδιασμό της βάσης έγινε και η προεργασία για το σχεδιασμό και την ανάλυση απαιτήσεων του γραφικού περιβάλλοντος εισαγωγής στοιχείων. Λαμβάνοντας υπόψη ότι το σύστημα θα μπορούσε να χρησιμοποιηθεί και πέρα από τα πλαίσια της παρούσας διδακτορικής διατριβής λήφθηκε μέριμνα ώστε να παρέχεται ένα φιλικό και ευέλικτο προς το χρήστη περιβάλλον.
Σύμφωνα με τη μεθοδολογία προσέγγισης η οποία ακολουθήθηκε προηγήθηκε στατιστική ανάλυση των 9.102 συλλεχθέντων δειγμάτων FNA ως προς τα κυτταρολογικά χαρακτηριστικά τους και τις διαγνώσεις. Οι κυτταρολογικές διαγνώσεις των συγκεκριμένων δειγμάτων συσχετίστηκαν με τις ιστολογικές διαγνώσεις, στοχεύοντας στον υπολογισμό της πιθανής επίδρασης και συμβολής κάθε κυτταρολογικού χαρακτηριστικού σε μια ορθή ή ψευδή κυτταρολογική διάγνωση, έτσι ώστε να προσδιοριστούν οι πιθανές πηγές λανθασμένης διάγνωσης. Τα δείγματα τα οποία περιείχαν μόνο αίμα ή πολύ λίγα θυλακειώδη κύτταρα χωρίς κολλοειδές θεωρήθηκαν ανεπαρκή για τη διάγνωση. Οι βιοψίες εκτελέσθηκαν είτε στο Α’ τμήμα του Πανεπιστημίου Αθηνών (οι περισσότερες από τις περιπτώσεις με ψηλαφητούς όζους) είτε αλλού (κυρίως κάτω από την καθοδήγηση του κέντρου αναφοράς). Τα δείγματα επιστρωμένα σε πλακάκια, στάλθηκαν στο κέντρο αναφοράς από διάφορα νοσοκομεία, με διαφορετικά πρωτόκολλα σχετικά με τα κριτήρια εκτέλεσης βιοψίας FNA σε θυρεοειδή. Μετεγχειρητικές ιστολογικές επαληθεύσεις ήταν διαθέσιμες για 266 ασθενείς (κακοήθειες και μη). Το χαμηλό ποσοστό ιστολογικών επαληθεύσεων οφείλεται στην ετερογενή προέλευση των ασθενών και στην έλλειψη ολοκληρωμένης παρακολούθησης και επανελέγχου των ασθενών. Για την αξιολόγηση των δεδομένων χρησιμοποιήθηκαν περιγραφικά στατιστικά μεγέθη όπως, μέση τιμή, τυπική απόκλιση, ποσοστά, μέγιστο και ελάχιστο. Έγιναν επίσης και χ2 δοκιμές επιπέδου σημαντικότητας διαφόρων παραμέτρων για να ελεγχθεί η πιθανή συσχέτιση ή η ανεξαρτησία. Για τη συσχέτιση των κυτταρολογικών και των ιστολογικών διαγνώσεων και την αξιολόγηση των εργαστηριακών ευρημάτων, πέραν των περιγραφικών στατιστικών μεγεθών χρησιμοποιήθηκαν και υπολογισμοί της ευαισθησίας, της ειδικότητας, της συνολικής ακρίβειας, της αρνητικής και θετικής αξίας πρόβλεψης (negative and positive predictive value). Προκειμένου να καθοριστεί εάν μια κατηγορία ασθενειών συσχετίζεται ή όχι με συγκεκριμένες κυτταρολογικές παραμέτρους εφαρμόστηκε μέθοδος ελέγχου στατιστικής σημαντικότητας σε επίπεδο 5% (p < 0,05). Η διαδικασία ακολουθήθηκε για κάθε κατηγορία ασθενειών ή συνδυασμό τους και για κάθε παράμετρο των κυτταρολογικών και αρχιτεκτονικών στοιχείων της κυτταρολογικής διάγνωσης. Τα αποτελέσματα της στατιστικής ανάλυσης επέτρεψαν το διαχωρισμό των δεδομένων σε καλοήθη, κακοήθη, νεοπλασματικά, ύποπτα για κακοήθεια και οριακά με χαρακτηριστικά γνωρίσματα μεταξύ ενός καλοήθους και ενός νεοπλασματικού.
Στην συνέχεια αναπτύχθηκε σύστημα υποστήριξης της διάγνωσης χρησιμοποιώντας εξειδικευμένες μεθόδους εξόρυξης δεδομένων. Το σύστημα αποτελείται από τέσσερις βαθμίδες. Η πρώτη βαθμίδα αυτού του συστήματος είναι το περιβάλλον Συλλογής Δεδομένων στην οποία τα δεδομένα αποθηκεύονται στη βάση δεδομένων. Η Δεύτερη Βαθμίδα αυτού του συστήματος αφορά στην Επιλογή Δεδομένων. Σύμφωνα με την καταγραφή των απαιτήσεων, την εισαγωγή και τη ψηφιοποίηση των στοιχείων, δημιουργήθηκαν 111 χαρακτηριστικά για κάθε ασθενή (record). Τα περισσότερα χαρακτηριστικά είχαν τιμές δυαδικού τύπου, αποτυπώνοντας την ύπαρξη ή μη του κάθε χαρακτηριστικού, ενώ κάποιες άλλες είχαν τιμές τύπων αριθμών ή αλφαριθμητικών χαρακτήρων. Από τα 111 χαρακτηριστικά επιλέχθηκαν 60 χαρακτηριστικά τα οποία περιγράφουν τη δομή των επιχρισμάτων ενώ δημιουργήθηκαν άλλα 7 χαρακτηριστικά τα οποία αφορούσαν στην ομαδοποίηση άλλων χαρακτηριστικών.
Η Τρίτη Βαθμίδα του συστήματος αφορά στην εύρεση των Κατάλληλων Χαρακτηριστικών. Λόγω του αρχικά υψηλού αριθμού χαρακτηριστικών παραμέτρων (67 ανά περίπτωση), ήταν απαραίτητο να εξαλειφθούν οι χαρακτηριστικές παράμετροι που συσχετίζονταν γραμμικά ή δεν είχαν καμία διαγνωστική πληροφορία. H μέθοδος επιλογής χαρακτηριστικών εφαρμόστηκε πριν από την ταξινόμηση, με γνώμονα την ανεύρεση ενός υποσυνόλου των χαρακτηριστικών παραμέτρων που βελτιστοποιούν σε ακρίβεια τη διαδικασία ταξινόμησης. Εφαρμόστηκε η τεχνική επιπλέουσας πρόσθιας ακολουθιακά μεταβαλλόμενης επιλογής (SFFS). Ο αριθμός των δειγμάτων που χρησιμοποιήθηκαν είναι 2.036 (1.886 καλοήθειες και 150 κακοήθειες). Εξ αυτών, όλες οι κακοήθειες είναι ιστολογικά επιβεβαιωμένες. Επίσης, 140 καλοήθειες είναι ιστολογικά επιβεβαιωμένες με επάρκεια υλικού. Οι υπόλοιπες 1.726 καλοήθειες είναι επιβεβαιωμένες με συνεκτίμηση κλινικών, εργαστηριακών και απεικονιστικών ιατρικών εξετάσεων (υπέρηχοι κ.λπ.). Από τα 2.036 δείγματα, το 25% χρησιμοποιήθηκε για την επιλογή χαρακτηριστικών παραμέτρων, δηλαδή 37 περιπτώσεις κακοήθειας (Malignant) και 472 περιπτώσεις καλοήθειας (Non Malignant). Από την εφαρμογή της τεχνικής (SFFS) επιλέχθηκαν τελικά 12 χαρακτηριστικά ως βέλτιστα για την ταξινόμηση των δεδομένων FNA σε καλοήθη και κακοήθη.
Η Τέταρτη βαθμίδα επεξεργασίας είναι η Εφαρμογής Ταξινόμησης με χρήση Μεθόδων Εξόρυξης Δεδομένων ή Ταξινομητής. Για το σκοπό αυτό, επιλέχθηκε να εφαρμοστεί μια πληθώρα αξιόπιστων, καλά επιβεβαιωμένων και σύγχρονων μεθόδων εξόρυξης δεδομένων. Το σύστημα εκπαιδεύτηκε και ελέγχθηκε σε σχέση με το δείγμα για το οποίο είχαμε ιστολογικές επιβεβαιώσεις (ground truth). Η ανεξάρτητη εφαρμογή τεσσάρων αξιόπιστων μεθόδων, Δέντρων Αποφάσεων (Decision Trees), Τεχνιτών Νευρωνικών Δικτύων (Artificial Neural Network), Μηχανών Στήριξης Διανυσμάτων (Support Vector Machine), και Κ - κοντινότερου γείτονα (k-NN), έδωσε αποτελέσματα συγκρίσιμα με αυτά της FNA μεθόδου. Περαιτέρω βελτίωση των αποτελεσμάτων επιτεύχθηκε με την εφαρμογή της μεθόδου πλειοψηφικού κανόνα (Majority Vote - CMV) συνδυάζοντας τα αποτελέσματα από την εφαρμογή των τριών καλύτερων αλγορίθμων, ήτοι των Νευρωνικών Δικτύων, Μηχανών Στήριξης Διανυσμάτων και Κ - κοντινότερου γείτονα. Η τροποποιημένη μέθοδος τεχνητών αυτοάνοσων συστημάτων (Artificial Immune Systems – AIS) χρησιμοποιήθηκε για πρώτη φορά στην ταξινόμηση και παρουσίασε ιδιαίτερα βελτιωμένα αποτελέσματα στην ταξινόμηση των επιχρισμάτων τα οποία χαρακτηρίζονται ύποπτα (suspicious) από τους ειδικούς και αποτελούν το αδύναμο σημείο της μεθόδου FNA. Αυτές οι περιπτώσεις υπόνοιας αποτελούν ένα πολύ δύσκολο κομμάτι για τη διάκριση μεταξύ των καλοηθειών και των κακοηθειών, ακόμα και για τους πλέον ειδικούς. Επειδή όλα τα περιστατικά που χαρακτηρίζονται από την βιοψία FNA ως υπόνοιες αντιμετωπίζονται κλινικά σαν κακοήθειες, η εφαρμογή των αλγοριθμικών μεθόδων βελτιώνει αισθητά τη διαχείριση αυτών των περιπτώσεων μειώνοντας τον αριθμό των άσκοπων χειρουργικών επεμβάσεων θυρεοειδεκτομών. / The Aim of present thesis is the development of an integrated system for supporting diagnosis (Decision Support System - DSS) using for categorizing FNA biopsy smears. Two categories were selected for the FNA smears: malignant and nonmalignant. The system is constituted by the following stages of 1) data collection, 2) data selection 3) choice of suitable clinical and cytological features, 4) application of data mining method for the categorization of FNA biopsy smears. Furthermore a fundamental objective of the doctoral thesis was the improvement of suspect smears (suspicious) categorization, for the latter FNA Biopsy has a known restriction. The system had been trained and checked in relation to the sample that histologic evaluation existed (ground truth). For smears that characterized as nonmalignant by FNA and histological data we’re not available, complementary clinical, laboratory and imaging evaluations took into account in order to create the sample.
Τhe smears that were available in this thesis, were collected from FNA biopsies in Pathologoanatomy Laboratory, A’ Pathology Department, Medical School of Athens University. Given that the above referred laboratory is a reference center, an important number of FNA smears were sent to it from other laboratories for cross check. The examination files were sorted in chronological order, but there were in paper forms. The requirements for the formation and the design of database system were collected. Based on the material of the diagnosis an improved system was designed and developed for data initialization and coding. The database was developed based on the design and analysis of requirements; in this database data were stored for further investigation. Analysis of the graphical user interface design was performed in parallel to the database design. Taking into account that the system might be used after the completion of thesis, the graphical user interface was designed in order to be user friendly and flexible environment.
According to the methodological approach that was followed, the various cytological characteristic of 9102 FNA smears aspired among 2000-2004 was analyzed statistically. The cytological reports cross correlated with histological diagnoses, aiming to calculate the effect or contribution of each cytological characteristic to a false or true cytological diagnosis and to find the possible sources of erroneous diagnosis. The smears that have blood or a few follicular cells without colloid were characterized as insufficient for further diagnosis. The aspiration was performed either in Α’ department of Athens University (most of the cases with palpable nodules) or elsewhere (mainly under guidance of the reference center). The acquired smears being send to the reference center from various hospitals with different protocols concerning criteria to perform a thyroid FNA. Histological reports were available for 266 patients. The small number of histological verifications was due to the heterogeneity and the lack of patients files. For evaluating of data, descriptive statistic values were used like mean, standard deviation, percentage, maximum and minimum. In addition to that χ2 tests of significance were performed in order to check possible correlation or independence. For correlating cytological and histological diagnosis and evaluating laboratory findings, apart from the descriptive statistic parameters also calculated sensitivity, specificity, total accuracy, negative predictive value and positive predictive value. Method of statistical significance in the level of 5% (p < 0,05) was applied in order to specify if a disease was correlated to a cytological parameter. Those checks were performed for each disease category in correlation to any cytological parameter. Statistical analysis divided the smears into nonmalignant, malignant, neoplasms, suspicious for malignancy and borderline.
A diagnosis support system was implemented using data mining methods. The system is consisted of four stages. The First stage of the system is the Data Collection environment, which stores the data to the database. The Second stage of this system concerns the Selection of Data. User requirements concluded that 111 characteristics are needed to describe each patient (record). Most of them have binary values, presenting existence and not existence, other have alphanumeric and number values. Among them 60 were selected and 7 more are produced from grouping other characteristics. The final analysis reveals that 67 characteristics of the smears are capable for describing the structure of smears in general.
The Third stage of system concerns the Selection of Best Characteristics. Due to the high number of attributes (67 per case), it was essential to eliminate the characteristics that are connected linearly or do not bring diagnostics information. The choice of characteristics applied before the classification, having the aim of discovering a subset of characteristics that optimizes the process of classification. The technique of Sequential Float Forward Search (SFFS) was applied. The number of patients that used was 2,036 (1886 non malignancies and 150 malignancies). Among them all malignancies were histologically confirmed. In addition to that 140 no malignancies were histologically confirmed in correlation to evaluation of clinics, laboratorial and medical image actions (ultrasounds etc.). Among 2.036 smears the 25% used for characteristics selection, 37 smears of Malignant and smears of Non Malignant. The Sequential Float Forward Search (SFFS) Technique, choose the best 12 elements that they reveal high performance to FNA data categorization.
The Fourth stage is the Application of Classification using Data Mining Methods or in other words data mining method. For this aim a set of reliable, well confirmed but also modern methods applied. In addition to that the system was trained and was checked using the sample with histological verifications (ground truth). The independent application of four reliable methods, Decision Trees, Artificial Neural Network, Support Vector Machine, and k-NN, resulting to comparable outcomes concerning those of FNA. However, further improvement was achieved with the application of Majority (Majority Vote - CMV) using of previous results of three algorithms Artificial Neural Network, Support Vector Machine, and k-NN. The modified Artificial Immune System (AIS) was applied for first time. AIS presents particularly improved results for the categorization of smears, which are characterised “suspicious” by the experts and is a known weakness of FNA method. These cases constitute a very difficult part for the discrimination among non-malignant and malignant, even for a specialist. Since all these cases are faced clinically using FNA as malignancies, the application of an improved algorithmic method improves accordingly the management of these cases by decreasing the number of useless surgical thyroid operations.
|
Page generated in 0.0272 seconds