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

Association Rules

ผู้เสนอ
Agrawal, R., Imielinski, T., & Swami, A.
ปี
1993
ประเภท
Unsupervised pattern discovery
กลุ่มวิธี
Machine learning

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

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

ใช้ทำอะไร?

Association rule learning เป็นเทคนิคแบบไม่มีผู้สอน (unsupervised technique) ที่ค้นหารูปแบบการปรากฏร่วมกัน (co-occurrence patterns) — ข้อความบ่งชี้ 'ถ้า X แล้ว Y' — ภายในชุดข้อมูลธุรกรรมขนาดใหญ่ เดิมทีถูกกำหนดรูปแบบอย่างเป็นทางการโดย Agrawal, Imielinski, และ Swami (1993) สำหรับการวิเคราะห์ตะกร้าสินค้าในซูเปอร์มาร์เก็ต ปัจจุบันมีการประยุกต์ใช้อย่างกว้างขวางในการแนะนำสินค้าในอีคอมเมิร์ซ, สารสนเทศสุขภาพ, ชีวสารสนเทศ, และการวิจัยพฤติกรรม

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

ลองนึกภาพการสแกนใบเสร็จการซื้อสินค้าหลายล้านรายการและถามว่า: ผลิตภัณฑ์ใดบ้างที่มักจะปรากฏร่วมกัน? การทำเหมืองกฎความสัมพันธ์ (Association rule mining) จะตอบคำถามนั้นโดยการนับความถี่ที่ชุดรายการ (itemsets) ปรากฏร่วมกัน (support), ความน่าเชื่อถือที่รายการหนึ่งทำนายอีกรายการหนึ่ง (confidence), และความสัมพันธ์ของการปรากฏร่วมกันนั้นแข็งแกร่งกว่าโอกาสโดยบังเอิญหรือไม่ (lift) กฎเช่น 'ผ้าอ้อม → เบียร์' ที่มีความเชื่อมั่นและค่า lift สูง แสดงให้เห็นถึงรูปแบบพฤติกรรมที่แท้จริง แทนที่จะเป็นเพียงเหตุบังเอิญ ทำให้เป็นเครื่องมือสำรวจที่มีประสิทธิภาพเมื่อคุณไม่มีตัวแปรผลลัพธ์ที่จะใช้สอน (supervise)

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

Association rule learning ถูกนำเสนออย่างเป็นทางการโดย Agrawal, Imielinski, และ Swami ในการประชุม ACM SIGMOD ปี 1993 โดยมีแรงจูงใจจากความท้าทายในการทำเหมืองฐานข้อมูลธุรกรรมของซูเปอร์มาร์เก็ต เอกสารปี 1994 ของพวกเขาได้นำเสนออัลกอริทึม Apriori ซึ่งเป็นวิธีการคำนวณที่มีประสิทธิภาพ สาขานี้เติบโตอย่างรวดเร็วในช่วงทศวรรษ 1990 และ 2000 โดย FP-growth (Han et al., 2000) ได้นำเสนอการปรับปรุงความเร็วเพิ่มเติมในภายหลัง กฎความสัมพันธ์ยังคงเป็นเทคนิคพื้นฐานในหลักสูตรการทำเหมืองข้อมูล (data mining) และมีการนำไปใช้อย่างสม่ำเสมอในการวิเคราะห์การค้าปลีก สุขภาพ และเว็บ

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

ใช้กฎความสัมพันธ์เมื่อเป้าหมายของคุณคือการค้นหารูปแบบการปรากฏร่วมกันในข้อมูลธุรกรรมหรือข้อมูลที่เข้ารหัสแบบไบนารี — ตะกร้าสินค้า, การวินิจฉัยร่วมทางคลินิก, ลำดับการคลิก, ชุดคำถามสำรวจ, หรือโปรไฟล์การแสดงออกของยีน วิธีการนี้เป็นแบบไม่มีผู้สอนและไม่ต้องการป้ายกำกับผลลัพธ์ ทำให้เหมาะสำหรับการสร้างสมมติฐาน อย่าใช้เมื่อคุณมีตัวแปรผลลัพธ์ที่กำหนดไว้และต้องการทำนาย (ใช้การจำแนกประเภทแบบมีผู้สอนหรือการถดถอยแทน); เมื่อข้อมูลของคุณเป็นแบบต่อเนื่องและยังไม่ได้ถูกแบ่งกลุ่มอย่างมีความหมาย; เมื่อขนาดตัวอย่างมีขนาดเล็ก (ชุดรายการที่เบาบางให้ค่าประมาณ support ที่ไม่น่าเชื่อถือ); หรือเมื่อผลลัพธ์ของกฎจะถูกเข้าใจผิดว่าเป็นการอนุมานเชิงสาเหตุ — กฎความสัมพันธ์เป็นเพียงความสัมพันธ์ (correlational)

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

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

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

