HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN - 372 Homework > problem:


2015-40. 50498 - K-Means

CEN - 372 Homework

Start: Sep.16.2015 at 10:00:00 AM
Finish: May.16.2016 at 02:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 2015-10. 50517 - Confusion Matrix
• 2015-20. 50518 - Histogram Equaliz...
• 2015-30. 50519 - Image Filtering
• 2015-40. 50498 - K-Means
• 2015-50. 50659 - Covariance Matrix
• 2015-60. 50505 - kht Puzzle
• 50. 50796 - KNN

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/5000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

K-Means

K-Means is one of the commonly used algorithms in Data Mining. It’s an unsupervised learning method. It partitions the given instances into the given number of clusters where each instance belongs to the cluster with the nearest distance.

When calculating K-Means,

  1. The first K data are assigned as K centers
    • First item is assigned as first center, etc.
  2. Then the distances of all instances to all K centers are calculated.
  3. And every instance is assigned to its nearest center.
  4. According to newly assigned instances, the coordinates of each center is calculated again.
  5. The operation continues from step 2 as far as the difference between previous and this total distances is greater than eps (e.g. 1e-4).

Question: Write a program that reads 3D information for n instances, and print the coordinates of k centers.

Input specification
You will be given two integers in the beginning: the number of instances (n) and the number of clusters (k) where 1 ≤ n ≤10,000 and 1 ≤ k ≤ 10. Then the following n lines will contain 3 integers (x, y and z coordinates) and a class information.

Output specification
Show 3 floating point numbers with 2 digits precision in k lines.

Sample Input I
11 3
-2 5 0
5 8 0
-2 5 0
4 -3 0
-4 6 0
3 8 0
5 -4 0
-5 3 0
-7 6 0
6 -2 0
5 -5 0

Sample Output I
5 -3.5 0
4 8 0
-4 5 0


Для отправки решений необходимо выполнить вход.

www.contester.ru