อัลกอริทึม Apriori: มันทำงานอย่างไร แบรนด์ต่างๆ สามารถใช้ Apriori Algorithm ได้อย่างไร?

เผยแพร่แล้ว: 2020-03-26

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

อัลกอริทึมนี้คืออะไร? และมันทำงานอย่างไร? คุณจะพบคำตอบสำหรับคำถามเหล่านี้ในบทความนี้ ก่อนอื่นเราจะมาดูกันว่าอัลกอริธึมนี้คืออะไรและทำงานอย่างไร

เอาล่ะ.

สารบัญ

อัลกอริทึม Apriori คืออะไร?

อัลกอริธึม apriori ให้ชุดรายการต่างๆ แก่คุณ พื้นฐานของมันคือคุณสมบัติ apriori ซึ่งเราสามารถอธิบายได้ดังนี้:

สมมติว่าชุดรายการที่คุณมีค่าสนับสนุนน้อยกว่าค่าสนับสนุนที่จำเป็น จากนั้น เซ็ตย่อยของเซ็ตไอเท็มนี้ก็จะมีค่าสนับสนุนน้อยกว่าที่ต้องการเช่นกัน ดังนั้น คุณจะไม่รวมมันในการคำนวณของคุณ และด้วยเหตุนี้ คุณจึงประหยัดพื้นที่ได้มาก

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

อ่านเพิ่มเติมได้ที่: ข้อกำหนดเบื้องต้นสำหรับวิทยาศาสตร์ข้อมูล เปลี่ยนแปลงไปตามกาลเวลาอย่างไร?

อัลกอริทึม Apriori ทำงานอย่างไร

อัลกอริทึม apriori สร้างกฎการเชื่อมโยงโดยใช้ชุดรายการบ่อย หลักการนั้นง่าย – เซ็ตย่อยของชุดรายการที่ใช้บ่อยก็จะเป็นชุดรายการที่ใช้บ่อยเช่นกัน ชุดไอเท็มที่มีค่าสนับสนุนมากกว่าค่าขีดจำกัดคือชุดไอเท็มที่ใช้บ่อย พิจารณาข้อมูลต่อไปนี้:

TID รายการ
T1 1 3 4
T2 2 3 5
T3 1 2 3 5
T4 2 5
T5 1 3 5

ในการทำซ้ำครั้งแรก สมมติว่าค่าสนับสนุนเป็นสอง และสร้างชุดรายการที่มีขนาด 1 ตอนนี้ คำนวณค่าสนับสนุนตามลำดับ เราจะทิ้งไอเทมที่มีค่าสนับสนุนต่ำกว่าค่าขั้นต่ำ ในตัวอย่างนี้ นั่นจะเป็นรายการที่สี่

C1 (ผลการทำซ้ำครั้งแรก)

ชุดไอเท็ม สนับสนุน
{1} 3
{2} 3
{3} 4
{4} 1
{5} 4

F1 (หลังจากเราทิ้ง {4})

ชุดไอเท็ม สนับสนุน
{1} 3
{2} 3
{3} 4
{5} 4

ในการทำซ้ำครั้งที่สอง เราจะรักษาขนาดของชุดไอเท็มสองชุด จากนั้นจึงคำนวณค่าการสนับสนุน เราจะใช้ชุดค่าผสมทั้งหมดของตาราง F1 ในการวนซ้ำนี้ เราจะลบชุดไอเท็มใด ๆ ที่มีค่าการสนับสนุนน้อยกว่าสอง

C2 (มีเฉพาะรายการใน F1)

ชุดไอเท็ม สนับสนุน
{1,2} 1
{1,3} 3
{1,5} 2
{2,3} 2
{2,5} 3
{3,5} 3

F2 (หลังจากที่เราลบรายการที่มีค่าสนับสนุนต่ำกว่า 2)

ชุดไอเท็ม สนับสนุน
{1,3} 3
{1,5} 2
{2,3} 2
{2,5} 3
{3,5} 3

ตอนนี้เราจะทำการตัดแต่งกิ่ง ในกรณีนี้ เราจะแบ่งชุดรายการของ C3 ออกเป็นชุดย่อย และลบชุดที่มีค่าสนับสนุนต่ำกว่าสองชุด

C3 (หลังจากเราทำการตัดแต่งกิ่ง)

ชุดไอเท็ม ใน F2?
{1,2,3}, {1,2}, {1,3}, {2,3} ไม่
{1,2,5} {1,2} {1,5} {2,5} ไม่
{1,3,5} {1,5} {1,3} {3,5} ใช่
{2,3,5} {2,3} {2,5} {3,5} ใช่

ในการทำซ้ำครั้งที่สาม เราจะยกเลิก {1,2,5} และ {1,2,3} เนื่องจากทั้งคู่มี {1,2} นี่คือผลกระทบหลักของอัลกอริทึม apriori

F3 (หลังจากเราทิ้ง {1,2,5} และ {1,2,3})

ชุดไอเท็ม สนับสนุน
{1,3,5} 2
{2,3,5} 2

ในการทำซ้ำครั้งที่สี่ เราจะใช้ชุดของ F3 เพื่อสร้าง C4 อย่างไรก็ตาม เนื่องจากค่าสนับสนุนของ C4 ต่ำกว่า 2 เราจะไม่ดำเนินการต่อและชุดรายการสุดท้ายคือ F3

C3

ชุดไอเท็ม สนับสนุน
{1,2,3,5} 1