จุดแข็ง

  • ไม่มีผู้สอนโดยสมบูรณ์: ไม่จำเป็นต้องมีตัวแปรผลลัพธ์ที่มีป้ายกำกับ ช่วยให้สามารถค้นหารูปแบบที่เปิดกว้างได้
  • ผลลัพธ์ที่ตีความได้: กฎแต่ละข้อเป็นข้อความ IF–THEN ที่มนุษย์อ่านได้ พร้อมค่า support, confidence, และ lift ที่วัดค่าได้
  • ปรับขนาดได้สำหรับฐานข้อมูลธุรกรรมขนาดใหญ่มากผ่านเทคนิคการตัดแต่ง (pruning heuristics) (Apriori, FP-growth)
  • สามารถประยุกต์ใช้ได้ในหลากหลายสาขาที่การปรากฏร่วมกันในบันทึกที่เข้ารหัสแบบไบนารีมีความหมาย
  • การสร้างสมมติฐาน: แสดงการปรากฏร่วมกันที่ไม่คาดคิดซึ่งสามารถนำไปสู่การวิเคราะห์ยืนยัน (confirmatory analysis) ต่อไปได้

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

  • การวิเคราะห์ตะกร้าสินค้า (Market basket analysis): การระบุว่าผลิตภัณฑ์ใดมักถูกซื้อร่วมกันเพื่อนำทางการจัดวางสินค้าและการส่งเสริมการขาย
  • การแนะนำสินค้าในอีคอมเมิร์ซ: การสร้างคำแนะนำ 'ลูกค้าที่ซื้อ X ก็มักจะซื้อ Y ด้วย'
  • การค้นหาภาวะโรคร่วมทางคลินิก (Clinical co-morbidity discovery): การค้นหาชุดของการวินิจฉัย ยา หรืออาการที่ปรากฏร่วมกันในบันทึกผู้ป่วย
  • ชีวสารสนเทศ (Bioinformatics): การตรวจจับยีนที่แสดงออกร่วมกัน (co-expressed genes) หรือความแปรผันทางพันธุกรรมที่ปรากฏร่วมกันในกลุ่มตัวอย่าง
  • การทำเหมืองการใช้งานเว็บ (Web usage mining): การค้นหารูปแบบลำดับการคลิก (clickstream patterns) และลำดับการนำทางบนเว็บไซต์ที่พบบ่อย
  • การวิจัยสำรวจและพฤติกรรม: การค้นหาชุดของรายการในแบบสอบถามหรือพฤติกรรมที่ปรากฏร่วมกันในกลุ่มผู้ตอบแบบสอบถาม

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

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

1

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

2

ชุดรายการทั้งหมด (itemsets) ที่มีความถี่ในฐานข้อมูลธุรกรรมตรงตามเกณฑ์การสนับสนุนขั้นต่ำ (minimum support threshold) ที่ผู้ใช้กำหนด จะถูกระบุ หลักการ Apriori — ชุดย่อยใดๆ ของชุดรายการที่พบบ่อยก็เป็นชุดรายการที่พบบ่อยเช่นกัน — ช่วยลดปริภูมิการค้นหาแบบผสม (combinatorial search space) ลงอย่างมาก ทำให้การแจงนับสามารถจัดการได้แม้ในแคตตาล็อกขนาดใหญ่

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

สำหรับชุดรายการที่พบบ่อยแต่ละชุด การแบ่งแยกที่เป็นไปได้ทั้งหมดระหว่างส่วนหน้า (antecedent) และส่วนหลัง (consequent) (X → Y โดยที่ X และ Y เป็นเซตย่อยที่ไม่ซ้ำกันและไม่ว่างเปล่า) จะถูกสร้างขึ้นเป็นกฎผู้สมัคร (candidate rules) จำนวนผู้สมัครอาจมีมาก ดังนั้นขั้นตอนการกรอง (filtering) ที่ตามมาจึงมีความสำคัญ

สูตร
X \Rightarrow Y, \quad X \cap Y = \emptyset
4

กฎผู้สมัครแต่ละรายการจะถูกประเมินด้วยค่าความเชื่อมั่น (confidence): ความน่าจะเป็นแบบมีเงื่อนไขที่ Y ปรากฏเมื่อ X ปรากฏอยู่ จะเก็บไว้เฉพาะกฎที่เกินเกณฑ์ความเชื่อมั่นขั้นต่ำ ซึ่งเป็นการกรองส่วนหน้า (antecedent) ที่ทำนายส่วนหลัง (consequent) ได้ดีกว่าอัตราพื้นฐานเพียงเล็กน้อย

