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

การทำเหมืองกฎความสัมพันธ์ (Association Rule Mining) (Apriori)

ผู้เสนอ
Rakesh Agrawal & Ramakrishnan Srikant
ปี
1994
ประเภท
Unsupervised pattern discovery algorithm
กลุ่มวิธี
Pattern mining

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

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

ใช้ทำอะไร?

การทำเหมืองกฎความสัมพันธ์ (Association Rule Mining) เป็นเทคนิคการทำเหมืองข้อมูลแบบไม่มีผู้สอน (unsupervised data-mining technique) ที่ค้นหารูปแบบการปรากฏร่วมกันของรายการต่างๆ ในชุดข้อมูลธุรกรรม (transactional datasets) โดยพื้นฐานแล้ว เทคนิคนี้ถูกนำเสนออย่างเป็นทางการโดย Agrawal, Imieliński, และ Swami ในปี 1993 และได้รับการปรับปรุงด้วยอัลกอริทึม Apriori ที่เป็นหลักโดย Agrawal และ Srikant ในปี 1994 โดยมีเป้าหมายเพื่อระบุ กฎในรูปแบบ X ⇒ Y ซึ่งหมายความว่าธุรกรรมที่มีเซตรายการ X มักจะมีเซตรายการ Y ด้วย โดยกฎเหล่านี้จะถูกวัดค่าด้วยความถี่ (support) ความเชื่อมั่น (confidence) และการยกขึ้น (lift)

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

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

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

บทความพื้นฐานโดย Agrawal, Imieliński, และ Swami (1993) ได้กำหนดปัญหาเรื่องกฎความสัมพันธ์ในบริบทของข้อมูลธุรกรรมซูเปอร์มาร์เก็ต บทความ VLDB ปี 1994 ของ Agrawal และ Srikant ได้นำเสนออัลกอริทึม Apriori และกลยุทธ์การตัดแต่งที่มีประสิทธิภาพ ทำให้การทำเหมืองข้อมูลขนาดใหญ่เป็นไปได้จริง งานวิจัยต่อมาได้พัฒนา FP-Growth (Han et al., 2000) ซึ่งหลีกเลี่ยงการสร้างผู้สมัครโดยสิ้นเชิง และ ECLAT ซึ่งทำการทำเหมืองในรูปแบบข้อมูลแนวตั้ง (vertical data format) ซึ่งเป็นการสร้างตระกูลอัลกอริทึมที่หลากหลายซึ่งปัจจุบันเป็นหัวใจสำคัญของหลักสูตรการทำเหมืองข้อมูล

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

การทำเหมืองกฎความสัมพันธ์เหมาะสำหรับชุดข้อมูลธุรกรรมขนาดใหญ่ที่เป้าหมายคือการค้นหารูปแบบการปรากฏร่วมกันโดยไม่มีตัวแปรเป้าหมายที่กำหนดไว้ล่วงหน้า โดยสมมติว่ารายการต่างๆ เป็นแบบไบนารี (มี/ไม่มี) ต่อธุรกรรม เหมาะสำหรับการวิเคราะห์ตะกร้าสินค้า (market basket analysis) ระบบแนะนำ (recommendation systems) การวิเคราะห์เส้นทางการคลิกบนเว็บ (web clickstream analysis) และการค้นหาการวินิจฉัยร่วมทางการแพทย์ (medical co-diagnosis discovery) ไม่เหมาะสำหรับข้อมูลต่อเนื่องหรือข้อมูลเชิงอันดับ (ordinal data) เว้นแต่จะถูกแบ่งกลุ่มก่อน (pre-discretized) สำหรับชุดข้อมูลที่มีมิติสูงมาก (พื้นที่ผู้สมัครแบบทวีคูณ) หรือเมื่อต้องการการอนุมานเชิงสาเหตุ (causal inference) มากกว่าการอนุมานเชิงความสัมพันธ์ (associative inference) ทางเลือกอื่น ได้แก่ FP-Growth สำหรับการแจงนับเซตรายการที่พบบ่อยที่เร็วกว่า และการทำเหมืองลำดับ (sequence mining) เมื่อลำดับเวลามีความสำคัญ

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

  • พื้นที่ผู้สมัครแบบทวีคูณ: จำนวนกฎเพิ่มขึ้นแบบผสมผสานกับจำนวนรายการที่แตกต่างกัน
  • กรอบงาน support–confidence อาจให้กฎที่ทำให้เข้าใจผิดได้เมื่ออัตราพื้นฐานของรายการแตกต่างกันอย่างมาก (จำเป็นต้องมีการปรับ lift)
  • แบบจำลองธุรกรรมแบบไบนารีต้องการการแบ่งกลุ่มตัวแปรต่อเนื่อง ซึ่งนำไปสู่การสูญเสียข้อมูล
  • การตั้งค่าเกณฑ์ support ขั้นต่ำที่สูงเกินไปจะทำให้พลาดกฎที่มีค่าน้อยแต่มีค่า; การตั้งค่าเกณฑ์ต่ำเกินไปจะสร้างกฎเล็กน้อยนับพัน

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

