Contia

The Web Trend

Category Archives: Έρευνα – Εκπαίδευση

Contia

Ανάλυση και Σχεδιασμός συστημάτων

Στις μέρες μας ένα μεγάλο ποσοστό μεγάλων projects αποτυγχάνει τόσο ως προς την εφαρμογή του όσο και ως προς την υλοποίησή του. Αυτό το φαινόμενο παρατηρείτε στον χώρο των επιχειρήσεων (μικρομεσαίων και μεγάλων) εδώ και πολλά χρόνια και συγκεκριμένα από τις αρχές της βιομηχανικής επανάστασης. Ο λόγος που συμβαίνει αυτό, η αποτυχία διεκπεραίωσης πολλών έργων, οφείλεται σε διάφορους παράγοντες όπως είναι οι περιβαλλοντικοί παράγοντες (νομικό & πολιτικό σύστημα), τεχνολογικοί παράγοντες, οικονομικοί παράγοντες και φυσικά οι ανθρώπινοι παράγοντες. Πολλοί ερευνητές ρίχνουν το φταίξιμο του προβλήματος στη διοίκηση του ανθρώπινου δυναμικού (του έργου) αλλά και στη κακή επικοινωνία μεταξύ των εμπλεκομένων.

Από πολλές απόψεις, η κατασκευή ενός πληροφοριακού συστήματος μοιάζει με τη κατασκευή ενός σπιτιού. Στην αρχή ξεκινάς με μία βασική ιδέα προς υλοποίηση, η ιδέα αυτή μετασχηματίζεται σε ένα απλό σχεδιάγραμμα το οποίο παρουσιάζεται στον υποψήφιο πελάτη μας, μέχρι να συμφωνήσει με το τελικό μας σχέδιο. Τρίτον τα σχέδια αυτά εμπλουτίζονται με περισσότερες λεπτομέρειες και γίνονται πιο αναλυτικά και στο τέλος το σπίτι κατασκευάζεται με βάση αυτά τα σχέδια, συχνά με την προσθήκη ορισμένων αλλαγών που ζητάει ο πελάτης κατά τη διάρκεια κατασκευής.

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

1. Προετοιμασία

Κατά τη φάση της προετοιμασίας η ομάδα έργου πρέπει να προσδιορίσει την αξία του συστήματος για την εταιρεία, δηλαδή πόσο θα κοστίσει το σύστημα ή κατά πόσο θα αυξήσει τα κέρδη της εταιρείας μετά τη λειτουργία του. Όλες οι αξίες που θα προσδώσει μελλοντικά το σύστημα υποβάλλονται με τη μορφή αιτήσεων συστήματος η οποία αποτελεί μία σύντομη περίληψη μίας επιχειρηματικής ανάγκης κι εξηγεί που ένα σύστημα θα προσφέρει λύσεις και οφείλει στην επιχείρηση.

Η ομάδα έργου πρέπει να συνεργαστεί με διάφορα τμήματα της επιχείρησης τα οποία έχει άμεση σχέση με την επιχειρηματική ανάγκη (π.χ τμήμα λογιστηρίου, τμήμα μάρκετινκ). Στη συνέχεια πραγματοποιείται η διεξαγωγή της ανάλυσης σκοπιμότητας. Η ανάλυση σκοπιμότητας εξετάζει κάποιες βασικές πτυχές του έργου όπως είναι:

  • Η τεχνική επιτευξημότητας της ιδέας, η οποία απαντάει στο ερώτημα μπορούμε να το φτιάξουμε;

  • Η οικονομική σκοπιμότητα που απαντάει στο ερώτημα θα προσφέρει όφελος στην επιχείρηση και εάν ναι σε πόσο χρονικό διάστημα περίπου;

  • Η εταιρική σκοπιμότητα που απαντάει στο ερώτημα αν το κατασκευάσουμε, θα χρησιμοποιηθεί;

Η αίτηση συστήματος και η ανάλυση σκοπιμότητας παρουσιάζονται σε μία επιτροπή επίβλεψης έργων ώστε να αποφασίσει αν είναι κατάλληλο προς υλοποίηση.

Αν το έργο εγκριθεί τότε περνά στη φάση της διαχείρισης έργου όπου ο διευθυντής οργανώνει και συντονίζει την ομάδα έργου που θα είναι υπεύθυνη για την ολοκλήρωσή του. Το παραδοτέο της διαχείρισης έργου είναι ένα σχέδιο έργου, το οποίο περιγράφει πως θα προσεγγίσει η ομάδα την ανάπτυξη του συστήματος.

2. Ανάλυση

Κατά την ανάλυση συστήματος η ομάδα έργου προσπαθεί να απαντήσει στις ερωτήσει ποιος θα χρησιμοποιήσει το σύστημα, τι θα κάνει αυτό; που και πότε θα χρησιμοποιηθεί; Αυτή η φάση ερευνά τρία βήματα:

  1. Αρχικά προσδιορίζεται η στρατηγική ανάλυσης που θα πρέπει να ακολουθήσει η ομάδα έργου. Αυτή η στρατηγική περιλαμβάνει σχέδια και γνώση από το υπάρχον σύστημα της εταιρείας αλλά και τρόπους σχεδιασμού ενός νέου συστήματος.

  2. Στη συνέχεια η ομάδα έργου προσπαθεί να συγκεντρώσει διάφορες πληροφορίες από άτομα που έχουν γνώση του έργου (συλλογή πληροφοριών μέσω ερωτηματολογίων ή μέσω συνεντεύξεων). Έπειτα δημιουργείται η κεντρική ιδέα του συστήματος από την οποία παράγεται το μοντέλο ανάλυσης. Το μοντέλο ανάλυσης περιγράφει πως θα λειτουργεί η επιχείρηση με τη λειτουργία του νέου αυτού συστήματος.

  3. Τέλος παράγεται η πρόταση συστήματος η οποία αποτελεί την συνένωση της κεντρικής ιδέας του συστήματος και του μοντέλου ανάλυσης, και παραδίδεται στον εντολέα έργου ο οποίος θα αποφασίσει αν θα προχωρήσει το έργο στον σχεδιασμό.

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

