100.000 alanda 500.000 noktaya sahip bir veritabanım var ve en yakın 2 noktayı bulmak istiyorum. Nasıl yaparım?500.000 puan ile 100 boyutlu bir alanda en yakın 2 nokta nasıl bulunur?
Güncelleme: Alan Öklid, Üzgünüz. Ve tüm cevaplar için teşekkürler. BTW bu ev ödevi değildir.
ANN library'u deneyebilirsiniz, ancak bu yalnızca 20 boyuta kadar güvenilir sonuçlar verir.
Teşekkürler. ANN tam aradığım şey. Umarım herşeyi RAM'de tutabilir. – louzer
ANN kullanımı kolaydır, ama o kadar doğru olduğu garanti edilmez o yaklaşık en yakın komşu uygulama olduğunu belirtmek gerekir. –
Introduction to Algorithms içinde, O (n * logn) zamanında iki boyutlu alanda en yakın iki noktayı bulmaya ayrılmış bir bölüm var. google books adresinden kontrol edebilirsiniz. Aslında, herkese bunu tavsiye ederim, böylelikle divide-ve-conquer tekniklerini uyguladıkları yöntem çok basit, zarif ve etkileyici.
Sorununuza doğrudan genişletilemese de (7 değişkeni 2^101 - 1 ile değiştirilir), çoğu veri kümesi için düzgün olması gerekir. Yani, mantıksal rastgele girdiniz varsa, n noktanın O(n*logn*m) karmaşıklık verecek ve m boyut sayısıdır.
Eğer Öklid alana sahip varsayarak hepsi bu düzenleme
. Örneğin, v vektörünün uzunluğu sqrt(v0^2 + v1^2 + v2^2 + ...)'dur. Ancak, metriği seçebiliyorsanız, algoritmayı optimize etmek için başka seçenekler de olabilir.
Vektörleri 100 boyuttan 20 boyuta dönüştürmek için verilerinizi PCA çalıştırın. Daha sonra bir K-En Yakın Komşu ağacı (KD-Tree) oluşturun ve öklid mesafesine göre en yakın 2 komşuyu alın.
Genellikle yoksa. Ölçüler çok büyükse o zaman kaba kuvvet yaklaşımı (paralel + dağılmış/harita küçültme) ya da kümelenme temelli bir yaklaşım yapmanız gerekir.
Bir kd ağacı kullanın. En yakın komşuluk problemine bakıyorsunuz ve bu tam bir problem sınıfını ele almak için yüksek düzeyde optimize edilmiş veri yapıları var.
http://en.wikipedia.org/wiki/Kd-tree
Not; Eğlenceli problem!
Doğru cevap budur. –
KD-TREE olarak bilinen veri yapısını kullanın. Çok fazla bellek ayırmanız gerekir, ancak verilerinizi temel alarak bir optimizasyon veya iki yol bulabilirsiniz.
http://en.wikipedia.org/wiki/Kd-tree.
Arkadaşım, Doktora Tezi'nde yıllar önce benzer bir sorunla karşılaştığında çalışıyordu. Çalışması, 10 boyutta 1M puanındaydı. Bunu çözmek için bir kd ağacı kütüphanesi kurduk. Çevrimdışı olarak bizimle iletişime geçmek isterseniz kodu okuyabiliriz. Bir metrik uzay http://www.elec.qmul.ac.uk/people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf
kdtrees kolay O Hatırladığım kadarıyla zaman (n log) belirli bir noktaya en yakın komşuluk bulmak olun. O (n log n) 'den daha az olan en yakın puan çiftini bulmak için bir optimizasyon var mı? – rampion
-1, ayrıca wikipedia kD-tree göre N >> 2^k ise (k boyutları ve N sayısıdır; bu durumda 2^100 >> 5e5 ve cevap tamamen yanıltıcıdır) – Unreason
10d 100d değil. Veri noktaları 100d'de 10-d düzlemde olsa bile, kd-tree çalışamaz (imho): 100 s derinliğinde bir kd ağacı düşünün. – denis
mi:
İşte onun yayınlanan gazeteniz? – Seth
İlgi çekici bir yer, 100 boyutlu bir alan nereden aldınız? –
soru, netlikten yoksundur. bu matematiksel bir soru mu? – Sarmaad