Tez No	İndirme	Tez Künye	Durumu
517317		Distributed bipartite graph clustering / İki parçalı çizge demetleme Yazar:RESUL TUGAY Danışman: PROF. DR. ŞULE GÜNDÜZ ÖĞÜDÜCÜ Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Bilim ve Teknoloji = Science and Technology Dizin:	Onaylandı Yüksek Lisans İngilizce 2018 75 s.
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.
Bipartite graphs are graphs whose vertices can be divided into two independent sets (X and Y) such that no two graph vertices within the same set are adjacent. There are many real-world examples which display natural bipartite structure. For instance, a bipartite graph where the distinct set of vertices are people and books and edges represent buying relationship between them. Another prominent example is a bipartite graph where the vertex sets are candidates and jobs and if a candidate applies to job, there is an edge between the corresponding vertices. In this thesis, we implement a distributed bipartite clustering method for large and sparse data. There are several approaches to cluster data which is bipartite in nature. For example k-means clustering method can be applied to the both sides of the graph separately. But bipartite clustering requires a clustering method that clusters data simultaneously. Spectral clustering is a way to cluster bipartite data simultaneously which means assigning vertices from both sides into the same coherent cluster. We use multi bipartitioning clustering algorithm which is based on spectral clustering in this thesis along with some other bipartite partitioning algorithms such as Bifennel, Aweto and etc. There are some steps that need to be done before bipartite graph is clustered. Firstly, bipartite graph is converted into adjacency matrix where rows represent one set of vertices of bipartite graph and columns represent the other set of vertices. If there is an edge between two vertices, then the value of the corresponding cell of the adjacency matrix is assigned to 1, otherwise it is assigned to 0. After having the adjacency matrix, the Laplace form of the adjacency matrix is created. This matrix is also known as degree matrix. Degree matrices namely D1 and D2 are constructed for X and Y respectively. Then adjacency matrix is multiplied with D1 and D2. Lastly, the spectral algorithm runs Singular Value Decomposition (SVD) on the formed adjacency matrix and finds second singular left and right vectors. After finding second singular right and left vectors, k-means clustering algorithm is run on these vectors to cluster data. This method only partitions the data into two cluster. But finding other singular vectors (2.,3.,...) other than only the second one, more clusters can be obtained. In this thesis, we used distributed SVD algorithm to find singular left and right vectors of adjacency matrix when the matrix is large and sparse. Distributed SVD algorithm divides the matrix into column-wise sub matrices and calculates SVD on these sub matrices independently. It is capable of finding the singular values, left and right vectors when the matrix is rectangular (number of rows are much more smaller than number of columns or vice versa) and dense. In other words, the rank of the sub matrices must be equal to the rank of the adjacency matrix itself. Because of the sparsity of the data, the rank that is less in sub matrices than the adjacency matrix xxi causes to find singular values and vectors with high error. We proposed an algorithm, called Ranky, to handle this problem. Ranky algorithm detects the rows which cause the rank of the sub matrices less then the rank of the adjacency matrix and fills accordingly in order to make them equal. Despite the Ranky algorithm can handle this problem, balanced clusters can not be obtained because of the sparse matrix. After that, we used partitioning algorithms to compress the adjacency matrix into dense matrix and then applied spectral clustering. There are several partitioning algorithms such as Hash, Grid, Aweto, Bifennel etc. But only Aweto and Bifennel take the advantage of bipartite graphs as we know. We use Bifennel partitioning algorithm and Distributed Bifennel algorithm to compress the data due to their efficiency and less replication factor. Lastly, we decompress the partitions to get final clusters. The evaluation criteria is the replication factor that measures partitioning algorithm performance in terms of the number of replicated vertices. The experimental results on a real world data set show that Distributed Bifennel algorithm has outperformed Bifennel algorithm in terms of execution time, while both algorithms produce equally likely replication factor, using different datasets. Each algorithm is run on the same datasets with different partitioning numbers (500 and 1000). Distributed Bifennel algorithm has partitioned the data 10 times faster than Bifennel using at most 28 threads. The algorithm was implemented in C++ and run on a 28 cores and 128 GB RAM machine running Linux. More experimental results with different settings are given in chapter 5.