Blatt 11 Aufgabe 4 C++

Implementieren Sie eine Funktion kmeans(points,initCenters,k,n) in C++11, welche per k-Means Algorithmus zu einer Liste von zweidimensionalen Datenpunkten points k Cluster findet und deren Center Koordinaten, sowie die Zuordnung von Punkten zu Clustern, zurückgibt. Der Algorithmus soll hierbei maximal n Iterationen durchführen. Die initialen Clusterzentren werden als initCenters übergeben. Es soll die euklidsche Distanz verwendet werden.

Die Zuordnung von Punkten zu Clustern soll über eine Liste L dargestellt werden, sodass der Punkt points[i] dem Cluster Nummer L[i] angehört.

Die resultierende Liste C aus Clusterzentren soll so sortiert sein, dass die Koordinaten von Cluster Nummer x in C[x] zu finden sind.

Scaffold Head: #include <array> #include <cmath> #include <fstream> #include <iostream> #include <vector> using Point = std::array<float,2>; using ListOfPoints = std::vector<Point>; template<class T> std::ostream& operator<<(std::ostream& stream, const std::vector<T>& vec){ stream << "["; for(size_t i = 0; i < vec.size(); i++){ stream << vec[i]; if(i != vec.size() - 1){ stream << ", "; } } stream << "]"; return stream; } std::ostream& operator<<(std::ostream& stream, const Point& p){ stream << "["; for(size_t i = 0; i < p.size(); i++){ stream << p[i]; if(i != p.size() - 1){ stream << ", "; } } stream << "]"; return stream; } struct KmeansResult{ ListOfPoints centerPoints; std::vector<int> clusterAssignments; };
Scaffold Foot: int main(int argc, char** argv){ if(argc < 2){ std::cout << "error missing input argument" << std::endl; return 0; } const int m = 300; std::ifstream input(argv[1]); if(input){ std::string s; int numTestcases; input >> numTestcases; for(int testcase = 0; testcase < numTestcases; testcase++){ int numPoints; input >> numPoints; ListOfPoints points; for(int i = 0; i < numPoints; i++){ Point arr; input >> arr[0] >> arr[1]; points.emplace_back(arr); } int k; input >> k; ListOfPoints initialCenters; for(int i = 0; i < k; i++){ Point arr; input >> arr[0] >> arr[1]; initialCenters.emplace_back(arr); } KmeansResult result = kmeans(points, initialCenters, k, m); std::cout << result.centerPoints << "\n"; std::cout << result.clusterAssignments << "\n"; } }else{ std::cout << "error could not open input file" << std::endl; } return 0; }

Start time:: Do 16 Jan 2020 13:45:00
End time:: Mi 22 Jan 2020 11:00:00

General test timeout:: 10.0 seconds

Tests

Command line arguments	`input.txt`
Comment prefix	`#`
Given input	3 5 2 2 6 8 10 4 16 8 18 4 2 6 0 12 10 29 1 3 3 0 8 4 8 2 6 3 7 0 7 8 1 1 1 4 6 3 6 0 2 5 8 4 3 3 3 3 3 6 7 6 2 7 4 8 3 0 3 4 6 6 7 4 8 8 1 0 2 8 8 3 2 1 8 4 4 2 0 2 6 6 8 7 1 20 19 6 14 17 13 0 16 1 12 17 3 4 19 10 3 17 0 1 9 10 7 3 12 17 6 10 20 9 1 2 5 2 15 20 17 14 19 1 4 8 4 7 13 15 2 5 5 16 19
Expected output	[[6, 4.66667], [17, 6]] [0, 0, 0, 1, 1] [[2.125, 1.375], [2.16667, 5.66667], [6.4, 7.2], [7.2, 2.7]] [0, 0, 3, 3, 3, 3, 2, 0, 1, 3, 3, 1, 3, 0, 0, 1, 2, 1, 2, 0, 1, 2, 3, 2, 0, 1, 3, 0, 3] [[6, 12.3333], [17.6667, 4.5], [3.33333, 3.33333], [14, 17]] [1, 3, 1, 1, 3, 2, 1, 0, 2, 0, 2, 3, 0, 1, 2, 2, 3, 3, 1, 2]

Blatt 11 Aufgabe 4 C++ Assignment

Tests