Skip to content
กลับไปยังผลการค้นหา

อัลกอริทึม Apriori

ผู้เสนอ
Agrawal, R. & Srikant, R.
ปี
1994
ประเภท
Frequent itemset and association rule mining algorithm
กลุ่มวิธี
Machine learning

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

อัลกอริทึม Apriori ซึ่งริเริ่มโดย Agrawal และ Srikant ในปี 1994 เป็นวิธีการพื้นฐานสำหรับการค้นหาชุดรายการที่ปรากฏบ่อย (frequent itemsets) และกฎความสัมพันธ์ (association rules) ในฐานข้อมูลธุรกรรม โดยใช้วิธีการค้นหาแบบกว้างตามระดับ (breadth-first, level-wise search) ซึ่งชี้นำโดยคุณสมบัติการต่อต้านการผูกขาด (anti-monotone property) ของความถี่ในการปรากฏ (support) เพื่อแจกแจงชุดรายการทั้งหมดที่ปรากฏร่วมกันเกินกว่าเกณฑ์ขั้นต่ำที่ผู้ใช้กำหนด จากนั้นจึงสกัดกฎ if-then ที่ตีความได้จากรูปแบบเหล่านั้น

แนวคิดเบื้องหลังวิธีการ

พิจารณาฐานข้อมูลใบเสร็จซูเปอร์มาร์เก็ต แนวคิดของ Apriori คือคุณสมบัติการต่อต้านการผูกขาด: หากสินค้าสองชิ้นมักจะถูกซื้อร่วมกันน้อยครั้ง ชุดรายการที่ใหญ่กว่าซึ่งมีสินค้าคู่นั้นอยู่ด้วยก็ไม่สามารถมีความถี่สูงได้ สิ่งนี้ช่วยให้อัลกอริทึมสามารถตัดทอนพื้นที่การค้นหาที่มีขนาดใหญ่แบบทวีคูณของชุดรายการที่เป็นไปได้ทั้งหมด โดยการสร้างรายการผู้สมัคร (candidates) ทีละระดับ — เริ่มต้นจากรายการเดี่ยวๆ จากนั้นเป็นคู่ แล้วเป็นสามรายการ — และทิ้งรายการผู้สมัครใดๆ ที่ชุดย่อย (subsets) ของมันเป็นที่ทราบกันดีว่าไม่มีความถี่สูงแล้ว ก่อนที่จะนับในข้อมูล

ประวัติศาสตร์

Rakesh Agrawal และ Ramakrishnan Srikant ได้นำเสนออัลกอริทึม Apriori ที่งาน VLDB ปี 1994 โดยต่อยอดจากสูตรปัญหาการทำเหมืองกฎความสัมพันธ์ของ Agrawal และคณะในปี 1993 ชื่ออัลกอริทึมสะท้อนถึงแนวคิดหลัก: การใช้ความรู้ล่วงหน้าเกี่ยวกับชุดรายการที่ปรากฏบ่อย (k)-itemsets เพื่อตัดทอนรายการผู้สมัครที่ระดับ k+1 กลายเป็นมาตรฐานที่ใช้อ้างอิงสำหรับอัลกอริทึม frequent-itemset ทั้งหมดที่ตามมา — รวมถึง FP-Growth (2000) และ Eclat — และยังคงเป็นบทมาตรฐานในตำรา data-mining และ machine learning

ควรใช้เมื่อใด

ใช้ Apriori เมื่อเป้าหมายคือการค้นหารูปแบบการปรากฏร่วมกันหรือความสัมพันธ์แบบ if-then ในข้อมูลธุรกรรมหรือข้อมูลการปรากฏของรายการแบบไบนารี — การวิเคราะห์ตะกร้าสินค้า (market basket analysis) การยืนยันรายการสำรวจร่วมกัน (survey item co-endorsement) การปรากฏร่วมกันของการวินิจฉัยทางการแพทย์ หรือความสัมพันธ์ของคำในข้อความ (text term association) เหมาะสำหรับชุดข้อมูลขนาดปานกลางที่ความโปร่งใสและการตีความกฎผลลัพธ์เป็นสิ่งสำคัญ อย่าใช้ Apriori เมื่อฐานข้อมูลธุรกรรมมีขนาดใหญ่มาก (หลายล้านแถวพร้อมรายการสินค้าจำนวนมาก) เนื่องจากต้องสแกนฐานข้อมูลเต็มรูปแบบซ้ำๆ ทำให้ช้าเมื่อเทียบกับ FP-Growth ในกรณีเหล่านั้น FP-Growth จะเป็นที่นิยมมากกว่า นอกจากนี้ยังไม่เหมาะสมสำหรับข้อมูลตัวเลขต่อเนื่องหากไม่ได้รับการแบ่งกลุ่มก่อน และไม่ได้จำลองทิศทางหรือความเป็นเหตุเป็นผล

