Clustering Algorithms

[tr3quart1sta]

Εχω μια συλλογη απο φρουτα:

fruits = ['apple', 'banana', 'cherry', 'grapes', 'kiwi', 'lemon', 'orange', 'strawberry']

αλλα η λιστα περιεχει περιπου 500 φρουτα.

Μετα εχω γυρω στα 86'000 καλαθια οπου στο καθενα σημειωνεται με ενα binary vector ποια απο τα φρουτα ειναι μεσα στο καλαθι:

basket1 = [1,0,0,0,0,1,0,0]
basket2 = [0,1,0,0,0,1,1,0]
basket3 = [0,1,0,0,0,0,0,0]
basket4 = [0,0,0,0,0,0,0,1]
basket5 = [1,0,0,0,0,0,0,1]
...

Π.χ. στο basket1 εχω μεσα apple και lemon. Τα baskets περιεχουν κατα μεσο ορο περιπου 3.5 φρουτα.

Αυτο που θελω να κανω ειναι ενα clustering των 86'000 καλαθιων, ωστε να σχηματιστουν ομαδες απο παρομοια καλαθια. Ο αριθμος των clusters ειναι ομως αγνωστος.

Οι περισσοτεροι αλγοριθμοι clustering χρησιμοποιουν μια μεθοδο για να μετρησουνε την "αποσταση" μεταξυ των vectors. Εδω εχω βρει οτι η μεθοδος που μου ταιριαζει περισσοτερο ειναι η Jaccard (σε συγκριση με Euclidian, Manhattan, Cosine, κλπ...) γιατι επιβραβευει τις θεσεις οπου εχουνε κοινα '1', ενω βρισκει τα κοινα '0' ως ασημαντα.

Εδω που εχω κολλησει τωρα ειναι οτι δεν ξερω πως να διαλεξω καποιον clustering algorithm (ή εστω την κατηγορια των clustering algorithms) που θα χρησιμοποιησει τον Jaccard για να κανει την ομαδοποιηση. (Θα προτιμουσα καποιον απο εδω ή εδω)

Καμια ιδεα??

[zynif]

Εσύ ορίζεις τον αριθμό των clusters. Όχι ο αλγόριθμος.

Θα έλεγα να δοκιμάσεις ένα hierarhical algorithm. Αυτός θα σου βγάλει ένα δενδρόγραμμα ως έξοδο. Εσύ μετά θα διαλέξεις πόσα θέλεις.

 

Yπάρχουν επίσης και τεχνικές clustering evaluation. Μπορείς να δοκιμάσεις διάφορους αλγόριθμους και να διαλέξεις αυτόν που βγάζει το μεγαλύτερο σκορ.

[defacer]

Εσύ ορίζεις τον αριθμό των clusters. Όχι ο αλγόριθμος.

 

AFAIK όχι στη γενική περίπτωση που κάνεις mining. Στην ουσία θέλεις να βάλεις τον υπολογιστή να λύσει το πρόβλημα "ξέρω πως σ' αυτά εδώ τα δεδομένα υπάρχει κάποια δομή αλλά δεν ξέρω ποιά ακριβώς και πρέπει να τη βρεις εσύ".

[Technology fan]

Όπως ειπώθηκε στο clustering δεν μπορείς να αφήσεις κενό τον αριθμό των clusters και αυτό είναι ένα πρόβλημα που ασχολείται η επιστήμη.

 

Παρόλα αυτά,  if I were you: δεν θυμάμαι που το είχα βρει, αλλά σε ένα άρθρο που πραγματευόταν το θέμα: choosing the correct number of clusters, δοκίμαζε διάφορους τύπους για το πως να διαλέγουμε αυτον τον αριθμό, και θυμάμαι είχε καταλήξει στο sqrt(instances): δηλαδή στη περίπτωσή σου το ρίζα(86000). Προφανώς είναι αρκετά αυθαίρετο, αλλά είναι αυτοματοποιημένο, και δεν έχεις να δικαιολογηθείς σε ερωτήσεις τύπου: και γιατί διάλεξες 20 και όχι 50 κέντρα...

 

Επίσης μία άλλη ιδέα είναι να κάνεις ένα αρχικό clustering και μετά βλέποντας την δομή αυτών των clusters είτε να διαχωρίσεις ένα cluster σε δύο αν ειναι πολύ απλωμένο, είτε να ενώσεις δυο clusters σε ένα αν μοιάζουν πολύ.

 

