Tez Arşivi

Tez aramanızı kolaylaştıracak arama motoru. Yazar, danışman, başlık ve özete göre tezleri arayabilirsiniz.


Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Anabilim Dalı

A new WAP-Tree based sequential pattern mining algorithm for faster pattern extraction

Hızlı örüntü çıkarımı için WAP-Ağacı tabanlı yeni bir dizisel örüntü madenciliği algoritması

Teze Git (tez.yok.gov.tr)

Bu tezin tam metni bu sitede bulunmamaktadır. Teze erişmek için tıklayın. Eğer tez bulunamazsa, YÖK Tez Merkezi tarama bölümünde 318840 tez numarasıyla arayabilirsiniz.

Özet:

Sequential pattern mining constitutes a basis for solution of problems in various domains like bio-informatics and web usage mining. Research on this field continues seeking faster algorithms. WAP-Tree based algorithms that emerged from web usage mining literature have shown a remarkable performance on single-item sequence databases. In this study, we investigated application of WAP-Tree based mining to multi-item sequential pattern mining and we designed an extension of WAP-Tree data structure for multi-item sequence databases, the MULTI-WAP-Tree. In addition, we propose a new mining strategy on WAP-Tree which involves a hybrid traversal strategy in possible sequences search space and a new early prunning idea called Sibling Principle on Pattern Tree. Two algorithms, FOF-PT and MULTI-FOF-PT, applying this strategy on WAP-Tree and MULTI-WAP-Tree respectively, are developed. Experiments showed that FOF-PT outperforms both other WAP-Tree based algorithms and PrefixSpan in terms of execution time. Moreover, experimental results revealed MULTI-FOF-PT finds patterns faster than PrefixSpan on dense multi-item sequence databases with small alphabets.

Summary:

Dizisel örüntü madenciliği, biyoenformatik ve web kullanım madenciliği gibi farklı alanlardaki problemlerin çözümünde temel teşkil etmektedir ve daha hızlı dizisel örüntü madenciliği algoritmalar arayışıyla bu alandaki araştırmalar devam etmektedir. Web kullanım madenciliği literatüründen çıkan WAP-Ağacı temelli algoritmalar, tekli dizi veritabanları üzerinde dikkat çekici bir performans göstermişlerdir. Bu tez kapsamında, WAP-Ağacı veri yapısının çoklu / genel dizi madenciliğine uygulanması araştırılmıştır ve WAP-Ağacı'nın çoklu dizi veritabanları için bir uyarlaması olan Çoklu-WAP-Ağacı tasarlanmıştır. Bunun yanı sıra, WAP-Ağacı üzerinde çalışan bir veri madenciliği yöntemi önerilmiştir. Önerilen yöntem, olası diziler arama uzayında melez bir gezinti stratejisi ve örüntü ağacında kardeşlik prensibi adlı bir erken budama fikri içerir. Bu fikri sırasıyla WAP-Ağacı ve Çoklu-WAP-Ağacına uygulayan FOF-PT ve MULTI-FOF-PT adlı iki algoritma geliştirilmiştir. Yapılan deneyler FOF-PT algoritmasının hem diğer WAP-Ağacı temelli algoritmalardan hem de PrefixSpan'dan çalışma zamanı açısından üstün olduğunu göstermiştir. Deneylerde, MULTI-FOF-PT algoritmasının da küçük alfabeli yoğun çoklu veritabanlarında PrefixSpan'dan daha hızlı çalıştığı gözlemlenmiştir.