K-D tree, R-tree ve boyut laneti | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython örnek paketi ↓

K-D tree, uzayı sırayla koordinat eksenleri boyunca böler. Dengeli yapımda median seçilir. En yakın komşu aramasında önce sorgunun bulunduğu taraf gezilir; bölme düzlemine uzaklık mevcut en iyi uzaklıktan küçükse diğer taraf da aranır. Bölme düzlemini geçmeden “diğer tarafta daha yakın nokta yok” kararı verilemez.

K-D tree dengeli olsa bile exact nearest-neighbour sorgusu en kötü durumda doğrusal olabilir. Boyut yükseldikçe uzaklıklar birbirine yaklaşır, bounding region budaması zayıflar. “Her KNN O(log n)” iddiası yanlıştır. Yaklaşık arama kalite/zaman takası sunar; recall ölçülmeli ve exact bir oracle ile karşılaştırılmalıdır.

R-tree, noktalar yerine dikdörtgenlerle kapsanan uzamsal nesneleri indeksler. Bounding box'lar üst üste binebilir; sorgu birden fazla dalı gezebilir. Ball tree, quadtree/octree ve spatial hashing farklı dağılımlarda avantajlıdır. Coğrafi koordinatları düz Öklid mesafesiyle ölçmek, tarih çizgisi veya büyük alanlarda fiziksel uzaklığı yanlış temsil edebilir.

Adım adım iz sürme

Sorgu (4,4), en iyi uzaklık 3 ve bölme x=5 ise düzleme uzaklık 1; karşı dal budanamaz.

Maliyet ve varsayımlar

Düşük boyutta dengeli yapı pratikte etkili olabilir; worst-case query O(n). Brute-force oracle O(nd).

Çalıştırılabilir örnek

Python 3 ile çalıştır. Assert küçük bir örneği denetler; genel doğruluk ispatı değildir. Bazı ileri örnekler özellikle küçük model veya referans oracle'dır; tam üretim uygulaması değildir.

Python 3

def nearest_oracle(points, query):
    return min(points, key=lambda p: sum((a-b)**2 for a,b in zip(p,query)))
assert nearest_oracle([(0,0),(5,5),(9,9)],(4,4))==(5,5)

KAVRADIĞINI KONTROL ET

Sıra sende

Bu oracle için boyut eşleşmesini neden doğrulamalısın?

Çözümün mantığını göster

zip kısa girdide durur; fazla koordinatlar sessizce yok sayılır. Eşit boyut, boş küme ve sayısal değer sözleşmesi ekle.

Bir adım ileri

Örneği değiştirmeden önce girdi sözleşmesini ve invariantı yaz.
Uygun olan boş, sınır, tekrar ve adversarial girdileri ekle. Basit bir oracle ile karşılaştır.
Belirtilen modelde maliyeti çıkar; farklı girdi büyüklüklerini ölç ve farkları gerekçelendir.

Temel kaynaklar ve ders notları

Bu eğitimde özgün anlatım kullanıldı; aşağıdaki kaynaklar ispatlar ve ileri okumalar sunar. Bağlantılar daha geniş ders modülünü kapsayabilir.

MIT 6.046J · Design and Analysis ↗

İlerlemeden önce alıştırmayı çöz.

RasimAtaberkŞahin