Market Basket Analysis Tag - Big Data Institute

ข่าวและบทความที่เกี่ยวข้อง

All Market Basket Analysis

บทความ

Association Rule: การหา Frequent Itemsets ด้วย Apriori Algorithm

จากบทความที่ผ่านมาได้มีการกล่าวถึง การวิเคราะห์ตะกร้าสินค้า (Market Basket Analysis) ด้วยการสร้างกฎความสัมพันธ์ หรือ Association Rule ไปแล้ว พร้อมกับอธิบายถึงแนวคิดพื้นฐานที่ถูกใช้ใน Association Rule ได้แก่ Support, Confidence และ Lift หากใครยังไม่รู้จักคำเหล่านี้ว่าหมายถึงอะไร สามารถเข้าไปอ่านในบทความ มาทำความรู้จัก Association Rule: เครื่องมือเพื่อการวิเคราะห์ตะกร้าตลาด กัน! ได้เลย ในส่วนของบทความนี้จะเป็นภาคต่อที่จะพูดถึงหนึ่งในขั้นตอนวิธีในการสร้างกฎความสัมพันธ์ โดยวิธีการที่เป็นที่นิยม เป็นเทคนิคที่ชื่อว่า Apriori Algorithm นั่นเอง เริ่มต้นขอเกริ่นก่อนว่ากระบวนการในการหากฎความสัมพันธ์ (Association Rule Mining) นั้นสามารถแบ่งปัญหาออกเป็น 2 งานย่อยด้วยกัน ได้แก่ 1. Frequent Itemset Generationคือการหา itemsets ที่ผ่านเกณฑ์ minimum support ซึ่งจะเรียก itemsets เหล่านี้ว่าเป็น “Frequent Itemsets” 2. Rule Generationคือการหากฎความสัมพันธ์ที่มีค่า Confidence หรือ Lift สูง หรือที่เรียกว่า “Strong Rules” ซึ่งกฎเหล่านี้จะถูกสร้างมาจาก Frequent Itemsets ที่ได้มาจากขั้นตอนก่อนหน้า ในสองกระบวนการนี้ Apriori Algorithm จะเข้ามาเป็นส่วนหนึ่งในการช่วยเพิ่มประสิทธิภาพและความเร็วของการสร้างกฎความสัมพันธ์ ที่มีจำนวน items และ transactions จำนวนมาก สำหรับในบทความนี้จะขอโฟกัสไปที่การประยุกต์ใช้ Apriori Algorithm ในขั้นตอนการหา Frequent Itemsets กันก่อน จากบทความก่อนหน้าเราพอทราบมาแล้วว่า หากมีสินค้าอยู่ N ชิ้น จะมี itemsets ที่เป็นไปได้ถึง 2N – 1 แบบ ซึ่งจะเห็นว่าจำนวน itemsets มีการเพิ่มแบบ exponential ตามจำนวน items ที่เพิ่มขึ้น สมมติ ถ้าร้านเรามีสินค้าทั้งหมด 4 items ได้แก่ apple, banana, water และ bread จะสามารถสร้าง itemsets ที่เป็นไปได้ทั้งหมด 24-1 = 15 itemsets ที่ประกอบไปด้วย itemsets ที่มีสินค้าแค่ 1 ชิ้น จนถึง itemsets ที่มีสินค้าครบ 4 ชิ้น ดังรูปด้านล่าง ถ้าใช้วิธีการแบบ Brute Force สำหรับการหา Frequent Itemsets ซึ่งจะหมายถึงการไล่คำนวณค่า Support ของทุก Itemsets ที่เป็นไปได้ทั้งหมด หรือทุก Candidate Itemsets สำหรับการใช้งานจริงในร้านค้าซึ่งมีสินค้าและ Transactions จำนวนมากนั้นอาจจะไม่เป็นการดี เนื่องจากใช้เวลาและทรัพยากรในการประมวลผลค่อนข้างสูง (Computational Expensive and Time Consuming) ดังนั้น Apriori Algorithm จึงถูกพัฒนาขึ้นมาเพื่อแก้ปัญหานี้ เพื่อลดจำนวน itemsets ที่จำนำมาพิจารณาให้เหลือน้อยลง โดยใช้หลักการที่ว่า “ถ้า itemset ใดเกิดไม่บ่อย superset ทั้งหมดของ itemset นั้น ก็จะเกิดไม่บ่อยด้วยเช่นกัน” เพื่อให้เห็นภาพมากขึ้นขอยกตัวอย่าง โดยหากลองพิจารณารายการซื้อขายที่เกิดขึ้นในอดีต เราพบ {apple} ใน 5 ตะกร้า สินค้าอื่นที่จะถูกซื้อร่วมกับ apple จะต้องปรากฎใน 5 ตะกร้านี้ด้วยเช่นกัน เป็นไปไม่ได้เลยว่า เราจะพบ {apple, bread} คู่กันเกิน 5 ตะกร้า ดังนั้นถ้าพบว่า {apple} ไม่ใช่ frequent itemsets แล้ว {apple, สินค้าใดๆ} ก็จะไม่ใช่ frequent itemsets ด้วยเช่นกัน หมายความว่า เราสามารถตัด supersets ของ itemsets ที่ไม่ใช่ Frequent Itemset ออกจากการพิจารณาได้เลย ซึ่งในทางปฏิบัติ ทำให้เราลดจำนวน itemsets ที่ต้องพิจารณา จาก 2N – 1 รูปแบบ ลงได้จำนวนมาก มีผลให้การคำนวณทำได้เร็วขึ้นนั่นเอง จากภาพด้านบนเป็นตัวอย่างของการลดจำนวน itemsets ที่นำมาพิจารณาด้วยหลักการที่กล่าวไปข้างต้น โดยแสดงให้เห็นว่า หาก {apple} ถูกพิจารณาแล้วว่ามีค่า support ต่ำกว่าเกณฑ์ที่ตั้งไว้ ซึ่งจะถือว่า {apple} นั้นเป็น Infrequent Itemset ดังนั้นจะเห็นว่า itemsets ทั้งหมด ที่สร้างมาจาก {apple} จะไม่ถูกนำมาพิจารณาในการสร้าง Association Rule ต่อไปเพราะ Support ของ itemsets เหล่านี้ที่มี apple เป็นส่วนประกอบ จะน้อยกว่าหรือเท่ากับ support ของ {apple} ซึ่งจะมีค่า Support ที่ต่ำกว่าเกณฑ์ ซึ่งสามารถสรุปได้ว่า itemsets เหล่านี้จะถือว่าเป็น Infrequent Itemsets ด้วยทั้งสิ้น โดยจะเรียกวิธีการนี้ว่า “Support-Based Pruning” จะเห็นว่าวิธีการนี้จะช่วยลด itemsets ที่จะนำมาพิจารณาลงได้อย่างมากเลยทีเดียว ขั้นตอนของ Apriori Algorithm เพื่อหา Frequent Itemsets Step 0: เริ่มต้นจากการสร้าง itemsets ที่มีจำนวนสมาชิก 1 item ที่เป็นไปได้จาก items ทั้งหมด เช่น {apple} และ {egg} เป็นต้น ขั้นตอนนี้คือการสร้าง Candidate 1-itemsets (C1) ขึ้นมา Step 1: ทำการคัดเลือก Frequent Itemsets โดยพิจารณาค่า Support...

