Fulltext

OFGIM: A New Algorithm to Mine Generalized-Itemsets

خوارزمية جديدة لتعدين مجاميع العناصر المعممة

Hussein K. Khafaji حسين كيطان الخفاجي

Al-Rafidain University College For Sciences مجلة كلية الرافدين الجامعة للعلوم
ISSN: 16816870 Year: 2013 Issue: 32 Pages: 70-93
Publisher: Rafidain University College كلية الرافدين الجامعة

Abstract

Most databases mined by a single layer/ crisp association rules algorithms are not flat but contain data in hierarchal/ generalized format. In spite of this fact, a few algorithms available to mine generalized itemsets to produce generalized association rules, GAR, which escort to mine more specific and concrete knowledge for decision makers. This research presents a new algorithm, (Optimized Frequent Generalized Itemsets Miner (OFGIM)), to mine generalized itemsets. Simply, it depends on extending the transactions of a database. The extension is done by adding the parent of an item to the transaction containing the item. The mining process is accomplished by the union of itemsets and the intersection of the tidsets. The algorithm requires two database scans only; the first one is for extending operation and the second scan is for mining process. The proposed algorithm does not need a specified data structure such as hash tree and prunes the apriori-based pruning steps.OFGJM was tested by using six synthetic databases. OFGJM overcomes apriori based algorithm in a ratio of ¼ in all the experiments, but it exhibitsits RAMappealing.

من المعتاد ان تكون قواعد البيانات التي تنقب لاستخراج قواعد الارتباط الثنائية هرمية او معممة. مع ذلك هنالك القليل من الخوارزميات التى تعنى بتعدين مجامميع العناصر الكبيرة المعممة للحصول منها على قواعد الارتباط المعممة والتي تقود الى معارف حقيقية ومحددة ذات النفع لمتخذي القرار.هذا البحث يقدم خوارزمية جديدة لاكتشاف المجاميع المعممة، الخوارزمية تعتمد ببساطة على توسيع صفقات قاعدة البيانات باضافة اباء عناصرها اليها. بعد عملية التوسيع تاتي عملية التعدين والتي تعتمد على اتحاد مجاميع العناصر وتقاطع قوائم الصفقات. الخوارزمية تحتاج الى عمليتي مسح لقاعدة البيانات، الاولى للتوسيع والثانية للتعدين. ولا تتطلب هيكل بيانات محدد مثل اشجار الاختزال وانها تشذب عمليات التشذيب التي تحتاجها خوارزمية الابريوري او الخوارزميات المعتمدة عليها. اختبرت الخوارزمية بأستخدام ستة قواعد بيانات وقد تفوقت بجميع ألأختبارات بمعدل 4/1 من زمن التنفيذ ولكنها اظهرت ازدياداً بأستخدام الذاكرة الرئيسية.

Keywords

Generalized-Itemsets --- العناصر المعممة