3. Σχεδιασμός

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

  1. Η ανάπτυξη της στρατηγικής σχεδιασμού που θα ακολουθήσει η ομάδα έργου. Σε αυτό το βήμα αποφασίζεται αν οι προγραμματιστές θα είναι εντός της εταιρείας ή θα γίνει πρόσληψη έμπειρων προγραμματιστών σε θέματα ανάπτυξης συστημάτων ή θα αγοραστεί και θα εγκατασταθεί έτοιμο πακέτο λογισμικού.

  2. Επόμενο και βασικό βήμα της φάσης του σχεδιασμού είναι η αρχιτεκτονική σχεδιασμού για το σύστημα, η οποία περιγράφει το υλικό, το λογισμικό και τη δικτυακή υποδομή που θα χρησιμοποιηθούν. Με αυτό το βήμα γίνεται πιο ξεκάθαρο πως οι χρήστες θα κινούνται εντός τους συστήματος χωρίς να αντιμετωπίζουν προβλήματα κατά τη λειτουργία του.

  3. Αναπτύσσονται οι προδιαγραφές δεδομένων και αρχείων τα οποία καθορίζουν που θα αποθηκεύονται και που θα χρησιμοποιούνται.

  4. Τέλος η ομάδα έργου διατυπώνει το σχέδιο προγράμματος κατά το οποίο καθορίζει τα προγράμματα που πρέπει να γραφτούν και τι ακριβώς κάνει το καθένα.

Το παραδοτέο που συντελείται κατά τη φάση του σχεδιασμού είναι η προδιαγραφή συστήματος η οποία αποστέλλεται στην ομάδα προγραμματισμού. Στο τέλος επανεξετάζονται οι φάσεις ώστε να δούμε λεπτομερώς αν ξεχάσαμε κάτι ή έγινε κάπου λάθος διατύπωση κατά τη συλλογή απαιτήσεων.

4. Υλοποίηση

Η τελευταία φάση του κύκλου ζωή ενός συστήματος είναι η φάση της υλοποίησης. Κατά τη διάρκεια αυτής της φάσης προγραμματίζεται το σύστημα και παραδίδεται στους άμεσα ενδιαφερομένους. Συνήθως η φάση αυτή επισκιάζει τις υπόλοιπες διότι χρειάζεται περισσότερο χρόνο για να πραγματοποιηθεί. Διαθέτει τρία βήματα:

  1. Το πρώτο βήμα είναι η κατασκευή του συστήματος. Το σύστημα κατασκευάζεται και ελέγχεται από την ομάδα έργου. Το βήμα αυτό είναι πολύ σημαντικό διότι πρέπει να αντιμετωπιστούν με επιτυχία τυχών σφάλματα που προκύπτουν κατά τον προγραμματισμό του συστήματος.

  2. Το δεύτερο βήμα είναι η εγκατάσταση του συστήματος στη κατάλληλη υποδομή της επιχείρησης. Αυτό το κομμάτι χρειάζεται ιδιαίτερη προσοχή γιατί είναι και ο καθοριστικός παράγοντας επιτυχίας του συνολικού συστήματος. Στην αρχή το σύστημα για κάποιο μικρό χρονικό διάστημα εγκαθίσταται δοκιμαστικά σε ένα τμήμα της επιχείρησης και αν λειτουργεί σωστά τότε εξαπλώνεται και στα υπόλοιπα τμήματα.

  3. Η ομάδα ανάλυσης καθορίζει ένα σχέδιο υποστήριξης το οποίο περιλαμβάνει μια επίσημη ή άτυπη επισκόπηση μετά την υλοποίηση.


Contia Thessaloniki

Σειριακή και Δυαδική Αναζήτηση

Εισαγωγή

Το πρόβλημα της αναζήτησης το συναντάμε πολλές φορές στην καθημερινότητά μας. Για παράδειγμα, για την αγορά ενός προϊόντος θα πρέπει να αναζητήσουμε σε μία λίστα από προϊόντα του καταστήματος για να βρούμε αυτό που ψάχνουμε. Επίσης, κατά την αναζήτηση μίας επαφής στο κινητό μας χρειάζεται να σκρολάρουμε πολλές φορές για να βρούμε την επαφή που ψάχνουμε (αν δεν γνωρίζουμε το όνομα του αποστολέα) ή να γράψουμε το όνομα του αποστολέα στην “μηχανή αναζήτησης” του κινητού και να κάνει αυτό την δουλειά για εμάς. Καταμετρώντας τον αριθμό παραδειγμάτων που συναντάμε το πρόβλημα της αναζήτησης διαπιστώνουμε εύκολα ότι ακόμα και για την πιο μικρή εργασία μας πρέπει να κάνουμε αναζήτηση.

Σε αντιστοιχία με τον πραγματικό κόσμο, η αναζήτηση είναι ένα σημαντικό πρόβλημα και στον εικονικό. Για παράδειγμα η αναζήτηση όλων των φίλων ενός ατόμου σε έναν 2D πίνακα όπου οι σειρές και οι στήλες αναπαριστούν άτομα και κάθε κελί παίρνει τιμές 0 ή 1 αν δύο άτομα είναι φίλοι. Μία τέτοια εργασία  ενδέχεται να κάνει μία ιστοσελίδα κοινωνικής δικτύωσης.

Σε αυτό το άρθρο θα μελετήσουμε δύο διαφορετικούς τρόπους αναζήτησης. Ο πρώτος τρόπος είναι με βάση την ωμή βία (σειριακή αναζήτηση) και ο δεύτερος βασίζεται στην τεχνική διαίρει και βασίλευε (δυαδική αναζήτηση) (το παρόν άρθρο δεν αναλύει περισσότερο αυτές τις δύο τεχνικές αλλά μπορείτε να μάθετε γι’αυτές από βιβλία σχετικά με την σχεδίαση αλγορίθμων)

Σειριακή αναζήτηση

