Kuru ürünler | kNN'nin fantezi kullanımı
AI Technology Review Press , Bu makalenin yazarı Wei Yixiao, bu makale ilk olarak Zhihu sütun basit kodunda (zhuanlan.zhihu.com/skywind3000) yayınlandı, AI Technology Review yeniden basma yetkisine sahiptir. Aşağıdaki orijinal metindir:
kNN (k-en yakın komşular) giriş seviyesi bir modeldir, çünkü basit ve güvenilirdir ve doğrusal olmayan problemler için iyi bir desteğe sahiptir.Tüm numunelerin kaydedilmesi gerekmesine rağmen, çeşitli alanlarda hala aktiftir ve nispeten sağlam tanıma sonuçları sağlar.
Bundan bahsetmişken, belki şunu söyleyeceksiniz, biliyorum, özellik uzayında test örneğine en yakın k eğitim örneklerini bulmak ve sonra çoğunun belirli bir kategoriye ait olduğuna karar vermek ve sonra bu kategori olarak tanımlamaktır.
Bu, kitapta / İnternette kNN'ye yapılan girişlerin çoğunun retoriğidir, eğer durum buysa, bu makaleyi yazmama gerek yok. Aslında kNN iyi kullanılıyor, bir çiçeği gerçekten kullanabilir, daha temel şeyler eğlencemize değer, değil mi?
İlk tür: sınıflandırma
Birinin bilmemesini önlemek için, basitçe sınıflandırma için kNN'nin temel fikrini gözden geçirelim.
Xu test örneği için, hangi kategoriye ait olduğunu bilmek istiyorsanız, önce tüm Eğitim örnekleri Xu'ya en yakın K komşularını bulun (k = 5) ve ardından bu K komşularının çoğunun hangi kategoriye ait olduğunu belirleyin ve bu kategoriyi test örneğinin tahmin sonucu olarak kullanın.Yukarıdaki şekilde gösterildiği gibi, 4 komşu kırmızıdır, 1 Yeşil ise, Xu'nun kategorisinin "kırmızı" olduğuna karar verilir.
İkinci tür: dönüş
Numune noktasına göre, hatayı numune noktasına en aza indirmek için bir eğri çizin ve ardından herhangi bir koordinat verildiğinde, regresyon adı verilen eğri üzerindeki değeri geri getirin. Peki kNN nasıl regresyon yapar?
Bir dizi örnek koordinatınız (xi, yi) var ve sonra bir test noktası koordinatı x verildiğinde, regresyon eğrisinde karşılık gelen y değerini bulun. KNN ile en kolay yol k en yakın örnek koordinatlarını x'e götürmek ve sonra y değerlerinin ortalamasını almaktır:
Yeşil uygun eğridir.Sklearn'deki KNeighborsRegressor kullanılır.Doğrusal olmayan regresyon probleminin çok iyi işlendiği görülebilir, ancak optimize edilebilir. K komşuları arasında, test noktası koordinatına olan mesafelerine göre x D mesafesinin karşılıklı 1 / d'si ağırlıklandırılır:
w =
y = toplam () / toplam (w)
X bir örnekle çakışırsa ve di = 0, 1 / d sonsuz ise, o zaman örneğin y değeri diğer noktalar dikkate alınmadan doğrudan alınır (sklearn yaklaşımı), dolayısıyla elde edilen Y değeri nispeten güvenilirdir. Yukarı:
Bu şekilde, hata çok daha küçüktür Mesafe y değeri ortalamasını dikkate almayan önceki yönteme sklearn'de tek tip, mesafeyi ağırlık olarak kullanan ikinci yönteme uzaklık denir.
Buradaki eğri uydurmanın etkisi çok güzel.Eğer yerleştirmeyi yapmak için gradyan inişi veya en küçük kareler kullanırsanız, böyle bir etki elde edemezsiniz Destek vektörü regresyon SVR'si bile bu kadar düşük bir hata oranına ulaşamaz. Biraz fazla uyuyorsanız, K değerini ayarlayabilirsiniz. Örneğin, eğriyi daha düzgün hale getirmek için K değerini artırın.
Daha iyi bir yaklaşım, wi'yi exp (-d) olarak ayarlamaktır, böylece d = 0 olduğunda değer 1 olur ve d sonsuz olduğunda 0'a yakın olur:
w = math.exp (-d )
Bu şekilde, x belirli bir eğitim örneğiyle çakışsa veya ona çok yakın olsa bile, wi sonsuz yapılmayacak ve diğer örneklerin ağırlığı göz ardı edilecek, bu da sklearn'de aykırı değerlerle karşılaşıldığında bir daire içinde dolaşmak zorunda kalma sorununu ortadan kaldıracaktır. Eğri daha düzgün olacaktır.
Üçüncü tür: Tek sınıf tanıma
Tek sınıflı sınıflandırma / tanıma da denir: aykırı değer / aykırı değer algılama, bu çok kullanışlıdır. Uygulamamızın 5 farklı kullanıcı hareketini tanıması gerektiğini varsayarsak, genel sınıflandırıcı size yalnızca belirli bir eylemin hangi eylem türüne ait olduğunu söyleyecektir, ancak kullanıcı bazı jest dışı ortak işlemler gerçekleştirirse, "ait olmama" Herhangi bir tür "ise, hareket modülünde herhangi bir işlem yapmadan onu yok saymanız gerekir.
Bu konuyu geleneksel sınıflandırıcılarla kullanmak çok zordur, çünkü negatif örnekler sonsuzdur, tüm ekstra hareketleri saymak için çok fazla, yalnızca pozitif örnekler toplayabiliriz. Bu, 0-9 dijital el yazısı tanıma ile aynıdır.Örneğin, kullanıcı bir A harfi yazarsa, bir giriş görüntüsünün 0-9 arasında olmadığını belirlememiz gerekir, ancak 0-9 örneği dışındaki tüm istisnaları sıralayamayız. Mümkün.
Şu anda, Tek sınıf tanıyıcı her zaman çok önemli bir rol oynamıştır. 0-9 arasındaki tüm örnekleri "pozitif örnekler" olarak giriyoruz ve test değerinin aynı kategoriye mi yoksa test sırasında geçersiz bir negatif kategoriye mi ait olduğunu kontrol ediyoruz. KNN'nin bunu yapması çok kolaydır. NN-d'nin yerel yoğunluk tahmin yöntemini kullanıyoruz:
Yöntem, test örneğini z işlemek, önce eğitim örneğinde en yakın komşu B'yi bulmak, z'den b noktasına olan mesafeyi d1 olarak hesaplamak ve ardından eğitim örneğinde B'ye en yakın C noktasını bulmak ve BC mesafesini şu şekilde hesaplamaktır. d2, eğer:
d1 < = alpha * d2 # alpha genellikle 1 alır
Ardından z örneğini (pozitif kategori olarak tanımlanır) kabul edin, aksi takdirde reddedin (negatif kategori olarak tanımlayın). Bu yöntem nispeten basittir, ancak yerel örnekler çok yoğunsa, d2 çok küçüktür ve negatif kategorinin reddedildiğini anlamak kolaydır. Bu nedenle daha olgun bir yaklaşım, eğitim örneğinde C1-Ck ila B arasındaki en yakın k örnek noktalarını bulmak ve ardından d2'yi C1-Ck'den B'ye olan mesafelerin ortalamasına ayarlamaktır. Bu yönteme kNN-d denir ve tanıma etkisi, yalnızca bir C seçen önceki NN-d'den çok daha iyidir.
Daha da genişletmek için, z'ye en yakın j noktasını B seçebilir, j sonuçlarını bulmak için yukarıdaki yöntemi kullanabilir ve son olarak z'nin kabul edilip edilmediğini belirlemek için oy kullanabilirsiniz. Buna j-kNN-d yöntemi denir. Yukarıda bahsedilen yöntem j'dir. = 1 özel durum.
SVM'nin ONE_CLASS algılama yöntemi ile karşılaştırıldığında, (j) kNN-d benzer bir tanıma etkisine sahiptir.Ancak, özellik boyutu arttığında, SVM'nin ONE_CLASS algılama doğruluğu keskin bir şekilde düşerken (j) kNN-d modeli daha iyi olabilir sonuç.
LIBSVM'deki üç ana kullanım: sınıflandırma, regresyon ve ONE_CLASS (aykırı değer tespiti), denetimli öğrenmedeki üç ana problem türüdür. Burada hepsini kNN ile uyguladık. Çok fazla örneğiniz yoksa ve her birini tanıtmak istemiyorsanız Paket bağımlılığı türü, o zaman kNN en basit ve en güvenilir alternatiftir.
Dördüncüsü: çekirdek işlevi ile
Yaygın olarak Kernel tabanlı kNN olarak bilinen, SVM'nin büyük ilerleme kaydetmesinin nedeni, çekirdek işlevlerinin tanıtılmasından sonradır ve çekirdek işlevleri, SVM'ye özgü değildir. Diğer modeller de çekirdek işlevleriyle aşılanabilir. Bu yönteme toplu olarak "çekirdek yöntemi" denir.
KNN'deki en kritik adım d (xi, xj) mesafesini bulmaktır.Bu mesafeyi bulmanın geleneksel Öklid mesafesi gibi birçok yolu vardır:
Veya Manhattan mesafesi:
Aslında, mesafe işlevi üzerinde bir karışıklık yaratıyor, bu nedenle kNN, çekirdek yöntemini tanıttıktan sonra mesafe işlevi üzerinde de bir karışıklık yaratıyor.
Temel fikir, doğrusal olarak ayrılmaz düşük boyutlu özellik vektörünü doğrusal olarak ayrılabilir yüksek boyutlu özellik uzayına (muhtemelen sonsuz boyut) eşlemektir. X vektörü yüksek boyutlu uzaya eşlenir ve ardından (x), ardından çekirdek fonksiyonu K ( xi, xj) iki yüksek boyutlu uzay vektörünün veya iç çarpımının iç çarpımını temsil eder:
K (xi, xj) = (xi). (xj)
Yaygın olarak kullanılan çekirdek işlevleri SVM ile aynıdır, yaygın olarak kullanılan Gauss çekirdeği (RBF) gibi birkaç tane vardır:
Polinom çekirdeği (POLY):
Ve doğrusal çekirdek (geleneksel Avrupa koordinat sistemindeki nokta çarpımına eşdeğer):
Daha sonra yüksek boyutlu uzayda iki nokta arasındaki mesafe, karot sonrası mesafenin karesi şu şekilde ifade edilebilir:
Bir dönüşümden sonra, (xi) ve (xj) 'yi ortadan kaldırırız ve mesafeyi ifade etmek için xi, xj'nin çekirdek fonksiyonunu kullanırız. Xi, xj'yi doğrudan uzaklığı bulmak için yüksek boyutlu bir uzaya dönüştürmek gerekli değildir. Bunun yerine, doğrudan çekirdek işlevi tarafından hesaplanır.
Çekirdek yöntemine aşina değilseniz, onu atlayabilir, rastgele bir çekirdek işlevi seçebilir ve kNN'nin iki örnek noktası arasındaki mesafeyi bulmak için uzaklık formülüne getirebilirsiniz.
Kai Yu, "Kernel Nearest-Neighbor Algorithm" (https://link.springer.com/article/10.1023/A:1015244902967) 'da çekirdek tabanlı kNN sınıflandırıcısının geleneksel kNN sınıflandırıcısından daha iyi performans gösterdiğini gösterdi çünkü Yalnızca mesafe ölçüm yöntemi değiştirildi, bu nedenle genel süre hala geleneksel kNN sınıflandırıcısına benzer, ancak etki çok daha iyi:
Farklı veri kümelerinde, çekirdekli kNN geleneksel kNN'den daha doğru ve kararlı olabilir. Doğrulamak için ABD Posta Hizmeti verilerini ve BUPA Canlı Bozukluk verilerini kullandılar ve sonuçlar, çekirdekleştirilmiş kNN sınıflandırıcısının doğruluğunun geleneksel kNN'den önemli ölçüde daha iyi olduğunu gösteriyor. Geleneksel kNN ve SVM'nin iyi bir savaşı vardır:
Benzer şekilde, Shehroz Khan ve arkadaşları "Bir Sınıf En Yakın Komşu Sınıflandırması için Çekirdekler" de, Kernel kNN'nin Tek Sınıf sınıflandırma probleminde SVM One-class'tan daha iyi tanıma yeteneği elde ettiğini ve bir dizi veri setine ulaştığını doğruladı. % 87 -% 95 doğruluk oranı.
Beşincisi: uzay bölümü teknolojisi ile
Büyük ölçekli örneklerde düşük kNN performansı sorununa yanıt olarak, kdtree gibi birçok alan bölümleme tekniği geliştirdik:
Uzamsal bir ikilik veri yapısıdır.Yapısı çok basittir.Bir kesme ekseni seçin (tüm numuneler bu eksenin üzerinde en büyük farka sahiptir) ve numuneleri bu eksenin değerine göre sıralayın, medyandan sol ve sağ kısımlara kesin ve ardından devam edin Geçerli düğümde yalnızca bir örnek olana kadar yinelemeli olarak kesin.
Arama yapmak için, önce hedef nokta z'nin bulunduğu yaprak düğümünü yinelemeli olarak bulun, düğümde bulunan örnek x'i "mevcut en yakın nokta" olarak kullanın ve ardından yarıçap olarak d'den z'ye uzaklığı ve tüm ağacı özyinelemeli olarak aramak için çemberin merkezi olarak z'yi kullanın. (Belirli bir alt ağacın aralığı küre ile kesişmiyorsa, aşağı doğru tekrarlanmayacaktır), en yakın nokta bu aralığa düşmelidir ve daha yakın bir nokta bulunduğunda aralık hemen azalacaktır.
Kdtree'de pek çok makale ve kod var. Makalenin uzunluğunu detaylandırmayı düşünmüyorum. İnternetteki çoğu kdree'nin en yakın komşuları bulmanıza yardımcı olduğunu vurgulamak istiyorum, ancak en yakın k en yakın komşuyu nasıl bulursunuz? Makalelerin çoğu söylemedi, birkaçı bunun hala yanlış olduğunu söyledi (sadece yaklaşık bir sonuç).
K uzunluğunda bir öncelik kuyruğu (veya maksimum yığın) tutmanız gerekir. En yakın komşuyu bulmak temelinde, sıra k örnekle dolana kadar kardeş düğümün komşu örneklerini kuyruğa doldurun ve ardından z'yi Çemberin merkezi, kuyrukta z'ye en yakın k'inci örnek yarıçaptır. Kd ağacında bir aralık araması gerçekleştirilir (ilk k noktaları aralık dahilinde olmalıdır) ve öncelik kuyruğu, arama işlemi sırasında ve en son kinci temel alınarak sürekli olarak güncellenir Z'den örnek mesafesinin yarıçapını ayarlayın.
Bu şekilde, z'ye en yakın ilk k örneğini doğru bir şekilde bulabilirsiniz. Kd ağacı boyutsallıkla ilgilidir.Örnek boyutu yüksek olmadığında kd ağacı hızlıdır, ancak örnek boyutu yüksek olduğunda kd ağacının performansı düşmeye başlayacaktır. Aynı zamanda, kd ağacı sadece Öklid uzayında kesmek için uygundur çünkü koordinat eksenini hesaplaması gerekir.
KNN'miz çekirdek yöntemini kullanıyorsa, kd ağacı işe yaramaz, çünkü o sırada özellikler yüksek boyutlu Hilbert uzayıyla eşlenir ve sonsuz boyutlar olabilir ve kd ağacının kenara çekilmesi gerekir.
Bu yüzden hipersfer uzay bölme yöntemine ihtiyacımız var.
Altıncı tip: hipersfer uzay bölümü
Aslında, aynı zamanda uzaysal bir ikilik olan sklearn'daki top-ağaçtır, ancak koordinat eksenine dayanmaz. Yalnızca iki örnek arasındaki mesafeyi çözerek inşa edilebilir. Bu, doğal olarak nükleer teknikleri tanıtmak için uygundur:
Tüm örnekleri bir hiperküreye koyarak başlayın ve x0 küresinin merkezi olarak bir örnek bulun, böylece diğer tüm örneklerden ona olan maksimum mesafe en kısa olur. Sonra x0'dan en uzak olan bir x1 noktasını bulun ve sonra x1'den en uzak olan noktayı x2 olarak bulun ve ardından küredeki tüm örnekleri x1'e en yakın noktaya göre x1'e ve x2'ye en yakın x2'ye atayın ve ardından iki alt küre oluşturun. Daha sonra, kürenin merkezini yeniden ayarlamak için yukarıdaki yöntemi kullanın ve ardından kdtree'ye benzer şekilde yalnızca bir numune dahil edilene kadar tekrar tekrar tekrarlayın.
Diğer bir yol, tüm örnekleri alt yaprak düğümlerine yerleştirmektir. Her yaprak düğüm birçok örnek içerir. Kesime karar vermenin yolu, bir düğümde bulunan örneklerin sayısı eşikten azsa kesilmeyecek, aksi takdirde gerçekleştirilecektir. Kesim.
Bir menzil araması gerçekleştirirken, kdtree ile aynıdır. İlk olarak, üst düğümün hiper küresinin, hedef nokta z ile merkez olarak hedef küre ile kesişip kesmediğini belirleyin (iki kürenin yarıçaplarının eklenip eklenmeyeceği). > = İki kürenin merkezleri arasındaki mesafe), kesişmiyorlarsa atlayın, kesişiyorlarsa, kesişimi değerlendirmek için düğümün sol ve sağ alt kürelerini almaya devam edin, eğer kesişirlerse, yaprak düğümüne ulaşana kadar yukarıdaki adımları yinelemeli olarak tekrarlayın.
Aralık aramanın yalnızca mesafe hesaplamasına dayanması gerektiğinden, vektörün kaç boyuta sahip olduğu ile hiçbir ilgisi yoktur ve ekseni kdtree gibi sayması gerekmez. Bu nedenle, bilyeli ağacın daha uzun yapım süresine ek olarak, genel verimlilik kdtree'yi aşar ve vektör boyutu yüksek olduğunda performans kdtree gibi düşmez ve ayrıca kNN'nin çekirdek sürümünü de destekler.
Kai Yu ve diğerleri posta verileriyle test ettiler. Örnek sayısı arttığında ve düzensizlik arttığında, yüksek boyutlu çekirdek uzayıyla eşleştirilse bile, doğrusal bölünmezlik olacaktır. Şu anda, SVM'nin doğruluğu azalacak ve Top ağacı ile donatılmış çekirdekleştirilmiş kNN artık daha yüksek doğruluk gösterebilir ve aynı zamanda iyi bir sorgu performansına sahip olabilir.
Yedinci: Fazla örneklerin ortadan kaldırılması
KNN'nin performans iyileştirmesi, klasik Yoğun En Yakın Komşular Veri Azaltma algoritması gibi sınıflandırma sonuçlarını olabildiğince etkilemeden gereksiz örnekleri kaldırarak performansı da artırabilir:
Basitçe söylemek gerekirse, önce örnek noktasını silin ve ardından bu noktayı değerlendirmek için diğer örnekleri kullanın. Değerlendirme sonucu doğruysa, bu gereksiz bir nokta olarak kabul edilir ve silinebilir. Yanlışsa, saklanmalıdır.
İndirgeme sonrası örnek veriler orjinalinden farklıdır. Çözüm sonucu yaklaşık bir çözümdür. Hata kontrol edilebilir olduğu sürece kNN'nin arama performansı büyük ölçüde iyileştirilebilir. Etki aşağıdaki gibidir:
Dairelerden noktalara dönen örnekler reddedilen örneklerdir.Soldan sağa, temelde marjinal kısımda sınırlı sayıda örnek tutulduğu görülmektedir.Sonuç çok çekici.
Önceki uzay bölümleme teknolojisi çözüm sonucunu etkilemediğinden, büyük ölçekli kNN genellikle ilk önce bir top-ağaçtır ve gereksiz numuneleri çıkarmak için yeterince hızlı değildir. Dikkat edilmesi gereken tek şey, artıklığın ortadan kaldırılmasının tek sınıf tanımayı veya yoğunluk hesaplamalarına dayanan diğer şeyleri etkileyeceği ve bazı ek işlemlerin gerekli olmasıdır.
Konu özeti
İlk k en yakın komşuyu ararken d mesafe aralığı eklemek, yalnızca hedeften d dahilindeki örnekleri aramak gibi birçok genişletilmiş kullanım vardır, bu da dolaylı olarak tek sınıf sorunun bir bölümünü çözebilir. Aynı anda tüm örneklerden uzaktaysanız, "Hiçbir şey" döndürür. D'nin seçimi, aynı türden örneklerin ortalama yoğunluğu bir alfa ile çarpılarak hesaplanabilir.
Sınıflandırmada, oylama sonuçları, yukarıda bahsedilen mesafenin tersi veya ağırlık olarak exp (-d) gibi, oylama için birden fazla komşunun aynı anda seçilmesinden önceki mesafeye göre de ağırlıklandırılabilir.
kNN, basit uygulaması, kontrol edilebilir hatası (kanıtlanmış) nedeniyle hala çeşitli uygulamalarda etkindir ve doğrusal olmayan problemlerin üstesinden gelebilir.Kullanımının nasıl genişletileceğini, hatasını azaltmak için çekirdek işlevlerinin nasıl kullanılacağını ve alanın nasıl kullanılacağını anlattık. Segmentasyon gibi teknikler performansını artırır.
Kısacası, çok basit olmasına rağmen, gerçekten eğlenmeye değer.İyi uygulanmış bir kNN kütüphanesi, hipersfer uzay kesme ile sınıflandırma, regresyon ve anormallik tanımaya ek olarak kümelemeyle ilgili birçok şeyi yapabilir. İyi kullanın, sizi hayal kırıklığına uğratmaz, sizin için güçlü bir yardımcı silah olabilir, ana silah kullanılamadığında onu kullanmak için kullanabilirsiniz.
Python teknoloji değişimi tartışma grubunu görüntülemek için orijinal metni okumak için tıklayın