จุดแข็ง

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

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

  • ภาคค้าปลีก: การจัดวางผลิตภัณฑ์และการแนะนำการขายพ่วง (cross-selling) จากบันทึกธุรกรรม ณ จุดขาย (point-of-sale transaction logs)
  • ภาคสุขภาพ: การวิเคราะห์การปรากฏร่วมกันของการวินิจฉัย ขั้นตอน หรือยา ในเวชระเบียนอิเล็กทรอนิกส์ (electronic health records)
  • การวิเคราะห์เว็บ: การค้นหารูปแบบเส้นทางการคลิกเพื่อแนะนำหน้าเว็บและการปรับปรุงการนำทาง
  • ชีวสารสนเทศ: การระบุชุดยีนที่แสดงออกร่วมกัน (co-expressed gene sets) และลวดลายการปฏิสัมพันธ์ของโปรตีน (protein interaction motifs)
  • ความปลอดภัยทางไซเบอร์: การตรวจจับเหตุการณ์เครือข่ายที่สัมพันธ์กันซึ่งบ่งชี้ถึงรูปแบบการบุกรุก

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

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

1

อัลกอริทึมจะสแกนฐานข้อมูลธุรกรรม D เพื่อเพื่อนับจำนวนครั้งที่เซตรายการ X ปรากฏ เซตรายการจะถูกประกาศว่าพบบ่อย (frequent) และถูกจัดเก็บไว้ใน L_k ก็ต่อเมื่อความถี่ (support) ของมัน (คือสัดส่วนของธุรกรรมที่มีเซตรายการนั้น) เท่ากับหรือสูงกว่าเกณฑ์ความถี่ขั้นต่ำที่ผู้ใช้กำหนด σ_min กระบวนการเริ่มต้นด้วยรายการเดี่ยวๆ (k=1) และสร้างชุดผู้สมัคร (candidate sets) ที่ใหญ่ขึ้นตามลำดับ

สูตร
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}
2

คุณสมบัติการต่อต้านความเป็นโมโนโทน (anti-monotonicity property) ของความถี่ระบุว่าเซตย่อยใดๆ ของเซตรายการที่พบบ่อยจะต้องเป็นเซตที่พบบ่อยด้วยเช่นกัน Apriori ใช้ประโยชน์จากคุณสมบัตินี้โดยการตัดเซตรายการ k รายการ (candidate k-itemset) ทุกชุดที่เซตย่อย (k-1) ของมันไม่ได้อยู่ในชุดที่ผ่านการตรวจสอบแล้ว L_{k-1} ทั้งหมด ซึ่งช่วยลดพื้นที่การค้นหาได้อย่างมาก และหลีกเลี่ยงการสแกนฐานข้อมูลที่มีค่าใช้จ่ายสูงสำหรับเซตรายการที่อาจไม่พบบ่อย

สูตร
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_k
3

จากเซตรายการที่พบบ่อยแต่ละชุด X ∪ Y อัลกอริทึมจะสร้างกฎ X ⇒ Y โดยที่ X และ Y เป็นเซตย่อยที่ไม่ทับซ้อนกัน กฎจะถูกเก็บไว้ก็ต่อเมื่อความเชื่อมั่น (confidence) ของมัน ซึ่งคือความน่าจะเป็นแบบมีเงื่อนไขของ Y เมื่อกำหนด X คำนวณได้จาก support(X ∪ Y) / support(X) เท่ากับหรือสูงกว่าเกณฑ์ความเชื่อมั่นขั้นต่ำ γ_min ขั้นตอนนี้จะแปลงการปรากฏร่วมกันของรายการดิบให้เป็นข้อความคาดการณ์แบบมีทิศทาง

สูตร
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}
4

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

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

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

  • การตั้งค่า support ขั้นต่ำต่ำเกินไปจะทำให้ผู้ทำการวิเคราะห์ท่วมท้นไปด้วยกฎที่ผิดพลาด การเลือกเกณฑ์ต้องอาศัยความรู้เฉพาะทางหรือการตรวจสอบไขว้ (cross-validation)
  • การสับสนระหว่างความสัมพันธ์ทางสถิติกับความเป็นสาเหตุ: ค่า lift ที่สูงไม่ได้หมายความว่า X ทำให้เกิด Y
  • การละเลยการกระจายความถี่ของรายการ: รายการทั่วไปมีอิทธิพลต่อกฎและเบียดบังความสัมพันธ์ของรายการที่หายากที่มีความหมาย
  • การพิจารณา confidence เพียงอย่างเดียวเป็นตัวชี้วัดคุณภาพ; กฎที่มี confidence สูงแต่ lift ต่ำอาจทำงานได้ไม่ดีไปกว่าการสุ่ม

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

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

Support วัดว่าเซตรายการปรากฏในชุดข้อมูลโดยรวมบ่อยเพียงใด Confidence วัดความน่าจะเป็นแบบมีเงื่อนไขของผลลัพธ์ (consequent) เมื่อกำหนดเงื่อนไขของเหตุ (antecedent) Lift ปรับค่า confidence ด้วยความถี่ตามขอบของผลลัพธ์ เพื่อเปิดเผยว่าการปรากฏร่วมกันนั้นเกินกว่าที่คาดหวังภายใต้ความเป็นอิสระหรือไม่ ทั้งสามเมตริกจำเป็นต้องใช้ร่วมกันเพื่อการประเมินกฎที่แข็งแกร่ง

อัลกอริทึม Apriori ลดต้นทุนการคำนวณได้อย่างไร?

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

เมื่อใดที่ควรใช้ FP-Growth แทน Apriori?

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

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

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

  1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

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