|
Çizge veri kümelerinin kullanımının artmasıyla, çizgelerde veri ve örüntü madenciliği alanına araştırmacıların ilgisi artmaktadır. Özellikle de, çizgelerde sıklıkla tekrarlayan örüntülerin bulunması uygulama alanlarının genişliği ve çeşitliliği sebebiyle oldukça ilgi toplamaktadır. Bu tez çalışmasında, söz konusu alanda yapılmış çalışmalar incelenmiş ve eksikliklerinden bahsedilmiştir. Bu eksikliklerin bir kısmını giderecek ve daha başarılı sonuçlar elde edilmesine olanak sağlayacak çizge veri kümelerinde kullanıcı destekli örüntü madenciliği için yeni bir yaklaşım önerilmiştir.Önerilen yaklaşımın temeli çizge veri yapıları ile ifade edilen veri kümelerinin özellik uzayına aktarılmasına dayanmaktadır. Bu sayede benzer örüntüleri bulmak amacıyla veri kümesi üzerinde çeşitli veri madenciliği yöntemlerinin uygulanmasına olanak sağlanmaktadır. Ayrıca önerilen yaklaşım, otomatik parametre seçimindeki dezavantajları görsel destekli veri madenciliği yöntemlerinin avantajlarını kullanarak azaltmaktadır. Ara adımlarda elde edilen bilgileri grafikler ve istatistiksel bilgiler olarak uzmanlara sunmaktadır. Böylece uzmanların veri kümesi ve ara adımlardaki sonuçlar hakkında bilgi sahibi olması sağlanmakta, gerekli yerlerde parametre seçiminde veya otomatik hesaplanan parametrelerde ince ayar yapılmasına olanak tanınmaktadır.Önerilen yaklaşım ile çizge veri kümelerinin, üç boyutlu özellik uzayına izdüşümü alınır. Bir çizgedeki her bir kenar ve kenarın iki ucundaki düğümler özellik uzayında bir nokta olarak gösterilir. Aynı sınıfa ait tüm çizgeler noktalar seklinde özellik uzayına dönüştürüldüğünde, benzer özellikte tekrar eden yapılar nokta küme gruplarını oluşturur. Tekrarlayan örüntüler, kümeleme yöntemleri ile çıkarılır. Çok geniş veri kümeleri ile çalışıldığında tüm çizgelerin aynı özellik uzayına aktarılması nokta kümelerinin elde edilmesini zorlaştırmaktadır. Özellik uzayındaki tekrar eden alt çizgeleri ortaya çıkarmak için örüntüler haricindeki diğer kenarlar histogram tabanlı görsel veri madenciliği yöntemleri ile filtrelenir. Tüm bu işlemler boyunca uzmanlar gerekli gördüğü yerlerde (ör: filtreleme, kümeleme) grafikleri inceleyerek gerektiğinde parametre değerlerinde ince ayar yapabilirler.Bu tez çalışmasında önerilen yaklaşım, gerçek bir veri kümesinde ve sentetik veri kümelerinde ayrıntılı olarak test edilmiştir. Her veri kümesinde iki sınıf vardır, her sınıf az miktarda gürültü ile birlikte aynı özellikteki örüntülere sahip çizgeleri içermektedir. Detaylı testlerden elde edilen sonuçlara göre, gürültüsüz veri kümelerinde önerilen yöntemin, örüntüleri %100 başarılı olarak bulduğu görülmüştür. Gürültülü veri kümelerinde ise ortalama başarı %95 olarak gerçekleşmiştir. Literatürdeki diğer yöntemler gürültüsüz ortamda başarılı bir şekilde örüntüleri bulurken, gürültülü veri kümelerinde örüntüleri çoğunlukla bulamamışlardır.
|
|
With the increasing use of graph datasets, pattern and data mining in graphs are attracting more attention of the researchers. Especially, finding frequently repeating patters in graphs is increasingly drawing more attention, because of its wide and versatile application areas. In this dissertation, previous studies on frequent pattern mining in graphs are analyzed and their deficiencies are discussed. To overcome some of these deficiencies and to allow more successful results in graph data sets, a user-assisted pattern mining method is proposed.The proposed approach is based on the transformation of graph data structures into a feature space. In this way, various data mining methods can be applied to the data to find similar patterns. Proposed approach eliminates the disadvantages of the automatic parameter selection methods using the advantages of visual data mining methods. The information obtained through intermediary steps is represented to the experts as graphs and statistical data. Hence, the experts are informed about the dataset and steps of the process; moreover, the selection or fine-tuning of computed parameters by the experts are permitted.With the proposed approach, graph representations of structural data are projected into a 3D feature space. Each graph piece, which is a triple composed of an edge and two nodes at each end, is represented as a point in the feature space. Once we represent each graph in the dataset as a set of points in the feature space, using a clustering algorithm, we determine clusters of points that have similar characteristics. However, discovering the clusters is non-trivial because of the noisy points that represent infrequent bonds. At this stage, noise is filtered using a histogram-based visual data mining method, so that the clusters can be discovered more clearly by various clustering algorithms. Once the clusters are discovered, frequent sub-structures are computed. During all these steps, a domain expert can intervene to guide the system or fine-tune the parameters if necessary (e.g., during filtering, clustering and so on).The approach proposed in the dissertation is tested in detail with a real-life dataset and various synthetic datasets. Datasets may include samples belonging to two classes, where each class contains graphs with some common patterns and properties with some noise. According to detailed analysis of our test results, the proposed approach can find frequent patterns with 100% success when noise is not included to the datasets. The average success in the noisy datasets is 95%. While other methods in the literature find the patterns successfully only when noise is not included to the datasets, they couldn?t successfully find patterns in the noisy data sets. |
