ΚΕΦΑΛΑΙΟ 3 Εξόρυξη γνώσης από μουσική πληροφορία

Η διαδικασία εξόρυξης ΕΠ παρουσιάζεται στις εργασίες [71], [88], όπου δυο αλγόριθμοι προτείνονται για την ανεύρεση των μη-τετριμμένων ΕΠ και της χαρακτηριστικής μελωδικής συμβολοσειράς. Ο πρώτος αλγόριθμος χρησιμοποιεί μια αμοιβαία συσχετιζόμενη μήτρα για την εξαγωγή των ΕΠ, ενώ ο δεύτερος βασίζεται σε μια επαναλαμβανόμενη λειτουργία ένωσης συμβολοσειρών. Πειραματικά αποτελέσματα των εργασιών [71], [88] υποδεικνύουν την υπεροχή του δεύτερου αλγόριθμου σε σχέση με τη μέθοδο με την αμοιβαία συσχετιζόμενη μήτρα. Περισσότερες πληροφορίες για τη μέθοδο με την ένωση συμβολοσειρών δίνονται στην Ενότητα 3.1.3. Οι Koh και Yu [79] παρουσίασαν μια μέθοδο εξόρυξης των ΜΜΕΠ από τη μελωδία ενός μουσικού δεδομένου χρησιμοποιώντας μια ακολουθία bit index όπως επίσης και μια επέκταση για την εξαγωγή των συχνών ακολουθιών νοτών από ένα σύνολο μουσικών αντικειμένων. Στη μέθοδο που προτείνεται στην εργασία [79], όλα τα ΕΠ βρίσκονται και επιβεβαιώνονται υπολογίζοντας τη συχνότητα εμφάνισής τους, ενώ ο έλεγχος πλεονασμού εκτελείται σε επόμενο στάδιο δημιουργώντας το σύνολο ΜΜΕΠ με μη αποδοτικό τρόπο. Οι Rolland και Ganascia [101], πρότειναν μια μέθοδο για την κατά προσέγγιση εξαγωγή των σειριακών προτύπων σε μουσικά δεδομένα, η οποία εξετάζει ένα πλήθος ιδιαιτεροτήτων των μουσικών δεδομένων και βασίζεται στον ορισμό μιας συνάρτησης ομοιότητας.

Όσον αφορά στη συμμετοχή των ΕΠ στην ανεύρεση των μουσικών θεμάτων, οι Smith και Medina [105] πρότειναν μια τεχνική ταιριάσματος προτύπων, η οποία καταλήγει στα μουσικά θέματα και βασίζεται σε πρότερη συλλογή των ΜΜΕΠ. Οι Meek και Birmingham στην εργασία [94] προσδιόρισαν μια πληθώρα χαρακτηριστικών, που απαιτείται να εξαχθούν από τα μουσικά δεδομένα για την ανεύρεση των μουσικών θεμάτων. Μεταξύ αυτών, θεωρούν ως σημαντικότερο τη θέση του θέματος (προτιμώντας τα θέματα που εμφανίζονται νωρίτερα στο μουσικό δεδομένο). Καθώς τέτοια χαρακτηριστικά, που προκύπτουν από ΕΠ, μπορούν να χρησιμοποιηθούν για την ανεύρεση των μουσικών θεμάτων, οι εργασίες [94], [105] μπορούν να θεωρηθούν συμπληρωματικές στο πρόβλημα που αντιμετωπίζει το παρόν κεφάλαιο. Επιπλέον, ένα ενδιαφέρον σύστημα για την ανεύρεση μουσικών θεμάτων βασισμένο στον παγκόσμιο ιστό παρουσιάζεται στην [80].

Τα πρότυπα είναι πιθανό να μη βρίσκονται μόνο σε μια φωνή (στην περίπτωση της πολυφωνικής μουσικής), καθώς ένα πρότυπο μπορεί να είναι κατανεμημένο σε αρκετές παράλληλα ηχούσες φωνές. Οι συγγραφείς των [75], [76] παρουσίασαν αλγόριθμους για την ανεύρεση κατανεμημένων προτύπων μεταξύ των οποίων και για το ταίριασμα κατανεμημένων προτύπων με το μέγιστο $k$ διαφορές (εξέλιξη μοτίβου).

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

Επιπλέον, όπως ήδη αναφέρθηκε, τα ΜΜΕΠ είναι επαναλαμβανόμενα πρότυπα και “περιέχουν” όλα τα ΕΠ που παράγονται ως υποακολουθίες τους. Κατά συνέπεια, τα ΜΜΕΠ εκ φύσεως μεταφέρουν τη σημασιολογική αξία των αντίστοιχων ΕΠ (των ιδίων ΜΜΕΠ αλλά και των ΕΠ που είναι υποακολουθίες τους). Η σημασιολογική αξία των ΕΠ περιγράφεται περαιτέρω στις [88], [68], [71], [79]. Ειδικότερα, τα πειραματικά αποτελέσματα στην εργασία [88] παρουσιάζουν ποσοστό ανάκλησης 100% στην εξαγωγή μουσικών μοτίβων από ΕΠ (δηλ. όλα τα μοτίβα πρέπει να είναι ΕΠ). Επίσης, οι εργασίες [71], [88] καταλήγουν ότι η ομαδοποίηση των μουσικών αντικειμένων μπορεί να γίνει αποδοτικά βάσει ΕΠ. Ωστόσο, πρέπει να καταστεί σαφές ότι τα ΜΜΕΠ είναι πρότυπα που αποκαλύπτουν μια διαφορετική, νέα όψη των μουσικών δεδομένων.

Στον τομέα της εξόρυξης στοιχειοσυνόλων, τελευταία προτάθηκαν διάφορες μέθοδοι για την ανεύρεση των μεγίστου μήκους συχνών στοιχειοσυνόλων [65], [87], [114]. Οι εργασίες αυτές εστιάζουν στην αποφυγή εξέτασης όλων των συχνών στοιχειοσυνόλων, μεταφέροντας την έρευνα προς τη γρήγορη ανεύρεση των στοιχειοσυνόλων που έχουν μέγιστο μήκος ή αυτών που είναι maximal³³Καθώς δεν υπάρχει δόκιμος όρος στην Ελληνική, στο κεφάλαιο αυτό παραμένει στην Αγγλική και έχει την εξής μαθηματική έννοια: Ένα maximal στοιχείο ενός υποσυνόλου $S$ ενός μερικώς ταξινομημένου συνόλου, είναι το στοιχείο του $S$ το οποίο δεν είναι μικρότερο από κανένα άλλο στοιχείο στο $S$(δηλ. δεν έχουν υπερσύνολο που να είναι επίσης συχνό). Εμφανώς, υπάρχει μια ευδιάκριτη αναλογία μεταξύ του προβλήματος που εξετάζουν οι εργασίες [65], [87], [114] και του προβλήματος της ανεύρεσης των ΜΜΕΠ. Ωστόσο, η διαδικασία εξόρυξης των ΜΜΕΠ παρουσιάζει σημαντικές διαφορές εξαιτίας των οποίων, οι προαναφερθείσες μέθοδοι, δεν μπορούν να εφαρμοστούν άμεσα.

Πρωτίστως, η κύρια διαφορά των μεθόδων για μεγάλα στοιχειοσύνολα είναι η εστίαση τους σε ογκώδεις, εγκατεστημένες σε δίσκο βάσεις στοιχειοσυνόλων. Ακολούθως, οι τεχνικές που χρησιμοποιούνται στις εργασίες [65], [87], [114] μειώνουν τον αριθμό προσβάσεων στη βάση με τη χρήση δομών βελτιστοποιημένων για μεγάλο όγκο δεδομένων. Αντιθέτως, για την εξόρυξη μουσικών ΕΠ και ΜΜΕΠ, η μουσική ακολουθία βρίσκεται στην κύρια μνήμη και οι εμπλεκόμενες δομές και τεχνικές έχουν κύριο στόχο την ταχύτητα εκτέλεσης. Συνεπώς, η εφαρμογή υπαρκτών μεθόδων για μεγάλα στοιχειοσύνολα θα ήταν ιδιαίτερα μη αποδοτική, καθώς οι βελτιστοποιήσεις τους αφορούν στο κόστος εισόδου/εξόδου. Για το λόγο αυτό, οι συγγραφείς της εργασίας [71] δεν προσπάθησαν την άμεση εφαρμογή μιας μεθόδου εξόρυξης για βάσεις ακολουθιών, όπως επίσης και στην εργασία [60] για το πρόβλημα της εξόρυξης ΕΠ σε μουσικές ακολουθίες. Επιπλέον, στο πεδίο της εξόρυξης ΕΠ και ΜΜΕΠ, μια υποακολουθία της μουσικής ακολουθίας είναι ΕΠ εάν η συχνότητα εμφάνισης της είναι μεγαλύτερη της μονάδας. Αντίθετα, οι αλγόριθμοι εξόρυξης μεγάλων στοιχειοσυνόλων θεωρούν αρκετά μεγαλύτερο κατώφλι για τη συχνότητα εμφάνισης των προτύπων⁴⁴Ακόμα και μικρά ποσοστά κατωφλιού εμφάνισης, λ.χ., 0.1%, αντιστοιχούν σε πολύ μεγαλύτερες τιμές απ’ ότι η απόλυτη τιμή της μονάδας., οπότε είναι αναπόφευκτο να έχουν αυξημένη επιβάρυνση στην περίπτωση που θεωρήσουν κατώφλι συχνότητας εμφάνισης ίσο με τη μονάδα.

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

Θεωρούμε τη μουσική ακολουθία να είναι μια ακολουθία χαρακτήρων από ένα αλφάβητο διακριτών στοιχείων. Γενικά, η μουσική περιγράφεται από αρκετά χαρακτηριστικά. Μεταξύ αυτών το τονικό ύψος, ο ρυθμός, η χροιά και η δυναμική θεωρούνται τα πιο σημασιολογικά αξιόλογα [66]. Ειδικότερα, για τη μουσική δυτικού τύπου, το τονικό ύψος έχει το μεγαλύτερη πληροφοριακή βαρύτητα [66]. Παρότι, το χαρακτηριστικό του ρυθμού δεν μπορεί να αγνοηθεί, χάριν ευκολότερης αναπαράστασης, εστιάζουμε στην πληροφορία που περιέχεται στο τονικό ύψος. Παρόμοια υπόθεση έχει γίνει και σε πολλές σχετικές εργασίες που αντιμετωπίζουν την ανεύρεση ΕΠ [71], [79], [105]. Ωστόσο, είναι ευνόητο ότι η προτεινόμενη μεθοδολογία μπορεί εύκολα να εφαρμοστεί σε ακολουθίες χαρακτηριστικών ρυθμού. Στην κατεύθυνση αυτή, θα ήταν ενδιαφέρουσα η διερεύνηση του συνδυασμού των δύο σημαντικών χαρακτηριστικών (δηλ., τονικό ύψος και ρυθμός) στα πρότυπα που βρέθηκαν. Όμως στην περίπτωση αυτή ελάχιστες παραλλαγές των θεμάτων θα οδηγούσαν σε διαφοροποιημένες συνδυαστικές ακολουθίες. Έτσι, θα χρειάζονταν ανάπτυξη μεθόδων που δεν θα ήταν ευαίσθητες σε μικρές παραλλαγές ώστε να μη χάνονται αρκετά ΕΠ.