ข้อจำกัดและข้อควรพิจารณา

  • การสแกนฐานข้อมูลเต็มรูปแบบซ้ำๆ ทำให้ช้าบนชุดข้อมูลขนาดใหญ่ — FP-Growth มักเป็นที่นิยมมากกว่าเมื่อใช้ในสเกลใหญ่
  • การลดเกณฑ์ support อาจทำให้เกิดชุดรายการผู้สมัครและกฎจำนวนมากแบบทวีคูณ ทำให้การตีความทำได้ยาก
  • ไม่สามารถจับลำดับเวลา ทิศทาง หรือความสัมพันธ์เชิงสาเหตุระหว่างรายการได้
  • ผลลัพธ์มีความอ่อนไหวต่อการเลือกเกณฑ์ support และ confidence ซึ่งต้องใช้ความรู้เฉพาะทางหรือการปรับแต่งอย่างเป็นระบบ

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • สร้างกฎ if-then ที่ตีความได้สมบูรณ์พร้อมค่า support, confidence, และ lift ที่วัดค่าได้
  • คุณสมบัติการตัดทอนแบบต่อต้านการผูกขาดทำให้การค้นหาที่โดยปกติจะเป็นแบบทวีคูณสามารถจัดการได้
  • ไม่ต้องมีการติดป้ายกำกับข้อมูลล่วงหน้า เป็นแบบไม่มีผู้สอน (unsupervised) โดยสมบูรณ์
  • พารามิเตอร์เกณฑ์ (support, confidence) ให้นักวิเคราะห์ควบคุมความละเอียดของกฎได้โดยตรง
  • กฎผลลัพธ์สามารถนำไปปฏิบัติได้และสามารถสื่อสารกับผู้มีส่วนได้ส่วนเสียที่ไม่ใช่ผู้เชี่ยวชาญด้านเทคนิคโดยไม่มีพื้นฐานเกี่ยวกับอัลกอริทึม
  • เป็นอัลกอริทึมต้นแบบที่ได้รับการอ้างอิงอย่างกว้างขวางและถูกนำไปใช้ในไลบรารี data-mining หลักเกือบทั้งหมด

การประยุกต์ใช้

  • การวิเคราะห์ตะกร้าสินค้า: การค้นหาว่าผลิตภัณฑ์ใดมักถูกซื้อร่วมกันเพื่อเป็นแนวทางในการจัดวางสินค้าและโปรโมชั่น
  • เวชสารสนเทศ (Medical informatics): การระบุอาการ การวินิจฉัย หรือการสั่งยาที่ปรากฏร่วมกันในบันทึกผู้ป่วย
  • การทำเหมืองพฤติกรรมการใช้งานเว็บ (Web usage mining): การค้นหาว่าหน้าเว็บหรือคุณสมบัติใดที่ผู้ใช้มีแนวโน้มจะเข้าชมหรือเปิดใช้งานร่วมกัน
  • การวิเคราะห์แบบสำรวจและแบบสอบถาม: การตรวจจับว่ารายการใดหรือการตอบแบบสอบถามใดที่มักจะได้รับการยืนยันร่วมกันอย่างเป็นระบบ
  • การเริ่มต้นระบบแนะนำ (Recommender system bootstrapping): การสร้างรายการความสัมพันธ์ของผู้สมัครก่อนที่จะนำ collaborative filtering ไปใช้
  • การตรวจจับการฉ้อโกง: การค้นหารูปแบบการปรากฏร่วมกันที่ผิดปกติในบันทึกธุรกรรมที่เบี่ยงเบนไปจากตะกร้าสินค้าปกติ

วิธีการทำงาน

วิธีการทำงาน

1

นักวิเคราะห์จะเลือกเกณฑ์สองค่าก่อนที่จะรันอัลกอริทึม: ความถี่ขั้นต่ำ (minimum support) ซึ่งเป็นสัดส่วนของธุรกรรมที่ต้องมีชุดรายการที่กำหนดจึงจะถือว่ามีความถี่สูง และความเชื่อมั่นขั้นต่ำ (minimum confidence) ซึ่งเป็นความน่าจะเป็นแบบมีเงื่อนไขที่จำเป็นสำหรับกฎ if-then ที่จะถูกเก็บไว้ ค่าทั้งสองนี้ควบคุมปริมาณและความเฉพาะเจาะจงของผลลัพธ์ และควรได้รับการปรับเทียบผ่านความรู้เฉพาะทางหรือการทดลองเบื้องต้น

2

อัลกอริทึมทำการสแกนฐานข้อมูลธุรกรรมเต็มรูปแบบหนึ่งครั้งเพื่อคำนวณว่าแต่ละรายการปรากฏบ่อยเพียงใด เฉพาะรายการที่มีความถี่ในการปรากฏตรงตามเกณฑ์ขั้นต่ำที่กำหนดเท่านั้นที่จะถูกเก็บไว้ ส่วนรายการที่เหลือจะถูกทิ้ง ชุดของรายการเดี่ยวที่มีความถี่สูงนี้จะสร้างชุดรายการผู้สมัครระดับแรก

สูตร
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

ชุดรายการที่มีความถี่สูงที่พบในระดับ k จะถูกรวมกันเป็นคู่เพื่อสร้างชุดรายการผู้สมัครขนาด k+1 เฉพาะคู่ที่มีรายการ k-1 แรกเหมือนกันเท่านั้นที่จะถูกรวมกัน ซึ่งเป็นกฎที่ช่วยให้ชุดรายการผู้สมัครมีขนาดกะทัดรัด การสแกนฐานข้อมูลใหม่จะคำนวณความถี่ในการปรากฏของรายการผู้สมัครแต่ละรายการ

4

ก่อนทำการนับ ชุดรายการผู้สมัครขนาด k+1 ทุกรายการจะถูกตรวจสอบกับชุดย่อย (k) ทั้งหมด หากชุดย่อยใดๆ ไม่มีความถี่สูงในระดับก่อนหน้า รายการผู้สมัครนั้นจะถูกตัดทอนทันทีโดยไม่ต้องอ่านข้อมูล โดยใช้คุณสมบัติการต่อต้านการผูกขาดเพื่อลดการคำนวณ ผู้รอดชีวิตจากขั้นตอนการตัดทอนนี้จะสร้างชุดรายการที่มีความถี่สูงในระดับถัดไป

5

จากชุดรายการที่มีความถี่สูงทุกชุดที่มีขนาดตั้งแต่สองรายการขึ้นไป กฎ if-then ที่เป็นไปได้ทั้งหมดจะถูกสร้างขึ้นโดยการแบ่งรายการออกเป็นส่วนหน้า (antecedent) และส่วนหลัง (consequent) กฎแต่ละข้อจะถูกประเมินตามความเชื่อมั่น ซึ่งเป็นสัดส่วนของธุรกรรมที่มีส่วนหน้าซึ่งมีส่วนหลังด้วย กฎที่ต่ำกว่าความเชื่อมั่นขั้นต่ำจะถูกทิ้ง

สูตร
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}
6

กฎที่รอดชีวิตจะถูกจัดอันดับตามค่า lift ซึ่งเปรียบเทียบความเชื่อมั่นที่สังเกตได้กับความถี่พื้นฐานของส่วนหลัง ค่า lift ที่สูงกว่า 1 บ่งชี้ว่าส่วนหน้าและส่วนหลังปรากฏร่วมกันมากกว่าที่คาดการณ์ไว้โดยบังเอิญ ค่า lift ใกล้เคียง 1 บ่งชี้ความเป็นอิสระ ค่า lift ที่ต่ำกว่า 1 บ่งชี้ความสัมพันธ์เชิงลบ กฎที่มีค่า lift สูงสุดคือการค้นพบที่สามารถนำไปปฏิบัติได้มากที่สุด

สูตร
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}

