Development of a framework for frequent itemset mining under multiple support thresholds

Abstract

Sık kümeler madenciliği yöntemleri yoğun veri tabanlarındaki özellikliörüntülerin bulunmasını sağlarlar. Bu yöntemler, sık kümeler setlerini bulurken tek birdestek eşik değerini esas alırlar. Oysa gerçek dunya uygulamalarında tek bir destek eşikdeğeri örüntülerin tek başlarına özelliğini yansıtmakta yetersiz kalmakta ve seyrek örüntü(rare item) problemi ortaya çıkarmaktadır. Son zamanlarda, bu seyrek örüntü problemininçözümüne odaklanan çalışmalar bulunmaktadır. Bu çalışmalar kümelere ve kümeelemanlarına farklı destek eşik değerleri atanmasına izin vermektedir. Böylece gereksizörüntüler oluşturulmadan seyrek örüntüler ele geçirilebilmektedir. Bu tez kapsamında,etkin bir Çoklu Destek Eşiklerinde Sık Kümeler (Multiple Item Support Frequent Patterngrowth algorithm, MISFP-growth) yöntemi önerilmektedir. Bu yöntem veri tabanındansık örüntülerin bulunmasını sağlayacak veriyi bir ağaçta saklamaktadır (MISFP-Tree). Buağaç tüm veriyi değil de çoklu eşiklerin minimumunu dikkate alarak oluşturulduğu için,oluşturulma sonrası budama ve yeniden oluşturulmaya gereksinim duymamaktadır. Buyöntemin etkinliği yeni bir ağaç tabanlı yöntemle (CFP-growth++) karşılaştırılarakgösterilmiştir. Karşılaştırma çalışmaları gerçek ve sentetik veri tabanları üzerindegerçekleştirilmiştir. Başarım değerlendirme sonuçları MISFP-growth yönteminin diğeryönteme göre, çalışma zamanı, bellek kullanımı ve ölçeklenebilirlik açısından dahabaşarılı olduğunu göstermiştir.

Frequent pattern mining is an essential method of data mining that is used toextract interesting patterns from massive databases. Traditional methods use singleminimum support threshold to find out the complete set of frequent patterns. However,in real word applications, using single minimum support threshold is not adequate sinceit does not reflect the nature of each item and causes a problem called rare item problem.Recently, several methods have been studied to tackle this problem by avoiding usingsingle minimum item support threshold. The nature of each item is considered wheredifferent items are specified with different minimum support thresholds. By this, thecomplete set of frequent patters are generated without creating uninteresting patterns andlosing substantial patterns. In this thesis, we propose an efficient method, Multiple ItemSupport Frequent Pattern growth algorithm, MISFP-growth, to mine the complete set offrequent patterns with multiple item support thresholds. In this method, Multiple ItemSupport Frequent Pattern tree, MISFP-Tree, is constructed to store all crucial informationto mine frequent patterns. Since in the construction of the MISFP-Tree is done withrespect to minimum of Multiple Itemset Support values; pruning and reconstructionphases are not required. To show the efficiency of the proposed method, it is comparedwith a recent tree-based algorithm, CFP-growth++. To evaluate the performance of theproposed algorithm, various experiments are conducted on both real and syntheticdatasets. Experimental results reveal that MISFP-growth outperforms the previousalgorithm in terms of execution time, memory space as well as scalability.