เรามีชุดไอเท็มต่อไปนี้กับ F3:

สำหรับ I = {1,3,5} เซตย่อยที่เรามีคือ {5}, {3}, {1}, {3,5}, {1,5}, {1,3}

สำหรับ I = {2,3,5} เซตย่อยที่เรามีคือ {5}, {3}, {2}, {3,5}, {2,5}, {2,3}

ตอนนี้ เราจะสร้างและใช้กฎกับชุดไอเท็ม F3 เพื่อจุดประสงค์นั้น เราจะถือว่าค่าความเชื่อมั่นขั้นต่ำในปัจจุบันคือ 60% สำหรับเซตย่อย S ของ I นี่คือกฎที่เราส่งออก:

  • S -> (I,S) (หมายความว่า S แนะนำ IS)
  • ถ้า support(I) / support(S) >= min_conf value

ลองทำสิ่งนี้สำหรับเซตย่อยแรกที่เรามี นั่นคือ {1,3,5}

กฎข้อที่ 1: {1,3} -> ({1,3,5} – {1,3}) หมายถึง 1 & 3-> 5

ค่าความเชื่อมั่น = ค่าสนับสนุนของ (1,3,5) / ค่าสนับสนุนของ (1,3) = ⅔ = 66.66%

เนื่องจากผลลัพธ์สูงกว่า 60% เราจึงเลือกกฎข้อที่ 1

กฎข้อที่ 2: {1,5} -> {(1,3,5) – {1,5}) หมายถึง 1 & 5 -> 3

ค่าความเชื่อมั่น = มูลค่าสนับสนุนของ (1,3,5) / มูลค่าสนับสนุนของ (1,5) = 2/2 = 100%

เนื่องจากผลลัพธ์สูงกว่า 60% เราจึงเลือกกฎข้อที่ 2

กฎข้อที่ 3: {3} -> ({1,3,5} – {3}) หมายถึง 3 -> 1 & 5

ค่าความเชื่อมั่น = มูลค่าสนับสนุนของ (1,3,5) / มูลค่าสนับสนุนของ (3) = 2/4 = 50%

เนื่องจากผลลัพธ์ต่ำกว่า 60% เราจึงปฏิเสธกฎข้อที่ 3

รับ หลักสูตรวิทยาศาสตร์ข้อมูล จากมหาวิทยาลัยชั้นนำของโลก เข้าร่วมโปรแกรม Executive PG, Advanced Certificate Programs หรือ Masters Programs ของเราเพื่อติดตามอาชีพของคุณอย่างรวดเร็ว

จากตัวอย่างข้างต้น คุณสามารถดูได้ว่าอัลกอริทึม Apriori สร้างและใช้กฎอย่างไร คุณสามารถทำตามขั้นตอนเหล่านี้สำหรับชุดไอเท็มที่สอง ({2,3,5}) ที่เรามี การลองใช้จะทำให้คุณมีประสบการณ์ที่ยอดเยี่ยมในการทำความเข้าใจว่าอัลกอริทึมยอมรับกฎเกณฑ์ใดและกฎเกณฑ์ใดที่ปฏิเสธ อัลกอริทึมยังคงเหมือนเดิมในที่อื่นๆ เช่น อัลกอริทึม Apriori Python

บทสรุป

หลังจากอ่านบทความนี้ เรามั่นใจว่าคุณคงคุ้นเคยกับอัลกอริทึมนี้และการประยุกต์ใช้งานเป็นอย่างดีแล้ว เนื่องจากมีการใช้ในระบบแนะนำ จึงได้รับความนิยมอย่างมากเช่นกัน

มีอัลกอริทึมที่มีประสิทธิภาพมากกว่าอัลกอริทึม Apriori หรือไม่?

อัลกอริทึม ECLAT (การทำคลัสเตอร์คลาสเทียบเท่าและ Lattice Traversal จากล่างขึ้นบน) พบว่ามีประโยชน์มากและเป็นที่นิยมสำหรับการขุดกฎการเชื่อมโยง ยิ่งไปกว่านั้น ยังเป็นที่รู้จักว่าเป็นอัลกอริธึมที่มีประสิทธิภาพและเร็วกว่าเมื่อเทียบกับอัลกอริธึม Apriori

อัลกอริทึม Apriori ทำงานในลักษณะแนวนอนโดยเลียนแบบการค้นหาแบบกว้างๆ ก่อนของกราฟ ในขณะที่อัลกอริทึม ECLAT ทำงานในลักษณะแนวตั้งโดยเลียนแบบการค้นหาเชิงลึกก่อนของกราฟ แนวทางแนวตั้งนี้เป็นเหตุผลเบื้องหลังความเร็วที่เร็วขึ้นและประสิทธิภาพที่ดีขึ้นของอัลกอริทึม ECLAT เมื่อเปรียบเทียบกับอัลกอริทึม Apriori

อัลกอริทึม Apriori มีประโยชน์สำหรับวัตถุประสงค์อะไร?

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

นอกจากนั้น อัลกอริธึมนี้ยังใช้ในภาคการดูแลสุขภาพเพื่อตรวจหาปฏิกิริยาไม่พึงประสงค์จากยา อัลกอริทึมสร้างกฎการเชื่อมโยงเพื่อกำหนดลักษณะเฉพาะของผู้ป่วยและยาที่อาจนำไปสู่ปฏิกิริยายาที่ไม่พึงประสงค์

ข้อดีและข้อเสียของอัลกอริทึม Apriori คืออะไร

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