การทำเหมืองชุดรายการที่พบบ่อยด้วย 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 ทำงานได้ดีเยี่ยม
วิธีการทำงาน
วิธีการทำงาน
ฐานข้อมูลจะถูกแปลงเป็นรูปแบบแนวตั้งเพียงครั้งเดียว: แต่ละรายการจะจับคู่กับ tidset ของมัน ซึ่งเป็นเซตของรหัสธุรกรรมที่ปรากฏอยู่ นี่คือโครงสร้างข้อมูลหลัก - งานที่ตามมาทั้งหมดคือการดำเนินการกับเซตบน tidsets ไม่ใช่การผ่านฐานข้อมูลต้นฉบับ
สูตร
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}ความถี่ของชุดรายการคือจำนวนสมาชิกของการตัดกันของ tidsets ของรายการ - จำนวนธุรกรรมที่มีทั้งหมด การนับกลายเป็นการตัดกัน ซึ่งรวดเร็ว และรายการเดี่ยวที่พบบ่อย (รายการที่มี tidset ใหญ่พอ) จะเป็นจุดเริ่มต้นของการค้นหา
สูตร
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |ชุดรายการจะถูกขยายโดยการตัดกันของ tidsets: tidset ของ X ∪ {y} คือการตัดกันของ tidsets ของ X และ {y} ECLAT สำรวจแลตทิซของชุดรายการแบบเจาะลึกภายในชั้นสมมูล (ชุดรายการที่มีคำนำหน้าเหมือนกัน) ดังนั้นการตัดกันจึงถูกนำกลับมาใช้ใหม่และการค้นหายังคงอยู่ในขอบเขตท้องถิ่น
สูตร
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}ส่วนขยายจะถูกเก็บไว้ก็ต่อเมื่อ 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 มีข้อได้เปรียบด้านประสิทธิภาพที่สำคัญ
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว