k means алгоритм ашигласан хялбар жишээ /Pokemon/

Ерөнхийдөө k means алгоритм нь өгөгдсөн өгөгдлийн олонлогоос хамаарч k тооны cluster буюу ижил төрлийн эсвэл ойролцоо шинж чанар бүхий бүлгүүдийг үүсгэхэд ашигладаг. Хэрэгжүүлэхэд хялбар болон энгийн шинж чанараараа энэ алгоритм алдартай. Зардал бага "эрчим хүчинд хэмнэлттэй" тул ихэнхдээ аливаа их хэмжээний өгөгдөлд pre-cluster буюу илүү өндөр түвшний алгоритм д өгөгдлүүдийг бэлдэж өгөхөд хэрэглэгддэг.

Mobicom ын Дэлхийн аваргын үеэр явуулж байсан бөмбөг булаацалддаг тоглоом шиг дүрэмтэй тийм аппликешн хийх бодолтой байна. Одоогоор санаа нь бол Pocket Monster буюу Pokemon: Өдөрт тодорхой нэг байршилд pokemon гарч ирэх ба хэн түүнийг түрүүлж авч хамгийн их pokemon той болсон нь түрүүлэх юм. Үүнийг хэрэгжүүлэхэд хамгийн тохиромжтой нь k means алгоритм

Зорилго нь: Өдөрт k тооны Pokemon уудыг гаргах ба тоглогчид тэрхүү Pokemon уудыг түрүүлж олж өөрийн болгох ёстой. Мөн тоглогчид өөрт нь ойр байх pokemon ыг хэлэх ба энэ мэдээлэл хэдэн хүнд очсон өөрөөр хэлбэл өөрт нь хэдэн өрсөлдөгч байгааг сануулах юм. "It's always good to know your enemy Right?" Мөн нэг цагийн дараа гэхэд тухайн сегментээс хамаарч pokemon ы байршил өөрчлөгдөх болно, өөрөөр хэлбэл цэнтройдыг дахин бодох болно.

Бидэнд "Players" нэртэй хүснэгт түүн дотор тоглогчдын мэдээлэл, хамгийн гол нь гео байршлын мэдээлэл (latitude, longitude) нь байгаа гэж үзье. Гео байршлын мэдээлэл мэдээж үргэлж өөрчлөгдөж байна. Хамгийн сүүлд GPS асаалттай байсан цэгийг ачаалах (current) байршил гэж үзнэ.

class Data{
 var $dbhost;
 var $username;
 var $password;
 var $database;

 var $connection;

 function Data(){
        //construction
        $this->InitialDB();
    }
    //initialize with this next time
    function InitialDB(){
        $this->dbhost  = 'localhost';
        $this->username = 'root';
        $this->password  = '';
        $this->database  = 'pokemon';
    }
    /**
     * get geo data to proceed next step
     * @return  latitude, longitude mysql result
     */
    function GetGeoData(){
        if(!$this->DatabaseConnect())
        {
            return false;
        }
        $query = "SELECT latitude, longitude FROM players";
        
        $result = mysqli_query($this->connection,$query);
        return $result;
    }
    /**
     * db connector
     * @return  true or false; is DB successfully connected
     */
    function DatabaseConnect(){

        $this->connection = mysqli_connect($this->dbhost,$this->username,$this->password,$this->database);
  
        if(!$this->connection){   
            error_log("Login info wrong", 0);
            return false;
        }
        if(!mysqli_select_db($this->connection,$this->database)){
            error_log("DB error", 0);
            return false;
        }
        if(!mysqli_query($this->connection,"SET NAMES 'UTF8'")){
            error_log("UTF encoding error", 0);
            return false;
        }
        return true;
    }
}

Харин одоо үндсэн кластер хийх Kmeans классыг хэрэгжүүлье. Энэхүү арга нь бидэнд кластер үүсгэж өгөхөөс гадна тус бүрт нь цэнтройдуудын координатуудыг өгөх болно. Цэнтройдуудын байршил дээр манай покемонууд гарах ба харин тухайн цэнтройдын сегментэд орсон тоглогчдод мэдээлэл илгээх болно.

class Kmeans
{
    var $data;
    var $cluster_result; // cluster hiigdeh array
    var $centroids;
    var $centroid_distance; // centroid hurtelh zainii array
    /**
     * baiguulagch
     *
     * @param  data  ogogdliin sangaas irsen lat long olonlog
     */
    public function Kmeans(array $data)
    {
        if (count($data) < 2) {
            error_log('Data must have more than 2'); // dor hayj hoyr huvaagdahiin tuld
        }
        $this->data = $data;
    }

    /**
     * cluster hiih undsen arga, busad arguudaa aguulna
     *
     * @param   kcount   k toonii cluster bolgoh
     * @return  array    cluster hiigdsen array butsaana
     */
    public function cluster($kcount)
    {
        if ($kcount < 2) {
            throw new Exception('k have to greater than 1');
        }
        if ($kcount > count($this->data)) {
            throw new Exception('k have to less than data'); // huvaagch ni huvaagdagchaas ih bj bolohgui
        }

        do {
            if (empty($centroids)) {
                $centroids = $this->getRandomInitialization($kcount); // ehnii udaa achaalj centroid iig songoh
            } else {
                $centroids = $this->calculateCentroids($this->cluster_result); // bj boloh centroidiig oloh
            }

            $new_cluster_result = array_fill(0, $kcount, []);
            foreach ($this->data as $current) {
                $closest_centroid = $this->calculateClosestCentroid($current, $centroids);
                array_push($new_cluster_result[$closest_centroid], $current);
            }
        } while ($this->clusterResultCheck((array) $this->cluster_result, $new_cluster_result) === false);
        
        $this->centroids = $centroids;
        return $this->getClusteredData();
    }

