الگوریتمی برای استخراج مجموعه آیتم متناوب هسته ای روی انتقال داده هاي دوگاني به صورت زنجيره اي پيوسته

An Algorithm for In-Core Frequent Itemset Mining on Streaming Data

Abstract

Frequent itemset mining is a core data mining operation and has been extensively studied over the last decade. This paper takes a new approach for this problem and makes two major contributions. First, we present a one pass algorithm for frequent itemset mining, which has deterministic bounds on the accuracy, and does not require any out-of-core summary structure. Second, because our one pass algorithm does not produce any false negatives, it can be easily extended to a two pass accurate algorithm. Our two pass algorithm is very memory efficient, and allows mining of datasets with large number of distinct items and/or very low support levels. Our detailed experimental evaluation on synthetic and real datasets shows the following. First, our one pass algorithm is very accurate in practice. Second, our algorithm requires significantly lower memory than Manku and Motwani’s one pass algorithm and the multi-pass a priori algorithm. Our two pass algorithm outperforms a priori and FP-tree when the number of distinct items is large and/or support levels are very low. In other cases, it is quite competitive, with possible exception of cases where the average length of frequent itemsets is quite high.

دانلود رایگان مقاله انگلیسی                            190.91 KB

چکیده
استخراج مجموعه آیتم متناوب یک عمل داده کاوی هسته ای می باشد و به طور گسترده در طول دهه ی اخیر مورد بررسی قرار گرفته است. این مقاله یک روش جدید برای این مسئله ارائه می کند و دو هم بخشی عمده ای را ایجاد می کند. اولا، یک الگوریتم یک مسیره برای استخراج مجموعه آیتم متناوب ارائه می کنیم، که دارای محدوده های مشخص روی صحت می باشد و به هیچ ساختار تجرید خارج از هسته نیاز ندارد. ثانیا، به علت اینکه الگوریتم تک مسیره ی ما هیچ نتیجه ی منفی نادرستی تولید نمی کند، می تواند به راحتی به یک الگوریتم صحیح دو مسیره توسعه یابد. الگوریتم دو مسیره ی ما تاثیر زیادی روی حافظه دارد و به استخراج مجموعه داده ها با تعداد زیادی آیتم مجزا و/یا سطوح پشتیبانی خیلی پایین اجازه می دهد. ارزیابی آزمایشی ما روی مجموعه داده های ترکیبی و حقیقی به صورت زیر می باشد. اولا، الگوریتم تک مسیره ی ما در عمل خیلی دقیق می باشد. ثانیا، الگوریتم ما به طور عمده به حافظه ی کمتری از الگوریتم تک مسیره ی Manku و Motwani و الگوریتم استقرایی چند مسیره نیاز دارد. الگوریتم دو مسیره ی ما به صورت استقرایی و درخت FP عمل می کند، زمانیکه تعداد آیتم های مجزا زیاد می باشد و/یا سطوح پشتیبانی خیلی پایین می باشند. در موارد دیگر، کاملا با اجرای موارد احتمالی، رقابتی می باشد، جاییکه میانگین طول مجموعه آیتم های متناوب بالا می باشد.20048

تعداد صفحات مقاله انگلیسی:12 صفحه
تعداد صفحات مقاله فارسی:37 صفحه