Εδώ πρέπει να αναφερθεί ότι για την αναπαράσταση που ακολουθείται από το πρωτόκολλο MIDI, το μέγεθος του αλφάβητου (πλήθος διακριτών στοιχείων) είναι ίσο με 128. Η συχνότητα επανάληψης $\sigma \upsilon \chi \nu (\mathrm{\Pi })$ (εφεξής συχνότητα) ενός ΕΠ $\mathrm{\Pi }$ ορίζεται ως ο αριθμός των εμφανίσεων του $\mathrm{\Pi }$ στην $A$. Το μήκος $|\mathrm{\Pi }|$ ενός ΕΠ $\mathrm{\Pi }$ είναι το πλήθος των νοτών στο $\mathrm{\Pi }$.

Ο ανωτέρω ορισμός αρχικά απαιτεί ένα ΕΠ $X$, για να είναι ΜΜΕΠ, να μην είναι υποακολουθία άλλου ΕΠ $X^{\prime }$, με το οποίο να έχουν ίδια συχνότητα, στην οποία περίπτωση το $X^{\prime }$ είναι το maximal. Επιπλέον, ο ορισμός απαιτεί το $X$ να έχει το μέγιστο μήκος από κάθε ΕΠ $X^{\prime }$. Παραδείγματος χάριν, στην ακολουθία Α = εαβγδεβγαβγδβγα, υπάρχουν 13 ΕΠ, που παρουσιάζονται στον Πίνακα 3.1 με τις αντίστοιχες συχνότητες εμφάνισης.

Εκ των 13 αυτών ΕΠ, το $\{\alpha \beta \gamma \delta \}$ είναι ΜΜΕΠ (καθώς είναι το maximal και δεν υπάρχει άλλο ΕΠ $X^{\prime }$ στην $A$ τέτοιο ώστε $|X^{\prime }|>|X|$), τα $\{\alpha ,\beta \gamma ,\beta \gamma \delta ,\beta \gamma \}$ είναι maximal, ενώ τα υπόλοιπα είναι τετριμμένα.

Τέλος, ο ορισμός του υπό εξέταση προβλήματος στο παρόν κεφάλαιο είναι ο εξής: δεδομένης μιας μουσικής ακολουθίας $A$, να βρεθούν όλα τα ΜΜΕΠ, εφόσον υπάρχουν.

Όπως έχει ήδη σχολιαστεί στην Ενότητα 3.1.2, ο Hsu και οι συνεργάτες του στην εργασία [71] πρότειναν δυο διαφορετικές τεχνικές για την ανεύρεση των μη-τετριμμένων ΕΠ. Εδώ, εστιάζουμε στον αλγόριθμο με την ένωση συμβολοσειρών, στον οποίο αναφερόμαστε ως HLC (από τα αρχικά των συγγραφέων). Ο HLC θα παρουσιαστεί επιγραμματικά (με τη βοήθεια ενός παραδείγματος), ώστε να περιγραφεί η καταλληλότητα του ως βασικού αλγορίθμου για την εξαγωγή των ΜΜΕΠ (βλ. Ενότητα 3.1.3).

Ο HLC χρησιμοποιεί την τριάδα $\{X,\sigma \upsilon \chi \nu (\mathrm{{\rm X}}),(\vartheta ϵ\sigma {\eta }_1,\vartheta ϵ\sigma {\eta }_2,\mathrm{\dots })\}$ για να αναπαραστήσει το κάθε ΕΠ που βρέθηκε σε μια μουσική ακολουθία $\mathrm{{\rm A}}$, όπου $X$ είναι το ΕΠ, $\sigma \upsilon \chi \nu (X)$ είναι η συχνότητα εμφάνισης του $X$ και κάθε $\vartheta ϵ\sigma {\eta }_i,1\le i\le \sigma \upsilon \chi \nu (\mathrm{{\rm X}})$, είναι το σημείο εκκίνησης του $X$ στην $A$. Σύμφωνα με την [71] η διαδικασία ένωσης συμβολοσειρών ορίζεται ως εξής: Υποθέτουμε ότι οι τριάδες: $\{{\alpha }_1{\alpha }_2\mathrm{\dots }{\alpha }_m,\sigma \upsilon \chi \nu ({\alpha }_1{\alpha }_2\mathrm{\dots }{\alpha }_m),(p_1,p_2,\mathrm{\dots },p_i)\}$ και
$\{{\beta }_1{\beta }_2\mathrm{\dots }{\beta }_n,\sigma \upsilon \chi \nu ({\beta }_1{\beta }_2\mathrm{\dots }{\beta }_n),(q_1,q_2,\mathrm{\dots },q_j)\}$
είναι δυο ΕΠ της συμβολοσειράς χαρακτηριστικών του μουσικού αντικειμένου. Ορίζεται η $k$-τάξης ένωση συμβολοσειρών $(k\ge 0)$ των δυο ΕΠ ως εξής:

όπου

• •

  $i=\sigma \upsilon \chi \nu ({\alpha }_1{\alpha }_2\mathrm{\dots }{\alpha }_m)$, $j=\sigma \upsilon \chi \nu ({\beta }_1{\beta }_2\mathrm{\dots }{\beta }_n)$, $h=\sigma \upsilon \chi \nu ({\gamma }_1{\gamma }_2\mathrm{\dots }{\gamma }_l)$,

• •

  ${\gamma }_t={\alpha }_t$ για $1\le t\le m$, ${\gamma }_t={\beta }_{t-m+k}$ για $m+1\le t\le l=m+n-k$,

• •

  $o_t=x=y-m+k$, όπου $x\in \{p_1,p_2\mathrm{\dots },p_i\}$ και $y\in \{q_1,q_2\mathrm{\dots },q_j\}$⁵⁵Η προϋπόθεση αυτή αναφέρεται στη συσχέτιση των στοιχείων στην ακολουθία $\gamma$ με τις θέσεις εμφάνισης των ακολουθιών $\alpha$ και $\beta$.,

• •

  , για $1\le t\le h-1$,

• •

  if $k>0$, ${\alpha }_{m-k+s}={\beta }_s$, για $1\le s\le k$.

Ο HLC εξελίσσεται σε 2 στάδια: Στο πρώτο εντοπίζονται τα ΕΠ μήκους $2^k$ (αρχικά, $k=0$), ενώ τα ΕΠ μήκους $2^{k+1}$ συνθέτονται εφαρμόζοντας ενώσεις ΕΠ μήκους $2^k$. Η έρευνα, κατά τη διάρκεια του πρώτου σταδίου, συνεχίζει μέχρι να βρεθεί μία τιμή του $k$, έστω $k_l$, για την οποία δεν υπάρχουν ΕΠ. Στο σημείο αυτό, ο HLC πρέπει να καθορίσει το μήκος $L$ του μέγιστου σε μήκους ΕΠ, το οποίο δεν είναι γνωστό εκ προοιμίου. Ωστόσο, το μήκος $L$ του μέγιστου ΕΠ είναι γνωστό ότι είναι μεταξύ . Επομένως, ο HLC εκτελεί δυαδική αναζήτηση για πρότυπα τα μήκη των οποίων είναι στο διάστημα $[2^{k_{l-1}},2^{k_l})$. Στο τέλος του πρώτου σταδίου, ο HLC έχει προσδιορίσει το $L$ και τα αντίστοιχα ΜΜΕΠ. Με το δεύτερο στάδιο, επιβεβαιώνει ότι όλα τα πρότυπα που βρέθηκαν στο προηγούμενο στάδιο είναι μη-τετριμμένα με τη βοήθεια μιας δενδρικής δομής που ονομάζεται RP-δένδρο, της οποίας κάθε κόμβος αποτελεί ένα από τα ΕΠ που βρέθηκαν. Μετά την αφαίρεση των τετριμμένων ΕΠ, μια πιο λεπτομερής διαδικασία εντοπίζει ΕΠ με μήκος που δεν είναι δύναμη του δυο, εφόσον υπάρχουν. Τα ΕΠ που προκύπτουν μετά την τελευταία αυτή διαδικασία εισάγονται στο RP-δένδρο. Τέλος, όλα τα τετριμμένα πρότυπα διαγράφονται, αφήνοντας το RP-δένδρο να περιέχει μόνο τα ΜΜΕΠ και τα μικρότερα μη-τετριμμένα ΕΠ, ολοκληρώνοντας το δεύτερο στάδιο του HLC.

Για να γίνει περισσότερο κατανοητή η λειτουργία του HLC, παραθέτουμε ένα παράδειγμα της εκτέλεσης του σε μια υποθετική μουσική ακολουθία (το παράδειγμα αυτό θα αποτελέσει και το τρέχον παράδειγμα στο κεφάλαιο αυτό). Έστω μια μουσική ακολουθία $S$, όπου S = EBCDEHGABFJDEHGJEBCDEABFJ. Ακολουθώντας τα προαναφερθέντα, τα ΕΠ μήκους 1, 2, 4 υφίστανται, παρότι το $E\mathrm{\Pi }[8]=\mathrm{\varnothing }$, όπου το ΕΠ[χ] ενέχει την έννοια του συνόλου των ΕΠ με μήκος $\chi$. Για να προσδιοριστεί το $L$ (και τα αντίστοιχα ΜΜΕΠ), θεωρούμε ότι $k_l=3$, εφόσον $8=2^3$; ενώ $k_{l-1}=2$, εφόσον $4=2^2$ και ΕΠ[4] είναι το τελευταίο μήκος για το οποίο υφίστανται ΕΠ. Ακολούθως, ο αλγόριθμος ψάχνει τις ενδιάμεσες τιμές μήκους 5, 6 και 7 ανακαλύπτοντας το ΕΠ[5]={EBCDE,2,(1,8)} $E\mathrm{\Pi }[6]=\mathrm{\varnothing }$ και $E\mathrm{\Pi }[7]=\mathrm{\varnothing }$. Κατά συνέπεια, $L$ = 5 και το σύνολο των ΜΜΕΠ είναι το ΕΠ[5]={EBCDE,2,(1,8)} (δηλ., το ΕΠ[5] περιέχει μόνο ένα ΜΜΕΠ). Το αποτέλεσμα του πρώτου σταδίου του HLC παρουσιάζεται στο Σχήμα 3.1, όπου το ΜΜΕΠ βρίσκεται στη ρίζα. (Στο Σχήμα 3.1, τα μη-τετριμμένα ΕΠ εμφανίζονται με τονισμένες γραμμές). Το επόμενο στάδιο του HLC δεν παρουσιάζει ενδιαφέρον για το παρόν καφάλαιο καθώς εστιάζει στα ΜΜΕΠ (που βρέθηκαν στο πρώτο στάδιο), κατά συνέπεια τα βήματα του HLC που εκτελούνται στο δεύτερο στάδιο παραλείπονται.

