A probabilistic investigation of k nearest neighbor directed graphs

Bu tez, rastgele k en yakın komşu (kEYK) yönlü çizgelerini temel alan niceliklerin asimptotik davranışlarının araştırılması üzerinedir. R^d'deki bir sonlu noktalar kümesinin kEYK yönlü çizgesi, her noktadan en yakın k komşusuna (yani, kümedeki ona en yakın k noktaya) oklar çizilmesiyle elde edilir. İlk olarak, verilmiş sabit bir yönlü çizgenin bir rastgele nokta sürecinden elde edilmiş kEYK yönlü çizgedeki kopyalarının sayısını çalışıyoruz. Homojen Poisson süreci ve düzgün nokta süreci sonucu oluşan nokta kümeleri üzerine tanımlı fonksiyonellerle ilgili asimptotik teoriyi kullanarak, alt yönlü çizge sayılarının asimptotik davranışları üzerine genel sonuçlar sağlıyoruz. Bu sonuçlardan çıkarım olarak, bir kEYK yönlü çizgesindeki sabit iç dereceye sahip noktaların sayısı, müşterek kEYK ikililerinin sayısı ve karşılıklı kEYK ikililerinin sayısı için asimptotik sonuçlar elde ediyoruz. Bazı özel koşullar altında, bu sayımların ortalama ve varyans değerlerini hesaplıyoruz ve aralarındaki stokastik bağımlılıkları inceliyoruz. kEYK tipi bağıntılar uzaysal veri analizinde yaygın olarak kullanılmaktadır (örneğin, ayrışma ve ortaşım motiflerini test etmek için). Birden fazla sınıftan oluşan bir veri kümesinde, bir sınıfın elemanları aynı sınıftaki elemanların yakınında bulunuyorsa uzaysal ayrışma; eğer bir sınıfın elemanları başka sınıflardaki elemanların yakınlarında ise uzaysal ortaşım meydana gelir. Bu tarz motifleri, veri noktalarının kEYK yönlü çizgesini kullanarak çalışıyoruz. Okları, iki uç noktalarının ait oldukları sınıflara göre kategorize edip, k en yakın komşu çapraz tablo (kEYKÇT) adında bir çapraz çizelge oluşturuyoruz. Bir kEYKÇT'deki girdilerin asimptotik dağılımını dört farklı rastgele model altında inceliyoruz. Bu dört rastgele modelin ikisinde veri noktaları bir etiketli nokta sürecinden elde edilirken diğer ikisinde ise, noktalar sabit kabul ediliyor ama noktaların sınıf etiketleri rastgele atanıyor. Baz alınan her bir model için, kEYKÇT'deki girdilerin beklenti, varyans ve kovaryans değerlerini tam veya asimptotik olarak hesaplıyoruz ve tablo girdilerinin ve bunlara bağlı karesel ifadelerin asimptotik dağılımlarını elde ediyoruz. Ayrıca, rastgele kEYK yönlü çizgelerinin eşdönüşüm-değişmez olduğunu gösteriyoruz ve eşdönüşüm-değişmez rastgele çizgelerin sınıflandırılmasını yönlü çizgelere uyarlıyoruz. Bu doğrultuda, rastgeleliğin yapının neresinde yer aldığına göre yeni rastgele yönlü çizge kümeleri tanımlıyoruz; şöyle ki, ok rastgele yönlü çizgeleri, köşe rastgele yönlü çizgeleri ve ok-köşe rastgele yönlü çizgeleri. İlaveten, bir rastgele çizgenin kenarlarına rastgele yön atayarak yön rastgele yönlü çizgelerini tanımlıyoruz. Bu dört rastgele yönlü çizge kümesinin arasındaki ilişkileri çalışıyoruz ve ek olarak, rastgele kEYK yönlü çizgelerinin bu sınıflandırmada nereye düştüğünü belirliyoruz.