Η σειριακή αναζήτηση είναι ένας αλγόριθμος ο οποίος σαρώνει έναν πίνακα μέχρι να βρει την πρώτη εμφάνιση ενός στοιχείου που αναζητείται. Το στοιχείο αυτό αναφέρετε ως κλειδί (key). Ένας απλός αλγόριθμος σε μορφή ψευδοκώδικα για αναζήτηση σε μονοδιάστατο πίνακα είναι ο παρακάτω


     Είσοδος: Ένας μονοδιάστατος πίνακας Α[Ν], ένα κλειδί Χ 
     Έξοδος:  Η θέση του πίνακα που βρέθηκε το κλειδί αλλιώς -1 
     i = 0 
     βρέθηκε = ψευδής 
     θέση = 0
     Όσο i < N και βρέθηκε == αληθής επανάλαβε
          Άν X == A[i] τότε
               βρέθηκε = αληθής
               θέση = i
          Τέλος_αν
          i = i + 1
      Τέλος_όσο
      Αν βρέθηκε == αληθής τότε
            Τύπωσε θέση
      Αλλιώς
            Τύπωσε -1
       Τέλος_αν




Δίνοντας ως είσοδο έναν μονοδιάστατο πίνακα μεγέθους Ν και ένα κλειδί Χ ο αλγόριθμος τυπώνει την θέση του πίνακα που βρέθηκε το κλειδί. Για να το πετύχει αυτό σαρώνει επαναληπτικά τον πίνακα μέχρις ότου ένας μετρητής να φτάσει το μέγεθος του πίνακα ή μέχρι να βρεθεί το κλειδί αν υπάρχει στον πίνακα. (Στις περισσότερες γλώσσες προγραμματισμού οι πίνακες ξεκινούν την αρίθμηση τους από την μηδενική θέση - έτσι και εδώ ακολουθήθηκε αυτή η σύμβαση). Έπειτα, ανάλογα με το αν βρέθηκε ή όχι το κλειδί "τυπώνετε στην οθόνη" είτε η θέση είτε η τιμή -1.

Ο αλγόριθμος αυτός είναι απλός και ικανοποιεί τις ανάγκες μας για αναζήτηση παρόλα αυτά όταν η είσοδος είναι πολύ μεγάλη (δλδ. το μέγεθος του πίνακα) τότε αυτή η διαδικασία είναι πολύ χρονοβόρα. Φανταστείτε ότι έχετε έναν τηλεφωνικό κατάλογο με 10 ονόματα. Αναζητώντας όλα τα άτομα 1 προς 1 σύντομα θα βρείτε αυτό που ψάχνετε. Αν όμως είχατε 5000 ονόματα; Η αναζήτηση θα κρατούσε πολύ περισσότερη ώρα.

Διαισθητικά είδαμε ότι το μέγεθος του πίνακα είναι αυτό που επηρεάζει την απόδοση, όμως, δεν είναι μόνο αυτό. Ένας ακόμη παράγοντας που επηρεάζει την απόδοση σε αντιστοιχία με το μέγεθος του πίνακα είναι ο αριθμός συγκρίσεων. Για να γίνουμε πιο κατανοητοί θα μελετήσουμε δύο περιπτώσεις. Στη πρώτη περίπτωση (στη καλύτερη) το στοιχείο που αναζητούμε βρίσκετε στην πρώτη θέση του πίνακα. Οπότε απαιτείται μία μόνο σύγκριση. Αυτό το σενάριο είναι το καλύτερο και ο αλγόριθμος είναι πολύ αποδοτικός. Αντίθετα στην δεύτερη περίπτωση (στην χειρότερη) ο αλγόριθμος δεν βρίσκει το στοιχείο στον πίνακα είτε το βρίσκει στην τελευταία θέση. Για να το γνωρίζει όμως αυτό θα πρέπει να ψάξει ολόκληρο το πίνακα άρα θα πρέπει να κάνει τόσες συγκρίσεις όσες το μέγεθος του πίνακα. Άρα αν ο πίνακας είναι μεγέθους Ν απαιτούνται Ν συγκρίσεις. Άρα λέμε ότι ο χρόνος εκτέλεσης της αναζήτησης στην χειρότερη περίπτωση είναι γραμμικός. Ενώ ο χρόνος εκτέλεσης στην καλύτερη περίπτωση είναι σταθερός.

Είναι όμως αυτός ο αλγόριθμος ο καλύτερος ή μπορούμε να έχουμε αλγορίθμους με μικρότερο χρόνο εκτέλεσης;

Δυαδική Αναζήτηση

Έστω ότι θέλετε να ψάξετε για έναν όρο μέσα σε ένα λεξικό. Αν ξεκινήσετε την αναζήτηση από τον πρώτο όρο και ψάξετε σειριακά για να βρείτε τον όρο, αργά η γρήγορα θα κουραστείτε και θα τα παρατήσετε. Υπάρχει ένα στοιχείο που είναι σημαντικό και δεν λάβατε υπόψιν κατά την αναζήτησή σας. Το λεξικό έχει όλους τους όρους ταξινομημένους σε αύξουσα διάταξη. Πως θα εκμεταλλευόσασταν αυτή την πληροφορία;

Ας πούμε ότι αναζητούμε τον όρο "φάσμα". Ανοίγουμε το λεξικό στη μέση και πέφτουμε στο γράμμα "κ". Γνωρίζουμε ότι η λέξη που ψάχνουμε βρίσκεται στο δεξί τμήμα του λεξικού οπότε αγνοούμε τις λέξεις στο διάστημα α-κ. Εφαρμόζουμε την ίδια τεχνική στο διάστημα κ-ω και πέφτουμε στο γράμμα "τ". Πάλι, γνωρίζουμε ότι στο διάστημα κ-τ δεν υπάρχει η λέξη άρα ψάχνουμε με τον ίδιο τρόπο στο διάστημα τ-ω. Επαναλαμβάνουμε αυτήν την διαδικασία μέχρις ότου βρούμε την σελίδα που περιέχει το γράμμα "φ". Όπως διαπιστώνουμε, αυτή η προσέγγιση είναι καλύτερη και πιο αποδοτική από την σειριακή αναζήτηση. Αυτός ο τρόπος αναζήτησης ονομάζεται δυαδική αναζήτηση και είναι ιδιαίτερα δημοφιλής. Παρακάτω παρουσιάζουμε ένα ψευδοκώδικα


     Είσοδος: Ένας ταξινομημένος μονοδιάστατος πίνακας Α[Ν], λέξη κλειδί Χ
     Έξοδος:  Η θέση του πίνακα που βρέθηκε το κλειδί αλλιώς -1 
     θέση = [Ν/2]
     βρέθηκε = ψευδής
     Όσο θέση >= 0 και θέση < Ν και βρέθηκε == ψευδής επανάλαβε 
           Αν Α[θέση] == Χ τότε 
                 βρέθηκε = αληθής 
           Αλλιώς
              Αν Χ > Α[θέση] τότε 
                 θέση = θέση + [θέση/2]
              Αλλιώς
                 θέση = θέση - [θέση/2]
           Τέλος_αν
         Τέλος_αν
     Τέλος_όσο 
     Αν βρέθηκε == αληθής τότε
        Τύπωσε θέση
     Αλλιώς 
         Τύπωσε -1 
    Τέλος_αν