Βασιζόμενοι στα προαναφερθέντα, πρέπει να διευκρινιστεί πως μεταξύ των μη-τετριμμένων ΕΠ, ο HLC ανακαλύπτει το σύνολο των ΜΜΕΠ. Εμφανώς, αυτό γίνεται με πολύ αποδοτικό τρόπο λόγω των ακόλουθων: (i) Απαιτείται να βρεθεί μόνο ένα λογαριθμικό πλήθος ενδιάμεσων μηκών για την ανεύρεση των ΜΜΕΠ (τα μήκη τύπου $2^k$ εξετάζονται μέχρι να βρεθεί ένα $k_l$ και τότε χρησιμοποιείται δυαδική αναζήτηση στο διάστημα $[2^{k_{l-1}},2^{k_l})$), ενώ μια απλοϊκή μέθοδος θα εξέταζε όλα τα πιθανά μήκη μεταξύ 1 και $L$. (ii) Πειραματικές μετρήσεις μπορούν να δείξουν ότι το απαιτητικότερο στάδιο σε χρόνο εκτέλεσης του HLC είναι το δεύτερο στάδιο, όπου δημιουργείται το RP-δένδρο και απαλείφονται τα τετριμμένα πρότυπα. Σε περίπτωση που το ενδιαφέρον εστιάζεται στην ανεύρεση των ΜΜΕΠ και μόνο, τότε το δεύτερο στάδιο μπορεί να παραληφθεί πλήρως.

Για τους λόγους αυτούς, μια τροποποιημένη εκδοχή του HLC (η οποία περιλαμβάνει μόνο το πρώτο του στάδιο) μπορεί να θεωρηθεί ως ένας καλός βασικός αλγόριθμος για εύρεση των ΜΜΕΠ, καθώς σαφώς υπερνικά την απλοϊκή μέθοδο. Ωστόσο, πρέπει να αναφερθεί ότι ο HLC δεν σχεδιάστηκε εξαρχής μονάχα για την ανεύρεση των ΜΜΕΠ. Παρότι εντοπίζει το σύνολο των ΜΜΕΠ χρησιμοποιώντας μόνο λογαριθμικό πλήθος ενδιάμεσων βημάτων, σε κάθε ένα από τα βήματα αυτά πρέπει να εντοπίσει όλα τα ΕΠ του βήματος. Καθώς το μέγιστο μήκος μπορεί να είναι της τάξης των μερικών εκατοντάδων, ο HLC πρέπει να εκτελέσει ενώσεις και να υπολογίσει τη συχνότητα μεγάλου αριθμού ΕΠ. Το γεγονός αυτό είναι ιδιαιτέρως εμφανές στα αρχικά βήματα, όταν το πλήθος των ΕΠ με σχετικά μικρό μήκος είναι κατά πολύ αυξημένο, εξαιτίας της μη-μονοτονικής ιδιότητας⁶⁶Σύμφωνα με την ιδιότητα της μη-μονοτονίας, μια υποακολουθία $X$ της $A$ δεν μπορεί να είναι ΕΠ εκτός εάν όλες οι υποακολουθίες της $X$ είναι επίσης ΕΠ (εδώ δεν ενδιαφερόμαστε για τη διαφοροποίηση μεταξύ τετριμμένων και μη, καθώς τα ΜΜΕΠ είναι εξ ορισμού μη-τετριμμένα).. Συνεπώς, απαιτείται μια άλλη μέθοδος που θα αποφεύγει όσο το δυνατό περισσότερο το κόστος εξέτασης (δηλ., τον υπολογισμό της συχνότητα εμφάνισης) των ενδιάμεσων προτύπων.

Τέλος, πρέπει να γίνει μνεία στην εργασία των Koh και Yu [79] όπου προτείνουν μια διαφορετική προσέγγιση για την ανεύρεση των ΕΠ. Η μέθοδος τους χρησιμοποιεί ένα πίνακα bit-index και εντοπίζει όλα τα ΕΠ με μοναδιαία αύξηση μήκους. Συνεπώς, η μέθοδος αυτή προσεγγίζει το επίπεδο των ΜΜΕΠ εξετάζοντας όλα τα ενδιάμεσα μήκη και όχι μόνο ένα λογαριθμικό πλήθος όπως ο HLC. Επιπλέον, παρόμοια με τον HLC, σε κάθε εξεταζόμενο επίπεδο, η μέθοδος της εργασίας [79], ελέγχει όλα τα ΕΠ. Πειραματικά αποτελέσματα στην [79] καταδεικνύουν μια βελτίωση του συνολικού χρόνου εκτέλεσης σε σύγκριση με τον HLC. Ωστόσο, τα αποτελέσματα αυτά αναφέρονται στη διαδικασία ανεύρεσης όλων των ΕΠ, όπου ο HLC περιλάμβανε την εκτέλεση του δαπανηρού δεύτερου σταδίου του. Κατά συνέπεια, ο τροποποιημένος HLC θεωρείται αποδοτικότερος από τη μέθοδο των Koh & Yu, όσον αφορά στο πρόβλημα της ανεύρεσης μόνο των ΜΜΕΠ.

Στην ενότητα αυτή περιγράφεται ο αλγόριθμος που M${}^2$P (Mining Maximum-length Patterns, Εξόρυξη μεγίστου μήκους προτύπων) βάσει των αποτελεσμάτων της εργασίας [77]. Ο αλγόριθμος M${}^2$P εξελίσσεται ως εξής: Έστω $A=⟨{\alpha }_1,\mathrm{\dots },{\alpha }_{\nu }⟩$ μια μουσική ακολουθία μήκους $\nu$. Υποθέτουμε ότι έχουν εντοπιστεί όλα τα ΕΠ μήκους δύο, ΕΠ[2] = $\{⟨{\alpha }_i,{\alpha }_j⟩:{\alpha }_i,{\alpha }_j\in A,\sigma \upsilon \chi \nu (⟨{\alpha }_i,{\alpha }_j⟩)\ge 2\}$. Τα στοιχεία της $A$ και του ΕΠ[2] σχηματίζουν ένα κατευθυνόμενο γράφο $\mathrm{\Gamma }(K,H)$, όπου το σύνολο των κόμβων $K(\mathrm{\Gamma })$ αντιστοιχεί στο σύνολο όλων των στοιχείων της $A$ και το σύνολο όλων των ακμών $H(\mathrm{\Gamma })$ στο σύνολο όλων των στοιχείων του ΕΠ[2] (δηλ., μια κατευθυνόμενη ακμή $⟨{\alpha }_i\to {\alpha }_j⟩$ στο γράφο αντιστοιχεί στο μέλος $⟨{\alpha }_i,{\alpha }_j⟩$ του ΕΠ[2]).

Κάθε μονοπάτι $M$ στο $\mathrm{\Gamma }$ μπορεί να θεωρηθεί ως πιθανό ΕΠ, καθώς όλα τα υπομονοπάτια του μήκους δύο (δηλ., οι κατευθυνόμενες ακμές) είναι ΕΠ. Συνεπώς, το σύνολο όλων των πιθανών μονοπατιών του $\mathrm{\Gamma }$ σχηματίζουν το χώρο έρευνας του εξεταζόμενου προβλήματος, καθώς τα ΜΜΕΠ είναι επίσης ΕΠ και αντιστοιχούν σε μονοπάτια του $\mathrm{\Gamma }$. Μια απλοϊκή προσέγγιση θα εξέταζε τον πλήρη γράφο, όπου κάθε πιθανό ζεύγος στοιχείων της $A$ θα αποτελούσε μια ακμή. Ωστόσο, η μέθοδος αυτή οδηγεί σε έναν υπέρμετρο αριθμό πιθανών μονοπατιών, ενώ (εξαιτίας της μη-μονοτονικής ιδιότητας) το πλήθος αυτό περικόπτεται δραστικά χάρις στο γεγονός ότι οι ακμές αντιστοιχούν μόνο σε μέλη του ΕΠ[2].

Ο αντικειμενικός σκοπός του M${}^2$P είναι να εντοπίσει στον προαναφερθέντα χώρο έρευνας τα μονοπάτια εκείνα που έχουν το μέγιστο μήκος και αντιστοιχούν σε ΕΠ. Για να το κατορθώσει αυτό, ο M${}^2$P διασχίζει το $\mathrm{\Gamma }$ ερευνώντας τα μονοπάτια που πηγάζουν από οποιονδήποτε από τους κόμβους του. Καθώς συναντά μονοπάτια, ο M${}^2$P ασχολείται μόνο με εκείνα που είναι υποψήφια να είναι ΜΜΕΠ (δηλ., όχι μόνο ΕΠ). Κατά τη διάρκεια της διάσχισης, κρατά αναφορά του μονοπατιού $\mathrm{\Phi }$ που έχει ήδη επισκεφτεί και: (i) έχει το μέγιστο μήκος μέχρι του σημείου αυτού, και (ii) αντιστοιχεί σε ΕΠ (δηλ., η συχνότητα του έχει υπολογιστεί και βρεθεί να είναι μεγαλύτερη του δυο)⁷⁷Αρχικά, κάθε ακμή του $\mathrm{\Gamma }$ μπορεί να να επιλεχθεί ως τέτοιο μονοπάτι.. Ο περιορισμός του χώρου έρευνας επιτυγχάνεται απορρίπτοντας τις προεκτάσεις (δηλ., προσαρτήματα κόμβων και ακμών κατά τη διάσχιση) μονοπατιών των οποίων η συχνότητα μετρήθηκε και δεν επαρκούσε ώστε να θεωρηθούν ΕΠ, καθώς καμία από τις προεκτάσεις τους δεν οδηγούσε σε ΜΜΕΠ (εξαιτίας της ιδιότητας της μη μονοτονικότητας, μιας και ένα ΜΜΕΠ είναι ΕΠ). Συνεπώς, κατά την πρόοδο της διάσχισης του $\mathrm{\Gamma }$, τρεις περιπτώσεις χρήζουν μνείας:

1η Περίπτωση:

Εάν το τρέχον μονοπάτι $M$ που έχει επισκεφτεί ο αλγόριθμος έχει μήκος μικρότερο από $|\mathrm{\Phi }|$, τότε η μέτρηση της συχνότητας του μπορεί να αποφευχθεί (καθώς δεν είναι ΜΜΕΠ με βεβαιότητα).

2η Περίπτωση:

Εάν $|M|>|\mathrm{\Phi }|$, τότε υπολογίζεται η συχνότητα του αντίστοιχου προτύπου στην $A$ και εάν βρεθεί το πρότυπο να είναι επαναλαμβανόμενο, τότε το $\mathrm{\Phi }$ εξισώνεται με το $M$. Εναλλακτικά, εάν δεν είναι ΕΠ, τότε (όπως έχει ήδη περιγραφεί) η διάσχιση δεν συνεχίζει σε κανένα μονοπάτι που να περιέχει το $M$.

3η Περίπτωση:

Τέλος, εάν το μήκος του $M$ είναι ίσο με το μήκος του $|\mathrm{\Phi }|$, τότε ο υπολογισμός της συχνότητας αποφεύγεται στο σημείο αυτό και διατηρούμε ένα πίνακα και τον συνδέουμε με το $\mathrm{\Phi }$. Εάν μετά το τέλος της διάσχισης του $\mathrm{\Gamma }$ δεν έχουν βρεθεί άλλα ΕΠ με μήκος μεγαλύτερο του $|\mathrm{\Phi }|$, όλα τα μονοπάτια που έχουν συνδεθεί με το $\mathrm{\Phi }$ είναι επίσης υποψήφια να είναι ΕΠ (το $\mathrm{\Phi }$ έχει επιβεβαιωθεί ως ΜΜΕΠ, εφόσον ήταν το πρώτο μονοπάτι το μήκος του οποίου εξετάσθηκε κατά τη διάσχιση, άρα και η συχνότητα του έχει υπολογιστεί εξαιτίας της πρώτης περίπτωσης.

Βάσει των προηγουμένων, ο M${}^2$P υπολογίζει τη συχνότητα ενός μονοπατιού μόνο εάν το μήκος είναι τέτοιο ώστε είναι πιθανό να είναι ΜΜΕΠ. Για το λόγο αυτό, αναβάλλει όσο το δυνατό περισσότερο τη δαπανηρή διαδικασία μέτρησης της συχνότητας, στοχεύοντας στην εύρεση νέων υποψηφίων με μεγαλύτερο μήκος. Το αποτέλεσμα είναι ότι ο M${}^2$P, αντίθετα με τον HLC, αποφεύγει τη μέτρηση της συχνότητας όλων των μονοπατιών ενός συγκεκριμένου μήκους. Αντίθετα, προσδιορίζει τη συχνότητα μονοπατιών συγκεκριμένου μήκους μόνο, έως ότου βρεθεί το πρώτο μονοπάτι που αντιστοιχεί σε ΕΠ. Τέλος, όταν τελειώσει η διάσχιση, εξετάζονται όλα τα συνδεδεμένα μονοπάτια που είναι συνδεδεμένα με το αρχικό ΜΜΕΠ (δηλ., εκείνα τα μονοπάτια με μήκος ίσο με το μέγιστο μήκος που βρέθηκε για το $|\mathrm{\Phi }|$), ώστε να βρεθούν όλα τα ΜΜΕΠ, καθώς μπορεί να υπάρχουν περισσότερα από ένα. Οφείλουμε να σημειώσουμε ότι η μέτρηση της συχνότητας στον M${}^2$P εκτελείται χρησιμοποιώντας αλγόριθμο ταιριάσματος συμβολοσειρών⁸⁸Χάριν απλότητας, θα μπορούσε να χρησιμοποιηθεί και ο αλγόριθμο Knuth-Morris-Pratt., καθώς η συχνότητα ενός μονοπατιού $M$ είναι ίση με το πλήθος των εμφανίσεων του $M$ (δηλ., της υποακολουθίας που αντιστοιχεί στο $M$) στην $A$.

Στην ενότητα αυτή περιγράφεται η αλγοριθμική μορφή του M${}^2$P, όπως παρουσιάζεται στο Σχήμα 3.2. Το δεδομένο εισόδου του M${}^2$P είναι η μουσική ακολουθία. Αρχικά, ο M${}^2$P υπολογίζει όλα τα ΕΠ μήκους δύο και τα αποθηκεύει στο σύνολο ΕΠ[2]. Η διαδικασία αυτή αποτελεί μέρος της αρχικοποίησης και εκτελείται με τη βοήθεια μιας διδιάστατης μήτρας $M$, το μέγεθος της οποίας για την αναπαράσταση MIDI είναι 128$\times$128. Ο γράφος $\mathrm{\Gamma }$ κατασκευάζεται βάσει του πίνακα γειτνίασης του $M$. Κατόπιν, ο M${}^2$P εκτελεί τη διάσχιση του $\mathrm{\Gamma }$ κατά τη διάρκεια της οποίας εξετάζει τα μονοπάτια $\mathrm{\Pi }$ που πηγάζουν από τους κόμβους του $\mathrm{\Gamma }$ (η διάσχιση επισκέπτεται τους κόμβους με προτεραιότητα κατά βάθος).

Στη διαδικασία διάσχισης του γράφου, το μήκος του τρέχοντος μονοπατιού $M$ συγκρίνεται με το μήκος του τρέχοντος μέγιστου μονοπατιού (Current Maximum Length - CML), το οποίο αρχικά είναι ίσο με δυο, καθώς ο M${}^2$P έχει ήδη προσδιορίσει το σύνολο ΕΠ[2]. Εάν το μήκος του $M$ είναι μεγαλύτερο από το CML, τότε ο M${}^2$P υπολογίζει τη συχνότητα του $M$ και σε περίπτωση που είναι μεγαλύτερη του δύο, το $M$ αποθηκεύεται (ως το μόνο στοιχείο) στην ουρά μέγιστου μήκους (Maximum Length Queue - MLQ), ενώ το CML γίνεται ίσο με το μήκος του $M$. Αντίθετα, όταν το μήκος του $M$ είναι ίσο με το CML, τότε το $M$ προστίθεται στην MLQ χωρίς να γίνει υπολογισμός της συχνότητάς του. Τέλος, εάν δεν έχει περικοπεί η έρευνα για μονοπάτια που περιέχουν το $M$ (περικοπές συμβαίνουν όταν η συχνότητα του $M$ υπολογιστεί και βρεθεί μικρότερη του δύο), η διάσχιση συνεχίζει επισκεπτόμενη γειτονικούς κόμβους $v$ του $M$.

Μετά το πέρας της διάσχισης του $\mathrm{\Gamma }$, ο M${}^2$P έχει προσδιορίσει (εφόσον υπάρχει) ένα ΜΜΕΠ (το πρώτο στοιχείο της MLQ). Ακολούθως, συνεχίζει υπολογίζοντας τη συχνότητα των όλων των υπόλοιπων στοιχείων της MLQ, ώστε να συγκεντρώσει το σύνολο όλων των ΜΜΕΠ.

Η ορθότητα του M${}^2$P μπορεί εύκολα να αποδειχθεί ως εξής: Υποθέτουμε ότι το $P_M$ είναι ένα ΜΜΕΠ με μήκος $M$, ενώ τα στοιχεία του είναι $⟨p_1,\mathrm{\dots },p_M⟩$. Εφόσον το $P_M$ είναι ΜΜΕΠ, η συχνότητα του είναι μεγαλύτερη ή ίση με δύο. Συνεπώς, κάθε διαδοχικό ζευγάρι $⟨p_i,p_{i+1}⟩$ των στοιχείων του $P_M$ ανήκει στο ΕΠ[2] και έχει μια αντίστοιχη ακμή στο $\mathrm{\Gamma }$. Ακολούθως, το $P_M$ θα εξεταστεί από τον M${}^2$P κατά τη διάρκεια της διάσχισης του $\mathrm{\Gamma }$, ακολουθώντας τις ακμές $⟨p_i,p_{i+1}⟩$ για . Εάν το $P_M$ είναι το πρώτο μονοπάτι με μήκος $M$ που θα εξεταστεί, τότε θα υπολογιστεί η συχνότητα του και το $P_M$ θα αποτελεί το πρώτο στοιχείο της MLQ (διαγράφοντας όποιες παλαιότερες εγγραφές που αντιστοιχούσαν σε υποψήφια μονοπάτια μικρότερου μήκους). Αλλιώς, εάν έχουν ήδη συμπεριληφθεί άλλα μονοπάτια με μήκος $M$ στην MLQ, καθώς δεν υπάρχει άλλο ΕΠ $P^{\prime }$ με $|P^{\prime }|>M$, το $P_M$ θα εξεταστεί στο βήμα μετά το τέλος της διάσχισης, όταν θα υπολογίζονται οι συχνότητες όλων των στοιχείων της MLQ. Κατά συνέπεια, σε κάθε περίπτωση το $P_M$ θα ενσωματωθεί στην MLQ και θα περιλαμβάνεται στην έξοδο του M${}^2$P.

Για να αποσαφηνιστεί η περιγραφή του M${}^2$P, στην ενότητα αυτή παρουσιάζεται ένα παράδειγμα της εκτέλεσής του ακολουθώντας το τρέχον παράδειγμα του κεφαλαίου αυτού. Στο παράδειγμα αυτό, η ακολουθία $S$ = EBCDEHGABFJDEHGJEBCDEABFJ, έχει σύνολο ΕΠ[2] και ο αντίστοιχος γράφος $\mathrm{\Gamma }$ παρουσιάζεται στο Σχήμα 3.3. Υποθέτουμε (χωρίς απώλεια της γενικότητας) ότι ο M${}^2$P ξεκινά τη διάσχιση από τα μονοπάτια που πηγάζουν από τον κόμβο $A$ και την ακμή $AB$, ειδικότερα. Αρχικά, επισκέπτεται το μονοπάτι ABC (Σχήμα 3.4a). Καθώς το μήκος του είναι $3>CML=2$, η συχνότητα του υπολογίζεται και βρίσκουμε ότι είναι μηδενική. Έτσι, ο M${}^2$P δεν συνεχίζει τη διάσχιση στο μονοπάτι ABC. Κατόπιν, συνεχίζει εξετάζοντας το ABF, του οποίου η συχνότητα υπολογίζεται ίση με δύο. Συνεπώς, το CML γίνεται ίσο με τρία και το ABF εισάγεται στην MLQ. Η διάσχιση συνεχίζει περαιτέρω με το μονοπάτι αυτό προχωρώντας στο ABFJ, του οποίου η συχνότητα υπολογίζεται ίση με δύο. Ομοίως, το CML γίνεται τέσσερα και η MLQ={ABFJ}. Συνεχίζοντας, εξετάζεται το μονοπάτι ABFJH, όμως η συχνότητα του είναι μηδενική. Συνεπώς, αποφεύγεται η εξέταση μονοπατιών που το περιέχουν.

Στη συνέχεια, η διάσχιση προχωρά στον κόμβο $B$ (Σχήμα 3.4b) και την ακμή BC. Αρχικά εξετάζεται το μονοπάτι BCD, το μήκος του οποίου είναι μικρότερο του CML, και ακολούθως η συχνότητα του δεν υπολογίζεται. Ωστόσο, η διάσχιση συνεχίζει σε μονοπάτια που περιέχουν το BCD, καθώς δεν μπορεί να απορριφθεί ως μη ΕΠ (δηλ., δεν έχει υπολογιστεί η συχνότητα του). Συνεπώς, το μονοπάτι BCDE ακολουθεί προς εξέταση, το μήκος του οποίου είναι ίσο με το CML. Έτσι, το BCDE προστίθεται στην MLQ που γίνεται ίση με {ABFJ,BCDE}.

Ομοίως, τα μονοπάτια που πηγάζουν από τον κόμβο C (Σχήμα 3.4c) δεν επηρεάζουν το CML ή την MLQ, ενώ τα μονοπάτια που απορρέουν από τον κόμβο D (Σχήμα 3.4d) προσθέτουν το DEHG στην MLQ (εφόσον $|\mathrm{𝐷𝐸𝐻𝐺}|=\mathrm{𝐶𝑀𝐿}=4$, η συχνότητα του δεν υπολογίζεται), ενώ η MLQ γίνεται {ABFJ,BCDE,DEHG}. Συνεχίζοντας με τον κόμβο $E$ (Σχήμα 3.4e), το μονοπάτι EBCD προστίθεται στην MLQ (MLQ={ABFJ,BCDE,DEHG,EBCD}). Κατόπιν, εξετάζεται το EBCDE και η συχνότητα του υπολογίζεται ίση με δύο (εφόσον το μήκος του είναι μεγαλύτερο από το CML). Ακολούθως, το CML γίνεται ίσο με πέντε, ενώ τα τρέχοντα στοιχεία της MLQ διαγράφονται και το EBCDE προστίθεται (εφόσον βρέθηκε μεγαλύτερη τιμή CML). Τέλος, όλοι οι υπόλοιποι κόμβοι ($F$, $G$, $H$ και $J$) δεν επιφέρουν καμία αλλαγή. Συνεπώς, εφόσον δεν υπάρχουν άλλα υποψήφια μονοπάτια στην MLQ το σύνολο των ΜΜΕΠ που βρέθηκαν είναι $\{\mathrm{𝐸𝐵𝐶𝐷𝐸}\}$.

Η αποδοτικότητα του αλγόριθμου M${}^2$P βασίζεται στα κεντρικά χαρακτηριστικά του, την ικανότητα του, όπως έχει ήδη περιγραφεί, να αποφεύγει τον υπολογισμό της συχνότητας εμφάνισης των υποψηφίων (εκτός του πρώτου που βρεθεί για κάθε μήκος) το μήκος των οποίων είναι ίσο με το CML, και τη δυνατότητα του να αποφεύγει εντελώς κάθε μέτρηση που σχετίζεται με υποψήφιους με μήκος μικρότερο του CML. Για την περαιτέρω βελτιστοποίηση της απόδοσής του, στην ενότητα αυτή περιγράφονται δυο τεχνικές ώστε να βελτιωθεί επιπλέον η βασική μορφή του M${}^2$P.

Όπως περιγράφεται στην εργασία [71], το πλήθος των ΕΠ με μικρό μήκος είναι κατά πολύ μεγαλύτερο από το πλήθος των ΕΠ με μεγάλο μήκος. Για το λόγο αυτό, θα ήταν επιθυμητό ο M${}^2$P (κατά τη διάρκεια της διάσχισης) να μειώσει τον αριθμό των εξεταζόμενων μονοπατιών με μικρό μήκος. Κάτι τέτοιο είναι εφικτό σε ένα βήμα προεργασίας. Έστω $\mathrm{\ell }$ το μήκος των ΕΠ των οποίων επιθυμούμε να μειωθεί το πλήθος. Ο M${}^2$P διαβάζει τη μουσική ακολουθία $S$ και κατακερματίζει τις υποακουλουθίες μήκους $\mathrm{\ell }$ σε ένα πίνακα κατακερματισμού, του οποίου τα περιεχόμενα είναι ακέραιοι μετρητές (αρχικά ίσοι με μηδέν). Κατά τη διάρκεια της διάσχισης, όταν εξετάζεται ένα μονοπάτι $P$ μήκους $\mathrm{\ell }$, ο M${}^2$P ελέγχει τον αντίστοιχο μετρητή και εάν αυτός είναι μικρότερος του δύο, τότε σταματά τη διάσχιση για προεκτάσεις του $P$, καθώς το $P$ δεν μπορεί να είναι ΕΠ. Ωστόσο, εάν η τιμή του μετρητή είναι μεγαλύτερη ή ίση του δύο, το $P$ είναι πιθανό να μη είναι ΕΠ, εξαιτίας πιθανών συγκρούσεων στον πίνακα κατακερματισμού. Ακολούθως, ο κατακερματισμός μπορεί μόνο να προσφέρει ένα διηθητήρα ώστε να μειωθεί το πλήθος των εξεταζόμενων μονοπατιών μήκους $\mathrm{\ell }$. Εδώ πρέπει να αναφερθεί ότι σχετική τεχνική κατακερματισμού έχει χρησιμοποιηθεί σε εξόρυξη στοιχειοσυνόλων [99]. Καθώς η τεχνική αυτή αποδίδει ικανοποιητικά μόνο για μονοπάτια μικρού μήκους, στις υλοποιήσεις προτείνεται να εξετάζονται τιμές $\mathrm{\ell }$ μικρές (λ.χ. ίσες με τρία και τέσσερα) αλλά και διακριτοί πίνακες κατακερματισμού για τις τιμές του $\mathrm{\ell }$.

Η δεύτερη τεχνική αντιμετωπίζει την επίδραση των κύκλων στο γράφο $\mathrm{\Gamma }$. Εμφανώς, τα στοιχειά των ΕΠ και ΜΜΕΠ δεν απαιτείται να είναι διακριτά, συνεπώς, κόμβοι και/ή ακμές του $\mathrm{\Gamma }$ είναι πιθανό να περιέχονται περισσότερες από μια φορές για το τρέχον εξεταζόμενο μονοπάτι (κατά τη διάρκεια της διάσχισης). Ας υποθέσουμε ότι ένα μονοπάτι $P$ είναι ΕΠ αλλά το μήκος του είναι μικρότερο από το CML. Στην περίπτωση αυτή, εάν το $P$ περιέχει κύκλο, χρησιμοποιώντας τους κόμβους και τις ακμές στον κύκλο για κατάλληλο αριθμό φορών (δηλ., αρκεί να ακολουθηθεί ο κύκλος όσες φορές απαιτείται), το $P$ μπορεί να επεκταθεί ώστε το μήκος του να γίνει ίσο με το CML. Επιπλέον, εξαιτίας της Περίπτωσης 3 (όπως αυτή περιγράφεται στην Ενότητα 3.1.4), ένα μεγάλο πλήθος μονοπατιών μπορούν να προστεθούν στην MLQ. Για το λόγο αυτό, προτείνεται η βελτίωση της αρχικής μορφής του M${}^2$P ώστε να μπορεί να εντοπίσει την ύπαρξη κύκλων στο τρέχον εξεταζόμενο μονοπάτι και όταν ισχύει η Περίπτωση 3 για μονοπάτι με κύκλο, να υπολογίζεται πρώτα η συχνότητα του και να ακολουθεί η προσθήκη του στην MLQ. Παρά το γεγονός ότι η τεχνική αυτή αυξάνει το πλήθος των ενδιάμεσων μονοπατιών των οποίων εξετάζεται η συχνότητα, εντούτοις περιορίζει την υπέρμετρη αύξηση των μελών της MLQ (η συχνότητα των οποίων θα πρέπει να υπολογιστεί στο τέλος της διάσχισης).

Οι δύο προαναφερθείσες βελτιστοποιήσεις έχουν βρεθεί να προσφέρουν ουσιαστική βελτίωση στην απόδοση του M${}^2$P. Για το λόγο αυτό, ενσωματώθηκαν στην αρχική μορφή του, όπως αυτή περιγράφηκε προηγουμένως.

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

Στην εργασία [108], οι συγγραφείς εισήγαγαν τα ιστογράμματα τονικού ύψους (ΙΤΥ) ως μέθοδο για την αναπαράσταση του του περιεχόμενου τονικού ύψους στα μουσικά ακουστικά και συμβολικά σήματα. Αρχεία τύπου MIDI χρησιμοποιήθηκαν για την εξαγωγή του τονικού ύψους, η συχνότητα εμφάνισης των οποίων προσδιορίζει το ΙΤΥ. Καθώς οι προδιαγραφές των αρχείων MIDI επιτρέπουν μόνο 128 διακριτές νότες, κάθε ΙΤΥ είναι ένας πίνακας 128 τιμών καταλογοποιημένος κατά το αναγνωριστικό της νότας, που αναπαριστά τη συχνότητα εμφάνισης της αντίστοιχης νότας.

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

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

Για την ελαχιστοποίηση του χώρου αναζήτησης, τέσσερα μονοδιάστατα χαρακτηριστικά εξάγονται από τα το εκτεταμένο και το συμπτυγμένο ΙΤΥ, τα PITCH-Fold, AMPL-Fold, PITCH-Unfold & DIST-Fold. Το πρώτο είναι ο αριθμός κάδου της μέγιστης κορυφής του συμπτυγμένου ΙΤΥ ενώ το δεύτερο είναι το πλάτος της μέγιστης κορυφής του συμπτυγμένου ΙΤΥ. Το PITCH-Unfold είναι η περίοδος της της μέγιστης κορυφής του εκτεταμένου ΙΤΥ και το DIST-Fold είναι το διάστημα (σε πλήθος κάδων) μεταξύ των δύο υψηλότερων κορυφών του συμπτυγμένου ΙΤΥ.

Βασισμένοι στα χαρακτηριστικά αυτά οι συγγραφείς της [108] πέτυχαν 50% ακρίβεια (accuracy) για πέντε γένη.

Στην εργασία [92] παρουσιάζεται ένα σύστημα που εξάγει 109 μουσικά χαρακτηριστικά από συμβολικά μουσικά και τα χρησιμοποιεί για την κατηγοριοποίησή τους κατά γένος. Τα χαρακτηριστικά βασίζονται στην ενορχήστρωση, την υφή, το ρυθμό, τη δυναμική, στατιστικά γνωρίσματα του τονικού ύψους, τη μελωδία και της συγχορδίες. Το ίδιο σύστημα απαιτεί εκπαίδευση για τον προσδιορισμό του αποδοτικότερου υποσυνόλου χαρακτηριστικών, ένα κόστος που εξισορροπεί την γενικότητα της λύσης με την απαιτούμενη προ-επεξεργασία της επιλογής του υποσυνόλου. Η ακρίβειά του κατά την κατηγοριοποίηση κατά γένος αναφέρεται 90% για υπό-γένη και 98% για γένη.

Τέλος, οι συγγραφείς της [64] παρουσίασαν τη χρήση πέντε χαρακτηριστικά που βασίζονται στη μελωδία, το ηχόχρωμα, το ρυθμό για την κατηγοριοποίηση κατά γένος συμβολικής μουσικής πληροφορίας. Στην έρευνά τους γίνεται σύγκριση διαφορετικών μεθόδων μηχανικής μάθησης (μεταξύ των οποίων τις decision-tree, Bayesian και rule-based ομαδοποιητές).

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

Η μέθοδος που χρησιμοποιείται στην εργασία [86] μπορεί να θεωρηθεί ως συμπληρωματική της μεθόδου που παρουσιάζει η Ενότητα 3.2.1. Οι συγγραφείς της [86] συλλογικά χαρακτηρίζουν ένα μουσικό γένος από τα ΕΠ που είναι κοινά στο γένος. Συνεπώς, κάθε νέο, ακόμα μη κατηγοριοποιημένο κομμάτι κρίνεται από την ομοιότητα των ΕΠ του με τα ΕΠ του γένους. Κατά τη μέθοδο που παρουσιάζεται εδώ, τα ΕΠ προσδιορίζουν τα μουσικά μέρη που περιέχουν ουσιώδη πληροφορία, ενώ τα υπόλοιπα μέρη θεωρούνται επουσιώδη και δεν εξετάζονται. Ακολούθως, τα ΕΠ ενός μουσικού κομματιού συνεισφέρουν στη συλλογή του συνόλου χαρακτηριστικών του κομματιού και κάθε νέο, ακόμα μη κατηγοριοποιημένο κομμάτι κρίνεται από την ομοιότητα των χαρακτηριστικών χρησιμοποιώντας τη μέθοδο $k$-NN.

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

Ένα ΙΔΥ είναι ένας πίνακας 25 ακεραίων τιμών (οι 8 συνήθεις διάρκειες, οι παρεστιγμένες και δις παρεστιγμένες επαυξήσεις τους και η κομμένη ή breve διάρκεια) καταλογοποιημένες βάσει του μεγέθους της διάρκειάς τους, που αναπαριστούν τη συχνότητα εμφάνισης κάθε διάρκειας νότας σε ένα μουσικό κομμάτι. Διαισθητικά, τα ΙΔΝ προσφέρουν μια μέθοδο για να αιχμαλωτιστεί η δομή και το ρυθμικό μέρος ενός κομματιού, κάτι που είναι επιπλέον εμφανές στα κλασσικά μουσικά κομμάτια όπου τα γένη δημιουργήθηκαν εξελίχθηκαν βασισμένα σε κανόνες. Παράδειγμα αποτελούν οι φούγκες (fugues) όπου είναι σύνηθες να υπάρχουν πολλά μέρη όπου οι διάρκειες των νοτών είναι μικρότερες από ότι στα άλλα μέρη με στόχο να μεταδώσουν ένα αίσθημα έντασης καθώς το αρχικό θέμα τους ήταν η απόδραση. Αντίθετα, οι σονάτες (sonatas) είναι γνωστές για τη δομή τους που είναι συνήθως αργή, ειδικότερα στα δεύτερα μέρη τους.

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

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

Τα προτεινόμενα χαρακτηριστικά είναι τα εξής:

Συμπτυγμένο τονικό ύψος

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

Διάρκεια

Στα χαρακτηριστικά διάρκειας, όλα τα χαρακτηριστικά όπως προαναφέρθηκαν στην ίδια Ενότητα εξάγονται μόνο από ΙΔΝ ώστε να παρουσιαστεί η διακριτική ικανότητα της πληροφορίας της διάρκειας των νοτών, όπως παράγονται από τα ΙΔΝ.

Τονικό ύψος & διάρκεια

Το χαρακτηριστικό αυτό παράγεται από το συνδυασμό των χαρακτηριστικών του τονικού ύψους και της διάρκειας. Ακολούθως, κάθε μουσικό κομμάτι αναπαρίσταται από 7 χαρακτηριστικά, 4 από το ΙΤΥ και 3 από το ΙΔΝ. Καθώς τα χαρακτηριστικά τονικού ύψους μπορούν να είναι σε έκδοση εκτεταμένη ή συμπτυγμένη, όμοια και το συνδυαστικό χαρακτηριστικό αυτό μπορεί να εξαχθεί για τις ίδιες εκδόσεις.

Σταθμισμένο τονικό ύψος & διάρκεια

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

Ακολούθως, έγινε πειραματική αξιολόγηση στα χαρακτηριστικά τονικού ύψους, διάρκειας και συνδυασμού τους, τόσο για εκτεταμένα όσο και συμπτυγμένα ΙΤΥ. Μετά την εξαγωγή των χαρακτηριστικών, η διακριτική ικανότητά τους αξιολογήθηκε με τη χρήση του αλγόριθμου k-NN και χρήση της μεθόδου “leave one out”. Κατά τη μέθοδο αυτή ένα μουσικό κομμάτι της βάσης δεδομένων προς εξέταση θεωρείται ως μη γνωστού γένους και τα υπόλοιπα ως δεδομένα εκπαίδευσης. Από τα γένη των k κοντινότερων γειτόνων του άγνωστου κομματιού το γένος με τις περισσότερες εμφανίσεις θεωρείται πως είναι το γένος του άγνωστου κομματιού. Η διαδικασία επαναλαμβάνεται για όλα τα κομμάτια της βάσης δεδομένων προς εξέτασης οδηγώντας στην ακρίβεια των χαρακτηριστικών. Η επιτευχθείσα ακρίβεια παρουσιάζεται στα Σχήματα 3.5a και 3.5b.

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

Το δεύτερο πείραμα κάνει χρήση του σταθμισμένου τονικού ύψους & διάρκειας. Τα Σχήματα 3.6a και Figure 3.6b, παρουσιάζουν τέσσερις από τις χαρακτηριστικότερες επιλογές στάθμισης για συμπτυγμένα και εκτεταμένα ΙΨΥ. Οι ετικέτες παρουσιάζουν το ποσοστό διάρκειας - τονικού ύψους που συμμετείχε.

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

Εξαγωγή στατιστικών χαρακτηριστικών

Η εξαγωγή των στατιστικών χαρακτηριστικών από τα ΕΠ συμβολικών δεδομένων προ-απαιτεί τον προσδιορισμό των μη τετριμμένων ΕΠ στο μουσικό κομμάτι. Εδώ, τα ΕΠ προσδιορίζονται με τη μέθοδο της εργασίας [71], δηλαδή με τη χρήση επαναλαμβανόμενων δράσεων ένωσης αλφαριθμητικών (string-join operations).

Έχοντας προσδιορίσει το σύνολο των ΕΠ για κάθε τραγούδι της βάσης δεδομένων προς εξέταση, υπολογίζεται ο πίνακας συν-εμφάνισης “co-occurrence matrix” $C(i,j)$ των διακριτών τονικών υψών που εμφανίζονται στα ΕΠ. Ένα κελί του $C(i,j)$ αντιπροσωπεύει το συνολικό πλήθος εμφανίσεων των i και j, στο ίδιο πλαίσιο $w$ σε όλα τα ΕΠ ενός τραγουδιού (δηλαδή, κάθε τραγούδι έχει ένα πίνακα συν-εμφάνισης που απαρτίζεται από τα ζεύγη όλων των ΕΠ του). Στη συνέχεια, τα στοιχεία του πίνακα συν-εμφάνισης $C(i,j)$ κανονικοποιούνται ώστε να προσδιορισθεί η αληθής συνεισφορά τους σε κάθε τιμή $C(i,j)$, καθώς οι πίνακες συν-εμφάνισης είναι συνήθως ιδιαίτερα αραιοί. Η δραστηριότητα κανονικοποίησης γίνεται ανάλογα με το πλήθος των ζευγαριών ΕΠ $n$ που συμμετείχε στη δημιουργία του. Για τον έλεγχο της κανονικοποίησης χρησιμοποιείται η παράμετρος $M$ ως εκθέτης του $n$ ($n^M$). Η χρήση της κανονικοποίησης για τον υπολογισμό σχετικών τιμών του πίνακα συν-εμφάνισης είναι απαραίτητη καθώς τα μεγαλύτερα κομμάτια τείνουν να έχουν περισσότερα ΕΠ, τα οποία συνεισφέρουν περισσότερο στον πίνακα.

Ακολούθως, τα τέσσερα προτεινόμενα χαρακτηριστικά είναι η εντροπία, η ενέργεια, η αντίθεση και η ομοιογένεια που υπολογίζονται από τον πίνακας συν-εμφάνισης $C(i,j)$ κάθε τραγουδιού, με τους ακόλουθους μαθηματικούς τύπους :

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

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

Χαρακτηριστικά διάρκειας

Επιπλέον, γίνεται χρήση των χαρακτηριστικών διάρκειας όπως αυτά περιγράφηκαν στην Ενότητα 3.2.1.

Υβριδική στάθμιση

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

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

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

Απόδοση

Το πρώτο (Σχήμα 3.8a) παρουσιάζει τη συνέπεια απουσίας της πληροφορίας των ΕΠ αλλά και την τις δευτέρου επιπέδου εξαρτήσεις στον υπολογισμό των χαρακτηριστικών (το πλαίσιο $w$ είναι ίσο με τη μονάδα), όσο αφορά την ακρίβεια. Με άλλα λόγια, από τα συμβολικά δεδομένα δεν εξάγονται τα ΕΠ, ενώ η χρήση κυλιόμενου πλαισίου γίνεται στην πληροφορία του τονικού ύψους. Επιπλέον, εξάγονται τα ΕΠ αλλά δεν συμπεριλαμβάνονται οι δευτέρου επιπέδου εξαρτήσεις των τονικών υψών στα ΕΠ. Τα βήματα αυτά γίνονται ώστε να προσδιορισμό της συμμετοχής της της εξάρτησης της πληροφορίας τονικού ύψους στα ΕΠ και να επιβεβαιώσει την επιλογή των ΕΠ ως ουσιώδη τμήματα του μουσικού κομματιού. Το Σχήμα 3.8a παρουσιάζει 21% αύξηση στην απόδοση εξαιτίας της χρήσης των ΕΠ και των δευτέρου επιπέδου εξαρτήσεων.

Η έρευνα για τον προσδιορισμό της αίσθησης διάθεσης που προκαλεί ένα τραγούδι αλλά και της κατηγοριοποίησης κατά τη διάθεση αυτή έχει λάβει ιδιαίτερο ενδιαφέρον, ενώ από το 2007 και μετά ο διαγωνισμός αξιολόγησης MIREX [155], [72] επιπλέον φιλοξενεί τη δράση "Κατηγοριοποίηση ακουστικής μουσικής κατά διάθεση" (“Audio Music Mood Classification”). Ακολούθως, η τρέχουσα Ενότητα παρουσιάζει μερικές από τις βασικές μεθόδους για την κατηγοριοποίηση μουσικής πληροφορίας κατά διάθεση.

Ταξινομίες διάθεσης

Για να είναι σε θέση να γίνει κατηγοριοποίηση τραγουδιών κατά τη διάθεση, συγκίνηση τους, ή αλλιώς, χρειάζεται αρχικά να προσδιοριστεί η διάθεση. Ο Hevner [70] είχε αρχικά προτείνει ομάδες διάθεσης βάσει επιθέτων ενώ διάφορα άλλα μοντέλα της διάθεσης βάσει ομάδων επιθέτων έχουν προταθεί έκτοτε [115], [72]. Το δημοφιλέστερο μοντέλο διάθεσης, που χρησιμοποιείται εκτενώς [110], [93] στην αυτόματη κατηγοριοποίηση τραγουδιών κατά διάθεση, και αποτελεί τη βάση της παρούσας Ενότητας, είναι το μοντέλο του Thayer [107]. Στο μοντέλο αυτό, η διάθεση προσδιορίζεται σε δύο άξονες, το σθένος και την εγρήγορση, χωρίζοντας έτσι το χώρο διάθεσης σε τέσσερα μέρη έχοντας θετική/υψηλή και αρνητική/χαμηλή τιμή αντίστοιχα. Στο πλαίσιο αυτό, το σθένος και η εγρήγορση συνδέονται με την ενέργεια και την ένταση, αντίστοιχα. Υψηλού σθένους (γεμάτη ενέργεια) διάθεση δηλώνει κατάσταση που περιγράφονται από επίθετα όπως"ενθουσιασμένος", "ξετρελαμένος", κλπ, ενώ χαμηλού σθένους (κενή ενέργειας) διάθεση αντιστοιχεί σε καταστάσεις όπως "υπνηλίας". Η θετική εγρήγορση δείχνει συναισθήματα όπως "ικανοποιημένος" και "χαρούμενος", ενώ παραδείγματα συναισθημάτων χαμηλού σθένους είναι τα "νευρικός" και "λυπημένος". Για πιο λεπτομερή αναπαράσταση των συναισθημάτων, ο διαχωρισμός κάθε άξονα σε τέσσερα διακριτά μέρη προτάθηκε, δηλ. η διέγερση και το σθένος κατηγοριοποιούνται σε τέσσερις κλάσεις [110], η οποία είναι και η αντιμετώπιση που υιοθετείται στην τρέχουσα Ενότητα.

Κατηγοριοποίηση κατά διάθεση με χρήση των στίχων

Τα γλωσσολογικά χαρακτηριστικά που εξάγονται από το κείμενο των στίχων, για εφαρμογές όπως η κατηγοριοποίηση κατά διάθεση, συνήθως περιλαμβάνουν συλλογές τύπου bag-of-words [74], [85], [100], δηλ. το κείμενο αντιμετωπίζεται λες και είναι μια συλλογή από μη-ταξινομημένες λέξεις που συνοδεύονται από τη συχνότητα εμφάνισής τους (term frequency - tf). Στοχεύοντας σε ένα μέτρο που να είναι περισσότερο καταδεικτικό της διακριτικής ικανότητας του τύπου μεταξύ διάφορων κειμένου, το tfidf υπολογίζει όχι μόνο τη συχνότητα ενός όρου/λέξης σε ένα τραγούδι αλλά και τη συνολική του συχνότητα στους στίχους όλων των τραγουδιών της συλλογής. Οι συγγραφείς της [110] αντιμετώπισαν τους στίχους που ανήκαν σε ένα είδος διάθεσης ως ένα κείμενο και υπολόγισαν το tfidf των λέξεων από 10,000 τυχαία επιλεγμένα τραγούδια και στη συνέχεια εφάρμοσαν τη μέθοδο κοντινότερου γείτονα για την κατηγοριοποίηση των τραγουδιών σε 4 ή 16 κλάσεις διάθεσης.

Το μεγάλο μέγεθος του πιθανού λεξιλογίου, σε συνδυασμό με την αραιότητα των δεδομένων του μοντέλου bag-of-words κάνει τη διαδικασία διαχωρισμού μεταξύ των λέξεων ιδιαίτερα δύσκολη. Επιπλέον, οι στίχοι στο μοντέλο bag-of-words οδηγούν σε μέτρια απόδοση [85], εκτός της περίπτωσης που άπλετη ποσότητα δεδομένων είναι διαθέσιμη [110]. Για να αντιμετωπιστεί η δυσκολία αυτή, διάφορες προτάσεις έχουν γίνει που πειραματίζονται είτε με τη μείωση των διαστάσεων ή τη μοντελοποίηση της γλώσσας.

Όσο αφορά τη μείωση των διαστάσεων, οι Yang και Lee [112] χρησιμοποίησαν το εργαλείο Harvard General Inquirer ώστε να μετασχηματίσουν τις λέξεις σε ένα περιορισμένου εύρους σύνολο ψυχολογικών χαρακτηριστικών και στη συνέχεια εφάρμοσαν μια μέθοδο με δενδρική μάθηση στον παραγόμενο πίνακα συχνότητας. Άλλες, λιγότερο απαιτητικές για γνώση, μέθοδοι πέτυχαν μείωση διαστάσεων εφαρμόζοντας λανθάνουσα σημασιολογική ανάλυση (Latent Semantic Analysis - LSA) στο κείμενο των στίχων. Οι συγγραφείς της εργασίας [85] εφάρμοσαν επίσης LSA στους στίχους των τραγουδιών της διαδικτυακής πηγής last.fm και στη συνέχεια εκτέλεσαν δυαδική κατηγοριοποίηση σε 4 κλάσεις διάθεσης και στις αρνητικές ομόλογές τους (λ.χ. e.g. "θυμωμένος" - "μη θυμωμένος").

Η μοντελοποίηση γλώσσας αναφέρεται στον προσδιορισμό στατιστικών ιδιοτήτων του κειμένου κάθε κλάσης διάθεσης. Οι συγγραφείς της εργασίας [85] εξόρυξαν τους 100 συχνότερους όρους κάθε κλάσης διάθεσης και τους 100 συχνότερους όρους της αρνητικής ομόλογης κλάσης σε μια προσπάθεια να προσδιορίσουν την διακριτική ικανότητα των όρων μεταξύ δύο κλάσεων. Οι όροι με τη μεγαλύτερη διακριτική ικανότητα αποτέλεσαν τα χαρακτηριστικά στίχων στα πειράματά τους. Τα αποτελέσματα ήταν σημαντικά καλύτερα από ότι στην περίπτωση χρήσης του μοντέλου bag-of-words.

Κατηγοριοποίηση κατά διάθεση με χρήση μορφολογίας

Στην εργασία [61] παρουσιάζεται η αυξημένη συνεισφορά των μορφολογικών χαρακτήρων στη μορφολογική ανάλυση. Οι μορφολογικοί χαρακτήρες περιλαμβάνουν επιφωνήματα, σημεία στίξης (λ.χ. το θαυμαστικό), και στατιστικά στοιχεία κειμένου (όπως η λεξιλογική ποικιλία, ο ρυθμός επανάληψης, το μήκος λέξης και πρότασης, κλπ.). Στον τομέα της μουσικής, τα μορφολογικά χαρακτηριστικά έχουν χρησιμοποιηθεί στην κατηγοριοποίηση κατά γένος[100], ενώ ένα προτεινόμενο σύνολο μορφολογικών χαρακτηριστικών παρουσιάζεται στην εργασία [73].

Κατηγοριοποίηση κατά διάθεση με χρήση ακουστικής πληροφορίας & στίχων

Οι μέθοδοι που χρησιμοποιούν τόσο στην ακουστική πληροφορία όσο και στο περιεχόμενο των στίχων για τον προσδιορισμό του αισθήματος διάθεσης, βασίζονται στην υπόθεση πως η συμπληρωματικότητα των δύο πληροφοριών αυτών πηγάζει από την συνήθη προσπάθεια των τραγουδοποιών για αλληλένδετους ήχους με στίχους σε ένα τραγούδι [85], [73], [93], [111], [113]. Πληθώρα μεθόδων έχουν προταθεί για το συνδυασμό των δύο τύπων πληροφορίας, όπως: η δημιουργία διαφορετικών προβλέψεων διάθεσης για κάθε τύπο και ο συνδυασμός τους στη συνέχει μέσω στάθμισης [85] ή γραμμικού συνδυασμού [113], η εκπαίδευση διαφορετικών μοντέλων από κάθε τύπο πληροφορίας για κάθε κατηγορία διάθεσης (λ.χ. χρήση στίχων για το σθένος και ακουστικής πληροφορίας για τη διέγερση) και στη συνέχεια η ενοποίηση των αποτελεσμάτων [113], η συνάθροιση όλων των χαρακτηριστικών στον ίδιο χώρο χαρακτηριστικών και η χρήση επαυξημένων διανυσμάτων χαρακτηριστικών[85]. Οι συγγραφείς της [85] συμπεραίνουν πως ο συνδυασμός της ακουστικής και στίχων πληροφορίας προσφέρει βελτίωση στη συνολική απόδοση της δράσης κατηγοριοποίησης για τις κατηγορίες που του μοντέλου Russell [102] που εξέτασαν.

Οι Yang και Lee [111], σε μια από τις πρώτες εργασίες του χώρου, πρότειναν το συνδυασμό της πληροφορίας των στίχων με μια πληθώρα ακουστικών χαρακτηριστικών ώστε να επιτευχθεί μεγιστοποίηση της ακρίβειας της κατηγοριοποίησης και ελαχιστοποίηση του μέσου σφάλματος. Ωστόσο, το ιδιαίτερα μικρό μέγεθος δεδομένων πειραματισμού (145 τραγούδια με στίχους) κρίθηκε πως δεν είναι επαρκές για να μπορεί να καταλήξει η εργασία σε συμπεράσματα. Οι συγγραφείς της [93] εξερεύνησαν παράγοντες τόσο στην ακουστική όσο και στην πληροφορία στίχων που ταυτόχρονα επηρεάζουν τη διάθεση που προκαλεί ένα τραγούδι.

Στο πλαίσιο μείωσης διαστάσεων, οι συγγραφείς της εργασίας [113] εξήγαγαν πλήθος από χαμηλού επιπέδου ακουστικά χαρακτηριστικά από 30-δευτερόλεπτα τραγουδιών αλλά και χαρακτηριστικά στίχων, δημιούργησαν μοντέλα bag-of-words με μια ή δύο λέξεις, καθώς επίσης εφάρμοσαν και τυχαιοκρατική μέθοδο LSA. Ακολούθως, κατηγοριοποίησαν τα τραγούδια σε τέσσερις κλάσεις ακολουθώντας το μοντέλο Russell [102] για να καταλήξουν στο ότι η χρήση των χαρακτηριστικών κείμενο προσφέρει ιδιαίτερα αυξημένη ακρίβεια στις μεθόδους που πειραματίστηκαν. Σύμφωνα με το προαναφερθέν μοντέλο, το συναίσθημα αναπαρίσταται σε ένα διδιάστατο χώρο, όπου η μια διάσταση είναι η μεταφορά της θετικής/αρνητικής πόλωσης (ευχαρίστηση/δυσαρέσκεια) ενώ η δεύτερη είναι η παρουσία/απουσία ενέργειας (διέγερση/υπνηλία). Όλα τα συναισθήματα μπορούν να αναπαρασταθούν στο διδιάστατο χώρο αυτό ως συνδυασμοί τιμών των προαναφερθέντων διαστάσεων. Χρησιμοποιώντας παρόμοια μεθοδολογία, αλλά με διαφορετικό πλαίσιο εφαρμογής, οι συγγραφείς της εργασίας [89] συνδύασαν την τυχαιοκρατική μέθοδο LSA σε πληροφορία στίχων και ακουστική για την ανεύρεση ομοιότητας μεταξύ καλλιτεχνών.

Εκτός των στίχων ενός τραγουδιού, υπάρχουν κι άλλες πηγές γλωσσικής πληροφορίας που έχουν χρησιμοποιηθεί στην ΕΜΠ, όπως οι ετικέτες από εικονικές κοινωνικές δράσεις [96]. Οι Hu και Downie [73], παρουσίασαν μια διαφοροποιημένη προσέγγιση όσο αφορά την ανάθεση ετικετών διάθεσης, εξερευνώντας τις κοινωνικές ετικέτες που ανατέθηκαν σε τραγούδια, καταλήγοντας στον ορισμό 18 κλάσεων διάθεσης. Ακλολούθως, τα δεδομένα τους είναι σημαντικά ογκοδέστερα από ότι τις προηγούμενες εργασίες (5296 τραγούδια). Τέλος, ο Lamere [82] παρουσίασε μια αναλυτική περιγραφή της χρήσης των κοινωνικών ετικετών στις δράσεις της ΕΜΠ.

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

Ακουστικά χαρακτηριστικά

Στην Ενότητα αυτή δύο σύνολα ακουστικών χαρακτηριστικών χρησιμοποιούνται. Το πρώτο, audio1, δημιουργήθηκε με χρήση της εφαρμογής jAudio [90] που εξάγει ένα σύνολο από γενικευμένα για τους στόχους της ΕΜΠ χαρακτηριστικά. Το audio1 αποτελείται από τα εξής χαρακτηριστικά: Spectral Centroid, Spectral Rolloff Point, Spectral Flux, Compactness, Spectral Variability, Root Mean Square, Fraction of Low Energy Windows, Zero Crossings, Strongest Beat, Beat Sum, Strength of Strongest Beat, 13 συντελεστές MFCC, 9 συντελεστές LPC και 5 συντελεστές Method of Moments.

Το δεύτερο σύνολο, audio2, δημιουργήθηκε με την εφαρμογή MIRtoolbox [84] και τη συνάρτησή του “mirfeatures”. Η συνάρτηση αυτή υπολογίζει ένα μεγάλο πλήθος από υψηλού επιπέδου χαρακτηριστικά που είναι οργανωμένα βάσει των αξόνων της μουσικής σε δυναμική, ρυθμό, ηχόχρωμα και τονικότητα. Λεπτομερέστερα, τα χαρακτηριστικά περιλαμβάνουν τις μέσες τιμές του RMS ανά πλαίσιο, την περίληψη διακύμανσης με την υψηλότερη κορυφή και το κέντρο βάρους της, μια προσέγγιση του tempo βάσει πλαισίων, οι χρόνοι ήχησης κάθε νότας και την καμπύλη του φακέλου που χρησιμοποιείται για τον υπολογισμό του χρόνου ήχησης, και πλήθος φασματικών χαρακτηριστικών (λ.χ. κέντρο βάρους, κύρτωση, εντροπία, ρυθμός μηδενισμού, ροή κλπ).

Χαρακτηριστικά στίχων

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

• •

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

• •

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

• •

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

• •

  δράση προσδιορισμού ρίζας λέξεων (stemming)⁹⁹Στην παρούσα Ενότητα η δράση stemming έγινε με το λογισμικό της εργασίας [103].

Μοντέλο Bag-of-words

Για την εξαγωγή των χαρακτηριστικών στίχων, οι στίχοι κάθε τραγουδιού αναπαραστάθηκαν ως ένα σύνολο από τις 20 συχνότερα εμφανιζόμενες λέξεις (ρίζες) στο τραγούδι (κατόπιν της αφαίρεσης των λειτουργικών λέξεων). Αντίθετα με άλλες εργασίες, η χρησιμοποιούμενη εδώ μέθοδος αντιμετωπίζει το πρόβλημα της αραιότητας των δεδομένων. Περίπου 3% των τραγουδιών είχαν λεξιλόγιο μικρότερο των 20 διακριτών λέξεων συνολικά και λιγότερο από το 1% των τραγουδιών είχαν αντίστοιχο λεξιλόγιο μικρότερο των 15 λέξεων. Κάθε λέξη συνοδεύεται από τη συχνότητα εμφάνισής τους και το tfidf της. Ακολούθως, ο συνολικός αριθμός γλωσσικών χαρακτηριστικών είναι 60.

Γλωσσικό μοντέλο

Αντίθετα με την εργασία [85], το χρησιμοποιούμενο εδώ γλωσσικό μοντέλο στοχεύει στην διάκριση μεταξύ διαφορετικών κλάσεων διάθεσης και όχι μεταξύ θετικής και αρνητικής έκδοσης κάθε κλάσης. Ακολούθως, οι 50 συχνότερα εμφανιζόμενες λέξεις στους στίχους μιας κλάσης υπολογίζονται οδηγώντας σε ένα σύνολο 218 διακριτών λέξεων words για οκτώ κλάσεις διάθεσης (τέσσερις για σθένος και τέσσερις για διέγερση). Αυτό αποτελεί το απόλυτο γλωσσικό μοντέλο (absolute language model - ALM) σε αντίθεση με την προσέγγιση αποστάσεων γλωσσικών μοντέλων της εργασίας [85]. Κάθε ένας από τους όρους αυτούς αποτελεί ένα χαρακτηριστικό γλωσσικής μάθησης και η τιμή του είναι αυτή του tfidf για έναν όρο στο κάθε τραγούδι (ALM tfidf). Ακολουθώντας την αιτιολόγηση της εργασίας [110], που αναφέρει πως το tf είναι επαρκής προσέγγισης όταν το idf έχει πολύ μικρή τιμή, ένα δεύτερο σύνολο δεδομένων ALM απαρτίζεται εκτός από τις τιμές tfidf και από τις τις τιμές tf (ALM tf+tfidf), δηλ. έχει διπλάσιο πλήθος γλωσσικών χαρακτηριστικών.

Μοντέλο LSA

Η Λανθάνουσα Σημασιολογική Ανάλυση (LSA) [83] είναι μια μέθοδος singular value decomposition (SVD) για πίνακες, που αρχικά προτάθηκε για τη μείωση των διαστάσεων του πίνακα όρων-κειμένων (term-document matrix) στις δράσεις ανάκτησης πληροφορίας. Η μέθοδος SVD αποδομεί τον αρχικό πίνακα όρων-κειμένων $A$ σε ένα γινόμενο τριών πινάκων και "μεταφέρει" τον $A$ σε ένα νέο σημασιολογικό χώρο:

$$A=TS{D}^T$$

(3.5)

όπου ο $T$ είναι πίνακας με γραμμές τους λεξικούς όρους και στήλες τις διαστάσεις του νέου σημασιολογικού χώρου. Οι στήλες του $D$ αναπαριστούν τα αρχικά κείμενα και οι γραμμές του τις νέες διαστάσεις, ενώ ο $S$ είναι ένας διαγώνιος πίνακες που περιέχει τις μοναδιαίες τιμές του $A$. Ο πολλαπλασιασμός των τριών πινάκων επαναδομεί τον αρχικό πίνακα. Το γινόμενο μπορεί να υπολογιστεί έτσι ώστε οι μοναδιαίες τιμές να είναι τοποθετημένες στον $S$ σε φθίνουσα ταξινόμηση. Όσο μικρότερη η κάθε μοναδιαία τιμή, τόσο λιγότερο επηρεάζει το γινόμενο. Ακολούθως, διατηρώντας μόνο τις πρώτες λίγες ($k$) μοναδιαίες τιμές και θέτοντας τις άλλες ίσες με μηδέν, ο υπολογισμός του γινομένου οδηγεί σε μια χαμηλής τάξης προσέγγιση $A_k$ του αρχικού πίνακα $A$ η οποία μπορεί να υπολογιστεί με χρήση της μεθόδου least-squares best fit. Ο μειωμένος αριθμός διαστάσεων του νέου πίνακα είναι ίσος με τον αριθμό $k$ των επιλεγμένων μοναδιαίων τιμών.

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

Μορφολογικά χαρακτηριστικά

Τα 15 μορφολογικά χαρακτηριστικά που χρησιμοποιούνται στην παρούσα Ενότητα βασίζονται στο σύνολο χαρακτηριστικών που προτείνουν οι Hu και Downie στην [73]. Οι συγγραφείς της καταλήγουν σε χαρακτηριστικά που περιλαμβάνουν: τον αριθμό των παρεμβολών στο κείμενο του τραγουδιού, το μέγεθος των στίχων του τραγουδιού, τον αριθμό των μοναδικών λέξεων, το λόγο λέξεων που επαναλαμβάνονται, το μέσο μήκος των λέξεων, τον αριθμό των γραμμών στίχων, τον αριθμό των μοναδικών γραμμών στίχων, τον αριθμό των κενών γραμμών στίχων, το λόγο των κενών γραμμών στίχων σε σχέση με τις γραμμές που έχουν κείμενο, το μέσο μήκος της γραμμής, την τυπική απόκλιση του μήκους της γραμμής, τον αριθμό των μοναδικών λέξεων ανά γραμμή, το λόγο επανάληψης γραμμών στίχων, τη μέση αναλογία επανάληψης λέξης ανά γραμμή και την τυπική απόκλιση του λόγου επανάληψης λέξης ανά γραμμή.

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