Development of an Application for Dynamic Itemset Mining Under Multiple Support Thresholds

Abstract

Handling dynamic aspect of databases and multiple support threshold requirement of items are two important challenges of frequent itemset mining algorithms. Frequent itemsets should be updated when the database is updated without re-running the mining algorithm. Frequent itemset mining algorithm should consider different support thresholds in order not to cause rare item problem. Existing dynamic itemset mining algorithms are devised for single support threshold whereas multiple support threshold algorithms are static. This thesis focuses on dynamic update problem of frequent itemsets under multiple support thresholds and introduces Dynamic MIS1 and Dynamic MIS2 algorithms. They are i) tree based and scan the database once, ii) consider multiple support thresholds, and iii) handle increments of additions, additions with new items and deletions. Proposed algorithms are compared to CFP-Growth++ and findings are; in static databases 1) Dynamic MIS1 achieves up to 5 times speed-up against CFP-Growth++ since it does not require tree pruning and merging, 2) execution time of Dynamic MIS2 and CFP-Growth++ are similar, 3) memory usage of Dynamic MIS1 is higher than CFP-Growth++, since it keeps whole tree in memory, in dynamic database 1) Dynamic MIS1 and Dynamic MIS2 perform better than CFP-Growth++ since they run only on increments, 2) Dynamic MIS1 can achieve speed-up of 56 times against CFP-Growth++, whereas the speed-up of Dynamic MIS2 cannot exceed 2 times, 3) Dynamic MIS2 is slightly better than CFP-Growth++ until increment size is less than 85% when the database is large and sparse, 25% when the database is small and dense.

Veritabanlarının devingenliği ve kümelerin farklı destek eşiklerine olan gereksinimi, sık kümeler madenciliği algoritmalarının önemli iki zorluğudur. Veri tabanına gelen her güncellemede, sık kümelerin tüm algoritmanın baştan çalıştırılmasına gerek kalmadan güncellenebilmesi ve seyrek kümeler problemine yol açmayacak şekilde kümelerin farklı eşik değerlerine olan gereksiniminin dikkate alınması gerekmektedir. Mevcut algoritmalar ya güncellemeleri sık kümelere yansıtmaya ya da farklı eşik değerlerini dikkate almaya odaklanmışlardır. Bu tez; veritabanlarının devingen güncellenmeleri durumunda, sık kümelerin de güncellenmesine ve sık kümelerin farklı eşik değerleri göz edilerek bulunmasına yoğunlaşmış ve Dynamic MIS1 and Dynamic MIS2 algoritmalarını önermiştir. Bu algoritmalar i) ağaç tabanlıdır ve veri tabanını sadece bir kere tarar, ii) çoklu eşik değerlerini dikkate alır ve iii) eklemeli, yeni elemanla eklemeli ve silmeli güncellemelerde sık kümeleri güncelleyebilirler. Önerilen algoritmalar CFP-Growth++ algoritması ile karşılaştırılmış ve şunlar bulunmuştur; statik veritabanlarında 1) Dynamic MIS1, CFP-Growth++’dan 5 kata kadar daha hızlıdır çünkü ağaç budama ve birleştirme yapmamaktır, 2) Dynamic MIS2 ve CFP-Growth++ algoritmalarının çalışma zamanları yakındır, 3) Dynamic MIS1’ın bellek gereksinimi tüm ağacı tutması gerektiği için CFP-Growth++’dan daha fazladır, devingen veritabanlarında ise 1) sadece gelen güncelleme üzerinde çalıştıkları için Dynamic MIS1 and Dynamic MIS2 algoritmaları CFP-Growth++’dan hızlıdırlar, 2) Dynamic MIS1’ın hızlanması 56 kata kadar ulaşırken, Dynamic MIS2’inki 2 katı geçemez, 3) geniş ve seyrek veri tabanında gelen güncellemenin büyüklüğü % 85’i, küçük ve sık veritabanlarında ise % 25’i geçmediği durumlarda Dynamic MIS2 algoritması CFP-Growth++’dan daha etkindir.