ข้อผิดพลาดที่พบบ่อย

  • การตั้งค่า minimum support ต่ำเกินไปจนทำให้เกิดกฎคุณภาพต่ำจำนวนมากโดยไม่ได้กรองด้วย lift
  • การตีความความเชื่อมั่นสูงว่าเป็นสาเหตุมากกว่าการปรากฏร่วมกัน — กฎที่มีความเชื่อมั่นสูงแต่ lift ใกล้เคียง 1 นั้นไม่มีนัยสำคัญ
  • การนำ Apriori ไปใช้กับคุณลักษณะต่อเนื่องโดยไม่ได้แบ่งกลุ่มก่อน ซึ่งจะเพิ่มพื้นที่รายการและทำให้ผลลัพธ์แย่ลง
  • การรายงานกฎโดยไม่ได้ตรวจสอบว่าขนาดตัวอย่างของชุดรายการมีมากพอที่จะเชื่อถือการประมาณค่า support ได้หรือไม่
  • การละเลยการลบกฎที่ไม่ให้ข้อมูล (เช่น กฎที่เกี่ยวข้องกับรายการที่ซื้อโดยทั่วไปเสมอ เช่น บัตรสะสมคะแนนของร้านค้า)

คำถามที่พบบ่อย

อะไรคือความแตกต่างระหว่าง support, confidence, และ lift?

Support คือสัดส่วนของธุรกรรมทั้งหมดที่มีชุดรายการนั้น — เป็นการวัดความแพร่หลาย Confidence คือความน่าจะเป็นแบบมีเงื่อนไขที่ส่วนหลังปรากฏเมื่อกำหนดส่วนหน้า — เป็นการวัดความน่าเชื่อถือของกฎ Lift คืออัตราส่วนของ confidence ที่สังเกตได้กับความถี่พื้นฐานของส่วนหลัง ค่า lift ที่สูงกว่า 1 แสดงถึงความสัมพันธ์เชิงบวกที่แท้จริง แทนที่จะเป็นเรื่องบังเอิญที่เกิดจากความนิยมของรายการ

เมื่อใดที่ฉันควรเลือก FP-Growth แทน Apriori?

FP-Growth บีบอัดฐานข้อมูลให้อยู่ในโครงสร้างต้นไม้และทำการทำเหมืองโดยไม่ต้องสแกนเต็มรูปแบบซ้ำๆ ทำให้เร็วกว่าอย่างมากบนชุดข้อมูลขนาดใหญ่หรือเมื่อ minimum support ต่ำ Apriori เข้าใจและนำไปใช้ง่ายกว่า และทำงานได้ดีบนชุดข้อมูลขนาดเล็กถึงปานกลางที่เวลาทำงานไม่ใช่คอขวด

ฉันจะเลือก minimum support และ confidence ได้อย่างไร?

ไม่มีกฎสากล แนวทางปฏิบัติทั่วไปคือการรันอัลกอริทึมที่ระดับ support หลายระดับ วาดกราฟจำนวน frequent itemsets เทียบกับ support และเลือกระดับที่จุดหักศอกของเส้นโค้ง จากนั้นกำหนด confidence ตามคำถามทางธุรกิจหรือการวิจัย — confidence ที่สูงขึ้นสำหรับกฎที่สำคัญยิ่งยวด และต่ำลงสำหรับการค้นพบเชิงสำรวจ ควรตรวจสอบกฎอันดับต้นๆ กับความรู้เฉพาะทางเสมอ

Apriori สามารถจัดการข้อมูลตัวเลขหรือข้อมูลต่อเนื่องได้หรือไม่?

Apriori ต้องการข้อมูลการปรากฏของรายการแบบไบนารี ตัวแปรต่อเนื่องต้องถูกแบ่งกลุ่มเป็นช่วง (เช่น อายุแบ่งเป็น ต่ำ/ปานกลาง/สูง) ก่อนที่จะเข้ารหัสเป็นรายการ การแบ่งกลุ่มที่ไม่ดีอาจทำให้กฎที่ค้นพบผิดเพี้ยนอย่างรุนแรง ดังนั้นกลยุทธ์การแบ่งกลุ่มจึงสมควรได้รับการพิจารณาอย่างรอบคอบ

Apriori บ่งบอกถึงความเป็นเหตุเป็นผลระหว่างรายการหรือไม่?

ไม่ กฎความสัมพันธ์จับการปรากฏร่วมกัน ไม่ใช่ความเป็นเหตุเป็นผลหรือทิศทาง กฎ 'ขนมปัง → เนย' หมายความว่ามักจะปรากฏในตะกร้าเดียวกัน ไม่ได้หมายความว่าการซื้อขนมปังทำให้ใครบางคนซื้อเนย หรือความสัมพันธ์นั้นไม่สมมาตรในแง่ของสาเหตุ

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Apriori algorithm. Wikipedia.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว