Fast and efficient frequent itemset detection by a novel clustering method

Abstract

Veritabanı ve depolama teknolojilerindeki ilerlemeler firmaları ve kurumları kısa zaman içerisinde büyük miktarlarda veri depolamasına olanak sağlar hale getirmiştir. Saklanan bu veri kümelerinin içerisinden şirket ve kurumlara faydalı olacak bilgiye ulaşmak için kullanılacak tekniklerin geleneksel veri analizi metotlarından ileri durumda olması gerekmektedir. Bu yüzden geleneksel veri analizi metotlarının ilerletilerek etkinlik ve performans penceresinden bakıldığında çok daha ileri olan teknikler geliştirilmeye çalışılmıştır. Veri kümelerinin ele alınarak bu kümelerden bilgiyi ortaya çıkarma çalışmalarından birini sık rastlanan öğe kümesi tespiti konusu oluşturmaktadır. Sık rastlanan öğe kümeleri tespiti pazarlama, satış, telekomünikasyon, tıp, biyoloji ve mühendislik alanlarındaki pek çok uygulamada karşılaşılan bir problemdir. Uygulama içeriğine bağlı olarak bir öğe ölçü, ürün, servis vb. olabilir. Birbirinden farklı n adet öğe içeren bir veri kümesi, 2^n adet sık rastlanan öğe kümesine sahiptir. Bu nedenle tüm sık rastlanan öğe kümelerini bulmak üssel zaman karmaşıklığı içeren karmaşık bir bilgi sistemi oluşturur. Bu çalışmada, bir veri kümesi içerisinde sık rastlanan öğe kümelerinin önemli bir kısmının hızlı bir şekilde bulunması için yeni bir algoritma tanıtmaktayız. Bu metot sık rastlanan öğe kümelerini tespit etmek için tasarlanmış yeni bir kümeleme algoritmasıdır. Sık rastlanan öğe kümeleri tespiti için kümeleme yapmanın iki avantajı vardır. İlki, zaman karmaşıklığını azaltarak oldukça kısa bir sürede sonuçlarının elde edilmesidir. ikincisi ise birbirine benzer sık rastlanan öğe kümeleri elde etmektir. Karmaşık bilgi sistemi içerisinde sık rastlanan öğe kümelerinin üretilmesi çok uzun zaman alması ve gereğinden fazla sık rastlanan öğe kümelerinin bulunması nedeniyle bu avantajların her ikisi de çok önemlidir.Anahtar Kelimeler: Veri Madenciliği, Kümeleme, Sık Rastlanan Öğe Kümeleri Tespiti, Birleşme Kuralları Madenciliği, İkili Değer Metotları

Advancements in database and storage technology have enabled the enterprises collect large amounts of data in a short amount of time. Methods and techniques for obtaining information from very large data sets should be more advanced compared to the traditional data analysis techniques. Frequent item set detection is one of these subjects which deals with very large data sets and reveals useful information for enterprises. Frequent item set detection is an important problem having numerous applications in marketing, sales, telecommunication, medicine, biology, and engineering. Depending on the application context, an item may be a measurement, good, service etc., and a data set with n distinct items can have 2^n frequent item sets. Therefore, finding all the frequent item sets constitutes a complex information system with exponential time complexity. This thesis presents a novel algorithm for quickly finding preponderant part of the frequent item sets in a data set, which is a new clustering algorithm designed for detecting frequent item sets. Advantages of clustering for frequent item set detection are twofold. First one is to produce results in considerably short amount of time by reducing the time complexity. Second advantage is to obtain frequent item sets that are similar to each other. Both of these advantages are vital, since in a complex information system generating all the frequent item sets takes a lot of time and there are many redundant frequent item sets.Keywords: Data Mining, Clustering, Frequent Item Set Detection, Association Rule Mining, BinaryMethods