8 boyutlu closest pair problemi

[barbu]

C de yazmam gerekiyor programı. 8 boyutlu 54k nokta içinde en yakın 2 noktayı bulucam. dolayısıyla brute force bir program işime yaramaz. recursive divide and conquer kullanmak geldi aklıma ama 8 boyut işin içine girine kafam karıştı iyice.

yardım plz

[di]

8 boyutlu derken? ;

[barbu]

bildiğin 8 boyut. 8 tane attribute var.
1. nokta:a1,b1,c1,d1,e1,f1...
2. nokta:a2,b2,c2,d2....
54bin tane de noktam.

brute force olmaz o yüzden. en iyi closest pair nlogn ile bulunuyor. ama işte 8 tane attribute işin içine girince beynim durdu. dışarıdan birisi görür belki diye koydum.

çok farkı olmaması lazım 2 noktayla. ama işte yapamadım.

bunu da clustering için kullanıcam. agnes clusteringi yapıcam. data mining filan. belki bilen çıkar.

[riglous]

8 "boyutlu" düzlemi bir çizgi bölmez.

Önce iki boyutlu düzlemde iki nokta arası nasıl hesaplanır buna bak.
Sonra 3 boyutlu ortamda iki nokta arasına bak.
Sonra 8 boyuta uyarla.
Clustering için de k-means kullanırsın sonrasında.

[Rerore]

2ye bölerek ilerle

[Larva]

Sunu okursan belki yardimi dokunur.
http://people.csail.mit.edu/indyk/6.838-old/handouts/lec17.pdf

Bir kac sene once 3 boyut icin divide and conquer kullanarak yazdigimi hatirliyorum. 8 Boyut icin gorsellestirmen pek mumkun degil matematik kismini kapman gerekiyor. 2 boyutlu cozumle ayni mantikla yaklasiyorsun. aradaki bounded ve sparse bolgeyi olusturup, o bolge icin ayni cozumu 7 dimensionda uyguluyorsun, recursive olarak boyut duse duse 2 boyuta iniyorsun sonra da 2 boyutlu cozumu uyguluyorsun

O(Nlog^7 N) olmasi gerek ama essek gibi bir constant gelicek sanirim.

[xetraynex]

mesaj kutunu bosaltabilirmisin barbu dolmus da :)

bu arada atacagim mesajin bu konu ile alakasi yok, bunun icin mi bosalttirdin mesaj kutumu deme sonra onceden soyliyim :)

[Alfheim]

barbu said:

bildiğin 8 boyut. 8 tane attribute var.
1. nokta:a1,b1,c1,d1,e1,f1...
2. nokta:a2,b2,c2,d2....
54bin tane de noktam.

brute force olmaz o yüzden. en iyi closest pair nlogn ile bulunuyor. ama işte 8 tane attribute işin içine girince beynim durdu. dışarıdan birisi görür belki diye koydum.

çok farkı olmaması lazım 2 noktayla. ama işte yapamadım.

bunu da clustering için kullanıcam. agnes clusteringi yapıcam. data mining filan. belki bilen çıkar.

clustering için de simple k-means'i, cosine similarity veya manhattan similarity distance metricleriyle kullanabilirsin.

(1-similarity) tabi distance hesaplandığı için

[barbu]

xetraynex said:

mesaj kutunu bosaltabilirmisin barbu dolmus da :)

bu arada atacagim mesajin bu konu ile alakasi yok, bunun icin mi bosalttirdin mesaj kutumu deme sonra onceden soyliyim :)

bosaltirim simdi.

bu arada clustering olarak agnes kullanmam lazım. projem o çünkü.