Stretch: A feature weighting method for the k nearest neighbor algorithms

Abstract

En yakın k komşu algoritması (EKK) uzun süreli çalışılmış parametresiz sınıflandırmaalgoritmalarındandır. EKK sınıflandırılmış örnek verilerin dağılımının altında yatan birleşik olasılıkyoğunluk fonksiyonunun bilinmediğini kabul eder ve bu fonksiyonu sınıflandırılmış örnek verilerikullanarak ölçümler. Her ne kadar bu varsayım pratikte karşılaşılan problemler açısından gerçekçi biryaklaşım olsa da EKK'nin sınıflandırma doğruluğu, veri depolama miktarı ve hesaplama zamanıüzerinde olumsuz etkilere sebep olur.Bu tezin amacı EKK algoritmasının anlaşılması ve EKK'nin sınıflandırma doğruluğununarttırılması için kullanılan yöntemlerin incelenmesidir. Bu tez esas olarak verilerin sahip olduğu ilgisizözelliklerin EKK algoritmasının sinıflandırma doğruluğuna olan etkisi üzerine yoğunlaşmıs ve busorunu çözmek amaçlı Stretch adında yeni bir yöntem önermiştir. Bu yöntem sınıflandırma öncesindeörnek veriler üzerinde dogrusal dönüşumler uygulayarak EKK'nin sınıflandırma doğruluğunuarttırmayı amaçlar. Başka bir değişle, Stretch örnek verileri kullanarak EKK algoritmasınınsınıflandırma doğrulu ğunu en yuksek büyüklüğe çıkartacak doğrusal dönüşümleri adım adım hesaplar.Bu yöntem her adımda örnek sınıflandırılmış veriler arasından bir veri seçer ve bu veriyi kendi ile aynısınıftaki verilerle yakınlaştıracak ve/veya kendisi ile farklı sınıflardaki verilerle uzaklaştıracak olandoğrusal dönüşümü hesaplar. Farklı adımlarda oluşturulmuş bu doğrusal dönuşümlerin bileşimi olansonuç doğrusal dönüşümü EKK algoritmasının sınıflandırma doğruluğu üzerinde istatiksel olarakkayda değer bir artış gösterir.

The k nearest neighbor learning algorithm (kNN) is one of the well studied nonparametriclearning algorithms. kNN assumes that the underlying joint probability density function of the trainingset is unknown and it estimates the underlying joint probability density functions using the labeled dataset (training set). Although this is a realistic assumption in terms of the real world problems, itintroduces some limitations on the predictive accuracy, the storage complexity and computationalcomplexity of the kNN.The goal of this thesis is to understand kNN and techniques that are used to increase thepredictive accuracy of kNN. This thesis mainly focuses on the effect of the irrelevant features on thepredictive accuracy of the kNN and introduces the Stretch method, a new preprocessing method toincrease the predictive accuracy of kNN by doing linear transformation on the training data matrix. Themethod incrementally constructs a linear transformation that maximizes the nearest neighborclassification accuracy on the training set. At each iteration the method picks an instance from the dataset, and computes a transformation that moves the instance closer to the instances with the samecategory and/or away from the instances in other categories. The composition of these iterative lineartransformations can lead to statistically significant improvements in kNN learning algorithms.