Tez No	İndirme	Tez Künye	Durumu
338355		Improving scalability and efficiency of ILP-based and graph-based concept discovery systems / Tümevaran mantık programlama tabanlı ve çizge tabanlı kavram keşif sistemlerinin ölçeklendirilebilirlik ve veriminin artırılması Yazar:ALEV MUTLU Danışman: DOÇ. DR. PINAR KARAGÖZ Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Grafikler = Graphics ; Tümevarımsal öğrenme = Inductive learning ; Veri madenciliği = Data mining ; Verimlilik = Productivity	Onaylandı Doktora İngilizce 2013 114 s.
Kavram keşfi, bir ilişki tanımının arkaplan ilişlileri olarak adlındırılan diğeri bazı ilişkiler cinsinden bulunması problemidir. Kavram keşif probleminde Tümevaran Mantık Programlama (TMP) ve çizge tabanlı yöntemler yoğun olarak kullanılmaktadır.TMP tabanlı yaklaşımlar bu problemde uzun süredir hakim bir şekilde kullanılıyor olsa da, bu tür sistemlerin bazı problemlerini çözdüğü için çizge tabanlı yaklaşılar da son zamanlarda bu alanda popülarite kazanmıştır.Birçok alanda uygulaması bulunmakla birlikte, TMP tabanlı sistemlerde verimililik ve ölçeklendirilebilirlik sorunları mevcuttur. Bu sorunlar genellikle TMP tabanlı sistemlerin oluşturduğu büyük arama alanlarından kaynaklanmaktadır. Bu çalışmada, tablolama ve paralleleştirme yöntemleri kullanılarak TMP tabanlı kavram keşif sistemlerinin arama alanı oluşturma ve değerlendirme aşamalarının iyileştirilmesi için yöntemler sunulmaktadır.Bu çalışmada tablolama yöntemlerini kullanan üç yöntem sunulmuştur, Tabular CRIS, Tabular CRIS-wEF ve Selective Tabular CRIS. Bu metotlarda, temel olarak, arama alanı değerlendirme sorguları daha sonra kullanılmak üzere tablolanmaktadır. Her üç metot bazı ortak temel fonksiyonları barındırmakla birlikte, ardıl gelen öncekinin ölçeklendirilebilirliğini iyileştirmek için bazı yeni yaklaşımlar sunmaktadır.Önerilen paralel yöntem, pCRIS, TMP tabanlı sistemlerin arama alanı oluşturma ve değerlendirme aşamalarını veri-paralel yöntemler kullanılarak paralelleştirmektedir. Önerilen yöntem fazladan yapılan işi ve senkronizayon anlarında işlemcilerin bekleme süresini asgari düzeyde tutacak şekilde tasarlanmıştır.Çizge tabanlı sistemler öncelikle TMP tabanlı sistemlerin problemlerinden biri olan yerel plato problemini gidermek için sunulmuştur. Veriyi etkin bir şekilde ifade edebildiği ve TMP tabanlı sistemlerin bazı problemerini ortadan kaldırdıgı için yakın zamanlarda, kavram keşfi probleminde, çizge tabanlı sistemler artan bir popülarite kazanmaktadır. Genel olarak bu tür sistemler ortak bileşen bulma ve yol bulma sistemleri olarak gruplandırılabilir. İlk kümeye düşen yöntemler ortak bileşenleri bulmak pahalı algoritmalar kullanmaktadır. İkinci kümeye düşen yaklaşımlar ise çizge içideki yolları tumak için komplike indeksleme yöntemlerine ihityaç duymaktadır. Bu çalışmada çizge tabanlı kavram keşif sistemleri için pahalı bileşen bulma algoritmalarına ve komplike indeksleme mekanizmalarına ihtiyaç duymayan melez bir yöntem sunulmaktadır. Önerilen yöntemde bezer yapılar gruplanmakta ve kavram tanımlarını oluşturan yollar çizge inşaa edilirken oluşturulmaktadır.
Concept discovery is the problem of finding definitions of target relation in terms or other relation given as a background knowledge. Inductive Logic Programming (ILP)-based and graph-based approaches are two competitors in concept discovery problem. Although ILP-based systems have long dominated the area, graph-based systems have recently gained popularity as they overcome certain shortcomings of ILP-based systems.While having applications in numerous domains, ILP-based concept discovery systems still sustain scalability and efficiency issues. These issues generally arose due to the large search spaces such systems build. In this work we propose memoization-based and parallelization-based methods that modify the search space construction step and the evaluation step of ILP-based concept discovery systems to overcome these problem.In this work we propose three memoization-based methods, called Tabular CRIS, Tabular CRIS-wEF, and Selective Tabular CRIS. In these methods, basically, evaluation queries are stored in look-up tables for later uses. While preserving some core functions in common, each proposed method improves efficiency and scalability of its predecessor by introducing constraints on what kind of evaluation queries to store in look-up tables and for how long.The proposed parallelization method, called pCRIS, parallelizes the search space construction and evaluation steps of ILP-based concept discovery systems in a data-parallel manner. The proposed method introduces policies to minimize the redundant work and waiting time among the workers at synchronization points.Graph-based approaches were first introduced to the concept discovery domain to handle the so called local plateau problem. Graph-based approaches have recently gained more popularity in concept discovery system as they provide convenient environment to represent relational data and are able to overcome certain shortcomings of ILP-based concept discovery systems. Graph-based approaches can be classified as structure-based approaches and path-finding approaches. The first class of approaches need to employ expensive algorithms such as graph isomorphism to find frequently appearing substructures. The methods that fall into the second class need to employ sophisticated indexing mechanisms to find out the frequently appearing paths that connect some nodes in interest. In this work, we also propose a hybrid method for graph-based concept discovery which does not require costly substructure matching algorithms and path indexing mechanism. The proposed method builds the graph in such a way that similar facts are grouped together and paths that eventually turn to be concept descriptors are build while the graph is constructed.