Ο αλγόριθμος παίρνει στην είσοδό του έναν ταξινομημένο πίνακα Α και ένα κλειδί και η έξοδός του είναι η θέση που βρέθηκε το κλειδί ή -1 αν το κλειδί δεν υπάρχει. Η αναζήτηση ξεκινάει από το μεσαίο στοιχείο του πίνακα αλλιώς από τη θέση που ορίζεται από το ακέραιο μέρους της διαίρεσης Ν/2. Έπειτα, ξεκινάει η επανάληψη η οποία όπως και πριν εκτελείται μέχρι να βρεθεί το κλειδί ή μέχρι ο δείκτης (θέση) να είναι έξω από τα επιτρεπόμενα όρια του πίνακα. Αν το κλειδί βρεθεί τότε αλλάζουμε την μεταβλητή σε αληθής. Αλλιώς θέτουμε την νέα θέση ανάλογα με το αν η τιμή του πίνακα στην προηγούμενη θέση είναι μικρότερη ή μεγαλύτερη από την το κλειδί.

Ένα παράδειγμα εκτέλεσης παρουσιάζεται παρακάτω:

%Contia %κατασκευή ιστοσελίδων

Διαισθητικά αντιλαμβανόμαστε ότι με αυτήν την προσέγγιση μπορούμε να κάνουμε λιγότερες συγκρίσεις για να φτάσουμε στο κλειδί που αναζητούμε. Αλλά πόσες; Στην καλύτερη περίπτωση το στοιχείο βρίσκεται στην θέση που ορίσαμε δηλαδή στη μεσαία θέση του πίνακα. Οπότε όπως και στην σειριακή αναζήτηση έτσι και εδώ ο χρόνος εκτέλεσης είναι σταθερός και απαιτείται μόνο μία σύγκριση. Για την χειρότερη περίπτωση θα αναπαραστήσουμε τα δεδομένα του πίνακα με την μορφή ενός πλήρους δυαδικού δένδρου.

Χωρίς βλάβη της γενικότητας, ορίζουμε ένα πλήρες δυαδικό δένδρο όπου το δεξί παιδί είναι μικρότερο από τον πατέρα και το αριστερό παιδί μεγαλύτερο. Ένα παράδειγμα δυαδικού δένδρου δίνεται παρακάτω.

%Contia %κατασκευή ιστοσελίδων

Στην χειρότερη περίπτωση, το κλειδί που αναζητούμε βρίσκεται στα φύλλα. Επομένως, ο αριθμός των συγκρίσεων που πρέπει να κάνουμε ισούται με το ύψος του δυαδικού δένδρου. Για να υπολογίσουμε το συνολικό αριθμό των στοιχείων ανά επίπεδο εργαζόμαστε ως εξής: στο πρώτο επίπεδο έχουμε ένα στοιχείο, στο δεύτερο 2 στοιχεία, στο τρίτο 4 κοκ. Παρατηρούμε ότι καθώς αυξάνεται ο αριθμός των επιπέδων τα στοιχεία αυξάνονται εκθετικά. Οπότε, αν ορίσουμε το τελευταίο επίπεδο ως k . Θα πρέπει \( 2^k +1 = N \). Λογαριθμίζοντας, προκύπτει \( k = log_2(N-1) \).  Επομένως εφόσον παραπάνω είπαμε ότι στην χειρότερη περίπτωση θα πρέπει να αναζητήσουμε το κλειδί στα φύλλα του δέντρου (δηλαδή στο τελευταίο επίπεδο), προκύπτει ότι ο χρόνος εκτέλεσης για να φτάσουμε στα φύλλα είναι λογαριθμικός. Επομένως, ο χρόνος εκτέλεσης στην χειρότερη περίπτωση είναι επίσης λογαριθμικός

Με την παραπάνω προσέγγιση αποδείξαμε τον χρόνο εκτέλεσης του αλγορίθμου δυαδικής αναζήτησης στην χειρότερη περίπτωση. Παρατηρούμε ότι ο χρόνος εκτέλεσης είναι πολύ καλύτερος από αυτόν της σειριακής γι'αυτό δικαίως αποτελεί μία πολύ καλή λύση στο πρόβλημα της αναζήτησης όταν ο πίνακας είναι ταξινομημένος.

Κάποιες χρήσιμες πηγές

  1. Δυαδική Αναζήτηση - python
  2. Δυαδική Αναζήτηση - παράδειγμα προγράμματος στην c

Contia Θεσσαλονίκη

Υπερμοντελοποίηση στην Μηχανική Μάθηση (overfitting)

Εισαγωγή

Οι αλγόριθμοι της επιβλεπόμενης  μηχανικής μάθησης (supervised machine learning) επιδιώκουν την δημιουργία μοντέλων (models) τα οποία εκπαιδεύονται από ένα σύνολο εκπαίδευσης(train set/ training set) με την βοήθεια χαρακτηριστικών (features) που έχουν προκύψει κατά την ανάλυση των δεδομένων πηγής. Σκοπός ενός μοντέλου μπορεί είναι να ταξινομεί (classify) νέες περιπτώσεις βάση ενός συνόλου κατηγοριών. Για να είναι εφικτή αυτή η λειτουργία θα πρέπει το μοντέλο που θα δημιουργηθεί να μπορεί να γενικεύσει.




