Son zamanlarda yüksek lisans tezim ile  uğraşmaktayım. Tez araştırmam Veri Madenciliği(Data Mining) üzerine. Araştırmış olduğum algoritmaları vaktim oldukça uygulamaya döküyorum. Gene vakit buldukça da blogumda paylaşacağım.

Araştırdığım algoritmalardan birisi bellek tabanlı sınıflandırma algoritmalarından en yakın k-komşu algoritması(k-nearest neighbor algorithm).

Bu yöntem, sınıfları belli olan bir örnek kümesindeki gözlem değerlerinden yararlanarak, örneğe katılacak yeni gözlemin hangi sınıfa ait olduğunu belirlemek amacıyla kullanılır.  Örnek kümedeki gözlemlerin herbirinin, sonradan belirlenen bir gözlem değerine olan uzaklıklarının hesaplanması ve en küçük uzaklığa sahip k sayıda gözlemin seçilmesi esasına dayanmaktadır. Uzaklıkların hesaplanmasında, i ve j noktaları için Öklid uzaklık formülü kullanılabilir:

karekök((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2)

Algoritmanın uygulaması aşağıdaki gibidir:

1. K parametresi belirlenir. Bu parametre verilen bir noktaya en yakın komşuların sayısıdır.
2. Söz konusu nokta ile diğer tüm noktalar arasındaki uzaklıklar tek tek hesaplanır.
3. Adım 2'de hesaplanan uzaklıklara göre satırlar sıralanır ve bunlar arasından en küçük olan k tanesi seçilir.
4. Seçilen satırların hangi kategoriye ait oldukları belirlenir ve en çok tekrarlanan kategori değeri seçilir.
5. Seçilen kategori, tahmin edilmesi beklenen gözlem değerinin kategorisi olarak kabul edilir.

Yukarıdaki bilgiler doğrultusunda php ile kodlanmış örnek bir uygulama yaptım.

Elimizde 10 adet gözlem verisi olsun:

Yukarıdaki gözlem değerlerine bakılarak yeni bir gözlem olan X1=8 ve X2=4 değerlerinin yani (8,4) gözleminin hangi sınıfa dahil olduğunu k-en yakın komşu yöntemi ile bulmak istiyoruz.

1. K'nın belirlenmesi: k=4 olarak alıyoruz.
2. Uzaklıkların hesaplanması: (8,4) noktası ile gözlem değerlerinin herbirisi arasındaki uzaklıklar hesaplanır. Bunun için Öklid uzaklık bağıntısı kullanılır.
   d(i,j) = sqrt( (2-8)^2 + (4-4)^2 ) = 6.00
   d(i,j) = sqrt( (3-8)^2 + (6-4)^2 ) = 5.39
   d(i,j) = sqrt( (3-8)^2 + (4-4)^2 ) = 5.00
   d(i,j) = sqrt( (4-8)^2 + (10-4)^2 ) = 7.21
   d(i,j) = sqrt( (5-8)^2 + (8-4)^2 ) = 5.00
   d(i,j) = sqrt( (6-8)^2 + (3-4)^2 ) = 2.24
   d(i,j) = sqrt( (7-8)^2 + (9-4)^2 ) = 5.10
   d(i,j) = sqrt( (10-8)^2 + (2-4)^2 ) = 2.83
   d(i,j) = sqrt( (3-8)^2 + (4-4)^2 ) = 5.00
   d(i,j) = sqrt( (3-8)^2 + (4-4)^2 ) = 5.00

   X1	X2	Distance
   2	4	6.00
   3	6	5.39
   3	4	5.00
   4	10	7.21
   5	8	5.00
   6	3	2.24
   7	9	5.10
   9	7	3.16
   11	7	4.24
   10	2	2.83

3. En küçük uzaklıkların belirlenmesi: Satırlar küçükten büyüğe doğru ya da büyükten küçüğe doğru sıralanarak en küçük k=4 tanesi belirlenir. Bu k adet nokta verilen (8,4) noktasına en yakın gözlem değeridir. Buna göre 2.24, 2.83, 3.16, 4.24 sonuçlarının olduğu noktalar en yakın sonuçlardır.
4. Seçilen satırlara ilişkin sınıfların belirlenmesi: (8,4) noktasına en yakın olan gözlem değerlerinin Y sınıfları göz önüne alınır ve hangisinin daha fazla olduğuna bakılır. Bu 4 sonuç içerisinde 1 adet GOOD, 3 adet BAD sonucu vardır. Buna göre verilen (8,4) noktasının sınıfı BAD olarak belirlenir.

Uygulamanın php ile yazılmış hali aşağıdadır:

<?php

class K_nearest {
/*
create k-nearest.txt file and paste data list
data list</pre>
2,4,BAD
3,6,GOOD
3,4,GOOD
4,10,BAD
5,8,BAD
6,3,GOOD
7,9,GOOD
9,7,BAD
11,7,BAD
10,2,BAD
*/
 public $dataFile = 'k-nearest.txt';
 private $arrDistances = array();
 private $arrValues = array();
 public $optimalNearest = 4;
 private $arrNearest = array();
 public $result = '';

 function __construct()
 {
 header('Content-Type: text/html; charset=utf-8');
 $this->readDataFile();
 }

 function __setVariables()
 {
 $this->arrDistances = array();
 $this->arrNearest = array();

 }

 public function execute($x1,$x2)
 {
 $this->__setVariables();
 $this->getDistance($x1,$x2);
 $this->sortDistances();
 $this->getNearest();
 $this->getResult();
 }

 private function getDistance($x1,$x2)
 {
 $tempVal = 0;

 foreach ($this->arrValues as $val) {
 $this->arrDistances[] = round(sqrt(pow(($val[0]-$x1),2)+pow(($val[1]-$x2),2)),2);
 }
 }

 private function sortDistances()
 {
 asort($this->arrDistances);
 }

 private function getNearest()
 {
 $i=0;
 foreach ($this->arrDistances as $key => $val) {

 if($i<$this->optimalNearest) {
 $this->arrNearest[] = $key;
 }

 $i++;
 }
 }

 private function getResult()
 {
 $countBad = 0;
 $countGood = 0;

 foreach ($this->arrNearest as $val) {

 if ($this->arrValues[$val][2] == "BAD") $countBad++;
 if ($this->arrValues[$val][2] == "GOOD") $countGood++;
 }

 if ($countBad>$countGood) $this->result =  'BAD';
 if ($countBad<$countGood) $this->result =  'GOOD';
 if ($countBad==$countGood) $this->result =  'EQUAL';
 }

 private function readDataFile()
 {
 $f = fopen($this->dataFile, "r");

 $i = 0;
 $arrTemp = array();

 while ( $line = fgets($f) ) {

 $arrTemp = explode(',',$line);

 $j = 0;
 foreach ($arrTemp as $var) {
 $this->arrValues[$i][] = trim($var);
 $j++;
 }

 $i++;
 }

 }

 private function print_pre($data)
 {
 echo "<pre>";
 print_r($data);
 echo "</pre>";
 }

}

$kNearest = new K_nearest();
$kNearest->execute(8,4);
echo $kNearest->result;
echo "<br>";
$kNearest->execute(1,2);
echo $kNearest->result;

Not: Uygulama ve anlatımda Dr. Yalçın ÖZKAN'ın Veri Madenciliği Yöntemleri kitabı esas alınmıştır. Hocamıza teşekkür ediyorum.