Rechenproblem?!



  • Guten Abend,

    ich bin neu hier und beschäftige mich erst seit ein paar Wochen mit C++ und hoffe ihr seit deswegen etwas nachsichtig mit meinem Unverständnis.

    Folgendes Problem: Ich möchte ein k-mean clustering durchführen. Habe 100 Punkte gegeben und möchte 10 Centroide dafür einrichten. Die 10 Centroide lege ich zu Beginn manuell fest und lasse sie dann dynamisch einen Zustand finden, der am Ende stabil sein soll. Habe schon diverse Artikel und Videos dazu angeschaut - scheint ein Standardproblem zu sein.
    Das Problem ist, dass ich die 100 Punkte manuell eingegeben habe und er vermutlich zu viel zum Rechnen hat und ich somit kein Ergebnis bekomme...Deswegen kann ich auch nicht genau sagen, ob der Code funktioniert. Habe es mit 5 Punkten und 2 Centroide versucht und da lief er. Leider bin ich nicht in der Lage es so zu programmieren, dass er die Daten automatisch einliest. Dann komme ich unten bei der Rechnung immer durcheinander.

    Bin für jeden Hilfe Dankbar! Vielen Dank schon Mal vorab!

    Hier mein Code:

    #include <iostream>
    #include <string>
    #include <fstream>
    #include <stdio.h>
    #include <math.h>
    #include <cstdlib>
    #include <iomanip>

    using namespace std;

    int main()
    {
    int i, j;

    float dmin, dpoint;
    float sum[10][2];
    int cluster[10], count[10], group;
    float flips;
    const int rows = 100;
    const int columns = 2;
    const int crows = 10;
    const int ccolumns = 2;

    // initialize the points

    int point[rows][columns]={{45,68},{45,70},{42,66},{42,68},{42,65},{40,69},{40,66},{38,68},{38,70},{35,66},{35,69},{25,85},{22,75},
    {22,85},{20,80},{20,85},{18,75},{15,75},{15,80},{30,50},{30,52},{28,52},{28,55},{25,50},{25,52},{25,55},{23,52},{23,55},{20,50},
    {20,55},{10,35},{10,40},{8,40},{8,45},{5,35},{5,45},{2,50},{0,40},{0,45},{35,30},{35,32},{33,32},{33,35},{32,30},{30,30},{30,32},
    {30,35},{28,30},{28,35},{26,32},{25,30},{25,35},{44,5},{42,10},{42,15},{40,5},{40,15},{38,5},{38,15},{35,5},{50,30},{50,35},
    {50,40},{48,30},{48,40},{47,35},{47,40},{45,30},{45,35},{95,30},{95,35},{53,50},{92,30},{53,35},{45,65},{90,35},{88,30},{88,35},
    {87,30},{85,25},{85,35},{75,55},{72,55},{70,58},{68,60},{66,55},{65,55},{65,60},{63,58},{60,55},{60,60},{67,85},{65,85},{65,82},
    {62,80},{60,80},{60,85},{58,75},{55,80},{55,85}};

    // initialize the centroids

    double centroid [crows][ccolumns] = {{45,68},{45,70},{42,66},{42,68},{42,65},{40,69},{40,66},{38,68},{38,70},{35,66}};

    // ...

    for (i = 0; i<100; i++) cluster[i] = 0;

    // until there is no change of clusters belonging to each pattern, continue

    flips = 100;
    while (flips>0) {

    flips = 0;

    for (j = 0; j < 10; j++)
    {
    count[j] = 0;
    for (i = 0; i < 2; i++)
    sum[j][i] = 0;
    }

    // now, we need to calculate the distance

    for (i = 0; i < 100; i++) {

    dmin = 2000; group = cluster[i];
    for (j = 0; j < 10; j++)
    {

    dpoint = 0.0;

    dpoint += sqrt(pow((point[i][0] - centroid[j][0]),2)+pow((point[i][1] - centroid[j][1]),2));
    fprintf(stdout, "%2.2f ", dpoint); // Show the value of the distance
    if (dpoint < dmin) {
    group = j;
    dmin = dpoint;
    }
    }

    // now, we need to calculate the G matrix (1 or 0)

    fprintf(stdout, " * %d *\n", group); // displays 0 or 1 (to which cluster it belongs)

    if (cluster[i] != group)
    {
    flips++;
    cluster[i] = group; // repeat this process until G(n)=G(n+1)
    }

    count[cluster[i]]++;

    for (j = 0; j < 2; j++)
    sum[cluster[i]][j] += point[i][j];
    }

    // now, display the coordinates of the centroid

    for (i = 0; i < 10; i++) {
    fprintf(stderr," The coordinates of the centroid are: ");
    for (j = 0; j < 2; j++) {
    centroid[i][j] = sum[i][j]/count[i];
    fprintf(stderr, "%2.2f ", centroid[i][j]);

    }
    } fprintf(stdout, "\n");

    }

    }



  • Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum C (C89, C99 und C11) verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.


  • Mod

    #include <iostream>
    #include <string>
    #include <fstream>
    #include <cstdlib>
    #include <iomanip>
    
    using namespace std;
    

    Bis auf diese 6 Zeilen, die einfach gar nichts in deinem Programm tun, ist das reines C. Programmiere bitte nicht durch das blinde Zusammenkopieren von Programmfetzen aus dem Internet, das wird nix. Ganz gefährlich ist Mischung von C und C++, besonders wenn man die beiden nicht auseinanderhalten kann. Dann kann man sich gleich von definiertem Programmverhalten verabschieden.

    Weiterhin stell bitte eine klare Frage, formatiere deinen Code und, wenn du ein Laufzeitproblem hast, dann liefere auch einen vollständigen (aber möglichst verkürzten) Code, so dass man das Problem auch nachvollziehen kann. Siehe den dritten Link in meiner Signatur.



  • Paris88 schrieb:

    int cluster[10];
    ...
    for (i = 0; i<100; i++) cluster[i] = 0;
    

    Meinst du, dass dies eine gute Idee ist?



  • Soviel Schwachsinn in einem Listing:

    Das ist doch nicht von dir, sondern zusammengeklaut oder?

    flips = 100;
    while (flips>0) {
    
    flips = 0;
    

    evtl noch mehr unnütze Ini's damit der Code richtig unleserlich wird

    der Abschuss

    fprintf(stderr," The coordinates of the centroid are: ");
    for (j = 0; j < 2; j++) {
    centroid[i][j] = sum[i][j]/count[i];
    fprintf(stderr, "%2.2f ", centroid[i][j]);
    

    wenn man stdout nimmt sieht man auch was, oder willst du alles als Fehlermeldung exportieren ?



  • Hallo zusammen,

    erstmal vielen Dank für die Ratschläge. Habe das Problem nun gelöst. Bin mir bewusst das der Code sehr kompliziert geschrieben ist, aber mein Hauptaugenmerk liegt nun einfach auf der Funktionalität.
    Hätte abschließend noch zwei Fragen und hoffe ihr könnt mir auch da weiterhelfen.
    Also erstmal würde ich die Centroidzugehörigkeit des Punktes in einer richtigen Tabelle zeigen und nicht hinter jedem Punkt einfach nur die Nummer des Centroids.
    Mein Code für die Berechnung ist:
    for (i = 0; i < 100; i++) {

    dmin = 2000; group = cluster[i];
    for (j = 0; j < 10; j++)
    {

    dpoint = 0.0;

    dpoint += sqrt(pow((point[i][0] - centroid[j][0]),2)+pow((point[i][1] - centroid[j][1]),2));
    fprintf(stdout, "%2.2f ", dpoint); // Show the value of the distance
    if (dpoint < dmin) {
    group = j;
    dmin = dpoint;
    }
    }
    // now, we need to calculate the G matrix (1 or 0)

    fprintf(stdout, " * %d *\n", group); // displays 0 or 1 (to which cluster it belongs)

    Wie kann ich die G-Matrix in einer richtigen Tabelle ausgeben?

    Meine zweite Frage ist folgende.
    Wenn ich beim einlesen der Punkte anstatt 2 Koordinaten 3 Koordinaten benutze. Ich möchte nach wie vor die Rechnung mit den ersten beiden Koordinaten durchführen, nur am Ende soll er den Eintrag der 3 Koordinate aufsummieren für jeden Centroidengruppe und eine Fehlermeldung bei zu großem Wert anzeigen. Jemand eine Idee?

    Vielen Dank schon Mal vorab und einen schönen letzten Ostertag!



  • parismogul schrieb:

    Wie kann ich die G-Matrix in einer richtigen Tabelle ausgeben?

    Zeilenumbrüche an den entsprechenden Positionen ausgeben.

    parismogul schrieb:

    Wenn ich beim einlesen der Punkte anstatt 2 Koordinaten 3 Koordinaten benutze. Ich möchte nach wie vor die Rechnung mit den ersten beiden Koordinaten durchführen, nur am Ende soll er den Eintrag der 3 Koordinate aufsummieren für jeden Centroidengruppe und eine Fehlermeldung bei zu großem Wert anzeigen. Jemand eine Idee?

    Je drei Variablen für Koordinaten in eine Struktur packen und ein Strukturarray benutzen, oder das int-Array um eine Dimension erweitern.
    Oder ein zweites int-Array passend zu deinem Koordinaten-Array.


Log in to reply