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

การทำเหมืองชุดรายการที่พบบ่อยด้วย ECLAT

ผู้เสนอ
Mohammed J. Zaki
ปี
2000
ประเภท
Frequent-itemset mining algorithm (vertical format)
กลุ่มวิธี
Pattern mining

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

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

ใช้ทำอะไร?

ECLAT ซึ่งโมฮัมเหม็ด ซากี นำเสนอในปี 2000 ทำการขุดชุดรายการที่พบบ่อยโดยใช้การแสดงข้อมูลแบบแนวตั้ง: แทนที่จะสแกนธุรกรรม จะเก็บรายการของรหัสธุรกรรม (tidset) ที่มีรายการนั้นๆ และคำนวณความถี่ของชุดรายการใดๆ โดยการตัดกันของ tidsets วิธีการแบบเจาะลึกที่ใช้การตัดกันนี้รวดเร็วและประหยัดหน่วยความจำ ซึ่งเป็นทางเลือกแทนการสแกนแนวนอนของ Apriori และโครงสร้างต้นไม้ของ FP-Growth

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

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

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

โมฮัมเหม็ด ซากี นำเสนอ ECLAT และกระบวนทัศน์การทำเหมืองแบบแนวตั้งในผลงานที่สรุปในบทความ IEEE TKDE ปี 2000 ของเขาเกี่ยวกับการทำเหมืองความสัมพันธ์ที่ปรับขนาดได้ ต่อมาได้ปรับปรุงด้วย diffsets (dECLAT) มันเข้าร่วมกับ Apriori (1994, การสร้างผู้สมัครแนวนอน) และ FP-Growth (2000, ใช้โครงสร้างต้นไม้) ในฐานะหนึ่งในสามตระกูลหลักของอัลกอริทึมชุดรายการที่พบบ่อย โดยแต่ละตระกูลมีการแลกเปลี่ยนระหว่างการสแกน หน่วยความจำ และความหนาแน่นของข้อมูลที่แตกต่างกัน ECLAT ยังคงเป็นตัวเลือกมาตรฐานในชุดเครื่องมือขุดข้อมูล

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

ใช้ ECLAT สำหรับการทำเหมืองชุดรายการที่พบบ่อยเมื่อแนวทางแบบแนวตั้งที่ใช้การตัดกันเหมาะสมกับข้อมูล - มักจะรวดเร็วมากบนชุดข้อมูลที่หนาแน่นและหลีกเลี่ยงการสแกนฐานข้อมูลซ้ำ ทำให้เป็นทางเลือกที่แข็งแกร่งแทน Apriori และคู่แข่งกับ FP-Growth มันโดดเด่นเมื่อ tidsets มีขนาดปานกลางและพอดีกับหน่วยความจำ และรูปแบบ diffset จัดการกับข้อมูลหนาแน่นได้ดี ข้อเสีย: tidsets สำหรับรายการที่พบบ่อยอาจมีขนาดใหญ่และใช้หน่วยความจำมากบนชุดข้อมูลขนาดใหญ่ที่เบาบาง การตัดกันระหว่างกลางจะเพิ่มค่าใช้จ่าย และเช่นเดียวกับการทำเหมืองที่ใช้ความถี่ทั้งหมด นี่เป็นเพียงขั้นตอนแรก ชุดกฎความสัมพันธ์ที่มีความเชื่อมั่น/ค่ายกจะถูกสร้างขึ้นหลังจากนั้น เลือกระหว่าง ECLAT, FP-Growth และ Apriori โดยพิจารณาจากความหนาแน่นของข้อมูลและหน่วยความจำ

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

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

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