21 June 2021

บทความ

Big Data 101

มาทำความรู้จัก Association Rule: เครื่องมือเพื่อการวิเคราะห์ตะกร้าตลาด กัน!

[latexpage] เคยคิดดูไหมว่า “หากเราจะจัดชั้นวางของในห้างสรรพสินค้า จะวางอะไรไว้ใกล้กับอะไรดี”, “หากเรามี online shopping application เราจะแนะนำสินค้าอะไรต่อไปให้ลูกค้าดี” หรือ “หากเราต้องการจะทำโปรโมชั่นแนะนำสินค้า เราจะแนะนำสินค้าอะไรคู่กันดี” Association rule หรือ กฎความสัมพันธ์ เป็นหนึ่งในเครื่องมือเพื่อการวิเคราะห์ตะกร้าตลาด (Market basket analysis) ที่สามารถเข้ามาช่วยตอบคำถามเหล่านี้ได้ Market Basket Analysis หรือ การวิเคราะห์ตะกร้าตลาด เป็นการวิเคราะห์เพื่อค้นหากลุ่มสิ่งของที่น่าจะปรากฎร่วมกันในตะกร้าซื้อขาย โดยผลลัพธ์ที่ได้จะแสดงในรูปของกฎที่บ่งบอกถึงความเป็นไปได้ในการซื้อสินค้าต่าง ๆ ร่วมกัน ในบทความนี้ เราจะมาทำความเข้าใจคำศัพท์ที่สำคัญ และตัววัดประสิทธิภาพที่ใช้กับกฎของความสัมพันธ์กันค่ะ สมมติว่าในร้านค้าของเรามีสินค้าอยู่ 5 ชนิด ได้แก่ ขนมปัง ไข่ เนย น้ำเปล่า และข้าว โดยมีการซื้อขายทั้งหมด 4 ตะกร้า ดังต่อไปนี้ ซึ่งสามารถเขียนแทนด้วยตารางข้างล่าง สินค้า ตะกร้าที่ (Transaction ID) 1 2 3 4 ขนมปัง 1 1 1 ไข่ 1 1 เนย 1 1 น้ำเปล่า 1 1 1 ข้าว 1 คำศัพท์สำคัญ (Key terms) เป้าหมายของการทำ Market basket analysis คือ เพื่อค้นหากลุ่มของสินค้าที่มีความสัมพันธ์กัน จึงเป็นการดีหากเราสามารถแทนคำศัพท์สำคัญที่เกี่ยวข้องนี้ (กลุ่มของสินค้า และ ความสัมพันธ์ระหว่างกลุ่มของสินค้า) ด้วยสัญลักษณ์ทางคณิตศาสตร์ ตัววัดประสิทธิภาพ (Metrics) จะเห็นได้ว่าสินค้าที่มีในร้านเพียงไม่กี่ชนิด สามารถสร้าง itemsets และ rules ได้หลากหลายรูปแบบ (สินค้าเพียง 5 ชนิดสามารถสร้าง itemsets ได้ถึง 31 รูปแบบ และสร้าง rules ได้ถึง 180 รูปแบบ) อันที่จริงจำนวนรูปแบบของ itemsets และ rules ที่เป็นไปได้ทั้งหมดเติบโตแบบ exponential เมื่อเทียบกับจำนวนสินค้าภายในร้านเลยทีเดียว [Tan, Steinbach & Kumar, 2006] อย่างไรก็ตาม ไม่ใช่ว่าทุกรูปแบบของ itemsets หรือ rules ที่มีความสำคัญ ตัววัดประสิทธิภาพที่ใช้ในการค้นหาความสัมพันธ์ (association mining) ที่มีความสำคัญจริง ๆ มีอยู่ด้วยกัน 3 ตัว 1 Support Support เป็นตัววัดประสิทธิภาพสำหรับ itemset โดยเป็นตัวเลขที่แสดงสัดส่วนของจำนวนตะกร้าการซื้อขายที่มี itemset ต่อจำนวนตะกร้าการซื้อขายทั้งหมด หรือกล่าวได้ว่า “มีการซื้อขายที่มี itemset อยู่ด้วยเป็นสัดส่วนเท่าไหร่ ในการซื้อขายทั้งหมด” หากเขียนในรูปแบบสมการทางคณิตศาสตร์จะได้ว่า Support(Itemset) $=$ จำนวนตะกร้าซื้อขายที่มี itemset จำนวนตะกร้าซื้อขายทั้งหมด ในตัวอย่างร้านค้าของเรา หากพิจารณา Itemset = {ขนมปัง} จะได้ว่า Support({ขนมปัง}) = 3/4 = 0.75 Support เป็นปราการด่านแรกที่ช่วยตัดจำนวน rules ที่จะเกิดขึ้นให้น้อยลง โดยจะคัดเลือกเฉพาะ itemsetที่มีค่า support มากกว่า minimum support threshold (ตัวเลขนี้ขึ้นอยู่กับโจทย์ปัญหาและประสบการณ์ของนักวิทยาศาสตร์ข้อมูล) ทั้งนี้ เนื่องจาก การที่กลุ่มของสินค้า (itemset) ใด ๆ มีสัดส่วนการปรากฏตัวในตะกร้าซื้อขายน้อยเกินไป ทำให้เรามีข้อมูลไม่เพียงพอที่จะสรุปความสัมพันธ์ของสินค้าภายในกลุ่มนั้น ๆ จึงตัดกลุ่มของสินค้า (itemset) นั้นออกจากการพิจารณาที่จะนำไปสร้าง rules จากกรณีตัวอย่าง หากเรากำหนด minimum support threshold = 0.5 และคัดเลือกเฉพาะ itemsets ที่มีค่า support มากกว่าหรือเท่ากับค่านั้น พิจารณากรณี itemset ที่มีสมาชิก 1 ตัว ข้าวจะถูกตัดออกไป เนื่องจาก support({ข้าว}) = 0.25 ซึ่งน้อยกว่า 0.5 สินค้า ตะกร้าที่ (Transaction ID) Support 1 2 3 4 ขนมปัง 1 1 1 3/4 = 0.75 ไข่ 1 1 2/4 = 0.5 เนย 1 1 2/4 = 0.5 น้ำเปล่า 1 1 1 3/4 = 0.75 ข้าว 1 1/4 = 0.25 หากนำสมาชิกที่เหลือมาพิจารณากรณี itemset ที่มีสมาชิก 2 ตัว จะพบว่าเหลือ itemsets {ขนมปัง, เนย} และ {ขนมปัง, น้ำเปล่า} เท่านั้น ที่มี support >= 0.5 และหากพิจารณาต่อไปยังกรณี itemset ที่มีสมาชิก 3 ตัว จะพบว่าไม่มี itemset ใดเลยที่มี support >=0.5 สินค้า ตะกร้าที่ (Transaction ID) Support 1 2 3 4 ขนมปัง, ไข่ 1 1/4 = 0.25 ขนมปัง, เนย 1 1 2/4 = 0.5 ขนมปัง,...

7 June 2021

รู้จัก BDI

Organization

Policy and Plan

Personnel

Operations