Irakli Koiava

K-means clustering         ვთქვათ მოცემული გვაქვს n ცალი დაკვირვების წერტილი (x 1 , x 2 , x 3 , ... , x n ), რომელთაგან თითოეული წარმოადგენს d განზომიალებიან ვექტორს. ამოცანა მდგომარეობს შემდეგში, რომ ჩვენ უნდა დავყოთ n ცალი დაკვირვების წერტილი K კლასტერად (k  ≤  n) S = {S 1 , S 2 , S 3 , ..., S k } ისე რომ ნებისმიერი წერილი მოხვდეს კლასტერში და თითოეული კლასტერისათვის მოვახდინოთ კვადრატების ჯამის მინიმიზაცია:         სადაც  μ i  არის i-ური კლასტერის წერტილების საშუალო. ეს პრობლემა შედის NP-რთული ამოცანების ჯგუფში . K-საშუალოს კლასტერიზაციის მეთოდი არის ევრისტიკული მეთოდი რომელიც საკმაოდ სწრაფად წყვეტს ამ ამოცანას და პოულობს ლოკალურ მინიმუმს. თუმცა პრაქტიკულ ამოცანებში ეს მინიმუმი ხშირად ემთხვევა გლობალურს.         რაც შეეხება თავად K-საშუალოს კლასტერიზაციის ალგორითმს, ის მთლიანად დაფუძნებულია Lloyd-ის ალგორითმზე . თავდაპირველად ხდება მოცემულ n წერტილზე ვორონოის დიაგრამის აგება შემთხვევითად ა...