Comparison of association algorism's efficiencies between Apriori and FP-Growth algorithms

Abstract

This research compares the Apriori algorithm and FP-growth algorithm in terms of the Association algorithm's efficiency outcomes. In order to investigate the processing time for finding the association rules for each algorithm, we assigned the parameters of both support and confidence values to be equal. The Apriori algorithm generates the association rules by searching the frequency of itemsets. Furthermore, the Apriori algorithm is used to replicate the search as close as the level-wise search. In order to reseach itemsets each time, the entire database must be scanned. On the other hand, the FP-growth algorithm generates the association rules by creating the frequent itemsets without the candidate itemsets. Moreover, the FP-growth algorithm uses the data compression of the database in the FP-tree process to avoid duplicated reading data. The data used in the study is the shopping data from Supermarket, which was imported to the Weka program to find the association rules. According to the experiment, it was found that both the Apriori algorithm and FP-growth algorithm are not different in terms of the association rules. Likewise, the FP-growth algorithm is better than the Apriori algorithm in terms of processing time.

การวิจัยนี้ ศึกษาเรื่องการเปรียบเทียบประสิทธิภาพของอัลกอริทึม Association ระหว่างอัลกอริทึม Apriori และอัลกอริทึม FP-Growth โดยจะกำหนดค่าสนับสนุน (Support Value) และค่าความเชื่อมั่น (Confidence Value) ซึ่งเป็นพารามิเตอร์ที่ใช้วัดประสิทธิภาพของกฎความสัมพันธ์ให้มีค่าเท่ากัน เพื่อดูเวลาที่ใช้ในการค้นหาความสัมพันธ์ของแต่ละอัลกอริทึม โดยที่อัลกอริทึม Apriori จะสร้างกฎความสัมพันธ์ด้วยการหาความถี่ของไอเท็มเซ็ต อาศัยการทำซ้ำใกล้เคียงกับวิธีค้นหาแบบ Level-wise ในการหาไอเท็มเซ็ตแต่ละครั้งต้องค้นหาข้อมูลทั้งหมดที่ถูกสร้างขึ้น ส่วนอัลกอริทึม FP-Growth จะสร้างกฎความสัมพันธ์ด้วยการสร้างไอเท็มเซ็ตที่ถูกค้นพบบ่อยครั้ง โดยไม่ต้องสร้างทั้งหมด นอกจากนี้ขั้นตอนวิธี FP-Growth ยังใช้การบีบอัดข้อมูลจากฐานข้อมูลให้อยู่ในรูปแบบของ FP-Tree เพื่อหลีกเลี่ยงการอ่านข้อมูลจากฐานข้อมูลซ้ำหลายรอบโดยข้อมูลที่ใช้ในการศึกษา คือ ข้อมูลซุปเปอร์มาร์เก็ต ซึ่งเป็นข้อมูลเกี่ยวกับการซื้อสินค้าของลูกค้า ในซุปเปอร์มาร์เก็ต นำเข้าโปรแกรม Weka เพื่อหากฎความสัมพันธ์ของอัลกอริทึม Apriori และ อัลกอริทึม FP-Growth จาก ผลการวิจัยพบว่า จำนวนกฎของทั้งสองอัลกอริทึมไม่ต่างกันและเวลาที่ใช้ในการหากฎความสัมพันธ์ของอัลกอริทึม FP-Growth น้อยกว่าอัลกอริทึม Apriori