Frequent subgraph mining over dynamic graphs
Değişken veri üzerinde sık alt çizge madenciliği
- Tez No: 631054
- Danışmanlar: Assoc. Prof. Dr. BELGİN ERGENÇ BOSTANOĞLU
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: İzmir Yüksek Teknoloji Enstitüsü
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 106
Özet
Sık alt çizgeler madenciliği bir çok veri madenciliği uygulaması için temel ve zorlu bir iştir. Modern uygulamalar devingen çizgelerle çalışmakta olup girdilerindeki veri akışı sık alt çizge madenciliği algoritmalarının karmaşıklığını arttırmaktadır. Yaklaşık sonuçların yeterli olduğu durumlarda örneklemeye dayalı yaklaşımlar kullanılmaktadır. Bu tez kapsamında üç adet yaklaşık sık alt çizge madenciliği algoritması önerilmektedir. Önerilen algoritmalarda yenilikçi olarak kontrollü depolama ile örneklem oluşturma yaklaşımı kullanılmıştır Devingen çizgeye ilişkin örneklem sabit boyutlu depoda tutulmakta ve yardımcı bir yığın veri yapısı kullanılmaktadır. Bu yığın veri yapısında depodaki çizge düğümlerinin bağlantı dereceleri tutulmaktadır. Sabit boyutlu depo dolduğunda ve yeni alan gereksinimi ortaya çıktığında bu depodan çizgenin en düşük dereceli düğümleri çıkarılmaktadır. Devingen çizge örneklemini tutan sabit depoda yüksek dereceli düğümlerin kalması sağlanarak sonuçlardaki doğruluk yer ve zaman maliyetini artmadan yükseltilebilmektedir. İlk olarak limitsiz boyutlu kontrollü depo örneklemesine dayalı“Controlled Reservoir Sampling with Unlimited heap size (UCRS)”algoritması önerilmiştir; adından da anlaşılacağı üzere kullanılan yardımcı yığının boyutu kısıtlanmamıştır. İkinci algoritma“Controlled Reservoir Sampling with Limited heap size (LCRS)”da büyüyen depo ile büyüyen yığının boyutuna sınır getirilmektedir. Üçüncü algoritma“Maximum Controlled Reservoir Sampling (MCRS)”ilk algoritmaya benzemektedir; yığın boyutu sınırlandırılmamıştır ancak en depodan düğüm silmek gerektiğinde en düşük dereceli düğüm yerine en yüksek dereceli düğüm . çıkarılmaktadır. Her üç algoritmanın başarım değerlendirmeleri zaman, ölçeklenebilirlik ve doğruluk ölçütleri ile yapılmıştır. Başarım değerlendirmelerinde önerilen algoritmalar iki güncel rakip algoritma ile yoğun ve seyrek veri setleri üzerinde karşılaştırılmıştır. Bulgular UCRS ve LCRS algorithmalarının ölçeklenebilir olduğunu rakip kenar tabanlı algoritmadan daha doğru sonuçlar verdiğini göstermiştir. LCRS seyrek veri setlerinde tüm rakip algoritmalardan daha iyi başarım elde etmiştir. MCRS algoritmasının sonuçları tüm algoritmalar arasında en kötüdür.
Özet (Çeviri)
Frequent subgraph mining (FSM) is an essential and challenging graph mining task used in several applications. Modern applications employ evolving graphs, so FSM is more challenging with evolving graphs due to the streaming nature of the input, and the exponential time complexity of the algorithms. Sampling schemes are used if approximate results serve the purpose. This thesis introduces three approximate frequent subgraph mining algorithms in evolving graphs. those algorithms use novel controlled reservoir sampling. Sample of the evolving graph and an auxiliary heap data structure is kept in a fixed sized reservoir. When the reservoir is full, and space is required the edges of lower degree or higher nodes are deleted. This selection is done by utilizing the heap data structure in the reservoir, which keeps the node degrees. By keeping the edges of higher degree nodes in the reservoir, accuracy is maximized without sacrificing time and space, in contrast, keeping the edges of higher degree nodes in the reservoir, accuracy is minimized with higher time and space. First algorithm is Controlled Reservoir Sampling with Unlimited heap size (UCRS), where the used heap size is unlimited. Second algorithm is Controlled Reservoir Sampling with Limited heap size (LCRS). It is a modified version of UCRS, but the heap size is limited, as a result; sample size in the reservoir increases since the total number of nodes dedicated for the reservoir includes the nodes of the heap also. Third algorithm is Maximum Controlled Reservoir Sampling (MCRS). It is a modified version of UCRS, but the candidate edge for deletion is an edge with maximum node degrees. Experimental evaluations to measure scalability and recall performances of the three algorithms in comparison to state of art algorithms are performed on dense and sparse evolving graphs. Findings show that UCRS and LCRS algorithms are scalable and achieve better recall than edge based reservoir algorithms. LCRS achieves the best recall on sparse datasets in comparison to edge or subgraph based reservoir algorithms. MCRS has the worst speed-up and recall among the other proposed and competitor algorithms.
Benzer Tezler
- Sık alt çizge madenciliği algoritmalarının kullanım alanları ve uygulanabilirliği
Application areas and usage of frequent subgraph mining algorithms
MEHMET SERDAR GÜR
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAydın Adnan Menderes ÜniversitesiYönetim Bilişim Sistemleri Ana Bilim Dalı
PROF. DR. MUSTAFA ÇETİN
- A distributed graph mining framework based on mapreduce
Eşle/indirge yöntemi üzerine kurulu dağıtık bir ağ madenciliği gerçeklemesi
SERTAN ALKAN
Yüksek Lisans
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Bölümü
YRD. DOÇ. DR. TOLGA CAN
- Development of space and time efficiency improvement methods and appling onto frequent subgraph mining algorithms
Sık alt çizge madenciliği algoritmalarına uygulanabilir alan ve zaman verimliliği arttıran metotların geliştirilmesi
MURAT OĞUZ
Doktora
Türkçe
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMaltepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. TURGAY TUGAY BİLGİN
- Çizge madenciliği ve algoritmaları
Graph mining and algorithms
SEMA BODUR
Yüksek Lisans
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. VECDİ AYTAÇ
- Information extraction from news related texts using graph mining techniques
Çizge madenciliği tekniklerini kullanarak haber ile ilgili metinlerden bilgi çıkarımı
RECEP FIRAT ÇEKİNEL
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. PINAR KARAGÖZ