K-nearest algoritmasının temellerinden önceki  yazımda bahsetmiştim. Bellek tabanlı bir sınıflandırma algoritmasıdır. 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.

Bu yazıda, örneki örnekten farklı olarak normalizasyon işlemi uygulanmaktadır. Normalizasyon işlemi, bir veri grubunun tamamının, aralarındaki oran bozulmadan 0-1 aralığında alınması işlemidir.
Yani elimizde bulunan eğitim setindeki verilerin 0-1 aralığında normalize edilmesi demektir.

Yukarıdaki gözlem değerlerine bakılarak yeni bir gözlem olan X1=7, X2=8 ve X3=5 değerlerinin yani (7,8,5) 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=3 alınır.
2. Normalizasyon: Normalizasyon işlemi için her bir sütundaki minimum ve maksimum değerler bulunur.  İlk sütun için min=3, max=18, 2.sütun için min=2 max=16, 3. sütun için min=4 max=19 şeklindedir.
   Daha sonra her bir veri kendi sütunundaki min ve max değerleri ile normalize edilir.
   Formül: Xn = ( X - X(min) / ( X(max)-X(min) )
3. Uzaklıkların hesaplanması: Normalizasyon işlemi uygulandıktan sonra her bir satır için öklid bağıntısı ile uzaklıklar hesaplanır.
   2 ve 3. adımlar uygulandıktan sonra aşağıdaki sonuçlar çıkmaktadır:

   X1	X2	X3	Uzaklık
   0.47	0.21	1.00	0.98
   0.33	0.00	0.00	0.44
   1.00	1.00	0.13	0.93
   0.60	0.93	0.27	0.63
   0.00	0.93	0.73	0.87

4. Sonucu istenen verilerin normalizasyonu: X17, X2=8 ve X3=5 verileri için de normalizasyon uygulanır. Buna göre çıkan sonuç:
   X1=0,26 , X2=0.43 ve X3=0.07
5. En yakın 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=3 tanesi belirlenir. Bu k adet nokta verilen (7,8,5) noktasına en yakın gözlem değeridir. Buna göre 2.24, 0.44, 0.63 ve 0.87 sonuçlarının olduğu noktalar en yakın sonuçlardır.
6. Seçilen satırlara ilişkin sınıfların belirlenmesi: (7,8,5) 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 3 sonuç içerisinde 1 adet NO, 2 adet YES sonucu vardır. Buna göre verilen (7,8,5) noktasının sınıfı YES olarak belirlenir.

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

<?php

class K_nearest_normalization {

/*

create k-nearest-normalization.txt file and paste data list

10,5,19,YES

8,2,4,NO

18,16,6,NO

12,15,8,YES

3,15,15,YES

*/

public $dataFile = 'k-nearest-normalization.txt';

private $arrDistances = array();

private $arrValues = array();

public $optimalNearest = 3;

private $arrNearest = array();

public $result = '';

private $x1;

private $x2;

private $x3;

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,$x3)

{

$this->x1 = $x1;

$this->x2 = $x2;

$this->x3 = $x3;

$this->__setVariables();

$this->normalization();

$this->getDistance();

$this->sortDistances();

$this->getNearest();

$this->getResult();

}

private function normalization()

{

$arrColOne   = array();

$arrColTwo 	 = array();

$arrColThree = array();

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

$arrColOne[]	= $val[0];

$arrColTwo[] 	= $val[1];

$arrColThree[] 	= $val[2];

}

$arrSize = count($arrColOne);

$firstIndex = 0;

$lastIndex = $arrSize-1;

sort($arrColOne);

$minColOne = $arrColOne[$firstIndex];

$maxColOne = $arrColOne[$lastIndex];

sort($arrColTwo);

$minColTwo = $arrColTwo[$firstIndex];

$maxColTwo = $arrColTwo[$lastIndex];

sort($arrColThree);

$minColThree = $arrColThree[$firstIndex];

$maxColThree = $arrColThree[$lastIndex];

$arrTemp = array();

$i=0;

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

$arrTemp[$i][0] = $this->normalate($val[0],$minColOne,$maxColOne);

$arrTemp[$i][1] = $this->normalate($val[1],$minColTwo,$maxColTwo);

$arrTemp[$i][2] = $this->normalate($val[2],$minColThree,$maxColThree);

$arrTemp[$i][3] = $val[3];

$i++;

}

$this->arrValues = $arrTemp;

$this->x1 = $this->normalate($this->x1,$minColOne,$maxColOne);

$this->x2 = $this->normalate($this->x2,$minColTwo,$maxColTwo);

$this->x3 = $this->normalate($this->x3,$minColThree,$maxColThree);

}

private function normalate($val,$colMinVal,$colMaxVal)

{

return round(($val-$colMinVal)/($colMaxVal-$colMinVal),2);

}

private function getDistance()

{

$tempVal = 0;

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

$this->arrDistances[] = round(sqrt(pow(($val[0]-$this->x1),2)+pow(($val[1]-$this->x2),2)+pow(($val[2]-$this->x3),2)),2);

}

$this->print_pre($this->arrDistances);

}

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()

{

$countYes = 0;

$countNo = 0;

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

if ($this->arrValues[$val][3] == 'YES') $countYes++;

if ($this->arrValues[$val][3] == 'NO') $countNo++;

}

if ($countYes>$countNo) $this->result =  'YES';

if ($countYes<$countNo) $this->result =  'NO';

if ($countYes==$countNo) $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_normalization();

$kNearest->execute(7,8,5);

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.