Chulalongkorn University Theses and Dissertations (Chula ETD)

วิธีการหากฎความสัมพันธ์แบบใหม่โดยต้นไม้แสดงรายการความถี่

Other Title (Parallel Title in Other Language of ETD)

A novel approach of mining association rules with frequent item tree

Year (A.D.)

2005

Document Type

Thesis

First Advisor

อรรถสิทธิ์ สุรฤกษ์

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.2005.1230

Abstract

ในปัจจุบันงานวิจัยเกี่ยวกับการวิเคราะห์หารูปแบบความสัมพันธ์ของข้อมูลจากฐานข้อมูลขนาดใหญ่ มีบทบาทและความสคำญในปัญหาของการทำเหมืองข้อมูลหรือการขุดค้นข้อมูล นอกจากนี้มีนักวิจัยจำนวนมากให้ความสนใจและศึกษาเพื่อการพัฒนากระบวนการ หรือคิดค้นวิธีการใหม่ในการหาความสัมพันธ์ให้มีประสิทธิภาพมากยิ่งขึ้น การสร้างกฎความสัมพันธ์เป็นวิธีหนึ่งในการสืบหากฎความสัมพันธ์ร่วมของกลุ่มข้อมูลในเชิงปริมาณ โดยที่แต่ละกฎถูกระบุด้วยค่าสนับสนุนและค่าความเชื่อมั่น โดยทั่วไปกฎความสัมพันธ์ถูกนำไปใช้ในการวิเคราะห์หาพฤติกรรมการซื้อของลูกค้า การหากฎความสัมพันธ์ของข้อมูลประกอบด้วย 2 ขั้นตอนใหญ่ๆ ได้แก่ การหาเขตรายการความถี่ซึ่งก็คือ เซตของรายการที่มีค่าสนับสนุนเกินค่าสนับสนุนขั้นต่ำที่กำหนดให้ และการนำเอาเชตรายการความถี่ที่สามารถหาได้สร้างเป็นกฎความสัมพันธ์ โดยในขั้นตอนแรกจะเป็นขั้นตอนที่ใช้เวลาและหน่วยความจำมาก เนื่องจากต้องทำการอ่านข้อมูลจากฐานข้อมูลเพื่อหาการเกิดร่วมกันของข้อมูลจำนวนมาก จึงเป็นเหตุให้มีนักวิจัยจำนวนมากให้ความสนใจที่จะปรับปรุงการหาเซตรายการความถี่จากฐานข้อมูล ในงานวิจัยนี้ได้นำเสนออัลกอริทึมเพื่อลดเวลาในการคำนวณ ซึ่งเป็นอัลกอริทึมที่พัฒนาจากเอฟพี-กโรธอัลกอริทึม โดยปรับปรุงขั้นตอนการสร้างต้นไม้แสดงรายการความถี่ และการหาเซตรายการความถี่จากต้นไม้แสดงรายการความถี่ การปรับปรุงการสร้างต้นไม้แสดงรายการความถี่ จะลดขั้นตอนการเรียงลำดับรายการในรายการเปลี่ยนแปลงทุกรายการเปลี่ยนแปลง และการปรับปรุงหาเซตรายการความถี่จะทำการรวมค่าสนับสนุน การหาสับเซตที่จำเป็น และการตัดเล็มต้นไม้แทนการหาคอนดิชันนอลแพทเทินเบซ และการสร้างคอนดิชันนอลเอฟพี-ทรี จากการทดลองและเปรียบเทียบเวลาการหาเซตรายการความถี่ปรากฏว่า การหาเซตรายการความถี่จากต้นไม้แสดงรายการความถี่ใช้เวลาในการคำนวณน้อยกว่า เอฟพี-กโรธอัลกอริทึม และความซับซ้อนเชิงเวลาของทั้งสองอัลกอริทึมมีค่าเท่ากับ (n) เมื่อ n คือ จำนวนรายการเปลี่ยนแปลงในฐานข้อมูล

Other Abstract (Other language abstract of ETD)

One of the most well-studied problem in data mining is to discover association rules in market basket datasets. Association rules, whose significance is measured by support and confidence, are intended to identify relationships among sets of items. The task of mining association rules consists of two main steps. The first step is to find all itemsets whose frequencies are above minimum support. These itemsets are called frequent itemsets. The second step involves generating high confidence rules among frquent itemsets. According to the size of datasets, finding frequent itemsets is computationally the most expensive step in association rule discovery. Therefore, it is necessary to develop appropriated structure capable of high compression ratios and supporting of fast finding frequent itemsets. In this thesis, we proposes a new algorithm for frequent itemsets mining called frequent item tree. It is improved from FP-growth algorithm in order to reduce computational time. The main idea of frequent item tree is separate into 2 sections. First is frequent item tree building improvement which reduces transaction sorting procedure. Second is frequent itemsets mining improvement which replaces conditional pattern base and conditional FP-tree procedure with Item frequency combination, necessary subsets finding and frequent item tree prunning. The experimental result shows advantages of our algorithm over FP-growth, in terms of runtime, although time complexity of them are (n) whereas n is number of transactions

Link to Full Text

Share

COinS