Συσταδοποίηση (Clustering) με συναρτήσεις.
 

Καλημέρα σας.
Παραθέτω ένα θέμα που με απασχόλησε φέτος το καλοκαίρι και νομίζω ότι είναι ενδιαφέρον για όσους θέλουν να ασχοληθούν.
Έχω Χ (από 2 έως 26) τυχαίους αριθμούς και θέλω να τους ομαδοποιήσω σε συστάδες (clusters), ώστε η απόσταση του μικρότερου από το μεγαλύτερο κάθε συστάδας να είναι το ελάχιστο δυνατό.
Ο αριθμός των πιθανών συστάδων μπορεί να κυμαίνεται από 1 έως Χ.
Προφανώς η "ιδανική" λύση είναι τόσες συστάδες όσοι και αριθμοί. Δηλαδή κάθε αριθμός να αποτελεί μια συστάδα.
Η χειρότερη λύση προφανώς είναι μία συστάδα που να περιέχει όλους τους Χ αριθμούς.
Το ζητούμενο είναι να βρούμε όλες τις ενδιάμεσες λύσεις, και ποια είναι η καλύτερη λύση για 2 η 3 ή ... ή Χ-1 συστάδες.
Για να γίνει κατανοητό το ζητούμενο δείτε το συνημμένο παράδειγμα για 5 τυχαίους αριθμούς.

Ευχαριστώ για το χρόνο σας.
Θανάσης
ΥΓ. Λόγω περιορισμών που ισχύουν στο εργασιακό περιβάλλον που πρόκειται να χρησιμοποιηθεί, η λύση πρέπει να είναι συμβατή με Excel2003 και να μην κάνει χρήση VBA.

Καλησπέρα

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

Έτσι προσπάθησα να υλοποιήσω μια λύση με βάση αυτό το ζητούμενο.

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

Αν δεν σε καλύπτει, πιθανόν να προσφέρει κάποιες ιδέες για την κάλυψη του ζητούμενου.

Φιλικά/Γιώργος

Σε ευχαριστώ πολύ Γιώργο.
Θα το μελετήσω, αν και δεν με καλύπτει το αποτέλεσμα σου για τις 3 συστάδες
{α, β, ε} , {γ}, {δ} όπου τα εύρη είναι 89, 0, 0 σε αντίθεση με το επιθυμητό {α}, {β, ε} , {γ, δ} με εύρη 0, 33, 59 αντίστοιχα. Φαντάζομαι ότι οι διαφορές μας στους 26 αριθμούς θα είναι πολύ περισσότερες.
Θα το μελετήσω και θα δω πως μπορεί να γίνει με συναρτήσεις στο Excel.
Εξαιρετική η ανάλυσή σου.
Ευχαριστώ και πάλι.
Θανάσης
ΥΓ πολύ σωστά αναφέρεις ότι το άθροισμα των διαφορών που αντιστοιχούν στις ομάδες (συστάδες) γίνεται ελάχιστο (άρα γίνεται ελάχιστη και η μέση διαφορά)
Εγώ θέλω να κάνω ελάχιστη την μέγιστη όχι την μέση διαφορά

Γιώργο μου έγραψες:
"...Με άλλα λόγια θα πρέπει να αρχίσουμε τη διαίρεση της ταξινομημένης ακολουθίας από τον αριθμό που έχει τη μεγαλύτερη διαφορά από τον προηγούμενό του και να συνεχίσουμε μ' αυτόν που έχει την αμέσως μικρότερη, μέχρι να συμπληρώσουμε το πλήθος των τμημάτων (συστάδων) που θέλουμε."
Τι γίνεται όταν έχουμε ίδιες διαφορές πώς επιλέγουμε την "την αμέσως μικρότερη" ;

Θανάσης

Θανάση, δεν το διατύπωσα απόλυτα σωστά.

Εννοούσα ότι συνεχίζουμε με την επόμενη ίση και αν δεν υπάρχει ίση με την αμέσως μικρότερη.

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

Γιώργος

Καλημέρα

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

Μια προσέγγιση υπάρχει στο επισυναπτόμενο αρχείο.

Δεν τον δοκίμασα σε δύσκολες καταστάσεις (πχ 26 αριθμοί 14 συστάδες) και δεν ξέρω πως θα συμπεριφερθεί.

Φιλικά/Γιώργος

Καλημέρα σας

Καταρχήν ευχαριστώ τον Γιώργο (kapetang) για το ενδιαφέρον του και την συμμετοχή του.

Τώρα για το κυρίως θέμα. δείτε στο συνημμένο μια πρώτη προσέγγιση που νομίζω ότι είναι απόλυτα αποδεκτή, (χωρίς VBA και Add-ins)

