Comparison of association algorism's efficiencies between Apriori and FP-Growth algorithms
Issued Date
2015
Copyright Date
2015
Resource Type
Language
eng
File Type
application/pdf
No. of Pages/File Size
viii, 51 leaves : ill.
Access Rights
open access
Rights
ผลงานนี้เป็นลิขสิทธิ์ของมหาวิทยาลัยมหิดล ขอสงวนไว้สำหรับเพื่อการศึกษาเท่านั้น ต้องอ้างอิงแหล่งที่มา ห้ามดัดแปลงเนื้อหา และห้ามนำไปใช้เพื่อการค้า
Rights Holder(s)
Mahidol University
Bibliographic Citation
Thematic Paper (M.Sc. (Technology of Information System Management))--Mahidol University, 2015
Suggested Citation
Banthita Tipjaksu Comparison of association algorism's efficiencies between Apriori and FP-Growth algorithms. Thematic Paper (M.Sc. (Technology of Information System Management))--Mahidol University, 2015. Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/94041
Title
Comparison of association algorism's efficiencies between Apriori and FP-Growth algorithms
Alternative Title(s)
การเปรียบเทียบประสิทธิภาพของอัลกอริทึม Apriori และอัลกอริทึม FP-Growth
Author(s)
Advisor(s)
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
การวิจัยนี้ ศึกษาเรื่องการเปรียบเทียบประสิทธิภาพของอัลกอริทึม Association ระหว่างอัลกอริทึม Apriori และอัลกอริทึม FP-Growth โดยจะกำหนดค่าสนับสนุน (Support Value) และค่าความเชื่อมั่น (Confidence Value) ซึ่งเป็นพารามิเตอร์ที่ใช้วัดประสิทธิภาพของกฎความสัมพันธ์ให้มีค่าเท่ากัน เพื่อดูเวลาที่ใช้ในการค้นหาความสัมพันธ์ของแต่ละอัลกอริทึม โดยที่อัลกอริทึม Apriori จะสร้างกฎความสัมพันธ์ด้วยการหาความถี่ของไอเท็มเซ็ต อาศัยการทำซ้ำใกล้เคียงกับวิธีค้นหาแบบ Level-wise ในการหาไอเท็มเซ็ตแต่ละครั้งต้องค้นหาข้อมูลทั้งหมดที่ถูกสร้างขึ้น ส่วนอัลกอริทึม FP-Growth จะสร้างกฎความสัมพันธ์ด้วยการสร้างไอเท็มเซ็ตที่ถูกค้นพบบ่อยครั้ง โดยไม่ต้องสร้างทั้งหมด นอกจากนี้ขั้นตอนวิธี FP-Growth ยังใช้การบีบอัดข้อมูลจากฐานข้อมูลให้อยู่ในรูปแบบของ FP-Tree เพื่อหลีกเลี่ยงการอ่านข้อมูลจากฐานข้อมูลซ้ำหลายรอบโดยข้อมูลที่ใช้ในการศึกษา คือ ข้อมูลซุปเปอร์มาร์เก็ต ซึ่งเป็นข้อมูลเกี่ยวกับการซื้อสินค้าของลูกค้า ในซุปเปอร์มาร์เก็ต นำเข้าโปรแกรม Weka เพื่อหากฎความสัมพันธ์ของอัลกอริทึม Apriori และ อัลกอริทึม FP-Growth จาก ผลการวิจัยพบว่า จำนวนกฎของทั้งสองอัลกอริทึมไม่ต่างกันและเวลาที่ใช้ในการหากฎความสัมพันธ์ของอัลกอริทึม FP-Growth น้อยกว่าอัลกอริทึม Apriori
Description
Technology of Information System Management (Mahidol University 2015)
Degree Name
Master of Science
Degree Level
Master's degree
Degree Department
Faculty of Engineering
Degree Discipline
Technology of Information System Management
Degree Grantor(s)
Mahidol University