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 บ่งชี้ว่ารายการนั้นปรากฏอยู่ การแสดงผลที่เบาบางและกว้างนี้เป็นรูปแบบอินพุตหลัก รายการที่ไม่ใช่ไบนารีหรือเชิงปริมาณจะต้องถูกแบ่งกลุ่ม (discretized) ก่อนขั้นตอนนี้
ชุดรายการทั้งหมด (itemsets) ที่มีความถี่ในฐานข้อมูลธุรกรรมตรงตามเกณฑ์การสนับสนุนขั้นต่ำ (minimum support threshold) ที่ผู้ใช้กำหนด จะถูกระบุ หลักการ Apriori — ชุดย่อยใดๆ ของชุดรายการที่พบบ่อยก็เป็นชุดรายการที่พบบ่อยเช่นกัน — ช่วยลดปริภูมิการค้นหาแบบผสม (combinatorial search space) ลงอย่างมาก ทำให้การแจงนับสามารถจัดการได้แม้ในแคตตาล็อกขนาดใหญ่
สูตร
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|} \geq \text{min\_sup}สำหรับชุดรายการที่พบบ่อยแต่ละชุด การแบ่งแยกที่เป็นไปได้ทั้งหมดระหว่างส่วนหน้า (antecedent) และส่วนหลัง (consequent) (X → Y โดยที่ X และ Y เป็นเซตย่อยที่ไม่ซ้ำกันและไม่ว่างเปล่า) จะถูกสร้างขึ้นเป็นกฎผู้สมัคร (candidate rules) จำนวนผู้สมัครอาจมีมาก ดังนั้นขั้นตอนการกรอง (filtering) ที่ตามมาจึงมีความสำคัญ
สูตร
X \Rightarrow Y, \quad X \cap Y = \emptyset
กฎผู้สมัครแต่ละรายการจะถูกประเมินด้วยค่าความเชื่อมั่น (confidence): ความน่าจะเป็นแบบมีเงื่อนไขที่ Y ปรากฏเมื่อ X ปรากฏอยู่ จะเก็บไว้เฉพาะกฎที่เกินเกณฑ์ความเชื่อมั่นขั้นต่ำ ซึ่งเป็นการกรองส่วนหน้า (antecedent) ที่ทำนายส่วนหลัง (consequent) ได้ดีกว่าอัตราพื้นฐานเพียงเล็กน้อย
สูตร
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}กฎที่เก็บไว้จะถูกจัดอันดับตามค่า 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 ที่มนุษย์อ่านได้ แทนที่จะเป็นค่าสัมประสิทธิ์ตัวเลขเดียว
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
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คัดลอกแล้ว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คัดลอกแล้ว