Yüksek ortalama-faydalı örüntü madenciliği için yeni tekniklerin geliştirilmesi
Developing new techniques for high average-utility itemset mining
Yazar: İRFAN YILDIRIM
Danışman: DOÇ. DR. METE ÇELİK
Erciyes Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2019
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Ağaç yapı = Tree structure ; Birliktelik kural madenciliği = Association rule mining ; Veri madenciliği = Data mining

Özet:
Büyük veri kümeleri içindeki yüksek ortalama-faydalı örüntü (YOFÖ)'lerin doğru ve eksiksiz bir şekilde keşfedilmesi sürecine yüksek ortalama-faydalı örüntü madenciliği (YOFÖM) problemi denilmektedir. YOFÖM, arama uzayının genişliğinden dolayı çözülmesi zor ve karmaşık bir problemdir. Literatürde,  çeşitli üst-limit modelleri, arama uzayı budama stratejileri ve veri yapıları gibi farklı teknikler kullanan YOFÖM yöntemleri bulunmaktadır. Ancak var olan YOFÖM yöntemleri yürütme zamanı ve bellek ihtiyacı açısından oldukça maliyetlidirler ve veri kümesinin hacminin artmasına bağlı olarak  ölçeklenebilir değillerdir. Ayrıca, veri kümelerinin sadece pozitif faydalı ögeler içerebileceği varsayıma göre tasarlanmışlardır. Hâlbuki birçok gerçek dünya veri kümesi aynı zamanda negatif faydalı ögeler de içermektedir.
 
Bu tez çalışmasında, YOFÖM probleminin etkili bir şekilde çözülmesi için çeşitli teknikler kullanan üç farklı yöntem geliştirilmiştir. Geliştirilen her yöntem farklı tipteki YOFÖM probleminin daha etkili çözülmesi için tasarlanmıştır. Geliştirilen ilk yöntem, klasik YOFÖM probleminin daha etkili bir şekilde çözülmesi için dört yeni üst-limit modeli, dört yeni budama stratejisi, iki yeni veri yapısı ve bir algoritma (YOFL-Büyüme) önermektedir. Geliştirilen ikinci yöntem, negatif faydalı YOFÖM probleminin daha etkili bir şekilde çözülmesi için bir yeni üst-limit modeli, üç yeni budama stratejisi, bir yeni veri yapısı ve bir algoritma (NYOFÖ-Keşif) önermektedir. Geliştirilen üçüncü yöntem, artırımlı YOFÖM problemindeki aday örüntülerin daha etkili bir şekilde bulunması için  bir yeni veri yapısı ve bir algoritma (HAYOFÖM) önermektedir.  Önerilen yöntemlerin başarımlarını değerlendirmek için sentetik ve gerçek veri kümeleri kullanılarak çeşitli deneyler yapılmıştır. Deneysel sonuçlar, önerilen yöntemlerin literatürdeki benzerlerine göre daha etkili bir şekilde çalıştıklarını göstermiştir. 
Bu tez çalışmasında, YOFÖM probleminin etkili bir şekilde çözülmesi için çeşitli teknikler kullanan üç farklı yöntem geliştirilmiştir. Geliştirilen her yöntem farklı tipteki YOFÖM probleminin daha etkili çözülmesi için tasarlanmıştır. Geliştirilen ilk yöntem, klasik YOFÖM probleminin daha etkili bir şekilde çözülmesi için dört yeni üst-limit modeli, dört yeni budama stratejisi, iki yeni veri yapısı ve bir algoritma (YOFL-Büyüme) önermektedir. Geliştirilen ikinci yöntem, negatif faydalı YOFÖM probleminin daha etkili bir şekilde çözülmesi için bir yeni üst-limit modeli, üç yeni budama stratejisi, bir yeni veri yapısı ve bir algoritma (NYOFÖ-Keşif) önermektedir. Geliştirilen üçüncü yöntem, artırımlı YOFÖM problemindeki aday örüntülerin daha etkili bir şekilde bulunması için yeni bir veri yapısı ve bir algoritma (HAYOFÖM) önermektedir.  Önerilen yöntemlerin başarımlarını değerlendirmek için sentetik ve gerçek veri kümeleri kullanılarak çeşitli deneyler yapılmıştır. Deneysel sonuçlar, önerilen yöntemlerin literatürdeki benzerlerine göre daha etkili bir şekilde çalıştıklarını göstermiştir.

Abstract:
The process of discovering the complete and correct set of high-average utility itemsets (HAUIs) in large datasets  is called the high average-utility itemsets mining (HAUIM) problem.
HAUIM is a complex and difficult problem to solve since its search space is large. 
In the literature, there are several HAUIM methods that use different techniques such as various upper-bound models,  search space pruning strategies, and data structures. 
However, the existing HAUIM methods are very costly in terms of execution time and memory and  are not scalable based on increase in the volume of datasets. 
Besides, they are designed based on the assumption that datasets can only contain items with positive utilities. But  many real-world datasets also contain items with negative utilities.

In this thesis, three different methods have been developed which use various techniques in order to solve HAUIM problem effectively. Each method is designed to solve different types of HAUIM problems more effectively.
The first method proposes four new upper-bound models, four new pruning strategies, two new data structures, and an algorithm (HAUL-Growth) to solve the classical HAUIM problem more effectively.
The second method proposes a new upper-bound model, three new pruning strategies, a new data structure, and an algorithm (MHAUIPNU) to solve HAUIM problem with negative utilities more effectively.
The third method proposes a new data structure and an algorithm (FIMHAUI) in order to find out the candidate patterns in the incremental HAUIM problem more effectively.
In order to evaluate the performance of the proposed methods, various experiments were conducted using synthetic and real datasets.
Experimental results showed that the proposed methods work more effectively than their counterparts in the literature.