Gömülü teknikler kullanılarak çizge medyanının hesaplanması
Finding graph medians using graph embedding techniques
- Tez No: 316536
- Danışmanlar: YRD. DOÇ. DR. MUHAMMED FATİH DEMİRCİ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2012
- Dil: Türkçe
- Üniversite: TOBB Ekonomi ve Teknoloji Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 75
Özet
Graph (Çizge) Teorisinin birçok uygulaması görüntü işleme, bilgisayarla görü, biyoinformatik, veri madenciliği ve yapay zeka çalışmalarında sıklıkla kullanılmaktadır. Objelerin çizge gösterimiyle gösterilmesi ve resim eşleştirilmesi ise nesne tanıma çalışmalarında önemli bir yer kaplamaktadır. Birçok örnek resim verilerinde gürültü miktarı doğal koşullar neticesinde fazlaca bulunmaktadır ve elde edilen sonuçlarda da hata miktarı fazla çıkmaktadır. Her bir resmin çizge gösterimiyle gösterilmesi sonucu eşleştirme problemi özünde çizge karşılaştırma problemiyle eşdeğer bir hal almaktadır. Veri miktarının fazla olması ve çizge karşılaştırma işleminin maliyetli olması sebebiyle yakınsama algoritmaları (approximation algorithms) kullanılarak, yapılan işlemin maliyetini azaltma çalışmaları yapılmaktadır. Verilen çizgeleri karşılaştırmak için her grup çizge için, o grubu temsil eden yeni bir çizge hesaplanarak, aranan çizgeyi temsilci çizge ile karşılaştırmanın daha hızlı ve tolere edilebilecek seviyede gerçeğe yakın sonuçlar vereceği öngörülmüştür. Daha önce yapılan çalışmalarda, temel olarak, iki çizgenin karşılaştırılması için çizge uzayındaki her bir çizgeyi, temsil eden vektör uzayına dönüştürme ve daha az maliyetle vektör uzayında işlemler yapma üzerinde durulmuştur. Yapılan çalışmada, her veri sınıfı için veri kümemiz içindeki tüm çizgeler, veri kaybını minimum düzeyde tutacak şekilde, geometrik uzaya izomorfik olarak l_1 norm (Manhattan Uzaklık Metriği) altında dönüştürülmüştür. Bu sayede temsilci çizge bulunması esnasında yapılacak işlemlerin masrafları azaltılmış ve kullanmış olduğumuz Tırtıl Ayrışması (Caterpillar Decomposition) tekniğiyle minimum seviyede veri kaybı olması sağlanmıştır. Daha önce yapılan çalışmalardan farklı olarak, elde edilen geometrik uzayda her bir nokta, çizge üzerindeki bir düğüme (node) denk gelmektedir ve bu sayede veri kaybı azalmaktadır. Temsilci çizgenin belirlenmesi için, oluşturulan vektör uzayında, K-Means Algoritması kullanılmaktadır. Elde edilen temsilci nokta kümesi ile çizgeleri karşılaştırmak için Hausdorff Mesafesi algoritmasının 25 farklı hesaplama metriği kullanılmaktadır. Bu işleyiş yapısı içerisinde minimum seviyede hatayla daha hızlı sonuçlar elde etmek mümkün olmaktadır.
Özet (Çeviri)
Graph theory applications are frequently used in image processing, computer vision, bioinformatics, data mining and artificial intelligence related works. On the other hand, representing objects with graphs and matching the images are important part of object recognitions applications. In most of sample image data, images have a lot of noise caused by natural conditions and the error levels in the final results are high. When each image is represented by a graph, matching problem inherently turns to be the same as graph comparison. Since the amount of data is huge and the graph comparison is costly, approximation algorithms are used to decrease the total cost. To compare the given graphs, for each group of graphs, a representative is selected. It is anticipated that, comparing the graph only with the representative graphs gives faster results and the results are tolerably close to the exact truth. In the previous works, to compare the graphs, mapping of each graph in the graph space into a vector in the vector space and then working on the vector space with minimum cost is used. In this work, for each data class we have, each graph in the set is mapped to geometric space by using isomorphic l_1 norm (Manhattan Distance metric), so that, the data lose is minimum. Consequently, the cost of finding the representative graph is decreased and the data lose is kept at the minimum by using Caterpillar Decomposition technique. Differently from the previous works, each point in the geometric space represents a node in the graph. Thus, the data lose is lowered. In the vector space, K-Means Algorithm is used to find the representative graph. To compare the representative points set with the graphs, 25 different distance metric calculations of Hausdorff Distance Algorithm is used. This working mechanism makes it possible to have faster results with minimum error level.
Benzer Tezler
- Trust-aware location recommendation in location-based social networks
Konum temelli sosyal ağlarda güven farkında konum önerisi
DENİZ CANTÜRK
Doktora
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. PINAR KARAGÖZ
- Hybrid evolutionary algorithms for solving the register allocation problem
Yazmaç özgüleme problemi için evrimsel karma algoritmalar
BETÜL DEMİRÖZ
Yüksek Lisans
İngilizce
2004
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ.DR. HALUK TOPÇUOĞLU
- Graph embeddings on protein interaction networks
Protein etkileşim ağlarında çizge gömülümleri
HALİL İBRAHİM KURU
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ABDULLAH ERCÜMENT ÇİÇEK
YRD. DOÇ. DR. ÖZNUR TAŞTAN OKAN
- New lightweight DoS attack mitigation techniques for RPL based IoT networks
RPL temelli IoT ağları için DoS saldırılarının etkisini azaltacak yeni teknikler
AHMET ARIŞ
Doktora
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SEMA FATMA OKTUĞ
- Design and analysis of interior permanent magnet machines equipped with novel semi-overlapping windings for electric vehicle applications
Elektrikli araç uygulamaları için yeni yarı kesişen sargılarla donanımlı gömülü kalıcı mıknatıslı makinaların tasarımı ve analizi
TAYFUN GÜNDOĞDU
Doktora
İngilizce
2021
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. GÜVEN KÖMÜRGÖZ KIRIŞ