Τι εννοούμε γενίκευση;

Για να κατανοήσουμε καλύτερα τον σκοπό των μοντέλων που έχουν προκύψει από επιβλεπόμενη μάθηση προσπαθώντας να λύσουν το πρόβλημα της ταξινόμησης (classification) θα δώσουμε ένα παράδειγμα. Σκεφτείτε ότι την επόμενη μέρα δίνετε εξετάσεις στη σχολή σας γνωρίζοντας τα θέματα των προηγούμενων ετών. Πιστεύοντας ότι και τα φετινά θέματα θα είναι τα ίδια, εστιάζετε την μελέτη σας μόνο σε αυτά. Αν τελικά στις εξετάσεις τα θέματα είναι ίδια με των παλαιότερων ετών τότε θα είστε σε θέση να γράψετε και ίσως να αριστεύσετε. Από την άλλη μεριά, αν τα θέματα είναι διαφορετικά το μόνο σίγουρο είναι ότι θα έχετε μία δύσκολη μέρα.

Ας μεταφέρουμε το παράδειγμα στην ανάλυση που κάναμε προηγουμένως. Κατά την εκπαίδευσή σας δεν γενικεύσατε με βάση τις γνώσεις που πήρατε από τα παλιά θέματα. Αντιθέτως, γνωρίσατε πολύ καλά ένα συγκεκριμένο σύνολο θεμάτων. Έτσι, το “μοντέλο” που χτίσατε δεν μπόρεσε να τα πάει καλά σε νέες περιπτώσεις που δεν ταιριάζουν στο σύνολο δεδομένων που εκπαιδευτίκατε. Τι όμως πήγε στραβά; Την απάντηση σε αυτό θα μας την δώσει η έννοια της υπερμοντελοποίησης (overfitting)

Υπερμοντελοποίηση

Ένας επίσημος ορισμός στην περίπτωση της ανάλυσής μας από το Oxford Dictionary θα σας διαφωτίσει.

The production of an analysis which corresponds too closely or exactly to a particular set of data, and may therefore fail to fit additional data or predict future observations reliably.

Εν ολίγοις αναφέρει ότι όταν η παραγωγή μίας ανάλυσης είναι προσαρμοσμένη σε ένα συγκεκριμένο σύνολο δεδομένων (set of data / dataset)  με αποτέλεσμα να μην μπορεί (η παραγωγή) να προσαρμοστεί σε νέα δεδομένα ή να προβλέψει νέες παρατηρήσεις αξιόπιστα παρατηρείται το φαινόμενο της υπερμοντελοποίησης.

Στην περίπτωση του παραδείγματος που δόθηκε παραπάνω, το σύνολο δεδομένων είναι τα παλιά θέματα ενώ η προσαρμογή σε νέα δεδομένα είναι η δυνατότητα του φοιτητή να γράψει τα νέα θέματα.

Περιπτώσεις υπερμοντελοποίσης μπορούμε να έχουμε όταν.

  1. Τα δεδομένα εκπαίδευσης δεν ταιριάζουν με τις νέες περιπτώσεις. Για παράδειγμα, φανταστείτε ότι θέλετε να ταξινομήσετε κάποια email σε ανεπιθύμητη ή επιθυμητή αλληλογραφία. Έστω ότι τα email που διαθέτουμε ως σύνολο εκπαίδευσης είναι μόνο ανεπιθύμητα. Το μοντέλο που θα χτιστεί δεν θα είναι σε θέση να προβλέψει μία νέα περίπτωση email ως επιθυμητή αλληλογραφία καθώς δεν θα έχει δει προγενέστερα μία τέτοια περίπτωση.
  2. Η επιλογή χαρακτηριστικών. Ως παράδειγμα θα χρησιμοποιήσουμε το παράδειγμα με την αλληλογραφία. Έστω ότι κάθε χαρακτηριστικό είναι μία λέξη σε ένα δοσμένο λεξικό της αγγλικής γλώσσας μαζί με λέξεις από την σύγχρονη τεχνολογία. Επίσης, το μοντέλο εκπαιδεύεται ώστε να μπορεί να προβλέψει αν η αλληλογραφία είναι επιθυμητή ή όχι βρίσκοντας συνδυασμούς λέξεων (π.χ. την λέξη δωρεάν και την λέξη iphone). Αν σε μία νέα περίπτωση email προκύψει κάποιος νέος όρος π.χ drone που δεν υπάρχει στο λεξικό τότε θα αγνοηθεί από το μοντέλο σε μία φράση τύπου “δωρεάν drone”, ή “χαρίζονται drone” με αποτέλεσμα να προβλεφθεί το email λάθος ως επιθυμητό.
  3. Η παραμετροποίηση (tuning) των αλγορίθμων μηχανικής μάθησης κατά την εκπαίδευση του μοντέλου. Όπως, αναφέρετε στο sklearn η παραμετροποίηση είναι μία επιθυμητή ενέργεια που την εφαρμόζουν πολλοί ερευνητές με σκοπό την βελτίωση των αποτελεσμάτων τους. Παρόλα αυτά, η επιλογή αλγορίθμων και η παραμετροποίησή τους θα πρέπει να γίνεται στο σύνολο εκπαίδευσης  και να δοκιμάζεται το μοντέλο σε άγνωστα δεδομένα. Σε αντιστοιχία με το παράδειγμα με τα παλιά θέματα που δόθηκε παραπάνω, εφαρμόζοντας διαφορετικούς τρόπους για να μάθει ο φοιτητής τα παλιά θέματα δεν οδηγεί σε καλύτερα αποτελέσματα όταν προκύψουν νέες περιπτώσεις.