    /**
     * bodogdson centroid iig avah
     * @return  array  centroids
     */
    public function getCentroids()
    {
        if (empty($this->centroids)) {
            return 0;
        }
        return $this->centroids;
    }

    /**
     * bodogdson cluster iig avagch
     * @return  array  clustered data array
     */
    public function getClusteredData()
    {
        if (empty($this->cluster_result)) {
            throw new Exception('Clustered data have not been hydrated yet - run cluster method first');
        }

        return $this->cluster_result;
    }
    /**
     * Sanamsarguigeer centroid uudiig songoh function
     * @param   $kcount  heden shirheg cluster bolgoh ve
     * @return  array k shirheg elementtei array
     */
    protected function getRandomInitialization($kcount)
    {
        $random_keys = array_rand($this->data, $kcount);
        $random_keys = array_flip($random_keys);
        return array_intersect_key($this->data, $random_keys);
    }

    /**
     * huvaagdsan clusteruudaas centroid oloh function
     *
     * @param   $cluster_result
     * @return  centroiduud butsaana
     */
    protected function calculateCentroids(array $cluster_result)
    {
        $centroids = [];
        foreach ($cluster_result as $cluster) {
            $cluster_sum = array_fill(0, count(current($cluster)), 0);
            foreach ($cluster as $current) {
                foreach ($current as $key => $value) {
                    $cluster_sum[$key] += $value;
                }
            }
            $centroid = array_fill(0, count(current($cluster)), 0);
            foreach ($cluster_sum as $key => $value) {
                $centroid[$key] = $value / count($cluster);
            }
            array_push($centroids, $centroid);
        }
        return $centroids;
    }

    /**
     * ajiglaj bui olonlog dotorh hamgiin oir centroid iig olj bolomjit shiljiltiig zaah
     *
     * @param   $current     datasetees ajiglaj bui array
     * @param   $centroids   centroiduud
     * @return  shiljih index
     */
    protected function calculateClosestCentroid(array $current, array $centroids)
    {
        $centroid_distance = [];
        foreach ($centroids as $centroid) {
            array_push($centroid_distance, $this->calculateDistance($current, $centroid));
        }
        asort($centroid_distance);
        $centroid_distance = array_keys($centroid_distance);
        return array_shift($centroid_distance);
    }

    /**
     * clustert zow huvaaj duussan esehiig shalgah
     *
     * @param   $cluster_result      omnoh cluster hiigdsen
     * @param   $new_cluster_result  suuld cluster hiigdsen
     * @return  omnohoosoo iluu bish bnu ugui yu boolean butsaana
     */
    protected function clusterResultCheck(array $cluster_result, array $new_cluster_result)
    {
        //medeej hooson bol davtalt yvagdah yostoi false butsaa
        if (empty($cluster_result)) {
            $this->cluster_result = $new_cluster_result;
            return false;
        }
        //omnohoos neg l elm oor clustert orvol tsaash yvah yostoi
        foreach ($cluster_result as $key => $cluster) {
            foreach ($cluster as $c) {
                if (!in_array($c, $new_cluster_result[$key])) {
                    $this->cluster_result = $new_cluster_result;
                    return false;
                }
            }
        }
        //oorchlolt bhgui tul davtalt duusnaa
        return true;
    }

    /**
     * hoyor tsegiin hoorondoh zaig eucled iin theorem ashiglaj oloh
     */
    protected function calculateDistance($point_a, $point_b)
    {
        $distance = 0;
        for ($i = 0, $count = count($point_a); $i < $count; $i++) {
            $difference = $point_a[$i] - $point_b[$i];
            $distance += pow($difference, 2);
        }
        //haritsuulaltad ashiglaj bgaa bolohoor sqrt buyu yzguur avah shaardlagagui
        return $distance;
    }
}

Харин одоо view хэсэгт дараах байдалтай хэрэгжүүллээ. Энэ нь ихэнхдээ сервис байдалтай ашиглагдана гэж үзээд ямар нэг хэвжүүлэлт хийсэнгүй, мөн дурын гэдгийг анзаарсан байх.

require_once("src/KMeans.php");
require_once("src/Data.php");

$data = new Data();
$array = array();
$k = 3; //3 cluster uusgeh

//populate data
$result = $data->GetGeoData();
while($row = mysqli_fetch_array($result, MYSQLI_ASSOC)) {
    $array[] = array($row['latitude'], $row['longitude']);
}

$kmeans = new Kmeans($array);

//mother of all process - cluster hiih
$kmeans->cluster($k);

//ene hesegt heseg delay hiij bolno (optional)
//cluster bolgoson segmentuudee avah
$clusterdata = $kmeans->getClusteredData();
//clusteruudiin centroid iig avah
$centroids = $kmeans->getCentroids();

echo "Pokemon гарах байршлууд 
-----------------------
";
echo json_encode($centroids);
echo "
__________________________
Тоглогчдын сегментүүд 
-----------------------
";
echo json_encode($clusterdata);

Энэ бүхний гаралт дараах байдалтай гарч байна. Тест учир харьцангуй цөөн өгөгдлүүдтэй байгаа. Их хэмжээний өгөгдөл дээр илүү тогтвортой ажиллах болно. k нь 3 буюу 3 сегмент болголоо.

Дүгнэлт: K means алгоритм ашиглан хялбар жишээ хийж үзлээ. Ямар нэгэн дээд түвшний кластер хийгээгүй буюу өөрөөр хэлбэл зөвхөн гео мэдээлэл үндэслэж гаргасан тул янз бүрийн байшин объект гол мөрөн эсвэл ямар нэгэн боломжгүй цэг дээр манай цэнтройд байрлахыг үгүйсгэхгүй.