Voronoi Diyagramları ve Python

Voronoi Diyagramları kullanım alanı çok geniş olabilecek bir konu. Wikipedia'da sanatsal işlerde kullanıldığı bile yazıyor. Benim şimdiye kadar tek kullandığım ve gayet işime yarayan kullanımı ise olasılık dağılımlarının gösterimi.

Belirli bir olasılık dağılımından rastgele nokta üreterek çalışan yöntemlerde (sample based) her dağılım kullanışlı olmayabiliyor. Robot hareketinde rastgele olarak yolu bulmaya çalışırken bu rastgeleliğin yarı-rastgele (quasi-random) olmasını sağlamaya çalışıyoruz. Hareket için uniform dağılım kullanacak olursak Voronoi diyagramı aşağıdaki gibi oluyor;

uniform_voronoi

Bu grafik bize 2 şeyi gösterebilir; birincisi sol alttaki gibi sıkışık alanlar oluşabilir, örnek sayımız sınırlı olduğunda buralarda takılıp kalabiliriz. İkincisi ise üst taraflardaki gibi büyük Voronoi hücreleri oluşabilir. Hücre ne kadar büyükse o noktaya yakın bir başka nokta da o kadar uzak demek, dolayısıyla nokta ulaşılabilir olmayabilir.

Üstteki grafiği de Python'da çizdirdim. Scipy + matplotlib ile uniform dağılımın Voronoi diyagramını oluşturmak için çok fazla kod yazmaya gerek kalmadı;

Matplotlib ile İlgili Bir Not

2-3 haftadır falan Matplotlib'i kullanarak bir proje geliştirmeye çalışıyorum. Proje çeşitli robot hareket ve sensör modellerini içerecek bir simulator aslında (Aşağıdaki görüntüde odometri modeli var).

ss

 

Burada, özellikle sampling ile çalışırken her dağılım için epey bir nokta çizdirmek gerekiyor. Ben ilk yazdığımda çok dikkat etmediğim için aşağıdaki gibi bir kodla çizdiriyordum:

Sonradan ortaya çıktı ki, meğerse bu plot fonksiyonu epey maliyetliymiş. Bu yukarıdaki kod netbookumda 17 sn.'de çalışıyor mesela. Aşağıdaki yöntemin ise bir öncekiyle arasında baya bir performans farkı var:

Bu da 0.01 sn gibi bir sürede çalışıyor.

Demek ki neymiş; ne kadar az plot çağırırsak o kadar iyiymiş :).

Matplotlib ile İki Değişkenli Normal Dağılımların Gösterimi

Olasılıksal süreçlerde, iş olasılık dağılımlarının gösterimine geldiğinde iki yöntem kullanabiliriz;

  • Sampling, yani dağılımdan veri üretilmesi.
  • Contour ya da heatmap denilen, örnekleme yapmadan gösterim.

Sampling yaklaşımının gösterilmesi diğer yönteme göre daha basittir. Hesaplamaları yaptığımız ortamlarda (scipy, MATLAB vs.) Gauss dağılımına göre rastgele sayı üretme fonksiyonu bulunduğundan, tek yapılacak iş belirli bir örnek sayısı kadar rastgele sayıyı bu dağılımdan üretmek olacaktır.

Elimizde

\[\mu = (4, 4)^T\]


ve

\[\sum = \begin{pmatrix}3 & 0.4 \\ 0.4 & 0.15\end{pmatrix}\]

parametrelerine sahip bir Gauss dağılımı olsun. Örnek sayısı 200 olmak üzere, Sampling yöntemini kullanırsak grafik aşağıdaki gibi olacaktır (kırmızı nokta ortalama noktasını göstermektedir).

sampled

Örnek sayısı arttıkça üstteki grafik gerçek dağılıma daha çok benzeyecektir.

Sampling yöntemi varyansla ilgili bir fikir verse de, grafiği daha anlaşılır yapmak için contour yöntemi kullanılır. Bu yöntem, 3 boyutlu ortamda Gaussian dağılıma tepeden bakmak olarak da tanımlanabilir. Grafiğin renkleri olasılığın değerine göre değişecektir.

direct

Bu grafikte büyük olasılık değerleri siyah renge yakın olarak gösterilmektedir.

Matplotlib'de bu tip grafikleri oluşturmak için, pyplot  içindeki  pcolormesh fonksiyonu kullanılır. Bu fonksiyon, grafik üzerindeki bir dikdörtgenin içerisinde bu işlemi yapar ve yapabilmek için bu dikdörtgenin her bir hücresine denk gelen \(x\), \(y\) ve \(p(x, y)\) değerlerini birer matrix olarak alır. Yukarıdaki grafiği çizen kod parçası aşağıdaki gibidir.

 

Grafiğe verilecek diğer colormap değerleri http://wiki.scipy.org/Cookbook/Matplotlib/Show_colormaps adresinden görülebilir.

Matplotlib ile algoritma animasyonları

Matplotlib, kullanım kolaylığı, arayüzünün güzelliği ve en önemlisi bir Python kütüphanesi olması sebebiyle en sevdiğim kütüphanelerden bir tanesi :). Büyük boyutta veriyle çalışırken çok uygun olacağını düşünmüyorum fakat özellikle algoritma geliştirirken, küçük dataset'ler üzerinde denemeler yaparken gayet uygun.

Matplotlib'in grafik çizme dışındaki yeteneklerinden biri de animasyon oluşturabilmesi. Grafik çizerken yapılan işlerin aynısını matplotlib'in sağladığı bir callback mekanizması içinde yaparak istenilen parametreler ile animasyonlar oluşturulabiliyor.

Kullanılacak fonksiyonlar matplotlib.animation modülü içerisinde bulunuyor.

Sonrasında, pyplot ile bir figür nesnesi yaratıp bunu aşağıdaki gibi animasyona vermek gerekiyor

Buradaki değişkenlere bakacak olursak;

generate_random : Her bir adımda çağırılacak fonksiyon. Bu isim benim denediğim örnekte yazdığım bir fonksiyonun ismiydi yani matplotlib'e özel bir şey değil.

25 : Fonksiyonun kaç kez çağırılacağını belirten parametre.

fargs : Fonksiyon çağrısında fonksiyona geçilecek argümanlar.

interval : Fonksiyon çağrısının kaç milisaniyede bir yapılacağı.

blit : Fonksiyonun, çizilecek nesneleri bir iterator içinde dönüp dönmeyeceği.

Ben örnekte Metropolis Algoritması'nı uyguladım. Algoritma basitçe her adımda bir doğru oluşturup ekrana çiziyor. Bu fonksiyon aşağıdaki gibi.

blit = True  verdiğimiz için bu fonksiyon her seferinde geriye,  Line2D  nesnelerinden oluşan bir liste dönüyor ve her seferinde bu liste ekrana çiziliyor.

Animasyonu ekrana çizdirdiğimiz gibi çeşitli formatlarda dosyalara da kaydedebiliyoruz. Aşağıda görülen gif dosyasını kaydetmek için şöyle bir kod yazmak gerekiyor;

Oluşan animasyon ise şöyle bir şey :)

animation

 

Örnek koda şuradan ulaşılabilir.