Για την επίλυση της υπερμοντελοποίησης και για την καλύτερη γενίκευση του μοντέλου που χτίζουμε θα μπορούσαμε να σπάσουμε (split) το σύνολο των δεδομένων μας σε σύνολο εκπαίδευσης (train set) και σύνολο δοκιμής (test set).  Εφαρμόζοντας αυτή την τεχνική, μπορούμε να κάνουμε διάφορες δοκιμές στο σύνολο εκπαίδευσης και όταν καταλήξουμε στις καλύτερες τότε βλέπουμε τα αποτελέσματα στο test set. Προσοχή όμως, δοκιμάζοντας διάφορες τεχνικές στο σύνολο εκπαίδευσης με σκοπό τα καλύτερα αποτελέσματα στο σύνολο δοκιμής, είναι και αυτό μία μορφή υπερμοντελοποίησης.

Κάποιες χρήσιμες πηγές

  1. Machine Learning: The Art and Science of Algorithms that Make Sense of Data 
  2. Overfitting 





Contia

Τι είναι Αλγόριθμος;

Εισαγωγή

Διαισθητικά ορίζουμε την έννοια του αλγορίθμου ως ένα σύνολο βημάτων τα οποία καθορίζουν τον τρόπο εκτέλεσης μίας εργασίας. Για παράδειγμα, τα βήματα που ακολουθεί ένα παιδί για να πάει στο σχολείο θα μπορούσαν να είναι τα εξής:

  1. Σήκω από το κρεβάτι
  2. Βγάλε τις πυτζάμες σου
  3. Βάλε τα ρούχα σου για το σχολείο
  4. Επισκέψου το μπάνιο
  5. Πάρε κλειδιά
  6. Βγες από το σπίτι
  7. Κλείδωσε
  8. Ακολούθησε τον δρόμο για το σχολείο

Προφανώς, για την επίτευξη του ίδιου σκοπού  θα μπορούσατε να ακολουθήσετε διαφορετικά βήματα. Επίσης, η σειρά των βημάτων θα μπορούσε να είναι διαφορετική. Για παράδειγμα, κάποιο παιδί ενδέχεται να επισκεφθεί πρώτα το μπάνιο και έπειτα να βγάλει τα ρούχα του. Αλλά, δεν μπορεί να βάλει τα ρούχα για το σχολείο χωρίς να βγάλει τις πυτζάμες (ίσως κάποιες φορές υπάρχουν εξαιρέσεις).

Οπότε για να ταιριάξουμε το παράδειγμα που δόθηκε με τον διαισθητικό ορισμό, η εργασία που καλείται να εκτελέσει το παιδί είναι η προετοιμασία για το σχολείο. Τα βήματα που πρέπει να ακολουθήσει είναι τα 8 παραπάνω. Άρα, αυτό το παράδειγμα είναι ένας αλγόριθμος. Επίσης, επειδή θα μπορούσαν διαφορετικά βήματα να οριστούν, λέμε ότι υπάρχουν διαφορετικοί αλγόριθμοι για την εκτέλεση της ίδιας εργασίας.




Ορισμός

Ένας αλγόριθμος είναι ένα διατεταγμένο σύνολο σαφώς ορισμένων, εκτελέσιμων βημάτων, το οποίο ορίζει μία τερματιζόμενη διαδικασία

Για να απλουστεύσουμε τον ορισμό, θα προσπαθήσουμε να εξηγήσουμε κάθε αναγραφόμενη πληροφορία δίνοντας επιπλέον παραδείγματα.

Ο ορισμός αναφέρει ότι το σύνολο των βημάτων θα πρέπει να είναι διατεταγμένο. Αυτό το στοιχείο σχετίζεται με την σειρά εκτέλεσης των βημάτων. Δηλαδή, τα βήματα θα πρέπει να ακολουθούν μία συγκεκριμένη ροή. Στο παράδειγμα που δώσαμε παραπάνω, για να επιτευχθεί η εργασία (προετοιμασία για το σχολείο), το παιδί θα πρέπει να ακολουθήσει την συγκεκριμένη ροή των βημάτων για να πετύχει τον στόχο του.

Τα βήματα θα πρέπει να είναι εκτελέσιμα. Αν ένα βήμα δεν μπορεί να εκτελεστεί τότε δεν μπορεί να εκτελεστεί η εργασία. Για παράδειγμα, φανταστείτε κάποιος να σας ζητούσε να πετάξετε (χωρίς αεροπλάνο) για να φτάσετε στην δουλειά σας. Η εργασία που πρέπει να πετύχετε είναι να πάτε στην δουλειά σας και το ένα βήμα που πρέπει να ολοκληρώσετε είναι το πέταγμα. Το βήμα αυτό είναι μη εκτελέσιμο.

Σαφώς ορισμένα βήματα. Ένα βήμα θα πρέπει να ακολουθεί συγκεκριμένες οδηγίες. Για παράδειγμα, ακολουθήστε τα βήματα για την εύρεση ενός σπιτιού:

  1. Επισκεφθείτε την σελίδα Χ ενοικίασης σπιτιών
  2. Επιλέξτε το καλύτερο σπίτι

Το πρώτο βήμα είναι σαφώς ορισμένο, καθώς υπάρχει μία συγκεκριμένη οδηγία που πρέπει να ακολουθήσεις. Αντιθέτως, το βήμα 2  είναι χαοτικό. Προκύπτουν πολλά ερωτήματα με αποτέλεσμα το βήμα αυτό να θεωρείται ασαφές.

Τέλος, ο αλγόριθμος πρέπει να ορίζει μία τερματιζόμενη διαδικασία. Αυτό το στοιχείο περισσότερο ταιριάζει με το κομμάτι της επιστήμης των υπολογιστών. Είναι σημαντικό για την κοινότητα να γνωρίζει πότε ένα πρόβλημα μπορεί να λυθεί αλγοριθμικά.





Contia

Η δομή δεδομένων Dictionary στην Python




Ένα λεξικό (dictionary) στην python (ο λεγόμενος πίνακας κατακερματισμού σε άλλες γλώσσες προγραμματισμού) είναι μία δομή δεδομένων η οποία αποθηκεύει ζευγάρια της μορφής <κλειδί,τιμή>.  Σε αντίθεση με τις λίστες, στις οποίες η αναζήτηση γίνεται με βάση κάποιον ακέραιο δείκτη που δείχνει σε συγκεκριμένη θέση μέσα στην λίστα, στο λεξικό η αναζήτηση γίνεται με βάση κάποιο κλειδί. Έτσι, έχουμε ζευγάρια της μορφής (string,[]), ( tuple, string) , (int,[]) κ.α.

