Editing the Nearest Feature Line Classifier

Abstract

ABSTRACT: The main drawbacks in Nearest Feature Line classifier are the extrapolation and interpolation inaccuracies. The former can easily be counteracted by considering segment rather than lines. However, the solution of the latter problem is more challenging. Recently developed techniques tackle with this drawback by selecting a subset of the feature line segments either during training or testing. In this study, a novel framework is developed that involves a discriminative component. The proposed approach is based on editing the feature line segments. It involves three major steps namely, error-based deletion, intersection-based deletion and pruning. The first step compares the benefit and cost of deleting each feature line segment and deletes those that contribute more to the classification error. For the implementation of the second step, a novel measure of intersection is defined and used for line segments in high dimensions to delete the longest of two intersecting segments. The pruning step re-evaluates the retained segments by considering their distances from the samples belonging to the other classes. The proposed approach is evaluated on fifteen real datasets from different domains. Experimental results have shown that the proposed scheme achieves better accuracies on majority of these datasets compared to two recently developed extensions of the nearest feature line approach, namely the rectified nearest feature line segment and shortest feature line segment on majority of these datasets. Keywords: Pattern classification; nearest feature line; line segment editing; interpolation inaccuracy; extrapolation inaccuracy.

……………………………………………………………………………………………………………………………………………………………………………………………………………………

ÖZ: Enyakın öznitelik çizgisi sınıflandırıcısının en önemli zayıflıkları ekstrapolasyon ve interpolasyon hatalarıdır. İlki çizgiler yerine çizgi parçaları kullanılarak kolaylıkla telafi edilebilir. Ancak, sonraki problemin çözümü daha zorludur. Son dönemde önerilen yöntemler bu sorunla eğitme veya sınama aşamalarında öznitelik çizgi parçalarının altkümelerini seçerek başa çıkmaya çalışmaktadırlar. Bu çalışmada, ayırt edici bileşen de içeren yeni bir çerçeve geliştirilmiştir. Önerilen yöntem öznitelik çizgi parçalarını azaltmaya dayanmaktadır. Bu yaklaşım hataya-dayalı silme, kesmeye-dayalı silme ve budama olmak üzere toplam üç basamak içermektedir. Birinci aşama, her öznitelik çizgi parçasını silmenin kazanım ve bedelini karşılaştırır ve sınıflandırma hatasına katkı yapanları siler. İkinci basamağın uygulanması için yeni bir kesişme tanımı yapılmış ve yüksek boyutlu öznitelik uzayında kesişen öznitelik parçalarının uzun olanını silmek için kullanılmıştır. Budama aşamasında, geriye kalan öznitelik çizgi parçaları diğer sınıflara ait eğitme verisine olan uzaklıkları dikkate alınarak yeniden değerlendirilmiştir. Önerilen yöntem, farklı alanlardaki onbeş gerçek veri kümesi üzerinde denenmiştir. Deneysel sonuçlar, önerilen yöntemin son yıllarda enyakın öznitelik çizgisi yaklaşımının uzantısı olarak geliştirilen düzeltilmiş en yakın öznitelik çizgi parçası ve en kısa öznitelik çizgi parçası isimli yaklaşımlara göre, veri kümelerinin çoğunda daha iyi başarım elde ettiğini göstermiştir. Anahtar Kelimeler: Örüntü sınıflandırma; en yakın öznitelik çizgisi; çizgi parçası seçme; interpolasyon hatası; ekstrapolasyon hatası.