สูตร
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}
5

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

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

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

  • การตั้งค่า minimum support ต่ำเกินไป ซึ่งทำให้ผลลัพธ์เต็มไปด้วยกฎที่ผิดพลาดและมีความถี่ต่ำซึ่งไม่สามารถสรุปผลได้ทั่วไป
  • การละเลยค่า lift และการรายงานกฎที่มีความเชื่อมั่นสูงทั้งหมด ซึ่งหลายกฎอาจเป็นเพียงการสะท้อนรายการที่มีอัตราพื้นฐานสูง
  • การปฏิบัติต่อกฎที่ค้นพบเสมือนว่าเป็นสาเหตุโดยไม่มีการตรวจสอบเพิ่มเติม (เช่น สับสนว่า 'เบียร์และผ้าอ้อมปรากฏร่วมกัน' กับ 'เบียร์เป็นสาเหตุของการซื้อผ้าอ้อม')
  • การใช้กฎความสัมพันธ์กับข้อมูลต่อเนื่องโดยไม่มีการแบ่งกลุ่มที่มีหลักการ ทำให้เกิดกฎที่ขึ้นอยู่กับขอบเขตของกลุ่ม (bin boundaries) ที่ไม่แน่นอนโดยสิ้นเชิง
  • การมองข้ามข้อกังวลเกี่ยวกับการเปรียบเทียบหลายครั้ง (multiple-comparison concerns) เมื่อมีการสร้างกฎหลายพันรายการและมีการเน้นเฉพาะบางรายการ

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

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

ไม่มีกฎสากล เริ่มต้นด้วยการสำรวจการกระจายตัวของ support ของรายการแต่ละรายการ จากนั้นกำหนด minimum support ให้ต่ำพอที่จะครอบคลุมรูปแบบที่น่าสนใจ แต่สูงพอที่จะรับประกันว่าชุดรายการปรากฏในธุรกรรมจำนวนที่สมเหตุสมผลเป็นอย่างน้อย ค่า minimum confidence ที่ 0.6–0.8 เป็นช่วงเริ่มต้นทั่วไป แต่ความรู้เฉพาะทางและลำดับชั้นตามค่า lift ควรเป็นแนวทางในการเลือกขั้นสุดท้าย

ความแตกต่างระหว่าง confidence และ lift คืออะไร และฉันควรให้ความสำคัญกับอะไรมากกว่ากัน?

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

สามารถใช้กฎความสัมพันธ์สำหรับการทำนายได้หรือไม่?

โดยหลักแล้วกฎเหล่านี้มีลักษณะเชิงพรรณนาและสำรวจมากกว่าเชิงทำนาย แม้ว่าจะเป็นไปได้ที่จะใช้กฎที่มีส่วนหลัง (consequent) คงที่ (รายการเป้าหมายเดียว) สำหรับการจำแนกประเภท — เทคนิคที่เรียกว่า associative classification — แต่การทำเหมืองกฎความสัมพันธ์แบบมาตรฐานไม่ได้ปรับฟังก์ชันการสูญเสียเชิงทำนาย (predictive loss function) ให้เหมาะสม และไม่ควรใช้แทนโมเดลที่มีผู้สอนเมื่อมีป้ายกำกับผลลัพธ์อยู่

ชุดข้อมูลของฉันมีตัวแปรต่อเนื่อง ฉันยังสามารถใช้กฎความสัมพันธ์ได้หรือไม่?

ได้หลังจากแบ่งกลุ่มเท่านั้น ตัวแปรต่อเนื่องต้องถูกแบ่งเป็นช่วงๆ (เช่น กลุ่มอายุ, ควินไทล์) ก่อนที่จะเข้ารหัสเป็นรายการไบนารี การเลือกขอบเขตของกลุ่มส่งผลกระทบอย่างมากต่อกฎที่จะปรากฏ ดังนั้นการตัดสินใจแบ่งกลุ่มควรมีแรงจูงใจทางทฤษฎีและรายงานอย่างโปร่งใส

กฎความสัมพันธ์แตกต่างจากการวิเคราะห์สหสัมพันธ์ (correlation analysis) อย่างไร?

สหสัมพันธ์ (เช่น Pearson's r) วัดความสัมพันธ์เชิงเส้นระหว่างตัวแปรต่อเนื่องสองตัว กฎความสัมพันธ์จะค้นหารูปแบบการปรากฏร่วมกันระหว่างชุดของรายการไบนารี — ขนาดการผสมใดๆ — ในข้อมูลธุรกรรม ตัวชี้วัด (support, confidence, lift) ใช้ความถี่เป็นฐานมากกว่าโมเมนต์ (moment-based) และผลลัพธ์คือชุดของกฎ IF–THEN ที่มนุษย์อ่านได้ แทนที่จะเป็นค่าสัมประสิทธิ์ตัวเลขเดียว

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

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

  1. Agrawal, R., Imielinski, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 207–216.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2018). Introduction to Data Mining (2nd ed., Ch. 5). Pearson.

    ISBN: 978-0-13-312890-1
    คัดลอกแล้ว