Επιπλέον, θα μπορούσες να δοκιμάσεις σε συνδυασμό τον αλγόριθμο random forest και να δοκιμάσεις πολλά διαφορετικά clusterings ωστε τελικά να πάρεις ένα κατα μέσο όρο καλό clustering.

[tr3quart1sta]

Επίσης μία άλλη ιδέα είναι να κάνεις ένα αρχικό clustering και μετά βλέποντας την δομή αυτών των clusters είτε να διαχωρίσεις ένα cluster σε δύο αν ειναι πολύ απλωμένο, είτε να ενώσεις δυο clusters σε ένα αν μοιάζουν πολύ.

 

Με ποιους αλγοριθμους ομως και γιατι??

[zynif]

Επιτρέπεται να μας δώσεις το data set να δοκιμάσουμε και εμείς ;

[tr3quart1sta]

Επιτρέπεται να μας δώσεις το data set να δοκιμάσουμε και εμείς ;

 

Δυστυχως οχι, υπαρχει NDA στη μεση...

[we_will_rise]

Υπάρχουν 500 φρούτα;

 

Sent from my iPhone using Insomnia

[Technology fan]

Με ποιους αλγοριθμους ομως και γιατι??

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

 

Θα σου έλεγα να δοκιμάσεις και μεθόδους τύπου spectral clustering αλλά με τον αριθμό δειγμάτων που έχεις είναι απαγορευτικό εκτώς αν έχεις γύρω στα 60gb ram ...

[zynif]

Ξέρεις τι πάει να πει μείωση διαστατικότητας  (dimensionality reduction ) ;

Aν ναι  ίσως να σου μειώσει κάπως το μέγεθος του προβλήματος ...

[Technology fan]

Ξέρεις τι πάει να πει μείωση διαστατικότητας  (dimensionality reduction ) ;

Aν ναι  ίσως να σου μειώσει κάπως το μέγεθος του προβλήματος ...

Λάθος!! η μείωση διάσταση δεδομένων (dimensionality reduction), προσπαθεί να μειώσει τις διαστάσεις των δεδομένων και όχι τα ίδια τα δεδομένα. (το λέει και το όνομα.. ) Στο συγκεκριμένο πρόβλημα οι διαστάσεις του προβλήματος είναι 8, δε το λές και super μεγεθος..

[tr3quart1sta]

Λάθος!! η μείωση διάσταση δεδομένων (dimensionality reduction), προσπαθεί να μειώσει τις διαστάσεις των δεδομένων και όχι τα ίδια τα δεδομένα. (το λέει και το όνομα.. ) Στο συγκεκριμένο πρόβλημα οι διαστάσεις του προβλήματος είναι 8 500, δε το λές και super μεγεθος..

[Technology fan]

 

Λάθος!! η μείωση διάσταση δεδομένων (dimensionality reduction), προσπαθεί να μειώσει τις διαστάσεις των δεδομένων και όχι τα ίδια τα δεδομένα. (το λέει και το όνομα.. ) Στο συγκεκριμένο πρόβλημα οι διαστάσεις του προβλήματος είναι 8 500, δε το λές και super μεγεθος..

 

Σόρρυ άρα το basket1=[1,0,0,0,0,1,0,0] είναι στη πραγματικότητα [1 0 0 0 0 1 0 0 .. μηδενικά μηδενικά .....0].

 

Οπότε ναι ενδεχομένως να μπορείς να κάνεις κάτι με dimensionality reduction αλλά όχι τρομερά πράγματα. Κάθε δείγμα σου θα είναι αραιό και θα πρέπει να το χειριστείς αλλιώς. Το μέγεθος του προβλήματος σου είναι το 86000.

[παπι]

Βασικα δεν ειναι vector με 500 διαστασεις. Αλλα vector με "μεσο ορο" 3.5 διαστασεις

[paparovic]

Είναι ακαδημαϊκό το πρόβλημα ή πρακτικό. Αν είναι πρακτικό, θα υπάρχει λόγος που κάνεις cluster τα baskets. Η επίλογή του τρόπου προφανώς θα εξαρτηθεί από τον λόγο. Δλδ. πρέπει να ξέρεις ΤΙ κάνεις. Αλλιώς, τα χωρίζεις τυχαία σε 2 ομάδες και καθάρισες.