✔ k-Means-Algorithmus in C++ - Problem bei Programmierung

A

Amateur2013

Grünschnabel
Hallo zusammen,

da ich neu in diesem Forum bin, hoffe ich, nicht gleich der bestehende Forum-Netiquette zuwider zu posten. Andernfalls wäre ich für einen netten Hinweis dankbar :)

Ich habe folgendes Problem: Ich wollte mir für eine wissenschaftliche Hausarbeit ein wenig Arbeit ersparen und habe ein kleines C++-Programm geschrieben, um meine Daten zu clustern (k-Means Algorithmus).
Um zu testen, ob mein Programm funktioniert habe ich zunächst 4 Datenpunkte geclustert. Mein Programm scheint ok zu sein. Nun habe ich es auf 100 Datenpunkte ausgeweitet (alle 100 Punkte werden im Programm genannt). Bei 4 Punkten rechnete das Programm ca. 5 Sekunden. Nun aber bei 100 Punkten rechnet es schon seit über 8 Stunden. Was ist das Problem****?

Ich wäre euch sehr dankbar, wenn ihr mir hierbei unter die Arme greifen könntet. Ist es möglich, dass Programm so zu ändern, dass auch 100 Punkte in wenigen Sekunden geclustert werden können?
Zu meinem Hintergrund: Ich habe mal als Mathestudent einen kleinen C++-Einführungskurs belegt, nichts großes. Daher bitte laientauglich erklären :)

Vielen Dank schon einmal, unten der Algo!
Gruß
Paul



C++: 
#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;
				}
			}
			
			
			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");
		
		
	}
	
}
 
Hallo und Willkommen im Forum, bin auch relativ neu hier .... :)

Die Dimension für cluster[10], count[10] (und sum?) ist falsch, sollte wohl 100 heissen.

Dadurch dass die Zählvariable i und die oben gennanten Variablen auf dem Stack liegen hasst du mit der Initialisierungsschleife einen Pufferüberlauf erzielt und auch die Variable i jedes mal mit 0 überschrieben.

Code: 
int i;
int cluster[10];
...
for (i = 0; i<100; i++) 
	cluster[i] = 0;
// -> cluster ist nur 10 Elemente groß, cluster[i] für i>=10 hat zufolge dass i irgendwann auch 0 gesetzt wird
// -> Endlosschleife

Hab jetzt nicht weiter geschaut, jedoch solltest du dafür Sorge tragen dass die Zugriffe korrekt sind.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück