İki parçalı çizge demetleme

Bu tez kapsamında iki parçalı büyük veriler için sunucu-istemci mimarisi kullanılarak çizge demetleme yapılmı¸stır. ˙ Iki parçalı çizgede iki farklı dügümler kümesi ( ˘ X ve Y) vardır. Aynı kümedeki dügümler arasında ayrıt bulunmazken, farklı kümelerdeki ˘ dügümler arasındaki ili¸skileri ifade etmek üzere ayrıtlar vardır. Örne ˘ gin satın alınan ˘ kitap, film, müzik ya da ba¸svurulan i¸s ilanları iki parçalı çizgenin bir dügümler ˘ kümesini olu¸stururken bunları satın alan veya ba¸svuru yapan ki¸siler çizgenin diger ˘ dügümler kümesini olu¸sturur. Günümüzde artan ˘ ˙ Internet kullanımı ile ˙ Internet ortamındaki veriler de bir hayli artmı¸stır. Bu verileri degi¸sik amaçlar için tek bir ˘ makinede i¸slemek zor bir hal almı¸stır. Bu tez çalı¸smasındaki amaç da iki parçalı çizge demetleme problemini paralel yakla¸sımlarla çözmektir. ˙ Iki parçalı çizge demetleme aralarında diger gruplara göre daha yo ˘ gun ili¸skiler bulunan ˘ farklı kümelerdeki dügümleri gruplamaktır. Böylece örne ˘ gin benzer türde müzikleri ˘ tercih eden kullanıcı grubunu bulmak ya da benzer i¸s ilanlarına ba¸svuran adayları bulmak mümkün olabilmektedir. Dügümler kümesi çok büyüdü ˘ günde literatürde var ˘ olan yöntemlerle iki parçalı çizge demetleme problemini standart donanımlar üzerinde çözmek mümkün olmamaktadır. Bu tez ile büyük veride iki parçalı çizge demetleme problemini çözmek için sunucu-istemci mimarisi ile paralel çalı¸san yakla¸sımlar önerilmi¸s ve büyük iki parçalı çizge demetleme yapabilen bir yazılım geli¸stirilmi¸stir. Öncelikle iki parçalı verinin bölütlenmesi için literatürde spektral demetleme adı verilen bir algoritmadan yararlanılmı¸stır. Algoritmanın birkaç varyasyonu olmakla birlikte, bu tezde simetrik olmayan kom¸suluk matrisi üzerinde Tekil Deger ˘ Ayrı¸stırması (SVD) uygulanarak bulunan demetlemeden yararlanılmı¸stır. Diger ˘ varyasyonlar kom¸suluk matrisinin simetrik oldugu durumlarda çalı¸sabildi ˘ ginden ve ˘ elimizdeki kom¸suluk matrisinin dikdörtgen olmasından dolayı bu tez kapsamında diger ˘ varyasyonlar kullanılmamı¸stır. Algoritma temel olarak iki parçalı veriyi satırları bir küme sütünları ise diger küme ve de ˘ gerleri aralarındaki ili¸ski olan kom¸suluk matrisi ˘ olarak tanımlar. Kom¸suluk matrisinin degerleri basit olarak e ˘ ger bir kümedeki bir ˘ elemanın diger kümedeki di ˘ ger elemanla ili¸skisi varsa "1" yoksa "0" olarak belirlenir. ˘ ˙ Iki parçalı çizgeden A kom¸suluk matrisi olu¸sturulduktan sonra, algoritma a¸sagıdaki ˘ gibi devam eder. 1. A kom¸suluk matrisinden a¸sagıdaki gibi ˘ K matrisi elde edilir: K = D− 1 1=2AD− 2 1=2 2. K matrisinin ikinci sag ( ˘ u2) ve sol (v2) tekil degerlerini hesaplanır ve a¸sa ˘ gıdaki Z ˘ matrisi formuna getirilir: Z = D− 1 1=2u2 D−1=2 1 v2 3. Z matrisi üzerinde k-ortalama demetleme algoritması ko¸sularak demetler bulunur. xxiii Burada bahsedilen D1 ve D2 matrisleri iki parçalı çizgenin sırasıyla ilk ve ikinci kümelerinin derece matrisleridir. Eger algoritma birden fazla boyutta demetlenmek ˘ istenirse, 2. adımda bulunan sag ve sol tekil vektörler sadece ikinci vektörler de ˘ gil, ˘ sırasıyla 3., 4., .. sag ve sol tekil vektörlerden olu¸smalıdır. Bu ¸sekilde ˘ Z matrisi tek boyutlu degil birden fazla boyutlu olur ve k-ortalama demetleme algoritması bu çok ˘ boyutlu matris üzerinde ko¸sturularak demetleme yapılır. Bazı veri kümeleri için iki parçalı çizgede X'in eleman sayısı Y'nin eleman sayısından bir hayli fazladır, bu da elde edilen A kom¸suluk matrisinin dikdörtgen yapıda olmasına sebep olur. Literatürde bu tip dikdörtgen matrisler üzerinde çalı¸sabilen dagıtık SVD ˘ algoritması önerilmi¸stir. Algoritma sunucu-istemci modeli ile çalı¸smaktadır. Verilen matriste satır sayısının kolon sayısından oldukça az oldugu dü¸sünülürse, sunucu ˘ A kom¸suluk matrisini kolon-temelli bölerek herbiri aynı sayıda satıra sahip olan küçük matrisleri (A1;A2;::) istemci makinalara gönderir. ˙ Istemci makinalar bagımsız olarak ˘ SVD algoritmasını bu küçük matrisler üzerinde ko¸sar ve elde ettigi tekil de ˘ gerleri, sol ˘ ve sag vektörleri sunucu makineye geri gönderir. Sunucu, istemcilerin elde ettikleri ˘ tekil degerleri ve tekil vektörleri toplayarak birle¸stirir ve ˘ A matrisinin tekil deger ve ˘ vektörlerini bulur. Daha sonra spektral algoritma k-ortalama demetleme algoritmasıyla birlikte veriyi bölütler. Fakat bu algoritma sadece yogun karesel matrisler üzerinde ˘ dogru sonuçlar vermektedir. Çünkü bölünen matrisler ile ˘ A matrisinin kertelerinin (rank) e¸sit olması gerekmektedir, Fakat elde ettigimiz iki parçalı çizge bir hayli ˘ seyrektir ve matris bölünürken küçük matrislerin kerteleri kom¸suluk matrisinin A kertelerinden dü¸sük olabilmektedir. Bu tez çalı¸smasında yukarıda bahsedilen problemi çözmeye yönelik yöntemler önerilmi¸stir. Önerilen Ranky isimli algoritma 3 farklı yakla¸sımdan olu¸smaktadır. Öncelikle A kom¸suluk matrisi bölünürken küçük matrislerde (A1;A2;::) kertenin daha dü¸sük olmasına sebebiyet veren satırlar bulunur ve bu satırların kolonlarından birisine rastgele "1" eklenerek bu satırın dü¸sük kerteye sebep olması önlenir. Bu i¸slemde satırların bulunmasının nedeni kom¸suluk matrisinin kertesini belirleyen, sayısı kolonların sayısından çok çok az olan satır sayısıdır. ˙ Ikinci olarak iki parçalı çizge demetleme yaptıgımız için, rastgele "1" ya da ˘ X'teki elemanlar ile Y'de elemanlar arasına rastgele ili¸ski eklemek yerine, bu satırların diger küçük matrislerdeki kom¸suları ˘ (diger satırlar) bulunur ve bu kom¸suların ili¸skisi bulunan kolonlardan rastgele bir kolon ˘ seçilir. Fakat elimizdeki veride kertenin dü¸sük olmasına sebep veren birden fazla satır olabilir, ve bu satırların kom¸suları benzer olabilir, bu ¸sekilde rastgele atanan "1" ya da ili¸ski aynı kolona denk gelebilir ki yaptıgımız deneylerde bu sonuçlarla kar¸sıla¸stık. ˘ Bu yüzden 3. yöntem olarak öncelikle 2. yöntem olan kom¸suluk yöntemini uygulayıp daha sonra ilk yöntem olan rastgelelik yöntemini uygulayarak bu problemi çözüyoruz. Önerilen bu yöntem kerte problemini çözüme kavu¸sturmu¸stur, fakat elde ettigimiz ˘ demetleme sonuçlarında veri büyük ve seyrek oldugundan tutarsızlık gözlemlenmi¸stir. ˘ Bundan dolayı veriyi seyrek halden daha yogun bir hale getirdikten sonra da ˘ gıtık ˘ SVD algoritması uygulanmı¸stır. Bu yöntem ile daha tutarlı iki parçalı demetler elde edilmi¸stir. Veri seyrek halden daha yogun bir hale bölütleme algoritmaları kullanılarak ˘ getirilmi¸stir. Basit olarak aynı dügümler kümesindeki benzer olan bazı dü ˘ gümler ˘ birle¸stirilerek tek bir dügüm olarak temsil edilmi¸stir. Daha yo ˘ gun hale getirilen bu ˘ veriye SVD algoritması uygulandıktan sonra birle¸sik olarak temsil edilen dügümler ˘ tekrardan ayrı¸stırılırak bölütleme tamamlanmaktadır. Örnegin elimizdeki iki parçalı ˘ çizgede örnegin ˘ X kümesinde 1.000.000 ve Y kümesinde 100.000 dügüm var ise, bu ˘ xxiv yöntemden sonra elimizdeki matriste toplam X kümesinden 10.000 Y kümesinde ise 1000 dügüm olabilmektedir. Bu sayılar parametre olarak de ˘ gi¸sebilmektedir. Birkaç ˘ dügüm tek bir dü ˘ güm ile gösterildikten sonra ˘ A kom¸suluk matrisi yeni baglantıları ˘ gösterecek ¸sekilde yeniden olu¸sturulur. Örnegin ˘ X kümesindeki i1, i2, i3 dügümlerinin ˘ sırasıyla Y kümesindeki a1, a2, a3 dügümleri ile ili¸skisi olsun. E ˘ ger algoritma bu ˘ üç dügümü ( ˘ i1, i2 ve i3) birle¸sik dügüm (yenidü ˘ güm1) olarak temsil etmi¸s ise yeni ˘ matriste bu yenidügüm1'in di ˘ ger üç ( ˘ a1, a2, a3) dügüm ile ba ˘ glantısı olacaktır. Bu ˘ ¸sekilde önceki matris seyrek olmaktan çıkıp daha yogun bir hale gelebilmektedir. ˘ Literatürde birçok çizge bölütleme algoritması olmakla birlikte biz bu tez kapsamında dügüm-bölmeli (vertex-cut) iki parçalı çizge bölütleme algoritmaları olan Hash,Grid, ˘ Bicut, Aweto ve Bifennel algoritmalarını kullandık. Bu algoritmaların ba¸sarımı tekrarlama faktörü (replication factor ) denilen ve toplam tekrarlanan dügümlerle ile toplam dü ˘ güm sayısının, toplam dü ˘ güm sayısına oranı ile ˘ hesaplanmaktadır. Hash tabanlı algoritma iki parçalı demetin en fazla dügüm içeren ˘ kümesindeki dügümlerin numaralarını belirlenen bir hash fonksiyonundan geçirerek ˘ bölütleme saglar. Örne ˘ gin ˘ X kümesinde 4 eleman (i1,i2,i3,i4) ve Y kümesinde 9 eleman (a1,a2,a3,...,a9) var ise, algoritma bu 9 elemanın numaralarını alır ve hash fonksiyonuna parametre olarak verir. Hash fonksiyonu bölütleme sayısına göre degi¸sebilmektedir. Varsayalım ki burada 3 tane bölüt olsun. Hash fonksiyonu ˘ H(x) = x%3 olur, fonksiyonda belirtilen x dügüm numarasıdır. Bu ¸sekilde ˘ i1,i4,i7 nolu dügümler bir bölüte 2,5,8 nolu dü ˘ gümler di ˘ ger bölüte ve son olarak ˘ i3,i6,i9 nolu dügümler ise di ˘ ger bölüte atanır. Daha sonra her küme sanki yeni bir dü ˘ gümmü¸s gibi ˘ davranılır ve kom¸suluk matrisi yeniden olu¸sturulur. Fakat görüldügü gibi bu yöntem ˘ hiçbir ¸sekilde dügümlerin kom¸suluk ili¸skilerini göz önünde bulundurmamaktadır. ˘ Hatta eger dü ˘ güm numaraları çok farklı ise bölütler de dengesiz olabilmektedir. ˘ Diger algoritmalar bu temel bölütleme algoritmasının göz önünde bulundurmadı ˘ gı ˘ kom¸suluk ili¸skilerini ve bölütlerin dengesini göz önünde bulundururak bölütleme yapar. Bu algoritmalar arasında Bifennel algoritmasının, önerildigi makalede en ˘ dü¸sük tekrarlama faktörüne sahip oldugu deneylerle ispat edilmi¸stir. Bu algoritma ˘ hem kom¸suluk ili¸skilerini göz önünde bulundurmu¸s hemde bölütlerdeki dengenin (dügüm sayısının) yakla¸sık e¸sit olmasını sa ˘ glamı¸stır. Bu tez kapsamında da Bifennel ˘ algoritması gerçeklenerek çift parçalı çizge demetleme sonuçları sunulmu¸stur.