Fulltext

Pruning of Apriori-Algorithm’s Pruning Steps

تــشـــــذيب خطوات الــتــشــــذيب في خوارزمية الأبريوري

Ala H. Al-Hamamy

Al-Rafidain University College For Sciences مجلة كلية الرافدين الجامعة للعلوم
ISSN: 16816870 Year: 2007 Issue: 21 Pages: 1-16
Publisher: Rafidain University College كلية الرافدين الجامعة

Abstract

Association rules mining is the main task of data mining. It consists of two compulsory steps, the first step is discovery of frequent itemsets, and the second one is extracting the rules from the mined frequent itemsets. The first step is massive computational step. There are many algorithms presented to complete this step, but all of these algorithms are variations of the Apriori algorithm, which is the state of the art. Apriori requires a priori knowledge to generate the frequent itemsets and involves two time-consuming pruning steps to exclude the infrequent candidates and hold frequents. The first pruning operation is degenerating each of the (k+1)-itemsets to its k-itemset subsets. The second pruning operation is support counting for each candidate passed the first exam. This research improves Apriori algorithm by pruning its pruning steps. It abridges the pruning steps to TID lists intersection and items union operations by taming the problem of frequent itemsets mining to lattice theory. It excludes the neediness to multi-scanning the database; instead, it scans the database only once.Keywords: Data Mining, Association Rules, Apriori Algorithm, Lattice

استكشاف قواعد الأرتباط هو واحد من اهم اغراض تعدين البيانات. لأستكشاف قواعد الأرتباط في قواعد البيانات، هنالك اجرائين لازمين هما: (1) استكشاف المجموعات الكبيرة للعناصر ، (2) واستخراج القواعد من هذه المجاميع المستكشفة. الأجراء الأول اعقد بكثير من الثاني والذي يحتاج الى اجراءات حسابية كبيرة. هنالك العديد من الخوارزميات المقترحة لانجاز الأجراء الأول، كلها تعتبر تنوعا من خوارزمية قياسية تدعى ابريوري. خوارزمية ابريوري تحتاج الى معرفة مسبقة لتوليد مستوى جديد من مجموعات العناصر الكبيرة. انها تولد مجموعات عناصر مرشحة لتكون كبيرة. لأستبعاد المرشحات التي لاتتواقر فيها الشروط،، الخوارزمية تستخدم عمليتي تشذيب معقدة؛ الأولى هي تهديم مجموعة العناصر

Keywords

Apriori-Algorithm’s --- خوارزمية الأبريوري