K-Means

Dün biri bana "şirkette yazdığım en karmaşık algoritma k-means yea" diye hava attı. Düşündüm de şimdiki işimde kullandığım en karmaşık algoritma DFS. O da abuk subuk bir yerde. Altta kalmamak için ben de k-means yazayım neyim eksik dedim :) .

K-means bir çeşit sıkıştırma algoritması olarak da kullanılabiliyor, Bishop'un kitabında örneği de var. Eğer bir resmi k-means ile sıkıştırmak istiyorsak standart k-means'i pikseller üzerinde tek boyutta uygulayabiliriz. Yanlış hatırlamıyorsam Bishop kitabında her bit için uyguluyordu, sadece 3 renk için uygulamak daha kolayıma geldi :) .

Elimizdeki resim şu olsun (kaynak);

ironman

K=2 ile sıkıştırdığımızda elimizdeki resim aşağıdaki gibi olacak;

ironman_k_2

K arttıkça resmin orijinale yaklaşmasını bekliyoruz. K=5 ile sıkıştırdığımızdaysa resim aşağıdaki gibi olacak;

ironman_k_5

Ben kendime C#'ta k-means yazmadı dedirtmem! :) (Bu arada cidden Python'daki list comprehension'lar hayat kurtarıyormuş, bir kez daha anlamış oldum).

Moving AI

Moving AI, University of Denver'da bir yapay zeka çalışma grubu. Jump Point Search algoritmasının anlatıldığı makaledeki sonuçları incelerken denk gelmiştim ama açıkçası sitelerini detaylıca incelememiştim. Bir zamandır da yol bulma algoritmalarını denerken daha büyük ve ayrıntılı haritalar kullanma fikrim vardı. StarCraft harita dosyalarını falan indirdim ama formatları çok karışık diye kurcalamadım. Moving AI ise tam bu sorunuma çözüm oldu :) .

Grubun sitesinde çeşitli benchmark arşivleri var. Bu arşivlerde 512x512'lik düz haritaların yanında StarCraft, Baldurs Gate, WarCraft gibi oyunların da haritaları var. Haritalar basit bir text formatı şeklinde verilmiş. Su, ağaç, bataklık gibi temel gruplara ayrılmış. Haritaların dışında, her harita için algoritmaları test edebileceğimiz test senaryoları da mevcut. Kısacası nimet gibi bir yer :) .

Haritaları okuyup sadık yarim matplotlib'e çizdiren kodu yazdım, otomatik olarak test eden kısımları da yazıp algoritmaları daha ayrıntılı haritalarda test etmeye başlayacağım.

Haritaları matplotlib'de çizdirince aşağıdaki gibi görünüyor (orijinali) (yeşiller ağaçlık alan :) );

map

Hammersley Sampling

Rastgele çalışmasını istediğimiz ama o kadar rastgele çalışmasını istemediğimiz bazı algoritmalar oluyor :) . Uniform oluşturduğumuz rastgele sayılar bazen işimizi görmüyor, bazen de zaten önceden elimizde olan kısıtlarla olasılık uzayını daraltmak istiyoruz. Bu gibi durumlarda quasi-random denilen, pseudo-random'ın da daha az rastgelesi sayıları kullanıyoruz.

Hammersley Sampling böyle sayıları üretebildiğimiz bir yöntem. Başlangıçta \(d\) boyutlu uzayda noktalar üretebilmek için \(d-1\) asal sayıya ihtiyaç var. Üreteceğimiz nokta sayısını da önceden bilmek lazım. \(i.\) noktanın 1. boyutu için üreteceğimiz sayı \(\frac{i}{n}\) oluyor. \(k. (k > 1)\) boyut için de şu yöntemi kullanıyoruz;

\(i\) sayısını, \(p_k\) sayı tabanında \(a_1a_2a_3...a_n\) şeklinde gösterdiğimizi düşünelim. Üreteceğimiz sayı

\[\Phi(i) = \frac{a_n}{p_k} + \frac{a_{n-1}}{{p_k}^2}+\frac{a_{n-2}}{{p_k}^3}..\]

ve ürettiğimiz nokta da

\[r(i) = (\frac{i}{N}, \Phi_1(i), \Phi_2(i)...)\]

olacak.

Yani örnek vermek gerekirse, elimizdeki asal sayılar \(p = (2, 3)\) olsun ve  \(N=10\) sayıdan \(i=5.\) sayıyı üretiyor olalım. Buradan

\[r_1(5) = \frac{5}{10} = \frac{1}{2}\]

olacak. 2 tabanında \(5 = 101\) olduğuna göre

\[r_2(5) = \frac{1}{8} + \frac{1}{2} = \frac{5}{8} \]

olacak. Son olarak, 3 tabanında \(5 = 12\) olduğuna göre

\[r_3(5) = \frac{1}{9} + \frac{2}{3} = \frac{7}{9}\]

olacak. Bu yöntemle 3 boyutlu uzayda \(r(5) = (\frac{1}{2},\frac{5}{8},\frac{7}{9})\) örneğini ürettik.

hammersley

p = (2) asal sayı kümesi ile üretilmiş Hammersley sayıları.

Bu yöntem ile RRT ya da PRM gibi algoritmaları çalıştıracaksak artık rastgele noktaları sadece Hammersley noktalarından seçeceğiz. Her şeyi süper hale getiren bir yöntem değil tabii ama makalelerden gördüğüm kadarıyla, özellikle engellerden kaçtığımız haritalar için baya kullanışlı.

 

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ı;

OptimizationTestSuite

Optimizasyon problemlerinde kullanılan algoritmaların (genetik algoritmalar, hill climbing, particle swarm optimization vs) test edilmesinde kullanılan bazı örnek fonksiyonlar var. Bunlar

\[f(x) = \sum\limits_{i=1}^{n} {x_i}^{2}\]

gibi basit bir fonksiyondan

\[f(x_1, x_2) = -\frac{1+cos(12\sqrt{{x_1}^2 + {x_2}^2})}{\frac{1}{2}({x_1}^2 + {x_2}^2) + 2}\]

fonksiyonu gibi kıl bir fonksiyona kadar çeşitli zorluklarda değişebiliyor (Bu fonksiyonların bahsedildiği makale buradan okunabilir).

Makaledeki 20 kadar fonksiyonun çeşitli algoritmalarla test edilmesini basitleştirmek için OptimizationTestSuite diye bir proje oluşturdum. Başlangıç olarak da içine Hill Climbing algoritmasını ve De Jong fonksiyonunu (ilk fonksiyon) koydum. Diğer problemleri ve algoritmaları eklemeye devam edeceğim.

Bu arada 2. fonksiyona kıl dememin sebebi, fonksiyonun \([-5.12, 5.12]\) aralığında çizilmiş aşağıdaki grafiğinden anlaşılabilir :) :

drop_wave