Απλά καταχωρούμε ετικέτες και αριθμούς στο φύλλο Data και έχουμε τα αποτελέσματα στο φύλλο Results.
Οι λεπτομέρειες και οι συναρτήσεις που χρησιμοποίησα περιέχονται στο φύλλο.

Θα χαρώ ιδιαίτερα να διαβάσω τα σχόλια ή τις παρατηρήσεις σας καθώς και τις προτάσεις σας για τυχόν βελτίωση. :yahoo:

Θανάσης.

Καλημέρα

Θανάση, σ’ ευχαριστώ για το ζόρικο πρόβλημα που μας έβαλες. Είναι απ’ αυτά που ακονίζουν το μυαλό.

Σχετικά με τη λύση που μας έδωσες και με στόχο της βελτίωσής της:

1) Θα πρέπει να διευκρινιστεί αν βρίσκει την ελάχιστη μέγιστη διαφορά ή την ελάχιστη μέση διαφορά.

2) Νομίζω ότι απαιτείται επανέλεγχος των τύπων.

Όπως φαίνεται στο φύλλο «Check» του επισυναπτόμενου αρχείου, για την περίπτωση 26 αριθμών και 13 συστάδων, το αποτέλεσμα που δίνει δεν είναι το βέλτιστο.

3) Κάποιες ετικέτες στο αποτέλεσμα δε χωρίζονται με κόμμα (hi αντί h, i).

Φιλικά/Γιώργος

Καλημέρα
Γιώργο
για το 1) στο μυαλό μου τουλάχιστον είναι σαφές "την ελάχιστη μέγιστη διαφορά" όπως είχα πει και σε προηγούμενο μήνυμα.
για το 2) θα το δω και θα επανέλθω.
για το 3) το hi δεν έχει διαχωριστικό γιατί τα h και i έχουν την ίδια τιμή. Δηλαδή τα θεωρώ σαν μία ετικέτα. Υπό κανονικές συνθήκες τα δεδομένα μας δεν πρέπει να περιέχουν ούτε διπλές ετικέτες αλλά ούτε και διπλές τιμές.

Ευχαριστώ και πάλι για το χρόνο σου.
Τα λέμε.
Θανάσης

Γιώργο έχεις δίκιο πρέπει να ξαναδώ του τύπους, γιατί όπως εντόπισες πρέπει να χωρίσουμε:
{ n, w, y }, { b, k, j } και { f, g, h=i } (max_diff=7)
αντί { n,w }, { y } και { b, k, j, f, g, h=i } (max_diff=8)

Θα το παλέψω.
Ευχαριστώ.
Θανάσης

Καλησπέρα

Θανάση, στο επισυναπτόμενο αρχείο υπάρχει μια υλοποίηση του ζητούμενου όχι με συναρτήσεις, αλλά με κώδικα.

Μολονότι δε ζητούσες λύση με κώδικα την ανεβάζω:

1) Για να έχουμε μια λύση.

2) Μπορεί ο κώδικας να δώσει ιδέες για τη εύρεση λύσης με συναρτήσεις.

3) Μπορεί να βοηθήσει στον έλεγχο των αποτελεσμάτων των λύσεων με συναρτήσεις.

Φιλικά/Γιώργος

Καλημέρα

Γιώργο σε ευχαριστώ και πάλι αν και δεν έχω δει ακόμα το αρχείο που ανέβασες.
Εγώ από την πλευρά μου το πάλεψα όπως είχα πει αλλά μάταια. :dft004:

Το πρόβλημα είναι ότι από την στιγμή που κάποια ετικέτα ενσωματωθεί σε μια συστάδα, δεν μπορεί να ξαναμπεί στους υπολογισμούς για την ελάχιστη απόσταση αφού αυτό που μετράω είναι η απόσταση του μέγιστου από τον ελάχιστο της κάθε συστάδας.
Το θέμα βέβαια (αν το σκέφτομαι σωστά) υπάρχει μόνο όταν έχουμε ίδιες αποστάσεις στις αρχικές τιμές.
Στην εφαρμογή οι πραγματικές τιμές είναι 26 σε μια απόσταση από 50Κ έως 400Κ με σχεδόν απίθανο το ενδεχόμενο ίσων αποστάσεων ή/και ίδιων τιμών.
Μελετώντας τα δεδομένα μου στα τελευταία 5 χρόνια τουλάχιστον δεν έχω ίσες αποστάσεις, οπότε θα έλεγα όλα καλά.

Τέλος πάντων, θα δω το συνημμένο σου και αν μπορέσω να βγάλω κάτι νέο θα επανέλθω.

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

Ευχαριστώ και πάλι.
Θανάσης.

ΥΓ. ελπίζω να φανεί χρήσιμος και σε άλλους που δεν έχουν τον περιορισμό "χωρίς VBA"