จุดแข็ง

  • ความถี่คำนวณโดยการตัดกันของ tidsets ที่รวดเร็ว - ไม่มีการสแกนฐานข้อมูลซ้ำ
  • การค้นหาแบบเจาะลึกพร้อมชั้นสมมูลคำนำหน้าจะนำงานกลับมาใช้ใหม่และจำกัดขอบเขตหน่วยความจำ
  • มักจะมีประสิทธิภาพมากบนชุดข้อมูลที่หนาแน่น แข่งขันกับ FP-Growth
  • การปรับปรุง diffset ช่วยลดต้นทุนหน่วยความจำและการตัดกันได้อีก

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

  • การทำเหมืองความสัมพันธ์ของตะกร้าสินค้าและร้านค้าปลีก
  • การวิเคราะห์การปรากฏร่วมกันของเว็บและคลิกสตรีม
  • การค้นพบการปรากฏร่วมกันที่พบบ่อยในชีวสารสนเทศ
  • งานชุดรายการที่พบบ่อยใดๆ ที่สนับสนุนแนวทางแบบแนวตั้งที่ใช้การตัดกัน
  • ชุดข้อมูลธุรกรรมที่หนาแน่นซึ่ง diffset ECLAT ทำงานได้ดีเยี่ยม

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

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

1

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

สูตร
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

ความถี่ของชุดรายการคือจำนวนสมาชิกของการตัดกันของ tidsets ของรายการ - จำนวนธุรกรรมที่มีทั้งหมด การนับกลายเป็นการตัดกัน ซึ่งรวดเร็ว และรายการเดี่ยวที่พบบ่อย (รายการที่มี tidset ใหญ่พอ) จะเป็นจุดเริ่มต้นของการค้นหา

สูตร
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

ชุดรายการจะถูกขยายโดยการตัดกันของ tidsets: tidset ของ X ∪ {y} คือการตัดกันของ tidsets ของ X และ {y} ECLAT สำรวจแลตทิซของชุดรายการแบบเจาะลึกภายในชั้นสมมูล (ชุดรายการที่มีคำนำหน้าเหมือนกัน) ดังนั้นการตัดกันจึงถูกนำกลับมาใช้ใหม่และการค้นหายังคงอยู่ในขอบเขตท้องถิ่น

สูตร
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

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

สูตร
\text{keep extensions with } \text{support} \ge \text{minsup}

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

  • การทำเหมืองข้อมูลขนาดใหญ่ที่เบาบางมากซึ่ง tidsets ทำให้หน่วยความจำเต็ม - พิจารณา diffsets หรือ FP-Growth
  • การตั้งค่าความถี่ขั้นต่ำต่ำเกินไปและสร้างชุดรายการจำนวนมากที่ไม่สามารถจัดการได้
  • การสับสนระหว่างชุดรายการที่พบบ่อยกับกฎความสัมพันธ์ (กฎเป็นขั้นตอนที่แยกต่างหาก)
  • การละเลยรูปแบบ diffset บนข้อมูลหนาแน่นซึ่งช่วยได้อย่างมาก

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

ECLAT แตกต่างจาก Apriori และ FP-Growth อย่างไร?

ทั้งสามหาชุดรายการที่พบบ่อย Apriori ใช้รูปแบบแนวนอนพร้อมการสร้างผู้สมัครและการสแกนหลายครั้ง; FP-Growth บีบอัดข้อมูลเป็นโครงสร้างต้นไม้และขุดค้นแบบเวียนซ้ำ; ECLAT ใช้รูปแบบ tidset แนวตั้งและคำนวณความถี่โดยการตัดกันของรายการรหัสธุรกรรมแบบเจาะลึก ECLAT และ FP-Growth หลีกเลี่ยงการสแกนซ้ำของ Apriori

tidset คืออะไร?

tidset (เซตของรหัสธุรกรรม) คือรายการของธุรกรรมที่มีรายการหรือชุดรายการที่กำหนด ECLAT เก็บสิ่งเหล่านี้ในแนวตั้งและคำนวณความถี่ของชุดรายการเป็นขนาดของการตัดกันของ tidsets ของรายการ ทำให้การนับกลายเป็นการตัดกันของเซต

diffsets คืออะไร?

Diffsets เก็บเฉพาะส่วนต่างระหว่าง tidset ของชุดรายการกับ tidset ของชุดหลัก แทนที่จะเป็น tidset เต็ม บนข้อมูลหนาแน่น สิ่งนี้ช่วยลดหน่วยความจำและต้นทุนการตัดกันได้อย่างมาก ทำให้รูปแบบ dECLAT มีข้อได้เปรียบด้านประสิทธิภาพที่สำคัญ

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

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

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว