K-საშუალოს კლასტერიზაცია

K-means clustering

        ვთქვათ მოცემული გვაქვს n ცალი დაკვირვების წერტილი (x1, x2, x3, ... , xn), რომელთაგან თითოეული წარმოადგენს d განზომიალებიან ვექტორს. ამოცანა მდგომარეობს შემდეგში, რომ ჩვენ უნდა დავყოთ n ცალი დაკვირვების წერტილი K კლასტერად (k ≤ n) S = {S1, S2, S3, ..., Sk} ისე რომ ნებისმიერი წერილი მოხვდეს კლასტერში და თითოეული კლასტერისათვის მოვახდინოთ კვადრატების ჯამის მინიმიზაცია:

        სადაც μ_i არის i-ური კლასტერის წერტილების საშუალო. ეს პრობლემა შედის NP-რთული ამოცანების ჯგუფში. K-საშუალოს კლასტერიზაციის მეთოდი არის ევრისტიკული მეთოდი რომელიც საკმაოდ სწრაფად წყვეტს ამ ამოცანას და პოულობს ლოკალურ მინიმუმს. თუმცა პრაქტიკულ ამოცანებში ეს მინიმუმი ხშირად ემთხვევა გლობალურს.
        რაც შეეხება თავად K-საშუალოს კლასტერიზაციის ალგორითმს, ის მთლიანად დაფუძნებულია Lloyd-ის ალგორითმზე. თავდაპირველად ხდება მოცემულ n წერტილზე ვორონოის დიაგრამის აგება შემთხვევითად არჩეული K გენერატორით, სადაც ვორონოის თითოეული რეგიონი მოიცავს რაღაც რაოდენობის წერტილებს თავდაპირველად მოცემული დაკვირვების წერტილებიდან. მათ საფუძველზე თითოეული რეგიონისათვის ხდება ცენტრის გამოთვლა და შემდეგ Lloyd-ის ალგორითმის თანახმად თითოეული გენერატორის გადატანა ახლად გამოთვლილ ცენტრზე. ამ პროცესს ვიმეორებთ იტერაციულად მანამ სანამ არ მივალთ იმ შემთხვევამდე როცა დიაგრამის განახლენბა გახდება უშედეგო. ამ ეტაპზე ალგორითმი პოულობს ლოკალურ მინიმიმს და ამთავრებს მუშაობას.

        მეთოდი ფართოდ გამოიყენება მონაცემთა ანალიზში, ხელონვურ ინტელექტში. ფაქტიურად ის არის ყველაზე გავრცელებული მეთოდი ამ პრობლემის გადასაჭრელად.