Δημιουργία Λεξικού

Για την δημιουργία ενός λεξικού στην python αρκεί να ορίσουμε my_dict = {} ή my_dict = { 'tooth':'teeth' , 'find':'found' } ή my_dict = dict(). Η πρώτη και η τελευταία δήλωση αρχικοποιούν ένα κενό λεξικό ενώ η δεύτερη εισάγει τα ζεύγη (tooth,teeth) και (find,found).

Εισαγωγή ζεύγους στο Λεξικό

Η εισαγωγή ενός ζεύγους σε ένα λεξικό είναι πολύ απλή. Για παράδειγμα, έστω ότι θέλουμε να δημιουργήσουμε έναν ανεστραμμένο κατάλογο (inverted index) στα τρία “έγγραφα” που βλέπουμε παρακάτω:

  • doc1: Οι γάτες κυνηγούν τα ποντίκια
  • doc2: Οι γάτες φοβούνται το σκοτάδι
  • doc3: Τα ποντίκια ζούνε στα υπόγεια

Θεωρούμε ότι κάποια βασική επεξεργασία του κειμένου έχει γίνει (π.χ stemming, stopwords removal) και έστω ότι έχουν εξαχθεί οι λέξεις ( γάτα, κυνηγώ, ποντίκι, φοβάμαι, σκοτάδι, ζω, υπόγειο). Αυτές οι λέξεις αποτελούν το λεξιλόγιό μας. Σκοπός, είναι να αποθηκεύσουμε σε μία δομή δεδομένων τις λέξεις του λεξιλογίου και για κάθε λέξη να κρατάμε μία λίστα με όλα τα έγγραφα στα οποία η λέξη έχει εμφανισθεί. Ο κώδικας που προκύπτει είναι:

 
voc = ['γάτα','ποντίκι','σκοτάδι',...]
docs= ['γάτα κυνηγώ  ποντίκι','γάτα φοβάμαι σκοτάδι' ...]
i_i = dict()
for word in voc:
  i_i[word] = []  #κάθε λέξη πρέπει να έχει μία λίστα 
  for i in range(0,len(docs)):
     if word in doc:  #αν η λέξη υπάρχει στο ι-οστό έγγραφο
        i_i[word].append(i) #κρατάμε τον δείκτη i
        break
  

Αναζήτηση με βάση το κλειδί

Συνεχίζοντας το προηγούμενο παράδειγμα, για να βρούμε την λίστα των εγγράφων που περιέχουν την λέξη ‘γάτα’ και ύστερα να την τυπώσουμε αρκεί να γράψουμε print i_i['γάτα'] . Σε περίπτωση που θέλουμε να διατρέξουμε την λίστα και να τυπώσουμε τον δείκτη κάθε εγγράφου σε ξεχωριστή γραμμή, το ακόλουθο σκριπτ μας δίνει τη λύση:

for doc_id in i_i['γάτα']:
   print doc_id

Και αν επιθυμούμε να τυπώσουμε το κείμενου του ι-οστού εγγράφου αρκεί να γράψουμε print docs[doc_id]

Αναζήτηση με βάση την τιμή

Ας υποθέσουμε ότι θέλουμε για το έγγραφο 2 να τυπώσουμε όλες τις λέξεις που εμφανίζονται σε αυτό. Το σκριπτ είναι:

id=2
for key in i_i:
    if id in i_i[key]:
       print key

Διαγραφή ενός ζεύγους από το λεξικό

Για την διαγραφή ενός ζεύγους αρκεί να χρησιμοποιήσουμε την δεσμευμένη λέξη κλειδί del ως εξής : del i_i[key]

Βιβλιογραφία

  1. https://docs.python.org/2/tutorial/datastructures.html
  2. http://www.nltk.org/book/ch05.html
  3. https://www.tutorialspoint.com/python/python_dictionary.htm

data file

Το πρόγραμμα γράφει κενό αρχείο

Σαν νέος προγραμματιστής έχει τύχει πολλές φορές να υλοποιείται ένα πρόγραμμα το οποίο γράφει σε ένα αρχείο και όταν το εκτελείται ή κάποιες φορές όταν τελειώνει η εκτέλεση του, το αρχείο να είναι κενό.

Το ερώτημα που προκύπτει και θα απαντηθεί παρακάτω είναι το εξής :

Γιατί κατά την εκτέλεση του προγράμματος δεν δημιουργούνται δεδομένα στο αρχείο;

Για το σκοπό της συζήτησής μας θα φέρουμε στο προσκήνιο τη γλώσσα γενικού σκοπού C. Το πλεονέκτημα της C έναντι των άλλων γλωσσών προγραμματισμού είναι ότι μας δίνει δυνατότητες για χαμηλού επιπέδου προγραμματισμό. Έτσι, θα είμαστε πιο κοντά στη μηχανή για να καταλάβουμε την συμπεριφορά της.

Πείραμα

Για τα πειράματά μας θα χρησιμοποιηθούν δύο συναρτήσεις:

  1. int open(const char *path, int oflags, mode_t mode);
  2. FILE *fopen(const char *filename, const char *mode);

Η συνάρτηση (1) χρησιμοποιείται για χαμηλού επιπέδου πρόσβασης σε αρχείο ενώ η συνάρτηση (2) ανήκει στην Standard I/O βιβλιοθήκη της C.

Οι βιβλιοθήκες που θα χρησιμοποιηθούν είναι οι εξής

#include  
#include 
#include 
#include 
#include 

Για την συνάρτηση (1) ο κώδικας είναι

int main(){
   int out;
   out = open("file.out",O_WRONLY|O_CREAT, S_IRUSR|S_IWUSR);
   for (int i=0; i< 10;i++) {
       write(out,&i,1);
       sleep(2);
   }
   return 0;
}

Για την συνάρτηση (2) ο κώδικας είναι

int main(){
   FILE *out;
   out = fopen("file.out");
   for (int i=0; i< 10;i++) {
       fputc(i,out);
       sleep(2);
   }
   return 0;
}

Τα δύο προγράμματα είναι αρκετά απλά. Τυπώνουν 10 χαρακτήρες με κώδικα ASCII στο διάστημα [0-9] σε αρχείο file.out ανά δύο δευτερόλεπτα.

Εκτέλεση

Αν εκτελέσετε τα δύο τμήματα κώδικα θα διαπιστώσετε ότι κατά την εκτέλεση του πρώτου μπορείτε να δείτε τα δεδομένα του αρχείου. Από την άλλη, αν εκτελέσετε τον δεύτερο τμήμα κώδικα το αρχείο είναι άδειο. Έτσι προκύπτει το εξής υπο-ερώτημα

Ποια είναι η διαφορά των δύο τμημάτων κώδικα;

Η διαφορά οφείλεται στις δύο συναρτήσεις που γράφουν στο αρχείο. Η συνάρτηση write() κάθε φορά που εκτελείται κάνει και μία κλήση συστήματος. Οπότε, η εγγραφή γίνεται κατευθείαν στο αρχείο και έτσι ο κειμενογράφος μπορεί να διαβάσει τα δεδομένα του. Από την άλλη, η συνάρτηση fputc() γράφει τα αποτελέσματα σε μία ενδιάμεση μνήμη (buffer) και όταν κρίνει αυτή απαραίτητο "αδειάζει" τα περιεχόμενά του στο αρχείο (συνήθως όταν γεμίσει ή όταν κληθεί κάποια άλλη συνάρτηση που αναγκάζει το buffer να μεταφέρει τα δεδομένα του στην έξοδο).  Εδώ όμως προκύπτει το εξής υπο ερώτημα

Γιατί να μην χρησιμοποιηθεί η write() έναντι της fputc() ;

Για να δούμε τι πλεονέκτημα έχει η μία μέθοδος έναντι της άλλης ας αυξήσουμε το διάστημα από [0-9] σε [0-999.999] και διαγράφουμε από το κάθε τμήμα κώδικα το sleep. Αν δουλεύετε σε linux μπορείτε να χρησιμοποιήσετε το εργαλείο time για να μετρήσετε το χρόνο του κάθε τμήματος κώδικα. Οι χρόνοι που προκύψανε είναι

write(): 6,9 δευτερόλεπτα
fputc(): 0,075 δευτερόλεπτα

Η write() είναι αρκετά πιο αργή από την fputc() διότι κάθε φορά που εκτελείται γίνεται μία κλήση συστήματος. Να σημειωθεί ότι τα αποτελέσματα των χρόνων σχετίζονται με πολλούς παράγοντες (π.χ πόσες διεργασίες εκτελούνται, προδιαγραφές συστήματος κ.α). Άρα, ενδέχεται να έχετε άλλα αποτελέσματα, αλλά σίγουρα η write() θα είναι πιο αργή από την fputc().


Artificial Intelligence - Contia

Το μέλλον της Τεχνητής Νοημοσύνης (Artificial Intelligence)

Συνοπτικά ο επιστημονικός τομέας της Τεχνητής Νοημοσύνης (Artificial Intelligence) περιλαμβάνει την επιστήμη και την εφαρμοσμένη μηχανική της κατασκευής ευφυών μηχανών με ειδικά ευφυή προγράμματα υπολογιστών. Για τον λόγο αυτό η ΤΝ μπορεί επίσης να χαρακτηρισθεί και ως ο διεπιστημονικός τομέας όπου η πληροφορική συναντάται με τη φιλοσοφία, την ψυχολογία, τη γλωσσολογία, τα μαθηματικά, τις νευροεπιστήμες, την εφαρμοσμένη μηχανική και άλλους επιστημονικούς τομείς.
Σήμερα αν και κανένας δεν είναι σε θέση ακόμα να ισχυρισθεί ότι έχει κατανοήσει όλα τα γνωρίσματα της ανθρώπινης νοημοσύνης και να τα εφαρμόσει σε μια τεχνητή οντότητα, υπάρχουν αμέτρητα προγράμματα ΤΝ που εξελίσσονται σε όλο τον κόσμο.

Όλο και περισσότεροι επιστήμονες αναρωτιούνται τι θα συμβεί στο μέλλον με την εξέλιξη του κλάδου της τεχνητής νοημοσύνης (Artificial Intelligence) καθώς έχουν μπει για τα καλά στις ζωές μας. Πολλοί είναι αυτοί που πιστεύουν ότι η χρήση της τεχνητής νοημοσύνης μπορεί να είναι μοιραία για το ανθρώπινο είδος αφού έχουμε παραδείγματα robots που έχουν αντικαταστήσει σε πολλές δουλείες τον ανθρώπινο παράγοντα, όπως για παράδειγμα σε πολλές αυτοκινητοβιομηχανίες όπου η συναρμολόγηση των αυτοκινήτων πραγματοποιείται αποκλειστικά από robots<>.

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

Η Contia υπέρμαχος της τεχνητής νοημοσύνης

Η Contia από την πλευρά της τάσσετε υπέρμαχος της επιστημονικής κοινότητας της τεχνητής νοημοσύνης συμβάλλοντας με αυτό τον τρόπο στην εξέλιξή της. Το πεδίο έρευνας της εταιρείας μας είναι ένα μέρος της τεχνητής νοημοσύνης το οποίο είναι η επεξεργασία φυσικής γλώσσας.
Σαν εταιρεία πληροφορικής έχουμε χρέος να ερευνούμε διάφορα επιστημονικά ζητήματα και συγκεκριμένα να είμαστε υποστηρικτές σύγχρονων τεχνολογιών ώστε να ενισχύσουμε την επιστημονική κοινότητα τόσο της Ελλάδας όσο και του εξωτερικού.


articles categories

Archieves

Donate

Help us to improve our blog. Please donate, if theses posts related with your interests
1,00
Personal Info

Donation Total: 1,00€